분산시스템을 위한 uid 만들기

Table of Contents

1 분산 시스템을 위한 유일 ID 생성기

여러 데이터베이스 서버를 쓰는 경우 유일성이 보장되는 ID를 만들어야 한다.

2 UUID

UUID는 128-bit hexagodecimal 숫자이다. UUID의 충돌성은 아주 낮다.

장점

  1. 만드는 것이 단순하다. 동기화 이슈가 없다.
  2. 각 서버가 자기 ID를 알아서 만드니 규모 확장이 쉽다.

단점

  1. ID가 128비트로 길다.
  2. ID를 시간순으로 정렬할 수 없다.
  3. ID에 숫자가 아닌 값이 포함될 수 있다.

2.1 포맷

  • time_low 4바이트(16진수 8개, 32비트) : integer giving the low 32 bits of the time, 시간의 low부분 32비트
  • time_middle 2바이트(16진수 4개, 16비트) : integer giving the middle 16 bits of the time, 시간의 middle부분 32비트
  • time_hi_and_version 2바이트(16비트) : 4-bit "version" in the most significant bits, followed by the high 12 bits of the time 최상위 비트에서 4비트는 "version" + 시간의 high 12비트
  • clock_seq_hi_and_res clock_seq_low 2바이트(16비트) : 1 to 3-bit "variant" in the most significant bits, followed by the 13 to 15-bit clock sequence, 최상위 비트에서 1~3비트의 '변종' + 클럭시퀀스 13~15비트
  • node 6비트(48비트) : the 48-bit node id, 노드 아이디

이렇게 32 + 16 + 16 + 16 + 48 = 128 비트가 이루어진다.

123e4567-e89b-12d3-a456-426614174000
xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx

M 은 UUID 버전이다. 여기서 버전은 1이다. N 은 최상위 비트에서 1~3비트의 변종을 말한다. 여기서 N은 a(10xx2)

위키를 보니 UUID는 버전이 있다. 이게 뭔지 한번 보자.

2.2 Nil UUID

"nil"값을 말한다. 00000000-0000-0000-0000-000000000000 이다.

2.3 Version 1 - date-time and a node ID (usually MAC address)

버전1은 현재날짜와시간 + 호스트컴퓨터의 맥어드레스 이다. 이 말은 동일한 컴퓨터에서 동일한 시간에 ID를 만드는 경우가 아니면 글로벌하게 유니크한 아이디가 만들어진다는 뜻이다. 또한 랜덤한 비트가 추가됨으로써 충돌의 가능성은 더 낮아진다.

하지만 이 유니크함은 익명성을 희생해야한다.

2.4 Version 2 - date-time and MAC address, DCE security version

RFC-4122에서 버전2를 "DCE security"한 UUID라고는 하지만 구체적인 디테일이 없다. 그래서 대부분 UUID구현에서 버전2는 무시한다고함.

2.5 Version 3 and 5 - namespace name-based

버전 3 및 버전 5 UUID는 네임스페이스 식별자와 이름을 해싱하여 생성. 버전 3은 해싱 알고리즘으로 MD5를 사용하고 버전 5는 SHA-1을 사용하여 버전5를 더 선호한다고함.

이것은 다른 말로하면 UUID에다가 식별자를 한번더 섞어버린 UUID를 만드는 것이다. 이렇게 함으로써 식별자를 이용한 UUID가 네임스페이스 내에서 동일한 식별자의 UUID는 동일하게 된다.

사이트 참고 : https://www.uuidtools.com/v3

2.6 Version 4 - random

버전4는 완전 랜덤이다. 자바의 randomUUID() 가 이것에 해당한다.

2.7 MySQL

참고로 MySQL 8.0에서는 아래처럼 테이블을 생성해서 사용할 수 있다.

create table t (
    uuid BINARY(16) default (UUID_TO_BIN(UUID())),
)

조회는 아래처럼

select BIN_TO_UUID(uuid) uuid from t;
---
The result is:

# uuid
'8c45583a-0e1f-11ec-804d-005056219395'

3 MongoDB's ObjectID

몽고디비는 12-byte(96-it)인 헥사고널 넘버를 가진다. 다음으로 이루어져있다.

  • a 4-byte epoch timestamp in seconds,
  • a 3-byte machine identifier,
  • a 2-byte process id,
  • a 3-byte counter, starting with a random value.

