深入了解分布式事務Percolator(三)

轉載請附本文連結：https://blog.csdn.net/maxlovezyy/article/details/99707690

本人在位元組跳動，歡迎加入我司，歡迎自薦，私聊即可。

實作篇

這裡設計實作的時候充分借鑒了TiDB相關的設計，當然也有一些自己的思考。

本篇在前一篇做了一些思考後，詳盡地講述一下分布式事務Percolator的具體實作，充分地考慮了工程問題。如果你是分布式的新手，相信在消化吸收之後會有一套自己對分布式事務以及分布式系統的注意點和設計有一個更深刻的認識。

資料模型

data	lock	write
key	{encoded_key}{start_ts}	{encoded_key}	{encoded_key}{commit_ts}
value	{value}	{flag}{pk}{start_ts(varint)}{ttl(varint)}{min_commit_ts(varint)}{committing}{has_short_value}{short_value}	{flag}{start_ts(varint)}{short_value}

每一個列對應資料層的3個列，意義參考Percolator。這裡value相對于Percolator做了細化，主要是針對異常以及mvcc做的設計。

• lock value:

  flag

  觸發上鎖的動作，類型為put、delete、lock；

  pk

  即Percolator中的primary key；

  ttl

  是lock的生命周期，用于清鎖逾時等判定；

  min_commit_ts

  用于優化讀事務，寫不阻塞讀，

  committing

  用于配合防止不停commit失敗；

  has_short_value

  是針對short_value為empty時的效率優化(load prewrite的時候不需要額外load data列來判斷data是否為空)；

  short_value

  是針對小value的優化，不寫data列，直接放到write裡。
• write value：flag類型為put、delete、lock、rollback；short_value參考lock value。
• 各個列key中的ts都是memcomparable的編碼方式

關鍵設計

1.MVCC

目前大多數分布式事務都主要支援SI隔離級别，Percolator也一樣，其通過mvcc機制實作SI隔離，達到讀寫互不幹擾，提高并發能力。Row或者cell的不同版本通過單調遞增的ts辨別，為了保證事務的一緻性，删除的時候并不in-place删除，而是标記删除。因為如果直接删除了，可能會導緻其他的讀事務得到不一緻的資料，比如事務T1先後讀a和b兩行資料，假設是in-place删除，可能在T1讀a和b中間，另一個事務T2把b删除了，之後T1再讀b的時候就會拿到了不一緻的a和b的視圖。

2.Lock列flag字段

Lock列的value為什麼要有flag呢？假設沒有這個flag辨別請求類型，通過事務client發請求commit時固然沒問題，因為client可以緩存并傳遞過來，但是加入client已經把primary送出了，之後就挂了，當resolve lock的時候就沒有辦法決議請求類型了，是以lock列需要儲存類型flag。

3.Lock

為了應對select … for update的需求(對于lock in share mode是不需要應對的，參考FAQ2)，需要支援行鎖，這裡拿具體例子來說，假設有如下事務：

txn start

select a … for update

update b …

txn commit

由于樂觀的模型，遇到select a … for update之後依然隻是添加了一項mutation，type是lock，遇到update b … 的時候依然是一項mutation，type是put，等到commit的時候走2PC。由于a又一個lock類型的mutation，是以prewrite的過程是完整存在的，如果過程中有其他事務先行執行了并與本事務的a mutation沖突了，則本事務失敗，整個過程類似于一個CAS的過程。至于為什麼write列要有一個Lock類型的記錄，而不是在a mutation送出的時候直接删除a的lock列，請看FAQ4。

範圍級的鎖(比如表鎖和range鎖)和row級别的是各自獨立的，範圍級的鎖走分布式鎖的思路，在外圍做鎖管理，并不沖突。具體實作的時候，假設支援了範圍級鎖，對于不需要範圍級鎖的業務也可以通過hint或者配置的機制繞過對範圍級鎖check的性能損耗。

