面向內存云的數據塊索引方法

王躍飛 于炯 魯亮

摘要：內存云（RAMCloud）通常通過移動數據的位置來解決內存利用率低的問題，致使Hash表數據定位失效，查詢數據效率低下；另一方面，在數據恢復過程中由于不能快速定位到需要的數據，每臺備份服務器返回的數據段不能更好地組織起來。針對以上問題，提出內存云全局鍵（RGK）及二叉樹索引。RGK分為三部分：定位到主服務器、定位到段以及定位到數據塊。前兩部分構成協調器索引鍵（CIK），在恢復中借助構造的協調器索引樹（CIT）能夠定位到段所在的主服務器；后兩部分構成主服務器索引鍵（MIK），數據在內存中位移后也能通過主服務器索引樹（MIT）快速獲取到數據。與傳統內存云集群相比，主服務器獲取數據塊的時間隨數據吞吐量的增大而明顯減少；協調器在閑散時間、重組日志時間等方面均有下降。實驗結果表明，全局鍵在構造的二叉索引樹的支持下能有效縮短獲取數據及快速恢復的時間。

關鍵詞：內存云；日志結構；二叉索引樹；數據塊定位；快速恢復

中圖分類號：TP393.02 文獻標志碼：A

Abstract：In order to solve the problem of low using rate， RAMCloud would change the positions of objects， which would cause the failure for Hash to localize the object， and the low efficiency of data search. On the other hand， since the needed data could not be positioned rapidly in the recovery process of the data， the returned segments from every single backup could not be organized perfectly. Due to such problems， RAMCloud Global Key （RGK） and binary index tree， as solutions， were proposed. RGK can be divided into three parts： positioned on master， on segment， and on object. The first two parts constituted Coordinator Index Key （CIK）， which means in the recovery process， Coordinator Index Tree （CIT） could position the master of segments. The last two parts constituted Master Index Key （MIK）， and Master Index Tree （MIT） could obtain objects quickly， even though the data was shifted the position in the memory. Compared with the traditional RAMCloud cluster， the time of obtaining objects can obviously reduce when the data throughput is increasing. Also， the idle time of coordinator and recombined time of log are both declining. The experimental results show that the global key with the support of the binary index tree can reduce the time of obtaining objects and recovering.

Key words：RAMCloud； logstructure； binary index tree； object localization； fast recovery

0 引言

近年來，固態存儲器的需求呈指數級增加，無論是搜索引擎還是社交網絡，都需要比磁盤更高的隨機訪問性能[1]。隨著應用的發展，這些數據逐漸從磁盤轉移到閃存或動態隨機訪問存儲器（Dynamic Random Access Memory，DRAM）中。由于在線數據密集型（On Line Data Intensive，OLDI）應用受到訪問延遲、吞吐量等性能參數的制約[2]，用戶與數據中心的交互難以跨越由類似問題形成的屏障。內存云的出現完美地解決了以上問題：內存云是一個將所有數據存儲在內存中的，由服務器集群組成的數據中心，磁盤僅在宕機或斷電等意外情況下用于數據的備份[3]。如圖1所示，在內存云集群中，每臺服務器分為兩部分，分別是主服務器（Master），用來存儲和計算；以及備份服務器（Backup），用于快速恢復。集群中含有一個類似于Hadoop分布式文件系統[4]中NameNode節點的協調器（Coordinator），用來管理配置信息等工作。主服務器采用日志（log）存儲方式，基本單位為段（segment），是組織數據塊（object）存儲的基本單位。

相對于傳統數據中心，內存云提供了良好的可用性、可擴展性以及海量數據讀寫的低延遲環境。在針對掉電易失性、數據存儲效率等問題上，研究人員制定了一系列策略以克服將數據存放在內存帶來的短板效應：1）內存數據管理。針對海量數據的管理，內存云無論在內存或是磁盤中均采用日志結構的存儲方式，能夠實現快速索引、寫入、修改等操作[5]。2）掉電易失問題。Stutsman[6]提出快速恢復策略，使主服務器掉電后能在2s內將所有的數據迅速恢復完畢，保證了數據的安全穩定。

