RStore：基于BigTable的關(guān)系數(shù)據(jù)模型存儲系統(tǒng)*

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

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

1 引言

隨著互聯(lián)網(wǎ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%的速度增長，到2020年，全球每年將產(chǎn)生35 ZB數(shù)據(jù)[2]。大數(shù)據(jù)為數(shù)據(jù)管理技術(shù)帶來了數(shù)據(jù)量大、數(shù)據(jù)產(chǎn)生速度快、數(shù)據(jù)類型復(fù)雜三重挑戰(zhàn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

給定表3中的TPC-C Customer關(guān)系表實例，該表在BigTable中的存儲結(jié)構(gòu)如表4所示。其中，“Customer:001”為001號元組的行鍵，編碼關(guān)系表名與主鍵值（以冒號分隔）。DataFamily列族下有3列，列名為 CustomerName、CustomerPhone 和 CustomerCredit。列名采取關(guān)系表名加屬性名的格式，列中分別存儲關(guān)系表中對應(yīng)的屬性數(shù)據(jù)。這條記錄的外鍵數(shù)據(jù)被存儲在IndexFamily列族下，列名的格式為“該條記錄所屬關(guān)系表名連接該條記錄的主鍵值-該條記錄中外鍵引用的屬性所屬關(guān)系表名連接該條記錄中引用的屬性值”，列中存儲單個字母S或者B。當(dāng)插入第一條包含外鍵關(guān)系的數(shù)據(jù)時，元數(shù)據(jù)管理器會記錄下“Customer-District”作為索引的元數(shù)據(jù)信息，以提高系統(tǒng)檢查數(shù)據(jù)庫中是否已經(jīng)存在對應(yīng)索引的速度。查詢時，用戶使用標(biāo)準(zhǔn)SQL SELECT語言，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é)提出的基表存儲結(jié)構(gòu)能夠滿足應(yīng)用在單個基表上基于主鍵的高效數(shù)據(jù)存取。然而，實際的應(yīng)用往往涉及多表查詢。經(jīng)典的關(guān)系數(shù)據(jù)庫管理系統(tǒng)采用表格連接操作處理多表查詢，但表格連接操作代價高昂，無法滿足大數(shù)據(jù)應(yīng)用對數(shù)據(jù)訪問性能的要求。RStore提供跨表查詢索引機(jī)制，消除多表查詢所需的連接操作。OLTP應(yīng)用中，多表查詢具有以下模式：查詢涉及的多表格元組之間存在主外鍵約束所表示的“一對多”或者“多對多”關(guān)系，且查詢總是從一個基表的元組開始，逐步擴(kuò)散至其他表格元組。例如，搜索客戶001最近購買的10件商品。該查詢涉及Customer、Order、OrderLine、Item 4張表。查詢從Customer表格出發(fā)，首先搜索001用戶的信息，然后根據(jù)主外鍵關(guān)系搜索其他表格直至找到全部元組RStore利用OLTP應(yīng)用的上述數(shù)據(jù)訪問模式，將與起始基表元組（示例中001號客戶）存在引用關(guān)系的外表元組索引至該元組（即，001元組）的列鍵下，從而消除了查詢處理中表格連接。RStore中，應(yīng)用開發(fā)人員可以使用CREATE INDEX q1idx Customer，on Order，OrderLine，Item from customer in tpcc來建立一個跨表查詢索引。缺省情況下，RStore只將外表中的主鍵索引至基表元組中，如果開發(fā)人員希望索引更多的外表屬性，可以將所需屬性置于表格名稱后的可選屬性列表中。

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

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

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

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

TPC-C測試數(shù)據(jù)模型中Warehouse和Item是具有多對多關(guān)系的一對實體，當(dāng)向以Warehouse和Item的主鍵為聯(lián)合主鍵的邏輯表插入數(shù)據(jù)時，系統(tǒng)按照多對多索引的創(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處理后存儲在BigTable數(shù)據(jù)模型中的一對多關(guān)系記錄

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

當(dāng)在兩個有主外鍵關(guān)系的表A和表B間聲明創(chuàng)建索引時，因為兩者有一對多的關(guān)系，所以必然在某一方的索引列族下存在著“表名連接上主鍵值-外鍵所在表名連接上外鍵值”格式的列名。假設(shè)A是一對多關(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表中記錄的同時獲得其他表中與其相關(guān)的記錄時，使用“CREATE INDEXON(，， ，…)FROMIN”創(chuàng)建索引。當(dāng)要查詢TPC-C數(shù)據(jù)模型中指定客戶（Customer）的訂單（Order）信息，包括訂單項（Order line）和其中具體物品的信息時，使用“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是一對多的關(guān)系，因此只會在Order的索引列族中存在關(guān)于Customer的列名索引，而在Customer索引列族下沒有找到“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是一對多關(guān)系，同樣在OrderLine記錄的索引列族中建立關(guān)于Order的列族索引。最后從OrderLiner出發(fā)，在Order記錄的索引列族下尋找是否有關(guān)于Item的索引，因為Order-Line和Item是多對一的關(guān)系，所以在插入OrderLine數(shù)據(jù)時便已在OrderLine的索引列族中建立了關(guān)于Item的索引。至此，這條建立索引的命令的工作已經(jīng)完成。“CREATE INDEX)ONFROMIN”由StartTable出發(fā)，建立指定TableSet上索引的算法如下。

1.Queue Q;/*聲明一個棧*/

2.Set UnvisitedSet=TableSet;/*新建一個集合保存未被訪問的表*/

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

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

4.Q.push(StartTable);

5.while!isEmpty(Q)

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

7. Q.pop();

8. for(table in UnvisitedSet)

9. if MetadataManager.existIndex(table，p)/*如果未被訪問的表集合中有表的索引列族中存在關(guān)于p的索引，通過查詢索引元數(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記錄索引列族中列名索引得到對應(yīng)的表*/

18. UnvisitedSet=UnvisitedSet.remove(q);

19. Q.push(q);

20.end for

21.end while

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

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

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

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

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

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ù)時，系統(tǒng)首先依照刪除數(shù)據(jù)前刪除索引的方法，刪除本條記錄對應(yīng)的在其他表中的索引，然后按照插入新值時建立索引的方法，在其他記錄的索引列族中插入新列。

3.3 性能分析

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

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

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

4 實驗結(jié)果

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

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

4.1 實驗設(shè)置

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

4.2 工作負(fù)載

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

4.3 查詢1及實驗結(jié)果

查詢1（Q1）的SQL語句如下：

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

4.4 查詢2及實驗結(jié)果

查詢2（Q2）的SQL語句如下：

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

4.5 寫入1及實驗結(jié)果

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

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

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

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

5 相關(guān)工作

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

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

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

數(shù)據(jù)庫性能調(diào)優(yōu)研究如何根據(jù)給定的查詢負(fù)載選擇存儲和索引結(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ù)庫性能。本文工作受到這些工作的啟發(fā)，但實現(xiàn)技術(shù)與這些工作完全不同。原因在于，已有工作主要針對“熱啟動”場景，即數(shù)據(jù)庫已經(jīng)運行給定負(fù)載一段時間，再進(jìn)行性能調(diào)優(yōu)，而本文工作主要針對“冷啟動”場景，即數(shù)據(jù)庫尚未運行給定負(fù)載就需要決定存儲格式和索引結(jié)構(gòu)。

6 結(jié)論

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