Snowflake 기반 분산 ID 생성기 구현기

대규모 트래픽 환경에서 충돌 없이, 정렬 가능한 64비트 고유 ID를 생성하기 위해 구현
여러 MSA에서 사용하기 위해 가장먼저 primary-id 생성기를 구현

구현 배경

기존 시스템에서 UUID를 Primary Key로 사용하고 있었지만, 다음과 같은 한계에 직면했다:
- 정렬되지 않아서 인덱스 삽입 비용 증가
- 16바이트 문자열로 비효율적인 저장/전송
- 멀티 인스턴스 환경에서 충돌 방지 전략 필요

그래서 Twitter의 Snowflake 알고리즘을 참고해, 시간순 정렬 가능한 64비트 정수형 ID 생성기를 직접 구현했다.

구현 목표

ULID처럼 정렬 가능한 ID
수천 개 동시 요청에서도 중복 없는 ID 보장
여러 노드에서 실행 시에도 충돌 방지 가능
최소한의 외부 의존성으로 단독으로 작동

아키텍처 및 구성

✔ ID 구성 구조 (64비트)

필드	비트 수	설명
timestamp	41 bits	커스텀 epoch 기준 밀리초
nodeId	10 bits	인스턴스 구분을 위한 노드 ID
sequence	12 bits	동일 밀리초 내 시퀀스
합계	63 bits	부호 비트 없이 사용 가능

코드 구조

primary-id-provider/
├── Snowflake.java
├── SnowflakeProperties.java
├── SnowflakeConfig.java
└── application.yaml

구현 코드 (Snowflke.java)


/**
 * Snowflake ID Generator
 * - Time-ordered 64-bit unique ID
 * - Custom epoch
 * - Supports multiple nodes
 *
 * Author: MyungJoo
 * Date: 2025-06-17
 */
public class Snowflake {

    // ===== Bit Allocation =====
    private static final int NODE_ID_BITS = 10;
    private static final int SEQUENCE_BITS = 12;

    private static final long MAX_NODE_ID = (1L << NODE_ID_BITS) - 1;
    private static final long MAX_SEQUENCE = (1L << SEQUENCE_BITS) - 1;

    private static final int NODE_ID_SHIFT = SEQUENCE_BITS;
    private static final int TIMESTAMP_SHIFT = NODE_ID_BITS + SEQUENCE_BITS;

    // ===== Custom Epoch: 2024-01-01T00:00:00Z =====
    private static final long CUSTOM_EPOCH = 1704067200000L;

    // ===== Instance Variables =====
    private final long nodeId;
    private long lastTimestamp = -1L;
    private long sequence = 0L;

    /**
     * @param nodeId [0, 1023]
     */
    public Snowflake(long nodeId) {
        if (nodeId < 0 || nodeId > MAX_NODE_ID) {
            throw new IllegalArgumentException("Node ID must be between 0 and " + MAX_NODE_ID);
        }
        this.nodeId = nodeId;
    }

    /**
     * Generate next unique ID
     */
    public synchronized long nextId() {
        long currentTimestamp = currentTime();

        // Clock rollback handling
        if (currentTimestamp < lastTimestamp) {
            // Option 1: wait for time to catch up (soft fail)
            currentTimestamp = waitNextMillis(lastTimestamp);
        }

        if (currentTimestamp == lastTimestamp) {
            sequence = (sequence + 1) & MAX_SEQUENCE;
            if (sequence == 0) {
                // Sequence overflow: wait for next millisecond
                currentTimestamp = waitNextMillis(currentTimestamp);
            }
        } else {
            sequence = 0;
        }

        lastTimestamp = currentTimestamp;

        return ((currentTimestamp - CUSTOM_EPOCH) << TIMESTAMP_SHIFT)
                | (nodeId << NODE_ID_SHIFT)
                | sequence;
    }

    /**
     * Busy-wait for next millisecond
     */
    private long waitNextMillis(long lastTimestamp) {
        long timestamp = currentTime();
        while (timestamp <= lastTimestamp) {
            Thread.yield(); // Reduce CPU waste
            timestamp = currentTime();
        }
        return timestamp;
    }

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

테스트

테스트: 동시성 검증

JUnit + ExecutorService 기반의 멀티스레드 테스트를 작성했다:

/**

Author: MyungJoo
Date: 2025-06-17

/
public class SnowflakeConcurrentTest {

private final Snowflake snowflake = new Snowflake(1L);

@Test
void generateIdsConcurrently_withoutDuplicates() throws InterruptedException {

  int threadCount = 100;
  int idsPerThread = 1000;
  ExecutorService executor = Executors.newFixedThreadPool(threadCount);

  Set<Long> allIds = Collections.synchronizedSet(new HashSet<>());
  CountDownLatch latch = new CountDownLatch(threadCount);

  for (int i = 0; i < threadCount; i++) {
      executor.submit(() -> {
          for (int j = 0; j < idsPerThread; j++) {
              long id = snowflake.nextId();
              allIds.add(id);
          }
          latch.countDown();
      });
  }

  latch.await(); // 모든 스레드 종료까지 대기
  executor.shutdown();

  int expected = threadCount * idsPerThread;
  assertEquals(expected, allIds.size(), "ID 중복 발생 가능성 있음");

  System.out.println("Generated " + allIds.size() + " unique IDs successfully.");

}
}

```

결과: 100,000개의 동시 요청에서도 충돌 없이 안전하게 ID 생성

728x90