作者｜根泰，攜程高級后端開發(fā)工程師，關(guān)注數(shù)據(jù)存儲和數(shù)據(jù)庫領(lǐng)域；遐齡，攜程研發(fā)總監(jiān)，關(guān)注大數(shù)據(jù)存儲、性能調(diào)優(yōu)。

Dynamo風(fēng)格數(shù)據(jù)庫來源于亞馬遜的Dynamo: Amazon’s Highly Available Key-value Store 論文，在該論文中論述了一種無主復(fù)制的數(shù)據(jù)庫，受此啟發(fā)，攜程酒店開發(fā)了多存儲介質(zhì)預(yù)定庫Hare和高可用性高性能的動態(tài)信息存儲服務(wù)InfoKeeper。本文將介紹Dynamo風(fēng)格的無主復(fù)制數(shù)據(jù)庫，及其在攜程酒店的實踐。

一、Dynamo風(fēng)格數(shù)據(jù)庫

在分布式系統(tǒng)中，為了提高數(shù)據(jù)的可用性和性能，通常會將同樣的數(shù)據(jù)復(fù)制多份，分擔(dān)讀寫請求和主備切換，在復(fù)制形式上，主要有單主復(fù)制、多主復(fù)制、無主復(fù)制。

1.1 單主復(fù)制

在單主復(fù)制中，只有一個主節(jié)點可以寫入，數(shù)據(jù)從主節(jié)點復(fù)制到從節(jié)點，從節(jié)點可以承擔(dān)讀請求，單主復(fù)制的結(jié)構(gòu)簡單，易于實現(xiàn)，沒有數(shù)據(jù)沖突。但是寫入依賴主節(jié)點，寫入性能由主節(jié)點的性能決定，主從節(jié)點之間存在復(fù)制延遲（在從節(jié)點上讀取到的數(shù)據(jù)不一定是最新的數(shù)據(jù)），在主節(jié)點發(fā)生故障進(jìn)行主從切換的時候存在數(shù)據(jù)丟失或者寫入的不可用。

1.2 多主復(fù)制

在多主復(fù)制中，有多個主節(jié)點承擔(dān)寫入的請求，相比于單主復(fù)制，數(shù)據(jù)的寫入請求被多個主節(jié)點分擔(dān)，但主從節(jié)點之間的復(fù)制延遲問題依然存在。除此之外，兩個主節(jié)點對同一份數(shù)據(jù)的并發(fā)寫入需要沖突解決機(jī)制決定以哪次寫入為準(zhǔn)。

1.3 無主復(fù)制

Dynamo風(fēng)格的數(shù)據(jù)庫就是無主復(fù)制，寫入的請求不會經(jīng)過特定的主節(jié)點復(fù)制到從節(jié)點，所有的節(jié)點都可以承擔(dān)讀取和寫入，容忍寫入時的不一致，在讀取時解決不一致。

假設(shè)一個數(shù)據(jù)庫中有三個節(jié)點，存儲的鍵值對X=1。在下面的示意圖中，三個節(jié)點都收到了同一個寫入的請求，C節(jié)點寫入失敗。

此時，三個節(jié)點內(nèi)鍵值X對應(yīng)的value是不一樣的，收到讀請求后自然會返回不同的值。

從上帝視角看，此時此刻，鍵值X對應(yīng)的value應(yīng)該是100，但對于一個運(yùn)行的系統(tǒng)，需要一個機(jī)制解決下面兩個問題，這個機(jī)制稱為仲裁。

對于讀取到的不同的值，哪個值為正確的值？

讀取多少個節(jié)點才能保證讀取到正確的值？顯然，如果只從C節(jié)點上讀取，那不管問題1的答案是什么，都得不到正確的值。

1.4 嚴(yán)格仲裁

使用時間戳或者版本號判定哪個值為正確的值：時間戳最大的或者版本號最大的，代表數(shù)據(jù)是最新的，最新的數(shù)據(jù)就是正確的數(shù)據(jù)。

