Google Megastore系統事務機制

Entity Group模型

網際網路應用往往可以根據使用者來進行拆分，比如Email系統，相冊系統，廣告投放效果報表系統，購物網站商品存儲系統等，同一個使用者内部的操作需要保證強一緻性，如要求事務，多個使用者之間的操作往往可以要求弱一緻性，比如使用者之間發Email不要求立即收到。是以，可以根據使用者将資料拆分為不同的子集分布到不同的機器上。Google進一步從網際網路應用特性中抽取Entity Group概念，進而實作可擴充性和資料庫語義之間的一種權衡，同時獲得NOSQL和RDBMS的優點。

CREATE TABLE User { 

required int64 user_id; 

required string name; 

} PRIMARY KEY(user_id), ENTITY GROUP ROOT;

CREATE TABLE Photo { 

required int32 photo_id; 

required int64 time; 

required string full_url; 

optional string thumbnail_url; 

repeated string tag; 

} PRIMARY KEY(user_id, photo_id), 

IN TABLE User, 

ENTITY GROUP KEY(user_id) REFERENCES User;

在上例中，使用者定義User和Photo兩張表，主鍵分别為<user_id>和<user_id, photo_id>，每一個使用者的所有資料構成一個Entity Group。每一個Entity Group有一個特殊的Root Entity，對應Bigtable存儲系統中的一行，如User表的一行為一個Root Entity，對Root Entity的原子性操作可利用Bigtable的單行事務實作。由于同一個Entity Group連續存放，是以多數情況下同一個使用者的所有資料屬于同一個Bigtable子表，分布在同一台Bigtable Tablet Server機器，進而提供較高的掃描性能和事務性能。當然，如果某一個Entity Group過大，比如超過一個子表的大小，這樣的Entity Group跨多個子表，進而可能分布到多台機器。

記錄檔

如上圖，總體上看，資料拆分成不同的Entity Group，每個Entity Group内的記錄檔采用基于Paxos的方式同步到多個機房，保證強一緻性。Entity Group之間通過Queue的方式保證最終一緻性或者Two-Phase Commit的方式實作分布式事務。我們先看單個叢集的情況，暫時忽略基于Paxos的Replication機制。

單叢集Entity Group内部：同一個Entity Group内部支援滿足ACID特性的事務。資料庫系統事務實作時總是會提到REDO Log和UNDO Log，在Megastore系統中使用REDO Log的方式實作事務。同一個Entity Group的REDO Log都寫到這個Entity Group的Root Entity中，對應Bigtable系統中的一行，進而保證REDO Log操作的原子性。用戶端寫完REDO Log後，事務操作成功，接下來的事情隻是回放REDO Log（也可稱為應用REDO Log）。如果回放REDO Log失敗，比如某些行所在的Tablet Server當機，事務操作也可成功傳回用戶端。後續的讀操作如果要求讀取最新的資料，需要先回放REDO Log。

單叢集Entity Group之間：Entity Group之間一般采用Queue的方式提供最終一緻性，Tablet Server上有定時掃描線程，發送跨Entity Group的操作到目的Entity Group。如果需要保證多個Entity Group之間的強一緻性，即實作分布式事務，隻能通過Two-phase Commit協定加鎖協調。

并發控制

網際網路應用是一個讀多寫少的應用，設計并發控制時一般不允許阻塞讀操作，常見的copy-on-write機制，MVCC并發控制等都是為了這個目的。Megastore實作的事務隔離級别為Serializable（可序列化），即資料庫的事務是可串行化執行的。由于Bigtable對每個Cell保留了不同版本的資料，天然适用MVCC機制。

事務執行：采用樂觀鎖的方式實作事務，讀取時記錄資料的版本号，事務送出時檢查Entity Group目前的事務版本号與讀取時記錄的版本号是否相同，如果相同則成功送出事務，否則重試。比如有兩個事務T1和T2，其中：

T1：Read a; Read b; Set c = a + b;

T2：Read a; Read d; Set c = a + d;

假設事務T1和T2對同一個Entity Group并發執行，T1執行時讀取a和b，同時記錄版本号為1，這時T1執行中斷，T2開始執行，首先讀取a和d，記錄的版本号也為1，接着T2送出，這時操作的Entity Group版本号為1，是以，沒有其它事務發生更新操作，T2成功送出，并更新該Entity Group的版本号為2。當T1恢複并繼續執行時，發現此時操作的Entity Group版本号被修改為2，T1復原重試。對同一個Entity Group的多個事務被串行化，Megastore之是以能提供Serializable級别的并發控制，得益于定義的Entity Group資料模型，由于同一個Entity Group同時進行的更新往往很少，事務沖突導緻重試的機率很低。

MVCC：MVCC機制的主要目的是讀操作不需要加鎖。Megastore提供了三種讀取模式：current, snapshot和incosistent。其中，current和snapshot模式讀取已經成功送出的事務，且current需要讀取最新的成功送出的事務，而incosistent直接讀取本地資料，不用關心是否出現事務進行到一半導緻資料不完整的情況。由于底層的Bigtable保留了曆史版本資料，snapshot模式實作時選取已經成功應用（回放REDO Log完成）的最新事務的版本号，并從Bigtable中讀取該版本号對應的資料，可能存在某些事務已經送出（已經記錄了REDO Log）但沒有應用（回放REDO Log）的情況，這些事務産生的效果在snapshot模式下是讀取不到的。而在current模式中，需要首先確定所有已經送出的事務被成功應用。

索引支援

Megastore支援兩種索引，一種是local index，另外一種是global index，其中local index和事務機制有關。每個Entity Group有一個local index，用于在Entity Group内部加快資料查詢。在某個Entity Group上執行事務操作時先記錄REDO Log，回放REDO Log時同時更新該Entity Group的資料和local index。

總體上看，Google Megastore論文，尤其是其中的事務機制，有些複雜，建議結合關系型資料庫的并發控制，ACID等特性先思考單個叢集的Megastore事務實作，再思考如何通過基于Paxos的Replication機制實作多個叢集之間的一緻性。