Paxos 学习总结，paxos学习总结

Paxos 学习总结，paxos学习总结

        最近学习了分布式领域的重要算法Paxos，这里罗列下关键点当作总结。自己水平有限，难免存在谬误，恳请读者指正。本篇不包括Paxos的基本理论介绍，Paxos基础可以参考下面的学习资料章节。

1 Paxos图示

        画图总结了原始的Paxos算法，主要来源于Paxos Made Simple。没有Leader也没有任何优化过程，并且把Proposer/Acceptor/Learners分开表示。这只是为了更容易梳理出三者之间的关系。我们只要知道实际Paxos工程中会把这三者重叠处理就可以了。

        Phase 1注：

        1 Proposer向一个多数派Acceptor发送阶段1a消息时，所谓多数派可能是全部Acceptor也可能只是一个大于50%的Acceptor集合。

        2 阶段1可能产生多个Master，在若干Master进入阶段2后，仍有可能有新的搅局者进入阶段1，Paxos的各个阶段是可以互相重叠的。也就是说可能出现某个Proposer处于阶段1而另一个Proposer处于阶段2中，且这两个Proposer也完全有可能因为访问同一个Acceptor而互相影响。处于阶段1和阶段2的Proposer之间的作用就是通过图中的虚线完成的：一个处于阶段2的Proposer因为给某个Acceptor的(num value)赋值导致另一个处于阶段1的Proposer不得不放弃自己的取值转而使用这个阶段2的Proposer的取值。

        Phase 2注：

        Q：如果多个Master已经发送2a消息，是不是未来的确定性取值一定在这几个Proposer中产生？
        A：当然不是，因为随时可能会有新搅局者在此时加入阶段1，假设x(3) y(5) 两个处于阶段2的Proposer(3,5是其n值)已经发出2a阶段消息，但龟速网络导致x的包在路上耽误了，而y的包也只到达了1个Acceptor，其他的包在路上。此时一个新的搅局者z加入阶段1，发送了更大的n(假设是6)，由于n大于Max(Max是5，6>5成立)所以它迅速获得资格进入阶段2并使用自己的值提交Acceptor，此后即使x和y的龟速消息再到达也无济于事了，因为Acceptor的Max已经被z的阶段1消息抬高了，x和y的阶段2a消息会被Acceptor丢弃。当然了xy战胜z的概率还是很大的，因为只要xy的2a阶段消息能在z的阶段a1阶段到达Acceptor前，抢占一半以上的Acceptor，就可以了。因为这样就有一半多的Acceptor会阻挡掉z的阶段1a消息(作用路径是图中虚线)，迫使z无法使用自己的值，而只能接受y已经设的值。

        Phase 3注：

        1 学习过程是可能会乱序的，所以必须按照id(也就是图中Phase3的num)递增顺序学习。

        2 阶段3的学习过程，消息传递时有多种选择，比如简单的多对多，m个Acceptor和n个Learner建立m*n条消息链路，然后发送消息。或者多对一对多，即所有的Acceptor将消息发送给一个固定的Learner，然后这个Learner再广播给所有其他Learner。可参考<<Paxos Made Simple>> 2.4节

