大智若魚::人生處處是道場: [雲端計算] 論文:Cassandra-一個分散式結構儲存系統(轉譯)

簡要說明一下老魚重新校譯和排版本篇文選的原由：

在 2009 年 Facebook 在 LADIS 大會上發佈這篇論文, 並且已經建立、實作並維護的該儲存系統，它可以提供可伸縮性、高性能與廣泛的適用性. 在 Facebook 經驗表明, Cassandra 可以在提供低延時(low latency)的同時, 提高非常高的更新吞吐量(thoughput). 後期的工作涉及增加壓縮功能、跨越多個鍵(key)的原子性作業支持以及輔助索引支持.

老魚籍由這篇論文, 它提供了下列幾點必要閱讀它的理由：

用以理解 Cassandra 來自 Google Bigtable 與 Amazon Dynamo 二者論文中, 所貢獻的系統設計思維.
對於準備或是目前正踏入雲端計算系統與應用的學術研究單位, 產品開發單位, 本篇論文與 Google BigTable 的論文同樣俱備參考價值.
Google / Facebook 所建構的雲系統, 二者均在其各自的論文中強調, 全數建構在廉價且大量以萬計的 PC Server 甚至僅是客製化 PC 主機板, 以獲取其日益低價的 RAM 與 PC 硬碟的成本效益優勢, 輔以 GNU/Linux 作業系統作為最底層的系統起始載體, 並在設計此雲系統的前提條件中, 都視各別叢集節點會發生故障為常態來開發該雲計算系統, 如此帶來高效能低成本的優勢價值, 絕非建立在購買高昂的名牌伺服器, 或甚投資大型單體叢集主機, 各位學習雲端計算者若無法接受這觀點, 實無法掌握 Cloud Copmuting 真正的系統研究價值.

因此, 老魚希望有心的您可以好好的閱讀它, 當然如果能配合實裝 Cassandra, 以達知行合一, 您將更加瞭解它. 世上沒有完美的IT系統, 但它可使您精進學習IT甚至突破創新！老魚一慣的習性用“紅筆字”, 劃上了自己認為的閱讀重點, 供各位參考, 看完本篇如果您有興趣深入, 可以再閱讀老魚先前 Blog 所整理的相關文章：

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

Cassandra - 一個分散式結構儲存系統

By Avinash Lakshman Facebook ,Prashant Malik Facebook

簡體中文譯者：jametong

原文出處：http://www.dbthink.com/?p=372

正體中文轉校譯文：郭朝益, http://oss-tw.blogspot.com/

概要

Cassandra 是一個分散式的儲存系統, 可用來管理分散在大量廉價伺服器上的巨量結構化資料, 並同時提供沒有單點故障的高可用性服務. Cassandra 的設計目的是運行在由數百個節點(node)也可能是分散於多個不同的資料中心所組成的基礎設施(infrastructure)上. 當節點達到這個規模層級時, 大大小小的組件出現故障就可能經常發生了, 而成為一種常態. Cassandra 在管理持久(Persistence)狀態時會面臨這些故障, 這種情況也驅動軟體系統的可靠性(reliability)與可伸縮性(scalability)須要依賴於 Cassandra 的服務.

雖然在大部分情況下, Cassandra 看上去像一個資料庫系統, 也與資料庫系統共享著大量的設計與實作手段, 但是Cassandra 並不支持完整的關聯式資料模型; 相反, 它提供了一個簡單資料模型的客戶端(Clinet), 支持對資料佈局與資料格式的動態控制. 我們設計 Cassandra 的初衷是: 可以運行在廉價硬體上, 並能在不犧牲讀取效率的情況下實作高效的寫入吞吐量.

1. 導論

