Avinash Lakshman , Facebook Prashant Malik，F(xiàn)acebook

?

?????????????????????????????張鵬@Sina RDC 譯

?

???????????????????????????????? 摘要 ABSTRACT

?

Cassandra 是一個分布式的存儲引擎，用來管理分布在大量普通商用級別服務(wù)器上面的海量的結(jié)構(gòu)化數(shù)據(jù)，可以提供高可用性，不存在單點故障。Cassandra設(shè)計目標，是運行在千臺規(guī)模的服務(wù)器節(jié)點上面，節(jié)點可以跨越IDC.在這個規(guī)模上，大小組件都會頻繁的發(fā)生故障。當故障發(fā)生時，Cassandra通過對持久層狀態(tài)的有效管理，來達成整個系統(tǒng)的可靠性和擴展性。在很多場合，Cassandra作為一個數(shù)據(jù)庫來使用，因此他借鑒了很多數(shù)據(jù)庫的設(shè)計和實現(xiàn)策略，但是他不能支持完整的關(guān)系數(shù)據(jù)庫模型；相反，他提供給客戶端一個簡單的數(shù)據(jù)模型，客戶端可以通過這個模型，來動態(tài)控制數(shù)據(jù)的布局和格式。Cassandra系統(tǒng)設(shè)計成可以運行在大量廉價商用機上面，具備高寫吞吐量的同時，不犧牲讀性能。

?

1.介紹 INCRODUCTION

?

Facebook是最大的社交網(wǎng)絡(luò)平臺，在峰值的時候，他可以通過部署在世界各地很多數(shù)據(jù)中心的幾萬臺服務(wù)器為幾億用戶提供服務(wù)。Facebook的平臺，為滿足系統(tǒng)性能，可靠性和效率，為滿足業(yè)務(wù)上的持續(xù)增長的擴展性，對運維提出了嚴格的需求。處理具有千臺的節(jié)點規(guī)模的基礎(chǔ)架構(gòu)的故障，已經(jīng)成為我們工作的常態(tài)。另外還有很多小的節(jié)點和網(wǎng)絡(luò)組件，在任何時候也都會發(fā)生故障。因此軟件系統(tǒng)在設(shè)計的時候，要把這些節(jié)點故障當成常態(tài)，而不是例外來處理。 為了應(yīng)對上述可靠性和擴展性挑戰(zhàn)，F(xiàn)acebook開發(fā)了Cassandra.

?

Cassandra采用了一系列眾所周知的技術(shù)，來達到擴展性和可用性。 Cassandra 被設(shè)計成收件箱搜索的存儲部分。用戶通過收件箱搜索功能，來完成日常收件箱搜索操作。在Facebook,這意味著系統(tǒng)要能夠應(yīng)對非常高的寫吞吐量，每天會有數(shù)十億的寫請求，這個數(shù)字還在隨著用戶的增長而不停增長。因為Facebook的數(shù)據(jù)中心，分布在不同的地域為用戶提供服務(wù)，因此在IDC之間復(fù)制數(shù)據(jù)，是降低搜索延遲的關(guān)鍵。收件箱搜索在2008年6月上線，當時有1億用戶，到今天(論文發(fā)表時間)，F(xiàn)acebook有2.5億用戶,Cassandra仍舊能夠滿足需求。 Cassandra目前為Facebook的多個服務(wù)提供后端存儲支持。

?

這個論文按照如下結(jié)構(gòu)組織. 第二章描述了相關(guān)的工作，都是在我們的設(shè)計中非常重要的方面。第三章詳細闡述了數(shù)據(jù)結(jié)構(gòu)。第四章簡要介紹了客戶端API。 第五章披露了分布算法和系統(tǒng)設(shè)計細節(jié)。第六章詳細介紹了如何搭建Cassandra系統(tǒng)和系統(tǒng)性能調(diào)優(yōu)。 第六章第一節(jié)介紹了Facebook平臺如何使用Cassandra 。最后第七章總結(jié)了Cassandra的后續(xù)工作。

?

2.相關(guān)工作 RELATED WORK

?

