分布式理論

1. 說說CAP原則？

CAP原則又稱CAP定理，指的是在一個分布式系統(tǒng)中，Consistency（一致性）、 Availability（可用性）、Partition tolerance（分區(qū)容錯性）這3個基本需求，最多只能同時滿足其中的2個。

CAP原則

2. 為什么CAP不可兼得呢？

首先對于分布式系統(tǒng)，分區(qū)是必然存在的，所謂分區(qū)指的是分布式系統(tǒng)可能出現(xiàn)的字區(qū)域網(wǎng)絡不通，成為孤立區(qū)域的的情況。

分區(qū)

那么分區(qū)容錯性（P）就必須要滿足，因為如果要犧牲分區(qū)容錯性，就得把服務和資源放到一個機器，或者一個“同生共死”的集群，那就違背了分布式的初衷。那么滿足分區(qū)容錯的基礎上，能不能同時滿足一致性和可用性？假如現(xiàn)在有兩個分區(qū)N1和N2，N1和N2分別有不同的分區(qū)存儲D1和D2，以及不同的服務S1和S2。

在滿足一致性 的時候，N1和N2的數(shù)據(jù)要求值一樣的，D1=D2。

在滿足可用性的時候，無論訪問N1還是N2，都能獲取及時的響應。

分區(qū)的服務

假如現(xiàn)在有這樣的場景：

用戶訪問了N1，修改了D1的數(shù)據(jù)。

用戶再次訪問，請求落在了N2。此時D1和D2的數(shù)據(jù)不一致。

接下來：

保證一致性：此時D1和D2數(shù)據(jù)不一致，要保證一致性就不能返回不一致的數(shù)據(jù)，可用性無法保證。

保證可用性：立即響應，可用性得到了保證，但是此時響應的數(shù)據(jù)和D1不一致，一致性無法保證。

所以，可以看出，分區(qū)容錯的前提下，一致性和可用性是矛盾的。

3. CAP對應的模型和應用？

CA without P理論上放棄P（分區(qū)容錯性），則C（強一致性）和A（可用性）是可以保證的。實際上分區(qū)是不可避免的，嚴格上CA指的是允許分區(qū)后各子系統(tǒng)依然保持CA。CA模型的常見應用：

集群數(shù)據(jù)庫

xFS文件系統(tǒng)

CP without A放棄A（可用），相當于每個請求都需要在Server之間強一致，而P（分區(qū)）會導致同步時間無限延長，如此CP也是可以保證的。很多傳統(tǒng)的數(shù)據(jù)庫分布式事務都屬于這種模式。CP模型的常見應用：

分布式數(shù)據(jù)庫

分布式鎖

AP wihtout C要高可用并允許分區(qū)，則需放棄一致性。一旦分區(qū)發(fā)生，節(jié)點之間可能會失去聯(lián)系，為了高可用，每個節(jié)點只能用本地數(shù)據(jù)提供服務，而這樣會導致全局數(shù)據(jù)的不一致性。現(xiàn)在眾多的NoSQL都屬于此類。AP模型常見應用：

Web緩存

DNS

舉個大家更熟悉的例子，像我們熟悉的注冊中心ZooKeeper、Eureka、Nacos中：

ZooKeeper 保證的是 CP

Eureka 保證的則是 AP

Nacos 不僅支持 CP 也支持 AP

4. BASE理論了解嗎？

BASE（Basically Available、Soft state、Eventual consistency）是基于CAP理論逐步演化而來的，核心思想是即便不能達到強一致性（Strong consistency），也可以根據(jù)應用特點采用適當?shù)姆绞絹磉_到最終一致性（Eventual consistency）的效果。

BASE的主要含義：

Basically Available（基本可用）

什么是基本可用呢？假設系統(tǒng)出現(xiàn)了不可預知的故障，但還是能用，只是相比較正常的系統(tǒng)而言，可能會有響應時間上的損失，或者功能上的降級。

