스노우플레이크

스노우플레이크는 서버 여러 대가 서로 묻지 않고 겹치지 않는 번호를 각자 만들어 내게 하는 방식입니다. 번호 하나를 받으려고 중앙의 한 곳에 다녀오지 않아도 됩니다. 대신 정수 하나를 자리로 쪼개서, 앞자리에는 만든 시각을 적고 뒷자리에는 만든 기계와 순번을 적습니다.

상세

스노우플레이크는 유일한 ID(Identifier, 식별자)를 만드는 일을 한 정수 안의 자리 나눠 쓰기로 바꾸기로 한 결정입니다. 64비트 정수 하나를 앞에서부터 시각 · 기계 번호 · 순번으로 갈라 놓고, 각 서버가 자기 자리만 채워 넣습니다. 트위터가 트윗에 붙일 번호를 만들려고 세운 방식이 이것입니다.

무엇이 불편해서 나왔는지가 원전에 그대로 적혀 있습니다. 트위터는 온라인 데이터 대부분을 MySQL 에 담고 있었고, 그것을 분산 데이터베이스인 Cassandra 와, 같은 표의 행을 여러 대에 나눠 담는 수평 샤딩 MySQL 로 옮기는 중이었습니다. MySQL 과 달리 Cassandra 에는 유일한 ID 를 만들어 주는 기능이 없습니다. 원전은 그것이 없는 게 당연하다고도 적습니다. Cassandra 가 흥미로워지는 규모에서는 모두에게 맞는 하나의 해법을 주기 어렵기 때문입니다.

원조 문서가 세운 요구는 여섯입니다.

이 여섯 줄이 곧 이 방식이 선 자리입니다. 요구에 안 맞는 선택지가 여기서 걸러졌습니다. 원전은 UUID(Universally Unique Identifier, 범용 고유 식별자)도 검토했지만 찾을 수 있는 방식이 전부 128비트를 요구했다고 적습니다. flickr 이 쓰는 방식처럼 번호만 내주는 MySQL 서버를 따로 두는 티켓 서버는, 따로 맞춰 주는 절차를 만들지 않으면 필요한 순서 보장을 주지 못했다고 적습니다. 여러 서버가 값을 놓고 서로 맞추는 데 쓰는 조율 서비스인 주키퍼에서 순서대로 번호가 붙는 항목을 받아 쓰는 방법도 봤지만, 필요한 성능이 안 나왔고 조율하는 방식이 실익 없이 가용성만 낮출까 걱정했다고 적습니다.

그래서 남은 것이 세 조각의 조합입니다. 원전은 대략 정렬된 64비트 ID 를 조율 없이 만들려고 시각과 기계 번호와 순번의 조합으로 정했다고 적습니다. 원전의 낱말로는 타임스탬프 · 워커 번호 · 순번이고, 이 문서는 그 자리를 각각 시각 · 기계 번호 · 순번이라고 부릅니다. 순번은 스레드마다 갖고, 기계 번호는 시작할 때 주키퍼로 고릅니다. 설정 파일로 덮어쓸 수도 있습니다.

번호 하나를 뽑는 순서는 이렇습니다.

flowchart TD
    A["지금 시각을 읽는다"] --> B{"지난번보다 이른가"}
    B -->|그렇다| X["발급을 거절한다"]
    B -->|아니다| C{"지난번과 같은 밀리초인가"}
    C -->|그렇다| D["순번을 1 올린다 · 넘치면 다음 밀리초를 기다려 그 시각을 쓴다"]
    C -->|아니다| E["순번을 0으로 되돌린다"]
    D --> H["시각 · 기계 번호 · 순번을 한 정수로 합친다"]
    E --> H

읽은 시각이 지난번보다 이르면 발급을 거절합니다. 원조 구현은 그 자리에서 예외를 던집니다. 같은 밀리초면 순번을 하나 올립니다. 그 순번이 한 바퀴 돌아 0이 되면 다음 밀리초가 될 때까지 기다렸다가 그 새 밀리초를 시각으로 씁니다. 밀리초가 바뀌었으면 순번을 0으로 되돌립니다. 마지막에 세 값을 각자의 자리로 밀어 넣어 하나의 정수로 합칩니다.

