PostgreSQL数据库和复制状态机的关系

用Paxos/Raft中复制状态机的视角看数据库的话，还是挺有意思的。

复制状态机

下图是Raft论文中的复制状态机流程图：

有3个组件构成：一致性组件；日志组件；状态机；

1. 为了保证在崩溃恢复后的线性读，需要先写成功WAL日志后再应用状态机，否则，一旦写WAL失败会导致重启恢复后读取不到曾经读到过的数据；

2. 为了保证能够读得到刚刚写入的数据，需要先应用状态机，再给客户端回应ack；

3. 为了实现容错，在日志组件中引入了分布式一致性（Paxos/Raft），将日志复制多个副本且通过共识算法保证一致性；

PostgreSQL数据库的状态机

PostgreSQL数据库本质上也是一个复制状态机（只是状态机异常复杂）：

1. 被复制的日志：就是PG的WAL日志（redo日志）；

2. 状态机：一个个8KB的数据页面（Heap表、BTree索引树）；

WAL日志的作用有两个：一是完成持久性和原子性；二是通过主备间日志复制+回放完成容错。

不同点是数据库中在DML时是先在内存中修改页面（状态机）后再写WAL日志（不是先写WAL日志再修改页面），这么做的原因是，PG的WAL是物理日志只有先修改了页面才知道物理日志应该记录什么内容（对于违反约束的事务所产生的WAL也没必要）。怎么保证线性读呢？答案是无需做额外的工作，数据库的MVCC机制天然支持了事务在提交之前是不可见的，即使修改了内存中的页面，其他事务也读取不到新版本的记录只能读取到老版本的记录。新的修改在事务COMMIT的时候修改事务状态后对其他事务可见，而事务COMMIT之前需要保证WAL日志落盘，以保证崩溃恢复能恢复出事务数据。同时，内存中被修改的页面（状态机）在刷盘的时候也要求其对应的WAL日志先落盘。从落盘的角度看，仍然是先

整体顺序为：

1. 修改内存页面（Heap页面或者BTree页面），通过MVCC保证测试的修改不可见；

2. 此时能得到物理WAL内容，并写入WAL Buffer；

3. 第2步中产生的WAL进行刷盘；

4. 事务状态为COMMITED，此时该事务在内存中的修改对其他事务原子可见；

可以看出，状态机的修改分成了两个阶段：先该内存；等刷WAL成功之后再生效。所以，从落盘的顺序上看还是遵循了先写日志再修改状态机的顺序。

Paxos日志、Raft日志、WAL日志的关系

Paxos日志

Paxos算法描述的是单条日志的一致性，基于Paxos实现的分布式系统理论上是可以乱序commit的，因此日志可能会有空洞，也就是说后产生的日志2可以优先于日志1 commit。此时需要做额外的工作以保证业务上的因果序，比如日志1和日志2修改状态机中的数据是完全没有依赖关系且允许并发执行的（比如：修改了两个库中的数据），那么就可以乱序commit和apply，否则需要按序commit和apply。另外，乱序commit后日志文件就会有洞，要求所有参与方，在崩溃恢复中需要逐个重放检查点后所有的日志再来一次投票以merge出完整的数日志流。当然，业务层也可以选择仅使用顺序commit，简化工程实现。乱序commit在一致性协议层面上是有收益的，而这点收益反应到上层业务中与其引入的复杂度相比，是得不偿失的。可以在业务上做乱序的优化。

Raft日志

Raft是Paxos的简化版，Raft最核心的约束是日志必须连续commit，不允许乱序commit。

Raft的日志是连续的，因此Raft的选主就很简单了：比一比谁的日志“最新”谁就是Leader。

Leader一旦产生后，其他Follower的日志向Leader看齐（Leader的日志“最新最全”）。

WAL日志

PostgreSQL数据库的WAL在物理上也是连续的，数据库系统中同时会有多个事务COMMIT都需要写WAL日志，为了加速写WAL的速度，引入了WALBuffer。WALBuffer在内存中是乱序写入的，而写WAL文件仍然是顺序写入（write和flush）。 WALBuffer的作用是允许多个事务并发的把自己的WAL日志组装好，拷贝到WALBuffer中（CopyXLogRecordToWAL），再由Walwriter进程或某个事务进程批量写WAL文件。

并发写WALBuffer

