7. 분산 시스템을 위한 유일 ID 생성기 설계

• 전제 조건을 정해보자
  • ID는 유일해야 하고, 정렬이 가능해야 한다
  • 새로 만든 ID는 이전에 만든 ID보다 큰 값일 것이다
  • ID는 숫자로만 구성되어야 한다 (?)
  • ID는 발급 날짜에 따라 정렬이 가능해야 한다
  • 초당 1만 개 이상의 ID를 만들 수 있어야 한다
  • ID는 64비트로 표현될 수 있는 값이어야 한다. (128 비트는..?)

다중 마스터 복제 (multi-master replication)

• DB의 AutoIncrement 기능을 이용하는 방법이다
• DB 수 만큼 ID 값을 증가시키는 것을 의미한다
  • ex) 3대의 DB가 존재한다면
    • 첫 번째 DB : 1, 4, 7, 10 ...
    • 두 번쨰 DB : 2, 5, 8, 11 ...
    • 세 번째 DB : 3, 6, 9, 12 ...
• 규모 확장성 문제를 어느정도 해결할 수 있지만 중요한 단점이 존재한다

다중 마스터 복제의 단점

• 여러 데이터 선테어 걸쳐 규모를 늘리기 어렵다
• ID의 유일성을 보장 되겠지만, 그 값이 시간 흐름에 맞추어 커지도록 보장할 수는 없다.
  • 여러 DB에서 ID를 정해진 규칙대로 생성하기에 ID 생성 시간에 따라 실제 ID 더 클 수도, 작을 수도 있다
• 서버를 추가하거나, 삭제할 때도 잘 동작하도록 만들기 어렵다.
  • 서버를 추가하거나, 삭제하면 Auto Increment 값을 재설정 해줘야 한다

UUID (Universally Unique Identifier)

• UUID는 유일성이 보장되는 ID를 만드는 또 하나의 간단한 방법이다
• 정보 식별을 위해 128 bit를 사용한다
• 중복 UUID 1개가 생길 확률을 50%로 끌어 올리려면 10억 개의 UUID를 100년 동안 계속 생성해야 한다고 한다
• UUID를 사용하면 각자의 DB 서버가 각자의 UUID 생성기를 사용해도 괜찮다. (유일성이 보장되기 때문이다)

UUID의 장점

• UUID를 만드는 방법은 단순하다
• 각 DB 서버가 각자 독립 된 UUID 생성기를 관리하기에, 동기화 이슈가 없다
• 각 DB 서버가 각자 독립 된 UUID 생성기를 관리하기에, 규모 확장이 쉽다

UUID의 단점

• ID가 128 bit로 길다
• ID를 시간순으로 정렬할 수 없다
• ID에 숫자가 아닌 값이 포함될 수 있다

티켓 서버(ticket server)

• Auto Increment 기능을 하는 중앙 서버를 두고, 각 어플리케이션 서버에서 중앙 서버에게 ID 값을 요청한다
• flickr 의 티켓 서버 사용 예시

티켓 서버의 장점

• 유일성이 보장 되는 숫자로만 구성 된 ID 값을 쉽게 만들 수 있다
• 구현이 쉽고, 중소 규모의 어플리케이션에 적합하다

티켓 서버의 단점

• SPOF (Single Point of Failure)가 된다.
• 중앙 서버(티켓 서버)에 장애가 발생하면, 그 영향범위가 전체 서비스까지 번진다
• 그렇다고 중앙 서버(티켓 서버)를 여러 대 사용하면 데이터 동기화 이슈를 해결해야 한다는 단점이 있다

트위터 스노플레이크(twitter snowflake) 접근 법

• ID 생성에 격파 전략 (divide and conquer) 적용한 방법이다
• ID 의 구조를 여러 절(section)으로 분할한다
• 64bit 길이의 ID 구조이다
• bit 단위 분석
  • Sign 비트
    • 1 bit
      • 음수와 양수를 구분하는 등 나중에 사용할 것을 대비해 유보해 놓는 필드이다
  • Timestamp 비트
    • 2 bit ~ 42bit (41bit)
      • 기원 시각(epoch) 이후로 몇 밀리초가 경과했는지 나타내는 값이다
      • 41 비트를 밀리초 단위로 사용할 수 있다
        • 2^41 - 1 로 계산해보면 41비트로 표현 가능한 밀리초는 2조 1990억 밀리초 이며, 년 단위로 환산하면 약 69년에 해당한다
        • 따라서 69년이 지나기 전에 epoch(기원 시각) 을 바꾸거나, ID 체계를 다른 것으로 이전해야 한다
  • 데이터센터 ID 비트
    • 43 bit ~ 47 bit (5bit)
      • 2^5로 계산해보면 약 32개의 데이터 센터를 지원할 수 있다
  • 서버 ID 비트
    • 48 bit ~ 52 bit (5bit)
      • 2^5로 계산해보면 약 32개의 서버를 사용할 수 있다
  • 일련 번호
    • 53 bit ~ 64 bit (12bit)
      • 각 서버에서 ID를 생성할 때마다 일련번호를 1만큼 증가시킨다
      • 이 값은 1 밀리초가 경과할 때마다 0으로 초기화 된다
      • 일련 번호는 12 비트로 약 4096개의 ID 값을 가질 수 있다. 한 서버는 1 밀리초에 4096개의 ID를 생성할 수 있다
      • 4096이라는 값은 정확한 계산에 기반하여 설계가 가능해야 한다. 예를 들어 1밀리초에 40000 개의 요청이 들어오는 서비스를 예로 들면 약 9대의 서버를 사용하도록 설계해야 한다