zookeeper-3.5-1.summary-paxos
====浠ヤ笅閮ㄥ垎鍐呭杞嚜paxos绠楁硶,骞跺湪鍏朵腑浠ヤ笉鍚岄鑹插姞浠ヨ瘎璁?===
绠楁硶鐨勫唴瀹?/span>[缂栬緫]
瑕佹弧瓒?P2c 鐨勭害鏉燂紝proposer 鎻愬嚭涓€涓彁妗堝墠锛岄鍏堣鍜岃冻浠ュ舰鎴愬鏁版淳鐨?acceptors 杩涜閫氫俊锛岃幏寰椾粬浠繘琛岀殑鏈€杩戜竴娆℃帴鍙?accept)鐨勬彁妗堬紙prepare 杩囩▼锛夛紝涔嬪悗鏍规嵁鍥炴敹鐨勪俊鎭喅瀹氳繖娆℃彁妗堢殑 value锛屽舰鎴愭彁妗堝紑濮嬫姇绁ㄣ€傚綋鑾峰緱澶氭暟 acceptors 鎺ュ彈(accept)鍚庯紝鎻愭鑾峰緱鎵瑰噯(chosen)锛岀敱 proposer 灏嗚繖涓秷鎭憡鐭?learner銆傝繖涓畝鐣ョ殑杩囩▼缁忚繃杩涗竴姝ョ粏鍖栧悗灏卞舰鎴愪簡 Paxos 绠楁硶銆?/p>
鍦ㄤ竴涓猵axos瀹炰緥涓紝姣忎釜鎻愭闇€瑕佹湁涓嶅悓鐨勭紪鍙凤紝涓旂紪鍙烽棿瑕佸瓨鍦ㄥ叏搴忓叧绯汇€傚彲浠ョ敤澶氱鏂规硶瀹炵幇杩欎竴鐐癸紝渚嬪灏嗗簭鏁板拰 proposer 鐨勫悕瀛楁嫾鎺ヨ捣鏉ャ€傚浣曞仛鍒拌繖涓€鐐逛笉鍦?Paxos 绠楁硶璁ㄨ鐨勮寖鍥翠箣鍐呫€?/p>
濡傛灉涓€涓病鏈?chosen 杩囦换浣昿roposer鎻愭鐨刟cceptor 鍦?prepare 杩囩▼涓洖绛斾簡涓€涓?proposer 閽堝鎻愭 n 鐨勯棶棰橈紝浣嗘槸鍦ㄥ紑濮嬪 n 杩涜鎶曠エ鍓嶏紝鍙堟帴鍙?accept)浜嗙紪鍙峰皬浜?n 鐨勫彟涓€涓彁妗堬紙渚嬪 n-1锛夛紝濡傛灉 n-1 鍜?n 鍏锋湁涓嶅悓鐨?value锛岃繖涓姇绁ㄥ氨浼氳繚鑳?P2c銆傚洜姝ゅ湪 prepare 杩囩▼涓紝acceptor 杩涜鐨勫洖绛斿悓鏃朵篃搴斿寘鍚壙璇猴細涓嶄細鍐嶆帴鍙?accept)缂栧彿灏忎簬 n 鐨勬彁妗堛€傝繖鏄 P1 鐨勫姞寮猴細
P1a锛氬綋涓斾粎褰?acceptor 娌℃湁鍥炲簲杩囩紪鍙峰ぇ浜?n 鐨?prepare 璇锋眰鏃讹紝acceptor 鎺ュ彈(accept)缂栧彿涓?n 鐨勬彁妗堛€?
鐜板湪宸茬粡鍙互鎻愬嚭瀹屾暣鐨勭畻娉曚簡銆?/p>
鍐宠鐨勬彁鍑轰笌鎵瑰噯[缂栬緫]
閫氳繃涓€涓喅璁垎涓轰袱涓樁娈碉細
- prepare 闃舵锛?ol style="line-height: 1.5em; margin-top: 0.3em; margin-bottom: 0px; margin-left: 3.2em;">
- proposer 閫夋嫨涓€涓彁妗堢紪鍙?n 骞跺皢 prepare 璇锋眰鍙戦€佺粰 acceptors 涓殑涓€涓鏁版淳锛?/li>
- acceptor 鏀跺埌 prepare 娑堟伅鍚庯紝濡傛灉鎻愭鐨勭紪鍙峰ぇ浜庡畠宸茬粡鍥炲鐨勬墍鏈?prepare 娑堟伅锛屽垯 acceptor 灏嗚嚜宸变笂娆℃帴鍙楃殑鎻愭鍥炲缁?proposer锛屽苟鎵胯涓嶅啀鍥炲灏忎簬 n 鐨勬彁妗堬紱
杩欎釜杩囩▼鍦ㄤ换浣曟椂鍊欎腑鏂兘鍙互淇濊瘉姝ｇ‘鎬с€備緥濡傚鏋滀竴涓?proposer 鍙戠幇宸茬粡鏈夊叾浠?proposers 鎻愬嚭浜嗙紪鍙锋洿楂樼殑鎻愭锛屽垯鏈夊繀瑕佷腑鏂繖涓繃绋嬨€傚洜姝や负浜嗕紭鍖栵紝鍦ㄤ笂杩?prepare 杩囩▼涓紝濡傛灉涓€涓?acceptor 鍙戠幇瀛樺湪涓€涓洿楂樼紪鍙风殑鎻愭锛屽垯闇€瑕侀€氱煡 proposer锛屾彁閱掑叾涓柇杩欐鎻愭銆?/p>
瀹炰緥[缂栬緫]
鐢ㄥ疄闄呯殑渚嬪瓙鏉ユ洿娓呮櫚鍦版弿杩颁笂杩拌繃绋?
鏈?A1, A2, A3, A4, A5 5浣嶈鍛? 灏辩◣鐜囬棶棰樿繘琛屽喅璁? 璁憳 A1 鍐冲畾灏嗙◣鐜囧畾涓?10%, 鍥犳瀹冨悜鎵€鏈変汉鍙戝嚭涓€涓崏妗? 杩欎釜鑽夋鐨勫唴瀹规槸:
鐜版湁鐨勭◣鐜囨槸浠€涔? 濡傛灉娌℃湁鍐冲畾, 鍒欏缓璁皢鍏跺畾涓?10%. 鏃堕棿: 鏈眾璁細绗?骞?鏈?5鏃? 鎻愭鑰? A1
鍦ㄦ渶绠€鍗曠殑鎯呭喌涓? 娌℃湁浜轰笌鍏剁珵浜? 淇℃伅鑳藉強鏃堕『鍒╁湴浼犺揪鍒板叾瀹冭鍛樺.
浜庢槸, A2-A5 鍥炲簲:
鎴戝凡鏀跺埌浣犵殑鎻愭, 绛夊緟鏈€缁堟壒鍑?
鑰?A1 鍦ㄦ敹鍒?浠藉洖澶嶅悗灏卞彂甯冩渶缁堝喅璁?
绋庣巼宸插畾涓?10%, 鏂扮殑鎻愭涓嶅緱鍐嶈璁烘湰闂.
杩欏疄闄呬笂閫€鍖栦负浜屾鎻愪氦鍗忚.
鐜板湪鎴戜滑鍋囪鍦?A1 鎻愬嚭鎻愭鐨勫悓鏃? A5 鍐冲畾灏嗙◣鐜囧畾涓?20%:
鐜版湁鐨勭◣鐜囨槸浠€涔? 濡傛灉娌℃湁鍐冲畾, 鍒欏缓璁皢鍏跺畾涓?20%. 鏃堕棿: 鏈眾璁細绗?骞?鏈?5鏃? 鎻愭鑰? A5
鑽夋瑕侀€氳繃渚嶄粠閫佸埌鍏跺畠璁憳鐨勬澶? A1 鐨勮崏妗堝皢鐢?浣嶄緧浠庨€佸埌 A2-A5 閭ｉ噷. 鐜板湪, 璐熻矗 A2 鍜?A3 鐨勪緧浠庡皢鑽夋椤哄埄閫佽揪, 璐熻矗 A4 鍜?A5 鐨勪緧浠庡垯涓嶄笂鐝? A5 鐨勮崏妗堝垯椤哄埄鐨勯€佽嚦 A3 鍜?A4 鎵嬩腑.
鐜板湪, A1, A2, A3 鏀跺埌浜?A1 鐨勬彁妗? A3, A4, A5 鏀跺埌浜?A5 鐨勬彁妗? 鎸夌収鍗忚, A1, A2, A4, A5 灏嗘帴鍙椾粬浠敹鍒扮殑鎻愭, 渚嶄粠灏嗘嬁鐫€
鎴戝凡鏀跺埌浣犵殑鎻愭, 绛夊緟鏈€缁堟壒鍑?
鐨勫洖澶嶅洖鍒版彁妗堣€呴偅閲?
鑰?A3 鐨勮涓哄皢鍐冲畾鎵瑰噯鍝竴涓?
鎯呭喌涓€[缂栬緫]
鍋囪 A1 鐨勬彁妗堝厛閫佸埌 A3 澶? 鑰?A5 鐨勪緧浠庡喅瀹氭斁鍋囦竴娈垫椂闂? 浜庢槸 A3 鎺ュ彈骞舵淳鍑轰簡渚嶄粠. A1 绛夊埌浜嗕袱浣嶄緧浠? 鍔犱笂瀹冭嚜宸卞凡缁忔瀯鎴愪竴涓鏁版淳, 浜庢槸绋庣巼 10% 灏嗘垚涓哄喅璁? A1 娲惧嚭渚嶄粠灏嗗喅璁€佸埌鎵€鏈夎鍛樺:
绋庣巼宸插畾涓?10%, 鏂扮殑鎻愭涓嶅緱鍐嶈璁烘湰闂.
A3 鍦ㄥ緢涔呬互鍚庢敹鍒颁簡鏉ヨ嚜 A5 鐨勬彁妗? 鐢变簬绋庣巼闂宸茬粡璁ㄨ瀹屾瘯, 浠栧喅瀹氫笉鍐嶇悊浼? 浣嗘槸浠栬鎶辨€ㄤ竴鍙?
绋庣巼宸插湪涔嬪墠鐨勬姇绁ㄤ腑瀹氫负 10%, 浣犱笉瑕佸啀鏉ョ儲鎴?
杩欎釜鍥炲瀵?A5 鍙兘鏈夊府鍔? 鍥犱负 A5 鍙兘鍥犱负鏌愮鍘熷洜寰堜箙鏃犳硶涓庝笌澶栫晫鑱旂郴浜? 褰撶劧鏇村彲鑳藉 A5 娌℃湁浠讳綍浣滅敤, 鍥犱负 A5 鍙兘宸茬粡浠?A1 澶勮幏寰椾簡鍒氭墠鐨勫喅璁?
鎯呭喌浜?/span>[缂栬緫]
渚濈劧鍋囪 A1 鐨勬彁妗堝厛閫佸埌 A3 澶? 浣嗘槸杩欐 A5 鐨勪緧浠庝笉鏄斁鍋囦簡, 鍙槸涓€旇€芥悂浜嗕竴浼? 杩欐, A3 渚濈劧浼氬皢"鎺ュ彈"鍥炲缁?A1. 浣嗘槸鍦ㄥ喅璁垚鍨嬩箣鍓嶅畠鍙堟敹鍒颁簡 A5 鐨勬彁妗? 杩欐椂鍗忚鏈変袱绉嶅鐞嗘柟寮?
1. 濡傛灉 A5 鐨勬彁妗堟洿鏃? 鎸夌収浼犵粺搴旇鐢辫緝鏃╃殑鎻愭鑰呬富鎸佹姇绁? 鐜板湪鐪嬫潵涓や唤鎻愭鐨勬椂闂翠竴鏍?鏈眾璁細绗?骞?鏈?5鏃?. 浣嗘槸 A5 鏄釜鎯逛笉璧风殑澶т汉鐗? 浜庢槸 A3 鍥炲:
鎴戝凡鏀跺埌鎮ㄧ殑鎻愭, 绛夊緟鏈€缁堟壒鍑? 浣嗘槸鎮ㄤ箣鍓嶆湁浜烘彁鍑哄皢绋庣巼瀹氫负 10%, 璇锋槑瀵?
浜庢槸, A1 鍜?A5 閮芥敹鍒颁簡瓒冲鐨勫洖澶? 杩欐椂鍏充簬绋庣巼闂灏辨湁涓や釜鎻愭鍦ㄥ悓鏃惰繘琛? 浣嗘槸 A5 鐭ラ亾涔嬪墠鏈変汉鎻愬嚭绋庣巼涓?10%. 浜庢槸 A1 鍜?A5 閮戒細鍚戝叏浣撹鍛樺箍鎾?
绋庣巼宸插畾涓?10%, 鏂扮殑鎻愭涓嶅緱鍐嶈璁烘湰闂.
涓€鑷存€у緱鍒颁簡淇濊瘉.
2. A5 鏄釜鏃犺冻杞婚噸鐨勫皬浜虹墿. 杩欐椂 A3 涓嶅啀鐞嗕細浠? A1 涓嶄箙鍚庡氨浼氬箍鎾◣鐜囧畾涓?10%.
鎯呭喌涓?/span>[缂栬緫]
鍦ㄨ繖涓儏鍐典腑, 鎴戜滑灏嗙湅瑙? 鏍规嵁鎻愭鐨勬椂闂村強鎻愭鑰呯殑鏉冨娍鍐冲畾鏄惁搴旂瓟鏄湁鎰忎箟鐨? 鍦ㄨ繖閲? 鏃堕棿鍜屾彁妗堣€呯殑鏉冨娍灏辨瀯鎴愪簡缁欐彁妗堢紪鍙风殑渚濇嵁. 杩欐牱鐨勭紪鍙风鍚?浠讳綍涓や釜鎻愭涔嬮棿鏋勬垚鍋忓簭"鐨勮姹?
A1 鍜?A5 鍚屾牱鎻愬嚭涓婅堪鎻愭, 杩欐椂 A1 鍙互姝ｅ父鑱旂郴 A2 鍜?A3; A5 涔熷彲浠ユ甯歌仈绯昏繖涓や釜浜? 杩欐 A2 鍏堟敹鍒?A1 鐨勬彁妗? A3 鍒欏厛鏀跺埌 A5 鐨勬彁妗? A5 鏇存湁鏉冨娍.
鍦ㄨ繖绉嶆儏鍐典笅, 宸茬粡鍥炵瓟 A1 鐨?A2 鍙戠幇鏈夋瘮 A1 鏇存湁鏉冨娍鐨?A5 鎻愬嚭浜嗙◣鐜?20% 鐨勬柊鎻愭, 浜庢槸鍥炲 A5 璇?
鎴戝凡鏀跺埌鎮ㄧ殑鎻愭, 绛夊緟鏈€缁堟壒鍑?
鑰屽洖澶嶄簡 A5 鐨?A3 鍙戠幇鏂扮殑鎻愭鑰匒1鏄釜灏忎汉鐗? 涓嶄簣鐞嗕細.
A1娌℃湁杈惧埌澶氭暟锛孉5杈惧埌浜嗭紝浜庢槸 A5 灏嗕富鎸佹姇绁? 鍐宠鐨勫唴瀹规槸 A5 鎻愬嚭鐨勭◣鐜?20%.
濡傛灉 A3 鍐冲畾骞崇瓑鍦板寰呮瘡涓€浣嶈鍛? 瀵?A1 鍋氬嚭"浣犱箣鍓嶆湁浜烘彁鍑哄皢绋庣巼瀹氫负 20%" 鐨勫洖澶? 鍒欏皢閫犳垚娣蜂贡. 杩欑鎯呭喌涓?A1 鍜?A5 閮藉皢璇曞浘涓绘寔鎶曠エ, 浣嗘槸杩欐涓や唤鎻愭鐨勫唴瀹逛笉鍚?
杩欑鎯呭喌涓? A3 鑻ュ A1 杩涜鍥炲, 鍙兘璇?
鏈夋洿澶х殑浜虹墿鍏虫敞姝や簨, 璇风瓑寰呬粬鍋氬嚭鍐冲畾.
鍙﹀, 鍦ㄨ繖绉嶆儏鍐典笅, A4 涓庡鐣屽け鍘讳簡鑱旂郴. 绛夊埌浠栨仮澶嶈仈绯? 骞堕渶瑕佸緱鐭ョ◣鐜囨儏鍐垫椂, 浠?鍦ㄦ渶绠€鍗曠殑鍗忚涓?灏嗘彁鍑轰竴涓彁妗?
鐜版湁鐨勭◣鐜囨槸浠€涔? 濡傛灉娌℃湁鍐冲畾, 鍒欏缓璁皢鍏跺畾涓?15%. 鏃堕棿: 鏈眾璁細绗?骞?鏈?鏃? 鎻愭鑰? A4
杩欐椂, (鍦ㄦ渶绠€鍗曠殑鍗忚涓?鍏朵粬璁憳灏嗕細鍥炲:
绋庣巼宸插湪涔嬪墠鐨勬姇绁ㄤ腑瀹氫负 20%, 浣犱笉瑕佸啀鏉ョ儲鎴?
| responser--> | A1 | A2 | A3 | A5 |
| 鑾峰彇鎶曠エ鏁皏 | 聽 | 聽 | 聽 | 聽 |
| A1 | 1 | 1[鍏堟潵鍏堜富鎸乚 | 0 | 聽 |
| A5 | 聽 | 1[A5鐨勬潈閲嶅ぇ] | 1 | 1 |
聽
鍐宠鐨勫彂甯?/span>[缂栬緫]
涓€涓樉鑰屾槗瑙佺殑鏂规硶鏄綋 acceptors 鎵瑰噯涓€涓?value 鏃讹紝灏嗚繖涓秷鎭彂閫佺粰鎵€鏈?learner銆備絾鏄繖涓柟娉曚細瀵艰嚧娑堟伅閲忚繃澶с€?/p>
鐢变簬鍋囪娌℃湁 Byzantine failures锛宭earners 鍙互閫氳繃鍒殑 learners 鑾峰彇宸茬粡閫氳繃鐨勫喅璁€傚洜姝?acceptors 鍙渶灏嗘壒鍑嗙殑娑堟伅鍙戦€佺粰鎸囧畾鐨勬煇涓€涓?learner锛屽叾浠?learners 鍚戝畠璇㈤棶宸茬粡閫氳繃鐨勫喅璁€傝繖涓柟娉曢檷浣庝簡娑堟伅閲忥紝浣嗘槸鎸囧畾 learner 澶辨晥灏嗗紩璧风郴缁熷け鏁堛€?/p>
鍥犳 acceptors 闇€瑕佸皢 accept 娑堟伅鍙戦€佺粰 learners 鐨勪竴涓瓙闆嗭紝鐒跺悗鐢辫繖浜?learners 鍘婚€氱煡鎵€鏈?learners銆?/p>
浣嗘槸鐢变簬娑堟伅浼犻€掔殑涓嶇‘瀹氭€э紝鍙兘浼氭病鏈変换浣?learner 鑾峰緱浜嗗喅璁壒鍑嗙殑娑堟伅銆傚綋 learners 闇€瑕佷簡瑙ｅ喅璁€氳繃鎯呭喌鏃讹紝鍙互璁╀竴涓?proposer 閲嶆柊杩涜涓€娆℃彁妗堛€傛敞鎰忎竴涓?learner 鍙兘鍏间换 proposer銆?/p>
Progress 鐨勪繚璇?/span>[缂栬緫]
[[1]鏍规嵁涓婅堪杩囩▼褰撲竴涓?proposer 鍙戠幇瀛樺湪缂栧彿鏇村ぇ鐨勬彁妗堟椂灏嗙粓姝㈡彁妗堛€傝繖鎰忓懗鐫€鎻愬嚭涓€涓紪鍙锋洿澶х殑鎻愭浼氱粓姝箣鍓嶇殑鎻愭杩囩▼銆傚鏋滀袱涓?proposer 鍦ㄨ繖绉嶆儏鍐典笅閮借浆鑰屾彁鍑轰竴涓紪鍙锋洿澶х殑鎻愭锛屽氨鍙兘闄峰叆娲婚攣锛岃繚鑳屼簡 Progress 鐨勮姹俔銆俒[2]杩欑鎯呭喌涓嬬殑瑙ｅ喅鏂规鏄€変妇鍑轰竴涓?leader锛屼粎鍏佽 leader 鎻愬嚭鎻愭銆備絾鏄敱浜庢秷鎭紶閫掔殑涓嶇‘瀹氭€э紝鍙兘鏈夊涓?proposer 鑷涓鸿嚜宸卞凡缁忔垚涓?leader銆侺amport 鍦?a href="http://research.microsoft.com/users/lamport/pubs/lamport-paxos.pdf" style="color: #663366; padding-right: 16px; background-position: 100% 50%;" class="external text">The Part-Time Parliament涓€鏂囦腑鎻忚堪骞惰В鍐充簡杩欎釜闂銆俔
聽ps:鍏朵腑[1]涓嶆槸寰堟竻妤氫负浠€涔堣浼氱粓姝maller 缂栧彿鎻愭,杩欐牱涓嶆槸涓庝綔鑰呯殑'鍏堟潵鍏堜富鎸?瑙傜偣鐭涚浘浜?鑰屼笖纭疄浼氬嚭鐜?涓嶆柇琚墦鏂殑灞€闈?
聽