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
{1
?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();
{2
每個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中；
2}
給quorum中的成員發送 OP_COLLECT消息，包含last_committed，first_committed，accepted_pn;
設置超時處理 collect_timeout();
1}
?
?
?
Paxos::handle_collect()? peon 收到OP_COLLECT消息后
{1
state = STATE_RECOVERING;
reset_lease_timeout();設置 last超時，超時重新選舉；
若我的最新的版本+1 比leader的第一個版本還舊，重新bootstrap()；
若我之前接受的PN小于發送者的PN，則同意，accept_pn=接收的PN；
如果對方的last_committed比我的小，把自己已經commit的分享給它share_state();
{2
這里面并沒有進行消息傳遞，只是把兩個版本之間的內容給打包進了msg，隨著msg的其他內容一起發送;
2}
若存在pending_v=last_committed+1這個版本即pending的proposal，那么要把 uncommitted_pn和pending_v對應的value都放到OP_LAST消息中告訴leader；
1}
?
?
?
Paxos::handle_last()? leader收到OP_LAST后
{1
自己比peon的first_committed落后很多，重新bootstrap();
調用store_state()處理對方的share_state分享的已經commit的數據；
{2
？？？
2}
若對方版本太舊，沒法同步，那么重新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）】
{3
?
?
3}
?
正常情況下extend_lease() leader 延長自己的lease時間，并將lease_expire時間發送給所有peon；
{4
發送OP_LEASE信息（last_committed，first_committed,lease_expire）
4}
?
do_refresh（） 一個paxos過程結束后，需要讓上層的各個service(monitor)刷新狀態；
{5
?
5}
finish_round（） 已經完成一輪的提議，狀態設置為STATE_ACTIVE，清理過量日志
{6
state = STATE_ACTIVE;//不是active是不會去propose的；
清理過量日志 trim（）；
propose_pending(); //表決下一個等待提案，并將狀態置為updating；
6）
?
1}
?
?
Paxos::handle_commit() peon 收到OP_COMMIT后
{1
?//將修改寫入后端存儲
? store_state(commit);
//刷新PaxosService服務
? (void)do_refresh();
?
1}
?
Paxos::handle_lease()? peon 收到OP_LEASE后
{1
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？）；
1}
?
Paxos::handle_lease_ack()? leader 收到OP_LEASE_ACK后
{1
處理feature_map；
等quorum中所有都回復后，timer.cancel_event(lease_ack_timeout_event);
warn_on_future_time（）；
1}
?
Paxos::lease_ack_timeout() 若lease timeout了
{1
mon->bootstrap()；
1}
?
?
?
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的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 股份有限公司设立的条件
- 下一篇： 中资银行是什么意思