多个事务并发地在内存中拼接出事务的WAL日志，将WAL日志逻辑上看成从0到正无穷的开放区间，要点如下：

1. WALBuffer本质上是一个ringbuffer;

2. 逻辑区间的分配；并发的事务应该写哪一段区间，保证区间是连续不相交的；

3. 物理区间的分配：分配出来逻辑区间后，其对应的在WALBuffer中的物理Buffer内存区间是否立即可用，此时的物理Buffer可能还填充之前事务的日志没来及刷盘，需要本事务帮助其他事务完成这段物理区间的刷盘；

4. 在对WAL刷盘时：需要保证在此之前被分配出去的逻辑区间所对应的物理区间都填充好了WAL日志，以保证在刷WAL日志时日志文件没有空洞（可能由于之前事务执行比较慢，它在第1步中得到的逻辑区间还没来及使用，此时刷WAL就会导致WAL文件上有空洞）；

逻辑区间的分配

XLogInsertRecord --> ReserveXLogInsertLocation

WAL日志文件有很多个段文件，每个WAL日志文件头部有Header用于管理记录该文件的元信息，所有的段文件逻辑上拼接起来可以看成一个从0到无穷大的区间。 事务在写WAL日志时首先计算出自己要写的数据量，分配一段逻辑区间（计算的时候需要考虑Header）。由于多个事务会同时写WAL日志，因此对逻辑区间的分配需要上锁保护，ReserveXLogInsertLocation是写WAL的关键路径，此处仅仅是几个整数的加法运算，因此也会很快。

SpinLockAcquire(&Insert->insertpos_lck);

startbytepos = Insert->CurrBytePos;
endbytepos = startbytepos + size;
prevbytepos = Insert->PrevBytePos;
Insert->CurrBytePos = endbytepos;
Insert->PrevBytePos = startbytepos;

SpinLockRelease(&Insert->insertpos_lck);

Insert->insertpos_lck锁用于保护Insert->CurrBytePos变量的读和写，该变量是所有进程可见且始终精确维护该值的正确性。

插入锁槽（WALInsertLocks）

为什么需要插入位点锁槽

如下图所示，事务0、事务1、事务2都通过ReserveXLogInsertLocation得到了各自的逻辑区间。事务0、事务2执行的较快，这两个事务产生的WAL已经填充到WALBuffer中，而事务1执行的较慢，其WAL日志还没有来及填充。此时，事务2在COMMIT时需要将在这之前的WAL日志flush。为了确保WAL文件没有空洞，需要等待事务1把自己产生的WAL也拷贝到WALBuffer中，然后事务2再发起flush操作。后续事务0、事务1就不需要再次flush，可以直接COMMIT了。

可以看出，使用WALBuffer能把多个事务COMMIT时的flush动作归并到一起执行，有效减少flush次数。 问题是：当系统中有上万个事务在并发执行时，事务2在决定要flush时就需要遍历当前系统中所有并发执行的事务，看看哪些事务分配得到的逻辑区间在自己前面且还没来得及把自己的事务数据填充到公用的WALBuffer中，如果存在这样的事务，事务2就需要等待，直到被通知已经把WAL填充到了公用的WALBuffer中。然后，事务2需要继续遍历其他事务，直到再也找不到这种逻辑区间在自己前面且没有把事务数据填充到公共WALBuffer的事务。这个过程的时间复杂度是系统中的并发事务数，其执行时间是不可预测的。而且，大部分的遍历是无效的。

插入位点锁槽的算法

PostgreSQL设计的算法是：使用固定数目的插入位点槽位（默认是NUMXLOGINSERTLOCKS 8个），事务在自己的私有内存中准备好要写入的WAL日志后（XLogRegisterData）进入XLogInsertRecord，从这8个锁槽中得到一个锁槽位并上锁后再进行后续操作。 锁槽位结构如下，其中insertingAt代表在这个锁槽位观察到的最大的正在使用的位点。

typedef struct
{
	LWLock		lock;
	XLogRecPtr	insertingAt;
	XLogRecPtr	lastImportantAt;
} WALInsertLock;

