Percolator是Google在2010年發表的論文《Large-scale Incremental Processing Using Distributed Transactions and Notifications》中提出的一種分布式事務解決方案。在論文中該方案是用來解決搜尋引擎的增量索引問題的。
Percolator支援ACID語義，并實作了Snapshot Isolation的事務隔離級别，是以可以将其看作是一種通用的分布式事務解決方案。Percolator基于google自己的Bigtable來實作的，其本質上是一個二階段送出協定，利用了Bigtable的行事務。
Percolator 包含三個元件：
Client：Client 是整個協定的控制中心，是兩階段送出的協調者（Coordinator）；
TSO：一個全局的授時服務，提供全局唯一且遞增的時間戳 （timetamp）；
Bigtable：實際持久化資料的分布式存儲；
二階段送出算法中有兩種角色，協調者和參入者。在Percolator中，Client充當協調者的角色，負責發起和送出事務。
Percolator依賴于TSO提供一個全局唯一且遞增的時間戳，來實作Snapshot Isolation。在事務的開始和送出的時候，Client都需要從TSO拿到一個時間戳。
Bigtable從資料模型上可以了解為一個multi-demensional有序Map，鍵值對形式如下：
key由三元組 (row, column, timestamp) 組成，value可以是認為byte數組。
在Bigtable中，一行 (row) 可以包含多個 (column)，Bigtable提供了單行的跨多列的事務能力，Percolator利用這個特性來保證對同一個row的多個column的操作是原子性的。Percolator的中繼資料存儲在特殊的column中，如下：
（圖檔來自：https://research.google）
我們主要需要關注三個column，c:lock ， c:write ， c:data ：
c:lock ，在事務Prewrite的時候，會在此column中插入一條記錄
c:write ，在事務commit的時候，會在此column中插入一條記錄
c:data ，存儲資料本身
事務中所有的讀操作都會讀到一個 consistent snapshot 的資料，等同于Repeated Read隔離級别；
兩個并發事務同時對同一個cell寫入時，隻會有一個事務能夠送出成功；
當一個事務送出時，如果發現本事務更新的一些資料，被其他比其start time大的事務修改之後，則roll back事務，否則commit事務；
存在write skew問題，兩個事務讀寫的資料集有重疊，但是寫入的資料集沒有重疊，這種情況下，兩個事務都可以成功commit，但是互相都沒有看見對方寫入的新資料，這達不到serializable的隔離級别。但是snpashot isolation相對serializable有更好的讀性能，因為讀操作隻需要讀快照資料即可，不需要加鎖。
Percolator使用兩階段送出算法（2PC）來送出事務，這兩個階段分别為 Prewrite 和 Commit。
在Prewrite階段：
1）從TSO中擷取一個timestamp，将其作為事務的start_ts；
2）對事務中需要寫入的每行資料，都會在lock列中寫入事務的start_ts，并在data列中寫入新的資料并附帶start_ts，例如上面的14:"value2"。這些locks中會有一個被選作為primary lock，其他locks叫做secondary locks。每個secondary lock都包含一個指向primary lock的指針。
1. 如果需要寫入的資料中已經有一個比start_ts 更大的新版本資料，那麼目前的事務需要rollback； 2. 如果需要插入lock的行資料中已經存在一個lock，那麼目前事務需要rollback。
在Commit階段：
1）從TSO中擷取一個timestamp，将其作為事務的commit_ts；
2）将primary lock删除，同時在write列中寫入commit_ts，這兩個操作需要是原子的。如果primary lock不存在了，那麼commit失敗；
3）對所有的secondary locks重複上述步驟。
下面看一個具體的例子，還是一個經典的銀行賬号轉賬的例子，從賬号Bob中轉賬7 dollar到賬号Joe中：
1、在事務開始之前，兩個賬号Bob和Joe分别有10 dollars和2 dollars。
2、在Prewrite階段，往Bob的lock列中寫入一個lock (7: I am primary)，這個lock為primary lock，同時在data列中寫入資料 7:$3。
3、在Prewrite階段，繼續寫入secondary locks。往Joe的lock列中寫入lock (7:[email protected])，這個lock指向之前寫入的primary lock，同時在data列中寫入資料 7:$9。
4、在commit階段，先清除掉primary lock，并在 write 列中使用新的timestamp (也就是commit_ts) 寫入一條新的記錄，同時清除 lock 列中的資料。
5、在commit階段，清除掉secondary locks，同時在 write 列中以新的timestamp寫入新的記錄。
1）擷取一個時間戳ts。
2）檢查目前我們要讀取的資料是否存在一個時間戳在[0, ts]範圍内的鎖。
如果存在一個時間戳在[0, ts]範圍的鎖，那麼意味着目前的資料被一個比目前事務更早啟動的事務鎖定了，但是目前這個事務還沒有送出。因為目前無法判斷這個鎖定資料的事務是否會被送出，是以目前的讀請求不能被滿足，隻能等待鎖被釋放之後，再繼續讀取資料。
如果沒有鎖，或者鎖的時間戳大于ts，那麼讀請求可以被滿足。
3）從write列中擷取在[0, ts]範圍内的最大 commit_ts 的記錄，然後依此擷取到對應的start_ts。
4）根據上一步擷取的start_ts，從data列擷取對應的記錄。
Percolator的事務協調者在Client端，而Client是可能出現crash的情況的。如果Client在送出過程中出現異常，那麼事務之前寫入的鎖會被留下來。如果這些鎖沒有被及時清理，會導緻後續的事務無限制阻塞在鎖上。
Percolator采用 lazy 的方式來清理鎖，當事務 A 遇到一個事務 B 留下來的鎖時，事務 A 如果确定事務 B 已經失敗了，則會将事務 B 留下來的鎖給清理掉。但是事務 A 很難百分百确定判斷事務 B 真的失敗了，那就可能導緻事務 A 正在清理事務 B 留下來的鎖，而事務 B 其實還沒有失敗，且正在進行事務送出。
為了避免出現此異常，Percolator事務模型在每個事務寫入的鎖中選取一個作為Primary lock，作為清理操作和事務送出的同步點。在清理操作和事務送出時都會修改primary lock的狀态，因為修改鎖的操作是在Bigtable的行事務下進行的，所有清理操作和事務送出中隻有一個會成功，這就避免了前面提到的并發場景下可能出現的異常。
根據primary lock的狀态就可以确定事務是否已經成功commit：
如果Primary Lock不存在，且 write 列中已經寫入了 commit_ts，那麼表示事務已經成功commit； 如果Primary Lock還存在，那說明事務還沒有進入到commit階段，也就是事務還未成功commit。
事務 A 在送出過程中遇到事務 B 留下的鎖記錄時需要根據事務 B 的Primary Lock的狀态來進行操作。
如果事務 B 的Primary Lock不存在，且 write 列中有 commit_ts 了，那麼事務
A 需要将事務 B 的鎖記錄 roll-forward。roll-forward操作是rollback操作的反向操作，也就是将鎖記錄清除，并在 write 列中寫入 commit_ts。 如果事務 B 的Primary Lock存在，那麼事務 A 可以确定事務 B 還沒有成功commit，此時事務 A 可以選擇将事務 B 留下鎖記錄清除掉，在清除掉之前，需要将事務 B 的Primary Lock先清理掉。 如果事務 B 的Primary Lock不存在，且 write 列中也沒有 commit_ts 資訊，那麼說明事務 B 已經被 rollback 了，此時也隻需要将事務 B 留下的鎖清理掉即可。
雖然上面的操作邏輯不會出現不一緻的情況，但是由于事務 A 可能将存活着的事務 B 的Primary Lock清理掉，導緻事務 B 被rollback，這會影響到系統的整體性能。
為了解決這個問題，Percolator使用了Chubby lockservice來存儲每個正在進行事務送出的Client的存活狀态，這樣就可以确定Client是否真的已經挂掉了。隻有在Client真的挂掉了之後，沖突事務才會真的清除掉Primary Lock以及沖突鎖記錄。但是還可能出現Client存活，但是其實其已經Stuck住了，沒有進行事務送出的動作。這時如果不清理掉其留下的鎖記錄，會導緻其他沖突事務無法成功送出。
為了處理這種場景，每個存活狀态中還存儲了一個wall time，如果判斷wall time太舊之後，則進行沖突鎖記錄的處理。長事務則需要每隔一定的時間去更新這個wall time，保證其事務不會是以被rollback掉。
最終的事務沖突邏輯如下：
如果事務 B 的Primary Lock不存在，且 write 列中有 commit_ts 了，那麼事務 A 需要将事務 B 的鎖記錄 roll-forward。roll-forward操作是rollback操作的反向操作，也就是将鎖記錄清除，并在 write 列中寫入 commit_ts。 如果事務 B 的Primary Lock存在，且TTL已經過期，那麼此時事務 A 可以選擇将事務 B 留下鎖記錄清除掉，在清除掉之前，需要将事務 B 的Primary Lock先清理掉。 如果事務 B 的Primary Lock存在，且TTL還未過期，那麼此時事務 A 需要等待事務 B 的commit或者rollback後繼續處理。
TiKV底層的存儲引擎使用的是RocksDB。RocksDB提供atomic write batch，可以實作Percolator對行事務的要求。
RocksDB提供一種叫做 Column Family(CF) 的功能，一個RocksDB執行個體可以有多個CFs，每個CF是一個隔離的key指令空間，并且擁有自己的LSM-tree。但是同一個RocksDB執行個體中的多個CFs共用一個WAL，這樣可以保證寫多個CFs是原子的。
在TiKV中，一個RocksDB執行個體中有三個CFs：CF_DEFAULT、CF_LOCK、CF_WRITE，分别對應着Percolator的data列、lock列和write列。
我們還需要針對每個key存儲多個版本的資料，怎麼表示版本資訊呢？在TiKV中，我們隻是簡單地将key和timestamp結合成一個internal key來存儲在RocksDB中。下面是每個CF的内容：
F_DEFAULT: (key,start_ts) -> value
CF_LOCK: key -> lock_info
CF_WRITE: (key,commit_ts) -> write_info
将key和timestamp結合在一起地方法如下：
将user key編碼為 memcomparable 的形式；
對timestamp按位取反，然後編碼成big-endian的形式；
将編碼後的timestamp添加到編碼後的key之後。
例如，key key1和時間戳 3 将被編碼成 "key1\\x00\\x00\\x00\\x00\\xfb\\xff\\xff\\xff\\xff\\xff\\xff\\xff\\xfe"。這樣同一個Key的不同版本在rocksdb中是相鄰的，且版本比較大的資料在舊版本資料的前面。
TiKV中對Percolator的實作與論文中稍有差别。在TiKV中，CF_WRITE中有4中不同的類型的資料：
Put ，CF_DEFAULT中有一條對應的資料，寫入操作是一個Put操作；
Delete ，表示寫入操作是一個Delete操作；
Rollback ，當復原一個事務的時候，我們不是簡單地删除CF_LOCK中的記錄，而是在CF_WRITE中插入一條Rollback的記錄。
Lock
對于一個事務來說，我們不以one by one的形式去做Prewrite。當我們有多個TiKV節點時，我們會在多個節點上并行地執行Prewrite。
在TiKV的實作中，當送出一個事務時，事務中涉及的Keys會被分成多個batches，每個batch在Prewrite階段會并行地執行。不需要關注primary key是否第一個Prewrite成功。
如果在事務在Prewrite階段發生了沖突，事務會被復原。在執行復原時，我們是在CF_WRITE中插入一條Rollback記錄，而不是Percolator論文中描述的删除對應地鎖記錄。這條Rollback記錄表示對應的事務已經rollback了，當一個後續的Prewrite請求到來時，這個Prewrite不會成功。這種情況可能在網絡異常的時候會出現。如果我們讓Prewrite請求成功，正确性還是可以保證，但是這個key會被鎖定，直到鎖記錄過期之後，其他事務才可以再次鎖定此key。
當我們通路一個value時，我們需要先從CF_WRITE中找到key對應最新版本start_ts，然後從CF_DEFAULT中找到具體的記錄。如果一個value比較小的話，那麼查找RocksDB兩次開銷相對來說有點大。
在具體實作中，為了避免short values兩次查找RocksDB，做了一個優化。如果value比較小，在Prewrite階段，我們不會将value放到CF_DEFAULT中，而是将其放在CF_LOCK中。然後在commit階段，這個value會從CF_LOCK移動到CF_WRITE中。然後我們在通路這個short value時，就隻需要通路CF_WRITE就可以了，減少了一次RocksDB查找。
對于每個事務，我們需要先配置設定一個start_ts，然後保證事務隻能看到在start_ts之前送出的資料。但是如果一個事務隻讀取一個key的資料，我們是否有必要為其配置設定一個start_ts呢？答案是否定的，我們隻需要讀取這個key的最新資料就可以了。
為了保證Snapshot Isolation，我們需要保證所有的transactional reads是repeatable的。commit_ts應該足夠大，保證不會出現一個事務在一次valid read之前被送出，否則就沒發保證repeatable read。例如：
Txn1 gets start_ts 100 Txn2 gets start_ts 200 Txn2 reads key "k1" and gets value "1" Txn1 prewrites "k1" with value "2" Txn1 commits with commit_ts 101 Tnx2 reads key "k1" and gets value "2"
Tnx2讀取了兩次"k1"，但是得到了不一樣的結果。如果commit_ts從PD上配置設定的，那麼肯定不存在此問題，因為如果Txn2的第一次read操作發生在Txn1的Prewrite之前，Txn1的commit_ts肯定發生在完成Prewrite之後，那麼Txn2的commit_ts肯定大于Txn1的start_ts。
但是，commit_ts也不能無限大。如果commit_ts大于實際時間的話，那麼事務送出的資料新的事務可能讀取步到。如果不向PD詢問，我們是不能确定一個時間戳是否超過目前的實際時間的。
為了保證Snapshot Isolation的語義以及資料的完整性，commit_ts的有效範圍應該是：
commit_ts的計算方法為：
其中region_N_max_read_ts為region N上所有讀操作的最大時間戳，region N為事務所涉及的所有region。
對于非分布式資料庫來說，保證事務的ACID屬性是比較容易地。但是對于分布式資料庫來說，為了保證事務地ACID屬性，2PC是必須地。TiKV使用地Percolator算法就是一種2PC算法。
在單region上，write batches是可以保證原子執行地。如果一個事務中影響的所有資料都在一個region上，2PC是沒有必要的。如果事務沒有write conflict，那麼事務是可以直接送出的。
優點：
事務管理建立在存儲系統之上，整體系統架構清晰，系統擴充性好，實作起來簡單；
在事務沖突較少的場景下，讀寫性能還不錯；
缺點：
在事務沖突較多的場景下，性能較差，因為出現了沖突之後，需要不斷重試，開銷很大；
在采用MVCC并發控制算法的情況下也會出現讀等待的情況，當存在讀寫沖突時，對讀性能有較大影響；
總體上Percolator模型的設計還是可圈可點，架構清晰，且實作簡單。在讀寫沖突較少的場景下，能夠有還不錯的性能。
1. Codis作者首度揭秘TiKV事務模型，Google Spanner開源實作
2. Google Percolator 事務模型的利弊分析
3. Large-scale Incremental Processing Using Distributed Transactions and Notifications – Google Research
4. Database · 原理介紹 · Google Percolator 分布式事務實作原了解讀 (taobao.org)
作者：vivo網際網路資料庫團隊-Wang Xiang