Documentation ¶
Overview ¶
Package consistenthash provides an implementation of a ring hash. 一致性哈希算法,参考分析: http://blog.segmentfault.com/lds/1190000000414004, http://blog.codinglabs.org/articles/consistent-hashing.html 一致性哈希算法主要使用在分布式数据存储系统中,按照一定的策略将数据尽可能均匀分布到 所有的存储节点上去,使得系统具有良好的负载均衡性能和扩展性。
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Map ¶
type Map struct {
// contains filtered or unexported fields
}
Map 结构,定义核心数据结构,其中hash是哈希函数,用于对key进行hash,keys字段保存所有的节点(包括虚拟节点)是可排序的, hashmap 则是虚拟节点到真实节点的映射。一致性哈希算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜问题。 一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。
func (*Map) Add ¶
Adds some keys to the hash. Map的Add方法,添加节点到圆环,参数是一个或者多个string,对每一个key关键字进行哈希, 这样每台机器就能确定其在哈希环上的位置,在添加每个关键字的时候,并添加对应的虚拟节点, 每个真实节点和虚拟节点个数由replicas字段指定,保存虚拟节点到真实节点的对应关系到hashmap字段。 比如在测试用例中,hash.Add("6", "4", "2"),则所有的节点是 2, 4, 6, 12, 14, 16, 22, 24, 26, 当has.Get('11') 时,对应的节点是12,而12对应的真实节点是2
hash.Add("6", "4", "2")是数据值:
2014/02/20 15:45:16 replicas: 3 2014/02/20 15:45:16 keys: [2 4 6 12 14 16 22 24 26] 2014/02/20 15:45:16 hashmap map[16:6 26:6 4:4 24:4 2:2 6:6 14:4 12:2 22:2]
说明: 此处添加虚拟节点的算法是有问题的,比如replicas = 3,传入的key为2,12,22,则就会出现某个节点的虚拟实际上就是 另外的真实节点。不过在groupcache中的应用不存在这个情况,因为keys都是字符串,而且是host:port形式的字符串,所以 就不会出现上面的情况。 在php-memcache中也实现了一致性hash算法的,在计算虚拟节点的时候,采用的是类似的算法。相关源码是: memcache_consistent_hash.c mmc_consistent_add_server函数内部:
for (i=0; i<points; i++) { key_len = sprintf(key, "%s:%d-%d", mmc->host, mmc->port, i); state->points[state->num_points + i].server = mmc; state->points[state->num_points + i].point = state->hash(key, key_len); MMC_DEBUG(("mmc_consistent_add_server: key %s, point %lu", key, state->points[state->num_points + i].point)); }