文档章节

【分布式基础】一致性哈希

毛爷爷夸我帅
 毛爷爷夸我帅
发布于 2014/09/12 17:36
字数 756
阅读 52
收藏 0

分布式过程中我们将服务分散到若干的节点上,以此通过集体的力量提升服务的目的。然而,对于一个客户端来说,该由哪个节点服务呢?或者说对某个节点来说他分配到哪些任务呢?

1. 强哈希

考虑到单服务器不能承载,因此使用了分布式架构,最初的算法为 hash() mod n, hash()通常取用户ID,n为节点数。此方法容易实现且能够满足运营要求。缺点是当单点发生故障时,系统无法自动恢复。同样不也不能进行动态增加节点。

2. 弱哈希

为了解决单点故障,使用 hash() mod (n/m), 这样任意一个用户都有m个服务器备选,可由client随机选取。由于不同服务器之间的用户需要彼此交互,所以所有的服务器需要确切的知道用户所在的位置。因此用户位置被保存到memcached中。当一台发生故障,client可以自动切换到对应backup,由于切换前另外1台没有用户的session,因此需要client自行重新登录。

他比强哈希的好处是:解决了单点问题。

但存在以下问题:负载不均衡,尤其是单台发生故障后剩下一台会压力过大;不能动态增删节点;节点发生故障时需要client重新登录

3. 一致性哈希

一致性哈希也只是提出四个概念和原则,并没有提及具体实现:
1
balance:哈希结果尽可能的平均分散到各个节点上,使得每个节点都能得到充分利用。
2
Monotonicity:上面也说了,如果是用签名取模算法,节点变更会使得整个网络的映射关系更改。如果是carp,会使得1/n的映射关系更改。一致性哈希的目标,是节点变更,不会改变网络的映射关系。
3
spread:同一份数据,存储到不同的节点上,换言之就是系统冗余。一致性哈希致力于降低系统冗度。
4
load:负载分散,和balance其实是差不多的意思,不过这里更多是指数据存储的均衡,balance是指访的均衡。

一致性哈希算法在1997年由麻省理工学院提出,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。

我们把每台server分成v个虚拟节点,再把所有虚拟节点(n*v)随机分配到一致性哈希的圆环上,这样所有的用户从自己圆环上的位置顺时针往下取到第一个vnode就是自己所属节点。当此节点存在故障时,再顺时针取下一个作为替代节点。



引用:

http://baike.baidu.com/view/1588037.htm


© 著作权归作者所有

毛爷爷夸我帅

毛爷爷夸我帅

粉丝 28
博文 115
码字总数 204692
作品 0
深圳
架构师
私信 提问
查找--深入理解一致性哈希算法

注:本篇博客只是讲述了一致性哈希的思想,我们会在之后讲述分布式哈希表以及一致性哈希的一种实现(Chord算法)。 什么是一致性哈希算法? 引用自维基百科: 一致性哈希是一种特殊的哈希算法...

珩翊
2018/06/26
0
0
使用虚拟节点改进的一致性哈希算法

分布式存储中的应用 ---在分布式存储系统中,将数据分布至多个节点的方式之一是使用哈希算法。假设初始节点数为 N,则传统的对 N 取模的映射方式存在一个问题在于:当节点增删,即 N 值变化时...

lionets
2014/07/07
6K
6
百度海量日志处理——任务调度实践与优化

作者简介 运小军 百度高级研发工程师 负责百度运维部大规模日志处理、海量事件数据存储相关设计研发工作,在分布式系统架构、大数据存储计算、高性能网络服务和即时通讯服务有广泛实践经验。...

g2v13ah
2017/11/02
0
0
5分钟带你理解一致性Hash算法。

QQ用得起来越少了,现在就加入300+技术微信群,公众号回复"微信群"即可加入。 一致性Hash算法背景 一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是...

架构之路
2017/12/03
0
0
一致性(连续性)hash算法(Consistent hashing)

一致性(连续性)hash算法(Consistent hashing) Consistent hashing is a scheme that provides hash table functionality in a way that the addition or removal of one slot does not s......

程序员诗人
2017/08/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

node.js中__dirname和./有什么区别?

在Node.js中编程并引用位于与当前目录相关的文件时,是否有任何理由使用__dirname变量而不仅仅是常规./ ? 到目前为止,我一直在使用./并且刚刚发现了__dirname的存在,并且基本上想知道将....

javail
16分钟前
35
0
Hive安装

下载上传apache-hive-2.1.1-bin.tar.gz文件并解压 tar -zxvf apache-hive-2.1.1-bin.tar.gz -C /export/servers 配置环境变量 vi /etc/profileexport HIVE_HOME=/export/servers/apache......

长臂猿猴
22分钟前
39
0
OS X:相当于Linux的wget

如何从库存OS X系统上的Un * x shell脚本执行HTTP GET? (安装第三方软件不是一种选择,因为这必须在我无法控制的许多不同系统上运行)。 例如,如果我在本地启动Mercurial服务器执行hg服务...

技术盛宴
32分钟前
39
0
Fedora 31 - 荣耀魔法本问题记录

最近荣耀魔法本装了Fedora31系统,没有像Deepin 15.11那样出现亮度不能调节和网卡不能用的问题。但是也有不少小问题: 触摸板有时启动后失效,需要重启。 触摸板的右键失效。 待机后进入桌面...

wffger
35分钟前
34
0
ElasticSearch深入:内部机制浅析(三)@

前言 上篇从分布式的角度阐述了 ES 的分布式设计和思想,这一篇打算与 Lucene 结合起来,摸透一些 ES 的常遇到的概念,我们可以将了解到的这些东西应用到优化实践中去。 一、Shard Shard 实际...

HLee
今天
30
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部