什么是LSN？

首先我们要理解一些PostgreSQL数据库软件设计上的基本背景知识：

当用户在数据库中修改数据时，修改首先发生在共享内存中的共享池(shared buffer)中。共享池就是一个数组，数组的每个成员叫做数据页(data page)，数据页的尺寸和磁盘上数据文件(data file)中的数据块(data block)的尺寸是一样的。缺省情况下，共享池中的数据页和磁盘上的数据块都是8192字节。数据页被修改后，该数据页并不会立刻写入到磁盘上对应的数据块上，因为这种设计导致数据库的性能非常差，所有的数据库软件(Oracle, PostgreSQL, MySQL和SQL Server)都会采用另外一个机制，就是提前写日志(WAL: Writer Ahead Log)，或者叫“重做”(REDO)，即：能够重现本次修改的信息被组织成一种特殊的格式，以这种格式来描述本次修改操作的信息叫做WAL记录(WAL record)，WAL记录就是连续的n个字节。WAL记录在数据页被修改后，立刻产生，并被写入到一个叫做WAL文件的磁盘文件上。对WAL文件的写入只有一种操作：即在该文件的尾部进行追加(Append)，这是一种顺序写。顺序写的速度要快于在各数据块上进行的随机写。下面这句英文对这个规律解释得很明确：

As the DB is operating, blocks of data are first written serially and synchronously as WAL files, then some time later, usually a very short time later, written to the DB data files. 

理论上，这个WAL文件有且只有一个，被存放在数据库集群的目录$PGDATA/pg_wal中。这个文件的每个字节的地址，即该字节在这个文件中的位置，都用一个8字节来记录，如下图所示：

如果我们对这个WAL文件上的每个字节进行编号，就是它们的位置，这个编号就是该字节的LSN。上图中，第一个字节的编号为0，所以它的LSN是0，第二个字节的编号是1，所以它的LSN是1。LSN是8个字节，所以第二个字节的LSN是0x0000000000000001，即15个0加上最后一位的1。前缀0x表示这是一个16进制的数，这个前缀是C语言表示16进制数的语法。

这个WAL文件最后一个字节的编号是0xFFFFFFFFFFFFFFFF，就是16个F。倒数第二个字节的编号是0xFFFFFFFFFFFFFFFE，就是15个连续的F加上一个E；倒数第三个字节的编号是0xFFFFFFFFFFFFFFFD，就是15个连续的F加上一个D。这三个巨大的数字就分别是这三个字节的LSN。因为LSN是8个字节，用16进制表示，就是16个数字，太长了，不好阅读，所以PG在高四字节和低四字节中加入一个分隔符，就是除号“/”。所以倒数第三个字节的LSN就是:

FFFFFFFF/FFFFFFFD

这个分隔符仅仅是为了我们阅读方便，并没有什么深层次的含义。

在上图中，有一个“当前写指针”(Current Position)，它指向了下一个还没有被填充的字节的位置。在这个指针的左边，就是已经写入的WAL记录；在这个指针的右边，是没有写入的空白空间。这个指针唯一的可能性是从左往右移动，因为往这个文件中写入的数据都是在文件的尾部进行追加的，所以这个指针代表这个文件的尾部。

所以我们可以得出结论：

所谓LSN，就是在一个巨大WAL文件中每个字节的编号，最小的LSN是00000000/00000000，最大的LSN是FFFFFFFF/FFFFFFFF。一个PG数据库集群(database cluster)中一共有2^64个LSN(其中2^64表示2的64次方)。

LSN唯一合法的操作是相减操作。因为LSN是表示WAL文件中某一个字节的编号，LSN2 - LSN1表示两个字节之间的距离，单位是字节。譬如，LSN1 = 00000001/12345678，LSN2 = 00000001/1234567A，则LSN2 - LSN1 = 2，则表示这两个字节之间的距离是2个字节。

分割巨大的WAL文件

这个WAL文件最多可以由2^64个字节组成，就是16EB，这实在太巨大了。1EB是1024PB，1PB是1024TB，你可以想象这个文件是多么的巨大。这个巨大的文件是根本无法在任何一台计算机上进行存储的。我们的解决方法就是把这个理论上的WAL文件进行等体积分割成更小的，易于管理的“小”文件。