Soft State（軟狀態(tài)）

什么是硬狀態(tài)呢？要求多個節(jié)點的數(shù)據(jù)副本都是一致的，這是一種“硬狀態(tài)”。軟狀態(tài)也稱為弱狀態(tài)，相比較硬狀態(tài)而言，允許系統(tǒng)中的數(shù)據(jù)存在中間狀態(tài)，并認為該狀態(tài)不影響系統(tǒng)的整體可用性，即允許系統(tǒng)在多個不同節(jié)點的數(shù)據(jù)副本存在數(shù)據(jù)延時。

Eventually Consistent（最終一致性）

上面說了軟狀態(tài)，但是不應該一直都是軟狀態(tài)。在一定時間后，應該到達一個最終的狀態(tài)，保證所有副本保持數(shù)據(jù)一致性，從而達到數(shù)據(jù)的最終一致性。這個時間取決于網(wǎng)絡延時、系統(tǒng)負載、數(shù)據(jù)復制方案設計等等因素。

分布式鎖

單體時代，可以直接用本地鎖來實現(xiàn)對競爭資源的加鎖，分布式環(huán)境下就要用到分布式鎖了。

5. 有哪些分布式鎖的實現(xiàn)方案呢？

常見的分布式鎖實現(xiàn)方案有三種：MySQL分布式鎖、ZooKepper分布式鎖、Redis分布式鎖。

分布式鎖

5.1 MySQL分布式鎖如何實現(xiàn)呢？

用數(shù)據(jù)庫實現(xiàn)分布式鎖比較簡單，就是創(chuàng)建一張鎖表，數(shù)據(jù)庫對字段作唯一性約束。加鎖的時候，在鎖表中增加一條記錄即可；釋放鎖的時候刪除記錄就行。如果有并發(fā)請求同時提交到數(shù)據(jù)庫，數(shù)據(jù)庫會保證只有一個請求能夠得到鎖。這種屬于數(shù)據(jù)庫 IO 操作，效率不高，而且頻繁操作會增大數(shù)據(jù)庫的開銷，因此這種方式在高并發(fā)、高性能的場景中用的不多。

5.2 ZooKeeper如何實現(xiàn)分布式鎖？

ZooKeeper也是常見分布式鎖實現(xiàn)方法。ZooKeeper的數(shù)據(jù)節(jié)點和文件目錄類似，例如有一個lock節(jié)點，在此節(jié)點下建立子節(jié)點是可以保證先后順序的，即便是兩個進程同時申請新建節(jié)點，也會按照先后順序建立兩個節(jié)點。

ZooKeeper如何實現(xiàn)分布式鎖

所以我們可以用此特性實現(xiàn)分布式鎖。以某個資源為目錄，然后這個目錄下面的節(jié)點就是我們需要獲取鎖的客戶端，每個服務在目錄下創(chuàng)建節(jié)點，如果它的節(jié)點，序號在目錄下最小，那么就獲取到鎖，否則等待。釋放鎖，就是刪除服務創(chuàng)建的節(jié)點。ZK實際上是一個比較重的分布式組件，實際上應用沒那么多了，所以用ZK實現(xiàn)分布式鎖，其實相對也比較少。

5.3 Redis怎么實現(xiàn)分布式鎖？

Redis實現(xiàn)分布式鎖，是當前應用最廣泛的分布式鎖實現(xiàn)方式。Redis執(zhí)行命令是單線程的，Redis實現(xiàn)分布式鎖就是利用這個特性。實現(xiàn)分布式鎖最簡單的一個命令：setNx(set if not exist)，如果不存在則更新：

setNx?resourceName?value??

加鎖了之后如果機器宕機，那我這個鎖就無法釋放，所以需要加入過期時間，而且過期時間需要和setNx同一個原子操作，在Redis2.8之前需要用lua腳本，但是redis2.8之后redis支持nx和ex操作是同一原子操作。

Redission

