Nosql儲存系統-叢集工作原理

一.nosql發展歷史

1.關係型資料庫

上世紀60年代以來至今，傳統的關係型資料庫一直被網際網路應用的作為首選資料儲存系統，典型的代表產品包括有oracle、mysql等。

關係型資料庫的核心優勢在於：第一，具備事務屬性，注重資料一致性，內部實現有複雜的鎖機制等還包含有其它一系列機制來保障資料一致性，能夠基於AID(原子性、隔離性和永續性)的基礎能力而帶來事務強一致性來保證我們的資料存、取安全；第二，關係型資料模式其支援的二維表格模式比較契合現實中大部分的業務場景且易於理解，因此得以快速應用和發展。

關係型資料庫最大的缺陷在於擴充套件性不足，在面對大量使用者的併發訪問以及海量儲存的存取場景下，往往很難平滑的去做到效能升級，而使得DB經常作為整個系統應用的發展瓶頸。通常情況下，關係型資料庫的擴充套件思路分為以下兩種：

（1）縱向擴充套件。縱向擴充套件即提升單機硬體基礎設施來提升處理能力。這種方式下雖然可以換來一定的效能提升，但是單機終歸是存在有效能上限的，且升級過程中往往需要停機處理而無法做到平滑升級。其整體收益成本比比較低。

（2）橫向擴充套件。橫向擴充套件即通過分片，將資料分散至多臺物理節點，降低單點壓力，來提升處理能力。這種方式通常是對上層應用抽象出一個邏輯資料庫，背後則是將資料分散到不同的物理資料庫上。整體上來說，這種方式雖然可以在大部分常規場景下帶來較大的效能提升，但與此同時又會引入另一個新的問題分散式事務問題，當然還包括有跨庫join、非路由鍵查詢等其它一系列問題。

2.NoSql的誕生

在隨著網際網路業務與場景不斷髮展的背景下，由於在應對海量儲存資料時傳統的關係型資料在擴充套件能力上的不足，以及出現了越來越多的場景在關係型模式下顯得並不適用，典型的如OLAP資料分析型別場景。促使Nosql技術開始誕生，Nosql的核心思想在於放棄傳統關係型資料庫的事務強一致性與關係模式，以此換取更高的可擴充套件性以及面對高併發海量資料時具備更強的處理能力。

對於Nosql而言，其定位並不是取代關係型資料庫，而是作為關係型資料庫的一種補充，兩者分別有各自適合的領域場景。典型的nosql產品包括：基於kv的redis、列儲存的hbase、文件型資料庫ES等。

3.NewSql

nosql雖然具備高擴充套件性的優勢但其實在放棄了傳統關係型資料庫的強事務一致性的代價下換來的。因此，在關係型資料庫與nosql均存在明顯侷限的背景下，NewSql概念開始應運而生。NewSQL可以說是傳統的RDBMS與NoSQL技術結合之下的產物。這些系統既擁有NoSQL資料庫的高擴充套件性，又希望能保持傳統資料庫的事務特性。典型的產品代表如google的spanner和國內的TiDB。

二.常見的Nosql產品簡介

常見的nosql產品如下：

產品名稱	特點	適用場景
redis	1.k-v結構；2.記憶體資料庫；3.高效能，單機2C4G下讀可達10WQPS；	1.快取；2.分散式鎖、延時佇列、限流等；
ES	1.文件型資料庫；2.結構化查詢。支援多欄位查詢，以及複雜的過濾和聚合統計功能；3.近實時查詢。預設1s refresh一次將記憶體中的資料固化生成一個新的segment，此時為該segment建立倒排索引，外部讀請求才能訪問到這個segment的內容；	1.大數量背景下的檢索類場景。例如日誌搜尋、大寬表解決mysql跨庫join問題以及作為輔助索引解決分表下的非路由鍵查詢問題；2.資料統計、分析；3.全文檢索；
Hbase	1.列儲存；2.採用塊儲存機制，底層資料結構採用的是LSM合併樹，將隨機IO寫轉變為一次性順序寫，相比於B+樹在寫效能上表現更加優秀。但讀效能會更弱；	1.PB級資料儲存規模；2.適合寫多讀少的場景，例如下沉的冷資料儲存；3.OLAP資料分析類場景；

