一致性hash 簡單實現 package com.jackiesteed.algorithms;import java.util.*;/*** 虛擬節點個數需要事先確定好, 而且不能修改.* 核心代碼模擬了一下remapping的邏輯, 如何做到均衡分配.* 如何保證一致性呢? 每次重新分配的時候, 只有被移動的虛擬節點才會收到影響, 保持了一致性.* 一致性hash 簡單實現, 單線程使用* key 固定為String, value 支持泛型* 感覺只是走了下流程, 離實際使用在性能, 并發方面還要改進.* Created by jackie on 5/24/15.*/ public class ConsistentHashMap <T>{/*** 存儲機器id對應的真實ip, 用來做遠程調用.*/private Map<String, Stack<Integer>> realNodeMap;/*** 虛擬節點到真實節點的映射* 虛擬節點數根據現實情況來權衡.* 節點數極大的話, 可以保證趨向于決定均勻分布, 但是remapping的時間開銷交大.* 節點數少, 壓力不一定非常均勻, 但是remapping速度回塊一些.* 但是虛擬節點數, 一定要是服務所需的機器數的N倍之多.*/private String[] virtualRealMap;/*** 用來模擬分布式系統里面的每臺機器* key 是ip, value mock機器里面的存儲, 是個java.util.Map*/private Map<String, Map<String, T>> hostMock;/*** 構造函數里面初始化虛擬節點個數.* @param virtualNodeCount*/public ConsistentHashMap(int virtualNodeCount){virtualRealMap = new String[virtualNodeCount];realNodeMap = new HashMap<String, Stack<Integer>>();hostMock = new HashMap<String, Map<String, T>>();}/*** 對外接口, 寫入數據到分布式存儲里面.* @param key* @param value*/public void put(String key, T value){put(getRealHashCode(key), key, value);}/*** 對外暴露的接口, 從分布式存儲提取數據.* @param key* @return*/public T get(String key){return get(getRealHashCode(key), key);}/*** 根據key計算需要映射的真是機器的id.* @param key* @return*/private String getRealHashCode(String key){//字符串原本的hash值int oriHashCode = key.hashCode();//key對應的虛擬節點的hash值int virtualHashCode = (oriHashCode % virtualRealMap.length + virtualRealMap.length) % virtualRealMap.length;//映射出來的真實String ip = virtualRealMap[virtualHashCode];return ip;}/*** 這個其實就是和真是的數據存儲進行交互了, ip用來訪問真實機器.* @param ip* @param key* @param value*/private void put(String ip, String key, T value){hostMock.get(ip).put(key, value);}/*** realHashCode表示對應機器的id, 從這臺機器上面獲取數據.* @param* @param key* @return*/private T get(String ip, String key){return hostMock.get(ip).get(key);}/*** 添加一臺機器.* @param ip*/public void addHost(String ip){/*** 如果已經存在了, 就不加入*/if(realNodeMap.containsKey(ip))return;hostMock.put(ip, new HashMap<String, T>());//目前還沒有機器加入, 那么需要走特殊的初始化流程if(realNodeMap.isEmpty()){Stack<Integer> virtualIds = new Stack<Integer>();for(int i = 0; i < virtualRealMap.length; i++){virtualRealMap[i] = ip;virtualIds.push(i);}realNodeMap.put(ip, virtualIds);return;}int expectCount = virtualRealMap.length / (realNodeMap.size() + 1);Stack<Integer> virtualIds = new Stack<Integer>();while(virtualIds.size() < expectCount){for(Map.Entry<String, Stack<Integer>> entry : realNodeMap.entrySet()){Stack<Integer> oldVirtualIds = entry.getValue();while(oldVirtualIds.size() > expectCount){int virtualId = oldVirtualIds.pop();virtualRealMap[virtualId] = ip;virtualIds.push(virtualId);}if(virtualIds.size() >= expectCount)break;}}realNodeMap.put(ip, virtualIds);}/*** 從分布式系統里刪除一臺機器* @param ip*/public void deleteHost(String ip){if(!realNodeMap.containsKey(ip))return;hostMock.remove(ip);Stack<Integer> virtualIds = realNodeMap.get(ip);int expectCount = virtualRealMap.length / (realNodeMap.size() - 1);realNodeMap.remove(ip);//說明這是最后一個ip, 沒有辦法把這個ip映射的虛擬節點重新映射了, 直接全部都刪掉.if(realNodeMap.isEmpty()){for(int i = 0; i < virtualRealMap.length; i++){virtualRealMap[i] = null;}return;}while(!virtualIds.isEmpty()){for(Map.Entry<String, Stack<Integer>> entry : realNodeMap.entrySet()){Stack<Integer> oldVirtualIds = entry.getValue();while(oldVirtualIds.size() < expectCount && !virtualIds.isEmpty()){int virtualId = virtualIds.pop();virtualRealMap[virtualId] = ip;oldVirtualIds.push(virtualId);}if(virtualIds.isEmpty())break;}//如果不增加, 有可能永遠分配不出去.expectCount++;}}public void dump(){System.out.println("=====================================================");System.out.println("VirtualNodeCount : " + virtualRealMap.length);for(Map.Entry<String, Stack<Integer>> entry : realNodeMap.entrySet()){System.out.print(entry.getKey() + " : | ");for(Integer virtualId : entry.getValue()){System.out.format("%2d | ", virtualId);}System.out.println();}System.out.println("=====================================================");}public static void main(String[] args){ConsistentHashMap<String> consistentHashMap = new ConsistentHashMap<String>(30);consistentHashMap.addHost("192.168.0.1");consistentHashMap.addHost("192.168.0.2");consistentHashMap.addHost("192.168.0.4");consistentHashMap.addHost("192.168.0.3");consistentHashMap.addHost("192.168.0.8");consistentHashMap.addHost("192.168.0.13");consistentHashMap.addHost("192.168.0.14");consistentHashMap.deleteHost("192.168.0.4");consistentHashMap.deleteHost("192.168.0.1");consistentHashMap.deleteHost("192.168.0.2");consistentHashMap.addHost("123.123.123.123");consistentHashMap.addHost("123.123.123.124");consistentHashMap.addHost("123.123.123.125");consistentHashMap.dump();consistentHashMap.put("jackie", "abc");System.out.println(consistentHashMap.get("jackie"));} }

?

posted on 2015-05-24 23:47?Jackiesteed 閱讀(...) 評論(...) 編輯 收藏

轉載于:https://www.cnblogs.com/jackiesteed/articles/4526848.html

總結

以上是生活随笔為你收集整理的一致性hash 简单实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。