Modeling and analysis of reliable peer-to-peer storage systems
Institution:
NiceDisciplines:
Directors:
Abstract EN:
This thesis aims at providing tools to analyze and predict the performance of general large scale data storage systems. We use these tools to analyze the impact of different choices of system design on different performance metrics. For instance, the bandwidth consumption, the storage space overhead, and the probability of data loss should be as small as possible. Different techniques are studied and applied. First, we describe a simple Markov chain model that harnesses the dynamics of a storage system under the effects of peer failures and of data repair. Then we provide closed-form formulas that give good approximations of the model. These formulas allow us to understand the interactions between the system parameters. Indeed, a lazy repair mechanism is studied and we describe how to tune the system parameters to obtain an efficient utilization of bandwidth. We confirm by comparing to simulations that this model gives correct approximations of the system average behavior, but it does not capture its variations over time. We then propose a new stochastic model based on a fluid approximation that indeed captures the deviations around the mean behavior. These variations are most of the time neglected by previous works, despite being very important to correctly allocate the system resources. We additionally study several other aspects of a distributed storage system: we propose queuing models to calculate the repair time distribution under limited bandwidth scenarios; we discuss the trade-offs of a Hybrid coding (mixing erasure codes and replication); and finally we study the impact of different ways to distribute data fragments among peers, i. E. , placement strategies.
Abstract FR:
Cette thèse vise à fournir des outils permettant d’analyser et de prédire la performance de systèmes de stockage de données à grande échelle. Nous avons utilisé ces outils pour analyser l’impact de différents choix de conception du système sur différentes mesures de performance. Par exemple, la consommation de bande passante, l’espace de stockage et la probabilité de perdre des données doivent être aussi faibles que possible. Tout d’abord, nous décrivons un modèle simple par chaîne de Markov et nous établissons des formules mathématiques closes. Ces formules nous permettent de comprendre les interactions entre les paramètres du système. Nous confirmons en comparant à des simulations que ces modèles donnent des approximations correctes du comportement moyen du système. En effet, un mécanisme de réparation paresseux est étudié et nous décrivons comment régler les paramètres du système pour obtenir une utilisation efficace de la bande passante. Nous proposons ensuite un nouveau modèle stochastique basé sur une approximation fluide pour saisir les écarts par rapport au comportement moyen. De plus, nous étudions plusieurs autres aspects d’un système de stockage distribué : nous utilisons un modèle de files d’attente pour calculer le temps de réparation pour un système avec bande passante limitée ; nous étudions un système de codage hybride : en mixant les codes d’effacement avec la simple réplication des données ; enfin, nous étudions l’impact des différentes façons de distribuer des fragments de données entre les pairs.