王躍飛 于炯 魯亮

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

關(guān)鍵詞：內(nèi)存云；日志結(jié)構(gòu)；二叉索引樹；數(shù)據(jù)塊定位；快速恢復(fù)

中圖分類號：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 引言

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

相對于傳統(tǒng)數(shù)據(jù)中心，內(nèi)存云提供了良好的可用性、可擴展性以及海量數(shù)據(jù)讀寫的低延遲環(huán)境。在針對掉電易失性、數(shù)據(jù)存儲效率等問題上，研究人員制定了一系列策略以克服將數(shù)據(jù)存放在內(nèi)存帶來的短板效應(yīng)：1）內(nèi)存數(shù)據(jù)管理。針對海量數(shù)據(jù)的管理，內(nèi)存云無論在內(nèi)存或是磁盤中均采用日志結(jié)構(gòu)的存儲方式，能夠?qū)崿F(xiàn)快速索引、寫入、修改等操作[5]。2）掉電易失問題。Stutsman[6]提出快速恢復(fù)策略，使主服務(wù)器掉電后能在2s內(nèi)將所有的數(shù)據(jù)迅速恢復(fù)完畢，保證了數(shù)據(jù)的安全穩(wěn)定。

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

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

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

1 問題描述

1.1 內(nèi)存云log日志結(jié)構(gòu)

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

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

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

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

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

1.3 快速恢復(fù)機制及存在的問題

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

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

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

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

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

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

2 全局鍵索引策略

2.1 內(nèi)存云全局鍵

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

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

結(jié)合1.2、1.3節(jié)討論的問題，為快速定位內(nèi)存云中的段與數(shù)據(jù)塊，現(xiàn)提出內(nèi)存云全局鍵的概念。

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

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

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

定義2 協(xié)調(diào)器索引鍵（Coordinator Index Key， CIK）。協(xié)調(diào)器索引鍵是包含在RGK前兩部分內(nèi)的一串長為s位的二進制碼，其中m表示RGK中標識主服務(wù)器的二進制位數(shù)，m至s位表示RGK中標識段的位數(shù)。

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

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

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

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

3 實驗與分析

3.1 實驗環(huán)境

實驗?zāi)M內(nèi)存云集群。創(chuàng)建11個節(jié)點，其中1個節(jié)點為協(xié)調(diào)器，10個節(jié)點為主服務(wù)器。每個節(jié)點內(nèi)主服務(wù)器內(nèi)存16GB，備份服務(wù)器硬盤100GB。主服務(wù)器內(nèi)段默認8MB，分別備份3份副本隨機放置在10個節(jié)點中內(nèi)的磁盤中。

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

3.2 實驗結(jié)果與分析

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

3.2.1 主服務(wù)器獲取數(shù)據(jù)塊

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

3.2.2 快速恢復(fù)時間分析

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

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

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

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

4 結(jié)語

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

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

參考文獻：

[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]吳軍. 數(shù)學之美[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.