一致性 Hash 算法

发布于: 2020 年 07 月 08 日

一致性哈希算法(Consistent Hashing)最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。

  • 负载均衡

  • 过渡平滑

  • 关键词单调

1.技术出现的背景、初衷,要解决什么样的问题

在使用缓存服务器集群时,为了实现“负载均衡”,可以通过模n的方式将数据固定路由到某个服务器节点。

但这种方式存在较大弊端:当减少或增加服务器节点后,由于n值发生了变化,所以访问数据的请求将被路由到新的缓存服务器上,导致缓存失效。此时,大量的访问请求会瞬间打到数据库上,可能造成数据库宕机,即缓存雪崩。

一致性哈希算法可以用来解决这样的问题。当某个节点发生变化时,只会影响路由到该节点上的缓存数据,也就是只有部分缓存失效,从而避免了缓存雪崩。

当新加入节点Node3时,只影响Node3后面的一部分数据。

2.技术的优势和劣势,即trade-off是什么

缺点:数据倾斜问题。

为解决此问题,引入的虚拟节点机制,即每一个服务节点计算多个哈希值,都放置到Hash环中,以达到数据能够较好的均匀分布的效果。

3.技术适用场景

Memcached、Key-Value Store、Bittorrent DHT、LVS中都有应用。

负载均衡可用时应用服务器、缓存、数据库,一致性hash算法并不能都适用,例如:数据库在扩容后就不能失效,所处要根据不同场景选择不同的算法。

4.技术的组成部分和关键点

1) 构造一个长度为2^32的整数环,称为Hash环;

2) 计算服务器节点的哈希值,并将其配置到0~2^32-1的环上;

3) 计算出存储数据的键的哈希值,映射到圆上;

4) 从数据映射的位置开始顺时针查找,将数据保存到第一个找到的服务器上。若找不到,取第一个节点。形成环形;

5.技术的底层原理换关键实现

1) 如何构造Hash环,即使用什么数据结构

Node必须能够快速的检索到,以便读取缓存数据,HashMap<hash, node>最快的算法O(1);

环上的Node需要是有序的,且能快速定位(比hash(key)大,且离hash值最近的节点),可以选择的方式:数组+排序O(NlogN)、二叉搜索树O(logN)。

面向接口编程:getNode(),然后用不同的方式实现。

6.已有的实现和他之间的对比

发布于: 2020 年 07 月 08 日 阅读数: 10
用户头像

羽球

关注

还未添加个人签名 2017.10.28 加入

还未添加个人简介

评论

发布
暂无评论
一致性Hash算法