분산 시스템 유일 ID 생성기 설계 — Twitter Snowflake (Java 구현)

📚 책: 가상 면접 사례로 배우는 대규모 시스템 설계 기초 (System Design Interview) 1권 — 글쓴이 알렉스 쉬 / 옮긴이 이병준. 이 글은 7장 스터디 노트다.

서론 — 문제 상황

상대적으로 큰 트래픽 부하가 발생하고 이를 처리해야 하는 상황이다. (초당 10,000개의 ID를 Insert해야 한다고 가정한다.)

10,000 RPS(TPS)를 한 서버의 애플리케이션으로 처리하기엔 과부하가 일어날 수 있다. 그래서 같은 기능을 하는 여러 서버를 묶어 클러스터링으로 성능을 끌어올리고, 요청을 여러 애플리케이션 서버로 분산한다.

이때 각 애플리케이션이 DB에 Insert를 보내고 ID가 Auto-Increment로 하나씩 올라간다면, 경쟁 조건(race condition)에 의해 ID가 겹칠 수 있다 (성능 이슈로 트랜잭션 격리 수준이 엄격하지 않다고 가정). 7장은 서로 다른 서버에서 ID를 생성해도 유일한 ID를 만드는 생성기를 다룬다.

ID 생성기의 요구사항은 다음과 같다.

1. 유일(Unique) ID
2. 숫자(Number) 타입
3. ID 자릿수는 64비트로 구성 (16진수 16글자 이내)
4. ID 발급 날짜순 정렬이 가능해야 함
5. 10,000 TPS를 감당할 수 있어야 함

방법론 — 4가지 중 Snowflake

책은 UUID, 다중 마스터 복제, 티켓 서버, Twitter Snowflake 4가지를 제시한다. 각 방법마다 고찰할 점이 많지만, 이 글에서는 메인으로 소개되는 Twitter Snowflake 기법을 다룬다.

Snowflake는 동시성 문제가 생길 만한 요소들을 ID를 구성하는 요소로 직접 넣어 동시성 문제를 구조적으로 제거한다.

그림 1. Snowflake ID 구성

Snowflake는 64비트이며 5개 구획으로 나뉜다. 각 구획을 보며 ID 구성만으로 동시성을 어떻게 해결했는지 따라가 보자.

• ① Sign — 1비트 : 당장은 안 쓰지만 추후 음수/양수 구별용.
• ② TimeStamp — 41비트 : 기원 시각(epoch) 이후 경과한 milliseconds. Snowflake 기원 시각은 Nov 04, 2010, 01:42:54 UTC = 1288834974657 ms.
• ③ DataCenter ID — 5비트 : 2⁵ = 총 32개 데이터센터 지원.
• ④ Server ID — 5비트 : 데이터센터당 32개 서버 지원. 32 × 32 = 총 1024개 서버.
• ⑤ Serial Num — 12비트 : 같은 서버에서 1ms 이내에 여러 ID가 생성되면 1씩 증가하고, 1ms가 지나면 0으로 초기화.

💡 간결한 아이디어 — 동시성이 발생할 수 있는 요소를 모두 ID 구성요소로 명시해 문제를 해결한다.

1. ID에 시각을 넣어 구분하자. 그런데 같은 시각에 여러 데이터센터에서 발생하면? → DC ID로 분기.
2. 한 데이터센터 안 여러 서버에서 같은 시각에 발생하면? → Server ID로 분기.
3. 같은 시각·같은 서버에서 동시에 발생하면? → Serial Num으로 분기.

이로써 애플리케이션 로직으로 DC/Server를 따로 체크할 필요 없이 ID 생성 자체가 유일성을 갖는다. (단, 동시에 들어와 Serial Num까지 같아지는 케이스는 ID Generator에서 처리해줘야 한다.)

구현 (Java)

비트 연산자로 5개 구획을 각각 Shift해 하나의 64비트 ID를 만들고, 10진법 Long 타입으로 반환하는 생성기다.

import java.time.LocalDateTime;
import java.time.ZoneId;

public class SnowFlakeIdGenerator {

    // 트위터의 기원 시각을 ms로 표현한 값
    private final long twEpoch = 1288834974657L;

    // 구성: TimeStamp 41bit, Server ID 5bit, DC ID 5bit, Serial 12bit
    private final long timestampBits = 41L;
    private final long serverIdBits = 5L;
    private final long datacenterIdBits = 5L;
    private final long serialBits = 12L;

