面向內(nèi)存云的數(shù)據(jù)塊索引方法

王躍飛 于炯 魯亮

摘要：內(nèi)存云（RAMCloud）通常通過移動(dòng)數(shù)據(jù)的位置來解決內(nèi)存利用率低的問題，致使Hash表數(shù)據(jù)定位失效，查詢數(shù)據(jù)效率低下；另一方面，在數(shù)據(jù)恢復(fù)過程中由于不能快速定位到需要的數(shù)據(jù)，每臺(tái)備份服務(wù)器返回的數(shù)據(jù)段不能更好地組織起來。針對(duì)以上問題，提出內(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í)間隨數(shù)據(jù)吞吐量的增大而明顯減少；協(xié)調(diào)器在閑散時(shí)間、重組日志時(shí)間等方面均有下降。實(shí)驗(yàn)結(jié)果表明，全局鍵在構(gòu)造的二叉索引樹的支持下能有效縮短獲取數(shù)據(jù)及快速恢復(fù)的時(shí)間。

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

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

相對(duì)于傳統(tǒng)數(shù)據(jù)中心，內(nèi)存云提供了良好的可用性、可擴(kuò)展性以及海量數(shù)據(jù)讀寫的低延遲環(huán)境。在針對(duì)掉電易失性、數(shù)據(jù)存儲(chǔ)效率等問題上，研究人員制定了一系列策略以克服將數(shù)據(jù)存放在內(nèi)存帶來的短板效應(yīng)：1）內(nèi)存數(shù)據(jù)管理。針對(duì)海量數(shù)據(jù)的管理，內(nèi)存云無論在內(nèi)存或是磁盤中均采用日志結(jié)構(gòu)的存儲(chǔ)方式，能夠?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)存二級(jí)清理機(jī)制。該策略可將內(nèi)存整體利用率提高至98%，卻使得定位數(shù)據(jù)的hash函數(shù)因數(shù)據(jù)的挪動(dòng)致使地址失效，最終數(shù)據(jù)的查找效率由O（1）降低為O（n）。2）在快速恢復(fù)方面，每臺(tái)備份服務(wù)器在恢復(fù)過程中主要通過自我查找的方式返回需要的數(shù)據(jù)。盡管實(shí)現(xiàn)了并行查找，但宏觀上查找的數(shù)據(jù)量依然非常大。

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

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

1 問題描述

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

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

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

1.2 二級(jí)清理機(jī)制及存在的問題

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

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

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

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

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

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

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

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

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

2 全局鍵索引策略

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

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

在圖4中，64bit Table Identifier用來唯一標(biāo)識(shí)集群中的表；64bit Version記錄了數(shù)據(jù)塊修改后的當(dāng)前版本，防止了數(shù)據(jù)的臟讀；數(shù)據(jù)塊時(shí)間戳Timestamp記錄了數(shù)據(jù)的寫入時(shí)間，區(qū)分新老數(shù)據(jù)塊，使清理時(shí)更加高效；Checksum用來確認(rèn)數(shù)據(jù)塊的正確性與完整性；Key Length記錄了鍵長(zhǎng)，Key、Value記錄了該數(shù)據(jù)塊的鍵值與數(shù)據(jù)塊內(nèi)的實(shí)際數(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)存云全局鍵是一串長(zhǎng)為64位的二進(jìn)制碼，能夠唯一標(biāo)識(shí)內(nèi)存云集群中的每一臺(tái)主服務(wù)器、每一個(gè)段以及最小數(shù)據(jù)單元數(shù)據(jù)塊。

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)環(huán)境

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

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

3.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

4 結(jié)語

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

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

參考文獻(xiàn)：

[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ù)學(xué)之美[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.