三. 叢集工作原理

3.1 叢集模式

對於大規模資料儲存系統都會面臨一個問題就是如何進行橫向擴充套件，當資料集越來越大時，一主多從的模式無法支援這麼大的資料儲存與訪問量，此時一般情況下就會考慮進行橫向擴充套件，將多個主從模式組合在一起對外提供服務。但是這裡有兩個首要問題就是如何實現資料的分片邏輯以及分片邏輯放在哪裡。於是在這種背景下就會衍生出兩種不同的叢集模式，一種就是集中式模式，一種則是去中心化的模式。

1.集中式

集中式叢集模式下，通常會引入一箇中心節點作為叢集的管理者，由管理者來進行叢集狀態管理、故障處理以及元資料維護等，其它節點只需響應資料請求，而無需知道叢集中其它節點的情況。典型的解決方案都會藉助於zookeeper分散式協調服務來進行叢集管理，比如Hbase、kafka等。

Zookeeper：維護叢集中的服務狀態，並提供服務故障通知；

master：儲存和維護叢集元資料，以及故障轉移等叢集事務處理；

2.去中心化

即P2P互動模式，客戶端與叢集節點直接進行互動，而非之前業界的Proxy方式。典型的叢集代表如redis cluster、es叢集。

redis Cluster介紹

redis3.0版本開始，官方正式支援叢集模式。redis官方叢集模式最大的兩個特點在於：

（1）去中心化。即P2P互動模式，客戶端與叢集節點直接進行互動，而非業界之前的Proxy方式。

（2）內部自治。redis 叢集模式並未像Hbase、Kafka等引入第三方元件比如ZK，來實現對叢集的節點狀態管理、故障轉移以及元資料管理等，而是基於Gssiop協議實現叢集內節點監控、狀態同步，並內建選舉演算法實現故障自動轉移，在叢集內部高度自治。

如下圖是一個三主三從的redis cluster，三個機房部署，其中一主一從構成一個分片，之間通過非同步複製同步資料。節點之間基於ping-pong心跳機制相互通訊感知對方狀態，一旦某個機房掉線，則分片上位於另一個機房的slave會被提升為master繼續對外提供服務。

3.2 資料分片

分散式叢集在進行橫向擴充套件時，首要問題就是如何實現資料的分片邏輯。

1.分片策略

常見分片策略如下：

（1）hash分片。hash分片也是我們最常用的分片策略。例如ES預設採用的就是這種方式。hash分片的好處在於資料會被打的比較分散，其次不用額外儲存對映關係，客戶端與服務端以約定好的hash公式進行路由。但是它的問題在於如果一旦需要進行擴縮容，那麼整個對映關係都會被打破，此時需要進行一次全量的rehash資料遷移，工作量非常大。所以一般情況下，在設計的時候會盡可能的讓這個hash模值大一點，避免頻繁的進行擴容。

（2）基於某一key值的範圍劃分。例如基於時間範圍或者id範圍分片。這種分片方式的優劣勢其實與hash的方式是相反的。它的好處在於，當需要進行擴縮容時，不會像hash一樣破壞掉全域性的對映關係，只需要對部分分片的對映關係產生影響。但是這種方式的問題在於它會存在一定的熱點資料問題，導致整個叢集各個節點的負載不均衡。例如Habse採用的就是這種方式，HBase 表根據 RowKey 的開始和結束範圍水平拆分為多個 Region，一個region就是分片。每個 Region 都包含了 StartKey 和 EndKey 之間的所有行。每個 Region 都會分配到叢集的一個節點上，即 RegionServer，由它們提供讀寫服務。

（3）一致性hash。一致性hash是通過構建一個環形的hash空間，對於使用者的請求，先經過hash對映到這個環上，這就是第一層的對映關係，只要這個hash的模值不變，這層關係就不會變。其次，順著環的順時針方向找到的第一個節點，就是負責該請求對應的節點。

