some in-memory erasure code systems

2021/06/23 Storage

EC is mainly for cold storage, providing low redundancy costs and availibity. But there are still some works on in-memory storage.

updating…

why we need EC in memory??

EC is not fast enough.

encoding, transferring need times

caching

(OSDI ‘16) EC-Cache: Load-balanced, Low-latency Cluster Caching with Online Erasure Coding

image.png

data management

(TODS ‘05) LH* RS—a highly-available scalable distributed data structure

(SYSTOR ‘17) Erasure coding for small objects in in-memory KV storage.

MemEC.

hybrid encoding

To save storage cost while keeping availability, they use EC for large data (like value).

image.png

all-encoding

but if value is too small, then MemEC encode the whole objects. And one chunk (4KB) is related to multiple [metadata, key, value] pairs.

Once the size of a new chunk reach its limit, it will be sealed. And only sealed data chunk will be encoded. Also, data in chunks can be updated unless the size is larger than the limit. Thanks to linear combination, the cost of updating parity chunk is small.

Chunk and object index maps are based on cuckoo hashing.

seems like a lazy-approach…

image.png

(FAST ‘16, TOS ‘17) Efficient and available in-memory KV-store with hybrid erasure coding and replication

Cocytus

consistent hashing

(SoCC ‘19) Coupling decentralized key-value stores with erasure coding

(EuroSys ‘18) Fast and strongly consistent per-item resilience in key-value stores

ref

  1. Rashmi, K. V., et al. “EC-Cache: Load-balanced, low-latency cluster caching with online erasure coding.” 12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16). 2016.
  2. Litwin, Witold, Rim Moussa, and Thomas Schwarz. “LH* RS—a highly-available scalable distributed data structure.” ACM Transactions on Database Systems (TODS) 30.3 (2005): 769-811.
  3. Yiu, Matt MT, Helen HW Chan, and Patrick PC Lee. “Erasure coding for small objects in in-memory kv storage.” Proceedings of the 10th ACM International Systems and Storage Conference. 2017.
  4. Chen, Haibo, et al. “Efficient and available in-memory KV-store with hybrid erasure coding and replication.” ACM Transactions on Storage (TOS) 13.3 (2017): 1-30.
  5. Cheng, Liangfeng, Yuchong Hu, and Patrick PC Lee. “Coupling decentralized key-value stores with erasure coding.” Proceedings of the ACM Symposium on Cloud Computing. 2019.
  6. Taranov, Konstantin, Gustavo Alonso, and Torsten Hoefler. “Fast and strongly-consistent per-item resilience in key-value stores.” Proceedings of the Thirteenth EuroSys Conference. 2018.

Search

    Table of Contents