基于K-V模式的高可用性分布式存儲技術(shù)研究

羅 常

（廣東電網(wǎng)公司茂名供電局，廣東茂名 525000）

0 引言

隨著互聯(lián)網(wǎng)的推廣，越來越多的人更加依賴于網(wǎng)絡(luò)。新型互聯(lián)網(wǎng)技術(shù)的出現(xiàn)，使得人們的生活變得更加網(wǎng)絡(luò)化。隨之而來的是大數(shù)據(jù)問題，其中首當(dāng)其沖的就是數(shù)據(jù)的存儲問題，以及數(shù)據(jù)庫實時響應(yīng)問題。以2013年阿里巴巴雙十一活動當(dāng)天的數(shù)據(jù)為例，2013年11月11號，阿里巴巴公司旗下支付寶全天成交額高達(dá)350億，支付寶達(dá)成的交易筆數(shù)為1.7億筆，全天總訂單數(shù)量為1.67億個，一天內(nèi)最高峰值為13 637人同時成功付款[1-2]。

透過阿里巴巴公司的數(shù)據(jù)，可以看出互聯(lián)網(wǎng)對數(shù)據(jù)庫存儲以及實時性的高要求。然而根據(jù)CAP原理（一致性、可用性、分區(qū)容忍性），傳統(tǒng)數(shù)據(jù)庫沒有分區(qū)容忍性，而是數(shù)據(jù)集中存儲，導(dǎo)致了系統(tǒng)吞吐量和性能上無法滿足現(xiàn)在互聯(lián)網(wǎng)的需求，再加上為了防止單點故障，數(shù)據(jù)必然有備份與復(fù)制，在強一致性的要求下，又必將以損失性能為代價。種種跡象表明傳統(tǒng)數(shù)據(jù)庫技術(shù)已經(jīng)無法滿足現(xiàn)在互聯(lián)網(wǎng)公司的需求[3]。

所以，在這種情況下，分布式存儲技術(shù)誕生了。分布式存儲技術(shù)憑借其獨特的高可用性、完全分布式存儲，以及實時性高等，已經(jīng)成熟被應(yīng)用到各家大型互聯(lián)網(wǎng)公司，比如百度、騰訊和阿里巴巴等[4]。

1 分布式存儲技術(shù)簡介

傳統(tǒng)關(guān)系數(shù)據(jù)庫在很多應(yīng)用場合出現(xiàn)了瓶頸，例如磁盤I/O瓶頸、可擴展性較差、分表分庫、主從復(fù)制不易實施、無法不間斷遷移等等，而NoSQL（Non relational，或者Not Only SQL，非關(guān)系型數(shù)據(jù)庫）彌補了關(guān)系型數(shù)據(jù)庫的不足，吸引大量開發(fā)人員參與研究。根據(jù)數(shù)據(jù)的存儲模型和特點，NoSQL可以分為key-val?ue存儲、列式存儲、文檔式存儲、對象式存儲等。其中K-V存儲模式使用比較廣泛，比較典型的有亞馬遜的Dynamo系統(tǒng)。

2 Dynamo系統(tǒng)特點及架構(gòu)

Dynamo是一個完全分布式的、無中心節(jié)點的、高可靠性、高可用性和容錯能力具有良好的系統(tǒng)。Dynamo作為key-value模型存儲平臺，性能、擴展性、可用性較好，得到了廣泛的應(yīng)用。一般情況下，它能保證99.99%的讀寫訪問響應(yīng)時間都在300 ms內(nèi)。一個Dynamo存儲平臺其實是由多個不同的存儲機器構(gòu)成的，各機器獨立且角色類似。各個存儲機器都存放一部分?jǐn)?shù)據(jù)文件，系統(tǒng)會自動完成這些數(shù)據(jù)的備份，由于系統(tǒng)的完全分布特點，不會因為單臺機器斷電等故障影響到系統(tǒng)的對外服務(wù)。Dynamo系統(tǒng)特點如下：

（1）分布式存儲、去中心節(jié)點；

（2）key-value模式；

（3）高容錯性；

（4）復(fù)合技術(shù)解決一致性問題；

（5）高可用性和擴展性。

在設(shè)計方面，Dynamo系統(tǒng)遵循以下幾條原則：（1）可擴展性：Dynamo每一級應(yīng)保證能擴展一臺存儲主機，并對系統(tǒng)及其操作者的影響比較小；（2）對稱性：dynamo應(yīng)能夠平等對待每個節(jié)點，保證每個節(jié)點有相同的性能；（3）去中心化：避免集中控制技術(shù)，延伸對稱特性，保證有利于去中心化；（4）異質(zhì)性：系統(tǒng)能夠在異質(zhì)性的基礎(chǔ)設(shè)施運行。

