摘要

基于LSM-tree的鍵值存儲系統(tǒng)是NewSQL/NoSQL產(chǎn)品中最常用的底層存儲方案，對其進行研究具有重要意義與應(yīng)用價值。論文針對 分布式鍵值系統(tǒng)首次提出了副本解耦的思想，在多副本容錯機制下能夠?qū)崿F(xiàn)副本數(shù)據(jù)的高效管理，從而顯著提升系統(tǒng)性能。并且論文提出的技術(shù)可以應(yīng)用到Cassandra、TiKV、ScyllaDB等系統(tǒng)中。本次分享將和大家一起討論基于副本解耦的分布式鍵值系統(tǒng)的設(shè)計實現(xiàn)方案，并探討未來的推廣應(yīng)用。

一、背景

1、在大數(shù)據(jù)時代，數(shù)據(jù)量呈指數(shù)級增長，預(yù)計到2025年，全球的數(shù)據(jù)總量將達175ZB，非結(jié)構(gòu)化和半結(jié)構(gòu)化數(shù)據(jù)已占據(jù)主導(dǎo)地位。對海量非結(jié)構(gòu)化和半結(jié)構(gòu)化數(shù)據(jù)進行高效存儲，KV存儲系統(tǒng)提供了很好的解決方案：

●?KV存儲系統(tǒng)具有靈活的數(shù)據(jù)模型，數(shù)據(jù)表示為KV對形式，為任意數(shù)據(jù)類型，且長度不定；

●?KV存儲的訪存接口非常簡單，向外提供Put、Get、Scan等簡單的接口進行數(shù)據(jù)讀寫；

●?KV存儲還具備高可擴展性，數(shù)據(jù)基于Key進行劃分和索引，無需維護額外的元數(shù)據(jù)。由于KV存儲系統(tǒng)具有上述諸多優(yōu)點，因此被廣泛應(yīng)用在了NewSQL和NoSQL產(chǎn)品中。比如目前常見的KV存儲系統(tǒng)：LevelDB、RocksDB、Cassandra、TiKV等。

2、目前主流的持久化KV存儲系統(tǒng)都采用LSM-tree（log-structured merge tree）架構(gòu)作為存儲引擎，其具有高效的寫入效率，但同時存在嚴(yán)重的讀寫放大問題。

如圖，KV數(shù)據(jù)首先緩存在內(nèi)存并進行排序，然后以批量追加的方式將數(shù)據(jù)寫入磁盤上，形成磁盤上的一個SSTable文件，SSTable文件中的數(shù)據(jù)是按Key有序的，這種寫入方式可以將大量的隨機寫轉(zhuǎn)換為順序?qū)?，從而充分利用磁盤順序?qū)懙膸拑?yōu)勢，獲得高效的寫入效率。

為兼顧讀性能，磁盤上的數(shù)據(jù)被組織成多層形式，且容量逐層遞增，并且除第0層以外，其他每層的數(shù)據(jù)是完全有序的。通過維護這樣一個多層有序的架構(gòu)，LSM-tree可以獲得高效的寫入和范圍查詢性能，并且提供高可擴展性，當(dāng)需要擴展存儲容量時，可以通過簡單的增加LSM-tree的層數(shù)來實現(xiàn)高效的擴展。

然而，LSM-tree多層的數(shù)據(jù)組織結(jié)構(gòu)導(dǎo)致查詢操作需要逐層搜索，從第0層開始，直到找到查詢的數(shù)據(jù)為止，并且寫入期間需要執(zhí)行頻繁的Compaction操作，具體Compaction操作需要從LSM-tree中讀取相鄰兩層的數(shù)據(jù)，然后執(zhí)行合并排序操作，再將合并后的有效數(shù)據(jù)寫回磁盤。因此，當(dāng)我們將數(shù)據(jù)從第0層逐漸合并到較高層時，需要將數(shù)據(jù)頻繁的讀出并且寫回，進而導(dǎo)致嚴(yán)重的讀寫放大問題，且嚴(yán)重消耗磁盤的IO帶寬。

3、分布式KV存儲系統(tǒng)被廣泛應(yīng)用，以支持大規(guī)模的數(shù)據(jù)存儲。

對于Cassandra、TiKV這一類分布式KV存儲系統(tǒng)，首先數(shù)據(jù)基于Key的一致性哈希或者Key的范圍劃分到各個存儲節(jié)點上，然后每個節(jié)點內(nèi)部使用一個LSM-tree來存儲管理所有數(shù)據(jù)，下圖以Cassandra為例做詳細(xì)的介紹。

