Snowflake ID란 C, C++, Java, Golang

Snowflake ID?

Snowflake ID는 Twitter에서 개발한 분산 시스템을 위한 고유한 ID 생성 알고리즘입니다.

• 이 방식은 빠르고 효율적으로 중복되지 않는 고유 ID를 대규모 시스템에서 생성할 수 있도록 설계되었습니다.
• Snowflake ID는 64비트 정수로 이루어져 있으며, 주로 분산 환경에서 고유한 ID를 생성할 때 사용됩니다.

Snowflake ID의 구성은 64비트(8바이트)로 되어 있으며, 다음과 같은 4가지 주요 부분으로 나뉩니다:

1. Timestamp (41비트)

• Snowflake ID는 41비트를 타임스탬프에 할당합니다.
• 이 타임스탬프는 특정 기준 시점(예를 들어, Twitter에서는 1970년이 아니라 2010년 11월 4일 기준)을 기준으로 현재 시간을 밀리초 단위로 저장합니다.
• 41비트는 약 69년의 시간을 표현할 수 있어, 그 기준 시점부터 69년 동안 고유한 ID를 생성할 수 있습니다.

예: 만약 기준 시점 이후 1밀리초가 경과되었다면, 타임스탬프 부분은 1로 기록됩니다.

2. Data center ID (5비트)

• 5비트는 데이터센터 ID로 사용됩니다. 이는 분산 시스템에서 각 데이터센터 혹은 노드를 식별하는 데 사용됩니다.
• 5비트는 최대 32개의 데이터센터 또는 노드를 나타낼 수 있습니다.

3. Worker ID (5비트) → Node, Server

• 이 5비트는 각각의 기계 또는 노드 안에서 ID를 생성하는 서버의 고유한 ID를 나타냅니다.
• 기계 ID는 각 데이터센터 내에서 노드를 구분하며, 최대 32개의 노드가 하나의 데이터센터에 존재할 수 있습니다.

4. 순차 증가 값 (12비트)

• 12비트는 같은 밀리초 내에서 생성된 ID들 간의 충돌을 방지하기 위해 사용됩니다. 같은 밀리초에 여러 ID가 생성될 경우, 이 부분의 값이 1씩 증가합니다.
• 12비트는 0에서 4095까지 표현할 수 있으므로, 같은 밀리초 내에서 최대 4096개의 ID를 생성할 수 있습니다.

Snowflake ID 예시

• 64비트 숫자로 표현된 ID가 다음과 같은 형태로 구성됩니다:
• 타임스탬프(41bit) | 데이터센터 ID(5bit) | 기계 ID(5bit) | 순차 증가 값(12bit)

동작 방식 요약

1. 타임스탬프: Snowflake 알고리즘은 현재 시간(기준 시점 이후)을 밀리초 단위로 기록합니다.
2. 데이터센터 ID와 기계 ID: 시스템의 각 데이터센터와 노드를 고유하게 식별합니다.
3. 순차 증가 값: 같은 밀리초 내에서 여러 ID가 생성될 때 순차적으로 증가하여 중복되지 않는 ID를 보장합니다.

이를 통해 Snowflake ID는 매우 짧은 시간 안에 고유한 ID를 빠르게 생성할 수 있습니다. 분산 시스템에서 이 방식은 충돌 없이 대규모 데이터를 처리할 때 매우 효율적으로 작동합니다.

특징

• 고유성: 전 세계적으로 고유한 ID를 생성할 수 있습니다.
• 시간 정렬: 생성된 ID는 시간 순서대로 정렬됩니다.
• 확장성: 여러 노드 및 데이터센터에서 병렬적으로 작동할 수 있습니다.
• 고성능: 짧은 시간 안에 많은 ID를 생성할 수 있습니다.

이 방식 덕분에 Snowflake ID는 분산된 시스템에서도 안전하게 고유한 ID를 생성할 수 있는 강력한 방법입니다.

예시 ID

가정:

