伯克利推出世界最快的KVS資料庫Anna：秒殺Redis和Cassandra

策劃編輯 | Natalie

譯者 | Martin

編輯 | Natalie、Emily

AI 前線導讀：天下武功，唯快不破。伯克利 RISE 實驗室推出了最新的鍵值存儲資料庫 Anna，提供了驚人的存取速度、超強的伸縮性和史無前例的一致性保證。Jeff Dean 說，當一個系統增長到十倍規模時，就需要進行重新設計。那麼，對於 RISE 實驗室的研究員們來說，怎樣才能設計出一個具備指數級增長規模的鍵值存儲資料庫呢？

更多乾貨內容請關注微信公眾號「AI 前線」，（ID：ai-front）

題外話：RISE 實驗室的前身是赫赫有名的伯克利 AMP 實驗室，該實驗室曾開發出了一大批大獲成功的分散式技術，這些技術對高性能計算產生了深遠的影響，包括 Spark、Mesos、Tachyon 等。如今，原 AMP 實驗室博士生，同時也是 Spark 和 Mesos 核心作者之一的 Matei 已經轉身去了斯坦福，並於去年年底推出了以普及機器學習實踐為目的的開源項目 DAWN（詳見 AI 前線報道 )，而 RISE 實驗室也在沒多久後推出了志在取代 Spark 的新型分散式執行框架 Ray（詳見 AI 前線報道）。

過去幾年，RISE 實驗室把研究重點放在如何設計一個無需協調的分散式系統上。他們提出了 CALM 基礎理論（http://db.cs.berkeley.edu/papers/sigrec10-declimperative.pdf），設計出了新編程語言 Bloom（http://bloom-lang.net/），開發出了跨平台程序分析框架 Blazes（https://arxiv.org/pdf/1309.3324.pdf），發布了事務協議 HATs（http://www.vldb.org/pvldb/vol8/p185-bailis.pdf）。但在推出 Anna 之前，他們還未就這些理論、語言、框架或協議在多核環境下或雲環境中能夠提供怎樣的性能有過任何測試或評估。

而 Anna 的推出正好印證了他們之前的研究成果。Anna 的論文顯示，在單個 AWS 實例上，Anna 的速度是 Redis 的 10 倍。而在一個標準的互動式基準測試中，也以 10 倍的速度打敗了 Cassandra。為了獲得更多的比較結果，他們還拿 Anna 與其他主流的鍵值系統進行了性能對比：比 Masstree 快 700 倍，比英特爾的「無鎖」TBB 哈希錶快 800 倍。當然，Anna 並沒有提供類似其他鍵值系統那樣的線性一致性。不過，Anna 使用了本地緩存存放私有狀態，仍然提供了極佳的無協調一致性，比「hogwild」風格的 C++ 哈希表要快上 126 倍。而且一旦到了雲端，Anna 更是獨領風騷，其他的系統無法真正提供線性伸縮，但 Anna 卻可以。

Anna 的性能和伸縮性主要歸功於它的完全無協調機制，節點工作進程有 90% 的工作負載是在處理請求，而其他大部分系統（如 Masstree 和英特爾的 TBB）只有不到 10% 的時間在處理請求，它們其餘的 90% 時間花在了等待協調上。不僅如此，其他系統因為使用了共享內存，還會出現處理器緩存擊穿問題。

Anna 不僅速度快，在一致性方面也達到了很高的水準。多年前，他們發布的事務協議 HATs 就已表明，無協調的分散式一致性和事務隔離性存在很大的提升空間，包括級聯一致性和讀提交事務級別。Anna 將 Bloom 的單格子組合設計模式移植到了 C++ 中，是第一個實現了上述所有級別一致性的系統。當然，也是因為設計上的簡潔，才能達到如此快的速度。

RISE 的研究員們在設計 Anna 的過程中學到了很多，它們已經遠遠超出了一個鍵值資料庫的範疇，可以被應用在任何一個分散式系統上。他們正基於 Anna 開發一個新的擴展系統，叫作 Bedrock。Bedrock 運行在雲端，提供了無需人工干預、低成本的鍵值存儲方案，而且是開源的。

