魯鵬凱，江大偉，陳 珂，壽黎但，陳 剛

浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310027

1 引言

隨著互聯(lián)網(wǎng)、移動(dòng)互聯(lián)網(wǎng)、物聯(lián)網(wǎng)應(yīng)用的普及，人們正在以前所未有的速度產(chǎn)生大數(shù)據(jù)[1-2]?；ヂ?lián)網(wǎng)數(shù)據(jù)中心（Internet Data Center，IDC）的研究顯示，2011年全球共產(chǎn)生1800 EB數(shù)據(jù)，且每年產(chǎn)生的數(shù)據(jù)量還在以60%的速度增長(zhǎng)，到2020年，全球每年將產(chǎn)生35 ZB數(shù)據(jù)[2]。大數(shù)據(jù)為數(shù)據(jù)管理技術(shù)帶來(lái)了數(shù)據(jù)量大、數(shù)據(jù)產(chǎn)生速度快、數(shù)據(jù)類型復(fù)雜三重挑戰(zhàn)。

為應(yīng)對(duì)大數(shù)據(jù)所帶來(lái)的挑戰(zhàn)，更好地支持大數(shù)據(jù)應(yīng)用開(kāi)發(fā)，近年來(lái)，工業(yè)界和學(xué)術(shù)界掀起了一股研發(fā)新型大數(shù)據(jù)管理系統(tǒng)的熱潮。理想的大數(shù)據(jù)管理系統(tǒng)應(yīng)該支持兩個(gè)重要特性：（1）快速應(yīng)用開(kāi)發(fā)。大數(shù)據(jù)管理系統(tǒng)應(yīng)能允許應(yīng)用開(kāi)發(fā)人員僅使用業(yè)務(wù)數(shù)據(jù)的邏輯數(shù)據(jù)模型就可以開(kāi)發(fā)大數(shù)據(jù)應(yīng)用，而無(wú)須關(guān)心大數(shù)據(jù)的實(shí)際物理存儲(chǔ)結(jié)構(gòu)、索引結(jié)構(gòu)等實(shí)現(xiàn)細(xì)節(jié)。（2）高伸縮及高效數(shù)據(jù)存取。大數(shù)據(jù)管理系統(tǒng)必須具有極高的系統(tǒng)伸縮性和高速的數(shù)據(jù)存取能力，以滿足大數(shù)據(jù)應(yīng)用的對(duì)大數(shù)據(jù)訪問(wèn)實(shí)時(shí)性的需求。

然而，目前主流的兩種大數(shù)據(jù)管理系統(tǒng)（關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)和NoSQL數(shù)據(jù)庫(kù)系統(tǒng)）都未能同時(shí)滿足上述兩個(gè)需求。關(guān)系數(shù)據(jù)庫(kù)采用關(guān)系數(shù)據(jù)模型作為應(yīng)用開(kāi)發(fā)接口[3-4]。開(kāi)發(fā)人員只需將業(yè)務(wù)數(shù)據(jù)建模為由行和列組成的二維表格，并將需要快速檢索的列申明為索引列，就可以開(kāi)發(fā)應(yīng)用。數(shù)據(jù)的物理存儲(chǔ)和索引結(jié)構(gòu)由系統(tǒng)自動(dòng)完成，無(wú)需應(yīng)用開(kāi)發(fā)人員干預(yù)。因此，關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)支持快速應(yīng)用開(kāi)發(fā)。不幸的是，越來(lái)越多的實(shí)踐表明關(guān)系數(shù)據(jù)庫(kù)在系統(tǒng)伸縮性和數(shù)據(jù)存儲(chǔ)性能方面不能滿足大數(shù)據(jù)應(yīng)用的要求[5]。原因主要有兩條：首先，關(guān)系數(shù)據(jù)庫(kù)普遍采用集中式架構(gòu)和主從式架構(gòu)。該架構(gòu)只允許垂直擴(kuò)容，即通過(guò)升級(jí)單臺(tái)計(jì)算機(jī)的處理能力來(lái)處理更大規(guī)模的數(shù)據(jù)集。垂直擴(kuò)容的代價(jià)高昂，無(wú)法在有限的經(jīng)濟(jì)條件下滿足大數(shù)據(jù)應(yīng)用對(duì)不斷增長(zhǎng)的大數(shù)據(jù)的處理需求。其次，關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)采用范式模型來(lái)存儲(chǔ)數(shù)據(jù)。單一實(shí)體的信息可能被分散到多個(gè)物理表格中存儲(chǔ)。例如，在TPC-C數(shù)據(jù)模式中，一條客戶訂單的信息就分散存儲(chǔ)在Order、OrderLine、Item 3張表中。范式模型的優(yōu)點(diǎn)是數(shù)據(jù)無(wú)冗余，但是當(dāng)需要檢索記錄時(shí)，需要進(jìn)行表格連接操作，因此檢索性能低下。

