Tabla hash distribuida

DHT ( ing. tabla hash distribuida - "tabla hash distribuida " ) es una clase de sistemas de servicio de búsqueda distribuida descentralizados que funcionan como una tabla hash . Como estructura de datos, una tabla hash puede ser una matriz asociativa que contiene pares ( clave-valor ). Además, el término DHT está asociado con una serie de principios y algoritmos que le permiten registrar datos, distribuir información entre un determinado conjunto de nodos de almacenamiento y restaurarlos mediante búsqueda distribuida por clave. Una característica de una tabla distribuida es la capacidad de distribuir información entre un conjunto de nodos de almacenamiento de tal manera que cada nodo participante pueda encontrar el valor asociado con una clave determinada. La responsabilidad de mantener la relación entre nombre y valor se distribuye entre los nodos, por lo que cambiar el conjunto de miembros provoca un número mínimo de interrupciones. Esto le permite escalar fácilmente DHT, así como monitorear constantemente la adición y eliminación de nodos y errores en su trabajo.

DHT es un marco que se puede utilizar para crear muchos servicios complejos, como sistemas de archivos distribuidos, distribución de archivos punto a punto y redes de entrega de contenido , caché web cooperativo, multidifusión , anycast , servicio de nombres de dominio y mensajería instantánea . Principales redes distribuidas que utilizan DHT: red I2P , BitTorrent , red eDonkey ( Red Kad ) , YaCy , Tox y Coral Content Distribution Network . Es posible crear motores de búsqueda sobre la red DHT.

Historia

La investigación de DHT estuvo inicialmente motivada en particular por los sistemas peer-to-peer como I2P , Napster , Gnutella , Freenet , que utilizaron recursos distribuidos a través de Internet para crear una sola aplicación. En particular, utilizaron Internet de banda ancha y espacio en el disco duro para brindar un servicio de distribución de archivos.

Estos sistemas difieren en cómo encontraron los datos de sus pares:

Napster tenía un servidor de índice central: cada nodo, después de unirse, debe enviar una lista de archivos almacenados localmente al servidor, que debe buscar y consultar los nodos que contienen los resultados. Este componente central hizo que el sistema fuera vulnerable a ataques y riesgos.
Gnutella y redes similares se han movido hacia un modelo de solicitud de inundación: básicamente, cada búsqueda daría como resultado el envío de un mensaje a todas las máquinas en la red. Si bien evitaba fallas centralizadas, este método era significativamente menos eficiente que Napster .
Finalmente, Freenet también se distribuyó por completo, pero el enrutamiento se basa en una clave heurística, en la que cada archivo tiene una clave asociada, y los archivos con claves similares tienden a agruparse en un conjunto similar de nodos. Lo más probable es que la solicitud se haya enviado a dichos clústeres sin necesidad de sondear a todos los pares. Sin embargo, Freenet no podía garantizar que se encontrarían los datos.

Los DHT utilizan un enrutamiento de claves más estructurado para lograr la descentralización de I2P , Gnutella y Freenet , y la eficiencia y los resultados garantizados de Napster . Un inconveniente es que, al igual que Freenet , DHT solo admite búsquedas de coincidencias exactas y no búsquedas de palabras clave, aunque estas funciones se pueden superponer a DHT.

Los primeros cuatro DHT ( CAN , Chord , Pastry y Tapestry ) se introdujeron alrededor de 2001 . Desde entonces, esta área de investigación ha estado bastante activa. Fuera de la academia, la tecnología DHT ha sido aceptada como un componente de BitTorrent y Coral Content Distribution Network .

Propiedades

DHT se caracteriza por las siguientes propiedades:

Descentralización : una forma de sistema de nodo colectivo sin coordinación;
Escalabilidad : el sistema funcionará con la misma eficacia con miles o millones de nodos;
Tolerancia a fallas : el sistema será igualmente confiable (en cierto sentido) con nodos que se conectan, desconectan y arrojan errores constantemente.

Una técnica clave para lograr este objetivo es que cualquier nodo debe coordinarse con solo unos pocos nodos en el sistema, generalmente O (log n ), donde n es el número de participantes (ver a continuación), de modo que solo se realice una cantidad limitada de trabajo. hecho a cada cambio en el número de participantes.

Algunos proyectos DHT buscan brindar protección contra usuarios maliciosos y permitir que los participantes permanezcan anónimos, aunque esto es menos común que en muchos otros sistemas P2P (especialmente cuando se comparten archivos); ver Redes anónimas .