Anna 架構簡析

圖 1：Anna 架構

上圖是 Anna 單節點的架構圖。Anna 伺服器由一系列獨立的線程組成，每個線程運行無協調的 actor。每個線程對應一個 CPU 核心，線程數量不超過 CPU 的總核數。客戶端代理負責將遠程請求分發給 actor，每個 actor 都有一個私有的哈希表，這些哈希表存放在共享內存中。線程間的變更通過內存廣播進行交換，而伺服器間的變更則通過 protobuf 進行交換。

這種線程和 CPU 核心一對一的模型避免了上下文切換開銷。actor 之間不共享鍵值狀態，通過一致性哈希對鍵空間進行分區，並使用多主複製機制在 actor 之間複製數據分區，而且複製係數是可配置的。actor 基於時間戳將鍵的更新通知給其他 actor 副本，每個 actor 有自己的私有狀態，這個狀態保存在一個叫作「格子」的數據結構中，確保在消息發生延遲、重排或重複時仍然能夠保證一致性。

Anna 性能評測

下面就 Anna 的無協調 actor 模型在多核 CPU 上的並行能力、多伺服器伸縮能力進行評測，並將它與其他流行的鍵值資料庫進行對比。

無協調 actor 模型的伸縮性

在無協調 actor 模型中，每個 actor 對應一個線程，對任何一個共享狀態都有自己的一份私有拷貝，並通過非同步廣播將更新通知給其他 actor。在多核伺服器上，這種模型比傳統的共享內存模型的性能要高出一個數量級。

為此，RISE 研究員設計了一個對比實驗，將 Anna 與其他基於共享內存的 TBB、Masstree 和自己實現的一個鍵值存儲系統（姑且把它叫作「Ideal」）進行了對比。他們在 AWS 的 m4.16xlarge 實例上運行實驗，每個實例配備了 32 核的 CPU。實驗中使用了 1 百萬個鍵值對，鍵的大小為 8 位元組，值的大小為 1KB。在實驗過程中，他們基於 zipfian 分布和各種係數生成不同的壓力負載，模擬不同層次的衝突。

在第一次實驗中，他們對比了 Anna 與 TBB、Masstree 和 Ideal 在單台伺服器上的吞吐量。他們逐漸增加線程數量，直到達到伺服器 CPU 核數的上限，並觀察它們的吞吐量。

圖 2

圖 3

圖 2 是在高並發情況下，線程數與吞吐量的變化關係，其中 zipf 係數為 4。圖 3 是在高並發情況下，CPU 時間的使用情況。CPU 時間被分為 5 類：處理請求（RH）、原子指令（AI）、合併格子（LM）、廣播（M）和其他。最右邊一欄是 L1 緩存擊穿數量（CM）。

從圖中可以看出，在這樣的負載壓力下，TBB 和 Masstree 幾乎失去了並行能力。因為大部分是更新操作，針對同一個鍵值的並行更新操作會被串列化，它們需要同步機制來防止多個線程同時更新同一個鍵值。因此，隨著線程數量的增加，它們性能也只能趨於平緩。Ideal 雖然比 TBB 和 Masstree 的性能高出 6 倍，但相比 Anna，還是差了很多。儘管它沒有使用同步機制，但在多個線程修改共享內存地址時，仍然存在緩存一致性方面的開銷。

相反，在 Anna 中，更新操作是針對本地狀態進行的，不需要進行同步，並定時通過廣播進行變更交換。在高並發情況下，儘管它的性能仍然受限於其複製係數，但比基於共享內存的系統要好很多。Anna 有 90% 的 CPU 時間用於處理請求，花在其他方面的時間則很少。可見，Anna 的無協調 actor 模型解決了鍵值存儲系統在多核環境里的伸縮性難題。

圖 4

圖 5