如圖，KV數(shù)據(jù)首先基于Key的一致性哈希進行分區(qū)，圖中有五個物理節(jié)點，每個節(jié)點有兩個虛擬節(jié)點，因此整個哈希環(huán)被劃分成十個范圍段。圖中0到100的范圍段被劃分成0-10、11-20、21-30等十個范圍段，并且每個范圍段都與順時針方向最近的虛擬節(jié)點和相對應(yīng)的物理節(jié)點相關(guān)聯(lián)。比如0-10、51-60這兩個范圍段被劃分到節(jié)點0；11-20和61-70這兩個范圍段被劃分到節(jié)點1。

通過上述劃分策略，每個節(jié)點會包含多個范圍段，并且節(jié)點內(nèi)部將所有范圍段存儲在一個LSM-tree中。4、為保證數(shù)據(jù)的高可靠，多副本容錯機制被廣泛應(yīng)用在分布式KV存儲系統(tǒng)中，即每份數(shù)據(jù)會復(fù)制成多份，并且存儲在多個節(jié)點上，因此每個節(jié)點上的數(shù)據(jù)可分為主副本和冗余副本。

●?主副本：指通過一致性哈希劃分策略劃分到節(jié)點上的數(shù)據(jù)；

●?冗余副本：指通過復(fù)制策略發(fā)送到節(jié)點上的冗余數(shù)據(jù)；

●?統(tǒng)一索引：對于節(jié)點上的主副本和冗余副本，現(xiàn)有KV存儲系統(tǒng)都采用統(tǒng)一的多副本管理方案，也就是把主副本和冗余副本統(tǒng)一存儲在一個LSM-tree中，如下圖。

考慮到LSM-tree架構(gòu)本身存在嚴(yán)重的讀寫放大問題，而統(tǒng)一的索引方案又會極大的增加LSM-tree中存儲的數(shù)據(jù)量，因此會進一步加劇LSM-tree的讀寫放大問題。

5、通過實驗進一步驗證了統(tǒng)一的多副本管理方案會加劇KV系統(tǒng)的讀寫放大。

如圖，在五個節(jié)點構(gòu)成的本地存儲集群上進行實驗，客戶端首先寫入300GB的KV數(shù)據(jù)，然后從集群中讀出30GB的KV數(shù)據(jù)，KV大小為1KB，這里分別統(tǒng)計了分布式KV系統(tǒng)Cassandra和TiKV在不同副本數(shù)量下的讀寫放大系數(shù)，圖（a）展示了寫放大系數(shù)，圖（b）展示了讀放大系數(shù)。

由實驗結(jié)果可知，當(dāng)副本數(shù)量越多時，KV存儲系統(tǒng)的寫放大和讀放大越嚴(yán)重，且放大系數(shù)增加的倍數(shù)超過副本數(shù)量增加的倍數(shù)，這里主要原因是上述分析的統(tǒng)一多副本管理方案，會大大加劇寫流程中執(zhí)行的Compaction數(shù)據(jù)量，并且也會成倍增加讀流程中需要搜索的數(shù)據(jù)量。

二、設(shè)計

為解決分布式KV系統(tǒng)中統(tǒng)一多副本管理導(dǎo)致的問題，接下來介紹解決方案。

2.1 設(shè)計思想

主要設(shè)計思想是在存儲層對主副本和冗余副本進行解耦，以避免讀寫過程中主副本和冗余副本之間的相互干擾。副本解耦后，采用多個LSM-tree來對解耦的多副本進行獨立管理。

如圖，當(dāng)系統(tǒng)配置為三副本時，在每個存儲節(jié)點上使用一個LSM-tree來存儲主副本，另外兩個LSM-tree來分別存儲來自其他兩個節(jié)點的冗余副本。這種方案的想法及實現(xiàn)都非常簡單，但是存在著一些典型的問題。

2.2 mLSM的兩個主要限制

●?多個LSM-tree會導(dǎo)致K倍的內(nèi)存開銷，因為每個LSM-tree都需要在內(nèi)存中維護一個MemTable；

●?多個LSM-tree的解耦方案對Compaction開銷的減少是非常有限的，因為每個LSM-tree仍然需要執(zhí)行頻繁的Compaction操作，從而來維護每層數(shù)據(jù)的完全有序，導(dǎo)致LSM-tree的Compaction開銷仍然非常嚴(yán)重。通過實驗驗證，當(dāng)客戶端寫200GB數(shù)據(jù)，采用三副本時，多個LSM-tree的解耦方案相比于統(tǒng)一索引方案，也就是原始方案，只減少了21%的Compaction數(shù)據(jù)量。

