CONAN ZONE

本文翻譯自Facebook員工在LADIS大會上發布的論文.Cassandra – A Decentralized Structured Storage System
這篇論文中,兩位作者詳細介紹了 Cassandra的系統架構,它的設計初衷,設計應用時使用到的相關技術,以及設計/實現/使用過程中得到的經驗教訓.

Cassandra – 一個分散的非結構化存儲系統
By Avinash Lakshman Facebook ,Prashant Malik Facebook; Translated ByJametong

概要

Cassandra 是一個分布式的存儲系統,可用來管理分布在大量廉價服務器上的巨量結構化數據,并同時提供沒有單點故障的高可用服務.Cassandra的設計目的是運行 在由幾百個節點(可能分布在多個不同的數據中心)組成的基礎設施(infrastructure)上.當節點達到這個規模時,大大小小的組件出現故障就可 能經常發生了.Cassandra在管理持久狀態時面臨這些故障,這種情況也驅動軟件系統的可靠性(reliability)與可伸縮性 (scalability)會依賴于Cassandra的服務.雖然大部分情況,Cassandra看上去像一個數據庫系統, 也與數據庫系統共享大量的設計與實現手段,但是Cassandra并不支持完整的關系數據模型;相反,它提供了一個簡單數據模型的客戶端,支持對數據布局 與數據格式的動態控制.我們設計Cassandra的初衷是,可以運行在廉價硬件上,并能在不犧牲讀效率的情況下實現高的寫吞吐量.

1. 導論

Facebook維護著世界上最大的社交網絡平臺,利用分布在世界各地的大量數據中心的成千上萬臺服務器,為上億 的用戶提供服務.Facebook平臺有嚴格的業務要求,包含性能、可靠性、效率以及高度的可伸縮性以支持平臺的持續增長.在一個包含成千上萬的組件的基 礎設施上處理故障是我們的標準運作模式;在任何時候,隨時都可能出現相當數量的服務器或網絡組件故障.這樣,軟件系統在構建時就需要將故障當作一種常態而 不是異常來處理.為了滿足上面描述的這些可靠性與可伸縮性,Facebook開發了Cassandra系統.
為了實現可伸縮性與可靠 性,Cassandra組合了多項眾所周知的技術.我們設計Cassandra的最初目的是解決收件箱搜索的存儲需要.在Facebook,這意味著這個 系統需要能夠處理非常大的寫吞吐量,每天幾十億的寫請求,隨著用戶數的規模而增長.由于我們是通過在地理上分布的數據中心對用戶進行服務的,因此支持跨越 多個數據中心的數據復制對于降低搜索延時就非常關鍵了.當我們在2008年6月發布收件箱搜索項目時,我們有1億的用戶,現在我們差不多有2.5億的用 戶,Cassandra一直保持了其對業務的承諾.目前,Facebook內部已經有多個服務部署了Cassandra作為其后端存儲系統.
本文 的結構如下.第2節討論相關研究,其中的部分研究對我們的設計有很大影響.第3節介紹詳細的數據模型.第4節簡要介紹客戶端API.第5節介紹系統設計以 及Cassandra中應用到的分布式算法.第6節介紹我們如何使用Cassandra部署Facebook平臺的一個應用.

2. 相關研究

