本文作者Peter Bailis是美國(guó)Berkeley的研究生，主要研究方向是分布式系統(tǒng)與數(shù)據(jù)庫(kù)。作者目前主要的研究?jī)?nèi)容是分布式數(shù)據(jù)的一致性，尤其是如何調(diào)和ACID特性和分布式一致性模型，以及如何在理論和實(shí)際中更好的理解最終一致性。

作者將分布式系統(tǒng)中的事務(wù)定義為針對(duì)多個(gè)服務(wù)器的同時(shí)操作，本文主要討論了分布式系統(tǒng)事務(wù)的原子性的一種實(shí)現(xiàn)算法。通常情況下原子性都是通過(guò)鎖實(shí)現(xiàn)的，這個(gè)算法并沒(méi)有使用鎖，原理很簡(jiǎn)單，采用了簡(jiǎn)單的多版本控制和存儲(chǔ)一些額外的元數(shù)據(jù)，雖然作者只是在實(shí)驗(yàn)環(huán)境中實(shí)現(xiàn)了這個(gè)算法，并沒(méi)有投入到實(shí)際生產(chǎn)中，但是作者思考問(wèn)題的方式值得參考。

分布式系統(tǒng)事務(wù)原子性

在現(xiàn)實(shí)的分布式系統(tǒng)中，多對(duì)象更新的操作很常見(jiàn)，但是實(shí)現(xiàn)起來(lái)卻并不簡(jiǎn)單。同時(shí)更新兩個(gè)或多個(gè)對(duì)象時(shí)，對(duì)于這些對(duì)象的其他讀取者，原子性很重要：你的更新要么全部可見(jiàn)，要么全部不可見(jiàn)。

這里所說(shuō)的原子性和線性一致并不是一個(gè)概念，數(shù)據(jù)一致性在Gilbert和Lynch證明CAP原理時(shí)被提到過(guò)，后來(lái)通常被稱為原子一致性。而線性一致化關(guān)注實(shí)時(shí)的順序操作，是一個(gè)單對(duì)象的問(wèn)題。這里的“原子性”源于數(shù)據(jù)庫(kù)環(huán)境(ACID中的“A”)，涉及對(duì)多個(gè)對(duì)象的執(zhí)行和查詢操作。為了避免混淆，我們稱這個(gè)原子性為“事務(wù)原子性”。

許多場(chǎng)景中都會(huì)遇到這種問(wèn)題，從社交網(wǎng)絡(luò)圖(例如Facebook的TAO系統(tǒng)，雙向的朋友關(guān)系被保存在兩個(gè)單向的指針中)到類似計(jì)數(shù)器(例如Twitter的Rainbird分層聚合器)和二級(jí)索引的分布式數(shù)據(jù)結(jié)構(gòu)。本文中，我將假設(shè)我們的工作都是高可用的事務(wù)，原子性的多對(duì)象更新，或事務(wù)的原子性，是其首要特性。

現(xiàn)有的技術(shù)

多對(duì)象更新的事務(wù)操作通常采用以下三種策略之一：

鎖

使用鎖來(lái)同時(shí)更新多個(gè)項(xiàng)目。執(zhí)行更新操作時(shí)加寫鎖，執(zhí)行讀操作時(shí)加讀鎖，就可以保證事務(wù)的原子性。但是在分布式環(huán)境中，局部故障和網(wǎng)絡(luò)延遲都意味著鎖操作可能會(huì)導(dǎo)致Bad Time。

具體來(lái)講，鎖操作有可能會(huì)導(dǎo)致一些怪異的結(jié)果。如果客戶端在持有鎖時(shí)宕機(jī)，服務(wù)器本應(yīng)該最終撤銷這個(gè)鎖。這需要某種形式的故障檢測(cè)或超時(shí)(在異步網(wǎng)絡(luò)中會(huì)導(dǎo)致一些尷尬的情況)以及在撤銷鎖前同時(shí)撤銷以前的操作。但是在執(zhí)行更新操作時(shí)阻塞讀操作顯然是不合理的，反之亦然。如果我們追求高可用性，鎖不是一個(gè)值得考慮的方案。

實(shí)體組

將想要同時(shí)更新的對(duì)象放在一起。這種策略通常稱為“實(shí)體組”，可以讓事務(wù)性原子更簡(jiǎn)單：在一臺(tái)機(jī)器上加鎖很快，而且不會(huì)遇到分布式鎖的局部故障和網(wǎng)絡(luò)延遲的問(wèn)題。不幸的是，這種解決方案會(huì)影響數(shù)據(jù)布局和分布，而且不適用于難于分割的數(shù)據(jù)。

Fuck-it模式

