20

gossip in failure detection

 4 years ago
source link: https://zhuanlan.zhihu.com/p/39703992
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

gossip in failure detection

人类的悲欢并不相通，我只觉得他们吵闹

在分布式系统中，有两个常见的问题：故障检测，集群关系变更。

  1. 基于heartbeat的解决方案
  • 集群中的所有从节点向主节点不停的发送headbeat-message。这样会导致这个中心节点成为单点，并且这个单点会成为 hotspot。 随着节点的增加，中心节点无法随之扩容。
  • 集群里的各个节点不停的向其他所有节点广播heartbeat-message。这样会使得网络负载随着节点的增加而增大， 并且当有多个节点挂掉之后，故障检测的时间会无法预料。

2. 基于gossip的解决方案

Gossip Protocol利用一种随机的方式将信息散播到整个网络中。正如Gossip本身的含义一样，Gossip协议的工作流程即类似于绯闻的传播，或者流行病的传播。

种子节点每秒都会随机向其他节点发送自己所拥有的节点列表，以及需要传播的消息。任何新加入的节点，就在这种传播方式下很快地被全网所知道。这个协议的神奇就在于它从设计开始就没想到信息一定要传递给所有的节点，但是随着时间的增长，在最终的某一时刻，全网会得到相同的信息。

v2-f0d4a78b342ba3773eb2d8e9274e4807_720w.jpg

Consul 里使用一种 gossip 协议来管理节点以及向集群广播消息. 底层功能通过 Serf 来提供.

Serf 使用的这个 gossip 协议是基于 SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol 协议来实现的.

Consul中同时使用了gossip和raft，那gossip和raft有什么区别？

1. raft是强一致性的，gossip是最终一致。
2. 在consul里raft用来处理Master选举以及分布式事务， 而gossip用来广播故障，成员关系变更。

SWIM协议（Scalable Weakly-consistent Infection-style Process Group Membership Protocol）

SWIM 协议主要由两个部分组成:

  • 故障检测：检测集群已经成员是否发生故障
  • 集群关系变更的广播：集群成员的加入/退出/故障等信息的广播

在之前的一些研究里, 表明了分布式故障检测协议一般都要如下属性:

  • 一致性: 集群里任意节点的 crash 都可以被所有正常的节点检测到
  • 故障检测的速度: 指的是一个节点发生故障到故障被集群里的某些节点检测到时间间隔
  • 准确性: 故障检测的误报率
  • 网络负载: 协议每秒产生的字节数

SWIM协议基本实现

  • 在每个故障检测周期 T’ 内, 从 [公式] 的节点列表里随机选择一个节点, 假设为 [公式]. 从 [公式] 向 [公式] 发送一个 [公式] . 然后 [公式] 等待 [公式] 返回 [公式] .
  • 如果在指定的时间内没有收到 [公式] 那么 [公式] 会开始调查 [公式] 是否故障。此时 [公式] 从几点列表里随机选择 [公式] 个节点发送 [公式] . 这 k 个节点接收到消息后对 [公式] 再从发送 [公式] , 如果 [公式] 返回了 [公式] 就把这个 [公式] 消息转发给 [公式] .
  • 最后 [公式] 判断是否有收到 [公式] , 无论是从 Mj 直接返回的还是其他节点转发的 [公式] . 如果没有收到, 那么在它本地的节点列表里把 [公式] 标记为故障, 然后把故障信息转交给传播组件处理.
  • 上述协议里使用其他节点给 [公式] 发消息而不是直接让 [公式] 多发几次消息的原因是, 避免是 [公式] 和 [公式] 之间的网络拥堵造成的超时.
  • 检测到节点故障之后, 故障信息会广播给集群里的其他节点. 其他节点接收到之后会把 [公式] 从本地的节点列表里移除.
  • 新加入的节点信息或自愿退出的节点信息通过同样的方式广播给其他节点.

传播机制优化

在上述协议的传播组件里, 需要广播故障或新节点等信息.

SWIM 协议通过在故障检测组件的 [公式] , [公式] 以及 [公式] 消息中捎带( [公式] )信息, 消除了对广播原语的外部依赖.

这种感染式传播机制, 因为很像人群中的谣言传播或者传染病传播.

每个节点 [公式] 会在本地维护一组最近更新的节点， 每个节点都有一个 [公式] 属性(The number of times the element has been piggybacked so far by )。 用来决定下次 [公式] 所要算选择的节点。

故障检测优化

为了减少故障检测的误判，改进的协议里增加了怀疑(suspicion)机制. 当 [公式] 没有响应 [公式] 的 [公式] 消息时, [公式] 会把 [公式] 标记为可疑, 并通过传播组件在集群内传播 {Suspect [公式] : [公式] Misupects [公式] } 消息. 任意节点 [公式] 接受到怀疑消息之后也会把 [公式] 标记为可疑.

可疑的节点仍然会留在节点列表中, 并会像对待正常节点一样.

如果节点 [公式] 成功地 [公式] 了可疑节点 [公式] , 会移除节点列表里 [公式] 的可疑标签, 并在集群中传播 {Alive [公式] : [公式] knows [公式] is alive} 消息. 收到消息的节点都会把 [公式] 的可疑标签移除.

