Table of Contents

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'
]

뭔가 잘 만들어지는 것 같다.

Author: Younghwan Nam

Created: 2024-04-16 Tue 10:05

Emacs 27.2 (Org mode 9.4.4)

Validate