memcach中一个具体实现算法：
初始化：
已有server m个和各自权重，构建 40*server个数*4个bucket，每个bucket实际上就是一个long值，按照权重分配给各个server，所有的bucket会分布在2的32次方的空间中，用一个TreeMap来存储。
| 以下是代码片段： double factor = Math .floor(((double) (40 * this.servers.length * thisWeight)) / (double) this.totalWeight); for (long j = 0; j < factor; j++) { //md5结果为16个字节，每4个一组，转成一个long值（在0到2的32次方间） byte[] d = md5.digest((servers[i] + "-" + j).getBytes()); for (int h = 0; h < 4; h++) { Long k = ((long) (d[3 + h * 4] & 0xFF) << 24) | ((long) (d[2 + h * 4] & 0xFF) << 16) | ((long) (d[1 + h * 4] & 0xFF) << 8) | ((long) (d[0 + h * 4] & 0xFF)); consistentBuckets.put(k, servers[i]); } } |
根据key来查找来分配server:
计算key的hash code,从TreeMap中查找大于它的节点，如果有则取第一个，没有则取TreeMap的第一个（相当于一个圆环）
| 以下是代码片段： SortedMap tmap = this.consistentBuckets.tailMap(hv); return (tmap.isEmpty()) ? this.consistentBuckets.firstKey() : tmap .firstKey(); |