앞자리에 시각을 두었기 때문에 정수의 크기 비교가 곧 시간순 비교가 됩니다. 다만 원전은 이것을 완전한 정렬이라고 말하지 않습니다. 원전이 쓰는 낱말은 k-정렬입니다. 트윗이 더는 정렬돼 있지 않지만, 서로 1초 안에 올라온 트윗은 ID 공간에서도 서로 1초 안에 있게 하겠다는 뜻이라고 원전이 직접 풀어 적습니다. 원조 문서는 그 폭으로 1초를 약속하되 수십 밀리초를 노린다고 적습니다.

대가

원조가 나눈 폭은 시각 41비트 · 기계 번호 10비트 · 순번 12비트입니다. 자리가 정확히 어디부터 어디까지인지는 아래 「형태」가 적습니다. 여기서 볼 것은 그 나눔이 무엇을 데려오는가입니다.

시계에 매입니다. 원전은 시스템 시계를 정확하게 유지하려면 NTP(Network Time Protocol, 네트워크 시각 동기 프로토콜)를 쓰라고 적습니다. 스노우플레이크는 뒤로 가는 시계로부터 자기를 보호하는데, 그 보호의 내용이 곧 대가입니다. 시계가 빨리 가서 NTP 가 몇 밀리초를 되돌리라고 하면, 마지막으로 번호를 만든 시각을 지날 때까지 번호 만들기를 거부합니다. 원조 구현은 그 자리에 "시계가 거꾸로 간다"는 오류를 남깁니다. 그리고 몇 밀리초 동안 발급을 거절하는지를 메시지에 담아 예외를 던집니다. 원전은 아예 NTP 가 시계를 뒤로 못 옮기는 모드로 돌리는 편이 더 낫다고 적습니다.

조율을 없앤 자리에 기계 번호 배정이 남습니다. 번호를 만드는 기계끼리 맞추지 않아도 되는 대신, 어느 기계가 몇 번인지는 시작할 때 정해져 있어야 합니다. 원전은 그 번호를 시작할 때 주키퍼로 고른다고 적습니다. 이 짐이 사라지지는 않습니다. Sony 의 후속 구현은 기계 번호를 기본으로 사설 IP(Internet Protocol) 주소의 하위 16비트에서 가져오고, 유일한지 검사하는 함수를 따로 받습니다. 그 함수를 주지 않으면 검사를 하지 않는다고 문서가 적습니다.

자리를 나눈 비율이 그대로 상한이 됩니다. 시각에 41비트를 주면 밀리초 정밀도로 69년입니다. 기계 자리에 10비트를 주면 1024대까지입니다. 순번에 12비트를 주면 기계마다 4096개마다 한 바퀴를 돕니다. 한쪽을 넓히려면 다른 쪽을 줄여야 합니다. Sony 의 구현이 그 맞바꿈을 그대로 보여 줍니다. 시각을 10밀리초 단위 39비트로, 순번을 8비트로, 기계를 16비트로 잡아서 수명은 174년으로 늘고 기계 수는 2의 16승으로 늘었지만, 한 인스턴스가 10밀리초당 만들 수 있는 개수는 2의 8승으로 원조보다 적어졌습니다.

번호가 시각을 흘립니다. 앞자리가 시각이므로 값 하나만 있으면 만들어진 때를 되짚을 수 있습니다. 값을 뒤쪽 자리들의 폭을 다 더한 만큼 오른쪽으로 밀면 시각 자리만 남습니다. 디스코드에서 그 폭은 22비트입니다. 디스코드가 기계 자리를 워커 5비트와 프로세스 5비트로 나눠 쓰고 마지막 12비트를 증가값이라 부르니, 그 셋을 더한 값입니다(세 자리의 대응은 아래 「예시」의 표에 있습니다). 거기에 자기 기준 시각을 더하면 밀리초 단위 시각이 나옵니다. 디스코드는 이 계산을 감추기는커녕 공개 문서에 식으로 적어 둡니다. 순서를 뒤집으면 원하는 시각의 ID 를 지어내 페이지 나누기의 기준으로 쓸 수도 있습니다.

이 넷은 조건이 맞을 때만 터지는 것이 아닙니다. 이 방식을 고른 순간 확정됩니다.

이름의 출처

트위터가 붙인 이름입니다. 2010년 6월 1일 트위터 엔지니어링 블로그에 「Announcing Snowflake」라는 글이 올랐고, 그 글이 이 이름을 걸고 코드를 공개한 자리입니다. 글은 트윗의 ID 를 만드는 방식을 바꾸겠다고 개발자 목록에 앞서 알린 적이 있다고 운을 뗀 다음, 그 ID 를 만드는 내부 서비스의 이름이 스노우플레이크이며 그 코드를 그날 공개한다고 적습니다.

