Key-value 存儲簡介

具備高可靠性及可擴展性的海量數據存儲對互聯網公司來說是一個巨大的挑戰，傳統的數據庫往往很難滿足該需求，并且很多時候對于特定的系統絕大部分的檢索都是基于主鍵的的查詢，在這種情況下使用關系型數據庫將使得效率低下，并且擴展也將成為未來很大的難題。在這樣的情況下，使用 Key-value 存儲將會是一個很好的選擇。

它被廣泛應用于緩存，搜索引擎等等領域。

???????? 根據以上的描述，一個好的 key-value 存儲需要滿足哪些條件呢？

l ? Availability 可用性

l ? Scalability 可擴展性

l ? Failover 故障恢復

l ? Performance 高性能

簡單來說，就是數據不能丟失，服務不能中斷，能對故障進行感知并能自動恢復，讀寫性能極高。

文件存儲

這一部分比較大，以后會另開主題寫

單文件還是多文件

不少 nosql 的產品采用的是單文件存儲的，數據量大以后肯定會遇到性能瓶頸，這一點無需多說，我想強調的是，采用多文件存儲數據優點還是非常多的，不過也需要注意，操作系統對于能夠打開的文件數目是由限制的，貌似 Linux 好像是 1024 （待確認），

Only Append

為了支持更快的寫操作，數據文件的寫操作只支持 append ，這個就不多說了，相信大部分的海量存儲設計都是這樣的。因此，更新操作等價于寫操作，不過在寫的時候第一步判斷寫到樹的哪個位置時肯定會定位到樹已有的節點上，這樣可以使得這次寫失效或者直接覆蓋。

這樣存在一個問題，就是對于失效的數據（比如更新過的數據）如何處理，比較好的辦法是啟動獨立線程定時或手動進行清理，請注意，這是一個非常巨大的過程，它將耗光你的 CPU 和 I/O ，因為要進行頻繁計算和數據遷移。

數據結構

B Tree 家族這一數據結構被廣泛的運用于數據庫索引，如 Mssql 的 B+tree ， oracle 的 B-tree ，熟悉索引的朋友一定很清楚，這種數據結構非常適合作為我們的 Key-value 存儲的數據結構 . 關于 B+tree ，可以參見下圖：它是一個多路搜索樹 , 數據存儲在葉子節點上，非葉子節點作為葉子節點的索引，加速數據的查找，而葉子節點是一個有序的鏈表，每次搜索都會到達葉子節點才會結束，插入新數據可能會引起節點的分裂。

在本篇文章中，你需要知道，上層的節點成為 IN （ Internal Node ） , 它持有其他節點的引用，葉子節點的上層是（ Bottom Internal Node ），而葉子節點則是存儲數據的節點。

??

圖片來自： http://blog.csdn.net/manesking/archive/2007/02/09/1505979.aspx

這部分是純粹的數據結構，就不多說了，如果想深入了解的話可以看看這篇論文《 The Ubiquitous B-Tree 》

設計要點

Partition

因為系統要具備高擴展性，因此，增加刪除機器是頻繁的操作，如何將數據均勻分散到集群中呢？比較常用的辦法是 hash 取模的辦法，但是這樣一來，增加機器的瞬間，按照之前的 hash 取模方式，數據無法讀取，這意味著需要對數據進行遷移，等待機器預熱，這是很不好的辦法。

目前比較公認的解決辦法就是一致性哈希 (consistent hashing)

首先按照機器的 hash 進行順時針分布，如圖，目前有 5 臺機器，如果有一個讀寫請求，那么 hash 該 key 值得的一個 hash 值，定位到環上，如果沒有定位到具體的機器，那么按照順時針查找，找到的第一個機器就是目標節點。

如果需要新增機器，增加過程為，首先 hash 新機器得到其位置，加入新機器 F ，這時訪問策略不變，那么按照之前的策略，如果 hash 到 C-F 之間的數據就無法找到了，但是這樣一來影響就局限于 C-F 之間，不象之前需要整體遷移了。

最后，為了降低增加機器所帶來的影響，我們可以為其增加虛擬節點（ virtual nodes ）。這樣的話服務器在環上的分布就比較均勻，這樣多個虛擬節點將對應一個我們的物理節點，增加機器所受到的影響也會變得最小。

Replication

為了達到高可用性和數據不丟失，我們需要通過復制將數據備份到多臺機器， replication 的實現機制一般是通過 Master 與 replica 之間的 TCP/IP 連接，然后根據相應的一致性策略將數據分發到 replica 上，這里的一致性策略主要包括兩項：

1. ???????? replica 能夠延遲 master 的時間，這個的意思就是說，在這個時間內更新的數據， replica 可能是看不到的。例如你設置的一致性時間是 3s ，那么在某個特定的時刻， replica 上的數據實際上可能是 master3s 以前的 snapshot 。