為解決關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)在系統(tǒng)伸縮性和數(shù)據(jù)存取性能方面的問(wèn)題，谷歌公司開(kāi)發(fā)出BigTable數(shù)據(jù)庫(kù)[6]。BigTable從兩方面做出改進(jìn)。首先，使用計(jì)算機(jī)集群架構(gòu)替代集中式結(jié)構(gòu)和主從架構(gòu)，集群中的任何一臺(tái)機(jī)器都可以提供數(shù)據(jù)存取服務(wù)。因此，Big-Table可以進(jìn)行水平擴(kuò)容，即通過(guò)增加集群節(jié)點(diǎn)（而非升級(jí)單個(gè)節(jié)點(diǎn)）的方式處理更大的數(shù)據(jù)集。與垂直擴(kuò)容相比，水平擴(kuò)容在有限的經(jīng)濟(jì)條件下，極大地增強(qiáng)了系統(tǒng)的伸縮性。其次，BigTable完全放棄了關(guān)系數(shù)據(jù)模型，引入BigTable數(shù)據(jù)模型。該數(shù)據(jù)模型的特點(diǎn)是允許應(yīng)用開(kāi)發(fā)人員精確地控制數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。使用BigTable，應(yīng)用開(kāi)發(fā)人員可以通過(guò)特定的數(shù)據(jù)存儲(chǔ)格式設(shè)計(jì)，將單一實(shí)體的全部信息存儲(chǔ)在單一表格的單一行下，從而消除數(shù)據(jù)檢索時(shí)的表格連接操作。雖然BigTable提供了優(yōu)越的數(shù)據(jù)存取性能，但是性能的提升是以開(kāi)發(fā)人員設(shè)計(jì)出高效的數(shù)據(jù)存儲(chǔ)格式為前提。當(dāng)開(kāi)發(fā)復(fù)雜的應(yīng)用時(shí)，數(shù)據(jù)存儲(chǔ)格式的優(yōu)化過(guò)程往往花費(fèi)開(kāi)發(fā)人員大量心力，降低了開(kāi)發(fā)效率[7-8]。

綜上所述，關(guān)系數(shù)據(jù)庫(kù)支持快捷的開(kāi)發(fā)體驗(yàn)，但是性能不佳。BigTable支持高效數(shù)據(jù)存取，但開(kāi)發(fā)效率不高。因此，主流的兩種大數(shù)據(jù)管理系統(tǒng)都未能同時(shí)提供大數(shù)據(jù)應(yīng)用開(kāi)發(fā)所需的快速應(yīng)用開(kāi)發(fā)和高效數(shù)據(jù)存取這兩項(xiàng)需求。

為解決主流大數(shù)據(jù)管理系統(tǒng)中存在的問(wèn)題，本文提出RBase大數(shù)據(jù)管理系統(tǒng)。RBase系統(tǒng)的基本思想是在BigTable系統(tǒng)的基礎(chǔ)上提供一個(gè)關(guān)系數(shù)據(jù)模型編程接口。應(yīng)用開(kāi)發(fā)人員使用關(guān)系數(shù)據(jù)模型開(kāi)發(fā)大數(shù)據(jù)應(yīng)用，RBase系統(tǒng)選擇數(shù)據(jù)存儲(chǔ)格式和索引結(jié)構(gòu)，并將數(shù)據(jù)存入BigTable，從而達(dá)到同時(shí)提供快速應(yīng)用開(kāi)發(fā)和高效數(shù)據(jù)存取的雙重目標(biāo)。RBase系統(tǒng)結(jié)構(gòu)如圖1所示，包含以下模塊：SQL解析器負(fù)責(zé)解析SQL語(yǔ)句，元數(shù)據(jù)管理器管理元數(shù)據(jù)，事務(wù)管理器負(fù)責(zé)事務(wù)處理，查詢處理器處理SQL SELECT查詢，RStore關(guān)系數(shù)據(jù)存儲(chǔ)系統(tǒng)負(fù)責(zé)索引關(guān)系元組，并將其存入BigTable。由于篇幅所限，本文只介紹RStore關(guān)系數(shù)據(jù)存儲(chǔ)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)。事務(wù)管理器和查詢處理器將在后續(xù)的文章中詳細(xì)討論。RStore系統(tǒng)的主要貢獻(xiàn)點(diǎn)如下：

（1）提出了一種基表存儲(chǔ)結(jié)構(gòu)，將關(guān)系數(shù)據(jù)庫(kù)中的所有表格存儲(chǔ)在同一張BigTable中，提供基于主鍵的數(shù)據(jù)存取。

Fig.1 RBase architecture圖1 RBase架構(gòu)

（2）提出了跨表索引結(jié)構(gòu)，將與基表元組存在引用關(guān)系的外表元組索引在該元組的列鍵下，消除了多表查詢時(shí)的連接操作。

2 BigTable數(shù)據(jù)庫(kù)系統(tǒng)簡(jiǎn)介

BigTable是一個(gè)分布式稀疏多維鍵值數(shù)據(jù)庫(kù)。與傳統(tǒng)的一維鍵值數(shù)據(jù)庫(kù)系統(tǒng)（如BerkeleyDB）不同，BigTable的鍵有3個(gè)維度：行鍵（row key）、列鍵（column key）、時(shí)間戳(row:string，column:string，time:int64)→string。

共享相同行鍵的鍵值對(duì)組成一行，行內(nèi)的列組成列族。整個(gè)數(shù)據(jù)庫(kù)按照行鍵、列鍵、時(shí)間戳的順序排序。表1顯示一個(gè)存儲(chǔ)網(wǎng)頁(yè)的BigTable。BigTable支持用行鍵、列鍵兩種方式查找值。給定行鍵范圍，BigTable可以返回所有滿足行鍵搜索條件的值。給定單一行鍵以及列鍵范圍，BigTable可以返回該行內(nèi)所有滿足列鍵搜索條件的值。與關(guān)系數(shù)據(jù)模型和一維鍵值對(duì)數(shù)據(jù)模型相比較，BigTable提供的多維鍵值數(shù)據(jù)模型在搜索機(jī)制上更為靈活、高效。每個(gè)列族（理論上）可以包含無(wú)限多個(gè)列。用戶可以在運(yùn)行時(shí)動(dòng)態(tài)地向列族中添加和刪除列。

