Facebook從成立之初作為一個小型區域型社交網站，到如今演變成為全球最大的社交網站，架構經歷了過幾次重大的迭代。其中，Facebook的存儲也從從小變大，從單一變得更具有多樣性，從而應對各種拓展性問題。

本文將首先從Facebook的升級轉變開始，談到數據存儲能力提升對於公司Scalability的巨大影響，然後介紹Facebook在Canssandra和Hbase之間的選擇，從而引申出NoSQL將要解決的問題領域，最後集中介紹了NoSQL Pattern的基本組成。希望能在看完文章之後，大家可以對NoSQL要解決的問題，NoSQL的基本構成，以及NoSQL對於Facebook這樣大型公司的重要性有一定的認識。

Facebook的數據存儲進化

對於Facebook在數據處理能力上的進化，可以先列幾個文章標題來直觀感受一下：

• New Facebook Chat Feature Scales To 70 Million Users Using Erlang, May 14, 2008.

• Facebooks New Real-time Messaging System: HBase to Store 135+Billion Messages a Month Nov 16, 2010.

• Facebooks New Realtime Analytics System: HBase to Process 20 Billion Events Per Day Mar 22, 2011

第一篇文章是和Chat功能相關，主要是講通過選用Erlang來增加Server端的處理能力。後兩篇講的都是如何高效、穩定的存儲大量數據來為Facebook的其他application服務。而其中反覆出現的關鍵詞——Canssandra，HBase，就是解決Facebook面對大量數據時Scale的基礎。

Cassandra和HBase為何而生

如果比較Canssandra和HBase（可參考http://bit.ly/2akMsKo）以及他們的共同特點，就可以發現他們非常適合解決以下Scalability問題：

• 如何實現應用層「無狀態」？ 為了讓應用層可拓展，需要分離數據層，就要讓應用層處於「無狀態」，也就是應用層不因為數據層的影響

• 數據層如何延伸？ 這是包括Facebook很多公司公司都要面臨的問題

• 如何將合適地劃分數據在不同機器上，實現負載平衡

• 數據在多個機器上，如何處理機器壞掉的情況？

• 如何在機器之間備份數據？

• 在數據備份的時候，如何保持同步呢？

• 如何結合雲計算，實現伺服器數量的自動延伸？ 也就是，任務量大的時候，就增加機器數量，任務量少的時候，就減少機器數量。

• 因為機器數量可變，當任務量變化導致機器數量變化的時候，又如何重新分配數據呢？

為了解決這些Scalability問題，NoSQL出現了，它成了一種解決大型數據存儲問題的常用方案，Canssandra 和 HBase就是根據NoSQL概念而開發出來的具體產品。

於是，我們想要了解Facebook的架構知識，就細化成了了解Facebook如何處理大型數據，再而變成為Canssandra和Hbase如何處理數據，然後變成為：NoSQL通常意義上是如何解決Scalable數據存儲問題的！

NoSQL Pattern基本概念介紹（乾貨）

常見NoSQL 產品

上面是三大巨頭相對應的NoSQL解決方案，Google的Bigtable，還有Amazon的Dynamo可以參考這篇文章（http://bit.ly/29SEee6）。 Canssandra 是移植了Dynamo的分散式設計，加上BigTable的數據模型而開發出來的。

這三種產品的共同點是：

• 鍵-值存儲

• 大量廉價主機上運行

• 數據在這些主機之間以劃分和備份的形式存儲（也就是Partition和Replica）

• 相對較弱的一致性要求（關於一致性的概念可以參考這個剪短說明：http://bit.ly/29SFPR0）

NoSQL 到底是什麼

說了那麼多， Facebook的技術一直看到Google，Amazon， NoSQL到底是怎麼回事？它的結構和主要技術構成由下圖可以表示：

A. API Model (DB操作)

對於資料庫的常見操作：讀、寫、修改。

B. NoSQL底層架構

底層架構由上百或上千台計算機組成，每個計算機是一個物理節點（Physical Node），這些物理節點的configuration，CPU， 硬碟大小都不盡相同。在每一個物理節點上，又可以分成若干個虛擬節點（Virtual Node）：