也就是系统中最多有NUMXLOGINSERTLOCKS 8个事务并发的将自己私有内存区域的WAL填充到WALBuffer。当事务将私有内存空间WAL日志填充到WALBuffer后，就更新自己的锁槽位insertingAt变量。因此，在事务2要进行flush时，只需要遍历其他7个槽位中记录的insertingAt位点即可。如果其他7个槽位的insertingAt都大于自己的逻辑区间，或者压根就没有上过锁（说明没有其他事务在操作公共的WALBuffer），那么就说明在事务2之前的WALBuffer都被填充上了WAL日志，没有空洞可以进行flush了。

所以，在事务将私有内存空间WAL日志填充到WALBuffer过程中（XLogInsertRecord），WALInsertLock锁是最先被上的，它代表了系统中执行XLogInsertRecord的权利。

8个锁槽位够用吗，会不会槽位太少让多个并发事务出现等待锁槽位？ 完整的拿锁顺序是：

XLogInsertRecord --> WALInsertLocks --> insertpos_lck

先获取锁槽位再获取insertpos_lck分配逻辑空间，因此8个并发事务在填充WALBuffer的区间是连在一起的，填充WAL仅仅是内存操作，也有可能某个事务的产生的WAL日志量是在太多了，内存拷贝慢了，或者WALBuffer不够用了引发了IO操作。

增大NUMXLOGINSERTLOCKS确实能让更多的事务并发的填充WAL，但是在并发较低的时候一个事务在每次flush时都要遍历NUMXLOGINSERTLOCKS个锁槽位，遍历的代价变大了。因此，增大NUMXLOGINSERTLOCKS不一定有收益。另外，填充WAL的速率一般是远大于flush的速率，填充的更快了，flush的速率跟不上也没有作用。

并发将事务的WAL填充到WALBuffer（CopyXLogRecordToWAL）

FastPath

在WALBuffer中有足够的空闲内存时，填充WAL日志仅仅是内存操作其执行过程是非常快速的。 具体如下：在得到锁和分配到逻辑区间后，将分配得到的逻辑区间StartPos映射到WALBuffer的内存偏移（GetXLogBuffer(CurrPos)），开始遍历本事务私有内存空间的WAL日志逐条拷贝到公共的WALBuffer内存中。 需要注意的是：此时得到的WALBuffer内存区域可能是其他进程（WalWriter或其他事务进程）初始化的，因此需要执行一次memory_barrier以确保能读取到其他进程写入的最新内存数据。

	while (rdata != NULL)
	{
		char	   *rdata_data = rdata->data;
		int			rdata_len = rdata->len;

		while (rdata_len > freespace)
		{

			memcpy(currpos, rdata_data, freespace);
			rdata_data += freespace;
			rdata_len -= freespace;
			written += freespace;
			CurrPos += freespace;

			//从WALBuffer中获取可用的内存区域（涉及锁槽的等待、排空对应区间的内存等）
			currpos = GetXLogBuffer(CurrPos);
			pagehdr = (XLogPageHeader) currpos;
			pagehdr->xlp_rem_len = write_len - written;
			pagehdr->xlp_info |= XLP_FIRST_IS_CONTRECORD;

			{
				CurrPos += SizeOfXLogShortPHD;
				currpos += SizeOfXLogShortPHD;
			}
			freespace = INSERT_FREESPACE(CurrPos);
		}

		memcpy(currpos, rdata_data, rdata_len);
		currpos += rdata_len;
		CurrPos += rdata_len;
		freespace -= rdata_len;
		written += rdata_len;

		rdata = rdata->next;
	}

此时仅仅是将WAL拷贝到了共享内存WALBuffer中并没有显示执行flush操作，在事务提交时进行flush操作。

RecordTransactionCommit(void)
{
	if ((wrote_xlog && markXidCommitted &&
		 synchronous_commit > SYNCHRONOUS_COMMIT_OFF) ||
		forceSyncCommit || nrels > 0)
	{
		// 事务提交前显示的flush日志
		XLogFlush(XactLastRecEnd);

		if (markXidCommitted)
			TransactionIdCommitTree(xid, nchildren, children);
	}
}

SlowPath

逻辑区间、WALBuffer内存区间、物理区间的关系

如下图所示：

1. 逻辑WAL日志：事务进程在写WAL日志开始前需通过ReserveXLogInsertLocation分配得到一段逻辑区间；

2. WALBuffer物理内存区间：内存循环缓冲区，大小默认4MB，WAL日志先填充到WALBuffer的内存中，需要经过一次映射；

3. 物理WAL日志：WALBuffer内存中的数据会通过WalWriter或者事务进程flush到WAL文件中，WAL文件在物理上是有多个Segment；

事务0的逻辑区间对应的WALBuffer是页面P5、P6； 事务1的逻辑区间对应的WALBuffer是页面P0； 事务2的逻辑区间对应的WALBuffer是页面P1；

最终，这3个事务对应的Buffer页面都填充好后flush到日志文件，对应到某个物理WAL日志段文件中的X1、X2、X3、X4页面。 注意：

1. WALbuffer是8KB对齐，事务产生的WAL可能非8KB对齐；

2. flush是8KB对齐；

3. 物理WAL日志文件有多个；

WalWriter进程

定期将WALBuffer内存中的数据flush到WAL文件中，并往前推进WALBuffer的内存初始化。以促进业务进程在需要写WAL到WALBuffer循环缓冲区中，其对应位置中的WAL已经被flush下去了：

1. 如果在flush时确实发现有工作要做，200ms后再flush一次；

2. 否则，在重试lefttillhibernate后，5000ms后尝试flush一次；

for(;;)
{
		/*
		 * Do what we're here for; then, if XLogBackgroundFlush() found useful
		 * work to do, reset hibernation counter.
		 */
		if (XLogBackgroundFlush())
			left_till_hibernate = LOOPS_UNTIL_HIBERNATE;
		else if (left_till_hibernate > 0)
			left_till_hibernate--;

		if (left_till_hibernate > 0)
			cur_timeout = WalWriterDelay;	/* in ms */
		else
			cur_timeout = WalWriterDelay * HIBERNATE_FACTOR;

		(void) WaitLatch(MyLatch, cur_timeout, WAIT_EVENT_WAL_WRITER_MAIN);
}

从WALBuffer中获取可用的内存区域（GetXLogBuffer）

逻辑区间到WALBuffer内存页面的映射

通常，WalWriter进程会促使WALBuffer循环缓冲区中的内存都是可用的，其对应位置的WAL已经被flush下去，业务进程可以将新的WAL数据直接填充到这段内存。 当事务进程产生WAL的速度大于WalWriter的消费速度，业务进程就需要主动将WALBuffer中的数据flush下去以释放这段内存区间，否则，自己的WAL会覆盖到之前事务的WAL数据。

再次回到这张图中：

事务2的逻辑区间经过计算后对应WALBuffer中的页面P1：

#define XLogRecPtrToBufIdx(recptr)	\
	(((recptr) / XLOG_BLCKSZ) % (XLogCtl->XLogCacheBlck + 1))

此时页面P1中的WAL数据是否已经被flush到物理文件中，如果没有flush，暂时还不能把事务2的WAL数据填充到页面P1中。事务2要主动把在P1之前的WALBuffer都进行flush。 为了追踪每个WALBuffer页面中的WAL对应的逻辑区间，在共享内存区中增加一个数组XLogCtl->xlblocks[]，个数和WALBuffer中的页面数一样，记录每个WALBuffer页面当前存储WAL日志的逻辑位点。

1. 先通过事务2要写入的逻辑区间计算得到页面P1下标idx；

2. 如果，XLogCtl->xlblocks[idx]记录的逻辑位点和事务2的逻辑区间相等，则说明本次事务2和之前的某个事务要写入的是同一个页面P1，它已经被初始化过了，可以将自己的事务数据直接写入到页面P1；

3. 否则，说明当前WALBuffer页面P1存储的WAL是循环缓冲区上一圈中某个事务的WAL数据；

推进WALBuffer空闲内存区（AdvanceXLInsertBuffer）

核心数据结构

1. XLogCtl->LogwrtResult：系统中已经Write和Flush WAL日志的最大位点，该结构的读取和更新需要锁XLogCtl->info_lck的保护；

2. XLogCtl->LogwrtRqst：系统中需要写盘的最大位点，每次往WALBuffer填充WAL之后更新，给WalWriter进程使用；

3. LogwrtResult：进程私有内存中看到的已经Write和Flush WAL日志的最大位点，为了减少各个事务进程对全局XLogCtl->LogwrtResult的读取，落后于全局XLogCtl->LogwrtResult，在需要精确值的地方会上锁info_lck并读取全局XLogCtl->LogwrtResult结构，同时更新进程私有内存值；

