Kademlia

Kademlia és una manera d'implementar una taula de hash distribuïda, o DHT, per a utilitzar-se en xarxes P2P, dissenyada per Petar Maymounkov i David Mazières. S'hi especifica l'estructura de la xarxa i com intercanviar informació entre els nodes constituents. Els nodes de Kademlia parlen entre si usant el protocol UDP per motius de rendiment.

L'objectiu de Kademlia és emmagatzemar i recuperar informació a/de la xarxa. És una base de dades distribuïda.

Kademlia és molt eficient. És també molt escalable: la mida de la xarxa pot créixer enormement sense que se'n vegi afectat el rendiment.

Kademlia és molt resistent a talls, avaries i atacs, dels que es recupera per sí sola en temps molt curts. És pràcticament impossible fer caure una xarxa com aquesta ni dividir-la en subxarxes.

Diverses xarxes d'intercanvi de fitxers usen Kademlia internament.

Distància

Cada node s'identifica dins de la xarxa mitjançant la seva ID o identificació de node. L'estructura de la xarxa es basa en aquesta ID.

El coneixement que cada node té de la xarxa depèn de la distància entre aquest node i els altres nodes. La xarxa determina un concepte de distància. Gràcies a això un node sempre pot comparar la distància des de la seva ID a la de dos altres nodes i decidir quin dels dos és més a prop o més lluny. Un node té un molt bon coneixement de la xarxa de prop seu (coneix la ID de tots els nodes més propers), i un coneixement decreixent amb la distància de la resta de parts de la xarxa (coneix la ID de només uns pocs de tots els nodes existents).

La distància a kademlia es defineix sobre l'espai de ID's i no té res a veure amb les adreces IP ni amb la distància física.

Valor i Clau

La informació que s'emmagatzema s'anomena Valor, tot Valor necessita una Clau que hi apunti.

Les claus tenen el mateix format que les IDs dels nodes. Gràcies a això un node "A" pot calcular la distància entre una clau i les IDs de dos altres nodes "B" i "C" i decidir quin dels dos és el més proper a aquesta clau. Els altres nodes estaran d'acord amb aquest càlcul.

Per a emmagatzemar un valor, abans cal conèixer sota quina clau es guardarà. Normalment s'utilitza el mateix valor per a calcular un hash a partir d'ell. El hash serà la clau.

Cerca de nodes

S'utilitza la clau per a trobar els nodes amb IDs més properes a la clau. Això es fa explorant la xarxa d'una manera iterativa, on cada pas proporciona IDs de nodes més i més propers a la clau. A continuació es pot procedir a emmagatzemar o recuperar els valors als nodes més propers a la clau.

Taules d'encaminament

El coneixement que un node té de la xarxa es guarda a la seva memòria i s'actualitza constantment amb tots els nodes que va coneixent, ja sigui quan emmagatzema valors, recupera valors o simplement ajuda a altres nodes a trobar nodes propers a claus. D'aquesta manera la xarxa s'actualitza a si mateixa constantment i emmagatzema una gran quantitat de redundància sobre la seva pròpia estructura.

La memòria que un node guarda sobre l'estructura de la xarxa està organitzada en diverses llistes (taules d'encaminament). Hi ha una llista per a cada bit que tingui la ID. És a dir, si s'utilitza una ID de 160 bits, cada node mantindrà 160 taules d'encaminament diferents. Cada taula d'encaminament correspon a cada bit de distància entre el mateix node i els altres nodes. Els altres nodes es guarden a una taula d'encaminament o altra depenent de la distància amb aquest node.

La mida de cada taula d'encaminament és un paràmetre comú a tota la xarxa anomenat k. Cada taula d'encaminament pot contenir fins a k nodes. La informació que es guarda de cada node és la seva ID i les dades que cal saber per a contactar-lo, és a dir, la seva adreça IP, port, etc. Un valor típic de k pot ser 10.

