AliSQL开源Sequence Engine

Introduction

单调递增的唯一值，是在持久化数据库系统中常见的需求，无论是单节点中的业务主键，还是分布式系统中的全局唯一值，亦或是多系统中的幂等控制。不同的数据库系统有不同的实现方法，比如MySQL提供的AUTO_INCREMENT，Oracle，SQL Server提供SEQUENCE等。

在MySQL数据库中，如果业务系统希望封装唯一值，比如增加日期，用户等信息，AUTO_INCREMENT的方法会带来很大的不便，在实际的系统设计的时候, 也存在不同的折中方法，比如：

• 序列值由Application或者Proxy来生成，不过弊端很明显，状态带到应用端，增加了扩容和缩容的复杂度。
• 序列值由数据库通过模拟的表来生成，但需要中间件来封装和简化获取唯一值的逻辑。

AliSQL自主实现了SEQUENCE ENGINE，通过引擎的设计方法，尽可能的兼容其他数据库的使用方法，简化获取序列值复杂度。

Github开源地址：https://github.com/alibaba/AliSQL

Description

AliSQL开源的SEQUENCE，实现了MySQL存储引擎的设计接口，但底层的数据仍然使用现有的存储引擎，比如InnoDB或者MyISAM来保存持久化数据，以便尽可能的保证现有的外围工具比如XtraBackup等工具的兼容，所以SEQUENCE ENGINE仅仅是一个逻辑引擎。

对sequence对象的访问通过SEQUENCE handler接口，这一层逻辑引擎主要实现NEXTVAL的滚动，CACHE的管理等，最后透传给底层的基表数据引擎，实现最终的数据访问。

下面我们透过语法来看下AliSQL SEQUENCE的使用。

Syntax

1. CREATE SEQUENCE Syntax:

CREATE SEQUENCE [IF NOT EXISTS] schema.sequence_name
   [START WITH <constant>]
   [MINVALUE <constant>]
   [MAXVALUE <constant>]
   [INCREMENT BY <constant>]
   [CACHE <constant> | NOCACHE]
   [CYCLE | NOCYCLE]
  ;

SEQUENCE OPTIONS:

• START
  Sequence的起始值
• MINVALUE
  Sequence的最小值，如果这一轮结束并且是cycle的，那么下一轮将从MINVALUE开始
• MAXVALUE
  Sequence的最大值，如果到最大值并且是nocycle的，那么将会得到以下报错：

ERROR HY000: Sequence 'db.seq' has been run out.

• INCREMENT BY
  Sequence的步长
• CACHE/NOCACHE
  Cache的大小，为了性能考虑，可以设置cache的size比较大，但如果遇到实例重启，cache内的值会丢失
• CYCLE/NOCYCLE
  表示sequence如果用完了后，是否允许从MINVALUE重新开始

例如：

  create sequence s
       start with 1
       minvalue 1
       maxvalue 9999999
       increment by 1
       cache 20
       cycle;

2. SHOW SEQUENCE Syntax

SHOW CREATE [TABLE|SEQUENCE] schema.sequence_name;

CREATE SEQUENCE schema.sequence_name (
  `currval` bigint(21) NOT NULL COMMENT 'current value',
  `nextval` bigint(21) NOT NULL COMMENT 'next value',
  `minvalue` bigint(21) NOT NULL COMMENT 'min value',
  `maxvalue` bigint(21) NOT NULL COMMENT 'max value',
  `start` bigint(21) NOT NULL COMMENT 'start value',
  `increment` bigint(21) NOT NULL COMMENT 'increment value',
  `cache` bigint(21) NOT NULL COMMENT 'cache size',
  `cycle` bigint(21) NOT NULL COMMENT 'cycle state',
  `round` bigint(21) NOT NULL COMMENT 'already how many round'
) ENGINE=InnoDB DEFAULT CHARSET=latin1

由于SEQUENCE是通过真正的引擎表来保存的，所以SHOW COMMAND看到仍然是engine table。

3. QUERY STATEMENT Syntax

SELECT [NEXTVAL | CURRVAL | *] FROM schema.sequence_name;
SELECT [NEXTVAL | CURRVAL | *] FOR schema.sequence_name;

这里支持两种访问方式，FROM和FOR：

• FROM clause: 兼容正常的SELECT查询语句，返回的结果是基表的数据，不迭代NEXTVAL。
• FOR clause：兼容SQL Server的方法，返回的结果是迭代后NEXTVAL的值。