Finalmente, DHT tiene que lidiar con problemas de sistemas distribuidos más tradicionales, como el equilibrio de carga, la integridad de los datos y el rendimiento (en particular, garantizar que las operaciones como el enrutamiento y el almacenamiento de datos o las búsquedas se completen rápidamente).

Estructura

La estructura de la DHT se puede dividir en varios componentes principales. Se basa en un espacio de claves abstracto, como un conjunto de cadenas de 160 bits (el número de bits puede variar). El esquema de particionamiento del espacio de claves distribuye la propiedad de las claves entre los nodos participantes. Luego, la red superpuesta conecta los nodos, lo que ayuda a encontrar al propietario de cualquier clave en el espacio de claves.

Con todos los componentes en su lugar, un uso típico de la DHT para almacenar y mostrar información es el siguiente: suponga que el espacio de claves son cadenas de 160 bits. Para almacenar un archivo con el nombre dado y la información en el DHT, se encuentra un hash SHA1 (valor de 160 bits) del nombre del archivo , a partir del cual se forma una clave k (hash) de 160 bits, después de lo cual se forma un mensaje put(k, data), где data - содержание самого файлаy enviado a cualquier nodo participante en el DHT. El mensaje va de un nodo a otro a través de la red superpuesta hasta llegar al único nodo responsable de la clave k, de acuerdo con el esquema de partición del espacio de claves, donde se almacenará el par (k, datos). Cualquier otro cliente puede obtener el contenido del archivo haciendo una clave (k), es decir, obteniendo un hash del nombre del archivo , para encontrar los datos asociados con la clave mediante el envío de un mensaje get(k). El mensaje pasará nuevamente a través de la superposición al nodo responsable de la clave, que responderá que los datos requeridos están disponibles.

Los componentes de la red de superposición y partición del espacio de claves se describen a continuación para presentar las ideas básicas comunes a la mayoría de los sistemas DHT. Muchos desarrollos difieren en los detalles.

Particionamiento del espacio de claves

La mayoría de los DHT utilizan diversas variaciones de hashing coherente para asignar claves a nodos. En el corazón de este método de partición se encuentra la función , que define el concepto abstracto de la distancia entre las claves y , que no tiene nada que ver con la distancia geográfica o el retraso de la red. A cada nodo se le asigna una sola clave, llamada su identificador (ID). El nodo con ID posee todas las claves para las cuales es la ID más cercana calculada usando . $\delta(k_1, k_2)$ $k_{1}$ $k_{2}$ $en$ $k_m$ $en$ $\delta(k_m, i_n)$

Ejemplo. Chord DHT trata las claves como puntos en un círculo, y es la distancia recorrida en el sentido de las agujas del reloj alrededor del círculo desde la clave hasta . Así, el círculo del espacio de claves se divide en segmentos contiguos cuyos extremos son identificadores de nodos. Si y son ID adyacentes, entonces el nodo con ID contiene todas las claves entre y . $\delta(k_1, k_2)$ $k_{1}$ $k_{2}$ $i_1$ $i_2$ $i_2$ $i_1$ $i_2$

El hashing consistente tiene la propiedad principal de que eliminar o agregar solo un conjunto de claves que pertenecen a nodos de ID adyacentes no afecta a otros nodos.

DHT y BitTorrent

Tanto DHT como PEX en realidad realizan la función principal de un rastreador de BitTorrent : ayudan a los participantes a compartir archivos a conocerse unos a otros. Ellos pueden:

Ayude a los participantes a encontrarse más rápido Por ejemplo, hay un compañero
X en la distribución con un puerto no disponible. Peer Z se conecta a la distribución, que no puede iniciar una conexión con X y tiene que esperar hasta que X se entere. X acaba de acceder al rastreador y lo hará dentro de una hora. Pero el compañero Y una vez más recurre al rastreador y aprende sobre el nuevo compañero Z. Si, al mismo tiempo, Y ha estado conectado durante mucho tiempo y está compartiendo archivos con X, entonces le dice a X la dirección de este nuevo compañero Z a través de PEX. Puede haber tales pares Y en la distribución muchos. Ahora X puede iniciar una conexión con Z sin esperar la próxima solicitud al rastreador, lo cual es especialmente importante si Z está desconectado para entonces. Con una gran proporción de distribuidores entrantes y salientes, esto reduce la espera para que comiencen a descargar.

Reduzca la carga en el rastreador
Al obtener direcciones de pares a través de DHT o PEX, los clientes acceden al rastreador con menos frecuencia, lo que reduce la carga.