글쓴이의 이름은 원전 글에 서명으로 적혀 있지 않습니다. 원전이 남긴 것은 두 단서뿐입니다. 그 글은 보안 문제로 보이는 것을 찾으면 트위터 보안 주소로 메일을 보내면서 자기도 참조에 넣어 달라며 [email protected] 을 적습니다. 같은 시기 공개된 저장소의 문서는 기여할 때 풀리퀘스트를 ryanking 에게 보내라고 적습니다. 이 사전은 두 단서를 나란히 두는 데서 멈춥니다.

형태

64비트 정수 하나입니다. 원조 저장소의 문서는 그 안을 이렇게 적습니다.

packet-beta
0-0: "남는 한 자리"
1-41: "시각 41비트"
42-51: "기계 번호 10비트"
52-63: "순번 12비트"

이 그림은 왼쪽부터, 곧 맨 위 비트부터 셉니다.

세 조각을 더하면 63비트입니다. 원조 문서는 남는 한 자리가 무엇인지 따로 설명하지 않습니다. 요구사항 쪽에 ID 를 64비트 미만으로 유지해야 한다고 적혀 있고, 원조 구현이 돌려주는 값의 타입이 부호 있는 64비트 정수라는 것까지가 원문에서 읽을 수 있는 전부입니다.

같은 저장소 안에서도 문서와 코드의 눈금이 다릅니다. 문서는 기계 자리를 "설정으로 넣는 기계 번호 10비트" 한 덩이로 적습니다. 같은 태그의 소스 코드는 그 10비트를 데이터센터 번호 5비트와 워커 번호 5비트로 다시 가르고, 두 값에 각각의 최댓값을 따로 둡니다.

packet-beta
0-0: "남는 한 자리"
1-41: "시각 41비트"
42-46: "데이터센터 번호 5비트"
47-51: "워커 번호 5비트"
52-63: "순번 12비트"

코드가 정한 자리이므로 순서까지 확정됩니다. 순번이 맨 아래 12비트를 쓰고, 워커 번호가 그 위 5비트, 데이터센터 번호가 다시 그 위 5비트입니다. 여기서 말하는 워커 번호는 원전 글이 10비트 전체를 부르던 이름과 글자가 같지만 그 절반을 가리킵니다. "데이터센터 5 + 기계 5" 라는 설명을 보게 되면 그것은 이 코드 쪽을 따라 적은 것입니다.

코드에서 값이 합쳐지는 자리는 한 줄입니다.

((timestamp - twepoch) << timestampLeftShift) |
  (datacenterId << datacenterIdShift) |
  (workerId << workerIdShift) |
  sequence

timestampLeftShift 는 순번 비트 수와 워커 비트 수와 데이터센터 비트 수를 더한 값이라 22입니다. twepoch 는 기준 시각이고 원조 구현에는 1288834974657 이 박혀 있습니다. 시각 자리에 담기는 것은 절대 시각이 아니라 이 기준 시각으로부터 흐른 밀리초입니다. 기준 시각은 구현이 각자 정하는 값입니다. 41비트가 69년이라는 말도 그 기준 시각부터 69년이라는 뜻입니다.

예시

디스코드

디스코드는 자기 문서에서 트위터의 스노우플레이크 형식을 쓴다고 밝히고, 자리 배치를 표로 적어 둡니다. 원조와 눈금이 다릅니다.

이 표는 맨 아래 비트를 0으로 두고 위로 셉니다. 앞의 그림들과 세는 방향이 반대입니다. 같은 배치를 반대 방향에서 적은 것입니다. 낱말도 다릅니다. 여기서 타임스탬프는 앞에서 시각이라 부른 자리이고, 증가값은 앞에서 순번이라 부른 자리입니다.

배치 자체도 원조와 두 군데가 다릅니다. 시각 자리가 41비트가 아니라 42비트입니다. 그리고 원조 문서가 한 덩이로 적은 기계 자리를 디스코드 문서는 워커와 프로세스 둘로 갈라 적습니다. 원조 코드도 그 자리를 5비트씩 둘로 갈랐지만 이름은 데이터센터와 워커였습니다. 폭이 같다고 해서 같은 뜻이라고 적어 둔 문서는 없습니다. 디스코드 문서는 자기 배치를 자기 말로 적을 뿐입니다.

