《IPFS原理与实践》 —2 IPFS底层基础

2021-04-16 16:14:10 FIL1688 14266

原理篇

理解IPFS

第2章 IPFS底层基础

第3章 IPFS协议栈

第4章 IPFS模块解析

第5章 BZZ

 

第2章

IPFS底层基础

欢迎来到第2章。这一章的内容相对较多,也相对独立。你可以选择先阅读这一章,了解这几个基础性系统的设计思路和算法细节;或者暂时跳过这一章,直接去了解IPFS系统设计。在这一章中,我们会着重介绍IPFS的几个基础性的子系统和数据结构,包括DHT、BitTorrent、Git和自验证文件系统,以及Merkle结构。

2.1 分布式哈希表(DHT)

第1代P2P文件网络需要中央数据库协调,例如在2000年前后风靡一时的音乐文件分享系统Napster。在Napster中,使用一个中心服务器接收所有的查询,服务器会向客户端返回其所需要的数据地址列表。这样的设计容易导致单点失效,甚至导致整个网络瘫痪。在第2代分布式文件系统中,Gnutella使用消息洪泛方法(message flooding)来定位数据。查询消息会公布给全网所有的节点,直到找到这个信息,然后返回给查询者。当然,由于网络承载力有限,这种盲目的请求会导致网络快速耗尽,因此需要设置请求的生存时间以控制网络内请求的数量。但无论如何,这种方式所需的网络请求量非常大,很容易造成拥堵。到了第3代分布式文件系统中,DHT 的创新提供了新的解决方案。DHT(Distributed Hash Table)主要思想如下:全网维护一个巨大的文件索引哈希表,这个哈希表的条目形如<Key, Value>。这里Key通常是文件的某个哈希算法下的哈希值(也可以是文件名或者文件内容描述),而Value则是存储文件的IP地址。查询时,仅需要提供Key,就能从表中查询到存储节点的地址并返回给查询节点。当然,这个哈希表会被分割成小块,按照一定的算法和规则分布到全网各个节点上。每个节点仅需要维护一小块哈希表。这样,节点查询文件时,只要把查询报文路由到相应的节点即可。下面介绍3种IPFS引用过的有代表性的分区表类型,分别是Kademlia DHT、Coral DHT和S/Kademlia。

2.1.1 Kademlia DHT

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二叉树的建立,需要确保每个网络的节点都能从树根沿着它的最短唯一前缀的路径到达。

 image.png

图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步即可到达。

2.节点路由表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所示。

 image.png

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


首页
产品
新闻
联系