3 Dynamo系統(tǒng)核心技術(shù)

3.1 分布式哈希（Distributed Hash Table）

為了達(dá)到去中心化的設(shè)計目的，DHT通過基于key-based路由策略來找到對應(yīng)的存儲節(jié)點（如圖1所示）：

圖1 分布式哈希圖

（1）整個分布式系統(tǒng)組成一個環(huán)，環(huán)根據(jù)節(jié)點的數(shù)目被化分為對應(yīng)的區(qū)域；

（2）每個區(qū)域用一個范圍值 token表示(n-1，n]；

（3）每個節(jié)點負(fù)責(zé)一個區(qū)域。

Hash算法往往有很多，為了保證Dynamo分布式系統(tǒng)的高可用性，通常采用MD5作為hash算法來分配key值給環(huán)上的區(qū)域，具體步驟如圖2所示。

圖2 Hash算法步驟

3.2 矢量時鐘（Vector clock）

使用Dynamo矢量時鐘以獲取同一個對象在不同時間的因果關(guān)系。矢量時鐘可以看做是節(jié)點（node），計數(shù)器（counter）列表。每個版本的矢量時鐘是與每個對象相關(guān)聯(lián)，其對象有因果或平行分支關(guān)系。Dynamo中，當(dāng)客戶端更新一個對象，它必須指定哪一個版本更新。這可以通過它從早期的讀出操作接收到的上下文對象中指定，該對象包含一個向量時鐘信息。當(dāng)系統(tǒng)處理一個讀請求，如果Dynamo訪問多個語法不太協(xié)調(diào)的分支，它會返回對應(yīng)于該葉節(jié)點包含的上下文版本信息

3.3 暗示移交(Hinted handoff)

Hinted handoff是用來處理系統(tǒng)短暫的失效的方法，當(dāng)所有主要負(fù)責(zé)的N個節(jié)點均失效的情況下，它試圖將信息存放在非主要責(zé)任節(jié)點的一個特殊的位置，并記下一個hint，其包含這次寫操作的真正目標(biāo)節(jié)點信息。當(dāng)消息服務(wù)收到一個Gossip信號得知有新的節(jié)點從失敗中恢復(fù)過來時，它查看該節(jié)點有沒有需要移交(handoff)的數(shù)據(jù)。通過檢查它是否是那個hint提到的節(jié)點，如果是，包含hint的那個節(jié)點將向它移交(handoff)副本。

Hinted Handoff實現(xiàn)為一個后臺線程，并用一個隊列來記錄所有要移交的hint信息。

Hinted handoff處理流程：從隊列中取出一個待處理的hinted-handoff；進行移交工作的節(jié)點，通過上面提到的特殊的位置得hint相關(guān)信息；

基于上述hint中的目標(biāo)接收信息，通過消息中心發(fā)給目標(biāo)接收的節(jié)點（即恢復(fù)的節(jié)點）；

接收節(jié)點收到消息后，應(yīng)用這個hint到本地。

3.4 Merkle樹

Merkle Tree（MT），也叫Hash Tree，屬于一種樹狀Hash結(jié)構(gòu)。在此樹中，葉節(jié)點的值是哈希值，所述非葉節(jié)點的值是它的子節(jié)點來的哈希值。Dynamo中，每個節(jié)點存儲一個key值，不同節(jié)點的key值范圍區(qū)間會相互重疊。在去熵操作中，考慮的關(guān)鍵是兩個節(jié)點key值范圍區(qū)的交叉點。MT的葉節(jié)點是key值相交范圍區(qū)的每個key的哈希值，通過葉節(jié)點的哈希從下到上便可以構(gòu)建出一個MT。Dynamo通過比對MT跟出的hash是否一致來判斷是否交換子節(jié)點。

MT能夠幫助Dynamo系統(tǒng)節(jié)省大量的時間和空間。在分布式條件下，空間被定義為對應(yīng)于傳輸網(wǎng)絡(luò)的數(shù)據(jù)量。從時間角度來看，MT避免了全局線性時間的比較；在網(wǎng)絡(luò)傳輸上，MT查到某一層，就獲取該層所需要的哈希值，大大降低了傳輸?shù)臄?shù)據(jù)量。

3.5 Gossip協(xié)議

Gossip是同步協(xié)議，主要用于分布式的非強一致性系統(tǒng)，以此來同步各節(jié)點狀態(tài)。

在去中心化的集群環(huán)境里，各節(jié)點同其他節(jié)點交換實時信息是極其重要的。這些實時信息包括：

