分布式哈希和一致性哈希是分布式存储和p2p网络中说的比较多的两个概念了。介绍的论文很多,这里做一个入门性质的介绍。
分布式哈希(DHT)
两个key point:每个节点只维护一部分路由;每个节点只存储一部分数据。从而实现整个网络中的寻址和存储。
DHT只是一个概念,提出了这样一种网络模型。并且说明它是对分布式存储很有好处的。但具体怎么实现,并不是DHT的范畴。
一致性哈希:
DHT的一种实现。本质还是一个哈希算法。回想平时我们做负载均衡,按querystring签名对后端节点取模是最简单也是最常用的算法,但节点的增删后所造成的问题显而易见,原有的请求几乎都落不到同一台机器上。优化一点的是carp算法(用机器ip和querystring一起做hash,选取hash值最小的一台),只让1/n的数据受到影响。
一致性哈希,似乎最早提出是在分布式cache里面的,让节点震荡的时候,影响最小,以提高分布式cache的命中率。不过现在更多的应用在分布式存储和p2p系统里面。
一致性哈希也只是提出四个概念和原则,并没有提及具体实现:
1、balance:哈希结果尽可能的平均分散到各个节点上,使得每个节点都能得到充分利用。
2、Monotonicity:上面也说了,如果是用签名取模算法,节点变更会使得整个网络的映射关系更改。如果是carp,会使得1/n的映射关系更改。一致性哈希的目标,是节点变更,不会改变网络的映射关系。
3、spread:同一份数据,存储到不同的节点上,换言之就是系统冗余。一致性哈希致力于降低系统冗度。
4、load:负载分散,和balance其实是差不多的意思,不过这里更多是指数据存储的均衡,balance是指访的均衡。
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是必须的。
下图简单描述了一个chord网络的部署,绿色节点为机器,编码为hash值。N0节点的finger表可以看出N0节点的路由规则,其他节点也有类似的finger表。蓝色节点为数据,根据hash值找到最近的节点并存储。虚线所指是表示冗余存储。
查询:先从自己的路由表中,找一个和数据id距离最近、并且存活在网络中的节点next。如果该节点的 id巧合和数据id相等,那么恭喜你。如果不相等,则到next进行递归查找。一般或需要经过多次查询才能找到数据所在的节点,而这个次数是可以被证明小于等于log2N的。
在这个查询的过程中就体现了路由表的选取优势了,其实是实现了一个二分查找,从每个节点来观察网络,都是将网络分成了log2N块,最大一块里面有N/2个节点。路由表里面其实是记录了每一块的第一个节点。这样每一次查询,最少排除了一半的节点。保证在 log2N次内找到目标节点。
下图简单展示了从N0节点查找N21节点的一个数据的过程,通过finger表经过2跳到达目的地。
新增一个节点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这种节点变更频繁的网络中快速找到有效的节点。
关于kad的介绍,这篇文章讲的比较详细wenku.baidu.com/view/ee91580216fc700abb68fcae.html
相关推荐
1. 基础知识 3 2. 环的原子管理算法 4 3. 路由算法 10 4. 组通信算法 15 5. 副本管理算法 17 6. 分布式哈希表的应用 21 1. 基
分布式哈希表技术(Distributed Hash Table)简称DHT,类似Tracker的根据种子特征码返回种子信息的网络.是一种分布式存储方法。
一个加密的IPv6网络,使用公钥密码术进行地址分配,并使用分布式哈希表进行路由。.zip
一个简单的分布式哈希表 概述 在这个项目中,您将使用Python(或您选择的语言)实现分布式哈希表。 哈希表将分布在多个进程中,并将通过HTTP API公开其所有公共功能。 进程可以使用您选择的协议相互通信。 哈希表的...
如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中,哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区
Hashtopolis Hashtopolis是一种用于将hashcat任务分发到多台计算机的多平台客户端-服务器工具。 Hashtopolis发展的主要目标是可移植性,健壮性,多用户支持和多组管理。 该应用程序包含两个部分: 代理多个客户端...
#分布式哈希表 此应用程序支持所有 DHT 功能并支持插入和查询操作。 因此,如果我们运行应用程序的多个实例,所有内容提供者实例都会形成一个 Chord 环,并根据 Chord 协议以分布式方式提供插入/查询请求。 实现了...
本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及 其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题 场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接...
随着虚拟节点的增加,数据量分配就比较平均了,但是并不是虚拟节点数量越多就越好,因为要考虑这些虚拟节点带来的性能开销以及算法的复杂性;
* 有两种方案,第一种普通hash分布,第二种一致性哈希分布 * * 普通hash分布 * 首先将key处理为一个32位字符串,取前8位,在经过hash计算处理成整数并返回,然后映射到其中一台服务器 * $servers[$this->...
现在的分布式P2P系统普遍采取的是DHT(distributed hash table,分布式哈希表)搜索方法。基于DHT的P2P网络搜索算法的研究已经是P2P研究的一个热点。从P2P定义出发,介绍了P2P网络按照拓扑结构的分类发展;然后深入...
#fly-archflylib创立的各种常见的架构技术内容列表cassandra-demo cassandra数据库的入门编程consistent-hash Java implementation of consistent-hashing基于java的一致性hash的实现一致性hash(consistent-hashing)...
一致性哈希算法,广泛应用于分布式计算,C版实现,属于分布式服务器管理的核心算法。
ufire-springcloud-platform 学习微服-基于一致性哈希算法实现websocket分布式扩展的尝试。
分布式哈希表(distributed hash table,缩写DHT)是分布式计算系统中的一类,用来将一个键(key)的集合分散到所有在分布式系统中的节点。这里的节点类似哈希表中的存储位置。分布式哈希表通常是为了拥有大量节点的...
MeshMap是P2P分布式哈希图的基于Java的实现。 服务发现是开箱即用的,但易于扩展为具有自己的服务发现机制的应用程序。 MeshMap的目标是提供一种简单的API,该API具有地图数据结构的所有功能,并且数据分布在集群中...
关于分布式散列表DHT的前世今生的故事:包括单机hash、分布式一致性hash
Redis哈希 redis-hashring是一个Python库,该库实现了用于构建分布式应用程序的一致哈希环,该哈希环存储在Redis中。问题假设您要构建一个负责同步帐户的分布式应用程序。 帐户可以连续保持同步,例如保持连接打开...
一致性哈希(Consistenthash)很好的解决了这个问题,当节点发生变化时,只会影响到部分数据,而且永远可以找到一个提供服务的节点。对于数据库Sharding的架构,Consistenthash并不十分适合,我们采用了一种新的hash...
wendy, 一种Hash分布哈希表的纯去实现 Wendy一个开源,pure- ,实现了Pastry分布式哈希表的 。状态 :Wendy仍处于积极发展状态。 它不应该用于任务关键软件。 它已经经被拍了一点,但可以能仍然有 Bug,我们还没有...