[Java] Snowflake

Snowflake란?

• Snowflake는 분산 컴퓨팅 환경에서 고유한 식별자를 생성할 수 있게 해주는 방법을 말한다.
• 트위터에서 개발했다.
• timestamp, machineId, sequence를 64bits 데이터로 관리한다.
• 64bits로 관리하는 이유는 signed long type이 64bits이기 때문인듯 하다.

Snowflake Format

• timestamp
  • 현재시간에서 기준시간을 뺀 값을 말한다.
    • 트위터에서는 기준시간을 2010년쯤으로 잡았다.
  • 42bits로 관리되고, 첫 bit는 양수를 나타내는 bit이다.
  • 실질적으로 41bits를 사용 가능하므로, 2^41 milis 미만의 시간만큼 관리할 수 있다.
    • 1L << 4 - 1 = 대략 34 ~ 35년
  • 서비스가 오래 유지될 것 같다면 timestamp의 bits를 늘린다.
• machineId
  • 다중 서버 환경에서 서버 머신을 구분지을 수 있는(서버별로 유니크한) ID를 말한다.
  • 10bits로 관리된다.
  • 2^10 미만의 machineId를 사용할 수 있다.
    • 1L << 10 - 1 = 최대 512
  • 서버가 여러대 투입이 필요할 것 같다면 machineId의 bits를 늘린다.
• sequence
  • 한 서버에서 동일 시간에 생성된 아이디를 유니크하게 만들어주는 값을 말한다.
  • 12bits로 관리된다.
  • 2^12 미만의 sequence를 사용할 수 있다.
    • 1L << 12 - 1 = 최대 2048
  • 한 서버에 동시 요청이 많이 들어올 것 같다면 sequence의 bits를 늘린다.

예제 코드

@RequiredArgsConstructor
public class Snowflake {
    private final long baseTimestamp;
    private final long machineId;

    private static final AtomicLong sequence = new AtomicLong();
    private static final int TIMESTAMP_BITS = 42;
    private static final int MACHINE_ID_BITS = 10;
    private static final int SEQUENCE_BITS = 12;

    public long generateId() {
        long timestamp = System.currentTimeMillis() - baseTimestamp;
        return (timestamp << MACHINE_ID_BITS + SEQUENCE_BITS) | (machineId << SEQUENCE_BITS) | extract(sequence.getAndIncrement(), SEQUENCE_BITS, 0);
    }

    public Header parse(long id) {
        return new Header(
            extract(id, TIMESTAMP_BITS, MACHINE_ID_BITS + SEQUENCE_BITS) + baseTimestamp,
            extract(id, MACHINE_ID_BITS, SEQUENCE_BITS),
            extract(id, SEQUENCE_BITS, 0)
        );
    }

    private long extract(long value, int bits, int shift) {
        long mask = (((1L << bits) - 1) << shift);
        return (value & mask) >> shift;
    }

    @Getter
    @RequiredArgsConstructor
    public static class Header {
        private final long timestamp;
        private final long machineId;
        private final long sequence;
    }
}

public class SnowflakeTest {
    @Test
    public void testSnowflake() {
        long twitterEpoch = 1288834974657L;
        long machineId = Long.parseLong("0101111010", 2);   // 378
        long id = 1541815603606036480L;

        Snowflake snowflake = new Snowflake(twitterEpoch, machineId);
        Snowflake.Header header = snowflake.parse(id);

        assertEquals(1656432460105L, header.getTimestamp());
        assertEquals(machineId, header.getMachineId());
        assertEquals(0L, header.getSequence());
    }
}

참고

• https://en.wikipedia.org/wiki/Snowflake_ID
• https://github.com/callicoder/java-snowflake