Achieving Availability, Efficiency, and Elasticity in Stripeless Erasure-Coded Storage

Erasure coding plays a crucial role in distributed storage systems to provide fault tolerance at a low storage cost. Conventional erasure coding schemes determine data placement based on stripes. However, placing data into stripes can incur non-negligible performance overheads that will manifest in emerging fast in-memory storage systems, making conventional erasure coding schemes suboptimal in such scenarios. Aiming to eliminate such overheads, we present Nos , a stripeless placement scheme for erasure-coded distributed in-memory storage. It lets each node independently replicate data to other nodes and encode received data replicas into parities with XOR. Thus, it avoids the overheads caused by stripes. To enable failure recovery, Nos uses a combinatoric structure called symmetric balanced incomplete block design (SBIBD) to decide primary-to-backup node affinities during replication. Atop Nos , we further build Nostor , a distributed in-memory key-value store. We also achieve high availability and efficient foreground serving simultaneously with Hotness-aware Two-phase Reconstruction ( HR ). Evaluations demonstrate that Nostor achieves 1.61× to 2.60× throughputs compared to Cocytus , PQ , and Split with similar or lower latencies than these stripe-based erasure coding baselines. Equipped with HR , Nostor + HR also achieves 46.7% P999 foreground latency reduction during node repair.