분산 ID 생성 방식과 Snowflake 알고리즘 상세 설명

I. 배경

인터넷 비즈니스 시스템에는 다양한 유형의 ID가 존재합니다. 이러한 ID는 전역적인 유일성을 보장해야 하며, 이러한 ID를 분산 ID라고 합니다. 분산 ID는 유일성, 증가 추세, 고가용성, 고성능과 같은 특징을 충족해야 합니다.

Snowflake 알고리즘은 분산 ID 생성 방식 중 하나로, Twitter에서 내부 분산 프로젝트에 적용했습니다. 이 알고리즘이 오픈 소스로 공개된 후 주요 기업들에게 인정받았습니다. 이러한 영향으로 주요 기업들은 자체적인 특징을 가진 분산 ID 생성기를 잇따라 개발했습니다. Snowflake 알고리즘을 자세히 알아보기 전에 일반적으로 사용되는 분산 ID 생성 방식에 대한 개요를 제공하는 것이 필요합니다.

II. 분산 ID 생성 방식

2.1 UUID

이 알고리즘의 핵심 아이디어는 머신의 네트워크 카드, 로컬 시간, 그리고 임의의 숫자를 결합하여 UUID를 생성하는 것입니다.

장점: 로컬에서 생성할 수 있습니다. 생성 과정이 간단하고 성능이 좋으며, 고가용성 문제의 위험이 없습니다.
단점: 생성된 ID가 너무 길어 저장 공간 낭비를 초래합니다. 또한 ID가 정렬되지 않고 읽을 수 없어 쿼리 효율성이 낮습니다.

2.2 데이터베이스 자동 증가 ID

MySQL의 auto_increment와 같은 데이터베이스의 ID 자동 증가 전략을 채택합니다. 고가용성을 달성하기 위해 여러 데이터베이스를 사용할 수 있으며, 반복되지 않는 ID를 생성하기 위해 각각 다른 단계 크기를 설정할 수 있습니다.

장점: 데이터베이스에서 생성된 ID는 절대적으로 정렬되며, 고가용성을 달성하는 방법이 비교적 간단합니다.
단점: 데이터베이스 인스턴스를 독립적으로 배포해야 하므로 비용이 많이 들고 성능 병목 현상이 발생할 수 있습니다.

2.3 Redis를 이용한 ID 생성

Redis의 모든 명령 작업은 단일 스레드입니다. Redis 자체는 incr 및 increby와 같은 자동 증가 원자적 명령을 제공하므로 생성된 ID가 유일하고 정렬되도록 보장할 수 있습니다. 단일 노드의 성능 병목 현상을 해결하기 위해 Redis 클러스터를 사용하여 더 높은 처리량을 얻을 수 있습니다. 예를 들어 5개의 Redis 노드를 포함하는 클러스터에서 각 Redis의 초기값을 각각 1, 2, 3, 4, 5로 설정하고 단계 크기를 5로 설정할 수 있습니다. 각 Redis에서 생성된 ID는 다음과 같습니다.

A: 1, 6, 11, 16, 21
B: 2, 7, 12, 17, 22
C: 3, 8, 13, 18, 23
D: 4, 9, 14, 19, 24
E: 5, 10, 15, 20, 25

단계 크기와 초기값은 미리 결정해야 합니다. Redis 클러스터를 사용하면 단일 실패 지점 문제를 피할 수도 있습니다. 또한 Redis는 매일 0부터 시작하는 일련 번호를 생성하는 데 더 적합합니다. 예를 들어 주문 번호는 "날짜 + 일일 자동 증가 번호" 형식을 채택할 수 있습니다. 매일 Redis에 키가 생성되고 INCR을 통해 증가합니다.

장점: 데이터베이스에 의존하지 않고 유연하고 편리하게 사용할 수 있으며 데이터베이스보다 성능이 좋습니다. 숫자 ID는 자연스럽게 정렬되므로 페이지 매김이나 정렬이 필요한 시나리오에 매우 유용합니다.
단점: 시스템에서 Redis를 사용하지 않는 경우 이 구성 요소를 도입하면 시스템 복잡성이 증가하고 코딩 및 구성 작업량도 비교적 많습니다.

2.4 Snowflake 알고리즘

Snowflake 알고리즘은 Twitter에서 내부 분산 프로젝트에 적용했으며 오픈 소스로 공개된 후 주요 국내 기업들에게 널리 인정받았습니다. Twitter는 2010년 어린이날에 각 트윗을 식별하기 위해 공식 블로그를 통해 이 알고리즘을 소개했습니다.

