作者簡(jiǎn)介

Nick，攜程軟件技術(shù)專(zhuān)家，關(guān)注分布式數(shù)據(jù)存儲(chǔ)以及操作系統(tǒng)內(nèi)核。

前言

在《攜程 Redis 跨 IDC 多向同步實(shí)踐》一文曾和大家分享過(guò)攜程在 Redis 雙向同步方面的心得，簡(jiǎn)單介紹了實(shí)現(xiàn)一個(gè) Redis 雙向同步系統(tǒng)中可能面臨的問(wèn)題，以及其中一種問(wèn)題（分布式一致性）的部分處理方案 -- CRDT（Conflict-free ReplicatedData Types）。本文將進(jìn)一步闡述在具體設(shè)計(jì)和落地過(guò)程中的一些細(xì)節(jié)， 希望對(duì)大家能夠有所幫助。包括：

• Cycle Break -- 如何打破盜夢(mèng)空間的無(wú)限循環(huán)?

• Last Write Wins & Vector Clock -- 沖突的解決既簡(jiǎn)單又復(fù)雜?

• Tomstone -- 憶往昔才能看今朝?

• GC -- CRDT 取經(jīng)之路的通天河?

• Expire -- 一致 or 不一致， 這是個(gè)問(wèn)題

相信通過(guò)對(duì)這些問(wèn)題的描述和解答， 大家對(duì)于如何實(shí)現(xiàn)一個(gè)雙向同步的 Redis 會(huì)有一幅清晰的構(gòu)圖。

一、Cycle Break -- 如何打破盜夢(mèng)空間的無(wú)限循環(huán)

1.1 復(fù)制回環(huán)

以下圖為例，假設(shè) A <-> B <-> C 三個(gè) Redis 建立起了雙向復(fù)制關(guān)系。現(xiàn)在客戶端先向其中一個(gè) Redis（假設(shè) A）發(fā)送了命令，SET KEY VAL（將 key 的值，設(shè)置或更新為 val），那么大概率會(huì)發(fā)生以下這樣的步驟：?

1）A 將 SET KEY VAL 同步至 B 和 C?

2）B 和 C 接收到操作后，又再次同步給其他兩個(gè) Redis?

3）如此循環(huán)往復(fù) ...

綜上所述，復(fù)制回環(huán)所帶來(lái)的問(wèn)題結(jié)合普通的數(shù)據(jù)結(jié)構(gòu)，會(huì)帶來(lái)以下問(wèn)題：

• 網(wǎng)絡(luò)風(fēng)暴?

• 數(shù)據(jù)不一致

1.2 如何解決

如何解決這個(gè)問(wèn)題呢，無(wú)非以下幾種方式：

1）在數(shù)據(jù)上做處理，使數(shù)據(jù)攜帶一定的信息，服務(wù)端通過(guò)對(duì)數(shù)據(jù)所攜帶信息的甄別，過(guò)濾掉冗余消息。

2）在內(nèi)容分發(fā)上做處理，服務(wù)端能夠識(shí)別不同的鏈接類(lèi)型，從而做到有的放矢，在同步數(shù)據(jù)之初便加以控制；

針對(duì) Redis 這種場(chǎng)景，我們選擇了第二種處理方案，既在復(fù)制數(shù)據(jù)的時(shí)候，根據(jù)數(shù)據(jù)來(lái)源的類(lèi)型，來(lái)決策是否同步給其他 Redis。

為了方便大家理解， 這里簡(jiǎn)單介紹一下 Redis 的內(nèi)部實(shí)現(xiàn)：Redis 對(duì)于每一個(gè)TCP鏈接，都會(huì)抽象成為一個(gè)叫 client 的對(duì)象，見(jiàn)下圖。而其中有一個(gè) flag 表示了這個(gè)鏈接（client）對(duì)應(yīng)的類(lèi)型，這就很好地契合了上文中列舉出的第二條選項(xiàng)。

所以，我們最終的處理方案是：Redis對(duì)數(shù)據(jù)源進(jìn)行甄別，只有屬于來(lái)自客戶端的操作，才會(huì)被選擇性地同步給 Peer Master。然而，對(duì)于傳統(tǒng)的 Master-Slave 架構(gòu)來(lái)講，還是會(huì)把所有對(duì)數(shù)據(jù)庫(kù)有變更的操作，都同步給 Slave。

二、Last Write Wins & Vector Clock -- 沖突的解決既簡(jiǎn)單又復(fù)雜

這里以一對(duì)簡(jiǎn)單的 K/V 為例，介紹下是如何處理沖突的。

2.1 沖突是如何產(chǎn)生的

下面一幅圖很好地詮釋了，為什么會(huì)有沖突以及沖突的后果。

假設(shè)我們?cè)谕粫r(shí)刻，分別在兩個(gè)互相同步的 Redis 上更新了一個(gè) Key，左邊的試圖將 Key 設(shè)置為 CAT，而后邊的客戶端試圖將 Key 設(shè)置為 DOG。

那么總共會(huì)有以下 4 種結(jié)果，前兩種雖然不盡如人意，但至少保證了數(shù)據(jù)的一致性。而后面兩種則是大家不希望看到的，因?yàn)閿?shù)據(jù)不一致對(duì)業(yè)務(wù)造成不可忽略的風(fēng)險(xiǎn)。

2.2 LWW -- Last Write Wins

其實(shí)解決這個(gè)問(wèn)題也很簡(jiǎn)單，就是“最后寫(xiě)入為準(zhǔn)”的原則。以下圖為例，假設(shè)兩個(gè) Redis 分別收到了對(duì)于同一個(gè) Key 的設(shè)值需求，那么我們就可以簡(jiǎn)單地根據(jù)這個(gè)原則來(lái)判定，最終的結(jié)果是最后一次的寫(xiě)入為準(zhǔn)。

看到這里，大家也許會(huì)發(fā)現(xiàn)，原來(lái)沖突處理如此簡(jiǎn)單，那我也可以大展身手了。當(dāng)然，大部分系統(tǒng)的實(shí)現(xiàn)，做到這一層，已經(jīng)解決了分布式一致性的問(wèn)題。但是，是不是這樣就皆大歡喜了呢？

答案當(dāng)然是否定的，繼續(xù)往下看你就會(huì)發(fā)現(xiàn)，這小小的 K/V 一致性，只是分布式系統(tǒng)中的冰山一角。冰山的下面有著千奇百怪的洪水猛獸，一個(gè)沒(méi)處理到，都會(huì)帶來(lái)無(wú)可估量的業(yè)務(wù)損失。

2.3 時(shí)鐘 -- 分布式系統(tǒng)永遠(yuǎn)的痛

相信部分同學(xué)在上學(xué)階段或是工作以后，拜讀過(guò)分布式系統(tǒng)的經(jīng)典書(shū)目 --Distributed System Concept and Design （如下圖）。這本書(shū)在開(kāi)篇就對(duì)分布式系統(tǒng)有了一個(gè)經(jīng)典的定義：

• Concurrency?

• No Global Clock?

• Independent Failures

下面這個(gè)問(wèn)題就是由時(shí)鐘問(wèn)題引起的。大家知道，不同的互聯(lián)網(wǎng)組件之間是靠著 NPT-Server 這一工具來(lái)達(dá)到時(shí)間的一致性的，但是不同的網(wǎng)絡(luò)區(qū)域之間的 NTP-Server 卻并不一定是同步的。即使同步，時(shí)鐘的準(zhǔn)確性往往取決于網(wǎng)絡(luò)的穩(wěn)定性（這一點(diǎn)與網(wǎng)絡(luò)延遲無(wú)關(guān)，也就是說(shuō)即時(shí)延遲是中美之間大概 200~300ms，如果是穩(wěn)定的延遲，那么 NTP-Server 的同步也基本穩(wěn)定）。

