Cassandra是一個分布式存儲系統，管理分布在很多商業服務器節點上的非常大量的結構化數據，同時提供無單點失效的高可用服務。Cassandra目標是在幾百個基礎節點上運行（可能分布在不同的數據中心）。在這個規模上，大大小小的組件經常失效。Cassandra對這些失敗持久狀態的管理方式促使軟件系統的可靠性和擴展性依賴這一服務。雖然在許多方面Cassandra類似于一個數據庫，并且共享很多設計和相關實現策略，但Cassandra并不支持完整的關系數據模型；相反，它為客戶提供了一個支持動態控制數據布局并且格式簡單數據模型。Cassandra系統設計目標是：運行在廉價商業硬件上，高寫入吞吐量處理，同時又不用以犧牲讀取效率為代價。

背景：

Facebook平臺在性能、可靠性、效率以及支持持續增長平臺所需的高擴展性等方面對操作有著嚴格的要求。我們的標準操作模式是在由幾千個組件組成的基礎設施上進行故障處理；任何時候都總有一些小型但非常重要的服務器或網絡組件會發生故障。因此，軟件系統需要建立處理故障（在這種情況下故障是一種常態而非異常）的機制。為了滿足上述可靠性和可擴展性的需要，Facebook研發了Cassandra。

Cassandra使用了一系列總所周知的技術來實現可擴展性和可用性。Cassandra是為滿足inbox搜索問題的存儲需求而設計的。In- box搜索是facebook中的一項功能，允許用戶通過他們Facebook的Inbox進行搜索。對于Facebook而言，這意味著系統需要處理一個非常高的寫入吞吐量，數十億計的每日寫入量，以及相同規模用戶量。由于用戶從分布在不同地區的不同的數據中心獲取數據，能夠在不同數據中心復制數據是解決搜索延遲的關鍵。In-box搜索服務是在2008年6月推出的，到目前為止已經有累計超過2.5億用戶使用，Cassandra也達到了它的設計初衷。Cassandra現在已經被用作多個Facebook服務的備份存儲系統

3. 數據模型

Cassandra中的表是一個分布式多維度由鍵索引的映射，值是一個高度結構化的對象。表中的行鍵是一個沒有大小限制的字符串，盡管通常情況下是16~36的字節長度。每個單行鍵下的操作都是一個原子副本，不管多少讀取或寫入了多少列。列被統一放在一個叫做列簇的集合中，這和Bigtable[4]系統的的工作機制很相似。Cassandra 有兩種列簇——簡單和超級列簇。超級列簇可以用一個列簇內又有一個列簇來形象化表示。

此外，應用可以在一個超列簇或普通列簇中指定列的排序。系統允許列按照時間或者名稱對列進行排序。列的時間排序是特地為像inbox搜索這類結果需要按時間排序的應用提供的。任何列簇的列都要通過列簇訪問規約（列和任何超列簇中的列都需使用列簇訪問規約:super column : column）來進行訪問。文中6.1小結給出了一個能夠非常好的體現超列簇抽象能力的例子。通常的應用使用專用的Cassandra 集群，并作為其服務的一部分來管理。盡管系統支持多表的概念，但所有部署結構中都只有一個表。

4. API

Cassandra的API包括以下三個簡單的方法.

insert(table; key; rowMutation)

get(table; key; columnName)

delete(table; key; columnName)

columnName可以是含有列族的一個特殊列, 一個列族，超列族，或者帶有超列的一個特定列.

5. 系統架構