Facebook 維護著世界上最大的社交網路平台, 利用分散在世界各地的大量資料中心的成千上萬台伺服器, 為上億的使用者提供服務. Facebook 平台有嚴格的業務要求, 包含性能、可靠性、效率以及高度的可伸縮性以支持平台的持續增長. 在一個包含成千上萬的組件的基礎設施上處理故障是我們的標準運作模式; 在任何時候, 隨時都可能出現相當數量的伺服器或網路組件故障. 如此, 軟體系統在構建時就需要將故障當作一種常態而不是異常來處理. 為了滿足上面描述的這些可靠性與可伸縮性, Facebook 開發了 Cassandra 系統.

為了實作可伸縮性與可靠性, Cassandra 組合了多項眾所周知的技術. 我們設計 Cassandra 的最初目的是解決收件箱(inbox)搜尋的儲存需要. 在 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 中的表格(talbe)是一個按照主鍵(PK)索引的分散式多維圖. 它的值是一個高度結構化的物件. 表格中的記錄鍵是一個沒有大小限制的字符串(string), 雖然它通常都只有16-36個位元組(bytes)的長度. 無論需要讀寫多少列, 單一記錄鍵的每個副本的每次作業都是一個原子性作業. 多個列可以組合在一起形成一個稱為 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 叢集(Cluster), 並將它們視為提供服務的一部分進行管理. 雖然, Cassandra 系統支持多數表格的概念, 但部署時在每個架構網要(Schema)中都只能有一個表格.

4. API

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

insert(table, key, rowMutation)
get(table, key, columnName)
delete(table, key, columnName)

列名可以是 column family 裡面的一個特定列, 或 column family, 或超級 column family, 或超級列裡面的一個列.

5. 系統架構

一個需要在生產環境運轉的儲存系統其架構是很複雜地. 除了真實的資料持久化組件外, 這個系統還需要包含以下特性; 可伸縮性與強大負載均衡(LB)解決方案、成員與故障檢測、故障/災難恢復、副本同步、超量負荷處理、狀態轉移、共時同作(Concurrency)與任務排程、請求編組、請求路由、系統監控與警報以及組態配置管理.

詳細描述這裡的每一個解決方案超出了本論文的範圍, 我們將集中介紹 Cassandra 使用的核心分散式系統技術:

分區、複寫、成員、故障處理以及伸縮性. 處理讀寫請求需要所有這些模組的協同處理. 通常,一個鍵(key)的請求可能被路由到 Cassandra 叢集的任何一個節點去處理. 這個節點會確保這個特定的鍵副本. 對於寫入作業來說, 系統會將請求路由到副本上, 並且等待仲裁數量的副本以確保寫入作業完成. 對於讀取作業來講, 基於客戶端要求的一致性保證, 系統要麼將請求路由到最近的副本, 要麼將請求路由到所有的副本並等待達到仲裁數量的回應.

5.1 分區(Partitioning)

增量擴展能力是我們設計 Cassandra 時考慮的一個關鍵特性. 它要求做到在叢集中的一組節點(Node)之間動態的對資料進行分區. Cassandra 使用一致性雜湊(consistent hash[11])技術在整個叢集上對資料進行分區, 但是使用一種保證順序(order preserving)的雜湊函數來實作.

在一致性雜湊中, 雜湊函數的輸出結果區間可以看作是一個封閉的圓形空間或者“環(ring)”(例如,最大的雜湊值迴繞到最小的雜湊值). 為系統中的每個節點分配這個空間上的一個隨機值, 代表它在這個環上的位置. 每個資料項都會根據它的鍵被指派給一個節點, 通過對這個資料項的鍵做雜湊計算, 獲得它在環上的位置,然後按照順時針找到比它的位置大的第一個節點.這個節點就被認為是這個鍵的協調器. 應用指定這個鍵, Cassandra 利用它來對請求做路由. 這樣,每個節點都會負責環上的一個區間-節點與它在環上的前一個節點(逆時針)之間的區間. 一致性雜湊的主要優勢是增加或刪除節點只會影響到它的近鄰, 其他的節點都不會受影響.

