Consistent Hashing 정리

• Consistent Hashing에 가장 큰 특징 중 하나는 HashRing에 k 개의 노드가 있는 상황에서, 노드가 사라지거나 추가될 때 1/k 정도의 key에 대한 것만 유실이 되고 나머지 key는 변동 없이 유지되는 것 임
• 같은 값으로 노드들이 만들어지면 순서도 항상 동일

 

Consistent Hashing의 핵심은 hash 함수

• Consistent Hashsing 의 가장 큰 핵심은 hash 함수
• hash 함수의 특징은 f = hash(key) 의 결과가 항상 같은 key에 대해서는 같은 hash 결과 값이 나옴 -> host1, host2, host3 와 같은 주소를 해시하면 hash 함수를 바꾸지 않는 이상은 항상 같은 hash 값이 나옴
• hash 값으로 정렬을 하게 되면 항상 같은 순서가 나옴

 

hash 값으로 Hash Ring을 생성하는 경우

• 이해를 쉽게 하기 위해서, hash의 결과가 0 부터 1 까지 float 형태로 나온다고 가정
• hash("host1") = 0.25, hash("host2") = 0.5, hash("host3") = 0.75 가 나온다고 가정
• 특정 key에 대한 hash 결과는 hash 값이 크면서 가장 가까운 host에 저장이 된다고 가정
  1. hash("key1") = 0.3 이면 key1이라는 key가 위치할 서버는 0.5 값을 가지는 host2가 되게 됨
  2. 0.75 보다 크면 Ring 이므로 다시 첫번째 host1에 저장이 됨
• hash 함수와 서버의 목록만 알면, 특정 key를 어디에 저장할 것인지 결정 가능

 

Consistent Hashing에서 서버가 추가되거나 삭제될 때 1/k 개의 key만 삭제

• hash("host4") = 0.6 인 서버가 하나 추가되었다고 가정
• 서버가 들어오면 순서는 host1, host2, host4, host3 이 됨
• host4 와 host3 사이의 값, 즉 hash 함수의 결과가 0.6 ~ 0.75 인 key들만 저장해야 할 서버가 바뀌지, 다른 key들은 원래의 위치에 그대로 저장됨
• 아래 그림으로 Consistent Hashing

 

1. A, B, C 세 대의 서버가 hash Ring을 구성

2. 첫번째 1이라는 key가 들어오면 hash("1") 해서 나온 결과값을 보니 B가 규칙에 맞아서 B에 저장

3. 두번째 2가 들어올 경우 hash("2") 해서 나온 결과값을 보니 C가 규칙에 맞아서 C에 저장

4. key 3,4는 hash("3"), hash("4")의 값이 A 서버에 속하므로 A 에 들어가고, key 5는 C에 가까워서 C에 들어가게 됨

5. A, B, C의 공간이 서로 균일하지가 않음 -> 가상 서버(vnode) 생성

• B가 죽는다고 가정하면 B의 부하는 전부 C로 넘어가게 됨 -> 불공평한 일이 발생 가능
• 불공평한 일이 발생할 가능성을 제거하기 위해 가상의 친구들을 더 만들어냄
  1. 가상 서버들을 한 서버당 2개씩 더 만듦 -> hash('A'), hash('A+1'), hash('A+2') 로 Hash Ring 에 추가
  2. B는 hash('B'), hash('B+1'), hash('B+2') 등으로 추가
  3. 총 3개의 서버를 9개로 보이게 함
• 아래와 같이 A+1은 실제로는 A지만, hash ring에서 가상적으로 다른 서버로 보이게 함
• hash ring 자체도 더 촘촘해지고, 어떤 서버가 한대 장애가 나더라도, 그 부하가, 적절하게 나머지 두 서버로 나눠지게 됨
• 실제 서비스에서는 서버당 수십개의 가상 노드를 만들어서 처리 -> 예시로2~3개로 설명하였지만, 실제는 많음
  

  

6. 핵심 결론 -> 서버 이름으로 hash 값을 만들어서 정렬한 것을 하나의 Ring 처럼 생각해서 key를 hash 값에 따라 저장

 

python2의 Consistent Hashing 코드 -> rebuild가 핵심

### consistent_hash.py 파일
import sys
import hashlib
import struct

VALUE_IDX = 2
HASH_IDX = 3
LAST = -1
FIRST = 0

class ConsistentHash:
    def __init__(self, kvlist, replica, hash_func = None):
        self.hash_func = hash_func
        if not self.hash_func:
            self.hash_func = self.ketama_hash
        self.kvlist = kvlist
        self.replica = replica
        self.continuum = self.rebuild(kvlist)

    def ketama_hash(self, key):
        return struct.unpack('<I', hashlib.md5(key).digest()[0:4])

    def rebuild(self, kvlist):
        continuum = [(k, i, v, self._hash("%s:%s"%(k,i))) \
                     for k,v in kvlist \
                     for i in range(self.replica)]
        continuum.sort(lambda x,y: cmp(x[HASH_IDX], y[HASH_IDX]))
        return continuum

    def _hash(self, key):
        return self.hash_func(key)

    def find_near_value(self, continnum, h):
        size = len(continnum)
        begin = left = 0
        end = right = size
        while left < right:
            middle = left + (right - left) / 2
            if continnum[middle][HASH_IDX] < h:
                left = middle + 1
            else:
                right = middle
        if right == end:
            right = begin
        return right, continnum[right][VALUE_IDX]

    def get(self, key):
        h = self._hash(key)
        if h > self.continuum[LAST][HASH_IDX]:
            return self.continuum[FIRST][VALUE_IDX]
        return self.find_near_value(self.continuum, h)

