2.1 分布式哈希表（DHT）

第一代P2P网络，需要中央数据库协调，使用中心服务器接收并返回客户端的所有查询。中心服务器的很容易因为单点宕机之类的使服务失效。

第二代P2P网络Gnutella使用message flooding来定位数据，查询消息会flooding到全网所有节点，这样的广播很容易引起广播风暴，造成通信阻塞、网络性能下降等问题。
第三代P2P网络文件系统就用到了DHT了。

DHT的主要思想：
全网维护一个巨大的文件索引哈希表，这个哈希表的条目以k,v形式存储。这里key通常是文件的某个哈希算法下的哈希值，（当然也可以是文件名或文件内容描述），而Value则是存储文件的IP地址。查询时，仅需要提供Key，就能从表中查询到存储到节点地址并返回给查询节点。
当然这个哈希表会被分割成小块，按照一定的算法和规则分布到全网各个节点上。每个节点仅需要维护一小块哈希表。这样，节点查询文件时，只要把查询报文路由到相应的节点即可。我们再下面介绍三种IPFS中会用到的具有代表性的分区表类型，分别是Kademlia DHT、Coral DHT和S/Kademlia。

2.1.1 Kademlia DHT

Kademlia DHT是分布式哈希表的一种实现。Kad DHT有如下特性：

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

KAD网络对之前我们说的DHT有较大的改进，一个新来的网络节点在初次连接网络会分配一个ID；
每个节点自身维护一个路由表和一个DHT，这个路由表保存网络中一部分节点的连接信息，DHT用于存放文件信息；
每个节点优先保存距离自己更近的节点信息，但一定确保距离在[2^n, 2^(n+1) -1]的全部节点，至少保存k个（k是常数），我们称为K-Bucket；每个网络节点需要优先存储与自己的ID，距离较小的文件；

每次检索时，将查询文件的哈希值与自己的ID求距离，然后找到这个距离对应的K-Bucket，向K bin中的节点查询。接收查询的节点也做同样的检查，如果发现自己存有这个数据，便将其返回给查询的节点。

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

Kademlia二叉状态树

Kademlia ID二叉树结构

Kad网络的节点ID是由一颗二叉树维护，我们最终生成的二叉树需要如下要求：

每个网络节点可以从根节点出发，沿着它的最短唯一前缀到达。
每个网络节点都应该是叶子节点。上图表示了二叉树的形成过程。Kad二叉树的建立，需要确保每个网络的节点都能从树根沿着它的最短唯一前缀的路径到达。

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

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

通常来说当i值很小时，K桶通常是空的（以0为例，距离为0的自然只有自己这一个节点），而当i很大时，其对应的K桶的项数又很可能特别多（因为范围很大）。这时，我们只选择存储其中的K个。在这里k的选择，要根据系统性能和网络负载来选择。比如，在BT中，k=8。因为每个K-Bucket覆盖距离范围呈指数增长，那么只需要保存至多160k个路由信息就足以覆盖全部的节点范围了。在查询时采用递归方式，最多只需要经过logN步查询，就可以准确定位到目标节点。

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

K桶更新步骤

1）路由查询机制

image.png

2）节点加入和离开

image.png

2.2 块交换协议（BitTorrent）

BitTorrent是一种内容分发协议。BT采用内容分发和点对点技术，帮助用户相互更高效地共享大文件，减轻中心服务器的负载。在BT网络里，每个用户同时需要上传和下载。文件持有者将文件发送给其中一个或多个用户，再由这些用户转发给其他用户，用户之间相互转发自己所拥有的文件部分，知道每个用户的下载都全部完成。这种方法可以使下载服务器同时处理多个大体积文件的下载请求，而无需占用大量带宽。

BitTorrent术语解释

torrent：它是服务器接收的元数据文件（通常结尾是.Torrent）。这个文件记录了下载数据的信息，但不包括文件自身。例如，文件名，文件大小，文件的哈希值，以及Tracker的URL地址。
tracker：是指互联网上负责协调BT客户端行动的服务器。当你打开一个torrent，你的机器连接tracker，并且请求一个可以接触的的peers列表。在传输过程中，客户端将会定期向tracker提交自己的状态。Tracker的功能仅在于帮助Peers相互达成连接，它不参与文件本身的传输。
peer：互联网上参与p2p连接的普通电脑。通常情况下peer没有完整的文件。
seed：有一个特定Torrent完整拷贝的电脑称为Seed。文件初次发布时，需要一个Seed进行初次共享。
swarm：连接一个Torrent的所有设备群组。
Chocking：Chocking阻塞是一种临时的拒绝上传策略，虽然上传停止了，但是下载仍然继续。BitTorrent网络下载需要每个Peers相互上传，对于不合作的peer，会采取临时阻断策略。
Pareto效率：帕累托效率是指资源分配已经到了物尽其用的阶段，对任意一个个体进一步提升效率只会导致其他个体效率下降，此时说明系统已经达到最优化了。