聚會時間公告: 因應COSCUP 2011, Kalug 8月份休會一次

七月 5, 2010
» [雲端計算] Cassandra 應用實例[轉譯]

本篇同樣是篇老魚轉譯而來的相關系列文選, 但老魚除了校譯和排版外, 加上了個人實作過程中的理解說明混於其中, 建議您閱讀本文前, 應當俱備的知識範圍:
  1. 曾玩過 Twitter 介面操作的經驗.
  2. 對 Cassandra 的基本管理與操作能力, 已對其 Data Model 有著初級理解, 當然相關的組態配置檔的位置和編輯能力是要俱備地.
  3. 對關聯型資料庫系統開發與 E-R Model 初步的應用經驗.
  4. 對程式設計能力有熱愛的研究精神.

如果您有輿趣, 可別錯過了本篇原文網址的討論串與後續原作者的新文章. 老魚希望有心的您可以好好的閱讀它, 當然如果能配合實裝 Cassandra 與裝載本實例的教材, 您將更加瞭解它. 世上沒有完美的IT系統, 但它可使您精進學習IT甚至突破創新!老魚一慣的習性用“紅筆字”, 劃上了自己認為的閱讀重點, 供各位參考, 看完本篇如果您有興趣深入, 可以再閱讀老魚先前 Blog 所整理的相關文章(按學習順序排列):

原文: http://www.rackspacecloud.com/blog/2010/05/12/cassandra-by-example/# 
原作者:Eric Evan, http://blog.sym-link.com/
原文發佈日期:May 12, 2010
簡體中文譯者:王旭
http://wangxu.me/blog/ , @gnawux), http://wangxu.me/blog/?p=383
翻譯時間:2010年5月15,25,26日
正體中文校譯:郭朝益, http://oss-tw.blogspot.com/

[雲端計算] Cassandra 應用實例[轉譯]

近來 Cassandra 備受矚目,很多人正在評估是否可以應用 Cassandra。由於這群人有著更積極的求知速度,相對的,我們的開發專案所提供的說明文檔就顯的過於粗淺了。在這些文檔中,最不足的是為有關聯型資料庫基礎的人解釋有關 Cassandra 資料模型的部份。

Cassandra 資料模型實際和傳統的資料庫差異非常大,足夠讓人眩暈,而且很多誤解都需要修正。有些人把這個資料模型描述成存放 map 的 map,或對於 super column 的應用場景,視為是存放 map 的 map 的 map。這些解釋經常用類似 JSON 標記的視覺輔助展示方法來進行佐證。其他人則把列族(column family, cf)看做是係數表,還有人把 column family 看作是存放列物件的集合容器。甚至有人有時把列(column)看成是三元組。我覺得所有這些解釋都不夠好。

問題在於很難去用推類比擬的手法來確切解釋一個新的東西,而且如果比較的不準確的話常常把人搞糊塗。我仍然期望有人能解釋清楚這個資料模型,但同時我覺得確切的例子可能更容易說明白一些。

Twitter


儘管 Twitter 本身就是 Cassandra 的一個實際的應用場景,它仍然是一個不錯的教學實例,因為它眾所周知而且易於抽象。在例子中,和很多網站一樣,每個使用者都有一份使用者資料(顯示名稱、密碼、email等),這些資訊鏈接到朋友(譯註:使用者 follow 的人)和 follower(譯註:follow使用者的人)。此外,如果沒有那些短 tweets 的話也就不是 twitter 了,tweet 每條 140 個字符,它們都關聯著諸如時間戳記和唯一的 id 等諸如此的元資料,這個 id 我們可以從 URL 裡看到。

現在我們在一個關聯資料庫裡來直接進行建模,我們首先需要一個表來存放使用者。
CREATE TABLE user (
id INTEGER PRIMARY KEY,
username VARCHAR(64),
password VARCHAR(64)
);

我們還需要兩張表來存儲一對多的 follow 關聯。
CREATE TABLE followers (
user INTEGER REFERENCES user(id),
follower INTEGER REFERENCES user(id)
);
 
CREATE TABLE following (
user INTEGER REFERENCES user(id),
followed INTEGER REFERENCES user(id)
);

顯然,我們還需要表來存儲 tweets。
CREATE TABLE tweets (
id INTEGER,
user INTEGER REFERENCES user(id),
body VARCHAR(140),
timestamp TIMESTAMP
);
由於僅僅是個例子,我已經極大簡化了情況,但僅僅是這個極度簡化的模型,也還有很多需要做的工作。例如,要以可行的方法達到資料歸一化就需要一個外部鍵(FK)值的約束限制,而因為我們需要從多張表 join 資訊,我們需要對任意值建索引,以保證其高效。

