Tabla hash distribuida

Una tabla hash distribuida ( DHT ) es un sistema distribuido que proporciona un servicio de búsqueda similar a una tabla hash . Los pares clave-valor se almacenan en una DHT, y cualquier nodo participante puede recuperar de manera eficiente el valor asociado con una clave dada. La principal ventaja de una DHT es que se pueden agregar o eliminar nodos con un trabajo mínimo en torno a la redistribución de claves. ^[1] Las claves son identificadores únicos que se asignan a valores particulares , que a su vez pueden ser cualquier cosa, desde direcciones hasta documentos o datos arbitrarios . ^[2] La responsabilidad de mantener la asignación de claves a valores se distribuye entre los nodos, de tal manera que un cambio en el conjunto de participantes causa una cantidad mínima de interrupción. Esto permite que una DHT escale a cantidades extremadamente grandes de nodos y maneje llegadas, salidas y fallas continuas de nodos.

Los DHT forman una infraestructura que se puede utilizar para crear servicios más complejos, como anycast , almacenamiento web cooperativo , sistemas de archivos distribuidos , servicios de nombres de dominio , mensajería instantánea , multidifusión y también sistemas de distribución de contenido e intercambio de archivos entre pares . Entre las redes distribuidas más destacadas que utilizan DHT se incluyen el rastreador distribuido de BitTorrent , la red Kad , la botnet Storm , el mensajero instantáneo Tox , Freenet , el motor de búsqueda YaCy y el sistema de archivos interplanetario .

La investigación sobre DHT estuvo motivada originalmente, en parte, por los sistemas peer-to-peer (P2P) como Freenet , Gnutella , BitTorrent y Napster , que aprovechaban los recursos distribuidos a través de Internet para proporcionar una única aplicación útil. En particular, aprovecharon el aumento del ancho de banda y la capacidad del disco duro para proporcionar un servicio de intercambio de archivos. ^[3]

Estos sistemas se diferenciaban en la forma en que localizaban los datos ofrecidos por sus pares. Napster, el primer sistema de distribución de contenido P2P a gran escala, requería un servidor de índice central: cada nodo, al unirse, enviaba una lista de archivos almacenados localmente al servidor, que realizaba búsquedas y remitía las consultas a los nodos que contenían los resultados. Este componente central dejaba al sistema vulnerable a ataques y demandas judiciales.

Gnutella y redes similares adoptaron un modelo de inundación de consultas : en esencia, cada búsqueda daría como resultado un mensaje que se transmitiría a todas las máquinas de la red. Si bien evitaba un único punto de falla , este método era significativamente menos eficiente que Napster. Las versiones posteriores de los clientes de Gnutella adoptaron un modelo de consultas dinámicas que mejoró enormemente la eficiencia. ^[4]

Freenet es un servicio totalmente distribuido, pero emplea un enrutamiento heurístico basado en claves en el que cada archivo está asociado a una clave y los archivos con claves similares tienden a agruparse en un conjunto similar de nodos. Es probable que las consultas se enruten a través de la red hacia dicho grupo sin necesidad de visitar muchos pares. ^[5] Sin embargo, Freenet no garantiza que se encuentren los datos.

Las tablas hash distribuidas utilizan un enrutamiento basado en claves más estructurado para lograr tanto la descentralización de Freenet y Gnutella como la eficiencia y los resultados garantizados de Napster. Una desventaja es que, al igual que Freenet, las DHT solo admiten directamente la búsqueda de coincidencia exacta, en lugar de la búsqueda por palabras clave, aunque el algoritmo de enrutamiento de Freenet se puede generalizar a cualquier tipo de clave donde se pueda definir una operación de proximidad. ^[6]

