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

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

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

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

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

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

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

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

鎖

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

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

實(shí)體組

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

Fuck-it模式

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

NBTA

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

NBTA示例

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

good和pending

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

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

競爭危害和指針

理想的狀態(tài)是，只讀取good狀態(tài)的數(shù)據(jù)，就可以保證事務(wù)的原子性。但是存在一種競爭條件的情況：比如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ù)的原子性。我們希望這種情況下，第二個服務(wù)器能夠自動調(diào)用pending狀態(tài)的數(shù)據(jù)以供讀取。

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

優(yōu)化

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

pending和good的規(guī)模

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

更快的寫操作

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

副本

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

讀/寫事務(wù)

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

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

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

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

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

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

結(jié)論

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