C. Partition

因為整體的hashtable是要分布在VNs 上的，所以需要找到一個方法，把key和相應的VN結合起來。

（1）partition = key mod (total_VN)

這樣的缺點在於，如果VN的數量改變的話，會引起大量現存的key map改變，從而所有的數據重新分布，這樣效率顯然非常低。

（2）Consistent Hashing

這裡的Key Space是有限大小的，一般是將0到2^32-1數字頭尾相連，就結合成一個閉合的環形。將VN映射到環中，以順時針的方向計算，key的歸屬節點是它遇到的第一個節點。

所以只有在相鄰節點崩潰的情況下，數據才會重新分布，其他所有key依然存在各自的VN之中。

D. 數據複製（Replica）

複製數據的好處：

• 提升可靠性能

• 將工作量分散到有相同備份的其他節點上面（balance workload）

E. Node的變化（Membership Changes）

為了可以根據workload增刪節點，使資源利用效率最大，或者是因為節點錯誤而導致crash，這些情況下都需要根據Consitent hashing來設計相應的節點處理辦法。

（1）新加入一個節點

將新節點存在向其他節點傳播；

左右相鄰節點開始同步地改變各自keys，replicas；

新加入節點開始從相鄰節點copy data；

新加入的節點信息開始傳播到其他節點；

Case1：如果在節點新加入的時候，遠離這個node的其他node的membership view還沒有更新，所以在這個時候，request還是會指向old node；但是因為new node的相鄰節點信息已經更新，他們會將request指向new node。

Case2：如果新加入節點還處於data的更新狀態中，還沒有準備處理request；就需要用到vector clock來表明自身狀態，client就會去訪問其他replica。

（2） 節點離開或者崩潰

Crashed node不會再回應neighbors』的gossip 信息。

Neighbor會更新membership信息，並開始asynchronously copy crashed node data。

上面涉及到的節點都是VN，虛擬節點。在實際中還要將VN和PN聯繫起來。分配VN的時候，原則是盡量避免VN 的 replicas存在相同的PN上面。最簡單的實現方式就是，將VN隨機分配到PN上面，只要確保PN上不含有相同key range的VN即可。

當PN崩潰的時候，多個VN都會同時崩潰，但是因為VN的replicas隨機分布在不同PN上面，這樣因為crash引起的workload就會分布到多個PN上面。 t

F. Client Consistency（一致性）

當有了數據的很多備份之後，需要關心的問題就是如何在機器之間同步讓用戶有一個consistent view of the data。

一致性模型有：

• Strict Consistency（one copy serializability）。

• Read your write consistency: 用戶可以立馬看到自己的update，但無法看到其他用 t戶的更新。

• Session Consistency: 當用戶的request處於一個session scope（一個server）上時，提供read your write consistency。

• Monotonic read consistency: 保證用戶只會看到最新更新的data。

• Eventual Consistency：（最終一致性）在更新進行中時，用戶會看到不一致的update。這個model的使用情況是，對一個數據的concurrent修改基本不會發生，用戶需要等一段時間才能看到之前的update。

在確定Consistency Model之後，NoSQL大部分的底層構建就已經完成。有了硬體部分，有了硬體之間抽象的架構，可是在具體使用中，還需要給出數據流動的方法。

要根據具體情況來選擇如何實現下面兩個問題：

• 用戶的request如何到達replicas（副本）

• 副本之間如何傳播update

Master Slave Model（Single Master）

每一個PN都會有一些VN作為分布的master，而其他VN作為slaves。

所有的請求都會經過Master來處理。假如Master在data 更新的傳輸過程中crash的話，有可能造成數據丟失。當Master crashed之後，最新更新的slave（VN）會被提升為新的master。

讀操作可以分到各個replicas上面。

Single Master Model適用於有很多read操作的app；當update操作是平均分布在key range之內時，這個模型也可以勝任。

