Questions
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
package example.consistent.hash;
public interface HashFunc { long hashCode(String key);}
复制代码
package example.consistent.hash;
import java.security.MessageDigest;import java.security.NoSuchAlgorithmException;
public class MD5HashFunc implements HashFunc{ MessageDigest instance;
public MD5HashFunc() { try { instance = MessageDigest.getInstance("MD5"); } catch (NoSuchAlgorithmException e) { } }
@Override public long hashCode(String key) { instance.reset(); instance.update(key.getBytes()); byte[] digest = instance.digest(); long result = 0; for (int i = 0; i < 4; i++) { result <<= 8; result |= ((int) digest[i]) & 0xFF; } return result; }}
复制代码
package example.consistent.hash;
public interface Node { String getKey(); void incDataCount(); int getDataCount();}
复制代码
package example.consistent.hash;
import java.util.Objects;
public class VirtualNode<T extends Node> implements Node { private T actualNode; private int id;
protected VirtualNode(T actualNode, int id) { if (actualNode == null) { throw new NullPointerException("Null actualNode"); } this.actualNode = actualNode; this.id = id; }
@Override public String getKey() { return String.format("%s#%s", this.actualNode.getKey(), this.id); }
@Override public void incDataCount() { throw new UnsupportedOperationException(); }
@Override public int getDataCount() { throw new UnsupportedOperationException(); }
protected boolean belongsTo(T oneNode) { if (oneNode == null) { throw new NullPointerException(); } return Objects.equals(this.actualNode.getKey(), oneNode.getKey()); }
protected T getActualNode() { return actualNode; }}
复制代码
package example.consistent.hash;
public class MyNode implements Node { private String name; private String ip; private int port; private AtomicInteger dataCount = new AtomicInteger();
public MyNode(String name, String ip, int port) { this.name = name; this.ip = ip; this.port = port; }
@Override public String getKey() { return String.format("%s#%s#%s", name, ip, port); }
@Override public void incDataCount() { dataCount.incrementAndGet(); }
@Override public int getDataCount() { return dataCount.get(); }}
复制代码
package example.consistent.hash;
import java.util.Iterator;import java.util.Objects;import java.util.SortedMap;import java.util.TreeMap;
public class VirtualNodeMgr<T extends Node> implements Router{ private SortedMap<Long, VirtualNode<T>> ring = new TreeMap<>(); private HashFunc hash; private int vNodeCountPerActualNode;
protected VirtualNodeMgr(HashFunc hash, int vNodeCountPerActualNode) { if (hash == null) { throw new NullPointerException(HashFunc.class.getSimpleName()); } this.hash = hash; if (vNodeCountPerActualNode <= 0) { throw new IllegalArgumentException("The number of virtual nodes for each actual node is equal to or smaller than zero!"); } this.vNodeCountPerActualNode = vNodeCountPerActualNode; }
@Override public Node asignTo(String key) { if (ring.isEmpty()) { return null; } Long hashVal = hash.hashCode(key); SortedMap<Long,VirtualNode<T>> tailMap = ring.tailMap(hashVal); Long nodeHashVal = !tailMap.isEmpty() ? tailMap.firstKey() : ring.firstKey(); Node result = null; if (ring.containsKey(nodeHashVal)) { result = ring.get(nodeHashVal).getActualNode(); result.incDataCount(); } return result; }
protected void addNode(T oneNode) {; int existingVNodeCount = getExistingVNodeCount(oneNode); for (int i = 0; i < vNodeCountPerActualNode; i++) { VirtualNode<T> vNode = new VirtualNode<>(oneNode, i + existingVNodeCount); ring.put(hash.hashCode(vNode.getKey()), vNode); } }
protected void delNode(T oneNode) { if (Objects.isNull(oneNode)) { throw new NullPointerException(); } Iterator<Long> it = ring.keySet().iterator(); while (it.hasNext()) { VirtualNode<T> virtualNode = ring.get(it.next()); if (virtualNode.belongsTo(oneNode)) { it.remove(); } } }
private int getExistingVNodeCount(T pNode) { int replicas = 0; for (VirtualNode<T> vNode : ring.values()) { if (vNode.belongsTo(pNode)) { replicas++; } } return replicas; }}
复制代码
package example.consistent.hash;
public interface Router { Node asignTo(String key);}
复制代码
package example.consistent.hash;
public interface NodeMgr<T extends Node> { void add(T oneNode); void del(T oneNode);}
复制代码
package example.consistent.hash;
public class VirtualConsistentHashRouter implements Router, NodeMgr{ private HashFunc myHash = new MD5HashFunc(); private VirtualNodeMgr mgr;
public VirtualConsistentHashRouter(HashFunc yourHash, int vNodeCountPerActualNode) { if (yourHash != null) { myHash = yourHash; } mgr = new VirtualNodeMgr(myHash, vNodeCountPerActualNode); }
public VirtualConsistentHashRouter(){ mgr = new VirtualNodeMgr(myHash, 150); }
@Override public Node asignTo(String key) { return mgr.asignTo(key); }
@Override public void add(Node oneNode) { mgr.addNode(oneNode); }
@Override public void del(Node oneNode) { mgr.delNode(oneNode); }}
复制代码
100 万测试数据模拟
package example.consistent.hash;
import java.util.HashMap;import java.util.Map;import java.util.UUID;
public class Test { private static final int DATA_COUNT = 1000000;
public static void main(String[] args) { MyNode[] nodes = {new MyNode("Jiangsu", "192.168.0.1", 8440), new MyNode("Shandong", "192.168.0.2", 8441), new MyNode("Zhejiang", "192.168.0.3", 8442), new MyNode("Hainan", "192.168.0.4", 8443), new MyNode("Henan", "192.168.0.5", 8444), new MyNode("Hebei", "192.168.0.6", 8445), new MyNode("Shanxi", "192.168.0.7", 8446), new MyNode("Shangxi", "192.168.0.8", 8447), new MyNode("Shandong", "192.168.0.9", 8448), new MyNode("Gansu", "192.168.0.10", 8449)}; VirtualConsistentHashRouter router = new VirtualConsistentHashRouter(); for (MyNode oneNoe : nodes) { router.add(oneNoe); }
long startT = System.currentTimeMillis(); Map<String, Node> data = new HashMap<>(DATA_COUNT); String key = null; Node serviceNode = null; for (int i = 0; i < DATA_COUNT; i++) { key = UUID.randomUUID().toString(); serviceNode = router.asignTo(key); data.put(key, serviceNode); } long endT = System.currentTimeMillis();
int totalDataCount = 0; for ( MyNode oneNode : nodes) { totalDataCount += oneNode.getDataCount(); } int avgDataCountPerNode = totalDataCount / nodes.length; int tmpSum = 0; for ( MyNode oneNode : nodes) { tmpSum += Math.pow(oneNode.getDataCount() - avgDataCountPerNode, 2); } int tmpAvg = tmpSum / nodes.length; System.out.println(String.format("采用虚拟一致性hash算法分布%s个数据耗时：%sms", DATA_COUNT, endT - startT)); System.out.println(String.format("平均每个节点缓存数据个数：%s 总体标准差：%s", avgDataCountPerNode, Math.sqrt(tmpAvg))); }
复制代码
运行结果
参考
https://github.com/Jaskey/ConsistentHash
https://howtodoinjava.com/java/java-security/how-to-generate-secure-password-hash-md5-sha-pbkdf2-bcrypt-examples/
https://blog.csdn.net/weixin_50271247/article/details/108776895
Summary
1、缓存的作用
缓存是性能优化的大杀器。
2、合理使用缓存
使用缓存对提高系统性能有很多好处，但是不合理的使用缓存可能非但不能提高系统的
性能，还会成为系统的累赘，甚至风险。实践中，缓存滥用的情景屡见不鲜——过分依
赖缓存、不合适的数据访问特性等
频繁修改的数据：
这种数据如果缓存起来，由于频繁修改，应用还来不及读取就已失效
或更新，徒增系统负担。一般说来，数据的读写比在 2:1 以上，缓存才有意义。
没有热点的访问：缓存使用内存作为存储，内存资源宝贵而有限，不能将所有数据都缓
存起来，如果应用系统访问数据没有热点，不遵循二八定律，即大部分数据访问不是集
中在小部分数据上，那么缓存就没有意义，因为大部分数据还没有被再次访问就已经被
挤出缓存了。
LRU
数据不一致与脏读：
一般会对缓存的数据设置失效时间，一旦超过失效时间，就要从数
据库中重新加载。因此应用要容忍一定时间的数据不一致，如卖家已经编辑了商品属性，
但是需要过一段时间才能被买家看到。在互联网应用中，这种延迟通常是可以接受的，
但是具体应用仍需慎重对待。还有一种策略是数据更新时立即更新缓存，不过也会带来
更多系统开销和事务一致性的问题。因此数据更新时通知缓存失效，删除该缓存数据，
是一种更加稳妥的做法。
“计算机科学中只有三件事最困难:缓存失效，命名事物，计数错误。”
——Phil Karlton
缓存雪崩：
缓存是为了提高数据读取性能的，缓存数据丢失或者缓存不可用不会影响到
应用程序的处——它可以从数据库直接获取数据。但是随着业务的发展，缓存会承担大
部分的数据访问压力，数据库已经习惯了有缓存的日子，所以当缓存服务崩溃的时候，
数据库会因为完全不能承受如此大的压力而宕机，进而导致整个网站不可用。这种情况，
被称作缓存雪崩，发生这种故障，甚至不能简单的重启缓存服务器和数据库服务器来恢
复网站访问。
缓存预热：
缓存中存放的是热点数据，热点数据又是缓存系统利用 LRU（最近最久未用）
算法对不断访问的数据筛选淘汰出来的，这个过程需要花费较长的时间，在这段时间，
系统的性能和数据库负载都不太好，那么最好在缓存系统启动的时候就把热点数据加载
好，这个缓存预加载手段叫做缓存预热（warm up）。对于一些元数据如城市地名列表、
类目信息，可以启动时加载数据库中全部数据到缓存进行预热。
缓存穿透：
如果不恰当的业务、或者恶意攻击持续高并发的请求某个不存在的数据，因
为缓存没有保存该数据，所有的请求都会落到数据库上，会对数据库造成很大的压力，
甚至崩溃。一个简单的对策是将不存在的数据也缓存起来（其 value 值为 null），并设
定一个较短的失效时间。
3、缓存的关键指标
缓存命中率
•缓存是否有效依赖于能多少次重用同一个缓存响应业务请求，这个度量指标被称作缓存命中
率。
•如果查询一个缓存，十次查询九次能够得到正确结果，那么它的命中率是 90%。
影响缓存命中率的主要指标
• 缓存键集合大小
缓存中的每个对象使用缓存键进行 识别，定位一个对象的唯一方式就是对缓存键执行精
确匹配。例如，如果想为每个商品缓 存在线商品信息，你需要使用商品 ID 作为缓存键。
换句话说，缓存键空间是你的应用能 够生成的所有键的数量。从统计数字上看，应用生
成的唯一键越多，重用的机会越小。例如，如果想基于客户 IP 地址缓存天气数据，则
可能有多达 40 亿个键(这是所有可能的 IP 地址的数量)。如果要基于客户来源国家缓存
天气数据，则可能仅需几百个缓存键(世界上所有国家的数量)。
一定要想办法减少可能的缓存键数量。键数量越少，缓存的效率越高。
• 缓存可使用内存空间
缓存可使用内存空间直接决定了缓存对象的平均大小和缓存对象数量。因为缓存通常存
储在内存中，缓存对象可用空间受到严格限制且 相对昂贵。如果想缓存更多的对象，就
需要先删除老的对象，再添加新的对象。替换(清除)对象会降低缓存命中率，因为缓存对
象被删除后，将来的请求就无法命中了。
物理上能缓存的对象越多，缓存命中率就越高。
• 缓存对象生存时间
缓存对象生存时间称为 TTL（ Time To Live ）。在某些场景中，例如，缓存天气预报数
据 15 分钟没问题。在这个场景下， 你可以设置缓存对象预定义 TTL 为 15 分钟。在其
他场景中，你可能不能冒险使用过于陈旧的数据。例如，在一个电子商务系统中，店铺
管理员可能在任何时刻修改商品价格，如果这些价格需要准确地展示在整个网站中。在
这个场景下，你需要在每次商品价格修改时让缓存失效。
简单讲，对象缓存的时间越长，缓存对象被重用的可能性就越高。
4、通读缓存（read-through）
代理缓存，反向代理缓存，CDN 缓存都是通读缓存。
通读缓存给客户端返回缓存资源，并在请求未命中缓存时获取实际数据。
客户端连接的是通读缓存而不是生成响应的原始服务器。
5、旁路缓存（cache-aside）
的对象，如果不存在或已过期， 应用会连接主数据源来组装对象，并将其保存回对象
缓存中以便将来使用。
6、路由算法
6.1 余数 hash
原理
利用缓存数据 key 的 hash 与服务器台数取余，取余结果即为该“key/value"存储的服务器编号。
优点
算法简单易实现。
缺点
当因业务需要扩容服务器时，大面积相同 key 的 hash 与扩容前的 hash 不一致，缓存不命中，导致需要大面积访问后台数据库或主机资源，进而发生“服务雪崩”，最终无法达到“扩容服务器提升性能”的预期。
6.2 一致性 hash 算法
扩容 NODE3 前
扩容 NODE3 后
原理
为了将大量的未知 Key 的 hash 值恒定地 散落在整个 hash 环上，将缓存数据存放于缓存数据的 key 的 hash 距离最近的缓存服务器中。
优点
解决了“余数 hash”算法的“缺点”。服务器扩容时，仅存在小部分数据命中失败。下图 NODE3 为扩容服务器，NODE2 与 NODE3 之间的数据 KEY0、KEY3 在扩容前数据缓存在 NODE1，扩容后这些数据将会缓存至 NODE3，扩容后首次访问这部分时，在 NODE3 中命中失败，需要为这部分数据从数据库获取。
缺点
缓存数据未均匀地分布至服务器（NODEi)，各个服务器负载不均衡。
6.3 基于虚拟节点的一致性 Hash 算法
原理
为了将大量的未知 Key 的 hash 值均匀地 、恒定地散落在整个 hash 环上，每个 NODE 具有相同个数的虚拟 NODE，所有 NODE 的虚拟 NODE 均均匀地分布在 hash 换上，计算缓存数据 key 的 hash，再将该缓存数据存放到距离其 key 的 hash 距离最近的虚拟 NODE 中。
优点
解决了“一致性 hash 算法”数据分布不均匀的问题。
6.4 其他参考资料
原始论文《Consistent Hashing and Random Trees》链接如下：
相关论文《Web Caching with Consistent Hashing》链接如下：
更多资料：
WikiPedia - Consistent hashing
codeproject - Consistent hashing
https://dzone.com/articles/simple-magic-consistent
https://blog.csdn.net/kefengwang/article/details/81628977
7、EDA 事件驱动架构
8、常见的 MQ 开源组件活跃度：
kafka(Scala)>RocketMQ(Java)>RabbitMQ(Erlang)>ActiveMQ(Java)
评论