文件系統(tǒng)和數(shù)據(jù)庫社區(qū)，對于通過分布數(shù)據(jù)方式來實現(xiàn)性能，可用性，可靠性，進行了廣泛的研究。不同于P2P存儲系統(tǒng)只能支持扁平的命名空間，分布式文件系統(tǒng)支持層級式的命名空間。像Ficus和Coda，通過復(fù)制文件來達到高可用性，但是與此同時，系統(tǒng)犧牲了一致性。對于更新沖突，一般通過專門的沖突解決程序來處理。Farsite 在未采用任何中心化服務(wù)器的同時，實現(xiàn)了分布式文件系統(tǒng)。Farsite通過復(fù)制技術(shù)，來實現(xiàn)高可用性和可擴展性。 GFS是另外一個分布式存儲系統(tǒng)，用來存儲Google內(nèi)部程序數(shù)據(jù)。 GFS采用了一個簡單的設(shè)計，通過一個Master服務(wù)器來存儲全部的metadata. 客戶的數(shù)據(jù)被切分成數(shù)據(jù)塊，存儲在塊存儲服務(wù)器上。當然現(xiàn)在Google通過Chubby實現(xiàn)了Master服務(wù)器的容災(zāi)。Bayou 是一個分布式的關(guān)系型數(shù)據(jù)庫，允許節(jié)點離線，提供實現(xiàn)最終一致性保證。 在上面這些系統(tǒng)中，Bayou,Coda,Ficus 允許節(jié)點離線操作，系統(tǒng)能夠彈性的處理網(wǎng)絡(luò)分區(qū)和運行中斷。 這些系統(tǒng)在沖突處理的方式上存在差別。比如，Coda 和 Ficus實現(xiàn)系統(tǒng)層面的沖突解決。Bayou允許應(yīng)用程序?qū)用孢M行沖突解決，所有這些系統(tǒng)，都能夠?qū)崿F(xiàn)最終一致性。類似這些系統(tǒng), Dynamo 在發(fā)生網(wǎng)絡(luò)分區(qū)的時候，仍舊允許讀寫操作，然后通過不同的沖突處理機制解決沖突，有一些機制，是客戶端驅(qū)動的。傳統(tǒng)的關(guān)系型數(shù)據(jù)庫的復(fù)制技術(shù)，關(guān)注于確保復(fù)制數(shù)據(jù)的強一致性。雖然強一致性對于應(yīng)用編寫者來說，是個方便的編程模型，但是這些系統(tǒng)因為強一致性的保證，而不能應(yīng)付網(wǎng)絡(luò)分區(qū)的情況。

?

Dynamo是Amazon用來存取購物車的存儲系統(tǒng)。 Dynamo 基于成員算法的 GOSSIP協(xié)議，幫助系統(tǒng)中每個節(jié)點維護其他全部節(jié)點的信息。 可以把Dynamo理解成一個結(jié)構(gòu)化的層，請求最多通過1跳路由達到目的。Dynamo通過時鐘向量圖來檢測更新沖突，優(yōu)先采用客戶端來解決沖突的機制。Dynamo中的寫操作執(zhí)行前，需要一個讀操作來獲取時間戳向量，這個特點，在系統(tǒng)需要高的寫吞吐量的時候，會成為瓶頸。 Bigtable提供結(jié)構(gòu)化和數(shù)據(jù)的分布式，但需要依賴于一個分布式文件系統(tǒng)來實現(xiàn)持續(xù)服務(wù)。

?

3.數(shù)據(jù)模型 DATA MODEL

?

Cassandra中的表，是一個分布式的多維MAP, 通過一個key進行索引。值是一個高度結(jié)構(gòu)化的對象。 表中每一行的key,是一個沒有大小限制的字符串，一般是16-32字節(jié)長度。在每個副本中通過Key對每一行的操作，不管進行多少列得讀寫都能保證原子操作。列，會被分組到SET里面，分組以后得列，被稱為 列族 , 就像BigTable一樣。Cassandra公開了兩種列族類型，簡單列族和超級列族。超級列族可以想象成，列族的嵌套結(jié)構(gòu)。而且，應(yīng)用程序還可以指定超級列族，列族里面的列的排序順序，排序順序可以按照時間，名字。通過時間對列來排序，是為了滿足收件箱搜索這類應(yīng)用開發(fā)出來的。通過Column_family :column形式，來訪問列族里面的列，可以通過Column_family :super_column : column 來訪問超級列族里面的列。

?

我們在Section6.1 會用一個很好的例子，來展示超級列族的抽象能力。 通常，應(yīng)用會使用專有的Cassandra集群作為他們服務(wù)的一部分。 雖然系統(tǒng)支持多表的概念，但是目前所有的部署還都是單表部署。