R+W>N，N：?總的節(jié)點個數(shù)，W: 判斷寫入成功所需的節(jié)點個數(shù)，R：讀取時至少需要讀取成功的節(jié)點個數(shù)，W+R>N時總會讀到最新的數(shù)據(jù)。如下圖所示，藍(lán)色的節(jié)點表示寫入成功的節(jié)點，即W=3，當(dāng)R=3時，讀取成功的節(jié)點和寫入成功的節(jié)點一定會有交集。W越小，寫入的可用性更高，寫性能越好，R越小，讀的可用性更高，讀性能越好。

假設(shè)單個節(jié)點的可用性P=99.9%，以此來計算無主復(fù)制時的讀和寫的可用性，不同的R、W的可用性情況如下表所示，以N=3舉例，R=1時讀的可用性等于。

根據(jù)表中所示，在N=3，R=W=2時，讀和寫的可用性都比單個節(jié)點的讀寫可用性高，這也是Dynamo風(fēng)格數(shù)據(jù)庫使用的推薦配置。

1.5  寬松仲裁

在嚴(yán)格仲裁時，如果達(dá)不到嚴(yán)格仲裁的R+W>N時會返回調(diào)用端錯誤碼，假設(shè)N=5，W=R=3，讀取的時候讀了5個節(jié)點，但是三個節(jié)點讀失敗了，只有兩個節(jié)點讀成功了，此時如果以兩個節(jié)點的結(jié)果比較版本號或者時間戳，得到的數(shù)據(jù)有可能是錯誤的，也有可能是正確的。

如果我們的系統(tǒng)能夠忍受返回不新鮮的數(shù)據(jù)的可能性，那么使用寬松仲裁是提高系統(tǒng)可用性的一種辦法。我們來定義寬松仲裁：在系統(tǒng)達(dá)不到嚴(yán)格仲裁的條件時，利用僅有的條件返回調(diào)用端結(jié)果，注意，必須是先嘗試滿足嚴(yán)格仲裁，達(dá)不到嚴(yán)格仲裁時使用僅有的條件返回調(diào)用端結(jié)果，比如，N=5，R=W=3，在讀取數(shù)據(jù)時先讀取三個節(jié)點，兩個節(jié)點讀取失敗，為了滿足嚴(yán)格仲裁，再讀取剩余的兩個節(jié)點，但是一個成功，一個失敗，此時一共有兩個節(jié)點讀取成功，使用兩個節(jié)點的數(shù)據(jù)寬松仲裁，得出結(jié)果，而不是一開始就只讀兩個節(jié)點，這兩種方式讀取到錯誤數(shù)據(jù)的概率差別很大。

使用寬松仲裁時得到正確數(shù)據(jù)的概率如下表所示，假設(shè)單個節(jié)點的可用性P=99.9%，N=1，R=W=1時，讀和寫的可用性是，N=3，R=1，W=1時讀到錯誤數(shù)據(jù)的概率

。

?

無主復(fù)制的數(shù)據(jù)庫在寫入的時候容忍了部分節(jié)點的不一致，但是我們希望每個節(jié)點上的數(shù)據(jù)盡可能的完整，這就需要節(jié)點版本補(bǔ)齊。

1.6 節(jié)點間的版本補(bǔ)齊

1）寫修復(fù)，節(jié)點寫失敗在寫入的時候已經(jīng)是被感知到的，可以通過消息隊列等方式異步的在寫入失敗之后補(bǔ)償修復(fù)。

2）讀修復(fù)，在讀取數(shù)據(jù)的時候，已經(jīng)知道了節(jié)點間的數(shù)據(jù)不一致，此時可以根據(jù)仲裁得出的數(shù)據(jù)來修復(fù)版本滯后的節(jié)點上的數(shù)據(jù)。

3）巡檢，主動的掃描介質(zhì)間的數(shù)據(jù)，根據(jù)仲裁的結(jié)果修復(fù)數(shù)據(jù)。

二、由無主復(fù)制向多介質(zhì)存儲擴(kuò)展

