IPFS 原理与实践 (17):IPFS 底层基础 2.1.1

阅读数:1 2019 年 12 月 21 日 18:51

IPFS原理与实践(17):IPFS底层基础 2.1.1

(Kademlia DHT)

内容简介
这是一部从实现原理和工程实践两个维度深入讲解 IPFS 和 Filecoin 的著作。作者是中文社区内非常有影响力的三位 IPFS/Filecoin 布道者,本书得到了 IPFS&FileCoin 创始人以及 IPFS 官方(协议实验室)的高度认可和强烈推荐。
为 * 大化满足读者需求,书中不仅介绍 IPFS 技术细节、区块链相关知识、Filecoin 项目技术细节,还加入了大量作者们在开发中的经验和技巧。为了适配当下及未来较长时间内读者的实际使用环境,书中所有案例都是基于生态链中较新的软件开发工具和前沿的软件开发技术编写的。
本书分为三大部分:
第一部分 基础篇(第 1 章)
全面介绍了 IPFS 的源起,概念、优势和应用领域,旨在帮助读者了解 IPFS 相关基础背景知识,从宏观层面认识 IPFS 技术所具有的创新性。
第二部分 原理篇(第 2~5 章)
旨在帮助读者深入理解 IPFS 和 Filecoin 的运行原理与工作机制。首先深入分析了分布式哈希表、块交换协议、版本控制、自验证文件系统 Merkle DAG 和 Merkle Tree 等底层基础知识,然后对 IPFS 协议栈中包含的 7 层子协议了进行了剖析,接着解析了 Multi-Format、libp2p、IPLD 三大 IPFS 核心模块,最后用了一整章的篇幅详细剖析了 Filecoin 项目。
第三部分 实战篇(第 6~8 章)
以工程化的方式,从基础至进阶,介绍了 IPFS 技术的实际使用,包括安装、配置、交互、入网、API、内容发布、数据保存、私网搭建等内容,之后通过两个不同风格的实际项目案例向读者展示了基于不同语言所实现的 IPFS 协议栈的使用方法。

Kademlia DHT 是分布式哈希表的一种实现,它的发明人是 Petar Maymounkov 和 David Mazières。Kademlia DHT 拥有一些很好的特性,如下:

  • 节点 ID 与关键字是同样的值域,都是使用 SHA-1 算法生成的 160 位摘要,这样大大简化了查询时的信息量,更便于查询。
  • 可以使用 XOR,计算任意两个节点的距离或节点和关键字的距离。
  • 查找一条请求路径的时候,每个节点的信息是完备的,只需要进行 Log(n) 量级次跳转。
  • 可根据查询速度和存储量的需求调整每个节点需要维护的 DHT 大小。

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

下面我们详细说明一下 KAD 网络算法细节。

  1. Kademlia 二叉状态树

Kademlia 网络的节点 ID 是由一棵二叉树维护的,最终生成的二叉树的特点如下:

  • 每个网络节点从根节点出发,沿着它的最短唯一前缀到达。
  • 每个网络节点是叶子节点。图 2-1 表示了二叉树的形成过程,例如这里黑色的节点 ID 拥有一个唯一的前缀 0011。对于任意的一个树的节点,我们可以沿着它的前缀作为路径,向下分解成一系列不包含自己的子树。Kademlia 二叉树的建立,需要确保每个网络的节点都能从树根沿着它的最短唯一前缀的路径到达。

IPFS原理与实践(17):IPFS底层基础 2.1.1

图 2-1 Kademlia ID 二叉树结构

下面我们介绍一下节点哈希是 0011….(一共 160 位)的子树划分方法。

现在我们的网络上有 18 个节点,如图 2-1 所示。从树根开始,树根的前缀是空。左子树和右子树的编号分别是 1 和 0。因为还存在其他 10 个节点都有共同的前缀 0,那么我们继续划分成 00 和 01 两棵子树,我们的目标节点(哈希值 0011…)显然属于 00 这棵子树。我们继续检查,发现还有 3 个节点是 00 前缀,那么继续划分子树 001、000。哈希位 00100…和 00101…两个节点与 0011 依旧是共有 001 前缀,所以 001 还不是最短唯一前缀,我们再继续划分子树,到 0011,那么不再有其他节点有相同的前缀,这条路径 0011 就是到树根最短的路径,同时 0011 是最短唯一前缀,0011 就成为它的网络 ID。

在 Kademlia 中,每个 DHT 条目包含 <key, value> 对。key 是文件的哈希值,value 是节点 ID。key 和 value 有相同的值域,都是 160 位。每一个新加入网络的计算机都会被随机分配一个节点 ID 值。数据存放在 key 值与 ID 值最接近 key 值的节点上。这样,我们就需要定义它们的远近了。XOR 运算可以解决这个问题。<key,Value> 在 160 位 Hash 上,判断两个节点 x、y 的距离远近的方法是进行二进制运算异或,d(x,y)=x⊕y。两个二进制位结果相同,它们的异或值是 0;如不同,值为 1。例如,我们将 111010 和 101011 取 XOR。

复制代码
111010
XOR 101011
----------------
010001

