一损谦、一致性Hash負(fù)載均衡原理

緩存服務(wù)器集群如下：

Cache集群.jpg

現(xiàn)需將對(duì)象Object存入到緩存服務(wù)器中，現(xiàn)在有4臺(tái)服務(wù)器岳颇，存入到哪臺(tái)呢照捡，也就是說需要定義一個(gè)規(guī)則來確定選取的服務(wù)器。

假設(shè)Object的數(shù)據(jù)結(jié)構(gòu)如下：

class Object {
    private String id;
    private String name;
    ......
}

普通Hash算法

緩存服務(wù)器集群為這樣的集合S = {A话侧，B栗精，C，D}瞻鹏，選擇服務(wù)器則也就是對(duì)這個(gè)集合進(jìn)行取樣悲立。

隨機(jī)取樣是一種方式，但是隨機(jī)取樣影響查找的性能新博。隨機(jī)獲取一臺(tái)服務(wù)器然后將Object存入薪夕，應(yīng)用程序中通過id從緩存服務(wù)器查找Object，這種方式是無法第一時(shí)間確定其所在的服務(wù)器的赫悄，需要遍歷集群中的所有服務(wù)器原献，然后比對(duì)查找出來的對(duì)象的id馏慨，才能獲得查找的Object。

數(shù)據(jù)結(jié)構(gòu)中的哈希表可以解決查找的問題姑隅。S集合使用線性列表方式存儲(chǔ)写隶，這樣每臺(tái)服務(wù)器相對(duì)應(yīng)的都有個(gè)編號(hào)，對(duì)于上面的4臺(tái)服務(wù)器來說讲仰，A的編號(hào)為0慕趴，其余的服務(wù)器編號(hào)依此類推。這樣的話確定了編號(hào)叮盘，就可以確定選擇的服務(wù)器秩贰。這個(gè)線性列表就是一張哈希表。通過下面的公式來確定對(duì)象Object存入到哪個(gè)編號(hào)的服務(wù)器中：

hash(id) % N 

N為集群中服務(wù)器的數(shù)量柔吼。

這樣通過id進(jìn)行查找的時(shí)候可以非扯痉眩快的確定Object所在的服務(wù)器。進(jìn)而從這臺(tái)服務(wù)器中獲取Object愈魏。

不過這樣做存在一個(gè)問題觅玻，從上面的公式中可以看到，服務(wù)器編號(hào)的確定跟集群中服務(wù)器的數(shù)量是有關(guān)系的培漏，如果N變化了溪厘，那么計(jì)算出來的編號(hào)就會(huì)發(fā)生變化。

增加了一臺(tái)服務(wù)器編號(hào)計(jì)算變?yōu)椋?/p>

hash(id) %（N + 1）

減少了一臺(tái)服務(wù)器編號(hào)計(jì)算變?yōu)椋?/p>

hash(id) %（N - 1）

N的變化會(huì)導(dǎo)致相同的id前后計(jì)算出來的編號(hào)不一樣牌柄，這樣會(huì)帶來什么問題呢畸悬？

問題就是：當(dāng)前集群中服務(wù)器數(shù)量為N，存入Object對(duì)象珊佣，確定編號(hào)為0蹋宦，也就是編號(hào)為0的服務(wù)器存放著Object對(duì)象，現(xiàn)在增加了一臺(tái)服務(wù)器咒锻，也就是當(dāng)前集群中服務(wù)器的數(shù)量為N+1冷冗，這時(shí)候通過id進(jìn)行查找，重新計(jì)算編號(hào)后得到的編號(hào)為1惑艇，編號(hào)為1的這臺(tái)服務(wù)器是沒有Object對(duì)象數(shù)據(jù)的蒿辙，然后查找結(jié)果報(bào)告的是無數(shù)據(jù)，也就是所謂的緩存失效滨巴。我們知道緩存的引入減少對(duì)數(shù)據(jù)庫(kù)的請(qǐng)求思灌，提升應(yīng)用的性能，現(xiàn)在因?yàn)榫彺娣?wù)器的增加恭取，大量根據(jù)id進(jìn)行查找的請(qǐng)求出現(xiàn)緩存失效的表現(xiàn)泰偿，勢(shì)必會(huì)直接去請(qǐng)求數(shù)據(jù)庫(kù)，導(dǎo)致數(shù)據(jù)庫(kù)訪問壓力增大秽荤，這就是緩存雪崩現(xiàn)象甜奄。

