第五周作业



• 用你熟悉的编程语言实现一致性 hash 算法。

• 编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。



import java.security.MessageDigest;

import java.security.NoSuchAlgorithmException;



public class Util {

public static long getMd5(String key) throws NoSuchAlgorithmException {

String code = "";

MessageDigest m = MessageDigest.getInstance( "MD5" ) ;

m.update( key.getBytes() );

byte s[] = m.digest() ;

for (int i = 0; i < s.length; ++i) {

code += Integer.toHexString(0x000000FF & s[i] | 0Xffffff00).substring( 6 ) ;

}

return Long.parseLong(code.substring( 0, 8 ), 16) ;

}

public double calcStandardDeviation(int totalNumber, int[] arr, int nodeNum) {

double avg = totalNumber*1.0 / nodeNum ;

double total = 0 ;

for (int i = 0; i < arr.length; ++i) {

total += Math.pow(arr[i] -avg, 2) ;

}

return Math.sqrt( total* 1.0 / nodeNum ) ;

}

}



import java.security.MessageDigest;

import java.security.NoSuchAlgorithmException;

public class Util {

public static long getMd5(String key) throws NoSuchAlgorithmException {

String code = "";

MessageDigest m = MessageDigest.getInstance( "MD5" ) ;

m.update( key.getBytes() );

byte s[] = m.digest() ;

for (int i = 0; i < s.length; ++i) {

code += Integer.toHexString(0x000000FF & s[i] | 0Xffffff00).substring( 6 ) ;

}

return Long.parseLong(code.substring( 0, 8 ), 16) ;

}

public double calcStandardDeviation(int totalNumber, int[] arr, int nodeNum) {

double avg = totalNumber*1.0 / nodeNum ;

double total = 0 ;

for (int i = 0; i < arr.length; ++i) {

total += Math.pow(arr[i] -avg, 2) ;

}

return Math.sqrt( total* 1.0 / nodeNum ) ;

}

}



import java.security.NoSuchAlgorithmException;



public class Node {

private int keyNum = 0;

private long lowBound;

private long upBound ;

public Node(long lowBound, long upBound) {

this.lowBound = lowBound ;

this.upBound = upBound;

}

public void addKey(String key) throws NoSuchAlgorithmException {

long code = Util.getMd5( key );

if (code > lowBound && code <= upBound) {

keyNum++;

}

}

public int getKeyNum() {

return keyNum ;

}



}



import java.security.NoSuchAlgorithmException;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

import java.util.Random;

import java.util.TreeMap;



public class ConsistencyHash {

private final Long MAXUINTVALUE = ( long ) ( Math.pow( 2, 32 ) - 1 );

private int virtualNodeNum = 0;

private List<String> hosts = new ArrayList<String>() ;

private Map<Range, Node> range2Node = new HashMap<Range, Node>();

private Map<Long, Integer> ring = new TreeMap<Long, Integer>();

public ConsistencyHash( int virtualNodeNum) {

this.virtualNodeNum = virtualNodeNum ;

}

public void initHashRing() throws NoSuchAlgorithmException {

ring.put( 0l, 0 );

for (String host: hosts) {

for (int i = 0; i < virtualNodeNum; ++i) {

String key = String.format( "%s%04d", host, i ) ;

ring.put(Util.getMd5(key) , 0 ) ;

}

}

ring.put(MAXUINTVALUE , 0 ) ;

long low =-1, up =-1;

for (Long val: ring.keySet()) {

if (low == -1 ) {

low = val ;

}else if (up == -1) {

up = val ;

range2Node.put( new Range(low, up), new Node(low, up) ) ;

low = up; up = -1;

}

}

}

public void addHost(String hostIp) {

hosts.add( hostIp ) ;

}

public void removeNode(String hostIp) {

for (int i = 0; i < virtualNodeNum; ++i) {

String key = String.format( "%s%04d", hostIp, i ) ;

ring.remove( key ) ;

}

hosts.remove( hostIp ) ;

}

public Range findRange(Object[] array, int low , int high, long hashCode) {

int mid = (low + high) / 2;

if ( mid >= 1 && (long)array[mid -1 ] < hashCode && (long)array[mid] >= hashCode) {

return new Range((long)array[mid-1], (long)array[mid]) ;

}else if(mid < array.length - 1 && (long)array[mid] < hashCode && (long)array[mid+1] >= hashCode) {

return new Range((long)array[mid], (long)array[mid+1]) ;

}else if( (long)array[mid] < hashCode) {

return findRange(array, mid+1, high, hashCode) ;

}else {

return findRange(array, low, mid-1, hashCode) ;

}

}

public void addKey(String key) throws NoSuchAlgorithmException {

final Object[] array = ring.keySet().toArray() ;

Range rng = findRange(array, 0, array.length, Util.getMd5(key)) ;

range2Node.get( rng ).addKey( key );

}

private static String buildKey(int size) {

final String CharTbl = "aA0bB1cC2dD3eE4fF5gG6hH7iI8jJ9kK,lL;mM|nN&oO%pP$qQ#rR@sS!tT*uU^vV(wW)xX-yYzZ";

final Random rand = new Random();

StringBuilder builder = new StringBuilder();

for ( int i = 0; i < size; ++i) {

builder.append( CharTbl.charAt(rand.nextInt( CharTbl.length() ) )) ;

}

return builder.toString() ;

}

public double calcStandardDeviation(int totalNumber) {

double avg = totalNumber*1.0 / hosts.size() ;

double total = 0 ;

for (Range rng : range2Node.keySet()) {

double diff = range2Node.get( rng ).getKeyNum() -avg ;

total += diff * diff ;

}

return Math.sqrt( total / hosts.size() ) ;

}

public static void main(String[] args) {

ConsistencyHash cHash = new ConsistencyHash(10) ;

cHash.addHost( "192.168.10.50" );

cHash.addHost( "192.168.10.51" );

cHash.addHost( "192.168.10.52" );

cHash.addHost( "192.168.10.53" );

cHash.addHost( "192.168.10.54" );

cHash.addHost( "192.168.10.55" );

cHash.addHost( "192.168.10.56" );

cHash.addHost( "192.168.10.57" );

cHash.addHost( "192.168.10.58" );

cHash.addHost( "192.168.10.59" );

try {

cHash.initHashRing();

} catch ( NoSuchAlgorithmException e ) {

// TODO Auto-generated catch block

e.printStackTrace();

}

for (int i = 0; i <1000000; ++i) {

try {

cHash.addKey( buildKey(10) );

} catch ( NoSuchAlgorithmException e ) {

// TODO Auto-generated catch block

e.printStackTrace();

}

}

System.out.println( "Standard Deviation: " + cHash.calcStandardDeviation( 1000000 )) ;

}

}

实现可能不是很好，但是完全是自已根据对概念的理解实现的，期待各路大神指点！