Table 1 BigTable for storing Web data表1 存儲(chǔ)網(wǎng)頁(yè)數(shù)據(jù)的BigTable

3 RStore關(guān)系數(shù)據(jù)模型存儲(chǔ)系統(tǒng)

RStore是RBase大數(shù)據(jù)管理系統(tǒng)的存儲(chǔ)模塊。給定如圖2所示的TPC-C關(guān)系數(shù)據(jù)模式，RStore將符合該數(shù)據(jù)模式的關(guān)系元組存儲(chǔ)于BigTable中，向上層的事務(wù)管理器和查詢處理器提供高效元組存取服務(wù)。RStore由Java開(kāi)發(fā)，建立在BigTable的開(kāi)源實(shí)現(xiàn)HBase之上[9-10]。本章以TPC-C數(shù)據(jù)模式為例，詳細(xì)介紹RStore的設(shè)計(jì)與實(shí)現(xiàn)細(xì)節(jié)。

對(duì)于上層應(yīng)用，RBase支持關(guān)系編程范式。應(yīng)用開(kāi)發(fā)前，用戶使用標(biāo)準(zhǔn)的SQL DDL語(yǔ)句聲明業(yè)務(wù)數(shù)據(jù)的表格結(jié)構(gòu)。建立一個(gè)TPC-C數(shù)據(jù)庫(kù)和Customer表，分別用CREATE DATABASE tpcc以及CREATE TABLE tpcc.customer(）完成。

Fig.2 TPC-C entity relationship diagram圖2 TPC-C中的實(shí)體關(guān)系圖

3.1 基表存儲(chǔ)結(jié)構(gòu)

在系統(tǒng)實(shí)現(xiàn)上，RStore根據(jù)用戶提供的表格定義和查詢申明，將數(shù)據(jù)存入BigTable中。RStore提供兩種數(shù)據(jù)存取策略：（1）基表存儲(chǔ)結(jié)構(gòu)；（2）跨表查詢索引。

在基表存儲(chǔ)結(jié)構(gòu)中，RStore將基表中的每一條元組存為BigTable中的一行，并將主鍵編碼進(jìn)BigTable的行鍵，為應(yīng)用提供基于主鍵的高效數(shù)據(jù)存取。在跨表查詢索引中，RStore根據(jù)主外鍵約束關(guān)系，將與基表元組存在引用關(guān)系的外表元組索引至該元組的列鍵下，利用BigTable的列鍵搜索機(jī)制，提供跨表元組存取。

基表在BigTable中的存儲(chǔ)結(jié)構(gòu)如表2所示。每一條元組存為一行。其中，DataFamily存儲(chǔ)主鍵之外的其他屬性數(shù)據(jù)，IndexFamily存儲(chǔ)該元組的跨表查詢索引。整個(gè)元組由行鍵（row key）索引，行鍵編碼表名和主鍵（即，:）。通過(guò)這種行鍵編碼方式，RStore將一個(gè)關(guān)系數(shù)據(jù)庫(kù)下的所有表格存儲(chǔ)在同一張BigTable中。

給定表3中的TPC-C Customer關(guān)系表實(shí)例，該表在BigTable中的存儲(chǔ)結(jié)構(gòu)如表4所示。其中，“Customer:001”為001號(hào)元組的行鍵，編碼關(guān)系表名與主鍵值（以冒號(hào)分隔）。DataFamily列族下有3列，列名為 CustomerName、CustomerPhone 和 CustomerCredit。列名采取關(guān)系表名加屬性名的格式，列中分別存儲(chǔ)關(guān)系表中對(duì)應(yīng)的屬性數(shù)據(jù)。這條記錄的外鍵數(shù)據(jù)被存儲(chǔ)在IndexFamily列族下，列名的格式為“該條記錄所屬關(guān)系表名連接該條記錄的主鍵值-該條記錄中外鍵引用的屬性所屬關(guān)系表名連接該條記錄中引用的屬性值”，列中存儲(chǔ)單個(gè)字母S或者B。當(dāng)插入第一條包含外鍵關(guān)系的數(shù)據(jù)時(shí)，元數(shù)據(jù)管理器會(huì)記錄下“Customer-District”作為索引的元數(shù)據(jù)信息，以提高系統(tǒng)檢查數(shù)據(jù)庫(kù)中是否已經(jīng)存在對(duì)應(yīng)索引的速度。查詢時(shí)，用戶使用標(biāo)準(zhǔn)SQL SELECT語(yǔ)言，RStore根據(jù)關(guān)系表和BigTable之間的結(jié)構(gòu)映射，從BigTable中檢索指定數(shù)據(jù)。

Table 2 BigTable data layout表2 BigTable的數(shù)據(jù)布局

Table 3 TPC-C Cusomer relational table表3 關(guān)系模型下的TPC-C Customer表

3.2 跨表查詢索引

上節(jié)提出的基表存儲(chǔ)結(jié)構(gòu)能夠滿足應(yīng)用在單個(gè)基表上基于主鍵的高效數(shù)據(jù)存取。然而，實(shí)際的應(yīng)用往往涉及多表查詢。經(jīng)典的關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)采用表格連接操作處理多表查詢，但表格連接操作代價(jià)高昂，無(wú)法滿足大數(shù)據(jù)應(yīng)用對(duì)數(shù)據(jù)訪問(wèn)性能的要求。RStore提供跨表查詢索引機(jī)制，消除多表查詢所需的連接操作。OLTP應(yīng)用中，多表查詢具有以下模式：查詢涉及的多表格元組之間存在主外鍵約束所表示的“一對(duì)多”或者“多對(duì)多”關(guān)系，且查詢總是從一個(gè)基表的元組開(kāi)始，逐步擴(kuò)散至其他表格元組。例如，搜索客戶001最近購(gòu)買的10件商品。該查詢涉及Customer、Order、OrderLine、Item 4張表。查詢從Customer表格出發(fā)，首先搜索001用戶的信息，然后根據(jù)主外鍵關(guān)系搜索其他表格直至找到全部元組RStore利用OLTP應(yīng)用的上述數(shù)據(jù)訪問(wèn)模式，將與起始基表元組（示例中001號(hào)客戶）存在引用關(guān)系的外表元組索引至該元組（即，001元組）的列鍵下，從而消除了查詢處理中表格連接。RStore中，應(yīng)用開(kāi)發(fā)人員可以使用CREATE INDEX q1idx Customer，on Order，OrderLine，Item from customer in tpcc來(lái)建立一個(gè)跨表查詢索引。缺省情況下，RStore只將外表中的主鍵索引至基表元組中，如果開(kāi)發(fā)人員希望索引更多的外表屬性，可以將所需屬性置于表格名稱后的可選屬性列表中。