當然，一般生產(chǎn)中都是使用Redission客戶端，非常良好地封裝了分布式鎖的api，而且支持RedLock。

分布式事務

6.什么是分布式事務?

分布式事務是相對本地事務而言的，對于本地事務，利用數(shù)據(jù)庫本身的事務機制，就可以保證事務的ACID特性。

ACID

而在分布式環(huán)境下，會涉及到多個數(shù)據(jù)庫。

多數(shù)據(jù)庫

分布式事務其實就是將對同一庫事務的概念擴大到了對多個庫的事務。目的是為了保證分布式系統(tǒng)中的數(shù)據(jù)一致性。分布式事務處理的關鍵是：

需要記錄事務在任何節(jié)點所做的所有動作；

事務進行的所有操作要么全部提交，要么全部回滾。

7.分布式事務有哪些常見的實現(xiàn)方案？

分布式常見的實現(xiàn)方案有 2PC、3PC、TCC、本地消息表、MQ消息事務、最大努力通知、SAGA事務 等等。

7.1 說說2PC兩階段提交？

說到2PC，就不得先說分布式事務中的 XA 協(xié)議。在這個協(xié)議里，有三個角色：

AP（Application）：應用系統(tǒng)（服務）

TM（Transaction Manager）：事務管理器（全局事務管理）

RM（Resource Manager）：資源管理器（數(shù)據(jù)庫）

XA協(xié)議

XA協(xié)議采用兩階段提交方式來管理分布式事務。XA接口提供資源管理器與事務管理器之間進行通信的標準接口。兩階段提交的思路可以概括為：參與者將操作成敗通知協(xié)調(diào)者，再由協(xié)調(diào)者根據(jù)所有參與者的反饋情況決定各參與者是否要提交操作還是回滾操作。

2PC

準備階段：事務管理器要求每個涉及到事務的數(shù)據(jù)庫預提交(precommit)此操作，并反映是否可以提交

提交階段：事務協(xié)調(diào)器要求每個數(shù)據(jù)庫提交數(shù)據(jù)，或者回滾數(shù)據(jù)。

優(yōu)點：盡量保證了數(shù)據(jù)的強一致，實現(xiàn)成本較低，在各大主流數(shù)據(jù)庫都有自己實現(xiàn)，對于MySQL是從5.5開始支持。缺點:

單點問題：事務管理器在整個流程中扮演的角色很關鍵，如果其宕機，比如在第一階段已經(jīng)完成，在第二階段正準備提交的時候事務管理器宕機，資源管理器就會一直阻塞，導致數(shù)據(jù)庫無法使用。

同步阻塞：在準備就緒之后，資源管理器中的資源一直處于阻塞，直到提交完成，釋放資源。

數(shù)據(jù)不一致：兩階段提交協(xié)議雖然為分布式數(shù)據(jù)強一致性所設計，但仍然存在數(shù)據(jù)不一致性的可能，比如在第二階段中，假設協(xié)調(diào)者發(fā)出了事務commit的通知，但是因為網(wǎng)絡問題該通知僅被一部分參與者所收到并執(zhí)行了commit操作，其余的參與者則因為沒有收到通知一直處于阻塞狀態(tài)，這時候就產(chǎn)生了數(shù)據(jù)的不一致性。

7.2 3PC（三階段提交）了解嗎？

三階段提交（3PC）是二階段提交（2PC）的一種改進版本 ，為解決兩階段提交協(xié)議的單點故障和同步阻塞問題。三階段提交有這么三個階段：CanCommit，PreCommit，DoCommit三個階段

3PC

CanCommit：準備階段。協(xié)調(diào)者向參與者發(fā)送commit請求，參與者如果可以提交就返回Yes響應，否則返回No響應。

PreCommit：預提交階段。協(xié)調(diào)者根據(jù)參與者在準備階段的響應判斷是否執(zhí)行事務還是中斷事務，參與者執(zhí)行完操作之后返回ACK響應，同時開始等待最終指令。

