算法/協議

説下paxos算法

Paxos 有點類似 2PC，3PC，但比這兩種算法更加完善。在很多多大廠都得到了工程實踐，比如阿里的 OceanBase 的 分佈式數據庫， Google 的 chubby 分佈式鎖 。

Paxos算法是什麼？ Paxos 算法是 基於消息傳遞 且具有 高效容錯特性 的一致性算法，目前公認的解決 分佈式一致性問題 最有效的算法之一。

Paxos算法的工作流程？

在Paxos中有這麼幾個角色：

• Proposer（提議者） : 提議者提出提案，用於投票表決。
• Accecptor（接受者） : 對提案進行投票，並接受達成共識的提案。
• Learner（學習者） : 被告知投票的結果，接受達成共識的提案。
  在實際中，一個節點可以同時充當不同角色。

詳細可以看這篇文章：Paxos 算法詳解

描述一下 ZAB 協議

詳情請看ZAB協議

ZAB協議（Zookeeper Atomic Broadcast）是Zookeeper中用於實現分佈式一致性的協議。該協議旨在確保分佈式系統中的數據一致性和可靠性，並具有以下特點：

• 支持崩潰恢復：當Leader節點崩潰或因其他原因導致Leader缺失時，ZAB協議能夠自動進入崩潰恢復模式。在崩潰恢復模式中，系統會重新選舉一個新的Leader節點，並確保所有Follower節點的狀態與新Leader保持一致，之後繼續進行消息廣播。
• 原子性保證：ZAB協議確保每個事務請求的原子性，即每個事務要麼被所有節點成功執行，要麼在所有節點上失敗回滾，不會出現部分成功的情況。這是通過兩階段提交過程來實現的。
• 一致性保證：ZAB協議通過多副本同步和消息廣播機制，確保集羣中所有節點的數據副本在最終狀態下是一致的。即使在Leader崩潰或網絡分區等異常情況下，也能通過崩潰恢復機制來恢復一致性。

ZAB協議的執行過程包括三個階段：

1. 準備階段（Prepare）：Leader節點準備數據（即一個事務提案），併為其分配一個唯一的事務ID（zxid），然後通知所有Follower節點。
2. 提議階段（Proposal，有時也稱為確認階段，但這裏用提議階段更準確）：Follower節點接收Leader發送的提案和zxid，將其寫入本地日誌，並準備自己所在的服務（如更新內存狀態等）。然後，Follower節點回復一個確認消息（或稱為Ack消息）給Leader節點，表示已經接收到並處理了該提案。注意，這裏的“確認”是指Follower節點已經準備好處理該提案，而不是指提案已經被提交。
3. 提交階段（Commit，有時也稱為廣播階段，但這裏用提交階段更準確，因為廣播通常發生在準備和確認之後）：在收到足夠數量的Follower節點的確認消息後（通常是超過半數的Follower節點），Leader節點會廣播一個提交消息（Commit消息）給所有的Follower節點。這表示該提案已經被大多數節點接受，並被正式提交到各自的內存樹中執行。

如果在確認階段（或提議階段），Follower節點沒有收到Leader節點的任何消息（包括提案和可能的超時通知），並且無法與Leader節點建立通信，那麼這些Follower節點可能會認為Leader已經失效，並可能觸發崩潰恢復模式。

然而，崩潰恢復模式通常不是由單個Follower節點單獨觸發的。實際上，ZooKeeper集羣中的節點會通過一種稱為“選舉算法”的機制來共同決定何時進入崩潰恢復模式，並選舉出一個新的Leader節點。

ZAB 和 Paxos 算法的聯繫與區別

ZAB（ZooKeeper Atomic Broadcast）算法和Paxos算法都是分佈式系統中用於實現數據一致性的算法。

兩者的主要聯繫在於它們都採用了類似領導者的選舉機制，通過多數派的投票來保證系統的穩定性。在ZAB中，這體現在它使用了一種類似於Paxos的領導者選舉過程，其中有一個領導者（leader）來協調多個跟隨者（follower）的操作。而在Paxos中，一個提案需要被大多數的進程接受並返回結果，才能被確定。

