實(shí)現(xiàn)
主要實(shí)現(xiàn)基本功能婴氮，不考慮泛型博助、增刪節(jié)點(diǎn)等功能。
主要包括 3 個(gè)類蒸痹。
Cache 接口
定義了 get, put, evict 3 個(gè)
public interface Cache {
Object get(Object key);
void put(Object key, Object value);
void evict(Object key);
}
復(fù)制代碼
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;
}
}
復(fù)制代碼
Node 類
實(shí)現(xiàn)了創(chuàng)建物理節(jié)點(diǎn)以及虛擬節(jié)點(diǎn)的功能，包括 插數(shù)據(jù)胸梆、查數(shù)據(jù)和刪數(shù)據(jù) 3 個(gè)方法敦捧。
虛擬節(jié)點(diǎn)的 Key 直接采用 "<IP>#1", "<IP>#2" 的格式，且每個(gè)物理節(jié)點(diǎn)對(duì)應(yīng)的虛擬節(jié)點(diǎn)數(shù)為 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;
}
}
復(fù)制代碼
ConsistentHashCache 類
一致性 hash 實(shí)現(xiàn)類绪颖，主要實(shí)現(xiàn)了 put秽荤，get 和 evict 方法。
其中菠发，查找 Key 對(duì)應(yīng)的虛擬節(jié)點(diǎn)直接采用了 Java 庫(kù)的 TreeMap 類來(lái)實(shí)現(xiàn)王滤。
此外，還提供了求標(biāo)準(zhǔn)差的工具方法滓鸠。
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());
}
}
復(fù)制代碼
測(cè)試及標(biāo)準(zhǔn)差
測(cè)試的 Key 采用 String 類型，隨機(jī)值利用 Apache Common Lang 的工具類來(lái)生成第喳。
節(jié)點(diǎn)數(shù) 采用 10 個(gè)節(jié)點(diǎn)糜俗。
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));
}
}
復(fù)制代碼
測(cè)試結(jié)果
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
復(fù)制代碼
多次測(cè)試，標(biāo)準(zhǔn)層大致分布在 4000 ~ 9000 之間曲饱。