En 2001, cuatro sistemas ( CAN , ^[7] Chord , ^[8] Pastry y Tapestry) hicieron que las DHT se convirtieran en un tema de investigación popular. En 2002, la Fundación Nacional de Ciencias de Estados Unidos financió un proyecto llamado Infraestructura para sistemas de Internet resilientes (Iris, por sus siglas en inglés) con una subvención de 12 millones de dólares. ^[9] Entre los investigadores se encontraban Sylvia Ratnasamy , Ion Stoica , Hari Balakrishnan y Scott Shenker . ^[10] Fuera del ámbito académico, la tecnología DHT se ha adoptado como un componente de BitTorrent y en proyectos PlanetLab como la Red de distribución de contenido Coral. ^[11]

Los DHT se caracterizan por destacar las siguientes propiedades:

• Autonomía y descentralización : Los nodos forman colectivamente el sistema sin ninguna coordinación central.
• Tolerancia a fallos : el sistema debe ser confiable (en cierto sentido) incluso con nodos que se unen, abandonan y fallan continuamente. ^[12]
• Escalabilidad : el sistema debe funcionar de manera eficiente incluso con miles o millones de nodos.

Una técnica clave utilizada para lograr estos objetivos es que cada nodo debe coordinarse con solo unos pocos otros nodos en el sistema ( más comúnmente, O (log n ) de los n participantes (ver más abajo) , de modo que solo se necesita realizar una cantidad limitada de trabajo para cada cambio en la membresía.

Algunos diseños de DHT buscan ser seguros contra participantes maliciosos ^[13] y permitir que los participantes permanezcan anónimos , aunque esto es menos común que en muchos otros sistemas peer to peer (especialmente de intercambio de archivos ); consulte P2P anónimo .

La estructura de un DHT se puede descomponer en varios componentes principales. ^{[14] [15]} La base es un espacio de claves abstracto , como el conjunto de cadenas de 160 bits . Un esquema de partición del espacio de claves divide la propiedad de este espacio de claves entre los nodos participantes. Luego, una red superpuesta conecta los nodos, lo que les permite encontrar al propietario de cualquier clave dada en el espacio de claves.

Una vez que estos componentes están en su lugar, un uso típico del DHT para almacenamiento y recuperación podría proceder de la siguiente manera. Supongamos que el espacio de claves es el conjunto de cadenas de 160 bits. Para indexar un archivo con un nombre de archivo y datos dados en el DHT, se genera el hash SHA-1 de nombre de archivo , lo que produce una clave de 160 bits k , y se envía un mensaje put ( k, datos ) a cualquier nodo que participe en el DHT. El mensaje se reenvía de un nodo a otro a través de la red superpuesta hasta que llega al único nodo responsable de la clave k según lo especificado por la partición del espacio de claves. Ese nodo luego almacena la clave y los datos. Cualquier otro cliente puede entonces recuperar el contenido del archivo al volver a aplicar el hash a nombre de archivo para producir k y pedirle a cualquier nodo DHT que encuentre los datos asociados con k con un mensaje get ( k ) . El mensaje se enrutará nuevamente a través de la superposición al nodo responsable de k , que responderá con los datos almacenados .

A continuación se describen los componentes de partición del espacio de claves y de red superpuesta con el objetivo de capturar las ideas principales comunes a la mayoría de las DHT; muchos diseños difieren en los detalles.

La mayoría de las DHT utilizan alguna variante de hash consistente o hash de encuentro para asignar claves a nodos. Los dos algoritmos parecen haber sido ideados de forma independiente y simultánea para resolver el problema de las tablas hash distribuidas.

Tanto el hash consistente como el hash de encuentro tienen la propiedad esencial de que la eliminación o adición de un nodo cambia solo el conjunto de claves que poseen los nodos con identificadores adyacentes y deja a todos los demás nodos intactos. Comparemos esto con una tabla hash tradicional en la que la adición o eliminación de un contenedor hace que se reasigne casi todo el espacio de claves. Dado que cualquier cambio de propiedad generalmente corresponde a un movimiento de objetos almacenados en la DHT de un nodo a otro que consume mucho ancho de banda, es necesario minimizar dicha reorganización para soportar de manera eficiente altas tasas de abandono (llegada y falla de nodos).

El hash consistente emplea una función que define una noción abstracta de la distancia entre las claves y , que no está relacionada con la distancia geográfica o la latencia de la red . A cada nodo se le asigna una clave única llamada su identificador (ID). Un nodo con ID posee todas las claves para las cuales es el ID más cercano, medido de acuerdo con .${\ Displaystyle \ delta (k_ {1}, k_ {2})}$$estilo de visualización k_{1}$$estilo de visualización k_{2}$$Estilo de visualización i_{x}}$$estilo de visualización k_ {m}}$$Estilo de visualización i_{x}}$${\displaystyle \delta(k_{m},i_{x})}$