Table 4 TPC-C Customer record in BigTable data model表4 BigTable數(shù)據(jù)模型下的TPC-C Customer記錄

TPC-C的模型中District和Customer是一對(duì)具有一對(duì)多關(guān)系的實(shí)體，在每個(gè)街區(qū)中住著許多客戶。在關(guān)系型數(shù)據(jù)庫(kù)中，用Customer表存儲(chǔ)客戶的信息，用District表存儲(chǔ)街區(qū)的信息。再在Customer表中添加一列，用來(lái)存儲(chǔ)街區(qū)數(shù)據(jù)記錄的主鍵，代表這兩個(gè)實(shí)體間一對(duì)多的關(guān)系。TPC-C數(shù)據(jù)庫(kù)中的District表和Customer表如表5所示。

表6展示了將表5中District和Customer記錄由RStore處理后存入BigTable中的數(shù)據(jù)布局。BigTable中Customer記錄里索引列族下作為索引的列名如前文介紹，是在插入該條數(shù)據(jù)時(shí)，由系統(tǒng)將記錄中外鍵的值按照“表名連接上主鍵值-外鍵所在表名連接上外鍵值”的格式作為列名插入到列族索引下的，列中的值“B”代表這是一個(gè)雙向的索引，即在Customer和District的列族索引中存儲(chǔ)著關(guān)于對(duì)方的索引。“S”則代表只在本表的索引列族中存儲(chǔ)有關(guān)于對(duì)方表的索引。當(dāng)在插入一對(duì)多關(guān)系中的“一”方時(shí)，系統(tǒng)所建立的以索引為列名的列的值僅設(shè)置為“S”。除了在一對(duì)多的關(guān)系中，“一”方的索引是在插入數(shù)據(jù)時(shí)完成的，多對(duì)多關(guān)系也是在插入數(shù)據(jù)時(shí)由系統(tǒng)完成的。系統(tǒng)將主外鍵相同的表標(biāo)記為多對(duì)多的關(guān)系表。假設(shè)A和B為多對(duì)多關(guān)系，當(dāng)向A和B的關(guān)系表插入每條數(shù)據(jù)時(shí)，完成如下兩步。（1）向A記錄的索引列族中插入列名為“AKeyA-BKeyB”的列，值為“B”。（2）向B記錄的索引列族中插入列名為“BKeyBAKeyA”的列，值為“B”。KeyA、KeyB分別為插入數(shù)據(jù)中A表的主鍵值和B表的主鍵值，這兩個(gè)值既是A和B關(guān)系表的聯(lián)合主鍵也是外鍵。在插入第一條包含外鍵關(guān)系的數(shù)據(jù)后，元數(shù)據(jù)管理器記錄下“A-B”和“B-A”作為多對(duì)多關(guān)系的索引元數(shù)據(jù)。

Table 5 TPC-C District table and Customer table表5 TPC-C中District表和Customer表

TPC-C測(cè)試數(shù)據(jù)模型中Warehouse和Item是具有多對(duì)多關(guān)系的一對(duì)實(shí)體，當(dāng)向以Warehouse和Item的主鍵為聯(lián)合主鍵的邏輯表插入數(shù)據(jù)時(shí)，系統(tǒng)按照多對(duì)多索引的創(chuàng)建方法，向Warehouse記錄的索引列族中插入列名為“WarehouseKeyWarehouse-ItemKeyItem”格式的列，向Item記錄的索引列族中插入“ItemKeyItem-WarehouseKeywarehouse”格式的列，如表7所示。元數(shù)據(jù)管理器記錄下“Warehuose-Item”、“Item-Warehouse”作為創(chuàng)建的索引的元數(shù)據(jù)。

Table 6 One-to-many records in BigTable data model processed by RBase表6 經(jīng)RBase處理后存儲(chǔ)在BigTable數(shù)據(jù)模型中的一對(duì)多關(guān)系記錄

以上兩種情況都是在未事先聲明索引的條件下插入數(shù)據(jù)時(shí)完成的，而District記錄里索引列族下作為索引的列名并不會(huì)在向表中插入數(shù)據(jù)時(shí)由系統(tǒng)完成創(chuàng)建，需要用戶使用提供的索引聲明創(chuàng)建語(yǔ)句。之所以這種情況需要用戶手動(dòng)聲明創(chuàng)建，是因?yàn)楸硎緝杀碛涗涢g關(guān)系的外鍵在向“多”方表插入數(shù)據(jù)時(shí)就已存在。如果用戶并不需要在查詢“一”方記錄的同時(shí)獲得相關(guān)的“多”方數(shù)據(jù)，系統(tǒng)為這種情況而建立的索引就不會(huì)被查詢引擎所使用，并且還要占據(jù)一定的物理存儲(chǔ)空間，降低數(shù)據(jù)庫(kù)的性能。

當(dāng)在兩個(gè)有主外鍵關(guān)系的表A和表B間聲明創(chuàng)建索引時(shí)，因?yàn)閮烧哂幸粚?duì)多的關(guān)系，所以必然在某一方的索引列族下存在著“表名連接上主鍵值-外鍵所在表名連接上外鍵值”格式的列名。假設(shè)A是一對(duì)多關(guān)系中的“多”方，則A記錄的索引列族下存在“AKeyA-BKeyB”格式的列名，系統(tǒng)按如下方式建立索引。

1.for column inA.IndexFamily

2.if column.name like“AKeyA-BKeyB”

3. insert into(B:KeyB,IndexFamily:BKeyB-AKeyA)values“B”;

4.end if

5.end for

6.MetadataManager.recordIndex(“B-A”);

當(dāng)需要在查詢TableA表中記錄的同時(shí)獲得其他表中與其相關(guān)的記錄時(shí)，使用“CREATE INDEXON(，， ，…)FROMIN”創(chuàng)建索引。當(dāng)要查詢TPC-C數(shù)據(jù)模型中指定客戶（Customer）的訂單（Order）信息，包括訂單項(xiàng)（Order line）和其中具體物品的信息時(shí)，使用“CREATE INDEX idx on Customer，Order，OrderLine，Item from Customer in tpcc;”命令創(chuàng)建滿足需求的索引。系統(tǒng)從Customer記錄出發(fā)，在Customer記錄的索引列族下尋找是否有關(guān)于Order、OrderLine或者Item的索引。由于Customer只和Order有關(guān)系且和Order是一對(duì)多的關(guān)系，因此只會(huì)在Order的索引列族中存在關(guān)于Customer的列名索引，而在Customer索引列族下沒(méi)有找到“CustomerKeyCustomer-OrderKeyOrder”、“Customer-KeyCustomer-OrderLineKeyOrderLine”或者“Order OrderKeyOrder-ItemKeyItem”格式的列名索引。然后在Customer的索引列族中根據(jù)表6中建立索引的方法，建立關(guān)于Order的列名索引。接著從Order出發(fā)，在Order記錄的索引列族下尋找是否有關(guān)于OrderLine或者Item的索引。與之前Customer上的情況相同，和Order有關(guān)系的只有OrderLine且和OrderLine是一對(duì)多關(guān)系，同樣在OrderLine記錄的索引列族中建立關(guān)于Order的列族索引。最后從OrderLiner出發(fā)，在Order記錄的索引列族下尋找是否有關(guān)于Item的索引，因?yàn)镺rder-Line和Item是多對(duì)一的關(guān)系，所以在插入OrderLine數(shù)據(jù)時(shí)便已在OrderLine的索引列族中建立了關(guān)于Item的索引。至此，這條建立索引的命令的工作已經(jīng)完成?！癈REATE INDEX)ONFROMIN”由StartTable出發(fā)，建立指定TableSet上索引的算法如下。

1.Queue Q;/*聲明一個(gè)棧*/

2.Set UnvisitedSet=TableSet;/*新建一個(gè)集合保存未被訪問(wèn)的表*/

Table 7 Many-to-many records in BigTable data model processed by RBase表7 BigTable中具有多對(duì)多關(guān)系的數(shù)據(jù)經(jīng)RBase處理后的結(jié)果

3.UnvisitedSet=UnvisitedSet.remove(StartTable);/*將出發(fā)表設(shè)為已訪問(wèn)*/

4.Q.push(StartTable);

5.while!isEmpty(Q)

6. p=Q.front();/*取隊(duì)首表對(duì)象*/

7. Q.pop();

8. for(table in UnvisitedSet)

9. if MetadataManager.existIndex(table，p)/*如果未被訪問(wèn)的表集合中有表的索引列族中存在關(guān)于p的索引，通過(guò)查詢索引元數(shù)據(jù)即可判斷*/

10. if!MetadataManager.existIndex(p,table)

11. buildIndex(p,table);

12. MetadataManager.recordIndex(p.name+“-”+table.name);

13. end if

14. end if

15.end for

16.for(tableIndex in p.indexFamily)

17. q=parseIndexToTable(tableIndex);/*解析p記錄索引列族中列名索引得到對(duì)應(yīng)的表*/

18. UnvisitedSet=UnvisitedSet.remove(q);

