哪種一緻性雜湊演算法才是解決分布式緩存問題的王者？

一緻性哈希是由Karger等人于1997年提出的一種特殊的雜湊演算法，目的是解決分布式緩存的問題，現在在分布式系統中有着廣泛的應用。本文将對ketama、jump consistent hash、rendezvous hash和maglev hash四種算法進行對比分析。

一、一緻性哈希的特性

• 平衡性

不同key通過算法映射後，可以比較均衡地分布到所有的後端節點上。

• 單調性

當有新的節點上線後，系統中原有的key要麼還是映射到原來的節點上，要麼映射到新加入的節點上，不會出現從一個老節點重新映射到另一個老節點。

• 穩定性

當服務發生擴縮容的時候，發生遷移的資料量盡可能少。

二、問題背景

假設我們有N個cache伺服器節點，那如何将資料映射到這N個節點上呢，最簡單的方法就是用資料計算出一個hash值，然後用hash值對N取模，如：hash(data) % N，這樣隻要計算出來的hash值比較均勻，那資料也就能比較均勻地映射到N個節點上了。但這帶來的問題就是，如果發生擴縮容，節點的數量發生了變化，那很多資料的映射關系都會發生變化。顯然這種方法雖然簡單，但并不太能解決我們的需求。

三、四種常見一緻性雜湊演算法

下面分别介紹對比四種比較常見的一緻性雜湊演算法，看看一緻性雜湊演算法是怎麼解決這問題的。

1、經典一緻性哈希

經典的一緻性雜湊演算法也就是我們常說的割環法 ，大家應該都比較熟悉。簡單來說就是，我們把節點通過hash的方式，映射到一個範圍是[0，2^32]的環上，同理，把資料也通過hash的方式映射到環上，然後按順時針方向查找第一個hash值大于等于資料的hash值的節點，該節點即為資料所配置設定到的節點。而更好點的做法是帶虛拟節點的方法，我們可以為每個實體節點配置設定若幹個虛拟節點，然後把虛拟節點映射到hash環，配置設定給每個實體節點虛拟節點數量對應每個實體節點的權重，如下圖1所示。這樣還是按順時針的方法查找資料所落到的虛拟節點，再看該虛拟節點是屬于哪個實體節點就可以知道資料是配置設定給哪個實體節點了。

這種割環法的實作多種，下面以比較有名的Ketama Hash實作為例進行對比分析。Ketama Hash的關鍵源碼如下：

#伺服器節點例子，第一列為位址，第二列為記憶體
#------ Server --------Mem-#
#255.255.255.255:6553566666#
10.0.1.1:11211600
10.0.1.2:11211300
10.0.1.3:11211200
10.0.1.4:11211350
10.0.1.5:112111000
10.0.1.6:11211800
10.0.1.7:11211950
10.0.1.8:11211100

typedef struct
{
    unsigned int point;  // point on circle
    char ip[22];
} mcs;

typedef struct
{
    char addr[22];
    unsigned long memory;
} serverinfo;

typedef struct
{
    int numpoints;
    void* modtime;
    void* array; //array of mcs structs
} continuum;

typedef continuum* ketama_continuum;

/** \brief Generates the continuum of servers (each server as many points on a circle).
  * \param key Shared memory key for storing the newly created continuum.
  * \param filename Server definition file, which will be parsed to create this continuum.
  * \return 0 on failure, 1 on success. */