一致性hash的優勢在於當進行擴縮容時，不會破壞全域性的對映關係，而導致整個rehash，發起全域性的資料遷移，而只會影響區域性資料的對映關係。比如縮容減少一個節點，因為第一層對映依然保持不變，原來的請求該分配到哪個節點還是在哪個節點上，只是改變了第二層從環上到節點之間的一個區域性對映關係。從環上來看，只會影響這個節點的上一個節點到這個這個節點的這一段弧區間上，整個環上的其它區間由於第一層關係不變，其對映關係不會受到影響。原來去掉的這個節點之間負責的那一段弧上請求，會全部順移到它的下一個節點，我們只需要把去掉節點負責的資料遷移到下一個節點即可，其它的所有節點不用做任何變更。

2.基於Hash槽的資料分片

redis cluster中，資料分片藉助與hash槽slot來實現，叢集預先劃分16384個slot，對於每個請求叢集的鍵值對，根據key 按CRC hash演算法雜湊生成的值唯一匹配一個slot。在redis叢集中每個master節點分片負責其中一部分槽位的讀寫請求，而且當且僅當每個slot都有對應節點負責時，叢集才會進入可用狀態。當動態擴縮容時，需求將16384個slot做一次再分配，相應資料也要進行遷移。

redis hash槽的演算法與一致性hash演算法的本質思想是一樣的，通過不直接建立請求到節點的對映關係，而是建立一種間接的對映關係。避免在發生擴縮容時對於傳統hash演算法而言因為模值的變化而打亂整個對映關係。如下圖所示，將對映關係分為兩層，hash槽通過槽位路由表作為中間對映，因為槽位數量是16384不會變，這樣當發生擴縮容時，對於請求而言該對映到哪個槽位還是對映到哪個槽位，即Part1對映不變，只用針對Part2部分中需要遷移的slot產生影響，而並非會讓全部請求受到影響；

3.3 客戶端互動流程

Redis叢集互動

redis客戶端與叢集之間的互動是基於槽位對映表來進行的，該對映表類似於叢集的資料分佈圖，其中維護著槽位與負責該槽位的節點地址資訊，客戶端根據該對映關係與節點進行直連互動。

redis客戶端首次連線叢集時，會從叢集中拉取一份完整的槽位對映表，快取在本地。在進行請求訪問時，首先會採用CRC16冗餘校驗法的值對16384取模，對映到具體一個槽位，隨之通過查詢槽位對映表定位到具體負責該槽位的節點，進而直接與節點進行通訊。對於服務端節點來說在收到請求後首先會判斷該槽位是否是自己負責的槽位，如果是，則會響應客戶端請求。如果不是，例如叢集發生擴縮容，此時槽位發生遷移，則會返回Moved/ask指令，引導客戶端重定向至正確的節點進行訪問。

Moved指令：當遷移已經全部完成，此時該slot已經永久轉交給另一個節點時，A節點會返回Moved指令。當Client收到Moved指令後，則會重定向至正確的節點再次進行訪問，同時更新本地的槽位對映表，下次直接訪問到正確的節點。

ASK指令：ASK指令主要是在遷移過程中，此時該slot的資料可能一部分位於B，而另一部分key可能還在源節點A上。此時對於讀請求而言，源節點A在收到請求後，會先在自己的資料庫中查詢，如果存在則直接返回結果；如果不存在則說明可能已經遷移至B，則會返回ask錯誤指令，引導client轉向目的地節點查詢key；

當Client收到Moved/AKS指令後，會去重定向至新的節點訪問，同時還會更新本地的槽位對映表，在下次訪問時直接定位至正確的節點上；

ES叢集互動過程

es作為搜尋引擎而言，其支援的查詢條件不侷限於路由key，還包括其它關鍵字作為條件進行查詢，因此其在查詢流程不太一樣。

es預設的查詢模式為query then fetch模式，此模式下整個查詢分為query 和 fetch兩個步驟，query步驟負責查詢符合條件文件id以及彙總排序擷取limit等，fetch階段則是查詢完整資料，查詢過程中需要進行兩次互動。

（1）client首先會將查詢請求傳送至任一協調節點；

（2）協調節點在收到請求後，會併發的將請求傳送至所有的資料節點；

