分布式哈希表DHT（Kademlia算法）-易于理解

近年来，区块链技术的普及（有人更喜欢将其称为分布式分类帐技术）使分布式技术的概念在公众眼中. 区块链技术之所以受到高度追捧的原因是，一方面，它显示了人类可以在计算机的帮助下以非中心，非权威，非分层的方式开展社会协作的美好前景. 另一方面，从物理上可证明的角度来看，分布式简单协议比集中式复杂协议更有效. 分布式技术似乎可以同时带来公平和效率.

理解分布式技术并不难，因为分布式技术并不先进，但是其设计通常足够聪明，值得称赞.

本文介绍了一种常见的，巧妙的分布式技术，即Kademlia算法.

Kademlia算法是一种分布式存储和路由算法. 什么是分布式存储？想象一下，有1000人的学校. 现在，学校突然决定拆除图书馆（无需设置集中式服务器），并将图书馆中的所有书籍分发给每个学生（所有文件分散并存储在不同的位置）节点. 也就是说，所有学生组成一个分布式图书馆.

从中央图书馆到分布式图书馆

在这种情况下，有几个关键问题需要回答.

每个同学分配什么书. 即，如何将存储的内容分配给每个节点，以及如何处理新的/删除的内容. 当您需要查找“分布式算法”之类的书时，您如何知道哪个学生手头有“分布式算法”（一个人问一千人，“您是否拥有“分布式算法”？”，显然是不经济的方法），以及如何与同班同学联系. 也就是说，如果节点要获取特定文件，则如何查找文件存储的节点/地址/路径.

如何找到您需要的书？

接下来，让我们看看Kademlia算法如何巧妙地解决了这些问题.

首先，让我们看一下每个同学（节点）的属性:

每个学生都应保持以下条件:

根据上面的类比，您可以查看此表:

概念比较

（哈希概念说明，请参阅百度百科-哈希算法）

关于为什么不是每个学生都有完整的通讯簿（每个节点维护着完整的路由信息​​）的原因: 首先，分布式系统中节点的进入和退出非常频繁，并且每次发生更改时，整个网络广播地址簿已更新，通信量将非常大. 其次，一旦任何学生被坏人绑架（节点被黑客破坏），坏人将立即拥有每个人的手机号码，这是不安全的.

以何种方式将图书整齐地收集在图书馆中并按索引号排序分配给学生？一般原则包括: 1）书籍可以更均匀地分配到学生手中，并且在任何情况下都不会出现某些学生书籍过多而大多数学生甚至没有书籍的情况； 2）学生想查找使用特定书籍时，可以在相对简单的索引中找到它.

Kademlia进行了以下安排:

假定“分布式算法”的书名的哈希值是00010000，则这本书必须存在于学生编号为00010000的学生手中. （这要求哈希算法的值范围与节点ID的值范围相同. Kademlia的节点ID是160位二进制文​​件. 此处以“节点ID”为例）

但是您必须考虑到某些同学将缺席. 如果00010000今天没有上学（节点不或完全退出网络），那么没人会得到这本书吗？该算法要求这本书不能仅存储在一个同学的手中，而必须同时存储在学生编号最接近00010000（即00010001、00010010、00010011）的k个学生的手中. 等等.

同样分布式算法实现图书，当您需要查找“分布式算法”这本书时，请对该书的标题进行哈希处理以获得00010000. 这是电话号码，您知道要寻找哪个学生. 剩下的问题是找到这些（几个）同学的手机号码.

图书搜索定位

由于您手头只有一些同学的，因此您可能没有00010000手机号码（IP地址）. 如何联系目标同学？

中没有目标同学

一个可行的想法是在中找到一个具有目标同学的同学. 如前所述，每个学生手中的地址簿都是按距离分层的. 该算法的设计是，同学离您越近，您的手机号码存储在中的可能性就越大. 该算法的核心思想是: 当您知道目标同学Z和您之间的距离时，您可以首先在通讯簿中找到您认为最接近同学Z的同学B，请让同学B进一步查找同学Z的电话号码.

上述距离是节点ID之间的XOR距离. XOR用于是/否或二进制运算.

XOR的算法为: 0⊕0= 0，1⊕0= 1，0⊕1= 1，1⊕1= 0（相同为0，差为1）

百度百科-XOR

以2个示例为例:

01010000和01010010之间的距离（即2个ID的XOR值）为00000010（转换为十进制为2）；