基本的一致性雜湊演算法還面臨一些挑戰. 首先, 在環(ring)上隨機性為每個節點指定位置可能導致資料與負載的分散不均衡. 其次, 基本的一致性演算法會抹殺節點之間性能的異質性(差異). 解決這個問題一般有兩種方法: 一種方法是在環上為節點指定多個位置(Dynamo採用的方法), 另一種方法是分析環上的負載資訊, 並移動負載較低的節點的位置以緩解負載過重的節點, 引文[17] 對此有詳細描述. Cassandra 選擇了後者, 因為使用它可以簡化設計與實作, 並且可以讓負載均衡的選擇更加具有確定性.

5.2 複寫(Replication)

Cassandra 使用複寫來實作高可用性與持久性. 每個資料項都會被複寫到 N 台主機, N 是通過每個實例“per-instance”參數配置的複寫因子. 每個鍵(key)都被指派給一個協調節點(上一節介紹的). 由協調節點負責複寫落在這個節點範圍中資料項的複寫. 除了將本節點範圍內的資料儲存到本地外, 協調器需要將這些鍵複製到環(ring)上的其他 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 成員(Membership)

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

5.3.1 故障檢測(Failure Detection)

故障檢測是這樣一種機制, 通過它一個節點在本地就可以確定系統中的任一其他節點是活著還是死了. 在 Cassandra 中, 故障檢測還被用來避免在多個作業中與不可達節點的進行通訊. Cassandra 使用的是 Φ Accrual 故障檢測器[8] 的一個改進版本.

Accrual 故障檢測器的設計思路是,故障檢測模組並不是產生一個布林值(boolean)來標記一個節點是活著還是死了. 相反, 故障檢測模組為每個被監控節點產生一個代表其懷疑級別的數值. 此值被定義為Φ. 其基本的思維是用 Φ 的值來表示一個範圍, 可以動態對其進行調整以反映監控節點上的網路與負載情況. Φ有以下幾種涵義: 給定部分閾值Φ, 並假定當 Φ=1 時我們就決定懷疑一個節點A, 我們犯錯誤(例如, 這個決定在將來可能由於心跳接收延遲而被證明是錯誤的)的機率為 10%. Φ=2 時出錯的機率大約為 1%, Φ=3 大約為 0.1%, 等等. 系統中的每個節點都會維護一個滑動窗口, 來表示叢集中其他節點的 gossip 訊息的到達間隔時間. 確定了這些到達間隔時間的分散後, 就可以計算出 Φ 的值了.

雖然原論文認為這個分散近似於高斯分散(Gaussian distribution), 由於 gossip 通道的本性以及它對延時(latency)的影響, 我們認為它與指數分散(Exponential Distribution)更加相似. 據我們所知, 我們實作的 Accrual 故障檢測在基於Gossip 的組態配置中還屬首創. Accrual 故障檢測器在準確性與速度上表現都非常好, 它們也能很好的適應不同的網路環境或伺服器負載環境.

5.4 引導程序(bootstrapping)

當一個節點第一次啟動的時候, 它會隨機的選擇一個標記(token)作為它在環(ring)上的位置. 為了容錯的需要, 映射(map)關係會被持久化到本地硬碟以及 Zookeeper 中. 接著 token 訊息會被傳播到整個叢集. 我們就是通過它來知道叢集中的所有節點以及它們在環上的位置的. 通過它, 任何一個節點都可以將一個鍵(key)的請求路由到叢集中的合適的節點. 在引導過程中, 當一個新的節點需要加入叢集時, 它需要讀取它的配置檔案, 配置檔案中包含叢集中的幾個聯絡點名單. 我們將這些聯絡點稱為叢集的種子(seed). 種子也可以來自一個類似於Zookeeper的配置服務(configuration service).

