Consistent hashing, 일관된 해싱

Consistent hashing, 일관된 해싱

  일관된 해싱(Consistent hashing)은 해싱 기법중 하나로 해싱 테이블 크기가 조정될 때 전체 키중에서 n/m 만 remmaping하면 되는 방법 이다. (n: 키의 개수, m: 슬롯 개수)
* 일반 해시 테이블에서는 거의 모든 키를 다시 매핑 해야 한다.

우선 Hash에 대한 부분부터 짚고 넘어가자.

 

---

 

Hash table(=Hash map)

  해시(Hash)는 임의의 데이터를 고정된 크기의 값으로 변환하는 과정으로 변환된 값을 해시 값 또는 해시 코드라고 하다.
이렇게 변환된 해시 값을 배열의 인덱스에 사용하는 자료구조로 Dictionary 혹은 Map 이라고도 부르며 이를 해시 테이블이라 하며 이런 특징을 이용하여 빠른 접근, 빠른 삽입, 빠른 삭제가 가능하다.

해시 함수를 통과한 데이터는 식별 가능한 고정 크기 값으로 변환되며 

hash("hello python")
8569808092792221344

hash("hello python2")
-6108771603744125716

실행시마다 독립적인 해시 값을 갖게 된다.

/Users/raynor/workspace/python3_sample/.venv/bin/python /Applications/PyCharm.app/Contents/plugins/python/helpers/pydev/pydevconsole.py --mode=client --host=127.0.0.1 --port=54948 

import sys; print('Python %s on %s' % (sys.version, sys.platform))
sys.path.extend(['/Users/raynor/workspace/python3_sample'])

PyDev console: starting.
Python 3.12.8 (main, Dec  3 2024, 18:42:41) [Clang 16.0.0 (clang-1600.0.26.4)] on darwin

hash("python")
5849901086014848506

hash("python")
5849901086014848506

========================================================================

/Users/raynor/workspace/python3_sample/.venv/bin/python /Applications/PyCharm.app/Contents/plugins/python/helpers/pydev/pydevconsole.py --mode=client --host=127.0.0.1 --port=54979 

import sys; print('Python %s on %s' % (sys.version, sys.platform))
sys.path.extend(['/Users/raynor/workspace/python3_sample'])

PyDev console: starting.
Python 3.12.8 (main, Dec  3 2024, 18:42:41) [Clang 16.0.0 (clang-1600.0.26.4)] on darwin

hash("python")
-7039268742544349232

hash("python")
-7039268742544349232

문제로는 서로 다른 데이터에 대해 해시 값이 동일하여 충돌하는 경우가 발생할 수 있는데 이를 해결하기 위한 두가지 방법이 있다.

 

Seperate Chaining, 개별 체이닝

개별 체이닝은 충돌 발생시 동일한 슬롯에 연결 리스트로 저장을 하는 방법이다.

 

Oepn Addressing, 오픈 어드레싱

오픈 어드레싱은 충돌 발생시 비어있는 슬롯을 검사(Prove sequence)하여 빈 슬롯에 저장을 하는 방법이다.

슬롯 검사 과정은 부하계수에 비례 해서 증가하기 때문에 개별 체이닝에 비해서 성능적인 부하가 있을 수 있다. 
Java, Go PHP는 개별 체이닝, Python은 오픈 어드레싱을 사용하고 있다.

 

---

 

Consistent hashing, 일관된 해싱

  다시 일관된 해싱(Consistent hashing)으로 돌아와서 분산 시스템으로 구성된 데이터 저장소에 데이터를 저장한다고 했을 때,
hash(data) % N(서버 개수) 방식으로 저장소를 선택하여 데이터에 저장하는 상황에서 서버의 개수가 N에서 N+a로 변경 되었을 때 새로 저장되는 데이터들은 문제가 없지만 기존에 저장되어 있는 데이터들은 모두 서버간 재배치가 필요해진다. 

 