DoCommit：提交階段。協(xié)調(diào)者根據(jù)參與者在準備階段的響應判斷是否執(zhí)行事務還是中斷事務：

如果所有參與者都返回正確的ACK響應，則提交事務

如果參與者有一個或多個參與者收到錯誤的ACK響應或者超時，則中斷事務

如果參與者無法及時接收到來自協(xié)調(diào)者的提交或者中斷事務請求時，在等待超時之后，會繼續(xù)進行事務提交

可以看出，三階段提交解決的只是兩階段提交中單體故障和同步阻塞的問題，因為加入了超時機制，這里的超時的機制作用于 預提交階段 和 提交階段。如果等待 預提交請求 超時，參與者直接回到準備階段之前。如果等到提交請求超時，那參與者就會提交事務了。無論是2PC還是3PC都不能保證分布式系統(tǒng)中的數(shù)據(jù)100%一致。

7.3 TCC了解嗎？

TCC（Try Confirm Cancel） ，是兩階段提交的一個變種，針對每個操作，都需要有一個其對應的確認和取消操作，當操作成功時調(diào)用確認操作，當操作失敗時調(diào)用取消操作，類似于二階段提交，只不過是這里的提交和回滾是針對業(yè)務上的，所以基于TCC實現(xiàn)的分布式事務也可以看做是對業(yè)務的一種補償機制。

TCC下單減庫存

Try：嘗試待執(zhí)行的業(yè)務。訂單系統(tǒng)將當前訂單狀態(tài)設置為支付中，庫存系統(tǒng)校驗當前剩余庫存數(shù)量是否大于1，然后將可用庫存數(shù)量設置為庫存剩余數(shù)量-1，。

Confirm：確認執(zhí)行業(yè)務，如果Try階段執(zhí)行成功，接著執(zhí)行Confirm 階段，將訂單狀態(tài)修改為支付成功，庫存剩余數(shù)量修改為可用庫存數(shù)量。

Cancel：取消待執(zhí)行的業(yè)務，如果Try階段執(zhí)行失敗，執(zhí)行Cancel 階段，將訂單狀態(tài)修改為支付失敗，可用庫存數(shù)量修改為庫存剩余數(shù)量。

TCC 是業(yè)務層面的分布式事務，保證最終一致性，不會一直持有資源的鎖。

優(yōu)點： 把數(shù)據(jù)庫層的二階段提交交給應用層來實現(xiàn)，規(guī)避了數(shù)據(jù)庫的 2PC 性能低下問題

缺點：TCC 的 Try、Confirm 和 Cancel 操作功能需業(yè)務提供，開發(fā)成本高。TCC 對業(yè)務的侵入較大和業(yè)務緊耦合，需要根據(jù)特定的場景和業(yè)務邏輯來設計相應的操作

7.4 本地消息表了解嗎？

本地消息表的核心思想是將分布式事務拆分成本地事務進行處理。例如，可以在訂單庫新增一個消息表，將新增訂單和新增消息放到一個事務里完成，然后通過輪詢的方式去查詢消息表，將消息推送到MQ，庫存服務去消費MQ。

本地消息表

執(zhí)行流程：

訂單服務，添加一條訂單和一條消息，在一個事務里提交

訂單服務，使用定時任務輪詢查詢狀態(tài)為未同步的消息表，發(fā)送到MQ，如果發(fā)送失敗，就重試發(fā)送

庫存服務，接收MQ消息，修改庫存表，需要保證冪等操作

如果修改成功，調(diào)用rpc接口修改訂單系統(tǒng)消息表的狀態(tài)為已完成或者直接刪除這條消息

如果修改失敗，可以不做處理，等待重試