在Facebook的環境中, 節點停機時間(由於故障或維護任務)通常都很短暫, 但有時也會延長一段時間. 故障可能有多種形式,如硬碟故障、CPU 損壞等. 節點停機很少不表示永遠離開(刪除節點), 因此, 不該導致分區指派的重新平衡或不可達副本的修復. 類似地, 人為錯誤也可能會導致意外地啟動新的 Cassandra 節點. 為了避免出現這種結果, 所有訊息中都包含了每個 Cassandra 實例叢集名稱. 如果組態配置中的人為錯誤導致一個節點嘗試加入一個錯誤的Cassandra 實例, 就可以根據叢集名稱來阻止它. 由於上述原因, 使用一種明確的機制來往 Cassandra 實例中添加或從中刪除節點或許更加合適. 管理員使用命令行(command line)工具或者瀏覽器登陸到 Cassandra 的節點,提出一個成員變更(節點變更)來加入或離開叢集.

5.5 叢集的縮展(Scaling the Cluster)

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

5.6 本地持久化(Local Persistence)

Cassandra 系統要依賴於本地檔案系統做資料的持久化. 這些資料是以一種易於高效檢索的格式儲存在硬碟上. 通常, 一次寫入作業會涉及提交日誌(Commit Log, 為了資料耐久性與可恢復性)寫入, 以及一次 RAM 資料結構的更新.只有在寫入提交日誌成功返回後, 才會執行 RAM 資料結構的寫入作業. 在每台主機上, 我們都單獨地分配了一塊硬碟存放提交日誌.

由於提交日誌地所有寫入作業都是連續的(sequential), 所以我們可以最大程度的利用硬碟吞吐量. 當 RAM 資料結構的大小(根據資料量大小與物件數量計算得出)超過一定的閾值, 它就會將自身轉儲到硬碟. 這個寫入作業會機器配備大量的廉價硬碟的某一個上執行. 所有到硬碟的寫入作業都是順序寫入. 隨著時間的推移, 硬碟上就會存在多個這樣的檔案, 後台會有一個合併進程(merge process)將這些檔案合併成一個檔案. 這個進程與 Bigtable 系統中的壓縮進程(compact process)非常類似.

通常, 一個讀取作業在檢索硬碟檔案之前會先查詢這個 RAM 資料結構. 檢索硬碟檔案是按照先新後舊(後進先出, LI-FO)的方式進行的. 當發生硬碟檢索時, 我們可能需要查看多個硬碟檔案. 為了避免查看不包含相應鍵(key)的檔案, 我們使用了布隆過濾器(bloom filter), 它對檔案中的鍵進行了彙總, 它同時存在於每一個資料檔案中並常駐在內存中. 當需要檢索某個鍵時, 會先查閱此布隆過濾器以確認給定的檔案是否確實包含此鍵.

column family 中的一個鍵可以包含大量的列. 當檢索的列距離鍵較遠時還需要利用一些特殊的索引. 為了避免在硬碟上掃瞄每一列, 我們維護了一份列索引來幫助我們直接定位到硬碟上的對應區塊(chunk). 由於指定鍵的列已經被序列化並寫出到硬碟, 我們是按照每個區塊 256K 的範圍創建索引的. 塊的範圍大小是可配置的, 不過, 我們發現 256K 的大小在我們的生產工作負載下運作良好.

5.7 實作細節

單一機器上的 Cassandra 進程主要由以下模組組成: 分區模組、叢集成員管理模組、故障檢測模組與儲存引擎模組. 所有這些模組都依賴於一個事件驅動的底層模組, 它是按照 SEDA[20] 架構設計的, 將訊息處理管道與任務管道切分成了多個階段.

這些全部模組都是完全利用 Java 實作的. 叢集成員模組與故障檢測模組都建立在使用非阻塞 IO 的網路層上. 所有的系統控制資訊都依賴於基於 UDP 協議的訊息傳輸, 而複寫與請求路由等應用相關的訊息則依賴於 TCP 協議傳輸.請求路由模組的實作使用了一個固定的狀態機.

當叢集的任一節點收到一個讀取/寫入請求時, 狀態機都會在以下幾種狀態之間切換：

(i)定位擁有該鍵(key)資料的節點
(ii)將請求路由到此節點並等待回應到達
(iii)如果答覆沒有在組態配置所設的超時時間內到達, 就將此請求置為失敗並返回給客戶端
(iv)根據時間戳記算出最新的答覆
(v)為任何資料不是最新副本進行安排資料的修復.