使用“fuck-it”模式，不進(jìn)行任何并發(fā)控制的情況下更新所有的對(duì)象，并保持事務(wù)的原子性。這個(gè)策略是很常見(jiàn)的：擴(kuò)展性良好，適用于任何系統(tǒng)，但是直到系統(tǒng)達(dá)到穩(wěn)定狀態(tài)后，才會(huì)提供原子性保證(例如聚合，或者說(shuō)最終一致性)。

NBTA

在這篇文章中，作者會(huì)介紹一種簡(jiǎn)單的替代方案，作者稱其為事務(wù)原子性的非阻塞實(shí)現(xiàn)，簡(jiǎn)稱為NBTA(Non-blocking transactional atomicity)，使用多版本和一些額外的元數(shù)據(jù)在不使用鎖的情況下，保證事務(wù)的原子性。具體來(lái)說(shuō)，這種方案不會(huì)由于過(guò)程錯(cuò)誤而阻塞讀取和寫入操作。關(guān)鍵的想法是避免執(zhí)行局部更新，并且利用額外的元數(shù)據(jù)代替副本間的同步。

NBTA示例

可以用這個(gè)簡(jiǎn)單的場(chǎng)景來(lái)說(shuō)明NBTA：有兩個(gè)服務(wù)器，server for x上存儲(chǔ)x，server for y上存儲(chǔ)y，初值都是0。假設(shè)有兩個(gè)客戶端，Client1要執(zhí)行寫入操作，使x=1，y=1，Client2要同時(shí)讀取x和y，關(guān)于副本的問(wèn)題稍后會(huì)討論。作者將Client1要執(zhí)行的寫入操作稱為一個(gè)事務(wù)，而這個(gè)事務(wù)的操作對(duì)象server for x和server for y被稱為事務(wù)兄弟。

good和pending

將每臺(tái)服務(wù)器的存儲(chǔ)分為兩中狀態(tài)：good和pending。要保證同屬于一個(gè)事務(wù)的寫入操作，如果其中一個(gè)操作被存儲(chǔ)為good狀態(tài)，這個(gè)事務(wù)的其它寫入操作要么被存儲(chǔ)為good，要么被存儲(chǔ)為pending。比如在上面所說(shuō)的場(chǎng)景中，如果x=1在server for x上被存儲(chǔ)為good，那么必須保證y=1在server for y被存儲(chǔ)為good或pending。

首先，各服務(wù)器會(huì)收到到寫操作請(qǐng)求保存為pending狀態(tài)，然后一旦服務(wù)器知曉(可能是異步的)某個(gè)寫入操作相關(guān)的事務(wù)兄弟都已經(jīng)將操作請(qǐng)求保存為pending狀態(tài)，這個(gè)服務(wù)器就會(huì)更新這個(gè)操作為good狀態(tài)?？蛻舳诉M(jìn)行兩輪通信，就可以使服務(wù)器得到寫操作已經(jīng)穩(wěn)定的信息：第一輪通信中，server for x和server for y會(huì)將從Client1收到請(qǐng)求保存為pending狀態(tài)，并將確認(rèn)回復(fù)給Client1，Client1收到確認(rèn)后會(huì)進(jìn)行第二輪通信，通知server for x和server for y寫操作已達(dá)到穩(wěn)定狀態(tài)。

競(jìng)爭(zhēng)危害和指針

理想的狀態(tài)是，只讀取good狀態(tài)的數(shù)據(jù)，就可以保證事務(wù)的原子性。但是存在一種競(jìng)爭(zhēng)條件的情況：比如server for x已經(jīng)更新x=1，并保存為good狀態(tài)，但在其事務(wù)兄弟server for y中相關(guān)操作y=1依舊是pending狀態(tài)，Client2如果只讀取good狀態(tài)的數(shù)據(jù)，得到的結(jié)果將是x=1，y=0，破壞了事務(wù)的原子性。我們希望這種情況下，第二個(gè)服務(wù)器能夠自動(dòng)調(diào)用pending狀態(tài)的數(shù)據(jù)以供讀取。

為了解決這個(gè)問(wèn)題，可以在每個(gè)寫入操作中加入一些額外的信息：事務(wù)兄弟的列表以及一個(gè)時(shí)間戳。這個(gè)時(shí)間戳是客戶端進(jìn)行多值更新前，為每個(gè)寫操作唯一生成的，比如，可以是客戶端ID+本地時(shí)間或一個(gè)隨機(jī)數(shù)。這樣的話，當(dāng)一個(gè)客戶端讀取good狀態(tài)的數(shù)據(jù)時(shí)，還會(huì)讀到時(shí)間戳和具有相同時(shí)間戳的事務(wù)兄弟的列表。客戶端也會(huì)在發(fā)送讀取請(qǐng)求附帶一個(gè)時(shí)間戳，服務(wù)器會(huì)根據(jù)時(shí)間戳從pending或good中取出數(shù)據(jù)交付給客戶端。如果客戶端的請(qǐng)求中沒(méi)有附帶時(shí)間戳，服務(wù)器會(huì)將good中時(shí)間戳最高的值交付給客戶端。