訂單服務中的消息有可能由于業(yè)務問題會一直重復發(fā)送，所以為了避免這種情況可以記錄一下發(fā)送次數(shù)，當達到次數(shù)限制之后報警，人工接入處理；庫存服務需要保證冪等，避免同一條消息被多次消費造成數(shù)據(jù)不一致。本地消息表這種方案實現(xiàn)了最終一致性，需要在業(yè)務系統(tǒng)里增加消息表，業(yè)務邏輯中多一次插入的DB操作，所以性能會有損耗，而且最終一致性的間隔主要有定時任務的間隔時間決定

7.5 MQ消息事務了解嗎？

消息事務的原理是將兩個事務通過消息中間件進行異步解耦。訂單服務執(zhí)行自己的本地事務，并發(fā)送MQ消息，庫存服務接收消息，執(zhí)行自己的本地事務，乍一看，好像跟本地消息表的實現(xiàn)方案類似，只是省去 了對本地消息表的操作和輪詢發(fā)送MQ的操作，但實際上兩種方案的實現(xiàn)是不一樣的。消息事務一定要保證業(yè)務操作與消息發(fā)送的一致性，如果業(yè)務操作成功，這條消息也一定投遞成功。

MQ消息事務

執(zhí)行流程：

發(fā)送prepare消息到消息中間件

發(fā)送成功后，執(zhí)行本地事務

如果事務執(zhí)行成功，則commit，消息中間件將消息下發(fā)至消費端

如果事務執(zhí)行失敗，則回滾，消息中間件將這條prepare消息刪除

消費端接收到消息進行消費，如果消費失敗，則不斷重試

消息事務依賴于消息中間件的事務消息，例如我們熟悉的RocketMQ就支持事務消息（半消息），也就是只有收到發(fā)送方確定才會正常投遞的消息。這種方案也是實現(xiàn)了最終一致性，對比本地消息表實現(xiàn)方案，不需要再建消息表，對性能的損耗和業(yè)務的入侵更小。

7.6 最大努力通知了解嗎？

最大努力通知相比實現(xiàn)會簡單一些，適用于一些對最終一致性實時性要求沒那么高的業(yè)務，比如支付通知，短信通知。以支付通知為例，業(yè)務系統(tǒng)調(diào)用支付平臺進行支付，支付平臺進行支付，進行操作支付之后支付平臺會去同步通知業(yè)務系統(tǒng)支付操作是否成功，如果不成功，會一直異步重試，但是會有一個最大通知次數(shù)，如果超過這個次數(shù)后還是通知失敗，就不再通知，業(yè)務系統(tǒng)自行調(diào)用支付平臺提供一個查詢接口，供業(yè)務系統(tǒng)進行查詢支付操作是否成功。

最大努力通知

執(zhí)行流程：

業(yè)務系統(tǒng)調(diào)用支付平臺支付接口， 并在本地進行記錄，支付狀態(tài)為支付中

支付平臺進行支付操作之后，無論成功還是失敗，同步給業(yè)務系統(tǒng)一個結(jié)果通知

如果通知一直失敗則根據(jù)重試規(guī)則異步進行重試，達到最大通知次數(shù)后，不再通知

支付平臺提供查詢訂單支付操作結(jié)果接口

業(yè)務系統(tǒng)根據(jù)一定業(yè)務規(guī)則去支付平臺查詢支付結(jié)果

8.你們用什么？能說一下Seata嗎？

我們用比較常用的是Seata——自己去實現(xiàn)分布式事務調(diào)度還是比較麻煩的。Seata 的設計目標是對業(yè)務無侵入，因此它是從業(yè)務無侵入的兩階段提交（全局事務）著手，在傳統(tǒng)的兩階段上進行改進，他把一個分布式事務理解成一個包含了若干分支事務的全局事務。而全局事務的職責是協(xié)調(diào)它管理的分支事務達成一致性，要么一起成功提交，要么一起失敗回滾。也就是一榮俱榮一損俱損~

全局事務和分支事務

Seata 中存在這么幾種重要角色：

TC（Transaction Coordinator）：事務協(xié)調(diào)者。管理全局的分支事務的狀態(tài)，用于全局性事務的提交和回滾。

