在数据库的使用场景中，最常见的是并发插入数据或并发导入数据场景。在该场景中并不指定自增ID，而是由数据库自动生成自增ID并插入到数据库中。因此，此类场景也称之为auto_inc场景下的数据插入。典型的业务场景如：游戏行业开服过程中大批的登录注册场景、电商活动中给商家后台推单场景等等。本文介绍了PolarDB对此类并发插入场景下的性能优化相关内容。
背景知识
在并发插入场景中，ID是递增的，直观感受上这种场景是插入到B-tree最右边的一个page中。但实际上并不是这样，这种场景并不能保证插入数据的连续性。因此，在插入数据的过程中，有可能插入的值比最右边的Page的最小值小，最终数据插入到了右边第2个page中。故这种场景其实是将数据插入到最右边的多个page中。因为插入线程获得auto_inc值后，直到真正执行INSERT操作这一段代码并没有加锁。因此，优先获得auto_inc的线程被调度走，而后获得auto_inc的线程先执行了INSERT操作。并发INSERT时，后续有可能插入比当前auto_inc的value小的行。示例如下：
mysql> create table t1 (`id` int(10) NOT NULL AUTO_INCREMENT,`c1` int(11) NOT NULL,PRIMARY KEY (`id`));
Query OK, 0 rows affected (0.04 sec)
### Session 1 ### Session 2
mysql> INSERT INTO t1 (c1) VALUES (123); mysql> INSERT INTO t1 (c1) VALUES (456);
Query OK, 1 row affected (20.41 sec) Query OK, 1 row affected (0.06 sec)
mysql> select * from t1;
+----+-----+
| id | c1 |
+----+-----+
| 2 | 456 |
+----+-----+
mysql> select * from t1;
+----+-----+
| id | c1 |
+----+-----+
| 1 | 123 |
| 2 | 456 |
+----+-----+Session1和Session2并发执行，Session2优先执行了INSERT操作。
由于Level 0存在多个page同时进行插入的情况，所以会出现以下场景：
在上图中，有3个线程进行乐观插入，插入的值为14、25和36。此时可以持有各自的page x lock来实现3个page同时并发插入。如果thread = 1，那么只有最右边的page进行插入，性能一定没有3个page同时并发插入的性能好。理论上允许同时插入的leaf page越多，并发越高，性能越好。要实现允许同时插入的leaf page越多，需要尽早进行SMO操作，使得Page尽早分裂，那么就需要有更多未被插满的Page允许用户同时进行插入。所以，PolarDB auto_inc场景性能优化点就是尽早执行SMO操作。下文介绍了InnoDB B-tree和Blink-tree在auto_inc场景下为尽早执行SMO操作所做的优化内容。
InnoDB B-tree在auto_inc场景下的性能优化
并发插入场景中，InnoDB中的实际情况如下：
经过测试发现，可能存在因为线程调度问题造成auto_inc差值允许3~4个Page同时插入的情况，初始场景如上图。
阶段1：当前有3个线程分别乐观插入到3个不同的level 0 leaf page中，并持有3个leaf page x lock。同时，还有N个线程持有Level 1 page s lock，等待在level 0 leaf page x lock上，即等待当前3个线程完成插入后N个线程再进行插入。
阶段2：此时SMO线程进行悲观插入，SMO线程持有index sx lock和Level 2 page x lock，等待在持有Level 1 Page的x lock上，但当前Level 1 page上已经有N个乐观插入线程持有page s lock在等待。
阶段3：SMO线程需要等待之前的N个乐观插入线程完成后（最右边Page的乐观插入大概率会失败，因为这次SMO操作就是为了做最右边Page的SMO，那么乐观线程插入失败以后会转换成悲观线程进行插入），获得了Level 1 Page x lock，再等待Level 0 leaf page上的X lock完成加锁操作，然后进行SMO操作。
SMO线程需要等待N个线程完成乐观插入尝试后，才可以进行SMO操作，且并发度越高，乐观插入线程越多。但SMO线程等待的时间越长，SMO操作越不能尽早执行，从而会导致性能无法提升。
那么为什么限制了Innodb_thread_concurrency以后，可以获得更好的性能呢?
从上面的分析可以看出，在auto_inc场景中，并发插入的Page并不多，差不多只有3~4个Page允许同时插入。过多的线程会导致SMO线程必须等待这些乐观线程插入尝试完成以后才能进行插入，乐观插入线程越多，等待的时间就会越长。最理想的情况是此时最右边的Page上没有乐观插入在等待，那么SMO线程就可以不需要等待任何线程，实现了尽早执行SMO操作这个目标。而限制Innodb_thread_concurrency相当于限制了乐观插入线程的数量，因此实现了更好的性能。实际测试中Innodb_thread_concurrency = 8就可以实现几乎最好的性能。
Blink-tree在auto_inc场景下的性能优化
现有的InnoDB Btree版本存在问题时，提出的解决方案是通过设置Innodb_thread_concurrency = 8来降低并发插入线程，从而保证高性能的插入。但Innodb_thread_concurrency = 8太低，正常使用过程中还有查询操作，因此，在实际使用过程中很少会进行这样的设置。
Blink-tree本身允许SMO并发，现有的InnoDB Btree同一时刻只能允许一个SMO执行，允许SMO并发执行相当于尽早执行SMO操作。
增加SMO线程还不够，如果SMO线程和上述InnoDB Btree实现一样，需要等待乐观插入完成后才能进行SMO操作，那么实际上多个SMO操作也是串行执行的，只需要提前执行SMO的时间。
因此，在Blink-tree上实现锁的优先级调度，从而实现尽早执行SMO操作。
在上述InnoDB Btree的阶段3中SMO线程需要和乐观插入线程去争抢执行的优先级，从而导致SMO线程执行效率不高。通过锁的优先级调度，赋予SMO线程最高的优先级，先唤醒等待在Page x lock上的SMO线程，然后再唤醒等待在address lock上的乐观插入线程，从而实现尽早执行SMO操作。
具体的实现方式如下图所示：
Blink-tree通过Lock coupling进行加锁，即使在悲观插入场景中，Level 1依然是S lock。
阶段1：当前有3个SMO线程正在并发执行SMO。因为Blink-tree实现SMO和Btree类似，需要持有右边的page lock，因此只有SMO 1能够执行，而SMO 2或SMO 3等待右边的Page Xlock。
阶段2：有N个线程尝试进行乐观插入操作，乐观插入时发现Page 1/2/3都在执行SMO操作，只有Page 4没有执行SMO操作。因此，想插入Page 1/2/3的线程放弃当前Page s lock，而等待在Page 1/2/3的address lock上，想插入Page 4的线程等待在Page 4 x lock上。
阶段3：SMO 1执行完后，通知SMO 2执行，然后唤醒等待在Page 1 address lock上的乐观插入线程。由于SMO 2正在执行SMO操作，且持有Page 1 X lock。因此，乐观插入线程需要等待SMO 2执行结束后才可以执行。SMO 2执行结束后通知SMO 3执行，同时唤醒等待在Page 2 address lock上的乐观插入线程。但是，由于SMO 3正在进行中，且持有Page 2 X lock。因此，乐观插入Page 2的线程因为SMO 3持有Page 2 X lock而无法执行SMO操作。但此时Page 1乐观插入线程已经可以执行，最后等待SMO 3也执行完成，Page 2/3的乐观插入线程也就可以执行了。
可以看出，Blink-tree通过增加并发SMO线程数量，同时引入锁的优先级调度，从而实现尽早执行SMO操作。从而实现了较InnoDB Btree更高的性能。
这里还有一个与InnoDB Btree在auto_inc场景下的性能优化的区别，等待address唤醒之后的乐观插入线程执行的依然是乐观插入操作，而InnoDB Btree 等待Page lock被唤醒之后执行的是悲观插入操作。
具体测试场景的数据如下：
Blink-tree在auto_inc场景下的性能是官方B-tree版本的2倍，同时较InnoDB B-tree在auto_inc场景下的性能提升了约13%。