国家重点研发计划(2017YFB1001804)
阿里巴巴创新研究计划(Alibaba Innovative Research,AIR)
[1] Lamport L. The part-time parliament. ACM Trans Comput Syst, 1998, 16: 133-169 CrossRef Google Scholar
[2] Ongaro D, Ousterhout J. In search of an understandable consensus algorithm. In: Proceedings of USENIX Annual Technical Conference (USENIX ATC '14), Philadelphia, 2014. 305--319. Google Scholar
[3] Demers A, Greene D, Hauser C, et al. Epidemic algorithms for replicated database maintenance. In: Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing (PODC '87), New York, 1987. Google Scholar
[4] Birman K P, Hayden M, Ozkasap O. Bimodal multicast. ACM Trans Comput Syst, 1999, 17: 41-88 CrossRef Google Scholar
[5] Sharma Y, Ajoux P, Ang P, et al. Wormhole: reliable pub-sub to support geo-replicated internet services. In: Proceedings of the 12th USENIX Conference on Networked Systems Design and Implementation (NSDI '15), Berkeley, 2015. 351--366. Google Scholar
[6] Ji S P, Ye C Y, Wei J, et al. MERC: match at edge and route intra-cluster for content-based publish/subscribe systems. In: Proceedings of the 16th Annual Middleware Conference (Middleware '15), New York, 2015. 13--24. Google Scholar
[7]
Alibaba. Nacos: an easy-to-use dynamic service discovery, configuration and service management platform for building cloud native applications. 2019.
[8] Kulkarni S S, Demirbas M, Madappa D, et al. Logical physical clocks. In: Proceedings of International Conference on Principles of Distributed Systems (OPODIS '14), Cham, 2014. 17--32. Google Scholar
[9]
Demirbas M, Leone M, Avva B, et al. Logical physical clocks and consistent snapshots in globally distributed databases.
[10] Lin M J, Marzullo K. Directional gossip: gossip in a wide area network. In: Proceedings of the 3rd European Dependable Computing Conference on Dependable Computing (EDCC-3), Berlin, 1999. 364--379. Google Scholar
[11] Eugster P T, Guerraoui R, Handurukande S B, et al. Lightweight probabilistic broadcast. In: Proceedings of International Conference on Dependable Systems and Networks (DSN '01), Washington DC, 2001. 443--452. Google Scholar
[12] Eugster P T, Guerraoui R, Handurukande S B. Lightweight probabilistic broadcast. ACM Trans Comput Syst, 2003, 21: 341-374 CrossRef Google Scholar
[13] Demers A, Greene D, Houser C, et al. Epidemic algorithms for replicated database maintenance. ACM SIGOPS Operating Syst Rev, 1988, 22: 8--32. Google Scholar
[14]
Apache. Apache Cassandra. 2019.
[15]
HashiCorp. Consul by HashiCorp. 2019.
[16]
Facebook. Location-aware distribution: configuring servers at scale, 2019.
[17]
Facebook. Systems at scale 2018: scaling data distribution at Facebook using LAD. 2019.
[18] Costa P, Migliavacca M, Picco G P, et al. Introducing reliability in content-based publish-subscribe through epidemic algorithms. In: Proceedings of the 2nd International Workshop on Distributed Event-based Systems (DEBS '03), New York, 2003. Google Scholar
[19] Riabov A, Liu Z, Wolf J L, et al. Clustering algorithms for content-based publication-subscription systems. In: Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS '02), Vienna, 2002. 133--142. Google Scholar
[20] Opyrchal L, Astley M, Auerbach J, et al. Exploiting IP multicast in content-based publish-subscribe systems. In: Proceedings of IFIP/ACM International Conference on Distributed Systems Platforms (Middleware '00), Heidelberg, 2000. 185--207. Google Scholar
[21] Li G L, Hou S, Jacobsen H-A. A unified approach to routing, covering and merging in publish/subscribe systems based on modified binary decision diagrams. In: Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS '05), Washington DC, 2005. 447--457. Google Scholar
[22] Li G L, Muthusamy V, Jacobsen H-A. Adaptive content-based routing in general overlay topologies. In: Proceedings of the 9th ACM/IFIP/USENIX International Conference on Middleware (Middleware '08), Berlin, 2008. Google Scholar
[23] Mahambre S P, Kumar S.D. M, Bellur U. A Taxonomy of QoS-Aware, Adaptive Event-Dissemination Middleware. IEEE Internet Comput, 2007, 11: 35-44 CrossRef Google Scholar
[24] D'Angelo G, Ferretti S, Marzolla M. Adaptive event dissemination for peer-to-peer multi-player online games. In: Proceedings of the 4th International ICST Conference on Simulation Tools and Techniques (SIMUTools '11), Brussels, 2011. 312--319. Google Scholar
Figure 1
(Color online) Overview of configuration update delivery in large-scale clusters
Figure 2
(Color online) Communications between nodes
Figure 3
(Color online) An example of configuration delivery in the large-scale cluster
Figure 4
(Color online) The complete $N$-ary tree-based overlay
Figure 5
(Color online) Performance evaluation in a large-scale cluster with $2\times10^5$ clients
Figure 6
(Color online) Performance evaluation in a large-scale cluster with $10^6$ clients
Figure 7
(Color online) Update delivery in a cluster with 20% nodes unreachable
Figure 8
(Color online) Performance of using different parameters
Figure 9
(Color online) Performance of using different phases
Initialization; |
|
send Req to $c$; |
|
DoSend($c$); |
|
Initialization; |
send Req to root;ELSIFReq is sent from $P_k$ |
update local state from Req and resolve conflicts; |
DoSend($P_i$); |
send Req to all connected clients; |
send Ack to $P_k$;ELSIFReq is Ack sent from $P_j(j~\neq~i)$ |
send Ack to parent; |