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

譯者  沈剛

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

目前大多數(shù)的數(shù)據(jù)庫(kù)系統(tǒng)都是通過(guò)鎖的方式來(lái)控制并發(fā)的情況。但是對(duì)于很多數(shù)據(jù)庫(kù)廠商來(lái)說(shuō)，都會(huì)有一個(gè)問(wèn)題:

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

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

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

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

|  CATS機(jī)制原理

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

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

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

Transaction contention 

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

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

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

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

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

|  結(jié)論

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

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

|  譯者簡(jiǎn)介

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

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