天津西青区属于什么风险区_安卓手机软件开发教程_青青河边草直播免费观看_网站seo谷歌

1. P2P分布式文件系统发展历史

1.1 基于中央数据库协调的P2P文件网络

第 1代 P2P 文件网络需要中央数据库协调，例如在 2000年前后风靡一时的音乐文件分享系统 Napster。在 Napster中，使用一个中心服务器接收所有的查询，服务器会向客户端返回其所需要的数据地址列表。这样的设计容易导致单点失效，甚至导致整个网络瘫痪

1.2 基于消息洪泛方法的P2P文件网络

在第 2 代分布式文件系统中，Gnutella 使用消息洪泛方法(message flooding)来定位数据。查询消息会公布给全网所有的节点，直到找到这个信息，然后返回给查询者。当然由于网络承载力有限，这种盲目的请求会导致网络快速耗尽，因此需要设置请求的生存时间以控制网络内请求的数量。但无论如何，这种方式所需的网络请求量非常大，很容易造成拥堵。

1.3 基于分布式哈希表DHT的P2P文件网络

到了第 3 代分布式文件系统中，DHT 的创新提供了新的解决方案DHT ( Distributed Hash Table) 主要思想如下:全网维护一个巨大的文件索引哈希表，这个哈希表的条目形如 <Kev.Value>。这里 Kev通常是文件的某个信息在哈希算法下的哈希值(也可以是文件名或者文件内容描述)，而 Value 则是存储文件的 IP 地址。查询时，仅需要提供Key，就能从表中查询到存储节点的地址并返回给查询节点。当然.这个哈希表会被分割成小块，按照一定的算法和规则分布到全网各个节点上。每个节点仅需要维护一小块哈希表。这样，节点查询文件时，只要把查询报文路由到相应的节点即可。下面介绍 3 种IPFS引用过的有代表性的分区表类型，分别是 Kademlia DHT、Coral DHT和S/Kademlia。

2. Kademlia DHT

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

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

2.1 异或XOR操作

$\oplus b = b \oplus a$ ，XOR符合交换率，具备对称性
$\oplus a = 0$ ，反身性，自己和自己的距离为零
$\oplus b > 0$ ，两个不同的key之间的距离必大于0
$\oplus b) + (b \oplus c) >=(a \oplus c)$ ，三角不等式，A经过B到C的距离总是大于A直接到C的距离。

Kad使用160位哈希算法(SHA1)，完整的key用二进制表示有160位，这样可以容纳2^160个节点。

2.2 地址管理

Kademlia 同样使用 m 位整数作为节点和资源的唯一标识. 与 Chord 中的 “区间负责制” 不同, Kademlia 中的资源都是被离它最近的节点负责. 出于容错考虑, 每个资源通常都被距离它最近的 k 个节点负责, 这里 k 是一个常量, 通常取 k 使得在系统中任意 k 个节点都不太可能在一小时之内同时失效, 比如取 k = 20. 有趣的是, 这里的 “距离” 并不是数值之差, 而是通过异或运算得出的. 在 Kademlia 中, 每个节点都可以看作一颗高度为 m + 1 的二叉树上的叶子节点. 把 ID 二进制展开, 从最高位开始, 自根节点逢 1 向左逢 0 向右, 直到抵达叶子节点. 如下图所示.
在这里插入图片描述
Kademlia 的巧妙之处就是定义两个 ID $x$ 和 $y$ 之间的距离为 $\oplus y$ . 异或运算的特点是异为真同为假, 如果两个 ID 高位相异低位相同, 它们异或的结果就大; 如果它们高位相同低位相异, 异或的结果就小. 这与二叉树中叶子的位置分布是一致的: 如果两个节点共有的祖先节点少(高位相异), 它们的距离就远; 反之, 如果共有的祖先节点多(高位相同), 它们的距离就近. 上图标注了一些节点之间的距离, 大家可以感受一下.

异或运算的另一个重要性质是, 异或的逆运算仍是异或. 即如果有 $\oplus y = d$ 则 $\oplus d = y$ . 这就意味着对于每个节点, 给的一个距离 $d$ , 至多有一个与其距离为 $d$ 节点. 这样一来 Kademlia 的拓扑结构是单向的(unidirectional). 单向性确保不管查找从哪个节点开始, 同一 Key 的所有查找都会沿着同一路径收敛.

2.3 路由算法

