분산 처리 시스템에서 유일한 식별자를 만드는 방법(twitter snowflake)

배경

프로그래밍을 하다 보면 유니크한 식별자 값이 필요한 경우가 있다.

객체를 식별하든 무언가 다른 것과 구분이 필요한 경우로 데이터베이스의 Primary Key나 UUID 같은 것이 그 예다.

필자의 경우 자바, 스프링, JPA 환경에서 프로그래밍을 주로 하는데 무의식적으로 JPA 엔티티의 ID 값으로 Long 타입을 사용했고 데이터베이스에 의존한 시퀀스 또는 auto_increment 값을 사용했다.

그러나 대규모 시스템에서는 이렇게 개발하면 문제가 발생할 수 있다.

대규모 시스템이라는 표현이 어떤 정량적인 방법으로 측정할 수 있는 건 아니어서 애매하지만 여기서는 이렇게 정의하겠다.

🦣 대규모 트래픽 + 대용량의 데이터 처리로 인해 “분산 처리”가 반드시 필요한 경우로 정의한다. (이럴거면 분산 시스템이라고 할 걸(?))

대규모 시스템에서의 문제

대규모 시스템에서는 어떤 문제가 있는지 방법 별로 좀 살펴본다.

1. RDB에 의존하여 Unique ID 생성하기

MySQL의 auto increment나 오라클의 sequence를 사용하면 구현하기도 간단하면서 유일성이 보장되는 ID 값을 생성할 수 있다.

심지어 무작위로 값을 주는 게 아니라 점점 값이 증가하는 방식으로 ID를 생성해주기 때문에 값만 보고도 어떤 게 먼저 생성된 값인지 나중에 생성된 값 인지도 파악할 수 있는 장점이 있다. (단순하게 유일한 키가 아니라 의미도 있는 키다!)

하지만 단점도 있다.

바로 데이터베이스에 의존한다는 것이다.

분산 처리를 하게 되면 여러 애플리케이션 및 미들웨어들이 존재할 텐데 그 많은 애플리케이션이 하나의 데이터베이스를 의존해야만 유일성을 보장받기 때문이다.

관계형 데이터베이스는 특히나 확장에 유연하지 않다. 통상 읽기와 쓰기를 분리하거나 샤딩, 파티셔닝을 사용하는데 쉽지 않다.

2. UUID 생성하기

UUID 유일 키를 생성하기 위한 표준 규격이라고 보면 된다.

eef5b253-8f4b-4544-9cb7-0a588d3f6f04

UUID는 128비트의 숫자이며, 32자리의 16진수(4비트 필요)로 표현된다. 여기에 8-4-4-4-12 글자마다 하이픈을 집어넣어 5개의 그룹으로 구분한다.

UUID 생성 규칙에 따른 버전이 여러 개지만, 책에 의하면 웬만한 규모의 시스템에서는 거의 중복이 일어나지 않을 수 있다고 한다. (아마 이 정도는 장애 내성? 복구?로 처리할 수 있는 정도인 것 같다!)

그뿐만 아니라 데이터베이스와 같은 것에 의존하지 않고도 애플리케이션 내부에서 빠르게 Unique ID를 생성해낼 수 있다는 장점이 있다.

단점은 UUID 버전에 따라 다르겠지만 키에 의미(semantic)를 갖기 어려울 수 있다는 것이다.

가령 RDB의 auto_increment, sequence는 더 크면 나중에 생겼겠구나를 알 수 있었지만 UUID는 그렇지 못한 경우도 있다.

이것보다 더 큰 단점은 크기(128비트 = 16바이트)가 크다는 것이다.

대규모 시스템에서는 저장용량이 다 비용이기 때문에 취약할 수 있다는 것이다.

(🤔 아니 8바이트의 Long 타입은 작고 16바이트의 UUID는 크다고 하니까 좀 억지 같아 보이긴 한다. 그런데 이런 Unique ID를 DB에 저장한다고 생각해보면 8바이트는 BIGINT 같은 타입 즉, 숫자로 관리될 수 있지만 16바이트는 문자열로 관리되어야 하기 때문이지 않을까 하는 상상을 해봤다.)

좋은 방법? snowflake!

지금으로부터 12년 전인 2010년에 트위터에서 분산 시스템에서 유일한 ID를 생성하는 좋은 방법으로 snowflake서비스를 만들었다.

유일한 아이디를 생성하는 동작원리를 알아보기 전에 요구사항을 되새겨 보겠다.

• 요구사항
  • 유일성을 보장해야 함
  • 분산 시스템에서 적합하기 위해서 특정 기술이나 시스템에 의존하지 않아야 함 (병렬 처리 가능)
  • 트래픽이 많으므로 초당 생성 가능한 ID 개수가 여유로워야 함
  • 크기는 작아야 함 (코드 수정 및 마이그레이션까지 생각하면 통상 8바이트)
• 선택적인 요구사항
  • 의미가 있으면 좋음 (ex. 나중에 만들어진 값일수록 숫자가 크다, 어디서 만들어진 것인지)

