A Layered Architecture for Erasure-Coded Consistent Distributed Storage

DOI10.1145/3087801.3087832MaRDI QIDQ5368941zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 11 October 2017

Published in Proceedings of the ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.01286, https://hdl.handle.net/1721.1/137772

zbMATH Keywords

consistencyerasure codesfault toleranceregenerating codeslivenesscommunication coststorage costedge computingasynchronous distributed networkobject storage

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Distributed algorithms (68W15) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Abstract: Motivated by emerging applications to the edge computing paradigm, we introduce a two-layer erasure-coded fault-tolerant distributed storage system offering atomic access for read and write operations. In edge computing, clients interact with an edge-layer of servers that is geographically near; the edge-layer in turn interacts with a back-end layer of servers. The edge-layer provides low latency access and temporary storage for client operations, and uses the back-end layer for persistent storage. Our algorithm, termed Layered Data Storage (LDS) algorithm, offers several features suitable for edge-computing systems, works under asynchronous message-passing environments, supports multiple readers and writers, and can tolerate $f_1<n_1/2$ and $f_2<n_2/3$ crash failures in the two layers having $n_1$ and $n_2$ servers, respectively. We use a class of erasure codes known as regenerating codes for storage of data in the back-end layer. The choice of regenerating codes, instead of popular choices like Reed-Solomon codes, not only optimizes the cost of back-end storage, but also helps in optimizing communication cost of read operations, when the value needs to be recreated all the way from the back-end. The two-layer architecture permits a modular implementation of atomicity and erasure-code protocols; the implementation of erasure-codes is mostly limited to interaction between the two layers. We prove liveness and atomicity of LDS, and also compute performance costs associated with read and write operations. Further, in a multi-object system running $N$ independent instances of LDS, where only a small fraction of the objects undergo concurrent accesses at any point during the execution, the overall storage cost is dominated by that of persistent storage in the back-end layer, and is given by $Theta(N)$.

Recommendations

• Optimistic Erasure-Coded Distributed Storage
• Architecture-aware coding for distributed storage: repairable block failure resilient codes
• Sparsity exploiting erasure coding for distributed storage of versioned data
• Information-Theoretically Secure Erasure Codes for Distributed Storage

Cited in

(5)

• Brief Announcement: CausalEC: A Causally Consistent Data Storage Algorithm based on Cross-Object Erasure Coding
• Radon: repairable atomic data object in networks
• Optimistic Erasure-Coded Distributed Storage
• Self-stabilizing and private distributed shared atomic memory in seldomly fair message passing networks
• Modeling and optimization of latency in erasure-coded storage systems

This page was built for publication: A Layered Architecture for Erasure-Coded Consistent Distributed Storage

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368941)