作者：劉旭晖 Raymond 轉載請注明出處
Email：colorant at 163.com
BLOG：http://blog.csdn.net/colorant/
最近了解了一下基于HBase的分布式事務的實作方案，首先當然是要看一下google的percolator的paper了，順便了解了一下幾個相似的開源實作。
關鍵字
Percolator,BigTable, 分布式事務, 增量計算
== 目标問題 ==
Percolator的目标是在海量規模的資料集上提供增量更新的能力，并通過支援分布式的事務來確定增量處理過程的資料一緻性和整體系統的可擴充性。
這個目标的需求來源于對谷歌的網頁索引系統的改進，此前谷歌的網頁索引系統采用的是基于MapReduce的全量批處理流程，所有的網頁内容更新，都需要将新增資料和曆史全量資料一起通過MapReduce進行批處理，帶來的問題就是網頁索引的更新頻率不夠快（從爬蟲發現網頁更新到完成索引進入檢索系統，需要2-3天或者更長的周期）
== 核心思想 ==
建構這樣的系統，本質的需求是
- 首先，底層的存儲系統中，資料集本身必須是可以水準擴充，并支援增量更新的
- 其次，要保證增量處理的吞吐率，必然需要支援大量并發的資料更新操作（這點和基于MR的處理過程不一樣），在這種應用場景下，分布式事務的支援也就成為了一個必須要支援的特性，通過分布式事務的支援，可以大大降低業務開發的難度，減少并發任務可能帶來的資料一緻性問題，本質上是為了保證整體系統的可靠性和易用性。
- 最後，Percolator的目标還包括提供一個增量處理的流程架構模型，用于驅動實際應用邏輯的運轉。
對于上述需求，傳統的DBMS可以滿足事務的需求，但是處理不了海量規模的資料；MR相關的批處理系統難以做到高效的增量更新；BigTable類的NoSql技術支援海量規模資料的增量更新，但是不提供跨行跨表的分布式事務的支援。
Percolator的架構以BigTable為基礎，通過增強其對分布式事務的支援能力來達到同時滿足海量資料，增量處理，事務支援這三個需求目标。
由于BigTable本身提供行級别的事務支援，此外還提供資料Version的概念，是以Percolator自然的實作就是借助MVCC的思想，在BigTable的行鎖基礎上增加跨行和跨表的Snapshot級别的事務隔離。
MVCC的思想在傳統DBMS中久已存在（Oracle／MySql等等），即使在谷歌自己的BigTable體系之上，也先後有MegaStore／Spanner等系統通過MVCC的思想來支援跨行事務，與MegaStore／Spanner等通過Paxos＋MVCC來實作事務支援不同，Percolator的實作采用的是兩階段送出＋MVCC，這麼做大概是在滿足應用需求的基礎上，降低開發實作難度？
Percolator在效率方面沒有做很精細化的考慮，是以和MegaStore類似，是通過功能疊加的形式，在BigTable的節點上運作Percolator的Worker來封裝對BigTable的使用，以增強事務支援的（相比之下，Spanner沒有通過BigTable來管理資料，而是直接管理了底層tablet）
此外由于MVCC對嚴格遞增時間系列的需求，整個體系中需要增加TimeStamp Oracle 時間戳服務。
而兩階段送出對鎖的管理産生的額外需求（主要是對失效worker遺留的鎖的清理）是通過Chubby server對worker的狀态監測來支援的。 綜上，整個Percolator的系統元件框圖（引用自官方相關PPT）如下：
== 實作 ==
實作上，percolator的分布式事務兩階段送出是通過在BigTable表内部每行資料中添加額外的column來标記相關的鎖資訊的。
簡單的來說，就是在事務開始的時候，會對涉及修改的所有行在:lock column上标記加鎖，然後在:datacolumn修改資料内容本身，最後在:write column上标記最新成功送出的資料的具體時間戳版本。這裡面涉及到的加鎖步驟，沖突解決，事務復原等細節，有興趣的自己看論文吧。
此外，事務的驅動架構，在Percolator裡面是通過一個稱為notification的機制來實作的，本質上就是表資料的變更會被使用者編寫的Observer觀察到，并觸發後續的事務。一個Percolator應用，會是由一系列的相關聯的Observers觸發鍊路串聯起來的。應用程式通過寫入起始的資料，觸發鍊路的第一個Observer，執行事務，進一步更新資料，觸發下一個Observer，直到完成整個應用邏輯。
在這條觸發鍊路上，每個Observer觸發的事務都是一個獨立的事務，Percolator不提供跨Observer的事務特性，也不負責處理比如Observer循環觸發等，這些邏輯的正确性需要由應用的實作方來保證。
為了實作notification機制，Percolator在BigTable的行資料内容上又額外添加了:notify和:ackcolumn用來起到通知變更和保證observer正确執行，具體細節同樣請參考paper原文。
== Trade off ==
Percolator的整體設計實作，是有明顯的取舍的，Percolator的增量處理流程在提高系統實時響應能力的同時，在性能上也付出了明顯的代價，如論文裡面提到的，基于2PC／MVCC實作的分布式事務方案在和底層BigTable，外部時間服務以及chubby鎖服務的互動上，引入了大量額外的讀寫操作，相對于直接讀寫BigTable，寫資料的代價約為400%，讀資料的代價增加的不多，約5%。
從工程的角度來看，Percolator也做了大量如Timestamp批量擷取，BigTable API改進，批量上鎖，延遲清理沖突，資料預讀取等優化，以緩解高并發增量系統引入的小批量資料操作和随機讀寫等行為帶來的額外性能問題，但是這些措施在一定程度上反過來也會影響整體系統的latency響應速度。（Percolator的定位不是對latency有很高要求的系統，允許幾十到上百秒的不确定的Latency延遲）
總體而言基于Percolator改進的網頁索引系統Caffeine在處理同樣規模和吞吐率的資料時，相對于原有的基于批量MR處理流程建構的系統，大概需要2倍左右的機器資源（但是latency的改進可以提高100倍以上）。
== 相關研究，項目等 ==
## 小米的Themishttps://github.com/XiaoMi/themis
Themis基本上就是percolator在HBase上的一個實作，但是相應的實作的是分布式事務着一部分，沒有實作notification／observers機制。在Hbase Jira上也開過一個相應的Issue：https://issues.apache.org/jira/browse/HBASE-10999
在TimeStamp時間方面，使用的是小米自己開發的chronos https://github.com/XiaoMi/chronos
總體架構上與Percolator不同的地方是在事務的實作方面，不完全是在client Librery中，單行的事務處理基本是通過Hbase Coprocessor來實作的（比如對字段加鎖，清除鎖之類），在用戶端client library中不需要相關的處理邏輯。
此外在實作細節方面，也做了一些工程上的變化，比如TimeStamp Server可以配置為本地的服務（要補充一下适用場合），對Prewrite階段的locker，沒有選擇持久化。隻寫入memstore中以提高性能等
在應用方面，比如實作了給MR任務使用的InputFormat和OutputFormat，然後由于支援了跨表的事務，是以他們也嘗試了通過Themis建構HBase的二級索引，做為一個獨立的子產品 Themis-indexer
至于小米内部将Themis應用在哪些具體的應用場景中，有機會要去了解一下。
## 南韓人的Haeinsa https://github.com/VCNC/haeinsa
Haeinsa的實作，主要思想和流程與percolator接近，通過樂觀鎖和兩階段送出來實作事務支援，但是在具體實作上進行了簡化處理。
首先它去除了Time Oracle，也就是說全局時間戳服務的部分，是以伺服器時間的同步需要由外部的機制來保證（比如NTPD）
其次上鎖的機制也做了簡化，隻有一個lock column用來辨別鎖的狀态，送出的資料的版本等等資訊，因為鎖資訊進行了簡化合并處理，需要在用戶端緩存讀取的lock辨別的資訊，用于在送出階段進行判别。
簡化了崩潰恢複機制，鎖逾時5秒以上就認為是錯誤逾時事務，會被其它事務清除任務狀态。
總體而言，因為用戶端需要緩存資料，涉及到兩次讀取操作，錯誤恢複機制也比較簡單，是以Haeinsa的使用定位也有一定的局限性，展現在：
每次事務處理的資料量不能太大（幾百行）
事務時間超過5秒的話，容易被其它事務打斷，對機器的時間同步要求也比較高。
加鎖的機制決定了事務的隔離級别是Serializable（這個如果要反過來說，事務級别的設定決定了整體方案的設計也可以。。。）是以比較适用于并發事務的沖突機率比較低的場合。回來說Serializable這個級别，Haeinsa貌似也解決不了幻讀的問題。
## Yahoo的OMID https://github.com/yahoo/omid
OMID的思路和percolator有着很大的差別，整體架構目标是LockFree的，在Yahoo内部的應用據說也比較成熟，篇幅問題，另外單獨再寫一篇學習文檔來比較 ：快速了解 Omid: Yahoo在HBase上的分布式事務方案
## Saleforce的Phoenix http://phoenix.apache.org/
Phoenix的事務的支援基本等于沒有，要說有也隻是read committed的，因為事務内資料變更的送出是在用戶端合并操作以後，在commit階段統一寫入HBase的，也就是可以支援一定程度的放棄事務復原資料的支援（根本就沒送出給HBase嘛，就是放棄操作而已）。除此之外，不提供任何HBase本身功能以外的事務支援，雖然在過去的各種road map future work中一再都提到要加強事務的支援。
## 淘寶的oceanbase
這個，就是淘寶自己搞的一套東西了，和HBase完全沒有關系，一開始的設計目标就是要支援事務，找時間仔細研究一下。