PgSQL · 源碼分析 · PG中的無鎖算法和原子操作應用一則 · 數據庫內核月報

## 原子操作概述近年來隨著服務器上CPU核數的不斷增加，無鎖算法（Lock Free）越來越廣泛的被應用于高并發的系統中。PostgreSQL 做為世界上最高級開源數據庫也在9.5時引入了無鎖算法。本文先介紹了無鎖算法和原子操作在PostgreSQL中的具體實現，再通過一個[Patch](https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=0e141c0fbb211bdd23783afa731e3eef95c9ad7a)來看一下在PostgreSQL中是如何利用它來解決實際的高并發問題的。無鎖算法是利用CPU的原子操作實現的數據結構和算法來解決原來只能用鎖才能解決的并發控制問題。眾所周知，在一個并發系統中特別是高并發的場景下，鎖的使用會影響系統性能。這里的CPU的原子操作是不可中斷的一個或者一系列操作, 也就是不會被線程調度機制打斷的操作，運行期間不會有任何的上下文切換。常用的原子操作包括： * CAS，Compare & Set，或是 Compare & Swap:?看某內存位置的值是不是等于一個值oldval，如果是就寫入新值newval，返回一個bool值標識是否做了更新 * Fetch-and-add:?把某個內存位置加上一個值 * Test-and-set:?寫值到某個內存位置并傳回其舊值本文并不打算對這些原子操作概念和原理本身進行展開討論，有興趣的讀者可以參考Wikipedia或其它的網上文章。 ## PostgreSQL中原子操作的實現由于PostgreSQL是一個跨平臺的開源軟件，支持十幾種CPU架構和眾多的操作系統，而原子操作又與CPU架構和編譯器緊密相關，所以原子操作在PostgreSQL中的實現稍顯復雜。在PostgreSQL中原子操作的實現涉及到的文件包括（由于PostgreSQL的頭文件都位于源碼的include目錄里，所以本文后面的說明頭文件路徑時都是只引用到include子目錄這一層）: * include/port/atomics.h * include/port/atomics目錄里的所有頭文件 * 源文件 src/backend/port/atomics.c 原子操作的所有對外部模塊可用符號都聲明在頭文件port/atomics.h中，而其他文件都可看作是原子操作模塊的內部實現文件不允許外部模塊直接引用。也就是說，如果要在PostgreSQL代碼中使用原子操作只需包含port/atomics.h即可。而port/atomics.h也是原子操作模塊的最主要的源文件，所有其他的源文件都是通過該文件組織起來的。下面從port/atomics.h源文件開始分析。 port/atomics.h 整個文件分成4個部分。第1部分和第2部分分別用來包含具體CPU架構相關的頭文件和各種編譯器相關的頭文件。這些頭文件都在port/atomics目錄下。第1部分所包含的頭文件里一般都是用匯編語言實現的CPU相關的內存屏障[1](http://mysql.taobao.org/monthly/2016/09/09/#fn.1)和原子操作的實現函數，目前只在X86架構下用GCC編譯的情況下實現了匯編版本原子操作，而其他的CPU架構則采用第2部分里的編譯器實現的通用版本，一般的編譯器如GCC[2](http://mysql.taobao.org/monthly/2016/09/09/#fn.2)都內置了原子操作的支持。之所以X86版本提供了基于匯編的實現主要是為了更好的性能和支持更老版本的GCC。第2部分的最后還包含了port/atomics/fallback.h頭文件，該文件聲明了PostgreSQL自己使用自旋鎖或操作系統的信號量模擬實現的原子操作的版本，具體實現位于src/backend/port/atomics.c中，這在第1部分和第2部分都沒有找到實現的情況下會使用該版本，注意使用該版本性能會比較差。通常支持一個新的平臺只需要在port/atomics.h的第1部分或第2部分中實現如下函數即可： * pg_compiler_barrier() * pg_write_barrier() * pg_read_barrier() * pg_atomic_compare_exchange_u32() * pg_atomic_fetch_add_u32() * pg_atomic_test_set_flag() * pg_atomic_init_flag() * pg_atomic_clear_flag() 前三個函數是實現內存屏障（Memory Barrier）的，剩下的是基本的原子操作函數， port/atomics.h的第3部分包含了頭文件port/atomics/generic.h, 它利用這幾個基本的原子操作實現更多的原子操作函數。 port/atomics.h第4部分是定義本模塊所有的導出函數，通常都是定義一個簡單的inline函數去調用該函數的具體實現（實現函數名一般為xxx_impl）。下面是第4部分具體定義的原子操作函數： * 內存屏障相關函數，包括 compiler barrier 和 read/write barrier * 語義上的布爾值（PG代碼里叫flag，具體實現上可能映射到一個字節，或一個整數）的原子操作，包括： * pg_atomic_init_flag，初始化一個flag * pg_atomic_test_set_flag, Test-And-Set，這也是flag的唯一支持的原子操作函數 * pg_atomic_unlocked_test_flag，檢查flag是否沒有被設置 * pg_atomic_clear_flag，清除已設置的flag * 32位無符號整數的原子操作，包括： * pg_atomic_init_u32, pg_atomic_read_u32, pg_atomic_write_u32，初始化、讀、寫操作 * pg_atomic_exchange_u32，給原子變量賦值并返回原值 * pg_atomic_compare_exchange_u32, 32位無符號整數的CAS操作，比較原子變量和另一個變量的值，如果相等就賦一個新值到原子變量里，返回一個布爾值標識是否進行了賦值操作 * pg_atomic_fetch_add_u32, pg_atomic_fetch_sub_u32, pg_atomic_fetch_and_u32, pg_atomic_fetch_or_u32 對某個原子變量進行加、減、與、或操作，并返回變量改變之前的值 * pg_atomic_add_fetch_u32, pg_atomic_sub_fetch_u32 對某個原子變量進行加、減操作，并返回變量改變之后的值 * 64位無符號整數的原子操作，與32位的實現的操作函數相似，只是實現的是64位版本，這里需要注意的是， 64位版本并不保證所有平臺的都支持，目前在PostgreSQL的源代碼中還沒有被使用。在port/atomics.h的文件開頭的注釋里，代碼的作者也提到了：除非必要否則盡量不要使用原子操作，可以使用更上層的數據結構或算法如LWLock，SpinLock或者普通鎖，因為使用原子操作需要更多的技巧，寫出完全正確的代碼是比較難的。目前在PostgreSQL的代碼中有3個地方使用了原子操作來提高并發性能，分別是事務提交時的并發處理， LWLock的實現和Buffer的管理，下一節我們將對其中的一個進行分析，其他對原子操作的使用將會在后續的文章中進行分析。 ## 使用原子操作減少事務提交時鎖的爭用在PostgreSQL中每個Session的執行時的一些關鍵的狀態信息都保存在PGPROC這個結構當中，如當前所執行事務的事務ID(xid)，PostgreSQL維護了一個PGPROC的數組叫ProcArray，由一個叫ProcArrayLock的鎖保護著。ProcArray在PostgreSQL當中屬于核心數據結構，在事務的開啟和結束，在執行任何查詢時獲取事務快照（Snapshot）[3](http://mysql.taobao.org/monthly/2016/09/09/#fn.3)做可見性判斷時都會獲取ProcArrayLock鎖去訪問ProcArray。現在在高并發的情況下ProcArrayLock鎖爭用已經非常嚴重了，在PostgreSQL 9.6時提交了一個Patch使用原子操作來減少對該鎖的爭用。當一個寫事務提交時，進程要修改自己的PGPROC結構來標識自己已經結束了，其中的一個主要動作是重置自己事務ID(xid)，為了簡化我們后面就管這個過程叫重置xid，這時需要以排它的方式獲取ProcArrayLock鎖，以防拿事務Snapshot的進程看到不一致的結果。當有很多事務提交時，每一個要提交的進程依次喚醒、拿鎖、放鎖，導致該鎖的過度爭用。為了提高效率這個Patch只讓一個進程獲取ProcArrayLock鎖，由該進程為所有同時提交的其他進程（Patch里叫一個ProcArray組）集中批量修改。下面來詳細分析一下該Patch的代碼。Patch修改了PGPROC結構和PGPROC數組頭結構PROC_HDR，在PGPROC中加入了3個成員變量： ~~~ /* Support for group XID clearing. */ /* 如果是一個ProcArray組的成員為true */ bool procArrayGroupMember; /* 指向下一個ProcArray組的成員 */ pg_atomic_uint32 procArrayGroupNext; /* * 這是在調用重置xid的函數所需要傳遞的參數 */ TransactionId procArrayGroupMemberXid; ~~~ 在PROC_HDR中加入一個成員變量： ~~~ /* ProcArray組的第一個成員 */ pg_atomic_uint32 procArrayGroupFirst; ~~~ 首先在事務提交時嘗試去獲取ProcArrayLock，如果獲取到了就直接調用重置xid函數，否則調用一個新加的函數ProcArrayGroupClearXid通過使用原子操作進行批量重置xid。整個Patch主要邏輯都在ProcArrayGroupClearXid函數中，該函數首先將自己加到ProcArray組的頭部： ~~~ while (true) { nextidx = pg_atomic_read_u32(&procglobal->procArrayGroupFirst); pg_atomic_write_u32(&proc->procArrayGroupNext, nextidx); if (pg_atomic_compare_exchange_u32(&procglobal->procArrayGroupFirst, &nextidx, (uint32) proc->pgprocno)) break; } ~~~ 這段代碼通過對位于PROC_HDR結構中的ProcArray組頭部進行CAS原子操作，不斷的嘗試將自己加入到ProcArray組中，這里是通過存儲其pgprocno（相當于PGPROC數組下標），形成一個用pgprocno串起來的鏈表。注意在以上3條語句之間隨時有可能由其他進程插進來把它們自己加到ProcArray組中導致CAS操作失敗，失敗之后程序會進行下一次循環直到成功。執行完這段代碼變量nexidx存儲的是原ProcArray組的頭部，代碼通過比較nextidx來判斷是否是ProcArray組的第一個成員即Leader，Leader的nextidx應該是初值INVALID_PGPROCNO，由Leader負責整個組的重置xid工作，非Leader成員只需等待Leader完成工作后通知自己即可。 ProcArray組的Leader先獲取PROCArray鎖，然后從組頭部拿到第一個元素，并把組頭置成初值INVALID_PGPROCNO，這時其他進程可以開始一個新的ProcArray組： ~~~ while (true) { nextidx = pg_atomic_read_u32(&procglobal->procArrayGroupFirst); if (pg_atomic_compare_exchange_u32(&procglobal->procArrayGroupFirst, &nextidx, INVALID_PGPROCNO)) break; } ~~~ 注意在執行這段代碼過程中，還會不斷有新到組成員加進來，所以使用了while循環。這個函數的最后就比較簡單了，ProcArray組的Leader循環組列表對每個成員調用重置xid函數，最后在釋放了ProcArrayLock鎖之后通知每個組成員繼續執行。通過對以上Patch代碼的分析我們可以看到PG巧妙的利用了原子操作有效的減少了在高并發的條件下在事務提交時對ProcArrayLock鎖的爭用。但隨著硬件服務器上CPU核數的不斷增加，并發的不斷加大，ProcArrayLock鎖的爭用仍然是一個需要不斷優化的熱點，其中一個最有希望的解決方案是使用CSN（commit sequence number）替代原來的事務快照（Snapshot）機制來做可見性判斷，這在PostgreSQL社區里已經有了Patch，我們將在后續文章進行分析。 * * * [1](http://mysql.taobao.org/monthly/2016/09/09/#fnr.1)?內存屏障是一個和原子操作相關的概念，限于篇幅本文沒有介紹，有興趣的讀者可參考PostgreSQL源代碼目錄下的src/backend/storage/lmgr/README.barrier，或其他網上資料 [2](http://mysql.taobao.org/monthly/2016/09/09/#fnr.2)?參見?[GCC 6.2.0 原子操作內置函數](https://gcc.gnu.org/onlinedocs/gcc-6.2.0/gcc/_005f_005fatomic-Builtins.html) [3](http://mysql.taobao.org/monthly/2016/09/09/#fnr.3)?在獲取事務快照（Snapshot）時需要以共享方式獲取ProcArrayLock鎖，并且循環整個ProcArray數組來拿到當前所有執行事務的列表，持鎖時間會更長，而且獲取事務快照是一個更頻繁的操作，根據事務隔離級別的不同，執行每個事務可能要進行多次獲取事務快照操作