4. 死鎖/活鎖避免

不同僚務之間可能出現互相依賴的死鎖情況。比如兩個事務t1和t2都依賴a和b兩個資源，t1先拿到了a的鎖，同時t2拿到了b的鎖，這樣就陷入了死鎖。

這種情況對于本事務模型存在嗎？顯然是不存在的。Percolator對于并行事務的寫沖突的處理辦法是遵循First-Write-Wins(FWW)原則來防止lost-update異常，又因為目前設計都是事務接口通路存儲層的鎖，會通過這種類似樂觀的方式發現鎖沖突并取消自己，是以事實上Percolator是不存在死鎖的情況的。但是卻存在活鎖的情況，就是t1和t2互相沖突來回取消。

對于上面提到的活鎖，一個naive的解決辦法就是每一個事務都對其所有buffer的row進行全排序且按序prewrite，這樣first prewrite的txn就會win。但存在的問題一個是one by one的方式性能太差，一個是存在大事務buffer過大的資源限制和排序性能損耗。

本設計采用的辦法是參考了常用的解決死鎖的兩個方法：Wait-Die和Wound-Wait，采用的是Wound-Die的方式。即對于任意一個事務，如果在prewrite的時候遇到比它年輕的事務加了lock，則嘗試直接強制resolve lock(不等)；反之則abort自己。可以看出，解決的原理就是對并行事務進行優先級的排序。為什麼不采用Wait-Die或者Wound-Wait？因為Percolator為了通過FWW的方式解決lost-upadte異常，是以wait的事務之後必然會沖突，沒有任何wait的意義。

5. 單條GC

由于mvcc機制，随着服務的運作，會有越來越多的備援資料存在，必須有垃圾回收機制對舊版本的無用資料進行清除。GC設計的關鍵是找一個safepoint，之後開始清除全局的所有key對應的write列ts小于safepoint的資料。

1. 準備階段

   事務的送出是2PC，在commit的過程中是可能出現某個Secondary commit過程中崩潰把lock和data留下的情況，這種情況是需要讀請求去resolve的。在GC過程中如果遇到了lock時間戳在safepoint之前的這種鎖，就必須進行resolve，所有涉及GC的row都resolve之後才可以進入執行階段。因為如果不resolve，存在其primary的write記錄被GC掉了導緻這個未決議的Secondary無法決議，資料不一緻出現的情況。

2. 執行階段

   GC遇到類型為put的記錄不能直接删除，因為有可能這是唯一一個記錄，删除了資料就丢失了。GC遇到類型為delete的記錄也不能直接删除，需要删除比其ts小的其他記錄後再删除本記錄，因為如果其後面跟着一條類型為put的記錄，這時候如果先删除目前delete記錄，則後面的put就是可見的了，這是錯誤的。具體流程如下：

   初始化can_remove = false，need_delete_ts = invalid, next_ts = safepoint

   i.掃描小于等于next_ts的版本，如果為空，則轉到iv；否則得到目前key的commit_ts，next_ts = commit_ts - 1轉到ii

   ii.如果can_remove為true，則删除目前版本的key，後轉到i；如果can_remove為false，則轉到iii

   iii.如果目前資料類型為put，則标記can_remove為true，後轉到i；如果類型為delete，則标記can_remove為true，設定need_deleted_ts為commit_ts，後轉到i；如果類型為rollback或lock，删除commit_ts資料，後轉到i

   iv.如果need_deleted_ts有效，則删除need_deleted_ts版本的資料(清理前面遇到的delete類型的write，delete不能直接删，需要GC的最後删，否則會暴漏它下面的類型為put的write)，GC結束

6. 分布式GC

a.safepoint

一般而言可以配置一個mvcc的多版本資料的生命周期，通過TSO的now減去lifetime得到safepoint。Lifetime也必須大于事務的最大生命周期，這樣能保證每一次的GC遇到ts小于safepoint的包括primary row可以直接處理，無需擔心一緻性（參考FAQ6）。