需要在產品設置中進行操作的存儲系統架構非常復雜。除了實際的數據持久化組件之外，系統還需要有以下特性；可擴展性和強大的負載均衡，會員和故障檢測，故障修復，副本同步，負載均衡，狀態轉移，并發和作業調度，請求編組，請求路由，系統監控和報警以及配置管理。每種解決方法詳細描述都超出了本文討論的范圍，所以我們只會討論Cassandra系統所使用的核心分布式技術：分區、復制、會員、故障處理以及擴展。所有的這些模塊都需要同步處理讀/寫請求。通常一個鍵的讀/寫請求需要被發送到Cassandra集群中的任何一個節點上，然后節點判斷是否為這個特定鍵的副本。對于寫操作，系統將請求路由到副本并等待法定的副本數目的響應，以確認寫操作的完成。對于讀取，需要依據用戶的一致性需求而定，系統要么將請求路由到最近的副本上或者路由到所有副本并等待法定的副本數目的響應。

5.1 分區

Cassandra 一個重要的設計特性就是持續擴展的能力。這要求動態將數據分區到集群中各個節點（即存儲主機）的能力。Cassandra 整個集群上的數據分區用的是一致性哈希[11]，但是使用了保序哈希函數來達到這一點。在一致性哈希算法中，一個散列函數輸出范圍被當作一個固定的圓形空間或‘環’來對待（即最大散列值之后為最小散列值）（有點類似Dynamo系統）。系統中的每一個節點被賦予一個在這一空間內表示其圓環的位置的隨機值。每一個數據項通過鍵來標識，通過散列數據項的鍵來確定環上的位置，然后分配到圓環上第一個離大于該條目位置最近的節點。這個節點被視為此鍵的坐標。應用對此鍵進行特化處理并且Cassandra使用它來進行請求路由。因此，每個節點只需對圓環上它與前任節點之間的區域負責。一致性哈希最主要的優點是離開或到達一個節點只會影響期直接毗鄰節點，而其他節點不受影響。基礎的一致性散列算法面臨一些挑戰。首先，每個節點圓環上隨機位置的分配導致數據和負載分布的不均勻。第二，基礎算法無視節點性能的不均勻性。通常解決這個問題有兩個方法：一個是將一個節點分配給環中多個位置（就像Dynamo的做法），第二種就是對環上的負載信息進行分析，優先路由負載小的節點以減輕負載較重的節點負擔（正如[17]中講述的）。Cassandra采用后一種方法，因為它能夠使得設計和實現易于處理，并且有助于負載均衡做出確定的選擇。

5.2復制

Cassandra采用復制策略來達到高可用性和耐受性。每個數據節點都會被復制到N個主機上，這里N是指復制因子，通過per-instance配置來設置。每個鍵k都被賦給了一個協調節點（上節已經提到）。由協調節點負責它自身范圍內數據項的復制。除了協調節點本地存儲了它自身區域內的每個鍵之外，協調節點還會將這些鍵復制到環上其他N-1個節點上。Cassandra提供了眾多的復制策略，例如”機架不可知”(rack unaware)、”機架可知”(rack aware)(同一個數據中心內)與”數據中心可知”(data-center aware)。應用選擇的復制策略決定了副本的數量。如果應用選擇了”機架不可知”(rack unaware)策略，那么系統將通過環上N-1個繼任協調節點來確定非協調副本個數。對于”機架可知”(rack aware)和”數據中心可知”復制策略時復制的算法要稍微復雜一點.Cassandra使用一個叫做Zookeeper[13]的系統從所有節點中選取一個領導節點。所有加入集群的節點時由領導者告知它們負責哪個環上哪個范圍的副本,并且領導節點需要保持協調一致，使得節點不需要對環上N-1之外的區域負責。節點所需負責區域范圍的元數據被緩存在每個節點本地，并在Zookeeper內做容錯處理,這樣當一個節點崩潰并返回的時候就可以知道它到底負責哪個范圍。借用Dynamo的說法，我們認為負責給定范圍的節點是這個范圍的“最優清單”。