对于异或操作,有如下一些数学性质:

  • d(x, x)=0
  • d(x, y)>0, iff x≠y
  • x, y:d(x, y)=d(y, x)
  • d(x, y)+d(y, z)≧d(x, z)
  • d(x, y) ⊕ d(y, z)=d(x, z)
  • 存在一对 x≧0, y≧0,使得 x+y≧x⊕y

我们很自然地发现,如果给定了 x,任意一个 a(a≧0) 会唯一确定另一个节点 y,满足 d(x, y)=a。假设这里的 x 是我们需要查询的文件 key,我们只需要不断更新 y,使得 y 沿着 d(x, y) 下降的方向找下去,那么一定能收敛到距离 x 最近的点。前面我们提到,文件就是存放在网络编号与文件哈希的 XOR 最近的几个节点上。那么换句话说,只要沿着 XOR 距离降低的方向查找,从任意一个网络节点开始查询,我们总能找到这个存放文件的地址。而且每次更新总能筛选掉一半的节点,那么最多只需 Log N 步即可到达。

  1. 节点路由表 K-Bucket

节点路由表用于保存每个节点与自己一定距离范围内其他节点的连接信息。每一条路由信息由如下 3 部分组成:IP Address、UDP Port、Node ID。KAD 路由表将距离分成 160 个 K 桶(存放 K 个数据的桶),分开存储。编号为 i 的路由表,存放着距离为 [2i,2(i+1)-1] 的 K 条路由信息。并且每个 K 桶内部信息存放位置是根据上次看到的时间顺序排列的,最早看到的放在头部,最后看到的放在尾部。因为网络中节点可能处于在线或者离线状态,而在之前经常在线的节点,我们需要访问的时候在线的概率更大,那么我们会优先访问它(尾部的节点)。

通常来说当 i 值很小时,K 桶通常是空的(以 0 为例,距离为 0 自然只有 1 个节点,就是自己);而当 i 值很大时,其对应 K 桶的项数又很可能特别多(因为范围很大)。这时,我们只选择存储其中的 K 个。在这里 k 的选择需要以系统性能和网络负载来权衡它的数量。比如,在 BitTorrent 的实现中,取值为

k=8。因为每个 K-Bucket 覆盖距离范围呈指数增长,那么只需要保存至多 160K 个路由信息就足以覆盖全部的节点范围了。在查询时使用递归方式,我们能证明,对于一个有 N 个节点的 KAD 网络,最多只需要经过 log N 步查询,就可以准确定位到目标节点。

当节点 x 收到一个消息时,发送者 y 的 IP 地址就被用来更新对应的 K 桶,具体步骤如下。

1)计算自己和发送者的 ID 距离:d(x,y)=x⊕y。

2)通过距离 d 选择对应的 K 桶进行更新操作。

3)如果 y 的 IP 地址已经存在于这个 K 桶中,则把对应项移到该 K 桶的尾部;如果 y 的 IP 地址没有记录在该 K 桶中,则:

①如果该 K 桶的记录项小于 k 个,则直接把 y 的 (IP address,UDP port,Node ID) 信息插入队列尾部。

②如果该 K 桶的记录项大于 k 个,则选择头部的记录项(假如是节点 z)进行 RPC_PING 操作。

  • 如果 z 没有响应,则从 K 桶中移除 z 的信息,并把 y 的信息插入队列尾部。
  • 如果 z 有响应,则把 z 的信息移到队列尾部,同时忽略 y 的信息。

K 桶的更新机制非常高效地实现了一种把最近看到的节点更新的策略,除非在线节点一直未从 K 桶中移出过。也就是说,在线时间长的节点具有较高的可能性继续保留在 K 桶列表中。采用这种机制是基于对 Gnutella 网络上大量用户行为习惯的研究结果,即节点的在线概率与在线时长为正比关系,如图 2-2 所示。

IPFS原理与实践(17):IPFS底层基础 2.1.1

图 2-2 网络中在线时长和继续在线的概率关系

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

(1)路由查询机制

KAD 技术最大特点之一就是能够提供高效的节点查找机制,并且还可以通过参数调节查找的速度。假如节点 x 要查找 ID 值为 t 的节点,Kad 按照如下递归操作步骤进行路由查找:

1)计算到 t 的距离:d(x,t)=x⊕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)。

(2)节点加入和离开

如果节点 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 桶中。

①该 K 桶没有满,则新节点直接插入这个 K 桶中;

②该 K 桶已经满了:如果该 K 桶覆盖范围包含了节点 u 的 ID,则把该 K 桶分裂为两个大小相同的新 K 桶,并对原 K 桶内的节点信息按照新的 K 桶前缀值进行重新分配;如果该 K 桶覆盖范围没有包含节点 u 的 ID,则直接丢弃该新节点信息。

3)上述过程不断重复,直到满足路由表的要求。达到距离近的节点的信息多、距离远的节点的信息少的结果,这样就保证了路由查询过程能快速收敛。

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

IPFS原理与实践(17):IPFS底层基础 2.1.1

购书地址 https://item.jd.com/12665074.html?dist=jd

评论

发布