对于任意一个给定节点, 我们将二叉树从根节点开始不断向下分成一系列不包含该节点的子树. 最高的子树由不包含该节点的二叉树的一半组成, 下一个子树又由不包含该节点的剩余树的一半组成, 以此类推. 如果这个二叉树的高度为 m + 1, 我们最终会得到 m 个子树.

接着在每个子树中任取 k 个节点, 形成 m 个 k 桶(k-bucket), 这 m 个 k 桶就是 Kademlia 节点的路由表. 我们定义最小子树中取得的节点为第 0 个 k 桶, 次小的子树中取得的节点为第 1 个 k 桶, 以此类推. 不难看出, 对于每个 $\le i < m$ , 第 $i$ 个 k 桶中节点与当前节点的距离总是在区间 $2^i,2^{i+1})$ 之内. 下图展示了 m = 3, k = 2 时节点 101 的 k 桶.
在这里插入图片描述
Kademlia 中每个节点都有一个基础操作, 称为 FIND_NODE 操作. FIND_NODE 接受一个 Key 作为参数, 返回当前节点所知道的 k 个距离这个 Key 最近的节点. 基于 k 桶, 找到这 k 个最近的节点很容易:

先求出这个 Key 与当前节点的的距离 $d$
对比该节点的路由表，上面说了, 第 $i$ 个k桶中节点与当前节点的距离总是在区间 $2^i,2^{i+1})$ 之内, 这些区间都不会互相重叠, 那么显然 $d$ 落在的区间所属的 k 桶中的节点就是距离这个 Key 最近的节点.
如果这个 k 桶中的节点不足 k 个, 则在后一个 k 桶中取节点补充, 如果还不够就再在后一个 k 桶中取. 如果这个节点所有的 k 桶中的节点数之和都不足 k 个, 就返回它所知道的所有节点.

2.4 节点查找

有了 FIND_NODE 操作, 我们就可以定义 Kademlia 中最重要的一个过程, 节点查找(node lookup). 节点查找要做的是, 给定一个 Key, 找出整个系统中距离它最近的 k 个节点. 这是一个递归过程。

首先初始节点调用自己的 FIND_NODE, 找到 k 个它所知的距离 Key 最近的节点.
接下来我们在这 k 个节点中取 $\alpha$ 个最近的节点, 同时请求它们为 Key 执行 FIND_NODE.这里的
也是一个常量, 作用是同时请求提高效率, 比如取 $\alpha=3$ .
在接下来的递归过程中, 初始节点每次都在上一次请求后返回的节点中取 $\alpha$ 个最近的, 并且未被请求过的节点, 然后请求它们为 Key 执行 FIND_NODE, 以此类推.
每执行一次, 返回的节点就距离目标近一点.
如果某次请求返回的节点不比上次请求返回的节点距目标 Key 近, 就向(这一轮剩下的)所有未请求过的节点请求执行 FIND_NODE.
如果还不能获取更近的节点, 过程就终止. 这时我们在其中取 k 个距离 Key 最近的节点, 就是节点查找的结果.

Kademlia 的大多数操作都基于节点查找. 发布资源时, 只需为资源的 Key 执行节点查找, 获取 k 个距离资源最近的节点, 把资源存储在这些节点上.

获取资源也类似, 也只需为目标资源的 Key 执行节点查找, 不同的是一旦遇到拥有目标资源的节点就停止查找. 此外, 一旦一个节点查找成功, 它就会把资源缓存在离自己最近的节点上. 因为 Kademlia 的拓扑结构是单向的, 其他离目标资源比自己远的节点在查找时就很可能会经由缓存的节点, 这样就能提前终止查找, 提高了查找效率.

2.5 k桶的维护

2.5.1 K桶的维护

所有的 k 桶都遵循最近最少使用(Least Recently Used, LRU)淘汰法. 最近最少活跃的节点排在 k 桶的头部, 最近最多活跃的节点排在 k 桶尾部.

当一个 Kademlia 节点接收到任何来自其他节点的消息(请求或响应)的时候, 都会尝试更新相应的 k 桶.
如果这个节点在接收者对应的 k 桶中, 接收者就会把它移动到 k 桶的尾部.
如果这个节点不在相应的 k 桶中, 并且 k 桶的节点小于 k 个, 那么接收者就会直接把这个节点插入到这个 k 桶的尾部.
如果相应的 k 桶是满的, 接收者就会尝试 ping 这个 k 桶中最近最少活跃的节点. 如果最近最少活跃的节点失效了, 那么就移除它并且将新节点插入到 k 桶的尾部; 否则就把最近最少活跃的节点移动到 k 桶尾部, 并丢弃新节点.