正如在5.1章節中所闡述的那樣， 每一個節點都能感知到系統內其它任意一個節點的存在，因此也知道它們這個系統所負責的范圍。正如在5.2章節中描述的那樣，通過放寬對設備的規定數目，即使面對節點失效和網絡分區，Cassandra也能提供對持久化的保證。數據中心失效通常是由于電力中斷、降溫失效、網絡中斷以及自然災害等。Cassandra被配置成把每一條數據都進行跨數據中心的復制。實質上，構建了一個針對某個key的引用列表，來使得存儲節點可以跨越多個數據中心。這些數據中心通過高速網路進行連接。這種跨多個數據中心進行復制的方案，使得我們能夠掌控整個數據中心而無任何中斷。

5.3會員

Cassandra中的集群成員基于Scuttlebutt[19]，一種非常有效的反熵Gossip（anti-entropy Gossip，一種Gossip算法）機制。Scuttlebutt最顯著的特性是它對CPU利用率非常高效并且非常高效的使用Gossip頻道。Gossip并不僅僅用于Cassandra系統成員內部之間，同樣能傳播其他系統相關的控制狀態

5.3.1故障檢測

故障檢測是一種節點可以在本地確定系統中其他節點是死是活的機制。在Cassandra中,故障檢測還被用來避免在多個操作中與不可達節點的進行通訊。Cassandra使用的是Φ Accrual故障檢測器[8]的一個改良版本。Accrual故障檢測原理是故障探測模塊不產生一個布爾值來代替節點的生死狀態，相反故障檢測模塊為每個被監控節點產生一個代表其懷疑級別的數值,該值被定義為Φ.其基本的思路是用Φ的值來表示一個范圍,可以動態對其進行調整以反映監控節點上的網絡與負載情況.

Φ有以下含義：給定一個Φ的閾值，當Φ=1時我們決定懷疑節點A（出現故障），然后我們將會犯錯（即這個決定在將來可能由于心跳接收延遲而被證明是錯誤的）的可能性為10%；當Φ=2時，可能性為1%；當Φ=3時可能性為0.1%，以此類推。系統中每個節點都維護了一個其他節點發出的gossip消息的內部到達時間的滑動窗口。根據內部到達時間間隔的分布，計算Φ值。盡管初稿中說分布近似為高斯分布(Gaussian distribution)，但是我們發現其實它更接近于指數分布(Exponential Distribution)，因為gossip 頻道本身的特性和它對延遲的影響，所以它更符合指數分布。據我們所知，我們的權責故障檢測實現在基于Gossip的配置中還屬首創。權責故障探測器的準確性和速度都非常好并且它們可以很好的適應不同的網絡狀況和服務器負載狀況。

5.4 引導

當一個節點第一次啟動時，它為它所在環上的位置隨機選擇一個令牌。出于容錯，映射被持久化到本地硬盤和Zookeeper中。令牌信息然后在集群中傳播開來。我們就是通過令牌來了解集群中的所有節點以及它們在環上所在的位置的，通過它任何一個節點都可以將一個鍵(key)的請求路由到集群中的合適的節點。在引導情況下，當一個節點需要加入到集群中時，它需要讀取自身包含集群中的聯絡點的列表的配置文件，我們把這些初始化聯絡點稱為集群種子。種子也可以來自于像Zookeeper之類的配置服務。

在facebook現實環境中(由于故障或維護引起)的節點中斷通常只是暫時的，但有些也可能持續一段很長的時間。引發故障的形式也多種多樣，比如磁盤故障、CPU損壞等。一個節點的斷開很少意味著它會永久斷開，因此不應該導致重新平衡分區指派或維護不可到達的副本。同樣，人為錯誤可能導致啟動了新的非初始化Cassandra節點。為此，每條信息都包含了集群中每個Cassandra實例的名稱。如果配置中的人為錯誤導致節點試圖加入一個錯誤的Cassandra 實例，它將會因為集群名稱錯誤而失敗。出于這些原因，使用顯示機制來從Cassandra實例上初始化添加和刪除節點是合適的。管理員使用命令行工具或瀏覽器連接到一個Cassandra 節點，并發出成員加入或離開集群的變更

