유일 ID 생성기 설계 및 snowflake 구현

2023-11-28 • infoqoch •

system-design

•

system-design

요구사항

대규모, 분산 시스템에서 유일 ID를 생성한 시스템을 설계해야 한다. 요구사항은 아래와 같다.
유일한 값을 생성한다.
정렬할 수 있다. ID가 1씩 증가하는 것은 아니지만, 시간이 지날수록 숫자의 크기는 커야 한다.
초당 10,000개(1밀당 10개)의 ID를 생성할 수 있다.
64비트 이하의 용량을 차지한다.

후보

다중 마스터 복제

DB에서 ID를 생성하여 제공한다. auto_increment를 사용한다.
DB의 갯수를 확장하여, 1이 아닌 N씩 아이디를 증가시킬 수 있다.
다만 문제는
- DB 서버를 확장하기 어렵고
- ID 전체를 정렬 했을 때 시간의 순서를 보장하지 않는다.

UUID

128비트이다.
시간 순으로 정렬할 수 없다.
숫자가 아닌 값이 포함된다.

티켓서버

별도의 ID 생성 서버를 둔다.
만들기 쉽다. 다루기 쉽다.
다만 SPOF(Single point of failure) 문제가 발생 한다.

트위터 스노플레이크(twitter snowflake id generator)

64비트의 숫자로 구성된 ID 생성 로직
ID 생성을 위한 별도의 서버나 네트워크를 필요로 하지 않는다.

구성

1비트: sign
- 현재 쓰임새가 없으나 나중을 위해 유보한 값
- 기본값은 0이며 바이너리에서 Long으로 파싱할 경우 언제나 정수로 표현된다.
41비트: 타임스탬프:
- 타임스탬프를 사용하며 최소단위는 밀리세컨이다.
- 시작점은 1970-01-01이 아닌 별도의 시간으로 설정한다.
5비트: 데이터 센터 ID: 2^5개로 32개의 데이터 센터를 지원한다.
5비트: 서버 ID: 하나의 데이터 센터에서 32개의 서버를 사용할 수 있다.
12비트: 일련번호: 각 서버에서는 ID를 생성할 때마다 이 번호를 1씩 증가시킨다. 1밀리초가 경과할 때마다 0으로 초기화 된다.

기타

시계 동기화 clock synchronization : 서버는 같은 시계를 사용해야 한다. NTP(Network Time Protocol)은 보편적인 해결 방식이다.
필요에 따라 각 비트의 갯수를 조절할 수 있다. 동시성이 적을 수록 타임스탬프를 늘리는 것이 유리하다.
ID 생성기는 높은 가용성을 요구 받는다.

snowflake의 구현

snowflake를 직접 구현해봤다.
병렬처리 가능하도록 synchronized를 사용했다. 가능하면 우회하거나 그 범위를 축소해보려 하였지만 좋은 아이디가 나오지 않았다.
4096개를 같은 시간 동안 소모할 경우 while을 사용하여 다음 시간까지 대기하였다.
아래는 비트연산자 «, 등을 사용하였다. int v = 10 << 1;의 형태로 사용 가능하다.

public class SnowFlake {
    private final long worker;
    private final long defaultTimestamp;
    private volatile int sequence = 0;
    private volatile long latestTimestamp = 0;

    public SnowFlake(int node, int app, long defaultTimestamp) {
        this.worker = ((long) node << 5) + app;
        this.defaultTimestamp = defaultTimestamp;
    }

    public synchronized long create() {
        long currentTimestamp = Instant.now().toEpochMilli();
        if(currentTimestamp != latestTimestamp){
            sequence = 0;
        } else if(sequence > 4095 && currentTimestamp == latestTimestamp){
            while((currentTimestamp = Instant.now().toEpochMilli()) == latestTimestamp);
            sequence = 0;
        }
        latestTimestamp = currentTimestamp;

        return (latestTimestamp - defaultTimestamp) << 22
                | worker << 12
                | sequence++;
    }
}

실제 작성한 코드 및 몇가지 테스트 내용은 다음 링크 참고 바랍니다! https://github.com/infoqoch/system-desgin/tree/master/unique-id

“가상 면접 사례로 배우는 대규모 시스템 설계 기초”를 재밌게 읽고 있습니다! 격주로 책의 내용을 정리하고 업로드할 예정입니다.