static int
ketama_create_continuum( key_t key, char* filename )
{
    if (shm_ids == NULL) {
        init_shm_id_tracker();
    }

    if (shm_data == NULL) {
        init_shm_data_tracker();
    }

    int shmid;
    int* data;  /* Pointer to shmem location */
    unsigned int numservers = 0;
    unsigned long memory;
    serverinfo* slist;

    slist = read_server_definitions( filename, &numservers, &memory );
    /* Check numservers first; if it is zero then there is no error message
     * and we need to set one. */
    if ( numservers < 1 )
    {
        set_error( "No valid server definitions in file %s", filename );
        return 0;
    }
    else if ( slist == 0 )
    {
        /* read_server_definitions must've set error message. */
        return 0;
    }
#ifdef DEBUG
     syslog( LOG_INFO, "Server definitions read: %u servers, total memory: %lu.\n",
        numservers, memory );
#endif




    /* Continuum will hold one mcs for each point on the circle: */
    mcs continuum[ numservers * 160 ];
    unsigned int i, k, cont = 0;

    for( i = 0; i < numservers; i++ )
    {
        float pct = (float)slist[i].memory / (float)memory;
        // 按記憶體權重計算每個實體節點需要配置設定多少個虛拟節點，正常是160個
        unsigned int ks = floorf( pct * 40.0 * (float)numservers );
#ifdef DEBUG
        int hpct = floorf( pct * 100.0 );

        syslog( LOG_INFO, "Server no. %d: %s (mem: %lu = %u%% or %d of %d)\n",
            i, slist[i].addr, slist[i].memory, hpct, ks, numservers * 40 );
#endif

        for( k = 0; k < ks; k++ )
        {
            /* 40 hashes, 4 numbers per hash = 160 points per server */
            char ss[30];
            unsigned char digest[16];

            // 在節點的addr後面拼上個序号，然後以該字元串去計算hash值
            sprintf( ss, "%s-%d", slist[i].addr, k );
            ketama_md5_digest( ss, digest );

            /* Use successive 4-bytes from hash as numbers
             * for the points on the circle: */
            int h;
            // 16位元組，每四個位元組作為一個虛拟節點的hash值
            for( h = 0; h < 4; h++ )
            {
                continuum[cont].point = ( digest[3+h*4] << 24 )
                                      | ( digest[2+h*4] << 16 )
                                      | ( digest[1+h*4] <<  8 )
                                      |   digest[h*4];


                memcpy( continuum[cont].ip, slist[i].addr, 22 );
                cont++;
            }
        }
    }
    free( slist );

    // 排序，友善二分查找
    /* Sorts in ascending order of "point" */
    qsort( (void*) &continuum, cont, sizeof( mcs ), (compfn)ketama_compare );
    
    . . .

    return 1;
}
           

Ketama Hash的實作簡單來說可以分成以下幾步：

1）從配置檔案中讀取伺服器節點清單，包括節點的位址及記憶體，其中記憶體參數用來衡量一個節點的權重；

2）對每個節點按權重計算需要生成幾個虛拟節點，基準是每個節點160個虛拟節點，每個節點會生成10.0.1.1:11211-1、10.0.1.1:11211-2到10.0.1.1:11211-40共40個字元串，并以此算出40個16位元組的hash值(其中hash算法采用的md5)，每個hash值生成4個4位元組的hash值，總共40*4=160個hash值，對應160個虛拟節點；

3）把所有的hash值及對應的節點位址存到一個continuum存組中，并按hash值排序友善後續二分查找計算資料所屬節點。

這種割環法的平衡性在虛拟節點數較多且搭配較好的hash函數的情況下，可以具備較好的平衡性和穩定性 ，實際應用中可以采用比Ketama算法預設160更多的虛拟節點數，hash算法也可以采用其他的算法。在算法的複雜度方面，Ketama算法的複雜度是O(log(vn))，其中n是節點數，v是節點的虛拟節點數。Ketama算法也能很好地滿足單調性，當發生節點數量發生伸縮的時候，相當于隻是在環上增加或者去掉相應的虛拟節點，也就隻會導緻變化的節點上的資料發生重新映射，因些能很好滿足單調性。

2、Rendezvous hash

這個算法比較簡單粗暴，沒有什麼構造環或者複雜的計算過程，它對于一個給定的Key，對每個節點都通過哈希函數h()計算一個權重值wi,j = h(Keyi, Nodej)，然後在所有的權重值中選擇最大一個Max{wi,j}。顯而易見，算法挺簡單，所需存儲空間也很小，但算法的複雜度是O(n)。從wiki上摘抄的python實作的核心代碼如下：

