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 un DHT, y cualquier nodo participante puede recuperar de manera eficiente el valor asociado con una clave dada. La principal ventaja de un DHT es que los nodos se pueden agregar o eliminar con un trabajo mínimo en torno a la 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, documentos o datos arbitrarios. 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 cause una cantidad mínima de interrupción. Esto permite que un DHT se amplíe 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 distribución de contenido y uso compartido de archivos entre pares. sistemas Las redes distribuidas notables que utilizan DHT 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. Holochain es un proyecto que tiene como objetivo proporcionar alojamiento DHT para computadoras domésticas.

Tablas de hadas distribuidas

Historia

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

Estos sistemas diferían en la forma en que ubicaban 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, enviaba una lista de archivos almacenados localmente al servidor, que realizaba búsquedas y remití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 demás 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.

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. Sin embargo, Freenet no garantiza que se encontrarán 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 solo 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 proximidad.

En 2001, cuatro sistemas (CAN, Chord, Pastry y Tapestry) convirtieron a las DHT en un tema de investigación popular. Un proyecto llamado Infraestructura para Sistemas de Internet Resilientes (Iris) fue financiado por una subvención de $ 12 millones de la Fundación Nacional de Ciencias de los Estados Unidos en 2002. Los investigadores incluyeron a Sylvia Ratnasamy, Ion Stoica, Hari Balakrishnan y Scott Shenker. Fuera de la academia, la tecnología DHT se ha adoptado como un componente de BitTorrent y en Coral Content Distribution Network.

Propiedades

Las DHT destacan de forma característica las siguientes propiedades:

• Autonomía y descentralización: Los nodos forman colectivamente el sistema sin ninguna coordinación central.
• Tolerancia por defecto: El sistema debe ser confiable (en algún sentido) incluso con los nodos que se unen continuamente, saliendo y fracasando.
• Escalabilidad: El sistema debe funcionar eficientemente incluso con miles o millones de nodos.

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

Algunos diseños de DHT buscan ser seguros contra participantes maliciosos y permitir que los participantes permanezcan en el anonimato, aunque esto es menos común que en muchos otros sistemas peer-to-peer (especialmente para compartir archivos); ver P2P anónimo.

Estructura

La estructura de una DHT se puede descomponer en varios componentes principales. 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, 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 nombre de archivo y datos en el DHT, se genera el hash SHA-1 de nombre de archivo, produciendo una clave de 160 bits k, y un mensaje put(k, data) es enviado a cualquier nodo que participe en el DHT. El mensaje se reenvía de nodo a nodo a través de la red superpuesta hasta que llega al único nodo responsable de la clave k según lo especificado por el espacio de claves fraccionamiento. Ese nodo luego almacena la clave y los datos. Cualquier otro cliente puede recuperar el contenido del archivo volviendo a codificar filename para producir k y solicitando 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 el datos.

Los componentes de la red superpuesta y de partición del espacio de claves 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.

Particionamiento de espacios de claves

La mayoría de los DHT utilizan alguna variante de hash coherente o hash de encuentro para asignar claves a nodos. Los dos algoritmos parecen haber sido diseñados de forma independiente y simultánea para resolver el problema de la tabla hash distribuida.

Tanto el hash coherente 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 pertenecen a los nodos con ID adyacentes y no afecta a los demás nodos. Compare esto con una tabla hash tradicional en la que la adición o eliminación de un cubo hace que se reasigne casi todo el espacio de claves. Dado que cualquier cambio en la propiedad generalmente corresponde al movimiento intensivo de ancho de banda de los objetos almacenados en el DHT de un nodo a otro, se requiere minimizar dicha reorganización para soportar de manera eficiente las altas tasas de abandono (llegada y falla del nodo).

Hashing consistente

