Interview/Etc
Snowflake ID란 C, C++, Java, Golang
김 정출
2024. 9. 26. 10:34
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)
동작 방식 요약
- 타임스탬프: Snowflake 알고리즘은 현재 시간(기준 시점 이후)을 밀리초 단위로 기록합니다.
- 데이터센터 ID와 기계 ID: 시스템의 각 데이터센터와 노드를 고유하게 식별합니다.
- 순차 증가 값: 같은 밀리초 내에서 여러 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를 보장하는 데 사용됩니다.
- 중복 방지
- Snowflake 알고리즘은 같은 밀리초 내에서 여러 개의 ID를 생성할 수 있습니다. 이때
sequence(시퀀스 번호)라는 값이 같은 밀리초 내에서 발생한 여러 요청을 구분해 주는데, 같은 밀리초에 ID를 여러 개 생성할 경우 시퀀스 번호가 증가합니다. - 만약 현재 밀리초와
lastTimestamp가 같다면,sequence를 증가시키면서 ID를 생성합니다. - 그러나 새로운 밀리초로 넘어가면, 시퀀스 번호를 초기화하고 ID 생성을 다시 시작합니다. 이때
lastTimestamp를 업데이트하여, Snowflake 알고리즘이 마지막으로 어떤 타임스탬프에서 ID를 생성했는지 기록합니다.
- Snowflake 알고리즘은 같은 밀리초 내에서 여러 개의 ID를 생성할 수 있습니다. 이때
- 밀리초 단위에서 중복된 시퀀스 처리
- Snowflake는 밀리초 단위로 타임스탬프를 사용하기 때문에, 한 밀리초 내에 여러 개의 ID를 생성하는 상황이 발생할 수 있습니다. 이때 같은 타임스탬프에서 여러 개의 ID를 만들면 중복된 ID가 생성될 수 있기 때문에,
lastTimestamp를 활용하여 중복을 방지합니다. - 만약 현재 시간(
timestamp)이lastTimestamp와 같으면, 시퀀스 번호(sequence)를 증가시켜 새로운 ID를 생성합니다. - 반대로 현재 시간이
lastTimestamp보다 크면(즉, 새로운 밀리초가 되었을 때), 시퀀스 번호를 0으로 초기화하고 새로운 타임스탬프를 사용해 ID를 생성합니다.
- Snowflake는 밀리초 단위로 타임스탬프를 사용하기 때문에, 한 밀리초 내에 여러 개의 ID를 생성하는 상황이 발생할 수 있습니다. 이때 같은 타임스탬프에서 여러 개의 ID를 만들면 중복된 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