def determine_responsible_node(nodes, key):
    """Determines which node, of a set of nodes of various weights, is responsible for the provided key."""
    highest_score, champion = -1, None
    for node in nodes:
        score = node.compute_weighted_score(key)
        if score > highest_score:
            champion, highest_score = node, score
    return champion
           

當發生擴縮的時候，相當于增加了一次計算hash的機會，如果計算出來的hash值超過原來的最大值，則該部分key配置設定到新的節點，縮容的時候則相當于把該節點上的key遷移到該key原本計算出來的hash值次高的節點上。可見，當節點變化的時候，rendezvous hash隻會影響到最大權重值落到變化的節點的key，也就是說隻有變化的節點上的資料需要重新映射，因些也很符合單調性的要求。 而Rendezvous hash算法的平衡性和穩定性則取決于哈希函數的随機特性 。

在wiki上還提供了優化方法（Skeleton-based variant）來降低算法的複雜度，如下圖2所示，把原始節點分成若幹個虛拟組，虛拟組一層一層組成一個“骨架”，然後在虛拟組中按照Rendezvous hash一樣的方法計算出最大的節點，進而得到下一層的虛拟組，再在下一層的虛拟組中按同樣的方法計算，直到找到最下方的真實節點，最終可以把算法複雜度降低到O(log n)。

3.Jump consistent hash

Jump consistent hash是Google于2014年發表的論文中提出的一種一緻性雜湊演算法， 它占用記憶體小且速度很快，并且隻有大概5行代碼，比較适合用在分shard的分布式存儲系統中 。其完整的代碼如下，其輸入是一個64位的key及桶的數量，輸出是傳回這個key被配置設定到的桶的編号。

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
    int64_t b = ­-1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
    }
    return b;
}
           

下面根據論文内容簡單介紹下其原理：

• 記ch(key, num_buckets)為桶數量為num_buckets時的hash函數
• 當num_buckets = 1時，顯而易見，所有key都會配置設定給僅有的一個桶，即ch(key, 1) == 0
• 當num_buckets = 2時，為了使用key分布均勻，應該有1/2的key保留在0号桶中，而有1/2的key應該遷移到1号桶中
• 由此可以發現，當num_buckets由n變為n+1時，ch(key, n+1)的結果中應該有n/n+1結果保持不變，而有1/n+1的結果發生怕了跳變，變成了n

Jump consistent hash的這種思路看上去其實挺簡單，就是num_buckets變化的時候，有些key的計算結果會發生變化。假如這裡我們取一個随機數來決定每次要不要跳變，并且這個随機數隻跟key有關，那麼我們得到的初步算法如下：

int ch(int key, int num_buckets) {
    random.seed(key) ;
    int b = 0; // This will track ch(key, j +1) .
    for (int j = 1; j < num_buckets; j ++) {
        if (random.next() < 1.0/(j+1) ) b = j ; //這個不會經常執行
    }  
    return b;
} 
           

從代碼可以看出，算法的複雜度是O(n)，而且大家會發現，大多數情況下不會發生跳變，也就是b=j并不會執行，并且随着j越來越大，跳變的可能越來越小， 那麼有沒有什麼辦法來進行優化，讓我們能通過一個随機數來直接得到下一次跳變的j，降低算法的複雜度呢？ 論文也在此基礎上給出了優化後的算法并推理論證：

• 把ch(key, num_buckets)看做是一個随機變量，對于特定的key k，jump consistent hash跟蹤了其桶編号的跳變
• 假設b是最後一次跳變的桶編号，也就是ch(k, b) != ch(k, b+1) 且ch(k, b+1) = b
• 假設下一次跳變的結果是j，也就是(b, j)之間每一次增加桶的結果都不應該發生跳變，對于(b,j)區間内的任意的i，j是下一次跳變的機率可以記為：P(j ≥ i) = P( ch(k, i) = ch(k, b+1) )
• 幸運的是P( ch(k, i) = ch(k, b+1) )的結果很好算，我們注意到P( ch(k, 10) = ch(k, 11) ) = 10/11, P( ch(k, 11) = ch(k, 12) ) = 11/12, P( ch(k, 10) = ch(k, 12) ) = 10/11 * 11/12 = 10/12。總的來說，如果n ≥ m, P( ch(k, n) = ch(k, m) ) = m / n. 是以對于任意的 i > b有：P(j ≥ i) = P( ch(k, i) = ch(k, b+1) ) = (b+1) / i，也就是j ≥ i的機率是(b+1) / i。
• 此時我們取一個[0，1]區間的随機數r，規定r < (b+1) / i就有j ≥ i，也就是i ≤ (b+1) / r，這樣我們就得到了i的上界是(b+1) / r，而對于任意的i都有j ≥ i，是以j = floor((b+1) / r)，這樣我們就用一個随機數r來算出了j。