（3）資料節點在收到請求後根據查詢條件在自己負責的分片上查詢符合條件的文件集合，不過只取文件 id和排名相關的欄位資訊，並將資料集返回至協調節點；

（4）協調節點在收到資料節點返回的結果集後，進行彙總排序取limit等，隨著得到需要返回的結果集docId集合；

（5）此時query階段結束，進入fetch階段，協調節點會根據hash演算法對docId進行路由，得到對應結果分別在哪些分片節點後，再次傳送請求至資料節點，fetch資料；

（6）資料節點根據docId查詢完整結果資料，並將資料再次返回至協調節點；

（7）協調結果進行完資料彙總後，將資料返回至客戶端；

除了query then fetch之外，es還有另外一種比較常見的查詢模式：query and fetch 。 此模式下向索引的所有分片 （ shard）都發出查詢請求， 各分片執行完query 後再執行fetch，即在分片節點中做完查詢、排序和擷取後將完整的資料一併返回至協調節點。這種搜尋方式是最快的。因為這種查詢方法只需要去 shard查詢一次。但是各個 shard 返回的結果的數量之和可能是使用者要求的 size 的 n 倍。

Hbase叢集互動過程

Hbase叢集與redis叢集不一樣，其基於ZK進行叢集狀態管理以及元資料維護，叢集中資料節點只知道自己負責的資料分片而不知其他節點。因此，在客戶端進行叢集訪問時，通常需要先於ZK進行一次訪問，在獲取路由表後，再與叢集節點直連訪問。kafka也是同理。

如下圖所示，HBase叢集中的讀取流程大致如下所示:

（1）client首先會訪問一次zk，查詢叢集中master節點；

（2）在查詢到master地址資訊後，Client第二次發起請求訪問master，查詢路由資訊表，路由表中記錄著每個region節點負責處理哪個範圍的rowkey；

（3）client在查詢到路由資訊後，會將其快取在本地，隨之基於路由資訊表，查詢rowkey對應的節點地址資訊；

（4）直連資料節點伺服器，傳送查詢請求獲取資料；

（5）節點伺服器在收到請求後，查詢對應的完整資料並將結果返回至客戶端；

3.4 叢集管理

1.叢集元資料管理

在集中式叢集中，通常情況下會直接基於第三方協調服務zk來管理和維護叢集元資料，zk在作為分散式協調服務之外，本身也是一個記憶體資料庫。不過通常為減輕zk壓力以及降低對zk的依賴，因此一般情況下，叢集還會基於zk選舉出一個master節點，代理zk進行元資料管理和維護以及非master節點的故障轉移等相關事務處理。同時，zk中也會備份一份叢集的元資料資訊，避免master故障後集群元資料丟失，當選舉出來的新master，會從zk中拉取一份叢集元資料繼續進行維護。

在去中心化的叢集中，例如redis叢集下每個節點都儲存有整個叢集的元資料資訊，包括自己以及其它節點的存活狀態、負責的slot槽位資訊等。各節點間基於 Gossip 協議來相互交換資訊，Gossip協議又叫病毒協議，是基於流行病傳播的方式在節點或者程序之間資訊交換的協議，在P2P去中心化的分散式系統中應用比較廣泛。

Gossip協議的特點在於：

1.去中心化。Gossip 協議不要求任何中心節點，所有節點都可以是對等的，任何一個節點無需知道整個網路狀況，只要網路是連通的，就可以把訊息散播到全叢集。

2.最終一致性。資料的傳播過程是由一傳十十傳百逐步流散開來，整個傳播過程需要經歷多個週期，可能需要一定的時間，不過在一個處於有界網路的叢集裡，理論上叢集各個節點對該份資訊的認知最終都將會收斂一致。

Redis Cluster 中的每個節點都維護一份自己視角下的當前整個叢集的狀態，主要包括：

a.叢集中各節點所負責的slots資訊；

b.叢集中各節點的存活狀態資訊；

對於叢集中每個節點而言，會按照一定的頻率週期，從自己的節點列表中隨機挑選部分最長時間沒有與它進行過通訊的節點，對這些節點發送ping訊息，並附加上自己視角下的叢集狀態資訊，節點在收到其他節點發送的ping訊息後再回復一個pong，以交換彼此的狀態資訊，對於差異化資料則版本決定是否更新本地狀態資料，最終叢集內所有節點達成統一認知。

