5. 샤드 라우팅의 mod-N 리해시 폭풍과 핫키 쏠림 (그리고 동시 변경 레이스)

난이도 최상

내 리뷰 · C#

내 리뷰 · C++

해설 · C#

해설 — 샤드 라우팅의 mod-N 리해시 폭풍과 핫키 쏠림 (그리고 동시 변경 레이스)

난이도: 최상

요약

Route 는 hash(key) % nodeCount(A)로 담당 샤드를 정한다. 이 방식은 세 층위로 깨진다. (1) 리해시 폭풍: 노드 수 n 이 바뀌면(B) % n 의 분모가 달라져 거의 모든 키의 매핑이 동시에 바뀐다(평균적으로 약 1/n 만 제자리). 샤드 1대 증설/장애가 월드 전체의 대규모 엔티티 이전·캐시 무효화·일시 정합성 붕괴를 유발한다. (2) 핫키 쏠림: 매핑이 키에 대해 결정적이라 인기 보스/채널 소수 키는 항상 같은 샤드로 가 그 샤드만 과부하된다 — 샤드를 늘려도 그 키의 부하는 한 샤드에 그대로 남는다. (3) 동시 변경 레이스: List<ShardNode> 를 락 없이 Route(읽기)와 OnNodeAdded/Removed(쓰기)가 동시 접근 → 자료구조 손상/인덱스 범위 밖 접근/n==0 나눗셈 예외.

문제점

1. (리해시 폭풍) mod-N 의 재배치 비율 — (A)(B)

증상: n: 4 → 5 로 바뀌면 키의 약 80%가 다른 샤드로 재매핑. 엔티티 상태 이전, 세션 재바인딩, 캐시 대량 미스가 동시에 폭발.
재현조건: 트래픽 급증 시점에 증설/장애로 노드 수 변경. 가장 필요할 때 가장 크게 흔들린다.
근본원인: 분모가 노드 수인 해시. 노드 집합 변화에 대한 매핑 안정성이 전혀 없다.

2. (핫스팟) 결정적 매핑의 인기 키 집중 — (A)

증상: 소수 핫키가 한 샤드에 고정 → 그 샤드 CPU/대역 포화, 나머지는 한가. 전체 증설로도 해소 안 됨(그 키의 분모가 1).
근본원인: 키 단위 단일 귀속. 핫키를 분산/복제하는 장치가 없다.

3. (불균형) GetHashCode 분포 + mod

long.GetHashCode()(상·하위 워드 XOR) 분포가 고르지 않으면 % n 결과가 편향돼 샤드 간 부하가 처음부터 불균등.

4. (데이터 레이스) 노드 목록 무동기 동시 접근 — (A read)(B write)

증상: Route 가 _nodes 를 읽는 동안 Add/Remove 가 구조를 바꾸면 List<T> 는 스레드 안전이 아니라 손상·예외. 제거 직후 Count 와 인덱싱 사이 경합으로 범위 밖 접근, 마지막 노드 제거 시 % 0.
근본원인: 공유 가변 컬렉션에 동기화·불변 스냅샷 교체가 없다.

수정안

일관성 해시(consistent hashing) + 가상 노드로 매핑 안정성을 확보하고, 핫키는 분산/복제하며, 노드 집합은 불변 스냅샷으로 원자 교체한다.

public sealed class ConsistentHashRing
{
    // 불변 스냅샷: 정렬된 (해시 -> 노드) 링. 교체는 통째로.
    private volatile Entry[] _ring = System.Array.Empty<Entry>();
    private readonly int _vnodes = 200;   // 노드당 가상 노드(부하 평탄화)

    public ShardNode Route(long key)
    {
        var ring = _ring;                              // 원자 스냅샷 읽기
        if (ring.Length == 0) throw new System.InvalidOperationException("no shards");
        uint h = Hash(key);
        int i = LowerBound(ring, h);                   // 시계방향 첫 가상노드
        return ring[i == ring.Length ? 0 : i].Node;
    }

    public void Rebuild(IReadOnlyList<ShardNode> nodes) // 증감 시 새 링을 만들어 교체
    {
        var list = new List<Entry>(nodes.Count * _vnodes);
        foreach (var nd in nodes)
            for (int v = 0; v < _vnodes; v++)
                list.Add(new Entry(Hash2(nd.Id, v), nd));
        list.Sort((a, b) => a.H.CompareTo(b.H));
        _ring = list.ToArray();                        // volatile 쓰기로 원자 교체
    }
    // ... Hash/Hash2/LowerBound/Entry 생략 ...
}