?

4.API

?

Cassandra API包含下面三個簡單方法。

?

.. insert(table , key , rowMutation)

?

?

?

columnName 可以指向列族中的一個列，一個列族，一個超級列族或者 超級列族中的一列。

?

5.系統(tǒng)架構(gòu) SYSTEM ARCHITECTURE

?

在生產(chǎn)環(huán)境中運行的存儲系統(tǒng)的架構(gòu)是非常復(fù)雜的。除了現(xiàn)行的數(shù)據(jù)存儲組件以外，系統(tǒng)還需要滿足如下要求。具有足夠健壯性和擴展性來支持負載均衡，節(jié)點間關(guān)系維護和故障檢測，故障恢復(fù)，同步復(fù)制，過載處理，狀態(tài)傳輸，并發(fā)和任務(wù)調(diào)度，請求封裝，請求路由，系統(tǒng)監(jiān)控，配置管理。詳細的介紹這些解決方案超出了本文的范圍，因此我們在本文介紹Cassandra中分布式存儲的核心技術(shù): 分區(qū)，復(fù)制，節(jié)點關(guān)系，失效處理和擴容。這些模塊協(xié)同工作，處理讀寫請求。一般來講，對于一個key的讀寫請求，會路由到Cassandra集群的某個具體節(jié)點上面。這個節(jié)點，能夠決定請求的副本節(jié)點。對于寫來說，系統(tǒng)將請求路由到副本上面，等待最少的副本節(jié)點【編輯:最少的副本節(jié)點，既能維持系統(tǒng)一致性的最低的副本的數(shù)量】完成寫請求。對于讀請求，根據(jù)客戶端對于一致性的要求，系統(tǒng)或者將請求路由到最近的副本節(jié)點，或者路由到所有的節(jié)點，等待有效的節(jié)點返回結(jié)果。

?

5.1分區(qū) Partitioning

?

Cassandra的一個關(guān)鍵特性，是可以規(guī)模擴容。這就要求，系統(tǒng)能夠動態(tài)在節(jié)點之間分割數(shù)據(jù)。Cassandra通過一致性的有序哈希算法，來分割數(shù)據(jù)。一致性的哈希函數(shù)中，輸出的值域，在一個固定的環(huán)形空間中（哈希的最大值 緊鄰著哈希的最小值）。在系統(tǒng)中，每個節(jié)點都會被隨機分配一個值，用來標定它在環(huán)中的位置。通過哈希數(shù)據(jù)的key，來定位數(shù)據(jù)所在節(jié)點的位置。然后按照順時針的循序，從數(shù)據(jù)節(jié)點的位置開始，找到第一個編號大于數(shù)據(jù)節(jié)點編號的節(jié)點。這個節(jié)點就是這個key的調(diào)度節(jié)點。應(yīng)用程序指定這個key，然后Cassandra通過這個key來路由請求。因此，每個節(jié)點都對 環(huán)中他和他的前任節(jié)點之間的區(qū)域負責。一致性哈希規(guī)則的好處就是，一旦有新的節(jié)點加入，或者有節(jié)點離線退出，那么受影響的就是節(jié)點相鄰的節(jié)點，其他的節(jié)點不受影響。基本的一致性哈希算法存在一些問題。第一，隨機的分配節(jié)點的位置，會導(dǎo)致數(shù)據(jù)和節(jié)點負載的不均衡。第二，基本算法沒有考慮到節(jié)點之間的性能差異。目前有兩種方案解決這些問題，第一，像dynamo一樣，為每個節(jié)點在環(huán)中分配多個位置。第二，分析環(huán)的負載情況，將負載較輕的節(jié)點，移動到負載較重的節(jié)點附近。Cassandra采用第二種方案，這種方案設(shè)計和實施上，都有非常好的可追蹤性，另外在做負載均衡時，可以提供非常有效的決策數(shù)據(jù)。

?

5.2復(fù)制 Replication

?

