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

1 UUID

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

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

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

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

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

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

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

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

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

page filter factor

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

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

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

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

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

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

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

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 인덱스는 모두 많은 양의 공간을 요구하게 될 것이다. 이는 디스크와, 메모리 둘 다에게 요구된다. 버퍼풀이 테이블 페이지와 인덱스 페이지를 모두 갖고 있기 때문이다.