일관된 해싱은 이를 해결하기 위한 기법으로 해시링(Hash Ring) 원형 구조를 사용하여 서버와 데이터를 배치 한다.

Hash Ring

• 0 ~ 알고리즘 해시 공간 범위의 해시 값을 원형으로 배치
  (MD5: 2^128, SHA-256: 2^256, ...)
• 서버와 데이터 키를 같은 해시 함수를 사용하여 원형 공간에 배치
• 각 데이터는 자신보다 큰 해시 값을 가진 가장 가까운 서버에 저장

동일한 해시 함수를 사용하여 해시 링에 매핑한 4개 서버가 있다고 가정해보자

해시 함수를 통한 해시 값은 자기보다 큰 가장 가까운 해시 값을 가진 서버에 저장 될 것이다.

아래처럼 서버 1대 추가 되었다면 key0만 재배치가 발생하고 다른 키들은 재배치가 발생하지 않는다.

아래처럼 서버 1대가 제거 되었다면 key1은 s1에서 s2로 재배치가 발생한다.

다만 이 경우가 발생할 때 해시 특성상 해시 값은 랜덤하게 나와 노드마다 균등하게 저장이 불가능하다. 일관된 해싱에서는 이를 해결하기 위해서 가상 노드(Virtula node) 개념을 사용하고 있다.

 

Virtula node, 가상노드

하나의 서버를 여러 개의 가상 노드(서브 노드)로 나누어 해시 링에 배치하여 서버 간 데이터 불균형 문제를 해결 합니다. 이를 통해서 노드가 고르게 분포되어 특정 서버에 트래픽이 몰리는 현상을 방지되고 부하가 균등하게 분산되어 로드 밸런싱 효과를 높여 준다.

 

---

구현

class ConsistentHashing:

    def __init__(self, nodes: List[Any], number_of_replicas: int, hash_func: Callable = None):
        self.nodes: set = set()
        self.number_of_replicas: int = number_of_replicas
        self.hash_ring = {}
        self.hash_func: Callable = hash_func or hash
        self.virtual_nodes: list = []

        for node in nodes:
            self.add_node(node)

    def add_node(self, node: Any):
        """
        Adds a node to hash ring with its virtual nodes.
        """
        self.nodes.add(node)

        for i in range(self.number_of_replicas):
            hash_value = self.hash_func(f"{node}:{i}")
            self.hash_ring[hash_value] = node
            bisect.insort(self.virtual_nodes, hash_value)

    def remove_node(self, node: Any):
        """
        Remove a node and its virtual nodes from the hash ring.
        """
        self.nodes.remove(node)

        for i in range(self.number_of_replicas):
            hash_value = self.hash_func(f"{node}:{i}")
            self.hash_ring.pop(hash_value, None)
            self.virtual_nodes.remove(hash_value)

    def get_node(self, key: Any):
        """
        Find the closest node for a given key.
        """
        hash_value = self.hash_func(key)
        index = bisect.bisect_right(self.virtual_nodes, hash_value) % len(self.hash_ring)
        return self.hash_ring[self.virtual_nodes[index]]

ch = ConsistentHashing(
    nodes=["A", "B", "C"],
    number_of_replicas=3,
    hash_func=lambda x: hash(x),
)
ch.get_node("hello")
'A'
ch.get_node("python")
'C'
ch.add_node("D")
ch.get_node("hello")
'A'
ch.get_node("kotlin")
'A'
ch.remove_node("A")
ch.remove_node("B")
ch.get_node("hello")
'D'

 

---

 

실제 사용 사례

• CDN(Content Delivery Network)
• Amazon DynamoDB, Apache Cassandra
• Memcached, Redis 클러스터

 

---

출처

https://en.wikipedia.org/wiki/Hash_table

https://en.wikipedia.org/wiki/Consistent_hashing

https://shanu95.medium.com/consistent-hashing-101-a9edbb623f1f