Heterogeneous distributed storage systems

: modeling, optimization and coding

Abstract

Cloud storage is a new paradigm of storing data. It allows users to access data anywhere and anytime. Companies such as Google, Amazon and Facebook are providing this service through their data centers, which are network connected. Such an architecture is called the distributed storage system (DSS). The storage resources that compose these distributed storage systems are heterogeneous in nature, which poses a challenging problem to cloud service providers: How should data be stored in a heterogeneous DSS such that data reliability and data availability are maximized? This thesis is devoted to modeling the heterogeneous distributed storage systems, establishing an optimization framework and constructing codes for such systems. First, we consider heterogeneous distributed storage systems in which storage nodes have different storage costs and different download costs, and investigate how to establish a fundamental tradeoff between system storage cost and system repair cost. We formulate the problem of establishing the tradeoff between system storage cost and system repair cost as a bi-objective linear programming problem subject to the min-cut constraint of information flow graphs. For heterogeneous distributed storage systems with general setting, we give a tight min-cut bound. Moreover, we show that the tradeoff between system storage cost and system repair cost of some special heterogeneous distributed storage systems can be established in polynomial time. Next, we propose a flexible irregular model for heterogeneous distributed storage systems and investigate how the cost of repairing failed storage nodes can be minimized. The fractional repetition (FR) code is generalized to the irregular fractional repetition (IFR) code, which is adaptable to heterogeneous environments and preserves the uncoded repair property. The code structure and the associated storage allocation can be obtained by solving an integer linear programming problem. For moderate sized networks, a heuristic algorithm is proposed and shown to be near-optimal by computer simulations. Finally, we focus on constructing locally repairable (LR) codes over heterogeneous storage networks. We take the network topology into account when repairing a node failure, and accordingly introduce a new concept called node locality. We demonstrate that the decision problem of determining whether a binary linear LR code exists, subject to the constraints of code rate, symbol locality, node locality, and repair cost, is NP-complete. The corresponding optimization version, which aims to maximize the code rate, is also considered. It is proved that the code rate maximization can be reduced to the minimum k-set cover problem, and can be solved in polynomial time for the special case where the symbol locality is one. For the general case where the symbol locality is greater than or equal to two, the problem is NP-hard and can be approximately solved by a greedy algorithm.

Date of Award	16 Feb 2015
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chi Wan SUNG (Supervisor)