一致性Hash算法的引入就是為了解決這種普通Hash算法存在的問題。

一致性Hash算法

在上面通過哈希函數(shù)對(duì)id進(jìn)行哈希窃款，然后對(duì)服務(wù)器數(shù)量進(jìn)行求余會(huì)受到服務(wù)器數(shù)量的影響课兄，需要尋求另外一種解決方式。

先來看看對(duì)id的哈希：

hash(id)

通過這個(gè)哈希函數(shù)計(jì)算出來的哈希碼通常都是一個(gè)整型數(shù)值晨继，一般是4個(gè)字節(jié)烟阐，也就是32位。取無符號(hào)表示紊扬，4個(gè)字節(jié)的整型的取值范圍為0~2^32-1蜒茄。也就是說任何的對(duì)象通過哈希函數(shù)計(jì)算后得到的哈希碼的數(shù)值都會(huì)在這個(gè)區(qū)間中。

將這個(gè)區(qū)間內(nèi)的點(diǎn)組成連接成環(huán)餐屎，如下所示：

環(huán)-1.jpg

現(xiàn)在有4個(gè)對(duì)象Object1~Object4, 對(duì)應(yīng)的id為id1~id4檀葛，將id1 ~ id4這4個(gè)id映射到環(huán)中，先進(jìn)行哈希計(jì)算：

h1 = hash(id1);
h2 = hash(id2);
h3 = hash(id3);
h4 = hash(id4);

映射后如下圖所示：

環(huán)-2.jpg

接下來取服務(wù)器的某種標(biāo)識(shí)腹缩，然后將3臺(tái)緩存服務(wù)器也映射到這個(gè)環(huán)中屿聋，先進(jìn)行哈希計(jì)算：

c1 = hash(cache1);
c2 = hash(cache2);
c3 = hash(cache3);

映射后的環(huán)如下所示：

環(huán)-3.jpg

現(xiàn)在id1~id4和Cache1,Cache2,Cache3都被映射到了環(huán)中党晋±樱回過頭來看一下我們到底要做什么腺办，我們要做的是確定id1 ~ id4分別被分配到Cache1~Cache3的哪個(gè)中谭贪，也就是確定id和Cache的分配關(guān)系锡搜。而在環(huán)中h節(jié)點(diǎn)可以代表id磕诊，c節(jié)點(diǎn)可以代表Cache哮兰，那么確定了h和c的對(duì)應(yīng)關(guān)系结缚，那么就間接地確定了id和Cache的關(guān)系竿痰。

如何確定h和c的對(duì)應(yīng)關(guān)系呢脆粥？可以這樣理解，把h當(dāng)做一個(gè)人菇曲，環(huán)為它查找路線冠绢，它沿著環(huán)開始走，尋找c節(jié)點(diǎn)常潮，找到的c節(jié)點(diǎn)收入囊中弟胀，即完成了h和c的對(duì)應(yīng)。如果找到的c節(jié)點(diǎn)代表的Cache服務(wù)器下線喊式，那么繼續(xù)從這個(gè)節(jié)點(diǎn)出發(fā)繼續(xù)尋找下一個(gè)要對(duì)應(yīng)的c節(jié)點(diǎn)孵户。

在上圖中h的查找我們采用逆時(shí)針行走方式，最終的對(duì)應(yīng)關(guān)系如下所示：

環(huán)-4.jpg

通過上面的操作則有：

• Object1被存入Cache1
• Object2被存入如Cache3
• Object3被存入Cache3
• Object4被存入Cache2

緩存服務(wù)器下線

現(xiàn)在Cache2服務(wù)器下線了岔留，根據(jù)上面的描述夏哭，最終的查找效果如下所示：

環(huán)-5.jpg

