Optimizing Distributed Protocols with Query Rewrites [Technical Report]
Proceedings of the ACM on Management of Data(2024)
摘要
Distributed protocols such as 2PC and Paxos lie at the core of many systems
in the cloud, but standard implementations do not scale. New scalable
distributed protocols are developed through careful analysis and rewrites, but
this process is ad hoc and error-prone. This paper presents an approach for
scaling any distributed protocol by applying rule-driven rewrites, borrowing
from query optimization. Distributed protocol rewrites entail a new burden:
reasoning about spatiotemporal correctness. We leverage order-insensitivity and
data dependency analysis to systematically identify correct coordination-free
scaling opportunities. We apply this analysis to create preconditions and
mechanisms for coordination-free decoupling and partitioning, two fundamental
vertical and horizontal scaling techniques. Manual rule-driven applications of
decoupling and partitioning improve the throughput of 2PC by 5× and
Paxos by 3×, and match state-of-the-art throughput in recent work. These
results point the way toward automated optimizers for distributed protocols
based on correct-by-construction rewrite rules.
更多查看译文
关键词
2PC,dataflow,datalog,distributed systems,monotonicity,partitioning,paxos,query optimization,relational algebra
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要