綜合上述兩個分析可以得出，多個LSM-tree的解耦方案并不是最佳選擇，需要進一步優(yōu)化設(shè)計。

2.3 設(shè)計方案

DEPART，分布式KV存儲系統(tǒng)的副本解耦方案

在存儲層對主副本和冗余副本進行解耦，然后根據(jù)功能需求，對解耦出的主副本和冗余副本進行差異化的管理，如下圖。

對于主副本：仍然使用LSM-tree架構(gòu)來存儲，但LSM-tree架構(gòu)更加輕量級，從而保證高效的讀寫和范圍查詢性能；

對于冗余副本：設(shè)計了一個有序度可調(diào)的兩層日志架構(gòu)進行存儲，可根據(jù)上層應(yīng)用的性能需求在讀寫性能之間做權(quán)衡。

2.4 方案挑戰(zhàn)

a. 挑戰(zhàn)一：如何設(shè)計副本區(qū)分機制

實現(xiàn)主副本和冗余副本的解耦，下圖是一個輕量級的副本區(qū)分機制。

如圖，當(dāng)一個節(jié)點收到KV數(shù)據(jù)后，采用和Coordinator相同的步驟，首先計算Key的哈希值，然后根據(jù)一致性哈希數(shù)據(jù)分布機制，可以映射得到該KV劃分到的節(jié)點ID。

如果計算得到的節(jié)點ID等于當(dāng)前節(jié)點，那么就說明這個KV數(shù)據(jù)是通過一致性哈希機制映射到當(dāng)前節(jié)點的，則該KV數(shù)據(jù)會被識別為主副本，并且存儲在LSM-tree當(dāng)中，否則這個KV數(shù)據(jù)就是通過復(fù)制策略從其他節(jié)點發(fā)送過來的冗余數(shù)據(jù)，則當(dāng)前節(jié)點將其識別為冗余副本，并且存儲在兩層日志當(dāng)中。

該解耦方案僅僅基于簡單的哈希計算，因此是低開銷的。此外，它在每個存儲節(jié)點上獨立執(zhí)行，因此不會影響上層的數(shù)據(jù)分布機制以及一致性協(xié)議。

b. 挑戰(zhàn)二：如何設(shè)計有序度可調(diào)的兩層日志架構(gòu)

(1) 對于解耦出的冗余副本，應(yīng)該如何進行高效的管理，使其滿足不同場景下的性能需求？這里設(shè)計了一個有序度可調(diào)的兩層日志架構(gòu)。

如上圖，當(dāng)節(jié)點收到冗余副本后，首先以批量追加的方式將冗余副本快速寫入到全局日志中，形成一個segment文件，這里的segment文件類似于LSM-tree當(dāng)中的SSTable文件，從而保證冗余副本可以高效的寫入磁盤。

(2) 然后使用一個后臺線程，將全局日志中的數(shù)據(jù)分割到不同的本地日志中，如下圖。

需要注意的是，每個本地日志用來存儲一類冗余副本，他們所對應(yīng)的主副本存儲在相同的節(jié)點，比如這里本地日志LOGi，就用來存儲對應(yīng)主副本在節(jié)點i的這類冗余副本。

這樣做的好處是可以實現(xiàn)細(xì)粒度的冗余副本管理，對于不同節(jié)點發(fā)送過來的冗余副本，使用不同的本地日志進行獨立管理，從而可以保證高效的冗余副本讀寫性能，并且當(dāng)恢復(fù)數(shù)據(jù)時，只需要讀取相應(yīng)的本地日志，避免了掃描所有的冗余副本，也可以提高數(shù)據(jù)恢復(fù)的效率。

(3) 其次，對于本地日志內(nèi)部的數(shù)據(jù)管理也需要詳細(xì)設(shè)計。

考慮到根據(jù)一致性哈希數(shù)據(jù)分布策略，每個節(jié)點會負(fù)責(zé)若干范圍段的數(shù)據(jù)，基于該特征，進一步設(shè)計了基于范圍的數(shù)據(jù)分組機制。

根據(jù)定義的范圍段，將本地日志進一步劃分成不同的獨立組，不同組之間的數(shù)據(jù)沒有重疊。比如節(jié)點2中的本地日志LOG0專門用來存儲對應(yīng)主副本在節(jié)點0上的冗余副本，又考慮到節(jié)點0中的主副本包含0-10、51-60等范圍段，因此節(jié)點2中的本地日志LOG0被劃分為Group 0[0-10]和Group 1[51-60]等若干組。

