
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方法的问题
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种直接的解决办法: 增加一个黑色节点,可以通过左旋来得到,即另一子树扔过来一个红色(本身保证黑色不减少) 父节点增加一个黑色 我们从上述直接的解决办法中就可以推理出去,自然就能得到该怎么分类,每个分类下具体怎么操作了。 一个可以检验你是否真的理解红黑树的办法就是:不借助任何东西,你自己是否能够在一张白纸上自己推导一遍。 本文章涉及到细节很多,难免有疏漏的地方,还请批评指正。 欢迎继续来讨论,越辩越清晰。 欢迎关注微信公众号:乒乓狂魔
系列文章 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。 欢迎关注微信公众号:乒乓狂魔
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之间的细微的区别 欢迎关注微信公众号:乒乓狂魔
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来完成。 目前先就这几个大的组件进行简单的对比,后续会对某些细节进行详细说明。