下图展示了如何对这个巨大的单一WAL文件进行分割，我们按照4GB作为分割单位，进行了分割。

大家可以看到，我们一共得到了2^32个文件，每个文件的大小都是2^32个字节。这是很容易理解的。我们对这些文件进行编号，从0开始，最后一个文件的编号是0xFFFFFFFF。

现在我们考察2号文件，它的第一个字节的LSN是00000002/00000000，最后一个字节的LSN是00000002/FFFFFFFF。类似的，10号文件的第一个字节的LSN是0000000A/00000000，最后一个字节的LSN是0000000A/FFFFFFFF。我们很容易发现一个规律，就是：

如果一个字节的LSN是x/y，则它必定保存在编号是x的文件中，这个文件的体积是4GB。

这个体积为4GB的文件，被我们称为“逻辑”(logical)WAL文件，它的编号就被称为“逻辑编号”。所以一个LSN代表的字节，必定保存在由它的高四字节所表示的逻辑文件中。

对WAL文件的二次分割

因为4GB文件过大，所以我们要对它进行二次分割，PG规定分割的体积是1MB,2MB, 4MB, 8MB, 16MB,32MB,64MB,128MB,256MB,512MB,1024MB这11个尺寸中的一个，缺省是16MB。这种二次分割后的更小体积的WAL文件被称为“段”(segment)WAL文件。我们通常说的“WAL文件”指的就是段文件。

假设被分割的更小的WAL文件的体积是16MB，则一个4GB的文件可以被分割为256个，因为2^32 / 2^24 = 2^8 = 256。我们来看一下相关源代码：

#define XLogSegmentsPerXLogId(wal_segsz_bytes)	\
	(UINT64CONST(0x100000000) / (wal_segsz_bytes)) 

宏定义XLogSegmentPerXLogId清楚地描述了如何计算段文件的个数。0x100000000就是4GB，它除于段文件的体积，就是段文件的个数，譬如WAL文件体积是1GB时，可以分割为4个；512MB时，可以被分割为8个，256MB时可以被分割为16个，依次类推。

进行二次分割后，就有两级编号，上图中逻辑文件的编号是从0到0xFFFFFFFF，但是段文件的编号就是从0到255，所以每个段文件的编号可以表示为0.0，0.1，......，0.255，1.0，1.1，......，1.255等等。

这个二级编号也可以变成一维编号，譬如0.0就是0，0.255就是255，1.0就是256，1.1就是257，1.255就是511等等。

在段文件体积是16MB的情况下，一个PG数据库集群有2^32 * 2^8 = 2^40个段文件，它们的编号从0到0xFFFFFFFFFF，你不要数了，一共10个连续的F。这个编号就是一维的编号。

在段文件体积是1MB的情况下，一个PG数据块集群有2^32 * 2^12 = 2^44个段文件，它们的编号从0到0xFFFFFFFFFFF，一共11个连续的F。

大家在阅读源代码时，可以看到一个数据类型XLogSegNo，它就是一维的编号。它被设计为64位，因为最多可能有2^44个编号，必须用44比特来表示，32位是表示不下的，只能用64位来表示。

/*
 * XLogSegNo - physical log file sequence number.
 */
typedef uint64 XLogSegNo;

理解了上述概念，很多源代码就能看懂了，你试试理解下面的代码：

static inline void /// 根据WAL文件的文件名，计算出一维的WAL文件的编号。
XLogFromFileName(const char *fname, TimeLineID *tli, XLogSegNo *logSegNo, int wal_segsz_bytes)
{
	uint32		log;
	uint32		seg;

	sscanf(fname, "%08X%08X%08X", tli, &log, &seg);
	*logSegNo = (uint64) log * XLogSegmentsPerXLogId(wal_segsz_bytes) + seg;
}

上述代码就是根据一个WAL文件的文件名，来计算出它的一维编号是多少。

希望上述帖子能够让你彻底理解这几个重要的概念。