數(shù)據(jù)分組可以有效提高數(shù)據(jù)GC以及恢復(fù)性能，因為GC和數(shù)據(jù)恢復(fù)操作只需要讀取相應(yīng)的組即可，避免了掃描整個的本地日志。

(4) 對于每個組內(nèi)的數(shù)據(jù)組織進行詳細(xì)的設(shè)計。

每個組會包含若干個sorted run文件,當(dāng)分割全局日志時，每次分割操作都會在第2層的本地日志的組內(nèi)產(chǎn)生一個sorted run文件，這些sorted run文件內(nèi)部的KV數(shù)據(jù)是完全有序的，但sorted run文件之間的KV數(shù)據(jù)并未排序。因此，可以通過調(diào)整組內(nèi)sorted run文件的個數(shù)來決定兩層日志的有序度，從而在讀寫性能之間做權(quán)衡。

比如，當(dāng)組內(nèi)的sorted run文件個數(shù)越少，則兩層日志的有序度越高，這時候讀操作需要檢查的sorted run的文件個數(shù)也就越少，因此讀性能會越好，但需要執(zhí)行更頻繁的合并排序操作，從而導(dǎo)致寫性能會越差；反之，兩層日志的有序度越低，合并排序開銷越少，則寫性能會越好，但讀操作需要檢查的sorted run文件個數(shù)也就越多，導(dǎo)致讀性能會越差。

（5）如何設(shè)置兩層日志的有序度。

考慮到有序度會決定系統(tǒng)的讀寫性能，因此可根據(jù)上層應(yīng)用的性能需求，來設(shè)置不同的有序度。

比如對于讀密集型應(yīng)用，或者系統(tǒng)配置為高的讀一致性等級，則可以通過減少組內(nèi)sorted run文件的個數(shù)來將兩層日志設(shè)置為高有序度，以保證好的讀性能；否則可以通過增加組內(nèi)sorted run文件的個數(shù)，來將兩層日志設(shè)置為低有序度，從而保證好的寫性能。

c. 挑戰(zhàn)三：副本解耦后如何加速數(shù)據(jù)恢復(fù)操作

副本解耦后，通過一種并行的恢復(fù)機制，以利用數(shù)據(jù)解耦存儲的特征來加速數(shù)據(jù)恢復(fù)操作。

如圖步驟①中，當(dāng)為節(jié)點上的數(shù)據(jù)構(gòu)建Merkle tree以檢測丟失的數(shù)據(jù)時，使用兩個線程，并行地從LSM-tree的主副本和兩層日志的冗余副本中讀數(shù)據(jù)。

當(dāng)修復(fù)多個范圍段的丟失數(shù)據(jù)時，如圖步驟③，同樣使用兩個線程，并行地從LSM-tree的主副本和兩層日志的冗余副本中讀寫數(shù)據(jù)。

三、實驗

3.1 實驗設(shè)置

●?在6個節(jié)點（5個存儲節(jié)點，1個客戶端節(jié)點）組成的本地集群中運行所有實驗， 10 Gb/s以太網(wǎng)交換機；

●?工作負(fù)載：使用YCSB 0.15.0來生成工作負(fù)載，KV對大小為1KB，生成的工作負(fù)載服從Zipf分布 (0.99)；

●?參數(shù)：默認(rèn)采用三副本，并且將寫一致性等級和讀一致性等級默認(rèn)設(shè)置為1（WCL=ONE, RCL=ONE）。

3.2 比較

●?Cassandra v3.11.4? VS? multiple LSM-trees (mLSM) VS DEPART

●?DEPART builds on Cassandra v3.11.4

在開源的分布式KV存儲系統(tǒng)Cassandra上實現(xiàn)了原型系統(tǒng)DEPART，同時也實現(xiàn)了多個LSM-tree的簡單解耦方案。將DEPART與Cassandra、多個LSM-tree的解耦方案分別進行性能比較，以展示系統(tǒng)DEPART的設(shè)計優(yōu)勢。

實驗一：基準(zhǔn)測試

實驗一分別測試了不同KV系統(tǒng)的寫、讀、范圍查詢和更新操作的吞吐量。