以上問題雖然得以解決，卻依然存在缺陷：1）在內存數據管理方面，由于數據以碎片形式寫入內存中的段，造成段內空隙廢棄較多，亟待重組清理。為提高內存利用率， Rumble等[7]提出內存二級清理機制。該策略可將內存整體利用率提高至98%，卻使得定位數據的hash函數因數據的挪動致使地址失效，最終數據的查找效率由O（1）降低為O（n）。2）在快速恢復方面，每臺備份服務器在恢復過程中主要通過自我查找的方式返回需要的數據。盡管實現了并行查找，但宏觀上查找的數據量依然非常大。

與傳統數據中心存儲介質不同，目前關于內存云在索引數據方面的研究較少。其他支持大數據應用的存儲系統，包括Bigtable、LevelDB、Redis和Cassandra[8-11]等在數據的管理上均采用簡單的鍵值對存儲，未使用輔助二級索引等其他方式，僅僅通過主鍵獲得數據成為數據操作的瓶頸。華為、Facebook以及Twitter等大型數據中心采用面向列的Hbase分布式存儲系統[12]，該數據庫為解決列與列之間的關聯采用二級索引H Index，在降低索引時間等方面取得了顯著效果。目前，一些新的觀點弱化了索引，轉而通過使用網絡協議，或兩階段協議等技術確保在一個遠程過程調用（Remote Procedure Call， RPC）期間數據獲取的穩定性和一致性[13-14]。在海量索引目標方面，典型地如網頁的甄別索引，將5000億個網址（截止至2010年）的信息指紋隨機映射到16字節整數空間[15]，為處理海量索引目標提出了可供參考的技術方法。

以上方案都為進一步研究內存云下的索引問題提供了寶貴的經驗與參考價值，然而并未結合內存云特殊的日志結構，致使內存云在索引數據上存在缺陷。本文在內存云數據塊原有的格式上添加了一個特有的內存云全局鍵（RAMCloud Global Key，RGK）。在構造的二叉樹索引的支持下可以實現快速定位數據和主服務器，減少獲取數據以及快速恢復的時間。

1 問題描述

1.1 內存云log日志結構

內存云采用日志結構（logstructure）存儲數據，每個主服務器內存空間為64GB，日志被分割成多個段，大小默認為8MB。數據塊存儲在段中。如圖2所示，內存云集群中存在多張表（table），表中的基本存儲單元為數據塊，在表內被唯一標識。每張表可以單獨存在于一個主服務器，也可以跨越多臺服務器存儲。通常情況下，每臺主服務器內含多張表的數據塊。

為方便增加、刪除和查詢某個數據塊，集群中每個內存云主服務器內含有一張Hash表。定位數據塊需要〈TableId，objectkey〉二元組，其中TableId指定了數據塊屬于哪張表，objectkey是數據塊在一張表內唯一受到標識的主鍵。Hash函數通過TableId和objectkey獲得唯一的數據塊地址，進而進行操作。

1.2 二級清理機制及存在的問題

由于數據塊的存儲地址依據Hash表計算得來，內存云中的段在存儲數據塊時不可避免地浪費了大量的段空間，為解決該問題，內存云使用了二級清理機制：第一級清理（segment compaction），是將任意段中的數據塊移動到一個新的段內并緊密排列；第二級清理（combined cleaning），是在備份服務器中進行同樣的段合并。

然而在第一級清理后，數據塊因為緊密排列導致其地址發生了變化，原先的Hash函數因無法計算地址而失效。這導致最初獲取數據塊的時間復雜度從O（1）升至O（n），此時只能通過在表內逐一比對objectkey以獲取所需的數據塊，同時這也激增了快速恢復的時間。如圖3所示。

1.3 快速恢復機制及存在的問題