4. XLogCtl->xlblocks[]：记录WALBuffer内存页面中WAL数据在WAL日志中的逻辑位点；

5. XLogCtl->InitializedUpTo：系统中即将需要初始化WALBuffer内存的位点，在这之前的内存设置了正确的XLogPageHeader可以直接使用；

和WALBuffer相关的锁：

1. WALBufMappingLock：保护XLogCtl->InitializedUpTo和XLogCtl->xlblocks[]数组；

2. XLogCtl->info_lck：保护XLogCtl->LogwrtResult等几个共享的位点信息；

3. WALWriteLock：保护WAL文件，同时最多只有一个进程能够写入WAL文件；

AdvanceXLInsertBuffer的核心流程

AdvanceXLInsertBuffer在WALBuffer中初始化内存直到位点超过了upto，包括两个动作：

1. 把upto之前的WALBuffer逐个页面写盘；

2. 把upto之前的WALBuffer内存初始化；

伪代码如下：

AdvanceXLInsertBuffer(upto)
{
	/* 最多有8个事务进程进入该函数， 上WALBufMappingLock锁，保护InitializedUpTo和XLogCtl->xlblocks[]的读写 */
	LWLockAcquire(WALBufMappingLock, LW_EXCLUSIVE);

	/* 上锁之后，再次检查是否有其他事务进程把自己要干的活给完成了 */
	while (upto >= XLogCtl->InitializedUpTo)
	{
		/* 系统中即初始化WALBuffer内存页面的位点 */
		nextidx = XLogRecPtrToBufIdx(XLogCtl->InitializedUpTo);

		/* 即将被初始化WALBuffer内存页面当前WAL数据所对应的逻辑区间 */
		OldPageRqstPtr = XLogCtl->xlblocks[nextidx];

		/*
		 * 已经写入WAL文件的位点比即将被初始化WALBuffer内存页面的位点小，则需要把OldPageRqstPtr之前的WALBuffer写到WAL文件中
		 * 这是一个乐观的估算
		 */
		if (LogwrtResult.Write < OldPageRqstPtr)
		{
			/* 上锁之后进行精确的比较，同时更新本地的私有变量LogwrtResult */
			SpinLockAcquire(&XLogCtl->info_lck);
			if (XLogCtl->LogwrtRqst.Write < OldPageRqstPtr)
				XLogCtl->LogwrtRqst.Write = OldPageRqstPtr;
			LogwrtResult = XLogCtl->LogwrtResult;
			SpinLockRelease(&XLogCtl->info_lck);

			/*
			 * 精确的比较：确实需要往前推进插入位点
			 */
			if (LogwrtResult.Write < OldPageRqstPtr)
			{
				/*
				 * 先释放WALBufMappingLock后再获取WALWriteLock，以避免死锁
				 * 此处可能产生死锁的原因是：当前事务进程通过WaitXLogInsertionsToFinish等待其他进程填充WALBuffer，而其他靠前的进程也可能进入到AdvanceXLInsertBuffer中，也会对WALBufMappingLock上锁。因此在进入WALWriteLock上锁之前，需要本进程释放先WALBufMappingLock锁，给其他进程推进insertingAt的机会；
				 * 在发现写入WAL文件的位点LogwrtResult.Write小于待初始化WALBuffer的位点OldPageRqstPtr时，
				 * 需要将区间[LogwrtResult.Write < OldPageRqstPtr, OldPageRqstPtr)进行写盘，以便释放出这段WALBuffer的内存区域被复用
				 * 此时，需要确保在OldPageRqstPtr位点之前的WALBuffer中的内存区域都是被填充了WAL数据的（前面介绍过，允许多个事务并发的填充WALBuffer内存区域）
				 * 这就是WaitXLogInsertionsToFinish函数的作用
				 */
				LWLockRelease(WALBufMappingLock);

				/* 遍历8个锁槽：等待WALBuffer内存中的插入位点追上OldPageRqstPtr */
				WaitXLogInsertionsToFinish(OldPageRqstPtr);

				/* 上锁WALWriteLock，只允许一个进程写WAL文件 */
				LWLockAcquire(WALWriteLock, LW_EXCLUSIVE);

				LogwrtResult = XLogCtl->LogwrtResult;
				/* 是否存在其他并发进车写WAL文件 */
				if (LogwrtResult.Write >= OldPageRqstPtr)
				{
					LWLockRelease(WALWriteLock);
				}
				else
				{
					WriteRqst.Write = OldPageRqstPtr;
					WriteRqst.Flush = 0;

					/* 上锁WALWriteLock后，写WAL文件 */
					XLogWrite(WriteRqst, false);
					LWLockRelease(WALWriteLock);
				}

				/* 同上，上WALBufMappingLock锁，再次从while地方开始重试 */
				LWLockAcquire(WALBufMappingLock, LW_EXCLUSIVE);
				continue;
			}
		}

		/* 下一个Buffer已经被写入WAL日志（不一定flush），该WALBuffer内存页面可以被复用了 */
		NewPageBeginPtr = XLogCtl->InitializedUpTo;
		NewPageEndPtr = NewPageBeginPtr + XLOG_BLCKSZ;

		/* 初始化下一个WALBuffer内存和文件头 */
		NewPage = (XLogPageHeader) (XLogCtl->pages + nextidx * (Size) XLOG_BLCKSZ);
		MemSet((char *) NewPage, 0, XLOG_BLCKSZ);
		NewPage->xlp_magic = XLOG_PAGE_MAGIC;
		NewPage->xlp_tli = ThisTimeLineID;
		NewPage->xlp_pageaddr = NewPageBeginPtr;

		/* 确保本进程对WALBuffer内存的操作，其他进程能读取到最新的内容 */
		pg_write_barrier();

		/* 设置xlblocks[nextidx]为最新值 */
		*((volatile XLogRecPtr *) &XLogCtl->xlblocks[nextidx]) = NewPageEndPtr;

		/* 在锁WALBufMappingLock的保护下，更新InitializedUpTo */
		XLogCtl->InitializedUpTo = NewPageEndPtr;

		npages++;
	}
	LWLockRelease(WALBufMappingLock);
}

