[가상 면접 사례로 배우는 대규모 시스템 설계 기초] 7장 - 분산 시스템을 위한 유일 ID 생성기 설계

분산 시스템에서 사용될 유일 ID 생성기

관계형 데이터베이스의 auto_increment 속성을 사용하면 안되나?

• 분산 시스템 → 데이터베이서 서버 한 대로 버틸 수 있을 것인가?
• 여러 데이터베이스 시스템 → 지연시간/여러 조건 불충족 등의 문제가 발생할 수 있다.

---

1단계, 문제 이해 및 설계 범위 확정

요구사항

• ID는 유일해야 한다.
• ID는 숫자로만 구성되어야 한다.
• ID는 64비트로 표현될 수 있는 값이어야 한다.
• ID는 발급날짜에 따라 정렬 가능해야 한다.
• 초당 10,000개의 ID를 만들 수 있어야 한다.

---

 

2단계, 개략적 설계안 제시 및 동의 구하기

여러 선택지 고려

다중 마스터 복제

앞서 말했듯 데이터베이스의 auto_increment 기능을 활용하는 것

• 1만큼 증가시켜 얻는 것이 아닌 데이터베이스의 수 k 만큼 증가시킨다.
• 겹치지 않고 초당 생산 가능 ID 수를 늘릴 수 있음

단점

• 여러 데이터 센터에 걸쳐 규모를 늘리기 어려움
• 시간 흐름에 맞추어 커지도록 보장할 수 없음
  • 데이터베이스 A, B가 있을 때, A에서만 100개의 ID가 만들어졌다. 그 다음 B에서 처음으로 ID를 생성했다. 그럼 A의 100번째 ID와 B의 첫 번째 ID의 대소관계로 시간의 흐름을 파악할 수 있을까? 없다. A가 더 큰데, B가 더 최신의 ID이므로.
• 서버를 추가하거나 삭제하면 제대로 동작하지 못할 수 있다. k가 변하게 됨.

---

UUID

컴퓨터 시스템에 저장되는 정보를 유일하기 식별하기 위한 128비트 수

장점

• UUID 만드는 것 단순. 중복확률도 진짜 매우 매우 낮음.
• 각 서버가 알아서 만드는 것이므로 규모 확장도 쉬움.

단점

• 128비트로 구성되어 요구사항에 맞지 않다. 길다.
• 숫자가 아닌 값이 포함될 수 있으며, 시간 순으로 정렬할 수 없다.

---

티켓 서버 (Ticket Server)

auto_increment 를 지원하는 데이터베이스 서버를 중앙 집중형으로 하나만 사용하는 것이 아이디어.

자세한 내용은 Flickr 사용사례 참고. 내용은 대략적으로 MySQL의 REPLACE INTO 명령어를 활용해 지원할 수 있다는 내용.

장점

• 유일성이 보장되는 오직 숫자로만 이루어진 ID를 쉽게 만들 수 있음
• 구현하기 쉽고, 중소 규모 애플리케이션에 적합 → 양이 많아지면 관리할 수 없는 정도로 테이블이 커질 수 있다.

단점

• SPOF → 단일 티켓서버 사용 시, 문제 포인트가 될 수 있음.
• 사용사례에서는 이를 막기 위해 2개의 티켓 서버를 사용한다고 함. 동기하는 것은 성능적으로 문제가 될 수 있어서 auto_increment 에 offset을 두고 증가시킴. 결국엔 다중 마스터 복제와 같은 문제가 발생할 것 같음.

---

트위터 스노플레이크 (Twitter snowflake)

위 구조를 사용

• Sign: 1 bit 할당
• Timestamp: 41 bit 할당. 기원시각 이후로 몇 millisecond가 경과했는지 나타내는 값
• Datacenter id: 5 bit 할당. 데이터 센터의 아이디. 5비트이므로 32개의 데이터센터 지원 가능.
• Server id: 5 bit 할당. 서버의 아이디. 5비트이므로 32개의 서버 지원 가능.
• sequence: 12bit 할당. 각 서버에서는 ID 생성시마다 해당 sequence 1씩 증가. 1 millisecond마다 0으로 초기화