對于為了性能、可用性與數據持久性對數據進行分布，文件系統與數據庫社區已經進行了廣泛的研究.與僅支持扁平 命名空間(namespace)的點對點(P2P)存儲系統相比,分布式文件系統通常支持層次化(hierarchical)的命名空間.與 Ficus[14]與Coda[16]類似的系統都是通過犧牲一致性來復制文件以實現高可用(high availability).通常使用特別的沖突解決(conflict resolution)程序來管理更新沖突(update conflict). Farsite[2]是一個沒有使用任何中心服務器的分布式文件系統. Farsite使用復制來實現高可用性與可伸縮性.Google文件系統(GFS)[9]是另一個分布式文件系統,用來存儲Google內部應用的各種狀 態數據.GFS設計比較簡單,用一臺主服務器存儲所有的元數據(metadata),數據拆分成塊(chunk)存儲在多個塊服務器(chunk server)上.不過,目前Google已經使用Chubby[3]抽象層為GFS的主服務器做了容錯處理(fault tolerant).Bayou[18]是一個分布式的關系數據庫系統,它支持斷開操作(個人理解為網絡斷開以后的操作)并提供最終的數據一致性 (eventual data consistency).在這些系統中,Bayou、Coda與Ficus允許斷開操作，并且在遇到類似與網絡斷開與停機時能夠做到自動復原.這些系統 在沖突解決程序上存在差異.例如,Coda與Ficus執行系統級別的沖突解決,而Bayou允許應用級別的沖突解決.但所有這些都保證最終一致性 (eventual consistency).與這些系統類似,即使在網絡段開的時候,Dynamo[6]也允許進行讀寫操作,并使用不同的沖突解決機制(部分客戶端驅動) 來解決更新沖突.傳統的基于復制的關系數據庫系統重點在保證復制數據的強一致性(strong consistency).雖然強一致性為應用寫程序提供了一個方便的編程模型,但是,這些系統在伸縮性與可用性方面卻受到了限制.因為這些系統提供強一 致性的保證,所以在網絡分開時,它們就無法進行處理.
Dynamo[6]是一個Amazon開發的存儲系統,Amazon用它來存儲檢索用戶的購 物車.Dynamo利用基于Gossip的會員算法來維護每個節點上所有其他節點的信息.可以認為Dynamo是一個只支持一跳路由請求(one-hop request routing)的結構化覆蓋層(structured overlay).Dynamo使用一個向量時鐘(vector lock)概要來發現更新沖突,但偏愛客戶端的沖突解決機制.為了管理向量時間戳(vector timestamp),Dynamo中的寫操作同時也需要執行一次讀操作.在一個需要處理非常大的寫吞吐量的系統中,這可能會成為瓶頸. Bigtable[4]既提供了結構化也支持數據的分布式,不過它依賴于一個分布式的文件系統來保證數據的持久化.

3. 數據模型

Cassandra中的表是一個按照主鍵索引的分布式多維圖.它的值是一個高度結構化的對象.表中的記錄鍵是一 個沒有大小限制的字符串,雖然它通常都只有16-36個字節的長度.無論需要讀寫多少列,單一記錄鍵的每個副本的每次操作都是一個原子操作.多個列可以組 合在一起形成一個稱為column family的列的集合,這一點與Bigtable[4]系統非常相似.Cassandra提供兩種類型的column family,簡單的column family與超級的column family.可以將超級column family想象成column family里面嵌入column family.進一步,應用還可以指定超級column family或者簡單column family里面的列的排序順序.系統允許按時間或者名稱對列進行排序.按照時間對列進行排序可以被類似于收件箱搜索這樣的應用使用,因為它們的結果始終 需要按照時間順序進行展示.column family中的每個列都需要通過規范column family : column來進行訪問,每個超級column family中的列都通過規范column family : super column : column來進行訪問.小節6.1給出了一個展示超級column family抽象能力的非常好的例子.通常,應用都會使用一個獨占的Cassandra集群,并將它們當作服務的一部分進行管理.雖 然,Cassandra系統支持多表的概念,在部署時每個概要中都只能有一個表.

4. API

Cassandra 的API由下面三種方法組成.

• insert(table, key, rowMutation)
• get(table, key, columnName)
• delete(table, key, columnName) 列名可以是column family里面的一個特定列,或column family,或超級column family,或超級列里面的一個列

5. 系統架構
一個需要在生產環境運轉的存儲系統的架構是很復雜的.除了真實的數據持久化組件外,這個系統還需要包含以下特性;可 伸縮性與強大負載均衡解決方案、會員與故障檢測、故障恢復、副本同步、超負荷處理、狀態轉移、并發與任務調度、請求編組、請求路由、系統監控與報警以及配 置管理.詳細描述這里的每一個解決方案超出了本論文的范圍,我們將集中介紹Cassandra使用的核心的分布式系統技術:分區、復制、會員、故障處理以 及伸縮性.處理讀寫請求需要所有這些模塊的協同處理.通常,一個鍵的請求可能被路由到Cassandra集群的任何一個節點去處理.這個節點會確定這個特 定的鍵的副本.對于寫操作來講,系統會將請求路由到副本上,并且等待仲裁數量的副本以確認寫操作完成.對于讀操作來講,基于客戶端要求的一致性保證,系統 要么將請求路由到最近的副本,要么將請求路由到所有的副本并等待達到仲裁數量的響應.

