在數據庫的使用場景中，最常見的是并發插入數據或并發導入數據場景。在該場景中并不指定自增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%。