Gossip协议

下载 11

搬砖工

发布于

8468

人观看

#信息技术

Gossip协议又被称为流行病协议（Epidemic Protocol），也有人叫它反熵（Anti-Entropy）。Gossip协议于1987年在ACM上发表的论文《Epidemic Algorithms for Replicated Database Maintenance》中被提出，主要用在分布式数据库系统中各个副本节点间的数据同步，这种场景的一个最大特点就是组成网络的节点都是对等的，网络中即使有的节点因宕机而重启，或有新节点加入，但经过一段时间后，这些节点的状态也会与其他节点达成一致，也就是说，Gossip天然具有分布式容错的优点。它是一个带冗余的容错算法，是一个最终一致性算法。虽然无法保证在某个时刻所有节点状态一致，但可以保证在”最终“所有节点一致，”最终“是一个现实中存在，但理论上无法证明的时间点。大名鼎鼎的 Bitcoin 则是使用了 Gossip 协议来传播交易和区块信息，实际上Gossip可以用于众多能接受“最终一致性”的领域：失败检测、路由同步、Pub/Sub、动态负载均衡。但Gossip的缺点也很明显，冗余通信会对网路带宽、CPU资源造成很大的负载，而这些负载又受限于通信频率，该频率又影响着算法收敛的速度，因此，针对不同的应用场景，也有很多的优化方法。

展开查看详情

1 .Gossip Protocols CS 6410 Eugene Bagdasaryan

2 .Gossip Protocols CS 6410 Eugene Bagdasaryan

3 .What was covered before?  Paxos  Byzantine Generals  Impossibility consensus What are these ideas aimed for? What is the difference with the current paper?

4 .What was covered before?  Paxos  Byzantine Generals  Impossibility consensus What are these ideas aimed for? Data consistency, fault-tolerance What is the difference with the current paper? “Eventual” consistency, scalability, fault-tolerance

5 .CAP theorem CAP = Consistency, Availability, Partition tolerance  Previous papers focused on Consistency and Partition Tolerance Paxos sometimes is unavailable for writes, but would remain consistent  This paper wants to provide Availability, Partition Tolerance, and “relaxed” form of consistency

6 .EPIDEMIC ALGORITHM FOR REPLICATED DATABASE MAINTENANCE Xerox Palo Alto Research Center 1987

7 .Authors Alan Demers Dan Greene Palo Alto Carl Hauser Wesley Irish Cornell Univ. Coyote Hill Research Center Washington State Univ. Consulting LLC John Larson Howard Sturgis Dan Swinehart Scott Shenker Doug Terry EECS Berkley Samsung Research America

8 .Real applications  Uber uses SWIM for real-time platform  Apache Cassandra internode communication  Docker’s multi-host networking  Cloud providers multi node networking (Heroku)  Serf by Hashicorp

9 .Context  Xerox wanted to run replicated database on hundred or thousand sites  Each update is injected at a single site and must be propagated to all other sites  A packet from a machine in Japan to one in Europe may traverse as many as 14 gateways and 7 phone lines

10 .Problem  High network traffic to send update over the large set of nodes  Time to propagate update to all nodes is significant

11 .Problem  High network traffic to send update over the large set of nodes  Time to propagate update to all nodes is significant ” For a domain stored at 300 sites, 90,000 mail messages might he introduced each night”.

12 .Basic idea Max Planck Institute für Dynamics and Self-organization

13 .Objective  Design algorithms that scale gracefully  Every replica receives every update eventually

14 .Objective  Design algorithms that scale gracefully  Every replica receives every update eventually “Replace complex deterministic algorithms for replicated database consistency with simple randomized algorithms that require few guarantees from the underlying communication system.“

15 .Why epidemic? Why gossip?  Highly available  Fault-tolerant  Overhead is tunable  Fast  Scalable  Epidemic spreads eventually to everyone

16 .Types of nodes infective – node that holds an update it is willing to share susceptible – node that has not yet received an update  removed – node that has received an update but is no longer willing to share 𝑠+𝑖+𝑟 =1

17 .Types of communication Direct mail Anti-entropy Rumor mongering

18 .DIRECT MAIL  attempts to notify all other sites of an update soon after it occurs.  Social network case – infected accounts sends private message to his whole contact list with malicious link

22 .DIRECT MAIL  Pros: Fast  Cons: not reliable heavy load on network

23 .ANTI-ENTROPY  Every site regularly chooses another site at random and by exchanging database contents with it resolves any differences between the two  Real life case – meet sometimes with old friends and tell all the fun stories about you and your friends.

20点赞

1收藏

11下载