如下圖所示，在下面的 Redis（我們稱之為 Redis-B）的網(wǎng)絡(luò)域的物理時(shí)鐘（Wall Clock），比上面的 Redis（我們稱之為 Redis-A）的網(wǎng)絡(luò)域的時(shí)鐘慢，在 Redis-A 上一個(gè)很早的操作發(fā)生之后，Redis-B 方才收到關(guān)于同樣Key的操作。從邏輯上講我們更希望 Redis-B 的操作作為最終結(jié)果，然而由于時(shí)鐘的快慢，如果使用 Last Write Wins 的策略，反而是早些時(shí)候在 Redis-A 上面的操作占了上風(fēng)，最終值為 VAL1。

2.4 Vector Clock

那么時(shí)鐘快慢帶來(lái)的問(wèn)題，是否無(wú)可避免？其實(shí)未必。

以上面的問(wèn)題為例，是不需要沖突處理的，只是單從 Wall Clock，我們無(wú)法判定邏輯操作的時(shí)間。所以引入了一個(gè)叫 Vector Clock 的邏輯時(shí)鐘，來(lái)表示一個(gè)操作的發(fā)生時(shí)刻。

以下圖為例，全局有兩個(gè)點(diǎn)，我們通過(guò)兩個(gè)向量來(lái)表示發(fā)生過(guò)的邏輯操作。

這里不展開(kāi)講了，具體 Vector Clock 是如何定義的，有專(zhuān)門(mén)的論文論述。而 AWS 聞名遐邇的 DynamoDB，更是通過(guò)對(duì) Vector Clock 的理論改進(jìn)，找到了更加適合自己的一種叫 Version Clock 的理論依據(jù)，感興趣的同學(xué)可以 Google 。

三、Tomstone -- 憶往昔才能看今朝

3.1 Delete

前面講了數(shù)據(jù)回環(huán)復(fù)制的處理、數(shù)據(jù)一致性的處理，這樣一個(gè)簡(jiǎn)單的分布式K/V 數(shù)據(jù)庫(kù)就誕生了，但是刪除操作依然會(huì)成為系統(tǒng)的“阿喀琉斯之踵”。

請(qǐng)看下圖，假設(shè)我們已經(jīng)存在了一個(gè)Key，在同一時(shí)刻 Redis-A（依照上文慣例，我們稱上面的 Redis 為 Redis-A）收到了更新請(qǐng)求，設(shè)置 Key 為 VAL，而 Redis-B 卻收到了 Delete 的命令，兩個(gè) Redis 互相同步之后，發(fā)現(xiàn)數(shù)據(jù)不一致了。

問(wèn)題的根源在哪里呢？在于 Delete 操作，將 Redis-B 上的值刪除了，當(dāng) SET KEY=VAL 的更新操作到達(dá)之時(shí)，便沒(méi)有了可以比較的對(duì)象。

3.2 Tomstone

這個(gè)問(wèn)題該如何處理？既然是沒(méi)有對(duì)象可比，我們創(chuàng)造一個(gè)對(duì)象不就可以了嗎？于是誕生了 Tomstone —— 被刪除對(duì)象的棲身地。對(duì)象的刪除，我們只做邏輯刪除，并不會(huì)將對(duì)象真正地從內(nèi)存中抹去，而是放置在一個(gè)叫做 Tomstone 的地方，讓其他后續(xù)的命令，能夠和之前的命令有一個(gè)對(duì)比。數(shù)據(jù)的存留與否也就有了判定的依據(jù)。

四、GC -- CRDT 取經(jīng)之路的通天河

GC -- Garbage Collection，很多語(yǔ)言都有這個(gè)特性，像 Java，Go。無(wú)獨(dú)有偶，我們這里所說(shuō)的 GC，原則和這些語(yǔ)言無(wú)異，都是為了處理一類(lèi)不再使用，但是又占有資源（通常是內(nèi)存資源）的一些數(shù)據(jù)的回收。

4.1 GC 的痛點(diǎn)

上一小節(jié)，我們簡(jiǎn)單介紹了 Tomstone 的概念，GC 也是由于 Tomstone 的引入而帶來(lái)的在實(shí)踐中不得不面對(duì)的問(wèn)題，如下圖所示：

