Taules de hash distribuïdes

Les taules de hash distribuïdes, o DHT, l'acrònim anglès de Distributed Hash Tables, és un sistema descentralitzat dissenyat per oferir serveis i operacions de recerca en xarxes telemàtiques de computadors. La idea fonamental de les DHT és la creació d'una taula de hash i emmagatzemar-la de forma distribuïda. Una taula de hash és una estructura que mapeja claus amb valors, és a dir, és un llistat de relacions (o parelles) entre dues cadenes de caràcters genèriques. Aquesta idea va ser formulada en una primera aproximació per C.G. Plaxton. Les DHT són habitualment utilitzades en les xarxes P2P estructurades, tal com la xarxa Kademlia.

Capes overlay

Les DHT s'utilitzen per obtenir un alt grau d'eficiència en l'encaminament de les xarxes P2P estructurades. Amb la utilització de les DHT en xarxes P2P s'aconsegueix crear capes overlay. La capa overlay és una xarxa lògica d'alt nivell construïda sobre una altra xarxa ja existent. Els nodes que formen aquesta capa estan units entre ells mitjançant enllaços lògics o virtuals, que s'anomenen camins. És habitual que aquests camins estiguin formats per diversos enllaços físics en les capes inferiors. Les capes overlay no tenen control sobre la forma en què s'encaminen els paquets en les capes inferiors, sols pot determinar en la capa overlay, la seqüència dels nodes que faran possible un cert encaminament. Inclús, en molts models utilitzats per estudiar la commutació de paquets en les xarxes de les capes inferiors, es considera que el trànsit es basa en missatges broadcast. Tot i així, les xarxes overlay han estat proposades com a possible camí per a millorar l'encaminament d'Internet, fins i tot per a complir requisits de qualitat de servei. Utilitzant les capes overlay no necessitem encaminar els missatges adjuntant les adreces IP dels nodes involucrats, sinó que podem encaminar missatges utilitzant les adreces lògiques indicades per la taula de hash distribuïda.

Espai de claus

Una DHT genera un cert espai de claus virtual. Quan parlem d'espai, ho fem en el sentit algebraic de l'expressió, i quan ens referim a claus estem parlant de la part del nom en les parelles nom/valor de les taules de hash. L'espai pot ser el de les cadenes de caràcters de m-bits d'extensió. A continuació, i utilitzant un cert esquema, es divideix la totalitat de l'espai en parts iguals, per atorgar cada una d'aquestes parts a un dels nodes que formen la xarxa. D'aquesta forma cada node es farà càrrec de les claus que caiguin dins de la seva partició o parcel·la, i per tant coneixerà i emmagatzemarà els valors d'aquestes claus. La forma que pren l'espai generat per la DHT i l'esquema utilitzat per a particionar-lo depèn de cadascuna de les xarxes estructurades.

Xarxes P2P de compartició de fitxers

Les xarxes que més freqüentment implementen una DHT són les que tenen com a objectiu la compartició de fitxers. En aquestes xarxes, les parelles clau/valor que formen la taula de hash tenen un concepte concret. Solem veure el valor com un fitxer, i la clau, com a resultat de l'aplicació d'una certa funció hash sobre el valor esmentat. La funció hash utilitzada en la majoria de casos és la SHA 1. En realitat aquesta taula de hash no existeix en cap moment com un únic llistat, sinó que en tot moment és dividida de forma que cada un dels nodes emmagatzemin una porció d'aquesta taula. Gràcies a aquest sistema distribuït, qualsevol node que participi en la DHT pot recuperar eficientment el valor associat a una certa clau. Les DHT suposen que els nodes coneixen una clau i en busquen el valor associat.

Els processos d'emmagatzematge i recerca dins d'una DHT, en el cas de considerar un sistema de compartició de fitxers, succeirien de la següent forma. Per emmagatzemar un fitxer dins la xarxa, primer es calcularia el hash del fitxer en qüestió, i se n'obté una cadena de caràcter de m-bits d'extensió. Aquesta cadena seria la clau, i el fitxer complet seria el valor. A continuació, s'enviaria un missatge a la xarxa per tal que el node responsable de la clau obtinguda rebi el valor del fitxer i pugui emmagatzemar la parella clau/valor (o dit d'altra forma, hash/fitxer). Llavors, qualsevol node dins la xarxa pot conèixer el valor de la clau, enviant el hash del fitxer al node responsable d'aquesta parella.