[서버]Distributed System Twitter id 생성(Snowflake)

트위터에 이런 좋은 자료도 있군요. 무려 10년 전의 자료입니다.

너무 길어서.. 그냥 구글 번역기에서 돌린 번역 내용과 원본 내용을 같이 붙입니다.

 

일반적으로 MySQL에서 id를 보면 unsigned 32bit라서.. 0~약42억 개의 수를 생성할 수 있습니다. 그런데 트위터같은 초거대 시스템에선 42억개의 id로도 부족하기에 64bit를 id를 저장하는데 씁니다. unsigned big int의 경우 범위가

0~18,446,744,073,709,551,615 라고 합니다. 약 18*10^18의 값을 가집니다. 

unsigned int가 42억 = 42*10^9의 값이니.. big int는 그냥 int보다 수십억배 큰 값입니다. 아마.. 이 값을 다 채우기는 쉽지 않을 것 같네요.

 

또 다른 문제로는 Distributed System에서 초당 수만개의 id를 생성하는 경우 어떻게 각 서버에서 고유한 id 값을 가지느냐 입니다. 하나의 서버에서 Sequential하게 id를 생성할 수 있지만.. 그러면 수많은 다른 서버들은 그 id를 할당받기 위해 기다려야 하므로 availibility 문제가 생기는 것 같습니다. 그래서 트위터에서는 id의 sequential을 어느정도 포기하고.. snowflake라 불리는 방법을 만든 것 같습니다.

 

timestamp + worker number + sequence number

 

snowflake에서 id는 위와같이 구성됩니다.

timestamp는 말 그대로.. timestamp구요. epoch time으로 millisec 혹은 sec 단위같습니다.

worker number는 zookeeper에 의해 서버?가 시작될 때 결정되며,

sequence number는 thread마다 다른 값을 가지게 됩니다.

 

이렇게하면.. 프로그램이 실행되는 최소단위인 thread마다 매 시간 마다 각 노드마다 다른 값을 가지게 되니 문제가 없을 것 같네요.

 

 

아래부터가 트위터에서 이야기하는 내용입니다.

 

Snowflake

눈송이 발표
작성자 : @rk
2010 년 6 월 1 일 화요일
얼마 전 API 개발자 목록에 트윗에 대한 고유 ID 번호를 생성하는 방식을 변경할 것이라고 발표했습니다.

이러한 변경을 수행 할 준비가되어 있지는 않지만 이러한 ID를 생성하는 내부 서비스 인 Snowflake를 위해 열심히 작업 해 왔습니다. 모든 사람이 우리가 사용하는 기술과 이것이 Twitter 플랫폼을 기반으로 구축하는 모든 사람에게 어떤 영향을 미칠지에 대해 숙지 할 수있는 기회를 제공하기 위해 오늘 Snowflake 코드 기반을 공개하고 있습니다.

더 나아 가기 전에 몇 가지 컨텍스트를 제공하겠습니다.

문제
우리는 현재 대부분의 온라인 데이터를 저장하기 위해 MySQL을 사용합니다. 처음에 데이터는 하나의 작은 데이터베이스 인스턴스에 있었으며 차례로 하나의 큰 데이터베이스 인스턴스가되고 결국에는 많은 큰 데이터베이스 클러스터가되었습니다. 자세한 내용은 블로그 게시물 전체에 유용한 여러 가지 이유로 이러한 시스템 중 상당수를 Cassandra 분산 데이터베이스 또는 수평으로 분할 된 MySQL (Gizzard 사용)으로 교체하기 위해 노력하고 있습니다.

MySQL과 달리 Cassandra에는 고유 한 ID를 생성하는 기본 제공 방법이 없습니다. Cassandra가 흥미로워지는 규모에서는 ID에 대해 한 가지 크기에 맞는 솔루션을 제공하기가 어려울 수 있으므로 그렇게해서는 안됩니다. 샤딩 된 MySQL도 마찬가지입니다.

이 시스템에 대한 우리의 요구 사항은 매우 간단하면서도 까다로 웠습니다.

고 가용성 방식으로 초당 수만 개의 ID를 생성 할 수있는 무언가가 필요했습니다. 이로 인해 자연스럽게 비협조적인 접근 방식을 선택하게되었습니다.

