分布式原理：Chord协议

根据前几章的内容，我们发现如果用gossip协议找信息，或者用multicast的方法找，找到了一个地址之后，我们再次定位就应该换种方法，起码不应该再用multicast或者gossip了，我们需要一个更高效的方法

Chord协议

主要内容是一致性哈希，下面是他的成绩

如何操作呢？

首先，我们假设手上有个n个node的network，我们先定义一个哈希环，大概是 $2^m$ 个点吧

然后，我们先把这些node的（IP+port）变成字符串然后取hash值，拿到一串数字，用这个数字mod $2^m$ ，拿到的数字就放在环上相应的位置。（此处记住这个m，后面要考）

这样我们就能建立一个完备的哈希环。Successor – first node clockwise

在我们眼中是个哈希环，但这一切都是虚拟的，在每个主机处它眼中就只有前后的连接。于是我们需要高效查找需要维护一个finger table

前面的m就用到了，m是多少，就在每个node处维护多少个finger

并且我们有

如何根据finger table查找呢？

首先，我们假设蓝色的线，也就是去找28问12的资源在哪里，看28的finger table，找到比他小的最大的数，是4，就去4问，看一下4，比12小的最大的数是9，又跑到9去问，一看9，就去11问，到了11，发现没有比他小的数，那就在此处最小的数节点处！

再来看一个红色的线，找1号问26号资源在哪，它首先给你带到了18，然后问18，给你带到了20，然后到20，给你带到了21，到了21发现没有比他小的了，那就在28!

写成代码就是：

def getNfingerTable(N)

def search(k,NfingerTable):
    biggest = 0
    for i,finger in NfingerTable:
        if finger <= k :
            biggest = k
            continue
        else:
            if biggest = 0:
                return NfingerTable[1]
            else:
                return search(k,getNfingerTable(biggest))

下面再来说说node如何加入：

每次有node加入的时候，整个网络的finger table都需要更新，因此Nodes run a stabilization protocol to keep successor/finger entries up to date