1、背景介紹Cassandra使用分布式哈希表（DHT）來確定存儲某一個數據對象的節點。在DHT 里面，負責存儲的節點以及數據對象都被分配一個token。token只能在一定的 范圍內取值，比如說如果用 MD5作為token的話，那么取值范圍就是0, 2128-1。存儲節點以及對象根據token的大小排列成一個環，即最大的token 后面緊跟著最小的token，比如對MD5而言，token 2”128T的下一個token 就是0。Cassandra使用以下算法來分布數據：首先，每個存儲節點被分配一個隨機的token（涉及數據分區策略），該token代 表它在DHT環上的位置；然后，用戶為數據對象指

2、定一個key（即row-key），Cassandra根據這個key計 算一個哈希值作為token，再根據token確定對象在DHT環上的位置；最后，該數據對象由環上擁有比該對象的token大的最小的token的節點來負 責存儲；根據用戶在配置時指定的備份策略（涉及網絡拓撲策略），將該數據對象備份到 另外的N-1個節點上。網絡中總共存在該對象的N個副本。因此，每個存儲節點最起碼需要負責存儲在環上位于它與它的前一個存儲節點之 間的那些數據對象，而且這些對象都會被備份到相同的節點上。我們把DHT環 上任何兩點之間的區域稱為一個range，那么每個存儲節點需要存儲它與前一個 存儲節點之間的range。

3、因為Cassandra以range為單位進行備份，所以每個節點需要定期檢查與它保 存了相同的range的節點，看是否有不一致的情況，這涉及到數據一致性策略。另外，Cassandra的一個特點是寫速度大于讀速度，這都歸功于它的存儲策略。本文總結了 Cassandra中使用的各種策略，包括數據分局策略，數據備份策略， 網絡拓撲策略，數據一致性策略和存儲策略等。Partitioner數據分區策略將key/value按照key存放到不同的節點上。Partitioner會按照某種策略給每 個cassandra節點分配一個token，每個key/value進行某種計算后，將被分配 到器對應的節點上。提供了

4、以下幾個分布策略：org.apache.cassandra.dht.RandomPartitioner： 將key/value按照（key的）md5值均勻的存放到各個節點上。由于key是無序 的，所有該策略無法支持針對Key的范圍查詢。org.apache.cassandra.dht.ByteOrderedPartitioner (BOP)： 將key/value按照key (byte)排序后存放到各個節點上。該Partitioner允許 用戶按照key的順序掃描數據。該方法可能導致負載不均衡。org.apache.cassandra.dht.OrderPreservingPartitione

5、r：該策略是一種過時的BOP，僅支持key為UTF8編碼的字符串。org.apache.cassandra.dht.CollatingOrderPreservingPartitioner：該策略支持在EN或者US環境下的key排序方式。備份策略(副本放置策略)為了保證可靠性，一般要將數據寫N份，其中一份寫在其對應的節點上(由數據 分片策略決定)，另外N-1份如何存放，需要有相應的備份策略。SimpleStrategy (以 前 稱 為 RackUnawareStrategy ， 對 應 org.apache.cassandra.locator.RackUnawareStrategy):不考慮數

6、據中心，將Token按照從小到大的順序，從第一個Token位置處依次取 N個節點作為副本。OldNetworkTopologyStrategy (以 前稱為 RackAwareStrategy ， 對應 org.apache.cassandra.locator.RackAwareStrategy):考慮數據中心，首先，在primary Token所在的數據中心的不同rack上存儲N-1 份數據，然后在另外一個不同數據中心的節點存儲一份數據。該策略特別適合多 個數據中心的應用場景，這樣可以犧牲部分性能(數據延遲)的前提下，提高系 統可靠性。NetworkTopologyStrategy (以 前

7、稱為 DatacenterShardStrategy，對 應 org.apache.cassandra.locator.DataCenterShardStrategy):這需要復制策略屬性文件，在該文件中定義在每個數據中心的副本數量。在各數 據中心副本數量的總和應等于Keyspace的副本數量。網絡拓撲策略該策略主要用于計算不同host的相對距離，進而告訴Cassandra你的網絡拓撲 結構，以便更高效地對用戶請求進行路由。org.apache.cassandra.locator.SimpleSnitch：將不同host邏輯上的距離(cassandra ring)作為他們之間的相對距離。org

8、.apache.cassandra.locator.RacklnferringSnitch:相對距離是由rack和data center決定的，分別對應ip的第3和第2個八位組。 即，如果兩個節點的ip的前3個八位組相同，則認為它們在同一個rack (同一 個rack中不同節點，距離相同)；如果兩個節點的ip的前兩個八位組相同，則 認為它們在同一個數據中心(同一個data center中不同節點，距離相同)。org.apache.cassandra.locator.PropertyFileSnitch:相對距離是由rack和data center決定的，且它們是在配置文件 cassandra-

9、perties 中設置的。調度策略對用戶請求采用某個策略調度到不同節點上。org.apache.cassandra.scheduler.NoScheduler :不用調度器org.apache.cassandra.scheduler.RoundRobinScheduler :不 同request_scheduler_id的用戶請求采用輪詢的方法放到節點的不同隊列中。一致性策略6.1 一致性等級Cassandra采用了最終一致性。最終一致性是指分布式系統中的一個數據對象的 多個副本盡管在短時間內可能出現不一致，但是經過一段時間之后，這些副本最 終會達到一致。Cassand

