🌐 안정 해시 (Consistent Hashing) 설계 및 원리

1. 개요

수평적 확장성(horizontal scalability)을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 분산하는 것이 중요하다.

안정 해시(Consistent Hashing)는 서버가 동적으로 추가되거나 제거될 때도 최소한의 데이터 이동만으로 분산 균형을 유지할 수 있는 기술로, 다양한 분산 시스템에서 널리 사용된다.

---

2. 전통적인 해시 기법의 한계: Rehash 문제

📌 기본 방식

서버 인덱스 = hash(key) % N   (N: 서버 수)

• 서버 수가 고정된 경우에는 잘 동작한다.
• 하지만 서버가 추가되거나 제거되면 N 값이 바뀌며 대부분의 키가 다른 서버로 재배치되어 캐시 미스 및 시스템 부하 발생.

---

3. 안정 해시란?

안정 해시는 서버 수(N)가 변경되어도 전체 키(k) 중 일부(k/n)만 재배치되는 해시 기법이다.

서버와 키를 같은 해시 공간에 매핑하고, 키는 시계 방향으로 가장 가까운 서버에 배정된다.

---

4. 핵심 개념

🔸 해시 공간 (Hash Space)

• 일반적으로 0 ~ 2³²-1의 정수 범위를 사용하는 원형 공간.

🔸 해시 링 (Hash Ring)

• 해시 공간을 원형 구조로 연결한 것. 맨 끝과 처음이 연결되어 순환 구조를 이룸.

🔸 키-서버 매핑

• 키와 서버 모두 해시 함수를 통해 링에 위치시킨다.
• 키는 자신보다 해시값이 큰 첫 번째 서버에 매핑된다 (시계 방향 탐색).

---

5. 서버 추가/제거 시 동작

✅ 서버 추가

• 새 서버 위치의 일부 키만 재배치됨 → 기존 서버에 영향 최소화

✅ 서버 제거

• 해당 서버의 해시 공간만 인접 서버로 이동 → 나머지 키는 그대로 유지

평균적으로 k/n개의 키만 재배치

---

6. 안정 해시의 문제점

❗ 1. 불균형한 파티션 분포

• 해시 함수가 랜덤하게 서버를 링에 배치하기 때문에 어떤 서버는 작은 해시 공간, 어떤 서버는 큰 공간을 가질 수 있다.

❗ 2. 키의 불균형 분포

• 일부 키가 특정 해시 범위에 몰려 Hotspot이 발생할 수 있다.

---

7. 해결책: 가상 노드 (Virtual Nodes)

✅ 개념

• 하나의 실제 서버가 해시 링에 여러 개의 가상 노드(VNode)로 존재한다.
• 각 VNode는 서로 다른 해시 값을 가진 독립적인 노드처럼 행동한다.

✅ 장점

• 키 분포의 표준 편차가 줄어들어 균등 분산 가능
• 적은 수의 서버로도 부하 균형 향상
• 장애 복구 및 동적 확장 유연

⚠️ 단점

• VNode 수가 많을수록 메모리 및 메타데이터 관리 비용 증가
• 적절한 수의 가상 노드를 선택하는 트레이드오프 필요

---

8. 키 재배치 기준

• 서버 추가 시: 해당 위치에서 다음 서버 사이의 키만 이동
• 서버 제거 시: 이전 서버부터 해당 서버 위치까지의 키만 이동

➡️ 대부분 키는 변경되지 않음

---

9. 장점 요약

항목	내용
확장성	서버 추가/제거 시 재배치 최소화
균형성	가상 노드를 통해 균등한 키 분포 달성
유연성	동적 서버 관리 용이
안정성	Hotspot 현상 완화, 장애 격리 효과

---

10. 활용 사례

• Amazon DynamoDB: 파티셔닝 컴포넌트
• Apache Cassandra: 데이터 분산 구조
• Discord: 메시지 샤딩 및 라우팅
• Netflix EVCache: 캐시 서버 샤딩 최적화

---

11. 실무 적용 팁

• 고성능 해시 함수 사용 (예: MurmurHash, CityHash 등)
• VNode 수 조절: 보통 서버당 100~200개 수준
• 메타데이터 정합성 유지: 링 구조 공유를 위한 중앙 저장소 또는 분산 락 활용
• 모니터링: 특정 VNode나 키 범위에 과부하가 몰리는지 확인

---

✅ 마무리

