Key-value 存儲簡介

具備高可靠性及可擴展性的海量數(shù)據(jù)存儲對互聯(lián)網(wǎng)公司來說是一個巨大的挑戰(zhàn)，傳統(tǒng)的數(shù)據(jù)庫往往很難滿足該需求，并且很多時候?qū)τ谔囟ǖ南到y(tǒng)絕大部分的檢索都是基于主鍵的的查詢，在這種情況下使用關(guān)系型數(shù)據(jù)庫將使得效率低下，并且擴展也將成為未來很大的難題。在這樣的情況下，使用 Key-value 存儲將會是一個很好的選擇。

它被廣泛應(yīng)用于緩存，搜索引擎等等領(lǐng)域。

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

l ? Availability 可用性

l ? Scalability 可擴展性

l ? Failover 故障恢復(fù)

l ? Performance 高性能

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

文件存儲

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

單文件還是多文件

不少 nosql 的產(chǎn)品采用的是單文件存儲的，數(shù)據(jù)量大以后肯定會遇到性能瓶頸，這一點無需多說，我想強調(diào)的是，采用多文件存儲數(shù)據(jù)優(yōu)點還是非常多的，不過也需要注意，操作系統(tǒng)對于能夠打開的文件數(shù)目是由限制的，貌似 Linux 好像是 1024 （待確認(rèn)），

Only Append

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

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

數(shù)據(jù)結(jié)構(gòu)

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

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

??

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

這部分是純粹的數(shù)據(jù)結(jié)構(gòu)，就不多說了，如果想深入了解的話可以看看這篇論文《 The Ubiquitous B-Tree 》

設(shè)計要點

Partition

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

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

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

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

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

Replication

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

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

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

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

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

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

<!--[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 集群

?

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

<!--[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 管理集群

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

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

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

3. ???????? 在事務(wù)提交時數(shù)據(jù)仍然維持在內(nèi)存中，而在存儲系統(tǒng)比較閑的時候進行持久到硬盤的操作，或在內(nèi)存不夠用的情況下進行寫磁盤操作。

Get 和 Put 操作

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

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

1. ???????? 執(zhí)行 tree 搜索以定位插入數(shù)據(jù)所在的位置

2. ???????? 鎖定該位置的父節(jié)點

3. ???????? 創(chuàng)建新的葉子節(jié)點

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

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

6. ???????? 標(biāo)記該父節(jié)點為 dirty( 意味著內(nèi)存中的版本沒有出現(xiàn)在磁盤中 )

7. ???????? 解鎖該父節(jié)點

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

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

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

數(shù)據(jù)模型

這塊比較大，這里只重點講一下以什么數(shù)據(jù)結(jié)構(gòu)存取的問題。

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

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

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

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

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

Checkpoint

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

過期數(shù)據(jù)清理

這一部分只針對按照順序?qū)懖⑶覂H append 的情況，為了減少 I/O 操作，無效數(shù)據(jù)僅僅被標(biāo)記為 delete 且刪除內(nèi)存中對應(yīng)的樹的葉節(jié)點而不進行物理的刪除，那么長期下去，失效數(shù)據(jù)會很多，這時候需要進行清理，一般的策略就是，當(dāng)失效數(shù)據(jù)在文件中所占比例達到一定程度以后，執(zhí)行清除操作。

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

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

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

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

Need More ？

復(fù)雜查詢

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

首先，我們有一個基于主鍵的 key-value 數(shù)據(jù)庫， key 存儲的主鍵，而 value 存儲的對象（物理存儲為 byte 數(shù)組），那么假如我們想對對象的某個屬性如 name 進行查詢的話，那么我們可以再建一個數(shù)據(jù)庫， key 是待查詢的字段， value 是主鍵數(shù)據(jù)庫的 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 的結(jié)果按照結(jié)果集大小進行排序，這樣可以省下不少時間消耗。

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

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

總結(jié)

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

聲明

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

參考文獻：

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 都是什么 )

海量數(shù)據(jù)存儲之Key-Value存儲簡介