問題背景
1、在解決memcache的分布式存儲的時候，用戶端需要選擇存儲節點；
2、正常取模運算的hash算法：叢集中機器上下線之後，命中率急劇下降，緩存需要重建立立，瞬間會給DB帶來極高的系統負載；
3、一緻性hash算法：叢集中機器上下線之後，能保持較高的命中率。
設計核心點
1、cache遷移少(提高命中率)
2、key分布均勻(負載均衡)
算法解讀
基本思想
不僅僅key進行hash,機器節點本身也進行hash
1、取0~2^32-1的環
2、算機器的hash，劃分區間
3、存取時,算key的hash，選擇區間的機器
圖解參見連結： https://blog.csdn.net/lihao21/article/details/54193868
虛拟節點
一緻性hash解決命中率問題，虛拟節點解決key的分布均勻問題(負載均衡)
1、使用一般的hash運算，伺服器的映射地點的分布非常不均勻；
2、使用虛拟節點的思想，為每個實體節點（伺服器）在圓環上配置設定100～200個點。
3、這樣就能抑制分布不均勻，最大限度地減小伺服器增減時的緩存重新分布。
源碼解讀(采用一緻性hash時，即定義枚舉型變量Locator為CONSISTENT時)
伺服器對于hash區間的割分
KetamaNodeLocator類中
//機器劃分hash區間，記錄在本類的ketamaNodes成員屬性中
protected void setKetamaNodes(List<MemcachedNode> nodes) {
TreeMap<Long, MemcachedNode> newNodeMap =
new TreeMap<Long, MemcachedNode>();
int numReps = config.getNodeRepetitions();
int nodeCount = nodes.size();
int totalWeight = ;
if (isWeightedKetama) {
for (MemcachedNode node : nodes) {
totalWeight += weights.get(node.getSocketAddress());
}
}
for (MemcachedNode node : nodes) {
if (isWeightedKetama) {
//帶權重的一緻性hash算法節點劃分@[email protected]
int thisWeight = weights.get(node.getSocketAddress());
float percent = (float)thisWeight / (float)totalWeight;
int pointerPerServer = (int)((Math.floor((float)(percent * (float)config.getNodeRepetitions() / * (float)nodeCount + ))) * );
for (int i = ; i < pointerPerServer / ; i++) {
for(long position : ketamaNodePositionsAtIteration(node, i)) {
newNodeMap.put(position, node);
getLogger().debug("Adding node %s with weight %s in position %d", node, thisWeight, position);
}
}
} else {
// Ketama does some special work with md5 where it reuses chunks.
// Check to be backwards compatible, the hash algorithm does not
// matter for Ketama, just the placement should always be done using
// MD5
//一緻性hash算法節點劃分@[email protected]
if (hashAlg == DefaultHashAlgorithm.KETAMA_HASH) {
for (int i = ; i < numReps / ; i++) {
for(long position : ketamaNodePositionsAtIteration(node, i)) {
newNodeMap.put(position, node);
getLogger().debug("Adding node %s in position %d", node, position);
}
}
} else {
//非一緻性hash算法節點劃分@[email protected]
for (int i = ; i < numReps; i++) {
newNodeMap.put(hashAlg.hash(config.getKeyForNode(node, i)), node);
}
}
}
}
assert newNodeMap.size() == numReps * nodes.size();
ketamaNodes = newNodeMap;
}
@[email protected]：非一緻性hash算法節點劃分
1、重複numReps次，每次都是計算一個虛拟節點的hash結果
2、計算每個虛拟節點進行hash運算的key值：config.getKeyForNode(node, i)
KetamaNodeKeyFormatter類中
public String getKeyForNode(MemcachedNode node, int repetition) {
// Carrried over from the DefaultKetamaNodeLocatorConfiguration:
// Internal Using the internal map retrieve the socket addresses
// for given nodes.
// I'm aware that this code is inherently thread-unsafe as
// I'm using a HashMap implementation of the map, but the worst
// case ( I believe) is we're slightly in-efficient when
// a node has never been seen before concurrently on two different
// threads, so it the socketaddress will be requested multiple times!
// all other cases should be as fast as possible.
String nodeKey = nodeKeys.get(node);
if (nodeKey == null) {
switch(this.format) {
case LIBMEMCACHED:
InetSocketAddress address = (InetSocketAddress)node.getSocketAddress();
nodeKey = address.getHostName();
if (address.getPort() != ) {
nodeKey += ":" + address.getPort();
}
break;
case SPYMEMCACHED:
nodeKey = String.valueOf(node.getSocketAddress());
if (nodeKey.startsWith("/")) {
nodeKey = nodeKey.substring();
}
break;
default:
assert false;
}
nodeKeys.put(node, nodeKey);
}
return nodeKey + "-" + repetition;
}
計算結果就是"SocketAddress-虛拟節點重複數"(10.10.1.118:11411-0)
3、根據key計算出虛拟節點的hash結果 DefaultHashAlgorithm類中
/**
* Compute the hash for the given key.
*
* @return a positive integer hash
*/
public long hash(final String k) {
long rv = ;
int len = k.length();
switch (this) {
case NATIVE_HASH:
rv = k.hashCode();
break;
case CRC_HASH:
// return (crc32(shift) >> 16) & 0x7fff;
CRC32 crc32 = new CRC32();
crc32.update(KeyUtil.getKeyBytes(k));
rv = (crc32.getValue() >> ) & ;
break;
case FNV1_64_HASH:
// Thanks to [email protected] for the pointer
rv = FNV_64_INIT;
for (int i = ; i < len; i++) {
rv *= FNV_64_PRIME;
rv ^= k.charAt(i);
}
break;
case FNV1A_64_HASH:
rv = FNV_64_INIT;
for (int i = ; i < len; i++) {
rv ^= k.charAt(i);
rv *= FNV_64_PRIME;
}
break;
case FNV1_32_HASH:
rv = FNV_32_INIT;
for (int i = ; i < len; i++) {
rv *= FNV_32_PRIME;
rv ^= k.charAt(i);
}
break;
case FNV1A_32_HASH:
rv = FNV_32_INIT;
for (int i = ; i < len; i++) {
rv ^= k.charAt(i);
rv *= FNV_32_PRIME;
}
break;
case KETAMA_HASH:
byte[] bKey = computeMd5(k);
rv = ((long) (bKey[] & ) << )
| ((long) (bKey[] & ) << )
| ((long) (bKey[] & ) << )
| (bKey[] & );
break;
default:
assert false;
}
return rv & L; /* Truncate to 32-bits */
}
@[email protected]一緻性hash算法節點劃分
1、對于每個節點要算出numReps個虛拟節點，每組算出四個，一共算numReps/4組；
2、算一組四個虛拟節點：ketamaNodePositionsAtIteration(node, i)
KetamaNodeLocator類中
private List<Long> ketamaNodePositionsAtIteration(MemcachedNode node, int iteration) {
List<Long> positions = new ArrayList<Long>();
byte[] digest = DefaultHashAlgorithm.computeMd5(config.getKeyForNode(node, iteration));
for (int h = ; h < ; h++) {
Long k = ((long) (digest[ + h * ] & ) << )
| ((long) (digest[ + h * ] & ) << )
| ((long) (digest[ + h * ] & ) << )
| (digest[h * ] & );
positions.add(k);
}
return positions;
}
config.getKeyForNode(node, iteration)還是取出"SocketAddress-虛拟節點重複數"(10.10.1.118:11411-0)作為key值
DefaultHashAlgorithm類中computeMd5方法用key算出md5值digest位元組數組
digest位元組數組是16位的，每四位一取，倒序拼接成32位的二進制數【(long) (digest[3 + h * 4] & 0xFF) << 24是将相鄰四個位元組中的最後一位以二進制左移32位】，作為虛拟節點最終在hash結果集合内的落點，一組就算出四個虛拟節點的位置
@[email protected]帶權重的一緻性hash算法節點劃分 1、從weights中獲得每個節點的權重(如果是帶權重的節點，之前初始化的時候會設定這裡的值)，算出每個節點權重所占的百分比；
2、根據百分比算出每個節點應該有的虛拟節點數(因為floor的關系，這裡算出來的虛拟節點數可能不等于重複率乘上節點數量，一般會比這個值小一點，原權重比例也會有所偏差，可以以權重2、3、5，重複率13，節點數3進行測算)
3、對于每個節點的虛拟節點，按照4個一組進行計算計算虛拟節點的hash結果ketamaNodePositionsAtIteration(node, i)，和不帶權重的ketama計算方式是一樣的
用戶端對于key值的計算
KetamaNodeLocator類中
public MemcachedNode getPrimary(final String k) {
MemcachedNode rv = getNodeForKey(hashAlg.hash(k));
assert rv != null : "Found no node for key " + k;
return rv;
}
1、根據存儲對象的key計算出hash結果hashAlg.hash(k)，與計算伺服器的虛拟節點hash結果用的是一個方法
2、根據算得的hash坐标在環中找到應該存儲的伺服器節點getNodeForKey(long hash)
MemcachedNode getNodeForKey(long hash) {
final MemcachedNode rv;
if (!ketamaNodes.containsKey(hash)) {
// Java 1.6 adds a ceilingKey method, but I'm still stuck in 1.5
// in a lot of places, so I'm doing this myself.
SortedMap<Long, MemcachedNode> tailMap = getKetamaNodes().tailMap(hash);
if (tailMap.isEmpty()) {
hash = getKetamaNodes().firstKey();
} else {
hash = tailMap.firstKey();
}
}
rv = getKetamaNodes().get(hash);
return rv;
}
判斷hash坐标是否正好坐落在伺服器虛拟節點上，在則直接獲得伺服器節點ip
不在，擷取hash坐标之後的弧，如果之後的弧上沒有伺服器節點ip了，說明應該繞完整個環的尾部，去找環的第一個節點，獲得伺服器節點ip
如果弧上還有伺服器節點ip的話，則選取第一個ip作為應該存儲的伺服器節點ip。
測試結果對比
不同算法結果對比
步驟：
1、将不同的算法枚舉值作為參數傳入，建立不同的memcache用戶端，建立過程根據不同的hash算法計算生成不同的伺服器hash結果集合(存儲在對應用戶端的MemcachedConnection的NodeLocator中)
2、獲得不同算法産生的NodeLocator
3、實驗标本使用線上環境某個長時間段内的大量資料進行測試，計算對應key值hash之後最終選擇的伺服器，統計對于大量資料每個算法的耗時，以及每個伺服器命中數的均勻性。
4、進行三次實驗對比
測試結果：
1st:
FNV1A_64_HASH costs:1184ms, number:2387858 perdata:0.49584188004479324ns.
10.10.1.118:11411 : 555973 , 23.28%
10.16.69.133:11411 : 533208 , 22.33%
10.16.69.135:11411 : 355425 , 14.88%
10.16.6.184:11411 : 235848 , 9.88%
10.10.1.228:11411 : 346293 , 14.50%
10.10.1.208:11411 : 361111 , 15.12%
variance:0.33143952290634493
FNV1_32_HASH costs:1174ms, number:2387858 perdata:0.49165402632819877ns.
10.10.1.118:11411 : 489055 , 20.48%
10.16.69.133:11411 : 395165 , 16.55%
10.16.69.135:11411 : 259880 , 10.88%
10.16.6.184:11411 : 232323 , 9.73%
10.10.1.228:11411 : 277434 , 11.62%
10.10.1.208:11411 : 734001 , 30.74%
variance:0.6438545073606985
KETAMA_HASH costs:2352ms, number:2387858 perdata:0.9849831941430353ns.
10.10.1.118:11411 : 411977 , 17.25%
10.16.69.133:11411 : 449525 , 18.83%
10.16.6.184:11411 : 387824 , 16.24%
10.16.69.135:11411 : 346523 , 14.51%
10.10.1.228:11411 : 382838 , 16.03%
10.10.1.208:11411 : 409171 , 17.14%
variance:0.12852730715084365
NATIVE_HASH costs:1024ms, number:2387858 perdata:0.42883622057928067ns.
10.10.1.118:11411 : 293716 , 12.30%
10.16.69.133:11411 : 209344 , 8.77%
10.16.69.135:11411 : 694618 , 29.09%
10.16.6.184:11411 : 362735 , 15.19%
10.10.1.228:11411 : 191147 , 8.00%
10.10.1.208:11411 : 636298 , 26.65%
variance:0.7987988531108471
CRC_HASH costs:1733ms, number:2387858 perdata:0.7257550490858334ns.
10.10.1.118:11411 : 347616 , 14.56%
10.16.69.133:11411 : 327404 , 13.71%
10.16.6.184:11411 : 459595 , 19.25%
10.16.69.135:11411 : 481764 , 20.18%
10.10.1.228:11411 : 395621 , 16.57%
10.10.1.208:11411 : 375858 , 15.74%
variance:0.1661475366273886
FNV1_64_HASH costs:971ms, number:2387858 perdata:0.4066405958813296ns.
10.10.1.118:11411 : 248007 , 10.39%
10.16.69.133:11411 : 324288 , 13.58%
10.16.6.184:11411 : 1051464 , 44.03%
10.16.69.135:11411 : 239652 , 10.04%
10.10.1.228:11411 : 126840 , 5.31%
10.10.1.208:11411 : 397607 , 16.65%
variance:1.7291444612562392
FNV1A_32_HASH costs:1578ms, number:2387858 perdata:0.660843316478618ns.
10.10.1.118:11411 : 312106 , 13.07%
10.16.69.133:11411 : 253577 , 10.62%
10.16.6.184:11411 : 644748 , 27.00%
10.16.69.135:11411 : 421664 , 17.66%
10.10.1.228:11411 : 323920 , 13.57%
10.10.1.208:11411 : 431843 , 18.08%
variance:0.3926374779645682
2nd:
FNV1A_64_HASH costs:1169ms, number:2387858 perdata:0.4895600994699015ns.
10.10.1.118:11411 : 555973 , 23.28%
10.16.69.133:11411 : 533208 , 22.33%
10.16.69.135:11411 : 355425 , 14.88%
10.16.6.184:11411 : 235848 , 9.88%
10.10.1.228:11411 : 346293 , 14.50%
10.10.1.208:11411 : 361111 , 15.12%
variance:0.33143952290634493
FNV1_32_HASH costs:1205ms, number:2387858 perdata:0.5046363728496418ns.
10.10.1.118:11411 : 489055 , 20.48%
10.16.69.133:11411 : 395165 , 16.55%
10.16.69.135:11411 : 259880 , 10.88%
10.16.6.184:11411 : 232323 , 9.73%
10.10.1.228:11411 : 277434 , 11.62%
10.10.1.208:11411 : 734001 , 30.74%
variance:0.6438545073606985
KETAMA_HASH costs:2314ms, number:2387858 perdata:0.9690693500199761ns.
10.10.1.118:11411 : 411977 , 17.25%
10.16.69.133:11411 : 449525 , 18.83%
10.16.6.184:11411 : 387824 , 16.24%
10.16.69.135:11411 : 346523 , 14.51%
10.10.1.228:11411 : 382838 , 16.03%
10.10.1.208:11411 : 409171 , 17.14%
variance:0.12852730715084365
NATIVE_HASH costs:987ms, number:2387858 perdata:0.4133411618278809ns.
10.10.1.118:11411 : 293716 , 12.30%
10.16.69.133:11411 : 209344 , 8.77%
10.16.69.135:11411 : 694618 , 29.09%
10.16.6.184:11411 : 362735 , 15.19%
10.10.1.228:11411 : 191147 , 8.00%
10.10.1.208:11411 : 636298 , 26.65%
variance:0.7987988531108471
CRC_HASH costs:1718ms, number:2387858 perdata:0.7194732685109416ns.
10.10.1.118:11411 : 347616 , 14.56%
10.16.69.133:11411 : 327404 , 13.71%
10.16.6.184:11411 : 459595 , 19.25%
10.16.69.135:11411 : 481764 , 20.18%
10.10.1.228:11411 : 395621 , 16.57%
10.10.1.208:11411 : 375858 , 15.74%
variance:0.1661475366273886
FNV1_64_HASH costs:1006ms, number:2387858 perdata:0.42129808388941054ns.
10.10.1.118:11411 : 248007 , 10.39%
10.16.69.133:11411 : 324288 , 13.58%
10.16.6.184:11411 : 1051464 , 44.03%
10.16.69.135:11411 : 239652 , 10.04%
10.10.1.228:11411 : 126840 , 5.31%
10.10.1.208:11411 : 397607 , 16.65%
variance:1.7291444612562392
FNV1A_32_HASH costs:1528ms, number:2387858 perdata:0.6399040478956454ns.
10.10.1.118:11411 : 312106 , 13.07%
10.16.69.133:11411 : 253577 , 10.62%
10.16.6.184:11411 : 644748 , 27.00%
10.16.69.135:11411 : 421664 , 17.66%
10.10.1.228:11411 : 323920 , 13.57%
10.10.1.208:11411 : 431843 , 18.08%
variance:0.3926374779645682
3rd：
FNV1A_64_HASH costs:1085ms, number:2387858 perdata:0.45438212825050733ns.
10.10.1.118:11411 : 555973 , 23.28%
10.16.69.133:11411 : 533208 , 22.33%
10.16.69.135:11411 : 355425 , 14.88%
10.16.6.184:11411 : 235848 , 9.88%
10.10.1.228:11411 : 346293 , 14.50%
10.10.1.208:11411 : 361111 , 15.12%
variance:0.33143952290634493
FNV1_32_HASH costs:1199ms, number:2387858 perdata:0.502123660619685ns.
10.10.1.118:11411 : 489055 , 20.48%
10.16.69.133:11411 : 395165 , 16.55%
10.16.69.135:11411 : 259880 , 10.88%
10.16.6.184:11411 : 232323 , 9.73%
10.10.1.228:11411 : 277434 , 11.62%
10.10.1.208:11411 : 734001 , 30.74%
variance:0.6438545073606985
KETAMA_HASH costs:2551ms, number:2387858 perdata:1.0683214831032668ns.
10.10.1.118:11411 : 411977 , 17.25%
10.16.69.133:11411 : 449525 , 18.83%
10.16.6.184:11411 : 387824 , 16.24%
10.16.69.135:11411 : 346523 , 14.51%
10.10.1.228:11411 : 382838 , 16.03%
10.10.1.208:11411 : 409171 , 17.14%
variance:0.12852730715084365
NATIVE_HASH costs:1050ms, number:2387858 perdata:0.43972464024242647ns.
10.10.1.118:11411 : 293716 , 12.30%
10.16.69.133:11411 : 209344 , 8.77%
10.16.69.135:11411 : 694618 , 29.09%
10.16.6.184:11411 : 362735 , 15.19%
10.10.1.228:11411 : 191147 , 8.00%
10.10.1.208:11411 : 636298 , 26.65%
variance:0.7987988531108471
CRC_HASH costs:1806ms, number:2387858 perdata:0.7563263812169736ns.
10.10.1.118:11411 : 347616 , 14.56%
10.16.69.133:11411 : 327404 , 13.71%
10.16.6.184:11411 : 459595 , 19.25%
10.16.69.135:11411 : 481764 , 20.18%
10.10.1.228:11411 : 395621 , 16.57%
10.10.1.208:11411 : 375858 , 15.74%
variance:0.1661475366273886
FNV1_64_HASH costs:1027ms, number:2387858 perdata:0.43009257669425904ns.
10.10.1.118:11411 : 248007 , 10.39%
10.16.69.133:11411 : 324288 , 13.58%
10.16.6.184:11411 : 1051464 , 44.03%
10.16.69.135:11411 : 239652 , 10.04%
10.10.1.228:11411 : 126840 , 5.31%
10.10.1.208:11411 : 397607 , 16.65%
variance:1.7291444612562392
FNV1A_32_HASH costs:1546ms, number:2387858 perdata:0.6474421845855155ns.
10.10.1.118:11411 : 312106 , 13.07%
10.16.69.133:11411 : 253577 , 10.62%
10.16.6.184:11411 : 644748 , 27.00%
10.16.69.135:11411 : 421664 , 17.66%
10.10.1.228:11411 : 323920 , 13.57%
10.10.1.208:11411 : 431843 , 18.08%
variance:0.3926374779645682
說明：每段開頭是采用的hash算法的名稱，number表示處理的總資料量，costs表示總耗時，perdata是計算得到的對于每個資料的平均處理耗時，下面是羅列的每個伺服器對應的ip、命中數和命中占比，variance表示占比計算得到的方差(乘了100倍處理)。
實驗結論：
1、對于同一标本，三次實驗采用各算法，每個伺服器的命中占比是不變的，其中KETAMA_HASH個伺服器命中占比比較均勻，其次表現較好的是CRC_HASH，其他的算法命中占比相差比較大；
2、對于同一标本，三次實驗采用各算法，所耗時間略有波動，綜合來說，NATIVE_HASH和FNV1_64_HASH耗時較少，KETAMA_HASH耗時較多，約是前兩種算法的兩倍，其他算法居于中間。
增減用戶端個數結果對比
步驟：基本步驟和上述相同，本次設定不同的伺服器台數，分别設定伺服器台數為2,4,6台，将結果進行縱向對比
測試結果：
6台：
FNV1A_64_HASH costs:1085ms, number:2387858 perdata:0.45438212825050733ns.
10.10.1.118:11411 : 555973 , 23.28%
10.16.69.133:11411 : 533208 , 22.33%
10.16.69.135:11411 : 355425 , 14.88%
10.16.6.184:11411 : 235848 , 9.88%
10.10.1.228:11411 : 346293 , 14.50%
10.10.1.208:11411 : 361111 , 15.12%
variance:0.33143952290634493
FNV1_32_HASH costs:1199ms, number:2387858 perdata:0.502123660619685ns.
10.10.1.118:11411 : 489055 , 20.48%
10.16.69.133:11411 : 395165 , 16.55%
10.16.69.135:11411 : 259880 , 10.88%
10.16.6.184:11411 : 232323 , 9.73%
10.10.1.228:11411 : 277434 , 11.62%
10.10.1.208:11411 : 734001 , 30.74%
variance:0.6438545073606985
KETAMA_HASH costs:2551ms, number:2387858 perdata:1.0683214831032668ns.
10.10.1.118:11411 : 411977 , 17.25%
10.16.69.133:11411 : 449525 , 18.83%
10.16.6.184:11411 : 387824 , 16.24%
10.16.69.135:11411 : 346523 , 14.51%
10.10.1.228:11411 : 382838 , 16.03%
10.10.1.208:11411 : 409171 , 17.14%
variance:0.12852730715084365
NATIVE_HASH costs:1050ms, number:2387858 perdata:0.43972464024242647ns.
10.10.1.118:11411 : 293716 , 12.30%
10.16.69.133:11411 : 209344 , 8.77%
10.16.69.135:11411 : 694618 , 29.09%
10.16.6.184:11411 : 362735 , 15.19%
10.10.1.228:11411 : 191147 , 8.00%
10.10.1.208:11411 : 636298 , 26.65%
variance:0.7987988531108471
CRC_HASH costs:1806ms, number:2387858 perdata:0.7563263812169736ns.
10.10.1.118:11411 : 347616 , 14.56%
10.16.69.133:11411 : 327404 , 13.71%
10.16.6.184:11411 : 459595 , 19.25%
10.16.69.135:11411 : 481764 , 20.18%
10.10.1.228:11411 : 395621 , 16.57%
10.10.1.208:11411 : 375858 , 15.74%
variance:0.1661475366273886
FNV1_64_HASH costs:1027ms, number:2387858 perdata:0.43009257669425904ns.
10.10.1.118:11411 : 248007 , 10.39%
10.16.69.133:11411 : 324288 , 13.58%
10.16.6.184:11411 : 1051464 , 44.03%
10.16.69.135:11411 : 239652 , 10.04%
10.10.1.228:11411 : 126840 , 5.31%
10.10.1.208:11411 : 397607 , 16.65%
variance:1.7291444612562392
FNV1A_32_HASH costs:1546ms, number:2387858 perdata:0.6474421845855155ns.
10.10.1.118:11411 : 312106 , 13.07%
10.16.69.133:11411 : 253577 , 10.62%
10.16.6.184:11411 : 644748 , 27.00%
10.16.69.135:11411 : 421664 , 17.66%
10.10.1.228:11411 : 323920 , 13.57%
10.10.1.208:11411 : 431843 , 18.08%
variance:0.3926374779645682
4台：
FNV1A_64_HASH costs:1147ms, number:2387858 perdata:0.48034682129339346ns.
10.10.1.118:11411 : 936837 , 39.23%
10.16.6.184:11411 : 713990 , 29.90%
10.10.1.228:11411 : 375920 , 15.74%
10.10.1.208:11411 : 361111 , 15.12%
variance:1.274646297334262
FNV1_32_HASH costs:1074ms, number:2387858 perdata:0.44977548916225335ns.
10.10.1.118:11411 : 809789 , 33.91%
10.16.6.184:11411 : 529418 , 22.17%
10.10.1.228:11411 : 314650 , 13.18%
10.10.1.208:11411 : 734001 , 30.74%
variance:0.9003891935351122
KETAMA_HASH costs:2217ms, number:2387858 perdata:0.928447168969009ns.
10.10.1.118:11411 : 653133 , 27.35%
10.16.6.184:11411 : 621488 , 26.03%
10.10.1.228:11411 : 551835 , 23.11%
10.10.1.208:11411 : 561402 , 23.51%
variance:0.2809445444425362
NATIVE_HASH costs:947ms, number:2387858 perdata:0.39658974696150273ns.
10.10.1.118:11411 : 312854 , 13.10%
10.16.6.184:11411 : 884987 , 37.06%
10.10.1.228:11411 : 191147 , 8.00%
10.10.1.208:11411 : 998870 , 41.83%
variance:2.3979443120759343
CRC_HASH costs:1574ms, number:2387858 perdata:0.6591681749919802ns.
10.10.1.118:11411 : 411390 , 17.23%
10.16.6.184:11411 : 845242 , 35.40%
10.10.1.228:11411 : 564908 , 23.66%
10.10.1.208:11411 : 566318 , 23.72%
variance:0.679887523513382
FNV1_64_HASH costs:976ms, number:2387858 perdata:0.40873452273962685ns.
10.10.1.118:11411 : 248007 , 10.39%
10.16.6.184:11411 : 1270549 , 53.21%
10.10.1.228:11411 : 471695 , 19.75%
10.10.1.208:11411 : 397607 , 16.65%
variance:3.016301833895297
FNV1A_32_HASH costs:1326ms, number:2387858 perdata:0.5553094028204357ns.
10.10.1.118:11411 : 413146 , 17.30%
10.16.6.184:11411 : 1056172 , 44.23%
10.10.1.228:11411 : 443434 , 18.57%
10.10.1.208:11411 : 475106 , 19.90%
variance:1.4911808957900026
2台：
FNV1A_64_HASH costs:1202ms, number:2387858 perdata:0.5033800167346635ns.
10.10.1.118:11411 : 1937413 , 81.14%
10.10.1.208:11411 : 450445 , 18.86%
variance:18.694518863029643
FNV1_32_HASH costs:1126ms, number:2387858 perdata:0.471552328488545ns.
10.10.1.118:11411 : 809789 , 33.91%
10.10.1.208:11411 : 1578069 , 66.09%
variance:11.587986880910444
KETAMA_HASH costs:2202ms, number:2387858 perdata:0.9221653883941173ns.
10.10.1.118:11411 : 1334362 , 55.88%
10.10.1.208:11411 : 1053496 , 44.12%
variance:9.345876737253043
NATIVE_HASH costs:1062ms, number:2387858 perdata:0.44475006470233996ns.
10.10.1.118:11411 : 1073300 , 44.95%
10.10.1.208:11411 : 1314558 , 55.05%
variance:9.255203403228546
CRC_HASH costs:1577ms, number:2387858 perdata:0.6604245311069586ns.
10.10.1.118:11411 : 959036 , 40.16%
10.10.1.208:11411 : 1428822 , 59.84%
variance:9.96766081685872
FNV1_64_HASH costs:1057ms, number:2387858 perdata:0.4426561378440426ns.
10.10.1.118:11411 : 712144 , 29.82%
10.10.1.208:11411 : 1675714 , 70.18%
variance:13.070891761052566
FNV1A_32_HASH costs:1317ms, number:2387858 perdata:0.5515403344755007ns.
10.10.1.118:11411 : 1023129 , 42.85%
10.10.1.208:11411 : 1364729 , 57.15%
variance:9.511633224617519
實驗結論：
1、不同的伺服器台數對于命中率的均勻性是有影響的；
2、KETAMA_HASH在各數量台數伺服器的情況下表現的命中均勻性都比較好；
3、CRC_HASH和FNV1A_32_HASH在某些情況下均勻性較好，某些情況下較差，具有波動性；
4、其他hash算法在各種情況下表現得均勻性都很差。
不同用戶端ip對于均勻性的影響
步驟：基本步驟和上述相同，本次設定伺服器台數為4台，三次實驗伺服器ip不同，對比三次結果伺服器命中率均勻性的不同 實驗結果：
FNV1A_64_HASH costs:1092ms, number:2387858 perdata:0.45731362585212354ns.
10.10.1.118:11411 : 936837 , 39.23%
10.16.6.184:11411 : 713990 , 29.90%
10.10.1.228:11411 : 375920 , 15.74%
10.10.1.208:11411 : 361111 , 15.12%
variance:1.274646297334262
FNV1_32_HASH costs:1213ms, number:2387858 perdata:0.5079866558229175ns.
10.10.1.118:11411 : 809789 , 33.91%
10.16.6.184:11411 : 529418 , 22.17%
10.10.1.228:11411 : 314650 , 13.18%
10.10.1.208:11411 : 734001 , 30.74%
variance:0.9003891935351122
KETAMA_HASH costs:2372ms, number:2387858 perdata:0.9933589015762244ns.
10.10.1.118:11411 : 653133 , 27.35%
10.16.6.184:11411 : 621488 , 26.03%
10.10.1.228:11411 : 551835 , 23.11%
10.10.1.208:11411 : 561402 , 23.51%
variance:0.2809445444425362
NATIVE_HASH costs:1142ms, number:2387858 perdata:0.4782528944350962ns.
10.10.1.118:11411 : 312854 , 13.10%
10.16.6.184:11411 : 884987 , 37.06%
10.10.1.228:11411 : 191147 , 8.00%
10.10.1.208:11411 : 998870 , 41.83%
variance:2.3979443120759343
CRC_HASH costs:1722ms, number:2387858 perdata:0.7211484099975795ns.
10.10.1.118:11411 : 411390 , 17.23%
10.16.6.184:11411 : 845242 , 35.40%
10.10.1.228:11411 : 564908 , 23.66%
10.10.1.208:11411 : 566318 , 23.72%
variance:0.679887523513382
FNV1_64_HASH costs:1094ms, number:2387858 perdata:0.45815119659544246ns.
10.10.1.118:11411 : 248007 , 10.39%
10.16.6.184:11411 : 1270549 , 53.21%
10.10.1.228:11411 : 471695 , 19.75%
10.10.1.208:11411 : 397607 , 16.65%
variance:3.016301833895297
FNV1A_32_HASH costs:1443ms, number:2387858 perdata:0.6043072913045918ns.
10.10.1.118:11411 : 413146 , 17.30%
10.16.6.184:11411 : 1056172 , 44.23%
10.10.1.228:11411 : 443434 , 18.57%
10.10.1.208:11411 : 475106 , 19.90%
variance:1.4911808957900026
FNV1A_64_HASH costs:1059ms, number:2387858 perdata:0.4434937085873616ns.
10.10.1.118:11411 : 555973 , 23.28%
10.16.69.133:11411 : 995377 , 41.68%
10.16.69.135:11411 : 386063 , 16.17%
10.10.1.208:11411 : 450445 , 18.86%
variance:1.2424831477658953
FNV1_32_HASH costs:1172ms, number:2387858 perdata:0.49081645558487985ns.
10.10.1.118:11411 : 489055 , 20.48%
10.16.69.133:11411 : 752254 , 31.50%
10.16.69.135:11411 : 382095 , 16.00%
10.10.1.208:11411 : 764454 , 32.01%
variance:0.7322146248064811
KETAMA_HASH costs:2288ms, number:2387858 perdata:0.9581809303568303ns.
10.10.1.118:11411 : 672247 , 28.15%
10.16.69.133:11411 : 599286 , 25.10%
10.16.69.135:11411 : 525914 , 22.02%
10.10.1.208:11411 : 590411 , 24.73%
variance:0.29719492884167864
NATIVE_HASH costs:999ms, number:2387858 perdata:0.41836658628779433ns.
10.10.1.118:11411 : 605520 , 25.36%
10.16.69.133:11411 : 380544 , 15.94%
10.16.69.135:11411 : 694618 , 29.09%
10.10.1.208:11411 : 707176 , 29.62%
variance:0.5507515972060639
CRC_HASH costs:1719ms, number:2387858 perdata:0.719892053882601ns.
10.10.1.118:11411 : 638712 , 26.75%
10.16.69.133:11411 : 499041 , 20.90%
10.16.69.135:11411 : 707826 , 29.64%
10.10.1.208:11411 : 542279 , 22.71%
variance:0.3666839176114445
FNV1_64_HASH costs:936ms, number:2387858 perdata:0.39198310787324875ns.
10.10.1.118:11411 : 263803 , 11.05%
10.16.69.133:11411 : 427774 , 17.91%
10.16.69.135:11411 : 716761 , 30.02%
10.10.1.208:11411 : 979520 , 41.02%
variance:1.5667703845361418
FNV1A_32_HASH costs:1390ms, number:2387858 perdata:0.5821116666066407ns.
10.10.1.118:11411 : 428731 , 17.95%
10.16.69.133:11411 : 796957 , 33.38%
10.16.69.135:11411 : 618340 , 25.90%
10.10.1.208:11411 : 543830 , 22.77%
variance:0.5638433094805416
FNV1A_64_HASH costs:1030ms, number:2387858 perdata:0.4313489328092374ns.
10.16.69.133:11411 : 533208 , 22.33%
10.16.6.184:11411 : 1144370 , 47.92%
10.16.69.135:11411 : 363987 , 15.24%
10.10.1.228:11411 : 346293 , 14.50%
variance:2.0951521038180405
FNV1_32_HASH costs:1035ms, number:2387858 perdata:0.43344285966753465ns.
10.16.69.133:11411 : 395165 , 16.55%
10.16.69.135:11411 : 760587 , 31.85%
10.16.6.184:11411 : 232323 , 9.73%
10.10.1.228:11411 : 999783 , 41.87%
variance:1.8403633087057236
KETAMA_HASH costs:2251ms, number:2387858 perdata:0.9426858716054305ns.
10.16.69.133:11411 : 664844 , 27.84%
10.16.6.184:11411 : 634944 , 26.59%
10.16.69.135:11411 : 530538 , 22.22%
10.10.1.228:11411 : 557532 , 23.35%
variance:0.3026909579301235
NATIVE_HASH costs:936ms, number:2387858 perdata:0.39198310787324875ns.
10.16.69.133:11411 : 209344 , 8.77%
10.16.69.135:11411 : 985967 , 41.29%
10.16.6.184:11411 : 362735 , 15.19%
10.10.1.228:11411 : 829812 , 34.75%
variance:2.0505247156316835
CRC_HASH costs:1637ms, number:2387858 perdata:0.6855516534065259ns.
10.16.69.133:11411 : 537661 , 22.52%
10.16.6.184:11411 : 581728 , 24.36%
10.16.69.135:11411 : 511612 , 21.43%
10.10.1.228:11411 : 756857 , 31.70%
variance:0.41047254512820197
FNV1_64_HASH costs:973ms, number:2387858 perdata:0.4074781666246486ns.
10.16.69.133:11411 : 607950 , 25.46%
10.16.6.184:11411 : 1144065 , 47.91%
10.16.69.135:11411 : 239652 , 10.04%
10.10.1.228:11411 : 396191 , 16.59%
variance:2.299425018737725
FNV1A_32_HASH costs:1335ms, number:2387858 perdata:0.5590784711653708ns.
10.16.69.133:11411 : 557717 , 23.36%
10.16.6.184:11411 : 729101 , 30.53%
10.16.69.135:11411 : 653616 , 27.37%
10.10.1.228:11411 : 447424 , 18.74%
variance:0.44542802226614386
實驗結論：
1、不同的伺服器ip對于每個算法的伺服器分布均勻性都有影響；
2、NATIVE_HASH受伺服器ip的影響特别大；
3、KETAMA_HASH受伺服器ip影響較小，且能保持良好的均勻性，CRC_HASH在某些情況下均勻性較好，某些情況下較差；
4、其他hash算法在各種情況下表現得均勻性都很差。
設定不同虛拟節點倍數
步驟：
1、控制虛拟節點倍數的是numReps變量，它在KetamaNodeLocatorConfiguration接口中定義，用getNodeRepetitions()方法獲得；
2、KetamaNodeLocatorConfiguration會在ConnectionFactoryBuilder進行build的時候，在createLocator方法中構造KetamaNodeLocator時被傳入KetamaNodeLocator中；
3、memcache預設使用的ConnectionFactoryBuilder會在build的時候将預設的DefaultKetamaNodeLocatorConfiguration載入KetamaNodeLocator，他的numReps預設為160且不可修改
private final int numReps = ;
4、自己編寫一個ConnectionFactoryBuilder，在build的時候，重寫createLocator方法時，傳入自己的MyKetamaNodeLocatorConfiguration,在自己的MyKetamaNodeLocatorConfiguration中重新設定numReps的值為160,320,480,640,1600,3200,對比實驗結果。
測試結果：
FNV1A_64_HASH
160：
FNV1A_64_HASH costs:1176ms, number:2387858 perdata:0.49249159707151763ns.
10.10.1.118:11411 : 555973 , 23.28%
10.16.69.133:11411 : 533208 , 22.33%
10.16.69.135:11411 : 355425 , 14.88%
10.16.6.184:11411 : 235848 , 9.88%
10.10.1.228:11411 : 346293 , 14.50%
10.10.1.208:11411 : 361111 , 15.12%
variance:0.33143952290634493
320：
FNV1A_64_HASH costs:1362ms, number:2387858 perdata:0.570385676200176ns.
10.10.1.118:11411 : 441835 , 18.50%
10.16.69.133:11411 : 480306 , 20.11%
10.16.69.135:11411 : 355425 , 14.88%
10.16.6.184:11411 : 318742 , 13.35%
10.10.1.228:11411 : 431662 , 18.08%
10.10.1.208:11411 : 359888 , 15.07%
variance:0.16774724292381052
480：
FNV1A_64_HASH costs:1241ms, number:2387858 perdata:0.5197126462293822ns.
10.10.1.118:11411 : 193664 , 8.11%
10.16.69.133:11411 : 479463 , 20.08%
10.16.69.135:11411 : 355425 , 14.88%
10.16.6.184:11411 : 373414 , 15.64%
10.10.1.228:11411 : 432505 , 18.11%
10.10.1.208:11411 : 553387 , 23.18%
variance:0.3336763701976884
640：
FNV1A_64_HASH costs:1379ms, number:2387858 perdata:0.5775050275183867ns.
10.10.1.118:11411 : 373886 , 15.66%
10.16.69.133:11411 : 479463 , 20.08%
10.16.6.184:11411 : 427466 , 17.90%
10.16.69.135:11411 : 382256 , 16.01%
10.10.1.228:11411 : 432505 , 18.11%
10.10.1.208:11411 : 292282 , 12.24%
variance:0.17161969978829905
1600：
FNV1A_64_HASH costs:1766ms, number:2387858 perdata:0.7395749663505954ns.
10.10.1.118:11411 : 545111 , 22.83%
10.16.69.133:11411 : 613142 , 25.68%
10.16.6.184:11411 : 289263 , 12.11%
10.16.69.135:11411 : 346545 , 14.51%
10.10.1.228:11411 : 446566 , 18.70%
10.10.1.208:11411 : 147231 , 6.17%
variance:0.5426740049801704
3200：
FNV1A_64_HASH costs:2211ms, number:2387858 perdata:0.9259344567390523ns.
10.10.1.118:11411 : 455113 , 19.06%
10.16.69.133:11411 : 346512 , 14.51%
10.16.69.135:11411 : 443590 , 18.58%
10.16.6.184:11411 : 389935 , 16.33%
10.10.1.228:11411 : 410865 , 17.21%
10.10.1.208:11411 : 341843 , 14.32%
variance:0.14436196587267802
FNV1_32_HASH
160：
FNV1_32_HASH costs:1205ms, number:2387858 perdata:0.5046363728496418ns.
10.10.1.118:11411 : 489055 , 20.48%
10.16.69.133:11411 : 395165 , 16.55%
10.16.69.135:11411 : 259880 , 10.88%
10.16.6.184:11411 : 232323 , 9.73%
10.10.1.228:11411 : 277434 , 11.62%
10.10.1.208:11411 : 734001 , 30.74%
variance:0.6438545073606985
320：
FNV1_32_HASH costs:1389ms, number:2387858 perdata:0.5816928812349813ns.
10.10.1.118:11411 : 489184 , 20.49%
10.16.69.133:11411 : 333188 , 13.95%
10.16.69.135:11411 : 362610 , 15.19%
10.16.6.184:11411 : 483796 , 20.26%
10.10.1.228:11411 : 350105 , 14.66%
10.10.1.208:11411 : 368975 , 15.45%
variance:0.1820378975835861
480：
FNV1_32_HASH costs:1506ms, number:2387858 perdata:0.6306907697191374ns.
10.10.1.118:11411 : 473926 , 19.85%
10.16.69.133:11411 : 319241 , 13.37%
10.16.69.135:11411 : 414314 , 17.35%
10.16.6.184:11411 : 465959 , 19.51%
10.10.1.228:11411 : 335353 , 14.04%
10.10.1.208:11411 : 379065 , 15.87%
variance:0.17289055882258353
640：
FNV1_32_HASH costs:1552ms, number:2387858 perdata:0.6499548968154722ns.
10.10.1.118:11411 : 482243 , 20.20%
10.16.69.133:11411 : 318593 , 13.34%
10.16.69.135:11411 : 445108 , 18.64%
10.16.6.184:11411 : 477512 , 20.00%
10.10.1.228:11411 : 320861 , 13.44%
10.10.1.208:11411 : 343541 , 14.39%
variance:0.20131515448144954
1600：
FNV1_32_HASH costs:1945ms, number:2387858 perdata:0.8145375478776377ns.
10.10.1.118:11411 : 392205 , 16.42%
10.16.69.133:11411 : 460475 , 19.28%
10.16.69.135:11411 : 329994 , 13.82%
10.16.6.184:11411 : 576403 , 24.14%
10.10.1.228:11411 : 278081 , 11.65%
10.10.1.208:11411 : 350700 , 14.69%
variance:0.2777437217142079
3200：
FNV1_32_HASH costs:2156ms, number:2387858 perdata:0.9029012612977824ns.
10.10.1.118:11411 : 409141 , 17.13%
10.16.69.133:11411 : 539964 , 22.61%
10.16.6.184:11411 : 280652 , 11.75%
10.16.69.135:11411 : 363105 , 15.21%
10.10.1.228:11411 : 348210 , 14.58%
10.10.1.208:11411 : 446786 , 18.71%
variance:0.22839794624712736
KETAMA_HASH
160：
KETAMA_HASH costs:2311ms, number:2387858 perdata:0.9678129939049976ns.
10.10.1.118:11411 : 411977 , 17.25%
10.16.69.133:11411 : 449525 , 18.83%
10.16.6.184:11411 : 387824 , 16.24%
10.16.69.135:11411 : 346523 , 14.51%
10.10.1.228:11411 : 382838 , 16.03%
10.10.1.208:11411 : 409171 , 17.14%
variance:0.12852730715084365
320：
KETAMA_HASH costs:2499ms, number:2387858 perdata:1.046544643776975ns.
10.10.1.118:11411 : 391581 , 16.40%
10.16.69.133:11411 : 438704 , 18.37%
10.16.6.184:11411 : 390527 , 16.35%
10.16.69.135:11411 : 348138 , 14.58%
10.10.1.228:11411 : 396903 , 16.62%
10.10.1.208:11411 : 422005 , 17.67%
variance:0.1251928291794245
480：
KETAMA_HASH costs:2526ms, number:2387858 perdata:1.0578518488117803ns.
10.10.1.118:11411 : 388526 , 16.27%
10.16.69.133:11411 : 416766 , 17.45%
10.16.6.184:11411 : 420646 , 17.62%
10.16.69.135:11411 : 368347 , 15.43%
10.10.1.228:11411 : 383291 , 16.05%
10.10.1.208:11411 : 410282 , 17.18%
variance:0.11754543766219773
640：
KETAMA_HASH costs:2587ms, number:2387858 perdata:1.0833977564830068ns.
10.10.1.118:11411 : 409084 , 17.13%
10.16.69.133:11411 : 393467 , 16.48%
10.16.6.184:11411 : 404729 , 16.95%
10.16.69.135:11411 : 377004 , 15.79%
10.10.1.228:11411 : 398191 , 16.68%
10.10.1.208:11411 : 405383 , 16.98%
variance:0.11311062154023681
1600：
KETAMA_HASH costs:2674ms, number:2387858 perdata:1.1198320838173794ns.
10.10.1.118:11411 : 393722 , 16.49%
10.16.69.133:11411 : 405244 , 16.97%
10.16.6.184:11411 : 389027 , 16.29%
10.16.69.135:11411 : 396296 , 16.60%
10.10.1.228:11411 : 415356 , 17.39%
10.10.1.208:11411 : 388213 , 16.26%
variance:0.11272230273956219
3200：
KETAMA_HASH costs:2927ms, number:2387858 perdata:1.2257847828472213ns.
10.10.1.118:11411 : 389331 , 16.30%
10.16.69.133:11411 : 397212 , 16.63%
10.16.69.135:11411 : 400242 , 16.76%
10.16.6.184:11411 : 397344 , 16.64%
10.10.1.228:11411 : 404854 , 16.95%
10.10.1.208:11411 : 398875 , 16.70%
variance:0.11148809000778596
NATIVE_HASH
160：
NATIVE_HASH costs:990ms, number:2387858 perdata:0.4145975179428592ns.
10.10.1.118:11411 : 293716 , 12.30%
10.16.69.133:11411 : 209344 , 8.77%
10.16.69.135:11411 : 694618 , 29.09%
10.16.6.184:11411 : 362735 , 15.19%
10.10.1.228:11411 : 191147 , 8.00%
10.10.1.208:11411 : 636298 , 26.65%
variance:0.7987988531108471
320：
NATIVE_HASH costs:1036ms, number:2387858 perdata:0.4338616450391941ns.
10.10.1.118:11411 : 293718 , 12.30%
10.16.69.133:11411 : 209343 , 8.77%
10.16.69.135:11411 : 694617 , 29.09%
10.16.6.184:11411 : 362735 , 15.19%
10.10.1.228:11411 : 191146 , 8.00%
10.10.1.208:11411 : 636299 , 26.65%
variance:0.7987996050576887
480：
NATIVE_HASH costs:1042ms, number:2387858 perdata:0.43637435726915086ns.
10.10.1.118:11411 : 293719 , 12.30%
10.16.69.133:11411 : 209342 , 8.77%
10.16.69.135:11411 : 694616 , 29.09%
10.16.6.184:11411 : 362735 , 15.19%
10.10.1.228:11411 : 191146 , 8.00%
10.10.1.208:11411 : 636300 , 26.65%
variance:0.7987997573996342
640：
NATIVE_HASH costs:1042ms, number:2387858 perdata:0.43637435726915086ns.
10.10.1.118:11411 : 293720 , 12.30%
10.16.69.133:11411 : 209342 , 8.77%
10.16.69.135:11411 : 694616 , 29.09%
10.16.6.184:11411 : 362735 , 15.19%
10.10.1.228:11411 : 191145 , 8.00%
10.10.1.208:11411 : 636300 , 26.65%
variance:0.7988003570512985
1600：
NATIVE_HASH costs:1097ms, number:2387858 perdata:0.4594075527104208ns.
10.10.1.118:11411 : 300948 , 12.60%
10.16.69.133:11411 : 209342 , 8.77%
10.16.69.135:11411 : 587836 , 24.62%
10.16.6.184:11411 : 375217 , 15.71%
10.10.1.228:11411 : 171437 , 7.18%
10.10.1.208:11411 : 743078 , 31.12%
variance:0.8476458026756032
3200：
NATIVE_HASH costs:1132ms, number:2387858 perdata:0.4740650407185017ns.
10.10.1.118:11411 : 300980 , 12.60%
10.16.69.133:11411 : 209342 , 8.77%
10.16.69.135:11411 : 587799 , 24.62%
10.16.6.184:11411 : 375214 , 15.71%
10.10.1.228:11411 : 171408 , 7.18%
10.10.1.208:11411 : 743115 , 31.12%
variance:0.8477000496670247
CRC_HASH
160：
CRC_HASH costs:1770ms, number:2387858 perdata:0.7412501078372332ns.
10.10.1.118:11411 : 347616 , 14.56%
10.16.69.133:11411 : 327404 , 13.71%
10.16.6.184:11411 : 459595 , 19.25%
10.16.69.135:11411 : 481764 , 20.18%
10.10.1.228:11411 : 395621 , 16.57%
10.10.1.208:11411 : 375858 , 15.74%
variance:0.1661475366273886
320：
CRC_HASH costs:1843ms, number:2387858 perdata:0.7718214399683734ns.
10.10.1.118:11411 : 291374 , 12.20%
10.16.69.133:11411 : 387281 , 16.22%
10.16.6.184:11411 : 462735 , 19.38%
10.16.69.135:11411 : 371289 , 15.55%
10.10.1.228:11411 : 489835 , 20.51%
10.10.1.208:11411 : 385344 , 16.14%
variance:0.1841338067695997
480：
CRC_HASH costs:1873ms, number:2387858 perdata:0.784385001118157ns.
10.10.1.118:11411 : 375365 , 15.72%
10.16.69.133:11411 : 362789 , 15.19%
10.16.6.184:11411 : 568127 , 23.79%
10.16.69.135:11411 : 324662 , 13.60%
10.10.1.228:11411 : 410299 , 17.18%
10.10.1.208:11411 : 346616 , 14.52%
variance:0.22471542586997548
640：
CRC_HASH costs:1904ms, number:2387858 perdata:0.7973673476396ns.
10.10.1.118:11411 : 416794 , 17.45%
10.16.69.133:11411 : 400187 , 16.76%
10.16.6.184:11411 : 539187 , 22.58%
10.16.69.135:11411 : 365325 , 15.30%
10.10.1.228:11411 : 373834 , 15.66%
10.10.1.208:11411 : 292531 , 12.25%
variance:0.20776696947943804
1600：
CRC_HASH costs:1923ms, number:2387858 perdata:0.8053242697011297ns.
10.10.1.118:11411 : 281105 , 11.77%
10.16.69.133:11411 : 365290 , 15.30%
10.16.69.135:11411 : 441715 , 18.50%
10.16.6.184:11411 : 466691 , 19.54%
10.10.1.228:11411 : 456081 , 19.10%
10.10.1.208:11411 : 376976 , 15.79%
variance:0.18471055021331423
3200：
CRC_HASH costs:1904ms, number:2387858 perdata:0.7973673476396ns.
10.10.1.118:11411 : 282749 , 11.84%
10.16.69.133:11411 : 435415 , 18.23%
10.16.69.135:11411 : 450655 , 18.87%
10.16.6.184:11411 : 486627 , 20.38%
10.10.1.228:11411 : 372277 , 15.59%
10.10.1.208:11411 : 360135 , 15.08%
variance:0.19121762886993007
FNV1_64_HASH
160：
FNV1_64_HASH costs:969ms, number:2387858 perdata:0.4058030251380107ns.
10.10.1.118:11411 : 248007 , 10.39%
10.16.69.133:11411 : 324288 , 13.58%
10.16.6.184:11411 : 1051464 , 44.03%
10.16.69.135:11411 : 239652 , 10.04%
10.10.1.228:11411 : 126840 , 5.31%
10.10.1.208:11411 : 397607 , 16.65%
variance:1.7291444612562392
320：
FNV1_64_HASH costs:1028ms, number:2387858 perdata:0.4305113620659185ns.
10.10.1.118:11411 : 248327 , 10.40%
10.16.69.133:11411 : 323947 , 13.57%
10.16.6.184:11411 : 1051144 , 44.02%
10.16.69.135:11411 : 239652 , 10.04%
10.10.1.228:11411 : 126841 , 5.31%
10.10.1.208:11411 : 397947 , 16.67%
variance:1.7277872629051703
480：
FNV1_64_HASH costs:1055ms, number:2387858 perdata:0.44181856710072376ns.
10.10.1.118:11411 : 248327 , 10.40%
10.16.69.133:11411 : 324255 , 13.58%
10.16.6.184:11411 : 1051365 , 44.03%
10.16.69.135:11411 : 239652 , 10.04%
10.10.1.228:11411 : 126841 , 5.31%
10.10.1.208:11411 : 397418 , 16.64%
variance:1.7284991720338077
640：
FNV1_64_HASH costs:1028ms, number:2387858 perdata:0.4305113620659185ns.
10.10.1.118:11411 : 248327 , 10.40%
10.16.69.133:11411 : 324377 , 13.58%
10.16.6.184:11411 : 1051245 , 44.02%
10.16.69.135:11411 : 239652 , 10.04%
10.10.1.228:11411 : 126841 , 5.31%
10.10.1.208:11411 : 397416 , 16.64%
variance:1.7279883165546042
1600：
FNV1_64_HASH costs:1045ms, number:2387858 perdata:0.43763071338412923ns.
10.10.1.118:11411 : 308326 , 12.91%
10.16.69.133:11411 : 365291 , 15.30%
10.16.6.184:11411 : 263191 , 11.02%
10.16.69.135:11411 : 504782 , 21.14%
10.10.1.228:11411 : 206764 , 8.66%
10.10.1.208:11411 : 739504 , 30.97%
variance:0.6719899505883513
3200：
FNV1_64_HASH costs:1185ms, number:2387858 perdata:0.49626066541645275ns.
10.10.1.118:11411 : 132475 , 5.55%
10.16.69.133:11411 : 509299 , 21.33%
10.16.6.184:11411 : 131879 , 5.52%
10.16.69.135:11411 : 566719 , 23.73%
10.10.1.228:11411 : 202817 , 8.49%
10.10.1.208:11411 : 844669 , 35.37%
variance:1.338157043584133
FNV1A_32_HASH
160：
FNV1A_32_HASH costs:1507ms, number:2387858 perdata:0.6311095550907968ns.
10.10.1.118:11411 : 312106 , 13.07%
10.16.69.133:11411 : 253577 , 10.62%
10.16.6.184:11411 : 644748 , 27.00%
10.16.69.135:11411 : 421664 , 17.66%
10.10.1.228:11411 : 323920 , 13.57%
10.10.1.208:11411 : 431843 , 18.08%
variance:0.3926374779645682
320：
FNV1A_32_HASH costs:1761ms, number:2387858 perdata:0.7374810394922982ns.
10.10.1.118:11411 : 400635 , 16.78%
10.16.69.133:11411 : 368357 , 15.43%
10.16.6.184:11411 : 362826 , 15.19%
10.16.69.135:11411 : 287307 , 12.03%
10.10.1.228:11411 : 410149 , 17.18%
10.10.1.208:11411 : 558584 , 23.39%
variance:0.228939842705781
480：
FNV1A_32_HASH costs:1806ms, number:2387858 perdata:0.7563263812169736ns.
10.10.1.118:11411 : 397470 , 16.65%
10.16.69.133:11411 : 369449 , 15.47%
10.16.69.135:11411 : 337365 , 14.13%
10.16.6.184:11411 : 342005 , 14.32%
10.10.1.228:11411 : 391804 , 16.41%
10.10.1.208:11411 : 549765 , 23.02%
variance:0.20084339336306026
640：
FNV1A_32_HASH costs:1812ms, number:2387858 perdata:0.7588390934469303ns.
10.10.1.118:11411 : 332503 , 13.92%
10.16.69.133:11411 : 420161 , 17.60%
10.16.69.135:11411 : 354662 , 14.85%
10.16.6.184:11411 : 346627 , 14.52%
10.10.1.228:11411 : 462565 , 19.37%
10.10.1.208:11411 : 471340 , 19.74%
variance:0.16619754052235786
1600：
FNV1A_32_HASH costs:1994ms, number:2387858 perdata:0.8350580310889508ns.
10.10.1.118:11411 : 407301 , 17.06%
10.16.69.133:11411 : 381842 , 15.99%
10.16.69.135:11411 : 335819 , 14.06%
10.16.6.184:11411 : 458970 , 19.22%
10.10.1.228:11411 : 425412 , 17.82%
10.10.1.208:11411 : 378514 , 15.85%
variance:0.13760105340499912
3200：
FNV1A_32_HASH costs:2194ms, number:2387858 perdata:0.9188151054208415ns.
10.10.1.118:11411 : 399804 , 16.74%
10.16.69.133:11411 : 397910 , 16.66%
10.16.6.184:11411 : 373879 , 15.66%
10.16.69.135:11411 : 404753 , 16.95%
10.10.1.228:11411 : 392987 , 16.46%
10.10.1.208:11411 : 418525 , 17.53%
variance:0.1142594682506669
對比結論:
1、KETAMA_HASH算法在各種情況下都有很好的均勻分布，并且倍數越高越均勻；
2、NATIVE_HASH算法不受節點倍數影響；
3、FNV1_64_HASH算法不受節點倍數影響，但在超過某段範圍之後，分布均勻性會改變；
4、FNV1_32_HASH 和 FNV1A_32_HASH随着節點倍數增加，均勻性會變好；
5、FNV1A_64_HASH 和 CRC_HASH 随節點倍數增加波動性很大；
算法原理(160倍率、640适用)
NATIVE_HASH
1、hash是取字元串的hashcode,
2、這樣虛拟節點的最後hash落位基本都在一起，虛拟節點穿插分布的作用并沒有起到，相同節點的虛拟節點基本都分布在一起，相當于沒有用到虛拟節點，
3、最終伺服器區間的分布也不均勻。
CRC_HASH
1、取CRC32并右移16位；
2、會發生虛拟節點落位沖突的情況，後面的将前面的直接覆寫(CRC32本身就有碰撞機率)；
3、會散亂分布。
相關連結：
http://xdxd.love/2016/01/14/CRC32算法詳解和使用場景/
https://blog.csdn.net/yunhua_lee/article/details/42775039
http://preshing.com/20110504/hash-collision-probabilities/
http://www.backplane.com/matt/crc64.html
FNV HASH算法：
FNV1_64_HASH：虛拟節點集中分布，無沖突覆寫
FNV1A_64_HASH：虛拟節點略有分散但是還是聚集分布，無沖突覆寫
FNV1_32_HASH：虛拟節點集中分布，無沖突覆寫
FNV1A_32_HASH：虛拟節點略有打亂，無沖突覆寫
https://blog.csdn.net/fall221/article/details/8291381
KETAMA_HASH
1、根據key取MD5得到16位字元數組，
2、将16位字元數組相鄰4位倒序拼裝成hash,一次得到四個虛拟節點hash,
3、最終虛拟節點hash分布穿插錯落且分布區間比較均勻，無沖突覆寫。
問題與思考
原來的hash算法是将叢集中的ip對應上一個點，每個機器ip對應上hash結果的一個點(比如8台機器，進行模7運算，将0-7對應的hash結果分别配置設定給8台機器)，這樣其實可以減少節點(比如第七台機器下線了，配置設定的hash值為6，則可以讓第八台機器負擔流量，接收6，7的hash結果)，但是增加節點的話配置設定不夠了(比如增加了一台機器9,但是hash結果隻有八個，不能區分出流量分給他，則必須重新定義hash的模數)
一緻性hash是将hash結果集取得很大(0～2^32)，然後将機器ip也取模，最後落在結果集上，将結果集劃分成區間，按照區間配置設定給各個機器，這樣機器減少時還是一樣，隻是新負擔的機器接管了區間，而在增加的時候，因為是劃分了區間，是以可以對區間再進行劃分，從原區間中劃分出來一部分分給新機器就可以了(其實就是新機器算一次ip的hash,将上一個節點的ip hash結果到新節點的ip hash結果這段區間分給新機器)
用戶端沒有存儲key和host的map，而是存儲了伺服器虛拟節點的區間分布情況，存儲在ketamaNodeLocator類中的ketamaNodes中，這是一個TreeMap結構，每次存儲時，都根據要存儲的key計算hash，然後在ketamaNodes中找到對應應該存儲的節點。
![使用Windbg分析dump檔案[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)