Modeling and Analysis of P2P Data Storage Systems
Julian Monteiro
Supervised by Stéphane Pérennes and Olivier DalleAbstract
Large scale peer-to-peer systems are foreseen as a way to provide highly reliable data storage at low cost. To achieve high durability, such P2P systems encode the user data in a set of redundant fragments and distribute them among the peers (see Figure 1). This redundancy has to be constantly monitored and maintained by a reconstruction process due to the occurrence of peer failures or departures. Indeed, the system performance depends on many parameters that need to be well tuned, such as the factor of redundancy, the code scheme used, the frequency of data repair and the size of a data block. These parameters impact the amount of resources (e.g., bandwidth, storage space, etc.) needed to obtain a certain reliability (e.g., probability to lose data). This thesis aims at providing tools to analyse and predict the performance of large scale data storage systems. Thus, different techniques are studied and applied. They range from formal analysis (using Markov chains and fluid models), simulations, and experimentation (using Grid5000 platform). By comparing to simulations, we show that Markov chain models give correct approximations of the system average behavior, but fails to capture its variations over time. Our main contribution is a new stochastic model based on fluid approximation, that capture the deviations around the mean behavior. We also use queuing models to estimate the repair time under limited bandwidth. We additionally study different ways to distribute fragments (placement strategies), and study a hybrid code that reduces the repair bandwidth consumption. Lastly, we conducted real experimentation on the Grid5000 platform to validate our results.
The contributions are organized as following:
- Methodology: We give an overview of the analysis techniques used throughout the thesis. First we give some background on the use of discrete time Markov chains to estimate the mean behavior of dynamic systems. Then, we present a simple example of modeling the populations of rabbits. This small example already exhibits the problematic of capturing the variations around the mean value. Then, we describe how to better capture the system dynamics by presenting the insights of a stochastic Fluid model. We finish with the description and discussion of simulation techniques.
- Mean Behavior and Guideline to Lazy Repair: We model a general storage system by using a Markov chain model. This model allows us to take into account the effects of disk failures along with the time consumed by the self-repairing process. We confirm that a lazy repair strategy can be employed to amortize the repairing cost, mainly bandwidth. We then derive closed-form mathematical expressions that estimate the system average behavior. These formulas give a good intuition of the system dynamics. Our contribution is a guideline to system designers and administrators to choose the best set of parameters.
* The results presented in this chapter appeared in [JDIR10] and were published in [P2P09, Globecom10]. - Capturing the Variations: We propose and study fluid models that assess the variations on the bandwidth consumption and the probability to lose data. These variations are caused by the simultaneous loss of multiple data blocks that results from a peer failure (or a peer leaving the system). In addition to its expectation, it gives a correct estimation of its variations.
* The results presented in this chapter appeared in [Algotel09] and were published in [P2P09]. - Repair Time Distribution under Limited Bandwidth: The speed of the repair of a data block is crucial for its survival. This speed is mainly determined by how much bandwidth is available. But in practice, concurrent reconstructions do compete for the same bandwidth. In this chapter, we propose a new analytical framework that takes into account this correlation. Mainly, we introduce queuing models in which reconstructions are served by peers at a cadence that depends on the available bandwidth. Moreover, we study the efficiency of different schedul- ing policies when serving data. The goal of this study is to provide a tight estimation of the probability to lose data under constrained bandwidth.
* The results presented in this chapter has been submitted for publication. - Data Placement Strategies: We study the impact of different data placement strategies on the system performance. This study is motivated by practical peer-to-peer storage systems that store data in logical neighbors. We use simulations and combinatorial models to show that, without resource constraints, the average values are the same no matter which placement policy is used. However, the variations in the use of bandwidth are much more bursty under the local policies (in which the data are stored in logical neighbors). When the bandwidth is limited, these bursty variations induce longer maintenance time and henceforth a higher risk of data loss.
* The results presented in this chapter appeared in [Algotel10] and were published in [LCN09, Globe10]. - Hybrid Coding: The reconstruction process of storage systems based on erasure codes (e.g., Reed-Solomon) have an important overhead in bandwidth consumption. In this chapter, we study the use of Hybrid coding: mixing erasure codes and simple data replication, i.e., keep one replica of the data along with the erasure codes. We model this systems using Markov chains, and then derive closed-form expressions to approximate the bandwidth usage and the system durability. We show when the Hybrid system has better trade-offs between bandwidth, space usage, and durability.
* The results presented in this chapter is been prepared for publication.