Cache2下線，那么Cache2中的數(shù)據(jù)就失效了献联，通過id4查找會(huì)出現(xiàn)緩存失效竖配，應(yīng)用程序此時(shí)會(huì)對(duì)緩存失效進(jìn)行處理何址，重新從數(shù)據(jù)庫(kù)或者其他地方獲取Object4對(duì)象，然后試圖重新將Object4放入到緩存服務(wù)器中进胯，放入到哪臺(tái)呢用爪？還是根據(jù)上面描述的原理，從h4節(jié)點(diǎn)出發(fā)胁镐，查找c節(jié)點(diǎn)偎血，找到的是c3節(jié)點(diǎn)，則將Object4重新放入到Cache3這臺(tái)服務(wù)器中盯漂。從這里可以看到颇玷，Cache2服務(wù)器的下線，只會(huì)影響到這臺(tái)服務(wù)器上的緩存數(shù)據(jù)就缆，并不會(huì)對(duì)其他緩存服務(wù)器上的數(shù)據(jù)造成影響帖渠。這和普通Hash算法的表現(xiàn)是不同的，普通Hash算法會(huì)影響其他緩存服務(wù)器上的數(shù)據(jù)竭宰。

增加緩存服務(wù)器

增加Cache4阿弃，c4節(jié)點(diǎn)落在h2和h3之間，此時(shí)根據(jù)id2進(jìn)行查找羞延，定位到h2節(jié)點(diǎn)渣淳，從h2出發(fā)尋找對(duì)應(yīng)的c節(jié)點(diǎn)，未增加之前找到的是c3節(jié)點(diǎn)伴箩，增加之后找到的是c4節(jié)點(diǎn)入愧，c4節(jié)點(diǎn)代表的緩存服務(wù)器Cache4并沒有Object2數(shù)據(jù)，那么應(yīng)用程序從數(shù)據(jù)庫(kù)或其他地方獲取Object2數(shù)據(jù)然后重新放入到Cache2中嗤谚，Cache3中的Object2此時(shí)就是無效的棺蛛。可以看出增加Cache4服務(wù)器巩步，只會(huì)影響到Cache2和Cache4之間的h節(jié)點(diǎn)代表的數(shù)據(jù)旁赊。

增加Cache4服務(wù)器后，最終的查找效果如下：

環(huán)-6.jpg

虛擬節(jié)點(diǎn)

先看一下下面的環(huán)：

環(huán)-7.jpg

現(xiàn)在只有兩臺(tái)緩存服務(wù)器Cache1和Cache2椅野，根據(jù)上面描述终畅，h和c的對(duì)應(yīng)關(guān)系如下：

環(huán)-8.jpg

從圖可以看到，數(shù)據(jù)大部分都被放入到了Cache2這臺(tái)緩存服務(wù)器竟闪。也就是說當(dāng)緩存服務(wù)器比較少的情況下离福，會(huì)出現(xiàn)某一臺(tái)緩存服務(wù)器大量緩存數(shù)據(jù)的情況，也就是說緩存分配不均勻炼蛤。

如何解決這種情況呢妖爷？一致性Hash算法引入了"虛擬節(jié)點(diǎn)"這種解決方案。

虛擬節(jié)點(diǎn)就是緩存服務(wù)器的副本理朋，每一個(gè)緩存服務(wù)器都會(huì)在環(huán)中有數(shù)個(gè)相對(duì)應(yīng)的虛擬節(jié)點(diǎn)絮识。當(dāng)增加緩存服務(wù)器的時(shí)候绿聘，相應(yīng)地就會(huì)在緩存創(chuàng)建數(shù)個(gè)相對(duì)應(yīng)的虛擬機(jī)節(jié)點(diǎn)；當(dāng)刪除緩存服務(wù)器的時(shí)候就會(huì)同時(shí)從環(huán)中移除相對(duì)應(yīng)的虛擬節(jié)點(diǎn)次舌。

如下圖所示斜友，現(xiàn)在有兩臺(tái)緩存服務(wù)器Cache1和Cache2，引入虛擬節(jié)點(diǎn)垃它，每臺(tái)緩存服務(wù)器對(duì)應(yīng)有兩個(gè)虛擬節(jié)點(diǎn)，那么環(huán)中就會(huì)有4個(gè)虛擬節(jié)點(diǎn)烹看。c1.1和c1.2代表的是Cache1国拇，c2.1和c2.2代表的就是Cache2。