可以看出，在该代码路径中，一次写一个Buffer页面并不是批量写，因为此时处于填充WAL的关键路径上，一般释放出一个Buffer页面就够用了，WalWriter在flush的时候会批量写。

XLogCtl->xlblocks[]数组的作用

WALBuffer是多个进程并发操作的循环缓冲区，需要解决两个问题：

1. 在复用一段WALBuffer内存区间时如何判断出这段内存区间是可以被复用的；

2. 当一个事务进程生产WAL日志的速率很快，WalWriter进程的消费较慢时，绕了一圈后，如何不覆盖上一圈的内存；

这两个工作通过XLogCtl->xlblocks来完成，如下图所示：

1. XLogCtl->xlblocks[]是一个数组大小和WALBuffer的页面数相等；

2. 每个XLogCtl->xlblocks数组中的数值记录了其相同下标XLogCtl->pages[]当前装载的数据在WAL文件中对应的逻辑位点；

上面2个问题可以规约为一个问题：对于下标为idx的页面，当前LogwrtResult.Write的位点是否大于XLogCtl->xlblocks[idx]

1. 如果大于，则说明XLogCtl->xlblocks[idx]指向的内存Buffer已经被WalWriter写入，可以被复用；

2. 否则，则说明XLogCtl->xlblocks[idx]指向的内存Buffer暂时还没有被写入到WAL文件，生产WAL的事务进程绕过了一圈又追了上来；

另外，WalWriter进程在批量写WAL文件时，需要分两次批量写入：

1. 第一次批量写P5P6；

2. 第二次批量写P0P1；

总结

PG的WAL日志是追加写的形式，因此只能有一个进程写文件； 为了加速写WAL文件，需要批量写，因此需要在内存中维护一个允许多个事务进程并发写的WALBuffer，在恰当的时机将WALBuffer的内存区域批量写入WAL文件； 在批量写WAL文件时，需要保证WALBuffer区域中是没有空洞的，因此引入了8个锁槽位来追踪系统中并发写WALBuffer的位点，XLogCtl->xlblocks数组追踪当前WALBuffer内存的位点来判断WALBuffer循环缓冲区是否可以被立即复用或写盘； 当前写WAL日志的算法性能依赖文件系统的PageCache），仅将WALBuffer内存pwrite到文件的PageCache，以快速的释放WALBuffer内存页。PolarDB-PG使用了DirectIO，在关键路径上写WAL文件时会发生IO，而原生仅需要内存拷贝到PageCache就可以了（小概率会触发IO，取决于PageCache和系统的IO负载）。PolarDB-PG内核研发同学正在将进行相关的优化，欢迎有兴趣的同学私信。

