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

羅 常

（廣東電網公司茂名供電局，廣東茂名 525000）

0 引言

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

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

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

1 分布式存儲技術簡介

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

2 Dynamo系統特點及架構

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

（1）分布式存儲、去中心節點；

（2）key-value模式；

（3）高容錯性；

（4）復合技術解決一致性問題；

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

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

3 Dynamo系統核心技術

3.1 分布式哈希（Distributed Hash Table）

為了達到去中心化的設計目的，DHT通過基于key-based路由策略來找到對應的存儲節點（如圖1所示）：

圖1 分布式哈希圖

（1）整個分布式系統組成一個環，環根據節點的數目被化分為對應的區域；

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

（3）每個節點負責一個區域。

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

圖2 Hash算法步驟

3.2 矢量時鐘（Vector clock）

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

3.3 暗示移交(Hinted handoff)

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

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

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

基于上述hint中的目標接收信息，通過消息中心發給目標接收的節點（即恢復的節點）；

接收節點收到消息后，應用這個hint到本地。

3.4 Merkle樹

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

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

3.5 Gossip協議

Gossip是同步協議，主要用于分布式的非強一致性系統，以此來同步各節點狀態。

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

（1）節點心跳；

（2）節點狀態（失效檢查）；

（3）節點實時負載。

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

（1）節點A→節點B，節點A發向節點B的請求信息（Gossip Request Message）；

（2）節點B→節點A，節點B發向節點A的確認信息（Gossip Ask Message）；

（3）節點A→節點B，節點A發向節點B的回應信息（Gossip Response Message）。

另外，上述消息傳遞系統可以檢測是否出現故障的節點。

4 具體實現

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

請求的協調基于事件驅動的原理，多個類SE?DA結構構成了消息處理管道。使用Java NIO Channels處理所有的數據通信。執行讀取和寫入是協調員的基本職責，即讀取一個或多個節點數據和寫入一個或多個節點存儲的數據。系統為每個客戶的請求創建一個狀態機，包含以下邏輯：

（1）標識負責一個key的節點；

（2）發送請求；

（3）等待回應；

（4）重試處理；

（5）加工包裝回客戶端的響應。

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

5 總結

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

［1］金海，袁平鵬.語義網數據管理技術及應用［M］.北京：科學出版社，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］.北京：電子工業出版社，2009.