兩者的區別在於它們的目標和實現方式不同：

• 目標：ZAB算法是為了構建一個高可用的分佈式數據主備系統（如ZooKeeper），而Paxos算法則是為了構建一個分佈式一致性狀態機系統。
• 實現方式：ZAB算法使用了消息廣播的方式來實現分佈式系統的協調，它要求每個消息都必須得到大多數節點的反饋才能確認，從而確保消息的一致性。同時，ZAB算法還引入了一個重要的概念，即消息的epoch，用來保證在領導者出現故障時，能夠正確地選擇新的領導者。Paxos算法則更加通用，它可以處理更廣泛的一致性問題，而不僅僅是消息廣播。然而，Paxos算法的實現較為複雜，因為它需要處理多種可能的情況，包括領導者故障、消息丟失等。

綜上所述，ZAB和Paxos的聯繫在於採用了領導者的選舉機制和多數派的投票原則，而區別在於它們的目標和實現方式不同。

CAP原則怎麼理解

CAP原則是由Eric Brewer提出的分佈式系統設計的基本定理。它指出在一個分佈式系統中，以下三個特性最多隻能同時滿足其中兩個：

• Consistency（一致性）：所有節點在同一時間具有相同的數據。
• Availability（可用性）：保證每個請求都會收到一個響應，無論響應成功或失敗。
• Partition Tolerance（分區容錯性）：分區容錯性表明系統能夠容忍網絡中的任意分區或節點失效。當網絡節點之間無法通信時，系統仍然必須正常運作。
  在實際應用中，由於網絡分區是不可避免的，所以在CAP中通常只能在C和A之間做出選擇。

為什麼CAP原則最多隻能同時滿足其中兩個？
假設有一個分佈式數據庫，分佈在兩個數據中心A和B。如果A和B之間的網絡連接斷開：

• 如果我們選擇保證一致性（C）和分區容錯性（P），那麼我們必須讓至少一個數據中心停止接受寫操作，以避免數據不一致，這就犧牲了可用性（A）。
• 如果我們選擇保證可用性（A）和分區容錯性（P），那麼兩個數據中心都可以繼續獨立工作，但可能會導致數據不一致，因此犧牲了一致性（C）。

怎麼理解BASE原則

BASE是對CAP中一致性和可用性權衡的結果，它的全稱是：

• Basically Available（基本可用）
• Soft state（軟狀態）
• Eventually consistent（最終一致性）

BASE原則是對CAP中AP的一個延伸，它的主要思想是：

• 基本可用：系統在出現故障時，保證核心可用，允許損失部分可用性。
• 軟狀態：允許系統中的數據存在中間狀態，並認為該狀態不會影響系統整體可用性。
• 最終一致性：系統中所有的數據副本，在經過一段時間後，最終能夠達到一致的狀態。

舉一個符合BASE原則場景例子：
在一個大型社交媒體平台上，用户可以在線更新他們的個人狀態（例如，發佈心情、描述活動等）。該平台有多個數據中心，分佈在不同的地理位置，以支持全球用户的低延遲訪問。為了能夠快速響應用户請求並保持高可用性，該平台選擇遵循BASE原則。

符合BASE原則的特徵：

1. 基本可用（Basically Available）： 在這個系統中，即使有部分數據中心出現故障，其他數據中心依然可以處理用户的狀態更新和查看請求。 用户可以不間斷地繼續發佈狀態，而不需要等待所有數據中心同步完成。
2. 軟狀態（Soft state）： 用户發佈的狀態信息在傳播過程中，允許在短時間內不同數據中心的數據有所不同。 不一致被認為是暫時的，並且在最終一致性（eventual consistency）下會得到解決。
3. 最終一致性（Eventually Consistent）： 雖然在某個時間點，不同的數據中心可能會顯示出不同的用户狀態，但是隨着時間的推移，通過後台的同步和合並機制，所有數據中心最終會達到一致的狀態。 系統可能使用異步複製來慢慢將所有數據中心的數據同步一致。