01000000和00000001之间的距离是01000001（转换为十进制是26 + 1或65）；

以此类推.

那么地址簿如何按距离分层？以下示例将告诉您，按XOR距离分层基本上可以理解为按数字分层. 想象以下情况:

基于0000110，如果一个节点的ID之前的所有数字均相同，则只有最后一个数字不同，只有一个这样的节点-0000111，与基节点的XOR值为0000001，即，距离为1；对于0000110，该节点被分类为“ k-bucket 1”；

如果节点的ID的前位数相同且与倒数第二位不同，则只有两个这样的节点: 0000101和0000100.与基节点的XOR值是0000011和0000010，即距离范围为3和2;对于0000110，该节点被分类为“ k-bucket 2”；

......

如果一个节点的ID的前有相同的位数，并且从第n个到最后一个不同，则此类节点的数量仅为2（i-1），并且到基本节点是[2（i-1），2i）;对于0000110，此类节点被分类为“ k-bucket i”；

不同的k桶按数字

理解以上描述的另一种方式: 如果将整个网络的节点分类为按节点ID排列的二叉树，则树尾的每个叶子都是一个节点，则下图更直观地显示了: 节点之间的距离.

K桶: 右下角的黑色实心圆是基本节点（根据维基百科的图片进行了修改）

回到我们的比喻. 每个同学仅维护地址簿的一部分，该地址簿根据距离进行分层（可以理解为从学生编号的编号和从一开始的他自己的编号的分层），即k-bucket1，k-bucket 2，k-bucket 3 ...尽管每个k-bucket中实际存在的学生数量正在逐渐增加，但每个学生仅在其自己的每个k-bucket中记录k个学生的手机号码（地址和端口k个节点），其中k是可调常数参数.

由于学生ID（节点ID）具有160位数字，因此每个学生的地址簿分为160层（该节点共有160 k个存储桶）. 整个网络最多可容纳2 ^ 160个同学（节点），但每个同学（节点）最多只能维护160 * k行地址簿（其他节点的地址和端口）.

我们现在将说明完整的请求流程.

A类（学生编号00000110）想要找到“分布式算法”. 首先需要计算书名的哈希值hash（“ distributed algorithm”）=00010000. 然后A知道ta需要找到同学00010000（名为Z同学）或学生号接近Z的同学.

Z的学生编号00010000与他的XOR之间的距离为00010110，并且距离范围为[24，25），因此此Z学生可能在k-bucket 5中（或者Z学生的学生编号和A学生的学生） number学生编号不同于第五名，因此Z类可能在k-bucket 5中. ）

然后A个同学检查他们的k-bucket 5中是否有Z个同学:

查询方法

Kademlia的这种查询机制有点像不断折叠一张纸以缩小搜索范围，从而确保对于任何n名学生，您最多只需要查询log2（n）次即可找到与目标的联系同班方式（也就是说，对于具有[2（n-1），2n）个节点的任何网络，最多只需要n个步骤即可找到目标节点.

每次搜索都会将距离缩小至少一半

以上是Kademlia算法的基本原理. 协议中的技术细节简要介绍如下.

在Kademlia算法中，每个节点只有4条指令

此机制可确保任何节点的加入和退出都不会影响整个网络.

Kademlia是一种分布式哈希表（DHT）. DHT是一个分散的分布式系统. 在这种类型的系统中，每个节点维护一部分存储的内容以及其他节点的路由/地址，从而导致网络中的任何参与者（即节点）更改（进入/退出）整个网络. 影响很小. DHT可用于构建更复杂的应用程序，包括分布式文件系统，对等技术文件共享系统分布式算法实现图书，协作式网页缓存，域名系统和实时通信.

Kademlia算法是由Petar Maymounkov和DavidMazières在2002年设计的. 它是具有XOR距离的哈希表分层的特征. 后来，诸如eMule和BitTorrent之类的P2P软件将Kademlia用作基础算法. Kademlia可以用作信息安全技术的基础之一.

Kademlia的优势是:

参考

维基百科分布式哈希表

Wikipedia-Kademlia

Kademlia: 基于XOR指标的对等信息系统

卡德姆里亚王子亭子笔记

韩峰. “区块链人工智能”. 新兴出版社的“新区块链新经济蓝图和指南”的翻译后注释

作者: Li_Heng_lius

链接:

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-264167-1.html