整合性ハッシュアルゴリズムCARP原理解析,Golang実装付

ここでは、Segmentfault
作者:CodeKiller
整合性ハッシュアルゴリズムCARP原理解析、Golang実装を添付
バックエンドサービス開発の過程で、mysqlの前にredisをキャッシュする必要があり、redisがクラスタ配置であることを要求し、各redisノードは総データ量の1/Nのみをキャッシュし、Nはredisの個数である.
ここで、hash(key)%Nを用いるvalueへのアクセスを選択する方法が考えられるが、この方法はもちろん、N個のredisサービスにデータを均一に割り当てることができ、実現も非常に簡単である.しかし、このようなハッシュ残高の取り方を用いると、redisクラスタの拡張または縮小、またはダウンタイムが発生した場合、すなわち上記の式のNが変化した場合、このときhash(key)%Nの値が一定に保たれる確率が非常に小さく、換言すれば、キャッシュシステムがこの場合に全体的に失効するという大きな問題がある.これはバックエンドのmysqlにとって瞬時の圧力が非常に大きく、mysqlの崩壊をもたらし、サービス全体の利用不能をもたらす可能性が高い.
従って、1台のredisサービスが停止した場合、1/Nのキャッシュのみが失効することができるかどうか、上記の状況に対応する方法を考えなければならない.
答えは一致性ハッシュアルゴリズムCARPを用いることであり、厳密にはCARPはアルゴリズムではなく、プロトコル、Cache Array Routing Protocol、Cacheグループルーティングプロトコルである.次に、その動作原理について説明します.
まず、redis 1、redis 2…というN個のredisサービスがあると仮定する.redisN,keyは、取得するデータのredisにおけるキーである.
最初のステップでは、すべてのサービス名とkeyのハッシュ値を計算します.

hash_v1 = hash(redis1 + key)
hash_v2 = hash(redis2 + key)
...
hash_vN = hash(redisN + key)

ステップ2では、計算値が最大のhash_vXです.では、選択したのはredisXです.

hash_vX = max(hash_v1, hash_v2, ..., hash_vN)

なぜredisサービスを1台増やした場合、1/(N+1)のキャッシュのみが無効になるのでしょうか.

hash_vX1 = max(hash_v1, hash_v2, ..., hash_vN)
hash_vX2 = max(hash_v1, hash_v2, ..., hash_vN, hash_vN+1)

上記の2つの式を見ると、hash_vX2がhash_vX1より大きくなければならない場合、hash_vN+1が前のN個のハッシュ値より大きくなければならない場合、あなたが選択したhash関数が十分にハッシュするならば、hash_vN+1が前のN個のハッシュ値より大きい確率は1/(N+1)である.redisサービスを1台減らすとキャッシュが無効になる確率を自分で計算することができます.
最後に、Golangインプリメンテーションバージョンを添付します.

package carp

import (
    "crypto/md5"
    "errors"
)

var (
    ErrHaveNoRedis = errors.New("have no redis")
)

//    carp   ,   redisArr           redis,       
func GetTargetIndex(key string, redisArr []string) (idx int, err error) {
    if len(redisArr) < 1 {
        return -1, ErrHaveNoTarget
    } else if len(redisArr) == 1 {
        return 0, nil
    }

    hashArr := make([]string, len(redisArr))
    for k, v := range redisArr {
        hashArr[k] = hashString(v + key)
    }
    idx = minIdx(hashArr)
    return
}

//    arr          
func minIdx(arr []string) (idx int) {
    if len(arr) < 1 {
        return -1
    }

    idx, min := 0, arr[0]

    for k, v := range arr {
        if v < min {
            idx = k
            min = v
        }
    }
    return
}

func hashString(str string) (hash string) {
    md5sum := md5.Sum([]byte(str))
    return string(md5sum[:])
}

上のコードではmd 5のハッシュアルゴリズムを使用していますが、パフォーマンスにもっと高い要求があればFNVハッシュアルゴリズムを使用することができます.