Ticket Servers: Distributed Unique Primary Keys on the Cheap

https://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/

flicker 구성 기본정보 MySQL 샤드는 복원력을 위해 master-master replication 쌍으로 구축. (이것은 주요 충돌을 피하기 위해 샤드 내에서 고유성을 보장할 수 있어야 한다는 것을 의미한다.)

GUIDs?

(UUIDs와 유사한 개념. UUIDs가 더 큰 개념.) globally unique id가 분명히 필요한 상황에서 GUIDs를 사용하면 왜 안될까? 대부분 GUIDs가 커서 mysql에서 인덱스하는게 좋지 않기 때문이다.

Consistent Hashing?

Amazon의 Dynamo와 같은 몇몇 프로젝트는 GUID/sharding 문제를 처리하기 위해 데이터스토어 상단에 일관된 해싱 링을 제공한다. write-cheap에는 좋지만, mysql은 빠른 랜덤 읽기에 최적화 되어 있다.

Centralizing Auto-Increments

MySQL auto-increments가 여러 데이터베이스에 걸쳐 작동하도록 할 수 없다면 하나의 데이터베이스만 사용하자.

SPOFs

HA를 위해 두대의 티켓서버를 운영하고 있다. 서버간 쓰기(/업데이트) 복제는 문제가 있을 수 있고 락은 성능을 떨어뜨릴 수 있다. ID공간을 중간, 짝수 홀수로 나누어서 서버 간 책임을 나눈다.

TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1

TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2

multi-master replication + ticket server 책에서 설명한 이 두개를 합쳐 구성했군

System design : Distributed global unique ID generation

https://medium.com/@sandeep4.verma/system-design-distributed-global-unique-id-generation-d6a440cc8e5

유니크 id를 만드는 방식에는 여러 목적이 있다.

고정된 사이즈의 랜덤한 unique id (이 경우 정렬 효율이 좋지는 않음)
순서가 보장된 unique id (auto-incrementing primary key)
고정 크기 + 순서 보장 -> Tweet Ids / Instagram Image id 등등

GUIDs

GUID는 보통 128비트의 유니크함이 보장된 값이다. (ex. 30dd879c-ee2f-11db-8314-0800200c9a66) 32 hex digit로 되어있고 8 - 4 - 4 - 4 - 12 의 chunk로 되어있어 2^128 개의 값을 생성할 수 있다.

보통 time base GUID를 사용하여 순서를 보장하지만 결국 2^128 개의 숫자한계가 있어서 collision 이 발생할 수 있음

ObjectID’s of MongoDB

12바이트로 구성된 몽고디비의 오브젝트 id 는 다음과 같이 구성된다.

4-byte timestamp value
5-byte random value
3-byte incrementing counter, initialised to a random value

결국 오브젝트id는 타임 베이스로 구성되어 정렬이 가능하나.. 64비트를 넘는 값이기 때문에 많은 용량을 차지한다.

Ticker Server — Flickr Ticketing Service

하나의 노드로 이루어진 데이터베이스는 SPOF가 발생하고 짧은 순간에 write 요청이 몰리면 이를 대처할 수도 없다.

이를 위해 두 TicketServer 예시를 들자. 두 티켓 서버는 각자의 offset을 가지고 auto-increment를 선언할텐데, 문제는 두 서버 중 어느 서버가 먼저 선언했는지 모른다는 것이다. 분산 디비를 사용하면 각자의 unique key의 정렬을 보장할 수 없다.

Snowflake from Twitter

(책에서 나온 것 처럼) 트위터는 이를 해결하기 위해 snowflake를 제안했다. 64bit id는 다음과 같이 구성된다.

timestamp(41bits)
worker number(10bits)
sequence number(12bits)
1bit future value

우리는 1024개의 노드까지 커버할 수 있다.

장점

UUID의 절반인 64bits로 구성됐다.
타임스탬프를 사용하여 정렬이 가능하다.
분산디비에서 사용 가능

단점

노드와 머신 ids를 관리하기 위해 Zookeeper가 필요
추가적인 snowflake 서버와 복잡성을 가져옴

Instagram Id generation

인스타의 id는 snowflake의 zookeeper를 피하기 위해 다음과 같이 구성돼있다.