BASE原則是對CAP中一致性和可用性權衡的結果，它通過犧牲強一致性來獲得可用性，並允許數據在一段時間內是不一致的，但最終達到一致狀態。

在Java分佈式系統開發中，我們經常需要根據具體業務需求來選擇適合的原則。例如：

• 對於需要強一致性的場景（如銀行交易），可能更傾向於選擇CP（一致性和分區容錯性）。
• 對於可以容忍短期不一致，但需要高可用的場景（如社交網絡的點贊功能），可能更適合選擇AP（可用性和分區容錯性）並遵循BASE原則。

在實際應用中，我們可能會使用各種技術和框架來實現這些原則，如分佈式事務、最終一致性等。理解這些原則對於設計可靠的分佈式系統至關重要。

説下Raft算法

Raft 也是一個 一致性算法，和 Paxos 目標相同。但它還有另一個名字 - 易於理解的一致性算法。Paxos 和 Raft 都是為了實現 一致性 產生的。這個過程如同選舉一樣，參選者 需要説服 大多數選民 (Server) 投票給他，一旦選定後就跟隨其操作。Paxos 和 Raft 的區別在於選舉的 具體過程 不同。

Raft算法的工作流程？

Raft 協議將 Server 進程分為三種角色：

• Leader（領導者）
• Follower（跟隨者）
• Candidate（候選人）

就像一個民主社會，領導者由跟隨者投票選出。剛開始沒有 領導者，所有集羣中的 參與者 都是 跟隨者。

那麼首先開啓一輪大選。在大選期間 所有跟隨者 都能參與競選，這時所有跟隨者的角色就變成了 候選人，民主投票選出領袖後就開始了這屆領袖的任期，然後選舉結束，所有除 領導者 的 候選人 又變回 跟隨者 服從領導者領導。

這裏提到一個概念 「任期」，用術語 Term 表達。

Leader選舉過程

Raft 使用心跳（heartbeat）觸發Leader選舉。當Server啓動時，初始化為Follower。Leader向所有Followers週期性發送heartbeat。如果Follower在選舉超時時間內沒有收到Leader的heartbeat，就會等待一段隨機的時間後發起一次Leader選舉。

Follower將其當前term加一然後轉換為Candidate。它首先給自己投票並且給集羣中的其他服務器發送 RequestVote RPC 。結果有以下三種情況：

• 贏得了多數（超過1/2）的選票，成功選舉為Leader；
• 收到了Leader的消息，表示有其它服務器已經搶先當選了Leader；
• 沒有Server贏得多數的選票，Leader選舉失敗，等待選舉時間超時（Election Timeout）後發起下一次選舉。

選出 Leader 後，Leader 通過 定期 向所有 Follower 發送 心跳信息 維持其統治。若 Follower 一段時間未收到 Leader 的 心跳，則認為 Leader 可能已經掛了，然後再次發起 選舉 過程。

什麼是分佈式系統

一個系統 各組件分別部署在不同服務器。彼此通過網絡通信和協調的系統。

• 可以指多個不同組件分佈在網絡上互相協作，比如説電商網站
• 也可以一個組件的多個副本組成集羣，互相協作如同一個組件，比如數據存儲服務中為了數據不丟失而採取的多個服務備份冗餘，當數據修改時也需要通信來複制數據

分佈式最早出現的目地首先是解決單點問題，避免單點故障，然後解決了性能問題。

什麼是分佈式事務

分佈式事務是相對本地事務而言的，對於本地事務，利用數據庫本身的事務機制，就可以保證事務的ACID特性。

而在分佈式環境下，會涉及到多個數據庫。

分佈式事務其實就是將對同一庫事務的概念擴大到了對多個庫的事務。目的是為了保證分佈式系統中的數據一致性。

分佈式事務處理的關鍵是：

• 需要記錄事務在任何節點所做的所有動作；
• 事務進行的所有操作要麼全部提交，要麼全部回滾。

分佈式事務有哪些常見的實現方案

詳情可以看分佈式事務實現方案