但是讓一個分散式系統正常工作相當有挑戰性,幾乎不可能不做任何折衷。對 Cassandra 來說也是如此,而且這也是為什麼上述資料模型對我們來說是無法工作的的原因。對於入門者,沒有可供參考的完整性,缺乏次索引使得 join 很難進行,所以,你必須反歸一化。另一方面,你被迫思考你要進行的查詢的方式和期望結果,因為這差不多就是資料模型看起來的樣子。

Twissandra


那麼如何把上述模型翻譯到 Cassandra 中呢?十分幸運,我們只需要看看 Twissandra,這是 Eric Florenzano 寫的一個 Twitter 的簡化版克隆版,來作為例子。那麼讓我們來使用 Twitter 和 Twissandra 作為例子來看看 Cassandra 的資料模型是如何地。

程式範例下載(Git, Python 要求)
git clone git://github.com/ericflo/twissandra.git

Schema (架構網要)

Cassandra 是一種無 schema 的資料存儲方式,但為你的應用做一些特定的組態配置還是必的。Twissandra 給出了一個可以工作的 Cassandra 組態配置,不過研究一下關於資料模型方面的組態配置還是物超所值的。
Keyspaces (鍵值空間)
Keyspaces 是 Cassandra 中最頂層的命名空間。在未來版本的 Cassandra 中,將可以動態創建 keyspace,正如在 RDBMS 中創建資料庫一樣,但是對於 0.6 和以前的版本,這些都在主要組態配置檔中定義,如:

 <Keyspaces>
<Keyspace Name="Twissandra">
...
Keyspace>
Keyspaces>




Column Families, CF (列族)
對於每個 keyspace,都可以有一個或多個列族(column family, cf)。column family 是用於關聯類型相近的記錄的命名空間。Cassandra 在寫入作業時,在一個 column family 內部允許有記錄(record)級的原子性,對它們進行查詢非常高效。這些特性十分重要,在進行你的資料建模前必須記牢,其它細節我們會在下面討論到。和 keyspace 類似,列族也在主要組態配置文件中定義,雖然在將來的版本中你將可以在系統運行期間就可創建列族,正像在RDBMS 中創建資料表一樣。

<Keyspaces>
<Keyspace Name="Twissandra">
<ColumnFamily CompareWith="UTF8Type" Name="User"/>
<ColumnFamily CompareWith="BytesType" Name="Username"/>
<ColumnFamily CompareWith="BytesType" Name="Friends"/>
<ColumnFamily CompareWith="BytesType" Name="Followers"/>
<ColumnFamily CompareWith="UTF8Type" Name="Tweet"/>
<ColumnFamily CompareWith="LongType" Name="Userline"/>
<ColumnFamily CompareWith="LongType" Name="Timeline"/>
Keyspace>
Keyspaces>

需要指出的是,上面的組態配置片段中,指定名字的時候同時指定了一個比較者類型。這凸顯了 Cassandra 和傳統資料庫的又一個重大不同,記錄按照設計的順序存儲,在之後不能輕易改變。
這些列族(CF)都是什麼?
一下子看到所有的七個 Twissandra 列族(column family, cf)是做何用途地可能不那麼直觀,所以,我們來逐個仔細看一下:
  • User
    • User 用於儲存使用者資訊,大致相當於本文最上面描述的使用者資料表。cf 中的每條記錄以UUID 為鍵(key)值,並且包含使用者名稱和密碼列。
  • Username
    • 在 User 列族中查詢一個使用者需要知道使用者的鍵值,但從使用者名稱怎麼找到這個 UUID 鍵值呢?在上面描述的 SQL 關聯式資料庫裡的話,我們就在 User 表裡來一個匹配使用者名的SELECT 語句(WHERE username = 'jericevans')就行了。但這對於 Cassandra 來說卻不可能。
    • 首先,關聯式資料庫可以順序地掃瞄全表來進行這樣一個 SELECT,但由於記錄是基於鍵值分佈在 Cassandra 叢集中的,這個匹配將可能會在多個節點上進行,可能是很多節點。而且,即使是資料就在一個節點上,仍然有一個原因會讓這一作業遠沒有關聯式資料庫效率高,因為關聯式資料庫可以對 username 列有索引(index)。前面提到過,Cassandra 在當前是不支持第二索引的。
    • 解決方案就是:建立一個我們自己的反向索引,進行使用者名稱到 UUID 鍵值的映射,這就是Username CF 的用途。
  • Friends
  • Followers
    • Friends 和 Follower CF 可以回答這些問題:使用者X follow 了哪些人? 誰 follow 了使用者X? 這兩個 CF 的鍵值都是這個唯一的使用者 ID,其中包含了哪些有 follow 關聯的使用者以及它們創建的時間。
  • Tweet
    • Tweet CF 用於存放所有的 tweets。這個列族以每個 tweet 的 UUID 為鍵值,還包含了使用者id,tweet 內容以及 tweet 時間等有關的列。
  • Userline
    • 這是屬於每個使用者的時間軸線。記錄的鍵值是使用者的 ID,其他的列中,包含有一個數字時間戳記到 Tweet CF 中的 tweet ID 的映射(map)。
  • Timeline
    • 最後,Timeline CF 類似於 Userline,只是這裡存儲著每個使用者的朋友的 tweet 的時間軸線視圖(View)。