隨著時(shí)間的推移，我們 Tomstone 中的對(duì)象會(huì)越來(lái)越多，直到吃掉你的全部?jī)?nèi)存，然后程序崩潰。

4.2 GC的解決方案 -- VectorClock 的靈活妙用

如何 GC 的問(wèn)題，其實(shí)不如說(shuō)是什么對(duì)象可以 GC，這里我們也舉兩個(gè)經(jīng)典的GC算法：

• 尋根法（GC Root）?

• 引用計(jì)數(shù)法（Reference Count）

兩種算法各有優(yōu)劣，Reference Count 可以方便地及時(shí)發(fā)現(xiàn)需要 GC 的對(duì)象，卻無(wú)法解決循環(huán)引用的問(wèn)題；GC Root 可以解決循環(huán)引用的問(wèn)題，卻給 GC 掃描帶來(lái)了一定負(fù)擔(dān)。

我們的系統(tǒng)，采用了類(lèi)似 RC 的算法來(lái)實(shí)現(xiàn) GC：如果發(fā)現(xiàn)其他所有同步的 Redis Peer Master 都已經(jīng)知道了某個(gè)對(duì)象被刪除的事實(shí)，那么這個(gè)對(duì)象，就可以被永久刪除（也就是 GC）了。

怎么發(fā)現(xiàn)對(duì)方知道某個(gè)對(duì)象被刪除了呢，前面有提到每個(gè) Redis 都有自己的 Vector Clock，而 Vector Clock是和操作綁定的，只需 Redis 之間互通有無(wú)，互相了解到對(duì)方的 Vector Clock，那么如何發(fā)現(xiàn)某個(gè)對(duì)象是否過(guò)期的問(wèn)題也迎刃而解。

當(dāng)然， 整個(gè)過(guò)程也并非上面說(shuō)起來(lái)那么簡(jiǎn)單。

比如，GC 的策略選擇，是主動(dòng) GC 還是被動(dòng) GC，抑或是兩者的結(jié)合？

單次 GC 時(shí)間長(zhǎng)短的控制？如果 GC 時(shí)間過(guò)長(zhǎng)，必然會(huì)影響 Redis 的響應(yīng)速度；過(guò)短的 GC ，則會(huì)導(dǎo)致對(duì)象一直堆積在 Tombstone 中，內(nèi)存得不到釋放。

五、Expire -- 一致 or 不一致，這是個(gè)問(wèn)題

作為緩存來(lái)說(shuō)，比較常見(jiàn)的是配置一定的緩存過(guò)期策略。一方面，可以保障數(shù)據(jù)的新鮮程度，另一方面無(wú)限制地將數(shù)據(jù)存入緩存，不僅不利于緩存的查詢速度，對(duì)于資源來(lái)說(shuō)也是不小的開(kāi)銷(xiāo)。所以，Redis 中引入了 Expire 的過(guò)期機(jī)制，給每一個(gè)緩存的 Key 設(shè)定一個(gè)過(guò)期時(shí)間是一個(gè)良好的習(xí)慣。

但是，在加入雙向同步的架構(gòu)之后，expire 似乎成為了一個(gè)問(wèn)題，要不要將過(guò)期時(shí)間保持一致？如果保持一致的話，應(yīng)該采取怎樣的數(shù)據(jù)結(jié)構(gòu)？

首先，我們應(yīng)該確認(rèn)一個(gè)問(wèn)題，緩存的過(guò)期時(shí)間不一致，會(huì)不會(huì)導(dǎo)致數(shù)據(jù)一致性的問(wèn)題？結(jié)合 Redis 的實(shí)現(xiàn)來(lái)說(shuō)，緩存過(guò)期時(shí)間不一致，不會(huì)帶來(lái)數(shù)據(jù)一致性的問(wèn)題（這個(gè)數(shù)據(jù)特指除過(guò)期時(shí)間之外的用戶數(shù)據(jù)）。要說(shuō)明白這個(gè)道理，我們先來(lái)看一下 Redis 是如何過(guò)期數(shù)據(jù)的。

