Postgresql中使用CAS实现无锁队列

mingjie

发布于 2023-03-01 13:33:09

6800

发布于 2023-03-01 13:33:09

文章被收录于专栏：Postgresql源码分析

概述

Postgresql中的大锁很多，其中ProcArrayLock和XactSLRULock使用了无锁队列优化（PG中XID的分发也可以用这种机制优化，高压场景下效果不错）。

ProcArrayLock
- 优化前：事务提交清理proc的xid，所有进程争抢ProcArrayLock（PG的锁机制会用sem排队）。
- 优化后：第一个向队列加入元素的proc为leader，后续的proc使用cas将要做的加入队列，由leader统一做。
XactSLRULock
- 优化前：写CLOG时，不同进程争抢XactSLRULock（PG的锁机制会用sem排队），拿到锁才有资格写SLRU页面。
- 优化后：第一个向队列加入元素的proc为leader，后续的proc使用cas将要做的加入队列，由leader统一做。

关于XactSLRULock请参考《Postgresql源码（101）深入分析clog组提交（clog group updates）》

本篇只精简CAS部分的实现，具体请参考上面文章。

Postgresql中的CAS无锁队列逻辑总结

PG中CAS无锁队列最简代码（所有变量为int）

ProcArrayGroupClearXid
    ...
    ...
	nextidx = pg_atomic_read_u32(&procglobal->procArrayGroupFirst);
	while (true)
	{
		pg_atomic_write_u32(&proc->procArrayGroupNext, nextidx);

		if (pg_atomic_compare_exchange_u32(&procglobal->procArrayGroupFirst,
										   &nextidx,
										   (uint32) proc->pgprocno))
			break;
	}

pg_atomic_compare_exchange_u32为PG的CAS实现，在X86下使用汇编lock锁总线cmpxchgl实现：

static inline bool
pg_atomic_compare_exchange_u32_impl(volatile pg_atomic_uint32 *ptr,
									uint32 *expected, uint32 newval)
{
	char	ret;

	/*
	 * Perform cmpxchg and use the zero flag which it implicitly sets when
	 * equal to measure the success.
	 */
	__asm__ __volatile__(
		"	lock				\n"
		"	cmpxchgl	%4,%5	\n"
		"   setz		%2		\n"
:		"=a" (*expected), "=m"(ptr->value), "=q" (ret)
:		"a" (*expected), "r" (newval), "m"(ptr->value)
:		"memory", "cc");
	return (bool) ret;
}

pg_atomic_compare_exchange_u32的逻辑比较简单：

1参一定赋值给2参nextidx：nextidx = procArrayGroupFirst，这步非常重要，2参nextidx每次都被更新为共享内存中的新值（并发被别人修改了），后续可以在新的基础上做操作。
3参可能赋值给1参procArrayGroupFirst：procArrayGroupFirst = pgprocno（如果1参等于2参）

实例

考虑ProcArrayGroupClearXid三并发进入ProcArrayGroupClearXid函数的场景：

进程一：进入前

procArrayGroupFirst  -----> invalid <----- nextidx

第一次进入CAS nextidx和procArrayGroupFirst都等于invalid，所以CAS返回true，并且参1procArrayGroupFirst更新为procno1。（nextidx记录procArrayGroupFirst的旧值，也就是队列原来的头部）

                            invalid <----- nextidx
                               ^
                               | procArrayGroupNext 
                               |               
procArrayGroupFirst  -----> procno1

进程二：CAS后

                            invalid
                               ^
                               | procArrayGroupNext 
                               |               
                            procno1  <----- nextidx
                               ^
                               | procArrayGroupNext 
                               |               
procArrayGroupFirst  -----> procno2

进程三：CAS

                            invalid
                               ^
                               | procArrayGroupNext 
                               |               
                            procno1
                               ^
                               | procArrayGroupNext 
                               |               
                            procno2  <----- nextidx
                               ^
                               | procArrayGroupNext 
                               |               
procArrayGroupFirst  -----> procno2

这样就通过CAS形成了一个无锁队列，其中队列头指针procArrayGroupFirst，队列关系由procArrayGroupNext串联，nextidx指向队列前一个元素。

因为CAS保证了compare 和 swap的原子性，所以pg_atomic_compare_exchange_u32不会出现以下场景：

比较完了相同，但swap时被别的进程改为不同了。
比较完了不同，但swap时被别的进程改为相同了。

综上，就是Postgresql中使用CAS实现无锁队列的方法。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-02-28，如有侵权请联系 cloudcommunity@tencent.com 删除

postgresql

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

postgresql

登录后参与评论

0 条评论

热度