什么是区块链:去中心化网络DHT介绍

  DHT可以译作分布式哈希表,是P2P网络进化中最为重要的环节,它解决了以往需要中心化服务器才能实现的资源发现问题,通过DHT网络模型P2P可以自行组网实现去中心化网络。以前有人问区块链节点是怎么互联的,这篇文章可以解答了

  DHT全称叫分布式哈希表(Distributed Hash Table),是一种分布式网络模型。在不需要服务器的情况下,每个客户端负责一个小范围的路由,并负责存储一小部分数据,从而实现整个DHT网络的寻址和存储。在区块链世界中,利用DHT可以实现众多节点的网络发现,实现各个节点在去中心化场景中的互联,DHT是非常重要的P2P网络技术之一。

  DHT定义

  DHT是分布式计算系统中的一类,用来将一个关键值(key)的集合分散到所有在分散式系统中的节点,并且可以有效地将消息转送到唯一一个拥有查询者提供的关键值的节点(Peers)。

  这里的节点类似散列表中的存储位置。分布式散列表通常是为了拥有极大节点数量的系统,而且在系统的节点常常会加入或离开(例如网络断线)而设计的。在一个结构性的延展网络(overlay network)中,参加的节点需要与系统中一小部分的节点沟通,这也需要使用分布式散列表。分布式散列表可以用以创建更复杂的服务,例如分布式文件系统、点对点技术文件分享系统、合作的网页缓存、多播、任播、域名系统以及实时通信等。

  分布式散列表本质上强调以下特性:

  离散性:构成系统的节点并没有任何中央式的协调机制。

  伸缩性:即使有成千上万个节点,系统仍然应该十分有效率。

  容错性:即使节点不断地加入、离开或是停止工作,系统仍然必须达到一定的可靠度。

  DHT原理

  DHT是P2P网络(结构化P2P)核心路由算法,主要是利用一致性hash,把节点和资源都表示成一个hash值,放入到这个大的hash环中,每个节点负责路由靠近它的资源。

  重要概念

  node:负责P2P路由信息,P2P网络的组网就是它来负责

  peer:负责管理资源,生成种子文件,发布资源信息

  nodeid:节点的唯一标识,是一个160bit的hash值

  infohash:资源的唯一标识,也是一个160bit的hash值,其和nodeid使用同一个算法

  距离:距离是两个hash值进行异或(XOR)操作后的值,值越小,距离越近

  节点和资源的距离: nodeid XOR infohash

  两个节点之间的距离:nodeid1 xor nodeid2

  种子文件:对某个资源的描述文件,种子文件包括了资源的infohash(160bit)、资源所在机器(nodeId IP PORT)、离资源所在机器最近的N个机器(nodeid IP PORT)列表

  典型场景

  1.新节点加入网络

  新安装的P2P客户端是一个孤立的节点,和其他节点都无联系,怎么加入P2P网络呢?需要有一个种子文件,种子文件中有多个该P2P网络中的node信息,根据种子文件中的节点列表,连接到P2P网络,并获取路由信息,获取最靠近本新节点的节点列表

  2.发布资源

  生成资源的Infohash,查找和infohash距离最近的N个Node,向这N个node广播新资源信息,告诉这些节点,我有某某资源,节点生成了资源,不过其路由信息不在这个节点上(也不在离这个节点的最近的M节点上),而是在和资源infohash最近的N个node上

  3.查找某个资源

  找到最靠近资源的N个node(使用nodeid xor infohash来计算距离远近),向这些node发送资源查询信息,如果有这个资源的详细信息,就返回给客户端,否则返回离资源更近的node列表给客户端,直到查询到资源提供者信息,如果没查到信息,且没有更近的node了,那就说明这个资源没有提供者,如果找到node信息(nodeid,ip,port)后,向这个node请求资源

  典型DHT实现介绍

  实现DHT的技术有很多种,常见的有:Chord, Pastry, Kademlia等。我们熟知的BT及BT的衍生派(Mainline, Btspilits, Btcomet, uTorrent…),eMule及eMule各类Mods(verycd, easy emules, xtreme…)等P2P文件分享软件都是基于该算法来实现DHT网络的,BT采用Python的Kademlia实现叫作khashmir,eMule采用C++的Kademlia实现干脆就叫作Kad,当然它们之间有些差别,但基础都是Kademlia。

  Chord算法:

  chord算是最为经典的实现。cassandra中的DHT,基本是chord的简化版。网络中每个节点分配一个唯一id,可以通过机器的mac地址做sha1,是网络发现的基础。

  假设整个网络有N 个节点,并且网络是呈环状。两个节点间的距离定义为每个节点会存储一张路由表(finger表),表内顺时针按照离本节点2、4、8、16、32.……2i的距离选定log2N个其他节点的ip信息来记录。

  存储方面:数据被按一定规则切割,每一份数据也有一个独立id(查询key),并且和节点id的值域是一样的。然后查找节点,如果存在和数据id一样的节点id,则将这份数据存在该节点上;如果不存在,则存储到离该数据id距离最近的节点上。同时,为了保证数 据的可靠性,会顺时针往下找K个冗余节点,存储这份数据。一般认为K=3是必须的。

  查询方面:先从自己的路由表中,找一个和数据id距离最近、并且存活在网络中的节点next。如果该节点的 id巧合和数据id相等,那么恭喜你。如果不相等,则到next进行递归查找。一般或需要经过多次查询才能找到数据所在的节点,而这个次数是可以被证明小 于等于log2N的。

  在这个查询的过程中就体现了路由表的选取优势了,其实是实现了一个二分查找,从每个节点来观察网络,都是将网络分成了log2N块,最大一块里面有N/2个节点。路由表里面其实是记录了每一块的第一个节点。这样每一次查询,最少排除了一半的节点。保证在 log2N次内找到目标节点。

  新增一个节点i,需要预先知道网络中已经存活的一个节点j,然后通过和节点j交互,更新自己和其他节点的路由表。并且,需要将离自己距离最近的节点中的数据copy过来,以提供数据服务。

  损失一个节点,路由算法会自动跳过这个节点,并且依靠数据的冗余来持续提供服务。

  KAD算法(Kademlia)

  kad算法其实是在chord上做的优化。主要是两个点:

  1、用二进制(32/64/128)表示一个节点的id,两节点的id异或运算得到节点间的距离。

  2、 每个节点保持的路由信息更丰富,同样是将整个网络按照划分成log2N份,在chord中,是保持log2N个路由节点,但在kad里面,是保存了 log2N个队列。每个队列长度为配置值K,记录网络中对应节点区域的多个节点,并且根据活跃时间对这些节点进行换入换出。

  第一点是方便进行网络划分,节点按照二进制中每一bit的0或1建成一棵二叉树。

  第二点是使得节点查询更迅速。从分割情况我们就可以得知,最坏情况不会差于chord,但保存更多的节点使得命中概率更高。另外队列中根据活跃时间进行换入换出,更有利于在p2p这种节点变更频繁的网络中快速找到有效的节点。

  来源:区块链大师 微信号 DACMaster

