建设厅质监总站网站,做饮食找工作哪个网站好,企业网站的功能列表,辽宁网络优化方法分布式系统的一致性是指从系统外部读取系统内部的数据时#xff0c;在一定约束条件下相同#xff0c;即数据#xff08;元数据#xff0c;日志数据等等#xff09;变动在系统内部各节点应该是一致的。 一致性模型分为如下几种#xff1a;
① 强一致性 所有用户在任意时… 分布式系统的一致性是指从系统外部读取系统内部的数据时在一定约束条件下相同即数据元数据日志数据等等变动在系统内部各节点应该是一致的。 一致性模型分为如下几种
① 强一致性 所有用户在任意时刻读到的数据无论会请求到哪个节点上都是一致的
② 单调一致性 有用户在任意时刻读到的数据一定会比之前读到的数据新也就是说可获取的数据顺序必是单调递增的
③ 弱一致性 相比于强一致性弱一致性要求没那个严格不同用户在不同时间读到的数据可能是不一致的但过了一段时间会达到一致。
④ 最终一致性 最终一致性属于弱一致性的一种实例。用户只能读到某次更新后的值但系统保证数据将最终达到完全一致的状态只是所需时间不能保障。 实际上一致性还包括顺序一致性、读写一致性、因果一致性等等这里不做过多讨论。 之前在分布式基础的文章里也有过讨论对于分布式系统主要有CAP理论和BASE理论。对于现实的网络来说BASE理论是比较适用的即实现最终一致性。 再说下共识共识是指不同的节点通过某种方法对于某种状态达成一致的过程。分布式一致性强调了多个副本呈现的数据的状态共识强调多个节点之间对某个提案达成一致的过程。通过共识实现某种一致性这种一致性包括某提案的一致性如选举下线通知等等也包括数据的一致性。 共识算法目前有很多种。但根据不同的错误类型可以分为两大类算法 1、拜占庭问题。恶意伪造导致的错误 2、非拜占庭。出现故障非恶意伪造。
拜占庭问题
我觉得一个比较简单明了的解释 假设有9位将军投票其中1名叛徒。8名忠诚的将军中出现了4人投进攻4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来投票结果是5人投进攻从而发起进攻而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。 目前存在的算法主要包括PAXOSRAFT还有用于区块链的工作量证明、权益证明等等算法。PAXOSRAFT主要用来解决不存在拜占庭问题的情况即不存在作弊情况基本上都是网络抖动网络出错系统宕机等问题因此基本上都是用于系统内部自治像开源的各种中间件消息队列Redis集群等等。而工作量证明权益证明这些用于区块链等领域的算法就需要考虑拜占庭问题。
共识算法
Gossip算法Raft算法ZABES选举算法
一、Gossip算法论文地址Gossip论文 我觉得用一个简单例子来描述gossip比较合适说一个村里儿有一家突然有一天发生了一个事儿女儿嫁给了一个大她20岁的老爷们儿她邻居先听说了这个事儿火急火燎地就把这个事儿告诉了和她打麻将的几个人儿然后这几个人又分别告诉了好朋友同时第一听说这件事儿的邻居还没闲下来还再巴巴地和别人说就这样很快整个村儿都知道了。一个消息最后所有人都知道了。 Gossip协议就是这样一种没有中心节点由最初的一个节点先随机选择几个节点通信然后知道信息的节点同样再选择几个节点通信就这样看似杂乱无章地相互通信最终达到了一致性的一种算法。 这种算法的一个优势是不管是有新节点加入还是有节点宕机对现有的网络和在线节点都不会有任何的影响。就算是突然有个新节点加入也会达到最终一致性。 目前这个算法已经非常成熟了。Redis-Cluster目前采用了这种协议。RedisCluster集群的每个节点都会有两个重要的数据结构一个是clusterNode记录了当前节点的状态一个是clusterState包含整个集群的状态等信息。clusterState的slots数组存储的是所有槽分配的地址信息注意和clsuterNode的区别。clusterNode的slots数组记录的就是当前节点的槽分配信息。如果我们想要查某个slot在哪个节点上直接使用clusterState的slot记录时间复杂度是O(1。
在RedisCluster中有几个比较重要的通信类别
Meet 通过当前集群的节点会向新节点发送握手请求加入现有集群。Ping 节点每秒会向集群中其他节点发送 ping 消息消息中带有自己已知的两个节点的地址、槽、状态信息、最后一次通信时间等。Pong 节点收到 ping 消息后会回复 pong 消息消息中同样带有自己已知的两个节点信息。Fail 节点 ping 不通某节点后会向集群所有节点广播该节点挂掉的消息。其他节点收到消息后标记已下线。 Gossip的特点就是随机冗余发送最终达到了一致性。但Gossip协议本身也是存在很多的缺点比如就是通信的冗余因为就算一个节点收到了某个消息那么下次仍然有可能收到的这样就造成了资源的浪费。 RedisCluster的机制是会每100ms发送一次 ping这里也不是发送给集群中的所有节点而是随机选择部分节点。一个clusterSendPing会带上当前节点以及其他部分节点的信息发送出去。 其实上面说的clusterSendPing也不能完全保证每个节点都能收到其他节点的消息。因此集群还会每1秒都会发送随机选择5个节点并从中选择最久没有接受pong消息的节点发送消息。 此外还会遍历当前节点中存储的所有其他节点选择一个最近接受ping消息时间已经超过了cluster_node_timeout/2的就会发送消息。 上面是RedisCLuster使用Gossip来达到最终一致性的。除此之外在选举过程Redis采用的是Raft算法。 二、Raft算法 Raft算法是基于之前的PAXOS算法优化的一种可行性方案PAXOS本身比较复杂本文也不做赘述。Raft目前是很多成熟的分布式系统都采用的算法。如Redis-clusterNacosRocketmq以及Kafka2.8开始摘除ZK之后也采用基于Raft的共识机制。 Raft算法大的策略是将问题分治处理将整个流程分为选举、日志同步、安全性、日志压缩、成员变更等等。 该算法的前提是为系统定义了三个角色 1、Leader角色。整个系统只有该角色负责处理客户端的请求并把日志同步给Follower也是一个角色 2、Follower角色。一个系统会有多个Follower他们会接收Leader的日志并在Leader通知提交日志的时侯进行提交持久化。它只能接收请求 3、Candidate角色。该角色只有在进行Leader选举的时侯才会存在每一个Follower都可能临时成为 Candidate 。 一个系统在正常运转的时侯肯定只有一个Leader和多个Follower存在。
下面是一个示意图我觉得它描述得非常清晰图片非原创。 如果一个Follower超过一定时间没有收到Leader角色的心跳那么它就会等待一段随机的时间发起Leader选举并将自己也设置为Candidate角色且投自己一票当然你说要投自己一票让别人也投你你应该带上自己的最后一条日志的term和log index。 如果在超时之前获得了大多数的投票那么自己就变成Leader如果收到了其他Leader的消息证明已经有新的Leader自己还变成Follower如果没有获得超过一半的投票那么就等待该次选举周期超时后再发起选举。 每一次选举的周期被称为term随着选举的不断发生,term不断增大。而Candidate在选举时只选举term更大index最新的节点。这个周期是非常重要的他要确保同一个参与选举的角色在一个Term内只能投一票避免会出现脑裂的情况。 Redis-Cluster采用的就是基于Raft的选举当某个Master挂掉之后多个Slave会在间隔一段随机时间后发出广播消息希望其他Master投它一票注意这里的随机时间避免同时发起选举导致长时间选不出一个master来不过这样也不能保证发起选举就在一个周期内就会选举成功这里导致一个问题是RedisCluster本身也是CP模式的Master到Slave数据同步是异步的可能会出现数据丢失的情况。
Raft日志同步 Raft算法除了可以用在上面的master选举意外还可以用于日志同步。 思想 Leader接收客户端的请求后会并行地向所有Follower以日志的形式发送当有半数以上的Follower成功提交了日志那么才会告知客户端成功提交了。每个日志都会包括term和索引index以及真正要执行的指令。 那么Follower是如何处理Leader发来的日志呢 首先Follower会将index-1的内容和Leader的进行对比如果一致就返回true.如果不等就返回falseLeader收到false会减小index值重新发送直到最后内容相同Follower之后的内容都会被覆盖。 到此为止可以看到Raft为每个日志都分配了term和index保证唯一性此外它也强制Follower必须要和当前的Leader保持一致。
官方描述
leader为每个follower维护一个 nextIndex 表明下一个将要发送给follower的log entry当leader刚上任时会把所有的 nextIndex 设置成其最后一个log entry的index加1如上图则是11当follower的日志和leader不一致时一致性检查会失败那么会把 nextIndex 减1最终 nextIndex 会是leader和follower相同log entry的index加1这时候再发送 AppendEntries 会成功并且会把follower的所有之后不一致的日志删除掉。
Nacos的CP模式用的就是Raft算法不过其是用了阿里改造的SOFA-Jraft。
Raft文章推荐 Raft日志复制 Raft论文 三、ZAB协议 该协议是在zookeeper中应用的一种一致性协议它有很多和Raft相似的地方。比如都是由leader发起写操作都采用心跳来检测存活性在选举过程中也都采用谁先获得多数投票谁就成为Leader。但ZAB又有很多独特的地方。如ZAB的Observer不参与请求只提供给客户端的读请求。 ZAB全称是Zookeeper Atomic Broadcastzookeeper原子广播协议字面意思就可知该协议是基于广播进行的。 Zookeeper主要有两种模式崩溃恢复和广播模式它就是在这两种模式下切换。 崩溃恢复和Raft的选举过程也很类似也是在Leader崩溃之后Follower选择出一个新的Leader也是获得超过一半的投票。但投票条件不同ZAB要求Follower在投票给一个节点前必须和该节点的日志保证一致而Raft没这要求谁term高就给谁投。ZAB的投票参考因素是ZXID是一个事务的序号是不断递增的一个值。ZXID是一个64位数字高32位表示每一代Leaderepoch低32位表示事务的IDcount)。 那么可能问了如果Leader在提交事务后崩溃了或者在把日志复制给Follower时新Leader会继续处理吗针对该问题ZAB协议保证了两点 1、已经被Leader的事务会被提交 2、已经被Leader跳过的事务不会再执行 日志复制和Raft处理方式也是大体一样也是收到半数以上Follower的Ack后才会提交事务。区别是ZAB中引入了一个队列并将带有ZXID的日志按顺序发送给所有Follower相比于RaftZAB实现了解耦。
广播模式的具体流程 1、不论是zk集群的哪个机器收到了写请求就算是follower收到了它首先是将请求转发给leader服务器leader负责具体的写请求处理 2、leader生成proposal提案并生成一个全局的ZXID在后续的恢复模式中是很重要的一个标识。然后通过与每个follwer的队列FIFO发送给followerZXID在上面已经提到了官方的对其的定义 Every change to the ZooKeeper state receives a stamp in the form of a zxid (ZooKeeper Transaction Id). This exposes the total ordering of all changes to ZooKeeper. Each change will have a unique zxid and if zxid1 is smaller than zxid2 then zxid1 happened before zxid2. 3、follower收到消息后会将数据持久化到硬盘随后向leader发送一个ACK 4、当leader收到集群一半以上的follower发送的ACK就会向所有的follower发送commit 5、follower收到leader发送的commit消息后就将数据载入内存供客户端读取。
下面这张图非原创比较清晰描述了上个过程但该图有个问题就是请求不一定就是发送给leader可以发送给ZK集群任意一个节点只不过是如果请求是写请求的话follower会转发给leader。 其实上面也是一个分布式事务的实现通过三阶段提交实现事务。关于分布式事务的介绍可以参见 分布式事务 四、ES选举Bully算法 ES的选举并没有采用常用的Raft算法而是使用Bully算法。其基础是为集群的每个节点都分配一个唯一id。ES会为整个集群的每个node分配一个唯一的id这个id是node在启动时随机分配的。此外每个节点都会有一个版本号clusterVersion该字段代表的是状态值master节点一定是拥有最新版本号的节点。 ES里的节点分成Master节点Master候选节点和数据节点。角色需要通过配置来做。Master节点对应Raft的LeaderMaster候选节点也是对应Follower和Candidate。 那么当发现Master节点下线时候选节点投票的原则是首先选择版本号更高的如果版本号都相同就选择id最小的。和Raft相同的是同样是要求一半以上投票的节点才可成为Master节点但和Raft不同的是ES并没有完全避免脑裂的问题这也是ES选举过程存在的最大问题之所以会出现脑裂是因为虽然也是获得绝大多数投票的才能成为master但是他并没有限制一个节点只能投一票如果一个节点在投票后迟迟等不到选举的结果可能又开始投票此时因为优先级的问题又投票给其他节点了就意味着这个节点投了两票给不同节点就会出现问题。这种问题Raft算法解决的就很好Raft引入了Term的概念一个Term周期内一个节点只能投一票。Term大的优先级高。 参考资料
zookeeper面试题
Raft协议和Zab协议及其对比
分布式一致性与共识算法
Redis-Cluster实现
Raft算法详解
共识机制
