PLATO Predictive LatencyAware Total Ordering柏拉图预测延迟感知全序.pptVIP

PLATO: Predictive Latency-Aware Total Ordering Mahesh Balakrishnan Ken Birman Amar Phanishayee Total Ordering a.k.a Atomic Broadcast delivering messages to a set of nodes in the same order messages arrive at nodes in different orders… nodes agree on a single delivery order messages are delivered at nodes in the agreed order Modern Datacenters Applications E-tailers, Finance, Aerospace Service-Oriented Architectures, Publish-Subscribe, Distributed Objects, Event Notification… … Totally Ordered Multicast! Hardware Fast high-capacity networks Failure-prone commodity nodes Total Ordering in a Datacenter Multicast Wishlist Low Latency! High (stable) throughput Minimal, proactive overheads Leverage hardware properties HW Multicast/Broadcast is fast, unreliable Handle varying data rates Datacenter workloads have sharp spikes… and extended troughs! State-of-the-Art Traditional Protocols Conservative Latency-Overhead tradeoff Example: Fixed Sequencer Simple, works well Optimistic Total Ordering: deliver optimistically, rollback if incorrect Why this works – No out-of-order arrival in LANs Optimistic total ordering for datacenters? PLATO: Predictive Ordering In a datacenter, broadcast / multicast occurs almost instantaneously Most of the time, messages arrive in same order at all nodes. Some of the time, messages arrive in different orders at different nodes. Can we predict out-of-order arrival? Reasons for Disorder: Swaps Emulab Testbed (Utah) Cornell Testbed Disorder: Emulab3 Disorder Predicting Disorder Predictor: Inter-arrival time of consecutive packets into user-space Why? Swaps: simultaneous multicasts ? low inter-arrival time Loss: kernel buffer overflow ? sequence of low inter-arrival times Predicting Disorder 95% of swaps and 14% of all pairs are within 128 μsecs Predicting Disorder PLATO Design Heuristic: If two packets arrive within Δ μsecs, possibility of disorder PLATO Heuristic + Lazy Fixed Sequencer Heuristic works ? ~ zero (Δ) latency Heuristi