5장. 안정 해시 설계

수평적 규모 확장을 달성하기 위해 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 

이를 위해 보편적으로 안정 해시를 사용한다.

 

해시 키 재배치 문제

N개의서버에 균등하게 나누는 보편적인 방법

  -  serverIndex = hash(key) % N(서버 개수)

서버가 추가되거나 제거되면 키가 변경되므로 상당한 데이터가 재배치 되어야 한다.

 

안정 해시

데이터나 키가 변경되지 않는 한, 항상 동일한 해시 값을 반환하는 해시 기법이다.

즉 서버의 개수가 변동된다고 해서 해시값이 변하지 않으며, 데이터의 재배치를 최소화할 수 있다.

 

가상 노드

가상 노드는 실제 노는 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드로 구성한다.

가상 노드의 개수를 늘리면 키의 분포가 균등해져, 데이터가 고르게 분포될 수 있다.

대신 가상 노드가 많으면 키를 재배치할 때 영향 받는 노드들이 많아질 수 있다.

 

안정 해시 구현 (GPT)

package ch05_consistent_hash;

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.SortedMap;
import java.util.TreeMap;

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

    public ConsistentHash(int numberOfReplicas) {
        this.numberOfReplicas = numberOfReplicas;
    }

    // 노드를 해시 링에 추가
    public void addNode(String node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            int hash = getHash(node + i);
            circle.put(hash, node);
        }
    }

    // 노드를 해시 링에서 제거
    public void removeNode(String node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            int hash = getHash(node + i);
            circle.remove(hash);
        }
    }

    // 데이터 키에 해당하는 노드 찾기
    public String getNode(String key) {
        if (circle.isEmpty()) {
            return null;
        }
        int hash = getHash(key);
        if (!circle.containsKey(hash)) {
            SortedMap<Integer, String> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }

    // SHA-256 기반 해시 함수
    private int getHash(String key) {
        try {
            MessageDigest digest = MessageDigest.getInstance("SHA-256");
            byte[] hashBytes = digest.digest(key.getBytes(StandardCharsets.UTF_8));
            return Math.abs(hashBytes[0] << 24 | (hashBytes[1] & 0xFF) << 16 | (hashBytes[2] & 0xFF) << 8 | (hashBytes[3] & 0xFF));
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("SHA-256 algorithm not found", e);
        }
    }

    public static void main(String[] args) {
        ConsistentHash consistentHash = new ConsistentHash(3); // 가상 노드 3개

        // 노드 추가
        consistentHash.addNode("NodeA");
        consistentHash.addNode("NodeB");
        consistentHash.addNode("NodeC");

        // 데이터 키 할당 확인
        System.out.println("Key1 -> " + consistentHash.getNode("Key1"));
        System.out.println("Key2 -> " + consistentHash.getNode("Key2"));
        System.out.println("Key3 -> " + consistentHash.getNode("Key3"));

        // 노드 추가 후 데이터 이동 확인
        consistentHash.addNode("NodeD");
        System.out.println("\nAfter adding NodeD:");
        System.out.println("Key1 -> " + consistentHash.getNode("Key1"));
        System.out.println("Key2 -> " + consistentHash.getNode("Key2"));
        System.out.println("Key3 -> " + consistentHash.getNode("Key3"));

        // 노드 제거 후 데이터 이동 확인
        consistentHash.removeNode("NodeC");
        System.out.println("\nAfter removing NodeC:");
        System.out.println("Key1 -> " + consistentHash.getNode("Key1"));
        System.out.println("Key2 -> " + consistentHash.getNode("Key2"));
        System.out.println("Key3 -> " + consistentHash.getNode("Key3"));
    }
}