Hashing consistente emplea una función δ δ ()k1,k2){displaystyle delta (k_{1},k_{2}} que define una noción abstracta de la distancia entre las teclas k1{displaystyle K_{1} y k2{displaystyle K_{2}, que no está relacionado con la distancia geográfica o la latencia de la red. Cada nodo se asigna una sola llave llamada su Identificador (ID). Un nodo con ID ix{displaystyle i_{x} posee todas las llaves km{displaystyle K_{m} para la cual ix{displaystyle i_{x} es el ID más cercano, medido según δ δ ()km,ix){displaystyle delta (k_{m},i_{x}}.

Por ejemplo, el Chord DHT utiliza el escote consistente, que trata los nodos como puntos en un círculo, y δ δ ()k1,k2){displaystyle delta (k_{1},k_{2}} es la distancia que viaja en el reloj alrededor del círculo de k1{displaystyle K_{1} a k2{displaystyle K_{2}. Así, el espacio clave circular se divide en segmentos contiguos cuyos puntos finales son los identificadores del nodo. Si i1{displaystyle I_{1} y i2{displaystyle I_{2} son dos IDs adyacentes, con una distancia más corta del reloj i1{displaystyle I_{1} a i2{displaystyle I_{2}, entonces el nodo con ID i2{displaystyle I_{2} posee todas las llaves que caen entre i1{displaystyle I_{1} y i2{displaystyle I_{2}.

Hashing de encuentro

En rendezvous hashing, también llamado mayor peso aleatorio (HRW) hashing, todos los clientes utilizan la misma función hash h()){displaystyle h()} (elegido antes del tiempo) 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 la llave k, un cliente computes n pesos hah 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 de hash más alto para esa clave. Un servidor con ID Sx{displaystyle S_{x} posee todas las llaves km{displaystyle K_{m} para el cual el peso hah h()Sx,km){displaystyle h(S_{x},k_{m}} es más alto que el peso precipitado de cualquier otro nodo para esa llave.

Hashing que conserva la localidad

El hashing que conserva la localidad garantiza que se asignen claves similares a objetos similares. Esto puede permitir una ejecución más eficiente de las consultas de rango; sin embargo, en contraste con el uso de hashing 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 abordan estos problemas. Self-Chord desacopla las claves de objeto de las ID de pares y ordena las claves a lo largo del anillo con un enfoque estadístico basado en el paradigma de inteligencia de enjambre. 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 asegura un tiempo de búsqueda logarítmico.

Red superpuesta

Cada nodo mantiene un conjunto de enlaces a otros nodos (sus vecinos o tabla de enrutamiento). Juntos, estos enlaces forman la red superpuesta. Un nodo elige a sus vecinos de acuerdo con una determinada estructura, denominada 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 teclas definida anteriormente. Entonces es fácil enrutar un mensaje al propietario de cualquier clave k utilizando el siguiente algoritmo codicioso (que no es necesariamente óptimo a nivel mundial): en cada paso, reenvía el mensaje al vecino cuyo ID sea más cercano a k. Cuando no existe tal vecino, 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 la cantidad máxima de saltos en cualquier ruta (longitud de la ruta) sea baja, 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 mayor grado máximo. Algunas opciones comunes para el grado máximo y la longitud de la ruta son las siguientes, donde n es la cantidad de nodos en el DHT, usando Big O notación:

Max.	Longitud máxima de la ruta	Usado en	Nota
O()1){displaystyle O(1)}	O()n){displaystyle O(n)}		Longitudes de búsqueda peor, con probables búsquedas mucho más lentas veces
O()1){displaystyle O(1)}	O()log⁡ ⁡ n){displaystyle O(log n)}	Koorde (con un grado constante)	Más complejo para implementar, pero el tiempo de búsqueda aceptable se puede encontrar con un número fijo de conexiones
O()log⁡ ⁡ n){displaystyle O(log n)}	O()log⁡ ⁡ n){displaystyle O(log n)}	Chord Kademlia Pastelería Tapiz	Más común, pero no óptima (longitud de grado/ruto). Chord es la versión más básica, con Kademlia parecer la variante optimizada más popular (debería haber mejorado la búsqueda promedio)
O()log⁡ ⁡ n){displaystyle O(log n)}	O()log⁡ ⁡ n/log⁡ ⁡ ()log⁡ ⁡ n)){displaystyle O(log n/log(log n)}	Koorde (con una búsqueda óptima)	Más complejo para implementar, pero las búsquedas pueden ser más rápidas (tienen un peor límite de casos)
O()n){displaystyle O({sqrt {n})}	O()1){displaystyle O(1)}		Las mejores necesidades de almacenamiento local, con mucha comunicación después de cualquier nodo conecta o desconecta

La elección más común, O()log⁡ ⁡ n){displaystyle O(log n)} La longitud de grado/ruto, no es óptima en términos de grado / duración del recorrido, pero tales topologías generalmente permiten más flexibilidad en la elección de los vecinos. Muchos Los 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 navegables de red de pequeño mundo, que transfiere la longitud de la ruta vs. grado de red.

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 compromiso grado/diámetro 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 las rutas más cortas.

Algoritmos para redes superpuestas

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 una DHT. Estos algoritmos son utilizados por las aplicaciones para superponer multidifusión, consultas de rango o para recopilar estadísticas. Dos sistemas que se basan en este enfoque son Structella, que implementa inundaciones y recorridos aleatorios en una superposición de Pastry, y DQ-DHT, que implementa un algoritmo de búsqueda de consultas dinámicas en una red Chord.

Seguridad

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.

Son viables los sistemas abiertos para el almacenamiento de datos distribuidos que son robustos frente a atacantes hostiles masivos.

Un sistema DHT 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. Whanau es un DHT diseñado para ser resistente a los ataques de Sybil.

Petar Maymounkov, uno de los autores originales de Kademlia, ha propuesto una forma de eludir la debilidad del ataque Sybil mediante la incorporación de relaciones de confianza social en el diseño del sistema. 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 en coautoría con el matemático Jonathan Kelner. Maymounkov ahora ha emprendido un esfuerzo integral de implementación de este nuevo sistema. Sin embargo, la investigación sobre defensas efectivas contra los ataques de Sybil generalmente se considera una pregunta abierta, y cada año se propone una amplia variedad de defensas potenciales en las principales conferencias de investigación de seguridad.

Implementaciones

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

• El espacio de dirección es un parámetro de DHT. Varios DHTs del mundo real usan espacio clave de 128 bits o 160 bits.
• Algunos DHTs del mundo real usan funciones de hash además de SHA-1.
• En el mundo real la clave k podría ser una molestia de un archivo contenido en lugar de un hash de un archivo Nombre para proporcionar almacenamiento de contenido, por lo que la renombre del archivo no impide que los usuarios lo encuentren.
• Algunos DHT también pueden publicar objetos de diferentes tipos. Por ejemplo, clave k podría ser el nodo ID y los datos asociados podrían describir cómo contactar este nodo. Esto permite la información de publicación de presencia y a menudo se utiliza en aplicaciones de IM, etc. En el caso más simple, ID es sólo un número al azar que se utiliza directamente como clave k (también en un DHT de 160 bits ID será un número de 160 bits, generalmente elegido aleatoriamente). En algunos DHTs, la publicación de los ID de los nodos también se utiliza para optimizar las operaciones DHT.
• La redundancia se puede agregar para mejorar la confiabilidad. El k, datos) par de teclas se puede almacenar en más de un nodo correspondiente a la llave. Generalmente, en lugar de seleccionar solo un nodo, los algoritmos DHT del mundo real seleccionan i nodos adecuados, con i ser un parámetro específico de implementación del DHT. En algunos diseños de DHT, los nodos están de acuerdo en manejar un cierto rango de espacio clave, cuyo tamaño puede ser elegido dinámicamente, en lugar de codificado duro.
• Algunos avanzados DHTs como Kademlia realizar búsquedas iterativas a través del DHT primero con el fin de seleccionar un conjunto de nodos adecuados y enviar put(k, data) mensajes sólo a esos nodos, reduciendo así drásticamente el tráfico inútil, ya que los mensajes publicados sólo se envían a nodos que parecen adecuados para almacenar la clave k; y las miradas iterativas cubren sólo un pequeño conjunto de nodos en lugar de todo el DHT, reduciendo el reenvío inútil. En tales DHTs, reenvío de put(k, data) los mensajes sólo pueden ocurrir como parte de un algoritmo de auto-sanación: si un nodo objetivo recibe un put(k, data) mensaje, pero cree que k está fuera de su rango manejado y se conoce un nodo más cercano (en términos del espacio clave DHT), el mensaje se envía a ese nodo. De lo contrario, los datos se indexan localmente. Esto conduce a un comportamiento DHT un tanto auto-equilibrio. Por supuesto, tal algoritmo requiere nodos para publicar sus datos de presencia en el DHT para que se puedan realizar las búsquedas iterativas.
• Dado que en la mayoría de las máquinas que envían mensajes es mucho más caro que los accesos locales de tabla de hah, tiene sentido hacer muchos mensajes referentes a un nodo en particular en un solo lote. Asumiendo que cada nodo tiene un lote local que consiste en la mayoría b operaciones, el procedimiento de agrupación es el siguiente. Cada nodo clasifica primero su lote local por el identificador del nodo responsable de la operación. Usando el tipo de cubo, esto se puede hacer en O(b + n), donde n es el número de nodos en el DHT. Cuando hay múltiples operaciones que abordan la misma clave dentro de un lote, el lote se condensa antes de ser enviado. Por ejemplo, múltiples búsquedas de la misma clave se pueden reducir a uno o varios incrementos se pueden reducir a una sola operación de adición. Esta reducción se puede aplicar con la ayuda de una tabla de hah local temporal. Por último, las operaciones se envían a los respectivos nodos.

Ejemplos

Protocolos e implementaciones de DHT

• Apache Cassandra
• BATON Superposición
• Mainline DHT – DHT estándar utilizado por BitTorrent (basado en Kademlia según lo dispuesto por Khashmir)
• Red de contenidos (CAN)
• Chord
• Koorde
• Kademlia
• Pastelería
• P-Grid
• Riak
• Tapiz
• TomP2P
• Voldemort

Aplicaciones que usan DHT

• BTDigg: motor de búsqueda de BitTorrent DHT
• Codeen: caching web
• Freenet: una red anónima resistente a la censura
• GlusterFS: un sistema de archivos distribuido utilizado para la virtualización de almacenamiento
• GNUnet: Red de distribución similar a Freenet, incluyendo una implementación DHT
• I2P: An open-source anonymous peer-to-peer network
• I2P-Bote: correo electrónico anónimo seguro sin servidor
• IPFS: Protocolo de distribución de hipermedias accesible a medida de contenido
• JXTA: plataforma P2P de código abierto
• LBRY: Un protocolo de intercambio de contenidos basado en blockchain que utiliza un sistema DHT influenciado por Kademlia para la distribución de contenidos
• Oracle Coherence: una red de datos en memoria construida sobre una implementación Java DHT
• Perfect Dark: una aplicación de intercambio de archivos entre iguales de Japón
• Retroshare: una red de amigos a amigos
• Jami: una plataforma de comunicación de voz, video y chat que conserva la privacidad, basada en un DHT como Kademlia
• Tox: un sistema de mensajería instantánea destinado a funcionar como reemplazo de Skype
• Twister: una plataforma de microblogging entre pares
• YaCy: un motor de búsqueda distribuido