1. 概述 對於分散式系統，人們首先對現實中的分散式系統進行高層抽象，然後做出各種假設，發展了諸如CAP, FLP 等理論，提出了很多一致性模型，Paxos 是其中最璀璨的明珠。我們對分散式系統的時序，複製模式，一致性等基礎理論特別關註。 在共識演算法的基礎上衍生了選舉演算法，並且為分散式事務提供了部分 ...
1. 概述
對於分散式系統，人們首先對現實中的分散式系統進行高層抽象，然後做出各種假設，發展了諸如CAP, FLP 等理論，提出了很多一致性模型，Paxos 是其中最璀璨的明珠。我們對分散式系統的時序，複製模式，一致性等基礎理論特別關註。
在共識演算法的基礎上衍生了選舉演算法，並且為分散式事務提供了部分的支持。本文從常見的幾種分散式存儲系統看看實踐中的分散式系統設計細節。理論結合實際，能更好地幫助我們加深理解。
2.分片
先來看看分片的定義：
The word “Shard” means “a small part of a whole“. Hence Sharding means dividing a larger part into smaller parts. In DBMS, Sharding is a type of DataBase partitioning in which a large database is divided or partitioned into smaller data and different nodes
分片是分散式存儲系統繞不開的話題，分片提供了更大的數據容量，能夠提升讀寫效率，提升數據可用性。
| 分散式存儲系統 | 分片 | 備註 |
| elasticsearch | 每個index 進行分片，即 shard | shard計算，shard = hash(routing) % number_of_primary_shards |
| kafka | 每個topic分析分片，即 partition | 根據key來選擇partition，也可以根據自定義partition演算法實現 同一的user發送到同一 的partition |
| redis-cluster | 對所有數據進行分片，hash slot 16384（2^14） | hash tags 確保數據分配到同一個slot：{123}:profile and user:{123}:account |
- 對redis-cluster 來講，redis client 需要緩存 key - slot 映射，因為redis 節點不會對 查詢請求進行代理，如果查詢數據不存在，則需要client重新查詢。
- redis-cluster 的設計目標是在提供高性能的基礎上，讓redis數據能分佈在多達1000個節點的集群上。
3.複製
複製提升了數據的可靠性，複製分片還可以用來做read。在分散式系統重，有兩種複製模式：
- 同步複製，主節點在同步數據到slave，然後返迴響應給到client
- 非同步複製，主節點先返迴響應給到client，然後同步數據到slave
| 分散式存儲系統 | 複製 | 備註 |
| elasticsearch | primary 複製數據到 in-sync copies，同步複製 | |
| kafka | 主分片複製數據到 ISR (in sync replica) | producer 可以配置 acks 和 min.insync.replicas 來調整一致性 |
| redis-cluster | 採用redis 的複製機制，非同步複製 | redis對性能非常敏感，所以採用的都是非同步複製 |
- 以上三種系統均採用 primary-backup model （Google I/O 2009 - Transactions Across Datacenters）, 具有低延遲，高吞吐，會有部分的數據丟失視窗
- 舊的elasticsearch 版本中可以調整write conistency level : one（primary shard）, all（all shard）, quorum（default）.
- kafka 是典型的日誌消息系統，數據量特別大，在常見的quorum-based 系統中，為了能容忍n個節點失敗，往往需要2n + 1 個節點，這對kafka來講多餘的存儲成本非常的高，於是kafka採用了ISR機制，即只維護那些與主分片及時保持同步的分片，當主分片失敗時，從ISR 中選取一個作為最新的主分片即可。
4.一致性
不同的複製策略帶來了不同的一致性，常見的一致性有
- 強一致性
- 最終一致性
- 弱一致性
根據Ryan Barrett在Google I/O 2009 - Transactions Across Datacenters中的定義，elasticsearch/kafka/redis-cluster 都採用了 primary-backup model，primary-backup model 的特點是最終一致性，但是具體細節有所不同。
| 分散式存儲系統 | 寫入一致性 | NWR 模型 | 備註 |
| elasticsearch | 最終一致性 （較強） | w(all write) , r(1) | 需要refresh 到文件系統緩存才可見，flush操作到磁碟 |
| kafka | 最終一致性 （可調） | w(ack writes) , r(1) | ack = 0 最弱，ack = all 最強 |
| redis-cluster | 最終一致性 （較弱） | w(1) , r(1) |
- 採用最終一致性，意味著在寫入過程中，會出現部分節點返回最新數據，部分節點返回過期數據的情況，由於這個時間視窗很小，往往可以接受。
- 我們在這裡提到了NWR模型，參考 partial quorums，partial quorums 在基於衝突解決的複製模型中使用廣泛，比如Dynamo。當 r + w > n 時總有節點能返回最新的數據。
5.選舉演算法
選舉演算法的基礎是共識演算法，paxos是其中最璀璨的明珠，paxos在共識演算法中的地位可以用這樣表述：
Either Paxos, or Paxos with cruft, or broken
paxos 最早應用於google 的 Chubby （lock manager），zk是 Chubby的開源版本。
| 分散式存儲系統 | 選舉演算法 | 備註 |
| elasticsearch | bully/類raft | bully演算法比較簡單，誰大就選誰 |
| kafka | zookeeper(zab)/kraft(raft) | |
| redis-cluster | 類raft |
- 可以看到很多分散式組件都有轉向raft的趨勢。
-
由於paxos演算法晦澀難懂，並且如果要應用到實際過程中需要做很多調整，所以開發了一個易於理解的版本raft演算法，raft演算法分為 leader election, log replication, safety, and membership changes 等模塊，相比於paxos 所有節點都是平等的，raft 進行leader 選舉，並且通過log replication進行數據同步，safety 確立了raft演算法的完備性，membership changes 處理節點變更的情形。log replication 表示了raft底層的數據結構，對我們設計類似系統大有裨益。
6.事務支持
存儲系統中，事務是非常重要一部分，我們來看看各類組件是否支持分散式事務，以及他們是如何實現的：
| 分散式存儲系統 | 事務支持 | 備註 |
| elasticsearch | 不支持 | |
| kafka | 支持事務，基於2PC | |
| redis-cluster | 不支持跨節點的事物，支持單節點的事物 | 使用multi/exec/watch 來實現 |
- 2PC是一種強一致的模型，具有高延遲，低吞吐的特點。
- 常見的分散式事務模型有，primary-backup model，multi-master model, 2PC, Paxos. 3PC 是2PC 的變體。個人認為TCC, 基於消息表的事務也是2PC 的變體。
7.總結
本文從分散式系統的幾個方面探討了elasticsearch，kafka，redis-cluster的細節，他們有很多共性，但是在許多方面也有很多不同。鑒於筆者對分散式系統的研究還不是很深入，如果錯誤，請指正。
8.參考
https://book.mixu.net/distsys/single-page.html
https://www.youtube.com/watch?v=srOgpXECblk
https://snarfed.org/transactions_across_datacenters_io.html
http://harry.me/blog/2014/12/27/neat-algorithms-paxos/
https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf
