PaRS: A Popularity-Aware Redundancy Scheme for In-Memory Stores

In-memory store has become a key component for an increasing number of data-intensive applications like OLTP and OLAP. To be resilient to data loss incurred by transient failures, redundancy strategies are incorporated into in-memory stores. In-memory datasets are characterized by skewed popularity, because they exhibit varied access frequencies (a.k.a., number of accesses). Therefore, it is prudent to apply customized redundancy schemes with dynamic memory efficiency and access parallelisms to different in-memory datasets. In this work, we propose an adaptive redundancy scheme-PaRS-for in-memory datasets. PaRS relies on a re-stripe or replication mechanism to transform involved redundancy groups according to their workload popularity growth. With PaRS in place, a memory-efficient redundancy layout is deployed for data blocks with low access frequencies; a redundancy layout exhibiting high access parallelism is adopted for highly-accessed data blocks. Compared with existing redundancy schemes that employ simple replication or erasure coding, PaRS facilitates a configurable tradeoff between memory efficiency and access parallelism for in-memory data blocks. Quantitative evaluations using YCSB show that PaRS enables in-memory stores to exhibit higher access performance and memory efficiency than the replication scheme. Furthermore, PaRS achieves better load balancing than the erasure coding, while sustaining superb access performance and memory efficiency. In particular, under a double-fault-tolerant in-memory store of limited memory, PaRS improves access latency by 15.1 to 31.5 percent compared to 3-way replication, and PaRS enhances load balancing by more than 3.9× relative to Reed-Solomon coding.