10、ra的一個特性是可以讓用戶指定每個讀/插入/刪除操作的一致性級別 (consistency level)o Casssandra API目前支持以下幾種一致性級別：ZERO：只對插入或者刪除操作有意義。負責執行操作的節點把該修改發送給所有 的備份節點，但是不會等待任何一個節點回復確認，因此不能保證任何的一致性。ONE：對于插入或者刪除操作，執行節點保證該修改已經寫到一個存儲節點的 commit log和Memtable中；對于讀操作，執行節點在獲得一個存儲節點上的 數據之后立即返回結果。QUORUM：假設該數據對象的備份節點數目為n。對于插入或者刪除操作，保證至 少寫到n/2+1個存儲節點上；

11、對于讀操作，向n/2+1個存儲節點查詢，并返回 時間戳最新的數據。ALL：對于插入或者刪除操作，執行節點保證n (n為replication factor)個 節點插入或者刪除成功后才向client返回成功確認消息，任何一個節點沒有成 功，該操作均失敗；對于讀操作，會向n個節點查詢，返回時間戳最新的數據，同樣，如果某個節點沒有返回數據，則認為讀失敗。注：Cassandra默認的讀寫模式W(QUORUM)/R(QUORUM)，事實上，只要保證W+RN (N為副本數)，即寫的節點和讀的節點重疊，則是強一致性.如果W+R=N，則 是弱一致性.(其中，W是寫節點數目，R是讀節點數目)。如果用戶在讀和寫

12、操作的時候都選擇QUORUM級別，那么就能保證每次讀操作都 能得到最新的更改。另外，Cassandra 0.6以上的版本對插入和刪除操作支持 ANY級別，表示保證數據寫到一個存儲節點上。與ONE級別不同的地方是，ANY 把寫到hinted handoff節點上也看作成功，而ONE要求必須寫到最終的目的 節點上。6.2維護最終一致性Cassandra通過4個技術來維護數據的最終一致性，分別為逆熵(Anti-Entropy)， 讀修復(Read Repair)，提示移交(Hinted Handoff)和分布式刪除。逆炳這是一種備份之間的同步機制。節點之間定期互相檢查數據對象的一致性，這里 采用的檢

13、查不一致的方法是Merkle Tree；讀修復客戶端讀取某個對象的時候，觸發對該對象的一致性檢查；舉例：讀取Key A的數據時，系統會讀取Key A的所有數據副本，如果發現有不一致， 則進行一致性修復。如果讀一致性要求為ONE，會立即返回離客戶端最近的一份數據副本。然后會在 后臺執行Read Repair。這意味著第一次讀取到的數據可能不是最新的數據；如 果讀一致性要求為QUORUM，則會在讀取超過半數的一致性的副本后返回一份副 本給客戶端，剩余節點的一致性檢查和修復則在后臺執行；如果讀一致性要求 高(ALL)，則只有Read Repair完成后才能返回一致性的一份數據副本給客戶端。 可見，該

14、機制有利于減少最終一致的時間窗口。提示移交對寫操作，如果其中一個目標節點不在線，先將該對象中繼到另一個節點上，中 繼節點等目標節點上線再把對象給它；舉例：Key A按照規則首要寫入節點為N1，然后復制到N2。假如N1宕機，如果寫入N2 能滿足ConsistencyLevel要求，則Key A對應的RowMutation將封裝一個帶hint 信息的頭部（包含了目標為N1的信息），然后隨機寫入一個節點N3,此副本不可 讀。同時正常復制一份數據到N2,此副本可以提供讀。如果寫N2不滿足寫一致 性要求，則寫會失敗。等到N1恢復后，原本應該寫入印的帶hint頭的信息將 重新寫回N1。（4）分布式刪除單機

15、刪除非常簡單，只需要把數據直接從磁盤上去掉即可，而對于分布式，則不 同，分布式刪除的難點在于：如果某對象的一個備份節點A當前不在線，而其 他備份節點刪除了該對象，那么等A再次上線時，它并不知道該數據已被刪除， 所以會嘗試恢復其他備份節點上的這個對象，這使得刪除操作無效。Cassandra 的解決方案是：本地并不立即刪除一個數據對象，而是給該對象標記一個hint， 定期對標記了 hint的對象進行垃圾回收。在垃圾回收之前，hint 一直存 在， 這使得其他節點可以有機會由其他幾個一致性保證機制得到這個hint。Cassandra通過將刪除操作轉化為一個插入操作，巧妙地解決了這個問題。存儲策略Ca

16、ssandra的存儲機制借鑒了 Bigtable的設計，采用Memtable和SSTable的方 式。和關系數據庫一樣，Cassandra在寫數據之前，也需要先記錄日志，稱之為 commitlog （數據 庫中的 commit log 分 為 undo-log, redo-log 以 及 undo-redo-log三類，由于cassandra采用時間戳識別新老數據而不會覆蓋已 有的數據，所以無須使用undo操作，因此它的commit log使用的是redo log），然后數據才會寫入到Column Family對應的Memtable中，且Memtable 中的數據是按照key排序好的。Memt

17、able是一種內存結構，滿足一定條件后批 量刷新（flush）到磁盤上，存儲為SSTable。這種機制，相當于緩存寫回機制 （Write-back Cache），優勢在于將隨機IO寫變成順序IO寫，降低大量的寫操作 對于存儲系統的壓力。SSTable 一旦完成寫入，就不可變更，只能讀取。下一次 Memtable需要刷新到一個新的SSTable文件中。所以對于Cassandra來說，可 以認為只有順序寫，沒有隨機寫操作。SSTable是不可修改的，且一般情況下，一個CF可能會對應多個SSTable，這樣， 當用戶檢索數據時，如果每個SSTable均掃描一遍，將大大增加工作量。 Cassandra為了減少沒有必要的SSTable掃描，使用了 BloomFilter，即通過多 個hash函數將key映射到一個 位圖中，來快速判斷這個key屬于哪個SSTable。為了減少大量SSTable帶來的開銷，Cassandra會定期進行compaction，簡單的 說，compaction就是將同一個C