（1）節(jié)點心跳；

（2）節(jié)點狀態(tài)（失效檢查）；

（3）節(jié)點實時負(fù)載。

Gossip只需要少量的網(wǎng)絡(luò)帶寬中央處理器。Gossip會定期隨機選擇一個節(jié)點啟動Gossip會話，其中每個Gossip都包含三個消息。比如，節(jié)點A啟動一個Gossip到節(jié)點B：

（1）節(jié)點A→節(jié)點B，節(jié)點A發(fā)向節(jié)點B的請求信息（Gossip Request Message）；

（2）節(jié)點B→節(jié)點A，節(jié)點B發(fā)向節(jié)點A的確認(rèn)信息（Gossip Ask Message）；

（3）節(jié)點A→節(jié)點B，節(jié)點A發(fā)向節(jié)點B的回應(yīng)信息（Gossip Response Message）。

另外，上述消息傳遞系統(tǒng)可以檢測是否出現(xiàn)故障的節(jié)點。

4 具體實現(xiàn)

Dynamo的本地持久化組件對不同的存儲引擎提供了不同的操作接口，因此能夠當(dāng)今眾多流行的數(shù)據(jù)庫，比如Berkeley數(shù)據(jù)庫，MySQL等。另外，它也有一個持續(xù)的后備存儲內(nèi)存緩沖機制。此持久性可插拔組件允許系統(tǒng)配置最適合的存儲引擎。比如，BDB一般都可以處理kB等級的對象，MySQL能夠處理MB甚至更大的對象。因此，如果對所有的對象采用統(tǒng)一引擎，勢必造成資源的浪費，而Dynamo根據(jù)處理對象的大小分布式選擇相應(yīng)的本地持久性引擎。

請求的協(xié)調(diào)基于事件驅(qū)動的原理，多個類SE?DA結(jié)構(gòu)構(gòu)成了消息處理管道。使用Java NIO Channels處理所有的數(shù)據(jù)通信。執(zhí)行讀取和寫入是協(xié)調(diào)員的基本職責(zé)，即讀取一個或多個節(jié)點數(shù)據(jù)和寫入一個或多個節(jié)點存儲的數(shù)據(jù)。系統(tǒng)為每個客戶的請求創(chuàng)建一個狀態(tài)機，包含以下邏輯：

（1）標(biāo)識負(fù)責(zé)一個key的節(jié)點；

（2）發(fā)送請求；

（3）等待回應(yīng)；

（4）重試處理；

（5）加工包裝回客戶端的響應(yīng)。

一般情況下每個狀態(tài)機只處理單個客戶端的請求。

5 總結(jié)

Dynamo經(jīng)過長時間應(yīng)用，它的高可用性得到了實踐證明：99.95%的應(yīng)用請求都成功收到無超時的響應(yīng)。雖然Dynamo存在著一致性的問題，但是該問題可以利用其他技術(shù)有效地解決。其次，在Dynamo中，用戶可以從自己的角度來設(shè)定三個參數(shù)值。在此之外，Dynamo還向系統(tǒng)的開發(fā)者們公布了系統(tǒng)協(xié)調(diào)一致性的邏輯上的問題。Dynamo的高可移植性使得移植應(yīng)用程序到Dynamo是非常容易的，針對不同的業(yè)務(wù)需求配置相應(yīng)的沖突協(xié)調(diào)機制可以大大提高系統(tǒng)效率。最后，Dynamo采用全成員(full membership)模式，每個節(jié)點都需要積極地與系統(tǒng)中的其他節(jié)點交換完整的路由表，以便知道其對等節(jié)點承載的數(shù)據(jù)，然而，這樣的設(shè)計以運比較多的節(jié)點的問題是路由表存儲的高成本，因此為了克服這種限制，需要通過對Dy?namo引入分層擴展技術(shù)。

［1］金海，袁平鵬.語義網(wǎng)數(shù)據(jù)管理技術(shù)及應(yīng)用［M］.北京：科學(xué)出版社，2010.

［2］ Hayes B.Cloud Computing［J］.Communications of the ACM，2008，51（7）：9-11.

［3］NAMJOSHI J， GUPTE A.Service Oriented Architecture for Cloud Based Travel Reservation Software as a Service［A］.Proceedings of the 2009 IEEE International Confer?ence on Cloud Computing（CLOUD’09）［C］.Sep 21-25， 2009， Bangalore， India.Los Alamitos，CA，USA：IEEE Computer Society，2009：147-150.

［4］王慶波，金何樂.虛擬化與云計算［M］.北京：電子工業(yè)出版社，2009.