有了上面這些 CF,現在我們可以來看一些常用的作業都是如何發生的。

把這些列族(CF)放在一起來試一下

添加一個新使用者
首先,新使用者需要一個方法來註冊一個帳戶,當他們註冊的時候,組要將他們增加到 Cassandra 資料庫中去。對於 Twissandra,我們來看看裡面的內容:(Client 實作以 Python - Pycassa 為例)

username = 'jericevans'
password = '**********'
useruuid = str(uuid())
 
columns = {'id': useruuid, 'username': username, 'password': password}
 
USER.insert(useruuid, columns)
USERNAME.insert(username, {'id': useruuid})

Twissandra 是用 Python 寫成的,使用 Pycassa 作為存取 Cassandra 的客戶端,上述大寫的 USER 和 USERNAME 是 pycassa.ColumnFamily 的實例,它們需要在使用之前的某個位置被分別初始化。

這裡說明一下,這不是從 Twissandra 裡原樣摘出來的。我讓他們更加簡單而且是自包含的。比如,在上面的例子中,如果沒有對使用者名和密碼的賦值的話,可能不那麼好理解,不過一個 web 應用只能從使用者註冊表單裡得到這些內容。

從這個例子中回來,有兩個不同的 Cassandra 寫入作業“insert( )”,第一個創建了一個使用者 CF,另一個更新了使用者名到使用者 UUID 鍵值的反向映射(map)表。在兩個例子中,參數都是用於查找記錄的鍵值,以及包含列名和值的 map。
Following 一個朋友
frienduuid = 'a4a70900-24e1-11df-8924-001ff3591711'
 
FRIENDS.insert(useruuid, {frienduuid: time.time()})
FOLLOWERS.insert(frienduuid, {useruuid: time.time()})

這裡我們再來兩個不同的 insert() 作業,這次是加入一個使用者到我們的朋友列表,並加入反向關聯:給被 follow 使用者增加一個 follower。
發出 Tweet
tweetuuid = str(uuid())
body = '@ericflo thanks for Twissandra, it helps!'
timestamp = long(time.time() * 1e6)
 
columns = {'id': tweetuuid, 'user_id': useruuid, 'body': body, '_ts': timestamp}
TWEET.insert(tweetuuid, columns)
 
columns = {struct.pack('>d'), timestamp: tweetuuid}
USERLINE.insert(useruuid, columns)
 
TIMELINE.insert(useruuid, columns)
for otheruuid in FOLLOWERS.get(useruuid, 5000):
TIMELINE.insert(otheruuid, columns)

要存儲一條新的 tweet,我們需要使用一個新的 UUID 作為鍵值,在 Tweet 列族創建一個記錄,其中的列包含作者的使用者 ID,創建的時間,當然還有 tweet 的文本內容本身。

此外,使用者的 Userline 中也要加入 tweet 的時間和它的 id。如果這是使用者的第一條 tweet 的話,這個insert() 會產生一條新的紀錄,後面的只是為這條記錄增加新列。

最後要給發出 tweet 的使用者和其他 follower 的 timeline 列族添加這條 tweet 的 ID 和時間。

值得注意的一件事是,這裡,時間戳使用的是 64位元長整型變數,而當它成為一個列的名字的時候,它會被包裝為網絡位元組序的二進制值。這是因為 Userline 和 Timeline CF 使用了一個 LongType Comparator,允許我們使用數值區間指定查找指定範圍,所以它們被按照數值來存放起來。
接收一個使用者的 tweets
timeline = USERLINE.get(useruuid, column_reversed=True)
tweets = TWEET.multiget(timeline.values())

接收一個使用者的 tweet,首先從 Userline 獲取tweet ID 的一個列表,然後從 Tweet CF 通過 multiget()方法來讀取這些 tweet。得到的結果將是通過著數值表示的時間戳記逆序排列的,因為 Userline 使用了LongTyper comparator,並且 reversed 設置為了 True。
獲取一個使用者的時間線
start = request.GET.get('start')
limit = NUM_PER_PAGE
 
