KAD

Kademlia DHT是分布式哈希表的一种实现,它主要提供以下特性:
1.节点ID与关键字是同样的值域,都是使用SHA-1算法生成的160位摘要,这样大大简化了查询时的信息量,更便于查询
2.可以使用XOR,计算任意两个节点的距离或节点和关键字的距离
3.查找一条请求路径的时候,每个节点的信息是完备的,只需要进行Log(n)量级次跳转
4.可根据查询速度和存储量的需求调整每个节点需要维护的DHT大小

KAD对DHT有较大的改进:
1.一个新来的网络节点在初次连接网络时会被分配一个ID
2.每个节点自身维护一个路由表和一个DHT,这个路由表保存网络中一部分节点的连接信息,DHT用于存放文件信息
3.每个节点优先保存距离自己更近的节点信息,但一定确保距离在[2的n次方,2的n+1次方-1]的全部节点至少保存k个(k是常数),我们称作K-Bucket
4.每个网络节点需要优先存储与自己的ID距离较小的文件
5.每次检索时,计算查询文件的哈希值与自己的ID的距离,然后找到与这个距离对应的K-Bucket,向K-Bucket中的节点查询,接受查询的节点也做同样的检查,如果发现自己的存有这个数据,便将其返回给查询的节点

KAD网络的节点ID是由一棵二叉树维护,它有如下特点:
1.每个网络节点从根节点出发,沿着它的最短唯一前缀到达
2.每个网络节点是叶子节点,KAD二叉树的建立,需要确保每个网络的节点都能从树根沿着它的最短唯一前缀的路径到达
3.在KAD中,每个DHT条目包含key,value对,key是文件的hash值,value是节点ID.key和value有相同的值域,都是160位.每一个新加入网络的计算机都会被随机分配一个节点ID值.数据存放在key值与ID值最接近key值的节点上.这样,我们就需要定义它们的远近了,XOR运算可以解决这个问题.key,value在160位hash上,判断两个节点x,y的距离远近的方法是进行二进制的异或,只要沿着XOR距离降低的方向查找,从任意一个网络节点开始查询,我们总能找到这个存放文件的地址,而且每次更新总能筛选掉一半的节点,那么最多只需要LogN步即可到达

节点路由表K-Bucket
1.节点路由表用于保存每个节点与自己一定距离范围内其他节点的连接信息.每一条路由信息由如下3部分组成:IP Address,UDP Port,Node ID.KAD路由表将距离分成160个K桶(存放K个数据的桶),分开存储.
2.编号为i的路由表,存放着距离为[2的i次方,2的i+1次方-1]的K条路由信息.并且每个K桶内部信息存放位置是根据上次看到的时间顺序排列的,最早看到的放在头部,最后看到的放在尾部.因为网络中节点可能处于在线或者离线状态,而在之前经常在线的节点,我们需要访问的时候在线的概率更大,那么我们会优先访问它(尾部的节点).
3.通常来说当i值很小时,K桶通常是空的(以0为例,距离为0自然只有1个节点,就是自己);而当i值很大时,其对应K桶的项数又很可能特别多(因为范围很大).这时,我们只选择存储其中的K个.在这里k的选择需要以系统性能和网络负载来权衡它的数量.比如,在BitTorrent的实现中,取值为k=8.因为每个K-Bucket覆盖距离范围呈指数增长,那么只需要保存至多160K个路由信息就足以覆盖全部的节点范围了
4.在查询时使用递归方式,我们能证明,对于一个有N个节点的KAD网络,最多只需要经过logN步查询,就可以准确定位到目标节点

当节点x收到一个消息时,发送者y的IP地址就被用来更新对应的K桶,具体步骤如下:
1.计算自己和发送者的ID距离:d(x,y)=x xor y
2.通过距离d选择对应的K桶进行更新操作
3.如果y的IP地址已经存在于这个K桶中,则把对应项移到该K桶的尾部;如果y的IP地址没有记录在该K桶中,则:
a.如果该K桶的记录项小于k个,则直接把y的(IP address,UDP port,Node ID)信息插入队列尾部
b.如果该K桶的记录项大于k个,则选择头部的记录项(假如是节点z)进行RPC_PING操作
c.如果z没有响应,则从K桶中移除z的信息,并把y的信息插入队列尾部
d.如果z有响应,则把z的信息移到队列尾部,同时忽略y的信息