UUID와 차이점은 길이가 작다는 것빼고는 비슷한 개념인 것 같다.

4 티켓 서버

Flickr는 분산 기본 키를 만들어내기 위해 이 기술을 이용하였다고 한다.

장점

  1. 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다.
  2. 구현하기 쉽다. (중소 규모 앱에 적합)

단점

  1. 티켓 서버가 SPOF(Single-Point-Of-Failjure)가 된다. 장애 대응을 위해 서버를 여러 대 중비해야 할 수 있다. 그렇게 하면 데이터 동기화라는 새로운 문제가 생긴다.

4.1 Flickr의 블로그보기

4.1.1 왜?

Flickr는 데이터스토어를 샤딩하여 스케일링을 수행했다. 때때로 데이터베이스 끼리 마이그레이션을 할 때도 있다. 그래서 우리는 primary key가 globally unique한 값이어야 한다.

더해서 우리 Mysql의 shards(샤드들)은 master-master replicants 쌍으로 구성된다. (for resiliency, 탄력성) 이는 충돌을 피하기 위해 샤드 내에서 유니크함을 보장할 수 있어야 한다.

우리는 MySQL auto-increment 컬럼을 추가해서 끝내고 싶었지만, Mysql은 물리적, 논리적 데이터들을 사이에서 고유성(unique)를 보장하지 않는다. (MySQL can't guarantee uniqueness across physical and logical databases.)

뭐 여러 데이터베이스를 연결하는 고유성은 보장하지 않는 다는 것이겠지…

4.1.2 GUID를 안 쓴 이유

GUID는 크다. 그리고 MySQL 에서 인덱싱이 별로임. 그러므로 인덱스 사이즈가 key consideration 이다.

If you can't keep your indexes in memory, you can't keep your database fast. 인덱스를 메모리에 머금을 수 없게 하면 database를 빠르게 할 수 없다. 티켓서버는 reporting, debugging이 직관적이다. 일부 캐싱핵을 발휘할 수도 있다.

4.1.3 해싱은?

Amazon의 DynamoDB는 GUID/샤딩 문제를 해결하기 위해 데이터 저장소에 일관된 해싱링을 제공한다. 이것은 쓰기비용이 저렴한 환경에서 더 적합하다. MySQL은 빠른랜덤읽기(fast random reads)에 최적화되어있다.

4.1.4 auto-increment를 중앙화.

여러 데이터베이스를 사이에서 작동하는 auto-increments 기능이 없다면, 그냥 데이터베이스 하나만 쓰는 것은 어떨까? 누군가 사진을 업로드할 때마다 하나의 데이터베이스에 새 행을 삽입하면 그 테이블의 auto-increment ID를 다른 모든 데이터베이스에서 기본 키로 사용할 수 있을 것이다.

물론 초당 60장 이상의 사진에서는 테이블이 꽤 커질 거질 수 있다. 우리는 사진에 대한 모든 추가적인 데이터를 제거하여, 중앙화된 데이터베이스에는 ID만 남기는 것이다! 이렇게 하더라도 테이블은 관리할 수 없을 정도로 빨리 커질 것이다. 그리고 댓글, 즐겨찾기, 그룹게시물, 태그 등이 있는데 모두 아이디가 필요하다!

4.1.5 REPLACE INTO 사용하기

10여 년 전 MySQL은 ANSI SQL 스펙에 대한 비표준 확장 REPLACE INTO 를 발표한다. 나중에 INSERT ON DUPLICATE KEY UPDATE 가 나타나서 원래 문제를 훨씬 더 잘 해결한다. 하지만 REPLACE INTO 도 여전히 지원한다.

REPLACEINSERT 와 동일하게 작동한다. 다른 점은 기존 row에 같은 값의 PRIMARY KEY나 UNIQUE index를 가진다면, old row는 삭제된다. 그리고 새로운 row가 추가된다.

이를 통해 데이터베이스의 한 행에서 원자적으로 업데이트하고 자동으로 증가하는 새 PRIMARY KEY를 얻을 수 있다.

아하 REPLACE INTO 를 이용해서 계속 INSERT를 해서 ID가 생성되는 정보를 저장하는 것이 아니라. 하나의 row에서 계속 바뀌기만 하도록 하는 것이다!!

4.1.6 Putting It All Together

Flickr ticket server 는 dedicated(전용) database server이다. 해당 데이터베이스에는 32-bit ID를 위한 Tickets32 와 64비트를 위한 Tickets64 가 있다.

CREATE TABLE `Tickets64` (
    `id` bigint(20) unsigned NOT NULL auto_increment,
    `stub` char(1) NOT NULL default '',
    PRIMARY KEY (`id`),
    UNIQUE KEY `stub` (`stub`)
) ENGINE=InnoDB

SELECT * FROM Tickets64 아래처럼 하나의 row만 리턴한다.

+-------------------+------+
| id                | stub |
+-------------------+------+
| 72157623227190423 |    a |
+-------------------+------+

좋다 우리가 새로운 globally unique 64-bit ID를 원한다면 아래의 SQL를 사용하면 된다.

REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();

4.1.7 SPOFs

ID를 제공하는 곳이 단일실패지점이 되는 것은 정말로 좋지 않다. 우리는 두 개의 티켓 서버를 실행하여 "고가용성"을 달성한다.

쓰기/업데이트 볼륨에서 상자간의 복제는 문제가 될 수 있으며, 잠금은 사이트의 성능을 죽인다. 우리는 ID공간을 반으로 나눠서 배분했다. (짝수, 홀수) 이렇게 책임을 나눔으로써 동기화가 필요없게 한 것이다.

TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1

TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2

4.1.8 More Sequences

실제로 티켓 서버에는 Tickets32 , Tickets64 외에도 다른 많은 테이블들이 있다. Photos, Accouts, Offline Tasks, Groups, etc… 이런 정보들에 시퀀스 정보가 필요하다.

Offline Tasks는 고유의 시퀀스를 갖는다. Groups, Accounts는 그들 고유의 시퀀스를 갖는다. 왜냐하면 비교적 적은 수의 시퀀스를 갖기 때문이다.

4.1.9 결과

이 방식은 우아하진 않지만 경이롭게도 아주 잘 동작한다. 2006년 1월 13일 금요일 프로덕션에 배포된 이후로 아주 잘…

5 Twitter Snowflake

트위터에서 snowflake라는 서비스를 공개했다. 64-bit sequence ID를 만들 수 있다. 다음으로 이루어져 있다.

  • Epoch timestamp in milliseconds precision : 41-bit. 41비트로 표현할 수 있는 최대 숫자는 뭘까. 241 -1 => 2199023255551 => Wednesday, September 7, 2039 3:47:35.551 PM 이렇게 된다. 하지만 여기서 꼼수를 부릴 수 있다고 한다. 이 숫자는 1970의 Epoch를 기준으로 아니 기준 숫자를 뒤로 미루면 그 시간부터 69년을 벌 수 있다는 말이다.
  • Node ID - 10 bits. 노드와 머신들의 ID들 1024개 정도를 지정할 수 있다.
  • Local counter permachine - 12 bits. 카운터의 최대값은 4095.

남은 1-bit는 signed-bit로 항상 0을 세팅한다.

당신의 마이크로서비스는 이 시퀀스 제너레이터로 독립적으로 ID를 생성할 수 있다. 효율적이고 bigint 크기에 알맞다.

아래는 코드를 빌려온 것이다.

import java.net.NetworkInterface;
import java.security.SecureRandom;
import java.time.Instant;
import java.util.Enumeration;

/**
 * Distributed Sequence Generator.
 * Inspired by Twitter snowflake: https://github.com/twitter/snowflake/tree/snowflake-2010
 *
 * This class should be used as a Singleton.
 * Make sure that you create and reuse a Single instance of SequenceGenerator per node in your distributed system cluster.
 */
public class SequenceGenerator {
  private static final int UNUSED_BITS = 1;  // Sign bit, Unused (always set to 0)
  private static final int EPOCH_BITS = 41;
  private static final int NODE_ID_BITS = 10;
  private static final int SEQUENCE_BITS = 12;

  private static final int maxNodeId = (int)(Math.pow(2, NODE_ID_BITS) - 1);
  private static final int maxSequence = (int)(Math.pow(2, SEQUENCE_BITS) - 1);

  // Custom Epoch (January 1, 2015 Midnight UTC = 2014-01-01T00:00:00Z)
  private static final long CUSTOM_EPOCH = 1420070400000L;

  private final int nodeId;

  private volatile long lastTimestamp = -1L;
  private volatile long sequence = 0L;

  // Create SequenceGenerator with a nodeId
  // 머신의 노드아이디를 입력해서 제너레이터를 만든다.
  public SequenceGenerator(int nodeId) {
    if (nodeId < 0 || nodeId > maxNodeId) {
      throw new IllegalArgumentException(String.format("NodeId must be between %d and %d", 0, maxNodeId));
    }
    this.nodeId = nodeId;
  }
  // 머신의 노드아이디가 없을 때 하나 만든다.
  // Let SequenceGenerator generate a nodeId
  public SequenceGenerator() {
    this.nodeId = createNodeId();
  }

  // 현재 네트워크 정보를 hashCode로 바꾼다. 
  // 예외가 나면 Random함수를 수행한다.
  public int createNodeId() {
    int nodeId;
    try {
      StringBuilder sb = new StringBuilder();
      Enumeration<NetworkInterface> networkInterfaces = NetworkInterface.getNetworkInterfaces();

      while(networkInterfaces.hashMoreElements()) {
	NetworkInterface networkInterface = networkInterfaces.nextElement();
	byte[] mac = networkInterface.getHardwareAddress();
	if (mac != null) {
	  for (int i = 0; i < mac.length; i++) {
	    sb.append(String.format("%02X", mac[i]));
	  }
	}
      }
      nodeId = sb.toString().hashCode();
    } catch (Exception ex) {
      nodeId = (new SecureRandom().nextInt());
    }

    nodeId = nodeId & maxNodeId;
    return nodeId;
  }

  // 일단 락을 걸고 있다.
  public synchronized long nextId() {
    long currentTimestamp = timestamp();

    if (currentTimestamp < lastTimestamp) {
      throw new IllegalStateException("Invalid System Clock!");
    }

    if (currentTimestamp == lastTimestamp) {
      sequence = (sequence + 1) & maxSequence;
      if (sequence == 0) {
	// Sequence Exhausted, wait till next millisecond.
	currentTimestamp = waitNextMillis(currentTimestamp);
      }
    } else {
      // reset sequence to start with zero for the next millisecond
      sequence = 0;
    }

    lastTimestamp = currentTimestamp;

    long id = currentTimestamp << (NODE_ID_BITS + SEQUENCE_BITS);
    id |= (nodeId << SEQUENCE_BITS);
    id |= sequence;  // id = id | sequence;

    return id;
  }

  // Get current timestamp in milliseconds, adjust for the custom epoch.
  // 밀리초단위의 현재 타임스탬프를 가져온다. 그리고 커스텀 epoch로 조절한다.
  private static long timestamp() {
    return Instant.now().toEpochMilli() - CUSTOM_EPOCH;
  }

  // Block and wait till next millisecond
  // 다음 밀리초까지 블록하고 기다린다.
  private long waitNextMillis(long currentTimestamp) {
    while (currentTimestamp == lastTimestamp) {
      currentTimestamp = timestamp();
    }
    return currentTimestamp;
  }
}

generator는 시스템의 MAC address를 이용해서 Node의 unique identifier를 만든다.

June 9, 2018 10:00:00 AM GMT 를 예로들자. 이 시간의 epoch timestamp는 1528538400000 이다.

currentTimestamp = 1528538400000 - 1420070400000 // 108468000000 (Adjust for custom epoch)

이제, ID의 처음 41비트는 (signed bit 0은 빼고!)는 이 epoch timestamp로 채워질 것이다. 레프트 시프트를 수행하면 된다. 22비트를 시프트 하는 이유는 10 비트의 nodeId를 넣고, 12비트의 로컬 카운터를 넣을 것이기 때문이다.

id = currentTimestamp << (10 + 12)

// 10 bit의 node ID
// node 786
id |= nodeId << 12
// 12 bit의 counter
// sequence 3450
id |= sequence // 454947766275219456

6 instagram은 어떻게 할까?

기본적으로 트위터의 방식을 사용한다. 트위터는 논리적은 shard들이 수천개며, 이것보단 상대적으로 적은 물리적 샤드들에 매핑되어 있다.

이 방식을 이용하면 적은 데이터베이스 서버로 시작해서, 점점 데이터베이스가 많아질 때, 이 논리적 shard들을 옮기기만 하면 된다. 기존 데이터의 re-bucket을 하지 않아도 된다. 인스타그램은 Postgres의 schema 기능을 사용했다. 이것으로 script와 관리가 수월해졌다.

스키마는 Postgres의 논리적 그룹화 기능이다. 각 Postgres DB는 여러 스키마를 가질 수 있으며, 각 스키마는 하나 이상의 테이블이 포함될 수 있다. 테이블 이름은 스키마별로 고유해야 하며, 기본적으로 Postgres는 모든 것을 'public'이라는 스키마에 배치한다.

각 '논리적'샤드는 우리 시스템의 Postgres 스키마이며, 각 샤딩된 테이블(사진의 좋아요들)은 각 스키마 내부에 존재한다.

Postgres의 내부 프로그래밍 언어인 PL/PGSQL과 Postgres의 기존 자동 증가 기능을 사용하여 각 샤드 내부의 각 테이블에 ID생성을 위임했다.

ID는 아래처럼 구성된다.

  • 밀리초 타임스탬프 41비트 (커스텀 epoch기준 41년을 얻음?)
  • 논리샤드 ID를 표현하는 13비트
  • auto-incrementing sequence를 표현하는 10비트, 1024 modulus 이므로, 1024까지만 가지며, 샤드별로, 밀리초 별로 가진다.

일단 위에서 41비트가 41년이라고 하니까 의문을 가졌다.

(2^41)-1 ms
    == 2199023255.551 s
    == 610839.7932086 hr 
    == 25451.65805036 days 
    == 69.6828 Julian years 
    == 69.6843 Gregorian Years

그러므로 41년이 아니라 69년이 맞다. 어쩌면 18년을 이미 사용했는지도 모른다. 이 글은 2012년도에 작성한 글이다. 그렇다면 2012 + 41 - 69 = 1984 이다. 1984년은 무엇을 의미하는 것일까? 아니 조지오웰의 1984를…?

인스타그램은 그래서 아래와 같은 코드를 만들었다. (자세한 내용은 참고문헌링크 클릭) 인스타그램은 PL/PGSQL 을 이용했다

CREATE OR REPLACE FUNCTION insta5.next_id(OUT result bigint) AS $$
DECLARE
    our_epoch bigint := 1314220021721;
    seq_id bigint;
    now_millis bigint;
    shard_id int := 5;
BEGIN
    SELECT nextval('insta5.table_id_seq') %% 1024 INTO seq_id;
    SELECT FLOOR(EXTRACT(EPOCH FROM clock_timestamp()) * 1000) INTO now_millis;
    result := (now_millis - our_epoch) << 23;
    result := result | (shard_id <<10);
    result := result | (seq_id);
END;
    $$ LANGUAGE PLPGSQL;

테이블을 아래처럼 만든다.

CREATE TABLE insta5.our_table (
    "id" bigint NOT NULL DEFAULT insta5.next_id(),
    ...rest of table schema...
  )

그런데 이 방식에 문제를 제기하는 사람들이 있다. (해당 내용도 아래 링크를 걸어놓았다) 대강 내용은 마지막쯤에 가면 overflow가 일어난다는 뜻이다. unsigned라고 못박아놓으면 되는거 아닌가 싶지만 위 코드를 그대로 실행했을 때, overflow가 난다는 것이니 문제가 있는 코드는 맞나보다.

select (1992325551 << 23);
-----------------------------
 -679477248

오… 흥미롭다. 하지만 이 의견은 뭔가 간과한 것이 있다. PostgreSQL에 대해 잘 모르지만 분명 숫자를 콘솔에서 바로 쓰면 BIGINT가 아닐 것이다. 그래서 테스트해보았다.

select pg_typeof(1992325551);
-----------------------------
integer

PostgreSQL의 integer는 signed integer다.( -2147483648 to +2147483647 )

그렇다면 BIGINT로 계산해보면 어떨까

select pg_typeof(1992325551);
-----------------------------
integer
select (1992325551::bigint << 23);
-----------------------------
16712838055723008

뭔가 잘 나온 것 같다.

테스트는 다음 링크에서 했다. https://extendsclass.com/postgresql-online.html

twitter의 snowflake가 앞부분에 강제 0을 넣는 방식이 이런 것을 방지하기 위해 비트 하나를 버린 것 같기도 하다.

7 참고문헌

Date: 2022-01-30 Sun 00:00

Author: Younghwan Nam

Created: 2022-11-15 Tue 08:10

Emacs 27.2 (Org mode 9.4.4)

Validate