고유 ID 생성 알고리즘 (SNOWFLAKE)

Snowflake 알고리즘은 분산 시스템에서 고유한 ID를 생성하기 위해 설계된 방법입니다. 이 알고리즘은 Twitter에서 개발되었으며, 여러 서버에서 동시에 ID를 생성할 때 발생할 수 있는 충돌을 방지하면서도 시간에 따라 정렬 가능한 ID를 생성합니다.

Snowflake ID의 구조:

1. Timestamp (41 bits): 밀리초 단위의 타임스탬프
2. Datacenter ID (5 bits): 데이터 센터 식별자
3. Worker ID (5 bits): 워커(서버) 식별자
4. Sequence number (12 bits): 같은 밀리초 내에서 생성된 ID를 구분하기 위한 시퀀스 번호

주요 특징:

1. 유일성: 분산 환경에서도 중복 없는 ID 생성
2. 정렬 가능: 시간 순서대로 정렬 가능
3. 높은 성능: 초당 수백만 개의 ID 생성 가능
4. 64비트 정수로 표현 가능

장점:

• 분산 시스템에 적합
• 시간 기반 정렬 가능
• 높은 생성 속도

단점:

• 구현이 복잡할 수 있음
• 시스템 시간에 의존적

Snowflake 알고리즘은 대규모 분산 시스템에서 효과적이지만, 작은 규모의 시스템에서는 과도한 복잡성을 가질 수 있습니다. 따라서 시스템의 규모와 요구사항에 따라 적절히 선택해야 합니다.

 

include <stdio.h>
#include <stdint.h>
#include <time.h>

#define EPOCH 1609459200000 // 2021-01-01 00:00:00 UTC

typedef struct {
    int64_t last_timestamp;
    int datacenter_id;
    int worker_id;
    int sequence;
} snowflake_t;

int64_t current_timestamp() {
    struct timespec ts;
    clock_gettime(CLOCK_REALTIME, &ts);
    return (int64_t)ts.tv_sec * 1000 + (int64_t)ts.tv_nsec / 1000000;
}

int64_t generate_snowflake(snowflake_t *sf) {
    int64_t timestamp = current_timestamp() - EPOCH;

    if (timestamp < sf->last_timestamp) {
        // Handle clock moving backwards
        fprintf(stderr, "Clock moved backwards. Refusing to generate id.\n");
        return -1;
    }

    if (timestamp == sf->last_timestamp) {
        sf->sequence = (sf->sequence + 1) & 4095; // 2^12 - 1
        if (sf->sequence == 0) {
            // Sequence exhausted, wait for next millisecond
            while (timestamp <= sf->last_timestamp) {
                timestamp = current_timestamp() - EPOCH;
            }
        }
    } else {
        sf->sequence = 0;
    }

    sf->last_timestamp = timestamp;

    return (timestamp << 22) |
           (sf->datacenter_id << 17) |
           (sf->worker_id << 12) |
           sf->sequence;
}

int main() {
    snowflake_t sf = {0, 1, 1, 0}; // Initialize with datacenter_id=1, worker_id=1

    for (int i = 0; i < 5; i++) {
        int64_t id = generate_snowflake(&sf);
        if (id != -1) {
            printf("Generated ID: %lld\n", id);
        }
    }

    return 0;
}

이 코드의 주요 구성 요소:

1. snowflake_t 구조체: Snowflake 생성기의 상태를 저장합니다.
2. current_timestamp() 함수: 현재 시간을 밀리초 단위로 반환합니다.
3. generate_snowflake() 함수: Snowflake ID를 생성합니다.
4. main() 함수: 예제로 5개의 Snowflake ID를 생성합니다.

주의사항:

• 이 구현은 단일 스레드 환경을 가정합니다. 멀티스레드 환경에서는 적절한 동기화 메커니즘이 필요합니다.
• 시스템 시간이 뒤로 가는 경우에 대한 처리가 간단합니다. 실제 환경에서는 더 복잡한 처리가 필요할 수 있습니다.
• 데이터센터 ID와 워커 ID는 수동으로 설정해야 합니다.

 

EPOCH(에포크)를 사용하는 이유는 다음과 같습니다:

1. 공간 효율성:
   • 전체 타임스탬프 대신 EPOCH로부터의 경과 시간만을 저장함으로써 필요한 비트 수를 줄일 수 있습니다.
   • Snowflake ID에서는 타임스탬프에 41비트만 사용하므로, 최대한 효율적으로 이 공간을 활용해야 합니다.
2. 더 긴 사용 기간:
   • EPOCH를 적절히 설정함으로써, 시스템의 예상 수명 동안 사용할 수 있는 고유 ID를 생성할 수 있습니다.
   • 예를 들어, 2021년 1월 1일을 EPOCH로 설정하면, 41비트로 약 69년 동안의 밀리초를 표현할 수 있습니다.
3. 시작점 정의:
   • 시스템이나 프로젝트의 시작 시점을 EPOCH로 정의함으로써, 모든 ID가 양수가 되도록 할 수 있습니다.
   • 이는 일부 시스템에서 음수 ID를 처리하는 문제를 방지할 수 있습니다.
4. 일관성:
   • 모든 서버와 클라이언트가 동일한 EPOCH를 사용함으로써, 생성된 ID의 일관성을 보장할 수 있습니다.
5. 의미있는 시작점:
   • 프로젝트나 시스템의 의미 있는 날짜를 EPOCH로 설정함으로써, ID에 추가적인 의미를 부여할 수 있습니다.
6. 타임스탬프 해석 용이성:
   • EPOCH를 알면 ID에서 실제 날짜와 시간을 쉽게 추출할 수 있습니다.

예를 들어, 코드에서 사용된 EPOCH(1609459200000)는 2021년 1월 1일 00:00:00 UTC를 나타냅니다. 이 시점부터의 경과 시간을 사용하여 ID를 생성하므로, 생성된 모든 ID는 이 날짜 이후의 시간을 나타내게 됩니다.

EPOCH를 사용함으로써 Snowflake 알고리즘은 효율적이고 의미 있는 방식으로 시간 정보를 ID에 인코딩할 수 있습니다.

 

 

 

 

 

2021년 1월 1일 00:00:00 UTC에 해당하는 EPOCH 값(1609459200000)을 생성하는 코드를 여러 프로그래밍 언어로 제공해드리겠습니다.

1. C 언어:

#include <stdio.h>
#include <time.h>

int main() {
    struct tm epoch_time = {0};
    epoch_time.tm_year = 2021 - 1900;  // 년도는 1900년부터의 오프셋
    epoch_time.tm_mon = 0;             // 월은 0부터 시작 (0 = 1월)
    epoch_time.tm_mday = 1;            // 일
    epoch_time.tm_hour = 0;            // 시
    epoch_time.tm_min = 0;             // 분
    epoch_time.tm_sec = 0;             // 초

	/* UTC */
    time_t epoch = timegm(&epoch_time);
    printf("EPOCH: %lld000\n", (long long)epoch);

    return 0;
}

1. Python:

from datetime import datetime, timezone

epoch = datetime(2021, 1, 1, tzinfo=timezone.utc).timestamp()
print(f"EPOCH: {int(epoch * 1000)}")

1. Java:

import java.time.ZoneOffset;
import java.time.ZonedDateTime;

public class EpochGenerator {
    public static void main(String[] args) {
        ZonedDateTime epochDateTime = ZonedDateTime.of(2021, 1, 1, 0, 0, 0, 0, ZoneOffset.UTC);
        long epoch = epochDateTime.toInstant().toEpochMilli();
        System.out.println("EPOCH: " + epoch);
    }
}