五大實例詳解，攜程 Redis 跨機房雙向同步實踐

前言

在《攜程 Redis 跨 IDC 多向同步實踐》一文曾和大家分享過攜程在 Redis 雙向同步方面的心得，簡單介紹了實現一個 Redis 雙向同步系統中可能面臨的問題，以及其中一種問題（分佈式一致性）的部分處理方案 — CRDT（Conflict-free ReplicatedData Types）。本文將進一步闡述在具體設計和落地過程中的一些細節，希望對大家能夠有所幫助。包括：

Cycle Break — 如何打破盜夢空間的無限循環
Last Write Wins & Vector Clock — 衝突的解決既簡單又複雜
Tomstone — 憶往昔才能看今朝
GC — CRDT 取經之路的通天河
Expire — 一致 or 不一致，這是個問題

相信通過對這些問題的描述和解答，大家對於如何實現一個雙向同步的 Redis 會有一幅清晰的構圖。

一、Cycle Break — 如何打破盜夢空間的無限循環

1.1 複製迴環

以下圖爲例，假設 A <-> B <-> C 三個 Redis 建立起了雙向複製關係。現在客戶端先向其中一個 Redis（假設 A）發送了命令，SET KEY VAL（將 key 的值，設置或更新爲 val），那麼大概率會發生以下這樣的步驟：

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

2）B 和 C 接收到操作後，又再次同步給其他兩個 Redis

3）如此循環往復 …

綜上所述，複製迴環所帶來的問題結合普通的數據結構，會帶來以下問題：

網絡風暴
數據不一致

1.2 如何解決

如何解決這個問題呢，無非以下幾種方式：

1）在數據上做處理，使數據攜帶一定的信息，服務端通過對數據所攜帶信息的甄別，過濾掉冗餘消息。

2）在內容分發上做處理，服務端能夠識別不同的鏈接類型，從而做到有的放矢，在同步數據之初便加以控制；

針對 Redis 這種場景，我們選擇了第二種處理方案，既在複製數據的時候，根據數據來源的類型，來決策是否同步給其他 Redis。

爲了方便大家理解，這裏簡單介紹一下 Redis 的內部實現：Redis 對於每一個TCP鏈接，都會抽象成爲一個叫 client 的對象，見下圖。而其中有一個 flag 表示了這個鏈接（client）對應的類型，這就很好地契合了上文中列舉出的第二條選項。

所以，我們最終的處理方案是：Redis對數據源進行甄別，只有屬於來自客戶端的操作，纔會被選擇性地同步給 Peer Master。然而，對於傳統的 Master-Slave 架構來講，還是會把所有對數據庫有變更的操作，都同步給 Slave。

二、Last Write Wins & Vector Clock — 衝突的解決既簡單又複雜

這裏以一對簡單的 K/V 爲例，介紹下是如何處理衝突的。

2.1 衝突是如何產生的

下面一幅圖很好地詮釋了，爲什麼會有衝突以及衝突的後果。

假設我們在同一時刻，分別在兩個互相同步的 Redis 上更新了一個 Key，左邊的試圖將 Key 設置爲 CAT，而後邊的客戶端試圖將 Key 設置爲 DOG。

那麼總共會有以下 4 種結果，前兩種雖然不盡如人意，但至少保證了數據的一致性。而後面兩種則是大家不希望看到的，因爲數據不一致對業務造成不可忽略的風險。

2.2 LWW — Last Write Wins

其實解決這個問題也很簡單，就是“最後寫入爲準”的原則。以下圖爲例，假設兩個 Redis 分別收到了對於同一個 Key 的設值需求，那麼我們就可以簡單地根據這個原則來判定，最終的結果是最後一次的寫入爲準。

看到這裏，大家也許會發現，原來衝突處理如此簡單，那我也可以大展身手了。當然，大部分系統的實現，做到這一層，已經解決了分佈式一致性的問題。但是，是不是這樣就皆大歡喜了呢？

答案當然是否定的，繼續往下看你就會發現，這小小的 K/V 一致性，只是分佈式系統中的冰山一角。冰山的下面有着千奇百怪的洪水猛獸，一個沒處理到，都會帶來無可估量的業務損失。