5.5 集群擴展

當一個新的節點被添加到系統中時，它將被分配一個令牌，這樣它可以緩解高負荷節點(的壓力)。這將導致節點可以將之前負責的區域拆分給到新節點。Cassandra 引導算法是用命令行操作或Cassandra網絡儀表從系統中其他節點初始化的。放棄這部分數據的節點的數據通過內核-內核拷貝技術轉移到新的節點。運行經驗表明數據可以在單個節點中以40MB/秒的速率進行傳輸。我們正在通過讓多個副本來參與并行化引導傳輸的方式來努力改善這一效率，就像Bit torrent（所做的一樣）。

5.6 本地持久化

Cassandra的數據持久化需要依賴本地文件系統。數據用一種高效讀取格式存放在硬盤上。出于耐受性和可恢復性考慮，通常寫操作將會涉及到提交日志寫入并且更新到一個內存數據結構中。寫入內存數據結構僅僅在寫入提交日志成功后才會進行。我們每臺機器上都有個專門磁盤用來提交日志，因為所有寫入提交日志是連續的，所以可以最大限度的利用磁盤吞吐量。當內存數據結構大小（根據數據大小和數量計算得出）超過一定閾值，它將轉儲到磁盤上。這個寫操作是在每臺機器配備的許多廉價磁盤中的一個上進行的。所有寫入操作寫入到磁盤都是有序的，并且生成了一個基于行鍵可進行快速檢索的索引。這些索引通常是數據文件在一起持久化的。隨著時間的推移，在磁盤上可能會存在很多這樣的文件，后臺會有一個合并進程將這些文件合并成一個文件。這個進程和Bigtable系統中的壓縮進程非常相似。

一個典型的讀取操作在讀取磁盤上文件之前首先將查詢內存數據結構。文件是以文件的新舊來進行排序的。當進行磁盤檢索時，我們可能需要檢索磁盤上的多個文件的關鍵字。為了避免查找到不包含關鍵字的文件，我們用布隆過濾器來匯總文件中的關鍵字，它同樣也存儲在每個數據文件中并常駐內存。（檢索時）首先將咨詢布隆過濾器來檢查搜索的關鍵字是否在給定的文件中。一個列簇中的關鍵字可能會包含很多列。所以當檢索的列距離鍵較遠時還需要利用一些特殊的索引。為了防止搜索時搜索磁盤上的每一列，我們維護列索引來幫組我們直接跳到磁盤上所取列的正確塊上。由于指定鍵的列已經被序列化并寫入到磁盤，所以我們按照每塊256K的范圍來生成索引。邊界的大小是可以配置的，但是我們發現在實際產品負載環境下中，256K大小工作良好。

5.7 實現細節

Cassandra 在一臺機器上的運行過程主要包括以下抽象模塊：分區模塊，集群會員管理和故障檢測模塊以及存儲引擎模塊。所有這些模塊都依賴于一個事件驅動的底層模塊,它按照SEDA[20]架構設計,將消息處理管道與任務管道切分成了多個階段。這些模塊均采用java實現。集群成員管理和故障檢測模塊建立在使用非堵塞IO的網絡層之上。所有系統控制消息依賴于基于UDP協議的消息傳輸，而復制與請求路由等應用相關的消息則依賴于TCP協議。請求路由模塊使用一個固定狀態機來實現。當一個讀/寫請求到達任何集群中的節點時狀態機將會在以下幾個狀態切換：（i）驗證節點是否擁有給定鍵的數據（ii）將請求路由到節點并等待響應返回（iii）如果副本在配置超時時間內沒有到達，將請求設置為失敗并返回客戶端（iv）根據時間戳分辨出最后到達的響應（v）如果副本的數據并不是最新，安排副本進行數據修復。出于論述目的，我們在這里不討論失敗的情況。系統寫入機制既可以配置成同步也可以配置成異步。對于特定高吞吐量需求的系統我們依賴異步復制策略，這種情況下,系統的寫入遠遠超過系統讀取。在同步復制的情況下，我們在指定仲裁數目的響應返回后才將結果返回到客戶端。