5.1 分區.

增 量擴展的能力是我們設計Cassandra時考慮的一個關鍵特性.它要求做到在集群中的一組節點(Node)之間動態的對數據進行分 區.Cassandra使用一致性散列(consistent hash[11])技術在整個集群上對數據進行分區,但是使用一種保證順序(order preserving)的散列函數來實現.在一致性散列中,散列函數的輸出結果區間可以看作是一個封閉的圓形空間或者”環”(例如,最大的散列值回繞到最 小的散列值).為系統中的每個節點分配這個空間上的一個隨機值,代表它在這個環上的位置.每個數據項都會根據它的鍵被指派給一個節點,通過對這個數據項的 鍵做散列計算,獲得它在環上的位置,然后按照順時針找到比它的位置大的第一個節點.這個節點就被認為是這個鍵的協調器.應用指定這個 鍵,Cassandra利用它來對請求做路由.這樣,每個節點都會負責環上的一個區間-節點與它在環上的前一個節點(逆時針)之間的區間.一致性散列的主 要優勢是增加或刪除節點只會影響到它的近鄰,其他的節點都不會受影響.基本的一致性散列算法還面臨一些挑戰.首先,在環上隨機的為每個節點指定位置可能導 致數據與負載的分布不均衡.其次,基本的一致性算法會抹殺節點之間性能的異質性(差異).解決這個問題一般有兩種方法:一種方法是在環上為節點指定多個位 置(Dynamo采用的方法),另一種方法是分析環上的負載信息,并移動負載較低的節點的位置以緩解負載過重的節點,引文[17]對此有詳細描 述.Cassandra選擇了后者,因為使用它可以簡化設計與實現,并且可以讓負載均衡的選擇更加具有確定性.

5.2 復制

Cassandra使用復制來實現高可用性與持久性.每個數據項都會被復制到N臺主機,N是通過參數”per- instance”配置的復制因子.每個鍵(k)都被指派給一個協調節點(上一節介紹的).由協調節點負責復制落在這個節點范圍的數據項的復制.除了將本 節點范圍內的數據存儲到本地外,協調器需要將這些鍵復制到環上的其他N-1個節點.關于如何復制數據,Cassandra為客戶端提供了多個選項.另 外,Cassandra還提供了多種不同的復制策略,例如”機架不可知”(rack unaware)、”機架可知”(rack aware)(同一個數據中心內)與”數據中心可知”(data-center aware).應用選擇的復制策略決定了副本的數量.使用”機架可知”與”數據中心可知”復制策略時復制的算法要稍微復雜一點.Cassandra使用一 個稱為Zookeeper[13]的系統在這些節點中選擇一個引導者(leader).所有節點在加入集群時都需要與此引導者聯系,并由引導者告知它們負 責哪個環上哪個范圍的副本,引導者還需保持協調一致的努力來保持不變,以確保沒有哪個節點負責環上的超過N-1個范圍.關于一個節點負責的范圍的元數據 (metadata)信息都會在每個節點做本地緩存,并在Zookeeper內做容錯處理,這樣當一個節點崩潰并返回的時候就可以知道它到底負責哪個范 圍.借用Dynamo的措辭,我們認為負責一個給定范圍的節點是這個范圍的”優選清單”.

5.1節已經介紹了每個節點都知悉系統中的所有其 他節點,以及它們各自負責的范圍.通過放寬5.2節介紹的仲裁數(quorum)的要求,即使在出現節點故障與網絡分區的情況下,Cassandra也可 以保證持久性.在斷電、冷卻故障、網絡故障或自然災害時，數據中心也會發生故障.可以配置Cassandra使得每條記錄都被復制到多個不同的數據中心. 實際上,可以這樣構建一個鍵的偏好列表,以實現鍵的存儲節點分布在多個數據中心.這些數據中心都是通過高速網絡進行互聯.即使整個數據中心出現故障,這種 跨越多個數據中心的復制架構允許我們做到不宕機.