안정 해시는 분산 시스템에서 유연한 확장, 장애 허용성, 성능 향상을 동시에 추구할 수 있는 핵심 기법이다. 단순한 구현으로 높은 효율성을 얻을 수 있으며, 캐시, 키-값 저장소, 마이크로서비스 샤딩 등 다양한 환경에서 널리 쓰이고 있다.

---

🧑‍💻 코드 구현 예시

🐍 Python: 안정 해시 구현 (with Virtual Nodes)

import hashlib
import bisect

class ConsistentHash:
    def __init__(self, replicas=100):
        self.replicas = replicas  # 가상 노드 수
        self.ring = dict()
        self.sorted_keys = []
        self.nodes = set()

    def _hash(self, key):
        return int(hashlib.md5(key.encode('utf-8')).hexdigest(), 16)

    def add_node(self, node):
        self.nodes.add(node)
        for i in range(self.replicas):
            virtual_node_key = f"{node}#{i}"
            hash_val = self._hash(virtual_node_key)
            self.ring[hash_val] = node
            bisect.insort(self.sorted_keys, hash_val)

    def remove_node(self, node):
        self.nodes.discard(node)
        for i in range(self.replicas):
            virtual_node_key = f"{node}#{i}"
            hash_val = self._hash(virtual_node_key)
            self.ring.pop(hash_val, None)
            index = bisect.bisect_left(self.sorted_keys, hash_val)
            if index < len(self.sorted_keys) and self.sorted_keys[index] == hash_val:
                self.sorted_keys.pop(index)

    def get_node(self, key):
        if not self.ring:
            return None
        hash_val = self._hash(key)
        index = bisect.bisect(self.sorted_keys, hash_val) % len(self.sorted_keys)
        return self.ring[self.sorted_keys[index]]

# 예제 사용
hash_ring = ConsistentHash()

hash_ring.add_node("ServerA")
hash_ring.add_node("ServerB")
hash_ring.add_node("ServerC")

print("Key1 →", hash_ring.get_node("Key1"))
print("Key2 →", hash_ring.get_node("Key2"))

hash_ring.remove_node("ServerB")
print("After removing ServerB:")
print("Key1 →", hash_ring.get_node("Key1"))
print("Key2 →", hash_ring.get_node("Key2"))

---

🦫 Go: 안정 해시 구현 (with Virtual Nodes)

package main

import (
	"crypto/md5"
	"fmt"
	"sort"
	"strconv"
)

type ConsistentHash struct {
	replicas    int
	keys        []int
	hashMap     map[int]string
	nodeSet     map[string]bool
}

func NewConsistentHash(replicas int) *ConsistentHash {
	return &ConsistentHash{
		replicas: replicas,
		hashMap:  make(map[int]string),
		nodeSet:  make(map[string]bool),
	}
}

func hashKey(key string) int {
	sum := md5.Sum([]byte(key))
	return int((uint32(sum[0])<<24 | uint32(sum[1])<<16 | uint32(sum[2])<<8 | uint32(sum[3])))
}

func (c *ConsistentHash) AddNode(node string) {
	if c.nodeSet[node] {
		return
	}
	c.nodeSet[node] = true
	for i := 0; i < c.replicas; i++ {
		virtualKey := node + "#" + strconv.Itoa(i)
		hash := hashKey(virtualKey)
		c.keys = append(c.keys, hash)
		c.hashMap[hash] = node
	}
	sort.Ints(c.keys)
}

func (c *ConsistentHash) RemoveNode(node string) {
	if !c.nodeSet[node] {
		return
	}
	delete(c.nodeSet, node)
	for i := 0; i < c.replicas; i++ {
		virtualKey := node + "#" + strconv.Itoa(i)
		hash := hashKey(virtualKey)
		delete(c.hashMap, hash)

		for j, h := range c.keys {
			if h == hash {
				c.keys = append(c.keys[:j], c.keys[j+1:]...)
				break
			}
		}
	}
}

func (c *ConsistentHash) GetNode(key string) string {
	if len(c.keys) == 0 {
		return ""
	}
	hash := hashKey(key)
	idx := sort.Search(len(c.keys), func(i int) bool {
		return c.keys[i] >= hash
	})
	if idx == len(c.keys) {
		idx = 0
	}
	return c.hashMap[c.keys[idx]]
}