在任何日志系統中都需要有一個清除提交日志條目的機制。在Cassandra中,我們采用滾動提交日志——即在一個舊的提交日志超過一個特定的（可配置）大小后自動開啟一個新的日志文件。我們發現每128MB滾動提交日志在生產環境中負載良好。每個提交日志都有一個基本上是一個大小固定的位向量的頭信息，其大小通常超過一個系統可能處理的列簇的個數。在我們的實現中，對于每個列簇,我們都會生成一個內存數據結構以及一個數據文件。每當一個特定的列簇的內存數據結構轉儲到磁盤，我們都會在提交日志中記錄它對應的位,說明這個列簇已經被成功地持久化到磁盤。這就表明這條信息已經被提交。每份提交日志都有一份這些位向量同時也在內存中維護一份。每當發生提交日志滾動的時候,它的位向量,以及它之前滾動的提交日志的位向量都會進行檢查。如果認為所有數據已經被成功持久化到磁盤之后這些日志將會被刪除。寫到提交日志的操作既可以是正常模式也何以是快速同步模式。在快速同步模式下，寫到提交日志將會開啟緩沖。這就意味著當機器崩潰時存在數據丟失的潛在風險。在這種模式下內存數據結構轉儲到磁盤上這一過程同樣也采用了緩沖。傳統數據庫并不是被設計成來處理特別高的寫入吞吐量。Cassandra將所有的寫入操作都轉換成有序的寫操作以最大限度地利用磁盤的寫入吞吐量。由于轉儲到磁盤的文件不再會被修改,從而在讀取它們的時候也不需要加鎖，Cassandra 服務器讀/寫操作實際上并沒有加鎖，因此我們不需要處理在以B-Tree實現的數據庫中存在的并發問題。

Cassandra系統根據主鍵來索引所有數據。磁盤上的數據文件被分成了一系列塊。每塊至多包含了128個主鍵并由一個塊索引來進行界定。塊索引抓取塊內鍵的相對偏移量和數據的大小。當內存數據結構轉儲到磁盤上時，（系統）將會產生一個塊索引并把它的偏移量作為索引寫入磁盤。在內存中也同樣維護一份索引以便進行快速訪問。通常讀取操作總是首先在內存數據結構中檢索數據。如果檢索到數據，將會把數據返回應用，因為內存數據結構包括了任意鍵的最新數據。如果沒有找到（對應的數據），我們則會使用磁盤I/O按照時間逆序對所有磁盤上的數據文件進行搜索。由于我們總是查詢的是最新的數據，所以我們首先在最新文件進行查找一旦找到就返回所查找數據。隨著時間的推移，磁盤上的數據文件的數量將會增加。我們使用一個壓縮進程，非常類似于Bigtable系統中所做的一樣——將多個文件合并成一個,對一系列有序數據文件進行合并排序。系統始終總是壓縮和大小彼此相近的文件，例如,永遠不會出現一個100GB的文件與另一個小于50GB的文件進行合并的情形。每隔一段時間就會運行一個主壓縮線程來將所有相關數據文件壓縮成一個大文件。這個壓縮進程是一個磁盤I/O密集型操作，因此需要對此做大量的優化以做到不影響后續的讀請求。

6. 實踐經驗

在Cassandra的設計、實現以及維護過程中我們積累了很多有用的經驗也學到了許多教訓。其中一個非常基礎的教訓就是在沒有了解應用使用的效果之前不要急著添加新功能。最棘手的情況不僅僅只來自于節點崩潰和網絡分區。我們將在此分享一些有趣的應用場景。

