太閣技術秀：一起聊聊cassandra

我們從五個方面介紹Cassandra Architecture：

• Why Cassandra architecture?

• How do nodes communicate?

• How to achieve eventual consistency?

• How to detect data inconsistency?

• How to increase write and read speed?

1. Why Cassandra architecture?

所有系統最開始都是centralized。但是有很多缺點，比如單機的處理能力不夠。

Centralized database如下圖：

所以出現了分散式的資料庫。如下圖：

Partitioning的方式有range partitioning, list partitioning, hash partitioning。其中hash partitioning使用最多。如下圖，數據根據key的hash結果，存入不同的資料庫中。相比其他兩種，它能夠balance，保證每個資料庫存的數據量相當。

如果要加一個server，如下圖，要將key重新hash，實現新的balance，這需要O(n)級別的移動。這是這種方法的缺點。

如果hash function和server不相關，就能解決問題。一個方法如下圖，有2的n次方個key space，每個server負責一部分key space（key的value）。

有四台server，每個server佔在一個數上，負責處理這個數之前的數，比如DB1負責15，0，1，2，3。這個結構是peer-to-peer，沒有主從關係。每個server都可以作為入口處理client的請求。

Client找到任一個server，數據的key經過hash，得到12。DB1找它的表，找到第一個大於這個值（12）的數，此例中是14，對應DB4，於是數據被存入DB4。Client索要數據的過程和存儲一致。這種方式的好處在於添加server和減少server時，數據遷移大大減小。

假如希望把新server DB5放在環中6處，這意味著以後4，5，6都歸這個新server管理。4，5，6原來的數據存在DB2，這些數據需要存到DB5。只需要和一個點通信。M個server，N個key space，只需N/M級別時間。假設DB5需要移除，只需要把4，5，6還給DB2。任何節點加入，只需要向後節點要數據，任何節點離開，只需要將數據給後節點。

2. How do nodes communicate?

在peer-to-peer結構中有一個很有名的協議，叫Gossip Protocol。它的精髓在於一傳十，十傳百。

每個node有個neighbor list，收到信息後轉發給neighbor list里的node。node之前收到過消息則不再轉發，降低網路overhead。有兩個重要參數，一個是Fan number，表示每個node轉發的node數量，此例中是3，第二個是Time to live（TTL）。下圖中，起始node的參數是3，它傳給的node的參數變為2，依次遞減，當node的參數是0時，不再轉發。

比如之前例子中，DB5加入後，將加入信息傳給其他server，DB5先將消息告訴DB1，DB3然後DB1將消息告訴DB4。如下圖：

下圖是Data Model，數據要有primary key：

現在有load balance的問題，因為即使最開始數據分布比較均勻，在加入新的server之後，還是會使有的server處理的數據很少，有的server處理的數據很多。此外，數據量小時，很容易出現hash後某些key多，某些key少。另一個不balance的地方在於單機處理數據的不同。解決方案有兩個：virtual nodes和move nodes。

Virtual node指一台機器能充當幾個點。比如有兩台機器，DB1和DB2，它們分到相同數據量的幾率很小，但是如果每個server可以扮演多個點，如下圖，DB1扮演DB1a，DB1b，DB1c，DB1d。這兩個server分到相同數據量的幾率就大很多。

目前為止，每個節點負責一部分數據，所以需要數據replication。備份需要注意的是不要將所有的node存在相同的physical server上。數據備份帶來consistency的問題。cassandra是一個AP系統，遵循CAP（C：數據是一致的，A：數據是可用的，P：數據被切分）原則。它有tunable consistency，有三個參數可調：N代表備份數，默認為3，W是寫操作所需的成功數，R是讀操作所需的成功數。下圖是一個例子：

N為3，最簡單的方法是用此DB後兩個DB作為備份。DB4的數據在DB1和DB4備份。此時再寫一個數。W為1，代表只要給一個DB寫成功就任務整個新數據的寫成功。R為1，代表只要從一個DB讀到需要數據就算讀取成功，但這樣的問題在於讀取的數據不一定是最新的。

下面的例子是W為3。三個DB都寫成功才算是數據的寫成功。

結果是：

三個DB都獲得最新的數據，這樣讀操作時只需從一個DB讀取，就能確保得到最新數據。

如果W為1，R為3，也能保證讀到最新的數據。

Strong Consistency保證一定讀到新數據：W + R > N。

如果W少R多時，判斷哪個數據是新數據時，可以通過比較timestamp，數據的存儲有timestamp信息。

3. How to achieve eventual consistency?

有三種方案：read repair，hinted handoff，anti-entropy repair

1）read repair

可以設置一個概率來觸發read repair，當它被觸發時，向所有replica發請求，從一個replica讀數據，從其他replica讀摘要，如果摘要和數據不一致，強迫所有replica進行比較，同步數據。

2）hinted handoff

即使W為2，也會嘗試給所有機器寫。當DB1fail，如果有兩個其他機器寫成功，仍會反應寫成功。DB3本不需要存這個數據，但現在存儲這個數據，並且在下面寫一個hint：DB1，表示數據本該存在DB1里。在短時間內，DB3會不斷嘗試把數據寫回DB1。

3）anti-entropy repair

每個node定期和其他replica進行數據比較，如果發現數據不同，進行merge。定期的時間默認為一秒鐘。如果node fail，重新啟動會嘗試和replica同步。如果數據很久沒有被讀取，當它被讀取時，進行同步數據更新。

4. How to detect data inconsistency?

Cassandra使用merkle trees的方式探測inconsistency。如下圖：

它將每塊數據進行hash。把每兩個hash後結果進行hash，依次類推，形成一個二叉樹。當發現不同時，類似二叉樹查找進行比較。它的缺點是如果寫操作很多時，merkle tree的構建非常複雜。

5. How to increase write and read speed?

1) increase write speed

寫的時候，首先嘗試往內存里寫，同時寫一個log。當內存里的table寫滿後，存入disk。

2) increase read speed

使用compaction。一定情況下，將幾個數據塊進行merge。把同一個key的數據塊放在一起。同時可以設置TTL，這個TTL以時間為單位，時間一到，數據刪除，減少merge。

Compaction提供三個方案：

1）SizeTieredCompactionStrategy (STCS)：每四個數據塊壓一塊，對於insert多的系統好。

2）LeveledCompactionStrategy (LCS)：對於update多的系統好

3）DataTieredCompactionStrategy (DTCS)：根據時間進行compaction

完整視頻請查看：太閣技術秀—一起聊聊Cassandra

註：本文系3月23日晚太閣技術秀一起聊聊Cassandra的技術整理，作者：Shaoke Xu

更多精彩內容， 請掃描下面二維碼，關注微信公眾賬號「論碼農的自我修養」

推薦閱讀：