19. Q.push(q);

20.end for

21.end while

這樣，當(dāng)有新的數(shù)據(jù)插入時(shí)，所有元數(shù)據(jù)管理器中記錄的已創(chuàng)建索引（包括原先由系統(tǒng)在插入數(shù)據(jù)時(shí)自動(dòng)創(chuàng)建的索引和手動(dòng)聲明創(chuàng)建的索引）都會(huì)根據(jù)新插入的值創(chuàng)建列名索引進(jìn)行更新。

當(dāng)用戶需要?jiǎng)h除一條記錄時(shí)，刪除之前，系統(tǒng)會(huì)自動(dòng)對(duì)索引進(jìn)行處理。當(dāng)刪除的是表6中row key為District:002的記錄時(shí)，系統(tǒng)先從元數(shù)據(jù)管理器中獲取所有關(guān)于District的索引元數(shù)據(jù)。對(duì)于“District-TableName”格式的索引，系統(tǒng)遍歷District的每一條記錄，檢索索引列族下列名為“Distric002-TableName KeyTableName”的列并刪除。同樣對(duì)于“TableName-District”格式的索引，系統(tǒng)遍歷TableName的記錄，檢索列族索引下列名為“TableNameKeyTableName-District002”格式的列并刪除。

假設(shè)要被刪除的記錄是row key為“TableA:ID”，刪除數(shù)據(jù)前關(guān)于索引的操作如下。

1.Set LocalIndexTableSet;/*和本記錄的實(shí)體有主外鍵關(guān)系，且將索引存儲(chǔ)在本實(shí)體記錄的索引列族下的實(shí)體名集合*/

2.Set UnlocalIndexTableSet;/*和本記錄的實(shí)體有主外鍵關(guān)系，且將索引存儲(chǔ)在自身索引列族下的實(shí)體名集合*/

3.LocalIndexTableSet=MetaManager.queryLocalIndex(“TableA”);/*從元數(shù)據(jù)管理器中查詢“TableA-TableName”格式索引的TableName集合*/

4.UnlocalIndexTableSet=MetaManager.queryUnlocalIndex(“TableA”);/*從元數(shù)據(jù)管理器中查詢“TableName-TableA”格式索引的TableName集合*/

5.for table in LocalIndexTableSet

6. for column inA.IndexFamily.

7. if column.name.startWith(TableA.name+ID+“-”TableName);

8. A.IndexFamily.remove(column);

9. end if

10. end for

11.end for

12.for table in UnLocalIndexTableSet

13. for column in table.IndexFamily.

14. if column.name.endWith(TableA.name+ID);

15. table.IndexFamily.remove(column);

16. end if

17. end for

18.end for

當(dāng)用戶更新外鍵數(shù)據(jù)時(shí)，系統(tǒng)首先依照刪除數(shù)據(jù)前刪除索引的方法，刪除本條記錄對(duì)應(yīng)的在其他表中的索引，然后按照插入新值時(shí)建立索引的方法，在其他記錄的索引列族中插入新列。

3.3 性能分析

當(dāng)用戶在如表5所示關(guān)系型數(shù)據(jù)庫(kù)下查詢ID為1的街區(qū)的信息和其中住著的顧客信息時(shí)，輸入“SELECT*FROM District JOIN Customer ON District.ID=Customer.DistrictID WHERE District.ID=1”，數(shù)據(jù)庫(kù)查詢引擎先讀取ID為1的District表中的記錄，然后遍歷Customer表，找出Customer表中每條滿足District-ID列中的值等于1的記錄，返回查詢結(jié)果給用戶。

如果是在如表6所示的BigTable中，執(zhí)行相同查詢請(qǐng)求時(shí)，當(dāng)查詢引擎根據(jù)ID為1取得District的一條記錄后，再解析該條記錄中的IndexFamily中的列名，尋找以“District001-Customer”為前綴的列名，列名剩下的部分便是和該條District記錄有一對(duì)多關(guān)系的Customer記錄的主鍵值。查詢引擎根據(jù)這些主鍵值就能夠獲取到相應(yīng)的Customer記錄。

對(duì)比這兩種情況，假設(shè)Customer中一共有M位客戶的記錄，其中ID為1的街區(qū)中住著N位客戶，第一種方式通過(guò)遍歷尋找相應(yīng)的記錄，時(shí)間復(fù)雜度為(N×M)。第二種方式直接根據(jù)Customer記錄的主鍵號(hào)獲取相應(yīng)記錄，時(shí)間復(fù)雜度為(N×lgM)。尤其是當(dāng)M很大，即系統(tǒng)中存儲(chǔ)的客戶記錄很多時(shí)（這也符合大數(shù)據(jù)應(yīng)用中的實(shí)際情況)，查詢速度的差異會(huì)越加明顯。

4 實(shí)驗(yàn)結(jié)果

當(dāng)用戶在如表5所示關(guān)系型數(shù)據(jù)庫(kù)下查詢ID為1的街區(qū)的信息和其中住著的顧客信息時(shí)，輸入“SELECT*FROM District JOIN Customer ON District.ID=Customer.DistrictID WHERE District.ID=1”，數(shù)據(jù)庫(kù)查詢引擎先讀取ID為1的District表中的記錄，然后遍歷Customer表，找出Customer表中每條滿足DistrictID列中的值等于1的記錄，返回查詢結(jié)果給用戶。