Cassandra通過復(fù)制技術(shù)，來實現(xiàn)高可用性和持續(xù)服務(wù)能力。 每個數(shù)據(jù)項目都會在N個機器上做復(fù)制, N被稱為復(fù)制因子，通過參數(shù)per-instance來配置。每個key都會賦值給調(diào)度節(jié)點k，調(diào)度節(jié)點負責在他的控制范圍內(nèi)的節(jié)點的數(shù)據(jù)復(fù)制工作。除了在調(diào)度節(jié)點控制范圍之內(nèi)復(fù)制數(shù)據(jù)項目以外，調(diào)度節(jié)點還會在環(huán)中N-1節(jié)點做數(shù)據(jù)復(fù)制工作。Cassandra允許客戶端控制如何復(fù)制數(shù)據(jù)。Cassandra提供了一些復(fù)制策略給客戶端，比如 “RackUnaware” “Rack Aware” (在一個數(shù)據(jù)中心內(nèi)) 以及 “Datacenter?Aware” .應(yīng)用程序通過復(fù)制策略來選擇副本。如果應(yīng)用程序端選擇了”Rack Unaware”策略，那么系統(tǒng)會選擇調(diào)度節(jié)點的N-1個后續(xù)節(jié)點，作為副本節(jié)點。對于”Rack Aware” 和 “Datacenter Aware” 策略算法上會復(fù)雜一些。Cassandra將會向Zookeeper做一次系統(tǒng)請求，獲取一個領(lǐng)袖節(jié)點。在每個節(jié)點加入集群時候，都會向領(lǐng)袖節(jié)點去查詢副本節(jié)點的覆蓋范圍，領(lǐng)袖節(jié)點能夠確保，環(huán)中的每個節(jié)點的副本節(jié)點數(shù)量，不超過N-1. 每個節(jié)點都會本地緩存一份關(guān)于節(jié)點覆蓋范圍的meta數(shù)據(jù)信息，同時考慮到容災(zāi)的需求，在ZooKeeper上面也會存儲一份。這樣當節(jié)點崩潰時候，就會有關(guān)于這個節(jié)點覆蓋范圍的備份信息存在。我們借用Dynamo parlance系統(tǒng)中的概念，將負責節(jié)點的覆蓋范圍，視為優(yōu)先的覆蓋范圍。

?

????在5.1已經(jīng)談到，每個節(jié)點都會關(guān)注系統(tǒng)中其他的節(jié)點，當然也會關(guān)注節(jié)點覆蓋范圍之

?

內(nèi)的節(jié)點。Cassandra在節(jié)點失效，節(jié)點間網(wǎng)絡(luò)中斷的情況下，通過降低對Quorum的要求，提供了持續(xù)服務(wù)的保證。 數(shù)據(jù)中心在電力中斷，網(wǎng)絡(luò)中斷，冷卻系統(tǒng)故障，或者自然災(zāi)害等情況下，都會失效。Cassandra可以配置成每一行多個數(shù)據(jù)中心都有副本。實際上，一個KEY的優(yōu)先覆蓋范圍列表在構(gòu)建的時候，會考慮到存儲節(jié)點跨越多個數(shù)據(jù)中心的情況。這些數(shù)據(jù)中心通過高速專線網(wǎng)絡(luò)相連。通過跨越數(shù)據(jù)中心的復(fù)制方案，我們可以處理任何數(shù)據(jù)中心的問題。

?

5.3節(jié)點關(guān)系 (Membership)

?

Cassandra中集群的節(jié)點關(guān)系依賴Scuttlebutt, Scuttlebutt基于高效的反熵GOSSIP協(xié)議。Scuttlebutt最突出的特征，是他具有高效的CPU，gossip通道利用率。在Cassandra系統(tǒng)中，Gossip協(xié)議不僅用來做節(jié)點關(guān)系管理，也用來傳輸系統(tǒng)相關(guān)的控制狀態(tài)。

?

5.3.1Failure Detection

?

失效檢測，是一種機制，通過它節(jié)點可以獲取其他節(jié)點是不是在正常工作。在Cassandra中，失效檢測還用來避免節(jié)點在一些操作中，同一些不可到達節(jié)點的通訊。 Cassandra采用修改過的Accrual Failure Detector. Accrual 模塊不會返回一個Boolean值來標識節(jié)點是工作還是宕機狀態(tài)，相反，這個模塊會返回每個受監(jiān)控節(jié)點的一個評估的等級，用Φ來表示，這樣做的目的是Φ實際表示的一個范圍，這個范圍可以動態(tài)調(diào)整以反映被監(jiān)控節(jié)點的網(wǎng)絡(luò)和負載情況。

?

下面具體解釋一下 Φ 的含義: 給定一個 Φ 的臨界值，然后假定我們在 Φ=1的時候，認為A節(jié)點有問題，我們這個猜測的錯誤（我們的結(jié)論，可能被心跳線等其他的狀態(tài)信息所推翻）概率為10% ，那么當Φ=2的時候，我們猜錯的概率只有1% ，在Φ=3的時候，我們猜錯的概率為0.1% … 在系統(tǒng)中每個節(jié)點都維護著一個其他節(jié)點發(fā)出的gossip消息的內(nèi)部到達時間的滑動窗口， 系統(tǒng)會計算這些到達時間的分布，然后計算Φ的值。盡管原始的論文中建議通過高斯分布來擬合數(shù)據(jù)，但是我們發(fā)現(xiàn)根據(jù)gossip 通道的特點和他對于延遲的影響，指數(shù)分布會有更高的擬合精度。據(jù)我們所知，我們是最先采用上述方式來使用基于gossip 的 Accrual Failure Detection。 Accrual Failure Detectors 在速度和精度上都表現(xiàn)良好，經(jīng)調(diào)整，在網(wǎng)絡(luò)狀況和服務(wù)器負載情況檢查上，也有尚佳表現(xiàn)。

?

5.4啟動 Bootstrapping

當一個節(jié)點最先加入到集群中時，系統(tǒng)會給他在環(huán)中，隨機分配一個位置。考慮到容災(zāi)需求，這個映射關(guān)系會在節(jié)點本地和Zookeeper中，都做存儲。然后系統(tǒng)會在集群中通過gossip協(xié)議廣播這個位置信息。然后環(huán)中所有的節(jié)點，都知道了這個信息。這就保證了任何節(jié)點都能將key路由到其他正確的節(jié)點上面。當一個節(jié)點準備加入到集群的時候，他會讀一個配置文件，配置文件中包含一些集群中可以聯(lián)系的節(jié)點。我們將這些初始的聯(lián)系節(jié)點，稱之為集群種子。集群種子也可以通過Zookeeper配置服務(wù)來提供。

?

Facebook的環(huán)境中，節(jié)點離線(因為失效或者維護任務(wù))經(jīng)常瞬間完成，但是也可能持續(xù)一段時間。失效可以以多種形態(tài)出現(xiàn)，比如磁盤錯誤，CPU損壞。一般節(jié)點都是臨時離線，因此不需要數(shù)據(jù)的從新分布或者修復(fù)不可達的副本。相似的，因為不小心啟動了一個新的Cassandra節(jié)點，會導(dǎo)致人為的錯誤，這會讓在每個Cassandra實例中的每個消息中，都會包括節(jié)點的名字。假如一個人為的配置錯誤讓一個節(jié)點加入了錯誤的Cassandra實例中，會導(dǎo)致集群名字失效。因為這些原因，因此需要一種明確的機制，來向Cassandra實例中增加或者移除節(jié)點。管理員可以通過命令行工具或者瀏覽器連接到Cassandra節(jié)點上面，進行節(jié)點的增加與刪除操作。

?

5.5集群擴容 (Scaling the Cluster )

?

當一個新的節(jié)點加入到系統(tǒng)中的時候，系統(tǒng)在環(huán)中為他分配一個位置，這樣他就可以緩解一些節(jié)點的過重的負擔。新的節(jié)點會承擔一些其他節(jié)點的職能。不管是通過命令行還是web界面增加節(jié)點，系統(tǒng)都會執(zhí)行初始化算法。其他的節(jié)點會通過內(nèi)存拷貝技術(shù)，將數(shù)據(jù)傳輸?shù)叫碌墓?jié)點。根據(jù)運維經(jīng)驗，單節(jié)點數(shù)據(jù)傳輸速度能達到40M/s。我們目前在研究類似于Bittorrent多副本傳輸技術(shù)，通過多個副本給上線節(jié)點傳輸數(shù)據(jù)，從而加快節(jié)點啟動過程。

?

????5.6本地持久化 (Local Persistence)

?