이러한 ID는 대략적으로 정렬 할 수 있어야합니다. 즉, A와 B 트윗이 거의 같은 시간에 게시되는 경우 우리와 대부분의 Twitter 클라이언트가 트윗을 정렬하는 방식이므로 서로 가까운 ID를 가져야합니다. [1]

또한이 숫자는 64 비트에 맞아야합니다. 우리는 이전에 트윗 ID를 저장하는 데 사용되는 비트 수를 늘리는 고통스러운 과정을 겪었습니다. 100,000 개 이상의 서로 다른 코드베이스가 관련되어있을 때 수행하기가 놀랍지 않게 어렵습니다.

옵션
우리는 여러 가지 접근 방식을 고려했습니다. MySQL 기반 티켓 서버 (예 : flickr 사용)는 일종의 재 동기화 루틴을 구축하지 않고는 필요한 주문 보장을 제공하지 못했습니다. 또한 다양한 UUID를 고려했지만 찾을 수있는 모든 구성에는 128 비트가 필요했습니다. 그 후 Zookeeper 순차 노드를 살펴 보았지만 필요한 성능 특성을 얻을 수 없었고 조정 된 접근 방식이 실질적인 보상없이 가용성을 낮출 까봐 두려웠습니다.

해결책
대략적으로 정렬 된 64 비트 ID를 조정되지 않은 방식으로 생성하기 위해 타임 스탬프, 작업자 번호 및 시퀀스 번호의 구성을 결정했습니다.

시퀀스 번호는 스레드 단위이며 작업자 번호는 시작시 zookeeper를 통해 선택됩니다 (구성 파일을 통해 재정의 가능함).

코드를 숙독하고 사용하는 것이 좋습니다. github에서 찾을 수 있습니다. 그러나 아직 프로덕션 단계에서 실행되지 않고 변경 될 가능성이 높은 것은 현재 알파 품질 소프트웨어라는 점을 기억하십시오.

피드백
버그를 발견하면 github에보고하십시오. 이해하는 데 문제가있는 경우 freenode의 #twinfra IRC 채널에 문의하십시오. 보안 문제라고 생각되는 사항을 발견하면 security@twitter.com (및 참조 : ryan@twitter.com)으로 이메일을 보내주십시오.

[1] 수학적 측면에서 트윗은 더 이상 정렬되지 않지만 k 정렬됩니다. 우리는 k를 1 초 미만으로 유지하는 것을 목표로합니다. 즉, 1 초 이내에 게시 된 트윗도 id 공간에서 1 초 이내에 게시됩니다.

 

 

Announcing Snowflake

By ‎@rk‎

Tuesday, 1 June 2010 

   

 

A while back we announced on our API developers list that we would change the way we generate unique ID numbers for tweets.

While we’re not quite ready to make this change, we’ve been hard at work on Snowflake which is the internal service to generate these ids. To give everyone a chance to familiarize themselves with the techniques we’re employing and how it’ll affect anyone building on top of the Twitter platform we are open sourcing the Snowflake code base today.

Before I go further, let me provide some context.

The Problem

We currently use MySQL to store most of our online data. In the beginning, the data was in one small database instance which in turn became one large database instance and eventually many large database clusters. For various reasons, the details of which merit a whole blog post, we’re working to replace many of these systems with the Cassandra distributed database or horizontally sharded MySQL (using gizzard).

Unlike MySQL, Cassandra has no built-in way of generating unique ids – nor should it, since at the scale where Cassandra becomes interesting, it would be difficult to provide a one-size-fits-all solution for ids. Same goes for sharded MySQL.

Our requirements for this system were pretty simple, yet demanding:

We needed something that could generate tens of thousands of ids per second in a highly available manner. This naturally led us to choose an uncoordinated approach.

These ids need to be roughly sortable, meaning that if tweets A and B are posted around the same time, they should have ids in close proximity to one another since this is how we and most Twitter clients sort tweets.[1]

Additionally, these numbers have to fit into 64 bits. We’ve been through the painful process of growing the number of bits used to store tweet ids before. It’s unsurprisingly hard to do when you have over 100,000 different codebases involved.

Options

We considered a number of approaches: MySQL-based ticket servers (like flickr uses), but those didn’t give us the ordering guarantees we needed without building some sort of re-syncing routine. We also considered various UUIDs, but all the schemes we could find required 128 bits. After that we looked at Zookeeper sequential nodes, but were unable to get the performance characteristics we needed and we feared that the coordinated approach would lower our availability for no real payoff.

