package Cache;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.UUID;
public class TestHashCircle {
    // 机器节点IP前缀
    private static final String IP_PREFIX = "192.168.0.";
    private static final int SERVER_NUMS = 10;
    private static final int VIRTUAL_NUMS = 200;
    private static final int RECORDS = 1000000;
    public static void main(String[] args) {
        // 每台真实机器节点上保存的记录条数
        Map<Node, Integer> map = new HashMap<>();
        // 真实机器节点, 模拟10台
        List<Node> nodes = new ArrayList<>();
        for (int i = 0; i < SERVER_NUMS; i++) {
            Node node = new Node(IP_PREFIX + i, 8070);
            nodes.add(node);
        }
        IHashService iHashService = new HashService();
        // 每台真实机器引入100个虚拟节点
        ConsistentHash<Node> consistentHash = new ConsistentHash<>(iHashService, VIRTUAL_NUMS, nodes);
        // 将5000条记录尽可能均匀的存储到10台机器节点上
        String[] keys = new String[RECORDS];
        for (int i = 0; i < keys.length; i++) {
            // 产生随机一个字符串当做一条记录，可以是其它更复杂的业务对象,比如随机字符串相当于对象的业务唯一标识
            keys[i] = UUID.randomUUID().toString() + i;
            // String data = "key" + (i * 17) + "ss" + i * 19;
        }
        for (String key: keys) {
            // 通过记录找到真实机器节点
            Node node = consistentHash.getServer(key);
            if (!map.containsKey(node)) {
                map.put(node, 0);
            }
            // 再这里可以能过其它工具将记录存储真实机器节点上，比如MemoryCache等
            // ...
            // 每台真实机器节点上保存的记录条数加1
            map.put(node, map.get(node) + 1);
        }
        double[] numbers = new double[SERVER_NUMS];
        // 打印每台真实机器节点保存的记录条数
        for (int i = 0; i < SERVER_NUMS; i++) {
            Node key = nodes.get(i);
            System.out.println(key.toString() + "节点记录条数：" + map.get(key));
            numbers[i] = map.get(key);
        }
        System.out.println("标准差: " + variance(numbers));
    }
    //标准差σ=sqrt(s^2)
    public static double StandardDiviation(double[] x) {
        double sum=0;
        for(int i = 0; i < x.length; i++){//求和
            sum += x[i];
        }
        double dAve = sum / x.length;//求平均值
        double dVar=0;
        for(int i = 0; i < x.length; i++){//求方差
            dVar = dVar + (Math.pow((x[i] - dAve), 2));
        }
        return Math.sqrt(dVar / x.length);
    }
    //标准差
    public static double variance(double[] data) {
        double variance = 0;
        double expect = sum(data) / data.length;
        for (int i = 0; i < data.length; i++) {
            variance = variance + (Math.pow((data[i] - expect), 2));
        }
        variance = variance / data.length;
        return Math.sqrt(variance);
    }
    
    private static double sum(double[] data) {
        double sum = 0;
        for (int i = 0; i < data.length; i++)
            sum = sum + data[i];
        return sum;
    }
}

package Cache;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash<T> {
    // 每个资源分割的节点数量
    private int numberOfReplica;
    // hash object
    private IHashService hashService;
    // 服务器节点list
    private SortedMap<Long, T> circle = new TreeMap<>();
    public ConsistentHash(IHashService hashService, int numberOfReplica,  List<T> servers) {
        this.numberOfReplica = numberOfReplica;
        this.hashService = hashService;
        for(int i=0; i<servers.size(); i++) {
            this.addServer(servers.get(i));
        }
    }
    public void addServer(T node) {
        for (int i=0; i<numberOfReplica; i++) {
            this.circle.put(this.hashService.hash(node.toString() + i), node);
        }
    }
    public void removeServer(T node) {
        for(int i=0; i<numberOfReplica; i++) {
            this.circle.remove(this.hashService.hash(node.toString() + i), node);
        }
    }
    /**
     * 从环上hash最近的位置取node
     * 
     * @param key
     * @return
     */
    public T getServer(String key) {
        if (circle.isEmpty()) return null;
        long hash = hashService.hash(key);
        if (!circle.containsKey(hash)) {
            // tailMap找到大于等于key的所有元素，使用红黑树原理
            SortedMap<Long, T> tailMap = circle.tailMap(hash);
            // 如果环大于hash的部分为空，证明hash值超过最后一个节点
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }
}

package Cache;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
/**
 * hash算法实现
 */
public class HashService implements IHashService {
    /**
     * MurMurHash算法,性能高,碰撞率低
     *
     * @param key String
     * @return Long
     */
    public Long hash(String key) {
        ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
        int seed = 0x1234ABCD;
        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);
            finish.put(buf).rewind();
            h ^= finish.getLong();
            h *= m;
        }
        h ^= h >>> r;
        h *= m;
        h ^= h >>> r;
        buf.order(byteOrder);
        return h;
    }
}

192.168.0.08070节点记录条数：100477
192.168.0.18070节点记录条数：103028
192.168.0.28070节点记录条数：95792
192.168.0.38070节点记录条数：104840
192.168.0.48070节点记录条数：93926
192.168.0.58070节点记录条数：98650
192.168.0.68070节点记录条数：104212
192.168.0.78070节点记录条数：103168
192.168.0.88070节点记录条数：93897
192.168.0.98070节点记录条数：102010
标准差: 3978.8067306668718

// 在WebStorage缓存对象的JavaScript代码
var preferences = {/* data object to be stored */};
localStorage.setItem('preferences', JSON.stringify(preferences));
// 访问缓存对象的JavaScript代码
var cachedData = localStorage.getItem('preferences');
var preferences = JSON.parse(cachedData);

//PHP客户端访问Memcached集群
$m = new Memcached();
//添加服务器集群
$cache->addServers(array(
array('cache1.example.com', 11211),
array('cache2.example.com', 11211),
array('cache3.example.com', 11211)
));
//写缓存，失效时间5分钟
$m->set('userCount', 123, 600);

String create(path, data, acl, flags)
  
void delete(path, expectedVersion)
  
Stat setData(path, data, expectedVersion)
  
(data, Stat) getData(path, watch)
  
Stat exists(path, watch)
  
String[] getChildren(path, watch)
  
void sync(path)
  
List multi(ops)