Chen Chen, Yoav Tock, and Sarunas Girdzijauskas.
In Proceedings of the 12th ACM International Conference on Distributed and Event-Based Systems (DEBS 2018), 2018.
Distributed pub/sub must make principal design choices with regards
to overlay topologies and routing protocols. It is challenging
to tackle both aspects together, and most existing work merely
considers one.We argue the necessity to address both problems simultaneously, since only the right combination of the two can deliver
an efficient internet-scale pub/sub. Traditional design space
spans from structured data-oblivious overlays employing greedy
routing strategies all the way to unstructured data-driven overlays
using naive broadcast-based routing. The two ends of the spectra
come with unacceptable prices: the former often exerts considerable
overhead on each node for forwarding irrelevant messages,
while the latter is difficult to scale due to prohibitive latencies stemming
from unbounded node degrees and network diameters.
To achieve the best of both worlds, we propose BeaConvey, a distributed pub/sub system for federated environments. First, we define the small-world and interest-close overlay (SWICO) that embraces both small-world properties and pub/sub semantics. To construct a SWCIO, we devise a greedy heuristic to assign small-world identifiers and fingers in a centralized manner. Second, we develop a family of peer-to-peer pub/sub routing protocols that leverages such SWICOs.
Empirical evaluation shows that BeaConvey achieves substantial improvement in routing overhead and propagation delays. For instance, the routing overhead of BeaConvey is only 20% to 40% of the state of the art. This acceleration is consistent across a variety of pub/sub workloads, and BeaConvey obtains such adaptability by optimizing both overlay and routing, which complement each other in different situations. Under one Facebook workload with a skewed distribution, 78% of the improvement is accredited to a better overlay. Under another non-skewed workload, more advanced routing contributes 95% of cost reduction.