5.3 會員

Cassandra中的集 群會員是基于Scuttlebutt[19]的,一個非常高效的反熵閑話(anti-entropy Gossip)機制. Scuttlebutt的突出的特點是它非常高效的CPU利用率以及非常高效的Gossip通道利用率.在Cassandra中,系統Gossip不止用 來管理會員信息,也用來傳輸其他系統相關的控制狀態.

5.3.1 故障檢測

故障檢測是這 樣一種機制,通過它一個節點在本地就可以確定系統中的任一其他節點是活著還是死了.在Cassandra中,故障檢測還被用來避免在多個操作中與不可達節 點的進行通訊.Cassandra使用的是Φ Accrual故障檢測器[8]的一個改進版本. Accrual故障檢測器的設計思路是,故障檢測模塊并不是產生一個布爾值來標記一個節點是活著還是死了.相反,故障檢測模塊為每個被監控節點產生一個代 表其懷疑級別的數值.此值被定義為Φ.其基本的思路是用Φ的值來表示一個范圍,可以動態對其進行調整以反映監控節點上的網絡與負載情況.
Φ有以下 幾種涵義:給定部分閾值Φ,并假定當Φ=1時我們就決定懷疑一個節點A,我們犯錯誤(例如,這個決定在將來可能由于心跳接收延遲而被證明是錯誤的)的概率 為10%.Φ=2時出錯的概率大約為1%,Φ=3大約為0.1%,等等.系統中的每個節點都會維護一個滑動窗口,來表示集群中其他節點的gossip信息 的到達間隔時間.確定了這些到達間隔時間的分布后,就可以計算出Φ的值了.雖然原論文認為這個分布近似于高斯分布(Gaussian distribution),由于gossip通道的本性以及他對延時(latency)的影響,我們認為它與指數分布(Exponential Distribution)更加相似.據我們所知,我們實現的Accrual故障檢測在基于Gossip的配置中還屬首創. Accrual故障檢測器在準確性與速度上表現都非常好, 它們也能很好的適應不同的網絡環境或服務器負載環境.

5.4 引導程序

當一個節點第一次啟動的時候,它會隨機的選擇一個令牌(token)作為它在環上的位置.為了容錯的需要,映射 關系會被持久化到本地磁盤以及Zookeeper中.接著令牌信息會被傳播到整個集群.我們就是通過它來知道集群中的所有節點以及它們在環上的位置的.通 過它,任何一個節點都可以將一個鍵(key)的請求路由到集群中的合適的節點.在引導過程中,當一個新的節點需要加入集群時,它需要讀取它的配置文件,配 置文件中包含集群中的幾個聯絡點名單.我們將這些聯絡點稱為集群的種子(seed).種子也可以來自一個類似于Zookeeper的配置服務 (configuration service).
在Facebook的環境中,節點停機時間(由于故障或維護任務)通常都很短暫,但有時也會延 長一段時間.故障可能有多種形式,如磁盤故障、CPU損壞等.節點停機很少不表示永遠離開(刪除節點),因此,不該導致分區指派的重新平衡或不可達副本的 修復.類似地,手工錯誤可能會導致意外地啟動新的Cassandra節點.為了避免出現這種效果,所有消息中都包含了每個Cassandra實例集群名 稱.如果配置中的手工錯誤導致一個節點嘗試加入一個錯誤的Cassandra實例,就可以根據集群名稱來阻止它.由于上述原因,使用一種明確的機制來往 Cassandra實例中添加或從中刪除節點或許更加合適.管理員使用命令行(command line)工具或者瀏覽器登陸到Cassandra的節點,提出一個會員變更(節點變更)來加入或離開集群.

5.5 集群的擴展

當有一個新節點加入系統時,它會被分配一個令牌,這樣就可以緩解負載過重的節點的負載.這樣導致的結果是,這 個新的節點會分擔部分先前由其他節點負責的范圍.Cassandra的引導算法可由系統中的任何其他節點通過命令行工具或Cassandra的網絡儀表盤 (web dashboard)來啟動.放棄這部分數據的節點通過內核到內核的拷貝技術將數據拷貝到新的節點.我們的運維經驗顯示,從單個節點傳輸的速率可以達到 40MB/s.我們還在努力對它進行改善,通過讓多個副本來參與并行化引導傳輸,類似于Bittorrent技術.

5.6 本地持久化

Cassandra系統要依賴于本地文件系統做數據的持久化.這些數據是以一種易于高效檢索的格式存儲在磁 盤上.通常,一次寫操作會涉及提交日志(Commit Log,為了數據耐用性與可恢復性)寫入,以及一次內存數據結構的更新.只有在寫入提交日志成功返回后,才會執行內存數據結構的寫入操作.在每臺主機上, 我們都單獨地分配了一塊磁盤存放提交日志.由于提交日志地所有寫入操作都是連續的(sequential),所以我們可以最大程度的利用磁盤吞吐量.當內 存數據結構的大小(根據數據量大小與對象數量計算得出)超過一定的閾值,它就會將自身轉儲到磁盤.這個寫操作會機器配備大量的廉價磁盤的某一個上執行.所 有到磁盤的寫操作都是順序寫.隨著時間的推移,磁盤上就會存在多個這樣的文件,后臺會有一個合并進程(merge process)將這些文件合并成一個文件.這個進程與Bigtable系統中的壓縮進程(compact process)非常類似.
通常,一 個讀操作在檢索磁盤文件之前會先查詢這個內存數據結構.檢索磁盤文件是按照先新后舊的方式進行的.當發生磁盤檢索時,我們可能需要查看多個磁盤文件.為了 避免查看不包含相應鍵(key)的文件,我們使用了布隆過濾器(bloom filter),它對文件中的鍵進行了匯總,它同時存在于每一個數據文件中并常駐在內存中.當需要檢索某個鍵時,會先查閱此布隆過濾器以確認給定的文件是 否確實包含此鍵.column family中的一個鍵可以包含大量的列.當檢索的列距離鍵較遠時還需要利用一些特殊的索引.為了避免在磁盤上掃描每一列,我們維護了一份列索引來幫助我 們直接定位到磁盤上的對應塊.由于指定鍵的列已經被序列化并寫出到磁盤,我們是按照每個塊(chunk)256K的范圍創建索引的.塊的范圍大小是可配置 的,不過,我們發現256K的大小在我們的生產工作負載下運作良好.

5.7 實現細節

單 臺機器上的Cassandra進程主要由以下模塊組成:分區模塊、集群會員管理模塊、故障檢測模塊與存儲引擎模塊.所有這些模塊都依賴于一個事件驅動的底 層模塊,它是按照SEDA[20]架構設計的,將消息處理管道與任務管道切分成了多個階段.所有這些模塊都是完全利用Java實現.集群會員模塊與故障檢 測模塊都建立在使用非堵塞IO的網絡層上.所有的系統控制信息都依賴于基于UDP協議的消息傳輸,而復制與請求路由等應用相關的消息則依賴于TCP協議傳 輸.請求路由模塊的實現使用了一個固定的狀態機.當集群的任一節點收到一個讀/寫請求時,狀態機都會在以下幾種狀態之間切換: (i)定位擁有這個鍵的數據的節點(ii)將請求路由到此節點并等待響應到達(iii)如果答復沒有在配置的超時時間內到達,就將此請求置為失敗并返回給 客戶端(iv)根據時間戳算出最新的答復(v)為任何數據不是最新的副本的安排數據修復.出于論述起見,詳細的故障情況我們就不在此討論了.這個系統的復 制模式可以配置為同步寫(synchronous write)也可以配置為異步寫(asynchronous write).對于特定的需要高吞吐量的系統,我們會選擇依賴于異步復制.這時,系統接收到的寫操作遠遠超過讀操作.對于使用同步的例子,在返回給用戶之 前我們會等待達到仲裁的響應數量.
在任何日志文件系統中,都需要有一個機制來清理提交日志項(commit log entry), 在Cassandra中,我們使用一種滾動的提交日志,在一個舊的提交日志超過一個特定的可配置大小后,就推出一個新的提交日志.在我們的生產環境中,我 們發現128M的滾動提交日志運作良好. 每個提交日志都有一個頭信息,基本上是一個大小固定的位向量,其大小通常超過一個系統可能處理的column family的個數.在我們的實現中,對于每個column family,我們都會生成一個內存數據結構以及一個數據文件.每當一個特定的column family的內存數據結構轉儲到磁盤,我們都會在提交日志中記錄它對應的位,說明這個column family已經被成功地持久化到磁盤.這表明這部分信息已經提交了.每個提交日志都有一份對應的位向量,這些位向量的信息同時也在內存中進行維護.每當 發生提交日志滾動的時候,它的位向量,以及它之前滾動的提交日志的位向量都會被檢查一下.如果確定所有的數據都已經被成功地持久化到磁盤,就刪除這些提交 日志.到提交日志的寫操作可以是普通模式(normal mode)也可以是快速同步模式(fast sync mode).在快速同步模式下,到提交日志的寫操作會被緩沖(buffered).這表明在機器崩潰時可能會出現潛在的數據丟失.在這種模式下,內存數據 結構轉儲到磁盤也會被緩沖.傳統的數據庫通常都不會被設計用來處理特別高的寫入吞吐量.Cassandra將所有的寫入操作都轉換成順序寫操作以最大限度 地利用磁盤的寫入吞吐量.由于轉儲到磁盤的文件不再會被修改,從而在讀取它們的時候也不需要持有任何鎖.Cassandra的服務實例的讀寫操作實際上都 是無鎖操作.所以,我們并不需要應付基于B-Tree的數據庫實現中存在的并發問題.
Cassandra系統通過主鍵來來索引所有數據.磁盤上的 數據文件被分解成一系列的塊.每個塊內最多包含128個鍵,并通過一個塊索引來區分.塊索引抓取塊內的鍵的相對偏移量以及其數據大小.當內存數據結構被轉 儲到磁盤時,系統會為其生成一個索引,它的偏移量會被寫當作索引寫到磁盤上.內存中也會維護一份這個索引以提供快速訪問.一個典型的讀操作總是會先檢索內 存數據結構.如果找到就將數據返回給應用程序,因為內存數據結構中包含任何鍵的最新數據.如果沒有找到,那么我們就需要對所有磁盤數據文件按照時間逆序來 執行磁盤IO.由于總是尋求最新的數據,我們就先查閱最新的文件,一旦找到數據就返回.隨著時間的推移,磁盤上的數據文件數量會出現增加.我們會運行一個 非常類似于Bigtable系統的壓縮進程,通過它將多個文件壓縮成一個文件.基本上是對很多排序好的數據文件進行合并排序.系統總是會壓縮大小彼此接近 的文件,例如,永遠不會出現一個100GB的文件與另一個小于50GB的文件進行合并的情形.每隔一段時間,就會運行一個主壓縮程序來將所有相關的數據文 件壓縮成一個大文件.這個壓縮進程是一個磁盤IO密集型的操作.需要對此做大量的優化以做到不影響后續的讀請求.

6. 實踐經驗

在設計、實現以及維護Cassandra的過程中,我們積累了不少有益的經驗,也獲得了許多經驗教訓.一個非常 基本的經驗教訓是,在沒有理解應用的使用效果之前不要增加任何新特性.最成問題的情況不僅僅來自節點崩潰與網絡分區.我們將在此分享幾個有趣的場景.

