MegaStore是Google在BigTable之上實作了一個跨機房高可用的資料庫。
它提供了類似DB的資料分布、索引的功能，實作了在EntityGroup内部以及EntityGroup之間的事務性，并且通過Paxos協定實作在DC之間多備份的一緻性。
MegaStore的目标：在跨機房PB級的資料規模上，支援互動式線上服務。我們知道在Google内部的通路情況是，每天幾百億次的通路請求的應用，讀寫比例大概在7：1。在這樣的規模上，需要達到的特性：
1）高擴充性，無論在機器擴充性還是資料規模上
2）快速的開發疊代速度，
3）低延遲
4）資料一緻性
5）高可用
MegaStore的實作原理：
1）從資料庫的擴充性的角度上，把大資料切分成更小粒度的資料集(EG)，每個資料庫保持一個獨立的log，儲存在BigTable當中。//這也就意味着在每個DC上有一個獨立的BigTable資料庫。
2）從可用性角度上講，在跨機房之間，實作了同步、可容錯的log-replicator,實作不同DC之間資料的一緻性。(Synchronous Paxos)
3) 從資料庫事務性的角度上，在EG内部是通過Write-Ahead-Log實作ACID，而在EG與EG之間，Megastore提供兩類方式，一是二階段送出協定，二是異步消息隊列。顯然，效率上講異步消息隊列更勝一籌。
MegaStore的資料模型：
1）支援基本的資料類型，以及ProtoBuf結構體
2）支援Required、Optional、Repeated語義
EG的資料被放置在BigTable連續行，處于如下的原因：
1）低延遲
2）高吞吐
3）Cache的效率
其中每一個Entity會被映射成BigTable中的一行，并且以該Row為部分Primary Key的其它表格，也會被記錄在這個EG當中，這樣做的一個最大的好處在于，比方Google通過Megastore提供的Gmail應用中，以userid為主鍵的其它資訊會被快速檢索出來。當然，MegaStore支援inline Indexing，會直接把索引資訊存在主Row對應的Column當中，盡快加速存儲。
MegaStore的Schema與具體存儲之間的映射關系：
以下是Schema定義格式：
Schema定義的要求：
1）支援兩種類型的表格：Entity Group Root Table以及Child Tables，其中Child Tables必須reference到Root Table
2）支援Local Indexing、Global Indexing、Inline Indexing，需要注意的是LocalIndexing存儲在EntityGroup内部，遵循單階段ACID語義的一緻性，而GlobalIndexing僅僅支援最終一緻性，換句話說，通過GlobalIndexing查詢到的資料可能不是最新的。針對Inline Indexing它屬于Local Index的一種，因為這種Table的Row由兩部分組成，一部分是Root Table的Primary Key，另外一部分是Indexing的Property，是以，IndexingTable的做法就是不在BigTable當中寫入新的一行，在原有的RootTable中增加新的列，列名采用新表的表名+property。
3）每一個EG對應一個WAL，這樣多WAL的情況，要比單WAL的情況要好很多，使得異常局部化，保證整個系統吞吐的穩定性。
注意：MegaStore的Table隻是邏輯上的概念，比方說BigTable的Column Name是MegaStore Table Name和Property的組合，例如，建立的INLINE INDEX，在存儲上和Parent Table放置在BigTable的同一行中。
同時，在Root Table的BigTable單行中，還存儲了transaction,replication中繼資料以及Transaction Log。下圖是整個MegaTable Table在BigTable之上的布局圖。
Entity Group内的讀寫操作，借助BigTable MVCC（Multi-Version Concurrent Control多版本并發控制）。例如在Hbase當中，采用了MemStoreTS控制讀寫資料資料的時間版本的可見性，保證讀到的資料是被Commited之後的資料，保證不會讀到處于uncommited的寫資料。與Hbase類似，MegaStore也會有一個WAL來記錄寫資料的edit log，不同的是，每個EG都對應一個WAL，甚至說在每個RootTable内對應Column分别記錄WAL和中繼資料。
Write操作：
1）擷取目前log中的可用位置。current read保證之前的commit的事務全部被applied到data。
2）資料的更新操作組合成一次commit事件，然後獲得最大的時間戳，append到WAL log中。
3）在Append到WAL log之後，該事件就處于Commited狀态了，寫操作就可以傳回用戶端了。後續就是異步地實作資料的更新。
串行化的Transaction，可以從上圖的此刻的狀态，如果假定此時發生了一次故障,那麼
1）Transaction1是安全的，資料已經被完全送出到Data；
2）Transaction2已經送出成功，此時隻需恢複從WAL到Data即可，該狀态沒有資料丢失。
3）Transaction3 失敗，此時傳回用戶端送出請求失敗。
Read操作：
支援三種方式的讀操作：
1）Current Read: 從WAL中擷取最新Committed的版本，事務系統會確定所有的Committed狀态的資料都已經寫入資料區，是以，該讀操作方式應用在一緻性要求較高的場合。
2) Snapshot Read：擷取最新的、且已經被完全寫入的事務的版本的資料。
3) In-Consistent Read：可以讀取還沒有被完全Applied狀态的資料。
一個事務完整的生命周期：
1）從中繼資料中擷取最新的版本(Committed)的資料
2）應用邏輯：Read+Modify+write
3）聚集多個Mutation到一個Log Entry(Transactions編号)，配置設定一個最新higher的TimeStamp,然後Paxos-Replicator會負責把這部分WAL同步到其它DC，完成之後傳回給用戶端即可。
4）Write Mutations更新Data和Index表
5）清理不需要的WAL
ps:4)5)兩步屬于異步操作。
MegaStore架構圖：
1）MegaStore的部署包括兩部分内容：用戶端庫、以及附屬Server。
2）每一個AppServer指定一個Replica為本地的，會把Transaction直接寫入本地的BigTable，然後通過Paxos算法，同步給其它的Replication Server，由其寫入BigTable。
3）Client、network、以及BigTable的錯誤，可能會導緻寫操作處于中間狀态。ReplicationServer會周期性檢查處于中間狀态的寫操作，重新送出該請求。
4）Coord使用Paxos語義在跨DC之間，實作Transaction的Log送出順序的一緻性。不同的DC的ReplicationServer在并發接收EG的commit時，需要通過Coord保證全局的WAL送出順序的一緻性。
思考：
1）Google-MegaStore的架構圖，Coord的作用是幫助AppServer了解整個環境中的狀态，提供相關的中繼資料，比如，另外Replica下的一個Server之類的。
2）有些Replica不儲存Data，可以了解為它隻負責備份使用，待需要時做資料還原。
3) Google的這個模型，個人感覺是以應用為中心的，不是以服務為中心的架構。例如，MegaStore服務的GMail應用，會以這個應用建構一套ReplicationServer、Coord，以及對應BigTable，而不是通過這個架構對外提供統一的服務。
參考文獻：
[1]ppt: http://www.slideshare.net/schubertzhang/learning-from-google-megastore-part1-12149098
[2]paper: http://research.google.com/pubs/pub36971.html
本系列文章屬于Binos_ICT在Binospace個人技術部落格原創，原文連結為http://www.binospace.com/index.php/google-megastore-interpretation/,未經允許，不得轉載。
From Binospace, post Google-MegaStore的解讀
文章的腳注資訊由WordPress的wp-posturl插件自動生成