環(huán)-9.jpg

引入虛擬節(jié)點(diǎn)后惯殊，h和c的對(duì)應(yīng)關(guān)系如下所示：

環(huán)-10.jpg

從上圖可以看到酱吝，此時(shí)緩存的數(shù)據(jù)是均勻分配的。

虛擬節(jié)點(diǎn)的引入會(huì)要求虛擬節(jié)點(diǎn)和緩存服務(wù)器有映射關(guān)系土思，找到虛擬節(jié)點(diǎn)后务热，通過映射關(guān)系就可以確定緩存服務(wù)器。

虛擬節(jié)點(diǎn)和緩存服務(wù)器的映射.jpg

參考文章：https://www.codeproject.com/Articles/56138/Consistent-hashing

二己儒、一致性Hash負(fù)載均衡算法實(shí)現(xiàn)

1. Hash函數(shù)

要將對(duì)象和服務(wù)器映射到Hash環(huán)中崎岂，需要計(jì)算出來哈希碼，這就需要有Hash函數(shù)來完成闪湾，也就是關(guān)系到使用的哈希算法冲甘。使用一個(gè)好的哈希算法是很重要的，為什么這么說呢途样，拿我們上面提到的緩存服務(wù)來說江醇，一個(gè)完美的解決方案是需要數(shù)據(jù)分配的平衡，假如Hash環(huán)的映射是這樣的：

哈希碼聚集.jpg

Hash碼數(shù)值落在一個(gè)小區(qū)間內(nèi)何暇，出現(xiàn)Hash碼聚集情況陶夜，那么從上圖可以看到緩存數(shù)據(jù)全部由c3節(jié)點(diǎn)的服務(wù)器存儲(chǔ)，出現(xiàn)數(shù)據(jù)分配不平衡裆站。那么就需要一個(gè)好的哈希處理使得哈希碼在環(huán)中的分配盡可能得分散条辟，類似這樣：

哈希碼分散.jpg

上面說到過，環(huán)中數(shù)值點(diǎn)的取值范圍為[0,2^32-1]宏胯，也就是說我們通過Hash函數(shù)計(jì)算出來的這些哈希碼數(shù)值應(yīng)該避免集中在某一小區(qū)間范圍內(nèi)捂贿。

Hash算法對(duì)于一致性Hash負(fù)載均衡的作用可見一斑，而寫出好的適用于一致性Hash負(fù)載均衡的Hash算法是需要些技術(shù)能力的胳嘲，這里不研究如何寫厂僧，而是查閱已有的實(shí)現(xiàn)方式。

xmemcached：哈希函數(shù)

xmemcached是memcached的java版本的客戶端了牛。它其中包含了一致性Hash算法的實(shí)現(xiàn)颜屠。

網(wǎng)上內(nèi)容摘抄：Memcached在實(shí)現(xiàn)分布集群部署時(shí)辰妙，Memcached服務(wù)端的之間是沒有通訊的，服務(wù)端是偽分布式甫窟，實(shí)現(xiàn)分布式是由客戶端實(shí)現(xiàn)的密浑，客戶端實(shí)現(xiàn)了分布式算法把數(shù)據(jù)保存到不同的Memcached服務(wù)端。

HashAlgorithm.java

package net.rubyeye.xmemcached;

import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.zip.CRC32;
import net.rubyeye.xmemcached.exception.MemcachedClientException;
import net.rubyeye.xmemcached.utils.ByteUtils;

/**
 * Known hashing algorithms for locating a server for a key. Note that all hash algorithms return
 * 64-bits of hash, but only the lower 32-bits are significant. This allows a positive 32-bit number
 * to be returned for all cases.
 */
public enum HashAlgorithm {

