Week5 一致性 hash 算法

发布于: 6 小时前

算法代码:

算法代码从之前项目中摘出,因为有POD上下线问题,需要动态添加节点,所以有加锁控制。

package camp.week5;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
import java.util.TreeMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class ConsistentHashAlgorithm {
private int numberOfReplicas = 32;
private final TreeMap<Integer, String> hashCircle = new TreeMap<>();
private final Lock lock = new ReentrantLock();
private int nodeSize = 0;
private HashFunction hashFunction = Hashing.md5();
public ConsistentHashAlgorithm(int numberOfReplicas) {
this.numberOfReplicas = numberOfReplicas;
}
public String mappingToNode(String key) {
Integer hash = hashFunction.hashBytes(key.getBytes()).asInt();
try {
lock.lock();
if (!hashCircle.containsKey(hash)) {
Integer ceilingKey = hashCircle.ceilingKey(hash);
hash = (ceilingKey == null ? hashCircle.firstKey() : ceilingKey);
}
} finally {
lock.unlock();
}
return hashCircle.get(hash);
}
public void addMember(String hostIdentifier) {
try {
lock.lock();
if (!hashCircle.containsValue(hostIdentifier)) {
for (int i = 0; i < numberOfReplicas; i++) {
hashCircle.put(hashFunction.hashBytes((hostIdentifier + i).getBytes()).asInt(), hostIdentifier);
}
}
nodeSize++;
} finally {
lock.unlock();
}
}
public void removeMember(String hostIdentifier) {
try {
lock.lock();
for (int i = 0; i < numberOfReplicas; i++) {
hashCircle.remove(hashFunction.hashBytes((hostIdentifier + i).getBytes()).asInt());
}
nodeSize--;
} finally {
lock.unlock();
}
}
}

测试代码:

package camp.week5;
import org.junit.Before;
import org.junit.Test;
import java.util.*;
public class ConsistentHashAlgorithmTest {
List<String> testData = new ArrayList<>();
@Before
public void setup() {
for (int i = 0; i < 1000000; i++) {
testData.add(UUID.randomUUID().toString());
}
}
@Test
public void TestGetMinStandardDeviation() {
int minMode = 0;
double minStandardDeviation = Double.MAX_VALUE;
for (int i = 150; i < 200; i++) {
int numOfReplicas = i;
int numOfNode = 10;
ConsistentHashAlgorithm algorithm = new ConsistentHashAlgorithm(numOfReplicas);
for (int j = 0; j < numOfNode; j++) {
algorithm.addMember("node".concat("_").concat(String.valueOf(j)));
}
Map<String, Integer> mapResult = new HashMap<>();
for (String key : testData) {
String mappingNode = algorithm.mappingToNode(key);
if (!mapResult.containsKey(mappingNode)) {
mapResult.put(mappingNode, 1);
} else {
mapResult.put(mappingNode, mapResult.get(mappingNode) + 1);
}
}
System.out.println("=============================================");
System.out.println("虚拟节点 ".concat(String.valueOf(numOfReplicas)).concat(" 个的对应分布情况:"));
System.out.println(mapResult);
double standardDeviation = getStandardDeviation(mapResult);
System.out.println("对应的标准差为:".concat(String.valueOf(standardDeviation)));
if (standardDeviation < minStandardDeviation) {
minMode = i;
}
}
System.out.println("最小标准差对应的虚拟节点数为:".concat(String.valueOf(minMode)));
}
private double getStandardDeviation(Map<String, Integer> result) {
long sum = 0;
for (Map.Entry<String, Integer> entry : result.entrySet()) {
int sub = entry.getValue() - 100000;
sum += Math.pow(sub, 2);
}
return Math.sqrt(sum / 10);
}
}

输出:

=============================================

虚拟节点 150 个的对应分布情况:

{node0=90048, node1=113077, node2=90241, node3=112142, node4=112597, node5=102893, node6=85721, node7=96532, node8=98887, node9=97862}

对应的标准差为:9494.719637777622

=============================================

虚拟节点 151 个的对应分布情况:

{node0=90645, node1=110489, node2=89873, node3=112644, node4=112784, node5=102572, node6=87820, node7=96630, node8=98741, node9=97802}

对应的标准差为:8922.63094608311

=============================================

虚拟节点 152 个的对应分布情况:

{node0=90977, node1=109347, node2=90999, node3=110698, node4=111911, node5=101220, node6=88069, node7=98893, node8=99083, node9=98803}

对应的标准差为:8083.652454181834

=============================================

虚拟节点 153 个的对应分布情况:

{node0=88749, node1=109455, node2=91549, node3=111732, node4=112340, node5=99810, node6=87712, node7=99133, node8=100712, node9=98808}

对应的标准差为:8550.013976596763

=============================================

虚拟节点 154 个的对应分布情况:

{node0=88477, node1=109932, node2=89208, node3=112913, node4=109285, node5=102264, node6=88152, node7=99519, node8=100487, node9=99763}

对应的标准差为:8642.185545335162

...........................

=============================================

虚拟节点 192 个的对应分布情况:

{node0=97339, node1=111295, node2=92631, node3=101480, node4=112563, node5=97862, node6=87628, node7=104144, node8=97305, node9=97753}

对应的标准差为:7321.896407352401

=============================================

虚拟节点 193 个的对应分布情况:

{node0=97630, node1=111439, node2=92964, node3=98639, node4=111365, node5=97516, node6=90001, node7=104216, node8=98227, node9=98003}

对应的标准差为:6693.615689595572

=============================================

虚拟节点 194 个的对应分布情况:

{node0=98241, node1=111258, node2=92876, node3=98820, node4=110983, node5=98092, node6=89833, node7=104110, node8=97744, node9=98043}

对应的标准差为:6598.685778244028

=============================================

虚拟节点 195 个的对应分布情况:

{node0=99177, node1=109326, node2=92791, node3=100623, node4=110760, node5=97217, node6=89898, node7=105032, node8=98055, node9=97121}

对应的标准差为:6348.03268737646

=============================================

虚拟节点 196 个的对应分布情况:

{node0=98869, node1=108647, node2=91603, node3=100475, node4=110496, node5=97365, node6=90211, node7=106537, node8=98104, node9=97693}

对应的标准差为:6413.799186129856

=============================================

虚拟节点 197 个的对应分布情况:

{node0=102392, node1=104990, node2=91654, node3=100549, node4=110363, node5=97813, node6=90344, node7=105838, node8=98812, node9=97245}

对应的标准差为:5908.2616732842835

=============================================

虚拟节点 198 个的对应分布情况:

{node0=102715, node1=105162, node2=91654, node3=100650, node4=109523, node5=98660, node6=89849, node7=105221, node8=100026, node9=96540}

对应的标准差为:5821.105822779723

=============================================

虚拟节点 199 个的对应分布情况:

{node0=102025, node1=104788, node2=91654, node3=100746, node4=109807, node5=98824, node6=89679, node7=104179, node8=100716, node9=97582}

对应的标准差为:5702.144158121575

最小标准差对应的虚拟节点数为:199

用户头像

TiK

关注

还未添加个人签名 2018.04.26 加入

还未添加个人简介

评论

发布
暂无评论
Week5 一致性hash算法