圖 4 是在低並發情況下，線程數與吞吐量的變化關係，其中 zipf 係數為 0.5。圖 5 是在低並發情況下，CPU 時間的使用情況，其中最右邊一列表示內存佔用（MF）。

當複製係數為 1 時，Anna 因為內存佔用率極低而獲得了更好的伸縮性。不過，隨著複製係數的增加（增加到 3），吞吐量出現了明顯下降（下降了四分之三）。這裡有兩個原因。首先，增加複製係數會佔用更多的內存，而且在低並發的情況下，唯一鍵的更新操作大量增加，所以無法通過合併的方式進行變更交換。圖 5 顯示，當複製係數為 3 時，Anna 有 69% 的 CPU 時間用於處理廣播變更。而在使用完整的複製係數時，Anna 也停止了伸縮，因為此時相當於每個線程只能處理一個請求。不過，儘管 TBB 和 Masstree 沒有廣播開銷，但在內存佔用和同步操作方面仍然存在大量開銷。因此，從這個實驗中可以得出這樣的結論：對於一個支持多主複製的系統來說，在低並發量情況下使用高複製係數對性能是一種傷害。

圖 6

圖 6 是在多個伺服器上增加線程數時的吞吐量變化情況。Anna 的複製係數設置為 3，先是啟動第一台伺服器的 32 個線程，然後是第二台伺服器的 32 個線程，最後是第三台伺服器的所有剩餘線程。從圖中可以看出，Anna 的吞吐量隨著線程數量的增加呈線性增長。在啟動第 33 個線程時吞吐量有輕微下降，不過那是因為第 33 個線程是屬於第二台伺服器的。但從整體來看，吞吐量的增長是很穩定的。可見，藉助 Anna 的無協調 actor 模型，是可以實現吞吐量線性增長的。

與其他系統的比較

為對比 Anna 與其他流行鍵值系統之間的性能差異，RISE 研究員設計了兩次實驗，第一次在單節點上與 Redis 進行對比，第二次在一個大型的分散式系統上與 Cassandra 進行對比。

Anna 具有多線程並行能力，而 Redis 使用的是單線程模型。所以，在第一次實驗中，他們在同一台伺服器上搭建了一個 Redis 集群，讓 Anna 與這個集群進行比較。實驗是在 AWS 的的 EC2 實例上運行的，其中 Redis 集群使用了儘可能多的線程。

圖 7

從圖 7(a) 可以看出，在高並發情況下，Redis 集群的整體吞吐量幾乎保持不變，而 Anna 可以在副本之間分散熱鍵。Anna 的吞吐量隨著複製係數的增加而增長，直到達到平緩。如果熱鍵完全被複制，吞吐量還會隨著線程的增加繼續增長。從圖 7(b) 可以看出，在低並發情況下，Anna 和 Redis 集群都獲得了不錯的並行能力，它們的吞吐量都隨著線程數的增加而增長。

從這次實驗可以看出，在高並發情況下，Anna 通過複製熱鍵的方式在性能方面吊打 Redis 集群，而在低並發情況下，Anna 可以與 Redis 集群達到相似的性能。

在第二次實驗中，RISE 研究員將 Cassandra 的一致性設置為最低級別（ONE），也就是說，只要一個節點確認就表示更新操作成功。他們在 AWS 的四個 EC2 可用區域（奧爾良、北弗吉尼亞、愛爾蘭和東京）上運行該實驗，並通過調整可用區域的節點數量來評測它們的伸縮性。它們的複製係數都被設置為 3。

圖 8

從圖 8 可以看出，隨著節點的增加，Anna 和 Cassandra 的性能都呈現出線性增長。不過，Anna 比 Cassandra 的性能高出一大截。事實上，在每個節點使用 4 個線程時，Anna 就可以打敗 Cassandra，而當把所有的線程都用上，Anna 比 Cassandra 的性能高出 10 倍以上。

參考資料：

https://rise.cs.berkeley.edu/blog/anna-kvs/?twitter=@bigdata

論文原文：

http://db.cs.berkeley.edu/jmh/papers/anna_ieee18.pdf

今日薦文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！