// 예제 실행
func main() {
	ch := NewConsistentHash(100)
	ch.AddNode("ServerA")
	ch.AddNode("ServerB")
	ch.AddNode("ServerC")

	fmt.Println("Key1 →", ch.GetNode("Key1"))
	fmt.Println("Key2 →", ch.GetNode("Key2"))

	ch.RemoveNode("ServerB")
	fmt.Println("After removing ServerB:")
	fmt.Println("Key1 →", ch.GetNode("Key1"))
	fmt.Println("Key2 →", ch.GetNode("Key2"))
}

---

🚀 Redis 클러스터에서의 해시링 전략

Redis는 일반적인 Consistent Hash Ring 대신, 다음과 같은 방식으로 데이터를 분산

📌 핵심 개념: Hash Slot

• Redis는 총 16,384개의 해시 슬롯(hash slots) 을 제공한다.
• 키는 해시 함수(CRC16(key) % 16384)를 통해 하나의 슬롯에 매핑된다.
• 각 Redis 노드는 해시 슬롯들의 서브셋을 담당한다.

즉, 일반적인 해시링에서의 "서버 인덱스 = hash(key) % N" 대신,

"해시 슬롯 = CRC16(key) % 16384" → 이 슬롯을 담당하는 노드에게 저장.

---

🔢 키 → 슬롯 → 노드 분배 구조

[Key] → [Hash Function] → [Hash Slot] → [Redis Node]

예:

• Key: "user:1234"
• CRC16("user:1234") % 16384 = 5621
• Redis 클러스터에서 슬롯 5000~6000을 담당하는 노드가 이 키를 저장함

---

💡 왜 16384 슬롯인가?

• 2¹⁴ = 16384: 메모리/성능/이식성 간의 밸런스를 고려한 고정 수
• 이 슬롯 수를 기준으로 클러스터의 데이터 분포와 이동을 정밀하게 제어 가능
• 서버를 추가/제거할 때도 해시 슬롯 단위로만 이동하면 되므로 효율적인 리밸런싱 가능

---

🔁 노드 추가/제거 시

Redis는 Consistent Hash Ring처럼 전체 키 재해싱이 필요 없이,

슬롯 단위로 분할 및 이동하기 때문에 안정적인 확장이 가능하다.

예:

• 3개의 노드가 각각 5461개 슬롯을 담당
• 노드를 추가하면 일부 슬롯을 기존 노드에서 새로운 노드로 이동만 하면 됨

---

📦 키 그룹핑: 해시 태그(Hash Tag)

Redis Cluster는 키가 여러 슬롯에 걸쳐 분산되기 때문에, 다중 키 연산(MGET, MSET 등)은 동일한 슬롯에 있는 키에 한해서만 지원돼.

이 문제를 해결하기 위해 Hash Tag 기능이 제공돼:

"user:{1234}:profile"
"user:{1234}:posts"

• 중괄호 {} 안의 부분만 해시 계산에 사용됨
• 이 경우 두 키는 모두 "1234"를 기반으로 같은 슬롯에 배치됨 → 연산 가능

---

🔐 해시 함수: CRC16

Redis는 내부적으로 CRC16 해시 함수를 사용한다.

hash_slot = CRC16(key) % 16384

이 함수는 빠르고 충돌이 적으며, 클러스터 전체에서 균형 있는 슬롯 분포를 달성하는 데 효과적이야.

---

📊 데이터 균등성 & 확장성

기능	설명
슬롯 기반 샤딩	키 해시값이 16384 슬롯에 균등 분포
노드 확장/축소	슬롯 단위로 분할/이동 가능
최소 재배치	새로운 노드에 일부 슬롯만 이동
가상 노드 없이 슬롯으로 분산	복잡도 감소, 속도 향상

---

🛠️ Redis 해시링 전략 vs Consistent Hashing 비교

항목	Redis Hash Slot 방식	일반적인 Consistent Hash Ring
분산 단위	고정된 16384 슬롯	해시 링 전체에서 노드 간 거리 기반
데이터 이동	슬롯 단위로 재배치 (정밀 제어)	해시값 기준 인접 구간 전체 재배치
구현 복잡도	상대적으로 단순	가상 노드/표준편차 조절 등 고려 필요
다중 키 연산	동일 슬롯 키만 가능 (해시 태그 필요)	일반적으로 불가능, 추가 구현 필요

---

📚 요약

항목	설명
해시 방식	CRC16(key) % 16384 → 해시 슬롯
데이터 분산	슬롯 단위로 분산, 각 노드가 일부 슬롯 담당
확장/축소	슬롯 단위 이동으로 안정성 유지
해시 태그	연관 키를 같은 슬롯에 그룹핑
가상 노드 없음	슬롯으로 역할 대체함

