Hash一致算法_一致性hash是如何做数据迁移

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

概述

这里存在一种场景, 当一个缓存服务由多个服务器组共同提供时, key应该路由到哪一个服务.这里假如采用最通用的方式key%N(N为服务器数目), 这里乍一看没什么问题, 但是当服务器数目发送增加或减少时, 分配方式则变为key%(N+1)或key%(N-1).这里将会有大量的key失效迁移,如果后端key对应的是有状态的存储数据,那么毫无疑问,这种做法将导致服务器间大量的数据迁移,从而照成服务的不稳定. 为了解决类问题,一致性hash算法应运而生.

1. 一致性hash算法特点

在分布式缓存中, 一个好的hash算法应该要满足以下几个条件:

均衡性(Balance)

均衡性主要指,通过算法分配, 集群中各节点应该要尽可能均衡.

单调性(Monotonicity)

单调性主要指当集群发生变化时, 已经分配到老节点的key, 尽可能的任然分配到之前节点,以防止大量数据迁移, 这里一般的hash取模就很难满足这点,而一致性hash算法能够将发生迁移的key数量控制在较低的水平.

分散性(Spread)

分散性主要针对同一个key, 当在不同客户端操作时,可能存在客户端获取到的缓存集群的数量不一致,从而导致将key映射到不同节点的问题,这会引发数据的不一致性.好的hash算法应该要尽可能避免分散性.

负载(Load)

负载主要是针对一个缓存而言, 同一缓存有可能会被用户映射到不同的key上,从而导致该缓存的状态不一致.

从原理来看,一致性hash算法针对以上问题均有一个合理的解决.

2. 一致性hash详解

一致性hash的核心思想为将key作hash运算, 并按一定规律取整得出0-2^32-1之间的值, 环的大小为2^32，key计算出来的整数值则为key在hash环上的位置，如何将一个key，映射到一个节点，这里分为两步.

第一步, 将服务的key按该hash算法计算,得到在服务在一致性hash环上的位置.

第二步, 将缓存的key，用同样的方法计算出hash环上的位置，按顺时针方向，找到第一个大于等于该hash环位置的服务key，从而得到该key需要分配的服务器。

如图，各key根据hash算法分配到各节点，当某一节点失效实效时，如NODE 2失败，则NODE 2 上的key将分配到hash环上相邻的节点，而其他key所在位置不变。

虚拟节点提高均衡性

如上图可看到，由于节点只有3个，存在某些节点所在位置周围有大量的hash点从而导致分配到这些节点到key要比其他节点多的多，这样会导致集群中各节点负载不均衡，为解决这个问题，引入虚拟节点，即一个实节点对应多个虚拟节点。缓存的key作映射时，先找到对应的虚拟节点，再对应到实节点。如下图所示，每个节点虚拟出两个虚拟节点，从而提高均衡性。

3. 一致性hash算法与其他算法对比

对于集群中缓存类数据key的节点分配问题，有这几种解决方法，简单的hash取模，槽映射，一致性hash。

hash取模

对于hash取模，均衡性没有什么问题，但是如果集群中新增一个节点时，将会有N／（N+1）的数据实效，当N值越大，失效率越高。这显然是不可接受的。

槽映射

其思想是将key值做一定运算（如crc16， crc32，hash），获得一个整数值，再将该值与固定的槽数取模（slots），每个节点处理固定的slots。获取key所在的节点时，先要计算出key与槽的对应关系，再通过槽与节点的对应关系找到节点，这里每次新增节点时，只需要迁移一定槽对应的key即可，而不迁移的槽点key值则不会实效，这种方式将实效率降低到了 N／（N+1）。不过这种方式有个缺点就是所有节点都需要知道槽与节点对应关系，如果client端不保存槽与节点的对应关系的话，它需要实现重定向的逻辑。