2 学习资料

        我觉得读论文大概是学习Paxos的最好的方式了，读不懂怎么办？一篇一篇换着读。下面4篇论文从不同的方面论述了Paxos原理及应用场景，内容虽有重复但也有很大互补性，仔细阅读这4篇基本可以对Paxos有全面的理解。我觉得作为最早发表Paxos算法的<<The Part-Time Parliament>>反而可以略过不读，或者在全面理解Paxos后再当作历史读物看看。

        1 <<Paxos Made Simple>>(原文，中文)

        这是Lamport 2001年写的基本上就是<<The Part-Time Parliament>>的简化版本。我觉得这篇比较通俗易懂。同时中译文质量也很高而且关键位置译者添加了一些注释有助于理解。在这里面Lamport强调的是Paxos的两阶段执行过程，最后的Phase 3没有被当作独立的阶段(Lamport用独立章节2.3介绍了Phase3)，不过在其他文献中更多把Paxos看作3阶段的过程，第3阶段也就是学习阶段。个人觉得3阶段更方便理解所以在作图的时候分为三阶段了。

        2 <<The Chubby lock service for loosely-coupled distributed systems>>(原文，中文)

        文章作者就是提出“世上只有一种一致性算法，那就是Paxos”的Mike Burrows。他在Google也是Paxos方面的先驱，而这篇Chubby也被下面Google自家的<<Paxos Made Live>>作为第一参考文献来引用。这篇Google工程实践经验主要介绍了Paxos在工程中的应用，Paxos的两大用途之一就是分布式锁，Google使用Paxos完成了其内部的分布式锁服务Chubby。这篇文章围绕3个主题：1什么是分布式锁 2Paxos如何作为分布式锁来使用 3工程实践中的各种困难如何克服。同时我们也能从这篇里寻觅到GFS和Bigtable是如何与Chubby配合的。

        3 <<Paxos Made Live>>(原文，中文)

        这篇应该算是Google对于其内部使用Paxos的总结，相比于Chubby那篇总结性更强，同时对于Paxos算法本身也有一定介绍 。本篇文章在Chubby篇之后写成，其参考文档里的第一篇就是那篇Chubby。本文很适合作为学习完Paxos原理后的第一篇文章来阅读。通过工程师视角描述的Paxos更容易被工程师理解（以后看到任何Engineering Perspective的字样要注意了，很可能会有惊喜哦）。比如在解释为什么实现一个Paxos系统如此困难时，他们是这么说的“虽然Paxos算法本身用一页伪代码就可以描述下来，但是我们的完整实现包含了数千行C++代码。代码膨胀并不简单地是因为我们采用了C++来取代伪代码，也不是因为我们代码风格的繁琐。将该算法转换为一个实际的，产品级系统需要引入很多的features和优化(有些是已经发表过的研究成果，有些不是)。”。对于Paxos的“在某个值上达成一致”这样的用法，它也明确介绍成“在我们的系统中，需要在‘(多副本)日志中的下一条记录是哪条’上达成一致。”，这种文章读起来真是酣畅淋漓！

        4 <<Consensus on Transaction Commit>>(原文，中文)

        两位图灵奖作者合著的文章必须不能错过。这篇同时由两位理论创始人介绍了自家的2PC和Paxos，然后提出了一个2PC和Paxos杂交出的Paxos提交算法。通过正常情况和异常情况的性能对比，得出结论“两阶段提交实际上与只有一个协调者Paxos提交是同构的”。这篇文章可以作为学习2PC和Paxos的一篇不错的文章。

        5 <<布式锁服务>>(链接)

        这篇要比上面4篇来头小多了，是国内大学生论文性的文章，作者的团队基本实现了一个简化版的Chubby，但是因为文章来源于实践还是很有意思，非常值得一读。

3 Paxos实例与Mutl-Paxos
        一个Paxos实例就是一次完整的Paxos运行过程。即完整的执行一遍Phase1~3(假设没有优化)，向Paxos提交一个value值就意味着在提交该value值时会启动一个Paxos执行实例。实际系统会以Paxos为基础来实现在一系列value值上的一致性，比如把一个日志文件，逐条的分发到一个多机的备份环境，每次分发一条日志可能就是运行一次Paxos实例。多个Paxos实例连续运行也就是Mutl-Paxos，Mutl-Paxos有几种优化方法，可以参考<<Paxos Made Live>> 4.2及5.2节。

4 编号n的选择
        Proposer需要选出一个递增的唯一序列号，有一种非常形象直观的方法：在一个具有n个副本的系统中，首先为每个副本r分配一个在0和n-1之间的标识符Ir。副本r可以选择一个比它所有已知的序列号大的最小s作为序号，同时保证s mod n=Ir。举例来说，在一个5副本的Paxos系统里，可以为副本1制作一个序列号队列0，5，10，15...为副本2制作好序列号队列1，6，11，16...以此类推，当Proposer需要增大序列号时，即从自己的队列里顺序取出一个即可，这样就保证了每个Proposer取出的都是全局最大而且与别人不重复的编号了。可参考<<Paxos Made Live>> 4.1节