文章内容系本站作者个人观点,不代表本站对其观点赞同或支持,文章的版权归该作者所有。如需转载,请注明文章来源。本文地址:http://www.cis.net.cn/kejikuaixun/44235.html
留言与评论(共有 条评论)
验证码:

最新文章

去中心化网络DHT介绍

科技快讯
DHT可以译作分布式哈希表,是P2P网络进化中最为重要的环节,它解决了以往需要中心化服务器才能实现的资源发现问题,通过DHT网络模型P2P可以自行组网实现去中心化网络。以前有人问区块链节点是怎么互联的,这篇文章可以解答了DHT全称叫分布式哈希表(DistributedHashTable),是一种分布式网络模型。在不需

区块链与实体(区块链和实体怎么结合)

科技快讯
9月28日,中国在海南生态软件园举行主题为“链接产业,赋能实体”的战略发布会,会上正式宣布火币中国总部落户海南。火币中国将抓住赋能实体经济的时势机遇,乘海南发展的春风,定位于“区块链+产业服务一站式平台”,下辖火币研究院、(中国)、火币Labs(中国)、火币英才、五大事业部,其中火币大学作为区块链行业的“黄埔军校”

王峰深夜十问薛蛮子,区块链让所有人都有机会干出BAT!

科技快讯
“3点钟无眠区块链群”最初由玉红在2月11日创立,玉红此前是360游戏的主要负责人,现在是SEEU&QYGAME创始人,后者曾推出了基于区块链的大型网络游戏《基本世界》。由于最初建群时是凌晨三点,故将其命名为3点钟无眠区块链群。春节七天,群里的人无心观看春晚,亦对于抢红包失去了兴趣,他们盯着群里快速变化的消

