Exploiting Nil-Externality for Fast Replicated Storage

Aishwarya Ganesan, Ramnatthan Alagappan, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Do some storage interfaces enable higher performance than others? Can one identify and exploit such interfaces to realize high performance in storage systems? This paper answers these questions in the affirmative by identifying nil-externality, a property of storage interfaces. A nil-externalizing (nilext) interface may modify state within a storage system but does not externalize its effects or system state immediately to the outside world. As a result, a storage system can apply nilext operations lazily, improving performance. In this paper, we take advantage of nilext interfaces to build high-performance replicated storage. We implement Skyros, a nilext-aware replication protocol that offers high performance by deferring ordering and executing operations until their effects are externalized. We show that exploiting nil-externality offers significant benefit: for many workloads, Skyros provides higher performance than standard consensus-based replication. For example, Skyros offers 3x lower latency while providing the same high throughput offered by throughput-optimized Paxos.

Original languageEnglish (US)
Title of host publicationSOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles
PublisherAssociation for Computing Machinery
Number of pages17
ISBN (Electronic)9781450387095
StatePublished - Oct 26 2021
Externally publishedYes
Event28th ACM Symposium on Operating Systems Principles, SOSP 2021 - Virtual, Online, Germany
Duration: Oct 26 2021Oct 29 2021


Conference28th ACM Symposium on Operating Systems Principles, SOSP 2021
CityVirtual, Online


  • Fault-tolerance
  • Replication
  • Storage

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Science Applications
  • Software


Dive into the research topics of 'Exploiting Nil-Externality for Fast Replicated Storage'. Together they form a unique fingerprint.

Cite this