TSID
1 동기
사이드 프로젝트에서 Snowflake TSID를 사용해보려고 한다.
Snowflake ID는 분산 시스템에서 고유한 식별자를 생성하기 위해 고안됨.
시간에 따라 정렬되며, UUID(128bit) 보다 작은 64bit 로 구성됨.
2 구조
snowflake TSID의 구조는 다음과 같다.
- 부호(Sign) : 1 bit
- 타임스탬프(Timestamp) : 41 bit
- 데이터센터 ID(Data Center ID) : 보통 5 bit
- 노드 ID(Node ID) : 보통 5 bit
- 시퀀스 번호(Sequence Number) : 보통 12 bit
3 코드
function snowflake({ dataCenterId, nodeId }) {
let dataCenterIdBigInt = BigInt(dataCenterId)
let nodeIdBigInt = BigInt(nodeId)
let sequence = BigInt(0)
let lastTimestamp = BigInt(-1)
function waitNextMillis(timestamp) {
while (timestamp === this.lastTimestamp) {
timestamp = BigInt(Date.now());
}
return timestamp;
}
return function(now_timestamp) {
let timestamp = BigInt(now_timestamp)
if (timestamp === lastTimestamp) {
sequence = (sequence + BigInt(1)) & BigInt(0xFFF); // 시퀀스 마스킹
if (sequence === BigInt(0)) {
timestamp = waitNextMillis(timestamp);
}
} else {
sequence = BigInt(0);
}
lastTimestamp = timestamp;
// 1704067200000 = 2024년 1월 1일의 Unix 타임스탬프
// 1288834974657 = 2010년 11월 4일의 Unix 타임스탬프
const timePart = (timestamp - BigInt(1704067200000)) << BigInt(22); // 타임스탬프 좌측 시프트
const dataCenterPart = dataCenterIdBigInt << BigInt(17); // 데이터 센터 ID 시프트
const nodePart = nodeIdBigInt << BigInt(12); // 노드 ID 시프트
return (timePart | dataCenterPart | nodePart | sequence); // ID 조합
}
}
console.log(snowflake({ dataCenterId: 1, nodeId: 1 })(new Date()).toString())
- dataCenterId, nodeId : 데이터 센터와 노드를 식별하는 ID. 여러 시스템에서 동시에 ID를 생성할 때, 각 ID가 유니크하도록 보장
- sequence : 같은 밀리초 내에 여러 ID가 생성될 때 구분하기 위함. (nodejs에서 사용될 일이 있는지 고민필요)
- lastTimestamp : 마지막으로 ID가 생성된 시간 등록. 동일한 밀리초 생성된 ID들의 시퀀스 값을 관리하는데 사용.
- 비트연산에서 사용하는 상수 값들
- `1288834974657` : Snowflake ID의 타임스탬프 부분에서 사용되는 특정 시작 시간(에포크)를 나타냄. 타임스탬프 값에서 이 값을 빼서, 더 작은 범위의 정수로 타임스탬프를 표현한다. (이 값은 내가 더 크게 지정해서 사용할 수도 있음) 난 그래서 2024년을 기준으로 만들고자함.
- `timestamp - 1288834974657) << 22` 타임스탬프 값을 22비트 왼쪽으로 이동시켜, ID의 상위 비트에 위치하도록 함. 이는 dataCenter ID, node ID, sequence 의 자리를 만들기 위함이다. 자연스럽게 17은 dataCenter 자리를 뺀, node Id와 sequence를 말함.
- `0xFFF` - 시퀀스 번호의 최대값을 정의함. 16진수로 4095를 의미하며, 0에서 4095사이 값을 가질 수 있음을 말함.
- `|` - 최종 조합, `timePart`, `dataCenterPart`, `nodePart`, `sequence` 파트를 OR 연산으로 결합함.
- waitNextMillis 는 sequence의 0xFFF(4095)를 넘어서면 0이 되면서 다음밀리초에 이어서 만들도록 한다.
4 테스트
실제로 (거의) 동시에 실행하면, 밀리초가 동일할 수 있기 때문에 sequence에 따라 만들어져야 할 것이다. 이것에 대해서 한번 테스트를 수행해보았다.
const generateId = snowflake({ dataCenterId: 1, nodeId: 1 });
// 여러 Snowflake ID 생성
const ids = [];
for (let i = 0; i < 5; i++) {
const id = generateId();
ids.push(id.toString());
}
console.log(ids);
일단 시퀀스가 생성되는 것은 알 수 있다. 비트단위로 보자.
[ '823086672908288', '823086672908289', '823086672908290', '823086672908291', '823086672908292' ]
const generateId = snowflake({ dataCenterId: 1, nodeId: 1 });
// 여러 Snowflake ID 생성
const ids = [];
for (let i = 0; i < 5; i++) {
const id = generateId();
ids.push(id.toString(2));
}
console.log(ids);
---
[
'10111011001110100001011110010000100001000000000000',
'10111011001110100001011110010000100001000000000001',
'10111011001110100001011110010000100001000000000010',
'10111011001110100001011110010000100001000000000011',
'10111011001110100001011110010000100001000000000100'
]
뭔가 잘 만들어지는 것 같다.