TM（Transaction Manager）：事務管理者。用于開啟、提交或回滾事務。

RM（Resource Manager）：資源管理器。用于分支事務上的資源管理，向 TC 注冊分支事務，上報分支事務的狀態(tài)，接收 TC 的命令來提交或者回滾分支事務。

Seata工作流程

S'eata整體執(zhí)行流程：

服務A中的 TM 向 TC 申請開啟一個全局事務，TC 就會創(chuàng)建一個全局事務并返回一個唯一的 XID

服務A中的 RM 向 TC 注冊分支事務，然后將這個分支事務納入 XID 對應的全局事務管轄中

服務A開始執(zhí)行分支事務

服務A開始遠程調(diào)用B服務，此時 XID 會根據(jù)調(diào)用鏈傳播

服務B中的 RM 也向 TC 注冊分支事務，然后將這個分支事務納入 XID 對應的全局事務管轄中

服務B開始執(zhí)行分支事務

全局事務調(diào)用處理結(jié)束后，TM 會根據(jù)有誤異常情況，向 TC 發(fā)起全局事務的提交或回滾

TC 協(xié)調(diào)其管轄之下的所有分支事務，決定是提交還是回滾

分布式一致性算法

9.分布式算法paxos了解么 ？

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

Paxos算法是什么？

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

Paxos算法的工作流程？

角色

在Paxos中有這么幾個角色：

Proposer（提議者） : 提議者提出提案，用于投票表決。

Accecptor（接受者） : 對提案進行投票，并接受達成共識的提案。

Learner（學習者） : 被告知投票的結(jié)果，接受達成共識的提案。

在實際中，一個節(jié)點可以同時充當不同角色。

Paxos的三種角色

提議者提出提案，提案=編號+value，可以表示為[M,V]，每個提案都有唯一編號，而且編號的大小是趨勢遞增的。

算法流程

Paxos算法包含兩個階段，第一階段**Prepare(準備)、第二階段Accept(接受)**。

Paxos算法流程

Prepare(準備)階段

提議者提議一個新的提案 P[Mn,?]，然后向接受者的某個超過半數(shù)的子集成員發(fā)送編號為Mn的準備請求

如果一個接受者收到一個編號為Mn的準備請求，并且編號Mn大于它已經(jīng)響應的所有準備請求的編號，那么它就會將它已經(jīng)批準過的最大編號的提案作為響應反饋給提議者，同時該接受者會承諾不會再批準任何編號小于Mn的提案。

總結(jié)一下，接受者在收到提案后，會給與提議者兩個承諾與一個應答：

兩個承諾：

承諾不會再接受提案號小于或等于 Mn 的 Prepare 請求

承諾不會再接受提案號小于Mn 的 Accept 請求

一個應答：

不違背以前作出的承諾的前提下，回復已經(jīng)通過的提案中提案號最大的那個提案所設定的值和提案號Mmax，如果這個值從來沒有被任何提案設定過，則返回空值。如果不滿足已經(jīng)做出的承諾，即收到的提案號并不是決策節(jié)點收到過的最大的，那允許直接對此 Prepare 請求不予理會。

Accept(接受)階段

如果提議者收到來自半數(shù)以上的接受者對于它發(fā)出的編號為Mn的準備請求的響應，那么它就會發(fā)送一個針對[Mn,Vn]的接受請求給接受者，注意Vn的值就是收到的響應中編號最大的提案的值，如果響應中不包含任何提案，那么它可以隨意選定一個值。

如果接受者收到這個針對[Mn,Vn]提案的接受請求，只要該接受者尚未對編號大于Mn的準備請求做出響應，它就可以通過這個提案。

當提議者收到了多數(shù)接受者的接受應答后，協(xié)商結(jié)束，共識決議形成，將形成的決議發(fā)送給所有學習節(jié)點進行學習。所以Paxos算法的整體詳細流程如下：

Paxos詳細流程

