Consistant hash

URL을 md5로 hash한  $hsh 변수에 저장된 16진수 문자열을 10진수 정수값으로 변환한 후, 총 슬롯 수 $total_slots로 나누어 node_index를 구하는 함수를 bash로 작성하면 아래와 같다.

 

hash_fn() {
    key=$1
    total_servers=3

    # converting data into bytes and passing it to hash function
    hsh=$(echo -n $key | md5sum | awk '{print $1}')

    # converting the HEX digest into equivalent integer value and converting negative values to positive
    echo $(( (16#$hsh % $total_servers + $total_servers) % $total_servers ))
}


server_index=$(hash_fn $1)

echo "URL: $1  server: $server_index"

위 bash code로 URL변경 시키면 아래와 같이 3개의 서버로 수렴됨을 알 수 있다.

동일한 URL(key)는 동일한 서버로 수렴된다.

# for i in {1..10} ; do uphash my/$i.json ; done
URL: my/1.json  server: 0
URL: my/2.json  server: 2
URL: my/3.json  server: 1
URL: my/4.json  server: 2
URL: my/5.json  server: 0
URL: my/6.json  server: 1
URL: my/7.json  server: 1
URL: my/8.json  server: 2
URL: my/9.json  server: 0
URL: my/10.json  server: 0

이러한 해시 함수를 이용하면 URL별로 upstream으로 트래픽을 고르게 분산시키고, 특정 URL에  upstream서버를 고정해서 사용할 수 있어 캐쉬 효율이 올라간다. 별로로 URL별 upstream 목록을 관리하지 않아도 되고 key로 사용되는 URL만 알면 hash함수로 바로 upstream을 알 수 있으므로 속도도 빠르다. 

하지만 단점이 있는데,  upstream서버가 장애가 일어나거나, upstream 서버가 늘어나거나 하는 변경이 일어나면 동일한 key라도 다른 서버로 재정렬되기 때문에 이때까지 cache해 놓은 파일이 다 쓸 모 없게 될 수 있다.

 

위 script에서 서버 수를 2로 줄이면 아래와 같이 전혀 다른 서버로 배치됨

# for i in {1..10} ; do uphash my/$i.json ; done
URL: my/1.json  server: 1
URL: my/2.json  server: 1
URL: my/3.json  server: 1
URL: my/4.json  server: 1
URL: my/5.json  server: 0
URL: my/6.json  server: 0
URL: my/7.json  server: 0
URL: my/8.json  server: 1
URL: my/9.json  server: 1
URL: my/10.json  server: 0

서버 수를 4로 늘여도 앞선 배치와 다르게 배치되어 서버 장애 및 확장에 문제가 발생할 수 있다.

# for i in {1..10} ; do uphash my/$i.json ; done
URL: my/1.json  server: 1
URL: my/2.json  server: 3
URL: my/3.json  server: 1
URL: my/4.json  server: 3
URL: my/5.json  server: 2
URL: my/6.json  server: 2
URL: my/7.json  server: 2
URL: my/8.json  server: 3
URL: my/9.json  server: 1
URL: my/10.json  server: 0

이를 최소화 하기 위해 고안된 방식이 consistance hash로 key-value 쌍을 저장하는 방법을 이용하면 이동을 최소화 할 수 있다. 아래는 bash로 작성된 계략적 형태임.

#!/bin/bash

# Define the list of servers
servers=("server1" "server2" "server3")

# Define the hash function
hash_fn() {
    key=$1

    # converting data into bytes and passing it to hash function
    hsh=$(echo -n $key | md5sum | awk '{print $1}')

    # converting the HEX digest into equivalent integer value
    echo $(( 16#$hsh ))
}

# Define the consistent hash function
consistent_hash() {
    key=$1
    num_servers=${#servers[@]}
    max=4294967295

    # Get the hash value of the key
    hsh=$(hash_fn $key)

    # Find the server that is responsible for this key
    for ((i=0; i<$num_servers; i++)); do
        if [[ $(hash_fn ${servers[$i]}) -gt $hsh ]]; then
            echo "${servers[$i]}"
            return
        fi
    done

    # If no server was found, return the first server
    echo "${servers[0]}"
}

# Test the consistent hash function
for i in {1..10}; do
    server=$(consistent_hash "my/$i.json")
    echo "URL: my/$i.json  server: $server"
done