2.3 時鐘 — 分佈式系統永遠的痛

相信部分同學在上學階段或是工作以後，拜讀過分佈式系統的經典書目 –Distributed System Concept and Design （如下圖）。這本書在開篇就對分佈式系統有了一個經典的定義：

Concurrency
No Global Clock
Independent Failures

下面這個問題就是由時鐘問題引起的。大家知道，不同的互聯網組件之間是靠着 NPT-Server 這一工具來達到時間的一致性的，但是不同的網絡區域之間的 NTP-Server 卻並不一定是同步的。即使同步，時鐘的準確性往往取決於網絡的穩定性（這一點與網絡延遲無關，也就是說即時延遲是中美之間大概 200~300ms，如果是穩定的延遲，那麼 NTP-Server 的同步也基本穩定）。

如下圖所示，在下面的 Redis（我們稱之爲 Redis-B）的網絡域的物理時鐘（Wall Clock），比上面的 Redis（我們稱之爲 Redis-A）的網絡域的時鐘慢，在 Redis-A 上一個很早的操作發生之後，Redis-B 方纔收到關於同樣Key的操作。從邏輯上講我們更希望 Redis-B 的操作作爲最終結果，然而由於時鐘的快慢，如果使用 Last Write Wins 的策略，反而是早些時候在 Redis-A 上面的操作佔了上風，最終值爲 VAL1。

2.4 Vector Clock

那麼時鐘快慢帶來的問題，是否無可避免？其實未必。

以上面的問題爲例，是不需要衝突處理的，只是單從 Wall Clock，我們無法判定邏輯操作的時間。所以引入了一個叫 Vector Clock 的邏輯時鐘，來表示一個操作的發生時刻。

以下圖爲例，全局有兩個點，我們通過兩個向量來表示發生過的邏輯操作。

這裏不展開講了，具體 Vector Clock 是如何定義的，有專門的論文論述。而 AWS 聞名遐邇的 DynamoDB，更是通過對 Vector Clock 的理論改進，找到了更加適合自己的一種叫 Version Clock 的理論依據，感興趣的同學可以 Google 。

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

3.1 Delete

前面講了數據迴環複製的處理、數據一致性的處理，這樣一個簡單的分佈式K/V 數據庫就誕生了，但是刪除操作依然會成爲系統的“阿喀琉斯之踵”。

請看下圖，假設我們已經存在了一個Key，在同一時刻 Redis-A（依照上文慣例，我們稱上面的 Redis 爲 Redis-A）收到了更新請求，設置 Key 爲 VAL，而 Redis-B 卻收到了 Delete 的命令，兩個 Redis 互相同步之後，發現數據不一致了。

問題的根源在哪裏呢？在於 Delete 操作，將 Redis-B 上的值刪除了，當 SET KEY=VAL 的更新操作到達之時，便沒有了可以比較的對象。

3.2 Tomstone

這個問題該如何處理？既然是沒有對象可比，我們創造一個對象不就可以了嗎？於是誕生了 Tomstone —— 被刪除對象的棲身地。對象的刪除，我們只做邏輯刪除，並不會將對象真正地從內存中抹去，而是放置在一個叫做 Tomstone 的地方，讓其他後續的命令，能夠和之前的命令有一個對比。數據的存留與否也就有了判定的依據。

四、GC — CRDT 取經之路的通天河

GC — Garbage Collection，很多語言都有這個特性，像 Java，Go。無獨有偶，我們這裏所說的 GC，原則和這些語言無異，都是爲了處理一類不再使用，但是又佔有資源（通常是內存資源）的一些數據的回收。

4.1 GC 的痛點

上一小節，我們簡單介紹了 Tomstone 的概念，GC 也是由於 Tomstone 的引入而帶來的在實踐中不得不面對的問題，如下圖所示：

隨着時間的推移，我們 Tomstone 中的對象會越來越多，直到喫掉你的全部內存，然後程序崩潰。

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

如何 GC 的問題，其實不如說是什麼對象可以 GC，這裏我們也舉兩個經典的GC算法：

