當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

ceph monitor----paxos算法1

發布時間：2025/5/22 编程问答 17 豆豆

生活随笔收集整理的這篇文章主要介紹了 ceph monitor----paxos算法1 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

對于分布式來說最重要的莫過于所有副本數據的一致性。

在monitor節點中，存在著Leader和Peon兩種角色。當客戶端發出讀命令時可以由相應的Peon或者Leader返回。一旦發生修改動作，所有的消息會第一時間發送給Leader節點，然后由Leader節點分發給Peon節點。

paxos算法保證了一次修改操作只能批準一個值，從而保證了分布式系統副本的一致性。

多個節點之間存在兩種通訊模型：共享內存（Shared memory）、消息傳遞（Messages passing），Paxos是基于消息傳遞的通訊模型的。

paxos轉換時機：

1.monitor啟動時，paxos初始化；

2.monitor進入bootstrap時，paxos的restart ；

3.monitor根據選舉結果，paxos對應初始化為leader或peon；

4.monitor異常后，paxos recovery階段；

5.monitor運行過程中，paxos決議；

概念說明

1.1 Epoch

每次選舉產生新的leader，也會產生新的epoch。不選舉則不會修改epoch。一個leader當選期間，發送的所有消息，都會帶有這個epoch。如果由于網絡分割等現象，有新的選舉發生，則根據epoch就發現leader已經變了。注意，按照paxos論文描述，沒有Leader也是可以正常運行的，只是可能降低效率。沒有leader則不需要epoch

1.2 PN(Proposal Number)

Leader當選后，會首先執行一次phase 1過程，以確定PN。在其為leader期間，所有的phase 2操作都共用一個PN。所以省略了大量的phase 1操作，這也是 paxos能夠減小網絡開銷的原因。 “Paxos made simple”文中說：

“A newly chosen leader executes phase 1 for infinitely many instances of the consensus algorithm”。

PN是必須的，無論是否有leader，都必須有PN

1.3Version

可以理解成Paxos的instance ID，或者raft的logID

1.4持久化

對比raft，雖然ceph的復制也可以看成一個個log的追加，但是所有信息都寫在k/v中，而不是寫log文件，比如instanceID為X的log，在k/v存儲中，其key是X,value是log的內容。其他各種需要持久化的值，都寫在k/v存儲中。

1.5其他需要持久化的數據結構

上述三個“uncommitted”開頭的值，可能壓根就不存在，比如正常關機，全部都commit了。

uncommitted_value：

* If the system fails in-between the accept replies from the Peons and the

?? * instruction to commit from the Leader, then we may end up with accepted

?? * but yet-uncommitted values. During the Leader's recovery, it will attempt

?? * to bring the whole system to the latest state, and that means committing

?? * past accepted but uncommitted values.

?? *

?? * This variable will hold an uncommitted value, which may originate either

?? * on the Leader, or learnt by the Leader from a Peon during the collect

?? * phase.

1.6 Ceph的Paxos存在如下幾個狀態：

1) Recovery狀態：Leader選舉結束后進入該狀態。該狀態的目的是同步Quorum成員間的狀態；

2) Active狀態：即空閑狀態，沒有執行Paxos算法審批提案；

3) Updating狀態：正在執行Paxos算法審批提案；

4) Updating Previous狀態：正在執行Paxos算法審批舊提案，舊提案即Leader選舉之前舊Leader提出但尚未批準的提案。

流程

phase1 交互過程

paxos的recovery過程

Phase1，目的是就PN達成一致，包括三個步驟，如下：

在Leader選舉成功后，Leader和Peon都進入Recovery階段。該階段的目的是為了保證新Quorum的所有成員狀態一致，這些狀態包括：最后一個批準(Committed)的提案，最后一個沒批準的提案，最后一個接受(Acceppted)的提案。每個節點的這些狀態都持久化到磁盤。對舊Quorum的所有成員來說，最后一個通過的提案應該都是相同的，但對不屬于舊Quorum的成員來說，它的最后一個通過的提案是落后的。

同步已批準提案的方法是，Leader先向新Quorum的所有Peon節點發送OP_COLLECT消息，并在消息中攜帶Leader自己的第1個和最后1個批準的提案的值的版本號。Peon收到OP_COLLECT消息后，將自己的第1個和最后1個批準的提案的值的版本號返回給Leader，并且如果Peon的最后1個批準的版本號大于Leader最后一個批準的版本號時，將所有在大于Leader最后一個版本號的提案值發送給Leader。Leader將根據這些信息填補自己錯過的提案。這樣，當Leader接收到所有Peon對OP_COLLECT消息的回應后，也就將自己更新到了最新的狀態。這時Leader又反過來將最新狀態同步到其它節點。

為獲取新Quorum所有成員中的最大提案號，Leader在發送OP_COLLECT消息時，提出它知道的最大的提案號，并將該提案號附加在OP_COLLECT消息中。如果Peon已接受的最大提案號大于Leader提出的提案號，則拒絕接受Leader提出的提案號并將自己已接受的最大提案號通過OP_LAST消息發送給Leader。Leader收到OP_LAST消息后，發現自己的提案號不是最大時，就在Peon接受的最大提案號的基礎上提出更大的提案號，重新進入Recovery階段。這樣，最終可以獲取到最大的提案號。

總而言之，Recovery階段的目的是讓新Quorum中所有節點處于一致狀態。實現這一目的的方法分成兩步：首先，在Leader節點收集所有節點的狀態，通過比較得到最新狀態；然后，Leader將最新狀態同步給其它節點。有兩個比較重要的狀態，最后一次批準的提案和已接受的最大提案號。

注意區分提案號(proposal number)、提案值(value)、提案值的版本號(value version)這三個概念。提案號由Leader提出，為避免不同Leader提出的提案號不沖突，同個Leader提出的提案號是不連續的。提案的值的版本號是連續的。

函數

void Paxos::leader_init()

void Paxos::peon_init()

void Paxos::collect(version_t oldpn)

void Paxos::handle_collect(MMonPaxos *collect)

void Paxos::handle_last(MMonPaxos *last)

void Paxos::handle_commit(MMonPaxos *commit)

Paxos屬性

uncommitted_v、uncommitted_pn、uncommitted_value

last_committed、accepted_pn

配置

OPTION(mon_lease, OPT_FLOAT, 5)???? // Lease租期

Phase2

paxos的propose過程

Phase 2，即正常工作過程中的Propose、accept和commit過程。

從begin()到commit_finish()稱為一輪，即一次提議的完成過程。

串行化提議：

Ceph的paxos實現，每次只允許一個提議在執行中，即上面提到?的一輪完成才能執行下一輪。在這個過程中，會有多次寫盤操作。?

這個過程實際上比較慢。對于ceph自身來說，osd等的狀態變更，?不頻繁，無需極高的paxos性能。但是如果用于做用于分布式數據?

庫等系統的日志，這種方式則有不足。

Lease階段

Paxos算法分成兩個階段，第一個階段為Prepare階段。在這階段中，(a)Proposer選擇它知道的最大提案號n，并向所有Acceptor發送Prepare消息。(b)Acceptor承諾不再接受編號小于n的提案，(c)并返回它接受的編號小于n的提案中編號最大的提案給Proposer。這個過程中，如果Proposer選擇的不是最大的提案號，那么Acceptor將拒絕Proposer的提案，而Proposer遭到拒絕后會提出編號更大的提案。這樣循環反復，Proposer最終可以提出編號最大的提案。另外，Acceptor返回接受的編號小于n的提案中編號最大的提案給Proposer的目的是為讓Proposer決定新提出的提案的值。對Ceph而言，由于Leader可以控制提案的進度，運行一次Paxos算法只有一個提案在審批，每次算法Leader都能夠由自己決定提案的值，所以Peon不必返回接受的編號小于n的提案中編號最大的提案。

Ceph中Paxos算法的實現，省略了Prepare階段，并且Leader選舉成功后每次執行算法使用同一個提案號。在Prepare階段要完成(a)、(b)和(c)三件事，前兩件事在Recovery階段完成，Leader和Peon的已接受的最大提案號保持相同。最后一件事情，由于Leader的存在不需要做。

Paxos算法的第二階段為Accept階段。在這個階段中，(d)Proposer根據在Prepare階段中學習到的知識提出提案。(e)Acceptor根據接受到的提案的提案號決定拒絕還是接受。最后，(f)Proposer根據反饋情況決定提案是否得到批準。對Ceph來說，每次算法只有一個提案所以可以直接決定提案的值，因此不必關心(d)。對(e)和(f)的實現和標準Paxos算法保持一致。

propose的觸發條件：

a.ConfigKeyService服務在修改或刪除key/value值;

b.Paxos以及PaxosService對數據做trim;

c.PaxosService的各種服務，更新map;

在此僅以PaxosService更新map為例：客戶端發來修改請求到底是個什么過程呢？

其他需要monitor協作的模塊構建與mon通訊的對象，然后發送消息給mon： monc->send_mon_message(m);

