Algorithms for Optimal Replica Placement Under Correlated Failure in Hierarchical Failure Domains
| Autor: | Neeraj Mittal, K. Alex Mills, Ramaswamy Chandrasekaran |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
FOS: Computer and information sciences
General Computer Science Discrete Mathematics (cs.DM) Computer science Replica Data_MISCELLANEOUS 0102 computer and information sciences 02 engineering and technology 01 natural sciences Condensed Matter::Disordered Systems and Neural Networks Replication (computing) Theoretical Computer Science Tree (data structure) Computer Science - Distributed Parallel and Cluster Computing 010201 computation theory & mathematics Server Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Failure domain 020201 artificial intelligence & image processing Data Structures and Algorithms (cs.DS) Distributed Parallel and Cluster Computing (cs.DC) Algorithm Computer Science - Discrete Mathematics Block (data storage) |
| DOI: | 10.48550/arxiv.1701.01539 |
| Popis: | In data centers, data replication is the primary method used to ensure availability of customer data. To avoid correlated failure, cloud storage infrastructure providers model hierarchical failure domains using a tree, and avoid placing a large number of data replicas within the same failure domain (i.e. on the same branch of the tree). Typical best practices ensure that replicas are distributed across failure domains, but relatively little is known concerning optimization algorithms for distributing data replicas. Using a hierarchical model, we answer how to distribute replicas across failure domains optimally. We formulate a novel optimization problem for replica placement in data centers. As part of our problem, we formalize and explain a new criterion for optimizing a replica placement. Our overall goal is to choose placements in which correlated failures disable as few replicas as possible. We provide two optimization algorithms for dependency models represented by trees. We first present an $O(n + \rho \log \rho)$ time dynamic programming algorithm for placing $\rho$ replicas of a single file on the leaves (representing servers) of a tree with $n$ vertices. We next consider the problem of placing replicas of $m$ blocks of data, where each block may have different replication factors. For this problem, we give an exact algorithm which runs in polynomial time when the skew, the difference in the number of replicas between the largest and smallest blocks of data, is constant. Comment: 64 pages, 9 figures. Preprint submission to Theoretical Computer Science |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|