• 在 發布收件箱搜索應用之前,我們必須先為超過1億用戶的7TB的收件箱數據創建索引,接著將它們存儲到我們的MySQL[1]基礎結構中,然后再將它們加載 到Cassandra系統中.整個處理過程涉及到在MySQL數據文件上運行Map/Reduce[7]任務,為它們創建索引,并按照逆序索引的方式將它 們存儲到Cassandra中.實際上,M/R進程是作為Cassandra的客戶端運行的.我們為M/R進程開放了后端通道,使它們可以按用戶匯總逆序 索引,并將序列化后的數據傳輸給Cassandra實例,以節省序列化/反序列化的開銷.這樣,Cassandra實例的瓶頸就只剩下網絡帶寬了.
• 大 部分應用都是只需要每個鍵的每個副本的原子操作.不過,還是有部分應用需要交易支持,它的主要目的是維護輔助索引.大部分有著多年RDBMS相關開發經驗 的開發人員都認為這個特性很有用.我們正在研究開放此類原子操作的機制.
• 我們嘗試實現了多種故障檢測器,包含[15]與[5]中所描述 的故障檢測器.我們得到的經驗是,隨著集群規模的增長,檢測到故障的時間也會出現增長,超出了我們的接受限度.在一個特定的包含100個節點的實驗中,檢 測一個故障節點竟然耗費大約2分鐘的時間.在我們的環境中,這實際上是不可接受的.利用accrual故障檢測器并設置一個稍顯保守的PHI(Φ)值(設 置為5),在上面的實驗中檢測到故障的平均時間大約為15秒.
• 不要對監控想當然.Cassandra系統與Ganglia[12]做了 很好的集成,Ganglia是一個分布式的性能監控工具.我們向Ganglia開放了各種系統級別的指標,在Cassandra部署到我們的生產環境時, 這一點幫助我們更深的理解了這個系統的行為.磁盤會無緣無故地出現故障.當磁盤出現故障時,引導算法中有多個異常分支(hook)來修復這個節點.但是, 這實際上是一個管理操作.
• 雖然Cassandra是一個完全分散地系統,我們了解到,為了使一些分布式特性的實現更加可控,支持一定數 量的協調操作還是非常必要的.我們打算對部分關鍵特性使用Zookeeper抽象,這些特性實際上與使用Cassandra作為存儲引擎的應用關系不大.

6.1 Facebook的收件箱搜索

對于收件箱搜索,我們為每個用戶維護了一份所有消息的索引,這些消息包含用戶作為發送者 的消息也包含其作為接收者的消息.目前啟用了兩種類型的索引(a)術語搜索(b)互動搜索,根據與此用戶給定互動的人的名稱返回用戶發送給此人以及從此人 處接收的所有消息.這個概要(schema)包含兩個column family,對于查詢(a),用user id作為鍵(key),以構成消息的單詞作為超級列(super column).對于查詢(b),user id仍然是鍵(key),接收者的id都是super column.對于這些super column中的每一個,單個消息的識別符都是列.為了實現快速檢索,Cassandra為數據的智能緩存提供了特定的鉤子(hook)代碼.例如,當用 戶點擊到搜索欄時,會有一條異步消息發送給Cassandra集群,再通過用戶索引在高速緩存(buffer cache)中準備好該用戶的數據.這樣,當實際的搜索查詢請求到達時,搜索結果很可能已經在內存中了.目前,這個系統在150個節點的集群上存儲了大約 50多TB的數據,這些節點分布在美國東西海岸的多個數據中心.下面展示了部分生長環境中測量出來的讀性能數據.

7. 結論

我們已經建立、實現并維護的存儲系統，可以提供可伸縮性、高性能與廣泛的適用性.我們的經驗表 明,Cassandra可以在提供低延時(low latency)的同時提高非常高的更新吞吐量(thoughput).后期的工作涉及增加壓縮功能、跨越多個鍵的原子操作支持以及輔助索引支持.

8. 致謝

Cassandra極大地受益與Facebook公司內部許多同事的反饋.另外還要特別感謝Karthik Ranganathan,他對MySQL中的所有數據建立了索引并將這些數據遷移到Cassandra中作為我們第一份正式部署.另外還要感謝來自 EPFL的Dan Dumitriu,感謝他對我們提出的寶貴建議(關于[19]與[8]).

9. 參考文獻

