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%。