PolarDB PostgreSQL版（以下简称 PolarDB-PG）是一款阿里云自主研发的企业级数据库产品，采用计算存储分离架构，兼容 PostgreSQL 与 Oracle。PolarDB-PG 的存储与计算能力均可横向扩展，具有高可靠、高可用、弹性扩展等企业级数据库特性。同时，PolarDB-PG 具有大规模并行计算能力，可以应对 OLTP 与 OLAP 混合负载；还具有时空、向量、搜索、图谱等多模创新特性，可以满足企业对数据处理日新月异的新需求。
原理剖析
Sequence 在系统表与数据表中的描述
在 PostgreSQL 中有一张专门记录 Sequence 信息的系统表，即 pg_sequence。其表结构如下：
postgres=# \d pg_sequence
Table "pg_catalog.pg_sequence"
Column | Type | Collation | Nullable | Default
--------------+---------+-----------+----------+---------
seqrelid | oid | | not null |
seqtypid | oid | | not null |
seqstart | bigint | | not null |
seqincrement | bigint | | not null |
seqmax | bigint | | not null |
seqmin | bigint | | not null |
seqcache | bigint | | not null |
seqcycle | boolean | | not null |
Indexes:
"pg_sequence_seqrelid_index" PRIMARY KEY, btree (seqrelid)
复制不难看出，pg_sequence 中记录了 Sequence 的全部的属性信息，该属性在 CREATE/ALTER SEQUENCE 中被设置，Sequence 的 nextval 以及 setval 要经常打开这张系统表，按照规则办事。
对于 Sequence 序列数据本身，其实现方式是基于 heap 表实现的，heap 表共计三个字段，其在表结构如下：
typedef struct FormData_pg_sequence_data
{
int64 last_value;
int64 log_cnt;
bool is_called;
} FormData_pg_sequence_data;
复制last_value记录了 Sequence 的当前的序列值，我们称之为页面值（与后续的缓存值相区分）log_cnt记录了 Sequence 在nextval申请时，预先向 WAL 中额外申请的序列次数，这一部分我们放在序列申请机制剖析中详细介绍。is_called标记 Sequence 的last_value是否已经被申请过，例如setval可以设置is_called字段：
-- setval false
postgres=# select setval('seq', 10, false);
setval
--------
10
(1 row)
postgres=# select * from seq;
last_value | log_cnt | is_called
------------+---------+-----------
10 | 0 | f
(1 row)
postgres=# select nextval('seq');
nextval
---------
10
(1 row)
-- setval true
postgres=# select setval('seq', 10, true);
setval
--------
10
(1 row)
postgres=# select * from seq;
last_value | log_cnt | is_called
------------+---------+-----------
10 | 0 | t
(1 row)
postgres=# select nextval('seq');
nextval
---------
11
(1 row)
复制每当用户创建一个 Sequence 对象时，PostgreSQL 总是会创建出一张上面这种结构的 heap 表，来记录 Sequence 对象的数据信息。当 Sequence 对象因为 nextval 或 setval 导致序列值变化时，PostgreSQL 就会通过原地更新的方式更新 heap 表中的这一行的三个字段。
以 setval 为例，下面的逻辑解释了其具体的原地更新过程。
static void
do_setval(Oid relid, int64 next, bool iscalled)
{
/* 打开并对Sequence heap表进行加锁 */
init_sequence(relid, &elm, &seqrel);
...
/* 对buffer进行加锁，同时提取tuple */
seq = read_seq_tuple(seqrel, &buf, &seqdatatuple);
...
/* 原地更新tuple */
seq->last_value = next; /* last fetched number */
seq->is_called = iscalled;
seq->log_cnt = 0;
...
/* 释放buffer锁以及表锁 */
UnlockReleaseBuffer(buf);
relation_close(seqrel, NoLock);
}
复制可见，do_setval 会直接去设置 Sequence heap 表中的这一行元组，而非普通 heap 表中的删除 + 插入的方式来完成元组更新，对于 nextval 而言，也是类似的过程，只不过 last_value 的值需要计算得出，而非用户设置。
序列申请机制剖析
讲清楚 Sequence 对象在内核中的存在形式之后，就需要讲清楚一个序列值是如何发出的，即 nextval 方法。其在内核的具体实现在 sequence.c 中的 nextval_internal 函数，其最核心的功能，就是计算 last_value 以及 log_cnt。
last_value 和 log_cnt 的具体关系如下图：
其中 log_cnt 是一个预留的申请次数。默认值为 32，由下面的宏定义决定：
/*
* We don't want to log each fetching of a value from a sequence,
* so we pre-log a few fetches in advance. In the event of
* crash we can lose (skip over) as many values as we pre-logged.
*/
#define SEQ_LOG_VALS 32
复制每当将 last_value 增加一个 increment 的长度时，log_cnt 就会递减 1。
当 log_cnt 为 0，或者发生 checkpoint 以后，就会触发一次 WAL 日志写入，按下面的公式设置 WAL 日志中的页面值，并重新将 log_cnt 设置为 SEQ_LOG_VALS。
通过这种方式，PostgreSQL 每次通过 nextval 修改页面中的 last_value 后，不需要每次都写入 WAL 日志。这意味着：如果 nextval 每次都需要修改页面值的话，这种优化将会使得写 WAL 的频率降低 32 倍。其代价就是，在发生 crash 前如果没有及时进行 checkpoint，那么会丢失一段序列。如下面所示：
postgres=# create sequence seq;
CREATE SEQUENCE
postgres=# select nextval('seq');
nextval
---------
1
(1 row)
postgres=# select * from seq;
last_value | log_cnt | is_called
------------+---------+-----------
1 | 32 | t
(1 row)
-- crash and restart
postgres=# select * from seq;
last_value | log_cnt | is_called
------------+---------+-----------
33 | 0 | t
(1 row)
postgres=# select nextval('seq');
nextval
---------
34
(1 row)
复制显然，crash 以后，Sequence 对象产生了 2-33 这段空洞，但这个代价是可以被接受的，因为 Sequence 并没有违背唯一性原则。同时，在特定场景下极大地降低了写 WAL 的频率。
Sequence 缓存机制
通过上述描述，不难发现 Sequence 每次发生序列申请，都需要通过加入 buffer 锁的方式来修改页面，这意味着 Sequence 的并发性能是比较差的。
针对这个问题，PostgreSQL 使用对 Sequence 使用了 Session Cache 来提前缓存一段序列，来提高并发性能。如下图所示：
Sequence Session Cache 的实现是一个 entry 数量固定为 16 的哈希表，以 Sequence 的 OID 为 key 去检索已经缓存好的 Sequence 序列，其缓存的 value 结构如下：
typedef struct SeqTableData
{
Oid relid; /* Sequence OID(hash key) */
int64 last; /* value last returned by nextval */
int64 cached; /* last value already cached for nextval */
int64 increment; /* copy of sequence's increment field */
} SeqTableData;
复制其中 last 即为 Sequence 在 Session 中的当前值，即 current_value，cached 为 Sequence 在 Session 中的缓存值，即 cached_value，increment 记录了步长，有了这三个值即可满足 Sequence 缓存的基本条件。
对于 Sequence Session Cache 与页面值之间的关系，如下图所示：
类似于 log_cnt，cache_cnt 即为用户在定义 Sequence 时，设置的 Cache 大小，最小为 1。只有当 cache domain 中的序列用完以后，才会去对 buffer 加锁，修改页中的 Sequence 页面值。调整过程如下所示：
例如，如果 CACHE 设置的值为 20，那么当 cache 使用完以后，就会尝试对 buffer 加锁来调整页面值，并重新申请 20 个 increment 至 cache 中。对于上图而言，有如下关系：
在 Sequence Session Cache 的加持下，nextval 方法的并发性能得到了极大的提升，以下是通过 pgbench 进行压测的结果对比。
总结
Sequence 在 PostgreSQL 中是一类特殊的表级对象，提供了简单而又丰富的 SQL 接口，使得用户可以更加方便的创建、使用定制化的序列对象。不仅如此，Sequence 在内核中也具有丰富的组合使用场景，其使用场景也得到了极大地扩展。
本文详细介绍了 Sequence 对象在 PostgreSQL 内核中的具体设计，从对象的元数据描述、对象的数据描述出发，介绍了 Sequence 对象的组成。本文随后介绍了 Sequence 最为核心的 SQL 接口——nextval，从 nextval 的序列值计算、原地更新、降低 WAL 日志写入三个方面进行了详细阐述。最后，本文介绍了 Sequence Session Cache 的相关原理，描述了引入 Cache 以后，序列值在 Cache 中，以及页面中的计算方法以及对齐关系，并对比了引入 Cache 前后，nextval 方法在单序列和多序列并发场景下的对比情况。
