hash 一致性算法与优化

发布于: 14 小时前

老版本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]

用户头像

Mr.Monkey

关注

还未添加个人签名 2020.05.28 加入

还未添加个人简介

评论

发布
暂无评论
hash一致性算法与优化