문서는 실제 값 하나를 놓고 그 자리들을 꺼내 보입니다. 175928847299117063 이 그 값입니다. 시각 자리의 비트열 000000100111000100000110010110101100000100 을 십진수로 읽으면 41944705796 이고, 여기에 디스코드 기준 시각 1420070400000 을 더하면 1462015105796 입니다. 이것을 밀리초 단위 시각으로 읽으면 2016-04-30 11:18:25.796 UTC 입니다. 워커 자리는 00001, 프로세스 자리는 00000 입니다. 증가값 자리의 값은 문서의 그림이 보여 주지 않습니다.

packet-beta
0-41: "시각 41944705796"
42-46: "워커 1"
47-51: "프로세스 0"
52-63: "증가값"

이 그림도 앞의 것들처럼 왼쪽부터, 곧 맨 위 비트부터 셉니다. 바로 위 표와는 방향이 반대입니다.

되짚는 식도 문서에 그대로 있습니다. 값을 22비트 오른쪽으로 밀고 1420070400000 을 더하면 시각이고, snowflake & 0xFFF 가 증가값입니다. 디스코드는 이 값을 HTTP(HyperText Transfer Protocol) 응답에서 언제나 문자열로 돌려준다고 적습니다. 일부 언어에서 정수가 넘치는 것, 곧 정수 오버플로를 막으려는 것입니다.

Sony sonyflake

Go 로 쓰인 후속 구현입니다. 문서 첫 줄이 트위터의 스노우플레이크에서 영감을 받았다고 밝히고, 바로 다음 줄에서 비트 배치를 일부러 다르게 잡았다고 적습니다. 기본값은 시각 39비트, 순번 8비트, 기계 번호 16비트이고 시각의 단위는 10밀리초입니다.

packet-beta
0-0: "남는 한 자리"
1-39: "시각 39비트 · 10밀리초 단위"
40-47: "순번 8비트"
48-63: "기계 번호 16비트"

문서가 주는 것은 세 조각의 폭과 적은 차례까지입니다. 남는 한 자리를 맨 위에 둔 것은 원조의 그림을 따라 그린 것이고, 그 자리를 문서가 못 박지는 않습니다. 문서가 적는 것은 시각 비트 수를 63 - 순번 - 기계 로 구한다는 것, 곧 63비트만 쓴다는 데까지입니다. 순번 비트 수와 기계 비트 수를 설정으로 넘길 수 있고, 그렇게 구한 시각 비트 수가 32보다 작으면 오류가 납니다.

문서는 이 배치가 무엇을 얻고 무엇을 잃는지를 원조와 나란히 적습니다. 수명 174년은 스노우플레이크의 69년보다 길고, 돌릴 수 있는 기계 수 2의 16승은 스노우플레이크의 2의 10승보다 많으며, 한 인스턴스가 10밀리초당 만드는 2의 8승 개는 스노우플레이크보다 적습니다.

기본 기준 시각은 2025년 1월 1일이고, 기본 기계 번호는 사설 IP 주소의 하위 16비트입니다.

경계

클라우드 데이터 웨어하우스를 파는 Snowflake Inc. 도 이 표제어에 드는가. 아닙니다. 이름만 같은 남남입니다. 그 회사의 공식 문서는 자기 제품이 진보된 데이터 플랫폼으로 구동된다고 적고, 그 플랫폼이 자체 관리형 서비스로 제공된다고 적습니다. 그 플랫폼이 한데 모은 것은 데이터 저장과 처리와 분석 솔루션입니다. 유일한 ID 를 만드는 이야기가 아닙니다.

가르는 기준은 하나입니다. 그 문서가 64비트 정수를 시각과 기계와 순번으로 쪼개는 이야기를 하고 있는가.

관련 항목

같은 문제를 푸는 다른 방식

UUID · 자동 증가 키 · 티켓 서버 · 주키퍼 순차 노드 · flickr

이 결정이 기대는 기반

NTP · 단조 시계 · 에포크 · 주키퍼 · 비트 마스크 · IP · Thrift

이것을 실제로 구현·채택한 제품

Discord · Sony sonyflake · Baidu uid-generator

이 결정과 맞물리는 기술

MySQL · Cassandra · 샤딩 · gizzard · 페이지 나누기 · k-정렬 · HTTP

이 결정에서 흔히 나는 오류·장애

시계 역행 · 정수 오버플로 · 시계 뒤틀림

헷갈리는 이웃

Snowflake Inc. · 눈송이 서버 · 눈송이 스키마