【摘要】:本文簡要介紹了Cassandra分布存儲系統的設計理念及其使用的各種分布存儲技術。文章首先分析了Cassandra分布存儲系統出現的緣由——Facebook社交網絡的系統需求，然后著重介紹了Cassandra系統中區別傳統關系型數據庫的數據結構，并且簡要分析了其分區技術在分布存儲系統中的應用，同時，介紹了基于數據的復制機制來達到數據高度的可獲得性、安全性和系統良好的擴展性的方式。最后，本文宏觀的總結了Cassandra系統的運行過程及適用范圍。
　　
　　【關鍵詞】:分布存儲，網絡，數據庫。
　　
　　 前言
　　Cassandra是一種分布存儲系統，很多商業服務網站使用它來對大量的結構化的數據進行管理。在對大量數據的管理中，Cassandra可以提供高速有效的服務并從未出現過錯誤。Cassandra運行于數百個節點的結構之上，而在這類規模的系統中，各類組件，無論規模大小，都會持續的拋出異常。然而，Cassandra保持數據持久性的方式很好的應對了這些異常，為存儲系統提高了強大的可靠性和擴展性。盡管Cassandra在一些設計和實施等方面與傳統的數據庫存在相似之處，但是Cassandra并不完全支持關系數據模型，即它不是一個傳統的關系數據庫。Cassandra提供給客戶端一個相對比較簡單的數據模型，這種數據模型支持對數據的布局和格式動態的控制。Cassandra系統旨在高效迅速的處理大量的寫操作，與此同時不會犧牲讀操作的效率，因而確保具有這種特性的商業網站能夠為客戶提高高效便捷的服務。
　　
　　簡介
　　Cassandra最初是由AvinashLakshman和PrashantMalik在Facebook開發設計，在2008年，Facebook將它貢獻給了開源社區。Cassandra的出現與Facebook的系統特性息息相關。Facebook是世界最大的社交網絡平臺，在高峰時段，Facebook要向數億的用戶提供服務，而Facebook數萬臺的服務器也遍布了全世界的各個數據中心。基于以上對海量數據處理的需求，Facebook想要為用戶提供優質的、可靠的和高效的服務，一個必要的條件在于其系統平臺應具有高度的擴展性以應對不斷增長的用戶數量和數據處理需求數量。因此，處理一個包含大量組件的系統可能出現的各種異常現象是Facebook系統平臺維護人員的常規工作：在任意時間點上，總會有少量卻很關鍵的服務器和網絡組件出現錯誤。在這種情形下，軟件系統應該以某種容錯的機制處理錯誤，而不是將錯誤當作異常來處理。因此，為了達到以上指出的系統的可靠性和擴展性，Facebook開發了Cassandra。
　　
　　數據結構
　　在Cassandra這種分布存儲系統中，類似于關系數據庫中的表結構是一個多維分布映射圖，并且以一個主鍵作為索引。在這種映射圖中，一個對象的值是高度結構化的，其中，行主鍵是一個沒有長度限制的字符串——通常情況下為16-36個字節。需要注意的是，在數據的任一副本中，針對任何一個行主鍵的操作都是原子的，即使多個列被同時讀或者寫。在Cassandra中，列的結構近似于Bigable中的列結構——列被組合在一起，并被稱為一個ColumnFamily或者SuperColumnFamily。下面詳細介紹Cassandra的列結構。
　　
　　Column
　　一個Column是一個包含名稱、值和時間戳的元組。它是最小的數據容器，其中，名稱和值通常沒有長度限制。Column相當于關系數據庫中的字段，不同的是，每一行中的Column內容可以不同，而關系數據庫中一張表內每行所對應的列字段都是相同的。這種方式相對比較靈活，對于具有少量字段，并且訪問時通常只需要通過Key/Value配對的數據非常適用。
　　SuperColumn
　　一個SuperColumn是包含名稱和值的元組，它并不包含Column中的時間戳。SuperColumn的值并不是一個二進制字節而是映射容器——包含“Key/Value”的組合。簡而言之，SuperColumn是一個包含多個Column的容器，在被包含的每個Column中，其Key值與其名稱一致。SuperColumn可以表達一個object的多個屬性，每個屬性用一個Column表示。
　　ColumFamily
　　一個ColumFamily結構類似于關系型數據庫中的表結構，它可以包含任意數量的行（row）。一個ColumFamily有一個名稱（類似于關系數據庫表的名稱），和若干行。在每一行中，分別包含各自的key（類似于行主鍵）和值（value）——包含多個Column的映射表，其結構與之前介紹的SuperColumn一致。
　　
　　API
　　
　　Cassandra的API提供如下三種方法：
　　
　　 insert(table;key;rowMutation)
　　 get(table;key;columnName)
　　 delete(table;key;columnName)
　　
　　columnName可以指ColumnFamily或者SuperColumnFamily中的任意一個Column或者任意一個SuperColumn中的Column的名稱。
　　
　　系統架構
　　一個存儲系統的結構通常比較復雜，除去保證真實數據持久性的必要組件，存儲系統還應該具有如下特性和功能：擴展性和平衡負荷的有效解決方案、伙伴關系管理（membership）和錯誤檢測、錯誤恢復、同步化復制、超負荷處理、狀態轉移、并行和任務排序、請求配置、請求路由、系統監視與警告，以及系統配置管理。而在Cassandra系統的搭建過程中，所應用的核心分布存儲技術主要包括：存儲空間分區，數據復制，伙伴關系管理，錯誤處理和系統擴展增容，所有的這些模塊協同工作，一起處理用戶的讀寫請求。以下分別介紹在Cassandra中應用的各種分布存儲技術。
　　
　　1. 分區（partition）
　　Cassandra最重要的設計特性之一即為可擴展性。為了達到這一目標，Cassandra分布存儲系統使用分區技術。具體而言，在Cassandra分布存儲系統中，存在多個位于不同地理位置的存儲節點，每個節點按照某種算法和方式復制存儲一定量的數據。新加入的數據以某種方式被分配到系統中的任一節點中。當數據量不斷增多時，可以通過增加節點的書目來提高系統的容量。當然，在Cassandra系統中，新增一個或多個節點并不會對已存在的絕大多數節點造成影響，它只會改變一個局部的存儲狀況。以上存儲方式的實現是通過動態分區的方式達到的，下面詳細介紹這一技術。
　　為了達到以上目標，存儲系統應該可以將數據動態的分配給集群中的不同的節點，或者說能夠動態的對存儲空間進行分區，并將節點存入。Cassandra使用一致性哈希函數對數據進行分區：哈希函數的輸出范圍是一個固定的圓環空間，稱為“ring”。在這個圓環中，最大的哈希輸出值與最小的哈希輸出值相毗鄰。系統中的任一節點被分配一個隨機的值，這個隨機的值代表了其在圓環空間上的位置。同時，對任一的數據的Key值做哈希運算，輸出的結果代表這個數據在圓環空間上的位置。與此同時，從任一數據在圓環上的位置為起點，沿著圓環順時針移動找到第一個節點，那么這個節點即為負責這個數據的存儲容器。因此，圓環空間上的任一節點都負責存儲其前一個節點和它之間的所有數據。這樣的好處是增加或者刪除一個節點只會影響其周圍的小范圍空間，而對圓環空間上的絕大多數其他節點沒有任何影響，進而達到了較好的擴展性。然而，這種隨機分配的機制并沒有考慮到不同節點的存儲能力，Cassandra解決這個問題的方法是分析圓環空間上的各節點的負載情況，并且使信息負荷量比較小的節點向負荷量比較大的節點移動，以緩解其存儲壓力。
　　
　　2. 復制
　　Cassandra使用數據復制的方法來保證數據高度的可用性和持久性。在Cassandra系統中，每個數據都會在N個主機上進行復制，每個Key值，k，會被指定給集群中的一個節點。如前所述，每個節點負責其控制范圍內的數據的副本，并且，為了在本地存儲其控制范圍內的Key值，節點會將其控制的Key值在圓環空間上的其他N-1個節點上進行復制，當然，Cassandra為客戶端提供了很多可供選擇的數據復制策略，比如“架構不可知”（RackUnaware），“架構可知”（RackAware）（同一數據中心內）和“數據中心可知”（DatacenterAware）。應用程序可以根據需要選擇自己復制數據的策略。如果一個特定的應用程序選擇了“架構不可知”的數據復制策略，那么那些被復制的但尚未指派存儲節點的副本會選擇圓環空間上初始節點的前N-1個節點。而對于“架構可知”和“數據中心可知”復制策略，則需要涉及比較復雜的算法。具體而言，Cassandra使用Zookeeper系統③在其集群中選擇一個領導節點（leader），。新加入集群的任一節點都要與領導節點進行通信，領導節點會告知其負責的副本的所在區域，同時領導節點要確保每個節點不會負責多于N-1的圓環空間上的區域。記錄每個節點負責的圓環區域的元數據會緩存在所有節點上并且在Zookeeper中做容錯處理——這種方式可以確保當某個節點癱瘓后再恢復時，它能夠了解到其原本負責的區域。例如，當集群的一個節點崩潰后返回時，它同Zookeeper與領導節點或者其他節點進行通信，領導節點或其他節點返回存儲在他們內部的關于這個節點崩潰前的存儲信息，這個節點通過這些信息恢復其存儲功能，重新負責原來的圓環區域。相似的概念可以借鑒Dynamo中的“偏好列表”（preferencelist），即負責給定區域的節點列表。
　　
　　基于以上的介紹，我們了解到，Cassandra節點簇中的每個節點都了解系統中的其他節點和其負責的存儲區域。通過這種方式，Cassandra可以在節點癱瘓和網絡分區的情況發生變化時保證數據的持久性。數據中心會因為很多因素而停止工作，比如停電，斷網或者自然災害。而Cassandra系統中數據的每個行（row）都會在多個節點被復制。實際上，一個Key的“偏好列表”就是保證擁有這個Key副本的N各節點分布在不同的數據中心。這些數據中心通過高速的網絡相連接。這種跨越多個數據中心的復制機制保證了在某些數據中心癱瘓時，系統不會受到很大影響，數據也不會丟失。
　　
　　3. 伙伴關系（Membership）
　　Cassandra節點集群中的節點間關系——我們稱之為“伙伴關系”（Membership），是建立在Scuttlebutt的基礎之上的——一種非常高效的、基于“Gossip”的關系機制。Scuttlebutt顯著的特性在于其高效的CPU利用率和“Gossip”通道的利用率。下面通過錯誤檢測的機制來進一步理解Cassandra中的伙伴關系。
　　
　　錯誤檢測（FailureDetection）是一種利用節點間關系的模塊，通過錯誤檢測，一個節點可以判斷系統中的其他節點是否在正常的工作。在Cassandra系統中，錯誤檢測也用來避免一個節點試圖同一個無法到達的錯誤或者癱瘓的節點進行交互。Cassandra利用一個改進版本的AccrualFailureDetector去完成錯誤檢測。AccrualFailureDetector的觀念在于，錯誤檢測模塊并不是通過返回一個布爾值來表示一個節點工作與否，而是返回一個代表每個被檢測節點的質疑等級值，這個值被定義為Φ，Φ值可以動態的調整以反應被檢測節點的網絡和加載的條件。AccrualFailureDetector的方法類似于統計學中的建設檢驗問題，而Φ相當于檢驗的統計量。在Cassandra系統中，Φ有如下的意義：給定一個具體的Φ值，我們在檢測節點時，會以某個對應的概率錯誤的認為這個節點存在錯誤。例如假設當Φ=1時我們檢測節點A，那么錯誤的判斷節點A工作狀況的概率為10%。同理，當Φ=2時，對應的概率為1%，當Φ=3時，對應的概率為0.1%，依次類推。每個節點收到系統內其他節點的“Gossip”信息的內部到達時間都被存儲在各自的節點的樣本窗口（samplingwindows）中，系統通過估計這些內部到達時間的分布來計算Φ值。然后再給定的顯著性要求下（允許犯錯誤的概率），用計算出來的Φ與分布中的臨界值做比較，如果大于臨界值，則拒絕原假設，即某個節點的確存在錯誤，針對這個節點的操作被中止；如果計算出來的Φ小于臨界值，則接受原假設，即某個節點沒有錯誤，可以進行對它的操作。具體過程見圖1.以前的文獻認為內部到達時間類似服從高斯分布（Gaussian），但是Cassandra使用指數分布來更好的估計這一分布。總的來說，AccrualFailureDetector擁有很高的精確度和運行速度，并且這種錯誤檢測的機制可以根據不同的網絡條件和服務器負荷情況來進行自我調整。
　　
　　圖1：AccrualFailureDetector
　　4. 引導程序（Bootstrapping）
　　當一個節點初次運行時，它在圓環空間上隨機選擇一個片段作為它的位置。為了使系統能夠容錯，圓環上節點的位置映射永久的保存在本地磁盤上，同時也存儲在領導節點上。然后，這個片段的信息被以“Gossip”的方式傳遞到集群中的其他節點上。通過這種方式，圓環空間上的所有節點都能夠同時了解其他節點的位置及存儲情況。這也保證了在復制一節中提到的高度的數據可獲得性：因為每個節點都存有其他所有節點的信息，因此，當任一節點接受到讀寫請求時，它能夠將針對某個Key值的請求正確的傳遞到存儲這個Key值的其他節點上。通過bootstrapping，當一個節點需要接入集群時，首先它會讀取其配置文件中的連接點列表。這些集群中初始的連接點被稱為集群的種子，種子也可以來自配置服務，如領導節點Zookeeper。
　　
　　5. 擴展增容
　　在分區一節中，曾經提到過Cassandra系統高度的擴展性，即新加入的存儲節點不會影響整個系統的正常工作。具體而言，當一個新的節點加入到系統中時，它被指派一個圓環空間上的片段，來緩解高負荷的節點。這種方式的結果是，新的節點會分割其他節點原來負責的區域，而新的節點只會分割它在圓環上的位置周圍的節點的存儲區域，而不會影響其他區域。存儲空間被分割的節點將其放棄的數據使用“kernel-kernel”的復制技術傳遞給新的節點。實際運行情況表明這些數據可以以每秒40MB的速度從一個單一節點傳遞到其他節點。Cassandra的開發人員通過使多個副本同時參與“bootstrap”傳輸來提高傳輸速度，這種并行傳輸的方式的機制與Bittorrent相似。通過高速的復制技術，Cassandra系統達到了高度的擴展性。
　　
　　 以上五種技術是在Cassandra系統中應用的比較核心的分布存儲技術，他們協同工作，保證了數據高度的可獲得性和擴展性。當數據量不斷擴大時，Cassandra系統能夠使用以上方法很好的保持系統的穩定，此外以上方法也保證了數據的安全性，基于復制機制的存儲方式不僅提高了可獲得性，同時面對若干主機出現癱瘓的情形，也能保持系統的正常工作，并且確保數據不會丟失。同時，Cassandra系統也能夠保證數據的持久性，這種數據的持久性要依賴本地文件系統。具體而言，對于寫操作，通常涉及兩個子操作：1.將寫操作記錄到一個“commitlog”中；2.當前一個操作成功后，更新內存中的數據結構。當內存中的數據容量達到一個特定值時，它將自己導入本地磁盤中。所有的寫操作都連續存儲在本地磁盤上，并且建立行主鍵的索引以便查詢，這些索引與數據文件一同存儲。對于讀操作，首先查詢內存中的數據結構，找不到所需信息時才檢索本地磁盤。這種內存—磁盤的雙重存儲，和首先將任一寫操作記錄到“commitlog”并存入磁盤的方式，通過本地文件系統的持久性保證了數據的持久性。
　　
　　總結
　　 Cassandra分布存儲系統旨在應對海量數據的存儲、數據的安全性問題以及基于Key-value的查詢需求。通過運用上文提到的各種技術，Cassandra將數據從傳統的關系數據庫單一數據中心的存儲方式過渡到分布的存儲方式。具體而言，Cassandra的系統結構為多個分布在不同地點的存儲節點，這些節點通過高速網絡相連。數據通過某種哈希算法被指派到系統中的各個節點中。同時，系統利用復制的技術將存儲在不同節點內的數據信息復制到其他節點上，這保證了數據的安全性，同時也提高了數據的獲取速度，具體的分配機制見上文“分區”一節的介紹。當數據量不斷擴大時，會有更多的節點加入到Cassandra系統的集群中，Cassandra節點集群的圓環邏輯結構保證了節點的加入不會影響系統中其他節點的工作，這使得系統具有良好的擴展性能。這種分區-復制的技術也保證了當系統中一個或多個節點癱瘓時，系統仍能正常工作，這是因為每個節點上不僅存儲了自己復制的區域內的數據，還保存著其他節點內數據的副本和所有節點存儲情況的元數據，進而在發生節點癱瘓時保證數據的安全。
　　 相對于關系型數據庫，Cassandra分布存儲系統中的數據結構并不能很好的支持復雜的結構關系查詢，但是對于一些只針對某個Key值進行簡單查詢的數據，其性能和反應時間要遠遠優于關系型數據庫。比如在當今流行的各大網絡社區或B2B,B2C網站中，面對海量的數據和每天大量的信息吞吐量，Cassandra這類基于Key-value的分布式存儲系統會逐漸的更加廣泛地得到應用。
　　
　　參考文獻:
　　
　　[1]. GiuseppeDeCandia,DenizHastorun,MadanJampani,GunavardhanKakulapati,AvinashLakshman,AlexPilchin,SwaminathanSivasubramanian,PeterVosshallandWernerVogels,Dynamo:Amazon’sHighlyAvailableKey-valueStore,2007
　　[2]. FayChang,JeffreyDean,SanjayGhemawat,WilsonC.Hsieh,DeborahA.WallachMikeBurrows,TusharChandra,AndrewFikes,RobertE.Gruber,Bigtable:ADistributedStorageSystemforStructuredData,2006
　　[3]. AvinashLakshman,PrashantMalik,Cassandra-ADecentralizedStructuredStorageSystem,2009
　　[4]. ArinSarkissian,WTFisaSuperColumn?AnIntrototheCassandraDataModel,2010-3-22
　　[5]. MoritzY.BeckerPeterSewell,ComputerLaboratory,UniversityofCambridge,JJThomsonAvenue,Cambridge,UnitedKingdom,Cassandra:DistributedAccessControlPolicieswithTunableExpressiveness
　　[6]. JonathanEllis,Cassandra_OpenSourceBigtable+Dynamo,2010
　　[7]. RonaldMathies,InstallingandusingApacheCassandraWithJavaPart1(Installation),InstallingandusingApacheCassandraWithJavaPart2(Datamodel),InstallingandusingApacheCassandraWithJavaPart3(Datamodel2),InstallingandusingApacheCassandraWithJavaPart4(ThriftClient),InstallingandusingApacheCassandraWithJavaPart5(ThriftClient2),2010
　　[8]. MikePerham,CassandraInternals–WritingandReading,http://www.mikeperham.com,2010