밀리초의 시간 (41bits)
논리적 샤드 id (13bits)
1024로 나눈 나머지를 사용한 auto-incrementing sequence -> 밀리초당 1024개의 ID와 샤드를 가질 수 있음

2011년 9월 9일 오후 5시라고 하면 인스타그램의 epoch 시간은 2011년 1월 1일 기준이므로 1387263000 밀리초가 할당된다. 41bits만 사용하므로 64bit를 left shift 시킨다.

id = 1387263000 <<(64-41)

2000개의 논리적 샤드가 있다고 하고 userId 는 31341개가 있다고 한다면 31341 % 2000 -> 1341 이것을 13bits에 맞게 left shift시킨다.

id |= 1341 <<(64-41-13)

이 노드에서 5000개가 이미 생성됐다면 이제 5001 번째 auto-increment 값이 생성될 것이고 이를 1024로 나눈 나머지를 구한다.

id |= (5001 % 1024)

이렇게 하면 앞의 41bits의 시간 데이터로 정렬이 가능하고 논리적 샤드는 Postgres’ Schemas를 사용하기 때문에 주키퍼 없이 사용 가능하다.

Announcing Snowflake

https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake

The Problem: Snowflake 가 등장하게 된 배경

초기에는 MySQL 인스턴스 한대로 시작했으나, 서비스가 커지면서 커다란 데이터베이스 클러스터를 관리하게 되었음.
시스템 중 다수를 Cassandra 분산DB, 혹은 수평으로 샤딩된 MySQL (gizzard를 사용) 로 교체하기 위해 노력하고 있음.
MySQL 은 자체 build-in unique id generation 이 가능하지만, Cassandra, shared MySQL 은 제공하지 않았다 (큰 규모에서 모든 용도를 만족하는 단일 솔루션을 제공하기가 어려움)

요구사항

We needed something that could generate tens of thousands of ids per second in a highly available manner.

These ids need to be roughly sortable

Additionally, these numbers have to fit into 64 bits.

roughly sorted 란?
- exactly sorted 라기 보단, almost sorted.
- 비슷한 시간에 올라온 트윗이 id 체계 상에서도 근접해있길 원한다.
- k-sorted
- what is k-sorted?
  - no item is no more than K positions from it's totally ordered position
  - 알고리즘 문제: Sort a nearly sorted (or K sorted) array
- k 의 값을 1초 미만으로 유지하는 것을 목표
- 1초 내에 게시된 트윗이 id 공간에서도 1초 내에 게시된다는 의미.

Options: 고려해본 수많은 옵션들.

MySQL-based ticket servers (like flickr uses)
- 순서 보장이 어려웠음.
UUIDs
- 128bits 스키마라, 64 bits 를 만족하지 못함.
Zookeeper sequential nodes
- 성능적 이득이 없었음.
- 실질적인 보상 없이 가용성이 낮아질까봐 두려웠음

Solution

3가지 구성요소: timestamp, worker number and sequence number.
sequence number 는 thread 당 부여된다.
worker number 는 기동 시 zookeeper 를 통해 선택된다.

지금의 snowflake

2010년에 공개된 snowflake 의 초기 릴리즈는 중단된 상태.
- snowflake 의 내부 구현에 크게 의존된 형태였기 때문.
현재의 twitter IDs 체계는 여전히 snowflake 구현에 기반.
- https://developer.twitter.com/en/docs/twitter-ids
can cause issues with programming languages that represent integers with fewer than 64-bits
- ex) JavaScript : integers are limited to 53-bits in size
- two formats: both as integers, and as strings 을 제공한다
```
{"id": 10765432100123456789, "id_str": "10765432100123456789"}
```

Network Time Protocol

https://en.wikipedia.org/wiki/Network_Time_Protocol

NTP

네트워크 시간 조정 프로토콜로서, 분산 시스템의 경우, 각 시스템이 로컬 시계들을 각자 갖고 있는데, 이러한 시계가 실제 시간 혹은 다른 시스템과 많이 상이한 경우가 있을 수도 있다.

이러한 문제는, 책에서 본 분산 시스템에서 unique id를 설계할 때, timestamp 를 고려하는 경우 문제가 될 수 있기 때문에, NTP를 통해서 해결할 수 있다.

NTP를 통해서 시간을 조정하는 방법

