乒乓狂魔
TA的个人档案
个人介绍
暂无个人介绍
擅长的技术
- Java
- 容器
- 数据库
- 高分内容
- 最新动态
- 文章
- 问答
-
发表了文章 2016-12-04
招募有志青年
0 初衷 现在有很多的技术交流群，很多的群都是这样的： 1 经常扯淡 2 很多伸手党 3 一些道听途说的结论都拿来作为自己的观点 4 技术交流的深度不够 花费了很多时间在群上，但是收获缺并不多。而想找到一个有深度的交流群，而不是一个问答群。希望如下： 1 针对一个话题，感兴趣的人都能够进行深入研究后，然后再在一起相互探讨 2 有很多处于相同阶段的志同道合的伙伴，大家都非常上进 而我就是这样的一个处在初级阶段的一个人，最近也在迷茫，该怎么去发展，想找同龄人一起交流。下面先简单谈谈我最近的粗浅感受，与君共勉 1 感受 1.1 深度和广度 有的人会告诉你要专一一点，不要什么都学。有时候你自己倒是想多补充补充广度，形成一个知识体系。 深度和广度其实有时候很难把控，可能你所谓的深度根本就不深。 我这个小白目前的想法是： 广度：初始阶段，扩展扩展广度。如中间件、数据库、分布式领域。 基本的数据结构和算法，JDK集合源码，多线程（锁、线程池） web:SpringMVC、Spring事务体系、mybatis或hibernate、数据库连接池 通信：TCP/IP，NIO框架Netty、thrift，RPC中的dubbo 消息队列：kafka、RocketMQ等 调度： 中间件形式的：quartz集群方案、elastic-job（它的Elastic-Job-Cloud也提供资源调度） 大数据方向的调度： oozie、zeus：把不同类型的调度job代码封装起来然后和大数据组件进行交互，用户只需写配置即可 大数据组件内部的调度，又会细划分为资源调度(yarn)和任务调度(AppMaster) KV存储：redis、memcached 关系型数据库如mysql的基本原理，sql引擎、事务（隔离级别、锁、MVCC）、binlog redo undo log、主从复制原理、高可用方案 分布式一致性：paxos、Raft、ZAB。ZooKeeper、etcd 分布式存储： NOSQL：redis的cluster、codis方案，HBase NewSQL:Spanner、CockroachDB、TiDB、OceanBase等。 上述众多分布式存储的共性部分可以简单概括为2个方面： 1 分片：hash分片如codis、Range分片如HBase、CockroachDB，又如消息队列这类存储天生具有良好的可分片特性（topic和partition）。还有分片这类meta信息的高可用存储，分片的调度（如分片的迁移或者分片的拆分）。如kafka通过leader选举选出一个Controller来管理meta信息（由于meta信息少，所以通过Controller的调度使得每个KafkaServer都存储了一份）和分片的调度。 2 分片的一致性和高可用：倾向于使用paxos、raft来实现分片的同步。如CockroachDB、TiDB使用raft，Spanner、OceanBase使用paxos。 分布式事务： 中间件层面：X/Open DTP模型（不仅与数据库对接还可以与其他实现XA协议的RM对接）、JTA，常采用2PC来实现，如ByteTCC框架 分布式存储层面：如google的Percolator分布式事务方案，小米的Themis（为HBase添加分布式事务支持）也是基于Percolator。很多都是2PC并且进行优化的方案。 提到了分布式事务又不得不说分布式时序问题： google的TrueTime CockroachDB的HLC 授时服务 分布式计算:MapReduce、Spark等等 几年内把这些东西的原理以及其中存在的缺陷搞清楚（根据自己的方向，有些深入理解，有些会用即可，有些可能涉及不到，有些漏掉，毕竟方向太多了）。能够融汇贯通，能够看到一些共性的东西，而不再把他们当做一个个孤立的软件来看待。很多设计都是相通的，很多问题是各个软件都会遇到的，如果你能总结出来，那么理解就会更加深入了。 这个时间因人而异，勤奋和懒惰的差距当然很大。 这个阶段还没到深入的地步，比如paxos论文你看懂了，但是真实落地到实际的生产系统又是一层挑战。比如你能看懂dubbo，不一定能自己写出来。 这个阶段同时要加强自己的代码能力，为下个阶段做准备。 深度：深入阶段，找到自己的感兴趣的方向，深入做下去，去面临现实中的各种挑战，去做出创新，如 消息队列，加入大厂的消息队列团队，真正去做出一个开源产品来 NOSQL：如深入搞HBase，成为committer啥的 分布式KV、分布式数据库 这个阶段当然需要专注在某个领域内，需要一定时间的积淀（当然我也没啥话语权，还没到这个阶段，只能这么粗略的认为）。 1.2 眼界 特别是我们这种普通程序员，如果局限在自己狭窄的范围，你可能放松对自己的要求。 比如学习ZooKeeper： 有些人就会用用 有些人看些文章了解其中的原理，自己咀嚼别人的知识 有些人看看源码，自己主动获取知识，但处于一知半解的状态 有些人源码看的更加深入一些，真正理解背后的设计，背后所面临的一致性问题 有些人不仅仅局限于ZooKeeper，开始扩展到其他系统，也能解决其中的不足，有条件的话自己也能造轮子 所以提高自己对知识的要求，你做的还远远不足。 1.3 打好基础 学好英语 需要看国外大师的一些博客文章、各种paper。所以学好英语是必须过的一关。 学好数据结构和算法 很多时候都会提出我们做web开发的需要学这些吗？正是因为你不会，才只能做这个。 1.4 多总结 举例如下： 当你面对redis的全量和增量同步中存在的问题时，你是否曾想其他软件是否也存在这个问题，他们又是怎么解决的？多去了解了解，做到融汇贯通 看文章：现在的文章真的太多太多了，这就导致了我们很多时候仅仅是粗浅的浏览了下，并没有去深入其中的细节（可能作者对于每一处都很认真的推敲，可能作者也是不负责任的写一写，这个需要你自己去辨别）。现在很多文章都没有高质量的评论交流可以从侧面看出，现在大家的阅读一般都很粗浅。 2 想做的事 2.1 愿景 想笼络想奋进的人进群，群人数保持在30到50人。 每周至少开展1个话题，由话题提出者主导研究，其他人感兴趣的参与研究，然后在某个固定时间大家一起交流。多个话题可以同时展开，各自参加各自的话题小分队 基本不允许提简单的问题，这种一般自行解决，最好提一些有质量的话题。这里是一个交流的平台，而不是一个问答平台。 长时间不参与各种话题只能劝退出群了，等你有空研究再参与进来 各种弄虚作假者来蹭的也会劝退 2.2 要求条件 想成大牛的潜力股，具有自我驱动力，能自主去研究一些东西 读源码是最最最基本的要求 对技术有自己独到的见解和认识 乐于分享技术（有自己的技术博客最好，并且要求博客内容质量高） 大牛也可以进来指导指导（哈哈） 满足条件的可以先看下下面的测试题，挑选其中3个回答，然后私信留言，核对后拉进群，一起讨论学习。 不满足条件的不要怪别人不给机会，只有自己先变得上进起来，别人自然会去主动找你。 2.3 预先的测试题 1 Guava RateLimter中预热是怎么一回事 2 你觉得RedLock有没有问题？如果有指出来 3 分布式一致性算法中，选举出新的leader后，Raft和ZAB是如何处理上一个leader残留的还未提交的事务的 4 如何改进kafka的日志丢失问题 3 话题内容 这里准备把一些话题列出来，仅供参考，大牛就不要拍砖了。 3.1 分布式锁话题 有哪些方案？ 方案都有哪些缺陷，你对RedLock怎么看？ 从各种方案中你能总结出如何来设计分布式锁？有哪些要点？ 3.2 红黑树 如何看待算法导论中红黑树的相关操作的解法 你是否能直接描述出如何插入删除数据的过程 3.3 恢复技术以及副本同步（增量和全量同步） redis的rgb和aof ZooKeeper的快照和事务日志 hdfs的image和editLog kafka？ mysql？ 上述几种都会面临如何恢复，以及如何进行副本同步。 这些过程中有哪些技术难点？他们分别是怎么应对的？ 你能总结出来什么东西？ 3.4 paxos 1 paxos的针对场景的误解： 达成一个建议的场景 日志复制场景 2 paxos的运行过程 3 paxos的证明过程 4 base paxos与ZAB和Raft的区别如多写入还是单写入 5 base paxos和multi-paxos 6 使用多轮的base paxos来进行日志同步，见使用Basic-Paxos协议的日志同步与恢复 7 使用Multi-Paxos协议的日志同步使用Multi-Paxos协议的日志同步与恢复 8 对于上述7文章中的幽灵复现问题的讨论 3.5 undo redo binlog 1 undo redo 都可以实现持久化，他们的流程是什么？为什么选用redo来做持久化？ 2 undo、redo结合起来实现原子性和持久化，为什么undo log要先于redo log持久化？ 3 undo为什么要依赖redo？ 4 日志内容可以是物理日志，也可以是逻辑日志？他们各自的优点和缺点是？ 5 redo log最终采用的是物理日志加逻辑日志，物理到page，page内逻辑。还存在什么问题？怎么解决？Double Write 6 undo log为什么不采用物理日志而采用逻辑日志？ 7 为什么要引入Checkpoint？ 8 引入Checkpoint后为了保证一致性需要阻塞用户操作一段时间，怎么解决这个问题？（这个问题还是很有普遍性的，redis、ZooKeeper都有类似的情况以及不同的应对策略）又有了同步Checkpoint和异步Checkpoint 9 开启binlog的情况下，事务内部2PC的一般过程（含有2次持久化，redo log和binlog的持久化） 10 解释上述过程，为什么binlog的持久化要在redo log之后，在存储引擎commit之前？ 11 为什么要保持事务之间写入binlog和执行存储引擎commit操作的顺序性？（即先写入binlog日志的事务一定先commit） 12 为了保证上述顺序性，之前的办法是加锁prepare_commit_mutex，但是这极大的降低了事务的效率，怎么来实现binlog的group commit？ 13 怎么将redo log的持久化也实现group commit？至此事务内部2PC的过程，2次持久化的操作都可以group commit了，极大提高了效率 3.6 AQS 1 AQS中一旦某个线程1获取到了锁正在执行同步代码块，这时候其他线程再来获取锁，他们会不断的CAS尝试获取锁一段时间之后再被阻塞还是立马被阻塞呢？ 这个问题要综合的考虑，既有AQS的问题又有AQS对外留出的tryAcquire方法的问题
-
发表了文章 2016-11-28
红黑树解法的why而非how
0 初衷 很多介绍红黑树的文章如同算法导论书中那样，都是上来直接给出一些分类情况，以及每个分类情况下的处理办法，而没有着重讲述为什么这么分类，为什么这个分类下执行这些操作，即只介绍了how，没有重点给出why。本篇文章的重点就在于解释why。 这样可能就导致一种现象：我按照这些分类以及分类下的操作办法，的确完整的走通想通了整个算法过程，感觉应该理解红黑树了，但是可能过了几个月后就忘记如何分类的了，忘记分类下如何操作的了。 归根到底是我们没有找出最本质的东西，比如说插入节点时遇到父子是红红的问题，对应的2个直接的解决办法如下： 将父节点改成黑色 将一个红节点扔到另一个子树中 这2个解决办法就是直接解决当前父子红红问题的，然后就可以在这2个办法的基础上进行详细的开展，就会推出插入节点时的分类情况及其操作办法了。文章的后面会详细展开这部分的推理，下面还是先把基础的二叉搜索树介绍下。 1 二叉搜索树 1.1 定义 二叉搜索树中的每个节点含有如下属性，key、left、right、p，分别对应该节点的值、左孩子、右孩子和父节点。 并且满足如下性质： 设x是二叉搜索树的一个节点，如果y是x左子树中的一个节点，那么y.keyx.key。 如下所示： 1.2 基本操作 最大、最小值都很简单，这里不再赘述了。 1.2.1 前驱和后继 按照中序遍历的方式来给出指定节点的前驱和后继 后继 如果该节点有右子树，则后继节点就是右子树的最小值 如果没有右子树，则后继沿着该节点往上找到一个父节点，该父节点的左子树包含当前节点。 如何来理解呢？ 中序遍历的顺序为：左根右。那么以当前节点作为根，查找它的后继： 如果有右子树，则 为 (左子树)根（右子树） ，很明显紧跟根后面的就是右子树中的第一个元素，按照中序遍历的方式右子树中第一个元素就是右子树的最小值 如果没有右子树，则为 (左子树)根，该部分中序遍历结束，那么这一部分可能是上层父节点的左子树部分或者右子树部分，如果是上层父节点的右子树部分，那么上一层父节点的根在该部分的前面，即为 根1（（左子树）根），此时同理，上层父节点的根也中序遍历完毕，开始上上层父节点的遍历，如果还是右子树，继续轮回，即为 根2 根1（（左子树）根）， 如果是左子树，那么下一个父节点则在该部分的右面，即，根2 根1（（左子树）根）根3。所以我们要找的节点的后继就是根3。 最好在纸上进行划分下。该算法见算法导论中下图  前驱 同理 1.3 查找 也挺简单的，如下： 1.4 插入 也比较简单，就是对比找到一个节点，直到遇到NIL节点，则该NIL节点的父节点就是要插入节点的父节点 然后再判断要插入的节点是比父节点大还是小，大的话作为右节点，小的话作为左节点。 见算法导论中下图： 1.5 删除 针对要删除节点（设为z节点）的孩子，分下面3种情况： 无孩子：直接删除当前节点即可，修改父节点，用NIL作为孩子替换z。 只有一个孩子：修改父节点，将该孩子替换z。 有2个孩子：找到z的后继（这里设置为y）来替换z。此时的后继y必然是z的右子树中的最小值。这就需要先将y从右子树中摘出来，即需要先将y的右子树替换y，摘出y后，再用y去替换z。让z的左子树作为y的左子树，z的新右子树（摘除y之后）作为y的右子树。 总结下就是：y（一定没有左孩子）的右孩子替换y，y替换z的过程。 此时有一个可以优化的地方就是：如果y是z的右孩子，那么z的新右子树就是y的右子树，那么此时就可以不用摘除了。 算法内容如下： 先定义一个节点替换的方法： 整体删除逻辑如下： 至此，基础的二叉搜索树就算铺垫完成了，下面就是重点的红黑树了。 2 红黑树 2.1 红黑树的5个性质 1 每个节点或是红色，或是黑色 2 根节点是黑色 3 每个叶节点（NIL）是黑色 4 如果一个节点是红色，则它的2个子节点都是黑色 5 对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点 一颗红黑树示例如下： 可以得出的一些结论： 红黑树的任何一个节点的左右子树的高度最多是另一子树的2倍。 由性质5和性质4可以得出，最短的路径都是黑色节点，最长的路径有交替的红色和黑色节点，所以一个子树最多是另一个子树高的的2倍，就是所谓的近似平衡。 2.2 旋转 可以参见下这里的一个动画浅谈算法和数据结构: 九 平衡查找树之红黑树 旋转的作用： 用来平衡左右子树的高度，而不违反二叉搜索树的性质，简单可以理解为将一个节点扔到另一个子树中 2.3 插入 2.3.1 普通插入 按照上述二叉搜索树的插入方式 2.3.2 插入后的修正 新插入的节点着色为红色，暂叫z节点，z的父节点叫z.p，它会违反红黑树的哪些性质？ 违反性质2 如果插入节点是根节点，则违反了性质2。此时只需要将z节点重新着为黑色即可。 违反性质4 如果z.p是红色，那么就违反了性质4。下面就针对性质4来具体的分析怎么解决 目前要解决的问题是：z是红色，z.p也是红色 可以得到的一些结论： z.p.p必然是黑色 因为在z插入之前是一颗红黑树，必然要满足性质4，所以z.p.p是黑色，z的叔父节点是不确定的，可红可黑。 z的兄弟节点只能是叶节点（黑色的） z.p是红色的，则z的兄弟节点必须是黑色的，如果z的兄弟节点不是叶节点，则z的兄弟节点必然比z这一路多了一个黑色，不满足性质5，所以z的兄弟节点是黑色的叶节点。 解决问题的要领： 不能增加或者减少黑高，只能部分增加并且部分减少然后相互抵消 解决父子红红问题有2个思路： 1 把z.p变成黑色，z.p.p变成红色 2 把z和z.p中的一个红色节点扔到z.p.p的另一个子树中 再来详细分析下这2个思路： 1 把z.p由红色变成黑色，z.p.p由黑色变成红色 z这一路增加一个黑色，减少一个黑色，黑高不变。但是z的叔父那一路就会因为z.p.p而少了一个黑色，所以如果z的叔父是红色，那么可以将z的叔父由红色变成黑色来抵消z.p.p的减少。 所以这个就要求z的叔父节点是红色。 但是这并没有完，我们将z.p.p由黑色变成红色，可能又会出现父子红红的情况，所以继续下一次的轮回 初始为：  转变成如下：  2 把z和z.p中的一个红色扔到z.p.p的另一个子树中 这个扔的操作就是通过左旋或者右旋，目前假如是右旋，即将z.p提升为z.p.p的位置，将z.p.p拉下来作为z的叔父节点的一路。颜色上，z.p由红变成黑色，z.p.p由黑色变成红色（这就要求z的叔父必须是黑色，不然又出现红红）。此时z和z的叔父2路都没有增加或者减少黑色。同时z.p的右子树会作为z.p.p的左子树（右旋的结果），此时z.p.p是红色，则z.p的右子树必须是黑色，即z必须是z.p的左子树。 一种情况z本来就是z.p的左孩子，另一种情况z是z.p的右孩子，那么可以通过左旋就可以实现，然后减交换z和z.p的位置。所以这里又分2种情况。分析完毕，下面看图形示意。 初始为：  这里需要将4或者5中的一个红色扔到6的另一个子树中，那么执行右旋后如下：  这里其实就要求5节点必须是黑色，即在旋转前4节点的右孩子必须是黑色，那么z必须是4节点的左孩子。这里我们只需要执行下左旋，将可以将红色的子转变成红色的父的左孩子，此时再将z节点设置为红色的子即4节点即可，执行上述的操作了。  总上2点解决方案的分析，我们可以得出如下的3个分类情况以及解决办法： 1 z的叔节点y是红色 即按照上述思路1中的方式，把z.p由红色变成黑色，z.p.p由黑色变成红色，z这一路保持黑高不变，z的叔节点由红色变成黑色，同样保持了黑高不变。z.p.p重新定义为z，继续下一次的轮回。 2 z的叔节点y是黑色的且z是一个右孩子 即按照上述思路2中的方式，通过左旋，来保证z.p的右子树不能是红色，必须是黑色（因为这个右子树将来要作为红色节点的孩子节点） 3 z的叔节点y是黑色的且z是一个左孩子 即按照上述思路2中的方式，通过对z.p进行右旋，z.p顶替了z.p.p及其颜色，z.p.p拉下着为红色，并将z.p之前的右子树挂到z.p.p的左子树下。 2.4 删除 2.4.1 普通删除 再来简单回顾下二叉搜索树的删除： 要删除的节点为z 删除就是分如下的3个条件： z没有孩子：直接删除 z只有1个孩子：将孩子替换z z有2个孩子：用z的后继y来替换z，同时y的右孩子来替换y的过程。 2.4.2 修正 这时候可能有3个节点： z：要删除的节点 y：z的后继 r：y的右孩子 在没删除之前，要删除的节点z的颜色可红可黑，y可红可黑，r如果存在的话只能是红色（因为y是没有左孩子的，如果r存在并且是黑色的，那么r这一路包含的黑色节点个数比y的另一路多，不符合性质5）。 问题就来了：这里有几个位置的节点需要进行修复？z的位置？y的位置？r的位置？ 结合上面删除的3种情况来详细分析下： z没有孩子：直接删除。 如果z是红色的话，此时什么性质都没有违反。 如果z是黑色的话，那么就少了一个黑色，之后需要补一个黑色。 z只有一个孩子：直接将孩子替换成z。 如果z是红色，则z的孩子必然都是黑色，由于只有1个孩子，那么就违反了性质5，则这种情况是不存在的。 那么z只能是黑色，并且那一个孩子只能是红色。此时孩子替换了z，缺少了一个黑色，需要补回来。 z有2个孩子：y的右孩子替换y（如果有的话），y替换z 那么z的后继y要替换z，继承z的颜色，那么z处就仍保持不变。y的右孩子r（如果有的话）要替换y，那么此时可能违反性质的地方就是y处了。 如果y是红色，则孩子必须是黑色，y是z的后继，则y是没有左孩子，y如果有右孩子，则必然是黑色，此时又不满足性质5。所以y是红色的时候，y是没有右孩子的。那么此时删除y就不违反任何性质。 如果y是黑色，如果有右孩子，则必然是红色（如果是黑色则不满足性质5）。所以不管有没有右孩子，此时删除y都是少了个黑色的，需要补回来的。 从上面可以看到有时候是需要修复z处的，有时候是需要修复y处的。进行统一概括的话，设置一个变量为x节点，该节点为需要修复的地方，得到如下结论： 如果x处节点原本是红色的话，没有违反任何性质，不需要修复 如果x处节点原本是黑色的话，都是少了一个黑色，需要修复的 其中x在前2种情况下就是原z处节点，在最后一种情况下就是原y处节点。 下面要解决的问题就是：对x节点缺少一个黑色的修复 最直接的解决办法如下： 1 对x这一路多补充一个黑色节点，即执行一次左旋或者右旋，往x这一路多扔一个节点，然后将该节点着为黑色 2 对x的父节点加一层黑色 下面就来详细展开下上述2个解决办法，来推导出对应的情况： 1 对x这一路多补充一个黑色节点，即执行一次左旋或者右旋，往x这一路多扔一个节点，然后将该节点着为黑色 这时候相当于x的兄弟节点那一路要给出一个节点，即它就少了一个节点。少了一个节点还要能保住黑高不变，则必然是扔了一个红色节点过来。扔过来后，再把该节点着为黑色，就为x这一路多增加了一个黑色，从而弥补了缺少的黑色。 设定x的兄弟节点是w。上述扔的操作可能执行的是左旋也可能是右旋，这里先假定是左旋。则这里w的右孩子替代w，w替代w的父节点及其颜色，w的父节点拉下来，并着为黑色。 根据上述描述，要想保证w这一路在少了一个节点之后，黑色数目不变，则w和w的右孩子必然有一个是红色，一个是黑色（2红违反性质4所以不可能，2黑则必然要少一个黑色所以也不可能）。到底谁是红色呢？ w的左孩子要作为w的原来父节点（该节点要被着为黑色）的右孩子，所以w的左孩子要挂在黑色的父节点下，要想保证黑高不变，那么该节点之前挂在w节点下，那么w节点也必须是黑色，则w的右孩子是红色了。 下面来看下这个过程： 原本为： 经过上述左旋并着色的操作过程后为： 所以只要满足了w为黑色，w的右孩子为红色，就可以采用该解决办法 为了满足w为黑色，w的右孩子为红色。也分如下几种情况： w为红色，则w的孩子必然为黑色（你可能认为万一w没有孩子怎么办？这里是不可能的，因为w的另一路z缺少了一个黑色，那么之前必然有一个黑色，而如果w没有孩子，则w这一路必然比z那一路少一个黑色，不满足性质5，所以不存在这种可能）。这时候如果对w进行左旋或者是右旋必然会改变左右黑高的不平衡。w为红色，则w.p为黑色，此时可以把w这一路的红色扔过去即执行左旋，w.p变为红色，w变为黑色。w的左子树（左孩子为黑色）作为w.p的右孩子。重新更正w为原w的左孩子，由于颜色为黑色，则可转到如下几种情况： w为黑色，w的右孩子为红色，这种本身就满足 w为黑色，w的右孩子为黑色，左孩子为黑色：这种不存在红色，排除 w为黑色，w的右孩子为黑色，左孩子为红色：可以进行右旋，如下图所示的转换 原本为：  右旋并着色后：  2 对x的父节点加一个黑色父节点加一个黑色，那么就要求x的兄弟节点必须要减少一个黑色。从上述解决办法1种可以得到，只有在w为黑色，w的2个孩子都为黑色的时候，无法采用解决办法1。这时候可以来采用解决办法2。 将w着为红色，那么w这一路就可以减少一个黑色。 减少了一个黑色之后，如果x的父节点是红色，那么直接将红色着为黑色，即可达到父节点多加一个黑色。如果x的父节点是黑色，那么就意味着x的父节点无法增加一个黑色，即缺少一个黑色，即将x设置为x的父节点，重新进入下一个轮回。 你可能意识到，如果一直轮回直到x的父节点是根，此时仍无法添加一个黑色，那么此时相当于全部所有节点都减少了一个黑色，仍然是不违反任何性质的，只是比之前的黑高小1。 所以从上面的2个解决办法中可以总结出来如下算法导论中的4种情况： 1 x的兄弟节点w是红色： 可以通过左旋来重新更正w的位置，更正后的w为黑色，转为如下几种情况 2 x的兄弟节点w是黑色，w的孩子全部是黑色 利用解决办法2，将x的父节点加一个黑色，将w这一路减少一个黑色。如果父节点是红色，那么直接着为黑色即相当于加上了黑色，如果父节点是黑色，那么将x设置为x的父节点，认为此时x仍然是缺少一个黑色，即开始下一个轮回 3 x的兄弟节点w是黑色，w的右孩子是黑色，左孩子是红色： 可以通过右旋达到下面的情况4 4 x的兄弟节点w是黑色，w的右孩子是红色 可以利用解决办法1，将w那一路的红色节点扔到x这一路，然后着为黑色，即x增加了一个黑色。而w那一路减少的是一个红色，所以黑高仍然保持不变。 至此，我们来总结下删除的2个重要过程： 1 确定要修复的x的位置 x的位置可能是z处，也可能是y处。参见算法导论中这一个过程：  上述RB-TRANSPLANT函数就是节点替换的函数，RB-DELETE-FIXUP函数就是修正函数 2 修正过程 修正过程即按照上述的分析总结对应的4种情况来处理，见算法导论如下图  至此，总算是将红黑树主要的插入和删除描述完毕了。 3 红黑树总结 过程各种分析情况挺多的，但是我们更应该去记住本质的东西，从而能够达到自己去推理对应的过程，所以再次强调 插入： 为了解决父子红红问题，有如下2种直接的解决办法： 父节点设置为黑色 一个红节点扔到另一个子树中 删除： 为了解决缺少一个黑色的问题，有如下2种直接的解决办法： 增加一个黑色节点，可以通过左旋来得到，即另一子树扔过来一个红色（本身保证黑色不减少） 父节点增加一个黑色 我们从上述直接的解决办法中就可以推理出去，自然就能得到该怎么分类，每个分类下具体怎么操作了。 一个可以检验你是否真的理解红黑树的办法就是：不借助任何东西，你自己是否能够在一张白纸上自己推导一遍。 本文章涉及到细节很多，难免有疏漏的地方，还请批评指正。 欢迎继续来讨论，越辩越清晰。 欢迎关注微信公众号：乒乓狂魔
-
发表了文章 2016-11-07
Raft对比ZAB协议
系列文章 Raft算法赏析 ZooKeeper的一致性算法赏析 Raft对比ZAB协议 0 一致性问题 本篇文章想总结下Raft和ZAB在处理一些一致性问题上的做法，详见之前对这2个算法的描述 Raft算法赏析 ZooKeeper的一致性算法赏析 上述分别是针对如下算法实现的讨论： Raft的实现copycat，由于Raft算法本身已经介绍的相当清晰，copycat基本上和Raft算法保持一致 ZAB的实现ZooKeeper，由于ZooKeeper里面的很多实现细节并没有在ZAB里体现（ZAB里面只是一个大概，没有像Raft那么具体），所以这里讨论的都是ZooKeeper的实现 一致性算法在实现状态机这种应用时，有哪些常见的问题： 1 leader选举 1.1 一般的leader选举过程 选举的轮次 选举出来的leader要包含更多的日志 1.2 leader选举的效率 会不会出现split vote？以及各自的特点是？ 1.3 加入一个已经完成选举的集群 怎么发现已完成选举的leader？ 加入过程是否对leader处理请求的过程造成阻塞？ 1.4 leader选举的触发 谁在负责检测需要进入leader选举？ 2 上一轮次的leader 2.1 上一轮次的leader的残留的数据怎么处理？ 2.2 怎么阻止之前的leader假死的问题 3 请求处理流程 3.1 请求处理的一般流程 3.2 日志的连续性问题 3.3 如何保证顺序 3.3.1 正常同步过程的顺序 3.3.2 异常过程的顺序 follower挂掉又连接 leader更换 3.4 请求处理流程的异常 4 分区的处理 下面分别来看看Raft和ZooKeeper怎么来解决的 1 leader选举 为什么要进行leader选举？ 在实现一致性的方案，可以像base-paxos那样不需要leader选举，这种方案达成一件事情的一致性还好，面对多件事情的一致性就比较复杂了，所以通过选举出一个leader来简化实现的复杂性。 1.1 一般的leader选举过程 更多的有2个要素： 1.1.1 选举轮次 1.1.2 leader包含更多的日志 1.1.1 选举投票可能会多次轮番上演，为了区分，所以需要定义你的投票是属于哪个轮次的。 Raft定义了term来表示选举轮次 ZooKeeper定义了electionEpoch来表示 他们都需要在某个轮次内达成过半投票来结束选举过程 1.1.2 投票PK的过程，更多的是日志越新越多者获胜 在选举leader的时候，通常都希望 选举出来的leader至少包含之前全部已提交的日志 自然想到包含的日志越新越大那就越好。 通常都是比较最后一个日志记录，如何来定义最后一个日志记录？ 有2种选择，一种就是所有日志中的最后一个日志，另一种就是所有已提交中的最后一个日志。目前Raft和ZooKeeper都是采用前一种方式。日志的越新越大表示：轮次新的优先，然后才是同一轮次下日志记录大的优先 Raft：term大的优先，然后entry的index大的优先 ZooKeeper：peerEpoch大的优先，然后zxid大的优先 ZooKeeper有2个轮次，一个是选举轮次electionEpoch，另一个是日志的轮次peerEpoch（即表示这个日志是哪个轮次产生的）。而Raft则是只有一个轮次，相当于日志轮次和选举轮次共用了。至于ZooKeeper为什么要把这2个轮次分开，这个稍后再细究，有兴趣的可以一起研究。 但是有一个问题就是：通过上述的日志越新越大的比较方式能达到我们的上述希望吗？ 特殊情况下是不能的，这个特殊情况详细见上述给出Raft算法赏析的这一部分 这个案例就是这种比较方式会选举出来的leader可能并不包含已经提交的日志，而Raft的做法则是对于日志的提交多加一个限制条件，即不能直接提交之前term的已过半的entry，即把这一部分的日志限制成未提交的日志，从而来实现上述的希望。 ZooKeeper呢？会不会出现这种情况？又是如何处理的？ ZooKeeper是不会出现这种情况的，因为ZooKeeper在每次leader选举完成之后，都会进行数据之间的同步纠正，所以每一个轮次，大家都日志内容都是统一的 而Raft在leader选举完成之后没有这个同步过程，而是靠之后的AppendEntries RPC请求的一致性检查来实现纠正过程，则就会出现上述案例中隔了几个轮次还不统一的现象 1.2 leader选举的效率 Raft中的每个server在某个term轮次内只能投一次票，哪个candidate先请求投票谁就可能先获得投票，这样就可能造成split vote，即各个candidate都没有收到过半的投票，Raft通过candidate设置不同的超时时间，来快速解决这个问题，使得先超时的candidate（在其他人还未超时时）优先请求来获得过半投票 ZooKeeper中的每个server，在某个electionEpoch轮次内，可以投多次票，只要遇到更大的票就更新，然后分发新的投票给所有人。这种情况下不存在split vote现象，同时有利于选出含有更新更多的日志的server，但是选举时间理论上相对Raft要花费的多。 1.3 加入一个已经完成选举的集群 1.3.1 怎么发现已完成选举的leader？ 1.3.2 加入过程是否阻塞整个请求？ 1.3.1 怎么发现已完成选举的leader？ 一个server启动后（该server本来就属于该集群的成员配置之一，所以这里不是新加机器），如何加入一个已经选举完成的集群 Raft：比较简单，该server启动后，会收到leader的AppendEntries RPC,这时就会从RPC中获取leader信息，识别到leader，即使该leader是一个老的leader，之后新leader仍然会发送AppendEntries RPC,这时就会接收到新的leader了（因为新leader的term比老leader的term大，所以会更新leader） ZooKeeper：该server启动后，会向所有的server发送投票通知，这时候就会收到处于LOOKING、FOLLOWING状态的server的投票（这种状态下的投票指向的leader），则该server放弃自己的投票，判断上述投票是否过半，过半则可以确认该投票的内容就是新的leader。 1.3.2 加入过程是否阻塞整个请求？ 这个其实还要看对日志的设计是否是连续的 如果是连续的，则leader中只需要保存每个follower上一次的同步位置，这样在同步的时候就会自动将之前欠缺的数据补上，不会阻塞整个请求过程 目前Raft的日志是依靠index来实现连续的 如果不是连续的，则在确认follower和leader当前数据的差异的时候，是需要获取leader当前数据的读锁，禁止这个期间对数据的修改。差异确定完成之后，释放读锁，允许leader数据被修改，每一个修改记录都要被保存起来，最后一一应用到新加入的follower中。 目前ZooKeeper的日志zxid并不是严格连续的，允许有空洞 1.4 leader选举的触发 触发一般有如下2个时机 server刚开始启动的时候，触发leader选举 leader选举完成之后，检测到超时触发，谁来检测？ Raft：目前只是follower在检测。follower有一个选举时间，在该时间内如果未收到leader的心跳信息，则follower转变成candidate，自增term发起新一轮的投票，leader遇到新的term则自动转变成follower的状态 ZooKeeper：leader和follower都有各自的检测超时方式，leader是检测是否过半follower心跳回复了，follower检测leader是否发送心跳了。一旦leader检测失败，则leader进入LOOKING状态，其他follower过一段时间因收不到leader心跳也会进入LOOKING状态，从而出发新的leader选举。一旦follower检测失败了，则该follower进入LOOKING状态，此时leader和其他follower仍然保持良好，则该follower仍然是去学习上述leader的投票，而不是触发新一轮的leader选举 2 上一轮次的leader 2.1 上一轮次的leader的残留的数据怎么处理？ 首先看下上一轮次的leader在挂或者失去leader位置之前，会有哪些数据？ 已过半复制的日志 未过半复制的日志 一个日志是否被过半复制，是否被提交，这些信息是由leader才能知晓的，那么下一个leader该如何来判定这些日志呢？ 下面分别来看看Raft和ZooKeeper的处理策略： Raft：对于之前term的过半或未过半复制的日志采取的是保守的策略，全部判定为未提交，只有当当前term的日志过半了，才会顺便将之前term的日志进行提交 ZooKeeper：采取激进的策略，对于所有过半还是未过半的日志都判定为提交，都将其应用到状态机中 Raft的保守策略更多是因为Raft在leader选举完成之后，没有同步更新过程来保持和leader一致（在可以对外处理请求之前的这一同步过程）。而ZooKeeper是有该过程的 2.2 怎么阻止上一轮次的leader假死的问题 这其实就和实现有密切的关系了。 Raft的copycat实现为：每个follower开通一个复制数据的RPC接口，谁都可以连接并调用该接口，所以Raft需要来阻止上一轮次的leader的调用。每一轮次都会有对应的轮次号，用来进行区分，Raft的轮次号就是term，一旦旧leader对follower发送请求，follower会发现当前请求term小于自己的term，则直接忽略掉该请求，自然就解决了旧leader的干扰问题 ZooKeeper：一旦server进入leader选举状态则该follower会关闭与leader之间的连接，所以旧leader就无法发送复制数据的请求到新的follower了，也就无法造成干扰了 3 请求处理流程 3.1 请求处理的一般流程 这个过程对比Raft和ZooKeeper基本上是一致的，大致过程都是过半复制 先来看下Raft： client连接follower或者leader，如果连接的是follower则，follower会把client的请求(写请求，读请求则自身就可以直接处理)转发到leader leader接收到client的请求，将该请求转换成entry，写入到自己的日志中，得到在日志中的index，会将该entry发送给所有的follower(实际上是批量的entries) follower接收到leader的AppendEntries RPC请求之后，会将leader传过来的批量entries写入到文件中（通常并没有立即刷新到磁盘），然后向leader回复OK leader收到过半的OK回复之后，就认为可以提交了，然后应用到leader自己的状态机中，leader更新commitIndex，应用完毕后回复客户端 在下一次leader发给follower的心跳中，会将leader的commitIndex传递给follower，follower发现commitIndex更新了则也将commitIndex之前的日志都进行提交和应用到状态机中 再来看看ZooKeeper： client连接follower或者leader，如果连接的是follower则，follower会把client的请求(写请求，读请求则自身就可以直接处理)转发到leader leader接收到client的请求，将该请求转换成一个议案，写入到自己的日志中，会将该议案发送给所有的follower(这里只是单个发送) follower接收到leader的议案请求之后，会将该议案写入到文件中（通常并没有立即刷新到磁盘），然后向leader回复OK leader收到过半的OK回复之后，就认为可以提交了，leader会向所有的follower发送一个提交上述议案的请求，同时leader自己也会提交该议案，应用到自己的状态机中，完毕后回复客户端 follower在接收到leader传过来的提交议案请求之后，对该议案进行提交，应用到状态机中 3.2 日志的连续性问题 在需要保证顺序性的前提下，在利用一致性算法实现状态机的时候，到底是实现连续性日志好呢还是实现非连续性日志好呢？ 如果是连续性日志，则leader在分发给各个follower的时候，只需要记录每个follower目前已经同步的index即可，如Raft 如果是非连续性日志，如ZooKeeper，则leader需要为每个follower单独保存一个队列，用于存放所有的改动，如ZooKeeper，一旦是队列就引入了一个问题即顺序性问题，即follower在和leader进行同步的时候，需要阻塞leader处理写请求，先将follower和leader之间的差异数据先放入队列，完成之后，解除阻塞，允许leader处理写请求，即允许往该队列中放入新的写请求，从而来保证顺序性 还有在复制和提交的时候： 连续性日志可以批量进行 非连续性日志则只能一个一个来复制和提交 其他有待后续补充 3.3 如何保证顺序 具体顺序是什么？ 这个就是先到达leader的请求，先被应用到状态机。这就需要看正常运行过程、异常出现过程都是怎么来保证顺序的 3.3.1 正常同步过程的顺序 Raft对请求先转换成entry，复制时，也是按照leader中log的顺序复制给follower的，对entry的提交是按index进行顺序提交的，是可以保证顺序的 ZooKeeper在提交议案的时候也是按顺序写入各个follower对应在leader中的队列，然后follower必然是按照顺序来接收到议案的，对于议案的过半提交也都是一个个来进行的 3.3.2 异常过程的顺序保证 如follower挂掉又重启的过程： Raft：重启之后，由于leader的AppendEntries RPC调用，识别到leader，leader仍然会按照leader的log进行顺序复制，也不用关心在复制期间新的添加的日志，在下一次同步中自动会同步 ZooKeeper：重启之后，需要和当前leader数据之间进行差异的确定，同时期间又有新的请求到来，所以需要暂时获取leader数据的读锁，禁止此期间的数据更改，先将差异的数据先放入队列，差异确定完毕之后，还需要将leader中已提交的议案和未提交的议案也全部放入队列，即ZooKeeper的如下2个集合数据 ConcurrentMap outstandingProposals Leader拥有的属性，每当提出一个议案，都会将该议案存放至outstandingProposals，一旦议案被过半认同了，就要提交该议案，则从outstandingProposals中删除该议案 ConcurrentLinkedQueue toBeApplied Leader拥有的属性，每当准备提交一个议案，就会将该议案存放至该列表中，一旦议案应用到ZooKeeper的内存树中了，然后就可以将该议案从toBeApplied中删除 然后再释放读锁，允许leader进行处理写数据的请求，该请求自然就添加在了上述队列的后面，从而保证了队列中的数据是有序的，从而保证发给follower的数据是有序的，follower也是一个个进行确认的，所以对于leader的回复也是有序的 如果是leader挂了之后，重新选举出leader，会不会有乱序的问题？ Raft：Raft对于之前term的entry被过半复制暂不提交，只有当本term的数据提交了才能将之前term的数据一起提交，也是能保证顺序的 ZooKeeper:ZooKeeper每次leader选举之后都会进行数据同步，不会有乱序问题 3.4 请求处理流程的异常 一旦leader发给follower的数据出现超时等异常 Raft：会不断重试，并且接口是幂等的 ZooKeeper：follower会断开与leader之间的连接，重新加入该集群，加入逻辑前面已经说了 4 分区的应对 目前ZooKeeper和Raft都是过半即可，所以对于分区是容忍的。如5台机器，分区发生后分成2部分，一部分3台，另一部分2台，这2部分之间无法相互通信 其中，含有3台的那部分，仍然可以凑成一个过半，仍然可以对外提供服务，但是它不允许有server再挂了，一旦再挂一台则就全部不可用了。 含有2台的那部分，则无法提供服务，即只要连接的是这2台机器，都无法执行相关请求。 所以ZooKeeper和Raft在一旦分区发生的情况下是是牺牲了高可用来保证一致性，即CAP理论中的CP。但是在没有分区发生的情况下既能保证高可用又能保证一致性，所以更想说的是所谓的CAP二者取其一，并不是说该系统一直保持CA或者CP或者AP，而是一个会变化的过程。在没有分区出现的情况下，既可以保证C又可以保证A，在分区出现的情况下，那就需要从C和A中选择一样。ZooKeeper和Raft则都是选择了C。 欢迎关注微信公众号：乒乓狂魔
-
发表了文章 2016-11-01
ZooKeeper的一致性算法赏析
1 ZAB介绍 ZAB协议全称就是ZooKeeper Atomic Broadcast protocol，是ZooKeeper用来实现一致性的算法，分成如下4个阶段。 先来解释下部分名词 electionEpoch：每执行一次leader选举，electionEpoch就会自增，用来标记leader选举的轮次 peerEpoch：每次leader选举完成之后，都会选举出一个新的peerEpoch，用来标记事务请求所属的轮次 zxid：事务请求的唯一标记，由leader服务器负责进行分配。由2部分构成，高32位是上述的peerEpoch，低32位是请求的计数，从0开始。所以由zxid我们就可以知道该请求是哪个轮次的，并且是该轮次的第几个请求。 lastProcessedZxid：最后一次commit的事务请求的zxid Leader election leader选举过程，electionEpoch自增，在选举的时候lastProcessedZxid越大，越有可能成为leader Discovery： 第一：leader收集follower的lastProcessedZxid，这个主要用来通过和leader的lastProcessedZxid对比来确认follower需要同步的数据范围 第二：选举出一个新的peerEpoch，主要用于防止旧的leader来进行提交操作（旧leader向follower发送命令的时候，follower发现zxid所在的peerEpoch比现在的小，则直接拒绝，防止出现不一致性） Synchronization： follower中的事务日志和leader保持一致的过程，就是依据follower和leader之间的lastProcessedZxid进行，follower多的话则删除掉多余部分，follower少的话则补充，一旦对应不上则follower删除掉对不上的zxid及其之后的部分然后再从leader同步该部分之后的数据 Broadcast 正常处理客户端请求的过程。leader针对客户端的事务请求，然后提出一个议案，发给所有的follower，一旦过半的follower回复OK的话，leader就可以将该议案进行提交了，向所有follower发送提交该议案的请求，leader同时返回OK响应给客户端 上面简单的描述了上述4个过程，这4个过程的详细描述在zab的paper中可以找到，但是我看了之后基本和zab的源码实现上相差有点大，这里就不再提zab paper对上述4个过程的描述了，下面会详细的说明ZooKeeper源码中是具体怎么来实现的 2 ZAB协议源码实现 先看下ZooKeeper整体的实现情况，如下图所示 上述实现中Recovery Phase包含了ZAB协议中的Discovery和Synchronization。 2.1 重要的数据介绍 加上前面已经介绍的几个名词 long lastProcessedZxid：最后一次commit的事务请求的zxid LinkedList ZooKeeper会保存最近一段时间内执行的事务请求议案，个数限制默认为500个议案。上述committedLog就是用来保存议案的列表，上述maxCommittedLog表示最大议案的zxid，minCommittedLog表示committedLog中最小议案的zxid。 ConcurrentMap outstandingProposals Leader拥有的属性，每当提出一个议案，都会将该议案存放至outstandingProposals，一旦议案被过半认同了，就要提交该议案，则从outstandingProposals中删除该议案 ConcurrentLinkedQueue toBeApplied Leader拥有的属性，每当准备提交一个议案，就会将该议案存放至该列表中，一旦议案应用到ZooKeeper的内存树中了，然后就可以将该议案从toBeApplied中删除 对于上述几个参数，整个Broadcast的处理过程可以描述为： leader针对客户端的事务请求（leader为该请求分配了zxid），创建出一个议案，并将zxid和该议案存放至leader的outstandingProposals中 leader开始向所有的follower发送该议案，如果过半的follower回复OK的话，则leader认为可以提交该议案，则将该议案从outstandingProposals中删除，然后存放到toBeApplied中 leader对该议案进行提交，会向所有的follower发送提交该议案的命令，leader自己也开始执行提交过程，会将该请求的内容应用到ZooKeeper的内存树中，然后更新lastProcessedZxid为该请求的zxid，同时将该请求的议案存放到上述committedLog，同时更新maxCommittedLog和minCommittedLog leader就开始向客户端进行回复，然后就会将该议案从toBeApplied中删除 2.2 Fast Leader Election leader选举过程要关注的要点： 所有机器刚启动时进行leader选举过程 如果leader选举完成，刚启动起来的server怎么识别到leader选举已完成 投票过程有3个重要的数据: ServerState 目前ZooKeeper机器所处的状态有4种，分别是 LOOKING：进入leader选举状态 FOLLOWING：leader选举结束，进入follower状态 LEADING：leader选举结束，进入leader状态 OBSERVING：处于观察者状态 HashMap recvset用于收集LOOKING、FOLLOWING、LEADING状态下的server的投票 HashMap outofelection用于收集FOLLOWING、LEADING状态下的server的投票（能够收集到这种状态下的投票，说明leader选举已经完成） 下面就来详细说明这个过程： 1 serverA首先将electionEpoch自增，然后为自己投票 serverA会首先从快照日志和事务日志中加载数据，就可以得到本机器的内存树数据，以及lastProcessedZxid（这一部分后面再详细说明） 初始投票Vote的内容： proposedLeader：ZooKeeper Server中的myid值，初始为本机器的id proposedZxid：最大事务zxid，初始为本机器的lastProcessedZxid proposedEpoch:peerEpoch值，由上述的lastProcessedZxid的高32得到 然后该serverA向其他所有server发送通知，通知内容就是上述投票信息和electionEpoch信息 2 serverB接收到上述通知，然后进行投票PK 如果serverB收到的通知中的electionEpoch比自己的大，则serverB更新自己的electionEpoch为serverA的electionEpoch 如果该serverB收到的通知中的electionEpoch比自己的小，则serverB向serverA发送一个通知，将serverB自己的投票以及electionEpoch发送给serverA，serverA收到后就会更新自己的electionEpoch 在electionEpoch达成一致后，就开始进行投票之间的pk，规则如下： /* * We return true if one of the following three cases hold: * 1- New epoch is higher * 2- New epoch is the same as current epoch, but new zxid is higher * 3- New epoch is the same as current epoch, new zxid is the same * as current zxid, but server id is higher. */ return ((newEpoch > curEpoch) || ((newEpoch == curEpoch) && ((newZxid > curZxid) || ((newZxid == curZxid) && (newId > curId))))); 就是优先比较proposedEpoch，然后优先比较proposedZxid，最后优先比较proposedLeader pk完毕后，如果本机器投票被pk掉，则更新投票信息为对方投票信息，同时重新发送该投票信息给所有的server。 如果本机器投票没有被pk掉，则看下面的过半判断过程 3 根据server的状态来判定leader如果当前发来的投票的server的状态是LOOKING状态，则只需要判断本机器的投票是否在recvset中过半了，如果过半了则说明leader选举就算成功了，如果当前server的id等于上述过半投票的proposedLeader,则说明自己将成为了leader，否则自己将成为了follower 如果当前发来的投票的server的状态是FOLLOWING、LEADING状态，则说明leader选举过程已经完成了，则发过来的投票就是leader的信息，这里就需要判断发过来的投票是否在recvset或者outofelection中过半了 同时还要检查leader是否给自己发送过投票信息，从投票信息中确认该leader是不是LEADING状态（这一部分还需要仔细推敲下） 2.3 Recovery Phase 一旦leader选举完成，就开始进入恢复阶段，就是follower要同步leader上的数据信息 1 通信初始化leader会创建一个ServerSocket，接收follower的连接，leader会为每一个连接会用一个LearnerHandler线程来进行服务 2 重新为peerEpoch选举出一个新的peerEpochfollower会向leader发送一个Leader.FOLLOWERINFO信息，包含自己的peerEpoch信息 leader的LearnerHandler会获取到上述peerEpoch信息，leader从中选出一个最大的peerEpoch，然后加1作为新的peerEpoch。 然后leader的所有LearnerHandler会向各自的follower发送一个Leader.LEADERINFO信息，包含上述新的peerEpoch follower会使用上述peerEpoch来更新自己的peerEpoch，同时将自己的lastProcessedZxid发给leader leader的所有LearnerHandler会记录上述各自follower的lastProcessedZxid，然后根据这个lastProcessedZxid和leader的lastProcessedZxid之间的差异进行同步 3 已经处理的事务议案的同步 判断LearnerHandler中的lastProcessedZxid是否在minCommittedLog和maxCommittedLog之间 LearnerHandler中的lastProcessedZxid和leader的lastProcessedZxid一致，则说明已经保持同步了 如果lastProcessedZxid在minCommittedLog和maxCommittedLog之间 从lastProcessedZxid开始到maxCommittedLog结束的这部分议案，重新发送给该LearnerHandler对应的follower，同时发送对应议案的commit命令 上述可能存在一个问题：即lastProcessedZxid虽然在他们之间，但是并没有找到lastProcessedZxid对应的议案，即这个zxid是leader所没有的，此时的策略就是完全按照leader来同步，删除该follower这一部分的事务日志，然后重新发送这一部分的议案，并提交这些议案 如果lastProcessedZxid大于maxCommittedLog 则删除该follower大于部分的事务日志 如果lastProcessedZxid小于minCommittedLog 则直接采用快照的方式来恢复 4 未处理的事务议案的同步LearnerHandler还会从leader的toBeApplied数据中将大于该LearnerHandler中的lastProcessedZxid的议案进行发送和提交（toBeApplied是已经被确认为提交的） LearnerHandler还会从leader的outstandingProposals中大于该LearnerHandler中的lastProcessedZxid的议案进行发送，但是不提交（outstandingProposals是还没被被确认为提交的） 5 将LearnerHandler加入到正式follower列表中意味着该LearnerHandler正式接受请求。即此时leader可能正在处理客户端请求，leader针对该请求发出一个议案，然后对该正式follower列表才会进行执行发送工作。这里有一个地方就是： 上述我们在比较lastProcessedZxid和minCommittedLog和maxCommittedLog差异的时候，必须要获取leader内存数据的读锁，即在此期间不能执行修改操作，当欠缺的数据包已经补上之后（先放置在一个队列中，异步发送），才能加入到正式的follower列表，否则就会出现顺序错乱的问题 同时也说明了，一旦一个follower在和leader进行同步的过程（这个同步过程仅仅是确认要发送的议案，先放置到队列中即可等待异步发送，并不是说必须要发送过去），该leader是暂时阻塞一切写操作的。 对于快照方式的同步，则是直接同步写入的，写入期间对数据的改动会放在上述队列中的，然后当同步写入完成之后，再启动对该队列的异步写入。 上述的要理解的关键点就是：既要不能漏掉，又要保证顺序 6 LearnerHandler发送Leader.NEWLEADER以及Leader.UPTODATE命令该命令是在同步结束之后发的，follower收到该命令之后会执行一次版本快照等初始化操作，如果收到该命令的ACK则说明follower都已经完成同步了并完成了初始化 leader开始进入心跳检测过程，不断向follower发送心跳命令，不断检是否有过半机器进行了心跳回复，如果没有过半，则执行关闭操作，开始进入leader选举状态 LearnerHandler向对应的follower发送Leader.UPTODATE，follower接收到之后，开始和leader进入Broadcast处理过程 2.4 Broadcast Phase 前面其实已经说过了，参见2.1中的内容 3 特殊情况的注意点 3.1 事务日志和快照日志的持久化和恢复 先来看看持久化过程： Broadcast过程的持久化 leader针对每次事务请求都会生成一个议案，然后向所有的follower发送该议案 follower接收到该议案后，所做的操作就是将该议案记录到事务日志中，每当记满100000个（默认），则事务日志执行flush操作，同时开启一个新的文件来记录事务日志 同时会执行内存树的快照，snapshot.[lastProcessedZxid]作为文件名创建一个新文件，快照内容保存到该文件中 leader shutdown过程的持久化 一旦leader过半的心跳检测失败，则执行shutdown方法，在该shutdown中会对事务日志进行flush操作 再来说说恢复： 事务快照的恢复 第一：会在事务快照文件目录下找到最近的100个快照文件，并排序，最新的在前 第二：对上述快照文件依次进行恢复和验证，一旦验证成功则退出，否则利用下一个快照文件进行恢复。恢复完成更新最新的lastProcessedZxid 事务日志的恢复 第一：从事务日志文件目录下找到zxid大于等于上述lastProcessedZxid的事务日志 第二：然后对上述事务日志进行遍历，应用到ZooKeeper的内存树中，同时更新lastProcessedZxid 第三：同时将上述事务日志存储到committedLog中，并更新maxCommittedLog、minCommittedLog 由此我们可以看到，在初始化恢复的时候，是会将所有最新的事务日志作为已经commit的事务来处理的 也就是说这里面可能会有部分事务日志还没真实提交，而这里全部当做已提交来处理。这个处理简单粗暴了一些，而raft对老数据的恢复则控制的更加严谨一些。 3.2 follower挂了之后又重启的恢复过程 一旦leader挂了，上述leader的2个集合 ConcurrentMap outstandingProposals ConcurrentLinkedQueue toBeApplied 就无效了。他们并不在leader恢复的时候起作用，而是在系统正常执行，而某个follower挂了又恢复的时候起作用。 我们可以看到在上述2.3的恢复过程中，会首先进行快照日志和事务日志的恢复，然后再补充leader的上述2个数据中的内容。 3.3 同步follower失败的情况 目前leader和follower之间的同步是通过BIO方式来进行的，一旦该链路出现异常则会关闭该链路，重新与leader建立连接，重新同步最新的数据 3.5 对client端是否一致 客户端收到OK回复，会不会丢失数据？ 客户端没有收到OK回复，会不会多存储数据？ 客户端如果收到OK回复，说明已经过半复制了，则在leader选举中肯定会包含该请求对应的事务日志，则不会丢失该数据 客户端连接的leader或者follower挂了，客户端没有收到OK回复，目前是可能丢失也可能没丢失，因为服务器端的处理也很简单粗暴，对于未来leader上的事务日志都会当做提交来处理的，即都会被应用到内存树中。 同时目前ZooKeeper的原生客户端也没有进行重试，服务器端也没有对重试进行检查。这一部分到下一篇再详细探讨与raft的区别 4 未完待续 本文有很多细节，难免可能疏漏，还请指正。 4.1 问题 这里留个问题供大家思考下： raft每次执行AppendEntries RPC的时候，都会带上当前leader的新term，来防止旧的leader的旧term来执行相关操作，而ZooKeeper的peerEpoch呢？达到防止旧leader的效果了吗？它的作用是干什么呢？ 4.2 下篇 下一篇就来对比一下raft和zab之间的细微的区别 欢迎关注微信公众号：乒乓狂魔
-
发表了文章 2016-09-30
Rocketmq源码分析（一）整体架构
1 系列 整体架构图 producer端发送消息 broker端接收消息 broker端消息的存储 consumer消费消息 分布式事务的实现 定时消息的实现 关于顺序消费 关于重复消息 关于高可用 2 整体架构图 先来看下官方给出的整体架构图 Producer集群：拥有相同的producerGroup,一般来讲，Producer不必要有集群的概念，这里的集群仅仅在RocketMQ的分布式事务中有用到 Name Server集群：提供topic的路由信息，路由信息数据存储在内存中，broker会定时的发送路由信息到nameserver中的每一个机器，来进行更新，所以name server集群可以简单理解为无状态（实际情况下可能存在每个nameserver机器上的数据有短暂的不一致现象，但是通过定时更新，大部分情况下都是一致的） broker集群：一个集群有一个统一的名字，即brokerClusterName，默认是DefaultCluster。一个集群下有多个master，每个master下有多个slave。master和slave算是一组，拥有相同的brokerName,不同的brokerId，master的brokerId是0，而slave则是大于0的值。master和slave之间可以进行同步复制或者是异步复制。 consumer集群：拥有相同的consumerGroup。 下面来说说他们之间的通信关系 Producer和Name Server：每一个Producer会与Name Server集群中的一台机器建立TCP连接，会从这台Name Server上拉取路由信息。 Producer和broker：Producer会和它要发送的topic相关的master类型的broker建立TCP连接，用于发送消息以及定时的心跳信息。broker中会记录该Producer的信息，供查询使用 broker与Name Server：broker（不管是master还是slave）会和每一台Name Server机器来建立TCP连接。broker在启动的时候会注册自己配置的topic信息到Name Server集群的每一台机器中。即每一台Name Server都有该broker的topic的配置信息。master与master之间无连接，master与slave之间有连接 Consumer和Name Server：每一个Consumer会和Name Server集群中的一台机器建立TCP连接，会从这台Name Server上拉取路由信息，进行负载均衡 Consumer和broker：Consumer可以与master或者slave的broker建立TCP连接来进行消费消息，Consumer也会向它所消费的broker发送心跳信息，供broker记录。 3 kafka的架构图 来看下kafka的整体架构图 来看看他们之间的连接关系 Producer和broker：Producer会和它所要发送的topic相关的broker建立TCP连接，并通过broker进行其他broker的发现(这个没有依赖ZooKeeper进行服务发现) broker和ZooKeeper：broker会将自己注册在ZooKeeper上，同时依赖ZooKeeper做一些分布式协调 Consumer和ZooKeeper：Consumer会将自己注册在ZooKeeper上，同时依赖ZooKeeper进行broker发现以及将消费offset记录在ZooKeeper上 Consumer和Broker:Consumer连接topic相关的broker进行消息的消费 4 RocketMQ和kafka的对比 4.1 消息的存储 我们知道topic是一类消息的统称，为了提高消息的写入和读取并发能力，将一个topic的消息进行拆分，可以分散到多个broker中。kafka上称为分区，而RocketMQ称为队列。 对于kafka：为了防止一个分区的消息文件过大，会拆分成一个个固定大小的文件，所以一个分区就对应了一个目录。分区与分区之间是相互隔离的。 对于RocketMQ：则是所有topic的数据混在一起进行存储，默认超过1G的话，则重新创建一个新的文件。消息的写入过程即写入该混杂的文件中，然后又有一个线程服务，在不断的读取分析该混杂文件，将消息进行分拣，然后存储在对应队列目录中（存储的是简要信息，如消息在混杂文件中的offset，消息大小等） 所以RocketMQ需要2次寻找，第一次先找队列中的消息概要信息，拿到概要信息中的offset，根据这个offset再到混杂文件中找到想要的消息。而kafka则只需要直接读取分区中的文件即可得到想要的消息。 看下这里给出的RocketMQ的日志文件图片分布式开放消息系统(RocketMQ)的原理与实践 这里我自己认为RocketMQ的做法还是值得商榷的，这样的做法在同步刷盘、异步刷盘时效率相对高些（由于量大所以效率相对高些），但是全部的topic往一个文件里面写，每次写入要进行加锁控制，本来不相干的topic却相互影响，就降低的写入的效率。这个锁的粒度有点大了，我自己认为应该一个队列对应一个CommitLog，这样做就是减少锁的粒度问题。 4.1 Prdocuer端的服务发现 就是Producer端如何来发现新的broker地址。 对于kafka来说：Producer端需要配置broker的列表地址，Producer也从一个broker中来更新broker列表地址（从中发现新加入的broker）。 对于RocketMQ来说：Producer端需要Name Server的列表地址，同时还可以定时从一个HTTP地址中来获取最新的Name Server的列表地址，然后从其中的一台Name Server来获取全部的路由信息，从中发现新的broker。 4.1 消费offset的存储 对于kafka：Consumer将消费的offset定时存储到ZooKeeper上，利用ZooKeeper保障了offset的高可用问题。 对于RocketMQ:Consumer将消费的offset定时存储到broker所在的机器上，这个broker优先是master，如果master挂了的话，则会选择slave来存储，broker也是将这些offset定时刷新到本地磁盘上，同时slave会定时的访问master来获取这些offset。 4.2 consumer负载均衡 对于负载均衡，在出现分区或者队列增加或者减少的时候、Consumer增加或者减少的时候都会进行reblance操作。 对于RocketMQ:客户端自己会定时对所有的topic的进行reblance操作，对于每个topic，会从broker获取所有Consumer列表，从broker获取队列列表，按照负载均衡策略，计算各自负责哪些队列。这种就要求进行负载均衡的时候，各个Consumer获取的数据是一致的，不然不同的Consumer的reblance结果就不同。 对于kafka：kafka之前也是客户端自己进行reblance，依靠ZooKeeper的监听，来监听上述2种情况的出现，一旦出现则进行reblance。现在的版本则将这个reblance操作转移到了broker端来做，不但解决了RocketMQ上述的问题，同时减轻了客户端的操作，是的客户端更加轻量级，减少了和其他语言集成的工作量。详细见这篇文章Kafka设计解析（四）：Kafka Consumer解析 4.3 Name Server和ZooKeeper Name Server和ZooKeeper的作用大致是相同的，从宏观上来看，Name Server做的东西很少，就是保存一些运行数据，Name Server之间不互连，这就需要broker端连接所有的Name Server，运行数据的改动要发送到每一个Name Server来保证运行数据的一致性（这个一致性确实有点弱），这样就变成了Name Server很轻量级，但是broker端就要做更多的东西了。 而ZooKeeper呢，broker只需要连接其中的一台机器，运行数据分发、一致性都交给了ZooKeeper来完成。 目前先就这几个大的组件进行简单的对比，后续会对某些细节进行详细说明。
滑动查看更多
暂无更多信息
-
发表了文章
2016-12-04
招募有志青年
-
发表了文章
2016-11-28
红黑树解法的why而非how
-
发表了文章
2016-11-21
kafka的高可用和一致性探究
-
发表了文章
2016-11-16
paxos算法证明过程
-
发表了文章
2016-11-10
分布式锁总结
-
发表了文章
2016-11-07
Raft对比ZAB协议
-
发表了文章
2016-11-01
ZooKeeper的一致性算法赏析
-
发表了文章
2016-10-27
Raft算法赏析
-
发表了文章
2016-09-30
Rocketmq源码分析（一）整体架构
-
发表了文章
2016-09-18
分布式锁的实现
-
发表了文章
2016-05-06
线程池源码分析-ThreadPoolExecutor
-
发表了文章
2016-05-06
线程池源码分析-FutureTask
-
发表了文章
2016-05-06
mysql锁技术讨论
-
发表了文章
2016-05-06
gecko框架概述
-
发表了文章
2016-05-06
NIO技术讨论
-
发表了文章
2016-05-06
dubbo源码分析系列（4）dubbo通信设计
-
发表了文章
2016-05-06
AOP技术讨论
-
发表了文章
2016-05-06
dubbo源码分析系列（3）服务的引用
-
发表了文章
2016-05-06
AOP事务的例子
-
发表了文章
2016-05-06
dubbo源码分析系列（2）服务的发布
滑动查看更多
暂无更多信息