La quantitat de IDs possibles és molt més gran que la població de nodes que hi haurà mai a qualsevol xarxa. Si suposem una distribució uniforme de les IDs del nodes, tindrem que a la meitat de tots els nodes de la xarxa els correspon la taula d'encaminament de la distància més llunyana. Però només en guardarem k d'aquest nodes.

A una distància un bit més propera, hi correspon una quarta part de tots els nodes de la xarxa. Per a un bit més a prop tindrem la vuitena part, etc. Com més properes són les distàncies, menor és el nombre de nodes corresponents que hi ha a la xarxa. Els k que guardem en representaran una proporció més gran; el node en tindrà un millor coneixement.

A mesura que ens anem acostant a distàncies més properes a la ID del mateix node, a cada taula d'encaminament li correspondran menys i menys possibles nodes, fins a arribar un moment en què els k nodes que s'hi poden guardar són suficients per a encabir tots els nodes que hi ha a aquesta distància. El coneixement que es té de la xarxa a aquesta distància és complet. Ara fem un pas enrere: La taula d'encaminament que hi ha només un bit més lluny (distància més gran) de l'anterior és especial. Per tal de garantir un bon coneixement de la xarxa més propera al node en casos en què la distribució no fos tan uniforme com hauria de ser, aquesta llista pot créixer més enllà de k nodes.

Les taules d'encaminament corresponents a distàncies encara més properes, estaran típicament buides. La taula d'encaminament corresponent a la distància zero contindrà la ID del mateix node, i potser de nodes amb la mateixa ID que ell.

Es produeixen IDs duplicades quan l'assignació de IDs es fa mitjançant algorismes pseudoaleatoris sense proporcionar entropia suficient. Els resultats possibles d'aquests algorismes no seran del tot aleatoris doncs només poden produir una varietat de resultats no superior a l'entropia que se'ls proporcioni.

Procés de cerca

Una cerca es fa a partir d'una clau. El node cercador llegeix dins de la seva memòria els k nodes que hi ha més propers a la clau. A cada un d'aquest nodes se'ls demana que retornin els k nodes que ells coneguin que siguin els més propers a la clau. Els resultats rebuts s'apunten a una llista de resultats que es manté ordenada per distància a la clau. Es torna a iterar preguntant el mateix als k nodes de la llista de resultats més propers a la clau, i es continua iterant d'aquesta manera fins que ningú no retorna cap node més proper que els que ja són a la llista de resultats. Quan la cerca s'ha acabat, els primers k nodes de la llista de resultats són el resultat de la cerca.

Com que el coneixement que un node té de la xarxa més propera a ell mateix és més precisa que la que té cap altre node sobre aquest precís tros de la xarxa, els resultats que l'algorisme de cerca va retornant són sempre més propers a la clau que els del pas anterior. Aquest algorisme és extraordinàriament eficient i depèn molt poc de la mida de la xarxa. És a dir, la xarxa pot créixer en mida tant com es vulgui sense que el rendiment se'n vegi afectat. En finalitzar la cerca, la llista de resultats conté els k nodes més propers a la clau buscada que existeixen a tota la xarxa.

Actualització

Analitzant el comportament de les xarxes d'intercanvi de fitxers, s'ha trobat que els nodes que porten més temps connectats a la xarxa són els que amb més probabilitat romandran connectats en el futur.

Kademlia fa ús d'aquest comportament prioritzant que els nodes que s'emmagatzemen a les taules d'encaminament siguin els més "antics" possibles.

L'algorisme en concret és el següent: Cada cop que es coneix un node, s'intenta emmagatzemar en una taula d'encaminament triada en funció de la distància entre aquest node i el mateix node. Si hi ha espai, és a dir si la llista contenia menys de k nodes, s'hi posa. Si la taula d'encaminament és plena, el nou node es posa dins una llista de reemplaçament. Cada taula d'encaminament tindrà una llista de reemplaçament associada. Llavors s'explora la taula d'encaminament començant pel node que fa més temps que no s'ha contactat. S'hi intenta contactar (se li fa ping) i si no contesta se'l substitueix per un dels nodes a la taula de reemplaçament. En altres paraules: només es guarda un node nou si hi ha un d'antic que no respon.

