提供高性能的讀寫服務(wù)是分布式研發(fā)工程師一直追求的目標(biāo)，譬如在 TiDB 中诵原，我們就基于原生的一致性算法 Raft 做了非常多的改進(jìn)和性能優(yōu)化愤诱。當(dāng)然，在分布式領(lǐng)域丐膝，復(fù)制協(xié)議不光只有 Raft 這么一種量愧，譬如這段時(shí)間钾菊，我就看到了另一個(gè)不錯(cuò)的實(shí)現(xiàn)，叫做 Hermes偎肃，來自于 Paper Hermes: a Fast, Fault-Tolerant and Linearizable Replication Protocol煞烫。
通常我們說分布式系統(tǒng)的高性能，無非就是關(guān)注兩點(diǎn)：低延遲和高吞吐累颂，對(duì)于讀寫請(qǐng)求來說滞详，無非就是：
- 讀
- 能從所有副本讀取數(shù)據(jù)
- 寫
- 更少的網(wǎng)絡(luò)交互
- 去中心化，不需要有單獨(dú)的地方進(jìn)行 serialization 處理
- 完全并發(fā)紊馏，任何 replica 都能進(jìn)行寫入
對(duì)于 TiDB 來說料饥，雖然我們?cè)?Raft 這邊支持了 Follower Read，也就是能從任意副本讀取數(shù)據(jù)朱监，但在寫入上面岸啡，還是只有 Leader 能提供寫服務(wù)。但是 Hermes 卻能做到任何副本寫入赫编，所以讓我對(duì)這篇 Paper 非常有興趣巡蘸，讀下來之后，其實(shí)會(huì)發(fā)現(xiàn)沛慢，原來 Hermes 的原理非常的簡(jiǎn)單赡若。
在介紹原理之前，先階段的說下团甲，Hermes 使用的是非常通用的 logical timestamp 機(jī)制逾冬，后面用 LT 來表示，一個(gè) LT 是一個(gè) [V, Cid] 的 tuple躺苦，V 就是通常的 Lamport clock身腻，而 Cid 則是 replica 的 Node ID。如果對(duì)于一個(gè) Key 的并發(fā)寫入 V 是相同的匹厘，則按照 Cid 進(jìn)行排序嘀趟。
Hermes 的 replica 有 Coordinator 和 Follower 兩種，Coordinator 接受 client 的寫入請(qǐng)求愈诚，參考論文的圖她按，一次寫入如下：
- Coordinator 接受 client 的 write 請(qǐng)求，將 Key 分配一個(gè)新的 LT炕柔，給其他 followers 也廣播一個(gè) Invalidation(INV) 消息酌泰。并且將 Key 變成 Write 狀態(tài)。
- 其他 followers 收到 INV 之后匕累，會(huì)比較 LT陵刹，如果收到消息的 LT 比本地的大，就會(huì)將 Key 變成 Invalid 狀態(tài)（如果這個(gè) Key 之前是 Write 或者 Replay欢嘿，則會(huì)變成 Trans 狀態(tài)）衰琐，并且回復(fù) ACK 消息也糊。無論之前比較的結(jié)果怎樣，ACK 里面的 LT 都是收到的 INV 的 LT羡宙。
- 如果所有的 ACK 都收到了狸剃，write 就認(rèn)為完成，這個(gè) Key 就變成 Valid 狀態(tài)（如果之前處于 Trans 狀態(tài)辛辨，則會(huì)變成 Invalid 狀態(tài)）
- Coordinator 再次廣播 Validation(VAL) 消息
- 當(dāng) Follower 收到 VAL 消息捕捂，只有 VAL 的 LT 等于之前本地的 local timestamp，才會(huì)將 Key 轉(zhuǎn)成 Valid 狀態(tài)斗搞，否則一律丟棄這個(gè) VAL 消息
可以看到，流程非常的簡(jiǎn)單慷妙，那么 Hermes 是如何支持 fault tolerance僻焚， Linearizability 這些特性的呢？
Hermes 保證膝擂，如果讀取的 Key 處于 Invalid 狀態(tài)虑啤，那么 read 則會(huì)一直等待，直到 Key 處于 Valid 狀態(tài)架馋。所以這里可以看到狞山，Hermes 采用 read wait 的方式滿足了 Linearizability。
而對(duì)于 fault tolerance叉寂，則是使用的 replayable write 的方式萍启，如果 Coordinator 在發(fā)送 VAL 消息之前跪了，那么就可能導(dǎo)致一個(gè) key 處于 invalid 狀態(tài)屏鳍。這里可以直接 replay write勘纯，因?yàn)?Hermes 會(huì)做如下事情：
- INV 消息里面會(huì)帶上寫入的新值，這樣收到 INV 的 replica 都能知道這個(gè)值钓瞭，并且將其設(shè)置為 Invalid 狀態(tài)
- Logical timestamp 能保證在每個(gè) replica 上面的 write 順序
- 基于上述兩點(diǎn)驳遵，任何一個(gè)節(jié)點(diǎn)如果發(fā)現(xiàn)一個(gè) key 處于 Invalid 狀態(tài)超過一段時(shí)間，就可以認(rèn)為自己是 coordinator山涡，使用之前的 LT堤结，重新傳遞之前的 INV 消息，安全的 replay 這個(gè) write鸭丛。
Membership 變更
再來說說另一個(gè)需要關(guān)注的 membership 變更竞穷，Hermes 采用的是比較常用的做法，叫做 m-update系吩。一個(gè) m-update 包括：
- 一個(gè)新的 lease
- 一批新的 live nodes
- 一個(gè)遞增的 epoch ID
一個(gè)接受了 m-update 的 replica 就可以當(dāng)成 coordinator 了来庭，這里需要注意：
- 如果 read 處于 Valid 的 key，仍然是按照之前的方式處理
- 如果 write 或者 read 處于 Invalid 的 key穿挨，則需要等 m-update 里面的 live nodes 接受到 m-update
- 如果一個(gè) follower 還沒接受到 m-update月弛，則會(huì)丟棄后續(xù)的消息肴盏，因?yàn)檫@些消息的 epoch ID 會(huì)比 follower 當(dāng)前的 epoch ID 要大
Example
下面是 Paper 實(shí)際列舉的一個(gè)例子：
- Node 1 開始 write A = 1，同樣帽衙，node 3 開始 write A = 3菜皂。
- Node 2 收到 Node 1 的 INV 消息，回復(fù)了 ACK厉萝，并且將 Key A 變成了 Invalid 狀態(tài)
- Node 3 給 Node 1 也回復(fù)了 ACK恍飘，但 Node 3 并沒有改變 A 或者它的狀態(tài)，因?yàn)?A 的 LT 是比 Node 1 發(fā)過來的 INV 要大的谴垫。
- Node 2 收到了 Node 3 的 INV章母，因?yàn)檫@個(gè) INV 的 LT 比之前的要大，所以 Node 2 更新了本地 A 的 LT 和 value
- Node 1 收到了 Node 3 的 INV翩剪，同理也更新了本地 A 的狀態(tài)
- Node 2 開始一次 read乳怎，因?yàn)?A 的狀態(tài)是 invalid，所以 read 會(huì) stalled前弯，然后收到 VAL 的消息蚪缀，就可以讀取了，這時(shí)候讀到的值是 3
- Node 1 收到了所有的 ACKs恕出，但仍然將 A 變成了 Invalid 狀態(tài)询枚，因?yàn)橹笆盏綇?Node 3 發(fā)來的帶有更大 LT 的 INV 消息，但還沒收到 Node 3 發(fā)來的 VAL 消息
- 如果 Node 3 跪掉了浙巫，Node 1 還沒收到 VAL 消息
- Lease 過期金蜀，Node 3 仍然是 failed，membership 更新
- 從 Node 1 讀取 A狈醉，會(huì)發(fā)現(xiàn)處于 Invalid 狀態(tài)廉油，Node 1 對(duì) A 進(jìn)行 replay 操作
- Node 2 收到消息不用處理，因?yàn)橛型瑯拥?LT
- Node 1 收到 Node 2 的 ACK苗傅，完成 replay抒线，并且廣播 VAL
寫在最后
上面只是簡(jiǎn)單的介紹了 Hermes 常用的讀寫流程以及成員變更方式，其實(shí) Hermes 還提供了 CAS 支持渣慕，不過我也懶得研究了嘶炭，總得來說，Hermes 還是非常簡(jiǎn)單的逊桦，而且非常容易實(shí)現(xiàn)眨猎，更難得可貴的是，Hermes 提供了 TLA+ 的證明强经，我現(xiàn)在也佩服我自己睡陪，竟然還能看得懂，之前的辛苦學(xué)習(xí)沒白費(fèi)。兰迫。信殊。
關(guān)于更多的信息，大家可以直接用官網(wǎng) https://hermes-protocol.com/ 看看汁果。
