PolarDB-PG分布式整體架構
PolarDB-PG開源是一個分布式的資料庫，第一期開源是單機和三節點高可用的部分，但是現在開源的單機的部分已經具備了支撐分布式的一些基本功能，包括基于時間戳的MVCC，以及事務可見性方面的一些特性。
本文會介紹單機如何支撐分布式事務，以及如何保證可見性、一緻性等特性，這些在開源的代碼裡面也已經有了，我們在後期會把分布式協調節點的邏輯開源，就可以真正地跑起一個分布式的資料庫，并且保證分布式事務全局一緻性，提供ACID特性。
基于送出時間戳的MVCC的設計動機
我們基于送出時間戳的MVCC的設計動機有兩個，一方面是改進單機的性能，就是消除基于快照的多核可拓展瓶頸，Postgre采用的是基于ID的快照來保證事務的隔離性，這樣的話會有一些快照的生成，還有生成的瓶頸。
另一方面，我們在單機上支援基于時間戳的分布式事務協定。這樣的話，我們既可以單機來跑，在部署成分布式以後，也可以去支援分布式事務。
消除基于快照的多核可擴充瓶頸
可以看到傳統PG基于快照的一些瓶頸，MySQL也是一樣的，都會從運作事務清單裡擷取一個快照來獲知在事務或語句開始的時候，目前正在運作的事務。
這樣的話會有一個問題，就是它會去加 Proc Array 的鎖去周遊，雖然是共享鎖，那麼這在高并發下就有一個周遊的開銷。
另外一個就是共享鎖的競争，因為事務在結束的時候需要加互斥鎖去清理，那麼這個時候就會造成鎖的競争以及擷取快照的開銷，O（N）的開銷，即要周遊N個Proc。
支援基于時間戳的分布式事務協定
我們在分布式場景下也是一樣的，如果在分布式場景也采用XID Snapshot的話，也會造成生成全局快照的單點GTM瓶頸，每個節點也需要通過網絡從GTM擷取一個分布式的快照，當叢集并發事務很高的時候，快照擷取的開銷也很大。
基于送出時間戳的MVCC
基于送出時間戳的MVCC的話，假如有任意的兩個事務T1、T2，T1送出的修改對T2可見的條件就會很簡單，就隻要T1的送出時間戳小于或等于T2的開始時間戳。事務開始和送出的時候，我們都會給它配置設定時間戳，對于單機資料庫，比如說現在開源的，我們就會采用一個原子變量來生成單調遞增的64位時間戳。
我們以一個事例來看，圖中有三個事務T1、T2、T3，我們可以看到T1、T2是串行的，相當于T2在T1結束以後才開始的，是以T1的修改對T2是可見的。T3和T2是并行的，這樣的話T3對T2不可見，我們可以通過時間戳來确定它的開始及結束的絕對順序，來保證可見性和隔離性。
送出時間戳存儲和通路
在基于時間戳的MVCC中，為了做可見性判斷，我們就要存儲每個事務的送出時間戳。
存儲的管理有空間配置設定、回收、持久化、故障恢複等。對于單機資料庫可以采用非持久化的存儲機制，就是PG社群裡CSN（Commit Sequence Number）的方案，它維護了一個對全局所有事務都可見的最小的Transaction Xmin。
當XID小于Transaction Xmin的送出時間戳的空間就可以回收，因為它對所有的事務都可見了，隻要它的XID小于這個，判斷它可見性的時候就可以直接判定為可見，是以就不需要存儲，它存儲送出時間戳的空間就可以回收，用來存儲其他事務的時間戳。
XID小于Transaction Xmin可以通過CLOG去判斷可見性，就是送出即可見。對于資料庫重新開機，重新開機之前送出的事務對目前正在運作的事務均可見。
對于一個分布式資料庫就不一樣，它需要一個持久化的存儲，為什麼？一是我們的每個節點是去中心化的，每個節點都獨立維護了自己的XID的配置設定，要去計算一個全局的Transaction Xmin不太可行。我們可能會有另外一種方法，就是用一個中心節點，比如說GTM，去維護全局唯一的XID，這樣的話計算全局Transaction Xmin就會有開銷。
同時分布式的邏輯就會很複雜，而且這樣的話XID消耗也會比較快。當規模很大的時候，比如幾百個節點的時候， XID消耗就會很快，因為32位的XID很快就會進入回卷的狀态。
當沒有全局XID配置設定的情況下，分布式資料庫中一個節點重新開機，重新開機之前的事務不一定可見，是以需要恢複送出時間戳去判斷可見性，是以一個理想的方案就是要把送出時間戳持久化存儲。
送出時間戳存儲設計與實作
可以看一下持久化存儲的系統。
最底層是送出時間戳的一個存儲，這是一個實體上的按頁持久化存儲，并且可故障恢複。上面Buffer層用來緩存通路過的實體頁面。
我們同時用了Hash-Partitioned的方法，實作多分區的LRU Buffer，來提高它的可擴充性，減少鎖競争。
事務在送出的時候就會以XID為Key，以CTS為值，寫入整個存儲中。在做MVCC Scan可見性判斷的時候，我們就會去存儲裡面去讀XID的Timestamp。為了加速，我們在Tuple Header裡也會緩存這些 Timestamp ，這就跟緩存CLOG的送出狀态一樣，就是為了減少對CTS的通路。
多核可擴充CTS buffer管理
接下來看一下多核可擴充CTS buffer的管理。
CTS在存儲上跟CLOG類似,是連續的空間，就是存儲32位連續XID的送出時間戳，每個XID占用8位元組去存儲它的Timestamp，實體上用連續的一些的檔案來存儲。同時将檔案邏輯上切分成一組實體頁，然後可以按需加載到LRU Buffer裡面。如果有一個全局的Buffer的話，我們可能會在LRU發生替換的時候，寫回的時候會有全局鎖的競争，在加鎖的時候等待IO的完成，這樣會序列化IO通路，并造成比較嚴重的可擴充性瓶頸。
我們實作了一個LRU多分區劃分。每個XID對應在一個固定的實體頁裡，然後實體頁再按照固定的算法映射到Hash-partitioned的LRU分區中，這樣的話我們可以去掉中心的競争，這樣每個分區可以獨立地進行LRU替換、刷盤、讀取磁盤，這樣可以消除全局鎖的競争，并且并行化IO處理。
多核可擴充性
上圖是一個實驗，我們在一個機器上，實驗是用戶端數目從1并發到128， LRU從1個LRU分區到64個LRU分區，但即便是不同的分區，它總的Buffer大小是一樣的。
在上圖中可以看到在不同并發（1~128）下不同LRU Partition的數目的吞吐。随着LRU的數目越多，它的性能和可擴充性越好。最下方的那條線就是單LRU，在32個并發的時候，它的性能就開始出現轉折，就會慢慢變差，甚至會并發越高性能越低，而多分區LRU會保證并發越高，性能能夠線性增長。
總體來說，我們可以保證性能更好，這樣頻繁通路CTS不會帶來很大的瓶頸和開銷。
CTS持久化和故障恢複
關于CTS持久化和故障恢複，我們每個事務XID在CTS中有四個狀态，分别是送出，終止，運作和2PC prepared。那麼在同步送出模式下，事務送出時間戳先寫入WAL，再寫入CTS，進而支援故障恢複。同時，我們用2PC record記錄來恢複CTS中prepared狀态。異步送出模式下就跟CLOG一樣，我們會去記錄最大送出的LSN，在CTS頁面在寫入磁盤之前，保證WAL已經持久化到該LSN。
CTS快速事務狀态查詢機制（1）
另外一個就是，我們相比社群CSN也好，PG也好，我們可以更好地做到快速事務狀态查詢。
Postgre SQL判斷事務狀态的時候，會結合CLOG和Proc Array去判斷，我們從CLOG中能夠擷取事務是否送出狀态，而判斷事務是否正在運作，需要周遊Proc Array來确定，判斷事務是否運作在tuple update，hot-chain pruning的時候關鍵路徑會被頻繁調用，造成 Proc Array鎖的競争，以及高并發下周遊開銷O（N）的時間開銷。
那PostgreSQL為什麼不能用CLOG來獨立地判斷事務是否運作，而要去周遊Proc Array呢？
這是因為CLOG中每個XID的Commit的狀态都是準确的,REDO可以恢複所有送出狀态，隻要送出了肯定都有。Abort的狀态就不一定了，因為Abort分為事務主動Abort，或者是報錯，它會記錄在CLOG中。但是資料庫Crash的時候，比如斷電或其他原因造成的事務abort，就來不及寫入CLOG， REDO也沒法恢複。對于CLOG中未寫入送出狀态的事務，它可能是正在運作，也有可能是Crash Aborted，這個時候我們就沒法通過CLOG去做判斷，是以PG需要結合Proc Array去判斷是否正在運作。
CTS快速事務狀态查詢機制（2）
我們設計了一種oldest active xid機制實作通過CTS O(1) 免鎖快速查詢所有事務狀态，可以去掉Proc Array的周遊。和CLOG一樣，CTS中送出事務狀态都是準确的，重新開機以後，我們可以确定一個oldest active xid。這個XID怎麼确定,就是通過 next xid, next xid也是故障恢複以後會确定下一個可用的xid初始化，并且要小于等于所有的2PC prepared xid。
故障恢複時，我們會把oldest active xid到next xid這一段區間裡面，CTS為0的全部會設成aborted，“P”就恢複成Prepared，“C”就恢複成Commit。“0”表示未設定，我們就認為它是在上一次故障的時候就aborted掉了還沒來得及寫，我們就把它主動恢複成abort。
運作時，小于oldest active xid的CTS，如果是非送出的，例如0，它 就是aborted，是在上一次crash aborted。如果大于這個的，就通過CTS直接去傳回。這樣的話我們就不需要去周遊Proc Array，Proc Array在高并發的時候開銷就會很大。這樣的話隻要O(1)的時間查詢就可以确定狀态是送出，abort還是運作，這樣性能會更好，并且會沒有鎖的競争。
CTS存儲空間回收
下面介紹CTS存儲空間回收。
因為我們是以XID為索引的Key，從2的32次方，PG會存在XID回卷，我們會跟着XID回卷去truncate CTS的空間。
PG的XID邏輯就是它有2的32次方的空間，它會一分為二，這樣它在回卷的時候保證可見性判斷。如上圖所示，next xid往上是它過去的xid，往下是它未來的xid。它不管怎麼轉，都是可以回卷，都可以正确比較兩個XID的大小。它會定期地建立一個Frozen xid cutoff，等于oldest xid減去一個配置的guc的一個Frozen參數，這樣把之前的xid全給回卷了。
并将之前回卷的XID在每個tuple中改成Frozen xid，這樣表示它對其它所有正在運作的事務均可見的，這一部分xid就被回收，可以再用了。
CTS就随着xid的邏輯，在它回卷的時候會把回收的XID空間對應的CTS存儲空間給Truncate掉，然後回卷的時候又重複利用來存儲送出時間戳。這樣的話就可以2的32方XID對應32GB的CTS檔案存儲就可以保證一直用下去，不會溢出。
基于CTS支援分布式全局一緻性事務（1）
我們基于CTS支援分布式全局一緻性的事務，相當于每個節點都會有個CTS，但是同一個分布式事務的送出時間戳是一樣的，比如1001。但是它在每個節點，XID是各自獨立配置設定的，各自獨立維護，但是它的送出時間戳是一樣的，可見性判斷都是全局一緻的。
開始和送出時間戳可以用中心化的時鐘GTM來生成，或者用混合邏輯時鐘HLC來生成。
基于CTS支援分布式全局一緻性事務（2）
我們目前主要開源的是HLC的版本，在分布式下，每個送出時間戳送出的實體時間并不一定完全一緻。比如T1在A節點和B節點，我們不能保證完全同時送出，另一個并發事務T2，可能會看到T1部分的修改，比如看到A送出了，看到了它的修改，但是B正在運作還沒送出，根據隔離性它不可見，此時就無法保證分布式的一緻性和隔離性。
我們可以采用2PC Prepare等待機制來解決全局送出一緻性：采用2PC來送出一個分布式事務，在Prepare階段，每個節點在CTS中寫入該分布式事務的Prepared狀态。Commit的時候，我們會去決策一個送出時間戳，再把送出時間戳發下去，把Prepare的狀态原子的替換成送出時間戳，當另外一個并發事務T2對T1的修改進行可行性判斷時，如果T1處于prepare的狀态，我們就要等待T1結束，再進行時間戳的比較。
這樣的話，我們就能避免在A節點、B節點看到部分送出結果的問題。
基于PostgreSQL資料結構的讀等待機制設計
那麼就有一個問題，就是基于PostgreSQL資料結構實作讀等待機制。
我們在讀等待的時候，不能把Buffer的鎖加上，這樣的話會阻塞寫，影響并發性能。如果發現它是prepare的，要等待它，我們首先要解鎖Buffer shared鎖，允許并發寫進來，同時等待xid結束再去加buffer。
這個地方可以保證它還能找到原來的位置進行掃描，這是因為PG的邏輯就是它會有item去指向這些Tuple，Tuple可能會移動進行頁面的compact，但是item是不會動的，它可以找到正确的位置，這樣的話就可以保證正确性。同時buffer也會引用計數，這樣保證buffer不會被删掉或做其它的操作。
基于HLC的分布式事務時鐘算法（1）
我們基于HLC的去中心化的分布式事務時鐘來支援分布式事務。
這個 HLC的算法在開源的代碼裡已經有了，但是協調邏輯分布式的代碼還沒有開源。我們後面加上分布式協調邏輯的代碼以後，就可以支援真正的分布式事務。
我們現在單機上采用HLC來支援單機的事務，就是跑一個單機也能正确地跑，跑分布式的時候，基于HLC可以保證全局一緻的事務。HLC的設計是實體和邏輯時鐘混合，64位時鐘由最低16位為邏輯時鐘，中間46位實體時鐘（毫秒）和最高兩個保留位組成。
這樣的話，邏輯時鐘主要是用來追蹤事務之間的因果先後順序。實體時鐘主要是用NTP或PTP去同步不同節點之間的實體時鐘，來保證它們可以讀到一個相對很新的快照。
每個節點維護一個max_ts時鐘，并周期性持久化，重新開機後REDO恢複最大值。
我們有三個時鐘操作，分别是ClockCurrent，ClockUpdate和ClockAdvance。
ClockCurrentc就是讀取目前的Clock，相當于我們用Max_ts和本地的實體時鐘local-phys-ts取最大值傳回。
ClockUpdate就是用一個Timestamp去更新Max_ts，我們取最大值。
ClockAdvance是把max_ts和 local-phys-ts取最大值後再加1傳回，整個過程都是加鎖來保證原子性。
上述操作中，local- phys-ts是本地機器擷取的實體時鐘，并取毫秒時間。左移16位與max_ts 對其進行運算（max-ts最低16位是邏輯時鐘）。
不同機器的實體時鐘可以通過NTP或PTP協定進行同步，保證很小的時鐘傾斜，保證跨協調節點之間的事務可以擷取一個freshness的快照。
基于HLC的分布式事務時鐘算法（2）
我們的時鐘算法就是在事務Begin的時候，會在協調節點上為它配置設定ClockCurrent進行startTS，startTS到了每個DN節點以後，會用startTS去更新本地的Max-ts混合邏輯時鐘。
事務Prepare的時候會去每個參與節點調用ClockAdvance，擷取prepareTS，同時傳回給協調節點。協調節點會從所有的prepareTS選最大值作為commitTS，同時更新CN的混合邏輯時鐘，并且下發給每個DN去送出事務，并且用commitTS去推動每個參與DN的混合邏輯時鐘前進。
版本鍊送出時間戳遞增
這個特性可以保證在版本鍊送出時間戳遞增。
假設我們在一個DN上有兩個事務T2、T3，T2先獲得鎖先進行送出，那麼ClockUpdate就會用T2的commit_ts，使得該節點的max_ts大于等于T2的commit_ts，那T3獲得鎖再進行送出，決策的T3的commit-ts，就會大于等于DN1的 prepare_ts，它就會大于等于 max{max_ts, local_phys_ts} + 1，這樣就能保證T3.commit_ts > max_ts >= T2.commit_ts，這樣的話版本鍊時間戳是遞增的。
Repeatable Read下，T3會被abort，進而避免丢失寫問題。
全局一緻性正确性證明
上面HLC的算法，我們可以證明它的正确性。
我們假設在任意一個節點如DN1上，如果有兩個并發事務T1、T2,如果T2在掃描T1的修改時，T1還未prepare，那麼T1對T2是不可見，因為沒有prepare，也沒有送出時間戳，是以直接就判斷不可見了。
這樣的話，T2的start_ts一定會小于T1的commit_ts，這個是因為T1在prepare階段分布式決策的T1的commit_ts一定會大于等于DN1的prepare_ts，則大于DN1的max_ts。而T2的start_ts 在到達本節點時，一定會更新max_ts，使得 max _ts大于等于 T2的start_ts。是以，當T2掃描T 1的修改時，T 1還未進入prepared狀态，則說明T 1的commit_ts一定會大于T2的start_ts。
由于commit_ts和start_ts是全局統一的，是以在任意節點，T1的commit_ts大于T2的start_ts條件都成立，根據時間戳比較判斷可見性，T1的修改對T2均不可見。
如果T2在掃描T1修改時，T1處于prepared狀态，T2需要等待T1的送出，或者說abort。如果abort，則不可見；如果送出，那就有commit_ts，直接時間戳比較進行可見性判斷，即如果T2.start_ts >= T1.commit_ts，則可見。
如果T2在其他節點沒有看到T1 的prepared狀态,根據上面第一點的證明，最終T1的commit_ts會大于T2的start_ts，則在本節點T2等待結束，也看不到T1的修改。是以，T2可能看到T1的修改，僅當T2在所有節點都看到了T1過了prepare階段。
根據上面的證明總結，如果T2在某個節點掃描時未看到T 1的prepared狀态，T1的修改對T2不可見，最終T2.start_ts < T1.commit_ts，是以T2在其它節點也不會看到T1的修改。如果在某個節點看到T1的prepared狀态，T2會等待T 1結束，這樣如果T2.start_ts >= T1.commit_ts，則可以看到T1的修改。進而我們可以保證T2要看到T1的修改，當且僅當T2的start_ts大于或等于T1的commit_ts。
外部一緻性正确性證明
另外比較關心的就是外部一緻性，HLC可以保證跨session之間的快照隔離（内部一緻性），以及同一個CN的強外部一緻性，跨CN的弱外部一緻性。
外部一緻性的定義是資料庫事務T1送出成功傳回，此時開啟的事務T2一定能夠看到T1的修改，相當于 T2在T1送出成功傳回以後，立即可以看到T1的修改。如果T1、T2都連接配接到一個CN的用戶端，我們就可以保證外部一緻性。T1結束的時候會用T1的commit_ts更新CN的max_ts，T1傳回給用戶端，發起T2請求，可以是不同的用戶端。T2的start_ts會大于等于T1的commit_ts，是以T2一定能看到T1的修改。
不同的CN之間有時鐘偏移，此時不定能保障立馬能看到，會有一定的時鐘傾斜，PTP協定将一個IDC的時鐘傾斜同步在1us内。用戶端到CN之間的網絡來回延遲遠大于時鐘偏移，此時就可以保證強一緻性。
不同CN之間，如果我們依賴傳統通用的NTP進行同步，可以保證讀到小于時鐘傾斜的送出事務修改。比如在CN1上剛送出了，CN2上時鐘偏移可能有5毫秒，要等5毫秒才能看到它的修改。當然，從CN1上傳回給用戶端，讓用戶端知道它已經送出成功了，也會有一定的時差，是以一般場景下讀不到最新送出，相對來說偏差是比較小的。
大部分場景下，跨Session要求讀到前面已經送出的需求一般相對較少，大部分情況下都是在同一個Session裡面的事務要求看到前面的修改，是以HLC可以保證即便是跨Session，不同的CN可以保證快照隔離，同一個CN是強外部一緻性的，跨CN會有弱外部一緻性，未來引入先進的 PPT協定就可以保證強外部一緻性。
Remote Recovery 設計動機
接下來介紹一下另外一個性能的優化——Remote Recovery機制。
PostgreSQL會通過full page writes來解決故障時部分寫入的頁面，因為故障的時候頁面可能會沒有完全寫入，在頁面寫入的中間就crash了。
此時，PG采用的是checkpoint後第一次修改，在WAL中寫入full page，回放時，用WAL中的full page來進行回放，此時full page寫的開銷就會很大。
Remote Recovery 設計想法
我們有一個Remote Recovery的設計想法，就是通常情況下一個資料庫節點是有多節點進行容災，像我們這次開源的三節點，它就有兩個節點進行容災。我們可以采用Remote Recovery機制在多個副本之間進行恢複，就是一個機器節點的頁面可能損壞了，但其他副本有最新的有正确頁面，就會備機去讀然後再進行故障恢複。
這個特性Oracle裡面也有，我們的特性和它的不同點在于Oracle的是做checksum的時候發現它不一緻了，就去其他節點恢複。我們還是沿用full page write的特性，在checkpoint後發現是第一次修改，就去備機讀。因為checksum并不一定保證完全的正确，而我們這樣的話可以保證完全的正确性。
Remote Recovery 實作
上圖為Remote Recovery的原理架構圖。
我們在回放的時候，發現它是checkpoint後第一次修改，我們就會從遠端mirrored節點，比如備機從主機，主機從備機，或者備機從備機，可以把另外一個full page先讀過來，然後再Apply。
Apply的時候跟WAL回放的原理一樣，就是隻有LSN大于遠端頁面的LSN才會回放，否則的話就直接跳過，說明在備機或遠端的一個節點已經回放過了。
這裡有個很核心的問題，就是何時需要去取remote full page？
在每個checkpoint後第一次修改頁面時，我們不寫full page，而是在WAL中寫入remote fetch page bit，記錄一下需要去遠端讀取頁面。
在節點故障恢複重做時，碰到remote fetch page bit，則從mirrored節點遠端fetch full page。主機寫入checkpoint的時候需要等待備機同步完成，因為我們需要保證主備之間最近的一個checkpoint大家都有，因為回放都是從最近的一個checkpoint開始的，是以必須保證之前的修改在其他節點已經有了，這樣我們才能保證回放正确。
這樣的話,我們回放的流程跟原來的單機回放是差不多的，也就是當LSN大于page LSN才重做。如果小于，那說明在mirrored的節點已經重做過了，我們就不需要再回放，直接跳過。
還有一些不存在的頁，說明它在後面已經删除掉該頁了，比如說删除表空間，回收等，我們也可以簡單跳過。
我們去連接配接mirrored節點的時候，需要判斷mirrored節點回放是否過了故障恢複節點最近的一個checkpoint點。如果沒有，就要等它過了這個點，保證兩邊最近的 checkpoint點是一樣的，因為恢複是從最近的checkpoint點來恢複，這樣就可以保證兩邊是一緻的。
Remote Recovery的正确性是保證兩個節點之間checkpoint點是一樣的，這樣我們後面回放的時候就有最新的資料，無非是LSN在另外一個節點是否回放過的差別。