System Design. Part07. 분산 시스템을 위한 유일 ID 생성기 설계

Part07. 분산 시스템을 위한 유일 ID 생성기 설계

대규모 분산 시스템에서는 수십억 건의 이벤트에 대해 중복 없이 고유한 ID를 빠르게 생성해야 한다.

1. Snowflake린?

이러한 요구사항을 충족하기 위해 등장한 것이 바로 Snowflake 알고리즘이다. Snowflake는 고유성, 시간 순 정렬성, 분산 확장성, 저지연 생성이라는 네 가지 핵심 요구사항을 64비트 정수 하나로 해결한다.

• 고유성 보장: 서로 다른 노드나 프로세스에서 ID를 생성하더라도 충돌 없이 고유성을 보장한다.
• 시간 순 정렬: 생성 시각 정보가 ID에 포함되어 있어 데이터베이스 정렬 및 조회 효율을 극대화할 수 있다.
• 분산 확장성: 중앙 집중식 락(Lock) 없이 수평 확장이 가능하므로 시스템 규모가 커져도 유연하게 대응할 수 있다.
• 저지연 생성: 밀리초(ms) 단위로 최대 수천 건의 ID를 즉시 발급할 수 있어 고성능이 요구되는 환경에 적합하다.

2. 기존 ID 생성 방식의 한계

방식	장점	단점
Auto-increment (SQL)	구현이 단순하고 정렬이 쉽다.	단일 DB 샤드에 종속되며, 분산 환경에서는 확장이 불가능하다.
UUID (v4)	완전 난수 기반이라 중복될 확률이 희박하다.	128비트라 저장 및 인덱싱 효율이 떨어지며, 시간 순 정렬이 불가능하다.
Random & Timestamp	구현이 간단하다.	난수 충돌 위험이 있으며, 타임스탬프만으로는 동시 생성 순서 보장이 어렵다.

3. Snowflake 64비트 구조

Snowflake ID는 64비트 정수로 구성되며, 각 비트는 특정 정보를 담고 있다.

필드	비트 수	설명
사인(Sign) 비트	1	항상 0으로 설정되어 양수를 나타낸다. 향후 확장을 위해 유보된 비트이다.
타임스탬프	41	Epoch(기준 시점) 이후 경과한 밀리초(ms) 수를 나타낸다. 트위터의 Snowflake 구현에서는 1288834974657 (UTC 2010년 11월 4일 01:42:54)을 Epoch로 사용한다. 이 필드 덕분에 약 69년간 고유 ID를 생성할 수 있다.
데이터센터 ID	5	ID를 생성하는 데이터센터를 식별하는 값이다. $2^5 = 32$개의 데이터센터를 지원한다.
서버 ID	5	각 데이터센터 내의 서버를 식별하는 값이다. 데이터센터당 $2^5 = 32$개의 서버를 사용할 수 있다.
일련번호 (시퀀스)	12	동일한 밀리초 내에서 연속적으로 ID가 생성될 때 증가하는 카운터다. 각 서버에서 ID를 생성할 때마다 이 값을 1만큼 증가시킨다. 1밀리초가 경과할 때마다 0으로 초기화(reset)된다. 0부터 4095까지의 값을 가질 수 있다.

┌─────────┬───────────────┬───────────┬───────────┬──────────┐
│ 1 bit   │    41 bits    │  5 bits   │  5 bits   │ 12 bits  │
│ Sign    │ TimestampDiff │ Datacenter│ Server ID │ Sequence │
│         │               │     ID    │           │          │
└─────────┴───────────────┴───────────┴───────────┴──────────┘

Epoch 기준: 트위터의 Snowflake는 2010-11-04T01:42:54.657Z를 Epoch로 사용한다. TimestampDiff = 현재_밀리초 – Epoch밀리초로 계산된다.

4. 동작 원리

Snowflake ID는 다음과 같은 과정을 통해 생성된다:

1. 현재 시간(밀리초) 을 읽어와 timestampDiff를 계산한다.
2. 비트 시프트를 통한 조합: 각 필드를 적절한 위치에 배치하기 위해 비트 시프트 연산을 수행한다:
   • timestampDiff를 22비트 왼쪽으로 시프트 (상위 41비트 위치로 이동)
   • datacenterId를 17비트 왼쪽으로 시프트 (타임스탬프 다음 5비트 위치로 이동)
   • serverId를 12비트 왼쪽으로 시프트 (데이터센터 ID 다음 5비트 위치로 이동)
   • sequence는 시프트 없이 하위 12비트에 배치

3. OR 연산을 통한 최종 조합: 이 네 부분을 OR 연산하여 64비트 정수 ID를 생성한다.

   ID = (timestampDiff << 22) | (datacenterId << 17) | (serverId << 12) | sequence

동일 밀리초 내 요청 처리: 같은 밀리초에 여러 ID 생성 요청이 들어오면 일련번호를 1씩 증가시킨다. 일련번호가 4095를 초과하면, 다음 밀리초가 될 때까지 대기한 후 일련번호를 0으로 초기화하고 ID를 생성한다.

5. 중요 고려사항

Snowflake 알고리즘을 구현하고 운영할 때 다음 사항들을 고려해야 한다:

• Clock Drift (시계 뒤틀림): 서버 간의 시계 차이로 인해 역순으로 ID가 생성될 위험이 있다. NTP(Network Time Protocol) 동기화를 철저히 하거나, 역순 ID가 감지될 경우 예외 처리를 통해 문제를 해결해야 한다.
• Sequence Overflow (시퀀스 오버플로우): 특정 밀리초에 생성할 수 있는 ID 개수(4096개)를 초과하면 다음 밀리초까지 대기하게 된다. 초당 생성량이 4096 × 노드 수를 넘어서는 시점에서 병목 현상이 발생할 수 있으므로, 시스템의 예상 부하를 고려해야 한다.
• Epoch 수명: 41비트 타임스탬프는 약 69년 동안 유효하다. 이 기간이 지나면 ID 생성이 불가능해지므로, 장기적으로는 재설계가 필요하다.
• 머신 ID 관리: 각 워커에 고유한 머신 ID를 할당하고 중복을 방지하는 것이 매우 중요하다.

6. 구현 예시 (Kotlin)

class Snowflake(
    private val datacenterId: Long, // 데이터센터 ID
    private val serverId: Long      // 서버 ID
) {
    companion object {
        private const val EPOCH = 1288834974657L // 트위터의 Epoch (Nov 04, 2010, 01:42:54 UTC)
        
        private const val DATACENTER_ID_BITS = 5L
        private const val SERVER_ID_BITS = 5L
        private const val SEQUENCE_BITS = 12L
        
        private const val MAX_DATACENTER_ID = (-1L shl DATACENTER_ID_BITS.toInt()).inv() // 31
        private const val MAX_SERVER_ID = (-1L shl SERVER_ID_BITS.toInt()).inv()         // 31
        private const val MAX_SEQUENCE = (-1L shl SEQUENCE_BITS.toInt()).inv()           // 4095
        
        private const val SERVER_ID_SHIFT = SEQUENCE_BITS.toInt()                        // 12
        private const val DATACENTER_ID_SHIFT = (SEQUENCE_BITS + SERVER_ID_BITS).toInt() // 17
        private const val TIMESTAMP_LEFT_SHIFT = (SEQUENCE_BITS + SERVER_ID_BITS + DATACENTER_ID_BITS).toInt() // 22
    }

    private var lastTimestamp = -1L
    private var sequence = 0L

    init {
        require(datacenterId in 0..MAX_DATACENTER_ID) {
            "Datacenter ID must be between 0 and $MAX_DATACENTER_ID"
        }
        require(serverId in 0..MAX_SERVER_ID) {
            "Server ID must be between 0 and $MAX_SERVER_ID"
        }
    }

    @Synchronized
    fun nextId(): Long {
        var currentTimestamp = System.currentTimeMillis()

        // 시계가 뒤로 돌아간 경우 예외 처리
        if (currentTimestamp < lastTimestamp) {
            throw IllegalStateException(
                "Clock moved backwards. Refusing to generate ID for ${lastTimestamp - currentTimestamp} milliseconds"
            )
        }

        // 동일 밀리초 내 요청 처리
        if (currentTimestamp == lastTimestamp) {
            sequence = (sequence + 1) and MAX_SEQUENCE // 12비트 시퀀스 번호 증가
            if (sequence == 0L) { // 시퀀스 오버플로우 발생 시 다음 밀리초까지 대기
                currentTimestamp = waitForNextMillis(lastTimestamp)
            }
        } else { // 새로운 밀리초가 시작되면 시퀀스 초기화
            sequence = 0L
        }

        lastTimestamp = currentTimestamp // 마지막 타임스탬프 업데이트

        // 각 부분을 비트 시프트하여 조합
        return ((currentTimestamp - EPOCH) shl TIMESTAMP_LEFT_SHIFT) or
               (datacenterId shl DATACENTER_ID_SHIFT) or
               (serverId shl SERVER_ID_SHIFT) or
               sequence
    }

    // 다음 밀리초까지 대기
    private fun waitForNextMillis(lastTimestamp: Long): Long {
        var timestamp = System.currentTimeMillis()
        while (timestamp <= lastTimestamp) {
            timestamp = System.currentTimeMillis()
        }
        return timestamp
    }
}

fun main() {
    try {
        val generator = Snowflake(datacenterId = 1, serverId = 1)
        
        println("Snowflake ID Generator 테스트")
        println("데이터센터 ID: 1, 서버 ID: 1")
        println("=" * 50)
        
        repeat(10) { i ->
            val id = generator.nextId()
            println("${i + 1}. Generated ID: $id")
            
            // ID 파싱 예시 (첫 번째 ID만)
            if (i == 0) {
                val timestamp = (id shr 22) + 1288834974657L
                val datacenterId = (id shr 17) and 0x1F
                val serverId = (id shr 12) and 0x1F
                val sequence = id and 0xFFF
                
                println("   ├─ Timestamp: ${java.time.Instant.ofEpochMilli(timestamp)}")
                println("   ├─ Datacenter ID: $datacenterId")
                println("   ├─ Server ID: $serverId")
                println("   └─ Sequence: $sequence")
            }
        }
        
    } catch (e: Exception) {
        System.err.println("Error: ${e.message}")
    }
}

7. 성능 특성

• 생성 속도: 단일 노드에서 밀리초당 최대 4,096개의 ID 생성 가능
• 전체 처리량: N개 노드 × 4,096개/ms = 초당 약 4,096,000 × N개의 ID 생성 가능
• ID 크기: 64비트 정수 (8바이트)로 UUID(16바이트)보다 50% 효율적
• 정렬성: 시간 순으로 생성되므로 데이터베이스 인덱싱에 유리