前面介紹無主復(fù)制數(shù)據(jù)庫的時候一直在使用“節(jié)點”這個概念，這里對節(jié)點做一個定義：運(yùn)行同一套代碼的、擁有完全相同功能的進(jìn)程，比如Redis的master和slave節(jié)點。

在攜程酒店的預(yù)定訂單和價態(tài)信息存儲中，選擇合適的存儲介質(zhì)一直是一個核心的技術(shù)問題，我們希望數(shù)據(jù)不僅在介質(zhì)內(nèi)有互備（Redis的master和slave），還能有介質(zhì)間的互備（比如Redis和Trocks），因為同一個存儲介質(zhì)總是擁有相似的運(yùn)作機(jī)制，同時出問題的概率更高。

在多介質(zhì)數(shù)據(jù)存儲中，我們對前面理論部分用存儲介質(zhì)代替“節(jié)點”后的語義就是：數(shù)據(jù)同時寫到多個存儲介質(zhì)中，容忍部分存儲介質(zhì)的寫入失敗，在讀出數(shù)據(jù)時，仲裁決定整個系統(tǒng)中數(shù)據(jù)最終的值，整個系統(tǒng)能夠容忍單一存儲介質(zhì)級別不可用的情況，系統(tǒng)的穩(wěn)定性從容忍單個節(jié)點故障提升到了存儲介質(zhì)級別。

三、Hare：多存儲介質(zhì)的預(yù)定庫

Hare的名稱來源于成語“狡兔三窟”，數(shù)據(jù)存儲在多個介質(zhì)中，以保證數(shù)據(jù)的安全。Hare承擔(dān)攜程酒店預(yù)定庫的功能，主要用于存儲在用戶下單的各個環(huán)節(jié)（創(chuàng)單、支付、提交）中產(chǎn)生的訂單相關(guān)數(shù)據(jù)。在訂單完成提交后從Hare同步到訂單庫，進(jìn)入訂單處理環(huán)節(jié)。Hare的架構(gòu)圖如下圖所示，應(yīng)用層代碼管理底層的Redis、Trocks、Hbase的寫入和讀取，以及仲裁返回給調(diào)用端的數(shù)據(jù)。介質(zhì)間版本補(bǔ)齊使用寫修復(fù)。

Hare內(nèi)部采用寬松仲裁，N=3，W=1，R=1，使用版本號判斷最新版本。需要特別指出的是，W=1并非任何一個介質(zhì)寫入成功就算成功，Hare內(nèi)部“期望”的寫入成功個數(shù)為2，但是當(dāng)所有介質(zhì)寫入完成后，寫入成功的介質(zhì)個數(shù)依然沒有達(dá)到2，就會優(yōu)先考慮可用性，寫入成功的個數(shù)等于1也算寫入成功。

當(dāng)W=1時，嚴(yán)格仲裁的R應(yīng)該等于3，Hare內(nèi)部會讀所有的3個介質(zhì)并比較版本號，返回版本號最大的數(shù)據(jù)。但如果讀完所有數(shù)據(jù)，依然只有一個介質(zhì)讀成功，還是會以成功的這個介質(zhì)的數(shù)據(jù)返回給調(diào)用方。所以寬松仲裁的含義是，在使用嚴(yán)格仲裁但達(dá)不到嚴(yán)格仲裁的條件時，優(yōu)先保證可用性。寫入和讀取時的流程圖如下所示。

四、InfoKeeper：高可用高性能的動態(tài)信息存儲

InfoKeeper是對Hare架構(gòu)在酒店價態(tài)量存儲場景下的改進(jìn)，Hare作為下單場景用，對性能要求較低，但對數(shù)據(jù)的可靠性要求更高。但在酒店的價態(tài)量存儲中，對性能要求更高，數(shù)據(jù)可靠性要求較下單場景低，所以InfoKeeper中存儲介質(zhì)的個數(shù)較Hare更少，選擇了Redis和Trocks兩個存儲介質(zhì)，仲裁的N=2，W=1，R=1。

