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.
facebook's new realtime messaging system: hbase to store 135+billion messages a month nov 16, 2010.
facebook's 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以及他們的共同特點，就可以發現他們非常适合解決以下scalability問題：
如何實作應用層“無狀态”？ 為了讓應用層可拓展，需要分離資料層，就要讓應用層處于“無狀态”，也就是應用層不因為資料層的影響
資料層如何延伸？ 這是包括facebook很多公司公司都要面臨的問題
如何将合适地劃分資料在不同機器上，實作負載平衡
資料在多個機器上，如何處理機器壞掉的情況？
如何在機器之間備份資料？
在資料備份的時候，如何保持同步呢？
如何結合雲計算，實作伺服器數量的自動延伸？ 也就是，任務量大的時候，就增加機器數量，任務量少的時候，就減少機器數量。
因為機器數量可變，當任務量變化導緻機器數量變化的時候，又如何重新配置設定資料呢？
為了解決這些scalability問題，nosql出現了，它成了一種解決大型資料存儲問題的常用方案，canssandra 和 hbase就是根據nosql概念而開發出來的具體産品。
于是，我們想要了解facebook的架構知識，就細化成了了解facebook如何處理大型資料，再而變成為canssandra和hbase如何處理資料，然後變成為：nosql通常意義上是如何解決scalable資料存儲問題的！
nosql pattern基本概念介紹（幹貨）
常見nosql 産品
這三種産品的共同點是：
鍵-值存儲
大量廉價主機上運作
資料在這些主機之間以劃分和備份的形式存儲（也就是partition和replica）
相對較弱的一緻性要求
nosql到底是什麼
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上面。
f. client consistency（一緻性）
當有了資料的很多備份之後，需要關心的問題就是如何在機器之間同步讓使用者有一個consistent view of the data。
一緻性模型有：
strict consistency（one copy serializability）。
read your write consistency: 使用者可以立馬看到自己的update，但無法看到其他用 戶的更新。
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這樣大型公司的成功至關重要了。
<b></b>
<b>本文來自雲栖社群合作夥伴"dbaplus"，原文釋出時間：2016-08-01</b>