[1] MySQL AB. Mysql.
[2] Atul Adya, William J. Bolosky, Miguel Castro, Gerald Cermak, Ronnie Chaiken, John R. Douceur, Jon Howell, Jacob R. Lorch, Marvin Theimer, and Roger P. Wattenhofer. Farsite: Federated, available, and reliable storage for an incompletely trusted environment. In In Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI, pages 1-14, 2002.
[3] Mike Burrows. The chubby lock service for loosely-coupled distributed systems. In OSDI ‘06: Proceedings of the 7th symposium on Operating systems design and implementation, pages 335-350, Berkeley, CA, USA, 2006. USENIX Association.
[4] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. Bigtable: A distributed storage system for structured data. In In Proceedings of the 7th Conference on USENIX Symposium on Operating Systems Design and Implementation – Volume 7, pages 205-218, 2006.
[5] Abhinandan Das, Indranil Gupta, and Ashish Motivala. Swim: Scalable weakly-consistent infection-style process group membership protocol. In DSN ‘02: Proceedings of the 2002 International Conference on Dependable Systems and Networks, pages 303-312, Washington, DC, USA, 2002. IEEE Computer Society.
[6] Giuseppe de Candia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: amazonO? s highly available key-value store. In Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, pages 205-220. ACM, 2007.
[7] Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data processing on large clusters. Commun. ACM, 51(1):107-113, 2008.
[8] Xavier D?efago, P?eter Urba?n, Naohiro Hayashibara, and Takuya Katayama. The φ accrual failure detector. In RR IS-RR-2004-010, Japan Advanced Institute of Science and Technology, pages 66-78, 2004.
[9] Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. The google file system. In SOSP ‘03: Proceedings of the nineteenth ACM symposium on Operating systems principles, pages 29-43, New York, NY, USA, 2003. ACM.
[10] Jim Gray and Pat Helland. The dangers of replication and a solution. In In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, pages 173-182, 1996.
[11] David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigrahy. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In In ACM Symposium on Theory of Computing, pages 654-663, 1997.
[12] Matthew L. Massie, Brent N. Chun, and David E.Culler. The ganglia distributed monitoring system: Design, implementation, and experience. Parallel Computing, 30:2004, 2004.
[13] Benjamin Reed and Flavio Junquieira. Zookeeper.
[14] Peter Reiher, John Heidemann, David Ratner, Greg Skinner, and Gerald Popek. Resolving file conflicts in the ficus file system. In USTC’94: Proceedings of the USENIX Summer 1994 Technical Conference on USENIX Summer 1994 Technical Conference, pages 12-12, Berkeley, CA, USA, 1994. USENIX Association.
[15] Robbert Van Renesse, Yaron Minsky, and Mark Hayden. A gossip-style failure detection service. In Service,Tˇ Proc. Conf. Middleware, pages 55-70, 1996.
[16] Mahadev Satyanarayanan, James J. Kistler, Puneet Kumar, Maria E. Okasaki, Ellen H. Siegel, and David C. Steere. Coda: A highly available file system for a distributed workstation environment. IEEE Trans. Comput., 39(4):447-459, 1990.
[17] Ion Stoica, Robert Morris, David Liben-nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan. Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Transactions on Networking, 11:17-32, 2003.
[18] D. B. Terry, M. M. Theimer, Karin Petersen, A. J. Demers, M. J. Spreitzer, and C. H. Hauser. Managing update conflicts in bayou, a weakly connected replicated storage system. In SOSP ‘95: Proceedings of the fifteenth ACM symposium on Operating systems principles, pages 172-182, New York, NY, USA, 1995. ACM.
[19] Robbert van Renesse, Dan Mihai Dumitriu, Valient Gough, and Chris Thomas. Efficient reconciliation and flow control for anti-entropy protocols. In Proceedings of the 2nd Large Scale Distributed Systems and Middleware Workshop (LADIS ‘08), New York, NY, USA, 2008. ACM.
[20] Matt Welsh, David Culler, and Eric Brewer. Seda: an architecture for well-conditioned, scalable internet services. In SOSP ‘01: Proceedings of the eighteenth ACM symposium on Operating systems principles, pages 230-243, New York, NY, USA, 2001. ACM.

No related posts.