• 타임스탬프: 1627483646823 밀리초 (예시로 특정 기준 시간 이후 경과된 밀리초)
• 데이터센터 ID: 3
• 기계 ID: 7
• 시퀀스 넘버: 42

이 정보를 기반으로 Snowflake ID가 생성됩니다.

1. 타임스탬프 (41비트):

• 1627483646823은 41비트로 표현되며, 이는 약 2조에 가까운 큰 숫자입니다.
• 41비트는 약 0000000000000001011111110100001110111011011110000100011로 표현될 수 있습니다.

2. 데이터센터 ID (5비트):

• 데이터센터 ID 3은 5비트로 표현하면 00011입니다.

3. 기계 ID (5비트):

• 기계 ID 7은 5비트로 표현하면 00111입니다.

4. 시퀀스 넘버 (12비트):

• 시퀀스 넘버 42는 12비트로 표현하면 000000101010입니다.

최종적으로 64비트로 결합된 Snowflake ID:

• 이를 모두 결합하면 64비트 숫자로 표현됩니다.이진수는 매우 길기 때문에, 이를 십진수로 변환하면 Snowflake ID는 약 1393834795323400000과 같은 숫자로 표현됩니다.

  0000000000000001011111110100001110111011011110000100011 | 00011 | 00111 | 000000101010 
  => Concat 
  000000000000000101111111010000111011101101111000010001100011001110000000101010

요약:

위의 예시에서 Snowflake ID는 64비트의 긴 숫자로 이루어져 있으며, 이를 사용하면 시스템에서 고유한 ID를 안전하게 생성할 수 있습니다.

Snowflake에서 lastTimestamp의 역할

• lastTimestamp는 Snowflake 알고리즘에서 마지막으로 사용된 타임스탬프를 저장하는 변수입니다. 이 변수는 Snowflake ID를 생성할 때 중요한 역할을 하며, 중복되지 않는 고유 ID를 보장하는 데 사용됩니다.

1. 중복 방지
   • Snowflake 알고리즘은 같은 밀리초 내에서 여러 개의 ID를 생성할 수 있습니다. 이때 sequence (시퀀스 번호)라는 값이 같은 밀리초 내에서 발생한 여러 요청을 구분해 주는데, 같은 밀리초에 ID를 여러 개 생성할 경우 시퀀스 번호가 증가합니다.
   • 만약 현재 밀리초와 lastTimestamp가 같다면, sequence를 증가시키면서 ID를 생성합니다.
   • 그러나 새로운 밀리초로 넘어가면, 시퀀스 번호를 초기화하고 ID 생성을 다시 시작합니다. 이때 lastTimestamp를 업데이트하여, Snowflake 알고리즘이 마지막으로 어떤 타임스탬프에서 ID를 생성했는지 기록합니다.
2. 밀리초 단위에서 중복된 시퀀스 처리
   • Snowflake는 밀리초 단위로 타임스탬프를 사용하기 때문에, 한 밀리초 내에 여러 개의 ID를 생성하는 상황이 발생할 수 있습니다. 이때 같은 타임스탬프에서 여러 개의 ID를 만들면 중복된 ID가 생성될 수 있기 때문에, lastTimestamp를 활용하여 중복을 방지합니다.
   • 만약 현재 시간(timestamp)이 lastTimestamp와 같으면, 시퀀스 번호(sequence)를 증가시켜 새로운 ID를 생성합니다.
   • 반대로 현재 시간이 lastTimestamp보다 크면(즉, 새로운 밀리초가 되었을 때), 시퀀스 번호를 0으로 초기화하고 새로운 타임스탬프를 사용해 ID를 생성합니다.

C

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

#define EPOCH 1288834974657L
#define DATA_CENTER_BITS 5
#define NODE_BITS 5
#define SEQ_BITS 12

#define MAX_DATA_CENTER_ID ((1 << DATA_CENTER_BITS) - 1)
#define MAX_NODE_ID ((1 << NODE_BITS) - 1)
#define MAX_SEQ ((1 << SEQ_BITS) - 1)

