Tabla de hash distribuida

Las tablas de hash distribuidas, conocidas por las siglas DHT, (del inglés, Distributed Hash Tables) son un tipo de tablas de hash, almacenan pares (clave, valor) y permiten consultar el valor asociado a una clave, en las que los datos se almacenan de forma distribuida en una serie de nodos ( sistemas distribuidos) y proveen un servicio eficiente de búsqueda que permite encontrar el valor asociado a una clave. Para esto último usan un sistema de enrutado que permite encontrar de forma eficiente el nodo en el cual está almacenada la información que se necesita.

La responsabilidad de mantener el mapeo de las claves a los valores está distribuida entre los nodos, de forma que un cambio en el conjunto de participantes causa una cantidad mínima de interrupción. Esto permite que las DHTs puedan escalar a cantidades de nodos extremadamente grandes, y que puedan manejar constantes errores, llegadas y caídas de nodos.

Las DHTs forman una infraestructura que puede ser usada para construir servicios más complejos, como sistemas de archivos distribuidos, compartición de archivos peer-to-peer, sistemas de distribución de contenido, caché web cooperativo, multicast, anycast, servicios de DNS, y mensajería instantánea. Redes distribuidas importantes que usan DHT incluyen los trackers distribuidos del protocolo BitTorrent, la red Kad, el Storm botnet, YaCy, y la Coral Content Distribution Network.

Distributed hash tables

Historia

Las búsquedas por medio de DHTs fueron motivadas originalmente por los sistemas peer-to-peer como Napster, Gnutella, y Freenet, que aprovechaban recursos distribuidos en Internet para proveer una única aplicación. En particular aprovechaban el creciente ancho de banda y capacidad de disco, para proporcionar un servicio de compartición de archivos.

La diferencia entre estos sistemas estaba en como encontraban los datos que tenían sus pares:

  • Napster fue el primer sistema de distribución de contenido P2P a gran escala. Tenía un servicio de indexado central donde cada vez que un nodo se incorporaba, mandaba al servidor una lista de los archivos que poseía a nivel local. El servidor era el encargado de realizar las búsquedas y direccionarlas a los nodos que contenían los resultados. La desventaja estaba en que éste componente central hacia al sistema vulnerable a ataques, además de demandas legales.
  • Gnutella y redes similares usaban un modelo de consultas por inundación, donde cada búsqueda resultaba en un mensaje que se repetía a todas las máquinas en la red. Éste método evitaba el problema de tener un único punto de fallo (el servidor centralizado), pero era significativamente menos eficiente que Napster.
  • Freenet también era totalmente distribuido, y empleaba una clave heurística de ruteo, en donde cada archivo estaba asociado a una clave. Los archivos con claves similares tendían a agruparse en conjuntos de nodos similares. De esta forma era probable que las búsquedas fueran ruteadas a esos conjuntos, sin tener que visitar muchos nodos. Sin embargo no se garantizaba que se iba a encontrar los datos.

Las DHTs usan un ruteo basado en claves que incorpora los beneficios de la descentralización de Gnutella y Freenet, y la eficiencia y resultados garantizados de Napster. Una desventaja es que las DHTs así como Freenet, solo soportan búsquedas de coincidencia exacta, no obstante es posible implementar una funcionalidad de búsquedas por palabra clave como una capa superior a las DHTs.

Las primeras cuatro DHTs - CAN, Chord, Pastry y Tapestry- surgieron en la misma época durante el 2001. Desde entonces esta forma de búsqueda ha sido muy usada, principalmente desde que BitTorrent las incorporó.

Other Languages