優(yōu)化

以下是NBTA算法的一些優(yōu)化：

pending和good的規(guī)模

如果用在good中只保存最近的寫入操作，那么一個(gè)寫入操作的兄弟事務(wù)可能會(huì)被覆蓋，為了避免這種情況的發(fā)生，服務(wù)器會(huì)在good中將歷史數(shù)據(jù)保留一定的時(shí)間。

更快的寫操作

有一種方案可以替代客戶端的第二輪通信操作。服務(wù)器一旦將寫操作存入pending中，就直接互相通信，可使用類似于PAXOS的算法實(shí)現(xiàn)。此外，客戶端也可以異步發(fā)起第二輪通信。然而，為了確保客戶端在這些情況下讀取寫操作，它們要保留元數(shù)據(jù)直到每個(gè)寫操作都被存為good狀態(tài)。

副本

目前為止的討論都基于每個(gè)數(shù)據(jù)項(xiàng)只存儲(chǔ)在一個(gè)服務(wù)器上。算法實(shí)現(xiàn)的前提條件是每個(gè)服務(wù)器的強(qiáng)一致性。服務(wù)器間的副本有兩種情況：如果所有的客戶端都只能訪問(wèn)一部分服務(wù)器，那么客戶端只需要對(duì)這些對(duì)應(yīng)的服務(wù)器集合進(jìn)行更新，這組服務(wù)器都存有數(shù)據(jù)的副本。如果客戶端可以訪問(wèn)任何服務(wù)器，那么需要花費(fèi)較長(zhǎng)的時(shí)間去同步數(shù)據(jù)。

讀/寫事務(wù)

以上討論的算法同樣適用于讀/寫操作。對(duì)于ANSI標(biāo)準(zhǔn)的可重復(fù)讀模型，主要的問(wèn)題是保證從一個(gè)事務(wù)的原子組中讀取?？梢栽谑聞?wù)執(zhí)行前，事先聲明所有的讀取操作或者通過(guò)類似向量時(shí)間的元數(shù)據(jù)實(shí)現(xiàn)。

元數(shù)據(jù)的規(guī)模

最謹(jǐn)慎的做法是將元數(shù)據(jù)一直保存，但是也可以在寫操作在所有服務(wù)器中都達(dá)到good狀態(tài)時(shí)，將元數(shù)據(jù)刪除。

算法的實(shí)現(xiàn)

作者采用LevelDB數(shù)據(jù)庫(kù)實(shí)現(xiàn)了NBTA算法及其改進(jìn)。在Yahoo!的云平臺(tái)上，8個(gè)操作的NBTA事務(wù)可以達(dá)到最終一致性的33%(所有都是寫操作)至95.2%(所有都是讀操作)峰值吞吐量。并且這種實(shí)現(xiàn)是線性擴(kuò)展的，運(yùn)行50個(gè)EC2實(shí)例，對(duì)于長(zhǎng)度為8的事務(wù)(50%的讀操作，50%的寫操作)，可以達(dá)到每秒執(zhí)行250000次操作。

實(shí)驗(yàn)結(jié)果表明NBTA的性能大大優(yōu)于基于鎖的操作，因?yàn)椴粫?huì)發(fā)生阻塞。主要的花銷來(lái)自于元數(shù)據(jù)以及將寫入操作從pending更新為good?；谶@些結(jié)果，作者已經(jīng)開(kāi)始將NBTA應(yīng)用于其它數(shù)據(jù)存儲(chǔ)和二級(jí)索引上。

結(jié)論

這篇文章展現(xiàn)了如何在不使用鎖的情況下，實(shí)現(xiàn)在任意數(shù)據(jù)分片的原子性多對(duì)象更新。數(shù)據(jù)庫(kù)中有很多類似于NBTA的算法。例如客戶端第二輪通信的優(yōu)化是通過(guò)PAXOS的算法實(shí)現(xiàn)的，使用額外的元數(shù)據(jù)保持并發(fā)更新類似于B樹(shù)或其它非鎖的數(shù)據(jù)結(jié)構(gòu)。當(dāng)然，多版本并發(fā)控制和基于時(shí)間戳的并發(fā)控制在數(shù)據(jù)庫(kù)系統(tǒng)中也都有悠久的歷史。但是NBTA的關(guān)鍵是實(shí)現(xiàn)事務(wù)的原子性，同時(shí)避免中央集權(quán)的時(shí)間戳或并發(fā)控制機(jī)制。具體來(lái)說(shuō)要在數(shù)據(jù)讀取操作前達(dá)到一個(gè)穩(wěn)定狀態(tài)，主要的挑戰(zhàn)是解決競(jìng)爭(zhēng)條件。在實(shí)際中，相比其它基于鎖的技術(shù)，這個(gè)算法表現(xiàn)得很好。