点击上方 "程序员小乐"关注, 星标或置顶一起成长
每天凌晨00点00分, 第一时间与你相约
每日英文
If you concentrate on the ONE thing in your life that makes you truly happy... everything else in your life will fall into place.
如果人只关注着真正带给自己快乐的事,那其余一切,就都清晰明了了。
每日掏心话
任何经历,都是一种积累;积累越多,人就越成熟。经历越多,生命就越有长度;经历越广,生命就越有厚度;
来自:MarkLux | 责编:乐乐
链接:marklux.cn/blog/90
往日回顾:Springboot + Vue + shiro 实现前后端分离、权限控制
正文
public class HashUtil { /** * 计算Hash值, 使用FNV1_32_HASH算法 * @param str * @return */ public static int getHash(String str) { final int p = 16777619; int hash = (int)2166136261L; for (int i = 0; i < str.length(); i++) { hash =( hash ^ str.charAt(i) ) * p; } hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; if (hash < 0) { hash = Math.abs(hash); } return hash; }}
public class ConsistentHashingWithoutVirtualNode { /** * 集群地址列表 */ private static String[] groups = { "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111" }; /** * 用于保存Hash环上的节点 */ private static SortedMap<Integer, String> sortedMap = new TreeMap<>(); /** * 初始化,将所有的服务器加入Hash环中 */ static { // 使用红黑树实现,插入效率比较差,但是查找效率极高 for (String group : groups) { int hash = HashUtil.getHash(group); System.out.println("[" + group + "] launched @ " + hash); sortedMap.put(hash, group); } } /** * 计算对应的widget加载在哪个group上 * * @param widgetKey * @return */ private static String getServer(String widgetKey) { int hash = HashUtil.getHash(widgetKey); // 只取出所有大于该hash值的部分而不必遍历整个Tree SortedMap<Integer, String> subMap = sortedMap.tailMap(hash); if (subMap == null || subMap.isEmpty()) { // hash值在最尾部,应该映射到第一个group上 return sortedMap.get(sortedMap.firstKey()); } return subMap.get(subMap.firstKey()); } public static void main(String[] args) { // 生成随机数进行测试 Map<String, Integer> resMap = new HashMap<>(); for (int i = 0; i < 100000; i++) { Integer widgetId = (int)(Math.random() * 10000); String server = getServer(widgetId.toString()); if (resMap.containsKey(server)) { resMap.put(server, resMap.get(server) + 1); } else { resMap.put(server, 1); } } resMap.forEach( (k, v) -> { System.out.println("group " + k + ": " + v + "(" + v/1000.0D +"%)"); } ); }}
[192.168.0.1:111] launched @ 8518713[192.168.0.2:111] launched @ 1361847097[192.168.0.3:111] launched @ 1171828661[192.168.0.4:111] launched @ 1764547046group 192.168.0.2:111: 8572(8.572%)group 192.168.0.1:111: 18693(18.693%)group 192.168.0.4:111: 17764(17.764%)group 192.168.0.3:111: 27870(27.87%)group 192.168.0.0:111: 27101(27.101%)
可以看到压力还是比较不平均的,所以我们继续,引入虚拟节点:
public class ConsistentHashingWithVirtualNode { /** * 集群地址列表 */ private static String[] groups = { "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111" }; /** * 真实集群列表 */ private static List<String> realGroups = new LinkedList<>(); /** * 虚拟节点映射关系 */ private static SortedMap<Integer, String> virtualNodes = new TreeMap<>(); private static final int VIRTUAL_NODE_NUM = 1000; static { // 先添加真实节点列表 realGroups.addAll(Arrays.asList(groups)); // 将虚拟节点映射到Hash环上 for (String realGroup: realGroups) { for (int i = 0; i < VIRTUAL_NODE_NUM; i++) { String virtualNodeName = getVirtualNodeName(realGroup, i); int hash = HashUtil.getHash(virtualNodeName); System.out.println("[" + virtualNodeName + "] launched @ " + hash); virtualNodes.put(hash, virtualNodeName); } } } private static String getVirtualNodeName(String realName, int num) { return realName + "&&VN" + String.valueOf(num); } private static String getRealNodeName(String virtualName) { return virtualName.split("&&")[0]; } private static String getServer(String widgetKey) { int hash = HashUtil.getHash(widgetKey); // 只取出所有大于该hash值的部分而不必遍历整个Tree SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash); String virtualNodeName; if (subMap == null || subMap.isEmpty()) { // hash值在最尾部,应该映射到第一个group上 virtualNodeName = virtualNodes.get(virtualNodes.firstKey()); }else { virtualNodeName = subMap.get(subMap.firstKey()); } return getRealNodeName(virtualNodeName); } public static void main(String[] args) { // 生成随机数进行测试 Map<String, Integer> resMap = new HashMap<>(); for (int i = 0; i < 100000; i++) { Integer widgetId = i; String group = getServer(widgetId.toString()); if (resMap.containsKey(group)) { resMap.put(group, resMap.get(group) + 1); } else { resMap.put(group, 1); } } resMap.forEach( (k, v) -> { System.out.println("group " + k + ": " + v + "(" + v/100000.0D +"%)"); } ); }}
这里真实节点和虚拟节点的映射采用了字符串拼接的方式,这种方式虽然简单但很有效,memcached官方也是这么实现的。将虚拟节点的数量设置为1000,重新测试压力分布情况,结果如下:
group 192.168.0.2:111: 18354(18.354%)group 192.168.0.1:111: 20062(20.062%)group 192.168.0.4:111: 20749(20.749%)group 192.168.0.3:111: 20116(20.116%)group 192.168.0.0:111: 20719(20.719%)
可以看到基本已经达到平均分布了,接着继续测试删除和增加节点给整个服务带来的影响,相关测试代码如下:
private static void refreshHashCircle() { // 当集群变动时,刷新hash环,其余的集群在hash环上的位置不会发生变动 virtualNodes.clear(); for (String realGroup: realGroups) { for (int i = 0; i < VIRTUAL_NODE_NUM; i++) { String virtualNodeName = getVirtualNodeName(realGroup, i); int hash = HashUtil.getHash(virtualNodeName); System.out.println("[" + virtualNodeName + "] launched @ " + hash); virtualNodes.put(hash, virtualNodeName); } }}private static void addGroup(String identifier) { realGroups.add(identifier); refreshHashCircle();}private static void removeGroup(String identifier) { int i = 0; for (String group:realGroups) { if (group.equals(identifier)) { realGroups.remove(i); } i++; } refreshHashCircle();}
测试删除一个集群前后的压力分布如下:
running the normal test.group 192.168.0.2:111: 19144(19.144%)group 192.168.0.1:111: 20244(20.244%)group 192.168.0.4:111: 20923(20.923%)group 192.168.0.3:111: 19811(19.811%)group 192.168.0.0:111: 19878(19.878%)removed a group, run test again.group 192.168.0.2:111: 23409(23.409%)group 192.168.0.1:111: 25628(25.628%)group 192.168.0.4:111: 25583(25.583%)group 192.168.0.0:111: 25380(25.38%)
[192.168.0.1:111-192.168.0.4:111] :5255[192.168.0.1:111-192.168.0.3:111] :5090[192.168.0.1:111-192.168.0.2:111] :5069[192.168.0.1:111-192.168.0.0:111] :4938
running the normal test.group 192.168.0.2:111: 18890(18.89%)group 192.168.0.1:111: 20293(20.293%)group 192.168.0.4:111: 21000(21.0%)group 192.168.0.3:111: 19816(19.816%)group 192.168.0.0:111: 20001(20.001%)add a group, run test again.group 192.168.0.2:111: 15524(15.524%)group 192.168.0.7:111: 16928(16.928%)group 192.168.0.1:111: 16888(16.888%)group 192.168.0.4:111: 16965(16.965%)group 192.168.0.3:111: 16768(16.768%)group 192.168.0.0:111: 16927(16.927%)
[192.168.0.0:111-192.168.0.7:111] :3102[192.168.0.4:111-192.168.0.7:111] :4060[192.168.0.2:111-192.168.0.7:111] :3313[192.168.0.1:111-192.168.0.7:111] :3292[192.168.0.3:111-192.168.0.7:111] :3261
节点A 0-5460 节点B 5461-10922 节点C 10923-16383
现在假设要增加一个节点D,RedisCluster的做法是将之前每台机器上的一部分Slot移动到D上(注意这个过程也意味着要对节点D写入的KV储存),成功接入后Slot的覆盖情况将变为如下情况:
节点A 1365-5460 节点B 6827-10922 节点C 12288-16383 节点D 0-1364,5461-6826,10923-1228
同理删除一个节点,就是将其原来占有的Slot以及对应的KV储存均匀地归还给其他节点。
2.P2P节点寻找
现在我们考虑如何实现去中心化的访问,也就是说无论访问集群中的哪个节点,你都能够拿到想要的数据。其实这有点类似于路由器的路由表,具体说来就是:
* 每个节点都保存有完整的HashSlot - 节点映射表,也就是说,每个节点都知道自己拥有哪些Slot,以及某个确定的Slot究竟对应着哪个节点。
* 无论向哪个节点发出寻找Key的请求,该节点都会通过CRC(Key) % 16384计算该Key究竟存在于哪个Slot,并将请求转发至该Slot所在的节点。
总结一下就是两个要点:映射表和内部转发,这是通过著名的**Gossip协议**来实现的。
最后我们可以给出Redis Cluster的系统结构图,和一致性Hash环还是有着很明显的区别的:
欢迎在留言区留下你的观点,一起讨论提高。如果今天的文章让你有新的启发,学习能力的提升上有新的认识,欢迎转发分享给更多人。
欢迎各位读者加入订阅号程序员小乐技术群,在后台回复“加群”或者“学习”即可。
猜你还想看
阿里、腾讯、百度、华为、京东最新面试题汇集
从上帝视角看Java如何运行
手把手带你实现线上环境部署概览
基于 token 的多平台身份认证架构设计
文章有问题?点此查看未经处理的缓存