`

分布式哈希表和一致性哈希

 
阅读更多

 

参考: http://apps.hi.baidu.com/share/detail/15756976

分布式哈希(DHT)
两个key point:每个节点只维护一部分路由;每个节点只存储一部分数据。从而实现整个网络中的寻址和存储。
DHT
只是一个概念,提出了这样一种网络模型。并且说明它是对分布式存储很有好处的。但具体怎么实现,并不是DHT的范畴。

一致性哈希:
DHT
的一种实现。本质还是一个哈希算法。回想平时我们做负载均衡,按querystring签名对后端节点取模是最简单也是最常用的算法,但节点的增删所造成的问题显而易见:原有的请求几乎都落不到同一台机器上。优化一点的是carp算法,只让1/n的数据受到影响。
一致性哈希,似乎最早提出是在分布式缓存里面的,让节点震荡的时候,影响最小。不过现在已经应用在分布式存储和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是必须的。

查询方面:先从自己的路由表中,找一个和数据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,记录网络中对应节点区域的多个节点,并且根据活跃时间对这些节点进行换入换出。
第一点是方便进行网络划分,节点按照二进制中每一bit01建成一棵二叉树。

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

关于kad的介绍,这篇文章讲的比较详细wenku.baidu.com/view/ee91580216fc700abb68fcae.html

 

分享到:
评论

相关推荐

    分布式哈希表 Pastry.zip

    分布式哈希表(Distributed Hash Table,DHT)是一种用于分布式系统中的数据存储技术,它将数据分散存储在多台独立的设备...Pastry 的设计和实现对于理解分布式系统、一致性哈希以及 Go 语言的应用有着重要的学习价值。

    哈希表-使用C++实现的分布式哈希表.zip

    在本压缩包中,我们关注的是使用C++实现的分布式哈希表,这是一种在多台计算机上分散存储数据的哈希表,它具有高可用性和可扩展性。 首先,让我们深入理解哈希表的基本原理。哈希函数是关键,它的任务是将任意长度...

    分布式哈希表(Distributed Hash Table DHT)1

    分布式哈希表(DHT,Distributed Hash Table)是一种用于分布式环境的数据存储技术,它将数据分布在网络中的多个节点上,以实现高效、可扩展的数据管理和检索。DHT的设计目标是提供一种全局一致性的哈希函数,使得...

    哈希表-使用Go实现的用于IB-Trust的分布式哈希表.zip

    在给定的压缩包文件中,“哈希表_使用Go实现的用于IB-Trust的分布式哈希表”可能是实现上述概念的一个具体项目。这个项目可能包含了DHT的实现代码,包括节点管理、路由算法、数据存储和一致性策略等部分。通过对该...

    基于分布式哈希表的分布式子空间聚类算法.pdf

    文章中提到的分布式系统、分布式开发、分布式哈希表和分布式表决等概念,都是现代分布式计算领域中的重要知识点。分布式系统涉及网络、计算机硬件、软件和数据等多方面的协同工作;分布式开发则强调跨网络、跨平台的...

    DHT-Android:使用 Android 群信应用实现的分布式哈希表

    分布式哈希表(DHT, Distributed Hash Table)是一种在分布式系统中存储和检索数据的数据结构,它通过将数据分散在多个节点上,实现了全局的键值对存储。DHT-Android 是一个专为 Android 平台设计的项目,旨在利用...

    FastDHT-分布式哈希系统

    通过阅读源码,你可以学习到如何实现分布式哈希表,以及如何与FastDFS集成进行文件去重。同时,了解系统的架构和设计模式也有助于你优化自己的分布式存储解决方案。 总之,FastDHT是一个强大的工具,为分布式环境下...

    和弦:在Go中实现的和弦分布式哈希表(DHT)

    分布式哈希表(DHT,Distributed Hash Table)是一种分布式数据存储系统,它将数据分散存储在网络中的多个节点上,从而实现数据的高效查找、存储和管理。在DHT中,每个节点负责一部分数据,通过特定的算法进行寻址,...

    基于一致性哈希算法的分布式数据库高效扩展方法研究.pdf

    一致性哈希算法最初由Karger等人提出,目的是解决分布式缓存的问题,它弥补了CARP的不足,并在P2P环境中发挥了DHT(分布式哈希表)的优势。在分布式数据库中,由于节点数量可能会增加或减少,原有的哈希算法可以确保...

    Distributed-Editing:使用Chord DHT(分布式哈希表)的对等并发富文本编辑平台

    Client.py:此文件使用弦环和n元树实现分布式哈希表(DHT)的两层覆盖网络。 它负责与其他节点进行通信。 使用以下代码在执行代码之前安装pyqt4:sudo apt-get install python-qt4 执行命令:索引服务器:python ...

    SimpleDht:Chord 基分布式哈希表 - 深入分布式系统

    分布式哈希表Chord常用于P2P网络、分布式数据库、内容分发网络(CDN)等场景,能够有效支持大规模数据的分布式存储和检索。 总的来说,“SimpleDht”项目提供了一个学习和研究Chord算法的实践平台,通过分析和修改...

    Socket-Project:分布式哈希表为多个客户端提供数据库管理功能

    总结,这个Socket-Project利用Java实现了分布式哈希表,通过Socket通信技术和一致性哈希算法,为多个客户端提供了高效的数据库管理服务。项目的具体实现细节,包括节点的加入、退出、数据查找、存储等操作,以及错误...

    一致性哈希与Chord1

    【一致性哈希与Chord1】是一篇关于分布式哈希算法的文章,主要讨论了一致性哈希和普通哈希的区别,以及如何通过引入虚拟节点来优化一致性哈希的分布问题。 1. **普通哈希算法**: - Java中的`HashMap`类是一个典型...

    一致性哈希算法演示.rar

    一致性哈希算法是一种分布式哈希表(DHT)中用于解决数据分片和负载均衡问题的算法。在大型分布式系统中,例如缓存系统、分布式数据库等,一致性哈希能够确保当节点加入或离开时,尽可能少的数据需要迁移,从而保持...

    带虚拟节点的一致性哈希

    一致性哈希(Consistent Hashing)是一种分布式哈希算法,主要应用于分布式缓存、负载均衡等领域,例如Memcached和Redis等系统。它解决了在分布式环境中数据分片与节点动态增减时,尽量减少数据迁移的问题。带虚拟...

    grad-DS-SimpleDHT:分布式系统 CSE 586 -- 简单的分布式哈希表

    通常,使用一致性哈希(Consistent Hashing)来解决节点加入或离开时的数据迁移问题。 2. **节点发现**:新加入的节点需要知道网络中其他节点的存在,这通常通过节点间的 gossip 协议或基于UDP的多播来实现。 3. **...

    一致性哈希算法C版实现

    一致性哈希算法是一种在分布式系统中解决数据分片和负载均衡问题的算法,它主要解决了在动态添加或移除节点时,尽可能少地改变已经存在的数据分布。在云计算和大数据处理领域,一致性哈希被广泛应用,例如在分布式...

    分布式分页机制与数据一致性.pptx

    - 一致性模型定义了分布式系统中数据的一致性级别,常见的模型包括强一致性、弱一致性和最终一致性。 - **分布式分页机制的常见问题**: - **热点数据问题**:某些页面的数据访问量远高于其他页面,可能导致这些...

    网络游戏-用于网络装备中的高性能、可更新和确定的哈希表的方法和设备.zip

    哈希表在网络装备中的应用不仅限于基本的数据存储,还可以用于实现更复杂的逻辑,如缓存机制、负载均衡策略、一致性哈希等。通过优化哈希算法和设计,可以减少网络延迟,提高服务可用性,为玩家提供流畅的游戏体验。...

Global site tag (gtag.js) - Google Analytics