Stripeless Data Placement for Erasure-Coded In-Memory Storage

Erasure coding plays a crucial role in distributed storage systems to provide fault tolerance at a low storage cost. Conventional erasure coding schemes are 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 erasure coding scheme. It lets each node in the storage system independently replicate data to other nodes and encode received data replica into parities with XOR. Thus, Nos 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. Evaluations demonstrate that Nostor achieves 1.61x and 2.60x throughputs with similar or lower latencies than stripe-based erasure coding baselines.