Por ejemplo, la DHT de acordes utiliza un algoritmo hash consistente, que trata a los nodos como puntos de un círculo y es la distancia que recorre el círculo en el sentido de las agujas del reloj desde hasta . Por lo tanto, el espacio de claves circular se divide en segmentos contiguos cuyos puntos finales son los identificadores de nodo. Si y son dos identificadores adyacentes, con una distancia en el sentido de las agujas del reloj más corta desde hasta , entonces el nodo con el identificador posee todas las claves que se encuentran entre y .${\ Displaystyle \ delta (k_ {1}, k_ {2})}$$estilo de visualización k_{1}$$estilo de visualización k_{2}$${\displaystyle i_{1}}$${\displaystyle i_{2}}$${\displaystyle i_{1}}$${\displaystyle i_{2}}$${\displaystyle i_{2}}$${\displaystyle i_{1}}$${\displaystyle i_{2}}$

En el hash de encuentro, también llamado hash de peso aleatorio más alto (HRW), todos los clientes usan la misma función hash (elegida de antemano) para asociar una clave a uno de los n servidores disponibles. Cada cliente tiene la misma lista de identificadores { S ₁ , S ₂ , ..., S _n } , uno para cada servidor. Dada una clave k , un cliente calcula n pesos hash w ₁ = h ( S ₁ , k ), w ₂ = h ( S ₂ , k ), ..., w _n = h ( S _n , k ) . El cliente asocia esa clave con el servidor correspondiente al peso hash más alto para esa clave. Un servidor con ID posee todas las claves para las cuales el peso hash es mayor que el peso hash de cualquier otro nodo para esa clave.${\estilo de visualización h()}$$Estilo de visualización S_{x}$$estilo de visualización k_ {m}}$${\displaystyle h(S_{x},k_{m})}$

El hash que preserva la localidad garantiza que se asignen claves similares a objetos similares. Esto puede permitir una ejecución más eficiente de consultas de rango; sin embargo, en contraste con el uso de hash consistente, no hay más garantía de que las claves (y, por lo tanto, la carga) se distribuyan de manera aleatoria uniforme sobre el espacio de claves y los pares participantes. Los protocolos DHT como Self-Chord y Oscar ^[16] abordan estos problemas. Self-Chord desacopla las claves de los objetos de las identificaciones de los pares y ordena las claves a lo largo del anillo con un enfoque estadístico basado en el paradigma de inteligencia de enjambre . ^[17] La ​​ordenación garantiza que los nodos vecinos almacenen claves similares y que los procedimientos de descubrimiento, incluidas las consultas de rango , se puedan realizar en tiempo logarítmico. Oscar construye una red navegable de mundo pequeño basada en un muestreo de caminata aleatoria que también garantiza un tiempo de búsqueda logarítmico.

Cada nodo mantiene un conjunto de enlaces con otros nodos (sus vecinos o tabla de enrutamiento ). Juntos, estos enlaces forman la red superpuesta. ^[18] Un nodo elige a sus vecinos de acuerdo con una determinada estructura, llamada topología de la red .

Todas las topologías DHT comparten alguna variante de la propiedad más esencial: para cualquier clave k , cada nodo tiene un ID de nodo que posee k o tiene un enlace a un nodo cuyo ID de nodo está más cerca de k , en términos de la distancia del espacio de claves definida anteriormente. Entonces es fácil enrutar un mensaje al propietario de cualquier clave k utilizando el siguiente algoritmo voraz (que no es necesariamente globalmente óptimo): en cada paso, reenviar el mensaje al vecino cuyo ID esté más cerca de k . Cuando no existe tal vecino, entonces debemos haber llegado al nodo más cercano, que es el propietario de k como se definió anteriormente. Este estilo de enrutamiento a veces se denomina enrutamiento basado en clave .