為避免內存數據掉電易失性，備份服務器以段為單位[16]，將每個主服務器的數據備份在了備份服務器內。在恢復過程中，協調器首先查看所有的備份服務器內的數據，用于檢查日志信息完整性。之后獲取需要的段，拼接后重新恢復完畢。

為保證安全，需要恢復的數據分別備份在成百上千個備份服務器內，因此查閱所有的備份服務器并判斷日志數據的完整性是一項十分消耗時間和資源的工作。在此階段中存在以下幾點問題：

1）每臺備份服務器獨立查找本機內所有相關的段。由于主服務器備份系數一般為3（在不同的備份服務器備份3份），因此每臺備份服務器內含有的段的數量級約為24000個。盡管研究人員提出了所有備份服務器的查找并行化，節省了時間，但從內存云集群的宏觀角度考慮，一次快速恢復的段查找仍維持在千萬數量級。

2）當每臺備份服務器將自身存儲的恢復所需的段地址傳遞給協調器后，協調器需要分析這些大量的段，之后重新將地址整合成一張恢復表（recovery map）。然而段的重組過程較為耗時，不僅因為返回段的無序性，同樣備份服務器在返回段的過程中并行化較低。

3）并不是所有的備份服務器都需要參與恢復過程。有些備份服務器并不含有需要的數據段，但在快速恢復機制中，這些服務器也參與了查找。

通過分析以上在清理機制與快速恢復過程中出現的問題，可以總結出對段和數據塊的定位是必要的。目前對數據塊的定位僅僅限定于〈TableId，objectkey〉二元組，對段的定位還沒有相關討論。

2 全局鍵索引策略

2.1 內存云全局鍵

內存云集群中，數據塊是數據組織的最小單位。每個數據塊在寫入內存時被賦予幾個關鍵值，用于數據塊的基本操作。圖4展示了數據塊在內存云中的存儲格式，圖中在原有的格式中添加了內存云全局鍵RGK。

在圖4中，64bit Table Identifier用來唯一標識集群中的表；64bit Version記錄了數據塊修改后的當前版本，防止了數據的臟讀；數據塊時間戳Timestamp記錄了數據的寫入時間，區分新老數據塊，使清理時更加高效；Checksum用來確認數據塊的正確性與完整性；Key Length記錄了鍵長，Key、Value記錄了該數據塊的鍵值與數據塊內的實際數據。

結合1.2、1.3節討論的問題，為快速定位內存云中的段與數據塊，現提出內存云全局鍵的概念。

定義1 內存云全局鍵（RAMcloud Global Key， RGK）。內存云全局鍵是一串長為64位的二進制碼，能夠唯一標識內存云集群中的每一臺主服務器、每一個段以及最小數據單元數據塊。

根據內存云集群、段以及段內數據塊的數量，將全局鍵有效位定為前33位，后31位作為預留或備用，如圖5所示。在RGK中，前10位作為集群主服務器的標識，可分別獨立標識1024臺主服務器。后13位標識每臺服務器內的段：內存云每臺服務器內存固定64GB，共劃分為8192個段，采用13位二進制標識。較小數據塊通常在10000B左右，因此最后10位標識每個段內的數據，可記錄1024個數據塊。

RGK的長度是允許變化的，備用數據位在集群數量擴增等情況下允許被占用。結合1.2、1.3節討論的問題，為實現數據的快速定位，現將RGK合理劃分。

定義2 協調器索引鍵（Coordinator Index Key， CIK）。協調器索引鍵是包含在RGK前兩部分內的一串長為s位的二進制碼，其中m表示RGK中標識主服務器的二進制位數，m至s位表示RGK中標識段的位數。

定義3 主服務器索引鍵（Master Index Key， MIK）。主服務器索引鍵是包含在RGK后兩部分內的一串長為（o-m）位的二進制碼，其中m至s位表示RGK中標識段的位數，s至o位表示RGK中標識數據塊的位數。

每臺主服務器內建立一棵深度為23的MIT。前十三層定位到一個確定的段，在該節點下的葉子節點均是該段的數據塊。與滿二叉樹不同之處在于，對每個葉子節點賦一條指針，指針指向該節點對應數據塊的物理地址，當Key值索引到該葉子節點，讀取該節點指針指向的地址。

