Pegasus: Tolerating Skewed Workloads in Distributed Storage with In-Network Coherence Directories


Jialin Li, National University of Singapore; Jacob Nelson, Microsoft Research; Ellis Michael, University of Washington; Xin Jin, Johns Hopkins University; Dan R. K. Ports, Microsoft Research


High performance distributed storage systems face the challenge of load imbalance caused by skewed and dynamic workloads. This paper introduces Pegasus, a new storage system that leverages new-generation programmable switch ASICs to balance load across storage servers. Pegasus uses selective replication of the most popular objects in the data store to distribute load. Using a novel in-network coherence directory, the Pegasus switch tracks and manages the location of replicated objects. This allows it to achieve load-aware forwarding and dynamic rebalancing for replicated keys, while still guaranteeing data coherence and consistency. The Pegasus design is practical to implement as it stores only forwarding metadata in the switch data plane. The resulting system improves the throughput of a distributed in-memory key-value store by more than 10x under a latency SLO -- results which hold across a large set of workloads with varying degrees of skew, read/write ratio, object sizes, and dynamism.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {258919,
author = {Jialin Li and Jacob Nelson and Ellis Michael and Xin Jin and Dan R. K. Ports},
title = {Pegasus: Tolerating Skewed Workloads in Distributed Storage with {In-Network} Coherence Directories},
booktitle = {14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)},
year = {2020},
isbn = {978-1-939133-19-9},
pages = {387--406},
url = {},
publisher = {USENIX Association},
month = nov

Presentation Video