Cassandra系統(tǒng)依賴本地文件系統(tǒng)做數(shù)據(jù)持久化。存儲結(jié)構(gòu)為了更有效的獲取數(shù)據(jù)而設(shè)計。一般寫操作包括兩個步驟，先寫到提交日志里面，這樣可以保證系統(tǒng)持續(xù)服務(wù)和系統(tǒng)故障時候，數(shù)據(jù)可以恢復(fù)。系統(tǒng)會在提交日志文件成功之后，在更新內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)。在每個節(jié)點上面，為了達到最高的數(shù)據(jù)吞吐量，都會采用一塊獨立的硬盤寫數(shù)據(jù)提交日志。當發(fā)現(xiàn)內(nèi)存中對象數(shù)目和數(shù)據(jù)大小達到一定的閥值的時候，數(shù)據(jù)會被dump到磁盤上面。節(jié)點都會安裝多塊普通硬盤，每次寫操作，會寫到一塊指定硬盤。所有的寫操作都順序進行，并且會建立基于ROW KEY的索引，以便于快速查找。這些回寫的索引，會像數(shù)據(jù)文件一樣存儲。當這種類型的文件多到一定程度，在后臺會啟動一個合并進程，將這些文件合并成一個文件。在BigTable中也有類似的合并操作。

?

一個典型的讀操作，會先在內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)做查找，如果內(nèi)存未命中，再去做文件系統(tǒng)查找。做文件查找的時候，會按照由新到老的順序。在做磁盤文件系統(tǒng)查找的時候，我們判斷key是否在一些文件中存在。為了加快效率，如果一個文件沒有包含key，那么系統(tǒng)就不會掃描這個文件。為此，對于每個文件的所包含的key信息，做摘要，然后寫到內(nèi)存里面，先采用布隆過濾器直接過濾內(nèi)存。如果一個key指向了一個含有多個列的列族，那么我在做基于這個key的讀取操作的時候，還需要額外的索引機制來獲取列，這時單純的key索引已經(jīng)不能滿足需求。為了防止掃描磁盤上每個列，我們維護了一個列的索引，這樣我們可以直接去磁盤的指定塊獲取這個列數(shù)據(jù)。因為key索引的列 會序列化到磁盤上面，所以我們以256k為一塊， 這個值也可以配置，不過我們發(fā)現(xiàn)對于生產(chǎn)環(huán)境的負載，256k已經(jīng)能夠滿足需求。

?

5.7實現(xiàn)細節(jié) (Implementation Details)

?

單機Cassandra進程，由以下部分組成： 分區(qū)模塊，集群節(jié)點關(guān)系管理和失效檢測模塊，存儲引擎模塊。 這些模塊依賴于事件驅(qū)動，消息處理管道和任務(wù)管道依據(jù)SEDA的架構(gòu)原則，切分成多個Stage. 這些模塊都由JAVA編寫。集群節(jié)點關(guān)系管理和失效檢測模塊構(gòu)建在網(wǎng)絡(luò)層之上，采用非阻塞I/O.所有的系統(tǒng)控制消息基于UDP協(xié)議傳輸，所有的應(yīng)用程序相關(guān)的消息，比如復(fù)制和請求路由，基于TCP協(xié)議傳輸。請求路由模塊，通過一個狀態(tài)機實現(xiàn)。當一個讀寫請求到達集群中的一個節(jié)點時，狀態(tài)機會在如下狀態(tài)間切換 (i) 確認這個擁有這個key數(shù)據(jù)的節(jié)點 (ii) 將請求路由到這些節(jié)點，并且等待請求到達的回復(fù)。(iii)如在請求在指定的超時時間內(nèi)，沒有回復(fù),那么將這個請求設(shè)定成失敗，并且返回客戶端 (iv)根據(jù)返回的時間戳，找出最新的響應(yīng)。(v) 如果發(fā)現(xiàn)有副本中的數(shù)據(jù)不是最新的，那么安排一個數(shù)據(jù)修復(fù)操作。本文不詳細討論失效處理的場景。系統(tǒng)可以配置成同步寫，也可以配置成異步復(fù)制。對于需要高吞吐量的系統(tǒng)，我們會配置成異步寫，這種系統(tǒng)一般為寫密集型。對于同步復(fù)制的系統(tǒng)，在我們給客戶端返回之前，我們要等待響應(yīng)的節(jié)點數(shù)量達到一個最低有效值。

?