尋根法（GC Root）
引用計數法（Reference Count）

兩種算法各有優劣，Reference Count 可以方便地及時發現需要 GC 的對象，卻無法解決循環引用的問題；GC Root 可以解決循環引用的問題，卻給 GC 掃描帶來了一定負擔。

我們的系統，採用了類似 RC 的算法來實現 GC：如果發現其他所有同步的 Redis Peer Master 都已經知道了某個對象被刪除的事實，那麼這個對象，就可以被永久刪除（也就是 GC）了。

怎麼發現對方知道某個對象被刪除了呢，前面有提到每個 Redis 都有自己的 Vector Clock，而 Vector Clock是和操作綁定的，只需 Redis 之間互通有無，互相瞭解到對方的 Vector Clock，那麼如何發現某個對象是否過期的問題也迎刃而解。

當然，整個過程也並非上面說起來那麼簡單。

比如，GC 的策略選擇，是主動 GC 還是被動 GC，抑或是兩者的結合？

單次 GC 時間長短的控制？如果 GC 時間過長，必然會影響 Redis 的響應速度；過短的 GC ，則會導致對象一直堆積在 Tombstone 中，內存得不到釋放。

五、Expire — 一致 or 不一致，這是個問題

作爲緩存來說，比較常見的是配置一定的緩存過期策略。一方面，可以保障數據的新鮮程度，另一方面無限制地將數據存入緩存，不僅不利於緩存的查詢速度，對於資源來說也是不小的開銷。所以，Redis 中引入了 Expire 的過期機制，給每一個緩存的 Key 設定一個過期時間是一個良好的習慣。

但是，在加入雙向同步的架構之後，expire 似乎成爲了一個問題，要不要將過期時間保持一致？如果保持一致的話，應該採取怎樣的數據結構？

首先，我們應該確認一個問題，緩存的過期時間不一致，會不會導致數據一致性的問題？結合 Redis 的實現來說，緩存過期時間不一致，不會帶來數據一致性的問題（這個數據特指除過期時間之外的用戶數據）。要說明白這個道理，我們先來看一下 Redis 是如何過期數據的。

Redis 的過期策略簡單來說分爲兩種，一種是主動過期，以一個固定的頻率輪詢存儲過期時間的字典，發現有 key 過期就執行刪除操作；另一種是被動過期，在用戶對 key 操作時，同時判定一下 key 的過期時間，是否需要過期掉。

兩種過期策略，都由 master 發起，slave 本身通過被動接受 master 同步過來的 delete 操作，來達到數據一致性（這裏我們忽略 slave-read-only 爲 false，且有客戶端過期 key 寫入的場景）。其實這個狀態下，是存在已經過期，但是在內存中沒有被刪除的 key，這個時候訪問 Redis，外在的表象爲 key 不存在。那麼對於客戶端來說，數據是一致的，過期的 key 確實拿不到了（雖然 Redis 內存中可能還有）。

對於雙向同步來說，如果併發地在兩端的 Redis 執行 expire 操作，就會發生衝突，是否處理衝突，如何處理衝突，是我們這裏想要討論的點。

在我們實際實現的過程中，曾經有一個版本確實實現了 expire 多個 Redis 之間的一致性，但是這樣做，引入了更多的數據結構來解決衝突處理問題。對比普通版本的 Redis，同樣大小的 expire 數據量，內存要多出一倍。對於攜程這樣 Redis 重度依賴的用戶來說，內存的增加無疑伴隨着大量費用的上升。所以最終的實現上，我們並沒有採取 expire 時間一致性的策略。

那麼是不是 expire 時間不一致，數據就有問題了呢？當然不是。舉例來說，有 A/B 兩個 Redis 建立了雙向同步。A/B 在同一時間點，分別對同樣的 key 設置了不同的過期時間（如下圖）。

一邊設置過期時間爲 30s，另外一邊設置爲 60s，互相同步之後，時間進行了對調。30s 以後 Redis-A 上面的 key 過期，觸發了 del 操作，同時把這個操作傳播給 Redis-B，因爲 delete 機制的存在，兩邊的數據是一致的。