泽民博客 ☰ Menu

gossip 算法 redis

gossip 是一种弱一致算法，也就是最终一致性算法。
特点：
1，去中心化，集群中各个节点都是对等的。
2，无法保证在某个时刻所有节点状态一致。
3，比较适合小数据量的同步。失败检测、路由同步、Pub/Sub、动态负载均衡



应用：redis 的 sentinel 的同步。 Cassandra集群。



  1. 概述
    gossip，顾名思义，类似于流言传播的概念，是一种可以按照自己的期望，自行选择与之交换信息的节点的通信方式
    gossip, or anto-entropy, is an attractive way of replicating state that does not have strong consistency requirements

  2. 算法描述



假设有 {p, q, …} 为协议参与者。 每个参与者都有关于一个自己信息的表。
用编程语言可以描述为：
记 InfoMap = Map<Key, (Value, Version)>， 那么每个参与者要维护一个 InfoMap 类型的变量 localInfo。 同时每一个参与者要知道所有其他参与者的信息, 即要维护一个全局的表，即 Map<participant, InfoMap> 类型的变量 globalMap。每个参与者更新自己的 localInfo， 而由 Gossip 协议负责将更新的信息同步到整个网络上。
每个节点和系统中的某些节点成为 peer (如果系统的规模比较小，和系统中所有的其他节点成为 peer)。 有三种不同的同步信息的方法：
1）push-gossip: 最简单的情况下， 一个节点 p 向 q 发送整个 GlobalMap
2）pull-gossip: p 向 q 发送 digest, q 根据 digest 向 p 发送 p 过期的 (key, (value, version)) 列表
3）push-pull-gossip:与pull-gossip类似，只是多了一步，A再将本地比B新的数据推送给B，B更新本地




  1. 特点
    gossip不要求节点知道所有其他节点，因此具有去中心化的特点，节点之间完全对等，不需要任何的中心节点。
    gossip算法又被称为反熵（Anti-Entropy），熵是物理学上的一个概念，代表杂乱无章，而反熵就是在杂乱无章中寻求一致，这充分说明了Gossip的特点：
    在一个有界网络中，每个节点都随机地与其他节点通信，经过一番杂乱无章的通信，最终所有节点的状态都会达成一致。每个节点可能知道所有其他节点，也可能仅知道几个邻节点，只要这些节可以通过网络连通，最终他们的状态都是一致的。
    gossip算法是一个最终一致性算法，其无法保证在某个时刻所有节点状态一致，但可以保证在”最终“所有节点一致，”最终“是一个现实中存在，但理论上无法证明的时间点




  2. 协调机制
    协调机制是讨论在每次2个节点通信时，如何交换数据能达到最快的一致性，也即消除两个节点的不一致性。
    协调所面临的最大问题是，因为受限于网络负载，不可能每次都把一个节点上的数据发送给另外一个节点，也即每个Gossip的消息大小都有上限。在有限的空间上有效率地交换所有的消息是协调要解决的主要问题。
    “Efficient Reconciliation and Flow Control for Anti-Entropy Protocols”中描述了两种同步机制
    1）precise reconciliation
    precise reconciliation希望在每次通信周期内都非常准确地消除双方的不一致性，具体表现为相互发送对方需要更新的数据，因为每个节点都在并发与多个节点通信，理论上很难做到。precise reconciliation需要给每个数据项独立地维护自己的version，在每次交互是把所有的(key,value,version)发送到目标进行比对，从而找出双方不同之处从而更新。但因为Gossip消息存在大小限制，因此每次选择发送哪些数据就成了问题。当然可以随机选择一部分数据，也可确定性的选择数据。对确定性的选择而言，可以有最老优先（根据版本）和最新优先两种，最老优先会优先更新版本最新的数据，而最新更新正好相反，这样会造成老数据始终得不到机会更新，也即饥饿。
    2）Scuttlebutt Reconciliation
    Scuttlebutt Reconciliation 与precise reconciliation不同之处是，Scuttlebutt Reconciliation不是为每个数据都维护单独的版本号，而是为每个节点上的宿主数据维护统一的version。比如节点P会为(p1,p2,…)维护一个一致的全局version，相当于把所有的宿主数据看作一个整体，当与其他节点进行比较时，只需比较这些宿主数据的最高version，如果最高version相同说明这部分数据全部一致，否则再进行precise reconciliation。




  3. Merkle tree
    信息同步无疑是gossip的核心，Merkle tree(MT)是一个非常适合同步的数据结构。
    简单来说 Merkle tree就是一颗hash树，在这棵树中，叶子节点的值是一些hash值、非叶节点的值均是由其子节点值计算hash得来的，这样，一旦某个文件被修改，修改时间的信息就会迅速传播到根目录。需要同步的系统只需要不断查询跟节点的hash，一旦有变化，顺着树状结构就能够在logN级 别的时间找到发生变化的内容，马上同步。
    在Dynamo中，每个节点保存一个范围内的key值，不同节点间存在有相互交迭的key值范围。在去熵操作中，考虑的仅仅是某两个节点间共有的key值范围。MT的叶子节点即是这个共有的key值范围内每个key的hash，通过叶子节点的hash自底向上便可以构建出一颗MT。Dynamo首先比对MT根处的hash，如果一致则表示两者完全一致，否则将其子节点交换并继续比较的过程。





