- 浏览: 395245 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (325)
- 神经网络 (1)
- javascript (11)
- 数据结构 (2)
- 计算机图形学 (11)
- 模式识别 (1)
- 前端开发 (14)
- 机器学习 (11)
- ios开发 (50)
- Python (9)
- HTML5 (4)
- 计算机视觉 (9)
- 数字图像处理 (7)
- 架构设计 (19)
- 数据库设计 (9)
- 算法设计 (59)
- Java (37)
- 其他 (3)
- 游戏开发 (5)
- c++ (17)
- Linux (3)
- TCP/IP (2)
- Flex (41)
- 健康 (6)
- AI (2)
- 工具 (1)
- 数据挖掘 (1)
- 性能优化 (6)
- 综合 (2)
- 网络通信 (12)
- Android (2)
- UML (3)
- 软件设计 (11)
- 编程经验 (7)
- J2EE (1)
- 多媒体技术 (3)
- 数学 (7)
- php (4)
- 设计 (1)
- CS (2)
- 计算机理论 (1)
- 信息安全 (1)
最新评论
-
ahead_zhan:
good good good
flex3控件_ModuleLoader -
lonerzf:
好样的。非常感谢楼主
OpenCV视频教程整理 -
lonerzf:
好样的。谢谢~
OpenCV视频教程整理 -
coding1688:
博主说的不错,我在实现瀑布流布局时也用的masonry插件,有 ...
Javascript 瀑布流式布局及其动态效果的实现 -
snowolf:
除非玩游戏,不然没啥win的事情,或者用win的银行客户端,通 ...
macbook安装操作系统的机理分析
参考: 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,记录网络中对应节点区域的多个节点,并且根据活跃时间对这些节点进行换入换出。
第一点是方便进行网络划分,节点按照二进制中每一bit的0或1建成一棵二叉树。
第二点是使得节点查询更迅速。从分割情况我们就可以得知,最坏情况不会差于chord,但保存更多的节点使得命中概率更高。另外队列中根据活跃时间进行换入换出,更有利于在p2p这种节点变更频繁的网络中快速找到有效的节点。
关于kad的介绍,这篇文章讲的比较详细wenku.baidu.com/view/ee91580216fc700abb68fcae.html
- 分布式哈希表_Distributed_Hash_Table.pdf (57.2 KB)
- 下载次数: 5
发表评论
-
【转】那些年使用过MapReduce的论文
2014-03-09 15:20 1008MapReduce is a programmi ... -
单点登录SSO的实现原理
2013-08-26 10:09 650转自:http://blog.csdn.net ... -
73本免费的、语言无关的优秀的编程书籍
2013-03-24 21:43 650这些书籍中有HTML格式的,也有PDF格式的,当 ... -
HBASE压缩算法-SNAPPY算法安装
2012-11-19 17:46 2821转自:http://www.cnblogs.com/s ... -
Hadoop集群实践
2012-11-11 17:01 740(0) 完整架构设计 [ Hadoop(HDFS) , ... -
REST介绍与REST在PHP中的应用
2012-10-06 17:27 594转自:http://www.nowamagic.net/ ... -
【转】大流量、高并发的网站的底层系统架构
2012-09-29 22:08 698转自: http://hi.baidu.com/liyi ... -
【转】建设一个靠谱的火车票网上订购系统
2012-09-29 21:59 1061转自:http://www.ifanr.com/68019 ... -
可扩展性数据库的架构设计
2012-07-17 19:59 789参考:http://www.51testing.c ... -
高并发高流量网站架构设计(参考)
2012-06-04 16:34 640参考:http://carywu.blog.51c ... -
BlazeDS的架构和工作原理简介
2012-06-02 14:09 851参考:http://hi.baidu.com/whlxj ... -
OpenMP,MPI,MapReduce 比较
2012-05-20 12:08 2115参考: http://blog.csdn.net/z ... -
大型高性能网站的十项规则
2011-11-21 15:48 630参考:http://kb.cnblogs.com/page/6 ... -
微博的短url如何实现
2011-11-03 18:38 2366参考:http://hi.baidu.com/icyd ... -
网络爬虫设计——URL去重存储库设计
2011-11-03 14:40 1383参考: http://apps.hi.b ... -
NoSQL架构实践(一)——以NoSQL为辅
2011-10-25 23:36 683参考:http://www.infoq.com/cn/n ... -
前端性能优化
2011-06-04 11:22 649图片篇: http://www.pin5i.com/showt ... -
FLASH/ActionScript 性能优化
2011-05-31 21:41 1158一. 图形方面的优化 1. 减少同时在屏幕上物体的个 ... -
浅谈领域驱动设计
2011-01-05 01:08 747需求背景 现在的 样子 如PoEAA中提到 ... -
各种架构图汇总!
2010-12-29 22:26 14721.Spring架构图 2.Hiber ...
相关推荐
Client.py:此文件使用弦环和n元树实现分布式哈希表(DHT)的两层覆盖网络。 它负责与其他节点进行通信。 使用以下代码在执行代码之前安装pyqt4:sudo apt-get install python-qt4 执行命令:索引服务器:python ...
关于分布式散列表DHT的前世今生的故事:包括单机hash、分布式一致性hash
针对Chord模型在节点加入或离开时产生大量消息,不适用于动态网络的问题,提出一种基于分布式哈希表(Distribute Hash Table,DHT)的自适应Chord模型,即Self-adaptive Chord。方法是该模型在节点加入或离开的时候...
算法特性:包括输入、输出、有穷性、确定性和可行性。即一个有效的算法必须能在有限步骤内结束,并且对于给定的输入产生唯一的确定输出。 算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序...
原子性操作:Redis支持原子性操作,能够保证多个操作的执行顺序和一致性,支持事务和流水线操作。 发布/订阅:Redis提供了发布/订阅功能,能够实现消息的异步发布和订阅,适用于实时通知、事件驱动等场景。 分布式...
为解决分布式协同设计系统中的异地编辑一致性及多副本同步等问题,提出基于分布式哈希表(DHT)的分布式互斥算法,给出该算法的实现方法。通过采用DHT化的优先队列解决了异地编辑一致性操作问题。将传统的“锁”算法...
系统中的参与者注册在一个由 Chord 算法支持的分布式哈希表中,因此系统中的保存和查找与参与客户端的数量成对数比例。Eclipse设置菜单 > 帮助 > 安装新软件 > 添加... 名称: M2Eclipse 位置: : 全选 > 下一步 > ...
分布式哈希表对于 Coursera 上的 UIUC 云计算概念课程第 1 部分:Gossip Membership Protocol:始终完整性(每个非故障进程检测每个节点的加入、故障和离开) 故障检测的准确性(当没有消息丢失且消息延迟很小时) ...
4.5.1 一致性哈希 81 4.5.2 对象版本 82 4.5.3 闲话协议和提示移交 83 4.6 小结 83 第5章 执行CRUD操作 84 5.1 创建记录 84 5.1.1 在以文档为中心的数据库中创建记录 85 5.1.2 面向列数据库的创建操作 91 ...
根据标准的一致性哈希算法实现了hashRing,并加入数据服务器存储空间大小不同等权重来平衡各节点的虚拟多维数据集复制因子,对象读取请求均根据对象名进行哈希运算映射到虚拟多维数据集上,再由虚拟多维数据集映射到...
问题:哈希表通常意味着您需要将所有内容存储在内存中。 1.2 简单的解决方案:压缩数据并存储在磁盘中 1.3 解决方案:分布式Key-value存储 分片:假设我们要存储像 URL 这样的键,我们可以将它们除以第一个字符,...
布鲁尔的猜想和一致,可用,可分区容忍的网站的可行性 | BASE:替代酸| | 最终一致| 无冲突的复制数据类型 拜占庭将军问题 兼职议会| Paxos变得简单| 存储 Bitcask-用于快速键/值数据的日志结构哈希表| | Google文件...
chapin blog微服务架构 & DevOpsK8SService Mesh苏槐系列文章如何快速搭建一个微服务架构微服务架构中...什么是一致性哈希?无序数组排序后的最大相邻差值数据库数据库是如何工作的?高效sql性能优化极简教程Mongo高级
什么是一致性哈希? 它基本上是一种技术,用于专门基于基于ID或某些唯一代码创建的哈希值在不同服务器之间处理请求。 这几乎是用于负载分配的最简单算法之一,因为它在重定向请求之前不会考虑节点内部的工作量。 您...
leetcode 跳跃 Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ Ⅶ Ⅷ ...五种数据类型、字典和跳跃表...缓存特征、缓存位置、缓存问题、数据分布、一致性哈希、LRU、CDN 消息处理模型、使用场景、可靠性 :hammer: 工具 一些 Git 的使用和概念。 正则
§10.3.2 相互产生运算的数字型字段长度和精度要一致 114 §10.3.2 不要为了节省空间而将字段的长度缩小或拆开 115 §10.4 将LOB类型的字段与其它的类型分开 115 §10.5 采用具有编码的设计方法 115 §10.6 建立公共...
【算法】什么是一致性哈希?用来解决什么问题? 144 【性能优化】页面静态化 144 【设计模式】写一个单例(延迟加载,高性能) 144 【容器】Apache Http Server和Tomcat 区别 145 【版本控制】GIT与SVN的区别 146 【高...