優點：

（1）容錯。Gossip 協議具有天然的分散式系統容錯特性，叢集中任何節點的狀態發生變化，例如上下線都不會影響 Gossip 訊息的傳播，且當節點重新上線後，依然會接收叢集內其他節點的狀態資料，並最終與其他節點達成一致。

缺點：

（1）Gossip是最終一致性，當叢集狀態發生變更時，變更資料需要經過多倫同步，整個叢集的節點才會達成一致，相比於ZK而言其感知會出現明顯延遲；

（2）Gossip協議下，每個節點按自己的節奏頻率週期性的傳送訊息，而由於同步全量狀態資訊使得Gossip包體積較大，會存在一定的網路壓力。其次由於隨機的傳送訊息，而收到訊息的節點也會重複該步驟，不可避免的引起同一節點訊息多次接收，增加訊息處理壓力。

2.叢集狀態檢測

對於集中式叢集模式的Hbase、kafka來說，對於叢集的狀態檢測也是基於ZooKeeper 來做的，每臺節點機器在啟動時，都需要事先在zookeeper中註冊一個節點，zk會與該節點維持一個會話關係，基於心跳檢測來感知節點的狀態變化。

具體來說，客戶端會週期性的向服務端傳送PING請求來保持心跳，一旦客戶端發生故障，超過限定時間後，Zookeeper伺服器會判定會話超時，並基於Watch機制實時通知給Master節點，master進行元資料更新以及後續的故障轉移，以此來完成對叢集中節點的狀態檢測。

跟大多數分散式系統一樣，Redis cluster也是基於heart beat來進行節點狀態檢測。redis內部節點基於Gossip協議通訊互動，具體來說，每個節點會定期會與其它節點發送ping-pong訊息進行互動，以此來感知對方是否狀態發生變化。對於叢集中每個節點而言，每次隨機挑選5個最長時間沒有與它進行過通訊的節點，對這些節點發送ping訊息，節點在收到其他節點發送的ping訊息後再回復一個pong。每個節點根據自己是否收到pong訊息的結果來感知其它節點的存活狀態。

節點上線

Redis Cluster 加入新節點時，首先需要在客戶端需要執行 CLUSTER MEET 命令，命令中需要指定新增節點的地址資訊。

redis叢集中任一節點在收到 MEET命令後，會根據據 MEET 命令中的 IP 地址和埠號，向新節點發送一條 MEET 訊息。

接著，新節點在收到Meet訊息後，會向節點一返回一條PONG訊息。

節點一接收到新節點返回的PONG訊息後，得知新節點已經成功的接收了自己傳送的MEET訊息。隨著將該新節點加入自己的元資料資訊庫中，從而完成了新節點接入的握手操作。

Meet成功之後，節點一會在下次週期性資訊互動過程中，將新節點加入的訊息傳遞出去。因為節點之間基於Gossip協議進行工作，在隨著時間的推移，最終叢集的所有節點都感知它的存在。

節點下線

redis叢集中節點會週期性心跳同步，當某一節點在發其ping請求後，發現某個節點超過一定未給出回覆，那麼它會把這個節點的狀態標記為pfail預下線的狀態。

節點一會在下一輪互動中，會將節點二疑似下線訊息同步出去。對於節點三在同步到這條訊息後，並不會直接把自己的節點列表中該故障節點的狀態也標記為預下線，因為這時候可能只是該節點一個人的主觀認為下線，只是先記錄下來節點一在XX時間認為節點二疑似下線；同時在節點三的下一輪ping-pong中，會優先選擇節點二進行互動；

隨著時間的推移，經過多輪同步後，對於節點X也超時未收到節點二的PONG，也認為節點二疑似下線，此時節點X發現叢集中大部分超過一半的節點都認為它下線時，節點X會把該節點二標記為fail下線狀態，並同時在叢集中廣播該節點fail。所有收到該訊息的節點在發現某節點已經被標記為fail狀態時，都會更新自己的節點列表將它標記為下線狀態，如果該節點是leader副本的節點，則其對應的slave節點在收到下線訊息會開始進行選舉，進入故障轉移流程。