if __name__ == "__main__":
    replica = 2
    kvlist = [("host1", "value1"), ("host2", "value2"), ("host3", "value3"), ("host4", "value4")]
    ch = ConsistentHash(kvlist, replica)
    print ch.continuum
    v = ch.get(sys.argv[1])
    print v[0], ch.continuum[v[0]]
    
    
##### 실행
$ python2 consistent_hash.py hosts1
[('host3', 0, 'value3', (1063727328,)), ('host4', 1, 'value4', (1685475194,)), ('host2', 1, 'value2', (2063768010,)), ('host4', 0, 'value4', (2327965545,)), ('host1', 1, 'value1', (2749222897,)), ('host2', 0, 'value2', (2807531582,)), ('host1', 0, 'value1', (3226067400,)), ('host3', 1, 'value3', (3295705430,))]
(1, ('host4', 1, 'value4', (1685475194,)))

$ python2 consistent_hash.py hosts2
[('host3', 0, 'value3', (1063727328,)), ('host4', 1, 'value4', (1685475194,)), ('host2', 1, 'value2', (2063768010,)), ('host4', 0, 'value4', (2327965545,)), ('host1', 1, 'value1', (2749222897,)), ('host2', 0, 'value2', (2807531582,)), ('host1', 0, 'value1', (3226067400,)), ('host3', 1, 'value3', (3295705430,))]
(6, ('host1', 0, 'value1', (3226067400,)))

 

Hash Ring을 구성하는 서버의 이름이 바뀌는 경우 -> hash ring이 다르게 구성됨

• Consistent hashing을 많이 쓰는 libmemcached 의 경우 보통 서버 주소가 들어가게됨
• "1.1.1.1:11211", "1.1.1.2:11211", "1.1.1.3:11211" 서버 이름을 가진 상황에서 1.1.1.2 서버가 문제가 발생
• 기존 장비를 교체하기 위해 새 장비를 받는데, 해당 장비의 IP는 1.1.1.4 가짐 -> Hash Ring이 꼬여 버릴 수 있음
• Hash Ring이 꼬이는 문제를 해결하기 위해서는 직접적인 이름 대신에 alias한 다른 이름으로 Consistent Hashing을 구성 필요
• 즉 redis001, redis002, redis003, redis004 이름으로 Hash Ring을 구성하고, 서버가 바뀌더라도 기존 이름을 사용사용하면 Consistent hashing의 문제 없음

 

Hash 재분배 vs Consistent Hashing 재분배

1.Hash 재분재

2.Consistent Hashing 재분배

 

Consistent hashing 응용

1.Web Cache

• 웹 캐시는 웹 서비스 품질을 높이려고 할 때, 가장 먼저 고려하는 요소 -> CSS, 자바스크립트, 이미지, HTML과 같은 정적인 페이지를 고성능의 서버에 캐시하고 있다가 웹 서버 대신 응답해 주는 일
• 캐시하기 힘든 동적인 페이지, 혹은 캐시 실패한 요청만 웹 서버로 전달
• Consistent hash를 이용하면, 분산 웹 캐시 시스템을 만들 수 있음
• Consistent hash로 구성하면, (관리 없이)자유롭게 캐시를 늘리거나 줄일 수 있음 -> 대량의 멀티미디어 파일을 서비스에 특히 유용하게 사용 가능

• Web Cache 순서
  1. 유저의 요청은 먼저 Proxy server로 향함
  2. Proxy 서버는 유저가 요청한 자원(URL)이 해시테이블에 있는지 확인
  3. 해시테이블에 있다면, Cache Server에 요청
  4. 해시테이블에 없거나, 캐시에서 가져오는게 실패했다면 Web Server에 요청
     

     

2. 샤딩(Sharding)

• 데이터베이스 샤드(Shard)는 검색이나 데이터베이스에서 사용하는 horizontal partition 기법
• 데이터베이스의 내용이 여러 서버 인스턴스로 저장하는 방식으로 로드를 분산함
• Key-Value 기반의 NoSQL 데이터베이스에서 consistent hash를 이용해서 샤딩을 구현하는 경우가 많음
  

  

※ 참고

• 참고 URL : https://www.popit.kr/consistent-hashing/
• Consistent Hashing 소개 논문 : https://dl.acm.org/doi/pdf/10.1145/258533.258660
• Consistent Hashing 응용 참고 : https://www.joinc.co.kr/w/man/12/hash/consistent