目錄(從整理的word裡複制粘貼過來的，格式有點點問題)
一、Cassandra架構
二、Cassandra資料模型
Colum / Colum Family, SuperColum / SuperColum Family
Colum排序
三、分區政策
Token，Partitioner
bloom-filter，HASH
四、副本存儲
五、網絡嗅探
六、一緻性
Quorum NRW
維護最終一緻性
七、存儲機制
CommitLog
MenTable SSTable
附
一、Cassandra架構
圖1 Cassandra
Cassandra是社交網絡理想的資料庫，适合于實時事務處理和提供互動型資料。以Amazon的完全分布式的Dynamo為基礎，結合了Google BigTable基于列族（Column Family）的資料模型，P2P去中心化的存儲，目前twitter和digg中都有使用。
在CAP特性上，HBase選擇了CP，Cassandra更傾向于AP，而在一緻性上有所減弱。
Cassandra的類Dynamo特性有以下幾點：
l 對稱的，P2P架構
n 無特殊節點，無單點故障
l 基于Gossip的分布式管理
l 通過分布式hash表放置資料
n 可插拔的分區
n 可插拔的拓撲發現
n 可配置的放置政策
l 可配置的，最終一緻性
類BigTable特性：
l 列族資料模型
n 可配置，2級maps，Super Colum Family
l SSTable磁盤存儲
n Append-only commit log
n Mentable (buffer and sort)
n 不可修改的SSTable檔案
l 內建Hadoop
二、 Cassandra資料模型
Colum / Colum Family, SuperColum / SuperColum Family
Column是資料增量最底層（也就是最小）的部分。它是一個包含名稱（name）、值（value）和時間戳（timestamp）的三重元組。
下面是一個用JSON格式表示的column：
{ // 這是一個Column
name: "emailAddress",
value: "[email protected]",
timestamp: 123456789
}
需要注意的是，name和value都是二進制的（技術上指byte[]），并且可以是任意長度。
與HBase相比，除了Colum/Colum Family外，Cassandra還支援SuperColum/SuperColum Family。
SuperColum與Colum的差別就是，标準Column的value是一個“字元串”，而 SuperColumn的value是一個包含多個Column的map，另一個細微的差别是：SuperColumn沒有時間戳。
{ // 這是一個SuperColumn
name: "homeAddress",
// 無限數量的Column
value: {
street: {name: "street", value: "1234 x street", timestamp: 123456789},
city: {name: "city", value: "san francisco", timestamp: 123456789},
zip: {name: "zip", value: "94107", timestamp: 123456789},
}
}
Column Family（CF）是某個特定Key的Colum集合，是一個行結構類型，每個CF實體上被存放在單獨的檔案中。從概念上看，CF像資料庫中的Table。
SuperColum Family概念上和Column Family（CF）相似，隻不過它是Super Colum的集合。
Colum排序
不同于資料庫可以通過Order by定義排序規則，Cassandra取出的資料順序是總是一定的，資料儲存時已經按照定義的規則存放，是以取出來的順序已經确定了。另外，Cassandra按照column name而不是column value來進行排序。
Cassandra可以通過Colum Family的CompareWith屬性配置Colume值的排序，在SuperColum中，則是通過SuperColum Family的CompareSubcolumnsWith屬性配置Colum的排序。
Cassandra提供了以下一些選：BytesType，UTF8Type，LexicalUUIDType，TimeUUIDType，AsciiType， Column name識别成為不同的類型，以此來達到靈活排序的目的。
三、分區政策
Token，Partitioner
Cassandra中，Token是用來分區資料的關鍵。每個節點都有一個第一無二的Token，表明該節點配置設定的資料範圍。節點的Token形成一個Token環。例如使用一緻性HASH進行分區時，鍵值對将根據一緻性Hash值來判斷資料應當屬于哪個Token。
圖3 Token Ring
分區政策的不同，Token的類型和設定原則也有所不同。 Cassandra (0.6版本)本身支援三種分區政策：
RandomPartitioner：随機分區是一種hash分區政策，使用的Token是大整數型(BigInteger)，範圍為0~2^127，Cassandra采用了MD5作為hash函數，其結果是128位的整數值(其中一位是符号位，Token取絕對值為結果)。是以極端情況下，一個采用随機分區政策的Cassandra叢集的節點可以達到2^127+1個節點。采用随機分區政策的叢集無法支援針對Key的範圍查詢。
OrderPreservingPartitioner：如果要支援針對Key的範圍查詢，那麼可以選擇這種有序分區政策。該政策采用的是字元串類型的Token。每個節點的具體選擇需要根據Key的情況來确定。如果沒有指定InitialToken，則系統會使用一個長度為16的随機字元串作為Token，字元串包含大小寫字元和數字。
CollatingOrderPreservingPartitioner：和OrderPreservingPartitioner一樣是有序分區政策。隻是排序的方式不一樣，采用的是位元組型Token，支援設定不同語言環境的排序方式，代碼中預設是en_US。
分區政策和每個節點的Token(Initial Token)都可以在storage-conf.xml配置檔案中設定。
bloom-filter, HASH
Bloom Filter是一種空間效率很高的随機資料結構，本質上就是利用一個位數組來表示一個集合，并能判斷一個元素是否屬于這個集合。Bloom Filter的這種高效是有誤差的：在判斷一個元素是否屬于某個集合時，有可能會把不屬于這個集合的元素誤認為屬于這個集合（false positive）。是以，Bloom Filter不适合那些“零錯誤”的應用場合，而在能容忍低錯誤率的場合下，Bloom Filter通過極少的錯誤換取了存儲空間的極大節省。
原理：位數組 + K個獨立hash（y）函數。将位數組中hash函數對應的值的位置設為1，查找時如果發現所有hash函數對應位都是1說明存在，很明顯這個過程并不保證查找的結果是完全正确的。
在Cassandra中，每個鍵值對使用1Byte的位數組來實作bloom-filter。
圖4 Bloom Filter
四、副本存儲
Cassandra不像HBase是基于HDFS的分布式存儲，它的資料是存在每個節點的本地檔案系統中。
Cassandra有三種副本配置政策：
1) SimpleStrategy （RackUnawareStrategy）：
副本不考慮機架的因素，按照Token放置在連續下幾個節點。如圖3所示，假如副本數為3，屬于A節點的資料在B.C兩個節點中也放置副本。
2) OldNetworkTopologyStrategy （RackAwareStrategy）:
考慮機架的因素，除了基本的資料外，先找一個處于不同資料中心的點放置一個副本，其餘N-2個副本放置在同一資料中心的不同機架中。
3) NetworkTopologyStrategy （DatacenterShardStrategy）：
将M個副本放置到其他的資料中心，将N-M-1的副本放置在同一資料中心的不同機架中。
五、網絡嗅探
網絡嗅探主要用來計算不同host的相對距離，進而告訴Cassandra網絡拓撲結構，以便更高效地對使用者請求進行路由。主要有三種配置政策：
1) org.apache.cassandra.locator.SimpleSnitch：
将不同host邏輯上的距離（Cassandra Ring）作為他們之間的相對距離。
2) org.apache.cassandra.locator.RackInferringSnitch:
相對距離是由rack和data center決定的，分别對應ip的第3和第2個八位組。即，如果兩個節點的ip的前3個八位組相同，則認為它們在同一個rack（同一個rack中不同節點，距離相同）；如果兩個節點的ip的前兩個八位組相同，則認為它們在同一個資料中心（同一個data center中不同節點，距離相同）。
3) org.apache.cassandra.locator.PropertyFileSnitch:
相對距離是由rack和data center決定的，且它們是在配置檔案cassandra-topology.properties中設定的。
六、一緻性
在一緻性上，Cassandra采用了最終一緻性，可以根據具體情況來選擇一個最佳的折衷，來滿足特定操作的需求。Cassandra可以讓使用者指定讀/插入/删除操作的一緻性級别，一緻性級别有多種，如圖5所示。
圖5 Cassandra一緻性級别
注：一緻性級别是由副本數決定，而不是叢集的節點數目決定。
Quorum NRW
- N: 複制的節點數量，即副本數
- R: 成功讀操作的最小節點數
- W: 成功寫操作的最小節點數
Quorum協定中，R 代表一次成功的讀取操作中最小參與節點數量，W 代表一次成功的寫操作中最小參與節點數量。R + W>N ，則會産生類似quorum 的效果。該模型中的讀(寫)延遲由最慢的 R(W)複制決定，為得到比較小的延遲，R和W有的時候的和比N小。
Quorum協定中，隻需W + R > N，就可以保證強一緻性。因為讀取資料的節點和被同步寫入的節點是有重疊的。在一個RDBMS的複制模型中（Master/salve)，假如N=2,那麼W=2,R=1此時是一種強一緻性,但是這樣造成的問題就是可用性的減低，因為要想寫操作成功，必須要等 2個節點的寫操作都完成以後才可以。
在分布式系統中，一般都要有容錯性，是以N一般大于3的，此時根據CAP理論，我們就需要在一緻性和分區容錯性之間做一平衡，如果要高的一緻性，那麼就配置N=W，R=1,這個時候可用性就會大大降低。如果想要高的可用性，那麼此時就需要放松一緻性的要求，此時可以配置W=1，這樣使得寫操作延遲最低，同時通過異步的機制更新剩餘的N-W個節點。
當存儲系統保證最終一緻性時，存儲系統的配置一般是W+R<=N，此時讀取和寫入操作是不重疊的，不一緻性的視窗就依賴于存儲系統的異步實作方式，不一緻性的視窗大小也就等于從更新開始到所有的節點都異步更新完成之間的時間。
一般來說，Quorum中比較典型的NRW為（3,2,2）。
維護最終一緻性
Cassandra 通過4個技術來維護資料的最終一緻性，分别為逆熵（Anti-Entropy），讀修複（Read Repair），提示移交（Hinted Handoff）和分布式删除。
1) 逆熵
這是一種備份之間的同步機制。節點之間定期互相檢查資料對象的一緻性，這裡采用的檢查不一緻的方法是 Merkle Tree；
2) 讀修複
用戶端讀取某個對象的時候，觸發對該對象的一緻性檢查：
讀取Key A的資料時，系統會讀取Key A的所有資料副本，如果發現有不一緻，則進行一緻性修複。
如果讀一緻性要求為ONE，會立即傳回離用戶端最近的一份資料副本。然後會在背景執行Read Repair。這意味着第一次讀取到的資料可能不是最新的資料；如果讀一緻性要求為QUORUM，則會在讀取超過半數的一緻性的副本後傳回一份副本給用戶端，剩餘節點的一緻性檢查和修複則在背景執行；如果讀一緻性要求高(ALL)，則隻有Read Repair完成後才能傳回一緻性的一份資料副本給用戶端。可見，該機制有利于減少最終一緻的時間視窗。
3) 提示移交
對寫操作，如果其中一個目标節點不線上，先将該對象中繼到另一個節點上，中繼節點等目标節點上線再把對象給它：
Key A按照規則首要寫入節點為N1，然後複制到N2。假如N1當機，如果寫入N2能滿足ConsistencyLevel要求，則Key A對應的RowMutation将封裝一個帶hint資訊的頭部（包含了目标為N1的資訊），然後随機寫入一個節點N3，此副本不可讀。同時正常複制一份資料到N2，此副本可以提供讀。如果寫N2不滿足寫一緻性要求，則寫會失敗。 等到N1恢複後，原本應該寫入N1的帶hint頭的資訊将重新寫回N1。
4) 分布式删除
單機删除非常簡單，隻需要把資料直接從磁盤上去掉即可，而對于分布式，則不同，分布式删除的難點在于：如果某對象的一個備份節點 A 目前不線上，而其他備份節點删除了該對象，那麼等 A 再次上線時，它并不知道該資料已被删除，是以會嘗試恢複其他備份節點上的這個對象，這使得删除操作無效。Cassandra 的解決方案是：本地并不立即删除一個資料對象，而是給該對象标記一個hint，定期對标記了hint的對象進行垃圾回收。在垃圾回收之前，hint一直存在，這使得其他節點可以有機會由其他幾個一緻性保證機制得到這個hint。Cassandra 通過将删除操作轉化為一個插入操作，巧妙地解決了這個問題。
七、存儲機制
Cassandra的存儲機制借鑒了Bigtable的設計，采用Memtable和SSTable的方式。
CommitLog
和HBase一樣，Cassandra在寫資料之前，也需要先記錄日志，稱之為Commit Log，然後資料才會寫入到Column Family對應的MemTable中，且MemTable中的資料是按照key排序好的。SSTable一旦完成寫入，就不可變更，隻能讀取。下一次Memtable需要重新整理到一個新的SSTable檔案中。是以對于Cassandra來說，可以認為隻有順序寫，沒有随機寫操作。
MenTable
MemTable是一種記憶體結構，當資料量達到塊大小時，将批量flush到磁盤上，存儲為SSTable。這種機制，相當于緩存寫回機制(Write-back Cache)，優勢在于将随機IO寫變成順序IO寫，降低大量的寫操作對于存儲系統的壓力。是以我們可以認為Cassandra中隻有順序寫操作，沒有随機寫操作。
SSTable
SSTable是Read Only的，且一般情況下，一個CF會對應多個SSTable，當使用者檢索資料時，Cassandra使用了Bloom Filter，即通過多個hash函數将key映射到一個位圖中，來快速判斷這個key屬于哪個SSTable。
為了減少大量SSTable帶來的開銷，Cassandra會定期進行compaction，簡單的說，compaction就是将同一個CF的多個SSTable合并成一個SSTable。在Cassandra中，compaction主要完成的任務是：
1） 垃圾回收： cassandra并不直接删除資料，是以磁盤空間會消耗得越來越多，compaction 會把标記為删除的資料真正删除；
2） 合并SSTable：compaction 将多個 SSTable 合并為一個（合并的檔案包括索引檔案，資料檔案，bloom filter檔案），以提高讀操作的效率；
3） 生成 MerkleTree：在合并的過程中會生成關于這個 CF 中資料的 MerkleTree，用于與其他存儲節點對比以及修複資料。
詳細存儲資料結構參考 http://www.ibm.com/developerworks/cn/opensource/os-cn-cassandraxu2
附
單體、子產品化
Cassandra和HBase的一個重要差別是， Cassandra在每個節點是是一個單 Java 程序，而完整的HBase 解決方案卻由不同部分組成：有資料庫程序本身，它可能會運作在多個模式；一個配置好的 hadoop HDFS 分布式檔案系統，以及一個 Zookeeper 系統來協調不同的 HBase 程序。