Una taula d'encaminament que no hagi estat usada des de fa una hora, serà automàticament refrescada. Un refresc és una cerca d'una clau aleatòria que sigui dins de l'interval d'IDs corresponent a aquesta taula d'encaminament concreta.

Emmagatzemar i recuperar valors

Un cop es tenen les IDs dels k nodes més propers a una clau, es pot procedir a emmagatzemar-hi un valor. Per motius de redundància, el valor s'emmagatzema per igual a tots els k nodes.

La lectura d'un valor procedeix de la mateixa manera, excepte que quan es contacta amb un node que coneix el valor, el retorna, i això atura la cerca.

Replicar valors

El valor es manté emmagatzemat als k nodes inicials. Al cap d'un temps, alguns d'ells hauran abandonat la xarxa, els nodes que quedin, cada cert temps, refrescaran el valor sobre la xarxa. És a dir, cada node cercarà altre cop quins són els nodes més propers a la clau en aquell moment, i els hi emmagatzemarà el valor. Per tal d'estalviar recursos, no ho farà si ell mateix ha rebut aquesta actualització dins del darrer període.

Cache

Per tal d'alleugerir la càrrega de feina dels nodes que siguen a prop d'una clau molt popular, s'afegeix un mecanisme de cache.

Un node que recupera un valor, s'haurà guardat la llista de resultats amb els nodes cada cop més propers a la clau que haurà vist durant el procés de cerca. Quan ja té el valor, mira quin era el node més proper a la clau que no tenia el valor emmagatzemat i l'hi emmagatzema.

D'aquesta manera els valors més populars queden emmagatzemats a més nodes. Quan un tercer node vulgui recuperar el mateix valor, pot trobar-se durant el procés de cerca amb el node que fa de cache i recuperarà el valor d'allí sense arribar a fer treballar els nodes encara més propers a la clau. La càrrega de feina s'escampa automàticament.

Els nodes de cache oblidaran un valor emmagatzemat (com a cache) un temps després que hi hagi estat emmagatzemat (i independentment de lo molt o poc que hagi estat consultat). El temps que es guardarà és una funció exponencial inversa de la distància d'aquest node a la clau. Això ha de ser així doncs no hi ha cap mecanisme per a actualitzar un valor en una cache.

Bootstrap

Per a entrar a formar part de la xarxa cal que el nou node conegui la informació de contacte (adreça IP) d'un node que sigui dins de la xarxa.

Posarà aquest node dins de la seva memòria i llançarà una cerca agafant la seva pròpia ID com a clau. Això farà que la seva ID quedi emmagatzemada a la memòria de tots els nodes involucrats en aquesta cerca i omplirà les seves pròpies taules d'encaminament amb els nodes contactats durant la cerca, que són els nodes que hi ha entre la seva pròpia ID i la ID del node usat per a entrar. Per a cada una de les taules d'encaminament corresponents a distàncies més llunyanes que el node d'entrada, es llançarà un refresc.

Altres detalls de l'algorisme

Distància

La distància entre dues ID o entre una ID i una clau es defineix com el resultat de calcular un OR exclusiu (XOR) amb els dos valors i interpretar el resultat com un nombre enter en base 2 (numeració binària).

Exemple

Si suposem IDs de 10 bits, com ara 1001010100, anem a calcular la distància entre 1010101010 i 1110100101. L'OR exclusiu dona un bit "1" quan els dos bits comparats són diferents i un bit "0" quan són dos bits iguals. El resultat és 0100001111, que és una distància més gran que 0100001110 i més petita que 0100010000.

Propietats