有哪些分佈式鎖的實現方案

一般需要使用分佈式鎖的場景如下：

• 效率：使用分佈式鎖可以避免不同節點重複相同的工作，比如避免重複執行定時任務等；
• 正確性：使用分佈式鎖同樣可以避免破壞數據正確性，如果兩個節點在同一條數據上面操作，可能會出現併發問題。

分佈式鎖特點

一個完善的分佈式鎖需要滿足以下特點：

• 互斥性：互斥是所得基本特性，分佈式鎖需要按需求保證線程或節點級別的互斥。；
• 可重入性：同一個節點或同一個線程獲取鎖，可以再次重入獲取這個鎖；
• 鎖超時：支持鎖超時釋放，防止某個節點不可用後，持有的鎖無法釋放；
• 高效性：加鎖和解鎖的效率高，可以支持高併發；
• 高可用：需要有高可用機制預防鎖服務不可用的情況，如增加降級；
• 阻塞性：支持阻塞獲取鎖和非阻塞獲取鎖兩種方式；
• 公平性：支持公平鎖和非公平鎖兩種類型的鎖，公平鎖可以保證安裝請求鎖的順序獲取鎖，而非公平鎖不可以。

分佈式鎖常見的實現有三種實現：

• 基於數據庫的分佈式鎖；
• 基於Redis的分佈式鎖；
• 基於Zookeeper的分佈式鎖。

基於數據庫的分佈式鎖

用數據庫實現分佈式鎖比較簡單，就是創建一張鎖表，數據庫對字段作唯一性約束。

加鎖的時候，在鎖表中增加一條記錄即可；釋放鎖的時候刪除記錄就行。

如果有併發請求同時提交到數據庫，數據庫會保證只有一個請求能夠得到鎖。

這種屬於數據庫 IO 操作，效率不高，而且頻繁操作會增大數據庫的開銷，因此這種方式在高併發、高性能的場景中用的不多。

上面列舉出了分佈式鎖需要滿足的特點，使用數據庫實現分佈式鎖也需要滿足這些特點，下面我們來一一介紹實現方法：

• 互斥性：通過數據庫update的原子性達到兩次獲取鎖之間的互斥性；
• 可重入性：在數據庫中保留一個字段存儲當前鎖的持有者；
• 鎖超時：在數據庫中存儲鎖的獲取時間點和超時時長；
• 高效性：數據庫本身可以支持比較高的併發；
• 高可用：可以增加主從數據庫邏輯，提升數據庫的可用性；
• 阻塞性：可以通過看門狗輪詢的方式實現線程的阻塞；
• 公平性：可以添加鎖隊列，不過不建議，實現起來比較複雜。

數據庫的表名為lock，各個字段的定義如下所示：

獲取鎖的SQL語句 ：獲取鎖的SQL語句分不同的情況，如果鎖不存在，那麼首先需要創建鎖，並且創建鎖的線程可以獲取鎖：

insert into lock(lock_key,lock_time,lock_duration,lock_owner,locked) values ('xxx',now(),1000,'ownerxxx',true)

如果鎖已經存在，那麼就嘗試更新鎖的信息，如果更新成功則表示獲取鎖成功，更新失敗則表示獲取鎖失敗。

update lock set
	locked = true,
	lock_owner = 'ownerxxxx',
	lock_time = now(),
	lock_duration = 1000
where
	lock_key='xxx' and(
	lock_owner = 'ownerxxxx' or
	locked = false or
	date_add(lock_time, interval lock_duration second) > now())

釋放鎖的SQL語句 當用户使用完鎖需要釋放的時候，可以直接更新locked標識位為false。

update lock set
	locked = false,
where
	lock_key='xxx' and
	lock_owner = 'ownerxxxx' and
	locked = true

看門狗

通過上面的步驟，可以實現獲取鎖和釋放鎖，那麼看門狗又是做什麼的呢？