6.总结
Gossip常见于大规模、无中心的网络系统，可以用于众多能接受“最终一致性”的领域：失败检测、路由同步、Pub/Sub、动态负载均衡。



1、节点间的内部通信机制
1.1 基础通信原理
redis cluster节点间采取gossip协议进行通信
维护集群的元数据有两种方式：集中式和gossip
集中式：
优点在于元数据的更新和读取，时效性非常好，一旦元数据出现变更立即就会更新到集中式的存储中，其他节点读取的时候立即就可以立即感知到；
不足在于所有的元数据的更新压力全部集中在一个地方，可能导致元数据的存储压力。
gossip：
优点在于元数据的更新比较分散，不是集中在一个地方，更新请求会陆陆续续，打到所有节点上去更新，有一定的延时，降低了压力；
缺点在于元数据更新有延时可能导致集群的一些操作会有一些滞后。
10000端口
每个节点都有一个专门用于节点间通信的端口，就是自己提供服务的端口号+10000，比如7001，那么用于节点间通信的就是17001端口。
每个节点每隔一段时间都会往另外几个节点发送ping消息，同时其他几点接收到ping之后返回pong。
1.2 gossip协议
gossip协议包含多种消息，包括ping，pong，meet，fail等等。
meet：某个节点发送meet给新加入的节点，让新节点加入集群中，然后新节点就会开始与其他节点进行通信；
ping：每个节点都会频繁给其他节点发送ping，其中包含自己的状态还有自己维护的集群元数据，互相通过ping交换元数据；
pong: 返回ping和meet，包含自己的状态和其他信息，也可以用于信息广播和更新；
fail: 某个节点判断另一个节点fail之后，就发送fail给其他节点，通知其他节点，指定的节点宕机了。



2、面向集群的jedis内部实现原理
2.1 基于重定向的客户端
请求重定向
客户端会挑选任意一个redis实例去发送命令，每个redis实例接收到命令，都会计算key对应的hash slot；
#查看key对应的hash slot
cluster keyslot key



#连接客户端时加-c参数可以自动重定向
redis-cli -c
计算hash slot
计算hash slot的算法，就是根据key计算CRC16值，然后对16384取模，拿到对应的hash slot；
用hash tag可以手动指定key对应的slot，同一个hash tag下的key，都会在一个hash slot中，比如set mykey1:{100}和set mykey2:{100}；
hash slot查找
节点间通过gossip协议进行数据交换，就知道每个hash slot在哪个节点上；
2.2 smart jedis
(1) 什么是smart jedis？
基于重定向的客户端，很消耗网络io，因为大部分情况下，可能都会出现一次请求重定向，才能找到正确的节点；
所以大部分的客户端比如java redis客户端，都是jedis，都是smart的，
本地维护一份hashslot -> node的映射表在缓存里，大部分情况下直接走本地缓存就可以找到hashslot -> node，不需要通过节点进行moved重定向；




  1. 高可用性与主备切换原理
    3.1 判断节点宕机
    如果一个节点认为另外一个节点宕机，name就是pfail，主观宕机；
    如果多个节点都认为另外一个节点宕机了，那么就是fail，客观宕机，跟哨兵的原理几乎一样，sdown，odown；
    在cluster-node-timeout内，某个节点一直没有返回pong，那么就被认为pfail；
    如果一个节点认为某个节点pfail了，那么会在gossip ping消息中，ping给其他节点，如果超过半数的节点都认为pfail了，那么就会变成fail；



3.2 从节点过滤
对宕机的master node，从其所有的slave node中，选择一个切换成master node；
检查每个slave node与master node断开连接的时间，如果超过了cluster-node-timeout * cluster-slave-validity-factor，那么就没有资格切换成master；



3.3 从节点选举
哨兵：对所有从节点进行排序，slave priority，offset，run id；
每个从节点，都根据自己对master复制数据的offset，来设置一个选举时间，offset越大（复制数据越多）的从节点，选举时间越靠前，优先进行选举；
所有的master node开始slave选举投票，给要进行选举的slave进行投票，如果大部分master node（N/2 + 1）都投票给了某个从节点，那么选举通过，那个从节点可以切换成master；
从节点执行主备切换，从节点切换为主节点；



3.4 与哨兵比较
整个流程跟哨兵相比，非常类似，所以说，redis cluster功能强大，直接集成了replication和sentinal的功能；


Category algorithm