Effective replication of large data in distributed hash tables

Abstract

I de siste årene har flere peer-to-peer systemer har blitt lansert. Blant dem er Spotify, Skype og Bitcoin. En annen interessant forskningsfelt i peer-to-peer systemer er sosiale nettverk som for eksempel Oneswarm. Peer-to-peer systemer kan være selvstendig og organisere seg for å gi en distribuert-hash-tabell funksjonalitet. Distribuerte hash tabeller, kjent som DHT, tilbyr en nøkkel-verdi lagringstjeneste. DHTer har blitt brukt i mange lagringstjenester som for eksempel Tapestry, Pastry. Selv om DHT er en veldig effektiv måte å lagre og slå opp filer på, oppstår det et problem ved lagring eller oppdatering av relativt store data i DHTer. Fordi verdier blir ofte replikert i DHTer, kan spredning av oppdateringer være treg. Det samme problemet oppstår som dersom noder forlater systemet og nye replikaer må bli skapt for å holde data tilgjengelig og beholde responstiden nede.

Noder i slike systemer kan mangle nødvendige ressurser for å spre relativt store filer raskt. Faktorer som lav båndbredde for avsendere eller trege mottakere kan forsinke spredningen og redusere totale ytelsen til slike systemer. Forsinkelsen kan multipliseres i tilfeller der trege sendere må spre store filer til trege mottakere. Spredningen forsinkelser til side, må trege sendere utnytte hele båndbredden til å spre slike filer. Dette skaper en ubalanse i nettverket, spesielt i dynamisk miljø.

I denne oppgaven, vil vi foreslå en ny spredning protokoll for DHTer. Ved hjelp av denne protokollen, vil systemet være i stand til å spre relativt store data raskt, balansere belastning og holde en lav overhead. I tillegg er faktorer som lav båndbredde. Vår evaluering viser at vår protokollen kan spre store filer raskere og holde overhead til mindre enn 1% i de fleste tilfeller.

In recent years several peer-to-peer systems have been launched. Among them are, Spotify, Skype and BitCoin. Another interesting and developing research field in peer-to-peer systems is online social networks such as Oneswarm. Peer-to-peer systems can autonomously organise themselves to provide DHT functionality. Distributed hash tables, known as DHTs, offer a key-value storage service. DHTs have been used in many storage services such as Tapestry, Pastry and Oneswarm. Although DHTs are very efficient way of storing and looking up small values or files, a problem arises when storing or updating relatively large data in DHTs. As values are often replicated, propagating updates to all replicas might be slow. The same problem occurs as peers leave the system and replicas must be created to serve users quickly or keep data available.

Peers in such systems may not have the necessary resources to propagate relatively large files quickly. Factors such as slow-senders or slow-receivers may delay the propagation and decrease the performance of such system. The delay can be multiplied in cases where slow-senders have to propagate large files to slow-receivers. Propagation delays aside, slow-senders must utilise their entire bandwidth to propagate such files. This creates a hotspot in the network and an obvious load imbalance, especially in a dynamic environment where replicas are created often.

In this thesis, we will propose a new propagation protocol for DHTs. Using this protocol, the system will be able to propagate relatively large data quickly while remaining load-balanced and keeping the overhead low. In addition, factors such as low-bandwidth connections and dynamic environments are taken into account. Our evaluation shows that our protocol can decrease the propagation time while introducing less than 1% overhead in most cases.