Raft的日志是连续的，因此Raft的选主就很简单了：比一比谁的日志“最新”谁就是Leader。

XLogInsertRecord --> ReserveXLogInsertLocation

SpinLockAcquire(&Insert->insertpos_lck);

startbytepos = Insert->CurrBytePos;
endbytepos = startbytepos + size;
prevbytepos = Insert->PrevBytePos;
Insert->CurrBytePos = endbytepos;
Insert->PrevBytePos = startbytepos;

SpinLockRelease(&Insert->insertpos_lck);

typedef struct
{
	LWLock		lock;
	XLogRecPtr	insertingAt;
	XLogRecPtr	lastImportantAt;
} WALInsertLock;

XLogInsertRecord --> WALInsertLocks --> insertpos_lck

	while (rdata != NULL)
	{
		char	   *rdata_data = rdata->data;
		int			rdata_len = rdata->len;

		while (rdata_len > freespace)
		{

			memcpy(currpos, rdata_data, freespace);
			rdata_data += freespace;
			rdata_len -= freespace;
			written += freespace;
			CurrPos += freespace;

			//从WALBuffer中获取可用的内存区域（涉及锁槽的等待、排空对应区间的内存等）
			currpos = GetXLogBuffer(CurrPos);
			pagehdr = (XLogPageHeader) currpos;
			pagehdr->xlp_rem_len = write_len - written;
			pagehdr->xlp_info |= XLP_FIRST_IS_CONTRECORD;

			{
				CurrPos += SizeOfXLogShortPHD;
				currpos += SizeOfXLogShortPHD;
			}
			freespace = INSERT_FREESPACE(CurrPos);
		}

		memcpy(currpos, rdata_data, rdata_len);
		currpos += rdata_len;
		CurrPos += rdata_len;
		freespace -= rdata_len;
		written += rdata_len;

		rdata = rdata->next;
	}

RecordTransactionCommit(void)
{
	if ((wrote_xlog && markXidCommitted &&
		 synchronous_commit > SYNCHRONOUS_COMMIT_OFF) ||
		forceSyncCommit || nrels > 0)
	{
		// 事务提交前显示的flush日志
		XLogFlush(XactLastRecEnd);

		if (markXidCommitted)
			TransactionIdCommitTree(xid, nchildren, children);
	}
}

for(;;)
{
		/*
		 * Do what we're here for; then, if XLogBackgroundFlush() found useful
		 * work to do, reset hibernation counter.
		 */
		if (XLogBackgroundFlush())
			left_till_hibernate = LOOPS_UNTIL_HIBERNATE;
		else if (left_till_hibernate > 0)
			left_till_hibernate--;

		if (left_till_hibernate > 0)
			cur_timeout = WalWriterDelay;	/* in ms */
		else
			cur_timeout = WalWriterDelay * HIBERNATE_FACTOR;

		(void) WaitLatch(MyLatch, cur_timeout, WAIT_EVENT_WAL_WRITER_MAIN);
}

#define XLogRecPtrToBufIdx(recptr)	\
	(((recptr) / XLOG_BLCKSZ) % (XLogCtl->XLogCacheBlck + 1))