---

 

3단계, 상세 설계

트위터 스노우플레이크 구조 사용

• 구조에서 Timestamp, Sequecne 값만 ID 생성시 도중 만들어지는 값 (동적으로 바뀌는 값)

Timestamp 가 가장 큰 비중(41 bit)을 차지함.

 

• 현재 시간을 millisecond로 변환 후 해당 서버의 기원시간을 뺀다. 그 결과를 2진수로 변환해서 사용.
  • 결국 timestamp는 0부터 시작하게 되는 것
• 41 bit로 이루어져있어 시간으로 따지면 최대 69년에 해당하는 값을 나타낼 수 있다. 즉, 해당 ID 생성기는 69년동안만 정상작동함. 69년이 지나면 중복된 ID가 나올 수 있고, 정렬에 따른 ID 생성순서를 표현할 수 없음.

---

 

4단계, 마무리

더 논의할 거리

• 시계 동기화(Clock synchronization)
  • 위에선 서버들이 다 같은 시계를 사용한다고 가정했음. 여러 서버가 물리적으로 독립된 여러 장비에서 돌아가게 되면 서버 시간이 다를 수 있기 때문에 위 방식이 동작하지 않을 수 있음.
  • NTP(Network Time Protocol) 같은 수단을 통해 서버간 시간을 동기화 시킴.
• 어플리케이션에 맞게 구조 변경
  • 트위터 스노우프레이크 → bit 구조가 딱 정해진게 아님. 어플리케이션마다 적절히 변경시켜 적용하면 됨.
  • 동시성이 낮고 수명이 긴 애플리케이션을 개발? → Sequence를 줄이고, Timestamp를 늘리는 것이 효과적일 수 있음.
• 고가용성
  • ID 생성기는 필수적인 컴포넌트(mission critical).
  • 고가용성을 제공해야만 한다.

---

 

책 외에 찾아본 것

• snowflake 구현체
  • twitter는 Github에 snowflake 구현을 archive 해놓았음. Scala로 만들어놓은 것을 확인.
  • java 구현체 (아래주소)
    • synchronization으로 되어있는데, atomic class 사용해서 활용해보기?

GitHub - beyondfengyu/SnowFlake: Twitter的雪花算法SnowFlake，使用Java语言实现。

 

• Snowflake가 그래도 큰 기업에서 많이 활용되었나보다. (by wiki)

Snowflake IDs, or snowflakes, are a form of unique identifier used in distributed computing. The format was created by Twitter and is used for the IDs of tweets. The format has been adopted by other companies, including Discord, and Instagram, which uses a modified version.

 

• ksuid 라는 UUID 생성 라이브러리가 요즘은 핫한 것 같다. 업데이트도 꾸준히 되고 있고, README에 설명도 자세히 나와있다. golang으로 만들어졌지만 여러 언어별 구현체 존재.

 

GitHub - segmentio/ksuid: K-Sortable Globally Unique IDs

why KSUID?
1. Naturally ordered by generation time
2. Collision-free, coordination-free, dependency-free
3. Highly portable representations

A brief history of the UUID | Segment Blog

 

• MySQL, MariaDB 같은 RDB에서 UUID 생성 쿼리가 있음

SELECT UUID();
=> f189f4ae-af11-11e7-b252-186590cec0c1 같은 값 출력

SELECT UNHEX(REPLACE(UUID(),'-',''));
=> '-'를 뺀 뒤 hex digit을 byte로 변환하여 데이터에 대한 최적화

 

• ULID (Universally Unique Lexicographically Sortable Identifier)

GitHub - ulid/spec: The canonical spec for ulid

https://blog.tericcabrel.com/discover-ulid-the-sortable-version-of-uuid/

There are 2⁸⁰ possible ids within a millisecond.

 

UUID와 유사한데 타임스탬프를 사용하기 떄문에 정렬이 가능하다고 함. 아주 적지만 충돌가능성이 있긴한가보다.