typedef struct {
    uint64_t lastTimestamp;
    uint64_t dataCenterId;
    uint64_t nodeId;
    uint64_t sequence;
} Snowflake;

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

uint64_t next_id(Snowflake *sf) {
    uint64_t timestamp = current_time_millis();

    if (timestamp == sf->lastTimestamp) {
        sf->sequence = (sf->sequence + 1) & MAX_SEQ;
        if (sf->sequence == 0) {
            while (timestamp <= sf->lastTimestamp) { // 다음 밀리초가 될 때까지 대기
                timestamp = current_time_millis();
            }
        }
    } else { // 새로운 밀리초에 진입했을 때
        sf->sequence = 0; // 시퀀스 초기화
    }

    sf->lastTimestamp = timestamp; // 업데이트!

    uint64_t id = ((timestamp - EPOCH) << (DATA_CENTER_BITS + NODE_BITS + SEQ_BITS))
                  | (sf->dataCenterId << (NODE_BITS + SEQ_BITS))
                  | (sf->nodeId << SEQ_BITS)
                  | sf->sequence;

      // 최종적으로 64비트를 생성하기 위해 Shift로 차례대로 자릿수만큼 밀고
      // | (Bit OR) 연산자를 통해 Concat하여 하나의 64비트 ID를 형성한다.

    return id;
}

int main() {
    Snowflake sf = {0, 1, 1, 0}; // 데이터센터 ID = 1, 노드 ID = 1
    uint64_t id = next_id(&sf);
    printf("Generated Snowflake ID: %llu\n", id);
    return 0;
}

C++

#include <iostream>
#include <cstdint>
#include <chrono>
#include <thread>

#define EPOCH 1288834974657L
#define DATA_CENTER_BITS 5
#define NODE_BITS 5
#define SEQ_BITS 12

#define MAX_DATA_CENTER_ID ((1 << DATA_CENTER_BITS) - 1)
#define MAX_NODE_ID ((1 << NODE_BITS) - 1)
#define MAX_SEQ ((1 << SEQ_BITS) - 1)

class Snowflake {
public:
    Snowflake(uint64_t dataCenterId, uint64_t nodeId)
        : dataCenterId(dataCenterId), nodeId(nodeId), sequence(0), lastTimestamp(0) {}

    uint64_t nextId() {
        uint64_t timestamp = currentTimeMillis();

        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & MAX_SEQ;
            if (sequence == 0) {
                while (timestamp <= lastTimestamp) {
                    timestamp = currentTimeMillis();
                }
            }
        } else {
            sequence = 0;
        }

        lastTimestamp = timestamp;

        return ((timestamp - EPOCH) << (DATA_CENTER_BITS + NODE_BITS + SEQ_BITS)) |
               (dataCenterId << (NODE_BITS + SEQ_BITS)) |
               (nodeId << SEQ_BITS) |
               sequence;
    }

private:
    uint64_t currentTimeMillis() {
        return std::chrono::duration_cast<std::chrono::milliseconds>(
                   std::chrono::system_clock::now().time_since_epoch())
            .count();
    }

    uint64_t dataCenterId;
    uint64_t nodeId;
    uint64_t sequence;
    uint64_t lastTimestamp;
};

int main() {
    Snowflake sf(1, 1); // 데이터센터 ID = 1, 노드 ID = 1
    uint64_t id = sf.nextId();
    std::cout << "Generated Snowflake ID: " << id << std::endl;
    return 0;
}

JAVA

public class Snowflake {
    private final static long EPOCH = 1288834974657L;
    private final static long DATA_CENTER_BITS = 5L;
    private final static long NODE_BITS = 5L;
    private final static long SEQ_BITS = 12L;

    private final static long MAX_DATA_CENTER_ID = (1L << DATA_CENTER_BITS) - 1;
    private final static long MAX_NODE_ID = (1L << NODE_BITS) - 1;
    private final static long MAX_SEQ = (1L << SEQ_BITS) - 1;