Más allá de la corrección básica del enrutamiento, dos restricciones importantes en la topología son garantizar que el número máximo de saltos en cualquier ruta (longitud de ruta) sea bajo, de modo que las solicitudes se completen rápidamente; y que el número máximo de vecinos de cualquier nodo ( grado máximo de nodo ) sea bajo, de modo que la sobrecarga de mantenimiento no sea excesiva. Por supuesto, tener rutas más cortas requiere un grado máximo más alto . Algunas opciones comunes para el grado máximo y la longitud de ruta son las siguientes, donde n es el número de nodos en la DHT, utilizando la notación Big O :

Grado máx.	Longitud máxima de ruta	Utilizado en	Nota
${\estilo de visualización O(1)}$	${\displaystyle O(n)}$		Peores longitudes de búsqueda, con tiempos de búsqueda probablemente mucho más lentos
${\estilo de visualización O(1)}$	${\displaystyle O(\log n)}$	Koorde (con grado constante)	Es más complejo de implementar, pero se puede encontrar un tiempo de búsqueda aceptable con un número fijo de conexiones
${\displaystyle O(\log n)}$	${\displaystyle O(\log n)}$	Tapiz de pastelería Chord Kademlia	La más común, pero no la óptima (grado/longitud de ruta). Chord es la versión más básica, y Kademlia parece ser la variante optimizada más popular (debería haber mejorado la búsqueda de promedios)
${\displaystyle O(\log n)}$	${\displaystyle O(\log n/\log(\log n))}$	Koorde (con búsqueda óptima)	Más complejo de implementar, pero las búsquedas pueden ser más rápidas (tienen un límite inferior en el peor de los casos)
${\displaystyle O({\sqrt {n}})}$	${\estilo de visualización O(1)}$		Peores necesidades de almacenamiento local, con mucha comunicación después de que cualquier nodo se conecta o desconecta

La opción más común, grado/longitud de ruta, no es óptima en términos de equilibrio entre grado/longitud de ruta, pero estas topologías suelen permitir una mayor flexibilidad en la elección de vecinos. Muchas DHT utilizan esa flexibilidad para elegir vecinos que están cerca en términos de latencia en la red física subyacente. En general, todas las DHT construyen topologías de red navegables de mundo pequeño, que equilibran la longitud de ruta frente al grado de red. ^[19]${\displaystyle O(\log n)}$

La longitud máxima de la ruta está estrechamente relacionada con el diámetro : el número máximo de saltos en cualquier ruta más corta entre nodos. Claramente, la longitud de la ruta en el peor de los casos de la red es al menos tan grande como su diámetro, por lo que las DHT están limitadas por el equilibrio entre grado y diámetro ^[20] que es fundamental en la teoría de grafos . La longitud de la ruta puede ser mayor que el diámetro, ya que el algoritmo de enrutamiento codicioso puede no encontrar las rutas más cortas. ^[21]

Aparte del enrutamiento, existen muchos algoritmos que explotan la estructura de la red superpuesta para enviar un mensaje a todos los nodos, o a un subconjunto de nodos, en una DHT. ^[22] Estos algoritmos son utilizados por aplicaciones para realizar multidifusión superpuesta , consultas de rango o para recopilar estadísticas. Dos sistemas que se basan en este enfoque son Structella, ^[23] que implementa inundaciones y recorridos aleatorios en una superposición Pastry, y DQ-DHT, que implementa un algoritmo de búsqueda de consultas dinámicas sobre una red Chord. ^[24]

Debido a la descentralización, la tolerancia a fallas y la escalabilidad de los DHT, son inherentemente más resistentes contra un atacante hostil que un sistema centralizado. ^{[ vago ]}

Son factibles sistemas abiertos de almacenamiento de datos distribuidos que sean robustos frente a ataques hostiles masivos. ^[25]