La distància a Kademlia manté la propietat triangular: Si agafem tres IDs diferents "A", "B" i "C", la distància entre les IDs "A" i "B" és més curta que la suma de les distàncies entre "A" i "C" i entre "C" i "B".

La distància és unidireccional. Així doncs la diferència entre les distàncies "A" a "B" i "A" a "C" no és la distància de "B" a "C".

Ús en xarxes d'intercanvi de fitxers

Les xarxes d'intercanvi de fitxers tenen uns nodes que posseeixen (totalment o parcialment) un fitxer que ofereixen, uns altres nodes que volen descarregar aquest fitxer i encara uns tercers nodes que no hi estan interessats. És necessari que els nodes que volen descarregar un fitxer puguin trobar als nodes que l'ofereixen. Kademlia s'usa per a aquest fi a diverses xarxes d'intercanvi de fitxers.

Històricament eDonkey va ser dels primers a implementar Kademlia, que va anomenar Overnet. Altres clients de la xarxa eDonkey en van copiar el protocol i per fi eMule va crear un protocol diferent (Kad) força millorat. D'aquí la idea va passar a la xarxa bittorrent on Azureus va implementar la primera xarxa trackerless. Després, la resta de clients de bittorrent es van posar d'acord en un protocol comú per a Kademlia.

Els nodes que ofereixen un fitxer usen Kademlia per a publicar la seva pròpia informació de contacte com a fonts d'aquest fitxer. La clau usada és el hash del fitxer. Qui vol descarregar el fitxer haurà primer de conèixer aquest hash per altres mitjans. Llavors consultarà Kademlia per a obtenir la informació de contacte de les fonts.

Les característiques diferenciadores de Kademlia en una xarxa d'intercanvi de fitxers són:

• Hi ha molts valors per a cada clau, per exemple moltes fonts d'un mateix fitxer.
• Es vol que la informació corresponent a un fitxer que ha desaparegut de la xarxa, desaparegui també ràpidament.

En funció d'aquestes característiques, la implementació de Kademlia no tindrà cache ni replicació de valors. En comptes d'això els nodes que publiquen la informació, la republiquen periòdicament per tal de mantenir-la actualitzada. La informació que no es republica desapareix a mesura que els nodes es desconnecten de la xarxa. Com que els valors emmagatzemats per a una determinada clau poden doncs variar d'un node a l'altre, la recuperació dels valors no s'atura al rebre'n el primer, sinó que es llegeixen els valors a tots els k nodes localitzats.

La cerca de fitxers per nom s'implementa dividint el nom del fitxer en les paraules que hi ha. De cada paraula es calcula el seu hash i s'emmagatzema el nom i hash del fitxer com a valor i el hash de la paraula com a clau.

Un usuari que vulgui trobar un fitxer en una xarxa d'intercanvi triarà una paraula que formi part del nom del fitxer, hi afegirà altres criteris de cerca, com ara altres paraules que també han de ser al nom i enviarà aquesta consulta als k nodes que emmagatzemen els valors indexats per aquesta primera paraula clau. El receptor cercarà en el seu magatzem els fitxers que compleixin els criteris de cerca i en retornarà una llista al sol·licitant. L'usuari triarà un dels fitxers rebuts per a ser descarregat. Com que junt amb el nom complet s'haurà rebut el hash del fitxer, s'usarà aquest hash com a clau per a recuperar una llista dels nodes que ofereixen el fitxer.

Enllaços externs

• "Kademlia: A Peer to peer information system Based on the XOR Metric"
• "Kademlia: The optimized Peer network", http://kademlia.scs.cs.nyu.edu/ (mort?, mirror)
• Pàgina d'en Petar Maymounkov
• Yi Qiao i Fabian E. Bustamante USENIX 2006 paper amb una interessant caracterització de Overnet i Gnutella. Arxivat 2010-01-07 a Wayback Machine.
• Especificacions de Kademlia : http://xlattice.sourceforge.net/components/protocol/kademlia/specs.html
• Khashmir: Implementació en Python