Snowflake ID Generator

보통 애플리케이션을 개발 할 때, DB 테이블의 식별자(PK)를 설계할 때, 비즈니스와 상관없이 데이터를 식별할 수 있도록 인조키를 많이 사용한다.

그렇다면, 식별자를 생성하는 방법은 어떤 것들이 있을까?

 

DB 에서 식별자 생성하기

MySql 은 PK를 자동 채번해주는 auto-increment 기능을 제공한다. 애플리케이션 서버에서 데이터를 생성할 때, PK를 직접 할당해주지 않고, DB에 insert 를 요청하면 DB 에서 알아서 PK를 채번해준다. 애플리케이션이 간단할 때는 이점이 많지만, 조금만 서비스가 커지면 단점이 드러난다. 한번에 다건 insert 를 못한다던지, 애플리케이션 서버에서 데이터 저장 후 식별자를 알기 위해서는 DB에서 조회를 한번 해와야한다던지 성능 부분에서 고려할 부분이 발생한다.

 

티켓 서버에서 식별자 생성하기

식별자를 생성해주는 티켓 서버를 하나 두고, 여러 분산 애플리케이션에서는 해당 티켓 서버로 요청하여 식별자를 받아와서 데이터 저장하는 방법도 있다. 예를들어, 레디스(Redis)에 테이블 별 시퀀스 값을 저장해두고, 애플리케이션에서 요청할 때마다 시퀀스 값을 증가 시킨 후 전달해주는 방식으로 설계할 수 있다. DB 에 저장하기 전에 티켓 서버에 요청하여 식별자를 얻어오고, 해당 식별자로 저장하기 때문에 애플리케이션에서 다건 insert 가 가능하고, 식별자를 알기 위해 DB 조회를 별도로 할 필요가 없다는 점은 장점이다. 하지만, 티켓 서버가 SPOF (Single point of failure) 가 되며, 네트워크 통신 비용이 추가된다. 물론, 티켓 서버에 식별자를 요청할 때, delta 값을 파라미터로 전달하여 원하는 갯수만큼 식별자를 증가시킨 후 받아오는 방법으로 통신 비용을 줄일 수는 있다.

 

UUID 생성하기

Java 를 포함하여 많은 언어에서 UUID를 생성할 수 있는 기능을 제공한다. 별도로 개발이 필요한 부분이 없어서 간편하다는 장점이 있지만 식별자로써 다소 용량(128비트)이 크다는 부분과 식별자만 봐서는 어떤 데이터가 먼저 생긴지 구분 할 수 없는등의 단점들도 존재한다.

 

Twitter Snowflake 방식으로 생성하기

2010년에 트위터에서 발표한 분산 처리 시스템에 적합한 ID 생성 알고리즘이 있다. 64비트 공간에 timestamp, 서버ID, 시퀀스 등의 정보를 담아 여러 분산 애플리케이션에서 요청해도 고유한 ID 를 생성해주도록 설계되었으며, 다음과 같은 특징을 갖고 있다.

• 분산 시스템으로부터 유일한 ID를 보장할 수 있다.
• 동시성 이슈가 없다. (병렬 요청에도 고유한 ID를 반환)
• 초당 생성할 수 있는 ID 수가 넉넉하다. (동일 애플리케이션 내에서 1밀리초당 4096개 생성 가능)
• 64비트라는 작은 공간을 사용한다. (128비트 UUID 에 비해)
• ID로부터 생성시간, 생성된 서버를 유추할 수 있다.

그렇다면, 트위터 스노우플레이크 방식의 ID 는 어떻게 만들어질까?

 

Twitter Snowflake bit 구성

• 부호 (1bit)
  • ID를 양의 정수로 생성하기 위해 항상 0으로 채운다.

 

• 타임스탬프 (41bit)
  
  • ID 생성을 요청한 시간의 epoch timestamp 값에서 기준 시간의 epoch timestamp 값을 뺀 값을 저장한다.
  • 밀리초 epoch time 을 사용하기 때문에 밀리초 단위의 정밀도를 보장한다.
  • 41bit 를 모두 1로 채우면 2의 41승 - 1 인 2,199,023,255,551 인데, 1년을 밀리초로 계산하면 31,536,000,000 (365 * 24 * 60 * 60 * 1000) 이므로 기준 시간으로부터 약 69.73년 (2,199,023,255,551 / 31,536,000,000) 동안 고유한 ID 생성이 가능하다.

 

• 서버ID (10bit)
  • 분산 서버 ID를 저장한다.
  • 2의 10승인 1024개의 서버까지 고유한 ID 생성을 보장한다.

 

• 시퀀스 (12bit)
  • 하나의 서버에서 1millisecond 이내의 4096개 (2의 12승)의 요청까지 수용할 수 있다.
  • 만약, 1millisecond 이내에 4096개를 초과한 요청이 온다고 하더라도, 시퀀스를 4095까지 증가시킨 후 1millisecond 지날때까지 약간 기다렸다가 다시 0부터 시작해서 시퀀스를 증가시킨다. 

 

회고

개인적으로 Twitter snowflake 방식의 ID 생성기를 개발해보니 분산 시스템에서는 사용하기 괜찮은 ID 생성기일 것 같다.

물론, 단점도 존재하지만 그럼에도 장점이 커 보인다.

 

다음은 github repository 링크이다.

https://github.com/baker-1ee/snowflake-id-generator

GitHub - baker-1ee/snowflake-id-generator: Java distributed Unique ID generator inspired by Twitter snowflake.

 

마지막으로, snowflake 의 장점과 단점을 정리해보았다.

 

장점

• 고유한 ID 생성: 분산 시스템에서 고유한 ID를 생성하기 위한 가장 일반적인 방법 중 하나입니다. 이를 통해 중복된 ID가 발생하는 것을 방지할 수 있습니다.
• 높은 확장성: 분산 시스템에서 사용하기에 적합한 알고리즘으로, 대규모 시스템에서도 효과적으로 작동합니다.
• 간단한 사용: 사용하기에 간단합니다. 서버 실행 시 하나의 인스턴스만 생성해두고 ID 생성이 필요한 곳에서 사용하면 됩니다.

단점

• 시스템 시계와의 의존성: 시스템의 시계와 밀접한 연관이 있습니다. 특정 서버의 시스템 시계가 다른 서버보다 빠르다면, 해당 서버에서 생성하는 ID의 타임스탬프는 항상 빠를 것 입니다.
• 타임스탬프 오버플로우: 41비트의 타임스탬프를 사용하여 ID를 생성합니다. 이러한 이유로, 시스템 시작 이후 69년이 지나면 오버플로우가 발생할 수 있습니다. 이 문제를 해결하기 위해서는 서버ID 비트를 줄이고, 타임스탬프 비트를 늘리는 방식으로 보완 가능합니다.
• 이기종 통신시 주의 : Javascript 와 같이 부동소수점 숫자체계를 사용하여 정수를 저장하는 경우, 2의 53승 이상의 정수를 근사값으로 저장하기 때문에 주의가 필요함. 문자열로 주고 받는 등의 처리로 해결 가능함

 

단점의 마지막 Javascript 관련 내용은 Javascript 에서 9천조 이상의 숫자를 다룰때 고민할 부분에서 정리하였다.