일관성 해시에서 노드 1개 증감 시 재배치되는 키는 평균 K/n 뿐(전체가 아니라). 리해시 폭풍 제거.
가상 노드로 샤드 간 부하를 평탄화(분포 편향 완화).
노드 집합은 새 링을 만들어 volatile 참조로 통째 교체 → reader 는 일관된 스냅샷만 본다(락 최소화).
핫키 전용 대책: 인기 키는 (a) 여러 샤드에 복제해 읽기를 분산, (b) 키를 서브키로 쪼개(bossId#shardSalt) 여러 슬롯에 흩뿌리기, (c) bounded-load consistent hashing 으로 과부하 샤드의 키를 다음 샤드로 흘리기.

더 나은 설계

매핑 변경 시 점진적 이전(키 워밍/더블 라이트/리다이렉트) 으로 컷오버를 부드럽게. 한 번에 전 키를 옮기지 않는다.
핫키는 별도 정책(전용 샤드·복제·로컬 캐시)으로 분리해 일반 샤딩과 다르게 다룬다.
라우팅 테이블은 버전 있는 불변 스냅샷으로 배포하고, 모든 게이트웨이가 같은 버전을 보도록 전파.

면접 포인트

hash % N 샤딩의 치명적 약점은 N 변화 시 거의 전 키 재배치다. 일관성 해시(+가상 노드) 로 재배치를 1/N 로 줄인다.
결정적 키 라우팅은 핫키를 한 샤드에 고정시킨다 — 복제·서브키 분할·bounded-load 로 따로 분산해야 한다.
운영 중 바뀌는 라우팅 테이블은 불변 스냅샷의 원자 교체로 공유해 reader 경합과 %0 같은 경계 버그를 없앤다.

해설 · C++

해설 — 샤드 라우팅의 mod-N 리해시 폭풍과 핫키 쏠림 (그리고 동시 변경 레이스)

난이도: 최상

요약

route 는 hash(key) % nodeCount(A)로 담당 샤드를 정한다. 세 층위로 깨진다. (1) 리해시 폭풍: 노드 수 n 이 바뀌면(B) 분모가 달라져 거의 모든 키 매핑이 동시에 변한다(평균 약 1/n 만 유지). 샤드 1대 증감이 월드 전체의 대량 엔티티 이전·캐시 무효화·일시 정합성 붕괴를 부른다. (2) 핫키 쏠림: 매핑이 키에 결정적이라 인기 보스/채널 소수 키가 항상 같은 샤드로 가 그 샤드만 과부하 — 증설해도 그 키 부하는 그대로. (3) 데이터 레이스/UB: std::vector 를 락 없이 route(읽기)와 addNode/removeNode(쓰기/재할당)가 동시 접근 → 반복자/포인터 무효화, 범위 밖 접근, 마지막 노드 제거 시 % 0(UB).

문제점

1. (리해시 폭풍) mod-N 재배치 비율 — (A)(B)

증상: n: 4→5 면 키의 약 80%가 다른 샤드로 재매핑. 상태 이전·세션 재바인딩·캐시 미스가 한꺼번에 폭발.
재현조건: 트래픽 급증 시점의 증설/장애. 가장 필요할 때 가장 크게 흔들린다.
근본원인: 분모가 노드 수인 해시 — 노드 집합 변화에 대한 매핑 안정성 부재.

2. (핫스팟) 결정적 매핑의 인기 키 집중 — (A)

소수 핫키가 한 샤드에 고정되어 그 샤드만 포화. 전체 증설로 해소 불가(그 키의 분모가 1).

3. (불균형) 해시 분포 + mod

std::hash<int64_t> 가 구현에 따라 항등(identity)에 가까우면 % n 결과가 키 패턴에 편향돼 처음부터 불균등.

4. (데이터 레이스 / UB) 노드 벡터 무동기 — (A read)(B write)

route 가 nodes_ 를 인덱싱하는 동안 push_back(재할당)/erase 가 일어나면 댕글링·무효 인덱스·%0. 표준상 UB.

수정안

일관성 해시 + 가상 노드로 매핑을 안정화하고, 노드 집합은 불변 스냅샷을 원자 교체하며, 핫키는 따로 분산한다.

#include <atomic>
#include <memory>
#include <map>

struct Ring {                         // 불변 스냅샷
    std::map<uint64_t, ShardNode> circle;   // 가상노드 해시 -> 샤드
};

class ConsistentHashRouter {
public:
    // route: 현재 스냅샷을 원자적으로 읽어 시계방향 첫 노드 반환
    ShardNode route(int64_t key) const {
        auto ring = std::atomic_load(&ring_);          // shared_ptr 원자 로드
        if (!ring || ring->circle.empty()) throw std::runtime_error("no shards");
        uint64_t h = hash(key);
        auto it = ring->circle.lower_bound(h);
        if (it == ring->circle.end()) it = ring->circle.begin();
        return it->second;
    }

    // 증감 시 새 링을 만들어 통째 교체 (vnode 로 부하 평탄화)
    void rebuild(const std::vector<ShardNode>& nodes, int vnodes = 200) {
        auto ring = std::make_shared<Ring>();
        for (auto& nd : nodes)
            for (int v = 0; v < vnodes; ++v)
                ring->circle.emplace(hash2(nd.id, v), nd);
        std::atomic_store(&ring_, ring);               // 원자 교체
    }
private:
    static uint64_t hash(int64_t);
    static uint64_t hash2(const std::string&, int);
    std::shared_ptr<Ring> ring_;                       // atomic_load/store 로 접근
};

일관성 해시에서 노드 1개 증감 시 재배치 키는 평균 K/n 뿐 — 리해시 폭풍 제거.
가상 노드로 분포 편향 완화. 노드 집합은 shared_ptr 스냅샷을 atomic_store 로 교체해 reader 가 일관된 한 벌만 본다(락 최소).
핫키 대책: 인기 키 복제(읽기 분산), 서브키 분할(bossId#salt), bounded-load consistent hashing 으로 과부하 샤드의 키를 다음 노드로 흘리기.

더 나은 설계

매핑 변경 시 점진적 이전(워밍/더블 라이트/리다이렉트)으로 컷오버를 부드럽게.
핫키는 전용 샤드·복제·로컬 캐시로 일반 샤딩과 분리.
라우팅 테이블은 버전 있는 불변 스냅샷으로 모든 게이트웨이에 같은 버전 전파.

면접 포인트

hash % N 의 치명적 약점은 N 변화 시 거의 전 키 재배치 — 일관성 해시(+가상 노드)로 1/N 수준으로 줄인다.
결정적 키 라우팅은 핫키를 한 샤드에 고정한다 — 복제/서브키 분할/bounded-load 로 별도 분산.
운영 중 바뀌는 공유 라우팅 테이블은 불변 스냅샷의 원자 교체(atomic_load/store on shared_ptr)로 reader 경합과 %0 경계 버그를 함께 없앤다.

← 문제로 돌아가기