論文閱讀筆記 - Megastore : ProvidingScalable, Highly Available Storage for Interactive Services

作者：劉旭晖 Raymond 轉載請注明出處

Email：colorant at 163.com

BLOG：http://blog.csdn.net/colorant/

更多論文閱讀筆記 http://blog.csdn.net/colorant/article/details/8256145

關鍵字

跨機房，資料同步，paxos，一緻性，Google Megastore

== 目标問題 ==

提供一個可伸縮的，高可靠，一緻性好，跨地域，低延遲，易用性好的資料庫存儲方案

== 核心思想 ==

以上目标（本質需求上相沖突）很難做到面面俱到，需要在不同的方面進行取舍。Megastore的核心思想是将資料分割成不同的EntityGroup，EntityGroup的資料備份是跨Datacenter存放的，在EntityGroup内部提供完整的ACID支援，保證資料寫操作在所有資料中心的同步備份。在EntityGroup之間隻提供受限的ACID，例如不保證資料的強一緻性等。

這種資料劃分的思想主要是基于多數的資料内在的都可以按照一定的原則分組（如按使用者劃分），組内的操作的對一緻性，實時性的要求比較高，但是因為多方同時操作同一個組的機率比較低，資料沖突發生的可能性較小，是以滿足一緻性等名額所帶來的代價也比較小，而跨組的操作可以對資料一緻性和更新延遲的容忍程度較高。可以降低這方面的名額。

如何在保證一緻性的基礎上做到高可靠性和高可用性的資料備份，是整個系統的關鍵。常見的廣域資料備份方案各有優缺點：

• 異步的主從節點：主節點異步的将log寫到從節點，不等待從節點的确認。這樣的優點是延遲小，缺點是主節點失敗時可能導緻部分資料丢失，也難以保證高可用性。
• 同步的主從節點：主節點将log同步的寫到從節點，隻有得到确認後才允許完成目前操作，這樣的優點是可以保證資料的可靠性，缺點是延遲大，主從節點的監控和切換需要有效的機制
• 樂觀的平等主節點：沒有主從節點之分，各個節點都可以接受資料修改，再異步的派發，優點是延遲小，高可用性，但是資料一緻性得不到保障。

Megastore的方案有點類似平等的節點方案，沒有主從節點之分，任何節點都可以發起寫操作，但是通過Paxos機制來決定哪個寫操作最終被采納并分發，進而保證資料的一緻性。

每個EntityGroup有自己的多備份的操作Log，保證高可用性，也可以最大并行化不同EntityGroup的操作。

跨EntityGroup的操作通過消息隊列來實作，因而是弱一緻性的。不過對于一緻性要求高的應用，也可以使用兩階段送出的方式保證強一緻性。

如何合理的劃分EntityGroup，達到最佳性能則是使用者需要考慮的。

== 實作細節 ==

• 提供了一個可完全串行化ACID的低延遲遠端資料備份環境。
• 為了保證資料操作的低延遲，megastore允許使用者指定EntityGroup的主資料中心，它的Schema的設計也保證EntityGroup内部資料的連續存儲。
• 一個EntityGroup的資料可能存放在不同的表裡（Entity Root Table和child Table），而不同EntityGroup的相同字段的資料則是存放在同一個表裡
• 由于BigTable這樣的key-value類資料庫本身是适合于存儲稀疏結構化的資料的，在Read為主的應用環境下，盡量使用denormalization的Schema設計和存儲方式，減少Join的開銷
• 使用了BigTable的一個單元格可以存儲多個Version的資料的特性來實作基于MVCC的ACID
• 讀操作分為current/snapshot/inconsistant三類，由于采用MVCC，讀寫可以并行，不同的讀操作針對不同的應用場合，current保證目前所有寫操作已經完成，來讀取最新資料，snapshot可以指定特定版本，inconsistant不保證資料的一緻性，立刻讀取目前資料
• 寫操作通過Paxos機制決定下一個Log位置，任何replica都可以發起寫操作，隻有競争獲得下一個Log位置的程序，可以真正執行寫操作，先寫log，再Apply change。類似樂觀鎖機制，競争失敗的寫操作自己重試。
• Paxos模型的通訊開銷是實作Paxos的系統或多或少都要面臨的問題，Megastore使用了一個coordinator服務程序來跟蹤本地資料備份replica中，哪些EntityGroup的資料是最新的，對這些資料，規避Paxos過程來直接讀取本地資料。而coordinator的狀态要由應用層在寫操作是負責同步更新
• 除了完整的Replica Server，Megastore還使用了兩種簡化的Replica Server角色，一種隻儲存Log不儲存資料，另一種隻儲存資料不儲存Log，分别用于Paxos仲裁和提供隻讀服務（可能不是最新版本的資料）
• 如果coordinator實效了，寫操作會被Block，這也就要求有一個機制檢測coordinator的實效，megastore使用Chubby Lock服務檢測coordinator失效，對于coordinator自己來說，如果更新chubby lock失敗，就認為本地的資料都不是最新的，Read操作都要走Paxos流程，對于寫操作，在檢測到coordinator失效時就不等待他的invalidate操作傳回，在失效被發現前，大概有10秒的時間write會被block，但是，實效的coordinator的恢複期間，讀寫操作都不會被block，依然可以正常進行。

== 資料 ==

平均讀延遲10ms，平均寫延遲100-400ms，取決于讀寫資料量的大小，資料備份replica的數量和資料中心的分布距離。可用性方面，基于多年100+的實際上線應用的資料統計多數可以達到99.999%以上的讀寫可用性。

== 相關研究，項目等 ==

項目相關的首先當然是底層的BigTable，其次是Chubby。理論相關如Paxos，和各種Fast Paxos的優化方案研究等

類似的項目：阿裡的Wasp，大概是基于Megastore的理論，在HBase上的一個仿照實作。

== 其它 ==

個人了解簡單總結：

megastore本身不是資料庫，更像一個基于Bigtable資料庫的多資料中心資料備份讀寫解決方案，采用了各式各樣的最佳實踐來達到它的目的。使用Paxos來同步和保證資料Replica的讀寫一緻性，采用劃分EntityGroup的方式來減少Paxos過程的沖突，使用Coordinator/localread/chubby lock以及其它各種機制來提高效率，減少延遲，檢測失效。使用megastore client Library屏蔽底層實作複雜性的同時，也提供給使用者足夠的靈活性來指導資料的存放和讀寫以提高效率。同時提供了Index，schema，queue等以提高底層BigTable資料庫的易用性。