3.5 高可用性

對於分散式儲存系統而言，叢集高可用保證在於解決兩個前提，第一個是要保證資料的可靠性，即當節點機器出現故障時，資料不能因此出現丟失。第二，在故障發生後集群需具備自動故障轉移機制。

1.資料的 可靠性 保證

通常而言，資料的可靠性都是基於多副本機制來解決的，即構建主從模式，為每個主節點部署多個slave從節點，當主節點故障時由從節點頂替。

對於多副本機制而言，其核心問題在於如何解決多副本之間的一致性。在多副本資料一致性問題上，一般會有兩種解決方案。一種是基於ACK應答機制下的主從複製機制；另一種是目前業界更為主流的方案，基於分散式共識演算法Paxos或者Raft來解決多副本之間的一致性問題。

主從複製+ ACK 機制

基於ACK的應答機制十分常見，首先從同步方式上來說又分為推模式和拉模式，拉模式相對而言十分常見，例如mysql的主從複製就是拉模式。兩種模式的比較如下：

模式	代表產品	優劣勢
拉	mysql、es\kafka等	優勢： 從節點可基於自身消費能力處理同步資料； 劣勢： 資料同步及時性相對差一點
推	redis	優勢： 資料同步相對更加及時； 劣勢： 從節點一旦同步過程中出現重啟，則重新啟動後需要再次完整的同步一次全量資料。因此，在這種模式下一般還需要配備相關的緩衝區機制。例如redis中會配置同步緩衝區，在commit之前同時會先在緩衝區中備份一份。從節點重啟後同步位移還在緩衝區中，則從緩衝區增量同步進行對齊。

從應答機制的角度上來說又分為非同步複製、半同步複製與全同步複製。

（1）非同步複製。主節點在收到寫請求後，會將資料寫入記憶體以及同步至中繼日誌後，進行commit提交。隨後通知slave節點過來複制，slave是否成功複製主節點並不關心。對於非同步複製而言，它是存在有資料丟失風險的，當master宕機時，從節點可能還沒來得及複製資料。

（2）半同步複製。半同步複製每次都會至少有一個從節點ack應答，相對而言它可以有更強的一個數據一致性保證。但還是會存在不一致的問題的場景，比如腦裂問題，導致資料丟失。當發生網路分割槽時，master節點和一個從節點被劃分到一個區域與其它的從節點分離，這時其它從節點發現與master失聯後就會選出一個新的master來提供服務，但是原來的master並不知道自己被失聯了，而且每次依然會有一個從節點給它ack應答，因此它也可以正常處理客戶端請求，這個時候就會存在兩個master同時對外提供服務，接收客戶端的寫請求，而當網路分割槽結束後舊的master發現有新的master了，就會向新的master看齊，丟棄掉腦裂期間客戶端提交的資料了。

（3）全同步複製。全同步複製則是必須每個從節點都給出ack應答才提交資料，這樣可以避免腦裂情況發生，因為當發生腦裂時舊master因為不能得不到所有從節點的ack應答，所以是不會處理客戶端的請求寫從而舊可以避免腦裂問題。但是它的問題是在於效能較低，因為需要全部副本的響應，如果其中一個節點響應較慢則會拖慢整體的提交時間。

分散式共識演算法

對於paxos、raft這類共識演算法來說，因為它採用的多數決的機制，在出現網路分割槽時，只會存在有一個大多數而不會同時出現兩個大多數。如果master位於網路分割槽後的少數派中，那這個master在接收到使用者請求後，由於與它連通的只有少數節點達不到超過一半節點的支援，因此它是無法提交資料的。只會由多數節點構成的叢集選舉出來的新master這一個master對外提供服務；如果master處於多數節點構成的叢集中，對於分隔出去的少數派節點構成的叢集中因為節點數量不超過一半，所以根本就選取不出來一個新master。因此對於共識演算法來說天然不會出現腦裂現象，相比於主從複製+ack的做法來說它能夠帶來更強的一致性保證。

分散式共識演算法核心優勢在於：

