PolarDB auto_inc场景性能优化之路

背景知识

在并发插入场景中，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%。