然而假如在鍵的範圍內之內，有一塊區域十分流行導致有很多次的write操作的話，這個model就無法將workload平均分配。針對這種情況，就要引入新的model。

Multi-Master Model（No Master）

沒有master的情況下，如何保證consistency呢？一種方法是，用傳統的2PC protocol，在每次update的時候，將所有副本的狀態都更新一次。在這種方法中，需要有一個coordinator來溝通各個副本，詢問每個副本是否ready，如果ready，coordinator需要命令所有副本執行commit操作，副本在完成操作之後要將結果寫入log file。

上面這種更新所有副本的方法，最大的問題是，coordinator沒有scalability，它需要在等待各個副本確認狀態之後才能進行下一步指令，會經歷大量的網路roundtrip以及disk I/O的延遲。如果有一個副本失敗的話，更新就失敗。當有大量機器存在的時候，這種情況會經常發生。

更高效的方式就是用Quorum Based 2PC（PAXOS）

在這種model中，coordinator只需要更新W個副本（而不是全部的N個），coordinator依然可以向所有N個副本寫操作，只要得到任意W個副本回復確認即可。從概率的角度上，這樣的方式更有效率。

因為不是所有的副本都被更新（W），所以在讀取數據的時候，不是讀取一個副本，而是要讀取R個，然後選取其中timestamp最新的那個。

Quorum Based 2PC 當W=N， R=1的時候，就變成了傳統的2PC更新方式。而W和R的參數選擇，則取決於設計者對一致性的要求程度。

而在read操作中，如何得到副本的timestamp信息，以及如何比較timestamp，就需要用到vector clock 這個技術了。

Gossip

如果用戶可以接受更加弱的一致性的話，除了Quorum Based 2PC之外，還可以使用Gossip 這種protocol來在各個replicas之間傳遞信息。

它常用於P2P的通信協議，這個協議就是模擬人類中傳播謠言的行為而來。簡單的描述下這個協議，首先要傳播謠言就要有種子節點。種子節點每秒都會隨機向其他節點發送自己所擁有的節點列表，以及需要傳播的消息。任何新加入的節點，就在這種傳播方式下很快地被全網所知道。這個協議的神奇就在於它從設計開始就沒想到信息一定要傳遞給所有的節點，但是隨著時間的增長，在最終的某一時刻，全網會得到相同的信息。

G. 存儲的具體實現

一種實現方式是讓數據的存儲pluggable，MySQL，Filesystem，或者一個巨大的Hashtable都可以用作存儲的機制。

另一種方式是，採用高可擴展性的存儲。具體的細節可以繼續閱讀CouchDB 還有 Google BigTable 的相關文獻，在這裡就簡單介紹一個在實現存儲中用到的技術。

Copy-on-modifed approach：

任何一個更新都會產生一個備份，進而影響其索引導致索引被修改後然後索引也會產生一個備份，這樣一直往複下去直到根索引。

NoSQL的總結

其實NoSQL的概念很大，所有不是RDBMS的存儲系統都可以叫做NoSQL。上面介紹的NoSQL主要是為了應對Scalability而產生的一種解決方案。在閱讀完這篇文章之後，對於如何解決2中的問題，也就有了方法和步驟：

• Partition Data，將data存在不同的機器上，balance work load（consistent hashing）

• 萬一其中有機器壞掉怎麼辦？how to handle failure（copy to neighbors）

• 如何在機器之間備份數據，做replica（Master or NoMaster model）

• 在數據備份的時候，如何保持同步呢？Synchronization（PAXOS， Gossip）

• 因為機器數量可變，當任務量變化導致機器數量變化的時候，又如何重新分配數據呢（VN的加入和離開）

以上就是NoSQL的一些基本概念，在掌握這些之後，閱讀Dynamo或者Canssandra時，就會更加的有方向感。也就會明白這種技術為什麼對於像Facebook這樣大型公司的成功至關重要了。

本文作者：Zhang Y，更多精彩內容，歡迎訪問官網 http://BitTiger.io 或關注 「論碼農的自我修養」 微信公眾號：bit_tiger