hash 一致性算法与优化

老版本hash一致性算法，在10台服务器，分片200情况下，偏移量大约18785。

优化后的算法，在相同情况下，偏移量大约为365。

新版本示意图：



老版本代码如下：

package com.edison.hash



import org.apache.commons.lang3.StringUtils



import java.util.ArrayList



import java.util.Arrays



import java.util.List



import java.util.Random



import java.util.stream.IntStream



* @program:



*



* @author:



* @create:



public class HashBetter



private static int serviceShard = 200



private static int[] services



private static int[] servicesValue



private static int maxInt =Integer.MAX_VALUE



private static Integer count = new Integer(1)



private static Integer countTmp = new Integer(1)



private static Integer currentValue = new Integer(0)



private static Integer currentAdd = new Integer(maxInt / 2 + 1)



private static boolean isFalf = false



public static void buildServices(List<String



services = new int[serviceList.size() * serviceShard]



servicesValue = new int[serviceList.size() * serviceShard]



serviceList.stream().forEach((x) ->



String serviceNum = StringUtils.substringAfter(x, "service_")



for (int i = 0; i < serviceShard; i++



long addTmp



if (isFalf



addTmp = ((long) maxInt / 2) + ((long) currentValue)



} else



addTmp = ((long) currentValue) + ((long) currentAdd)



if (addTmp > maxInt



addTmp = (int) addTmp - maxInt



currentValue=(int) addTmp



services[serviceShard * Integer.parseInt(serviceNum) + i] = currentValue



if (countTmp ==



count=(count * 2)



countTmp=count



currentAdd=(currentAdd/ 2)



isFalf = false



} else



countTmp



if (isFalf



isFalf = false



}else



isFalf=true



})



services = Arrays.stream(services).parallel().sorted().toArray()



public static double calcStd



Integer[] visitData = Arrays.stream(servicesValue).boxed().toArray(Integer[]::new)



double avg = Arrays.stream(visitData).mapToInt(Integer::intValue).average().orElse(0d)



double avgStd = Arrays.stream(visitData).map(count -> Math.pow(count - avg, 2)).mapToDouble(Double::doubleValue).average().orElse(0d)



double std = Math.sqrt(avgStd)



return std



public static void inputKeys(IntStream



intStream.parallel().forEach((x) ->



int currHash = String.valueOf(x).hashCode() & 0x7FFFFFFF



getPoint(0, services.length - 1, currHash)



})



private static void getPoint(int stat, int end, int



if (stat ==



servicesValue[stat] = servicesValue[stat] + 1



} else



if (end == stat +



if (services[stat] >



servicesValue[stat] = servicesValue[stat] + 1



} else if (services[stat] < currHash && currHash < services



servicesValue[end] = servicesValue[end] + 1



} else if (currHash > services



if (end + 1 >= services.length



servicesValue[0] = servicesValue[0] + 1



} else



servicesValue[end + 1] = servicesValue[end + 1] + 1



} else



int i = ((end - stat) / 2) + stat



int tmp = services[i]



if (tmp > currHash && i ==



servicesValue[0] = servicesValue[0] + 1



} else if (tmp > currHash && services[i - 1] <



servicesValue[i] = servicesValue[i] + 1



} else if (tmp >



getPoint(stat, i, currHash)



} else



getPoint(i, end, currHash)



public static void main(String



List<String> serviceList = new ArrayList<>()



for (int i = 0; i < 10; i++



serviceList.add("service_" + i)



HashBetter.buildServices(serviceList)



Random random = new Random()



for (int t = 0; t < 1000; t++



IntStream intStream = random.ints(1000000, 0, Integer.MAX_VALUE)



HashBetter.inputKeys(intStream)



System.out.println(HashBetter.calcStd())



servicesValue = new int[serviceList.size() * serviceShard]



新版本hash一致代码如下：



package com.edison.hash



import org.apache.commons.lang3.StringUtils



import java.util.ArrayList



import java.util.Arrays



import java.util.List



import java.util.Random



import java.util.stream.IntStream



* @program:



*



* @author:



* @create:



public class HashBetter



private static int serviceShard = 200



private static int[] services



private static int[] servicesValue



private static int maxInt =Integer.MAX_VALUE



private static Integer count = new Integer(1)



private static Integer countTmp = new Integer(1)



private static Integer currentValue = new Integer(0)



private static Integer currentAdd = new Integer(maxInt / 2 + 1)



private static boolean isFalf = false



public static void buildServices(List<String



services = new int[serviceList.size() * serviceShard]



servicesValue = new int[serviceList.size() * serviceShard]



serviceList.stream().forEach((x) ->



String serviceNum = StringUtils.substringAfter(x, "service_")



for (int i = 0; i < serviceShard; i++



long addTmp



if (isFalf



addTmp = ((long) maxInt / 2) + ((long) currentValue)



} else



addTmp = ((long) currentValue) + ((long) currentAdd)



if (addTmp > maxInt



addTmp = (int) addTmp - maxInt



currentValue=(int) addTmp



services[serviceShard * Integer.parseInt(serviceNum) + i] = currentValue



if (countTmp ==



count=(count * 2)



countTmp=count



currentAdd=(currentAdd/ 2)



isFalf = false



} else



countTmp



if (isFalf



isFalf = false



}else



isFalf=true



})



services = Arrays.stream(services).parallel().sorted().toArray()



public static double calcStd



Integer[] visitData = Arrays.stream(servicesValue).boxed().toArray(Integer[]::new)



double avg = Arrays.stream(visitData).mapToInt(Integer::intValue).average().orElse(0d)



double avgStd = Arrays.stream(visitData).map(count -> Math.pow(count - avg, 2)).mapToDouble(Double::doubleValue).average().orElse(0d)



double std = Math.sqrt(avgStd)



return std



public static void inputKeys(IntStream



intStream.parallel().forEach((x) ->



int currHash = String.valueOf(x).hashCode() & 0x7FFFFFFF



getPoint(0, services.length - 1, currHash)



})



private static void getPoint(int stat, int end, int



if (stat ==



servicesValue[stat] = servicesValue[stat] + 1



} else



if (end == stat +



if (services[stat] >



servicesValue[stat] = servicesValue[stat] + 1



} else if (services[stat] < currHash && currHash < services



servicesValue[end] = servicesValue[end] + 1



} else if (currHash > services



if (end + 1 >= services.length



servicesValue[0] = servicesValue[0] + 1



} else



servicesValue[end + 1] = servicesValue[end + 1] + 1



} else



int i = ((end - stat) / 2) + stat



int tmp = services[i]



if (tmp > currHash && i ==



servicesValue[0] = servicesValue[0] + 1



} else if (tmp > currHash && services[i - 1] <



servicesValue[i] = servicesValue[i] + 1



} else if (tmp >



getPoint(stat, i, currHash)



} else



getPoint(i, end, currHash)



public static void main(String



List<String> serviceList = new ArrayList<>()



for (int i = 0; i < 10; i++



serviceList.add("service_" + i)



HashBetter.buildServices(serviceList)



Random random = new Random()



for (int t = 0; t < 1000; t++



IntStream intStream = random.ints(1000000, 0, Integer.MAX_VALUE)



HashBetter.inputKeys(intStream)



System.out.println(HashBetter.calcStd())



servicesValue = new int[serviceList.size() * serviceShard]