  /**
   * Native hash (String.hashCode()).
   */
  NATIVE_HASH,
  /**
   * CRC32_HASH as used by the perl API. This will be more consistent both across multiple API users
   * as well as java versions, but is mostly likely significantly slower.
   */
  CRC32_HASH,
  /**
   * FNV hashes are designed to be fast while maintaining a low collision rate. The FNV speed allows
   * one to quickly hash lots of data while maintaining a reasonable collision rate.
   * 
   * @see http://www.isthe.com/chongo/tech/comp/fnv/
   * @see http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash
   */
  FNV1_64_HASH,
  /**
   * Variation of FNV.
   */
  FNV1A_64_HASH,
  /**
   * 32-bit FNV1.
   */
  FNV1_32_HASH,
  /**
   * 32-bit FNV1a.
   */
  FNV1A_32_HASH,
  /**
   * MD5-based hash algorithm used by ketama.
   */
  KETAMA_HASH,

  /**
   * From mysql source
   */
  MYSQL_HASH,

  ELF_HASH,

  RS_HASH,

  /**
   * From lua source,it is used for long key
   */
  LUA_HASH,

  ELECTION_HASH,
  /**
   * The Jenkins One-at-a-time hash ,please see http://www.burtleburtle.net/bob/hash/doobs.html
   */
  ONE_AT_A_TIME;

  private static final long FNV_64_INIT = 0xcbf29ce484222325L;
  private static final long FNV_64_PRIME = 0x100000001b3L;

  private static final long FNV_32_INIT = 2166136261L;
  private static final long FNV_32_PRIME = 16777619;

  /**
   * Compute the hash for the given key.
   * 
   * @return a positive integer hash
   */
  public long hash(final String k) {
    long rv = 0;
    switch (this) {
      case NATIVE_HASH:
        rv = k.hashCode();
        break;
      case CRC32_HASH:
        // return (crc32(shift) >> 16) & 0x7fff;
        CRC32 crc32 = new CRC32();
        crc32.update(ByteUtils.getBytes(k));
        rv = crc32.getValue() >> 16 & 0x7fff;
        break;
      case FNV1_64_HASH: {
        // Thanks to pierre@demartines.com for the pointer
        rv = FNV_64_INIT;
        int len = k.length();
        for (int i = 0; i < len; i++) {
          rv *= FNV_64_PRIME;
          rv ^= k.charAt(i);
        }
      }
        break;
      case FNV1A_64_HASH: {
        rv = FNV_64_INIT;
        int len = k.length();
        for (int i = 0; i < len; i++) {
          rv ^= k.charAt(i);
          rv *= FNV_64_PRIME;
        }
      }
        break;
      case FNV1_32_HASH: {
        rv = FNV_32_INIT;
        int len = k.length();
        for (int i = 0; i < len; i++) {
          rv *= FNV_32_PRIME;
          rv ^= k.charAt(i);
        }
      }
        break;
      case FNV1A_32_HASH: {
        rv = FNV_32_INIT;
        int len = k.length();
        for (int i = 0; i < len; i++) {
          rv ^= k.charAt(i);
          rv *= FNV_32_PRIME;
        }
      }
        break;
      case ELECTION_HASH:
      case KETAMA_HASH:
        byte[] bKey = computeMd5(k);
        rv = (long) (bKey[3] & 0xFF) << 24 | (long) (bKey[2] & 0xFF) << 16
            | (long) (bKey[1] & 0xFF) << 8 | bKey[0] & 0xFF;
        break;

      case MYSQL_HASH:
        int nr2 = 4;
        for (int i = 0; i < k.length(); i++) {
          rv ^= ((rv & 63) + nr2) * k.charAt(i) + (rv << 8);
          nr2 += 3;
        }
        break;
      case ELF_HASH:
        long x = 0;
        for (int i = 0; i < k.length(); i++) {
          rv = (rv << 4) + k.charAt(i);
          if ((x = rv & 0xF0000000L) != 0) {
            rv ^= x >> 24;
            rv &= ~x;
          }
        }
        rv = rv & 0x7FFFFFFF;
        break;
      case RS_HASH:
        long b = 378551;
        long a = 63689;
        for (int i = 0; i < k.length(); i++) {
          rv = rv * a + k.charAt(i);
          a *= b;
        }
        rv = rv & 0x7FFFFFFF;
        break;
      case LUA_HASH:
        int step = (k.length() >> 5) + 1;
        rv = k.length();
        for (int len = k.length(); len >= step; len -= step) {
          rv = rv ^ (rv << 5) + (rv >> 2) + k.charAt(len - 1);
        }
        break;
      case ONE_AT_A_TIME:
        try {
          int hash = 0;
          for (byte bt : k.getBytes("utf-8")) {
            hash += (bt & 0xFF);
            hash += (hash << 10);
            hash ^= (hash >>> 6);
          }
          hash += (hash << 3);
          hash ^= (hash >>> 11);
          hash += (hash << 15);
          rv = hash;
        } catch (UnsupportedEncodingException e) {
          throw new IllegalStateException("Hash function error", e);
        }
        break;
      default:
        assert false;
    }

    return rv & 0xffffffffL; /* Convert to unsigned 32-bits */
  }