monitor收到消息后，進入Monitor::handle_forward()?? extract the original message and put it into the regular dispatch function

?

具體代碼過程

Phase1? recovery階段

Paxos::collect()? leader發起collect

?state = STATE_RECOVERING;

清空一些值：

uncommitted_v

uncimmitted_pn

uncommitted_value

peer_first_committed

peer_last_committed

若DBStore中存在pending的proposal,那么其version一定為last_committed+1；

uncommitted_pn=pending pn；

uncommitted_v=last_committed+1；

找到uncommitted_v對應的uncommitted_value；

否則uncommitted_pn=accepted_pn；

生成新的pn，自己先accept：accepted_pn=get_new_proposal_numble();

每個monitor有自己的rank，把rank作為自己產生的PN的低位數，則各自不同;

比如，rank=5的，產生的只可能是105, 205, 305等，即n*100 +5;

update. make it unique among all monitors;

第n次選舉后產生的pn值為100*n+rank(leader);

持久化到DBStore中；

給quorum中的成員發送 OP_COLLECT消息，包含last_committed，first_committed，accepted_pn;

設置超時處理 collect_timeout();

Paxos::handle_collect()? peon 收到OP_COLLECT消息后

state = STATE_RECOVERING;

reset_lease_timeout();設置 last超時，超時重新選舉；

若我的最新的版本+1 比leader的第一個版本還舊，重新bootstrap()；

若我之前接受的PN小于發送者的PN，則同意，accept_pn=接收的PN；

如果對方的last_committed比我的小，把自己已經commit的分享給它share_state();

這里面并沒有進行消息傳遞，只是把兩個版本之間的內容給打包進了msg，隨著msg的其他內容一起發送;

若存在pending_v=last_committed+1這個版本即pending的proposal，那么要把 uncommitted_pn和pending_v對應的value都放到OP_LAST消息中告訴leader；

Paxos::handle_last()? leader收到OP_LAST后

自己比peon的first_committed落后很多，重新bootstrap();

調用store_state()處理對方的share_state分享的已經commit的數據；

？？？

若對方版本太舊，沒法同步，那么重新bootstrap();

若對方比我舊但在可同步范圍，發送OP_COMMIT消息，share_state()分享已經commit的數據；

若peon接受過的PN比自己的accepted_pn大，那么提高PN值，重新collect（）；

若peon接受了自己的PN，記錄下peon同時發送的uncommitted_pn, value,v;

若quorum中所有都接受自己的PN，（num_last == mon->get_quorum().size()），

若存在未commit的value（uncommitted_value)，（uncommitted_v == last_committed+1）則state = STATE_UPDATING_PREVIOUS，開始propose過程：begin（uncommitted_value）；

【STATE_UPDATING_PREVIOUS是對應剛當選后，發現有uncommitted_value，并且是下一個版本（last_committed+1）】

正常情況下extend_lease() leader 延長自己的lease時間，并將lease_expire時間發送給所有peon；

發送OP_LEASE信息（last_committed，first_committed,lease_expire）

do_refresh（） 一個paxos過程結束后，需要讓上層的各個service(monitor)刷新狀態；

finish_round（） 已經完成一輪的提議，狀態設置為STATE_ACTIVE，清理過量日志

state = STATE_ACTIVE;//不是active是不會去propose的；

清理過量日志 trim（）；

propose_pending(); //表決下一個等待提案，并將狀態置為updating；

6）

Paxos::handle_commit() peon 收到OP_COMMIT后

?//將修改寫入后端存儲

? store_state(commit);

//刷新PaxosService服務

? (void)do_refresh();

Paxos::handle_lease()? peon 收到OP_LEASE后

warn_on_future_time（）檢查OP_LEASE消息的時間戳和當前時間差，判斷是否超出允許的mon_clock_drift_allowed;

更新自己的lease_expire；

設置狀態為STATE_ACTIVE；

發送OP_LEASE_ACK消息（last_committed，first_committed，ceph_clock_now()，feature_map？）；

Paxos::handle_lease_ack()? leader 收到OP_LEASE_ACK后

處理feature_map；

等quorum中所有都回復后，timer.cancel_event(lease_ack_timeout_event);

warn_on_future_time（）；

Paxos::lease_ack_timeout() 若lease timeout了

mon->bootstrap()；

Phase2? propose階段

數據概覽

首先我們分析的版本是0.94.7的版本，也就是目前Hammer最新的版本。對于leveldb中的數據，我們需要來一個感性的認識，請看下面數據，由于數據太多這里僅僅列出了key：