出於論述起見, 詳細的故障情況我們就不在此討論了. 這個系統的複寫模式可以配置為同步寫入(synchronous write)也可以配置為非同步寫入(asynchronous write). 對於特定的需要高吞吐量的系統, 我們會選擇依賴於非同步複寫. 這時, 系統接收到的寫入作業遠遠超過讀取作業. 對於使用同步的例子, 在返回給使用者之前我們會等待達到仲裁的回應數量.

在任何的日誌式檔案系統中, 都需要有一個機制來清理提交日誌項(commit log entry), 在 Cassandra 中, 我們使用一種滾動式的提交日誌, 在一個舊的提交日誌超過一個特定的可組態配置大小後, 就推動產出一個新的提交日誌. 在我們的生產環境中, 我們發現 128M 的滾動提交日誌運作良好.

每個提交日誌都有一個檔頭資訊, 基本上是一個大小固定的位向量值, 其大小通常超過一個系統可能處理的 column family 的個數. 在我們的實作中, 對於每個 column family, 我們都會產出一個 RAM 資料結構以及一個資料檔案. 每當一個特定的 column family 的 RAM 資料結構轉儲到硬碟, 我們都會在提交日誌中記錄它對應的位值, 說明這個column family 已經被成功地持久化到硬碟. 這表明這部分資訊已經提交了. 每個提交日誌都有一份對應的位向量,這些位向量的資訊同時也在 RAM 中進行維護. 每當發生提交日誌向前滾動的時候, 它的位向量, 以及它之前滾動的提交日誌的位向量都會被檢查一下. 如果確定所有的資料都已經被成功地持久化到硬碟, 就刪除這些提交日誌.

提交日誌的寫入作業可以是普通模式(normal mode)也可以是快速同步模式(fast sync mode). 在快速同步模式下,到提交日誌的寫作業會被緩衝(buffered). 這表明在該機器崩潰時可能會出現潛在的資料丟失. 在這種模式下, RAM 資料結構轉儲到硬碟也會被緩衝. 傳統的資料庫通常都不會被設計用來處理特別高的寫入吞吐量. Cassandra 將所有的寫入作業都轉換成順序寫作業以最大限度地利用硬碟的寫入吞吐量. 由於轉儲到硬碟的檔案不再會被修改, 從而在讀取它們的時候也不需要持有任何鎖. Cassandra 的服務實例的讀寫作業實際上都是無鎖作業. 所以, 我們並不需要應付基於 B-Tree 的資料庫實作中存在的共時同作(Concurrency)問題.

Cassandra 系統通過主鍵(PK)來索引所有資料. 硬碟上的資料檔案被分解成一系列的塊. 每個塊內最多包含 128 個鍵, 並通過一個塊索引來區分. 塊索引抓取塊內的鍵的相對偏移量以及其資料大小. 當 RAM 資料結構被轉儲到硬碟時, 系統會為其生成一個索引, 它的偏移量會被寫入當作索引寫到硬碟上. RAM 中也會維護一份這個索引以提供快速存取. 一個典型的讀取作業總是會先檢索 RAM 資料結構. 如果找到就將資料返回給應用程序, 因為 RAM 資料結構中包含任何鍵的最新資料. 如果沒有找到, 那麼我們就需要對所有硬碟資料檔案按照時間逆序來執行硬碟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)中準備好該使用者的資料. 這樣, 當實際的搜尋查詢請求到達時, 搜尋結果很可能已經在 RAM 中了. 目前, 這個系統在 150 個節點的叢集上儲存了大約 50多TB 的資料, 這些節點分散在美國東西海岸的多個資料中心.下面展示了部分生長環境中測量出來的讀取性能資料.

延時統計	搜尋交互	術語
最小	7.69ms	7.78ms
中數	15.69ms	18.27ms
最大	26.13ms	44.41ms

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.