Solution

To generate the roughly-sorted 64 bit ids in an uncoordinated manner, we settled on a composition of: timestamp, worker number and sequence number.

Sequence numbers are per-thread and worker numbers are chosen at startup via zookeeper (though that’s overridable via a config file).

We encourage you to peruse and play with the code: you’ll find it on github. Please remember, however, that it is currently alpha-quality software that we aren’t yet running in production and is very likely to change.

Feedback

If you find bugs, please report them on github. If you are having trouble understanding something, come ask in the #twinfra IRC channel on freenode. If you find anything that you think may be a security problem, please email security@twitter.com (and cc myself: ryan@twitter.com).

[1] In mathematical terms, although the tweets will no longer be sorted, they will be k-sorted. We’re aiming to keep our k below 1 second, meaning that tweets posted within a second of one another will be within a second of one another in the id space too.

 

 

 

Twitter IDs

Twitter 내의 각 개체 (Tweet, Direct Message, User, List 등)에는 고유 한 ID가 있습니다.

플랫폼 초창기에는 이러한 ID가 순차적으로 생성 될 수있을만큼 작은 숫자였습니다. 시간이 지남에 따라 성장을 수용하기 위해 ID가 32 비트에서 64 비트로 이동했습니다. 오늘날 Twitter ID는 순차가 아닌 시간을 기반으로하는 고유 한 64 비트 부호없는 정수입니다. 전체 ID는 타임 스탬프, 작업자 번호 및 시퀀스 번호로 구성됩니다. Twitter는 이러한 ID를 지속적으로 생성하기 위해 "Snowflake"라고하는 내부 서비스를 개발했습니다 (Twitter 블로그에서 자세한 내용을 확인하십시오).

64 비트만큼 큰 숫자는 64 비트 미만의 정수를 나타내는 프로그래밍 언어에 문제를 일으킬 수 있습니다. 이에 대한 예로 정수가 53 비트 크기로 제한되는 JavaScript가 있습니다. 이에 대한 해결 방법을 제공하기 위해 Twitter API (v1 / 1.1)의 원래 디자인에서 ID 값은 정수와 문자열의 두 가지 형식으로 반환되었습니다.

 

{"id": 10765432100123456789, "id_str": "10765432100123456789"}

 

브라우저 자바 스크립트 콘솔에서 (10765432100123456789) .toString () 명령을 실행하면 결과는 "10765432100123458000"이됩니다. 64 비트 정수는 번역의 결과로 정확도를 잃게됩니다 (때로는 "munging"이라고합니다. 데이터로 변경).

버전 1.1까지의 Twitter API에서는 정확도 손실을 방지하기 위해 항상 숫자의 문자열 표현을 사용해야합니다.

최신 버전의 API에서는 모든 큰 정수 값이 기본적으로 문자열로 표시됩니다.

 

 

Each object within Twitter - a Tweet, Direct Message, User, List, and so on - has a unique ID.

At the very beginning of the platform, these IDs were small enough numbers that they could be generated sequentially. Over time, to accommodate growth, the IDs moved from being 32-bit, to 64-bit. Today, Twitter IDs are unique 64-bit unsigned integers, which are based on time, instead of being sequential. The full ID is composed of a timestamp, a worker number, and a sequence number. Twitter developed an internal service known as “Snowflake” in order to consistently generate these IDs (read more about this on the Twitter blog).

Numbers as large as 64-bits can cause issues with programming languages that represent integers with fewer than 64-bits. An example of this is JavaScript, where integers are limited to 53-bits in size. In order to provide a workaround for this, in the original designs of the Twitter API (v1/1.1), ID values were returned in two formats: both as integers, and as strings.

 

{"id": 10765432100123456789, "id_str": "10765432100123456789"}

 

If you run the command  (10765432100123456789).toString() in a browser JavaScript console, the result will be "10765432100123458000" - the 64-bit integer loses accuracy as a result of the translation (this is sometimes called “munging” - a destructive change to a piece of data).

In Twitter APIs up to version 1.1, you should always use the string representation of the number to avoid losing accuracy.

In newer versions of the API, all large integer values are represented as strings by default.

 

출처

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

Announcing Snowflake

developer.twitter.com/en/docs/twitter-ids

Twitter IDs