通过这个机制就能在的通信的同时刷新 k 桶. 为了防止某些范围的 Key 不易被查找的情况, 每个节点都会手动刷新在上一小时未执行查找的 k 桶. 做法是在这个 k 桶中随机选一个 Key 执行节点查找.

2.5.2 节点加入

一个新节点 $n$ 要想加入 Kademlia, 它首先使用一些算法生成自己的 ID, 然后它需要通过一些外部手段获取到系统中的任意一个节点 $n^{'}$ , 把 $n^{'}$ 加入到合适的 k 桶中. 然后对自己的 ID 执行一次节点查找. 根据上述的 k 桶维护机制, 在查找的过程中新节点 $n$ 就能自动构建好自己的 k 桶, 同时把自己插入到其他合适节点的 k 桶中, 而无需其他操作.

节点加入时除了构建 k 桶之外, 还应该取回这个节点应负责的资源. Kademlia 的做法是每隔一段时间(例如一个小时), 所有的节点都对其拥有的资源执行一次发布操作; 此外每隔一段时间(例如24小时)节点就会丢弃这段时间内未收到发布消息的资源. 这样新节点就能收到自己须负责的资源, 同时资源总能保持被 k 个距离它最近的节点负责.

如果每个小时所有节点都重发它们所拥有的资源, 就有些浪费了. 为了优化这一点, 当一个节点收到一个资源的发布消息, 它就不会在下一个小时重发它. 因为当一个节点收到一个资源的发布消息, 它就可以认为有 k - 1 个其他节点也收到了这个资源的发布消息. 只要节点重发资源的节奏不一致, 这就能保证每个资源都始终只有一个节点在重发.

2.5.3 节点失效和离开

有了上述 k 桶维护和资源重发机制, 我们不需要为节点的失效和离开做任何其它的工作. 这也是 Kademlia 算法的巧妙之处, 它的容错性要高于其他分布式哈希表算法.

2.6 协议消息

Kademlia协议共有四种消息。

PING消息—用来测试节点是否仍然在线。
STORE消息—在某个节点中存储一个键值对。
FIND_NODE消息—消息请求的接收者将返回自己桶中离请求键值最近的K个节点。
FIND_VALUE消息，与FIND_NODE一样，不过当请求的接收者存有请求者所请求的键的时候，它将返回相应键的值。每一个RPC消息中都包含一个发起者加入的随机值，这一点确保响应消息在收到的时候能够与前面发送的请求消息匹配。

3. Coral DHT

3.1 基本元素

节点ID：NID(node identifier)，m位的一个数字（m要足够大以保证不同节点的NID相同的几率小的可以忽略不计），由节点机器的IP地址通过哈希操作得到。
资源ID：KID（key identifiers），原为键ID，其实际表示一个资源（因为Key与一个资源value哈希绑定），故在本文中统称资源ID（这样比较直观），m位的一个数字（m要足够大以保证不同资源的KID相同的几率小的可以忽略不计），由Key通过哈希操作得到。
常哈希函数：较之一般哈希函数，节点的加入和离开对整个系统影响最小，另外还有一些优势在此不赘述。在Chord中使用SHA-1来进行常哈希计算。
Chord环：Chord Ring，NID和KID被分配到一个大小为 $2^m$ 的环上，用于资源分配（给某一个节点）和节点分布，以及资源定位（注：在这个环上的ID为0– $2^{m-1}$ ）。首先我们说资源分配，资源被分配到NID>=KID的节点上，这个节点成为k的后继节点，是环上从k起顺时针方向的第一个节点，记为successor(k)。而节点分布则顺时针将节点N由大到小放在这个环上。例如下边这幅图：

看不懂的同学可以先看这一篇博客。
链接: 负载均衡——一致性哈希算法

3.2 Chord资源定位(Key Location)

3.2.1 简单的资源定位

考虑如下场景：假设我们要找KID=a的资源的所在位置，我们需要从当前节点N开始对比a是否大于N并且小于等于后继节点，如果是，则KID=a的资源在后继节点上。所以最坏的情况是在这个环上查找一圈，复杂度为节点的个数n。

3.2.2 可伸缩的资源定位算法