注意, 如果 [公式] 收到了自己可疑的消息, 会开始传播一个 Alive 消息表明自己还活着.

在特定的超时时间之后, 如果 [公式] 中的 [公式] 被标记为可疑, 那么 [公式] 会把 [公式] 从节点列表中移除, 并向集群中传播 {Confirm [公式] : [公式] declares [公式] as faulty} 消息.

这个故障确认消息会覆盖之前的怀疑消息或存活消息, 并从所有的节点列表中删除 [公式] .

怀疑机制减少了故障误判率.

对于同一个节点的多次 Suspect 或 Alive 消息通过唯一的标识符来区分. 这些标识符通过节点列表里每个元素的一个虚拟生命周期数(incarnation number)提供. 这个数字对于节点来说是全局的.

节点 [公式] 的初始生命周期数为 0, 当它加入到集群后, 这个值只能被它自己增加. 当它接受到在当前生命周期数里自己被怀疑的消息, Mi 会用它的标识符和递增的生命周期数生成一个 Alive 信息, 并在集群中广播.

故障检测目标选择

基本的 SWIM 协议保证最终能检测某个节点的故障, 但对于节点开始故障和检测出故障之间的时间间隔没有明确保证.

[公式] 会维护一个当前的节点列表, 但不是随机选择一个节点作为 [公式] 的目标, 而是使用 round-robin.

新加入的节点会随机地选择列表里的一个位置插入.

一旦完成了整个列表的一个遍历, [公式] 会再次随机地对列表重新排序.

如果成员列表的大小不超过 [公式] , 这样保证了节点从失败到被检测出失败不会超过 (2 [公式] - 1) 个协议周期.

参考链接：

http://www.cs.cornell.edu/info/projects/spinglass/public_pdfs/swim.pdf​www.cs.cornell.eduhttps://www.serf.io/docs/internals/gossip.html​www.serf.io一种分布式健康检测和节点变更的协议 - SWIM 介绍​lastmayday.orgGossip 协议简介 - Kaiyuan's Blog​kaiyuan.me
编辑于 2018-07-16

report

Recommend

  • 66
    • www.backendcloud.cn 7 years ago
    • Cache

    Raft算法和Gossip协议 | 后端云

    简单介绍下集群数据同步，集群监控用到的两种常见算法。Raft算法raft 集群中的每个节点都可以根据集群运行的情况在三种状态间切换：follower, candidate 与 leader。leader 向 follower 同步日志，follower 只从 leader 处获取日志。在节点初始启动时，节点的 raft...

  • 49
    • www.chaindesk.cn 6 years ago
    • Cache

    认识Gossip | ChainDesk

  • 33
    • www.cnblogs.com 5 years ago
    • Cache

    浅谈集群版Redis和Gossip协议

    昨天的文章写了关于分布式系统中一致性哈希算法的问题，文末提了一下Redis-Cluster对于一致性哈希算法的实现方案，今天来看一下Redis-Cluster和其中的重要概念Gossip协议。 1.Redis Cluster的基本概念 集群版的Redis听...

  • 24
    • blog.51cto.com 5 years ago
    • Cache

    浅谈集群版Redis和Gossip协议-Java技术学习笔记

    今天来看一下Redis-Cluster和其中的重要概念Gossip协议。1.Redis Cluster的基本概念集群版的Redis听起来很高大上，确实相比单实例一主一从或者一主多从模式来说复杂了许多，互联网的架构总是随着业务的发展不断演进的。单实例Redis架构最开始的一主N从加上读写分离...

  • 16
    • edisonxu.com 4 years ago
    • Cache

    P2P 网络核心技术：Gossip 协议

    P2P 网络核心技术：Gossip 协议Gossip protocol 也叫 Epidemic Protocol （流行病协议），实际上它还有很多别名，比如：“流言算法”、“疫情传播算法”等。这个协议的作用就像其名字表示的意思一样，非常容易理解，它的方式其实...

  • 10
    • vearne.cc 4 years ago
    • Cache

    聊聊Gossip的一个实现

    版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc Gossip是一种去中心化、容错并保证最终一致性的协议。它的基本思想是通过不断的和集群中的节点gossip交换信息，经过 O(log(n))个回合, gossip...

  • 7
    • hackernoon.com 4 years ago
    • Cache

    Gossip Simulation Implemented In Python

    Gossip Simulation Implemented In PythonMay 18th 2021 new story14

  • 7
    • ayende.com 4 years ago
    • Cache

    How RavenDB uses gossip protocol to replicate documents efficiently in a cluster

    Jun 28 2021

  • 10
    • techxplore.com 4 years ago
    • Cache

    Celebrity gossip site relaunches after sex tape forced shutdown

    July 28, 2021 ...

  • 10
    • www.macstories.net 3 years ago
    • Cache

    MacStories Unwind: Gossip Girl and Hawkeye

    Jan 14, 2022 — 20:12 CUT MacStories Unwind: Gossip Girl and Hawkeye

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK