文章目錄
- 前言
- 鎖類型
- Spinlocks
- 信号量方式 實作的Spinlock
- 初始化 SpinLockInit(lock)
- 加鎖 SpinLockAcquire(lock)
- 解鎖 SpinLockRelease(lock)
- TAS 指令方式 實作的 Spinlock
- 初始化 SpinLockInit(lock)
- 加鎖 SpinLockAcquire(lock)
- Linux kernel Spinlock 實作
- LWLocks
- InitializeLWLocks 初始化輕量鎖
- LWLockAcquire 加鎖
- LWLockRelease 解鎖
- Regular Locks
- 鎖模式 以及 相容性
- 資料結構
- 初始化 正常鎖
- 加鎖 LockAcquire
- 解鎖 LockRelease
- 總結
前言
本節将在之前PG 事務體系實作的基礎上 記錄 PostgreSQL 實作事務過程的一個非常重要的子系統 : 鎖。它是 PG 實作事務的核心系統,為了更好得提升并發場景下的事務可靠性以及性能而存在。
本節的PG代碼版本是:
REL_12_2
,篇幅會比較長,可能會對比不同系統的一些鎖實作細節,希望大家能夠對鎖體系的實作有廣度以及深度的系統了解(當然也是自我學習的過程),有一些代碼細節了解有問題的情況也希望熟悉的同學及時指出。
鎖類型
PG 内部使用了四種類型的鎖,自低向上分别是
Spinlocks
,
LightWeigt locks (LWLocks)
,
Regular locks
,
SIReadLock predicate locks
。
-
Spinlocks
自旋鎖。 是用來保護一個非常小的臨界區資源,是以它本身适用的持續周期是非常短,而這種鎖的實作方式就是 占有一個CPU核心持續自旋(自我輪詢)。目前來看,自旋鎖的實作以及應用遍布整個網際網路體系,尤其是底層的基礎架構 — 資料庫系統,存儲系統 以及 OS 系統。PG 因為起源于上世紀70年代,當時的網際網路也才剛興起沒多久,是以PG的 spinlock 也都是自己實作的(使用了硬體的 atomic-test-and-set 指令),并沒有使用 os 現在提供的 spinlock。
在PG内部,spinlock 被用來實作
,保護一些原子變量。但是 spinlock 并不會提供 死鎖檢測 、持鎖期間抛異常無法自動釋放鎖等機制。但是還是實作了逾時機制,即長時間得不到鎖,就讓出CPU。LWLocks
-
LightWeight locks
輕量鎖。用來保護一些存儲在共享記憶體中的資料結構。支援兩種模式:排他(讀/寫)和共享(讀讀)。當然,LWLocks 也不支援死鎖檢測 和 逾時(底層的spinlock 已經支援了),但是能夠在持鎖期間抛錯誤時自動釋放鎖資源。
它底層的實作機制也是spinlock,等待鎖 是通過讓程序等待在一個 OS 信号量上(不會消耗CPU),這個信号量被持有程序釋放之後,則會根據等待順序來讓程序按照順序加鎖。
-
Regular locks
正常鎖。這是PG 非常重要的鎖類型,用來保護 使用者驅動産生的 PG 對象的通路安全。其支援了非常多的鎖模式,分别用來保護 PG 對象:表(Relation),頁面(page),元組(row) 等。
其完整支援了 死鎖檢測 以及 事務結束時的自動釋放鎖功能,是以正常鎖是 PG事務并發控制中 最複雜的一部分,也是我們下文展開鎖細節中描述最多的一部分。
-
預測鎖。是PG 為了實作 SSI (Serializable and Snapshot Transaction Isolation Level) 隔離級别時使用的鎖,這一部分的實作 以及 SSI 的介紹會單獨放在 一個小章節進行描述,因為這個隔離級别并不是 ANSI 标準中的,而是PG 為使用者使用友善單獨做的一個隔離級别,用來避免寫偏序問題。SIReadLock predicate locks
以上就是PG内部的四種基本的鎖類型,接下來我們一起 自低向上 仔細看看 PG 這樣的擁有40多年曆史 的資料庫是如何實作這一些鎖的(最後一種本節不會描述)。
Spinlocks
在 PostgreSQL 中 spinlock 的實作有兩種方式,一種是依賴信号量,另一種是根據系統是TAS(Test-And-Set 根據系統是否支援來決定是否使用)。
信号量方式 實作的Spinlock
所有核心用到的spinlock 相關的接口都在
spin.h
中,通過宏定義實作,實際的實作是在
s_lock.h
中。
實際使用中,PostgreSQL 核心會建議不要使用信号量實作的 spinlock,因為大多數的 os 會對建立的信号量的個數有限制,除非有必要,建議還是使用 TAS 方式實作的spinlock。
因為信号量有個數限制,
初始化 SpinLockInit(lock)
信号量本身會在 postgres 程序啟動的時候預先建立好 spinlock 要使用的 固定個數的信号量,友善程序運作過程中快速使用,這一些預先建立好的信号量會儲存到
SpinlockSemaArray
全局變量中。
預建立指定個數的信号量會在如下邏輯中進行:
PostmasterMain
reset_shared()
CreateSharedMemoryAndSemaphores
SpinlockSemaInit
預先 通過
sem_init
系統調用初始化的信号量的個數為 :
NUM_SPINLOCK_SEMAPHORES + NUM_ATOMICS_SEMAPHORES
= 128 + 64 = 192個。
PG 單機 允許的最大的連接配接數是 100個 backend,很少了,是以目前支援的這麼多的信号量肯定是夠用,當然邏輯上肯定是要支援超過最大信号量個數的。
void
SpinlockSemaInit(void)
{
PGSemaphore *spinsemas;
int nsemas = SpinlockSemas();
int i;
/*
* We must use ShmemAllocUnlocked(), since the spinlock protecting
* ShmemAlloc() obviously can't be ready yet.
*/
spinsemas = (PGSemaphore *) ShmemAllocUnlocked(SpinlockSemaSize());
for (i = 0; i < nsemas; ++i)
spinsemas[i] = PGSemaphoreCreate();
SpinlockSemaArray = spinsemas;
}
其中
PGSemaphoreCreate
内部會調用
sem_init(sem, 1, 1)
初始化一個新的信号量,并且将這個信号量的值指派為1 并且 設定可以跨線程以及程序可見的标記(第二個參數 pshared)。
啟動過程中建立好的這麼多信号量在後續有Spinlock 的使用需求時會先初始化spinlock,即通過函數
#define S_INIT_LOCK(lock) s_init_lock_sema(lock, false)
進行,這個初始化的目的是辨別目前調用者使用的是
SpinlockSemaArray
信号量數組中的哪一個信号量,将index 放在lock中,需要注意的是雖然有192個信号量,但實際讓使用的隻有
NUM_SPINLOCK_SEMAPHORES
128個。
void
s_init_lock_sema(volatile slock_t *lock, bool nested)
{
/* 靜态變量,辨別目前調用者要使用 SpinlockSemaArray 數組中信号量的 index. */
static int counter = 0;
/* 不使用0 号信号量 */
*lock = ((++counter) % NUM_SPINLOCK_SEMAPHORES) + 1;
}
加鎖 SpinLockAcquire(lock)
調用者進行加鎖,會通過邏輯:
#define SpinLockAcquire(lock) S_LOCK(lock)
#define S_LOCK(lock) \
(TAS(lock) ? s_lock((lock), __FILE__, __LINE__, PG_FUNCNAME_MACRO) : 0)
宏定義
S_LOCK
主要的作用是加鎖,在信号量場景下其加鎖步驟為:
- 通過 信号量實作的
函數 TAS(lock)
tas_sema(lock)
去等待 lock值 對應的 信号量數組中的對應信号量可被通路。
操作方式是通過
将這個從信号量數組中拿到的信号量的值 減1 變為0,這樣後來的調用者想要對同一個信号量進行通路,因為其value 已經是 0 ,則會傳回失敗狀态。sem_trywait
- 如果加鎖成功(信号初始值大于0,減1之後會傳回成功,辨別加鎖成功),則會進入
s_lock
邏輯,進而進行自旋(busy-loop狀态)。
這個函數實作也是前面介紹 PG
時提到的 逾時機制的實作,它也是 Spinlock
方式的spinlock 需要進入的邏輯。TAS
第一步中的
tas_sema
函數實作如下:
主要是信号量的系統調用操作,并且要求保證最後執行完
sem_trywait
之後信号量的值為0 才行,這樣才能保證後續的其他操作目前信号量的調用者 除了解鎖操作 即 調用
sem_post
之外 無法持有信号量。
int
tas_sema(volatile slock_t *lock)
{
int lockndx = *lock;
if (lockndx <= 0 || lockndx > NUM_SPINLOCK_SEMAPHORES)
elog(ERROR, "invalid spinlock number: %d", lockndx);
/* Note that TAS macros return 0 if *success* */
return !PGSemaphoreTryLock(SpinlockSemaArray[lockndx - 1]);
}
bool
PGSemaphoreTryLock(PGSemaphore sema)
{
int errStatus;
/*
* Note: if errStatus is -1 and errno == EINTR then it means we returned
* from the operation prematurely because we were sent a signal. So we
* try and lock the semaphore again.
*/
do
{
/*
* 保證執行完之後,信号量的值變為了0(有效的加鎖操作)。
* 判斷信号量的值是否大于0,是則減一,并傳回true。
* 如果内部發現信号量已經是0 了,則會傳回false,辨別
* 已經有一個其他的調用者在持有鎖了。
*/
errStatus = sem_trywait(PG_SEM_REF(sema));
} while (errStatus < 0 && errno == EINTR);
if (errStatus < 0)
{
if (errno == EAGAIN || errno == EDEADLK)
return false; /* failed to lock it */
/* Otherwise we got trouble */
elog(FATAL, "sem_trywait failed: %m");
}
return true;
}
第二步 主要是嘗試操作完信号量之後 發現已經有一個更早的調用者持有了信号量(其實是信号量為0),通會過
s_lock
進行忙等,且有需要則進入逾時邏輯。
忙等以及逾時處理的主要邏輯實作是通過一個
SpinDelayStatus
結構體。
typedef struct
{
int spins; /* 自旋的次數,即執行TAS_SPIN(lock)為真的次數 */
int delays; /* 執行pg_usleep 的次數 */
int cur_delay; /* 目前要sleep 的時間,機關是us */
const char *file; /* 調用者源代碼所在的檔案名 */
int line; /* 行号 */
const char *func; /*函數名,這三個都是為了友善記錄日志。*/
} SpinDelayStatus;
s_lock忙等的前提是
TAS_SPIN(lock)
傳回為真,即沒有獲得到鎖,才會有如下的邏輯,主要實作是在
perform_spin_delay
函數中:
-
次數小于 spins
多次(預設是100次) 還沒有拿到鎖,即TAS_SPIN(lock) 傳回值一直為真。spins_per_delay
那就繼續執行,嘗試擷取鎖。
- 如果超過了
:spins_per_delay
- delays 次數小于
(1000次) 且上次的睡眠時間沒有設定過,那就設定一個最小的睡眠時間(預設是100us) ,執行NUM_DELAYS
,并更新下一次的delay時間為目前的1x或者2x(保證每一次觸發delay的時間比目前長,這樣較長持有的 spinlock 能減少對CPU的持續的占用)。pg_usleep
- delay次數超過了
,則辨別 spinlock 等待的時間太長了,會elog panic。NUM_DELAYS
- 每一次進入到超過
之後會重置一下 spins 為0。spins_per_delay
邏輯如下
void
perform_spin_delay(SpinDelayStatus *status)
{
/* CPU-specific delay each time through the loop */
SPIN_DELAY();
/* Block the process every spins_per_delay tries */
if (++(status->spins) >= spins_per_delay)
{
if (++(status->delays) > NUM_DELAYS)
s_lock_stuck(status->file, status->line, status->func);
if (status->cur_delay == 0) /* first time to delay? */
status->cur_delay = MIN_DELAY_USEC;
pg_usleep(status->cur_delay);
#if defined(S_LOCK_TEST)
fprintf(stdout, "*");
fflush(stdout);
#endif
/* increase delay by a random fraction between 1X and 2X */
status->cur_delay += (int) (status->cur_delay *
((double) random() / (double) MAX_RANDOM_VALUE) + 0.5);
/* wrap back to minimum delay when max is exceeded */
if (status->cur_delay > MAX_DELAY_USEC)
status->cur_delay = MIN_DELAY_USEC;
status->spins = 0;
}
}
當然, PG spin_locks 針對
spins_per_delay
的次數設定還是會動态變更,根據每次加鎖是否需要delay,如果不用delay 認為現在加鎖需求不是很頻繁,則每次 finish 之後會增加100次,直到增加到
MAX_SPINS_PER_DELAY
1000次為止。
解鎖 SpinLockRelease(lock)
信号量實作的spinlock的 解鎖邏輯 比較簡單了,主要通過操作信号量的
sem_post
完成針對指定信号值的 加一 操作。
#define SpinLockRelease(lock) S_UNLOCK(lock)
#define S_UNLOCK(lock) s_unlock_sema(lock)
void
s_unlock_sema(volatile slock_t *lock)
{
/* lock 為存儲在數組中的信号量index */
int lockndx = *lock;
if (lockndx <= 0 || lockndx > NUM_SPINLOCK_SEMAPHORES)
elog(ERROR, "invalid spinlock number: %d", lockndx);
/* 信号量解鎖 */
PGSemaphoreUnlock(SpinlockSemaArray[lockndx - 1]);
}
void
PGSemaphoreUnlock(PGSemaphore sema)
{
int errStatus;
/*
* Note: if errStatus is -1 and errno == EINTR then it means we returned
* from the operation prematurely because we were sent a signal. So we
* try and unlock the semaphore again. Not clear this can really happen,
* but might as well cope.
*/
do
{
/* 信号量加一 */
errStatus = sem_post(PG_SEM_REF(sema));
} while (errStatus < 0 && errno == EINTR);
if (errStatus < 0)
elog(FATAL, "sem_post failed: %m");
}
本來還有一個自旋鎖的釋放
SpinLockFree(lock)
,因為目前用到的信号量需要長期駐留在記憶體中,在PG 主程序退出時統一通過
sem_destroy
進行釋放。
可以看到使用信号量實作自旋鎖,需要非常多次的系統調用的參與,系統調用意味着有使用者态到核心态的上下文切換,這其實是對cpu的一種持續消耗,效率并不高。
接下來我們再看看 PG 核心推薦使用的 第二種實作自旋鎖的方式 – TAS(test-and-set)。
TAS 指令方式 實作的 Spinlock
PG 支援了非常多硬體架構中的自旋鎖的實作,因為在硬體伺服器架構中不同的原子操作的CPU指令不同,本節我們主要關注
intel x86_64
這個資料庫系統所使用的較多的伺服器架構。
初始化 SpinLockInit(lock)
TAS 的初始化沒有其他的操作,主要是将 lock狀态設定為 S_UNLOCK(lock) 時的狀态就好了,即設定為 0 就好了。
核心主要是看一下加鎖所應用到的指令集。
加鎖 SpinLockAcquire(lock)
x86_64
架構下支援 TAS 的加鎖實作還是會通過如下邏輯:
#if !defined(S_LOCK)
#define S_LOCK(lock) \
(TAS(lock) ? s_lock((lock), __FILE__, __LINE__, PG_FUNCNAME_MACRO) : 0)
#endif /* S_LOCK */
和信号量實作的 spinlock 的差異是在
TAS(lock)
中,先看代碼:
static __inline__ int
tas(volatile slock_t *lock)
{
register slock_t _res = 1;
__asm__ __volatile__(
" lock \n"
" xchgb %0,%1 \n"
: "+q"(_res), "+m"(*lock)
: /* no inputs */
: "memory", "cc");
return (int) _res;
}
以上實作執行了一段彙編代碼:
- lock 指令, intel x86_64 的官方文檔中的描述( 8.1.4小節)指出當我們的硬體 cpu型号是
或者 intel486
處理器,lock 指令會鎖記憶體總線,即使這個變量的記憶體資料在cpu-cache中,也會鎖總線。但是這樣對性能的影響非常大,是以後來的 Pentium
以及 更新的處理器 對于處于cpu-cache中的記憶體區域隻會鎖 cache ,通過 CPU 的多核 cache一緻性協定 + 記憶體屏障 來保證通路的原子性,這種方式的lock 指令相比于之前鎖總線,對CPU性能提升還是挺明顯的。P6
- xchg 指令,用來交換兩個寄存器中的值,它的執行是在 lock指令之後
-
表示指令可以對臨時變量 +q(res)
進行讀寫,_res
表示可以對記憶體變量 "+m"(*lock)
的記憶體區域進行讀寫。*lock
- 最後傳回 (int)_res的值,如果傳回值為 1,則表示加鎖失敗,如果為0,則表示加鎖成功(unlock 會設定 *lock的值為0)。
加完鎖之後如果加鎖失敗,還是會進入到
s_lock
的邏輯,我們再次看看這個函數的邏輯:
int
s_lock(volatile slock_t *lock, const char *file, int line, const char *func)
{
SpinDelayStatus delayStatus;
/* 初始化 SpinDelayStatus 結構體的狀态 */
init_spin_delay(&delayStatus, file, line, func);
/* tas 函數傳回值不為0,表示加鎖失敗,會嘗試進入忙等。*/
while (TAS_SPIN(lock))
{
perform_spin_delay(&delayStatus);
}
finish_spin_delay(&delayStatus);
return delayStatus.delays;
}
忙等以及逾時等待的邏輯前面講 信号量的時候已經描述的比較清楚了,我們需要關注的是在
perform_spin_delay
函數裡面對關于
x86_64
的
SPIN_DELAY();
宏定義的實作。
它底層執行了一個
rep; nop
指令,其實也就是
pause
指令,這個指令核心目的在前面提到的官方文檔中也有描述,因為我們實作的是忙等,在一個循環中,這個過程 lock變量的資料被放在了 cpu-cache 中, 通路較為高效。但是,其他cpu 釋放鎖并修改了這個 lock變量的值,由于cpu cache一緻性,發現本地cpu這個變量的值和記憶體中的值不一緻,會觸發cache失效并去flush 本地cpu的pipeline。
nop
即
pause
指令會提示cpu 目前執行的代碼序列是一段
spin-wait
循環,cpu會根據這個提示來防止記憶體序失效 并且 阻止重新整理 pipeline。
而且
pause
指令的優勢還在于能夠減少 為 spin-lock 這樣的循環等待生成的流水順序列,進而降低了電源的功耗,cpu 官方建議對于忙等過程,需要加入
pause
指令,能夠有效提升整體CPU高負載下的性能。
#define SPIN_DELAY() spin_delay()
static __inline__ void
spin_delay(void)
{
/*
* Adding a PAUSE in the spin delay loop is demonstrably a no-op on
* Opteron, but it may be of some use on EM64T, so we keep it.
*/
__asm__ __volatile__(
" rep; nop \n");
}
對于釋放鎖鎖資源 的過程,這一部分隻需要操作指令集,且lock變量一般是屬于某一個結構體的整型變量,結構體資源釋放的時候會去做釋放操作,看了一下
SpinLockFree
的宏定義并沒有其他人去使用。
解鎖則在TAS中就是變更 lock狀态,目前的實作是辨別
*lock = 0
,因為lock不是原子變量,是以會有安全問題:
-
并不是一個原子變量,會導緻記憶體重新派列記憶體序列,有可能通路不安全,且會有cpu 和記憶體資料同步較慢的問題,間接影響性能*lock
- 不同的硬體平台可能定義自己的 S_UNLOCK,如果将這個簡單得定義為 内聯 宏定義,編譯器可能會重新排列臨界區内部的執行指令,進而可能出現部分臨界區内部的指令在臨界區外部 鎖釋放之後 執行。是以這裡保持所有平台都用相同的邏輯
。*lock = 0
Linux kernel Spinlock 實作
PG 這裡對自己應用的系統資源占用情況的把控較為精确,不太會有 spinlock 頻繁競争的情況,是以也就沒有排隊問題的處理了,僅僅支援忙等以及 timeout 或者 delay limit次數 這樣的限制就足夠了。
而在 Linux kernel中 為了提供一個較為通用的 spinlock 接口或者内部代碼對 spinlock的需求 都提出了排隊的需求(多程序 以及多線程的支援,尤其多多線程),不能所有的 caller 都等待一個變量的狀态,這樣可能會出現某一個caller 長期饑餓的情況。
是以 Linux kernel 實作的自旋鎖是需要排隊機制的(當然,linux 核心支援了很多不同的硬體架構,不同架構下的spinlock的實作因為各自的架構原因都是有差異的,這裡我們介紹一個比較有代表性的 arm 架構)
如下圖是 arm 架構下的 spinlock 實作的形态,需要利用 tickets 維護一個排隊機制:
先看看 spinlock 的鎖結構體内容:
typedef struct {
union {
u32 slock;
struct __raw_tickets {
#ifdef __ARMEB__
u16 next;
u16 owner;
#else
u16 owner; /* 辨別目前程序 認為是誰正在持有鎖 */
u16 next; /* 唯一辨別一個 無法搶占spinlock 的程序 */
#endif
} tickets;
};
} arch_spinlock_t;
tickets
内部的兩個
uint16
類型的變量用來維護不同spinlock 之間的等待隊列。
再看看以上流程圖,加鎖以及解鎖 時的排隊部分邏輯如下:
- 初始時 spinlock 的核心字段 next = owner = 0
- 程序1 首次拿到spin_lock,會本地儲存下next的值,即 next = 0,并将 spinlock 的 next 字段原子加1。
- 獲得鎖的前提是,程序本地的 next 和 owner相等,該程序才能獲得鎖。
- 接下來 程序2 嘗試搶占spin_lock,發現此時 spin_lock 的next值為1(程序1 搶占之後 原子自增了1),先儲存到程序本地,然後再次執行spinlock 本身的next 值 原子加一。此時 spinlock的 owner 仍然為0。因為 對于程序2,next = 1 , owner = 0,兩者不想等,是以進行自旋。
- 同理程序3 和程序 4 也想要搶占 spinlock 鎖,程序3 先到,将next = 2 儲存到程序本地 讓spinlock 加一,并進入自旋。程序4 将next = 3 儲存到本地,讓spinlock 加一 進入自旋。
- 程序1 處理完臨界區釋放鎖,會讓 spinlock 的 owner 加1,因為程序2 自旋時一直 check 程序本地的 next 和 spinlock 的 owner字段是否相等,此時 lock.owner = 1 , 程序2 的 next = 1,已經相等了。是以程序2 持有了鎖。
- 程序2 處理完臨界區釋放鎖,會讓 spinlock 的 owner 再次加一,變成了2,就和程序3 的 next 字段相等了,這樣程序3就持有了鎖。依次,程序4也會持有鎖。
代碼中 arm架構的 加鎖流程如下:
static inline void arch_spin_lock(arch_spinlock_t *lock)
{
unsigned long tmp;
u32 newval;
arch_spinlock_t lockval; // 程序/線程 本地儲存的 spinlock 鎖資訊,主要維護next 和 owner
prefetchw(&lock->slock); // 從記憶體中讀取 不同程序/線程 間傳遞的 spinlock 資訊到L2 cache
__asm__ __volatile__(
"1: ldrex %0, [%3]\n" // 原子讀取 lock資訊,因為已經prefetch到cpu-cache了,是以不需要鎖記憶體總線
" add %1, %0, %4\n" // 自增
" strex %2, %1, [%3]\n" // 自增的結果原子更新到 spinlock變量
" teq %2, #0\n"
" bne 1b"
: "=&r" (lockval), "=&r" (newval), "=&r" (tmp)
: "r" (&lock->slock), "I" (1 << TICKET_SHIFT)
: "cc");
/* 程序 check 本地的next 和 讀取到的spinlock 的 owner字段是否相等,不等則自旋 */
while (lockval.tickets.next != lockval.tickets.owner) {
wfe(); // 類似 x86_64 的 pause 指令,防止cpu 流水線失效造成的性能損耗
// 嘗試從記憶體中讀取 spinlock 本身的 owner字段
lockval.tickets.owner = READ_ONCE(lock->tickets.owner);
}
smp_mb(); // 記憶體屏障
}
解鎖代碼就比較簡單了,spinlock 的 owner 字段加一就好了。
static inline void arch_spin_unlock(arch_spinlock_t *lock)
{
smp_mb();
lock->tickets.owner++;
dsb_sev();
}
到此,整個 PG spinlock的基本體系就描述完了,當然核心的spinlock 實作比較多,也有一些依賴排隊論 實作的
qspinlock
,有更多的細節。
對于我們來說,PG 本身實作的spinlock 在 通用架構下已經是對硬體非常友好的實作方式了,而且提供了 timeout 和 retry limit 這樣的限制,最大程度得降低了 spinlock 本身不當使用的場景下對整體性能的影響。
對于 PG 核心的開發者們來說,spinlock 本身的使用原則肯定是 臨界區執行時間非常短的場景。
接下來我們一起看看 LWLock 的實作方式,它主要用來保護 PG 内部非常多的存儲在共享記憶體中的資料結構。
LWLocks
LWLocks 在 PG 内部起着非常重要的作用,保護了對衆多共享記憶體變量的通路以及修改。
對于輕量鎖來說本身的使用形态可能比較接近讀寫鎖(讀讀共享,讀寫加鎖,寫寫加鎖),但是PG 為了保證加鎖過程中的性能以及減少鎖沖突會有一些額外的優化(維護了等待隊列)。
InitializeLWLocks 初始化輕量鎖
關于輕量鎖實作部分的主要代碼是在
lwlock.c
中,輕量鎖本身底層實作(加鎖/解鎖)都是一樣的,但是為了降低鎖沖突,PG 為每一個子系統/子結構 配置設定了一個輕量鎖變量,也做了一些鎖變量的分類。
-
INDIVIDUAL_LWLOCKS,顧名思義,這種輕量鎖變量隻為一些 特定的共享記憶體變量提供保護。這一些鎖變量的數量都是比較固定的,所處的位置以及保護的臨界區也是 PG 内部最為重要的一部分。
比如 下圖 async 中保護 asyncCtl 共享記憶體變量的 就隻用
變量,保護 autovacuum 程序正常運作的就隻用 AsyncCtlLock
變量 :AutvacuumLock
- PG 在
中定義了很多 individual 輕量鎖變量,這一些變量都會被初始化放在 lwlocknames.txt
MainLWLockArray
全局數組裡,友善随時取用。
初始化代碼
中的下面這一部分邏輯就是主要初始化他們:InitializeLWLocks
-
Name tranches locks
這一種鎖主要是一些不在特定場景使用的輕量鎖,或者使用者自定義新的輕量鎖,自己使用。
typedef enum BuiltinTrancheIds
{
LWTRANCHE_CLOG_BUFFERS = NUM_INDIVIDUAL_LWLOCKS,
LWTRANCHE_COMMITTS_BUFFERS,
LWTRANCHE_SUBTRANS_BUFFERS,
LWTRANCHE_MXACTOFFSET_BUFFERS,
LWTRANCHE_MXACTMEMBER_BUFFERS,
LWTRANCHE_ASYNC_BUFFERS,
LWTRANCHE_OLDSERXID_BUFFERS,
LWTRANCHE_WAL_INSERT,
LWTRANCHE_BUFFER_CONTENT,
LWTRANCHE_BUFFER_IO_IN_PROGRESS,
LWTRANCHE_REPLICATION_ORIGIN,
LWTRANCHE_REPLICATION_SLOT_IO_IN_PROGRESS,
LWTRANCHE_PROC,
LWTRANCHE_BUFFER_MAPPING,
LWTRANCHE_LOCK_MANAGER,
LWTRANCHE_PREDICATE_LOCK_MANAGER,
LWTRANCHE_PARALLEL_HASH_JOIN,
LWTRANCHE_PARALLEL_QUERY_DSA,
LWTRANCHE_SESSION_DSA,
LWTRANCHE_SESSION_RECORD_TABLE,
LWTRANCHE_SESSION_TYPMOD_TABLE,
LWTRANCHE_SHARED_TUPLESTORE,
LWTRANCHE_TBM,
LWTRANCHE_PARALLEL_APPEND,
LWTRANCHE_SXACT,
LWTRANCHE_FIRST_USER_DEFINED
} BuiltinTrancheIds;
每一個 這種類型的輕量鎖變量會被單獨注冊,有屬于自己的 id 辨別以及名字,開發者需要加,也需要通過如下方式注冊
當然,這一些輕量鎖變量會單獨放在
&NamedLWLockTrancheArray
全局數組中, 初始化的時候會從 individual 個鎖之後開始初始化接下來的 擁有命名的輕量鎖。
static void
InitializeLWLocks(void)
{
int numNamedLocks = NumLWLocksByNamedTranches();
...
/* Initialize named tranches. */
if (NamedLWLockTrancheRequests > 0)
{
char *trancheNames;
NamedLWLockTrancheArray = (NamedLWLockTranche *)
&MainLWLockArray[NUM_FIXED_LWLOCKS + numNamedLocks];
trancheNames = (char *) NamedLWLockTrancheArray +
(NamedLWLockTrancheRequests * sizeof(NamedLWLockTranche));
lock = &MainLWLockArray[NUM_FIXED_LWLOCKS];
...
}
}
這一些輕量鎖變量的所有具體使用場景,是我們本節沒有精力關注的,主要還是關注在鎖本身的實作上,關注其實作細節,有我們可以學習借鑒的地方。
LWLockAcquire 加鎖
在 PG 7.0 版本以及之前的版本,LWLock 的加鎖實作是直接通過 spinlock 來實作的。但是輕量鎖本身的應用場景對鎖本身提出了兩個比較重要的需求:
- 對于讀讀場景,我們希望可以無鎖方式去讀,而讀寫 或者 寫寫 這樣有修改的場景則需要有鎖來進行保護
- 在有修改的場景,不希望 有部分操作很難甚至永遠搶不到鎖的現象。
對于這樣的需求,僅僅隻用spinlock 顯然無法實作。
對于第一個需求,在 LWLock 的實作中提出了兩種主要的鎖模式
LWLockMode
,
LW_EXCLUSIVE
和
LW_SHARED
。當然,實際實作中還增加了一種額外的鎖模式
LW_WAIT_UNTIL_FREE
,這個模式下所有的操作都是需要等待的。
先看一下鎖資料結構:
typedef struct LWLock
{
uint16 tranche; /* tranche ID */
pg_atomic_uint32 state; /* state of exclusive/nonexclusive lockers */
proclist_head waiters; /* list of waiting PGPROCs */
#ifdef LOCK_DEBUG
pg_atomic_uint32 nwaiters; /* number of waiters */
struct PGPROC *owner; /* last exclusive owner of the lock */
#endif
} LWLock;
其中:
- tranche, 用來唯一辨別一個 輕量鎖變量,tranche id 以及 trance name 的類型和注冊方式前面已經講過了。
- state,辨別目前鎖的mode,是 exclusive 還是 noexclusive 的。
- Waiters,這是一個按照加鎖順序來儲存的等待鎖隊列(雙向連結清單實作的,其中的節點元素是
)。pgprocno
第一需求的實作方式是在上一個鎖解鎖的時對等待隊列中的 加鎖操作進行喚醒,如果第一個鎖操作是一個排他鎖(exclusive),那麼隻會喚醒一個鎖操作;如果第一個鎖操作是一個共享鎖(shared),那麼會喚醒目前等待隊列中的所有的共享鎖操作,如下圖:
喚醒鎖(解鎖)的代碼實作待會再細說,先對解鎖的大體流程有一個初步的了解,可以發現對于第一個需求這樣的解鎖肯定是滿足的,對于第二個需求,也就是加鎖過程中會構造一個鎖操作的隊列(同一個鎖變量被并發使用是)。
加鎖的主要步驟如下:
- 嘗試加鎖,如果成功就傳回
- 如果嘗試失敗,則需要等待。
- 這裡 PG 為了考慮部分輕量鎖操作的臨界區比較小,這裡本應做的等待并沒有直接去執行。而是先将目前鎖加入等待者隊列中。緊接着再次嘗試加鎖,此時對于那一些操作較小的臨界區可能已經釋放鎖了,此時嘗試加鎖可能會成功,如果成功了的話則需要回退添加到隊列中的鎖。
- 如果前面的步驟還是沒有加鎖成功,意味着需要有較長時間的等待。則會讓這把鎖等待在一個信号量上,直到這個信号量被釋放。
bool
LWLockAcquire(LWLock *lock, LWLockMode mode)
{
PGPROC *proc = MyProc;
bool result = true;
int extraWaits = 0;
...
for (;;)
{
bool mustwait;
/*
* 嘗試加鎖,如果成功,則直接傳回。
*/
mustwait = LWLockAttemptLock(lock, mode);
if (!mustwait)
{
LOG_LWDEBUG("LWLockAcquire", lock, "immediately acquired lock");
break; /* got the lock */
}
...
/* 先加入到鎖隊列中。 */
LWLockQueueSelf(lock, mode);
/* 再次嘗試加鎖,如果成功,則回退等待隊列。 */
mustwait = LWLockAttemptLock(lock, mode);
if (!mustwait)
{
LOG_LWDEBUG("LWLockAcquire", lock, "acquired, undoing queue");
LWLockDequeueSelf(lock);
break;
}
...
/* 如果失敗,則等待在一個信号量上。 */
for (;;)
{
PGSemaphoreLock(proc->sem);
if (!proc->lwWaiting)
break;
extraWaits++;
}
...
}
}
中間過程中 的一些鎖入隊 或者 嘗試加鎖操作 會統一由 spinlock 實作的一系列原子操作來保障。
- 比如 鎖對象加入雙向連結清單構造的隊列之前會有一個
進行 連結清單操作的保護,這個函數内部是LWLockWaitListLock
實作的 CAS 操作,底層是通過spinlock 實作的。pg_atomic_fetch_or_u32
- 還有一系列的 spinlock 實作的原子操作(原子寫,原子TAS 操作,原子Fetch等)都在
中。fallback.h
LWLockRelease 解鎖
解鎖過程需要解決的需求前面加鎖部分介紹的時候已經提到了。輕量鎖的核心是在保證不被餓死的情況下盡可能降低鎖的沖突,最直接的方式就是利用共享和排他模式來解決。
而這兩種模式的實作就是在解鎖的過程。
大體步驟如下:
- 建立 要喚醒的臨時鎖隊列
。wakeup
- 使用
進行加鎖,後續會操作 目前的lock 等待隊列LWLockWaitListLock
。waiters
- 周遊目前鎖的
,将每一個鎖操作添加到 waiters
臨時鎖隊列。wakeup
- 如果 第一個等待的鎖操作 模式是
,則break 周遊,否則将 非 EXCLUSIVE
的鎖模式 添加到 wakeup 隊列中。EXCLUSIVE
- 周遊
隊列,執行喚醒操作,主要是通過設定信号量(讓 每一個鎖操作 – proc 的waiter 的信号量 加一),恢複其可以消費的狀态。wakeup
對應的源代碼邏輯如下:
LWLockRelease
LWLockWakeup
static void
LWLockWakeup(LWLock *lock)
{
bool new_release_ok;
bool wokeup_somebody = false;
proclist_head wakeup;
proclist_mutable_iter iter;
/* 初始化 臨時的等待隊列。 */
proclist_init(&wakeup);
/* 周遊所有的 lock-waiters. */
proclist_foreach_modify(iter, &lock->waiters, lwWaitLink)
{
PGPROC *waiter = GetPGProcByNumber(iter.cur);
/* 已經添加到喚醒隊列的,且waiter->lwWaitMode 是排他模式就跳過。 */
if (wokeup_somebody && waiter->lwWaitMode == LW_EXCLUSIVE)
continue;
/* 否則,就沖原來的wiaters 中删除,添加到 wakeup臨時隊列的尾部。 */
proclist_delete(&lock->waiters, iter.cur, lwWaitLink);
proclist_push_tail(&wakeup, iter.cur, lwWaitLink);
if (waiter->lwWaitMode != LW_WAIT_UNTIL_FREE)
{
/*
* Prevent additional wakeups until retryer gets to run. Backends
* that are just waiting for the lock to become free don't retry
* automatically.
*/
new_release_ok = false;
/*
* Don't wakeup (further) exclusive locks.
*/
wokeup_somebody = true;
}
/*
* 對于第一個是排他鎖的,就直接break.
*/
if (waiter->lwWaitMode == LW_EXCLUSIVE)
break;
}
...
/* 喚醒 緩存到 wakeup臨時隊列中的鎖操作. */
proclist_foreach_modify(iter, &wakeup, lwWaitLink)
{
PGPROC *waiter = GetPGProcByNumber(iter.cur);
LOG_LWDEBUG("LWLockRelease", lock, "release waiter");
proclist_delete(&wakeup, iter.cur, lwWaitLink);
/*
* Guarantee that lwWaiting being unset only becomes visible once the
* unlink from the link has completed. Otherwise the target backend
* could be woken up for other reason and enqueue for a new lock - if
* that happens before the list unlink happens, the list would end up
* being corrupted.
*
* The barrier pairs with the LWLockWaitListLock() when enqueuing for
* another lock.
*/
pg_write_barrier();
waiter->lwWaiting = false;
/* 主要通過操作這個waiter等待的信号量,會對信号量的值+1,來恢複信号量可以在加鎖部分繼續消費的能力。 */
PGSemaphoreUnlock(waiter->sem);
}
輕量鎖 利用spinlock 實作的一系列原子變量,保障了内部資料結構并發通路的安全性。
為了滿足上層應用/調用者 需求(降低鎖沖突 ,減少長期無法加鎖/餓死的情況),分别實作了 共享模式和排他模式來減少部分場景的鎖沖突 以及 等待隊列來減少鎖操作餓死的情況,提供了按照鎖操作的順序來加鎖的能力。
當然,LWLock 本身為了性能的考慮,内部也有一些代碼細節(比如第一次嘗試加鎖之後不成功,會放入等待隊列,再一次嘗試加鎖,對于臨界區較小的場景,這樣能夠快速得到鎖,不需要再次陷入信号量的長期等待中)。
接下來再一起看看 PG 内部最為複雜的鎖類型 – 正常鎖。
Regular Locks
正常鎖它保護的臨界區是資料庫對象的操作,而不是單純的共享記憶體變量或者某一個原子變量。在PG内部資料庫對象包括 表、頁面、元組等,Regular lock 在這一些對象的保護性質中就像是讀寫鎖,在這裡聽起來并沒有什麼複雜度,和 LWLock 的作用大同小異?
Regular locks 複雜度的展現在于使用者上層較多的 DML/DDL 語句對不同的資料庫對象的操作 保證安全 的情況下盡最大可能提升性能,這才是核心。比如 select 一個表的一個元組,總不能因為 有其他對該表的 delete/update 事務操作就像讀寫鎖一樣阻塞等待吧?并發得針對一個表進行修改 (alter-table) + update /delete 不能出現互相等待的情況吧,還需要有死鎖檢測。
是以,如果在衆多的DML/DCL 語句中 操作衆多的 資料庫對象 來定制一套通用的規則保證性能最大化 且 不會出現類似死鎖的安全問題,那複雜度就上來了。
鎖模式 以及 相容性
Regular locks 總共提供了8種鎖模式,鎖模式這裡的區分主要是為了對 DML 和 DDL 操作進行區分,保證安全性的情況下讓不同的操作一起執行的時候擁有最大的性能。
8種鎖模式 以及 加鎖對應的主要操作語句類型 如下:
#define AccessShareLock 1 /* SELECT 最低級别的鎖 */
#define RowShareLock 2 /* SELECT FOR UPDATE/FOR SHARE */
#define RowExclusiveLock 3 /* INSERT, UPDATE, DELETE */
#define ShareUpdateExclusiveLock 4 /* VACUUM (non-FULL),ANALYZE, CREATE INDEX
* CONCURRENTLY */
#define ShareLock 5 /* CREATE INDEX (WITHOUT CONCURRENTLY) */
#define ShareRowExclusiveLock 6 /* like EXCLUSIVE MODE, but allows ROW
* SHARE */
#define ExclusiveLock 7 /* blocks ROW SHARE/SELECT...FOR UPDATE */
#define AccessExclusiveLock 8 /* ALTER TABLE, DROP TABLE, VACUUM FULL,
* and unqualified LOCK TABLE ,對系統表進行操作時會申請該鎖*/
這8種鎖之間的相容性如下表:
Mode | (1) | (2) | (3) | (4) | (5) | (6) | (7) |
AccessShareLock (1) | ❌ | ||||||
RowShareLock (2) | ❌ | ❌ | |||||
RowExclusiveLock (3) | ❌ | ❌ | ❌ | ||||
ShareUpdateExclusiveLock (4) | ❌ | ❌ | ❌ | ❌ | |||
ShareLock (5) | ❌ | ❌ | ❌ | ❌ | |||
ShareRowExclusiveLock (6) | ❌ | ❌ | ❌ | ❌ | ❌ | ||
ExclusiveLock (7) | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | |
AccessExclusiveLock (8) | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ |
鎖模式相容的意思是 當我們加鎖的時候,相容的鎖類型之間不會互相阻塞;不相容的模式 對于後加鎖的事務操作會阻塞等鎖,具體如何等待擷取鎖的邏輯後續會較長的描述。
接下來看幾個相容性相關的簡單例子:
-
AccessExclusiveLock 和 AccessShareLock
主要是保護對系統表的操作,也就是 DDL 操作,這種鎖模式與所有的鎖模式都不相容。AccessExclusiveLock
s1 : begin;
s1 : alter table a add c3 int;
s2 : select relation::regclass, pid, mode,granted,fastpath from pg_locks where relation = 'a'::regclass;
relation | pid | mode | granted | fastpath
----------+---------+---------------------+---------+----------
a | 4016693 | AccessExclusiveLock | t | f
(1 row)
s3 : select * from a; # 卡住,因為不相容,需要等鎖,直到 s1 的事務送出。
s2 : select relation::regclass, pid, mode,granted,fastpath from pg_locks where relation = 'a'::regclass;
relation | pid | mode | granted | fastpath
----------+---------+---------------------+---------+----------
a | 4017039 | AccessShareLock | f | f
a | 4016693 | AccessExclusiveLock | t | f
# 此時 s3 還沒有擷取到鎖,可以看到 granted 是false
(2 rows)
s1 : commit;
s3 : # 恢複執行
c1 | c2 | c3
----+-----+----
11 | 333 |
3 | 333 |
(2 rows)
s2 : select relation::regclass, pid, mode,granted,fastpath from pg_locks where relation = 'a'::regclass;
relation | pid | mode | granted | fastpath
----------+---------+-----------------+---------+----------
a | 4017039 | AccessShareLock | t | f
(1 row)
# 此時 s3 加鎖成功, granted 為 true. 因為s3 還沒有送出,是以還持有鎖。
由上面的案例可以很明顯的發現
AccessExclusiveLock
的相容性是最差的,因為它是表鎖,涉及到一些中繼資料(系統表 catalog)的操作,是以持鎖期間需要保證這段時間内不會有其他任何操作能夠通路或者操作這個表。
系統表能夠看到整個 資料庫内部的所有鎖模式的視圖,上面提到的幾列含義分别如下:
pg_locks
- relation, 目前資料庫内部唯一辨別一張表,這裡會展示表名。
- pid, 目前操作所屬的backend 程序id
- mode , 這個操作要加鎖的模式
- granted, 是否獲得了目前模式的鎖,是 則為 t – true, 否 則為 f – false.
- fastpath, 是否進入了快速路徑(後續會細說,就是提升性能的一種方式), t 或者 f 同上。
-
ExclusiveLock , RowExclusiveLock , RowShareLock, AccessShareLock
模式相容性也比較差,它會阻塞除了 ExclusiveLock
AccessShareLock
之外的所有的鎖。
行鎖 和 RowExclusiveLock
以及 RowExclusiveLock
說的是相容的,但是前提是不會操作到同一行 即 同一個元組,如果操作的是同一個元組的話那還是會有不相容的問題(額外加一個 RowShareLock
),如下案例:ExclusiveLock
s1 : begin;
s1 : select * from a for update;
s2 : begin;
s2 : update a SET c3 = 2; # 阻塞,因為s1 select for update了,需要送出之後 s2才能繼續加鎖
s3 : select relation::regclass, pid, mode,granted,fastpath from pg_locks where relation = 'a'::regclass;
relation | pid | mode | granted | fastpath
----------+---------+------------------+---------+----------
a | 4017039 | RowExclusiveLock | t | t # s2 ,update 操作要加 RowExclusiveLock 鎖
a | 4016693 | RowShareLock | t | t # s1, select for update 加 `RowShareLock` 模式
a | 4017039 | ExclusiveLock | t | f # s2
(3 rows)
s1 : commit;
s3 : select relation::regclass, pid, mode,granted,fastpath from pg_locks where relation = 'a'::regclass;
relation | pid | mode | granted | fastpath
----------+---------+------------------+---------+----------
a | 4017039 | RowExclusiveLock | t | t # s1 送出了,僅剩下 s2 的update操作了,隻需要保留`RowExclusiveLock`即可
(1 row)
可以看到 不同僚物之間當
update
操作 和
select ... for update
會操作同一行資料時 對于 update 操作的程序 除了 正常要加的
RowExclusiveLock
模式之外,還需要加一個
ExclusiveLock
,保證 s1 事務送出之後目前的 update 才會有效。
此時,仍然保留 s2 的事務不送出,如果我們嘗試 update 一個其他行的資料,那就不會有沖突了:
s4 : begin;
s4 : update a set c3 = 3 where c1 = 3;
s3 : select relation::regclass, pid, mode,granted,fastpath from pg_locks where relation = 'a'::regclass;
relation | pid | mode | granted | fastpath
----------+---------+------------------+---------+----------
a | 4017039 | RowExclusiveLock | t | t # s2 的 未送出的 update.
a | 4016693 | RowExclusiveLock | t | t # s4 的 update 操作
(2 rows)
- 當然,PG 還提供了
語句來直接對一個事務加指定模式的鎖,做一些鎖模式的正确性測試。LOCK
s5 : begin;
s5 : lock TABLE a in share mode;
s5 : select relation::regclass, pid, mode,granted,fastpath from pg_locks where relation =
'a'::regclass;
relation | pid | mode | granted | fastpath
----------+---------+-----------+---------+----------
a | 4016988 | ShareLock | t | f
(1 row)
其他像share 相關的lock 模式就是建立索引時會加的。
從上面簡單的例子能夠較為清楚得看到一些相容性的基本情況,對于不相容的鎖模式也很明顯,會阻塞直到其他先持有鎖的事務送出/終止(完成釋放鎖)。
資料結構
介紹詳細的資料結構内容之前先粗略理清楚實作 Regular 過程中的幾種主要的鎖資料結構。
-
存在于共享記憶體中,用來儲存目前資料庫中所有事物的鎖對象,被稱為 主鎖表(LockMethodLockHash)LOCK
-
存在于共享記憶體中,用來儲存目前程序(會話 – backend)的事務鎖狀态,用于建立鎖和程序會話的關系。PROCLOCK
-
存儲到會話本地 – 非共享,因為實際操作過程中會話可能會在一個鎖對象上申請多次相同類型的鎖,這樣就沒有必要做沖突檢測,直接從會話本地拿就好了。LOCALLOCK
在描述這三個主要的正常鎖資料結構細節之前,先通過如下流程圖整體看看這三種鎖之間的關系,就能有一個整體的認識了:
以上流程圖較長的描述了三種主要的鎖資料結構之間的互相指向關系,需要注意的是:
-
是儲存在會話本地(backend 程序本地),對其他的會話不可見,是以從上面的 LOCALLOCK
資料結構中能看到其儲存的 LOCK 以及 PROCLOCK 隻有屬于自己會話的。同時維護了一個可以同台擴容的 LOCALLOCK
LOCALLOCKOWNER
數組來讓自己能夠管理同一個會話内部多個不同的鎖之間的歸屬關系。因為同一個會話内部可能會加同一種類型的鎖多次,這樣在釋放資源的時候就能夠按照歸屬關系有序釋放。
當然,
存在和核心目的還是為了一個會話 避免頻繁加同一種模式鎖的時候去通路共享記憶體中的 LOCALLOCK
和LOCK
PROCLOCK
,進而降低加鎖性能。
關于
資料結構的管理形态如下,本質上是一個單連結清單,希望能夠辨別每一個ResourceOwnerData
節點所屬的初始資料總管(執行器的 ResourceOwnerData
會辨別目前執行語句中所有的加鎖操作都有一個可以追溯的起始資料總管),進而快速得申請釋放鎖,不同的 CreatePortal
之間也有連結清單維護的所屬關系。ResourceOwnerData
- 對于
和 LOCK
來說,它們本身都存儲在共享記憶體中,會被整個資料庫看到,不同的會話都能看到全局的一個鎖視圖,這個時候對這兩種資料結構的通路就需要提供一些能夠通路到全局的子變量。比如 PROCLOCK
的 LOCK
變量,是一個雙向連結清單,能夠通路到所有的 procLocks
;同時PROCLOCKS
的 PROCLOCK
變量,能夠通路到自己的 tag
結構,也能通路到自己所屬的 LOCK
結構。PROC
是唯一辨別一個會話的核心結構,儲存使用者通路資料庫時啟用的一個會話backend程序所有的上下文資訊。其内部也存儲了一個目前會話通路資料操作所添加的鎖模式數組
PROC
,能夠通路到自己所有的
myProcLocks
對象。
PROCLOCK
初始化 正常鎖
對正常鎖的初始化過程主要通過
InitLocks
函數來實作,會為以上三個資料結構各建立一個hash表,用來儲存鎖資料結構。
-
,資料庫級别的鎖表,為Lock 資料結建構立的hash表,hash key 用LockMethodLockHash
通過hash函數生成,整個hash表會存儲到共享記憶體中。LOCKTAG
-
, 程序級别的鎖表,為 LockMethodProcLockHash
資料結建構立的hash 表,hash key用 ProcLock
通過hash函數生成,同樣會存儲到共享記憶體中。PROCLOCKTAG
-
本地鎖表,為 LockMethodLocalHash
資料結構的建立的hash表,LocalLock
通過hash 函數生成hash-key, 存儲到本地。LOCALLOCKTAG
關于
LOCKTAG
或者
PROCLOCKTAG
這樣的标記 都是為了存儲這個鎖 鎖定的對象類型、對象id 以及 加鎖方法。比如 對
LOCKTAG
的一個宏定義初始化:
#define SET_LOCKTAG_RELATION(locktag,dboid,reloid) \
((locktag).locktag_field1 = (dboid), \
(locktag).locktag_field2 = (reloid), \
(locktag).locktag_field3 = 0, \
(locktag).locktag_field4 = 0, \
(locktag).locktag_type = LOCKTAG_RELATION, \
(locktag).locktag_lockmethodid = DEFAULT_LOCKMETHOD)
這個鎖的對象類型是 relation,也就表鎖。在表鎖參與的情況下對 LOCKTAG的初始化還需要 dboid (資料庫對象id)以及 reloid (表對象id) 的參與。同樣的還有
Tuple
鎖 以及
page
鎖,tuple的話就需要額外儲存 blocknum 以及 offnum id資訊來在資料表内唯一辨別一個tuple。
回到正常鎖的初始化,主體邏輯是在
InitLocks
中進行的,它被
CreateSharedMemoryAndSemaphores
調用,這個函數則是postmaster或者backend程序每次啟動的時候都必須執行的邏輯,用來初始化自己程序需要的一些全局記憶體變量或者共享記憶體變量。
在 InitLocks 中,對三個資料結構的初始化邏輯如下:
void
InitLocks(void)
{
HASHCTL info;
long init_table_size,
max_table_size;
bool found;
...
MemSet(&info, 0, sizeof(info));
info.keysize = sizeof(LOCKTAG);
info.entrysize = sizeof(LOCK);
info.num_partitions = NUM_LOCK_PARTITIONS;
/* 初始化 存儲資料庫級别鎖 的hash表。 */
LockMethodLockHash = ShmemInitHash("LOCK hash",
init_table_size,
max_table_size,
&info,
HASH_ELEM | HASH_BLOBS | HASH_PARTITION);
...
/* 初始化 程序級别鎖的 hash表。 */
LockMethodProcLockHash = ShmemInitHash("PROCLOCK hash",
init_table_size,
max_table_size,
&info,
HASH_ELEM | HASH_FUNCTION | HASH_PARTITION);
...
/* 快速鎖機制需要用到的資料結構。 */
FastPathStrongRelationLocks =
ShmemInitStruct("Fast Path Strong Relation Lock Data",
...
/* 本地鎖 的hash表。 */
LockMethodLocalHash = hash_create("LOCALLOCK hash",
16,
&info,
HASH_ELEM | HASH_BLOBS);
因為
LOCK
和
PROCLOCK
本身需要儲存到共享記憶體中,是以會通過
ShmemInitHash
函數進行初始化,同時hash表需要分桶
HASH_PARTITION
,而對于
LOCKLOCK
則儲存在程序本地,并且不需要分桶,是以它的初始化并沒有加入
HASH_PARTITION
标記。
快速鎖機制是為了讓加多次弱鎖(鎖模式部分介紹過的8種鎖模式中有三種互相相容, 隻有這三種是弱鎖,其他的都是強鎖)的程序儲存資訊到程序本地而不用讓其他程序知道,弱鎖場景是比較通用的場景,這樣能夠提升加鎖的性能,不需要每次去共享記憶體中加載 主鎖表和程序鎖表的資訊(不需要走死鎖檢測流程)。
加鎖 LockAcquire
接下來就進入了正常鎖的核心鍊路,加鎖的實作了,主要邏輯還是如何利用前面提到的三種資料結構來加速鎖的擷取 或者 降低等待者對性能的影響。
LockAcquire
-->
LockAcquireExtended
,基本步驟如下:
主要的輸入參數為:
locktag
鎖對象的類型,
lockmode
8種 鎖模式 中的一種。
- 先利用輸入的 logtag 作為hash-key,在本地鎖表對應的hash表(LockMethodLocalHash)中查找,沒有找到則建立一個,存儲到hash表中。
- 如果目前鎖對象加鎖次數
大于 0,則這個鎖意味着被别人持有了,則直接傳回 nLocks
.LOCKACQUIRE_ALREADY_HELD
- 如果鎖類型是
且 鎖對象是 Relation,則會嘗試配置設定一個 transactionid 來在後續加鎖成功之後寫一條 WAL record.AccessExclusiveLock
- 如果
為真,則表示滿足快速鎖的條件,申請的是弱鎖(弱鎖,鎖模式 < EligibleForRelationFastPath
ShareUpdateExclusiveLock
):
a. 如果 強鎖 的計數不為0,則表示已經有強鎖了,因為不相容,則無法成功擷取鎖。
b. 否則,通過
進行加鎖,成功了就傳回加鎖成功。FastPathGrantRelationLock
- 如果申請的是強鎖,
這個為真,則會先将目前程序持有的 強鎖的計數自增,通過 ConflictsWithRelationFastPath
并将快速鎖資訊從會話本地轉移到主鎖表中(共享記憶體中)。FastPathTransferRelationLocks
- 要加的鎖 不在本地鎖表,也不在 FashPath中,則需要通路程序鎖表和主鎖表。目前申請鎖類型是強關系鎖,則通過
嘗試從主鎖表中查找 或者建立 目前的鎖項。SetupLockInTable
- 如果這種鎖模式需要做沖突檢測 且 沒有其他會話在等待這把鎖, 那 通過
直接執行鎖模式的沖突檢測(并不是死鎖檢測,隻是确認已經持有的鎖和目前鎖是否沖突);否則目前會話也需要進入 LockCheckConflicts
的等鎖邏輯,這裡WaitOnLock中會有死鎖檢測的邏輯,防止循環等待問題。WaitOnLock
- 如果 第三步執行成功了,則需要寫入一條 WAL-record(友善其他的主從程序恢複的時候能夠知道這裡加了一把表鎖),傳回加鎖成功即可。
這幾步的源代碼實作如下:
第一步:查找本地鎖表
/* 仍然從InitLocks 初始化好的 儲存本地鎖表的hash表 LockMethodLocalHash 中查找是否有localtag對應的鎖 */
locallock = (LOCALLOCK *) hash_search(LockMethodLocalHash,
(void *) &localtag,
HASH_ENTER, &found);
/* 沒有則建立一個 */
if (!found)
{
locallock->lock = NULL;
locallock->proclock = NULL;
locallock->hashcode = LockTagHashCode(&(localtag.lock));
locallock->nLocks = 0;
locallock->holdsStrongLockCount = false;
locallock->lockCleared = false;
locallock->numLockOwners = 0;
locallock->maxLockOwners = 8;
locallock->lockOwners = NULL; /* in case next line fails */
locallock->lockOwners = (LOCALLOCKOWNER *)
MemoryContextAlloc(TopMemoryContext,
locallock->maxLockOwners * sizeof(LOCALLOCKOWNER));
}
第二步:檢查該鎖在本地鎖表中的加鎖次數
因為
nLocks
大于0 就意味着這個鎖已經被目前程序持有了,會做一個resource owner的一個更新,将目前owner添加到 前面介紹鎖資料結構中提到的 ResourceOwner 連結清單中。
/* nLocks 辨別目前locklock 被持有的次數。 */
if (locallock->nLocks > 0)
{
/* 繼續增加次數,并将本次的resource owner 添加到本地管理的 resource owner節點連結清單中。 */
GrantLockLocal(locallock, owner);
if (locallock->lockCleared)
return LOCKACQUIRE_ALREADY_CLEAR;
else
/* 傳回已經持有了。 */
return LOCKACQUIRE_ALREADY_HELD;
}
**第三步:針對表鎖 且鎖模式為AccessExclusiveLock 配置設定一個transactionid **
主要目的是為了記錄一條 wal-log ,對于表鎖這種超大粒度的鎖需要讓其他程序拿到這個wal-log 進行recovery的時候能夠看到這裡曾經加過表鎖。
/* 表鎖的check如下,且要求本次加鎖不是 recovery期間 */
if (lockmode >= AccessExclusiveLock &&
locktag->locktag_type == LOCKTAG_RELATION &&
!RecoveryInProgress() &&
XLogStandbyInfoActive())
{
LogAccessExclusiveLockPrepare();
log_lock = true;
}
第四步:進入快速鎖模式
快速鎖模式是針對會話加弱鎖時減少對主鎖表/程序鎖表 等存儲在共享記憶體鎖資訊的通路,弱鎖之間是互相相容的,是以不需要做死鎖檢測。當然,快速鎖機制添加成功的前提是目前會話之前沒有添加過強鎖 且 還有充足的儲存弱鎖的位置,那就能夠加鎖成功。
/*EligibleForRelationFastPath 用來檢查目前的tag和mode 是否滿足進入快速鎖機制的條件。 */
if (EligibleForRelationFastPath(locktag, lockmode) &&
FastPathLocalUseCount < FP_LOCK_SLOTS_PER_BACKEND)
{
...
/* 使用輕量鎖保護這個加鎖過程。 */
LWLockAcquire(&MyProc->backendLock, LW_EXCLUSIVE);
/* 先檢查強鎖計數,如果不為0,表示已經加過強鎖了,則無法進入快速鎖模式。 */
if (FastPathStrongRelationLocks->count[fasthashcode] != 0)
acquired = false;
else
/* 否則嘗試加鎖。 */
acquired = FastPathGrantRelationLock(locktag->locktag_field2,
lockmode);
LWLockRelease(&MyProc->backendLock);
/* 如果加鎖成功,直接傳回成功。*/
if (acquired)
{
/*
* The locallock might contain stale pointers to some old shared
* objects; we MUST reset these to null before considering the
* lock to be acquired via fast-path.
*/
locallock->lock = NULL;
locallock->proclock = NULL;
GrantLockLocal(locallock, owner);
return LOCKACQUIRE_OK;
}
}
static bool
FastPathGrantRelationLock(Oid relid, LOCKMODE lockmode)
{
uint32 f;
uint32 unused_slot = FP_LOCK_SLOTS_PER_BACKEND;
/* relid 是唯一辨別一個資料庫的表,查找已有的儲存的快速鎖數組(16個)中是否有這個relid,有則直接傳回真。 */
/* Scan for existing entry for this relid, remembering empty slot. */
for (f = 0; f < FP_LOCK_SLOTS_PER_BACKEND; f++)
{
if (FAST_PATH_GET_BITS(MyProc, f) == 0)
unused_slot = f;
else if (MyProc->fpRelId[f] == relid)
{
Assert(!FAST_PATH_CHECK_LOCKMODE(MyProc, f, lockmode));
FAST_PATH_SET_LOCKMODE(MyProc, f, lockmode);
return true;
}
}
/* 沒有找到,則拿空閑slot儲存目前鎖,同樣直接傳回真就好了。 */
/* If no existing entry, use any empty slot. */
if (unused_slot < FP_LOCK_SLOTS_PER_BACKEND)
{
MyProc->fpRelId[unused_slot] = relid;
FAST_PATH_SET_LOCKMODE(MyProc, unused_slot, lockmode);
++FastPathLocalUseCount;
return true;
}
/* No existing entry, and no empty slot. */
return false;
}
第五步:加強鎖的話需要轉移快速鎖存儲的鎖資訊到主鎖表中
弱鎖優先會嘗試能否進入快速鎖模式,也就是第四步。如果是目前會話加的是 強鎖,則會進入如下邏輯。
/* 對強鎖的檢查,主要是通過檢查mode 是否大于 ShareUpdateExclusiveLock. */
if (ConflictsWithRelationFastPath(locktag, lockmode))
{
uint32 fasthashcode = FastPathStrongLockHashPartition(hashcode);
/* 通過spinlock保護,自增強鎖的計數。 */
BeginStrongLockAcquire(locallock, fasthashcode);
/* 嘗試将 快速鎖機制中的鎖資訊轉移到主鎖表中。*/
if (!FastPathTransferRelationLocks(lockMethodTable, locktag,
hashcode))
{
/* 失敗了,則終止強鎖的加鎖過程。*/
AbortStrongLockAcquire();
if (locallock->nLocks == 0)
RemoveLocalLock(locallock);
if (locallockp)
*locallockp = NULL;
if (reportMemoryError)
ereport(ERROR,
(errcode(ERRCODE_OUT_OF_MEMORY),
errmsg("out of shared memory"),
errhint("You might need to increase max_locks_per_transaction.")));
else
return LOCKACQUIRE_NOT_AVAIL;
}
}
static bool
FastPathTransferRelationLocks(LockMethod lockMethodTable, const LOCKTAG *locktag,
uint32 hashcode)
{
...
/* 1. 周遊所有的程序項 */
for (i = 0; i < ProcGlobal->allProcCount; i++)
{
PGPROC *proc = &ProcGlobal->allProcs[i];
uint32 f;
/* 2. 找到目前鎖所在的資料庫id. */
if (proc->databaseId != locktag->locktag_field1)
{
LWLockRelease(&proc->backendLock);
continue;
}
/* 3. 找到了databaseId,則檢視目前會話内部的16個slot中 是否有目前表的relid. */
for (f = 0; f < FP_LOCK_SLOTS_PER_BACKEND; f++)
{
/* Look for an allocated slot matching the given relid. */
if (relid != proc->fpRelId[f] || FAST_PATH_GET_BITS(proc, f) == 0)
continue;
/*
* 4. 找到了relid,則進入轉移過程:先将快速機制儲存的所有鎖資訊
* 通過 SetupLockInTable 添加到主鎖表,完成後再從快速鎖中清理這個鎖資訊。
*/
。。。
for (lockmode = FAST_PATH_LOCKNUMBER_OFFSET;
lockmode < FAST_PATH_LOCKNUMBER_OFFSET + FAST_PATH_BITS_PER_SLOT;
++lockmode)
{
...
proclock = SetupLockInTable(lockMethodTable, proc, locktag,
hashcode, lockmode);
...
GrantLock(proclock->tag.myLock, proclock, lockmode);
FAST_PATH_CLEAR_LOCKMODE(proc, f, lockmode);
}
...
}
...
}
return true;
}
第六步:在主鎖表中查找或者建立目前強鎖項
/* 先從 主鎖表 -- LockMethodLockHash 中查找 + 建立;沒有找到則從 程序鎖表 -- LockMethodProcLockHash查找+建立 */
proclock = SetupLockInTable(lockMethodTable, MyProc, locktag,
hashcode, lockmode);
第七步:檢查添加的鎖是否與已有的鎖模式沖突,鎖模式沖突的情況下進入等鎖
if (lockMethodTable->conflictTab[lockmode] & lock->waitMask)
status = STATUS_FOUND;
else
/* 檢查鎖模式是否沖突,傳回ok 則表示能夠獲得鎖;否則就要進入等鎖模式。*/
status = LockCheckConflicts(lockMethodTable, lockmode,
lock, proclock);
等鎖的過程主要通過
WaitOnLock
函數實作,因為有強鎖沖突,是以需要嘗試死鎖檢測。
死鎖檢測的調用棧如下:
ProcSleep
CheckDeadLock
DeadLockCheckRecurse // 檢查soft-edge是否有死鎖
FindLockCycle // 檢查hard-edge是否有死鎖
PG 的死鎖檢測和大多數資料庫的實作都類似,采用的是WFG(Waits-For Graph) 有向圖,參與加鎖的所有程序作為有向圖中的一個個定點,如果程序A 等待程序B釋放鎖,則生成一條A->B的邊。如果存在環,則存儲死鎖。
有一些差異點的地方是 PG 除了維護程序等待已經被其他程序持有的鎖的邊(hard-edge) 之外 還會維護 不同等待程序之間的互相依賴邊(soft-edge),比如 程序A在B之後申請鎖,A和B 的鎖互相沖突,那麼PG 的鎖喚醒函數
ProcLockWakeup
會優先喚醒B擷取鎖,這個時候需要建立 A -->B 的一條邊來表示兩者的依賴關系,這種邊就是soft-edge,它們也需要單獨做死鎖檢測。
在函數
CheckDeadLock
中:
- 利用
函數先進行 soft-edge 的死鎖檢測,如果發現有死鎖,則後續會嘗試調整 内部的依賴關系來避免死鎖,利用這種方式會避免 abort目前事務,嘗試解決死鎖。DeadLockCheckRecurse
- 如果 soft-edge沒有死鎖,則在
檢測hard-edge 是否有死鎖,程序等待已持有鎖的其他程序釋放鎖,這個過程有死鎖問題,那PG 這裡會直接 elog(FATAL),來Abort 終止目前事務。FindLockCycle
因為死鎖檢測在PG的實作中還是有比較多的細節,這個就需要後續深入更詳細的優化細節之後再來單獨分享了。
第八步:記錄 AccessExclusiveLock 一條record-log
主要是為了針對相容性最差的鎖,需要記錄一條WAL日志,防止其他stand-by程序目前WAL recovery 時漏掉這個鎖(隻有這個鎖會與其他隻讀的鎖沖突 – SELECT 語句 對應的最弱的鎖模式 AccessShareLock ),導緻一些資料一緻性的問題,standby是隻讀的 pg 程序。
if (log_lock)
{
/*
* Decode the locktag back to the original values, to avoid sending
* lots of empty bytes with every message. See lock.h to check how a
* locktag is defined for LOCKTAG_RELATION
*/
/* 擷取第三步構造好的 transactionid, 并利用 LogAccessExclusiveLocks 将封裝好的log-tag 寫入到WAL中。*/
LogAccessExclusiveLock(locktag->locktag_field1,
locktag->locktag_field2);
}
到此完成加鎖之後傳回
LOCKACQUIRE_OK
即可。
解鎖 LockRelease
解鎖相對來說流程就簡單很多了:
- 從
查找LOCALLOCK,在它的owner數組裡找到與目前程序對應的元素,解除LOCALLOCK與ResourceOwner之間的關聯,并減小相應計數值。LockMethodLocalHash
- 将LOCALLOCK的加鎖次數(nLocks)減1,如果減為0了,表示目前程序不再持有鎖,則後續有兩種解鎖途徑,分别是快速鎖和主鎖表。
- 對于快速鎖,調用FastPathUnGrantRelationLock清除快速鎖的加鎖标記。如果解鎖成功即可傳回。
- 如果沒找到快速鎖,且LOCALLOCK.lock為空,說明被轉移到了主鎖表裡(在加鎖邏輯中,當申請快速鎖成功時,會把LOCALLOCK.lock置空)。
- 查找主鎖表
以及 LockMethodLockHash
,如果沒有找到,則blog-error。找到了 調用LockMethodProcLockHash
更新LOCK和PROCLOCK資訊。UnGrantLock
- 調用
:要麼删除主表項,要麼調用ProcLockWakeup()喚醒等待者,這裡會按照 WFG 中建構的 soft-edge 以及 hard-edge 依賴關系進行喚醒。CleanUpLock
解鎖的代碼流程鍊路整體簡單一些,就不展開了。
總結
到此整個PG的幾種鎖體系就描述完了,自低向上可以發現越來越複雜,代碼細節中的性能取舍在 PG 這樣擁有接近40年曆史的經典資料庫中展現的淋漓盡緻了。
最底層的
Spinlock
保護的對象是某一個變量,臨界區足夠小,需要考慮和硬體互動細節,不會很複雜。但是需要對各種體系結構下的CPU-記憶體 架構指令足夠精通才能寫出對硬體友好的極緻代碼,而這一部分也是對性能影響最重要的部分(這裡的性能比較好解決,因為有現成的解決方案,比如x86_64 架構的 lock + xchg 指令),因為調用次數足夠多。