mysql> select * from s;
+---------+---------+----------+---------------------+-------+-----------+-------+-------+-------+
| currval | nextval | minvalue | maxvalue            | start | increment | cache | cycle | round |
+---------+---------+----------+---------------------+-------+-----------+-------+-------+-------+
|       0 |   30004 |        1 | 9223372036854775807 |     1 |         1 | 10000 |     0 |     0 |
+---------+---------+----------+---------------------+-------+-----------+-------+-------+-------+
1 row in set (0.00 sec)

mysql> select * for s;
+---------+---------+----------+---------------------+-------+-----------+-------+-------+-------+
| currval | nextval | minvalue | maxvalue            | start | increment | cache | cycle | round |
+---------+---------+----------+---------------------+-------+-----------+-------+-------+-------+
|       0 |   20014 |        1 | 9223372036854775807 |     1 |         1 | 10000 |     0 |     0 |
+---------+---------+----------+---------------------+-------+-----------+-------+-------+-------+

4. 兼容性

因为要兼容MYSQLDUMP的备份方式，所以支持另外一种CREATE SEQUENCE方法，即：通过创建SEQUENCE表和INSERT一行初始记录的方式, 比如：

  CREATE SEQUENCE schema.sequence_name (
  `currval` bigint(21) NOT NULL COMMENT 'current value',
  `nextval` bigint(21) NOT NULL COMMENT 'next value',
  `minvalue` bigint(21) NOT NULL COMMENT 'min value',
  `maxvalue` bigint(21) NOT NULL COMMENT 'max value',
  `start` bigint(21) NOT NULL COMMENT 'start value',
  `increment` bigint(21) NOT NULL COMMENT 'increment value',
  `cache` bigint(21) NOT NULL COMMENT 'cache size',
  `cycle` bigint(21) NOT NULL COMMENT 'cycle state',
  `round` bigint(21) NOT NULL COMMENT 'already how many round'
) ENGINE=InnoDB DEFAULT CHARSET=latin1

INSERT INTO schema.sequence_name VALUES(0,0,1,9223372036854775807,1,1,10000,1,0);
COMMIT;

但强烈建议使用native的CREATE SEQUENCE方法。

5. 语法限制

• Sequence不支持subquery和join
• FOR clause只支持sequence表，普通引擎表不支持
• 可以使用SHOW CREATE TABLE或者SHOW CREATE SEQUENCE来访问SEQUENCE结构，但不能使用SHOW CREATE SEQUENCE访问普通表
• 不支持CREATE TABLE的时候指定SEQUENCE引擎，sequence表只能通过CREATE SEQUENCE的语法来创建

High level architecture

1. Sequence initialization

Sequence对象的创建，会转化成拥有固定[CURRVAL, NEXTVAL, MINVALUE, MAXVALUE, START, INCREMENT, CACHE, CYCLE, ROUND]这9个字段的引擎表，并根据CREATE SEQUENCE clause的定义，初始化了一条数据，所以sequence对象实质上是拥有一条记录的存储引擎表，SLAVE复制的BINLOG使用CREATE SEQUENCE ...语句生成的QUERY EVENT来完成。

2. Sequence interface

SEQUENCE handler实现了一部分的handler interface，并定义了两个重要的属性，SEQUENCE_SHARE和BASE_TABLE_FILE，SEQUENCE_SHARE保存着共享的sequence对象属性和CACHE的值，NEXTVAL的值首先从cache中获取，只有在cache使用完了，才会查询基表。
BASE_TABLE_FILE是基表的handler，对持久化的数据的访问和修改，都通过BASE_TABLE_FILE handler进行访问。

3. Sequence cache

Sequence对象的CACHE值保存在SEQUENCE_SHARE中，使用SEQUENCE_SHARE::MUTEX进行保护，所有对cache的访问是串行的。比如cache size是20，那么SEQUENCE_SHARE中只是保存一个cache_end值，当访问的NEXTVAL到了cache_end，就会从基表中获取下一个batch放到cache中。NEXTVAL根据INCREMENT BY设置的步长进行迭代。

4. Sequence update

当cache用完了之后，会从基表中获取下一个batch，这样会更新基表中的记录，查询会转化成更新语句，
其更新的主要步骤如下:

1. 升级SEQUENCE的MDL_SHARE_READ METADATA LOCK 到 MDL_SHARE_WRITE级别
2. 持有GLOBAL MDL_INTENSIVE_EXCLUSIVE METADATA LOCK
3. 开启AUTONOMOUS TRANSACTION
4. 更新记录并生成BINLOG EVENT
5. 持有COMMIT METADATA LOCK
6. XA提交AUTONOMOUS TRANSACTION 并释放MDL锁

5. Autonomous transaction

因为nextval不支持ROLLBACK重用，所以必须重启一个自治事务来脱离事务上下文，
其步骤如下：

