"대규모 시스템 설계" 책 스터디 중
트위터의 Snowflake 관련 내용을 보완하기 위해 서칭하다가 찾게 된 내용입니다
트위터 기술 블로그 내용 중 "대규모 시스템 설계"와 관련있고, 제가 관심있는 부분을 정리하였습니다 (참고: 2010년 6월 1일 작성)제 포스팅을 읽는 다른 분들에게도 도움이 되는 내용이기를 바랍니다.
1. 트위터의 Snowflake 방식
1-1. 트위터의 데이터 저장소
- MySQL 기반
- 단일 소규모 DB 인스턴스 → 이후 단일 대규모 DB 인스턴스로 확장 → 대규모 DB 클러스터로 분산
- 시스템 다수를 Cassandra나 MySQL 샤딩으로 교체
- 참고: Cassandra는 내장 전역 유일키 생성기가 없어 별도 솔루션이 필요
1-2. 분산 유일키 생성에 대한 트위터의 요구사항
- 고가용성, 초당 수만 건 생성, 로컬 O(1)에 가까운 지연 → 비조정(uncoordinated) 방식 지향
- 대체로 시간 정렬(K-sorted) 지원
- 64 bit
- 트위터는 이미 트윗 ID 저장용 비트 수를 늘리는 고통스러운 과정을 겪은 바 있음- 비트 확장 이슈 재발 방지(광범위한 코드 영향 최소화)
2. 고려했던 선택지
| 방식 | 유일성 | 정렬성 | 지연/성능 | 가용성/운영 | 비고 |
|---|---|---|---|---|---|
| MySQL 티켓서버(플리커) | 좋음 | 순서 보장 가능 | DB I/O 병목 | DB 의존 | 재동기화/장애 시 복잡 |
| UUID(v4 등) | 확률적 유일 | 없음 | 로컬 생성 O(1) | 좋음 | 128비트(인덱스 비우호) |
| ZK 순차 노드 | 전역 순서 | 강함 | 조정 비용↑ | ZK 의존↑ | 지연/가용성 트레이드오프 |
| Snowflake | 구성적 유일 | K-sorted | 로컬 O(1) | ZK는 워커ID 임차만 | 선택 |
- MySQL 기반 티켓 서버(플리커 방식)
- 별도의 재동기화 루틴을 구축하지 않고서는 필요한 순서 보장을 제공하지 못함 - 다양한 UUID 방식
- 발견한 모든 방식은 128비트가 필요했음 - Zookeeper 순차 노드
- 트위터는 로컬 계산을 통한 낮은 지연·높은 가용성을 원했기 때문에, 전역 순서를 위해 조정이 필요한 ZK 순차 노드는 배제
3. 해결책(Snowflake)
- ID =
⟨시간⟩ ⊕ ⟨데이터센터⟩ ⊕ ⟨워커⟩ ⊕ ⟨시퀀스⟩의 조합 채택 - 시퀀스 번호: 워커(프로세스) 단위로 할당, 동일 ms 내 0..4095 증가(스레드 간 동기화로 공유)
- 워커 번호: 시작 시 Zookeeper를 통해 선택됨(구성 파일을 통해 재정의 가능)
4. Twitter Snowflake의 구현 포인트
4-1. 비트 구성
- 각 필드는 충돌 공간을 분할하는 네임스페이스
- 시간 41bits, DC 5bits, 워커 5bits, 시퀀스 12bits → 설계적으로 충돌 배제
시간(41b) | DC(5b) | 워커(5b) | 시퀀스(12b)
ID = ⟨시간⟩ ⊕ ⟨데이터센터⟩ ⊕ ⟨워커⟩ ⊕ ⟨시퀀스⟩1) 시간
- timestampLeftShift = 12+5+5 = 22 → 나머지 상위 비트는 시간
- twepoch = 1288834974657L 기준(2010-11-04 01:42:54.657 UTC)
- 수명: 41비트(ms) ≈ 약 69.7년 → 위 twepoch 기준 ~2080년대 초까지 사용 가능
2) 데이터 센터
- datacenterIdBits = 5 → 데이터센터 ID 0~31
3) 워커
- workerIdBits = 5 → 워커 ID 0~31
4) 시퀀스
- sequenceBits = 12 → 같은 ms 내에서 0~4095 순번
4-2. 코드 스니펫
private[this] val sequenceBits = 12L
private[this] val workerIdBits = 5L
private[this] val datacenterIdBits = 5L
val twepoch = 1288834974657L
// ...중략
((timestamp - twepoch) << timestampLeftShift) |
(datacenterId << datacenterIdShift) |
(workerId << workerIdShift) |
sequence
//...5. 운영 시 주의
-
시계 역행(Clock Skew): 감지 시 예외로 생성 차단(중복 방지 우선). 엄격한 NTP 운영 필수
-
버스트 처리: 동일 ms에 4096개 초과 시 다음 ms까지 대기 → tail latency 증가 가능
→ 워커 확장, 요청 평탄화(배치·리밋) 고려 -
전역 단조증가 아님: 다중 워커·DC 간엔 전역 순서 보장 X → 정렬/인덱스에 시간 보조키 병행 권장
-
ZK 의존 영역 최소화: 워커ID 임차만 조정. 세션 만료/네트워크 분할 시 중복 워커ID 방지(펜싱 토큰 등) 설계
6. 용어 정리
6-1. K-sorted(대체로 시간 정렬)
- 상위 비트가 시간이라 대체로 시간순 정렬되지만, 서로 다른 워커/동일 ms에서는 전역 단조증가가 절대적으론 보장되지 않음
6-2.조정방식과 비조정 방식
1) 비조정(uncoordinated) 방식
- ID 생성 시 별도의 합의/락 없이 각 노드가 독립적으로 생성
- 가용성·지연에 유리 (Snowflake의 핵심 철학)
2) 조정(coordinated) 방식
- 중앙 조정(예: DB 시퀀스, ZK 순차 노드)으로 순서 보장
- 전역 순서엔 유리하나 지연·가용성 손해
6-3.모노토닉 시계(monotonic clock)
- 시스템 시간이 뒤로 가지 않는다는 가정
- 위배되면 충돌 위험 존재 → Snowflake는 예외로 중단
6-4.시계 스큐(clock skew)
- 노드 간 시간 차이
- NTP 튜닝·알람이 필수
6-5.O(1) 생성
- 네트워크 왕복/합의 없이 로컬 비트 연산만으로 즉시 생성 → 매우 낮은 지연