2. ???????? master 事務提交返回之前是否需要得到 replica 的確認。為了盡量保證數據不丟失， master 需要得到一定數量的 replica 確認數據更新成功之后才能提交事務。

關于數據可靠性和性能之間，是需要進行折衷的，很顯然，越是高的數據保障，那么性能肯定會受到影響。在這樣的情況下，需要對上層的應用進行分析，看是否允許丟失一部分數據。

另外，還有一個問題就是，數據的同步是采用 master 分發還是 replica 定時請求的問題，兩者各有優缺點，前者會在 replica 較多的情況下遇到瓶頸，而后者可能會有一些延遲。多級同步的方式能在一定程度上解決這個問題，即 master 向某些機器同步，而這些機器向其他機器同步。

當然， master 管理寫請求而 replica 管理讀請求，至于如何決定讀寫請求的分發，我們可以使用 monitor 節點，由它來作為讀寫的入口， 如下圖，然后 Monitor 管理集群的狀態和生命周期，例如 Master fail 后， monitor 將收到事件，它將發起一次選舉選出新的 Master ，一般的選舉算法就是在集群中尋找最后一次更新的節點，因為往往它的數據是最新。還有就是在有新的機器加入集群的情況下， Monitor 會告訴新機器集群內的 master 是誰， replica 機器才能與 master 取得連接同步數據。

<!--[if gte mso 9]><xml> <o:OLEObject Type="Embed" ProgID="Visio.Drawing.11" ShapeID="_x0000_i1025" DrawAspect="Content" ObjectID="_1344072934"> </o:OLEObject> </xml><![endif]-->

使用 Monitor 的 Master-replica 集群

?

當然，自從有了 ZooKeeper ，這種監控和協同的臟活累活就可以都交給它了，利用 ZooKeeper 管理集群內節點的健康狀況具備很大的便利，畢竟，上面這個辦法的架構存在單點問題，最后肯定 Monitor 會拖集群的后腿。所以用 ZooKeeper 管理集群并且針對不同的事件作出響應。下面是一個示意圖：

<!--[if gte mso 9]><xml> <o:OLEObject Type="Embed" ProgID="Visio.Drawing.11" ShapeID="_x0000_i1026" DrawAspect="Content" ObjectID="_1344072935"> </o:OLEObject> </xml><![endif]-->

用 ZooKeeper 管理集群

最后，關于事務提交時的處理策略也值得注意，你需要為 master 和 replica 都指定 . 一般情況下，我們需要在減少頻繁的 I/O 操作和數據保障性方面進行折衷，以下提交策略可選：

1. ???????? 在事務提交時將數據由內存刷到硬盤，這樣數據具有最高的保障，但是你需要等待昂貴的 I/O 操作。

2. ???????? 在事務提交時將數據刷到操作系統 buffer 中，然后由操作系統自己決定何時刷到硬盤。這樣可以在虛擬機掛了的情況下保證數據不丟失，但是不能 hardware failture

3. ???????? 在事務提交時數據仍然維持在內存中，而在存儲系統比較閑的時候進行持久到硬盤的操作，或在內存不夠用的情況下進行寫磁盤操作。

Get 和 Put 操作

這兩個動作是 key-value 存儲系統最核心的兩個操作，因此在設計上需要做更多的考慮。

下面是一種寫操作的過程：

1. ???????? 執行 tree 搜索以定位插入數據所在的位置

2. ???????? 鎖定該位置的父節點

3. ???????? 創建新的葉子節點

4. ???????? 將葉子節點寫入。這個寫操作發生在內存中，并且返回一個 number 它決定了葉子節點寫到硬盤的位置

5. ???????? 修改父節點指向該葉子節點的引用。該父節點既持有指向內存的葉子節點的引用又持有磁盤的位置的 number 。

6. ???????? 標記該父節點為 dirty( 意味著內存中的版本沒有出現在磁盤中 )

7. ???????? 解鎖該父節點

請注意，很明顯，這個寫操作完全發生在內存中，那么何時將數據同步到磁盤呢？這就是后面要講的 checkpoint 。通過它定時的將內存中的臟數據寫到硬盤。

讀操作就簡單很多了，搜索 tree ，定位到葉子節點，取出數據就行了，當然還有一些包括為緩存服務的操作就不細講了（比如，為每個節點計數，每次對該節點的訪問都使得其 +1 ，這樣在緩存 evict 的時候就很有用了）

上面所說的寫操作在內存中并不會影響到讀操作，因為，為了加快讀操作，我們會在啟動時預加載硬盤數據文件的內容到內存，由于只有葉子節點存儲數據，因此我們需要根據加載的葉子節點還原整棵 B+tree ，毫無疑問這是一個耗時的操作，但是卻是值得的。

數據模型

這塊比較大，這里只重點講一下以什么數據結構存取的問題。

首先需要解決的是，存儲對象的問題，很顯然，我們都有存取對象的需求，那么如何將對象轉換為我們的底層存儲格式呢？一般的辦法有序列化， Json ， XML 之類，下面依次講一下優缺點：

