issues
search
meloncha
/
study
0
stars
0
forks
source link
[대규모 시스템 설계 기초] 7장 분산 시스템을 위한 유일 ID 생성기 설계
#7
Open
meloncha
opened
2 years ago
meloncha
commented
2 years ago
1단계. 문제 이해 및 설계 범위 확정
ID의 특성? -> 유일, 정렬 가능
ID는 항상 1만큼 커져야 하는가? -> 시간의 흐름에 따라 커지지만 언제나 1씩 증가하지는 않는다
ID는 숫자로만 구성? -> YES
시스템 규모? -> 초당 10,000 ID 생성 가능해야 한다
요구사항
유일
숫자로만 구성
64비트로 표현될 수 있는 값
발급 날짜에 따라 정렬 가능
초당 10,000개의 ID 생성 가능
2단계. 개략적 설계안 제시 및 동의 구하기
분산 시스템에서 유일성이 보장되는 ID를 만드는 방법
다중 마스터 복제(multi-master replication)
UUID(Universally Unique Identifier)
티켓 서버(ticket server)
트위커 스노우플레이크(twitter snowflake) 접근법
다중 마스터 복제
데이터베이스의
auto_increment
기능을 활용
다음 ID의 값을 구할 때, k(현재 사용 중인 데이터베이스 서버 수)만큼 증가
단점
여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다 -> 전체 데이터 센터의 서버 수 만큼 증가시켜야 해서 그런걸까?
ID의 유일성은 보장되지만, 시간의 흐름에 맞추어 커지도록 보장은 안된다. -> 한 서버에서 ID를 많이 생성하면 다른 서버에 비해 숫자가 너무 커진다
서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다 -> 서버 추가, 삭제시 증가량 K를 다시 설정해야 한다 (전체 서버에 대해서)
UUID
UUID : 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수
서버 간 조율 없이 독립적으로 생성 가능하다
장점
UUID를 만드는 것은 단순하다. 서버 사이의 조율이 필요 없으므로 동기화 이슈가 없다
각 서버가 알아서 만드므로 규모 확장도 쉽다
단점
ID가 128비트로 길다. (요구사항은 64비트)
ID를 시간순으로 정렬할 수 없다
ID에 숫자가 아닌 값이 포함될 수 있다
티켓 서버
auto_increment
기능을 갖춘 티켓 서버를 중앙 집중형으로 하나만 사용
장점
유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다
구현하기 쉽고, 중소 규모 애플리케이션에 적합하다
단점
티켓 서버가 SPOF(Single-Point-Of-Failure)가 된다
이 문제를 해결하기 위해 티켓 서버를 여러 대 준비하는 경우 데이터 동기화 같은 새로운 문제가 발생
트위터 snowflake 접근법
64비트 ID를 여러 section으로 분할
사인(sign) 비트 : 1비트. 나중을 위해 유보. 음수와 양수를 구별
타임스탬프(timestamp) : 41비트. 기원 시각 이후 몇 밀리초가 경과했는지 나타내는 값
데이터센터 ID : 5비트. 32개의 데이터 센터를 지원할 수 있음
서버 ID : 5비트. 데이터 센터당 32개 서버를 사용할 수 있음
일련번호 : 12비트. 각 서버에서는 ID를 생성할 때마다 일련번호 1씩 증가. 1밀리초(타임스탬프 최소 시간) 경과할 때마다 0으로 초기화
3단계. 상세 설계
ID 구조 중 데이터 센터 ID와 서버 ID는 시스템이 시작할 때 결정. 운영 중에는 바뀌지 않는다
타임스탬프나 일련번호는 ID 생성기가 돌고 있는 중에 만들어지는 값
타임스탬프
시간의 흐름에 따라 큰 값을 갖게 되므로 ID는 시간 순으로 정렬이 가능
41비트로 표현할 수 있는 최대값은 대략 69년
69년이 지나면 기원 시각을 바꾸거나 ID 체계를 다른 것으로 이전해야 한다
일련번호
12비트로 4096개의 값을 가질 수 있다. (1밀리초 동안 최대 4096개의 ID 생성을 지원)
1 밀리초 동안 하나 이상의 ID를 만들어 낸 경우 값이 증가
4단계. 마무리
시계 동기화(clock synchronization)
section의 길이 최적화 : 동시성이 낮고 수명이 길다면 일련번호 section을 줄이고, 타임스탬프 section의 길이를 늘리는 것이 효과적이다
고가용성(high availability) : ID 생성기는 필수 불가결 컴포넌트이므로 아주 높은 가용성을 제공해야 한다
meloncha
commented
2 years ago
고민 point
시계 동기화 하는 법
NTP 사용하면 됨...
snowflake 조심해야할 점
멀티스레드로 snowflake 알고리즘을 사용하여 id를 생성하면 동일한 id가 나올 가능성이 있다
여러 인스턴스를 생성하면 인스턴스 간에 숫자가 반복될 수 있다
싱글톤으로 작성해야한다
참고 :
https://programmer.ink/think/implementation-of-snowflake-algorithm-in-singleton-mode.html
UUID 의 대안 : ULID
Universally Unique Lexicographically Sortable Identifier
사전순으로 정렬가능한 UUID
참고 :
https://github.com/ulid/spec
https://velog.io/@injoon2019/UUID-vs-ULID
1단계. 문제 이해 및 설계 범위 확정
요구사항
2단계. 개략적 설계안 제시 및 동의 구하기
분산 시스템에서 유일성이 보장되는 ID를 만드는 방법
다중 마스터 복제
auto_increment
기능을 활용UUID
티켓 서버
auto_increment
기능을 갖춘 티켓 서버를 중앙 집중형으로 하나만 사용트위터 snowflake 접근법
3단계. 상세 설계
타임스탬프
일련번호
4단계. 마무리