Vite P2P网络协议简介



  • 1.png
    作者

    今天的技术分享来自Vite资深Web开发Jerry君,他曾任职于小米等一线互联网公司,具有丰富的web开发经验;Jerry君今天要跟我们聊一聊Vite的P2P网络。

    简介

    P2P 是 peer-to-peer 的简写,一般称为对等网络。有别于传统的 C/S 架构,P2P有以下特点:

    没有统一的调度中心和数据库,即去中心化。

    节点具有相同的逻辑和地位1,既是 client 又是 server。

    节点之间的连接是不可靠的。

    C/S 架构undefined
    2.png
    P2P 架构undefined
    3.png
    去中心化的区块链底层网络模型正适合采用 P2P 架构。

    [1] 节点具有相同的逻辑是指在网络层面,应用层面当然是可以区分的,比如全节点、轻节点等。

    结构化模型与 DHT

    因为 P2P 网络是去中心化的,并没有集中的数据库,节点可以随时加入和离开。如何快速有效的定位某个资源就成了核心问题,即:内容路由。

    针对这个问题,P2P 的网络模型经过了一些演化:集中式、纯分布式、混合式、结构化2。

    集中式使用集中索引、分布存储,强依赖索引服务器,可靠性不够高。

    纯分布式节点与资源随机分布、无序,容易形成洪泛和消息风暴。

    混合式采用超级节点和普通节点结合,较为依赖超级节点。

    结构化 P2P 网络一般基于分布式哈希表(DHT, Distributed Hash Table),对资源进行 hash 得到资源 ObjectID,每个网络节点分配一个 NodeID。理想情况下 ObjectID 与 NodeID 一一对应,资源 i 存储在节点 i 上3。这样的话,节点 n 查询资源 i 时可以直接请求节点 i 。

    或者可以根据 ID 进行某种规则排序,节点 n 如果没有节点 i 的信息,可以先请求节点 i 的邻居节点,这样也会减少路由跳数,提高效率。

    结构化模型中,节点和资源进行了映射和划分,不再是随机分配,所以负载更加均衡、扩展性也更好。

    [2] 网络模型参考:

    https://en.wikipedia.org/wiki/Peer-to-peer

    [3] 实际可用将资源存储在节点及其邻居节点上,提高资源冗余性。

    KAD

    DHT 只是一种思想,基于这种思想有很多种具体实现: Chord4 Pastry5 CAN6 KAD7 等。

    Vite 采用的是 KAD 算法,这也是目前主流的 DHT 算法。使用可配置的 ED25519 加密公钥作为 NodeID。

    [4] Chord 参考:

    https://en.wikipedia.org/wiki/Chord_(peer-to-peer)

    [5] Pastry 参考:

    http://www.freepastry.org/PAST/overview.pdf

    [6] CAN paper:

    http://www.icir.org/sylvia/thesis.ps

    [7] Kademlia paper:

    https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf

    KAD 算法要点如下:

    使用 XOR 计算两个 NodeID 之间的距离(逻辑距离,而不是物理距离)

    每个节点保存 N 个 K-bucket,N 是 NodeID 的 bit 位数,K 可以自行调整。第 i 个 K-bucket 内的节点与当前节点的距离介于 2i 和 2i+1。
    4.png
    所有的节点分配到 N 个子树内,从每棵子树内挑选 K 个节点存放到对应的 K 桶内。

    当节点 A 请求资源 i 时,假如 A XOR i 等于 d。那么 A 就从第 log2d 个 K 桶内查找,如果有节点 i,就直接向节点 i 请求资源 i。

    如果没有节点 i,那么可以并发的向这 K 个节点查询节点 i。这 K 个节点将自己的 K-bucket 内距离节点 i 最近的 K 个节点返回给 A,从而一步步锁定节点 i 的位置。

    可见 KAD 路由的算法复杂度是 O(log n)。

    KAD 总结

    KAD 相比 Chord 等算法有以下优点:

    实现简单。

    足够灵活(N K 并发请求数都可调整)。

    扩展性容错性好。

    实际应用中还是要适当调整的,比如 Vite 节点 ID 的长度是 256,但是 K-bucket 数少于 256。

    节点通讯

    节点之间的消息有以下 4 种:

    PING 测试一个节点是否在线。

    STORE 要求节点存储数据。

    FIND_NODE 查询某个节点。

    FIND_VALUE 查询某个资源,同 find_node。

    目前并没有 STORE 的需求,所以 vite 内最常用的是 PING 和 FIND_NODE。

    节点发现

    一个 Vite 新节点启动时,会向配置的 bootnodes 查询自己的位置。再向 bootnodes 返回的节点查询自己的位置。如此循环往复,直到没有更近的节点返回。如此就构建了自己的 K-buckets。

    节点维护

    由于节点在频繁的变动中,KAD 采用如下策略维护 K-bucket。

    1、每个 bucket 内的节点按照最近联系的时间倒序排列,最近通讯的节点在最后面。

    2、当一个节点与自己通讯时,检查对方是否在 bucket 内。

    如果存在,那么将其移动到 bucket 尾部。

    如果不存在,且 bucket 没有满,则放到 bucket 头部。

    如果不存在,bucket 已满,则 PING 当前 bucket 的头结点(最久没有联系)。PING 通则抛弃新节点,PING 不通则使用新节点替换该头结点。

    这个策略保证了结点的及时更新,并且越常在线的节点越不容易被替换,网络也相对稳定。

    总结

    Vite 的底层 P2P 网络采用的是相对主流的方案,在此之上构建了 Vite 的通讯协议(比如交易、区块的广播,节点同步等)。

    欢迎大家review我们的代码,也请关注我们的后续文章,谢谢支持。

    github代码库::https://github.com/vitelabs/go-vite

    #公链黑马,代码说话#

    (三)


    请通过Vite官方渠道了解最新动态:

    官网:https://www.vite.org/

    Twitter:https://twitter.com/vitelabs
    本文转发链接:https://www.jinse.com/bitcoin/225747.html
    ViteX交易所挖矿!使用邀请码:3651387503 ,可挖矿手续费九折、降低上币挖矿费用等福利。Vite APP下载: https://app.vite.net/
    实时查看挖矿及分红情况(官网):https://vitex.net/


Log in to reply
 

Suggested Topics