分布式哈希表常用在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)”

Merkle Tree简介

Merkle Tree实际上就是 树+Hash,具有树的性质,树的每个节点都是Hash值。Merkle Tree有以下特点:

  1. Merkle Tree可以是二叉树,也可以是多叉树,不管是什么树,它都具有树结构的所有特点。
  2. Merkel Tree的叶子节点的Value是数据集合的单元数据 或 单元数据的Hash值。
  3. Merkel Tree所有非叶子节点的Value是所有子节点Value的Hash值。

Merkle Tree的应用

Merkel Tree多用在数据验证,其中最有名的应用领域可能就属加密货币了。矿机在挖矿实际上就是在运算一组复杂的公式:

SHA256(SHA256(version + prevHash + merkleRoot + time + currentDifficulty + nonce )) < TARGET

这里不必深究公式的意义,只需要关注其中的一个“merkleRoot”参数,这个“merkleRoot”就是Merkle Tree的根节点的值。想要算出根节点的值,必须要从叶子节点出发(在加密货币中,叶子节点通常为各区块内从n个交易提取的n个Hash值),最后由根节点的两个子节点的Hash计算出根节点的Hash。这只是挖矿的一个小环节。

Merkle Tree的实现

Continue reading “Merkle Tree及其实现”