AdvanceXLInsertBuffer(upto)
{
	/* 最多有8个事务进程进入该函数， 上WALBufMappingLock锁，保护InitializedUpTo和XLogCtl->xlblocks[]的读写 */
	LWLockAcquire(WALBufMappingLock, LW_EXCLUSIVE);

	/* 上锁之后，再次检查是否有其他事务进程把自己要干的活给完成了 */
	while (upto >= XLogCtl->InitializedUpTo)
	{
		/* 系统中即初始化WALBuffer内存页面的位点 */
		nextidx = XLogRecPtrToBufIdx(XLogCtl->InitializedUpTo);

		/* 即将被初始化WALBuffer内存页面当前WAL数据所对应的逻辑区间 */
		OldPageRqstPtr = XLogCtl->xlblocks[nextidx];

		/*
		 * 已经写入WAL文件的位点比即将被初始化WALBuffer内存页面的位点小，则需要把OldPageRqstPtr之前的WALBuffer写到WAL文件中
		 * 这是一个乐观的估算
		 */
		if (LogwrtResult.Write < OldPageRqstPtr)
		{
			/* 上锁之后进行精确的比较，同时更新本地的私有变量LogwrtResult */
			SpinLockAcquire(&XLogCtl->info_lck);
			if (XLogCtl->LogwrtRqst.Write < OldPageRqstPtr)
				XLogCtl->LogwrtRqst.Write = OldPageRqstPtr;
			LogwrtResult = XLogCtl->LogwrtResult;
			SpinLockRelease(&XLogCtl->info_lck);

			/*
			 * 精确的比较：确实需要往前推进插入位点
			 */
			if (LogwrtResult.Write < OldPageRqstPtr)
			{
				/*
				 * 先释放WALBufMappingLock后再获取WALWriteLock，以避免死锁
				 * 此处可能产生死锁的原因是：当前事务进程通过WaitXLogInsertionsToFinish等待其他进程填充WALBuffer，而其他靠前的进程也可能进入到AdvanceXLInsertBuffer中，也会对WALBufMappingLock上锁。因此在进入WALWriteLock上锁之前，需要本进程释放先WALBufMappingLock锁，给其他进程推进insertingAt的机会；
				 * 在发现写入WAL文件的位点LogwrtResult.Write小于待初始化WALBuffer的位点OldPageRqstPtr时，
				 * 需要将区间[LogwrtResult.Write < OldPageRqstPtr, OldPageRqstPtr)进行写盘，以便释放出这段WALBuffer的内存区域被复用
				 * 此时，需要确保在OldPageRqstPtr位点之前的WALBuffer中的内存区域都是被填充了WAL数据的（前面介绍过，允许多个事务并发的填充WALBuffer内存区域）
				 * 这就是WaitXLogInsertionsToFinish函数的作用
				 */
				LWLockRelease(WALBufMappingLock);

				/* 遍历8个锁槽：等待WALBuffer内存中的插入位点追上OldPageRqstPtr */
				WaitXLogInsertionsToFinish(OldPageRqstPtr);

				/* 上锁WALWriteLock，只允许一个进程写WAL文件 */
				LWLockAcquire(WALWriteLock, LW_EXCLUSIVE);

				LogwrtResult = XLogCtl->LogwrtResult;
				/* 是否存在其他并发进车写WAL文件 */
				if (LogwrtResult.Write >= OldPageRqstPtr)
				{
					LWLockRelease(WALWriteLock);
				}
				else
				{
					WriteRqst.Write = OldPageRqstPtr;
					WriteRqst.Flush = 0;

					/* 上锁WALWriteLock后，写WAL文件 */
					XLogWrite(WriteRqst, false);
					LWLockRelease(WALWriteLock);
				}

				/* 同上，上WALBufMappingLock锁，再次从while地方开始重试 */
				LWLockAcquire(WALBufMappingLock, LW_EXCLUSIVE);
				continue;
			}
		}

		/* 下一个Buffer已经被写入WAL日志（不一定flush），该WALBuffer内存页面可以被复用了 */
		NewPageBeginPtr = XLogCtl->InitializedUpTo;
		NewPageEndPtr = NewPageBeginPtr + XLOG_BLCKSZ;

		/* 初始化下一个WALBuffer内存和文件头 */
		NewPage = (XLogPageHeader) (XLogCtl->pages + nextidx * (Size) XLOG_BLCKSZ);
		MemSet((char *) NewPage, 0, XLOG_BLCKSZ);
		NewPage->xlp_magic = XLOG_PAGE_MAGIC;
		NewPage->xlp_tli = ThisTimeLineID;
		NewPage->xlp_pageaddr = NewPageBeginPtr;

		/* 确保本进程对WALBuffer内存的操作，其他进程能读取到最新的内容 */
		pg_write_barrier();

		/* 设置xlblocks[nextidx]为最新值 */
		*((volatile XLogRecPtr *) &XLogCtl->xlblocks[nextidx]) = NewPageEndPtr;

		/* 在锁WALBufMappingLock的保护下，更新InitializedUpTo */
		XLogCtl->InitializedUpTo = NewPageEndPtr;

		npages++;
	}
	LWLockRelease(WALBufMappingLock);
}