每个节点N都维护了最多m项(m为ID的位数)的路由表（称为finger table），用来定位资源。这个表的第i项是该节点偏移 $2^{i-1}$ 位子后的后继节点（>=该位置）。
在这里插入图片描述
节点N8的路由表中，左边那一栏包含了N8+1到N8+32（2^5-1）的位置，右边那一栏每个位置对应的实际存在的节点。比如N8+1-N14，表示在N8后的第一个位置上的资源由N14来负责。这样记录有以下优势：

每个节点只包含全网中一小部分节点的信息。
每个节点对于临近节点负责的位置知道的更多，比如N8节点对于N14负责的位置知道3处，而对N21负责的位置只知道1处。
路由表通常不包含直接找到后继节点的信息，往往需要询问其他节点来完成。
当在某个节点上查找资源时，首先判断其后继节点是不是就持有该资源，若没有则直接从该节点的路由表从最远处开始查找，看哪一项离持有资源的节点最近（发现后跳转），若没有则说明本节点自身就有要寻找的资源。如此迭代下去。

3.2.3 伸缩定位场景

考虑N8节点需要资源K54(该资源可能存在也可能不存在)。
在这里插入图片描述

首先判断其后继节点是不是持有该资源 $\in (NID,SNID]$
若没有：则从该节点的路由表的最远处开始查找，，看哪一项离持有资源的节点最近（发现后跳转）,查找 $\in (NID,KID]$ （发现后跳转，跳转到第一步）
若没有发现则说明本节点可能有要查询的资源

经证明，最多经过O(log N)次查找就能找到一个资源。

3.2 Chord的节点加入

3.2.1 基本操作

Chord通过在每个节点的后台周期性的进行stabilization询问后继节点的前序节点是不是自己来更新后继节点以及路由表中的项。
有下面几个操作：

join()，节点n想要加入时，调用join(n’)。其中 n’可以是任意节点，n’负责找到新节点 n 的直接后继节点。
stabilize(): 每个节点周期性地运行这个操作，以询问后继节点的前序节点是不是自己。
notify(): 如果 stabilize()过程中发现节点关系变化，则通过相邻节点做调整。
fix_fingers(): 修改路由表。
图 11 是原先的结构。
现在 N26 节点要加入系统，首先它指向其后继 N32，然后通知 N32，N32 接到通知后将 N26 标记为它的前序节点（predecessor）。如图 12 所示。
然后 N26 修改路由表，如图 13 所示。
下一次 N21 运行 stabilize()询问其后继节点 N32 的前序节点是不是还是自己，此时发现 N32 的前序节点已经是 N26，如图 14 所示。
于是 N21 就将后继节点修改为 N26，并通知 N26 自己已经将其设置为后继节点，N26 接到通知后将 N21 设置为自己的前序节点。

3.2.2 加入操作带来的影响：

1）、正确性方面：当一个节点加入系统，而一个查找发生在 stabilization 结束前，那么此时系统会有三个状态：
A、所有后继指针和路由表项都正确时：对正确性没有影响。
B、后继指针正确但表项不正确：查找结果正确，但速度稍慢（在目标节点和目标节点的后继处加入非常多个节点时）。
C、后继指针和路由表项都不正确：此时查找失败，Chord 上层的软件会发现数据查找失败，在一段时间后会进行重试。
总结一下：节点加入对数据查找没有影响。
2）、效率方面：当 stabilization 完成时，对查找效率的影响不会超过 O(log N) 的时间。当 stabilization 未完成时，在目标节点和目标节点的后继处加入非常多个节点时才会有性能影响。可以证明，只要路由表调整速度快于网络节点数量加倍的速度，性能就不受影响。

3.3 Chord 节点失败的处理

Chord 依赖后继指针的正确性以保证整个网络的正确性。但如图，若 N14, N21, N32 同时失效，那么 N8 是不会知道 N38 是它新的后继节点。为了防止这样的情况，每个节点都包含一个大小为 r 的后继节点列表，一个后继节点失效了就依次尝试列表中的其他后继节点。可以证明，在失效几率为 1/2 的网络中，寻找后继的时间为 O(log N) 。

3.4 Consistent Hashing 和 DHT 的区别

分布式哈希（DHT）和一致性哈希（Consistent Hashing）的区别

分布式哈希: 将哈希表分散在不同的节点上，并且提供相应的方法来查找。
一致性哈希: 当节点宕机或者扩容的时候，需要重新哈希，一致性哈希实现的 DHT 避免对大量的数据重新哈希（如 Chord 算法就是一种一致性哈希算法），所以一致性哈希是 DHT 的一种实现。