（1）容錯。因為其多數派的原則，在出現網路分割槽時，只要不要超過半數以上的節點不可用，整個共識系統仍然是滿足大多數原則的，仍然可以正常運轉，在可用性方面具備非常強的一個容錯能力。

（2）在強一致性的同時具備一定的效能優勢。相比於全同步複製而言，因為多數決的機制，每次commit並不需要全部的節點同意，因此效能上而言相比於全同步複製更具有優勢。

因為共識演算法它所帶來的強一致性保證和對叢集節點的超強的容錯能力，所以現在越來越多的分散式儲存系統在解決多副本一致性問題上都在使用共識演算法，比如new sql的tidb，內部就是基於raft演算法以及mysql自身也推出了MGR叢集，內部就是使用的mutil-paxos演算法取代傳統的半同步複製來解決多副本的一致性問題。

2.故障轉移

一般來說，對於引入第三方協調服務的儲存系統來說，會事先在叢集中選舉一個Master，此master並非我們所說的主從複製中的leader副本節點。以kafka為例，在Kafka叢集中這類節點稱之為Controller。當節點發生故障時，會由ZK將故障通知至Controller節點，此時觸發controller節點進行故障轉移。

按故障節點型別來說分為以下幾類：

（1）leader副本節點故障。當故障節點為某分片的leader副本節點時，則直接會由Controller負責為該分割槽重新選舉新的Leader副本；Controller在watch關於某leader副本節點故障後，則會直接從該leader副本節點的從節點列表中找到位移提交最大也就是資料最新的節點作為新的master。

（2）Controller節點故障。當故障節點為Controller自身時，則由藉助於ZK從叢集中的其他leader節點中選取一個新的controller節點。整個選舉過程本質上也是ZK的一次分散式鎖的搶佔過程。當controller產生時，會從ZK中拉取一份叢集元資料備份儲存到本地。同時一般來說Controller節點並不是單獨的物理節點例項，而是由叢集中某leader分片節點擔任。當controller節點故障時，同時也是leader副本節點故障，因此當新master產生後，同時還會為舊master節點的slave節點中選舉新的leader副本。

對於redis、ES這些在叢集內部實現自治的集群系統而言，則通常會在叢集內部實現選舉演算法，來實現故障轉移。

當叢集中某節點在發現半數以上的節點都認為某節點疑似下線後，會將該節點標記為確定下線並在叢集中進行廣播。當slave收到節點下線通知後，判斷如果是自己的master節點，則觸發選舉流程，開始進行故障轉移。

以redis為例其選舉演算法流程如下：

（1）slave收到master下線通知，開啟一個紀元，將currentEpoch+1，開啟選舉；

（2）slave計算髮起投票的延時時間。對於所有有資格參選的節點來說，並不會一收到選舉通知後立馬就開始發起選舉，而是會先延遲一段時間。其延時時間的計算基於當前slave複製的資料總量，如果總量越高比較資料越接近master，那麼它的延時時間會越短，被選中的概率也就越大。

（3）發起投票。slave在延時時間到期後，會向叢集廣播投票請求；

（4）投票。叢集中只有master節點具備投票權利，且在每個紀元中只有一次投票機會，master的投票原則是先到先得。當master收到投票請求後，會先基於自身的元資料審查該節點是否為故障節點的slave節點，如果是且當前還未給其他的slave節點投過票，則會將票投給該節點，因此理論上而言，資料越新的從節點獲得票數會越高；

（5）票數統計。每個節點在達到指定時間後會統計自身的票數，因為每個節點只能投一次票，所以得票超過一半以上的只會有一個節點。

（6）廣播通知。當該從節點發現自己得票一半以後，就會像整個叢集中廣播新master節點的訊息，讓其它節點都知道它已經是最新的主節點，其它的主節點在收到後會更新自己的節點表，從節點則會將它設為新的主節點，此時選舉結束。如果有一些從節點發現自己既沒有達到半數以上的投票，又在指定時間內沒有收到新master的訊息，則會開啟新的紀元，再次發起選票，但是此次其它的主節點發現如果直接的節點列表中該主節點的狀態不是fail狀態或者對該紀元已經進行過投票，不會再進行投票。