Research On Efficient Erasure Coding Technologies For In-memory Key-value Stores

In order to meet the high-throughput and low-latency high-performance service requirements in real-time scenarios such as big data and cloud computing,in-memory key-value stores are gradually being widely studied and applied as key components.Frequent node failures or network congestion in an in-memory key-value store can seriously impair performance,so it is necessary to ensure its high reliability.Compared with the traditional replication,erasure coding can achieve high reliability with low storage overhead,so it is gradually becoming a common choice in various distributed storage systems to ensure reliability.However,deploying erasure coding in in-memory key-value stores will cause a contradiction between performance requirements of in-memory key-value stores and structural properties of erasure coding,resulting in performance challenges in terms of scaling,storage,repair,and update.Therefore,for in-memory key-value stores,the following three aspects of research are carried out on how to design erasure coding technologies with efficient scaling,efficient storage and repair,and efficient update performance:Since the workload of the in-memory key-value store changes in real time,frequent scaling is required.However,the classic consistent-hash-based scaling scheme will change erasure-coded data chunks and lead to a large number of parity chunk updates,resulting in significant computational and network transfers,and cannot effectively handle degraded reads during the scaling.To address this challenge,a fragmented erasure coding model called Frag EC is proposed,which allows data chunks to be fragmented and stored on multiple nodes through decoupled metadata management,decouples the mapping relationship between data chunks and nodes,and realizes zero parity update overhead during scaling.A multi-hash-ring-based scaling technology is designed to limit scaling operations to part of hash rings,thus ensuring that degraded reads are always available during scaling.Based on the above strategies,a prototype ECHash is implemented.The experimental results show that,compared with the traditional unfragmented single-hash-ring-based scheme,ECHash can improve the scaling throughput by 5.2× and reduce the degraded read latency by 89.0%.Since the storage resources of in-memory key-value stores are expensive and scarce,it is necessary to improve storage efficiency as much as possible.Recently,the latest erasure coding scheme called Wide stripe in industry,can achieve extreme storage efficiency,but it will aggravate data repair penalties and decrease data availability.To address this challenge,a composite locality mechanism called Combined Locality is proposed.It combines the classic parity locality and topology locality mechanisms,systematically addresses the wide-stripe repair problem and examines the trade-off between the storage efficiency and the repair bandwidth.Multi-node encoding and inner-rack parity updates technologies are designed to improve the encoding and update performance of the wide stripe.Based on the above strategies,a prototype ECWide is implemented.The experimental results show that,compared with the classic parity-and topology-locality-based schemes,ECWide can reduce the single-chunk repair time by 90.5% while incurring a redundancy as low as 1.063.Since the updates of in-memory key-value stores are frequent,the traditional erasurecode-based update schemes will lead to a large number of I/Os and network transfers during parity chunk updates,or the significant memory overhead.To address this challenge,a hybrid update architecture called Hybrid PL is proposed.It is the first to introduce parity logging to in-memory key-value stores,performs the in-place update scheme for data chunks and XOR parity chunks achieving low memory overhead and efficient single-chunk repair performance,and leverages the parity logging technology for remaining parity chunks achieving efficient update performance.A merge-based buffer logging is designed to improve the update performance of log nodes.Parity logging with merging and log-assist node repair technologies are designed to improve the repair performance of multiple chunk failures.Based on the above strategies,a prototype Log ECMem is implemented.The experimental results show that,compared with the existing in-place update and full-stripe update schemes,Log ECMem can reduce the update time by 58.0% and the memory overhead by 49.0%.