[CS300 #136] 샤딩과 파티셔닝 — 데이터를 나눠 담는 기준

컴퓨터공학 300 주제 시리즈의 136번째 글이다. 전체 지도는 여기.

한 줄 요약

파티셔닝은 큰 데이터를 키 기준으로 여러 조각으로 나누는 일이고, 그 조각을 서로 다른 기계에 흩어 두는 것을 흔히 샤딩이라 부른다. 복제가 “같은 데이터를 여러 곳에” 라면 샤딩은 “다른 데이터를 여러 곳에” 다. 무엇을 기준으로 나누느냐가 성능과 운영 난이도를 결정한다.

왜 필요한가

복제로 읽기는 늘릴 수 있다. 하지만 쓰기는 여전히 리더 하나가 다 받고, 데이터 전체가 각 복제본에 다 들어가야 한다. 데이터가 한 기계의 디스크보다 커지거나, 쓰기가 한 기계가 감당할 수 있는 양을 넘으면 복제로는 해결되지 않는다.

이때 데이터를 나눈다. 사용자 1억 명을 100개 샤드에 나누면 샤드 하나는 100만 명분만 갖고, 쓰기도 100곳으로 흩어진다. 수평 확장(scale-out)의 핵심 기법이다.

대가도 분명하다. 여러 샤드에 걸친 쿼리와 트랜잭션이 어려워지고, 샤드를 늘릴 때 데이터를 옮겨야 하며, 한 샤드에 부하가 몰리는 핫스팟이 생길 수 있다.

핵심 개념

용어 정리

수직 파티셔닝: 열(컬럼)을 나눈다. 자주 쓰는 컬럼과 큰 BLOB 컬럼을 다른 테이블로.
수평 파티셔닝: 행을 나눈다. 이 글의 주제다.
샤드/파티션: 나뉜 한 조각. 제품마다 부르는 이름이 다르다(MongoDB 샤드, Cassandra·DynamoDB 파티션, Elasticsearch 샤드, Kafka 파티션).
파티션 키(샤드 키): 어느 조각으로 갈지 정하는 값.

나누는 방법

방법	규칙	장점	단점
범위(range)	키 구간별로 (A~F, G~M …)	범위 조회가 한 샤드에서 끝난다	순차 키(시간, 자동 증가 ID)면 최신 샤드에 쓰기가 몰린다
해시(hash)	hash(key) 로 결정	고르게 분산된다	범위 조회가 모든 샤드로 퍼진다
목록(list)	값 목록으로 (지역=KR → 샤드1)	업무 규칙과 맞추기 쉽다	값마다 크기가 달라 불균형
디렉터리	별도 조회표로 매핑	유연한 재배치	조회표가 단일 장애점·병목

모듈로 해싱의 함정

가장 쉬운 방법은 shard = hash(key) % N 이다. 문제는 N 이 바뀔 때다. 4개에서 5개로 늘리면 키 대부분의 나머지가 바뀐다. 거의 모든 데이터를 옮겨야 한다.

일관된 해싱 (Consistent Hashing)

카거(David Karger) 등이 1997년 웹 캐시 분산을 위해 제안했다. 해시 공간을 원(링)으로 보고, 노드도 키도 원 위의 점에 놓는다. 키는 시계 방향으로 처음 만나는 노드에 속한다.

           n0
        ●       ●  k1 → n1
    n3 ●           ● n1
        ●       ●
           n2        k2 → n2

노드 하나를 추가하면 그 노드 바로 앞 구간의 키만 새 노드로 옮겨진다. 평균 K/N 개만 움직인다. 노드마다 원 위에 여러 점(가상 노드, vnode)을 찍으면 분포가 고르게 되고, 노드가 빠질 때 부하가 여러 노드로 나뉘어 넘어간다. Dynamo, Cassandra 가 이 방식을 쓴다.

고정 개수 파티션

다른 실용적 방법은 처음부터 파티션을 노드 수보다 훨씬 많이(예: 노드 10대에 파티션 1000개) 만들어 두고, 노드가 늘면 파티션 단위로 통째로 옮기는 것이다. 키→파티션 매핑은 영원히 고정되고, 파티션→노드 매핑만 바뀐다. Elasticsearch 의 프라이머리 샤드 수, Redis Cluster 의 16384 해시 슬롯, Kafka 의 파티션이 이런 구조다.

핫스팟과 샤드 키 설계

샤드 키가 나쁘면 고르게 나눠도 소용없다.

유명인 계정 하나에 요청이 몰리면 그 키가 있는 샤드만 탄다. 키에 무작위 접미사를 붙여 쪼개고 읽을 때 합치는 기법을 쓴다.
타임스탬프를 범위 키로 쓰면 “지금” 샤드에만 쓰기가 몰린다.
자주 함께 조회하는 데이터는 같은 샤드에 있게 한다(예: 주문과 주문 항목을 고객 ID 로 샤딩).

샤딩의 비용

샤드 간 쿼리: 조건에 샤드 키가 없으면 모든 샤드에 물어보고 합쳐야 한다(scatter-gather).
샤드 간 트랜잭션: 다음 글의 2PC 나 사가가 필요하다.
보조 인덱스: 샤드마다 지역 인덱스를 두면 읽기가 흩어지고, 전역 인덱스를 두면 쓰기가 여러 샤드를 건드린다.
재분배: 데이터 이동 중의 부하와 일관성.

한 기계 안의 파티셔닝

샤딩은 기계를 나누지만, 파티셔닝은 한 데이터베이스 안에서도 유용하다. PostgreSQL 의 선언적 파티셔닝은 큰 테이블을 범위·목록·해시로 나눠, 조건에 맞는 파티션만 읽는 파티션 프루닝과 오래된 파티션을 통째로 떼어 내는 빠른 삭제를 가능하게 한다. 로그·이벤트처럼 시간으로 쌓이는 테이블에서 특히 효과가 크다.

직접 해 보기

키 10만 개를 4개 샤드에서 5개로 늘릴 때, 모듈로 해싱과 일관된 해싱(가상 노드 100개)이 각각 몇 %의 키를 옮기는지 잰다.

import bisect, hashlib
from collections import Counter

def h(s):
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")

keys = [f"user:{i}" for i in range(100_000)]

# 1) 해시 모듈로: shard = hash(key) % N
def mod_shard(k, n): return h(k) % n
moved = sum(mod_shard(k, 4) != mod_shard(k, 5) for k in keys)
print(f"모듈로 해싱   4→5 샤드: {moved/len(keys):5.1%} 이동")

# 2) 일관된 해싱 (노드마다 가상 노드 vnodes 개)
class Ring:
    def __init__(self, nodes, vnodes=100):
        self.points = sorted((h(f"{n}#{v}"), n) for n in nodes for v in range(vnodes))
        self.hashes = [p for p, _ in self.points]
    def node(self, k):
        i = bisect.bisect(self.hashes, h(k)) % len(self.points)
        return self.points[i][1]

r4, r5 = Ring(["n0", "n1", "n2", "n3"]), Ring(["n0", "n1", "n2", "n3", "n4"])
moved = sum(r4.node(k) != r5.node(k) for k in keys)
print(f"일관된 해싱 4→5 노드: {moved/len(keys):5.1%} 이동 (이상적 값 20%)")
load = Counter(r5.node(k) for k in keys)
print("노드별 키 수:", dict(sorted(load.items())))

모듈로 해싱   4→5 샤드: 79.9% 이동
일관된 해싱 4→5 노드: 21.5% 이동 (이상적 값 20%)
노드별 키 수: {'n0': 20188, 'n1': 18475, 'n2': 19078, 'n3': 20773, 'n4': 21486}

모듈로 방식은 80% 를 옮긴다. 새 노드 하나를 위해 데이터 대부분이 이사한다. 일관된 해싱은 새 노드의 몫(1/5 = 20%) 근처만 옮긴다. 노드별 분포도 고르다. vnodes=1 로 바꿔 돌리면 분포가 크게 치우치는 것을 볼 수 있다. 가상 노드가 왜 필요한지 보여 준다.

현업에서는

PostgreSQL 시간 파티셔닝. 로그성 테이블을 월별 파티션으로 나누고, 보존 기간이 지난 파티션은 DETACH 후 DROP 한다. 수억 행 DELETE 보다 훨씬 빠르고 테이블 팽창도 없다.
Kafka 파티션 수. 파티션 수는 소비자 병렬성의 상한이다. 같은 키의 메시지는 같은 파티션으로 가서 순서가 보장된다. 파티션을 나중에 늘리면 키→파티션 매핑이 바뀌어 키별 순서 보장이 깨질 수 있으므로 처음에 넉넉히 잡는 편이다.
Elasticsearch. 인덱스의 프라이머리 샤드 수는 생성 후 바로 바꿀 수 없어서(split·shrink·reindex 필요) 초기 설계가 중요하다. 샤드가 너무 많으면 클러스터 상태 관리 비용이, 너무 적으면 샤드가 커져 복구가 느려진다.
애플리케이션 샤딩. 데이터베이스가 샤딩을 지원하지 않으면 애플리케이션이 샤드 키로 연결할 DB 를 고른다. 이때 샤드 키 없는 관리자용 조회가 모든 샤드를 훑게 되는 점을 미리 설계에 반영한다.

확인 문제

복제와 샤딩이 각각 해결하는 문제는?
자동 증가 ID 를 범위 샤딩의 키로 쓰면 어떤 문제가 생기는가?
노드 4대에서 5대로 늘릴 때 모듈로 해싱이 대부분의 키를 옮기는 이유는?
가상 노드를 쓰는 이유 두 가지는?
Kafka 에서 파티션 수를 나중에 늘릴 때 주의할 점은?

풀이

복제는 내구성·가용성·읽기 확장을, 샤딩은 데이터 크기와 쓰기 처리량의 확장을 해결한다.
새 데이터가 항상 마지막 범위에 들어가 마지막 샤드 하나에 쓰기가 몰린다(핫스팟).
hash % 4 와 hash % 5 는 대부분의 값에서 다르므로, 키 대부분의 샤드가 바뀐다.
노드별 데이터 분포를 고르게 하고, 노드가 빠지거나 들어올 때 이동 부하를 여러 노드에 나누기 위해서다.
키→파티션 매핑이 바뀌어 같은 키의 메시지가 다른 파티션으로 가므로 키별 순서 보장이 깨질 수 있다.