데이터 수집: 클라이언트는 여러 NTP 서버로부터 delay와 offset 값을 수집한다.

# 타임스탬프 교환:

# 클라이언트는 요청 메시지를 서버에 보낼 때 T1 타임스탬프를 첨부합니다. 이는 요청 메시지를 보내기 시작한 시점의 클라이언트의 시간을 나타냅니다.
# 서버는 요청 메시지를 받을 때 T2 타임스탬프를 생성합니다. 이는 서버가 요청을 받은 시점의 시간을 나타냅니다.
# 서버는 응답 메시지를 클라이언트에 보낼 때 T3 타임스탬프를 첨부합니다. 이는 응답 메시지를 보내기 시작한 시점의 서버의 시간을 나타냅니다.
# 클라이언트는 응답 메시지를 받을 때 T4 타임스탬프를 생성합니다. 이는 클라이언트가 응답을 받은 시점의 시간을 나타냅니다.

Delay = (T4 - T1) - (T3 - T2)
Offset = ((T2 - T1) + (T3 - T4)) / 2

정렬: 수집된 값들 중에서 delay 값을 기준으로 정렬합니다. 일반적으로, 더 낮은 delay 값은 더 좋은 네트워크 연결을 의미하므로 이러한 서버들이 우선적으로 고려된다.

Stratum 검토: NTP는 계층적 구조를 가지고 있으며, 각 서버는 stratum 레벨을 갖습니다. Stratum 0은 고정된 시간 소스 (예: 원자시계)를 나타내며, stratum 1은 stratum 0 소스에 직접 연결된 서버를 나타냅니다. Stratum 값이 증가할수록 그 서버는 기준 시간 소스에서 더 멀어집니다. 더 낮은 stratum을 가진 서버는 일반적으로 더 선호된다.

신뢰성 평가: 서버가 제공하는 시간 값들의 일관성과 안정성을 평가. 이 평가는 서버들 간의 offset 값들의 분산을 비교하여 수행될 수 있음. 너무 큰 offset 값을 가진 서버는 불안정할 수 있으므로 제외될 수 있다.
Falsetickers 제거: Intersection Algorithm과 같은 알고리즘을 사용하여 오류가 있는 서버 (falsetickers)를 식별하고 제외한다.
- Intersection Algorithm Intersection Algorithm을 이해하기 쉽게 설명하기 위해 간단한 예시를 보자. 다음과 같은 시간 소스들로부터의 응답을 가정해 보자.
서버 A: 10 ± 1 -> [9,11] 서버 B: 10.5 ± 0.5 -> [10,11] 서버 C: 11 ± 1 -> [10,12]

이렇게 되면 Intersection 부분이 [10, 11]로 정해지는데, intersection에 가장 적합한 후보는 "서버 B"가 되므로, 가장 적절한 서버를 필터링 할 수 있게 된다.

최적의 시간 소스 선택: 위의 단계들을 통해 가장 적절하다고 판단되는 서버를 선택. 일반적으로, 가장 낮은 delay와 stratum 값을 가진, 그리고 offset의 분산이 작은 서버가 선택된다.
시간 조정: 선택된 서버로부터 받은 offset 값을 사용하여 로컬 클라이언트의 시계를 조정합니다. 이 조정은 급격한 시간 변경을 피하기 위해 점진적으로 수행될 수 있다.

시간 변경

즉시 조정: offset 값이 크게 차이 나는 경우 (예: 클라이언트의 시간이 몇 분 또는 몇 시간이나 늦거나 빠른 경우), 시간을 즉시 조정하여 서버의 시간과 일치시킬 수 있다. 하지만 이런 방식은 로그 파일, 데이터베이스 트랜잭션 등 시간에 민감한 작업에 문제를 일으킬 수 있다.
점진적 조정 (slewing): 대부분의 경우, NTP는 offset을 점진적으로 조정하는 방식을 사용. 이는 시계의 진행 속도를 약간 빠르게 또는 느리게 조절하여 offset을 조금씩 줄여나가는 방식. 이 방식은 시스템에서 발생하는 시간 관련 문제를 최소화하면서 시간을 정확하게 조정한다.

data-tech-newbie / system-design-interview

Chapter 7: Design a unique id generator in distributed systems #5