概述
https://www.cnblogs.com/frankyou/p/7238099.html
CAP
- Consistency
- Availability
- Partition-Tolerance
- 網(wǎng)絡(luò)分區(qū)：網(wǎng)絡(luò)延遲或中斷導(dǎo)致的限時內(nèi)通訊失敗
- 由于必需滿足，所以取舍在于C和A
BASE
- Basically Available
- Soft State
- 可異步
- Eventual Consistency
2PC
http://blog.csdn.net/feilengcui008/article/details/50557511?spm=a2c4e.11153940.blogcont5854.3.1e843545OLEAJn
https://yq.aliyun.com/articles/5854
- Vote + Commit
- 強(qiáng)一致，非高可用
- Commit階段Coordinator和Participant同時掛掉；當(dāng)其余Participant均返回accept時，無法決定下一步，會被阻塞
- 缺點(diǎn)
- 同步阻塞
- 單點(diǎn)故障
3PC
https://segmentfault.com/a/1190000004474543
- can_commit + pre_commit + do_commit
- 高可用，可能不一致
- Pre-Commit階段發(fā)生網(wǎng)絡(luò)分區(qū)，導(dǎo)致abort信號無法送達(dá)，Participant超時后commit，導(dǎo)致不一致
Paxos
https://www.cnblogs.com/linbingdong/p/6253479.html
- Google Chubby的作者M(jìn)ike Burrows說：這個世界上只有一種一致性算法，那就是Paxos，其它算法都是殘次品
What does Paxos do?
paxos-001.jpg
- 宕機(jī)或網(wǎng)絡(luò)故障下，在集群內(nèi)部對某個值達(dá)成一致
作者
- 萊斯利·蘭伯特（Leslie Lamport，即LaTeX 中的"La"，現(xiàn)在在微軟研究院）
- 作為2013年新科圖靈獎得主，現(xiàn)在七十多歲，是計(jì)算機(jī)科學(xué)領(lǐng)域一位擁有杰出成就的傳奇人物
- 期間多次榮獲ACM，IEEE及其他各類計(jì)算機(jī)重大獎項(xiàng)
- Lamport對時間時鐘、面包店算法、拜占庭將軍問題及Paxos算法具創(chuàng)造性研究
誕生
- 1990年將其對Paxos算法的研究論文The Part-Time Parliament提交給了ACM TOCS Jnl.的評審委員會
- 由于Lamport“創(chuàng)造性”地使用了故事的方式進(jìn)行算法的描述，導(dǎo)致當(dāng)時委員會工作人員沒有一個能正確地理解算法
- 并要求Lamport使用嚴(yán)謹(jǐn)?shù)恼娣绞絹砻枋鏊惴ǎ駝t將不予接收這篇論文
- 最終，Lamport拒絕了對論文的修改，并撤銷對論文的提交
- 時隔6周年，來自微軟的Butler Lampson在WDAG96上提出了重新審視這篇論文的建議
- 次年的WDAG97上，麻省理工學(xué)院的Nancy Lynch公布其根據(jù)Lamport的原文重新修改后的Revisiting the Paxos Algorithm“幫助"”Lamport用數(shù)學(xué)術(shù)語定義并證明了Paxos算法
- 1998年的ACM TOCS上，這篇延遲了9年的論文終于被接受
- 標(biāo)志著Paxos算法正式被計(jì)算機(jī)科學(xué)接收并開始影響更多的工程師解決分布式一致性問題
- 2001年，Lamport本人也做出了讓步，使用了通俗易懂的語言重新講述了原文，并發(fā)表了Paxos Made Simple
- 然而Lamport本人認(rèn)為他自己的表述足夠讓人理解Paxos算法，所以通篇沒有任何數(shù)學(xué)符號
論文故事
- 一個叫Paxos的小島上住了一批居民，島上所有事情由一些特殊的人決定，他們叫做議員(Senator)。議員總數(shù)是確定的，不能更改。島上每次環(huán)境事務(wù)的變更都需要通過一個提議（Proposal），每個提議都有一個編號(PID)，這個編號是一直增長的，不能倒退。每個提議都需要超過半數(shù)((Senator Count)/2 +1)的議員同意才能生效。每個議員只會同意大于當(dāng)前編號的提議，包括已生效的和未生效的。如果議員收到小于等于當(dāng)前編號的提議，就會拒絕，并告知對方：你的提議已經(jīng)有人提過了。這里的當(dāng)前編號是每個議員在自己的記事本上記錄的編號，他不斷更新這個編號。整個議會不能保證所有議員記事本上的編號總是相同的?，F(xiàn)在議會有一個目標(biāo)：保證所有的議員對于提議都能達(dá)成一致的看法。
- 現(xiàn)在議會開始運(yùn)作，所有議員一開始記事本上面記錄的編號都是0。有一個議員發(fā)了一個提議：將電費(fèi)設(shè)定為1元/度。他首先看了一下記事本，嗯，當(dāng)前提議編號是0，那么我的這個提議的編號就是1。于是他給所有議員發(fā)消息：1號提議，設(shè)定電費(fèi)1元/度。其他議員收到消息后查詢記事本，哦，當(dāng)前提議編號是0，這個提議可接受。于是他記下這個提議并回復(fù)：我接受你的1號提議；同時在記事本上記錄：當(dāng)前提議編號為1。發(fā)起提議的議員收到超半數(shù)的回復(fù)，立即給所有人發(fā)通知：1號提議生效！收到的議員會修改自己的記事本，將1號提議由記錄改成正式法令，當(dāng)有人問他電費(fèi)為多少時，他會查看法令并告訴對方：1元/度。
- 現(xiàn)在看沖突的解決：假設(shè)總共有三個議員S1-S3，S1和S2同時發(fā)起了一個提議:1號提議，設(shè)定電費(fèi)。S1設(shè)為1元/度, S2設(shè)為2元/度。S3先收到了S1的提議，他在記事本上做了記錄。緊接著他收到了S2的提議，他一查記事本，咦，這個提議的編號小于等于我的當(dāng)前編號1，于是他拒絕了這個提議：對不起，這個提議先前提過了。于是S2的提議被拒絕，S1正式發(fā)布了提議: 1號提議生效。
