Write a Blog >>
Mon 24 Feb 2020 09:35 - 10:00 - Key Value Store (Mediterranean Ballroom) Chair(s): Milind Chabbi

Key-Value Stores (KVSs) came into prominence as highly-available, eventually consistent (EC), "NoSQL'' Databases, but have quickly transformed into general-purpose, programmable storage systems. Thus, EC, while relevant, is no longer sufficient. Complying with the emerging requirements for stronger consistency, researchers have proposed KVSs with multiple consistency levels (MCL) that expose the consistency/performance trade-off to the programmer. We argue that this approach falls short in both programmability and performance. For instance, the MCL APIs proposed thus far, fail to capture the ordering relationship between strongly- and weakly-consistent accesses that naturally occur in programs.

Taking inspiration from shared memory, we advocate Release Consistency (RC) for KVSs. We argue that RC’s one-sided barriers are ideal for capturing the ordering relationship between synchronization and non-synchronization accesses while enabling high-performance.

We present Kite, the first highly-available, replicated KVS that offers a linearizable variant of RC for the asynchronous setting with individual process and network failures. Kite enforces RC barriers through a novel fast/slow path mechanism that leverages the absence of failures in the typical case to maximize performance while relying on the slow path for progress. Our evaluation shows that the RDMA-enabled and heavily-multi-threaded Kite achieves orders of magnitude better performance than Derecho (a state-of-the-art RMDA-enabled state machine replication system) and significantly outperforms ZAB (the protocol at the heart of Zookeeper). We demonstrate the efficacy of Kite by porting three lock-free shared memory data structures, and showing that Kite outperforms the competition.

Mon 24 Feb
Times are displayed in time zone: (GMT-07:00) Tijuana, Baja California change

09:35 - 10:25: Main Conference - Key Value Store (Mediterranean Ballroom)
Chair(s): Milind ChabbiUber Technologies Inc.
PPoPP-2020-papers09:35 - 10:00
Vasilis GavrielatosUniversity of Edinburgh, UK, Antonios KatsarakisUniversity of Edinburgh, UK, Vijay NagarajanUniversity of Edinburgh, UK, Boris GrotUniversity of Edinburgh, UK, Arpit JoshiIntel
PPoPP-2020-papers10:00 - 10:25
Hagar MeirIBM Haifa Research Lab, Edward BortnikovYahoo Research, Anastasia BraginskyYahoo Research, Dmitry BasinYahoo Research, Yonatan GottesmanYahoo Research, Eshcar HillelYahoo Research, Oath, Idit KeidarTechnion - Israel institute of technology, Eran MeirYahoo Research, Gali SheffiTechnion - Israel