分布式哈希表常用在P2P网络中,如常见的BitTorrent。而Kademlia算法是要解决在网络中的寻找节点问题。

分布式哈希表(Distributed Hash Table)

在介绍Kademlia之前有必要熟悉一下DHT。

分布式哈希表就是将文件的哈希表存储在多个节点中,每个节点存储一部分文件的同时维护一个路由表,即每个节点包含:

  • Hash key(文件哈希值)
  • Hash Value(文件的一部分)
  • 路由表(在kademlia算法中称为k-bucket)

这些节点相互连接组成网络:

具体到P2P的文件共享中,假如要分享1G的电影,可以将1G的文件分割为128KB的小块,并生成小块的哈希值。

分布式哈希表实际上是P2P共享发展史上的第三种技术路线,前两代都存在一定的问题,简单介绍一下:

  1. 第一代 Tracker服务器
    • 这种模式下,文件块是分发到各个节点上的,但是每个节点在获取其他节点的位置时需要连接中央服务器。
    • 这种情况下中央服务器就成为了单点故障,一旦中央服务器出现故障或者被不可抗力ban掉后整个网络就无法运行
  2. 第二代
    • 在看到第一代的不足后,第二代P2P在查找节点时会询问与自身相连的所有节点,如果周边节点不知道目标节点的位置,又回广播一遍查询信息,直到找到目标节点。
    • 显然这种情况很容易催生广播风暴,严重占用网络带宽。即使通过设定TTL、限制查询递归次数也无法解决这个问题。

Kademlia算法

首先声明算法的三个参数:

  1. keyspace
    • 节点ID的位数,默认是160位
    • 决定每个节点的路由表(k-bucket)有几层
  2. k *重要*
    • 路由表里的每层存储k个信息
    • 每次查询时返回k个信息
    • 存储文件时,将文件存储到k个节点
    • 默认值为8
  3. α
    • 向其他节点查询目标节点时,每次向α个节点发送请求

Continue reading “Kademlia算法与分布式哈希表(DHT)”

关于最小生成树以及Prim算法参考上一篇:最小生成树MST 之 Prim及其实现

Kruskal算法

Kruskal算法实际上是 贪心+并查集,贪心用来查找权值最小的边,并查集来检测顶点的连通性(关于并查集不再详述)。

不同于Prim算法,Kruskal不是面向顶点来生成MST的,Kruskal只考察边集,只看当前最小权值的边,所以需要并查集来检测顶点连通的状态(Prim通过已连通的顶点来选择权值最小的边,而Kruskal先去掉所有的点,在总边集中找最小的边)。

Kruskal算法的步骤:

  1. 将边集内的边按权值大小升序排序。
  2. 依次考察每条边,如果边的两顶点不同源(至少有一点未被访问),则将此边纳入生成树。
  3. 执行步骤2,直到每一个点都被访问。

从步骤中可以看出,Kruskal的性能取决于排序算法,需要选择合适的排序算法。

Kruskal的实现(Python)

  • 随机生成5×5-9×9的图(邻接矩阵)
  • 排序使用python自带的sorted()方法
  • 输出访问顺序和总开销
import random, time
father = []
MAX_DISTANCE = 100  # 边的最大权值


def create_map():  # 生成图(邻接矩阵)
    map = []
    size = random.randint(5, 9)
    print("图大小:", size)
    
    for i in range(size):
        row = []
        for j in range(size):
            row.append(random.randint(1, MAX_DISTANCE))
        map.append(row)
    
    print("生成图:")
    for i in range(size):
        print(map[i])
    
    return map


def get_edges(map):
    edges = []
    for i in range(len(map)):
        for j in range(len(map)):
            edges.append([i, j, map[i][j]])
    return len(map), len(edges), edges


def find(n):  # 查找顶点的父亲顶点
    if father[n] == n:
        return n
    father[n] = find(father[n])
    return father[n]


def union(map_size, edge_size, edges):
    global father
    father = [i for i in range(map_size)]  # 并查集,初始情况下顶点的源点为自身
    tol_distance = 0  # 总开销
    visit_order = []  # 记录访问顺序
    
    for i in range(edge_size):
        node1 = find(edges[i][0])  # 边的一个顶点的源点
        node2 = find(edges[i][1])  # 边的令一个顶点的源点
        if node1 != node2:  # 不同源
            visit_order.append(edges[i])
            tol_distance += edges[i][2]
            father[node2] = node1  # 合并,将两顶点的源点合并为一个
            
    return visit_order, tol_distance
    

def kruskal(map_size, edge_size, edges):
    edges = sorted(edges, key=lambda x: x[2])  # 对边进行权值的升序排序
    return union(map_size, edge_size, edges)


def main():
    map_size, edge_size, edges = get_edges(create_map())
    visit_order, tol_distance = kruskal(map_size, edge_size, edges)

    print("访问顺序:[顶点, 顶点, 权值]")
    for each in visit_order:
        print(each)

    print("总开销:", tol_distance)

    
if __name__ == "__main__":
    main()

Continue reading “最小生成树MST 之 Kruskal及其实现”

昨天突然想不起来并查集的名字,忽觉忘记的有点多,于是决定复习一下各种算法。

问题引入

要在n个城市之间铺设光缆,主要目标是要使这 n 个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

将城市抽象为点,光缆抽象为边,费用抽象为权值,就可以绘制一幅连通加权无向图

类似的还有修路,建桥等问题,抽象出来都属于最小生成树。

最小生成树简介

最小生成树是一副连通加权无向图中一棵权值最小的生成树。

在一给定的无向图 G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即 {\displaystyle (u,v)\in E}),而 w(u, v) 代表此边的权重,若存在 T 为 E 的子集(即 {\displaystyle T\subseteq E})且 (V, T) 为树,使得

的 w(T) 最小,则此 T 为 G 的最小生成树

最小生成树其实是最小权重生成树的简称。

一个连通图可能有多个生成树。当图中的边具有权值时,总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言,对于非连通无向图来说,它的每一连通分量同样有最小生成树,它们的并被称为最小生成森林

以有线电视电缆的架设为例,若只能沿着街道布线,则以街道为边,而路口为顶点,其中必然有一最小生成树能使布线成本最低

来自 最小生成树 – 维基百科

Prim算法

与之齐名的还有Kruskal算法,相比之下,Prim是从图中的顶点出发,而Kruskal更注重图中的边。

不管是Prim还是Kruskal,其核心都是贪心——寻找当前状态下最小权值的边。

算法步骤:

  1. 从一个顶点出发。
  2. 查找与已连接顶点相连的边权值最小的边。
  3. 通过此边连接对应顶点。
  4. 重复2、3步骤,直到连接所有顶点。

Continue reading “最小生成树MST 之 Prim及其实现”