是以上面的算法可以優化成以下實作：

int ch(int key, int num_buckets) {
    random. seed(key) ;
    int b = -1; //  bucket number before the previous jump
    int j = 0; // bucket number before the current jump
    while(j<num_buckets){
        b=j;
        double r=random.next(); //  0<r<1.0< span="">
        j = floor( (b+1) /r);
    }
    return b;
}</r<1.0<>
           

這裡算法的複雜度變成了O(ln n)，代碼裡的随機函數需要是一個均勻的随機數生成器，論文中這裡采用了一個64位的線性同餘随機數生成器，是以對于key本來就是64位整數的，也不需要再對key進行hash計算了。Jump consistent hash的平衡性也取決于線性同餘随機數生成器，是以也有着比較好的平衡性，論文中也與Karger經典的一緻性雜湊演算法進行了對比，下圖3為其對比結果，從标準差來看，jump consistent hash的平衡性比經典的一緻性雜湊演算法好很多。而當節點數量發生變化的時候，jump consistent hash會發生跳變的key的數量已經是理論上的最小值1/n了。但jump consistent hash也有一個比較明顯的缺點，它隻能在尾部增删節點，而不太好在中間增删，對于那種節點随機故障需要剔除的情況，如果用這個算法就需要再采用其他方法來處理了。

4、Maglev hash

Maglev hash是Google于2016年發表的一篇論文中提出來的一種新的一緻性雜湊演算法。Maglev hash的基本思路是建立一張一維的查找表，如圖4所示，一個長度為M的清單，記錄着每個位置所屬的節點編号B0…BN，當需要判斷某個key被配置設定到哪個節點的時候，隻需對key計算hash，然後對M取模看所落到的位置屬于哪個節點。

如何查找看上去很簡單，問題是如何産生這個查找表 。接下來以圖5為例介紹下如何生成查找表，假設我們有三個節點，B0、B1、B2，我們為每個節點生成長度為M(圖5中M=7)的permutation list(偏好序列)，序列是(0，M-1)的随機數(如何生成這個序列我們下面解釋)，如圖5所示，B0的偏好序列是[3,0,4,1,5,2,6]。另外我們準備一個長度為M的待填充的查找表Entry。然後我們按B0、B1、B2的順序，根據每個節點的偏好序列中的數字來填充查找表Entry。我們把偏好序列中的數字作為查找表中的目标位置，把該序列的節點編号填充到查找表的目标位置上，如果目标位置已經被占用，則繼續往下檢視偏好序列的下一個數字。以圖5舉例，具體步驟如下：

1）首先從B0的開始，B0偏好序列的第一個數字是3，是以查找表的3号位置填上B0

2）按順序輪到B1，其偏好序列的第一個數字是0，是以查找表的0号位置填上B1

3）接着輪到B2，發現第一個數字是3，而查找表的3号位置已經被占用，那繼續看B2的偏好序列的第二個數字是4，是以查找表的4号位置填上B2

4）然後又回到B0，這時發現B0的第二個數字是0已經被占用，往下看偏好序列的第三個數字是4，也被占用了，則繼續往下看第四個數字是1，查找表的1号位置沒被占用，是以查找表的1号位置填上B0

5）按此規則繼續處理B1、B2，直到把查找表的所有位置都填滿

論文中也給出了查找表生成過程的僞代碼，如下圖6所示：