在任何日志型文件系統(tǒng)里面，都需要一種機制，來清理提交日志。當老的日志超過一定的尺寸的時候，會自動開啟一個新的日志文件。 日志輪詢的尺寸，可以配置，我們經(jīng)驗是在生產(chǎn)環(huán)境中，日志文件保持在128M，是個不錯的選擇。每一條提交日志，都有一個位向量組成的頭，這個頭固定大小，但是能夠容納系統(tǒng)所能處理的列族的最大數(shù)目。在我們的實現(xiàn)中，每生成一個列族，在內(nèi)存和文件系統(tǒng)都會生成一份數(shù)據(jù)結(jié)構(gòu)。每次內(nèi)存中一個特定列族的數(shù)據(jù)結(jié)構(gòu)成功回寫到磁盤的時候，我們更改提交日志的頭，將這個列族對應(yīng)的位向量置位，這標志著這片信息被成功提交。每一條提交日志都會有位向量，位向量在內(nèi)存中維護。當日志文件需要做輪詢的時候，系統(tǒng)會做位向量的對比，如果當發(fā)現(xiàn)所有的數(shù)據(jù)都已經(jīng)被持久化到磁盤上面，那么老的日志文件會被刪除。寫提交日志的操作，可以采用普通模式或者快速同步模式。在快速同步模式下寫日志，系統(tǒng)會先緩沖寫請求。這樣做如果機器宕機，會有丟失數(shù)據(jù)的風險。Cassandra在做內(nèi)存數(shù)據(jù)回寫的時候，仍舊采用緩沖的方式持久化數(shù)據(jù)。傳統(tǒng)的數(shù)據(jù)庫不是為了高寫吞吐量設(shè)計的，Cassandra將所有的寫請求順序的寫入磁盤，以達到最高的寫吞吐量。因為文件回寫磁盤的時候是順序進行的，因此不存在互斥問題，當讀的時候也不需要鎖。Cassandra對于讀寫，都是無鎖狀態(tài)，因此不需要處理基于B-TREE數(shù)據(jù)庫的并發(fā)問題。

?

Cassandra根據(jù)主鍵索引所有的數(shù)據(jù)。磁盤中的數(shù)據(jù)文件被打碎成一些列的塊，每塊最多含有128個key,塊之間通過塊索引分割開來。塊索引中包括key的偏移量和key對應(yīng)的數(shù)據(jù)的大小。當內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)回寫硬盤的時候，會生成塊索引，他們的偏移量會寫以獨立索引的形式寫到獨立的硬盤上面。為了訪問速度，這個索引也會在內(nèi)存中存一份。一般讀操作都會先在內(nèi)存中查找數(shù)據(jù)結(jié)構(gòu)。如果在內(nèi)存中命中，那么直接返回客戶端，因為內(nèi)存中總是存儲最新的數(shù)據(jù)。如果基于內(nèi)存的查找失敗，那么在文件系統(tǒng)按照時間倒序做查找。因為我們最常查找最新的數(shù)據(jù)，因此我們?nèi)绻谧钚碌臄?shù)據(jù)文件中發(fā)現(xiàn)命中，那么直接返回數(shù)據(jù)。隨著時間的推移，硬盤上面文件會越來越多。然后我們會像Big Table一樣啟動一個文件合并進程，將多個文件合并成一個。一般合并的文件，都是有序的，因此合并的文件尺寸會比較相近，比如不能將一個100G的文件同一個小于50G的文件合并。一個合并進程，會定時的將相關(guān)的文件合并成一個大文件。合并操作會是I/O密集型，因此為了不影響讀，系統(tǒng)會采取很多優(yōu)化措施。

?

6.實踐經(jīng)驗 (PRACTIAL EXPERIENCES )

?

在設(shè)計，實現(xiàn)，維護Cassandra過程中，我們收獲了很多。最重要的經(jīng)驗就是，如果沒有了解到應(yīng)用端對新特性的使用造成的影響，那么最好不要增加這個新特性。大部分問題不是因為節(jié)點崩潰或者網(wǎng)絡(luò)分割引起的。 下面我們分享一下這些問題場景。

?