如果是在如表6所示的BigTable中，執(zhí)行相同查詢請(qǐng)求時(shí)，當(dāng)查詢引擎根據(jù)ID為1取得District的一條記錄后，再解析該條記錄中的IndexFamily中的列名，尋找以“District001-Customer”為前綴的列名，列名剩下的部分便是和該條District記錄有一對(duì)多關(guān)系的Customer記錄的主鍵值，查詢引擎根據(jù)這些主鍵值就能夠獲取到相應(yīng)的Customer記錄。

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)在一個(gè)11個(gè)節(jié)點(diǎn)的計(jì)算機(jī)集群上進(jìn)行，其中1個(gè)節(jié)點(diǎn)為主節(jié)點(diǎn)，運(yùn)行HDFS的NameNode和HBase的HMaster。其他節(jié)點(diǎn)為從節(jié)點(diǎn)，運(yùn)行HDFS的DataNode和HBase的RegionServer。集群中每個(gè)節(jié)點(diǎn)配置單顆12核英特爾至強(qiáng)E5-2650 v4處理器2.2 GHz，128 GB DDR4內(nèi)存，2 TB硬盤，hdparm顯示硬盤的順利掃描速度約為每秒120 MB。整個(gè)集群由千兆以太網(wǎng)連接。對(duì)于HDFS，設(shè)定文件塊大小為128 MB。對(duì)于HBase，設(shè)定RegionServer最大可使用100 GB內(nèi)存。系統(tǒng)其他參數(shù)采用HDFS和HBase的缺省設(shè)定。

4.2 工作負(fù)載

本實(shí)驗(yàn)使用TPC-C測(cè)試基準(zhǔn)中的5張數(shù)據(jù)表Customer、Order、OrderLine、Item以及Stock。本實(shí)驗(yàn)沒(méi)有使用TPC-C評(píng)測(cè)負(fù)載。這是因?yàn)門PC-C測(cè)試基準(zhǔn)中的5個(gè)事務(wù)主要用來(lái)測(cè)試數(shù)據(jù)管理系統(tǒng)的事務(wù)處理能力，而RBase是存儲(chǔ)系統(tǒng)并無(wú)事務(wù)處理器。因此，本實(shí)驗(yàn)遵循谷歌對(duì)BigTable存儲(chǔ)系統(tǒng)的評(píng)測(cè)原則，僅測(cè)試系統(tǒng)的讀寫(xiě)性能。本實(shí)驗(yàn)設(shè)計(jì)了2個(gè)查詢?cè)u(píng)測(cè)用例和1個(gè)寫(xiě)入評(píng)測(cè)用例。查詢用例1返回給定客戶最近購(gòu)買的10件商品。查詢用例2取自TPCC的StockLevel事務(wù)，返回低于指定庫(kù)存的商品數(shù)目。寫(xiě)入用例1向Order表中添加一筆新的訂單。

4.3 查詢1及實(shí)驗(yàn)結(jié)果

查詢1（Q1）的SQL語(yǔ)句如下：

其中，（:c_w_id,:c_d_id,:c_id)為輸入?yún)?shù)確定待查詢用戶。為運(yùn)行查詢，對(duì)RBase系統(tǒng)建立如下的跨表查詢索引：CREATE INDEX q1idx on Customer，Order，OrderLine，Item from Customer in tpcc。對(duì)MegaStore，將Customer和Order作為父子表存儲(chǔ)在一張Big-Table中，OrderLine存儲(chǔ)于另一個(gè)BigTable中，再額外用一張BigTable在OrderLine表的（ol_w_id，ol_d_id，ol_o_id）上建立次級(jí)索引。實(shí)驗(yàn)中，變換集群大小，測(cè)試當(dāng)從節(jié)點(diǎn)數(shù)目增加時(shí)，系統(tǒng)的吞吐率（即，系統(tǒng)CPU滿載時(shí)，每秒處理的查詢總數(shù)）和查詢響應(yīng)時(shí)間。圖3（a）和圖3（b）顯示了實(shí)驗(yàn)結(jié)果?？梢钥吹剑琑store的吞吐率和平均響應(yīng)時(shí)間明顯優(yōu)于MegaStore，這主要是由于跨表查詢索引消除了耗時(shí)的表格連接操作。

4.4 查詢2及實(shí)驗(yàn)結(jié)果

查詢2（Q2）的SQL語(yǔ)句如下：

為運(yùn)行查詢，對(duì)RBase系統(tǒng)建立跨表查詢索引CREATE INDEX q2idx on OrderLine，Stock from Stock in tpcc。對(duì)MegaStore，將Stock和OrderLine存為父子表。圖4（a）和圖4（b）分別顯示了兩個(gè)系統(tǒng)的吞吐率和平均響應(yīng)時(shí)間。本查詢中兩個(gè)系統(tǒng)之間的差距顯著縮小，這是因?yàn)椴樵?只涉及兩張表格，因此表格連接并未產(chǎn)生較大開(kāi)銷。

4.5 寫(xiě)入1及實(shí)驗(yàn)結(jié)果

寫(xiě)入用例1向Order表中插入一條訂單記錄，較為簡(jiǎn)單，故此處略去相關(guān)的SQL語(yǔ)句。圖5（a）和圖5（b）顯示了兩個(gè)系統(tǒng)的實(shí)驗(yàn)結(jié)果。雖然兩個(gè)系統(tǒng)的吞吐率大致相當(dāng)，但是MegaStore的平均響應(yīng)時(shí)間優(yōu)于RStore。這是因?yàn)镽Store在插入訂單記錄時(shí)，會(huì)更新跨表查詢索引，因此引入了額外的I/O操作。