+--------------------------------------------------------------------------+
| 1 Bit Unused | 41 Bit Timestamp |  10 Bit NodeID  |   12 Bit Sequence ID |
+--------------------------------------------------------------------------+

Snowflake 알고리즘은 64비트를 사용하여 ID를 저장합니다.

최상위 비트는 예약되어 있으며 현재 사용되지 않습니다.
다음 41비트는 타임스탬프로 사용되며, 가장 작은 시간 단위는 밀리초입니다. 41비트 타임스탬프는 약 69년 동안 사용할 수 있습니다(2^41 -1). 시간 표현 범위를 최대한 활용하기 위해 타임스탬프는 시스템이 처음 배포된 시간(예: 2020-02-02 00:00:00)부터 계산을 시작할 수 있습니다.
다음 10비트는 머신 ID(worker id)로 사용되며, 1024대의 머신을 지원할 수 있습니다. 10비트는 데이터 센터 ID와 머신 ID의 두 부분으로 나눌 수도 있습니다. 예를 들어 5:5 비율로 나누면 32개의 데이터 센터를 지원할 수 있으며, 각 데이터 센터는 최대 32대의 머신을 수용할 수 있습니다.
마지막 12비트는 단위 시간(밀리초) 내의 자동 증가 ID이며, 4096개의 ID를 나타낼 수 있습니다. 즉, 각 머신은 밀리초당 최대 4096개의 ID를 생성할 수 있습니다.

타임스탬프, 머신 ID 및 자동 증가 ID가 차지하는 비트 수는 실제 상황에 따라 조정할 수 있습니다. Snowflake 알고리즘은 처음 몇 비트가 타임스탬프이므로 기본적인 순차성을 가지며 ID는 시간별로 정렬할 수 있습니다.

III. Snowflake 알고리즘 상세 설명

3.1 Golang 핵심 코드

var (
    // 시스템이 처음 시작된 시간(밀리초)으로 설정할 수 있습니다. 41비트를 차지하며 69년 동안 사용할 수 있습니다.
    Epoch int64 = 12345688374657

    // 인스턴스의 ID는 10비트를 차지하며 최대 1024개의 인스턴스를 지원할 수 있습니다.
    NodeBits uint8 = 10

    // 단계 크기는 12비트를 차지합니다. 각 인스턴스는 밀리초당 최대 2^12 = 4096개의 반복되지 않는 데이터를 생성할 수 있습니다.
    StepBits uint8 = 12
)

// 생성 알고리즘
func (n *Node) Generate() ID {

    n.mu.Lock()
    // 설정된 타임스탬프부터 현재까지 경과된 밀리초 수
    now := time.Since(n.epoch).Nanoseconds() / 1000000
    // 마지막으로 기록된 시간과 같으면 step을 1씩 증가시키고, 그렇지 않으면 step을 0으로 재설정합니다.
    if now == n.time {
        n.step = (n.step + 1) & n.stepMask

        if n.step == 0 {
            for now <= n.time {
                now = time.Since(n.epoch).Nanoseconds() / 1000000
            }
        }
    } else {
        n.step = 0
    }

    n.time = now
    // 타임스탬프 41비트 | 노드 10비트 | step 12비트
    r := ID((now)<<n.timeShift |
        (n.node << n.nodeShift) |
        (n.step),
    )

    n.mu.Unlock()
    return r
}

특정 비트 할당은 (41, 10, 12), (41, 6, 16) 등과 같이 필요에 따라 조정할 수 있습니다. 전체 Golang 코드 리포지토리: snowflake github.

3.2 장점

적은 저장 공간: 8바이트만 필요합니다.
높은 가독성: ID는 특정 구조와 의미를 가집니다.
좋은 성능: ID는 중앙에서 또는 독립 노드에서 생성할 수 있습니다.

3.3 단점

시간 롤백은 ID의 반복 생성을 초래합니다.

3.4 클럭 롤백에 대한 해결책

머신 ID의 10비트에서 2비트를 클럭 롤백 비트로 사용할 수 있습니다. 클럭 롤백이 감지되면 롤백 비트를 1씩 증가시키고, 최대값에 도달하면 0부터 순환합니다. 예를 들어 10비트 머신 번호를 8비트 머신 번호 + 2비트 롤백 비트로 조정합니다. 클럭 롤백이 감지될 때마다 롤백 비트를 1씩 증가시킵니다. 롤백 비트가 최대값(3)보다 크면 0으로 재설정합니다. 동일한 시간 동안 클럭 롤백은 최대 3번까지 지원됩니다. 각 롤백 후에는 클럭 롤백 비트가 다르기 때문에 최종적으로 생성된 ID도 다릅니다.