Percolator

英 [ˈpɜ:kəleɪtə(r)]美 [ˈpɚkəˌletɚ]

n.過濾器，抽出器。

Percolator是由谷歌推出的，在海量數據(PB級)上實現增量計算的平台。它使得在已有的結果集上進行小粒度的更新(small updates)更加快速。

Percolator不是對現有的全量計算的替代；不能分解的計算應該由mapreduce處理，而不是由Percolator處理；Percolator適合處理的對一致性要求強烈的計算，否則bigtable就能處理；Percolator適合處理海量的數據，否則現有的DBMS就能處理。

在google內部，使用到Percolator的產品有web indexing system 和 render pages into images。

基本介紹

• 外文名：Percolator
• 性質：平台
• 推出機構：谷歌
• 用途：在海量數據(PB級)上實現增量計算

基本信息

Google在新一代內容索引系統中放棄了MapReduce，替代者是尚不為人知的分散式數據處理系統Percolator。 　The Register報導，Percolator是一種增量處理平台，它能持續更新索引系統，無需從頭重新處理一遍整個系統。Google的工程師計畫在下個月舉行的年度USENIX Symposium 會議上公布Percolator相關論文。為了提高效率，MapReduce和其它批量處理系統創造了大數據批量，因此無法處理單個小規模的數據更新。Percolator系統便是為了解決這一問題，它能對一個大數據集增量處理更新。用Percolator替代MapReduce，每天處理相同數量的文檔，能在搜尋結果中將文檔平均年齡（average age）減少50%。

簡介

Percolator是由谷歌推出的，在海量數據(PB級)上實現增量計算的平台。它使得在已有的結果集上進行小粒度的更新(small updates)更加快速。

Percolator不是對現有的全量計算的替代；不能分解的計算應該由mapreduce處理，而不是由Percolator處理；Percolator適合處理的對一致性要求強烈的計算，否則bigtable就能處理；Percolator適合處理海量的數據，否則現有的DBMS就能處理。

在google內部，使用到Percolator的產品有web indexing system 和 render pages into images。

設計

Percolator是基於bigtable的。另外，Percolator還基於另外兩個服務：提供嚴格遞增的時間戳的timestamp oracle服務和提供分散式鎖的chubby服務。

實現Percolator有兩個要素。第一是事務，事務保證了數據的一致性。第二是observer(類似於DBMS中的觸發器)，observer掃描表中的數據並觸發事務。

事務

Percolator是通過快照隔離(Snapshot isolation)實現事務的，多版本數據是快照隔離的必要條件，幸運的是bigtable可以通過時間戳來支持多版本的數據。

例如

在Percolator有一張Balance表，記錄了各個用戶的賬戶餘額，見圖2。現在要從Bob的賬戶轉$7至Joe，如何實現這個事務?

Balance表最終都存儲在bigtable的表中。在bigtable中，存儲Balance表的格式見圖3。其中bal:data存儲的真正的數據，其它列存儲的是元數據。各個列定義如下：

●data: 真正的數據

●lock: 鎖。標記primary lock的位置

●write: 有效數據的時間戳。

●notify: observer使用，後續會給出解釋，本小節不關心。

●ack_O: observer使用，後續會給出解釋，本小節不關心。

實現轉帳事務的流程如下：

1) 對Bob的賬戶加主鎖。並修改賬戶數據為$3。見圖4。

註：我們並沒有修改其有效數據的時間戳(即沒有修改Bal:write)，所以其它事務看到Bob

的餘額仍是$10。

2) 對Joe的賬戶加鎖，此鎖指向此事務的主鎖 Bob.bal。修改其Joe賬戶數據為$9。

見圖5。

註：我們並沒有修改其有效數據的時間戳(即沒有修改Bal:write)，所以其它事務看到Joe

的餘額仍是$2。

3) 解主鎖，並修改bal:write使得修改後的數據對其它事務是可見的。見圖6。

註：這一步是commit point。即只要執行了這一步，此事務只能被完全執行，不能回滾；如果沒有執行

至這一步，此事務是可以回滾的。

4) 解Joe的鎖，並修改bal:write使得修改後的數據對其它事務是可見的。見圖7。

5) 結束。