https://mysqlserverteam.com/contention-aware-transaction-scheduling-arriving-in-innodb-to-boost-performance/ 

譯者  沈剛 

|  事務調度

目前大多數的數據庫系統都是通過鎖的方式來控制并發的情況。但是對于很多數據庫廠商來說，都會有一個問題:

當有多個事務同時需要獲取同一把鎖，那么哪個事務應該最先獲得這把鎖？

包括之前版本的MySQL在內，幾乎所有的數據庫都是通過FIFO機制來解決這個問題。簡單來說，FIFO機制就是將鎖分配給最先請求該鎖的事務（即該事務在等待隊列的最前面，除非它們與當前鎖賦予的鎖不兼容）。因為這種機制實現起來比較簡單，所以很多的數據庫廠商都是通過FIFO的策略進行事務調度，沒有考慮其他的調度策略。 

最近一個密歇根大學的研究組織提出，這個問題背后隱藏著巨大的性能提升空間。Mozafari教授和他的學生證明了不同的鎖分配策略以及事務調度策略對于數據庫性能有著很大的影響。他們提出了一種稱之為Contention-Aware Transaction Scheduling(CATS)的算法，使用這種算法進行事務調度相較于之前的FIFO策略，顯著地減少了數據庫延遲，提高了吞吐量。 

Oracle MySQL官方團隊和Mozafari教授以及他的學生們緊密合作，使得MySQL是第一個采用這種新技術的數據庫。在MySQL 8.0.3版本之后，CATS策略作為InnoDB的默認調度算法，也就是說MySQL的使用者可以感覺到顯著的性能提升，尤其是在持續高壓力負載的情況下。

|  CATS機制原理

CATS算法是基于很簡單的一個觀點：不是所有的事務都是平等的，不是所有的對象都是平等的。當一個事務已經持有了多個對象的鎖，當該事務請求一個新的鎖的時候，該事務應該被優先分配。從另一個方面講，解鎖這樣的事務有助于解鎖更多的事務。因為該事務優先被分配鎖能更快的結束事務，釋放另外已經獲取到的對象的鎖。通過這種方式可以使數據庫獲得更高的吞吐和更低的延遲。 

有一個比喻的例子：如果有一個出租車司機和一個公交車司機都在等咖啡，那么先給公交車司機做咖啡（即使公交車司機比出租車司機遲來）可能會讓更多的人盡早到達他們的目的地。因為公交車上的乘客比出租車上的乘客多。這看起來似乎對出租車司機不公平，但是這種策略可以使得整個系統運行的更快，這對于系統內的每個人都是有利的。 

當然，我們現在是在解決鎖的問題而不是交通司機的問題。讓我們通過一個簡單的例子來闡述一下CATS機制在數據庫中是如何工作的。我們知道在不同的事務隔離級別下，事務在讀取或者更新數據的時候，需要先獲取對應數據的鎖。當一個事務所需要的鎖已經被其他事務所持有了，那么這個事務會一直等待直到其他事務釋放這個鎖。當事務已經持有一部分對象鎖的時候，可能會在獲取其他對象的鎖的時候一直被阻塞住，這個時候就需要死鎖檢測機制來檢測當前數據庫中沒有鎖等待循環，防止死鎖。來看下面這張圖： 

Transaction contention 

在這種場景下，FIFO策略很簡單，只需要考慮那個事務先請求O1對象的鎖。但是CATS算法會更加智能地處理這個情況：CATS算法會計算每個事務直接阻塞和間接阻塞的事務數量，然后將O1對象的鎖分配給阻塞了更多事務的事務。在這個場景下，t1事務阻塞了4個事務，t2事務阻塞了3個事務。所以根據CATS算法會將O1對象的鎖分配給t1事務。這樣可以將更多的事務釋放出來，這樣有利于提高系統整體的性能。 

對于共享鎖（S鎖），CATS算法會盡可能多的分配共享鎖。在這方面FIFO和CATS算法有不同的地方。FIFO按照隊列的先后順序分配共享鎖，當遇到分配的對象上已經有排他鎖（X鎖）了，則停止分配。而在CATS中，按照事務阻塞的事務數進行倒序排序，然后按照這個順序進行鎖分配。

|  CATS機制帶來的性能提升

Oracle的Dimitri Kravtchuk通過Sysbench 的OLTP腳本測試這種新的算法。通過結果顯示，在并發情況下，CATS算法比FIFO算法在TPS，平均延遲，95%延遲等指標方面都有顯著的性能提升。有趣的是，即使在沒有并發的情況下，CATS算法的性能和FIFO算法性能是一樣的。那是因為在沒有并發的時候，沒有事務需要進行調度，所以也就沒有性能的差異。換而言之，使用CATS算法替換FIFO算法，沒有任何損失，反而在數據庫繁忙的時候，有很大的性能提升。

CATS vs. FIFO in TPS, mean latency and 95th percentile (up to 5.05x improvement)

|  結論

MySQL是全球第一個使用這種最先進的CATS事務調度算法的數據庫。這個算法解決了數據庫在遇到高壓力情況下性能急劇下降的問題，這個也是MySQL 8.0主要想要達到的目標。 

CATS算法是針對當事務并發超過32的情況，這個數值沒有參數配置，是通過經驗設置的。

|  譯者簡介

沈 剛·沃趣科技數據庫技術專家

熟悉MySQL數據庫運行機制，豐富的數據庫及復制架構故障診斷、性能調優、數據庫備份恢復及遷移經驗。