用户的在线时间越长,他在下一时段继续在线的可能性就越高.所以,通过把在线时间长的节点留在K桶里,可以明显增加K桶中的节点在下一时间段仍然在线的概率,这利于保持KAD网络的稳定性和减少网络维护成本(不需要频率构建节点的路由表)

路由查询机制:
KAD技术最大特点之一就是能够提供高效的节点查找机制,并且还可以通过参数调节查找的速度.假如节点x要查找ID值为t的节点,Kad按照如下递归操作步骤进行路由查找:
1.计算到t的距离:d(x,t) = x xor t
2.从x的第log(d)个k桶中取出节点的信息,同时进行FIND_NODE操作.如果这个K桶信息少于个,则从附近多个桶中选择距离最接近d的总个节点
3.对接受到查询操作的每个节点,如果发现自己就是t,则回答自己是最接近t的;否则测量自己和t的距离,并从自己对应的K桶中选择个节点的信息给x
4.x对新接收到的每个节点都再次执行FIND_NODE操作,此过程不断重复执行,直到每一个分支都有节点响应自己是最接近t的
5.通过上述查找操作,x得到了k个最接近t的节点信息

这里强调,是k个最接近t的节点信息,而不是完全信息相等,因为网络中可能根本不存在ID为t的节点.也是为权衡性能而设立的一个参数,就像K一样.在BitTorrent实现中,取值为=3.这个递归过程一直持续到x=t,或者路由表没有任何关于t的信息.由于每次查询都能从更接近t的K桶中获取信息,这样的机制保证了每一次递归操作都能够至少获得距离减半(或距离减少1bit)的效果,从而保证整个查询过程的收敛速度为O(logN),这里N为网络全部节点的数量

上述是查询节点ID的方法,对于文件查询也是一样的方法.区别仅在于进行FIND_Value操作,查找自己是否保存ID为t的文件.文件查询过程的收敛速度同样是O(LogN).

节点加入和离开
1.如果节点u要加入KAD网络,它必须和一个已经在KAD网络中的节点,比如w,取得联系.u首先把w插入自己适当的K桶中,对自己的节点ID执行一次FIND_NODE操作,然后根据接收到的信息更新自己的K桶内容.通过对自己邻近节点由近及远的逐步查询,u完成了仍然是空的K桶信息的构建,同时也把自己的信息发布到其他节点的K桶中.在KAD网络中,每个节点的路由表都表示为一棵二叉树,叶子节点为K桶,K桶存放是的有相同ID前缀的节点信息,而这个前缀就是该K桶在二叉树中的位置.这样,每个K桶都覆盖了ID空间的一部分,全部K桶的信息加起来就覆盖了整个160bit的ID空间,而且没有重叠

以节点u为例,其路由表的生成过程如下:
1.最初,u的路由表为一个单个的K桶,覆盖了整个160bit ID空间.
2.当学习到新的节点信息后,则u会尝试把新节点的信息,根据其前缀值插入对应的K桶中
a.当K桶没有满,则新节点直接插入这个K桶中
b.当K桶已经满了:如果该K桶覆盖范围包含了节点u的ID,则把该K桶分裂为两个大小相同的新K桶,并对原K桶内的节点信息按照新的K桶前缀值进行重新分配;如果该K桶覆盖范围没有包含节点u的ID,则直接丢弃该新节点信息
3.上述过程不断重复,直接满足路由表的要求.达到距离近的节点的信息多,距离远的节点的信息少的结果,这样就保证了路由查询过程能快速收敛

节点离开KAD网络不需要发布任何信息,等待节点离线的时间足够长,其他网络节点访问它失效后,便会自动将其移出各自的路由表,那么这一节点也就离开了