timeline = TIMELINE.get(useruuid, column_start=start,
column_count=limit, column_reversed=True)
tweets = TWEET.multiget(timeline.values())

和上一個例子類似,這次是從 Timeline 讀取 tweet ID,不過這次我們還使用了 start 和 limit 來控制讀取列的範圍。這樣有助於輸出結果的分頁。

那麼,下一步呢?

希望這篇足夠提供給你一個大致的概念。重複一下,我從程式碼中提取了一些例子,為了簡明起見,在撰寫本文時略去了一些作業,所以現在你可能是 check out 出 Twissandra 的原始碼並進行下一步深入研究的好時機了。有很多功能,諸如 retweet 和 lists,都還空著沒有實作,你可以作為一個練習的起點。如果你已經熟悉 Python 和 Django 的話,那你可以考慮實作一下這些方法。

Cassandra 的 wiki 包含了大量的資訊,而且還在不斷增多,還包括一個即時更新的眾人貢獻的 文章與投影片 的列表。

如果你喜歡 IRC 的話,你可以加入 irc.freenode.net 的 #cassandra 頻道,來和來自全球對 Cassandra 社群者們聊聯天,他們總是熱衷於提供協助和回答詢問的問題。如果你更青睞 email 的話,cassandra-user 郵件列表上也有很多可以提供協助的人。

七月 2, 2010
» [雲端計算] 論文:Cassandra-一個分散式結構儲存系統(轉譯)

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

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

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

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

因此, 老魚希望有心的您可以好好的閱讀它, 當然如果能配合實裝 Cassandra, 以達知行合一, 您將更加瞭解它. 世上沒有完美的IT系統, 但它可使您精進學習IT甚至突破創新!老魚一慣的習性用“紅筆字”, 劃上了自己認為的閱讀重點, 供各位參考, 看完本篇如果您有興趣深入, 可以再閱讀老魚先前 Blog 所整理的相關文章:
  1. [雲端計算] NOSQL 背後的共通原則
  2. [雲端計算] HBase vs Cassandra: 我們遷移系統的原因
  3. [製圖分享] 雲端計算-NOSQL:Cassandra目錄結構關聯概要

本文翻譯自 Facebook 員工在 LADIS 大會上發佈的論文.
這篇論文中, 兩位作者詳細介紹了 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 協議傳輸.請求路由模組的實作使用了一個固定的狀態機. 