算法的流程模擬，可以查看參考[13]。

Paxos算法有什么缺點嗎？怎么優(yōu)化？

前面描述的可以稱之為Basic Paxos 算法，在單提議者的前提下是沒有問題的，但是假如有多個提議者互不相讓，那么就可能導致整個提議的過程進入了死循環(huán)。Lamport 提出了 Multi Paxos 的算法思想。Multi Paxos算法思想，簡單說就是在多個提議者的情況下，選出一個Leader（領導者），由領導者作為唯一的提議者，這樣就可以解決提議者沖突的問題。

10.說說Raft算法？

Raft算法是什么？

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

Raft算法的工作流程？

Raft算法的角色

Raft 協(xié)議將 Server 進程分為三種角色：

Leader（領導者）

Follower（跟隨者）

Candidate（候選人）

就像一個民主社會，領導者由跟隨者投票選出。剛開始沒有 領導者，所有集群中的 參與者 都是 跟隨者。那么首先開啟一輪大選。在大選期間 所有跟隨者 都能參與競選，這時所有跟隨者的角色就變成了 候選人，民主投票選出領袖后就開始了這屆領袖的任期，然后選舉結(jié)束，所有除 領導者 的 候選人 又變回 跟隨者 服從領導者領導。這里提到一個概念 「任期」，用術語 Term 表達。三類角色的變遷圖如下：

Raft三種角色變遷圖

Leader選舉過程

Raft 使用心跳（heartbeat）觸發(fā)Leader選舉。當Server啟動時，初始化為Follower。Leader向所有Followers周期性發(fā)送heartbeat。如果Follower在選舉超時時間內(nèi)沒有收到Leader的heartbeat，就會等待一段隨機的時間后發(fā)起一次Leader選舉。Follower將其當前term加一然后轉(zhuǎn)換為Candidate。它首先給自己投票并且給集群中的其他服務器發(fā)送 RequestVote RPC 。結(jié)果有以下三種情況：

贏得了多數(shù)（超過1/2）的選票，成功選舉為Leader；

收到了Leader的消息，表示有其它服務器已經(jīng)搶先當選了Leader；

沒有Server贏得多數(shù)的選票，Leader選舉失敗，等待選舉時間超時（Election Timeout）后發(fā)起下一次選舉。

Leader選舉

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

分布式設計

11.說說什么是冪等性？

什么是冪等性？

冪等性是一個數(shù)學概念，用在接口上：用在接口上就可以理解為：同一個接口，多次發(fā)出同一個請求，請求的結(jié)果是一致的。簡單說，就是多次調(diào)用如一次。

什么是冪等性問題？

在系統(tǒng)的運行中，可能會出現(xiàn)這樣的問題：

用戶在填寫某些form表單時，保存按鈕不小心快速點了兩次，表中竟然產(chǎn)生了兩條重復的數(shù)據(jù)，只是id不一樣。

開發(fā)人員在項目中為了解決接口超時問題，通常會引入了重試機制。第一次請求接口超時了，請求方?jīng)]能及時獲取返回結(jié)果（此時有可能已經(jīng)成功了），于是會對該請求重試幾次，這樣也會產(chǎn)生重復的數(shù)據(jù)。

mq消費者在讀取消息時，有時候會讀取到重復消息，也會產(chǎn)生重復的數(shù)據(jù)。

這些都是常見的冪等性問題。在分布式系統(tǒng)里，只要下游服務有寫（保存、更新）的操作，都有可能會產(chǎn)生冪等性問題。PS:冪等和防重有些不同，防重強調(diào)的防止數(shù)據(jù)重復，冪等強調(diào)的是多次調(diào)用如一次，防重包含冪等。

怎么保證接口冪等性？

接口冪等性

insert前先select在保存數(shù)據(jù)的接口中，在insert前，先根據(jù)requestId等字段先select一下數(shù)據(jù)。如果該數(shù)據(jù)已存在，則直接返回，如果不存在，才執(zhí)行 ?insert操作。

加唯一索引加唯一索引是個非常簡單但很有效的辦法，如果重復插入數(shù)據(jù)的話，就會拋出異常，為了保證冪等性，一般需要捕獲這個異常。如果是java程序需要捕獲：DuplicateKeyException異常，如果使用了spring框架還需要捕獲：MySQLIntegrityConstraintViolationException異常。

加悲觀鎖更新邏輯，比如更新用戶賬戶余額，可以加悲觀鎖，把對應用戶的哪一行數(shù)據(jù)鎖住。同一時刻只允許一個請求獲得鎖，其他請求則等待。

?

?

????select?*?from?user?id=123?for?update;??

這種方式有一個缺點，獲取不到鎖的請求一般只能報失敗，比較難保證接口返回相同值。

?

?

加樂觀鎖更新邏輯，也可以用樂觀鎖，性能更好?？梢栽诒碇性黾右粋€timestamp或者version字段，例如version:在更新前，先查詢一下數(shù)據(jù)，將version也作為更新的條件，同時也更新version：

?

?

update?user?set?amount=amount+100,version=version+1?where?id=123?and?version=1;??

更新成功后，version增加，重復更新請求進來就無法更新了。

?

?

建防重表有時候表中并非所有的場景都不允許產(chǎn)生重復的數(shù)據(jù)，只有某些特定場景才不允許。這時候，就可以使用防重表的方式。例如消息消費中，創(chuàng)建防重表，存儲消息的唯一ID，消費時先去查詢是否已經(jīng)消費，已經(jīng)消費直接返回成功。

狀態(tài)機有些業(yè)務表是有狀態(tài)的，比如訂單表中有：1-下單、2-已支付、3-完成、4-撤銷等狀態(tài)，可以通過限制狀態(tài)的流動來完成冪等。

分布式鎖直接在數(shù)據(jù)庫上加鎖的做法性能不夠友好，可以使用分布式鎖的方式，目前最流行的分布式鎖實現(xiàn)是通過Redis，具體實現(xiàn)一般都是使用Redission框架。

token機制請求接口之前，需要先獲取一個唯一的token，再帶著這個token去完成業(yè)務操作，服務端根據(jù)這個token是否存在，來判斷是否是重復的請求。

分布式限流

12.你了解哪些限流算法？

計數(shù)器

計數(shù)器比較簡單粗暴，比如我們要限制1s能夠通過的請求數(shù)，實現(xiàn)的思路就是從第一個請求進來開始計時，在接下來的1s內(nèi)，每個請求進來請求數(shù)就+1，超過最大請求數(shù)的請求會被拒絕，等到1s結(jié)束后計數(shù)清零，重新開始計數(shù)。這種方式有個很大的弊端：比如前10ms已經(jīng)通過了最大的請求數(shù)，那么后面的990ms的請求只能拒絕，這種現(xiàn)象叫做“突刺現(xiàn)象”。

漏桶算法

就是桶底出水的速度恒定，進水的速度可能快慢不一，但是當進水量大于出水量的時候，水會被裝在桶里，不會直接被丟棄；但是桶也是有容量限制的，當桶裝滿水后溢出的部分還是會被丟棄的。算法實現(xiàn)：可以準備一個隊列來保存暫時處理不了的請求，然后通過一個線程池定期從隊列中獲取請求來執(zhí)行。

漏桶算法

令牌桶算法

令牌桶就是生產(chǎn)訪問令牌的一個地方，生產(chǎn)的速度恒定，用戶訪問的時候當桶中有令牌時就可以訪問，否則將觸發(fā)限流。實現(xiàn)方案：Guava RateLimiter限流Guava RateLimiter是一個谷歌提供的限流，其基于令牌桶算法，比較適用于單實例的系統(tǒng)。

令牌桶算法

分布式面試題就整理到這里了，主要是偏理論的一些問題，分布式其實是個很大的類型

編輯：黃飛

?