[220202] 순서가 있으면서 좀 더 크기가 작은 새로운 ID, TSID.

Table of Contents

1 UUID

mysql의 UUID() 는 UUID.v1 이며, java.randomUUID() 는 UUID.v4를 리턴한다. UUID를 사용하는 몇가지 이유가 있다.

  1. 어플리케이션에서 ID를 만들 수 있다. 하여 중앙에서 관리할 필요가 없어졌다.
  2. 충돌 가능성이 아주 낮다.
  3. ID로 추측할 수 없어서 안전하게 공개할 수 있다.

하지만 UUID를 db에 저장하는 것은 좋지 않은 생각이다.

1.1 첫째

UUID는 큰 값이다. 모든 단일 식별자에 16바이트가 필요하며, 이는 연결된 모든 외래키에도 영향을 미친다.

1.2 둘째

PK는 일반적으로 B+ Tree인덱스가 있음. 이는 데이터를 정렬된 순서로 저장함. 여기서 랜덤한 값을 저장하게 되면 문제가 생김.

  • 값이 랜덤하게 온다면, 현재 쓰고 있는 페이지의 뒤를 이어서 계속 쓰는 것이 아니라 페이지를 새로 만들어서 앞에 붙여야 한다. 그러면 8kb 페이지가 꽉 차지 않는 경우가 많아진다. 이렇게 버려지는 공간이 많아진다. disk와 데이터베이스의 버퍼풀 캐시 또한 마찬가지다.
  • 정렬이 계속 발생한다. 트리를 리밸런싱 하면서 더 많은 인덱스 페이지 분할과 병합이 수행된다.
  • Mysql, sqlserver를 쓰면 문제는 더 심각해짐 왜냐면 PK가 기본적으로 클러스터드 인덱스이기 때문이다.

1.2.1 B+Tree

클러스터드 인덱스에서 사용하는 B+ Tree는 B-Tree 와 다르게 모든 키가 리프에 존재하고, 근처에 있는 값을 포인터로 연결한다. (그래야 레인지 조회가 쉽기 때문인듯)

1.2.2 Clustered Index and Secondary Index

세컨더리 인덱스는 리프노드에 PK 키 값을 저장하고 있다. 모든 세컨더리는 찾고자 하는 값을 PK의 키에 의존한다. 그래서 PK의 키 크기는 최대한 간결한 것이 좋다. int는 4바이트 bigint는 8바이트이므로 잘 생각해야 한다.

예를 들어, 유저의 경우 만약에 나의 애플리케이션이 int를 절대 초과하지 않는 모델이라면 굳이 8바이트가 필요 없을 것이다.

1.2.3 Clustered Index column monotonicity (monotonically increasing)

또한 B+Tree는 균형을 계속 유지하는 자료구조이다. 그러므로 키가 추가될 때 단조롭게 증가하는 것이 좋다.

  1. page filter factor

    리프노트드는 여러 레코드를 수용할 수 있으며, 각 레코드를 차례로 추가하면 페이지가 효율적으로 채워져서 페이지에 빈공간이 줄어든다. 그 결과 필요한 페이지 수를 줄일 수 있다. UUID를 PK로 사용하면 새로운 UUID는 기존 리프페이지를 찾지 못할 수 있으므로(?) 점점 더 많은 리프 페이지가 할당되고 부분적으로만 채워진다.

  2. cause many page splits

    왜냐하면 UUID는 랜덤한 순서로 insert가 수행되기 때문이다. 이로써 DB엔진이 더 많은 인덱스 관리 업무를 수행해야 한다.

  3. Buffer Pool

    만약에 Clustered Index가 아주 크고 한번에 메모리로 올릴 수 없다면, 단조롭게 증가하는 PK 값이 버퍼풀에서 값을 찾을 확률이 더 높다. 반대로 무작위로 생성된 리프 노드가 버퍼 풀에서 찾을 확률이 더 낮을 수 있겠다.

    왜 버퍼풀에 캐시된 페이지를 만날 확률이 단순하게 증가하는 값일 때 만날 확률이 높을까? 버퍼풀은 기본적으로 LRU(least recently used) 알고리즘으로 캐시를 관리한다. (https://dev.mysql.com/doc/refman/8.0/en/innodb-buffer-pool.html) 그러므로 증가하는 값을 PK로 사용하면 현재 가장 큰 값은 버퍼풀에 캐시되어 있을 것이니 추가가 쉬워질 것이다.

2 TSID (Time-Sorted Unique Identifiers)

UUID를 PK로 추가하고 싶다면, TSID를 사용하는 것이 더 좋다.

TSID Creator 에서 제공한다. 이것은 64-bit TSID를 제공한다. 이는 두 부분으로 나뉜다.

  • a 42-bit time component
  • a 22-bit random component

여기서 random component는 아래로 구성된다.

  • a node identifier (0 to 20 bits)
  • a counter (2 to 22 bits)

tsid-creator 라는 깃허브에 보니 기본 개념은 Snowflake ID를 따왔다고 한다. Snowflake ID

그러면 이전에 블로그에 작성한 uid 관련 블로그에 있는 트위터의 snowflake 구현체를 참고하면 될 것 같다.

TSID는 UUID의 절반인 64-bit이면서 B+Tree 인덱스 키에 적합하다. 물론 SQLServer는 NEWSEQUENTIALID 제공하지만 이또한 128-bit의 GUID 이다.

UUID 7버전을 보면 7버전에는 new time-based UUID 로 만드려고 하나보다. 조금 아쉬운 점은 역시나 128-bit 라는 점이다.

만약 모든 PK가 128-bit 라면 PK, FK 인덱스는 모두 많은 양의 공간을 요구하게 될 것이다. 이는 디스크와, 메모리 둘 다에게 요구된다. 버퍼풀이 테이블 페이지와 인덱스 페이지를 모두 갖고 있기 때문이다.

3 출처 :

Date: 2022-02-02 Wed 00:00

Author: Younghwan Nam

Created: 2024-01-04 Thu 09:13

Emacs 27.2 (Org mode 9.4.4)

Validate