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

?

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

?

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

?

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

?

1.介紹 INCRODUCTION

?

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

?

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

?

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

?

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

?

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

?

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

?

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

?

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

?

我們?cè)赟ection6.1 會(huì)用一個(gè)很好的例子，來(lái)展示超級(jí)列族的抽象能力。 通常，應(yīng)用會(huì)使用專(zhuān)有的Cassandra集群作為他們服務(wù)的一部分。 雖然系統(tǒng)支持多表的概念，但是目前所有的部署還都是單表部署。

?

4.API

?

Cassandra API包含下面三個(gè)簡(jiǎn)單方法。

?

.. insert(table , key , rowMutation)

?

?

?

columnName 可以指向列族中的一個(gè)列，一個(gè)列族，一個(gè)超級(jí)列族或者 超級(jí)列族中的一列。

?

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

?

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

?

5.1分區(qū) Partitioning

?

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

?

5.2復(fù)制 Replication

?

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

?

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

?

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

?

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

?

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

?

5.3.1Failure Detection

?

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

?

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

?

5.4啟動(dòng) Bootstrapping

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

?

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

?

5.5集群擴(kuò)容 (Scaling the Cluster )

?

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

?

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

?

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

?

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

?

5.7實(shí)現(xiàn)細(xì)節(jié) (Implementation Details)

?

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

?

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

?

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

?

6.實(shí)踐經(jīng)驗(yàn) (PRACTIAL EXPERIENCES )

?

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

?

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

?

6.1Facebook 收件箱搜索 (Index Search)

?

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

?

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

?

8.致謝 ACKNOWLEDGEMENTS

?

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

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

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