  private static ThreadLocal<MessageDigest> md5Local = new ThreadLocal<MessageDigest>();

  /**
   * Get the md5 of the given key.
   */
  public static byte[] computeMd5(String k) {
    MessageDigest md5 = md5Local.get();
    if (md5 == null) {
      try {
        md5 = MessageDigest.getInstance("MD5");
        md5Local.set(md5);
      } catch (NoSuchAlgorithmException e) {
        throw new RuntimeException("MD5 not supported", e);
      }
    }
    md5.reset();
    md5.update(ByteUtils.getBytes(k));
    return md5.digest();
  }

  // public static void main(String[] args) {
  // HashAlgorithm alg=HashAlgorithm.CRC32_HASH;
  // long h=0;
  // long start=System.currentTimeMillis();
  // for(int i=0;i<100000;i++)
  // h=alg.hash("MYSQL_HASH");
  // System.out.println(System.currentTimeMillis()-start);
  // }
}

Dubbo：哈希函數(shù)

/**
 * ConsistentHashLoadBalance
 */
public class ConsistentHashLoadBalance extends AbstractLoadBalance {
   
    // 代碼省略
    ......

    private static final class ConsistentHashSelector<T> {

        // 代碼省略
        ......

        private long hash(byte[] digest, int number) {
            return (((long) (digest[3 + number * 4] & 0xFF) << 24)
                    | ((long) (digest[2 + number * 4] & 0xFF) << 16)
                    | ((long) (digest[1 + number * 4] & 0xFF) << 8)
                    | (digest[number * 4] & 0xFF))
                    & 0xFFFFFFFFL;
        }

        private byte[] md5(String value) {
            MessageDigest md5;
            try {
                md5 = MessageDigest.getInstance("MD5");
            } catch (NoSuchAlgorithmException e) {
                throw new IllegalStateException(e.getMessage(), e);
            }
            md5.reset();
            byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
            md5.update(bytes);
            return md5.digest();
        }

    }

}

2. 環(huán)存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)

環(huán)由[0, 2^32-1]這個(gè)區(qū)間內(nèi)的整數(shù)值組成粗井。體現(xiàn)在程序中就是用一種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)這些值尔破。

比如說用列表來存儲(chǔ)，將服務(wù)器標(biāo)識(shí)通過Hash函數(shù)計(jì)算后得到的哈希碼存入到列表中浇衬，類似這樣：

列表表示環(huán).jpg

現(xiàn)在這個(gè)列表就表示了哈希碼環(huán)±凉梗現(xiàn)在假設(shè)對(duì)象標(biāo)識(shí)經(jīng)過Hash函數(shù)計(jì)算后得到的哈希碼值87。那么現(xiàn)在h=87耘擂，從環(huán)中找c點(diǎn)胆剧。如何確定c點(diǎn)呢？觀察一下哈希碼環(huán)醉冤，我們可以發(fā)現(xiàn)順時(shí)針行走秩霍，哈希碼值越來越小蚁阳；逆時(shí)針行走哈希碼值越來越大铃绒，而上面我們說到確定了h點(diǎn)后，逆時(shí)針行走查找c點(diǎn)螺捐，既然是逆時(shí)針行走那么就是找第一個(gè)大于h點(diǎn)的c匿垄，也就是說從列表中查找第一個(gè)大于h的元素。

滿足這個(gè)需求的實(shí)現(xiàn)方法當(dāng)然有很多了归粉，這里有一種方式椿疗，就是先對(duì)列表進(jìn)行從小到大排序，排序后列表結(jié)構(gòu)如下：