1. ?????? 序列化。可能是比較簡單易實現的辦法，但是空間占用過大

2. ?????? Json 和 XML 都差不多，存儲格式比較可讀一點，解析和轉換比較方便，不過對于數據量大的情況還是不推薦。

3. ?????? 字符串或者字節數組。我們按照一定的約定將對象拼成字符串，或者一次將對象的屬性寫入到字節數組，讀取時按照相同的順序解析即可，比較好的辦法是定義一個接口，然后由客戶端去實現對象字符串之間轉換順序的方法。這個比較推薦。

還有一些序列化的工具值得推薦，比如 hadoop 下的 avro 。

Checkpoint

和普通的關系型數據庫一樣， key-value 也可以有自己的 checkpoint ，一般情況， checkpoint 是為了減少數據恢復所需要的時間 . 在檢查點到來時，按照之前的設計，它會將所有的 dirty Internal Node 寫入 log ，這樣會存在一個問題，大多數情況下， checkpoint 會把整棵樹寫到 log, 解決問題的辦法是我們采用增量的辦法進行 log ，例如，如果有 a 和 b 加入到某個父節點。那么此時如果進行 checkpoint 時我們需要首先寫一個完整的 IN 引用，并且記錄對其進行的操作， add a ， add b ，這些操作記錄在一個 list 中，當 list 變得過大以后我們又重新寫一個完整的 IN 節點。

過期數據清理

這一部分只針對按照順序寫并且僅 append 的情況，為了減少 I/O 操作，無效數據僅僅被標記為 delete 且刪除內存中對應的樹的葉節點而不進行物理的刪除，那么長期下去，失效數據會很多，這時候需要進行清理，一般的策略就是，當失效數據在文件中所占比例達到一定程度以后，執行清除操作。

1. ???????? 首先根據預先存儲的記錄信息判斷哪些文件需要進行清理操作。

2. ???????? 掃描文件，找到仍然 active 的數據，拷貝到新的文件，掃描完成后刪除此文件。

請注意，在寫操作密集的情況下，這會造成競爭，因此盡量在訪問量少的情況下執行此操作。

另外，可以使用多線程來進行清理操作。當然還有很多策略可以在清理的時候使用，比如，緩存一個葉子節點的父節點，在鎖住該父節點執行遷移操作的時候可以順便掃描該父節點下的其他葉子節點。

Need More ？

復雜查詢

人的欲望是無止境的 ……. 除了基于主鍵的檢索你可能還需要基于某個屬性的檢索，最好還能在多個屬性上查詢完了以后來個取交集，這個時候怎么辦呢？

首先，我們有一個基于主鍵的 key-value 數據庫， key 存儲的主鍵，而 value 存儲的對象（物理存儲為 byte 數組），那么假如我們想對對象的某個屬性如 name 進行查詢的話，那么我們可以再建一個數據庫， key 是待查詢的字段， value 是主鍵數據庫的 id 。

Primary Database

Key(ID)	Value(Object)
1	Byte[]
2	Byte[]

Secondary Database

Foreign Key(Name)	Value(ID)
dahuang	2
tugou	1

這樣一來按照 name 查詢只需要查詢一次 secondary database 取出主鍵 id ，再查一查 primary database 即可，這有點像正排索引和倒排索引的概率，如果對于多個字段的組合查詢，只需要對其進行一次 join 即可，在 join 的時候可以先對待 join 的結果按照結果集大小進行排序，這樣可以省下不少時間消耗。

雖然 key-value 存儲按照上面的描述也可以支持多條件查詢，但是不建議這樣做，一是建立索引（二級數據庫）需要額外的空間，二是這樣需要多次查詢影響性能，不管怎么樣適度的折衷吧。

最后不得不提一下，由于 B+tree 的數據結構，它很好地支持 范圍查詢 （查詢可以不下到葉子節點）可以極大的彌補搜索引擎中倒排索引進行范圍查詢需要全部掃描的缺陷。這也是其應用場景之一。

總結

Key-value 在海量數據存儲中占據很重要的地位，對于它的深入研究能帶給我們很多啟發，而它在某些局部問題上所表現的優秀的能力也值得我們關注。本文大致總結了一下目前所了解的一些問題，沒有提到的東西還有很多（文件系統設計，事務，緩存等等），接下來如果有空會對文件系統設計進行詳細講解。

聲明

首先，本文只是代表本人的一些淺見，不代表任何官方意見。其次，由于作者水平的原因，肯定會出現錯誤，歡迎指正（最好站內，給我留一點臉面 -_- ）

參考文獻：

Dynamo: Amazon’s Highly Available Key-value Store

http://blog.csdn.net/manesking/archive/2007/02/09/1505979.aspx (BTree,B-Tree,B+Tree,B*Tree 都是什么 )

海量數據存儲之Key-Value存儲簡介