Coding techniques for distributed storage

  1. Gastón Brasó, Bernat
Supervised by:
  1. Jaume Pujol Capdevila Director
  2. M. Villanueva Director

Defence university: Universitat Autònoma de Barcelona

Fecha de defensa: 29 November 2013

Committee:
  1. Josep Rifa Coma Chair
  2. Angela Barbero Díez Secretary
  3. Diego Napp Avelli Committee member

Type: Thesis

Teseo: 352015 DIALNET lock_openTDX editor

Abstract

Encara que l'emmagatzematge online d'informació és un negoci creixent, no està exempt de problemàtiques, una d'elles és la persistència i accessibilitat de les dades. Cal replicar les dades de manera que si es perd una còpia no es perdi la informació de forma definitiva. Malauradament, la replicació de dades (coneguda com a ``backup'') no és una solució eficient, ja que introdueix molta redundància que provoca sobre costos. Els codis correctors d'errors són coneguts per augmentar la persistència i l'accessibilitat de les dades minimitzant la redundància necessària. Però el seu us introdueix altres problemes com l'anomenat ``repair problem'': com substituir un node d'emmagatzematge descarregant el mínim de dades dels altres nodes. En aquesta dissertació, estudiem l'estat de l'art pel que fa als codis aplicats a sistemes d'emmagatzematge distribuïts, com per exemple el ``cloud storage''. També ens introduïm al ``repair problem'' des de la vessant més aplicada, usant topologies de sistemes reals com els ``data centers''. Concretament, aportem una família de codis regeneratius que anomenem quasi-cyclic flexible regenerating codes i que es caracteritza per minimitzar l'ús de recursos computacionals en el procés de regeneració d'un node. Alhora, aquesta solució minimitza les dades emmagatzemades i l'ample de banda necessari per regenerar un node que falla. També estudiem el cas en que els costos de descàrrega de les dades no són homogenis. En concret, ens centrem en el cas dels racks, on els nodes d'emmagatzematge estan distribuïts en racks, i el cost de descàrrega de dades dels nodes en el mateix rack és molt menor que el cost de descàrrega de dades dels nodes en un altre rack. Aquest nou model generalitza els models teòrics anteriors i ens permet comprovar que els costos poden disminuir si adaptem el model teòric a la topologia concreta del sistema d'emmagatzematge distribuït.