实现
主要实现基本功能，不考虑泛型、增删节点等功能。
主要包括 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 之间。
