一致性哈希算法,是1997年麻省理工学院提出,用来解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。不同的是,一致性哈希修正了CARP使用简单哈希算法中未决的问题,是第一个实用的DHT算法。
一致性哈希算法有4个特点:
1. 平衡性(Balance)
指哈希的结果尽可能分布到所有的缓冲中,使所有的Cache都得到利用,这一点多数Hash算法基本上都已实现了。
2. 单调性(Monotonicity)
指在加入新的Cache后,原有的分配key值应该指到新的Cache。简单的哈希算法不能满足这一要求。
3. 分散性(Spread)
指相同的数据,由不同的终端来映射到缓冲中时,应该映射到同一个缓冲。
4. 负载(Load)
是相对于分散性而说,每一个缓冲,不能被不同的客户端映射成不同的内容。
在分布式集群中,对机器的添加删除,或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的hash(key) mod N算法(key是数据的key,N是机器节点数),那么有机器添加或者删除后,大量的缓存命不中,缓存数据需要重新建立,甚至是进行整体的缓存数据迁移,瞬间会给DB带来极高的系统负载,设置导致DB服务器宕机。
设计分布式cache系统时,一致性hash算法可以帮我们解决哪些问题?
分布式缓存设计核心点:在设计分布式cache系统的时候,我们需要让key的分布均衡,并且在增加cache server后,cache的迁移做到最少。
一致性哈希算法的实现:
1. 建立环形空间
public class Shard<S> { // S类封装了机器节点的信息 ,如name、password、ip、port等 private TreeMap<Long, S> nodes; // 虚拟节点 private List<S> shards; // 真实机器节点 private final int NODE_NUM = 100; // 每个机器节点关联的虚拟节点个数 public Shard(List<S> shards) { super(); this.shards = shards; init(); } private void init() { // 初始化一致性hash环 nodes = new TreeMap<Long, S>(); for (int i = 0; i != shards.size(); ++i) { // 每个真实机器节点都需要关联虚拟节点 final S shardInfo = shards.get(i); for (int n = 0; n < NODE_NUM; n++) // 一个真实机器节点关联NODE_NUM个虚拟节点 nodes.put(hash("SHARD-" + i + "-NODE-" + n), shardInfo); } } public S getShardInfo(String key) { SortedMap<Long, S> tail = nodes.tailMap(hash(key)); // 沿环的顺时针找到一个虚拟节点 if (tail.size() == 0) { return nodes.get(nodes.firstKey()); } return tail.get(tail.firstKey()); // 返回该虚拟节点对应的真实机器节点的信息 } /** * MurMurHash算法,是非加密HASH算法,性能很高, * 比传统的CRC32,MD5,SHA-1(这两个算法都是加密HASH算法,复杂度本身就很高,带来的性能上的损害也不可避免) * 等HASH算法要快很多,而且据说这个算法的碰撞率很低. * http://murmurhash.googlepages.com/ */ private Long hash(String key) { ByteBuffer buf = ByteBuffer.wrap(key.getBytes()); int seed = 0x1234ABCD; ByteOrder byteOrder = buf.order(); buf.order(ByteOrder.LITTLE_ENDIAN); long m = 0xc6a4a7935bd1e995L; int r = 47; long h = seed ^ (buf.remaining() * m); long k; while (buf.remaining() >= 8) { k = buf.getLong(); k *= m; k ^= k >>> r; k *= m; h ^= k; h *= m; } if (buf.remaining() > 0) { ByteBuffer finish = ByteBuffer.allocate(8).order( ByteOrder.LITTLE_ENDIAN); // for big-endian version, do this first: // finish.position(8-buf.remaining()); finish.put(buf).rewind(); h ^= finish.getLong(); h *= m; } h ^= h >>> r; h *= m; h ^= h >>> r; buf.order(byteOrder); return h; } }
一致性哈希基本解决了在P2P环境中最为关键的问题——如何在动态的网络拓扑中分布存储和路由。每个节点仅需维护少量相邻节点的信息,并且在节点加入/退出系统时,仅有相关的少量节点参与到拓扑的维护中。所有这一切使得一致性哈希成为第一个实用的DHT算法。
概念:
DHT: Distributed Hash Table,分布式哈希表,是一种分布式存储方法。
CARP :Common Access Redundancy Protocol,共用地址冗余协议,或简称 CARP 能够使多台主机共享同一 IP 地址。
参考:
相关推荐
对已有的负载平衡的改进算法,通过一致性哈希算法,负载平衡更加的有效。
一致性哈希算法
一致性哈希算法,广泛应用于分布式计算,C版实现,属于分布式服务器管理的核心算法。
#资源达人分享计划#
运行平台:VS 2019 一致性哈希算法演示项目,演示新增节点key分布情况;移除节点key分布情况! C#,C#,C#.......
基于动态转移的分布式缓存系统一致性哈希算法改进,张昊,张永军,近年来,随着大数据与分布式集群的广泛应用,一致性哈希算法在分布式缓存系统的负载均衡中得到了广泛的应用。一致性哈希算法虽然
#资源达人分享计划#
#资源达人分享计划#
一致性哈希算法用来解决分布式系统中热点接入与删除管理,是目前公认的最有效的算法,该文档图文并茂,详细解释了这一算法。
#资源达人分享计划#
白话解析:一致性哈希算法1
#资源达人分享计划#
一致性哈希算法应用及优化(最简洁明了的教程)
Ketama算法是一致性hash算法的一个优秀实现。增删节点后数据命中率及均分率都很高。
基于NIO-EPOOL模型netty实现的具备一致性哈希算法的NAT端口映射器
在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。
其次介绍了系统的实现流程,阐明了系统的关键技术:利用录音服务器对其镜像端口的SIP报文进行解析获得媒体流并解码、采用一致性哈希算法的内存数据库作为解码数据的缓存机制、利用Ckafka技术在两者之间构建实时数据...
ufire-springcloud-platform 学习微服-基于一致性哈希算法实现websocket分布式扩展的尝试。
一致性哈希算法的php版,希望能帮到phper了解一致性哈希