Loading
2022. 5. 6. 17:07 - lazykuna

Unique ID Generator의 설계

출처: twitter from Alex Xu

어떤 객체를 나타날 때 고유의 ID를 배분하는 것은 중요한 일인데, 근래의 거대한 시스템 (링크드인, 트위터, 페이스북 등)에서는 이를 어떻게 해결하고 있는지에 대한 내용입니다.

요구사항

  • Globally unique 할 것
  • 시간 순으로 정렬이 가능할 것
  • 숫자로 표현이 가능할 것
  • 64-bit 제약
  • Scalable 하면서(= on cluster) 빠른 응답시간이 필요 (low-latency)

선택지

  • DB 기능 사용
    • Single server DB에서만 사용 가능한 기능
    • 사실 cluster DB에서도 사용 가능하긴 함: 다만 이 경우 index pre-allocation을 하는 경우가 있어, 시간순 보장을 일부 못 할 수도 있음. 다만 이를 어느 정도 tolerance 할 경우에는 나름 최선의 선택이라고 봄
  • UUID
    • 생성하기 쉽지만 시간 순으로 발급되지 않음
  • DB ticket server
    • (솔직히 DB 기능 사용하는 거랑 별 반 차이 없다고 보임..)
  • Redis
    • 홀/짝 방식으로 클러스터 구성
    • 단점: scaling에 큰 제약
  • Twitter Snowflake ID
    • 핵심 포인트: unique ID를 구성하는 요소를 timestamp + nodeID + sequentialID 3 가지로 넣어서 64bit ID를 구성하도록 함.
    • globally unique하면서, scaling에도 제약이 없고, time order도 완벽하게 준수할 수 있는 최선의 방법
    • 심지어 ID 생성 할 때 Manager 개념 필요 없이 노드 자체에서 생성이 가능하므로 통신 비용으로 인한 오버헤드도 없어진다!
    • 다만 유일한 제약은 timestamp당 최대 4096개(2^12)의 요청을 처리할 수 있는 셈. ⇒ 일반적인 서비스의 RPS를 고려하면 아주 충분한 수준으로 보임

Cluster 단위에서 unique 해야 함에도 불구하고, 노드 간 통신이 필요없도록 구현했다는 점이 가장 재미있는 포인트네요.

참고