写点什么

联联周边游系统源码

用户头像
Geek_a620db
关注
发布于: 2020 年 12 月 28 日
联联周边游系统源码

死磕以太坊源码分析之 Kademlia 算法

  • Kademlia

死磕以太坊源码分析之 Kademlia 算法

死磕以太坊源码分析之 Kademlia 算法

KAD 算法概述

Kademlia 是一种点对点分布式哈希表(DHT),它在容易出错的环境中也具有可证明的一致性和性能。使用一种基于异或指标的拓扑结构来路由查询和定位节点,这简化了算法并有助于证明。该拓扑结构有一个特点:每次消息交换都能够传递或强化有效信息。系统利用这些信息进行并发的异步查询,可以容忍节点故障,并且故障不会导致用户超时。

KAD 算法要处理的问题

  1. 如何分配存储内容到各个节点,新增/删除内容如何处理

  2. 如何找到存储文件的节点/地址/路径

节点状态

节点的基本属性包括如下:

  • 节点 ID,Node ID

  • 节点 IP 地址与端口号

在 Kad 网络中,所有节点都被当作一颗二叉树的叶子,并且每一个节点的位置都由其 ID 值的最短前缀唯一的确定。

对于任意一个节点,都可以把这颗二叉树分解为一系列连续的,不包含自己的子树。最高层的子树,由整颗树不包含自己的树的另一半组成;下一层子树由剩下部分不包含自己的一半组成;依此类推,直到分割完整颗树。图 1 就展示了节点 0011 如何进行子树的划分:



虚线包含的部分就是各子树,由上到下各层的前缀分别为 0,01,000,0010。

Kad 协议确保每个节点知道其各子树的至少一个节点,只要这些子树非空。在这个前提下,每个节点都可以通过 ID 值来找到任何一个节点。这个路由的过程是通过所谓的 XOR(异或)距离得到的。

图 2 就演示了节点 0011 如何通过连续查询来找到节点 1110 的。节点 0011 通过在逐步底层的子树间不断学习并查询最佳节点,获得了越来越接近的节点,最终收敛到目标节点上。



需要说明的是:只有第一步查询的节点 101,是节点 0011 已经知道的,后面各步查询的节点,都是由上一步查询返回的更接近目标的节点,这是一个递归操作的过程


用户头像

Geek_a620db

关注

app系统定制开发TV18200808116 2020.12.26 加入

还未添加个人简介

评论

发布
暂无评论
联联周边游系统源码