由實驗結(jié)果可知，相比于Cassandra，系統(tǒng)DEPART可以顯著提升所有操作的吞吐量。而對于多個LSM-tree的解耦方案，其可以較好地提升Cassandra的讀性能，但對Cassandra的寫性能提升非常有限。主要原因是多個LSM-tree的解耦方案會導(dǎo)致解耦出的每個LSM-tree仍然需要執(zhí)行頻繁的Compaction操作，以維護每層數(shù)據(jù)的完全有有序，從而導(dǎo)致總的Compaction開銷仍然非常嚴(yán)重。

實驗二：不同一致性配置

實驗評估了不同一致性配置下的系統(tǒng)性能。這里對于強一致性等級，考慮了三副本下不同的寫一致性等級和讀一致性等級配置。

由實驗結(jié)果可知，與Cassandra相比。系統(tǒng)DEPART可以在不同一致性配置下均可以提高所有操作的吞吐量，并且相比于多個LSM-tree的解耦方案，DEPART可以有效提高寫入和更新操作的吞吐量。

然而，當(dāng)讀一致性等級（RCL）配置為大于1時，與Cassandra相比，DEPART的讀性能收益會變小，并且DEPART的讀性能還要略差于多個LSM-tree的解耦方案。其主要原因是，在這種讀一致性配置下，每個讀請求需要成功訪問至少兩個副本，因此必須搜索兩層日志當(dāng)中的冗余副本；又由于兩層日志中的冗余副本并未完全排序，因此讀取兩層日志的性能要低于讀取完全排序的LSM-tree的主副本。

注意，DEPART的讀性能仍然要好于Cassandra，因為副本解耦后，DEPART搜索的數(shù)據(jù)量更少，但是DEPART的讀性能要差于多個LSM-tree，因為多個LSM-tree保持冗余副本完全有序。

實驗三：數(shù)據(jù)恢復(fù)性能

分別測試當(dāng)恢復(fù)不同數(shù)據(jù)量時所需要的時間。

與Cassandra相比，DEPART將恢復(fù)時間減少38%-54%，主要原因是并行修復(fù)機制可以并行地讀寫主副本和冗余副本。

實驗四：有序度參數(shù)S對系統(tǒng)讀寫性能的影響

如表格所示，當(dāng)S的值為1時，兩層日志會變?yōu)閮蓪覮SM-tree，KV數(shù)據(jù)是完全有序的，因此它可以獲得最高的讀吞吐量。但由于頻繁的合并排序操作，這時候?qū)懲掏铝渴亲畹偷摹?/p>

當(dāng)S的值從1不斷增大時，兩層日志的有序度會不斷降低，故合并排序開銷逐漸減小，因此寫性能會不斷增加，而讀性能會不斷降低。

因此，可以通過調(diào)整S的取值，在讀寫性能之間做合適的權(quán)衡。

四、總結(jié)

DEPART是一個基于副本解耦的高性能和高可靠的分布式KV存儲系統(tǒng)，包括輕量級副本解耦方案、兩層日志架構(gòu)、有序度可調(diào)機制、并行恢復(fù)機制等關(guān)鍵模塊設(shè)計。

KV研究熱點總結(jié)與展望

首先，目前KV領(lǐng)域的絕大部分工作都集中在優(yōu)化KV存儲引擎上，例如改進LSM-tree架構(gòu)，以減輕讀寫放大問題，以及結(jié)合新型硬件來重新設(shè)計KV存儲引擎等等。

但在KV系統(tǒng)的數(shù)據(jù)容錯層，相關(guān)研究極少，我們進行了初步探索，觀察到當(dāng)前統(tǒng)一的多副本管理會極大加劇KV系統(tǒng)的讀寫放大，因此研究設(shè)計了基于副本解耦的多副本差異化管理框架，極大提升了系統(tǒng)性能。這項工作基于Cassandra開源平臺實現(xiàn)，并可以應(yīng)用在TiKV等一系列基于LSM-tree的分布式KV存儲系統(tǒng)中。

對于KV系統(tǒng)未來的研究方向，可以結(jié)合應(yīng)用層的需求和緩存特征來進行特定的KV系統(tǒng)設(shè)計。例如，研究設(shè)計一種屬性感知的內(nèi)存KV系統(tǒng)，使其在存儲結(jié)構(gòu)上能夠支持對數(shù)據(jù)屬性值的高效讀寫，最終部署到云存儲平臺，以高效支撐SQL數(shù)據(jù)庫等應(yīng)用。此外也可以結(jié)合上層應(yīng)用的其他特征和需求來設(shè)計針對性的KV存儲系統(tǒng)。

詳細(xì)內(nèi)容請參閱論文《DEPART: Replica Decoupling for Distributed Key-Value Storage》