當然，safepoint的确定不能單單是通過【目前所有事務的start time的最小值】 确定，還需要考慮未決議的鎖。因為假設資料現場是下圖這樣，如果gc的safepoint确定為7，那麼一旦k1的write列[email protected]被gc之後，k2就沒法決議了。是以gc發起之前要掃描叢集所有小于初始safepoint的鎖，有的話就resolve，等都resolve了就可以執行gc了。

b.分布式

對于上面提到的naive形式的GC，有幾個顯而易見的問題：

i.單點處理GC邏輯，叢集大的時候可能受限于CPU、網絡、QoS(比如可能有表格存儲服務針對單ip的限流)等方面導緻忙不過來，叢集的GC速度過慢

ii.當叢集資料量大了或者負載高的時候，可能出現一輪GC時間過長，具體執行partition GC時有滞後情況的出現。比如目前判定GC的safepoint是t1, 當GC處理某一tablet資料的時候，其實時間已經很滞後了，這時候其實safepoint早都可以更新為t2了，tablet掃出來的時間小于t2的資料而非小于t1的資料其實都可以清理了。

針對上面提到的問題，可以通過下面的優化點解決：

i.safepoint的計算獨立出來

ii.GC master實時根據safepoint計算生成tablet級的GC task

iii.GC worker向master認領GC task

7. 長事務的支援

由于TransactionProxy需要緩存mutations，記憶體空間有限，如果支援的話就需要分批prewrite并記錄key(keys空間很大還需要持久化)而非commit的時候再一起。另外為了避免GC等導緻resolve長事務，需要為其lock續ttl或者壓根寫死大事務lifetime上限(存在挂掉之後事務很久不結束的可用性問題，但心跳續ttl不存在此問題)。大事務的方案需要解決三個問題：

1. 目前mutations是完全緩存在記憶體的，對于大事務理論上proxy的記憶體是會撐不住。

   解決方式有兩種，一種是限定大事務的最大batch大小，比如說1G。目前的伺服器支援這樣的大小應該都還OK。還有一種是分批prewrite，但這裡有一個問題就是不能全局排序，導緻可能出現活鎖，或者性能問題。比如兩個事務有交疊，a、b、c，如果一個事務t1 prewrite了b，另一個事務t2 prewrite了a、c，假設t2 prewrite b發現沖突之後abort，可能與此同時t1也發現了a、c沖突abort b，都失敗了。而如果全局排序了，以order的方式進行prewrite就不會有這個問題。一期先全攢在記憶體。

2. 每一個事務根據大小都有一個預設的ttl為了防止事務的coordinator hang或者crash。對于大事務會有lifetime大于初始ttl，導緻事務中途大機率會被resolve的情況。

   通過keep-alive的方式解決這個問題。Coordinator會啟動一個異步線程對primary的ttl進行續約，同時也會結合GCMaster把safepoint統一起來，以防止是以帶來的資料不一緻和可用性問題。

3. 大事務會影響讀的可用性。因為Percolator的設計上目前讀遇到鎖是需要等待或lock逾時進行resolve的，是不可以直接傳回最新資料的，會出現幻讀、不可重複讀問題。

   通過給lock列加一個min_commit_ts解決這個問題。當讀遇到lock的時候，就把min_commit_ts改成讀事務的start_ts + 1。當寫事務commit的時候遇到由于commit_ts expire錯誤時修改commit_ts為min_commit_ts再進行commit。這裡可能存在的一個問題就是對于熱讀可能導緻commit頻繁失敗重來。可以在lock列增加一個committing狀态位，當commit發起失敗是因為commit_ts expire導緻的，則改committing狀态為true，如果處于committing了則不可以更改min_commit_ts了。

