RE-Store: Reliable and Efficient KV-Store with Erasure Coding and Replication

Yuzhe Li, Jiang Zhou, Weiping Wang, Yong Chen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations


In-memory key/value stores (KV-stores) are a key building block for numerous applications running on a cluster. As cluster scales have grown, efficiency and availability have become increasingly critical characteristics. Traditional replication provides redundancy, but is inefficient due to its high storage overhead. Erasure coding can provide data reliability with significantly lower storage requirements, but is primarily used for long-term archival data due to the limitation of its write performance. Recent studies have attempted to combine these two techniques by using replication for frequently-updated metadata, and erasure coding for large, read-only data. In this study, we propose RE-Store, an in-memory key/value store system which utilizes a novel hybrid replication/erasure coding scheme to achieve both efficiency and reliability. RE-Store introduces replication into erasure coding by making one copy of each encoded datum and replacing partial parity with replicas for improved storage-efficiency. When failures occur, it uses these replicas to ensure data availability and thus avoids the inefficiencies of erasure coding during repair. RE-Store provides fault tolerance through fast, online recovery during different failure scenarios with little performance degradation. We have implemented RE-Store on a real key/value system and conducted extensive evaluations to validate its design and to study its performance, efficiency, and reliability. Experimental results show that RE-Store performs similarly to erasure coding and replication under normal operations while saving 18% to 34% of the memory used by replication when tolerating 2 to 4 failures.

Original languageEnglish
Title of host publicationProceedings - 2019 IEEE International Conference on Cluster Computing, CLUSTER 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728147345
StatePublished - Sep 2019
Event2019 IEEE International Conference on Cluster Computing, CLUSTER 2019 - Albuquerque, United States
Duration: Sep 23 2019Sep 26 2019

Publication series

NameProceedings - IEEE International Conference on Cluster Computing, ICCC
ISSN (Print)1552-5244


Conference2019 IEEE International Conference on Cluster Computing, CLUSTER 2019
Country/TerritoryUnited States


  • KV-store
  • availability and reliability
  • erasure coding
  • fault tolerance
  • replication


Dive into the research topics of 'RE-Store: Reliable and Efficient KV-Store with Erasure Coding and Replication'. Together they form a unique fingerprint.

Cite this