我們將InfoKeeper中參與仲裁的介質(zhì)稱為主介質(zhì)（圖中綠色），將只會寫入但是不參與仲裁的介質(zhì)稱為從介質(zhì)（圖中淡藍(lán)色），從介質(zhì)的寫入是否成功都不會影響對客戶端的響應(yīng)。介質(zhì)間的版本補(bǔ)齊使用寫修復(fù)。在酒店價態(tài)量存儲中架構(gòu)圖如下。

InfoKeeper寫入的流程圖如下。

InfoKeeper現(xiàn)在支持的存儲介質(zhì)有redis、trocks、mysql、es、hbase、oceanbase、Tikv、qmq、kafka、soa。qmq通常作為推送增量的方式，kafka用于推送離線數(shù)據(jù)，soa用于通過soa接口調(diào)用的方式更新服務(wù)端的緩存。因為接口較消息隊列延時更低，所以soa面向?qū)彺嫘迈r程度要求很高的使用方，比如酒店查詢服務(wù)，在InfoKeeper中將消息隊列和soa接口當(dāng)作一種存儲介質(zhì)看待，只是這種存儲介質(zhì)不能提供讀功能。

InfoKeeper中存儲的數(shù)據(jù)目前在百億級別，InfoKeeper完成了這些數(shù)據(jù)的存儲、承擔(dān)了40萬QPS的讀能力，以及數(shù)據(jù)從存儲方到各個使用方的高效流轉(zhuǎn)。得益于強(qiáng)大的讀能力（強(qiáng)大的讀寫能力主要是因為選擇了性能更好的KV型存儲介質(zhì)為主介質(zhì)，可以根據(jù)數(shù)據(jù)讀取方對性能和數(shù)據(jù)新鮮度的要求，選擇對應(yīng)的存儲介質(zhì)和仲裁的方式），一些散落在各個使用方的緩存廢棄，改為直接從InfoKeeper讀。根據(jù)統(tǒng)計，InfoKeeper節(jié)省了20%的硬件成本，數(shù)據(jù)的流轉(zhuǎn)效率較以往使用關(guān)系型數(shù)據(jù)庫存儲，使用方從關(guān)系型數(shù)據(jù)庫拉取的方式大大提高，還消除了關(guān)系型數(shù)據(jù)庫的單點性能限制。

建立緩存的一種新模式

在InfoKeeper前面的架構(gòu)圖中，如果將主介質(zhì)改為關(guān)系型數(shù)據(jù)庫，從介質(zhì)改為redis，就實現(xiàn)了為DB建緩存的目的，只是把從DB拉數(shù)據(jù)改為了主動往redis寫數(shù)據(jù)，減輕了DB的壓力。如果需要建多份緩存，只需要多掛幾個從介質(zhì)就可以實現(xiàn)。目前酒店的房型通用緩存就是使用這種方式。

五、設(shè)計目標(biāo)的驗證

怎么確認(rèn)多介質(zhì)存儲系統(tǒng)符合設(shè)計預(yù)期，能夠容忍存儲介質(zhì)級別的故障？Hare上線6個季度，InfoKeeper上線4個季度以來，我們在每個季度都會對Hare和InfoKeeper做單個介質(zhì)注入故障的演練，在演練期間應(yīng)用和上下游正常，在注入故障恢復(fù)之后，寫修復(fù)最終追趕成功，可以確認(rèn)系統(tǒng)符合設(shè)計預(yù)期。

六、展望

現(xiàn)在InfoKeeper和Hare還在應(yīng)用代碼層面，沒有形成通用的組件，新的業(yè)務(wù)的加入需要在現(xiàn)有代碼的基礎(chǔ)上增加業(yè)務(wù)邏輯，開發(fā)者對底層的多介質(zhì)存儲的代碼是有感的，也可能需要修改多介質(zhì)存儲層的代碼以更好的貼合新的業(yè)務(wù)。

我們計劃對Infokeeper和Hare的代碼進(jìn)行合并，形成一個通用的組件，讓新的使用方能對多介質(zhì)存儲層無感，做到開箱即用，降低多介質(zhì)存儲的使用門檻，使得使用方能更專注于業(yè)務(wù)代碼。