Redis 的過(guò)期策略簡(jiǎn)單來(lái)說(shuō)分為兩種，一種是主動(dòng)過(guò)期，以一個(gè)固定的頻率輪詢存儲(chǔ)過(guò)期時(shí)間的字典，發(fā)現(xiàn)有 key 過(guò)期就執(zhí)行刪除操作；另一種是被動(dòng)過(guò)期，在用戶對(duì) key 操作時(shí)，同時(shí)判定一下 key 的過(guò)期時(shí)間，是否需要過(guò)期掉。

兩種過(guò)期策略，都由 master 發(fā)起，slave 本身通過(guò)被動(dòng)接受 master 同步過(guò)來(lái)的 delete 操作，來(lái)達(dá)到數(shù)據(jù)一致性（這里我們忽略 slave-read-only 為 false，且有客戶端過(guò)期 key 寫(xiě)入的場(chǎng)景）。其實(shí)這個(gè)狀態(tài)下，是存在已經(jīng)過(guò)期，但是在內(nèi)存中沒(méi)有被刪除的 key，這個(gè)時(shí)候訪問(wèn) Redis，外在的表象為 key 不存在。那么對(duì)于客戶端來(lái)說(shuō)，數(shù)據(jù)是一致的，過(guò)期的 key 確實(shí)拿不到了（雖然 Redis 內(nèi)存中可能還有）。

對(duì)于雙向同步來(lái)說(shuō)，如果并發(fā)地在兩端的 Redis 執(zhí)行 expire 操作，就會(huì)發(fā)生沖突，是否處理沖突，如何處理沖突，是我們這里想要討論的點(diǎn)。

在我們實(shí)際實(shí)現(xiàn)的過(guò)程中，曾經(jīng)有一個(gè)版本確實(shí)實(shí)現(xiàn)了 expire 多個(gè) Redis 之間的一致性，但是這樣做，引入了更多的數(shù)據(jù)結(jié)構(gòu)來(lái)解決沖突處理問(wèn)題。對(duì)比普通版本的 Redis，同樣大小的 expire 數(shù)據(jù)量，內(nèi)存要多出一倍。對(duì)于攜程這樣 Redis 重度依賴的用戶來(lái)說(shuō)，內(nèi)存的增加無(wú)疑伴隨著大量費(fèi)用的上升。所以最終的實(shí)現(xiàn)上，我們并沒(méi)有采取 expire 時(shí)間一致性的策略。

那么是不是 expire 時(shí)間不一致，數(shù)據(jù)就有問(wèn)題了呢？當(dāng)然不是。舉例來(lái)說(shuō)，有 A/B 兩個(gè) Redis 建立了雙向同步。A/B 在同一時(shí)間點(diǎn)，分別對(duì)同樣的 key 設(shè)置了不同的過(guò)期時(shí)間（如下圖）。

一邊設(shè)置過(guò)期時(shí)間為 30s，另外一邊設(shè)置為 60s，互相同步之后，時(shí)間進(jìn)行了對(duì)調(diào)。30s 以后 Redis-A 上面的 key 過(guò)期，觸發(fā)了 del 操作，同時(shí)把這個(gè)操作傳播給 Redis-B，因?yàn)?delete 機(jī)制的存在，兩邊的數(shù)據(jù)是一致的。

緩存過(guò)期（Expire）這一小節(jié)，先分享到這里。實(shí)現(xiàn)的過(guò)程中，我們還對(duì)過(guò)期策略進(jìn)行了優(yōu)化，防止并發(fā)地過(guò)期刪除操作，造成不必要的網(wǎng)絡(luò)開(kāi)銷(xiāo)。

六、總結(jié)

本文試著從一個(gè)個(gè)具體的小例子出發(fā)，帶大家 review 一個(gè)分布式的 K/V 系統(tǒng)是如何搭建起來(lái)的。后續(xù)還將帶來(lái)內(nèi)存優(yōu)化篇 -- ZGC 的 colored pointer 在攜程 Redis 的靈活運(yùn)用。

總結(jié)

以上是生活随笔為你收集整理的干货 | 五大实例详解，携程 Redis 跨机房双向同步实践的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。