---

✍️ 실무 팁

• Redis Cluster 사용할 땐, 키 이름에 해시 태그({})를 활용해 다중 키 연산 문제 방지
• Redis 클러스터의 슬롯 이동 명령어 (CLUSTER SETSLOT, CLUSTER ADDSLOTS) 등을 통해 리밸런싱을 수동 제어할 수 있음
• 클러스터 스케일업/스케일다운 시 슬롯 재분배는 서비스 영향 최소화함

---

🧑‍💻 코드 구현 예시

• Redis Cluster에서 key → 해시 슬롯 → 노드로 분산되는 흐름을 코드로 보여주기
• Redis의 CRC16 해시 함수 사용, 16384 슬롯 사용, 그리고 슬롯 → 노드 매핑 방식을 구현
• Python과 Go에서 각각 Key → Slot → Node를 추적하는 샘플 작성

---

🧪 가정

• Redis 노드 3개: "NodeA", "NodeB", "NodeC"
• 슬롯 분배:
  • NodeA: 슬롯 0 ~ 5460
  • NodeB: 슬롯 5461 ~ 10922
  • NodeC: 슬롯 10923 ~ 16383

---

🐍 Python 예시

import crcmod

# Redis의 CRC16 해시 함수와 동일한 것 사용
crc16 = crcmod.predefined.mkPredefinedCrcFun('crc-aug-ccitt')

# 슬롯 → 노드 매핑
slot_ranges = {
    "NodeA": range(0, 5461),
    "NodeB": range(5461, 10923),
    "NodeC": range(10923, 16384)
}

def get_slot(key: str) -> int:
    # Redis Cluster에서 키에 {}가 있으면 그 부분만 해싱
    if '{' in key and '}' in key:
        start = key.index('{') + 1
        end = key.index('}')
        key = key[start:end]
    return crc16(key.encode()) % 16384

def get_node_for_key(key: str) -> str:
    slot = get_slot(key)
    for node, slots in slot_ranges.items():
        if slot in slots:
            return f"{key} → slot {slot} → {node}"
    return f"{key} → slot {slot} → Unknown"

# 테스트
keys = ["user:1000", "order:42", "product:{123}", "product:{124}"]
for k in keys:
    print(get_node_for_key(k))

출력 예시:

user:1000 → slot 5793 → NodeB
order:42 → slot 10927 → NodeC
product:{123} → slot 14113 → NodeC
product:{124} → slot 2853 → NodeA

---

🦫 Go 예시

package main

import (
	"fmt"
	"github.com/snksoft/crc"
)

var slotRanges = map[string][2]int{
	"NodeA": {0, 5460},
	"NodeB": {5461, 10922},
	"NodeC": {10923, 16383},
}

func getHashSlot(key string) int {
	// 해시 태그 처리: {tag}
	start := -1
	end := -1
	for i := 0; i < len(key); i++ {
		if key[i] == '{' && start == -1 {
			start = i
		} else if key[i] == '}' && start != -1 {
			end = i
			break
		}
	}
	if start != -1 && end != -1 {
		key = key[start+1 : end]
	}
	crc16 := crc.Calculator(crc.CRC16_XMODEM)
	hash := crc16.Checksum([]byte(key))
	return int(hash % 16384)
}

func getNodeForKey(key string) string {
	slot := getHashSlot(key)
	for node, rng := range slotRanges {
		if slot >= rng[0] && slot <= rng[1] {
			return fmt.Sprintf("%s → slot %d → %s", key, slot, node)
		}
	}
	return fmt.Sprintf("%s → slot %d → Unknown", key, slot)
}

func main() {
	keys := []string{"user:1000", "order:42", "product:{123}", "product:{124}"}
	for _, key := range keys {
		fmt.Println(getNodeForKey(key))
	}
}

Go에서는 github.com/snksoft/crc 패키지를 사용해서 Redis와 동일한 CRC16-XMODEM 해시를 계산했어.

go.mod에 다음 의존성을 추가해야 해:

go get github.com/snksoft/crc

---

✅ 결과적으로 이 코드는 다음을 시뮬레이션 해줌

• Redis가 키를 어떤 슬롯에 배정하는지 (CRC16 해시 기반)
• 어떤 노드가 해당 슬롯을 담당하고 있는지
• 해시 태그({})를 통해 다중 키가 같은 슬롯에 매핑되는 방식

---