五、一致性哈希算法

public class Server {		private String serverName;	//1:up, 2:down	private volatile int status = 1;		public String getServerName() {		return serverName;	}	public void setServerName(String serverName) {		this.serverName = serverName;	}	public int getStatus() {		return status;	}	public void setStatus(int status) {		this.status = status;	}		public boolean isAvailable(){		return this.status == 1;	}		@Override	public String toString() {		return serverName;	}	}

import java.util.List;import java.util.TreeMap;import java.util.Map.Entry;
public class ShardingAlgo {	private TreeMap<Long, Server> nodes;	private final MurmurHash algo = new MurmurHash();		public ShardingAlgo(List<Server> servers, int virtualNodeNum){		initialize(servers, virtualNodeNum);	}		private void initialize(List<Server> servers, int virtualNodeNum) {	    nodes = new TreeMap<Long, Server>();
	    for (int i = 0; i < servers.size(); i++) {	      Server server = servers.get(i);    	  for (int n = 0; n < virtualNodeNum; n++) {    		  nodes.put(this.algo.hash("SHARD-" + i + "-NODE-" + n), server);    	  }	    }	}		public Server getShardInfo2(String key){		Entry<Long, Server> entry = select(algo.hash(key));		/*		while(!entry.getValue().isAvailable()){			entry = select(entry.getKey() + 1);		}		*/		return entry.getValue();	}		private Entry<Long, Server> select(Long hashVal){		Entry<Long, Server> entry = nodes.ceilingEntry(hashVal);		if(entry == null){			entry = nodes.firstEntry();		}		return entry;	}}

/* * Licensed to the Apache Software Foundation (ASF) under one or more contributor license * agreements. See the NOTICE file distributed with this work for additional information regarding * copyright ownership. The ASF licenses this file to You under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance with the License. You may obtain a * copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable * law or agreed to in writing, software distributed under the License is distributed on an "AS IS" * BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License * for the specific language governing permissions and limitations under the License. */
import java.io.UnsupportedEncodingException;import java.nio.ByteBuffer;import java.nio.ByteOrder;
/** * This is a very fast, non-cryptographic hash suitable for general hash-based lookup. See * http://murmurhash.googlepages.com/ for more details. <br> * <p> * The C version of MurmurHash 2.0 found at that site was ported to Java by Andrzej Bialecki (ab at * getopt org). * </p> */public class MurmurHash {  /**   * Hashes bytes in an array.   * @param data The bytes to hash.   * @param seed The seed for the hash.   * @return The 32 bit hash of the bytes in question.   */  public static int hash(byte[] data, int seed) {    return hash(ByteBuffer.wrap(data), seed);  }
  /**   * Hashes bytes in part of an array.   * @param data The data to hash.   * @param offset Where to start munging.   * @param length How many bytes to process.   * @param seed The seed to start with.   * @return The 32-bit hash of the data in question.   */  public static int hash(byte[] data, int offset, int length, int seed) {    return hash(ByteBuffer.wrap(data, offset, length), seed);  }
  /**   * Hashes the bytes in a buffer from the current position to the limit.   * @param buf The bytes to hash.   * @param seed The seed for the hash.   * @return The 32 bit murmur hash of the bytes in the buffer.   */  public static int hash(ByteBuffer buf, int seed) {    // save byte order for later restoration    ByteOrder byteOrder = buf.order();    buf.order(ByteOrder.LITTLE_ENDIAN);
    int m = 0x5bd1e995;    int r = 24;
    int h = seed ^ buf.remaining();
    int k;    while (buf.remaining() >= 4) {      k = buf.getInt();
      k *= m;      k ^= k >>> r;      k *= m;
      h *= m;      h ^= k;    }
    if (buf.remaining() > 0) {      ByteBuffer finish = ByteBuffer.allocate(4).order(ByteOrder.LITTLE_ENDIAN);      // for big-endian version, use this first:      // finish.position(4-buf.remaining());      finish.put(buf).rewind();      h ^= finish.getInt();      h *= m;    }
    h ^= h >>> 13;    h *= m;    h ^= h >>> 15;
    buf.order(byteOrder);    return h;  }
  public static long hash64A(byte[] data, int seed) {    return hash64A(ByteBuffer.wrap(data), seed);  }
  public static long hash64A(byte[] data, int offset, int length, int seed) {    return hash64A(ByteBuffer.wrap(data, offset, length), seed);  }
  public static long hash64A(ByteBuffer buf, int seed) {    ByteOrder byteOrder = buf.order();    buf.order(ByteOrder.LITTLE_ENDIAN);
    long m = 0xc6a4a7935bd1e995L;    int r = 47;
    long h = seed ^ (buf.remaining() * m);
    long k;    while (buf.remaining() >= 8) {      k = buf.getLong();
      k *= m;      k ^= k >>> r;      k *= m;
      h ^= k;      h *= m;    }
    if (buf.remaining() > 0) {      ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);      // for big-endian version, do this first:      // finish.position(8-buf.remaining());      finish.put(buf).rewind();      h ^= finish.getLong();      h *= m;    }
    h ^= h >>> r;    h *= m;    h ^= h >>> r;
    buf.order(byteOrder);    return h;  }
  public long hash(byte[] key) {    return hash64A(key, 0x1234ABCD);  }
  public long hash(String key){    try {		return hash(key.getBytes("UTF-8"));	} catch (UnsupportedEncodingException e) {		throw new RuntimeException(e);	}  }}

import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;

public class ShardingTest {
	public static void main(String[] args) {		//10台服务器		List<Server> servers = new ArrayList<Server>();		for(int i = 0; i < 10; i++){			Server server = new Server();			server.setServerName("server"+i);			server.setStatus(1);			servers.add(server);		}				//n个不同虚拟节点node		int[] nodeNums = {1, 10, 50, 100, 160, 512, 1024, 2048, 5120, 6144, 7168};		//样本数		int sampleSize = 1000000;		batch(servers, nodeNums, sampleSize);			}		public static void batch(List<Server> servers, int[] virtualNodeNum, int sampleSize){		for(int n = 0; n < virtualNodeNum.length; n++){			ShardingAlgo sa = new ShardingAlgo(servers, virtualNodeNum[n]);						//100万样本			Map<Server, Long> s = new HashMap<Server, Long>();			Server server;			for(int i = 0; i < sampleSize; i++){				server = sa.getShardInfo2("key"+i);				s.put(server, s.get(server) == null ? 1 : s.get(server) + 1);			}						System.out.println("虚拟节点数量:"+virtualNodeNum[n]);			System.out.println("请求分布情况:"+s);			Long[] arrays = new Long[s.values().size()];			s.values().toArray(arrays);						SimpleMath simpleMath = new SimpleMath();			double sd = simpleMath.standardDiviation(arrays);			System.out.println("sd:"+sd);		}	}		public static class SimpleMath {
		//标准差σ=sqrt(s^2)		public  double standardDiviation(Long[] x) {			int m=x.length;			double sum=0;			for(int i=0;i<m;i++){//求和			    sum+=x[i];			}			double dAve=sum/m;//求平均值			double dVar=0;			for(int i=0;i<m;i++){//求方差				dVar+=(x[i]-dAve)*(x[i]-dAve);			}			return Math.sqrt(dVar/m);	
		}	}}