在應用的收件箱搜索（進行搜索之前）我們必須對超過1億用戶大約7TB的收件箱數據進行索引，將他們保存在我們的MySQL[1]基礎設備上，然后將其加載到Cassandra系統中。整個過程涉及到對MySQL數據文件進行Map/Reduce[7]調度；建立索引，然后將逆序索引保存到Cassandra中。實際上,M/R進程是作為Cassandra的客戶端運行的。我們為M/R進程開放后端通道，使其可以對每位用戶的反向索引進行聚合，并將將序列化的數據傳遞給Cassandra實例，以避免序列化/范序列化的額外開銷。這樣Cassandra實例的瓶頸就只剩下網絡帶寬了。

大多數應用只需要每個鍵每個副本的原子級操作。然而，任然有許多應用需要事務的支持——主要是出于維護二級索引的考慮。大多數有幾年RDBM開發經驗的開發者都認為這是一個非常實用的功能。我們正在研究一種機制開放此類原子操作。

我們嘗試了各種實現的故障檢測器，比如在 [15] 和 [5]講到的那些。我們的試驗表明隨著集群規模的增長,檢測到故障的時間也會出現增長,超出了我們的接受限度。在一個特定的包含100個節點的實驗中,檢測一個故障節點竟然耗費大約2分鐘的時間。這在我們實際的運行環境中是行不通的。采用accrual故障檢測器并設置一個稍顯保守的PHI(Φ)值(設置為5),在上面的實驗中檢測到故障的平均時間大約為15秒。

不要對監控想當然。Cassandra系統很好的集成了Ganglia[12]——一個分布式性能監測工具。我們向Ganglia開放了各種系統級別的指標，這在我們將Cassandra部署到生產環境時，幫助我們對這個系統的行為有了更深的理解。磁盤無緣無故的發生故障，當磁盤出現故障，引導算法中有一些異常分支可以修復節點，然而這實際上是一個管理操作。

7. 結論

我們已經構建，實現并且操作了一個存儲系統，它提供了可擴展性，具有高性能并且具有廣泛的適用性。我們通過使用經驗展示了Cassandra可以支持在吞吐量上有一次大的提升同時降低傳輸延時。下一步的工作包括：添加數據壓縮，支持跨key的原子操作能力，支持二級索引。

盡管Cassandra是一個完全分散的系統，我們已經意識到為了使得某些分布式特性更加可控，大量的協調必不可少。例如Cassandra集成了Zookeeper，它可以在大型可擴展分布式系統中被用來協調各種任務。我們打算對一些關鍵特性使用Zookeeper抽象，這實際上同使用Cassandra作為存儲引擎的應用的關系不大。

6.1 搜索Facebook收件箱

對于facebook收件箱來說,我們建議每個用戶都應該檢索下那些發送人和接收人都互換了的郵件. 目前啟用了兩種搜索的功能:?短語搜索- 輸入一個用戶名就能返回所有有關他曾經收到和發送過的郵件.這種模式一般是兩列組成. 對于a查詢來說,某個用戶的ID就是組成頂級列郵件的關鍵字和關鍵詞.個人郵件會在頂級列中標記出包含關鍵字的郵件.?對于b查詢來說,某個用戶的ID也是關鍵字,而且頂級列就變成接收者的ID看. 對于每個頂級列來說,個人郵件標識就是列. 這主要是為了實現緩存智能數據以便更好的讓搜索變得快速和準確. 比如,當用戶點擊進入搜索工具欄的時候就會準確的從緩存中根據關鍵字異步顯示出匹配關鍵字的郵件. 這樣,要是真選擇了某個可供選擇的選項,那么查出來的結果就好像早就緩存在內存中一樣. 目前系統可以按150節點字符串緩存大約50+TB的數據, 這些數據會在東西海岸數據中心同步儲存和展開. 下面展示了測試大量讀取數據的結果.

總結

以上是生活随笔為你收集整理的Cassandra - A Decentralized Structured Storage System的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。