5 paxos优化

        这里优化的基础和原始Paxos算法有微小差异，这里假设所有的Proposer是由一个固定的Leader来发起请求的，选出一个Leader来作为唯一的提案提出者可以防止活锁，活锁是由于不断的新Proposer提出更高编号的阶段1a请求而导致每个Proposer完成阶段2a的消息。关于Leader可参考<<Paxos Made Simple>> 2.4节

        1 可以通过让Leader仅给半数以上的Acceptor发送阶段2a消息来减少正常情况下的消息数。Leader只要从半数以上的Acceptor接受到阶段2b消息，就可以知道v已经被选定，如果未收到足够多的阶段2b消息，再向其余的Acceptor发送阶段2a消息。这种方法可参考<<Consensus on Transaction Commit>> 4.1节

        2 可以将多个Paxos实例串联起来以减少消息数目。如果在多个实例执行中，协调者(也就是Leader)没有变化，那么阶段1a 1b的消息可以被忽略。为了从这个优化中获益，Muti-Paxos算法会设计很久才会选举一次Leader(这其实就是Fast Paxos的基本思想了,其实这也比较符合直觉，选举Leader其实不是保持一致性的主要工作，而是为了应对异常而已，在很多实现里，选举Leader这一步往往是被简化的)。这种方法可参考<<Paxos Made Simple>> 4.2节
        3 Acceptor在选定v后直接广播给learner，而不是先发送给Leader，再由Leader转发给Learner，这样以额外消息数为代价将阶段3的消息延迟消除，与Leader类似，在这些进程收到来自半数以上的acceptor的阶段2b消息后，就可以获知被选定的value值了。这种方法可参考<<Consensus on Transaction Commit>> 4.1节

6 Paxos用法
        我觉得<<大规模分布式存储系统>>中的说法比较准确的，Paxos有两种用法：

        1 实现全局的锁服务或者命名和配置服务，例如Google Chubby以及Apache Zookeeper。

        2 将用户数据复制到多个数据中心，例如Google Megastore以及Google Spanner。

        对于用途2相对好理解，因为原始Paxos示例就展示了复制数据到多备份机的功能。对于用途1，可以阅读Chubby论文来学习：首先要明白Paxos分布式锁是建议性锁而单机的类Mutex是强制锁，作为建议性锁要求使用方在使用资源前主动询问锁的状况，建议锁和资源在物理上是分离的，防君子不防小人。我们假设建议性锁与Mutex一样，会有一个类似id的身份标识。分布式锁的id不是"123abc"这样的无意义标识符，而是高大上的Unix文件路径格式，从"123abc"变成"/123/abc"，这样id变得非常直观，因为可以通过id直接表示出锁是哪个组哪个应用的哪个功能的，这样的名字"/projectX/groupA/add"明显比"123abc"要直白了很多。这种路径同时使得锁具备了层级父子关系也非常容易引入更多特性。要明白这种表示法其本质上与Unix的文件系统关系不大，因为"/"完全可以用别的符号比如“｜”代替，比如"|projectX|groupA|app"，写成反斜线完全是为了照顾程序员的直觉，减少学习成本(Chubby 论文是这么说的“因为Chubby的名字空间结构类似于文件系统......同时也降低了培训Chubby用户的难度。”)。所谓锁的id表示法更雅观的名字应该叫命名空间，这类似于编程语言的命名空间：通过层级关系最终定位一个类/变量的方法。

        看完了命名空间，那Paxos究竟如何当作分布式锁使用呢？Paxos的基本用途就是使得多台机器在一个确定性取值上达成一致。假设现在有一个5备份机的Paxos环境，我们就叫它5Paxos。有一个外部项目Xapp要使用5Paxos作为分布式锁，Xapp要锁住自己的某个服务http://www.xxx.com/make-id，它需要先向5Paxos发送一个lock值，和自己申请的路径"/Project/Xapp/make-id"。这样5Paxos就在这个确定性取值(“/Project/Xapp/make-id”是lock还是unlock)上达成一致，当前的一致就是lock。只有当Xapp再发送一个unlock后，5Paxos在新的取值unlock上重新达成一致。因为是建议性锁，所以Xapp内部任何要使用这个make-id接口的服务必须在使用前主动检查一下5Paxos存储的"/Project/Xapp/make-id"锁定状态是lock还是unlock。并遵守“在unlock时不访问这个服务”的君子协定，这样锁的作用就最终达成了。而作为分布式锁的最大优点就是高可用性，5Paxos的5台备份机中坏掉2台完全不影响这个锁的正常工作。