• 在Inbox Search 上線以前，我們有1億用戶，需要索引的數(shù)據(jù)有7Tb ，然后將索 引存儲在Mysql里面，加載到Cassandra中。整個過程包擴在Mysql數(shù)據(jù)上面運行Map/Reduce 任務(wù)，索引他們，然后在Cassandra中存儲反向索引信息。M/R 處理過程，作為Cassandra的一個客戶端來執(zhí)行。我們暴露了給M/R過程一些后端通道，將每個用戶的倒排索引信息聚合起來，序列化，發(fā)送給Cassandra進程。這種工作方式系統(tǒng)的唯一瓶頸是網(wǎng)絡(luò)帶寬。
• 多數(shù)的應(yīng)用程序，要求在副本進行上面Key操作為原子操作。 當然有些應(yīng)用對于事物的要求，主要是為了維護一些二級指標。多數(shù)RDBMS’s 開發(fā)這都會覺得這是個有用的特性。我們在努力建立一種機制，實現(xiàn)這些原子操作。
• 我們也測試了其他的失效檢測器，比如在附錄【15】，【5】中列出的方案。我們發(fā)現(xiàn)，隨著節(jié)點規(guī)模的擴大，失效檢測時間很快超出了可以接受的范圍，在一個實驗中，集群有100個基點，檢測出一個失效節(jié)點，花費了2分鐘，這個時間對我們來講完全不可接受。最后測試Accrual failure detector 時候，將PHI保守的設(shè)定為5，100個節(jié)點的集群，平均失效檢測時間在15秒左右。
• 監(jiān)控是不能想當然來做的。Cassandra 內(nèi)置了分布式性能監(jiān)控工具 Ganglia .我們?yōu)镚anglia提供了多樣的系統(tǒng)級別監(jiān)控指標，方便我們更好的了解在生產(chǎn)環(huán)境的負載情況下，我們的系統(tǒng)表現(xiàn)。 當硬盤突然失效的時候，會觸發(fā)節(jié)點啟動算法進行節(jié)點修復(fù)。
• 盡管Cassandra是個完全去中心化的系統(tǒng)，但是我們在實現(xiàn)某寫分布式功能的時候，發(fā)現(xiàn)設(shè)置一些協(xié)調(diào)節(jié)點，能夠讓我們更容易的駕馭系統(tǒng)。比如Cassandra設(shè)置了Zookeeper ，在規(guī)模的集群中做協(xié)調(diào)調(diào)度工作。我們的目標是把Cassandra中同存儲無關(guān)的功能，都整合到Zookeeper上面。

?

6.1Facebook 收件箱搜索 (Index Search)

?

在Facebook的收件箱搜索中，所有的發(fā)送，接收消息，都按照用戶做了索引，每個用戶一份。目前搜索支持兩種方式(a) term search (b) 交互式搜索 – 給定一個人的名字，返回這個人所有收發(fā)的消息。對于(a)查詢，用戶id是key，消息存放在超級列里面，每個包含關(guān)鍵詞的消息標識存在列里面。對于(b)查詢，用戶id仍舊是key,收件人的id是超級列族。對于每個超級列族，每個消息的標識都放到列里面。為了加速搜索過程，Cassandra提供了智能緩存機制。比如當一個用戶點擊搜索條的時候，一個異步的消息發(fā)送到Cassandra集群，集群根據(jù)這個消息準備一份這個用戶的索引放到cache里面。這樣當用戶開始搜索的時候，搜索結(jié)果很可能已經(jīng)在內(nèi)存里面了。收件箱搜索系統(tǒng)目前運行在150個節(jié)點的集群上面，數(shù)據(jù)量50+TB。 集群節(jié)點分布在美國東海岸和西海岸的數(shù)據(jù)中心。下面的圖是一些生產(chǎn)環(huán)境的性能數(shù)據(jù)。

?

Latency Stat

?

Search Interactions

?

Term Search

?

Min

?

7.69ms

?

7.78ms

?

Median

?

15.69ms

?

18.27ms

?

Max

?

26.13ms

?

44.41ms

?

7.結(jié)論 CONLUSION

?

我們設(shè)計，實施，運營了一個能夠提供擴展性，高性能，廣泛適用的存儲系統(tǒng)。Cassandra可以在提供非常高的數(shù)據(jù)更新吞吐量時候保持低延時。未來的工作，會增加壓縮，多個key的原子操作和 二級索引支持。

?

8.致謝 ACKNOWLEDGEMENTS

?

Cassandra 從內(nèi)部員工那里得到了很多改進反饋。在第一次部署的時候，KarthikRanganathan 索引了所有Mysql的數(shù)據(jù)，并且?guī)臀覀冞w移到Cassandra里面。 另外感謝EPFL的Dan Dumitriu 的有很多價值建議。

轉(zhuǎn)自： http://blog.sina.com.cn/s/blog_502c8cc40100p860.html

Cassandra -去中心化的結(jié)構(gòu)化存儲系統(tǒng) - 轉(zhuǎn)