如何从Cryptoshuffle木马中保护自己的比特币?

科技快讯
俄罗斯的网络安全公司卡巴斯基实验室已经警告加密货币的所有者,即使在私人钱包里,他们的硬币也不安全。一种名为CryptoShuffler的新型木马,是通过在用户的剪贴板上替换钱夹地址来复制和粘贴用于传输的钱包数据,从而直接从用户的鼻子中盗取硬币。没有钱包是安全的,因为特洛伊利用计算机上的剪贴板功能。尽管网络研究人员认为这个

人民网:十余省发布指导意见布局区块链发展

科技快讯
区块链和基于区块链产生并发展起来的数字货币,是近年出现的新兴事物,已经有越来越多的人对其产生了兴趣,并加入到这个行业中。去年国内出台监管措施以后,这个行业将何去何从更是受到广泛关注。今天人民网的一篇文章似乎可以提供一个观察、分析的方向。01、多地下血本力争区块链之都,抢占发展机遇5月7日,一篇题为《二三线城市为争区块

谷歌DoubleClick广告服务遭挖矿恶意软件滥用

科技快讯
随着比特币和以太坊等加密货币价值的快速上涨,针对加密货币的网络攻击数量也在随之增加。黑客瞄准了几乎所有加密货币业务参与者,这包括加密货币交易所、加密货币钱包、ICO、DAO、矿业公司、虚拟私人服务器和托管服务等等。

清华大学五道口张晓燕学生(清华五道口金融学院张晓燕)

科技快讯
在当前,区块链是未来金融科技的底层技术已经成为一个基本共识。它具有一些独特的特征,改变了传统金融中的一些弱点。具体表现在:脱媒(dis-intermediation),也称非中介化,在金融市场上表现为扩宽直接融资渠道,降低融资成本;去中心化(decentralization),这是一种更为开放、扁平、平等的信息结构,通过分布式计算,点对点提高了交易效率,也使得交

迅雷网心成为中国区块链技术应用示范基地

科技快讯
9月8日,“2018中国新经济产业领袖峰会”在京召开,“新时代、新技术、新业态、新未来”峰会主题下,本次大会汇聚了国务院、工信部等政府部门首脑、国内顶级经济学家、行业领袖企业及人士,聚焦区块链技术等新技术主导的新经济时期。其中,迅雷旗下的网心科技作为中国区块链技术发展的领军企业,受邀出席

以太坊跌成这样,你真的了解它吗,以太坊为代表的智能合约平台

科技快讯
续前:第二个概念就是以太坊虚拟机EVM。在一个编程系统之上,通常会有一些编译和执行的虚拟机来去做支撑。JAVA有JVM,那么在以太坊里,也会有以太坊的虚拟机,可以执行任意复杂的算法代码。开发者可以使用现有的JavaScript或Python以及其他友好的编程语言,在以太坊上创造出自己想要的应用。第三个概念是智能合约(SmartContract)。智能合

TNCoin为投资者提供加密货币支持的房地产资产

科技快讯
位于田纳西州纳什维尔的房地产投资平台TNCoinLLC最近宣布成立该国首个房地产代币化资产基金之一。TNCoin将使用Stellar共识协议向投资者分发代币化股票,从而实现现代投资者喜爱的加密货币的便携性和可替代性。基金经理DelMazo绍说:“通过提供更稳定、证券化的选择,TNCoin正朝着加密货币的方向积极发展。”对于希望利用这种独特