    private final long dataCenterId;
    private final long nodeId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;

    public Snowflake(long dataCenterId, long nodeId) {
        if (dataCenterId < 0 || dataCenterId > MAX_DATA_CENTER_ID) {
            throw new IllegalArgumentException("Data Center ID can't be greater than " + MAX_DATA_CENTER_ID + " or less than 0");
        }
        if (nodeId < 0 || nodeId > MAX_NODE_ID) {
            throw new IllegalArgumentException("Node ID can't be greater than " + MAX_NODE_ID + " or less than 0");
        }
        this.dataCenterId = dataCenterId;
        this.nodeId = nodeId;
    }

    public synchronized long nextId() {
        long timestamp = currentTimeMillis();

        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & MAX_SEQ;
            if (sequence == 0) {
                while (timestamp <= lastTimestamp) {
                    timestamp = currentTimeMillis();
                }
            }
        } else {
            sequence = 0;
        }

        lastTimestamp = timestamp;

        return ((timestamp - EPOCH) << (DATA_CENTER_BITS + NODE_BITS + SEQ_BITS)) |
               (dataCenterId << (NODE_BITS + SEQ_BITS)) |
               (nodeId << SEQ_BITS) |
               sequence;
    }

    private long currentTimeMillis() {
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        Snowflake sf = new Snowflake(1, 1); // 데이터센터 ID = 1, 노드 ID = 1
        long id = sf.nextId();
        System.out.println("Generated Snowflake ID: " + id);
    }
}

Golang

package main

import (
    "fmt"
    "sync"
    "time"
)

const (
    epoch       int64 = 1288834974657
    dataCenterBits uint = 5
    nodeBits    uint = 5
    sequenceBits uint = 12

    maxDataCenterID int64 = -1 ^ (-1 << dataCenterBits)
    maxNodeID   int64 = -1 ^ (-1 << nodeBits)
    maxSequence int64 = -1 ^ (-1 << sequenceBits)
)

type Snowflake struct {
    mutex        sync.Mutex
    lastTimestamp int64
    dataCenterID int64
    nodeID       int64
    sequence     int64
}

func NewSnowflake(dataCenterID, nodeID int64) *Snowflake {
    if dataCenterID < 0 || dataCenterID > maxDataCenterID {
        panic(fmt.Sprintf("Data Center ID must be between 0 and %d", maxDataCenterID))
    }
    if nodeID < 0 || nodeID > maxNodeID {
        panic(fmt.Sprintf("Node ID must be between 0 and %d", maxNodeID))
    }
    return &Snowflake{
        dataCenterID: dataCenterID,
        nodeID:       nodeID,
    }
}

func (s *Snowflake) NextID() int64 {
    s.mutex.Lock()
    defer s.mutex.Unlock()

    timestamp := currentTimeMillis()

    if timestamp == s.lastTimestamp {
        s.sequence = (s.sequence + 1) & maxSequence
        if s.sequence == 0 {
            for timestamp <= s.lastTimestamp {
                timestamp = currentTimeMillis()
            }
        }
    } else {
        s.sequence = 0
    }

    s.lastTimestamp = timestamp

    id := ((timestamp - epoch) << (dataCenterBits + nodeBits + sequenceBits)) |
        (s.dataCenterID << (nodeBits + sequenceBits)) |
        (s.nodeID << sequenceBits) |
        s.sequence

    return id
}

func currentTimeMillis() int64 {
    return time.Now().UnixNano() / int64(time.Millisecond)
}

func main() {
    sf := NewSnowflake(1, 1) // 데이터센터 ID = 1, 노드 ID = 1
    id := sf.NextID()
    fmt.Printf("Generated Snowflake ID: %d\n", id)
}

Reference

• https://en.wikipedia.org/wiki/Snowflake_ID
• https://medium.com/@jitenderkmr/demystifying-snowflake-ids-a-unique-identifier-in-distributed-computing-72796a827c9d