可以看到這里有paxos，有monmap，osdmap，mdsmap，auth，logm，和上一篇（Ceph Monitor基礎架構與模塊詳解）中的Monitor的架構圖很像。paxos記錄了每次propose的value，具體可以這么來看：

以paxos:1869為例，paxos為prefix，1869為key。可以將不同的prefix當做不同的表，里面的key是主鍵，其存儲的值是value，這里paxos:1869存儲的就是Monitor一致同意的1869次決議。所有的狀態的變化都是從這個決議里產生的。

那我們有什么方式可以查看決議的內容呢？我們可以通過如下命令先將數據從leveldb中導出來：

然后使用ceph-dencoder工具來查看：

從上面的數據輸出我們可以得出一下幾點：

paxos:1869存儲的是MonitorDBStore::Transaction序列化后的數據
Monitor的Transaction和Osd的Transaction類似，都封裝了多個op的操作
log通過paxos來保持一致性，所以這里有，同理osdmap，monmap，pgmap等都應該Transaction里
這里僅僅是paxos決議的值，但是上面有osdmap的key，那么osdmap:num的val應該也是和paxos里相應的內容一樣
Paxos應該有Trim機制，因為如果數據一致這么存下去，不是辦法

Paxos更新一個值的流程

1、Leader

1）設置new_value =v，v中值就是我們上面看到的paxos:1869中的值，都是kv。

2）將自己加入到同意者集合。

3）生成MonitorDBStore::Transaction，以paxos為前綴，last_commited+1 的key來將v寫入到leveldb中，同時更新pending_v，和pending_pn。

4）將new_value, last_commited和accepted_pn發送給quorum中的所有成員。

2、Peon

1）判斷自己的accepted_pn和Leader發送過來的accepted_pn是否相等，如果小于就忽略，認為是舊一輪的決議。

2）判斷自己last_commited是否和leader發送過來的相關，如果不相關，就是出現了不一致，直接assert。

3）同Leader中的3）。

4）將accpted_pn 和 last_commited發送給Leader。

3、Leader

1）判斷Peon發送過來的pn是不是和自己的accepted_pn一致，如果不等可能有則返回。

2）判斷last_commited，如果Peon發送過來的last_commited比last_commted -1 小，則認為是舊一輪的消息，丟棄。

3）判斷Peon是否在同意者結合，如果不在就加入，如果在，說明一個Peon發送了兩次accept消息，Leader直接assert。

4）當接受者結合和quorum結合一樣的時候，也就是大多數人都同意了，Leader提交決議。

5）更新leveldb中的last_commited為last_commited + 1。

6）將new_value中的數據都展開封裝成transaction，然后寫入，插入回調。

7）當Leader完成本地的提交之后，調用回調向quorum中的所有成員發送commit消息。

4、Peon

1）在接收到commit消息之后，進行內部提交。

這里有幾點需要說明的是：

在決議的過程中其實提交了Leader提交了兩次，一次是直接將決議當做bl寫入paxos的prefix中，另一次是將bl解析出來（bl里的內容都是封裝的小的op操作）在寫入bl里封裝的prefix的庫中。

所有的update操作的請求都會路由到Leader，也就是說無論你有3個，或者5個，在處理update請求的時候只會是1個。

OSDMap的管理

這里我們以OSDMap為例，來看看它是如何從生成到進庫的。

當有osd up或者down的時候，monitor會感知到。當消息走到prepare_update的時候，會在各自的prepare函數經過各種處理，最終會將更新紀錄到pending_inc中。因為OSDMap的更新全紀錄在pending_inc這個變量里。然后在dispatch中，會判斷是不是要走決議流程，如果走了決議流程之后會首先將pending_inc中的內容encode進transaction，這里調用了一個很重要的函數encode_pending。在這個函數里將pending_inc中該有的內容都塞進了transaction。當有了這個transaction之后，就是會走我們上面講的Paxos決議流程了。最終這些決議會持久化到leveldb中。

從上面我們可以看到Monitor的架構，這里雖然講的是OSDMonitor怎么處理消息的，但是MDSMonitor，MonMapMonitor都是一樣的。Update操作改變自己的pending_inc，然后在encode_pending的時候生成transaction，然后就是走決議流程。

同樣可以通過以下命令將osdmap拿出來看看：

轉載于:https://www.cnblogs.com/yi-mu-xi/p/10364841.html

總結

以上是生活随笔為你收集整理的ceph monitor----paxos算法1的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。