Admite la distribución durante los períodos de indisponibilidad del rastreador
Si el rastreador es la única fuente de información sobre los pares, la distribución se detendrá gradualmente si no funciona. Usando PEX , los clientes pueden intercambiar información entre sí sobre los pares con los que tuvieron sesiones de comunicación, lo que ralentiza el proceso de detener la distribución. DHT le permite reemplazar completamente el rastreador.

DHT le permite distribuir sin un rastreador
Tal distribución se llama trackerless ( sin rastreador ). Se crea un torrente sin una dirección de seguimiento y los clientes se encuentran a través de DHT. Es cierto que, al mismo tiempo, la persona que inició la distribución debe tener una dirección IP real a la que se pueda acceder desde el exterior. Al participar en distribuciones trackerless, los clientes de BitTorrent adquieren cierto parecido con eMule utilizando la red Kad .

Clave privada

En los rastreadores públicos (abiertos), donde cualquiera puede descargar un torrent y participar en la distribución, DHT y PEX benefician a todos los participantes.

Para rastreadores privados (cerrados), en primer lugar, es importante que solo los usuarios registrados puedan participar en las distribuciones y que sigan ciertas reglas. A la primera solicitud de un cliente, un rastreador privado tiene la oportunidad de evitar que se distribuya, simplemente sin decirle las direcciones de otros clientes participantes. Por lo tanto, es importante para un rastreador privado que los clientes no reciban estas direcciones a través de DHT/PEX.

DHT y PEX aparecieron en los clientes Azureus y BitComet alrededor del verano de 2005. Los administradores de muchos rastreadores privados no estaban contentos con esta nueva funcionalidad y, por lo tanto, comenzaron a prohibir estas nuevas versiones de clientes en el rastreador.

Luego, los desarrolladores del cliente propusieron una nueva clave dentro del archivo torrent: private . Si es igual a 1, el cliente está obligado a deshabilitar automáticamente DHT / PEX para este torrente, independientemente del deseo del usuario. Tal torrent se llama Torrent seguro.

Casi todos los rastreadores privados modernos aplican private:1 en todos los torrents publicados en el rastreador y también prohíben varias versiones obsoletas de clientes que admiten DHT o PEX, pero que aún no conocen la clave privada . Se cree que los usuarios de rastreadores simplemente no pueden usar DHT / PEX en las distribuciones, y no hay problema. De hecho, para no tener en cuenta la calificación, basta con reemplazar su clave de acceso por cualquier otra. Y ni siquiera tienes que robarlo. Basta con registrar otra cuenta para tomar la clave de acceso de la misma.

DHT y estadísticas

Esta sección solo se aplica a los rastreadores privados donde la clave privada no está forzada en los torrents , y en algunas distribuciones (dependiendo de si el distribuidor mismo insertó la clave privada en el torrente ) se pueden usar DHT y PEX.

A menudo, existe la opinión de que DHT habilitado en el cliente afecta el seguimiento de las estadísticas del cliente por parte del rastreador, por ejemplo, "distribuido a través de DHT, por lo que las estadísticas pasaron el rastreador". Esto no es verdad.

Primero, DHT/PEX solo se usa para obtener direcciones de pares. No se mantienen archivos compartidos, ni contabilidad alguna de estadísticas sobre los mismos. El cliente informa las estadísticas de los datos descargados y cargados solo al rastreador.

Es decir, "distribuido a través de DHT" en realidad significa "Recibí información sobre algunos (o todos) compañeros a través de DHT, y probablemente algunos compañeros también me encontraron a mí a través de DHT".

En segundo lugar, aunque los clientes generalmente saben de dónde obtuvieron las direcciones de sus pares, ningún cliente separa el tráfico en "recibido/enviado a pares DHT" y "recibido/enviado a pares recibido del rastreador". Incluso si lo desea, sería difícil para el cliente hacer esto: algunos pares se pueden recibir tanto desde el rastreador como a través de DHT o PEX y, a menudo, el cliente no sabe cómo recibió su dirección el par que inicia la conexión.

El cliente informa al rastreador los datos totales sobre los volúmenes descargados y entregados a todos los pares con los que se comunicó , independientemente de si el cliente se enteró de los pares individuales a través del rastreador, DHT o PEX, o si ese par incluso inició la conexión. . Es decir, aunque aparezcan usuarios “dejados” (que no acceden al rastreador) en la distribución debido a DHT/PEX, el cliente seguirá reportando al rastreador todo lo que ha descargado y regalado.

