分布式协议-两阶段、三阶段提交、paxos、raft备份
又撸了一遍分布式协议，准备自己对paxos复盘下，下面是感觉还不错可以参考的文章, 知识只能是常看常新了。
推荐书：从PAXOS到ZOOKEEPER分布式一致性原理与实践
-
维基百科之Paxos算法
大家都是这个写的最经典，但是真心看不懂啊，可以先撸一遍留下来印象，回头再撸 -
如何浅显易懂地解说 Paxos 的算法？
好多的回答，挑着看吧 -
关于分布式事务、两阶段提交协议、三阶提交协议
算是基本说明吧 两阶段 3阶段 -
Raft协议实战之Redis Sentinel的选举Leader源码解析
这个可以做补充 -
Zab vs. Paxos 原
提到paxos算是有限状态机，理解的一个新思路，zab那块不是很明白顺序性怎么回事。
-zookeeper入门系列-理论基础-zab协议
1 文章摘抄
basic paxos一些想法
- basic paxos一些想法：
分布式一致性与分布式锁之间存在差别，例如对于一个值同时发起两个修改，一致性不确保两个修改都会执行，执行其中任意一个都是可能的，常见情况是其中一个返回修改失败，再次进行修改后成功。一致性只保证所有机器中的值是相等的。其实在预决议和最终决议两个阶段，acceptor的策略是一样的，同意编号更大的，proposer的策略也是一样的，超过一半同意就执行下一步。但是因为时序问题，不同消息到达acceptor时，acceptor存在不同情况（错位），需要作出一个能最终达到一致性的决定，
优先级：更大编号的最终决议>更小编号的最终决议>更大编号的预决议>更小编号的预决议>没有预决议。
作者：楼虎彪
链接：https://www.zhihu.com/question/19787937/answer/370367692
提议ID生成算法
image.png
作者：凉拌灰土
原文：https://blog.csdn.net/cnh294141800/article/details/53768464
有的文章这么写，有的从别的地方直接贴，容易把人看糊涂了。
我说下自己的理解，
主要要看m的理解，m应该是最新的生成轮次。看下计算式子：
s%n=ir ==> s= m*n+ir ==> m=(s-ir)/n, s是已知的，s是当前节点自增值和接收到acceptor的拒绝后所得到的值比较后最大的那个值，ir是节点编号，n是当前节点个数。注意paxos协议里面如果acceptor拒绝的话会回传最新的值是哪个proposer提交的，所以这个例子应该这么写：
例： 以3个proposer P0、P1、P2为例，开始时各节点的初始m=0,编号分别为0，1，2。
1） P0提交的时候发现了P1已经提交，P1编号为1 >P0的0，因此P0重新计算编号：当前最大的s是1，是P1提供的，那最大s对应m的计算公式是m1=(s1-ir1)/n,即为m=(1-1)/3=0，当前节点m是0，与P0现在的m是相等的，因此m++；那new s0=m*n+ir0 即为1*3+0=3
2） P2以编号2提交，发现小于P0的3，因此P2重新编号：当前最大的s是P0的3，所以m=（3-0）/3=1;比当前节点的m大，所以当前节点的m需要等于最新的m，那new P2 = 1*3+2 = 5。
这个算法如果proposer扩节点了怎么整？
paxos协议的问题
-
活锁问题。在base-paxos算法中，不存在leader这样的角色，于是存在这样一种情况，即P1提交了一个proposal n1并且通过了prepare阶段；此时P2提交了一个proposal n2(n2>n1)并且也通过了prepare阶段；P1在commit时因为已经通过了n2而被拒绝；于是P1继续提交一个proposal n3并且通过prepare阶段；巧的是此时P2开始commit了，由于n2<n3再次被拒绝……如此循环往复。这种情况被称为活锁。即整个系统都没死，但由于互相请求资源而被互相锁死。为了不发生活锁的情况，最简单的方式当然是缩减proposer到一个，这样就不会发生互相请求锁死的情况，也即退化。事实上很多后来的工业级协议，都是paxos协议的退化或者变种。
-
复杂度问题。base-paxos协议中还存在这样那样的问题，于是各种变种paxos出现了，比如为了解决活锁问题，出现了multi-paxos；为了解决通信次数较多的问题，出现了fast-paxos；为了尽量减少冲突，出现了epaxos。可以看到，工业级实现需要考虑更多的方面，诸如性能，异常等等。这也是为啥许多分布式的一致性框架并非真正基于paxos来实现的原因。
-
全序问题。对于paxos算法来说，不能保证两次提交最终的顺序，zab解决了这个问题。
作者：liweisnake
原文：https://blog.csdn.net/liweisnake/article/details/70045164
2 撸了好几天paxos算法了，按照自己的理解整理下。自己写了个流程图，便于理解吧。
分布式算法.png
3 数学归纳法
看了好久也没看明白算法的证明，恶补了下数学归纳法，高中的知识已经还给老师了。。。。。
按照出题的形式来吧，一般数学归纳法证明的数学题都张下面这样。手写吧,电脑写数学题还是麻烦。
微信图片_20190412172811.png
