Anna: A KVS For Any Scale

Chenggang Wu, Jose Faleiro, Yihan Lin and Joseph M. Hellerstein

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2019-122
August 16, 2019

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-122.pdf

Modern cloud providers offer dense hardware with multiple cores and large memories, hosted in global platforms. This raises the challenge of implementing high-performance software systems that can effectively scale from a single core to multicore to the globe. Conventional wisdom says that software designed for one scale point needs to be rewritten when scaling up by 10-100x. In contrast, we explore how a system can be architected to scale across many orders of magnitude by design. We explore this challenge in the context of a new key-value store system called Anna: a partitioned, multi-mastered system that achieves high performance and elasticity via wait-free execution and coordination-free consistency. Our design rests on a simple architecture of coordination-free actors that perform state update via merge of lattice-based composite data structures. We demonstrate that a wide variety of consistency models can be elegantly implemented in this architecture with unprecedented consistency, smooth fine-grained elasticity, and performance that far exceeds the state of the art.

Advisor: Joseph M. Hellerstein


BibTeX citation:

@mastersthesis{Wu:EECS-2019-122,
    Author = {Wu, Chenggang and Faleiro, Jose and Lin, Yihan and Hellerstein, Joseph M.},
    Title = {Anna: A KVS For Any Scale},
    School = {EECS Department, University of California, Berkeley},
    Year = {2019},
    Month = {Aug},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-122.html},
    Number = {UCB/EECS-2019-122},
    Abstract = {Modern cloud providers offer dense hardware with multiple cores and large memories, hosted in global platforms. This raises the challenge of implementing high-performance software systems that can effectively scale from a single core to multicore to the globe. Conventional wisdom says that software designed for one scale point needs to be rewritten when scaling up by 10-100x. In contrast, we explore how a system can be architected to scale across many orders of magnitude by design.
We explore this challenge in the context of a new key-value store system called Anna: a partitioned, multi-mastered system that achieves high performance and elasticity via wait-free execution and coordination-free consistency. Our design rests on a simple architecture of coordination-free actors that perform state update via merge of lattice-based composite data structures. We demonstrate that a wide variety of consistency models can be elegantly implemented in this architecture with unprecedented consistency, smooth fine-grained elasticity, and performance that far exceeds the state of the art.}
}

EndNote citation:

%0 Thesis
%A Wu, Chenggang
%A Faleiro, Jose
%A Lin, Yihan
%A Hellerstein, Joseph M.
%T Anna: A KVS For Any Scale
%I EECS Department, University of California, Berkeley
%D 2019
%8 August 16
%@ UCB/EECS-2019-122
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-122.html
%F Wu:EECS-2019-122