La contabilidad correcta de las estadísticas depende solo del estado del rastreador: el rastreador funciona, las estadísticas se tienen en cuenta, si no funciona, no se tiene en cuenta. Solo en el caso de un rastreador que no funciona a largo plazo, DHT / PEX puede desempeñar un papel indirecto, evitando que el intercambio de archivos desaparezca gradualmente en tal "distribución sin tener en cuenta las estadísticas".

Cómo funciona DHT

La implementación de la red distribuida en los clientes de BitTorrent se basa en una variante de DHT llamada Kademlia . En términos generales, DHT (tabla hash distribuida) significa un sistema distribuido descentralizado para combinar una gran cantidad de nodos que aparecen y desaparecen constantemente y transferir mensajes de manera eficiente entre ellos. Varios sistemas más complejos se construyen sobre la base de estructuras DHT, como el intercambio de archivos P2P , el almacenamiento en caché web cooperativo, los servicios DNS, etc.

DHT utiliza el protocolo UDP . Los clientes de BitTorrent "escuchan" en el mismo número de puerto UDP que utilizan para las conexiones TCP entrantes . Si está utilizando activamente DHT, entonces es deseable abrir este puerto UDP para acceder desde el exterior, pero no es necesario; DHT funcionará así.

Cada cliente conectado es un nodo separado en la red DHT. Tiene su propia ID (identificador) única, seleccionada aleatoriamente del mismo espacio de 160 bits que infohash y torrents.

Cada nodo mantiene una tabla de enrutamiento que contiene información de contacto para muchos de los nodos "más cercanos" y para algunos más distantes. La "proximidad" de dos nodos se calcula a partir de la "similitud" de sus ID y no tiene nada que ver con su proximidad geográfica.

Cuando un nodo quiere encontrar pares para una distribución, compara el infohash de esa distribución con las ID de los nodos que conoce y luego envía una solicitud al nodo cuya ID es más similar a ese infohash. Ese nodo le devuelve la dirección del nodo cuyo ID es aún más cercano al infohash del torrent.

Luego, nuestro nodo envía una solicitud a ese nuevo nodo y recibe de él la dirección del siguiente nodo, cuya ID es aún más similar al infohash del torrent.

Por lo tanto, las solicitudes de los clientes que participan en la distribución de un torrent con un infohash particular fluyen gradualmente hacia los nodos cuyas ID son más similares a este infohash. Estos nodos recuerdan solicitudes anteriores, y todos los nodos solicitantes posteriores devolverán direcciones de pares anteriores de la misma distribución.

Desventajas

Hay varios protocolos incompatibles que sirven a diferentes redes.
La operación del cliente como un nodo DHT crea una gran carga en el enrutador (enrutador).
Los hashes se publican abiertamente, lo que permite el seguimiento interactivo de las distribuciones (que es lo que usan los titulares de los derechos de autor). [1] [2] [3]

Notas

↑ Los investigadores espían a los usuarios de BitTorrent en tiempo real . Consultado el 30 de septiembre de 2017. Archivado desde el original el 21 de agosto de 2017. (indefinido)
↑ Protocolo DHT . Consultado el 29 de mayo de 2010. Archivado desde el original el 20 de mayo de 2015. (indefinido)
↑ Extensión para que los pares envíen archivos de metadatos . Fecha de acceso: 29 de mayo de 2010. Archivado desde el original el 10 de mayo de 2016. (indefinido)

Enlaces

Descripción del protocolo DHT (Traducción) (Ruso)
Descripción del protocolo DHT en BitTorrent.org
en el Wiki de Azureus
en el sitio web de BitComet

Protocolo de intercambio de archivos BitTorrent ( programas cliente )
Los autores	personas Eric Clinker bram cohen Navin Compañías BitTorrent Inc. Vuse, Inc.
Tecnología	reemplazar Intercambio de pares (PEX) Tabla hash distribuida (DHT) captura amplia Cifrado de protocolo ADN multitracker rastreador anunciar raspar caja de semillas
Rastreadores	la bahia pirata caza iso Mininova RuTracker.org pornolab.net free-torrents.org Demonoide 1337x
Motores	IPB IPBTT phpBB2 _ Muelle de Torrente Embarcadero de Torrent II phpBB3 ppkbb3cker xbtbb3cker_ SMF SMF Rastreador simple Por determinar Otro xbtit Rastreador BTITeam Torrent Trader Torrent Hoster Rastreador de
Artículos relacionados	TorrentFreak