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 un DHT y cualquier nodo participante puede recuperar de manera eficiente el valor asociado con una clave determinada. La principal ventaja de un DHT es que se pueden agregar o eliminar nodos con un trabajo mínimo de redistribución de claves. Las claves son identificadores únicos que se asignan a valores particulares , que a su vez pueden ser cualquier cosa, desde direcciones hasta documentos y datos arbitrarios . [1] La responsabilidad de mantener el mapeo 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 un DHT escale a un número extremadamente grande 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 en caché 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 y intercambio de archivos entre pares . Las redes distribuidas notables que utilizan DHT incluyen el rastreador distribuido de BitTorrent , la red Kad , la botnet Storm , la mensajería instantánea Tox , Freenet , el motor de búsqueda YaCy y el sistema de archivos InterPlanetary .
La investigación de DHT fue originalmente motivada, en parte, por 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. [2]
Estos sistemas se diferenciaban en cómo localizaban los datos ofrecidos por sus pares. Napster, el primer sistema de entrega de contenido P2P a gran escala, requería un servidor de índice central: cada nodo, al unirse, enviaría una lista de archivos almacenados localmente al servidor, que realizaría búsquedas y remitiría las consultas a los nodos que contenían el contenido. resultados. Este componente central dejó al sistema vulnerable a ataques y demandas.
Gnutella y redes similares pasaron a un modelo de inundación de consultas ; en esencia, cada búsqueda daría como resultado la transmisión de un mensaje 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 pasaron a un modelo de consulta dinámica que mejoró enormemente la eficiencia. [3]
Freenet está completamente distribuido, pero emplea un enrutamiento heurístico basado en claves en el que cada archivo está asociado con 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 a dicho clúster sin necesidad de visitar muchos pares. [4] 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. Un inconveniente es que, al igual que Freenet, los DHT sólo admiten directamente la búsqueda de coincidencia exacta, en lugar de la búsqueda de palabras clave, aunque el algoritmo de enrutamiento de Freenet se puede generalizar a cualquier tipo de clave en el que se pueda definir una operación de cercanía. [5]
En 2001, cuatro sistemas ( CAN , [6] Chord , [7] Pastry y Tapestry) convirtieron los DHT en un tema de investigación popular. Un proyecto llamado Infraestructura para sistemas de Internet resilientes (Iris) fue financiado con una subvención de 12 millones de dólares de la Fundación Nacional de Ciencias de los Estados Unidos en 2002. [8] Los investigadores incluyeron a Sylvia Ratnasamy , Ion Stoica , Hari Balakrishnan y Scott Shenker . [9] Fuera del mundo académico, la tecnología DHT se ha adoptado como componente de BitTorrent y en proyectos PlanetLab como Coral Content Distribution Network. [10]
Los DHT característicamente enfatizan las siguientes propiedades:
Una técnica clave utilizada para lograr estos objetivos es que cualquier nodo necesita coordinarse solo con 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 un número limitado Es necesario realizar una gran cantidad de trabajo para cada cambio de membresía.
Algunos diseños DHT buscan ser seguros contra participantes maliciosos [12] y permitir que los participantes permanezcan en el anonimato , aunque esto es menos común que en muchos otros sistemas peer-to-peer (especialmente el intercambio de archivos ); ver P2P anónimo .
La estructura de una DHT se puede descomponer en varios componentes principales. [13] [14] La base es un espacio de claves abstracto , como el conjunto de cadenas de 160 bits . Un esquema de partición de espacios de claves divide la propiedad de este espacio de claves entre los nodos participantes. Luego, una red superpuesta conecta los nodos, permitiéndoles encontrar al propietario de cualquier clave determinada 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 realizarse 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 determinados en DHT, se genera el hash SHA-1 del nombre de archivo , lo que produce una clave k de 160 bits , y se envía un mensaje put ( k, datos ) a cualquier nodo que participe en DHT. El mensaje se reenvía de nodo a nodo a través de la red superpuesta hasta que llega al nodo único responsable de la clave k según lo especificado por la partición del espacio de claves. Luego, ese nodo almacena la clave y los datos. Cualquier otro cliente puede luego recuperar el contenido del archivo aplicando nuevamente el hash del nombre del archivo para producir k y pidiendo a cualquier nodo DHT que encuentre los datos asociados con k con un mensaje get ( k ) . El mensaje será nuevamente enrutado a través de la superposición al nodo responsable de k , que responderá con los datos almacenados .
La partición del espacio de claves y los componentes de la red superpuesta se describen a continuación con el objetivo de capturar las ideas principales comunes a la mayoría de los DHT; Muchos diseños difieren en los detalles.
La mayoría de los 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 la tabla hash distribuida.
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 propiedad de los nodos con ID adyacentes y no afecta a todos los demás nodos. Compare esto con una tabla hash tradicional en la que la adición o eliminación de un depósito hace que se reasigne casi todo el espacio de claves. Dado que cualquier cambio de propiedad generalmente corresponde a un movimiento intensivo de ancho de banda de objetos almacenados en el DHT de un nodo a otro, es necesario minimizar dicha reorganización para soportar de manera eficiente altas tasas de abandono (llegada y falla del nodo).
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 única clave llamada identificador (ID). Un nodo con ID posee todas las claves cuyo ID es el más cercano, medido según .
Por ejemplo, Chord DHT utiliza hash consistente, que trata los nodos como puntos en un círculo y es la distancia que recorre el círculo en el sentido de las agujas del reloj desde hasta . Por tanto, el espacio de claves circular se divide en segmentos contiguos cuyos puntos finales son los identificadores de nodo. Si y son dos ID adyacentes, con una distancia más corta en el sentido de las agujas del reloj desde hasta , entonces el nodo con ID posee todas las claves que se encuentran entre y .
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 1 , S 2 , ..., S n } , uno para cada servidor. Dada alguna clave k , un cliente calcula n pesos hash w 1 = h ( S 1 , k ), w 2 = h ( S 2 , 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 cuyo peso hash es mayor que el peso hash de cualquier otro nodo para esa clave.
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, a diferencia del uso de hash consistente, no hay más seguridad de que las claves (y por lo tanto la carga) se distribuyan de manera uniforme y aleatoria en el espacio de claves y los pares participantes. Los protocolos DHT como Self-Chord y Oscar [15] abordan estos problemas. Self-Chord desacopla las claves de objetos de las identificaciones de pares y clasifica las claves a lo largo del anillo con un enfoque estadístico basado en el paradigma de inteligencia de enjambre . [16] La clasificació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. [17] 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 usando el siguiente algoritmo codicioso (que no es necesariamente óptimo globalmente): en cada paso, reenvía el mensaje al vecino cuyo ID sea más cercano a 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 claves .
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 la 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. Eso sí, al tener recorridos más cortos se requiere mayor titulación máxima . Algunas opciones comunes para el grado máximo y la longitud de la ruta son las siguientes, donde n es el número de nodos en el DHT, usando la notación O grande :
La elección más común, grado/longitud de ruta, no es óptima en términos de equilibrio entre grado/longitud de ruta, pero dichas topologías generalmente permiten una mayor flexibilidad en la elección de vecinos. Muchos DHT utilizan esa flexibilidad para elegir vecinos que estén cerca en términos de latencia en la red física subyacente. En general, todos los DHT construyen topologías de redes navegables de mundo pequeño, que compensan la longitud de la ruta con el grado de la red. [18]
La longitud máxima de la ruta está estrechamente relacionada con el diámetro : el número máximo de saltos en cualquier camino más corto 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 los DHT están limitados por la compensación grado/diámetro [19] que es fundamental en la teoría de grafos . La longitud de la ruta puede ser mayor que el diámetro, ya que es posible que el algoritmo de enrutamiento codicioso no encuentre los caminos más cortos. [20]
Además 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 un DHT. [21] Estos algoritmos son utilizados por aplicaciones para realizar superposiciones de multidifusión , consultas de rango o para recopilar estadísticas. Dos sistemas que se basan en este enfoque son Structella, [22] que implementa inundaciones y paseos aleatorios en una superposición de Pastry, y DQ-DHT, que implementa un algoritmo de búsqueda de consulta dinámica en una red Chord. [23]
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. [ impreciso ]
Son factibles sistemas abiertos para el almacenamiento de datos distribuidos que sean robustos contra atacantes hostiles masivos. [24]
Un sistema DHT que está cuidadosamente diseñado para tener tolerancia a fallas bizantinas puede defenderse contra una debilidad de seguridad, conocida como ataque Sybil , que afecta a la mayoría de los diseños DHT actuales. [25] [26] Whanau es un DHT diseñado para ser resistente a los ataques de Sybil. [27]
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. [28] 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 fue escrito en coautoría con el matemático Jonathan Kelner. [29] Maymounkov ha emprendido ahora un esfuerzo integral de implementación 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 necesaria ]
Las diferencias más notables encontradas en casos prácticos de implementaciones DHT incluyen al menos las siguientes:
Un valor puede ser una dirección, un documento o un elemento de datos arbitrario.
{{cite journal}}: Citar diario requiere |journal=( ayuda ){{cite book}}: |website=ignorado ( ayuda ){{cite journal}}: Citar diario requiere |journal=( ayuda ){{cite journal}}: Citar diario requiere |journal=( ayuda )