介紹完查找表是如何生成的， 還剩下一個問題就是各節點的偏好序列又是如何生成的 。論文中給出的方法是取兩個不相關的hash函數，然後以各個節點的名字使用兩個hash函數分别計算，得到一個offset和一個skip，如下圖7所示，有了offset和skip，對于i号節點的偏好序列的第j個數，則通過(offset + j * skip) mod M就可以得到。論文中還強調了，這裡的M必須是一個素數，這是為了讓每個skip值跟M互質。另外，算法的複雜度是O(MlogM)，最壞情況是O(M*M)，這種情況發生在節點數量N=M，并且每個節點生成的序列都是一樣的情況下，為了避免這種情況，一般建議選擇一個值遠大于N的M。

論文中說明了，按這種方法生成的查找表，每個節點分到的槽位基本是M/N個，最多隻有1的差别，其中N是指所有節點的數量，由此可以看到，Maglev hash有很好的平衡性。下圖8是論文中給出的，Maglev hash與經典一緻性hash及Rendezvous在均衡性方面的實作對比結果，其中的small跟large分别代碼查找表大小為65537和655373，而min跟max分别代表最小及最大的槽位占比。從圖中可以看到，無論是在small還是large的情況下，Maglev hash的均衡性都是最好的，而在small的情況下經典一緻性hash及Rendezvous的最小及最大的槽位占比相差還是挺大的，當然這種情況可以随着查找表的增大而有所下降。

接下來看下 當節點發生增删的時候，對生成的查找表有什麼影響 。以下圖9為例，我們在圖5原來的基礎上假設B1節點出現故障被淘汰掉了，這必然導緻查找表裡的一些槽位編号發生變化，從圖9可以看到，當B1節點删除後，有3個槽位發生了變化，其中0号跟2号位置，由于B1節點的删除被重新配置設定給了B0，這符合一緻性hash的單調性，比較好了解，但還發生了一個從B0到B2的重新映射，這是不符合一緻性雜湊演算法的單調性要求的，論文中也指出了這種情況的存在。

在穩定性方面，經典一緻性哈希、Rendezvous和Jump consistent hash都做到了在後端節點數量發生變化的時候的最小重新映射，而從圖9删除節點的情況來看，Maglev hash并沒有做到最小重新映射。針對這個問題，論文中也對Maglev hash對後端節點數量變化的容忍性做了測試實驗，下圖10是其測試結果，展示了相同後端節點數量、不同查找表大小的情況下，槽位映射結果發生變化的百分比與後端節點故障的百分比的關系。從圖10可以看到， 随着後端節點故障百分比的增加，槽位映射結果發生變化的百分比也在增加，但是在查找表大小比較大的情況下，Maglev hash對後端節點的增删有更好的容忍性 。

但盡管是這樣，Google仍然隻采用65537的查找表大小，據說是覺得後端節點同時故障的機率小，而且還有其他保護機制，另外是當查找表大小從65537增加到655373的時候，查找表的生成時間從1.8ms增加到22.9ms，是以查找表也不能無限擴大。

四、總結

下面簡單地以一個表格對以上四種一緻性雜湊演算法進行對比總結：

算法	擴容	縮容	平衡性	單調性	穩定性	時間複雜度
Ketama	好	好	較好	好	較好	O(log vn)
Rendezvous	好	好	較好	好	較好	O(n)
Jump consistent hash	好	需要額外處理	好	好	好	O(ln n)
Maglev hash	較好	較好	好	較好	較好	O(MlogM),最壞O(M*M)

最後：

我們身為技術人員，最怕的就是安于現狀，一直在原地踏步，那麼你可能在30歲就會迎來自己的職業危機，因為你工作這麼久提升的隻有自己的年齡，技術還是萬年不變！

如果你想在未來能夠自我突破，圓夢大廠，那或許以上這份Java學習資料，你需要閱讀閱讀，希望能夠對你的職業發展有所幫助。

擷取方式： 隻需你**點贊+關注**後，進[Java架構資源交流群] ，找管理者擷取哦-！

*點贊+關注**後，進[Java架構資源交流群] ，找管理者擷取哦-！