PgSQL · 源碼分析 · PG中的無鎖算法和原子操作應用一則

無鎖算法是利用cpu的原子操作實作的資料結構和算法來解決原來隻能用鎖才能解決的并發控制問題。 衆所周知，在一個并發系統中特别是高并發的場景下，鎖的使用會影響系統性能。 這裡的cpu的原子操作是不可中斷的一個或者一系列操作, 也就是不會被線程排程機制打斷的操作， 運作期間不會有任何的上下文切換。

常用的原子操作包括：

cas，compare & set，或是 compare & swap: 看某記憶體位置的值是不是等于一個值oldval， 如果是就寫入新值newval，傳回一個bool值辨別是否做了更新

fetch-and-add: 把某個記憶體位置加上一個值

test-and-set: 寫值到某個記憶體位置并傳回其舊值

本文并不打算對這些原子操作概念和原理本身進行展開讨論，有興趣的讀者可以參考wikipedia或其它的網上文章。

由于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個部分。

通常支援一個新的平台隻需要在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的管理，下一節我們将對其中的一個進行分析，其他對原子操作的使用将會在後續的文章中進行分析。

當一個寫事務送出時，程序要修改自己的pgproc結構來辨別自己已經結束了，其中的一個主要動作是重置自己事務id(xid)， 為了簡化我們後面就管這個過程叫重置xid，這時需要以排它的方式擷取procarraylock鎖，以防拿事務snapshot的程序看到不一緻的結果。 當有很多事務送出時，每一個要送出的程序依次喚醒、拿鎖、放鎖，導緻該鎖的過度争用。為了提高效率這個patch隻讓一個程序擷取procarraylock鎖， 由該程序為所有同時送出的其他程序（patch裡叫一個procarray組）集中批量修改。

下面來詳細分析一下該patch的代碼。patch修改了pgproc結構和pgproc數組頭結構proc_hdr，在pgproc中加入了3個成員變量：

在proc_hdr中加入一個成員變量：

首先在事務送出時嘗試去擷取procarraylock，如果擷取到了就直接調用重置xid函數， 否則調用一個新加的函數procarraygroupclearxid通過使用原子操作進行批量重置xid。

整個patch主要邏輯都在procarraygroupclearxid函數中，該函數首先将自己加到procarray組的頭部：

這段代碼通過對位于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循環。

這個函數的最後就比較簡單了，procarray組的leader循環組清單對每個成員調用重置xid函數， 最後在釋放了procarraylock鎖之後通知每個組成員繼續執行。

通過對以上patch代碼的分析我們可以看到pg巧妙的利用了原子操作有效的減少了在高并發的條件下在事務送出時對procarraylock鎖的争用。 但随着硬體伺服器上cpu核數的不斷增加，并發的不斷加大，procarraylock鎖的争用仍然是一個需要不斷優化的熱點， 其中一個最有希望的解決方案是使用csn（commit sequence number）替代原來的事務快照（snapshot）機制來做可見性判斷， 這在postgresql社群裡已經有了patch，我們将在後續文章進行分析。