3. Records Organization Bucket
01. Pattern Overview
Bucket 패턴은 고카디널리티(high-cardinality) 컬럼에 대해 데이터 접근을 최적화하는 패턴.
- 수평 파티셔닝은 low-cardinality에만 적합
- Bucket은 이 문제를 modular hashing으로
핵심 공식:
bucket_number = hash(key) % num_buckets예를 들어 50개 버킷을 설정하면, 수백만 개의 user_id가 50개 그룹으로 분배됨.
같은 user_id는 항상 같은 버킷에 들어가지만, 하나의 버킷에는 여러 다른 user_id가 함께 저장
02. 최적화 효과
Bucket Pruning: 버킷 컬럼이 WHERE 조건에 사용되면, 쿼리 엔진이 해싱 알고리즘으로 해당 키가 속한 버킷을 즉시 알 수 있다. 나머지 49개 버킷은 아예 읽지 않는다.
# user_id = 'abc123' → hash('abc123') % 50 = 7# → 버킷 7만 읽으면 됨, 나머지 49개 스킵spark.sql("SELECT * FROM visits WHERE user_id = 'abc123'")Shuffle 제거: 두 테이블이 동일한 버킷 설정(같은 컬럼, 같은 버킷 수)으로 구성되어 있으면, JOIN 시 네트워크를 통한 데이터 교환(shuffle)이 불필요. 같은 버킷 번호끼리 로컬에서 바로 결합가능
Table A - bucket 0: [user A, B, X] Table B - bucket 0: [user A, B, X]Table A - bucket 1: [user E, F] → Table B - bucket 1: [user E, F]Table A - bucket 2: [user L, M] Table B - bucket 2: [user L, M]
→ 각 버킷끼리 로컬 JOIN → shuffle 없음이 최적화가 동작하려면 양쪽 테이블의 bucket column과 bucket 수가 동일해야 함
Consequences
Mutability: 버킷 스키마(컬럼, 버킷 수)는 사실상 불변. 변경하려면 전체 데이터를 다시 써야 함(backfill).
Bucket Size 결정의 어려움:
- 현재 데이터 볼륨에 맞추면 미래에 버킷이 너무 커지고, 미래를 예측해서 크게 잡으면 현재 불필요한 빈 버킷이 많아진다.
- 현재 볼륨 기준으로 적절히 설정하고, 필요시 backfill을 감수하는 것이 현실적
Spark bucketBy
from pyspark.sql import SparkSession
spark = SparkSession.builder.getOrCreate()
input_dataset = spark.read.format("delta").load("/data/visits")
# user_id 기준 50개 버킷으로 저장# saveAsTable: 버켓팅은 Hive metastore 테이블로 저장해야 함input_dataset.write \ .bucketBy(50, "user_id") \ .saveAsTable("visits_bucketed")주의: bucketBy는 save()가 아니라 **saveAsTable()**과 함께 사용해야 한다. 버킷 메타데이터가 Hive metastore에 저장되어야 쿼리 엔진이 pruning과 shuffle 제거를 적용할 수 있기 때문이다.
Bucket + Horizontal Partition 조합
파티션이 1차 필터(coarse-grained), 버킷이 2차 필터(fine-grained) 역할
# 날짜로 파티셔닝 + user_id로 버켓팅input_dataset.write \ .partitionBy("event_date") \ .bucketBy(50, "user_id") \ .saveAsTable("visits_partitioned_bucketed")쿼리 WHERE event_date = '2024-01-01' AND user_id = 'abc123'이 실행되면:
- 파티션 pruning으로
event_date = '2024-01-01'파티션만 선택 - 버킷 pruning으로 해당 파티션 내 user_id가 속한 버킷만 선택
Bucket vs Partition 선택 기준
| 기준 | Partition | Bucket |
|---|---|---|
| 카디널리티 | 낮음 (날짜, 국가) | 높음 (user_id, device_id) |
| 물리적 구조 | 디렉토리/파티션 분리 | 같은 위치 내 파일 분리 |
| 주요 최적화 | partition pruning | bucket pruning + shuffle 제거 |
| 변경 비용 | 매우 높음 | 매우 높음 (backfill 필요) |
Concept
- Bucket : 고카디널리티 컬럼에 대해 modular hashing으로 레코드를 고정된 수의 그룹(버킷)에 분배하여 저장하는 패턴
- Modular Hashing :
hash(key) % num_buckets공식으로 각 키가 속할 버킷 번호를 결정하는 알고리즘 - Bucket Pruning : 쿼리 조건의 키를 해싱하여 해당 버킷만 읽고 나머지를 건너뛰는 최적화
- Shuffle 제거 : 동일 버킷 설정의 두 테이블을 JOIN할 때 네트워크 데이터 교환 없이 로컬에서 결합하는 최적화
- saveAsTable vs save : Spark에서 버킷 메타데이터는 Hive metastore에 저장되므로 saveAsTable을 사용해야 함
- Backfill : 버킷 스키마 변경 시 전체 데이터를 새 설정으로 다시 쓰는 작업
- High-cardinality : 고유 값이 매우 많은 속성 (예: user_id). 파티셔닝 부적합, 버켓팅 적합
추가학습
Consistent Hashing
일반 Modular Hashing의 문제
hash(key) % N방식은 N(버킷 수)이 바뀌면 거의 모든 키의 위치가 바뀐다.
# 버킷 3개일 때hash("user_A") % 3 = 1hash("user_B") % 3 = 2hash("user_C") % 3 = 0
# 버킷 4개로 변경hash("user_A") % 4 = 3 ← 위치 변경hash("user_B") % 4 = 0 ← 위치 변경hash("user_C") % 4 = 2 ← 위치 변경- 3개에서 4개로 1개만 추가했는데 3개 키 전부 재배치 필요.
- 대규모 분산 시스템에서 이건 전체 데이터 마이그레이션을 의미
Consistent Hashing 핵심
Consistent Hashing은 **해시 링(hash ring)**이라는 원형 공간 사용.
- 0 ~ 2³² 범위의 원형 공간(링)을 만든다
- 각 **노드(서버/버킷)**를 해시 함수로 링 위에 배치한다
- 각 키도 같은 해시 함수로 링 위에 배치한다
- 키는 시계 방향으로 가장 가까운 노드에 할당된다
Node A (hash=100) ↑ ------●------ / \ / key X \ ● (hash=80) ● Node B (hash=200) | → Node A에 할당 | | | \ / \ ● / ------●------ Node C (hash=300)노드 추가/제거 시 영향 범위 최소화
핵심은 노드가 추가되거나 제거될 때 영향받는 키가 최소화된다는 것
# Node D (hash=150)를 추가하면# 영향받는 범위: Node A(100) ~ Node D(150) 사이의 키만# 나머지 키들은 전혀 이동하지 않음
Before: key(hash=120) → Node B(200) (A 다음으로 가장 가까운 노드)After: key(hash=120) → Node D(150) (새로 추가된 더 가까운 노드)
# hash=200~300 사이 키들은 여전히 Node C로 감 → 영향 없음일반 modular hashing에서는 노드 1개 추가 시 거의 모든 키가 재배치되지만, consistent hashing에서는 평균 K/N개 (K=전체 키 수, N=노드 수)만 이동
Virtual Node (vnode)
실제 구현에서는 물리 노드 하나당 **여러 개의 가상 노드(virtual node)**를 링에 배치.
균등 분배: 노드가 3개뿐이면 링 위에 3개 점만 찍히므로 키 분배가 불균등해질 수 있다. 노드당 100~200개의 vnode를 만들면 링 위에 골고루 분포되어 균등 분배가 가능
이기종 노드 대응: 성능이 좋은 서버에는 vnode를 더 많이 할당하여 더 많은 키를 처리하게 할 수 있음
# 물리 노드 3개, 각각 vnode 4개씩Node A → vnode_A1(hash=50), vnode_A2(hash=180), vnode_A3(hash=290), vnode_A4(hash=350)Node B → vnode_B1(hash=80), vnode_B2(hash=150), vnode_B3(hash=260), vnode_B4(hash=330)Node C → vnode_C1(hash=110), vnode_C2(hash=200), vnode_C3(hash=310), vnode_C4(hash=370)
# 링 위에 12개 점이 골고루 분포 → 균등한 키 분배Redis에서의 Consistent Hashing
Redis Cluster는 consistent hashing을 약간 변형한 hash slot 방식을 사용
# Redis Cluster: 16384개 고정 hash slotslot = CRC16(key) % 16384
# 각 노드가 slot 범위를 담당Node A: slot 0 ~ 5460Node B: slot 5461 ~ 10922Node C: slot 10923 ~ 16383순수 consistent hashing과의 차이점은:
- **고정된 slot 수(16384개)**를 사용한다. 링 위에 동적으로 해시하는 게 아니라 slot 단위로 할당한다.
- 노드 추가 시 기존 노드에서 **slot 범위를 이전(reshard)**하는 방식이다
- 이 방식이 구현이 더 단순하고 예측 가능하다
# Node D 추가 시 각 노드에서 slot 일부를 이전Node A: slot 0 ~ 4095 (5461개 → 4096개)Node B: slot 4096 ~ 8191 (5462개 → 4096개)Node C: slot 8192 ~ 12287 (5461개 → 4096개)Node D: slot 12288 ~ 16383 (새로 할당)