當叢集的任一節點收到一個讀取/寫入請求時, 狀態機都會在以下幾種狀態之間切換:
  1. (i)定位擁有該鍵(key)資料的節點
  2. (ii)將請求路由到此節點並等待回應到達
  3. (iii)如果答覆沒有在組態配置所設的超時時間內到達, 就將此請求置為失敗並返回給客戶端
  4. (iv)根據時間戳記算出最新的答覆
  5. (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.69ms7.78ms
中數15.69ms18.27ms
最大26.13ms44.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.

六月 30, 2010
» [製圖分享]雲端計算-NOSQL:Cassandra目錄結構關聯概要

患其身不貴於國也,而不患其主之不貴於天下也;
皆患其家之不富也,而不患其國之不大也;
此所以欲榮而愈辱,欲安而益危。...《易》曰:
“復自道,何其咎,吉”,以言本無異則動卒有喜。
今處官則荒亂,臨財則貪得,列近則持諫,將眾則罷怯,
以此厚望於主,豈不難哉?
- 《呂氏春秋-務本》

上述的短文, 在告誡我們, 如果我們老是都是只想著“己之私利”,
而不願在其社會本位(職責)上務盡思其公利(國家/組織/公司/家庭),
最終的因果循環將回到您的己身“欲榮而愈辱, 欲安而益危"...

回到本篇的主題, 首先 Cassandra 是什麼?
各位可以先從老魚的永久學習筆記頁整理看起:
(雖然目前看來還是有點亂, 持續整理中...)

您也可以從這個不錯的 YouTube 記錄中, 了解 Cassandra,


如果您是位進階者, 讀讀老魚轉載並花了不少時間校對詞句的Blog文選,
  1. [雲端計算] NOSQL 背後的共通原則
  2. [雲端計算] HBase vs Cassandra: 我們遷移系統的原因


底下的這張圖表, 適合想踏入 Cassandra 的初步學習用,
在下回的Blog文, 老魚再將 Cassandra Data Model 的整理筆記給各位.

雲端計算-NOSQL: Cassandra目錄結構關聯概要圖表(點圖放大再另存)

四月 28, 2010
» [雲端計算] NOSQL 背後的共通原則

同樣的這篇文章, 也是老魚從簡體中文譯者那“借來”的, 除了加工再潤詞成正體中文(當然也用紅筆自行畫了重點~呵), 在文中作者提到了 Google 檔案系統論文中最初的設計基礎, 建立在“硬體與網路的失效(Failure)是必定會發生的!”, 這才是一個真正的世界, 大多的 NOSQL 實作可分為二大觀點, 重視使用硬碟, 抑或盡可能的利用 RAM做為一級存儲, 作者也進行了比較說明, 本文中對於想進入 NOSQL 技術領域者, 可以視為一篇入門文選, 所以老魚在此分享本文給各位. Wikipedia - NOSQL, http://en.wikipedia.org/wiki/NoSQLNOSQL Database ORG, http://nosql-database.org/原文: http://natishalom.typepad.com/nati_shaloms_blog/2009/12/the-common-principles-behind-the-nosql-alternatives.html Posted by Nati Shalom at 12:01 PM Dec 15, 2009 譯文: 王旭(http://wangxu.me , @gnawux)2009年12月 16/19日 簡體轉正體中文及校潤詞句:郭朝益(http://wisdomfish.org, @master) 幾個星期之前,我寫了一篇文章描述了經常被稱作 NOSQL 這一類新型資料庫的背後需求動機。幾個星期之前,我在 Qcon 上發表了一個演講,其中,我介紹了一個 可伸縮性(scalable)的 Twitter 應用的構建模式,在我們的議論中,一個顯而易見的難題就是資料庫的 規模可伸縮性(scalability)。要解答這個問題,我試圖尋找隱藏在各種 NOSQL 背後的共通模式,並展示他們是如何解決資料庫規模可伸縮性問題的。在本文中,我將盡力勾勒出這些共通的原則。 實作者們的共通原則 假設失效是必然發生的 Assume that Failure is Inevitable 與我們在此之前認知通過昂貴硬體之類的手段,盡力去避免失效的手段不同,NOSQL 實作都建立在硬碟、機器和網路都會失效(Failure)這些假設之上。我們有需要承認,我們不能徹底阻止這些失效,相反,我們需要讓我們的系統能夠在假使非常極端的條件下也能應付這些失效。Amazon S3 就是這種設計的一個好例子。你可以在我最近的文章 Why Existing Databases (RAC) are So Breakable! 中找到進一步描述。在那裡,我介紹了一些來自 Jason McHugh 所講演的以"失效"為導向的架構設計內容(Jason 是在 Amazon 做 S3 相關工作的高階工程師)。 對資料進行分區 Partition the Data 通過對資料進行分區(分割),我們最小化了失效帶來的服務失效影響,也將讀寫操作的負載分佈到了不同的機器上。如果一個節點(Node)失效了,只有該節點上存儲的資料受到影響,而不是全部的資料。 對同一資料保持多個副本 Keep Multiple Replicas of the Same Data 大部分 NOSQL 實作都基於資料副本的熱備份(hot-backup)來保證連續的高可用性(high availability)。某些實作產品提供了 API,可以控制副本的複製,也就是說,當你存儲一個物件的時候,你可以在物件級別指定你希望保存的副本數量。在 GigaSpaces,我們還可以立即複製一個新的副本到其他節點,甚至在必要時啟動一台新機器。這讓我們不必在每個節點上保存太多的資料副本,從而降低總存儲量以節約成本。 你還可以控制副本複製是同步(synchronous)還是異步(非同步, asynchronous)的,或者兩者兼俱。這決定了你的叢集(Cluster)的一致性、可用性與性能[consistency, reliability and performance]三者。對於同步複製,可以犧牲性能保障一致性和可用性(進行寫入作業之後的任意讀取作業都可以保證得到相同版本的資料,即使是發生失效也會如此)。而最為常見的 GigaSpaces 的配置是同步副本到被分界點,異步存儲到後端存儲。 動態伸縮 Dynamic Scaling 要掌控不斷呈線性增長的資料量,大部分 NOSQL 實作提供了不停機或完全重建分區的擴展叢集的方法。一個已知的處理這個問題的演算法稱為一致性雜湊法(consistent hashing)。有很多種不同演算法可以實作一致性雜湊演算。 演算法會在節點加入或失效時 通知某一分區的鄰近節點。僅有這些節點受到這一變化的影響,而不是整個叢集。有一個協議用於掌控需要在原有叢集和新節點之間重新分佈的資料的變換區間。另一個(簡單很多)的演算法使用邏輯分區。在邏輯分區中,分區的數量是固定的,但分區在機器上的分佈式動態的。於是,例如有兩台機器和 1000 個邏輯分區,那麼每 500 個邏輯分區會放在一台機器上。當我們加入了第三台機器的時候,就成了每 333 個分區放在一台機器上了。因為邏輯分區是輕量級的(基於在記憶體中的雜湊表[hash table]),分散這些邏輯分區非常容易。 第二種方法的優勢在於它是可預測並且一致的,而使用一致性雜湊演算方法,分區之間的重新分佈可能並不平穩,當一個新節點加入網路時可能會消耗更長時間。一個使用 者在這時尋找正在轉移的資料會得到一個異常。邏輯分區方法的缺點是可伸縮性受限於邏輯分區的數量。 更進一步的關於這一問題的討論,建議閱讀 Ricky Ho 的文章 NOSQL Patterns 。 對查詢式的支持 Query Support 在這個方面,不同的實作有著本質上相當的區別。不同實作的一個共通性在於雜湊表中的 key/value 匹配。有些實作提供了更高階的查詢式支持,例如文檔導向(document-oriented)的方 法,其中資料以 blob 的方式存儲,關聯一個鍵值對屬性列表(List)。這種模型是一種無預定義結構的(schema-less)存儲,對一個文檔增加或刪除屬性是非常容易 地,無需考慮文檔結構的演變。而 GigaSpaces 支持很多 SQL 操作。假如 SQL 查詢沒有指出特定的鍵值(key),那麼這個查詢就會被平行地(parallel query) map 到所有的節點去,由客戶端完成結果的聚合(aggregated)。所有這些都是發生在系統後端的,使用者程式碼無需關注這些。 使用 Map/Reduce 處理聚合 Use Map/Reduce to Handle Aggregation Map/Reduce 是一個經常被用來進行複雜分析的模型,經常會和 Hadoop 聯繫在一起。 map/reduce 常常被看作是平行聚合查詢(parallel aggregated queries)的一種模式。大部分 NOSQL 實作並不提供 map/reduce 的內建支持,需要一個外部的框架來處理這些查詢。對於 GigaSpaces 來說,我們在 SQL 查詢中隱含了對 map/reduce 的支持,同時也顯式地提供了一個稱為 executors 的 API 來支持 map/reduce。在這模型中,你可以將程式碼發送到資料所在地地方,並在該節點上直接運行複雜的查詢。這方面的更多細節,建議閱讀 Ricky Ho 的文章 Query Processing for NOSQL DB 。 磁碟基礎 vs. 內部記憶體的實作 Disk-Based vs. In-Memory Implementation NOSQL 實作分為基於檔案的方法和在記憶體(RAM)中的方法。有些實作提供了混合模型,將RAM和磁碟結合使用。兩類方法的最主要區別在於每 GB 成本和讀寫(R/W)性能。最近,Stanford University 斯坦福的一項稱為「The Case for RAMCloud」的調查,對磁碟和 RAM 兩種方法給出了一些性能和成本方面的有趣比較。總體上說,成本也是性能的一個函數。對於較低性能的實作,磁碟方案的成本遠低於基於 RAM 的方法,而對於高性能需求的場合,RAM 方案則更加廉價。 記憶體型態雲端系統 (RAMClouds)最顯而易見的缺點就是單位容量的高成本和高電能耗損。對於這些指標,RAMClouds 會比純粹的磁碟系統差 50到 100倍,比使用快閃記憶體(flash memory)的系統差5-10倍(典型配置情況和指標參見參考文獻[1])。RAMClouds 同時還比基於磁碟和快閃記憶體的系統需要更多的機房面積。這樣,如果一個應用需要存儲大量的廉價資料,不需要高速存取,那麼,快閃記憶體將不是最佳選擇。 然而,對於要求高吞吐量需求的應用,RAMClouds 將更有競爭力。當使用每次操作的 成本和電能耗損作為衡量因素的時候,RAMClouds 的效率是傳統硬碟系統的 100 到 1000 倍,是快閃憶記體系統的 5-10 倍。因此,對於高吞吐量需求的系統來說,RAMClouds不僅提供了高性能,也提供了更高的效率。同時,如果使用 DRAM 動態記憶體晶片組提供的低功耗模式,也可以降低 RAMClouds 的電能功耗,特別是在系統閒置的時候。此外,RAMClouds 還有一些缺點,一些 RAMClouds 無法支持需要將資料在多個資料中心之間進行資料複製。對於這些環境,更新的時間延遲將主要取決於資料中心間資料傳輸的時間消耗

四月 24, 2010
» [雲端計算]HBase vs Cassandra: 我們遷移系統的原因

首先要跟各位聲明的, 這篇文章內容主要是老魚去申請轉載而來, 而我僅是用長年閱讀簡體中文詞彙的經驗加以正體中文和稍加校詞潤飾, 特別選這篇文, 有幾個目的: 老魚為一個新的SNS開發專案, 進行研究評估幾個雲端(分散式)儲存系統, 過程中也是棄了 HBase, MongoDB 選 Cassandra, 而當我這二天看到這篇文中的不少技術選型的出發點, 讓我閱讀後有不少處有所同感(在文章中標紅色的段落).籍由這篇文選, 希望同是身為電腦科學工程與甚至任職企業資訊採購決策管理者一份子的您, 能從這篇文中, 去思考當我們在企業中扮演一個對資訊科技採購時, 不應只是表面名牌價格與廠商行銷手法, 龐大複雜且難以駕馭系統規劃被廠商合理化之, 反造成企業長期的營運維護成本上升, 企業逐漸受外在資訊廠商所“挾持”, 從而失去企業自我資訊自主的競爭本能.這篇文中如果扣除作者在評論其二家產品, 各位看官也可以獲得不少目前電腦科學領域中當前最競爭的幾點新知, 尤其作者是以該領域的專家評論, 在出發點上就不會有太多被一般新聞過度炒作“雲端計算Cloud Computing”名詞上的疑慮.文中作者也對 CAP, CA, AP 等理論給予突破性的實證觀點.原文: http://ria101.wordpress.com/2010/02/24/hbase-vs-cassandra-why-we-moved/ 原作者:Dominic Williams 原文發佈日期:February 24, 2010 at 7:27 pm 譯者:王旭(http://wangxu.me/blog/ , @gnawux) 翻譯時間:2010年3月21-25日 簡體轉正體中文及校潤詞句:郭朝益(http://wisdomfish.org, @master) 我的團隊近來正在忙於一個全新的產品——即將發佈的網絡遊戲 www.FightMyMonster.com。 這讓我們得以奢侈地去構建一個全新的 NoSQL 資料存儲庫系統,也就是說,我們可以把恐怖的 MySQL sharding 和昂貴的可伸縮性拋在腦後了。最近有很多人一直在問,為什麼我們要把注意力再從 HBase 上轉移到 Cassandra 上去。我確認,確實有這樣的變化,實際上我們在基礎上已經把程式碼移植到了 Cassandra 上了,這裡我將作出解釋。 為了那些不熟悉 NOSQL 的讀者,在往後的其他文章中,我會介紹為什麼我們將會在未來幾年中看到如地震般的從 SQL 到 NoSQL 的遷移,這正和向雲計算的遷移一樣重要。往後的文章還會嘗試解釋為什麼我認為 NoSQL 可能會是貴公司的正確選擇。不過本文我只是解釋我們選擇 Cassandra 作為我們的 NoSQL 解決方案的選擇。 免責聲明——如果你正在尋找一個捷徑來決定你的系統選擇,你必須要明白,這可不是一個詳盡而嚴格的比較,它只是概述了另一個初創團 隊在有限時間和資 源的情況下的邏輯。Cassandra 的血統是否預言了它的未來 我最喜歡的一個電腦工程師們用來找 bug 的謁語是「廣度優先於深度」。 這也許可能對那些解決技術細節的人來說很惱人,因為它暗示著如果他們只是看看的話,解決方法就會簡單很多(忠告:只對那些能夠原諒你的同事說這個)。我之所以給出這個謁語的原因在於,我發現,軟體工程問題中,如果我們強迫自己在進入某行程式碼的細節層面之前,先去看看那些較高層次的考慮的話,可以節省大量時間。 所以,在談論技術之前,我在做 HBase 和 Cassandra 之間的選擇問題上先應用一下我的箴言。我們選擇切換的技術結論可能已經可以預測了:Hbase 和 Cassandra 有著迥異的血統和基因,而我認為這會影響到他們對我們的商業適用性。 嚴格來說,Hbase 和它的支持系統源於著名的 Google BigTable 和 Google 檔案系統設計(GFS 的論文期刊被發佈於 2003 年,BigTable 的論文發於 2006 年)。而 Cassandra 則是最近 Facebook 資料存儲庫系統的開放源始碼分支專案,它在實作了 BigTable 的資料模型的同時,使用了基於 Amazon 的 Dynamo 系統架構來存儲資料(實際上,Cassandra 的最初開發工作就是由兩位從 Amazon 跳槽到 Facebook 的 Dynamo 電腦工程師完成的)。 在我看來,這些不同的歷史也導致 Hbase 更加適合於資料倉儲、大型資料的處理和分析(如進行 Web 頁面的索引等等),而 Cassandra 則更適合於實時(Real-Time, RT)事務交易處理和提供交互型資料。要進行系統研究來證明這個觀點超出了本文的範疇,但我相信你在考慮資料庫的時候總能發現這個差異的存在。 注意:如果你正在尋找一個簡單的證明,你可以通過主要 Committer(對參與專案程式撰寫並提交貢獻者之稱) 的關注點來進行驗證:大部分 HBase 的 committer 都為 Bing 工作(M$[Microsoft] 在去年09收購了他們的搜尋公司,並允許他們在數月之後繼續提交開放專案的程式碼)。與之對應,Cassandra 的主要 committer 來自 Rackspace,用來可以自由授權獲取, 支持先進且通用的 NoSQL 的解決方案,用以與 Google, Yahoo, Amazon EC2 等所提供的鎖定在專有授權的 NoSQL 系統解決方案的相互抗衡。Malcolm Gladwell 會說只是根據這些背景的不同就可以簡單地選擇了 Cassandra。不過這是小馬過河的問題。但當然,閉著眼睛就進行一個商業選擇是相當困難的…… 哪個 NoSQL資料儲存庫風頭更勁? 另一個說服我們轉向 Cassandra 的原因是我們社群中的大風潮。如你所知,在電腦科學平台行業裡,始終有著大者恆大的慣性——那些被普遍前景看好的系統平台,會有更多人群聚在這個平台周圍,於是,從長遠來看,你可以得到更好的生態系統的支援(也就是說,大部分支援的軟體工程可以從該社群中獲取,並且也會有更多的開發者可以因此被僱傭)。 如果從 HBase 開始時,我的印象就是它後面有巨大的社群力量,但我現在相信,Cassandra 更加強大。最初的印象部分來源於 StumpleUpon 和 Streamy 的兩位 CTO 兩位非常有說服力的出色的演講者,他們是 Web 行業中兩個在 Cassandra 成為一個可選系統之前的 HBase 的兩個重要的貢獻者,同時也部分來源於閱讀一篇名為「HBase vs Cassandra: NoSQL 戰役!」的文章(大部分內容都己被廣泛證實了)。 勢力是很難被確證的,你不得不自己進行研究,不過我可以找到的一個重要的標誌是 IRC 上的開發者動向。如果你在 freenode.org 上比較 #hbase 和 #cassandra 的開發這頻道,你會發現 Cassandra 差不多在任何時候都有達兩倍的開發者在線上。 如果你用考慮 HBase 一般的時間來考察 Cassandra,你就能發現 Cassandra 的背後確實有非常明顯的加速勢力。你可能還會發現那些逐漸出現的鼎鼎大名,如 Twitter,他們也計劃廣泛使用 Cassandra(這裡)。 註:Cassandra 的網站看起來比 HBase 的好看多了,但認真的說,這可能不僅是市場的趨勢。繼續吧。 深入到技術部分: CAP 和 CA 與 AP 的神話 對於分散式系統,有個非常重要的理論(這裡我們在討論分散式資料庫,我相信你 注意到了)。這個理論被稱為 CAP 理論,由 Inktomi 的 聯合創始人兼首席科學家 Eric Brewer 博士提出。 這個理論說明,分散式(或共享資料)系統的設計中, 至多只能夠提供三個重要特性中的兩個——一致性(C)、可用性(A)和容忍網路分區(P)[Consistency, Availability and tolerance to network Partitions.]。簡單的說,一致性指如果一個人向資料庫寫了一個值,那麼其他使用者能夠立刻讀取這個值,可用性意味著如果一些節點(Node)失效了,叢集(Cluster)中的分散式系統仍然能繼續工作,而容忍分區意味著, 如果節點被分割成兩組無法互相通信的節點,系統仍然能夠繼續工作。 Brewer 教授是一個傑出的人物,許多開發者,包括 HBase 社區的很多人,都把此理論牢記在心,並用於他們的軟體系統設計當中。事實上,如果你搜尋網路上攸關於 HBase 和 Cassandra 比較的文章,你通常會發現,HBase 社群解釋他們選擇了 CP,而 Cassandra 選擇了 AP ——毫無疑問,大多數開發者需要某種程度的一致性 (C)。 不過,我需要請你注意,事實上這些生命基於一個不完全的推論。 CAP 理論僅僅適用於一個分散式演算法(我希望 Brewer 教授可以統一)。但沒有說明你不能設計一個超出理論的系統,並在其中各種操作的底層演算法選擇上進行特性切換。所以,在一個系統中,確實一個操作職能提供這些特性中的兩個,但被忽視的問題是在系統設計(SD)中,實際是可以允許調用者來選擇他們的某個操作時需要哪些特性的。不僅如此, 現實世界也非簡單的劃分為黑白兩色,所有這些特性都可以以某種程度來提供。這就是 Cassandra。 這點非常重要,我重申:Cassandra 的優點在於你可以根據具體情況來選擇一個最佳的折衷,來滿足特定操作的需求。Cassandra 證明,你可以超越通常的 CAP 理論的解讀

support:

一頁

A Django site.