想象一下，如果用户獲取鎖到釋放鎖之間的時間大於鎖的超時時間，是不是會有問題？是不是可能會出現多個節點同時獲取鎖的情況？這個時候就需要看門狗了，看門狗可以通過定時任務不斷刷新鎖的獲取事件，從而在用户獲取鎖到釋放鎖期間保持一直持有鎖。

基於Redis的分佈式鎖

Redis的Java客户端Redisson實現了分佈式鎖，我們可以通過類似ReentrantLock的加鎖-釋放鎖的邏輯來實現分佈式鎖。

詳情可以看redis實現分佈式鎖

基於Zookeeper的分佈式鎖

Zookeeper實現的分佈式鎖適用於引入Zookeeper的服務

詳情可以看zk實現分佈式鎖

三種鎖的優缺點

基於數據庫的分佈式鎖：

• 數據庫併發性能較差；
• 阻塞式鎖實現比較複雜；
• 公平鎖實現比較複雜。

基於Redis的分佈式鎖：

• 主從切換的情況下可能出現多客户端獲取鎖的情況；
• Lua腳本在單機上具有原子性，主從同步時不具有原子性。

基於Zookeeper的分佈式鎖：

• 需要引入Zookeeper集羣，比較重量級；
• 分佈式鎖的可重入粒度只能是節點級別；

瞭解哪些限流算法

詳情可以看請求限流算法

• 計數器

計數器比較簡單粗暴，比如我們要限制1s能夠通過的請求數，實現的思路就是從第一個請求進來開始計時，在接下來的1s內，每個請求進來請求數就+1，超過最大請求數的請求會被拒絕，等到1s結束後計數清零，重新開始計數。

這種方式有個很大的弊端：比如前10ms已經通過了最大的請求數，那麼後面的990ms的請求只能拒絕，這種現象叫做“突刺現象”。

• 漏桶算法

就是桶底出水的速度恆定，進水的速度可能快慢不一，但是當進水量大於出水量的時候，水會被裝在桶裏，不會直接被丟棄；但是桶也是有容量限制的，當桶裝滿水後溢出的部分還是會被丟棄的。

算法實現：可以準備一個隊列來保存暫時處理不了的請求，然後通過一個線程池定期從隊列中獲取請求來執行。

• 令牌桶算法

令牌桶就是生產訪問令牌的一個地方，生產的速度恆定，用户訪問的時候當桶中有令牌時就可以訪問，否則將觸發限流。

實現方案：Guava RateLimiter是一個谷歌提供的限流，其基於令牌桶算法，比較適用於單實例的系統。

説説什麼是冪等性

詳情可以看冪等性

你瞭解時間輪(Time Wheel)嗎?有哪些應用場景?

時間輪(Time Wheel)是一種用於管理和調度大量定時任務的數據結構。它是一種高效的定時任務調度算法，主要用於優化任務調度的效率，特別是在需要處理大量定時任務時。時間輪是一種環形的數據結構，通過將時間劃分為若干個時間片(槽)，每個時間片負責管理一定時間段(如秒、分鐘等內
的任務。

工作原理：

• 時間輪的中心是一個環形結構，每個槽表示一個時間段。當時間輪的指針移動到某個槽時，該槽中的任務會被執行。
• 任務被插入到特定的槽中，根據任務的延遲時間確定插入的位置。
• 時間輪以固定的時間步長(如秒)推進，每次推進一個時間單位，執行相應中的任務

應用場景

• 高效的定時任務調度：在需要處理大量定時任務的場景，如高併發的定時任務系統，時間輪可以有效地減少任務調度的開銷。
• 網絡服務器：在網絡服務器中，時間輪常用於實現定時操作，如連接超時、請求超時等。
• 分佈式系統：在分佈式系統中，時間輪可以用於協調不同節點的定時任務，優化任務調度和超時處理

實際應用示例:

• Netty：Netty 是一個高性能的網絡框架，它使用時間輪來管理定時任務，如超時處理和定時操作。
• Guava：Google 的 Guava 庫中也有時間輪的實現，用於優化定時任務調度的性能。
• Caffine Cache：這個高性能本地緩存庫中也有時間輪的實現，即 TimerWheel。