4. 大事務會影響GC的回收時效性。因為樸素的實作方式下GC需要先resolve所有在next candidate safepoint時間點之前的lock之後才可以進行GC，否則有可能把primary的commit(Percolator write列) ROLLBACK/COMMIT記錄删掉了但secondary的lock還在進而無法決議了的問題。

   參考3中提到的優化，resolve lock時可以這樣解決此問題。對于primary lock在的情況，直接提高primary lock的min_commit_ts到一個大于next candidate safepoint的值即認為GC需求下的resolve lock行為成功了；對于primary lock已經不在了的情況(已送出或復原)，直接resolve secondary即可。所有在next candidate safepoint時間點下的lock都resolve了之後就可以以它作為ready的safepoint進行GC了。與此同時大事務/長事務依然沒有被cancel掉。

   值得注意的是，直接這樣做其實隐藏了一個問題就是這樣做會破壞一緻性快照，出現幻讀。 為什麼呢？比如目前有一個事務時間戳是t1，它是可以見到時間戳小于等于t1的資料的，但其實當時可能有t2版本的資料存在的。如果通過上面的方式使得大于t2時間的safepoint得以生效開始GC，那麼t1版本的資料會被回收掉，會導緻事務出現幻讀。解決這個問題其實也很簡單，而且這其實是一個普适的解決方案：每個事務在送出的時候都需要去gc master擷取一下目前的safepoint，如果safepoint大于事務的start_ts，則可能有問題，事務需要abort。為什麼說是普适的呢？因為即便沒有本優化，對于一個事務，如果單單靠定死的逾時來控制gc帶來的可能的破壞快照的問題也是會存在問題的，因為client和server是可能存在時鐘漂移的，gc master開始生成新的safepoint并開始gc的時候safepoint之前開始的事務的client可能還沒有逾時，它有可能讀到被GC破壞了的快照。是以要保證絕對的一緻性就必須在送出的時候擷取一次safepoint進行比較。那麼有沒有可能某一個事務頻繁地被這種case(safepoint更新)abort呢？對于小事務，一般是不會的，retry大機率會成功，因為gc周期就算再小也不會太小(比如60s夠不夠小)，retry很難碰上safepoint再次更新。如果這時候要有一個稍微大的事務(執行時間超過了gc周期)進來确實是可能會出現一直被abort無法成功，但這個問題其實不能算是本優化引入的問題(但也算是因本優化而起，因為本優化的目的就是要縮短gc周期以應對高ops系統的gc回收遲滞導緻版本過多性能退化問題)，而是gc的周期設定本身就和業務不相配的問題，也可能是gc周期是靜态的，本身太泛泛，無法滿足各種case。這種其實可以提供一種hint機制讓使用者可以顯式地動态修改gc的周期，甚至系統可以主動探測到這樣的問題進行自動優化。

   不過這裡其實還隐藏了另外一個問題，那就是大事務本身會被abort的問題，一旦提升safepoint，大事務本身也就會被abort了。 怎麼辦？可以有一個比較trick的解決方案，就是每一個事務都要向gc master申請一個指定ts的gc lock(事務的start_ts即可)，gc master的safepoint不可以大于所有gc lock的最小時間。什麼時候解鎖呢？當事務進入到committing狀态時或者幹脆加一個類似于FreezeRead接口(不會再有讀了)就解鎖。

   到這，也會驚喜地發現這樣解決的話上一個問題也就不是問題了哈哈。

8. TSO