　　都说勤能补拙，但是勤要勤到点子上。
　　不要盲目的学习，做一道题要有一道题的收获。千万不要机械地做题，做对就算了，做错就看答案改正。做题要细细地做，知道题目在考什么知识点。做错了要分析自己哪里出错了，不要把问题归结到粗心，粗心的实质往往是不熟悉,是计算能力低下。找出问题有针对性地学习。做透一道题，就算一开始做错了，也比你机械地完成10道题更有收获。
　　另外要养成做笔记的习惯，但是做笔记不是叫你抄老师上课的板书，而是记录自己学习时的收获，一点一滴地累积，可以是一个不懂得字的读音，可以是文言文里一个不会的名词，可以是一个不懂的英语单词，也可以是一道做错的题目，或者一道做对的难题。
　　总结如下：
　　善于利用时间
　　在学习中，你不仅要懂得珍惜时间，更要学会运筹时间，使自己在最短的时间内，得到最大的学习效果。

　　合理分配精力
　　在学习中，你必须分清主次，合理地分配自己的精力，从而使自己在繁重的学习中保持清醒的头脑，用有限的精力来帮助自己取得尽可能高的学习效率。

　　学会排除干扰
　　在学习中，来自外界和自身的一些干扰都会影响你的学习效率，你必须要学会排除和隔离这些学习中的消极因素，将它们的负面效应降到最低。
 

总结
时光如逝，岁月如流，一转眼的时光，1年的学习生活已经过去了.,在小五学年的学期末,特写此文以总结一学期的学习好与坏.期末考试的好与坏都看这一年的努力多少,我这一学期的表现都会在这里展现.
这一年来.在老师和同学们关心、帮助下，通过自身不断努力，各方面均取得一定的进步。
在同学之间的互相学习中，体会到了知识就是人的力量源泉，没有专业知识、专业技巧，什么成功都不会与你相约，只有真正的掌握了解所学的东西才能便于日后面对社会的种种问题。对于现金社会，我要不断的充实自己，完善自己，使自己能够成为适应这个社会的专业人才，
将来如果社会给我机会的时候，我就能以我的所学完完全全的融会到往后的工作当中去，
所以现在属于我们的知识储备期。曾经有位老师跟我们说过：人的机遇难求，
当机遇来的时候就要好好的抓住它，当时如果你没有驾驭它的能力，
你还是只能眼睁睁的看着它从你的身边溜走，而无可奈何，与其到时后悔，
不如现在好好储备自己的知识量，时刻准备着，等待着机会的到来。……
总结现在有以下几点:
第一，学习态度比较端正。能够做到上课认真听讲，不与同学交头接耳，不做小动作，自觉遵守课堂纪律；对老师布置的课堂作业，能够当堂完成；对不懂的问题，主动和同学商量，或者向老师请教。

第二，改进了学习方法。为了改进学习方法，我给自己订了一个学习计划：
（1）做好课前预习。也就是要挤出时间，把老师还没有讲过的内容先看一遍。尤其是语文课，要先把生字认会，把课文读熟；对课文要能分清层次，说出段意，正确理解课文内容。
（2）上课要积极发言。对于没有听懂的问题，要敢于举手提问。
（3）每天的家庭作业，做完后先让家长检查一遍，把做错了的和不会做的，让家长讲一讲，把以前做错了的题目，经常拿出来看一看，复习复习。
（4）要多读一些课外书。每天中午吃完饭，看半个小时课外书；每天晚上做完作业，只要有时间，再看几篇作文。

第三,每天回家我就先完成老师布置的作业，然后完成妈妈布置的作业，做完作业，看一些课外书。虽然我每天这样学习，但月考时，我的成绩却不很理想。
最后一次月考后，在老师和爸爸、妈妈的帮助下，我对自己的学习进行了认真总结，从中悟出了不少好的学习方法。
我有个不足的地方。就是有时听老师布置作业时不够专心，总是一只耳朵进，一只耳朵出，回到家里糊里糊涂，只好打电话问同学了。
在新的学期，我要发扬成绩，改正错误，更加刻苦努力、一丝不苟的学习，争取每门功课都能取得好的成绩，当一个名副其实的好学生。同学,关心集体,尊敬老师,经常帮老师干活,且帮助集体做事.