생성 규칙

총 64비트 크기의 아이디를 만들어낼 것인데 규칙이 있다.

• 처음 1비트는 양의 정수를 다룰 것이므로 항상 0으로 고정해둔다. (맞나?)
• 이후 41비트는 timestamp 값으로 “현재 timestamp(ms) - 기준 시점의 timestamp(ms) 값”이다.
  • 기준 시점은 unix time으로 1970년 1월 1일 자정으로 시킬 수도 있겠으나 오버플로우의 위협에서 벗어나 더 많은 시간 동안 유효하기 위해서 “채번 시작 시의 unixtime 값”을 사용한다.
    • 채번 시작 시간 = 1288834974657 = 2010년 11월 4일 10시 42분 54초
  • 41비트로는 2의 41 제곱, 그러니까 대충 2조 2천억 ms까지 표현 가능하고, 대충 1년이 300억ms니까 10년이면 3,000억 ms, 따라서 약 69~70년이면 2조 ms를 오버플로우 할 수 있기에 꽤나 넉넉하다.
• 이후 10비트는 애플리케이션 또는 장비 고유 번호로 쓰인다.
  • 사용하기 나름인데 5비트씩 두 그룹으로 나눠서 앞에 5비트는 클러스터 ID(=data center ID), 뒤에 5비트는 인스턴스 ID(=worker ID)로 쓰기도 한다.
• 마지막 12비트는 단순히 채번을 위한 1씩 증가하는 시퀀스다.

이렇게 64비트를 사용하여 유일 키를 만들어낸다.

앞선 요구사항들도 만족했는지 살펴본다.

• 유일 키를 보장할 수 있다.
• 특정 기술이나 시스템에 의존하지 않는다. 즉, 병렬 처리가 가능하다.
• 초당 생성할 수 있는 아이디 수가 넉넉하다.
  • 단순 계산해서 시퀀스 12비트로 1ms 당 4,096개의 유일한 아이디를 생성할 수 있으니 1초(1000ms) 당 4,096,000개의 아이디를 생성할 수 있으니 이론만으로는 충분히 대용량을 처리할 수 있어 보인다.
• 크기도 64비트로 적은 공간을 사용한다.
• 타임스탬프 값을 앞 쪽 비트 자리에 배치하여 시간이 지남에 따라 점점 커지는 값이기 때문에 큰 값일수록 나중에 만들어진 것을 확인할 수 있는 의미를 가지며, 나아가 어떤 데이터 센터에서 어떤 인스턴스가 생성한 키라는 것도 알 수 있다.

No Silver Bullet

은탄환은 없다.

뭔가 이론상 완전체처럼 느껴질 수 있으나 또 다른 이슈를 살펴보자.

시스템 시간에 의존한다.

데이터베이스 같은 시스템에 의존하지 않는 대신 시스템 시간에 의존한다.

즉, 분산 시스템에 있는 모든 인스턴스가 같은 시스템 시간을 보장할 수 있어야 한다. (NTP 도 보장해주진 않음…)

만약 하나의 인스턴스의 시스템 시간이 1초 정도 미래라고 가정해보면 해당 인스턴스에서 생성된 키는 다른 인스턴스에서 생성된 키 값보다 크다. (=진짜 나중에 생성된 값이 아닌 게 생긴다.)

라이브러리 VS 서버

시스템에 의존하지 않으니 라이브러리로 만들어서 사용하게 되면 위와 같은 시스템 시간이 문제다.

그렇다고 속칭 ID generator 서버를 만들면 ID generator 서버는 항상 서비스 가능한 상태를 유지하기 위한 비용이 많이 드는 문제가 있다.

뿐만 아니라 코드도 섬세하게 구현해야 할 것이다. 예를 들면 한 번에 N개의 아이디를 채번할 수 있는 API를 제공하는 그런 것까지 말이다.

또 다른 이슈

자바스크립트는 정수의 표현이 53비트로 제한되어있는 문제가 있다. (snowflake로 생성한 아이디를 사용하는데 문제가 있다.)

브라우저 자바 스크립트 콘솔에서 (10765432100123456789).toString() 명령을 실행하면 결과는 "10765432100123458000"이 된다. 64 비트 정수는 정확도를 잃게 된다.

그래서 자바스크립트에서는 snowflake로 생성된 아이디를 ‘문자열’로 다뤄야 하는 이슈가 있다.

결론

결과적으로 애매한 중, 소규모에서 snowflake와 같은 아이디어를 적용하기에는 사실 오버 엔지니어링에 가깝고 정말 큰 서비스를 제공해야 하는 경우에 영감을 받아볼 수 있을 것 같다.

잘못된 내용이 있으면 고칠 수 있도록 도와주시면 감사하겠습니다!

• 참고 자료 / 사이트
• https://darkstart.tistory.com/147
• https://en.wikipedia.org/wiki/Snowflake_ID#/media/File:Snowflake-identifier.png