排序后的列表.jpg

循環(huán)列表進(jìn)行查找糠悼，第一個(gè)大于h的點(diǎn)就是88届榄。查找涉及到時(shí)間復(fù)雜度，這種方式需要遍歷列表倔喂，在查找性能上并不是最好的铝条。

數(shù)據(jù)有序并且查找的時(shí)間復(fù)雜度小。使用Java容器類中的TreeMap比較合適席噩。

更詳細(xì)說明參考：https://www.cnblogs.com/xrq730/p/5186728.html

3. 代碼實(shí)現(xiàn)

參考Dubbo的ConsistentHashLoadBalance類

ConsistentHashLoadBalancer.java

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * @Author rocky.hu
 * @Date 2019-04-20 20:34
 */
public class ConsistentHashLoadBalancer implements LoadBalancerStrategy<Server> {

    private CandidateSelector<Server> candidateSelector;

    @Override
    public Server choose(List<Server> candidates) {
        return null;
    }

    public Server choose(List<Server> candidates, String key) {
        int identityHashCode = System.identityHashCode(candidates);
        if (candidateSelector == null || candidateSelector.identityHashCode != identityHashCode) {
            candidateSelector = new CandidateSelector<Server>(candidates, identityHashCode);
        }

        return candidateSelector.select(key);
    }

    private static final class CandidateSelector<T> {

        // 引入虛擬節(jié)點(diǎn)概念班缰，此屬性表示Hash環(huán)中總的虛擬節(jié)點(diǎn)數(shù)
        private final TreeMap<Long, Server> virtualCandidates;
        // 每臺(tái)真實(shí)服務(wù)器節(jié)點(diǎn)的虛擬節(jié)點(diǎn)數(shù)，這個(gè)值可做成可配置化的
        private final int replicaNumber = 160;
        // 服務(wù)器列表的Hash碼悼枢，做緩存作用埠忘，用來判斷服務(wù)器列表長(zhǎng)度的變化
        private final int identityHashCode;

        CandidateSelector(List<Server> candidates, int identityHashCode) {
            this.virtualCandidates = new TreeMap<Long, Server>();
            this.identityHashCode = identityHashCode;

            // 將服務(wù)器節(jié)點(diǎn)映射到Hash環(huán)中
            for (Server server : candidates) {
                String address = server.getAddress();
                for (int i = 0; i < replicaNumber / 4; i++) {
                    byte[] digest = md5(address + i);
                    for (int h = 0; h < 4; h++) {
                        long m = hash(digest, h);
                        virtualCandidates.put(m, server);
                    }
                }
            }

        }

        public Server select(String key) {
            byte[] digest = md5(key);
            return selectForKey(hash(digest, 0));
        }

        private Server selectForKey(long hash) {
            // 使用TreeMap的ceilingEntry方法返回鍵值大于或等于的指定鍵的Entry（相當(dāng)于Hash環(huán)逆時(shí)針行走查找服務(wù)器節(jié)點(diǎn)）
            Map.Entry<Long, Server> entry = virtualCandidates.ceilingEntry(hash);
            if (entry == null) {
                entry = virtualCandidates.firstEntry();
            }
            return entry.getValue();
        }

        private long hash(byte[] digest, int number) {
            return (((long) (digest[3 + number * 4] & 0xFF) << 24)
                    | ((long) (digest[2 + number * 4] & 0xFF) << 16)
                    | ((long) (digest[1 + number * 4] & 0xFF) << 8)
                    | (digest[number * 4] & 0xFF))
                    & 0xFFFFFFFFL;
        }

        private byte[] md5(String value) {
            MessageDigest md5;
            try {
                md5 = MessageDigest.getInstance("MD5");
            } catch (NoSuchAlgorithmException e) {
                throw new IllegalStateException(e.getMessage(), e);
            }
            md5.reset();
            byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
            md5.update(bytes);
            return md5.digest();
        }
    }

}

Server.java

/**
 * @Author rocky.hu
 * @Date 2019-04-21 00:47
 */
public class Server {

    private String address;


    public String getAddress() {
        return address;
    }

    public void setAddress(String address) {
        this.address = address;
    }
}