Vite P2P网络协议简介

Vite P2P网络协议简介

作者

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

简介

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

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

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

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

C/S 架构undefined

Vite P2P网络协议简介

P2P 架构undefined

Vite P2P网络协议简介

去中心化的区块链底层网络模型正适合采用 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。

Vite P2P网络协议简介

所有的节点分配到 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

Discord:https://discordapp.com/invite/CsVY76q

Telegram:https://t.me/vite_zh

文章作者: ViteLabs 我要纠错
声明:本文由入驻金色财经的作者撰写,观点仅代表作者本人,绝不代表金色财经赞同其观点或证实其描述。
提示:投资有风险,入市须谨慎。本资讯不作为投资理财建议。

金色财经 > 区块链 > Vite P2P网络协议简介