a. Leader批量擷取範圍ts，以避免每次get ts都需要走raft。另外為了避免單機擷取時間的系統調用有瓶頸，可以把ts做一個變換，僅保留毫秒或秒級的精度，其餘位由該毫秒或秒内的一個單調遞增的數字取代。感覺秒級精度完全能滿足GC對于時效性的需求，還有什麼其他問題沒？ts其實需求就是一個單調遞增的數字即可，如果不是GC有時間概念，ts完全可以僅是一個單調遞增的數字。這裡其實還可以有一種設計：TSO配置設定的ts就隻是一個純粹的單調遞增的數字，但是定期(比如秒級)去記錄目前秒内所配置設定的ts邊界并同步GC master，由于ts和時間都是單調遞增的，是以GC的時候可以通過GC master擷取到safepoint點内最大已配置設定的ts，再進行GC，這樣設計ops可能又會高很多。如果實在是要支援超高ops，也可以将ts擴充為<ts, id>的組合，其中id為uint64_t類型單調遞增的數字，這樣的話不考慮其他瓶頸因素理論上每秒可以支援uint64_t::MAX_VALUE的ts配置設定ops。目前采用秒級時間戳+id組合在一個int64_t中的方法。

b. TrueTime、extend HLC。好處是不沖突的情況下支援的 ops會增加，但是引入的問題是時間架構的複雜性以及請求增加的額外延遲。

9. 跨表事務

在Lock列value的primary中增加表資訊。

10. 共享事務

有多個不同TransactionProxy client共享一個事務的需求。這個需求對整體事務模型來說是不具有侵入性的，看起來也是一個分布式下合理的需求。各個client可以共享一個事務session，session id其實就是事務的start_ts。有兩個的方案（暫不考慮大事務）如下：

方案一

• Client

1. Client leader(request proposer)建立一個【共享】txn，記錄session
2. Client leader向worker分發請求，其context中帶有txn的session
3. Client worker各自通過session發起join txn請求，發起資料操作請求
4. Client leader收集worker的response發起commit/abort

• TransactionProxy

1. 建立的事務類型為共享事務，通過TransactionManager™建立事務session
2. 各個proxy有txn join之後，向TM注冊
3. 各個proxy對于讀立即執行，對于mutations緩存下來
4. TM收到commit之後，對注冊在此session的Proxy發起PreCommit請求
5. 各個proxy收到PreCommit請求之後回複一個推薦的primary
6. TM确定一個primary，對其發起prewrite
7. Primary proxy成功後傳回TM結果
8. TM對所有secondary并行發起prewrite，TM根據各個proxy的結果決定commit/abort
9. TM對primary發起commit/abort，傳回給client leader結果，并根據結果對secondary作出相應處理

方案二

與方案一相比，方案二把各個client的事務請求歸到了同一個proxy上，session中加入了proxy的ip，txn client sdk在處理的請求的時候通過session中的ip處理，這樣與方案一的【TransactionProxy側】相比，不需要TM的存在了，因為所有mutations資訊都在一個proxy之中了。

當然上述方案細節上還需要考慮各種逾時以及錯誤等cases，TM也是一個故障域和可能的性能瓶頸點（假如采用方案一）。另外對于大事務不能完全緩存mutations的情況下，也能有效支援，無非就是提前選一個primary分批次prewrite而已。

FAQ

Q1 為什麼需要持久化對資料的lock到lock列，而不是僅僅在記憶體中？

A1 分布式的情況下，同一個事務的資料分布在不同的伺服器上，如果lock僅僅在記憶體中，那麼一旦某個secondary row所在機器挂了，lock資訊就丢了，原子性也就沒了。而且Percolator的lock列設計巧妙，lock中包含了primary資訊，能把同一個事務中的資料串起來，這個串起來的資訊也是必須持久化才能保證一緻性(比如如果不持久化，假設primary已經commit，未送出的secondary挂了重新開機之後不知道自己的狀态了)、原子性的。

Q2 鎖的實作隻提到了for update的寫鎖，lock in share mode的讀鎖呢？

A2 這就是SI隔離的好處，讀是針對快照的，mvcc的寫不會與讀沖突，故不需要讀鎖。

Q3 為什麼write列需要寫rollback标志的資料？

A3 可防止處理遲到的無用prewrite。當然也可以不寫rollback标記，有resolve邏輯不會影響正确性。

