Consistent Hashing의 이해와 구현

반응형

Consistent Hashing은 분산 시스템에서 노드(서버)의 추가나 제거 시에도 데이터의 재분배(리밸런싱)를 최소화하는 해싱 기법입니다. 전통적인 해싱 방식은 해시 공간을 균등하게 분할하여 키를 각 노드에 할당하지만, 노드가 변경되면 대부분의 키가 재할당되는 단점이 있습니다. 반면 Consistent Hashing은 전체 해시 공간을 원형(해시 링)으로 구성하고, 각 노드를 이 링 상에 여러 개의 가상 노드(virtual node)로 매핑하여 키를 할당합니다. 이를 통해 한 노드가 추가되거나 제거되더라도, 영향을 받는 키의 비율이 작아져 시스템의 안정성과 확장성을 높일 수 있습니다.

동작 원리

1. 해시 링 구성:
   해시 공간을 0부터 2³²-1 또는 0부터 2⁶⁴-1 등의 범위로 보고, 이를 원형으로 취급합니다. 각 노드는 하나 이상의 가상 노드를 생성하여 링 상에 배치됩니다.
2. 키 할당:
   데이터를 저장할 때, 해당 키를 해시 함수를 통해 해시 값을 구합니다. 이 해시 값을 기준으로 링 상에서 키보다 크거나 같은 첫 번째 노드(가상 노드)를 찾고, 그 노드에 데이터를 할당합니다. 만약 해시 값이 링의 최대값보다 크다면, 링의 시작점으로 돌아갑니다.
3. 노드 추가/제거 시 효과:
   새로운 노드가 추가되면, 해당 노드의 가상 노드 위치에 위치한 키들만 새 노드로 이동하며, 제거 시에도 동일하게 영향을 받는 키의 수가 제한됩니다. 이로 인해 전체 시스템에 대한 부하를 줄이고, 서비스 중단 없이 확장이 가능해집니다.

 

Consistent Hashing의 장점

• 확장성: 노드 추가 및 제거 시 전체 데이터의 대부분은 그대로 유지되므로, 분산 캐시나 분산 저장소에서 유용합니다.
• 부하 분산: 가상 노드의 수를 조정하여 각 노드에 고르게 데이터를 분산할 수 있습니다.
• 내결함성: 특정 노드 장애 시에도 다른 노드로 최소한의 데이터만 재분배되어 시스템 안정성이 높아집니다.

간단한 Java 코드 예제

import java.util.SortedMap;
import java.util.TreeMap;
import java.util.Collection;

public class ConsistentHash<T> {
    private final int numberOfReplicas;
    private final SortedMap<Integer, T> circle = new TreeMap<>();

    public ConsistentHash(int numberOfReplicas, Collection<T> nodes) {
        this.numberOfReplicas = numberOfReplicas;
        for (T node : nodes) {
            add(node);
        }
    }

    public void add(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.put(hash(node.toString() + i), node);
        }
    }

    public void remove(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.remove(hash(node.toString() + i));
        }
    }

    public T get(Object key) {
        if (circle.isEmpty()) {
            return null;
        }
        int hash = hash(key.toString());
        if (!circle.containsKey(hash)) {
            SortedMap<Integer, T> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }

    private int hash(String key) {
        // 간단한 해시 함수 예시 (실제 환경에서는 더 복잡한 해시 알고리즘 사용 권장)
        return key.hashCode();
    }

    // 테스트 코드 예제
    public static void main(String[] args) {
        java.util.List<String> nodes = java.util.Arrays.asList("NodeA", "NodeB", "NodeC");
        ConsistentHash<String> ch = new ConsistentHash<>(3, nodes);
        String key = "my_data_key";
        System.out.println("Key '" + key + "' is assigned to: " + ch.get(key));
    }
}

간단한 Python 코드 예제

import hashlib
import bisect

class ConsistentHash:
    def __init__(self, nodes=None, replicas=3):
        self.replicas = replicas
        self.ring = {}
        self.sorted_keys = []
        if nodes:
            for node in nodes:
                self.add_node(node)
    
    def add_node(self, node):
        for i in range(self.replicas):
            key = self.hash_function(f"{node}:{i}")
            self.ring[key] = node
            self.sorted_keys.append(key)
        self.sorted_keys.sort()
    
    def remove_node(self, node):
        for i in range(self.replicas):
            key = self.hash_function(f"{node}:{i}")
            del self.ring[key]
            self.sorted_keys.remove(key)
    
    def get_node(self, key_str):
        key = self.hash_function(key_str)
        idx = bisect.bisect(self.sorted_keys, key)
        if idx == len(self.sorted_keys):
            idx = 0
        return self.ring[self.sorted_keys[idx]]
    
    def hash_function(self, key):
        return int(hashlib.md5(key.encode('utf-8')).hexdigest(), 16)

# 테스트 코드 예제
if __name__ == "__main__":
    nodes = ["NodeA", "NodeB", "NodeC"]
    ch = ConsistentHash(nodes=nodes, replicas=3)
    test_key = "my_data_key"
    print("Key '{}' is assigned to: {}".format(test_key, ch.get_node(test_key)))

결론

Consistent Hashing은 분산 시스템에서 데이터의 효율적 분배와 확장성을 위해 필수적인 알고리즘입니다. 노드의 추가 및 제거가 빈번한 환경에서 데이터의 재배치를 최소화하여 시스템의 안정성을 높이며, 부하 분산과 내결함성 측면에서 큰 장점을 제공합니다. 위의 Java와 Python 예제는 Consistent Hashing의 기본 원리와 구현 방법을 이해하는 데 도움을 주며, 실제 환경에서는 해시 충돌 방지 및 성능 최적화를 위한 추가적인 고려가 필요합니다.