Un sistema DHT que está cuidadosamente diseñado para tener tolerancia a fallas bizantinas puede defenderse contra una debilidad de seguridad, conocida como el ataque Sybil , que afecta a la mayoría de los diseños DHT actuales. ^{[26] [27]} Whanau es un DHT diseñado para ser resistente a los ataques Sybil. ^[28]

Petar Maymounkov, uno de los autores originales de Kademlia , ha propuesto una forma de sortear la debilidad del ataque Sybil incorporando relaciones de confianza social en el diseño del sistema. ^[29] El nuevo sistema, cuyo nombre en código es Tonika o también conocido por su nombre de dominio como 5ttt, se basa en un diseño de algoritmo conocido como "enrutamiento eléctrico" y coescrito con el matemático Jonathan Kelner. ^[30] Maymounkov ha llevado a cabo un esfuerzo de implementación integral de este nuevo sistema. Sin embargo, la investigación sobre defensas efectivas contra los ataques Sybil generalmente se considera una cuestión abierta, y cada año se propone una amplia variedad de defensas potenciales en las principales conferencias de investigación de seguridad. ^{[ cita requerida ]}

Las diferencias más notables encontradas en casos prácticos de implementaciones de DHT incluyen al menos las siguientes:

• El espacio de direcciones es un parámetro de DHT. Varias DHT del mundo real utilizan un espacio de clave de 128 o 160 bits.
• Algunas DHT del mundo real utilizan funciones hash distintas de SHA-1 .
• En el mundo real, la clave k podría ser un hash del contenido de un archivo en lugar de un hash del nombre de un archivo para proporcionar almacenamiento direccionable por contenido , de modo que el cambio de nombre del archivo no impida que los usuarios lo encuentren.
• Algunas DHT también pueden publicar objetos de diferentes tipos. Por ejemplo, la clave k podría ser el ID del nodo y los datos asociados podrían describir cómo contactar con este nodo. Esto permite la publicación de información de presencia y se utiliza a menudo en aplicaciones de mensajería instantánea, etc. En el caso más simple, el ID es simplemente un número aleatorio que se utiliza directamente como clave k (por lo que en una DHT de 160 bits, el ID será un número de 160 bits, generalmente elegido al azar). En algunas DHT, la publicación de los ID de los nodos también se utiliza para optimizar las operaciones de la DHT.
• Se puede agregar redundancia para mejorar la confiabilidad. El par de claves (k, datos) se puede almacenar en más de un nodo correspondiente a la clave. Por lo general, en lugar de seleccionar solo un nodo, los algoritmos DHT del mundo real seleccionan i nodos adecuados, donde i es un parámetro específico de la implementación del DHT. En algunos diseños de DHT, los nodos acuerdan manejar un cierto rango de espacio de claves, cuyo tamaño se puede elegir dinámicamente, en lugar de estar codificado de forma rígida.
• Algunas DHT avanzadas como Kademlia realizan búsquedas iterativas a través de la DHT primero para seleccionar un conjunto de nodos adecuados y enviar mensajes put(k, data) solo a esos nodos, reduciendo así drásticamente el tráfico inútil, ya que los mensajes publicados solo se envían a los nodos que parecen adecuados para almacenar la clave k ; y las búsquedas iterativas cubren solo un pequeño conjunto de nodos en lugar de todo el DHT, lo que reduce el reenvío inútil. En tales DHT, el reenvío de mensajes put(k, data) solo puede ocurrir como parte de un algoritmo de autocuración: si un nodo de destino recibe un mensaje put(k, data) , pero cree que k está fuera de su rango manejado y se conoce un nodo más cercano (en términos de espacio de claves DHT), el mensaje se reenvía a ese nodo. De lo contrario, los datos se indexan localmente. Esto conduce a un comportamiento de DHT de cierta manera autoequilibrado. Por supuesto, un algoritmo de este tipo requiere que los nodos publiquen sus datos de presencia en la DHT para que se puedan realizar las búsquedas iterativas.
• Dado que en la mayoría de las máquinas enviar mensajes es mucho más costoso que acceder a la tabla hash local, tiene sentido agrupar muchos mensajes relacionados con un nodo en particular en un solo lote. Suponiendo que cada nodo tiene un lote local que consta de b operaciones como máximo, el procedimiento de agrupación es el siguiente. Cada nodo primero ordena su lote local por el identificador del nodo responsable de la operación. Usando la ordenación por cubos , esto se puede hacer en O(b + n) , donde n es el número de nodos en la DHT. Cuando hay múltiples operaciones que abordan la misma clave dentro de un lote, el lote se condensa antes de enviarse. Por ejemplo, múltiples búsquedas de la misma clave se pueden reducir a una o múltiples incrementos se pueden reducir a una sola operación de suma. Esta reducción se puede implementar con la ayuda de una tabla hash local temporal. Finalmente, las operaciones se envían a los nodos respectivos. ^[31]

