RStore：基于BigTable的關系數據模型存儲系統*

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

浙江大學 計算機科學與技術學院，杭州 310027

1 引言

隨著互聯網、移動互聯網、物聯網應用的普及，人們正在以前所未有的速度產生大數據[1-2]?；ヂ摼W數據中心（Internet Data Center，IDC）的研究顯示，2011年全球共產生1800 EB數據，且每年產生的數據量還在以60%的速度增長，到2020年，全球每年將產生35 ZB數據[2]。大數據為數據管理技術帶來了數據量大、數據產生速度快、數據類型復雜三重挑戰。

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

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

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

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

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

（1）提出了一種基表存儲結構，將關系數據庫中的所有表格存儲在同一張BigTable中，提供基于主鍵的數據存取。

Fig.1 RBase architecture圖1 RBase架構

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

2 BigTable數據庫系統簡介

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

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

Table 1 BigTable for storing Web data表1 存儲網頁數據的BigTable

3 RStore關系數據模型存儲系統

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

對于上層應用，RBase支持關系編程范式。應用開發前，用戶使用標準的SQL DDL語句聲明業務數據的表格結構。建立一個TPC-C數據庫和Customer表，分別用CREATE DATABASE tpcc以及CREATE TABLE tpcc.customer(）完成。

Fig.2 TPC-C entity relationship diagram圖2 TPC-C中的實體關系圖

3.1 基表存儲結構

在系統實現上，RStore根據用戶提供的表格定義和查詢申明，將數據存入BigTable中。RStore提供兩種數據存取策略：（1）基表存儲結構；（2）跨表查詢索引。

在基表存儲結構中，RStore將基表中的每一條元組存為BigTable中的一行，并將主鍵編碼進BigTable的行鍵，為應用提供基于主鍵的高效數據存取。在跨表查詢索引中，RStore根據主外鍵約束關系，將與基表元組存在引用關系的外表元組索引至該元組的列鍵下，利用BigTable的列鍵搜索機制，提供跨表元組存取。

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

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

Table 2 BigTable data layout表2 BigTable的數據布局

Table 3 TPC-C Cusomer relational table表3 關系模型下的TPC-C Customer表

3.2 跨表查詢索引

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

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

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

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

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

TPC-C測試數據模型中Warehouse和Item是具有多對多關系的一對實體，當向以Warehouse和Item的主鍵為聯合主鍵的邏輯表插入數據時，系統按照多對多索引的創建方法，向Warehouse記錄的索引列族中插入列名為“WarehouseKeyWarehouse-ItemKeyItem”格式的列，向Item記錄的索引列族中插入“ItemKeyItem-WarehouseKeywarehouse”格式的列，如表7所示。元數據管理器記錄下“Warehuose-Item”、“Item-Warehouse”作為創建的索引的元數據。

Table 6 One-to-many records in BigTable data model processed by RBase表6 經RBase處理后存儲在BigTable數據模型中的一對多關系記錄

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

當在兩個有主外鍵關系的表A和表B間聲明創建索引時，因為兩者有一對多的關系，所以必然在某一方的索引列族下存在著“表名連接上主鍵值-外鍵所在表名連接上外鍵值”格式的列名。假設A是一對多關系中的“多”方，則A記錄的索引列族下存在“AKeyA-BKeyB”格式的列名，系統按如下方式建立索引。

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”);

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

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

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

Table 7 Many-to-many records in BigTable data model processed by RBase表7 BigTable中具有多對多關系的數據經RBase處理后的結果

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

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)/*如果未被訪問的表集合中有表的索引列族中存在關于p的索引，通過查詢索引元數據即可判斷*/

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記錄索引列族中列名索引得到對應的表*/

18. UnvisitedSet=UnvisitedSet.remove(q);

19. Q.push(q);

20.end for

21.end while

這樣，當有新的數據插入時，所有元數據管理器中記錄的已創建索引（包括原先由系統在插入數據時自動創建的索引和手動聲明創建的索引）都會根據新插入的值創建列名索引進行更新。

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

假設要被刪除的記錄是row key為“TableA:ID”，刪除數據前關于索引的操作如下。

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

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

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

4.UnlocalIndexTableSet=MetaManager.queryUnlocalIndex(“TableA”);/*從元數據管理器中查詢“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

當用戶更新外鍵數據時，系統首先依照刪除數據前刪除索引的方法，刪除本條記錄對應的在其他表中的索引，然后按照插入新值時建立索引的方法，在其他記錄的索引列族中插入新列。

3.3 性能分析

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

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

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

4 實驗結果

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

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

4.1 實驗設置

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

4.2 工作負載

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

4.3 查詢1及實驗結果

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

其中，（:c_w_id,:c_d_id,:c_id)為輸入參數確定待查詢用戶。為運行查詢，對RBase系統建立如下的跨表查詢索引：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）上建立次級索引。實驗中，變換集群大小，測試當從節點數目增加時，系統的吞吐率（即，系統CPU滿載時，每秒處理的查詢總數）和查詢響應時間。圖3（a）和圖3（b）顯示了實驗結果?？梢钥吹剑琑store的吞吐率和平均響應時間明顯優于MegaStore，這主要是由于跨表查詢索引消除了耗時的表格連接操作。

4.4 查詢2及實驗結果

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

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

4.5 寫入1及實驗結果

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

Fig.3 Q1 throughput results and avg.latency results圖3 查詢1的系統吞吐率和平均響應時間

Fig.4 Q2 throughput results and avg.latency results圖4 查詢2的系統吞吐率和平均響應時間

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

5 相關工作

與本文相關的工作分為3類：NoSQL數據庫系統、基于NoSQL的關系數據庫系統、數據庫性能調優。

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

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

數據庫性能調優研究如何根據給定的查詢負載選擇存儲和索引結構。文獻[20]和文獻[21]綜述了相關工作。文獻[22]和文獻[23]分別研究了如何選擇數據切分、物化視圖、索引結構以自適應地提升數據庫性能。本文工作受到這些工作的啟發，但實現技術與這些工作完全不同。原因在于，已有工作主要針對“熱啟動”場景，即數據庫已經運行給定負載一段時間，再進行性能調優，而本文工作主要針對“冷啟動”場景，即數據庫尚未運行給定負載就需要決定存儲格式和索引結構。

6 結論

本文提出了RStore，一個基于BigTable的關系數據存儲系統。對于應用開發，RStore支持關系編程范式，用戶只需申明業務數據的表格結構，無需關心數據的存儲細節。對于系統實現，RStore自動將關系數據存入BigTable，支持高伸縮和高效的數據訪問。RStore同時滿足了大數據應用對數據管理系統快速應用開發和高效數據訪問的需求。