Fig.3 Q1 throughput results and avg.latency results圖3 查詢1的系統(tǒng)吞吐率和平均響應(yīng)時(shí)間

Fig.4 Q2 throughput results and avg.latency results圖4 查詢2的系統(tǒng)吞吐率和平均響應(yīng)時(shí)間

Fig.5 Order insertion throughput results and avg.latency results圖5 插入記錄時(shí)系統(tǒng)的吞吐率和平均響應(yīng)時(shí)間

5 相關(guān)工作

與本文相關(guān)的工作分為3類：NoSQL數(shù)據(jù)庫(kù)系統(tǒng)、基于NoSQL的關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)、數(shù)據(jù)庫(kù)性能調(diào)優(yōu)。

NoSQL數(shù)據(jù)庫(kù)系統(tǒng)研究如何開(kāi)發(fā)高效、分布式鍵值存儲(chǔ)系統(tǒng)。文獻(xiàn)[11]綜述了此類工作。已提出的NoSQL數(shù)據(jù)庫(kù)分為一維鍵值數(shù)據(jù)庫(kù)，如Dynamo[12-13]和PNUTS[14]，以及多維鍵值數(shù)據(jù)庫(kù)，如BigTable[6]。本文工作是對(duì)這些工作的擴(kuò)展。即，在NoSQL數(shù)據(jù)庫(kù)之上提供關(guān)系數(shù)據(jù)模型，提升大數(shù)據(jù)應(yīng)用開(kāi)發(fā)效率。

基于NoSQL的關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)研究如何在NoSQL數(shù)據(jù)庫(kù)的基礎(chǔ)上提供關(guān)系數(shù)據(jù)模型。此類工作與本文工作高度相關(guān)，但在應(yīng)用場(chǎng)景和實(shí)現(xiàn)技術(shù)方面與本文工作存在區(qū)別。文獻(xiàn)[15-19]研究如何在分布式文件系統(tǒng)的基礎(chǔ)上提供SQL查詢接口。這些工作針對(duì)OLAP類大數(shù)據(jù)應(yīng)用，優(yōu)化目標(biāo)為批量讀寫(xiě)。而本文工作針對(duì)OLTP類大數(shù)據(jù)應(yīng)用，優(yōu)化目標(biāo)為少數(shù)元組的讀寫(xiě)。MegaStore[7]和Spanner[8]是建立在BigTable基礎(chǔ)之上的OLTP數(shù)據(jù)庫(kù)，設(shè)計(jì)目標(biāo)與本文相同。區(qū)別在于，MegaStore和Spanner需要用戶自行設(shè)計(jì)如何將多個(gè)關(guān)系表存儲(chǔ)在同一個(gè)BigTable中，以提高查詢性能，并非完整地支持關(guān)系數(shù)據(jù)模型的申明式編程范式。而本文工作僅需用戶申明數(shù)據(jù)表結(jié)構(gòu)和跨表查詢索引，無(wú)需用戶關(guān)心底層存儲(chǔ)實(shí)現(xiàn)細(xì)節(jié)，屬于標(biāo)準(zhǔn)的關(guān)系編程范式。

數(shù)據(jù)庫(kù)性能調(diào)優(yōu)研究如何根據(jù)給定的查詢負(fù)載選擇存儲(chǔ)和索引結(jié)構(gòu)。文獻(xiàn)[20]和文獻(xiàn)[21]綜述了相關(guān)工作。文獻(xiàn)[22]和文獻(xiàn)[23]分別研究了如何選擇數(shù)據(jù)切分、物化視圖、索引結(jié)構(gòu)以自適應(yīng)地提升數(shù)據(jù)庫(kù)性能。本文工作受到這些工作的啟發(fā)，但實(shí)現(xiàn)技術(shù)與這些工作完全不同。原因在于，已有工作主要針對(duì)“熱啟動(dòng)”場(chǎng)景，即數(shù)據(jù)庫(kù)已經(jīng)運(yùn)行給定負(fù)載一段時(shí)間，再進(jìn)行性能調(diào)優(yōu)，而本文工作主要針對(duì)“冷啟動(dòng)”場(chǎng)景，即數(shù)據(jù)庫(kù)尚未運(yùn)行給定負(fù)載就需要決定存儲(chǔ)格式和索引結(jié)構(gòu)。

6 結(jié)論

本文提出了RStore，一個(gè)基于BigTable的關(guān)系數(shù)據(jù)存儲(chǔ)系統(tǒng)。對(duì)于應(yīng)用開(kāi)發(fā)，RStore支持關(guān)系編程范式，用戶只需申明業(yè)務(wù)數(shù)據(jù)的表格結(jié)構(gòu)，無(wú)需關(guān)心數(shù)據(jù)的存儲(chǔ)細(xì)節(jié)。對(duì)于系統(tǒng)實(shí)現(xiàn)，RStore自動(dòng)將關(guān)系數(shù)據(jù)存入BigTable，支持高伸縮和高效的數(shù)據(jù)訪問(wèn)。RStore同時(shí)滿足了大數(shù)據(jù)應(yīng)用對(duì)數(shù)據(jù)管理系統(tǒng)快速應(yīng)用開(kāi)發(fā)和高效數(shù)據(jù)訪問(wèn)的需求。