Q4 在lock的實作中，為什麼write列需要寫lock類型的資料，而不是commit的時候直接清除lock列類型為lock的資料？

A4 由于Percolator的mutation是buffer在client端的，一次性prewrite擷取鎖，整體上等于是樂觀鎖模型，是以沒辦法在事務中遇到select … for update就先在資源層lock住，隻能造一個write type為lock類型的記錄，在txn commit的時候根據prewrite的這個lock mutation做一個類似CAS的check，失敗了說明這個txn開始的select … for update失敗了。至于commit時為什麼要真正把這個lock寫到write裡而不是遇到lock列的類型為lock直接簡單删除，原因是如果不在write列寫入一個commit，可能有stale的txn送出資料。而且有了這個标志還能保證幂等性，commit之後再commit不會出錯。對于可以防止stale txn送出資料的情況，可參考如下例子(站在client使用的視角)：

1. Txn1
          t2 : create
          t3 : select a ... for update
          t5 : if(a.exist) update b.pid = a
          t6 : commit.prewrite(client commit事務之後proxy的第一階段)
          t7 : commit.commit(client commit事務之後proxy的第二階段)
      2. Txn2
          t1 : create
          t4 : select a ... for update
          t8 : if(a.child == empty) delete a
          t9 : commit.prewrite
          t10: commit.commit
           

如果txn1 commit的時候不在write寫入lock類型的a，那麼txn2這個start_ts小于txn1 start_ts的事務是可以送出成功的。這樣txn1和txn2就依然有write skew的問題，b.pid指向的parent a還是會被删除掉而b成了孤兒。是以lock類型的mutation送出的時候必須在write列寫入類型為lock的記錄。

可能有的人會想語義上來看是沒必要必須失敗一個事務的啊，假設是Mysql非SI隔離級别比如RR級下這樣做結果會是兩個事務都成功，而本事務模型為什麼出現這種case就必須失敗一個？其實本質原因就是本文設計的事務是lazy的CAS check形式的鎖，select … for update一行讀取到的資料在當行及以後的使用中并沒有處于受保護的臨界區之中，而Mysql非SI隔離級别下則不同，其會是直接先lock住for update的row，之後的處理都處于lock的保護之中，不會出現隔離和一緻性問題，是以都會成功，而本文涉及的事務模型就必須失敗一個才能保證一緻性。

Q5 為什麼不能in-place删除而要标記删除？

A5 假設是in-place删除，可能在T1讀a和b中間，另一個事務T2把b删除了，之後T1再讀b的時候就會拿到了不一緻的a和b的視圖。

Q6 GC可不可能resolve的時候，判定事務逾時了，進而rollback了事務導緻一緻性問題？GC可不可能回收了某個doing的start_ts小于safepoint的事務涉及的row的舊版本，進而 導緻本能讀取到這個row的一緻性舊版本卻讀不到了？

A6 第一個問題不是問題，因為不會導緻資料的不一緻。第二個問題也不是問題，可以把lifetime設定的長一點，保證gc回收到的隻能是老資料，保證safepoint之前的所有事務都要麼已完成，要麼已經處于逾時的失效狀态。對于失效狀态的事務，用戶端也造就cancel了，即便讀到不一緻的視圖也無所謂， 因為使用者壓根見不到。

Q7 事務與二級索引的關系是怎樣的？

A7 二級索引屬于在另一套名字空間下的資料。如果要維護二級索引與資料的強一緻性，那就需要跨表事務的支援。如果僅需要異步的二級索引，則二級索引的建立和事務沒關系。

Q8 事務的lock ttl如何考慮？GC的lifetime如何考慮？

A8 事務lock的預設ttl應該配置為大于業務上一般情況下事務執行生命周期的一個值；GC的lifetime應該配置為大于事務ttl的一個值。這裡涉及到了可用性與一緻性了解上的語義問題，是以需要服務和業務方仔細斟酌配置。