    // 비트 시프트 — 각 구획만큼 왼쪽으로 밀어줄 자리 수를 미리 계산
    private final long serialIdShiftFromRight = serialBits;
    private final long datacenterIdShiftFromRight = serialBits + serverIdBits;
    private final long timestampLeftShiftFromRight = serialBits + serverIdBits + datacenterIdBits;
    private final long signLeftShiftFromRight = serialBits + serverIdBits + datacenterIdBits + timestampBits;

    // Serial이 한 바퀴 돌면 0으로 되돌리기 위한 마스크
    private final long serialMask = -1L ^ (-1L << serialBits);

    private long oldTimestamp = -1L;
    private long serialNum = 1L;

    // 같은 ms에 여러 요청이 몰릴 수 있어 synchronized
    public synchronized long generateNewId(long serverId, long dataCenterId) throws Exception {

        long timestamp = getCurrentTimeStamp();   // 현재 시각(ms)

        long signedId = 1L;
        long timestampId = timestamp - twEpoch;

        // Serial Number 증가
        if (timestamp == oldTimestamp) {
            // 한 바퀴 돌면 serialNum을 0으로
            serialNum = (serialNum + 1) & serialMask;

            // 1ms 안에 4096개(2^12)를 다 쓰면 다음 ms까지 대기
            if (serialNum == 0) {
                long newTime = getCurrentTimeStamp();
                while (timestamp != newTime) {
                    newTime = getCurrentTimeStamp();
                }
            }
        } else {
            serialNum = 1L;   // 시각이 달라지면 초기화
        }

        oldTimestamp = timestamp;

        // 5개 구획을 Shift해 하나의 64bit ID로 합친다
        long snowFlakeId =
                signedId << signLeftShiftFromRight |
                timestampId << timestampLeftShiftFromRight |
                dataCenterId << datacenterIdShiftFromRight |
                serverId << serialIdShiftFromRight |
                serialNum;

        return snowFlakeId;
    }

    private long getCurrentTimeStamp() {
        // 데이터센터마다 다를 수 있어 ZoneId로 통일
        ZoneId zoneId = ZoneId.of("Asia/Seoul");
        return LocalDateTime.now().atZone(zoneId).toInstant().toEpochMilli();
    }
}

결과는 비트·10진법 모두 확인했다. (맨 앞 Sign을 1로 둬서 10진법 표기 시 음수가 된다.)

비트 표기 : 1001100011111100110110001011011111001111000000100001000000000001
10진법    : -7422819801849786367

10진법 값을 String으로 바꿔 Insert 시 ID에 넣는 방식으로 사용했다.

테스트 환경

이제 이 ID Generator를 10,000 TPS 환경에 노출시켜 중복 없이 들어가는지 확인할 차례다. 테스트 환경은 다음과 같이 구성했다.

그림 2. ID Generator 테스트 아키텍처

필자는 홈 클라우드 서버를 구축해 외부에서 SSH로 붙을 수 있게 해뒀다. 집에 PC가 6대라 private 망으로 위 구성이 가능하다.

1. Apache Bench — n개의 요청을 동시(concurrency)에 보낼 수 있는 성능 테스트기.
2. Nginx — 대표적인 웹 서버지만 여기서는 Reverse Proxy(로드 밸런서)로 사용.
3. Nexus Repository — 위에서 만든 Id-Generator jar를 애플리케이션에 전달.
4. Netty — Spring Boot 기본 내장 Tomcat 대신, 성능을 위해 Event Loop 방식의 Netty 서버를 사용.
5. MongoDB — DB. Non-Blocking을 지원하는 mongo-reactive-db ORM 사용.

각 구성요소마다 할 말이 많지만 이 글에서는 테스트 구성만 소개한다. 다음 글에서 위 성능 테스트 결과를 공유할 예정이다.

위 구성 중 Nginx 설치·버전 설정은 아래 글에서 자세히 다룬다.

Nginx 설치 가이드 — Ubuntu / CentOS (특정 버전·설정 구조·방화벽)

AWS EC2 등 클라우드 서버에 Nginx 설치 — Ubuntu(apt)·CentOS(yum) 버전별 설치, /etc/nginx 설정 구조(sites-available/enabled), UFW·firewalld·AWS 보안그룹 방화벽까지 한 번에.

taystudios.com/blog

📦 이 글은 제가 운영하던 티스토리 블로그에서 옮겨온(migration) 글입니다. 원문: taehyuklee.tistory.com/10