由于樹的深度固定為23，在該循環重復有限次后即能獲取到指向數據地址的指針，索引的使用提高了定位某個數據塊的性能。而優化前為獲取數據，需要調用二元組〈TableId，objectkey〉，再通過校對objectkey獲取數據，增加了內存時延。

另一方面，MIT索引屬于聚集索引，這是因為數據是以段數據塊的形式有規律地組織起來的，索引鍵值的邏輯順序映射了物理存儲順序。在磁盤掃描中，檢索數據不需要指針跳動，掃描數據避免了多余的不連續磁盤I/O開銷。并且于聚集索引的范圍掃描執行情況優良，因為聚集索引的葉子節點在物理上是按照組成聚集索引的順序排列在磁盤上的。

3 實驗與分析

3.1 實驗環境

實驗模擬內存云集群。創建11個節點，其中1個節點為協調器，10個節點為主服務器。每個節點內主服務器內存16GB，備份服務器硬盤100GB。主服務器內段默認8MB，分別備份3份副本隨機放置在10個節點中內的磁盤中。

由于實驗模擬的集群節點少內存小，實驗中RGK設置為25位。其中前4位定位到唯一主服務器，第5～15位確定該服務器內的唯一段，16～25位定位到數據塊。主服務器內 10GB用來放置數據，共存放數據段1280個。要說明的是，MIT（即RGK去除前4位）第11層為滿節點，其中含有768個空節點，這些空節點的孩子節點也為空，不存在索引問題。

3.2 實驗結果與分析

通常在內存中，獲取數據的速度與數據傳輸通道容量、吞吐量、內存時延等因素相關。實驗中，獲取數據的速度通過公式S/T計算大小。其中S為訪問數據量，T為訪問時間。

3.2.1 主服務器獲取數據塊

圖9展示了原主服務器（noMIT）與引入MIT兩種不同情況下，獲取 1GB～10GB的數據共需要的時間。未引入索引樹時，隨著獲取數據的增加，直線的斜率增大。這是因為獲取數據的方法是通過逐一比對每張表內的〈TableId，objectkey〉二元組，內存訪問延遲較高。當引入MIT時，吞吐量與時間呈線性關系，是因為在索引樹葉子節點使用指針指向數據的地址，內存訪問延遲很低。

3.2.2 快速恢復時間分析

為模擬快速恢復，采用蒙特卡羅算法隨機生成一組1280×3條1～10的數據組成的矩陣，表示某臺主服務器內1280個段，每個段隨機備份在1～10號節點中的3個節點。每臺備份服務器約含3840個段，空間占據30GB。

表2展示了恢復階段協調器的時間概況。恢復過程中協調器節點首先等待從磁盤中返回的數據，隨后將數據按崩潰前的順序重新組織。通過表中的對比可以觀察到：1）協調器閑散時間有效減少；2）重組段的時間有效減少。

實驗3.2.2節的結果使備份服務器返回數據的時間提前，使協調器更早地獲得要恢復的段。重組段時間減少是由于每個段含唯一的RGK，通過比對RGK的大小可以迅速重組崩潰的日志。

由于集群僅含有10個節點，每個節點需恢復的數據量大。一個集群含有節點一般來說在500～1000，數據隨機備份在大量節點上恢復的時間也比較少。

4 結語

目前一些數據中心為快速獲取數據都會采用在原有的數據格式中添加第二主鍵的方法，如MongoDB等，但這種方法是將數據的存儲方式改為JavaScript對象表示法（JavaScript Object Notation， JSON）格式，加重了數據的負擔。本文在內存云日志結構中添加了全局鍵，為獲取、修改數據提供了另一種更高效的聚集索引方法，同時減少了快速恢復的時間。當然，全局索引大小上也存在局限性。當集群服務器超過兩千臺，或者段內的較小數據塊沒有經過合并算法合并，都會帶來索引樹占據內存過大等問題。對于超大內存云集群與其涵蓋的海量數據，是否專門使用一組內存服務器搭建索引樹則是一個新的需要探索的問題。