1. 备份当前基表引擎的事务上下文
2. 备份当前BINLOG引擎的上下文
3. SEQUENCE和BINLOG分别注册AUTONOMOUS TRANSACTION
4. 等更新完成，XA提交AUTONOMOUS TRANSACTION
5. 还原当前事务上下文

6. Sequence read only

因为SEQUENCE的SELECT语句会转换成UPDATE语句，所以SELECT NEXTVAL FOR s statement须持有 MDL_SHARE_WRITE 和 GLOBAL MDL_INTENSIVE_EXCLUSIVE METADATA LOCK 进行，以便在READ ONLY的时候，阻塞对sequence对象的访问。

7. Skip cache

这里指两种CACHE:

• 一种是SEQUENCE的CACHE，可以使用SELECT NEXTVAL FORM Sequence_name来skip。
• 另外一种是QUERY CACHE，所有的SEQUENCE都设置了不支持QUERY CACHE，这样避免由于QUERY CACHE导致NEXTVAL没有迭代。

8. Sequence backup

由于SEQUENCE是通过真正的引擎表来保存的，所以类似XtraBackup这样的物理备份可以直接使用，而类似于MYSQLDUMP这样的逻辑备份，SEQUENCE会备份成CREATE SEQUENCE语句和INSERT语句的组合来完成。

Next Release

本次开源了部分功能，下一次release将继续开源SEQUENCE的部分功能：

• 支持CURRVAL的访问，CURRVAL表示当前session的上一次的NEXTVAL访问的值。
• 兼容更多数据库的访问方法，比如：

Oracle Syntax:
  SELECT sequence_name.nextval FROM DUAL;

PostgreSQL Syntax:
  nextval(regclass);
  currval(regclass);
  setval(regclass, bigint);

Usage Scenario

1. 更具有业务含义的主键设计 .

例如：[八位日期 + 四位USER ID + sequence_number]的流水业务单据号的设计格式，可以通过SELECT NEXTVAL FOR Sequence和应用封装的方式实现，相比较无意义的id数字，这种格式会带来几个优势：

• 保持和时间同步的有序性，有利于数据的归档，比如可以直接使用这种ID来进行按日/月/年RANGE分区, 无缝使用MySQL的partition特性
• 增加USER的id信息，可以作为天然的分库分表逻辑位， 提升数据节点可扩展性
• 保持数字的有序性，保证InnoDB这种聚簇索引表的插入性能稳定

业界目前采用的设计方法：

• Booking使用了AUTO_INCREMENT的方法， 先插入一个无业务含义的数字，然后使用last_insert_id()方法获取ID值，最后在业务逻辑中使用这个ID值。 其劣势就是必须先插入，并没有办法再修改这个无业务含义的id。
• Twitter采用了另外一种格式，[41 bits timestamp + 10 bits configured machine ID + 12 bits sequence number], sequence number的生成机制没有透露，machine ID的的设计，使用Zookeeper来管理的machine ID或者机器的MAC address。
• UUID的方法，这种方式生成了一个随机的唯一值，严重影响了插入的性能，并且增大了索引大小，降低了命中率，没有任何优势。

2. 分布式节点的唯一值设计

分布式SEQUENCE生成:

• 可以为每一个节点设计sequence，比如为每个节点设计不同的INCREMENT BY步长来达到MySQL AUTO_INCREMENT中，设置auto_increment_increment和auto_increment_offset的效果，但相比较auto increment的全局配置，并且保存在my.cnf中的方法，SEQUENCE可以把这些配置当做sequence对象的属性持久化保存下来，优势明显。但不推荐使用这种方法来设计唯一值，会给运维留下不少坑。
• 使用类似twitter的方法，每一个节点上创建sequence，然后增加节点信息到sequence number中，生成唯一值。

集中式SEQUENCE生成:

• 对于分布式节点中的ID需求，使用独立的集中式的sequence服务来生成，但如果要保证持续可用，sequence服务仍然需要设计成多节点的，比如Flickr的Ticket Servers设计：

Sequence服务节点上创建Ticket表：

CREATE TABLE `Tickets64` (
  `id` bigint(20) unsigned NOT NULL auto_increment,
  `stub` char(1) NOT NULL default '',
  PRIMARY KEY  (`id`),
  UNIQUE KEY `stub` (`stub`)
) ENGINE=MyISAM

+-------------------+------+
| id                | stub |
+-------------------+------+
| 72157623227190423 |    a |
+-------------------+------+

使用以下语句，生成ID值：

REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();

因为PHOTOS，COMMENTS，FAVORITES，TAGS都需要ID, 所以会建不同的ticket表来完成，为了保持持续可用，采用了：

TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1

TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2

来保证高可用。
如果使用sequence对象，可以大大简化ID的获取逻辑，并更加安全。