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

譯者  沈剛

|  事務(wù)調(diào)度

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

當(dāng)有多個事務(wù)同時需要獲取同一把鎖，那么哪個事務(wù)應(yīng)該最先獲得這把鎖？

包括之前版本的MySQL在內(nèi)，幾乎所有的數(shù)據(jù)庫都是通過FIFO機(jī)制來解決這個問題。簡單來說，F(xiàn)IFO機(jī)制就是將鎖分配給最先請求該鎖的事務(wù)（即該事務(wù)在等待隊(duì)列的最前面，除非它們與當(dāng)前鎖賦予的鎖不兼容）。因?yàn)檫@種機(jī)制實(shí)現(xiàn)起來比較簡單，所以很多的數(shù)據(jù)庫廠商都是通過FIFO的策略進(jìn)行事務(wù)調(diào)度，沒有考慮其他的調(diào)度策略。 

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

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

|  CATS機(jī)制原理

CATS算法是基于很簡單的一個觀點(diǎn)：不是所有的事務(wù)都是平等的，不是所有的對象都是平等的。當(dāng)一個事務(wù)已經(jīng)持有了多個對象的鎖，當(dāng)該事務(wù)請求一個新的鎖的時候，該事務(wù)應(yīng)該被優(yōu)先分配。從另一個方面講，解鎖這樣的事務(wù)有助于解鎖更多的事務(wù)。因?yàn)樵撌聞?wù)優(yōu)先被分配鎖能更快的結(jié)束事務(wù)，釋放另外已經(jīng)獲取到的對象的鎖。通過這種方式可以使數(shù)據(jù)庫獲得更高的吞吐和更低的延遲。 

有一個比喻的例子：如果有一個出租車司機(jī)和一個公交車司機(jī)都在等咖啡，那么先給公交車司機(jī)做咖啡（即使公交車司機(jī)比出租車司機(jī)遲來）可能會讓更多的人盡早到達(dá)他們的目的地。因?yàn)楣卉嚿系某丝捅瘸鲎廛嚿系某丝投?。這看起來似乎對出租車司機(jī)不公平，但是這種策略可以使得整個系統(tǒng)運(yùn)行的更快，這對于系統(tǒng)內(nèi)的每個人都是有利的。 

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

Transaction contention 

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

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

|  CATS機(jī)制帶來的性能提升

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

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

|  結(jié)論

MySQL是全球第一個使用這種最先進(jìn)的CATS事務(wù)調(diào)度算法的數(shù)據(jù)庫。這個算法解決了數(shù)據(jù)庫在遇到高壓力情況下性能急劇下降的問題，這個也是MySQL 8.0主要想要達(dá)到的目標(biāo)。 

CATS算法是針對當(dāng)事務(wù)并發(fā)超過32的情況，這個數(shù)值沒有參數(shù)配置，是通過經(jīng)驗(yàn)設(shè)置的。

|  譯者簡介

沈 剛·沃趣科技數(shù)據(jù)庫技術(shù)專家

熟悉MySQL數(shù)據(jù)庫運(yùn)行機(jī)制，豐富的數(shù)據(jù)庫及復(fù)制架構(gòu)故障診斷、性能調(diào)優(yōu)、數(shù)據(jù)庫備份恢復(fù)及遷移經(jīng)驗(yàn)。