下一步將針對內存云架構，對備份服務器的存儲方式進行新的探索與改進。通常段的存儲是按照內存中的存儲方式完全備份在備份服務器內的，按照以空間換取時間的研究思路，可將數據稀疏存儲在空間足夠充足的硬盤上。如何存放備份服務器的Hash表，如何設置Hash函數，仍然是下一步研究的重點。

參考文獻：

[1]FOX A， GRIBBLE S D， CHAWATHE Y， et al. Clusterbased scalable network services[C]// Proceedings of the 16th ACM Symposium on Operating Systems Principles. New York： ACM， 1997： 78-91.

[2]ARMBRUST M， FOX A， GRIFFITH R， et al. A view of cloud computing[J]. Communications of the ACM， 2010， 53（4）： 50-58.

[3]OUSTERHOUT J， AGRAWAL P， ERICKSON D， et al. The case for RAMClouds： scalable highperformance storage entirely in DRAM[J]. ACM SIGOPS Operating Systems Review， 2010， 43（4）：92-105.

[4]BORTHAKUR D. The hadoop distributed file system： architecture and design[EB/OL].[20150505]. http：//hadoop.apache.org/common/docs/r0.18.2/hdfs_design.pdf.

[5]RUMBLE S. Memory and object management in RAMCloud[D]. Stanford： Stanford University， 2014： 17-44.

[6]STUTSMAN R. Durability and crash recovery in distributed inmemory storage systems[D]. Stanford： Stanford University， 2013： 49-53.

[7]RUMBLE S， KEJRIWAL A， OUSTERHOUT J. Logstructed memory for DRAMbased storage[C]// Proceedings of the 12th USENIX Conference on File and Storage Technologies. Berkeley： USENIX， 2014： 1-16.

[8]CHANG F， DEAN J， GHEMAWAT S， et al. Bigtable： a distributed storage system for structured data[J]. ACM Transactions on Computer Systems， 2008， 26（2）： 4.

[9]MITCHELL C， GENG Y， LI J. Using onesided RDMA reads to build a fast， CPUefficient keyvalue store[C]// Proceedings of the 2013 USENIX Annual Technical Conference. Berkeley： USENIX， 2013： 103-114

[10]KIM W， CHO I， MIN D， et al. Design of data backup on distributed memory system based on keyvalue store using hot/cold data management[C]// Proceedings of the 2014 Conference on Research in Adaptive and Convergent Systems. New York： ACM， 2014： 359-361.

[11]LAKSHMAN A， MALIK P. Cassandra： a decentralized structured storage system[J]. ACM SIGOPS Operating Systems Review， 2010， 44（2）： 35-40.

[12]CHEN H， LU K， SUN M， et al. Enumeration system on HBase for lowlatency[C]// Proceedings of the 2015 15th IEEE/ACM International Symposium on Cluster， Cloud and Grid Computing. Piscataway， NJ： IEEE， 2015： 1185-1188.

[13]BAKER J， BOND C， CORBETT J C， et al. Megastore： providing scalable， highly available storage for interactive services[C]// Proceedings of the 5th Biennial Conference on Innovative Data Systems Research. [S.l.]： VLDB， 2011： 223-234.

[14]CORBETT J C， DEAN J， EPSTEIN M， et al. Spanner： Googles globally distributed database[J]. ACM Transactions on Computer Systems， 2013， 31（3）： 8.

[15]吳軍. 數學之美[M]. 北京：人民郵電出版社， 2012：142-152.（WU J. Beauty of Mathematics[M]. Beijing： Posts & Telecom Press， 2012：142-152.）

[16]ONGARO D， RUMBLE S M， STUTSMAN R， et al. Fast crash recovery in RAMCloud[C]// Proceedings of the 23rd ACM Symposium on Operating Systems Principles. New York： ACM， 2011： 29-41.