三分钟了解DSP （网络篇）- DHT

引言

DHT全称叫分布式哈希表(Distributed Hash Table)，是一种分布式存储方法，一类可由键值来唯一标示的信息按照某种约定/协议被分散地存储在多个节点上，这样也可以有效地避免“中央集权式”的服务器（比如：tracker）的单一故障而带来的整个网络瘫痪。实现DHT的技术/算法有很多种，常用的有：Chord, Pastry, Kademlia等。

总述

dht网络中每一个node节点有一个全局的唯一标识，叫node ID（节点id），节点id是随机从文件中的160位的hash中随机抽取的。distance metric（距离度量）用来比较两个节点id或者节点id和hash之间的距离。所有的节点（必须保存一个routing table（路由表）保存它和dht网络中一小部分节点交流的信息。离节点id越近的其它节点id的信息越详细。所有的节点必须知道很多离它们很近的其它节点，离它们很远的节点只需要有足够的握手信息就行了。

在Kad算法中，距离度量是对两个hash值进行XOR（异或）运算，并且把结果转换成无符号整数。distance(A,B)=|A xor B|，结果值越小，距离越近。

当一个节点想找到一个文件的peer节点信息时，就使用距离算法把文件的hash字段和它自己路由表中的节点id进行比较，然后和距离最近的节点进行通信，向它们发送请求获取正在下载这个文件的peer节点列表的信息。如果它请求的节点知道这个文件的peer节点列表，则把peer节点列表返回给发送请求的节点。如果不知道，它必须返回自己路由表中离文件hash最近的节点列表给请求者。原始节点不断迭代的发送请求直到找到离目标文件hash更近的节点。搜索结束之后，下载节点把peer节点的信息保存在自己的路由表里面。

原理

每一个节点都维护一个路由表保存一些已知的通信好的节点。路由表中的节点通常用来作为起始节点，当其它节点向这个节点发送请求时，路由表中的这些节点就会被返回给发送请求的结点。

路由表覆盖从0到2的160次完整的nodeID空间。路由表又被划分为buckets(简称K桶)，每一个bucket包含一个子部分的nodeID空间。一个空的路由表只有一个bucket，它的ID范围从min=0到max=2的160次。K桶结构如下：

DSP对DHT的改进

本文来源：DSP
原文标题：三分钟了解DSP （网络篇）- DHT

—-

编译者/作者：DSP

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。