Java 实现一致性 Hash 算法实现(训练营第五课)

发布于: 2020 年 07 月 08 日

实现

主要实现基本功能,不考虑泛型、增删节点等功能。

主要包括 3 个类。

Cache 接口

定义了 get, put, evict 3 个

public interface Cache {
Object get(Object key);
void put(Object key, Object value);
void evict(Object key);
}

HashUtils 类

提供了求 hash 的工具方法,采用 FNV1_32_HASH 算法。

public class HashUtils {
/**
* FNV1_32_HASH
*
* @param obj
* object
* @return hashcode
*/
public static int hashcode(Object obj) {
final int p = 16777619;
int hash = (int) 2166136261L;
String str = obj.toString();
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;
}
}

Node 类

实现了创建物理节点以及虚拟节点的功能,包括 插数据、查数据和删数据 3 个方法。

虚拟节点的 Key 直接采用 "<IP>#1", "<IP>#2" 的格式,且每个物理节点对应的虚拟节点数为 200。

一些常量直接写死,未作可配置处理。

public class Node {
private static final int VIRTUAL_NODE_NO_PER_NODE = 200;
private final String ip;
private final List<Integer> virtualNodeHashes = new ArrayList<>(VIRTUAL_NODE_NO_PER_NODE);
private final Map<Object, Object> cacheMap = new HashMap<>();
public Node(String ip) {
Objects.requireNonNull(ip);
this.ip = ip;
initVirtualNodes();
}
private void initVirtualNodes() {
String virtualNodeKey;
for (int i = 1; i <= VIRTUAL_NODE_NO_PER_NODE; i++) {
virtualNodeKey = ip + "#" + i;
virtualNodeHashes.add(HashUtils.hashcode(virtualNodeKey));
}
}
public void addCacheItem(Object key, Object value) {
cacheMap.put(key, value);
}
public Object getCacheItem(Object key) {
return cacheMap.get(key);
}
public void removeCacheItem(Object key) {
cacheMap.remove(key);
}
public List<Integer> getVirtualNodeHashes() {
return virtualNodeHashes;
}
public String getIp() {
return ip;
}
public Map<Object, Object> getCacheMap() {
return cacheMap;
}
}

ConsistentHashCache 类

一致性 hash 实现类,主要实现了 put,get 和 evict 方法。

其中,查找 Key 对应的虚拟节点直接采用了 Java 库的 TreeMap 类来实现。

此外,还提供了求标准差的工具方法。

public class ConsistentHashCache implements Cache {
private final List<Node> nodeList = new ArrayList<>();
private final NavigableMap<Integer, Node> hashRing = new TreeMap<>();
public ConsistentHashCache(Collection<String> ips) {
for (String ip : ips) {
addNode(ip);
}
}
public void addNode(String ip) {
Objects.requireNonNull(ip);
Node node = new Node(ip);
nodeList.add(node);
for (Integer virtualNodeHash : node.getVirtualNodeHashes()) {
hashRing.put(virtualNodeHash, node);
}
}
@Override
public Object get(Object key) {
return findMatchNode(key).getCacheItem(key);
}
@Override
public void put(Object key, Object value) {
findMatchNode(key).addCacheItem(key, value);
}
@Override
public void evict(Object key) {
findMatchNode(key).removeCacheItem(key);
}
private Node findMatchNode(Object key) {
Map.Entry<Integer, Node> entry = hashRing.ceilingEntry(HashUtils.hashcode(key));
if (entry == null) {
entry = hashRing.firstEntry();
}
return entry.getValue();
}
public List<Node> getNodeList() {
return nodeList;
}
public double standardDeviation(int totalItems) {
double sum = 0;
int average = totalItems / nodeList.size();
for (Node node : nodeList) {
sum += Math.pow(node.getCacheMap().size() - average, 2);
}
return Math.sqrt(sum / nodeList.size());
}
}

测试及标准差

测试的 Key 采用 String 类型,随机值利用 Apache Common Lang 的工具类来生成。

节点数 采用 10 个节点。

public class ConsistentHashCacheTest {
public static final String IP_PREFIX = "10.0.";
public static final int NODE_SIZE = 10;
public static final int STRING_COUNT = 1000 * 1000;
private static final Random random = new Random();
private static Cache cache;
private static List<String> sList = new ArrayList<>();
@BeforeClass
public static void setup() {
Set<String> ipSet = new HashSet<>();
do {
String ip = new StringBuilder(IP_PREFIX).append(random.nextInt(255)).append(".").append(random.nextInt(255))
.toString();
if (!ipSet.contains(ip)) {
ipSet.add(ip);
}
} while (ipSet.size() < NODE_SIZE);
for (int i = 0; i < STRING_COUNT; i++) {
sList.add(RandomStringUtils.randomAlphanumeric(10));
}
cache = new ConsistentHashCache(ipSet);
}
@Test
public void test() {
for (String s : sList) {
cache.put(s, s);
}
Assert.assertEquals(sList.get(1), cache.get(sList.get(1)));
Assert.assertEquals(sList.get(10), cache.get(sList.get(10)));
Assert.assertEquals(sList.get(100), cache.get(sList.get(100)));
Assert.assertEquals(sList.get(1000), cache.get(sList.get(1000)));
Assert.assertEquals(sList.get(10000), cache.get(sList.get(10000)));
Assert.assertEquals(sList.get(100000), cache.get(sList.get(100000)));
Assert.assertEquals(sList.get(999999), cache.get(sList.get(999999)));
for (Node node : ((ConsistentHashCache) cache).getNodeList()) {
System.out.println(node.getIp() + " -> " + node.getCacheMap().size());
}
System.out.println("Standard Deviation: " + ((ConsistentHashCache) cache).standardDeviation(STRING_COUNT));
}
}

测试结果

10.0.254.202 -> 97792
10.0.71.172 -> 92942
10.0.149.126 -> 109542
10.0.198.178 -> 91354
10.0.197.26 -> 96427
10.0.249.213 -> 102239
10.0.118.66 -> 90961
10.0.114.202 -> 103897
10.0.206.226 -> 103859
10.0.5.53 -> 110987
Standard Deviation: 6861.2632801839045

多次测试,标准层大致分布在 4000 ~ 9000 之间。

用户头像

看山是山

关注

还未添加个人签名 2018.11.16 加入

还未添加个人简介

评论 (2 条评论)

发布
用户头像
类 ConsistentHashCache:15 漏加了物理节点的hash 值: sortedNodeHash2Node.put(HashUtils.hashcode(node), node);
2020 年 07 月 09 日 09:13
回复
我看大部分资料介绍时,都没有提到物理节点和虚拟节点的 hash 都加到 hash ring。这个加不加好像影响不大呢?
2020 年 07 月 09 日 10:33
回复
是的,我看了好多资料都没加。
2020 年 07 月 12 日 15:38
回复
用户头像
手动点赞
2020 年 07 月 08 日 15:28
回复
没有更多了
Java实现一致性 Hash 算法实现(训练营第五课)