• Casandra apache
• Superposición de BATON
• DHT de línea principal : DHT estándar utilizado por BitTorrent (basado en Kademlia proporcionado por Khashmir) ^[32]
• Red direccionable por contenido (CAN)
• Acorde
• Coro
• Kademlia
• Pasteles
• Cuadrícula P
• Riak
• Base de datos Scylla
• Tapiz
• TomP2P
• Voldemort

• BTDigg : motor de búsqueda BitTorrent DHT
• Codeen : almacenamiento en caché web
• Freenet : una red anónima resistente a la censura
• GlusterFS : un sistema de archivos distribuido utilizado para la virtualización del almacenamiento
• GNUnet : red de distribución similar a Freenet que incluye una implementación de DHT
• I2P : una red peer to peer anónima de código abierto
• I2P-Bote : correo electrónico anónimo seguro y sin servidor
• IPFS : un protocolo de distribución de hipermedia punto a punto direccionable por contenido
• JXTA : plataforma P2P de código abierto
• LBRY : un protocolo de intercambio de contenido basado en blockchain que utiliza un sistema DHT influenciado por Kademlia para la distribución de contenido.
• Oracle Coherence : una cuadrícula de datos en memoria construida sobre una implementación de Java DHT
• Perfect Dark : una aplicación japonesa para compartir archivos entre pares
• Retroshare : una red de amigos ^[33]
• Jami : una plataforma de comunicación de voz, video y chat que preserva la privacidad, basada en un DHT similar a Kademlia
• Tox : un sistema de mensajería instantánea diseñado para funcionar como reemplazo de Skype
• Twister : una plataforma de microblogging peer to peer
• YaCy : un motor de búsqueda distribuido

• Couchbase Server : un sistema de almacenamiento de objetos distribuido, persistente, replicado y en clúster compatible con el protocolo memcached.
• Memcached : un sistema de almacenamiento en caché de objetos de memoria distribuida y de alto rendimiento.
• Árbol hash de prefijo : consultas sofisticadas sobre DHT.
• Árbol de Merkle : árbol que tiene cada nodo que no es hoja etiquetado con el hash de las etiquetas de sus nodos hijos.
• La mayoría de los almacenes de datos distribuidos emplean algún tipo de DHT para la búsqueda.
• Los gráficos de salto son una estructura de datos eficiente para implementar DHT.

• Tablas hash distribuidas, parte 1 por Brandon Wiley.
• Tablas hash distribuidas enlazan con la página de Carles Pairot sobre investigación en DHT y P2P
• Instantáneas de kademlia.scs.cs.nyu.edu en Archive.org
• Eng-Keong Lua; Crowcroft, Jon; Pias, Marcelo; Sharma, Ravi; Lim, Steve (2005). "Encuesta IEEE sobre esquemas de redes superpuestas". CiteSeerX  10.1.1.111.4197 :cubriendo redes superpuestas descentralizadas estructuradas y no estructuradas, incluidas DHT (Chord, Pastry, Tapestry y otras).
• Medición de DHT en la línea principal en el Departamento de Ciencias de la Computación, Universidad de Helsinki, Finlandia.