小小狐狸 2019-06-27
一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是为了解决因特网中的热点(Hot spot)问题
国际惯例,先上源码 https://github.com/manerfan/c...
一致性哈希可应用于负载均衡、分布式缓存(缓存分片)等场景中,以下以分布式缓存为例
如,现有N个缓存实例,将一个对象object映射到某一个缓存上可以采取取模方式 hash(object) % N
我们称之为简单hash算法。一般,简单hash算法确实能够比较均匀地实现分布式映射,但如果考虑缓存实例变动(增删)的情况:
hash(object) % (N - 1)
hash(object) % (N + 1)
对于以上情况,无论新增还是移除,大部分object所映射的缓存实例均会改变,缓存命中率大幅度降低从而回源到服务器,短时间内造成缓存雪崩现象
一致性 Hash 算法简单的说,在移除/添加一个缓存实例时,尽可能小的改变已存在key映射关系,尽可能的满足单调性的要求。
通常的hash算法都是将一个value映射到一个32位的key值,我们可以将这个[0, 2^32-1]空间想象成一个首尾相接的环形队列
通过hash函数计算对象hash值,将对象映射到hash环形空间
使用缓存实例的ip、port等信息,通过hash函数计算其hash值,将缓存实例映射到hash空间
沿着顺时针方向,查找距离对象object最近的缓存实例,并将对象映射到该实例
按照同样的算法,在添加实例后发现,只有少部分对象的映射关系改变
按照同样的算法,在移除实例后,同样只有少部分对象的映射关系改变
为了使对象尽可能均匀地映射到所有的缓存实例中(解决缓存实例分布不均匀的问题),引入虚拟节点的概念
虚拟节点其实为真实节点在hash空间中的复制品,一个真实节点可以对应多个虚拟节点
虚拟节点的hash求值可以在真实节点的求值基础上加入编号等信息 hash(realCacheKey#1)
、 hash(realCacheKey#2)
实现目标:
这里,我们定义一个公共接口
/** * 真实节点 */ interface PhysicalNode { fun hashKey(): String }
自定义节点数据,只需要实现PhysicalNode接口及hashKey方法,程序会通过hashKey的值计算节点的hash值
如,我们定义常规服务节点
/** * 常规的服务节点 * * @param name 服务名称 * @param host 服务host/ip * @param port 服务port */ data class HostPortPhysicalNode(val name: String, val host: String, val port: Int) : PhysicalNode { override fun hashKey() = "$name:$host:$port" }
这里,我们还需要定义一个虚拟节点
/** * 虚拟节点 * * @param parent 真实节点 * @param replica 虚拟节点id */ data class VirtualNode<out T : PhysicalNode>(val parent: T, private val replica: Int) : PhysicalNode { override fun hashKey() = "${parent.hashKey()}#$replica" fun matches(key: String) = parent.hashKey() == key }
虚拟节点的hashKey为真实节点hashKey加上节点编号
这里,我们同样定义一个公共接口
/** * 哈希函数 */ interface HashFunc { fun hash(str: String): Long }
自定义hash含蓄,只需要实现HashFunc接口及hash方法
如,我们定义md5函数
class Md5 : HashFunc { override fun hash(str: String): Long { val md5 = MessageDigest.getInstance("MD5") md5.reset() md5.update(str.toByteArray()) val bytes = md5.digest() var h: Long = 0 bytes.forEach { h = h shl 8 h = h or (it.toLong() and 0xFF) } return h } }
ConsistentHash
及ConsistentHashHelper
的实现,见 ConsistentHashHelper.kt
我们使用ConsistentHashHelper来构建ConsistentHash
val consistentHash = ConsistentHashHelper.create<HostPortPhysicalNode>().build()
如果需要自定义hash函数,可以通过withHash
指定,默认使用md5
val consistentHash = ConsistentHashHelper.create<HostPortPhysicalNode>() .withHash(MyMd5HashFunc()) .build()
同样,可以通过withNodes指定在初始化时生成节点信息
val master = HostPortPhysicalNode("master", "192.169.1.1", 8080) val slave = HostPortPhysicalNode("slave", "192.169.1.2", 8080) val consistentHash = ConsistentHashHelper.create<HostPortPhysicalNode>() .withHash(MyMd5HashFunc()) .withNodes(listOf(master, slave), 2) // 节点,并指定每个节点的副本数(可以省略,缺省1) .build()
运行过程中,可以动态增删节点
val backup = HostPortPhysicalNode("backup", "192.168.1.13", 8888) consistentHash.add(backup, 4) // 增加节点,并指定每个节点的副本数(可以省略,缺省1) consistentHash.remove(slave.hashKey())
通过getNode函数获取对应object所映射的缓存实例
consistentHash.getNode(hashFunc.hash(object1.key)) consistentHash.getNode(hashFunc.hash(object2.key))