ULID, UUID와 MySQL B-tree index

최근 ULID(https://github.com/ulid/spec)가 팀 내에서 화제거리이다.

ULID를 PK로 했을 때, auto_increment의 sequencial insert 패턴과 비교해 어떤 움직임이 있는 지, 그리고 어떤 영향을 예상할 수 있을까에 대해서 조금 이야기 해 보고 싶다.

 

우선 UUID의 이야기를 보면, UUID는 기본적으로 random성격의 ID가 발행되는 데, 이 것을 PK로 해서 MySQL에 insert할 때에는  random으로 들어갈 가능성이 높을 것으로 생각된다. 이 때 MySQL이 사용하고 있는 B-tree index는 어떤 동작을 할까?

많은 사람들은 B-tree index의 "B"는 Binary라고 생각하는 사람도 많은 것 같은데, 여기서 B는 "Balanced"의 의미이다.
그런 의미로 Balanced-index는 항상 Balance를 유지하기 위해서 일정한 알고리즘으로 index를 reorganized하게 된다.
즉, Index를 merge 하거나, split 하거나, reorganized 하는 것으로, 최적의 tree를 만들게 된다. 그리고 새로운 insert가 들어가도 Balance가 무너지지 않도록 어느 정도의 빈 공간을 확보하게 되어 있다.

여기에서 데이터가 무작위로 들어오면 다양한 곳에서 이 rebalance 작업이 수행되어 성능에도 영향을 줄 수 있다.

 

그러나 UUID와 달리 ULID는 다음과 같은 특징이 있다.

• 128-bit compatibility with UUID
• 1.21e+24 unique ULIDs per millisecond
• Lexicographically sortable! (사전순의 소팅가능!)
• Canonically encoded as a 26 character string, as opposed to the 36 character UUID
• Uses Crockford’s base32 for better efficiency and readability (5 bits per character)
• Case insensitive
• No special characters (URL safe)
• Monotonic sort order (correctly detects and handles the same millisecond)

그리고, 아래와 같은 구조를 가지고 있다.
확실히 일정한 코드가 되는 이 timestamp가 앞쪽에 있기 때문에 insert할 때, sequencial data가 될 것으로 보인다.
물론 auto_increment처럼 완전한 sequencial data 되는지는 조금 의문~ (이런 부분을 검증해 볼 필요가 있을듯 한데, 시간이~~)

 01AN4Z07BY      79KA1307SR9X4MV3
|----------|    |----------------|
 Timestamp          Randomness
   48bits             80bits

여기서, MySQL의 B-tree index를 생각해 보자.
앞으로 ULID를 PK로 채택하려 할 때는 MySQL에서 Index page의 rebalance를 한 번 진지하게 확인해 나갈 필요가 있을지도 모른다.

확인 방법은 아래와 같이 informantion_schema로 확인할 수 있을 것 같다.
(참고로, AWS Aurora/RDS도 확인 가능하다~)

mysql> SELECT NAME, COMMENT FROM INFORMATION_SCHEMA.INNODB_METRICS
    ->        WHERE NAME like '%index_page%';
+--------------------------------+-------------------------------------------------+
| NAME                           | COMMENT                                         |
+--------------------------------+-------------------------------------------------+
| index_page_splits              | Number of index page splits                     |
| index_page_merge_attempts      | Number of index page merge attempts             |
| index_page_merge_successful    | Number of successful index page merges          |
| index_page_reorg_attempts      | Number of index page reorganization attempts    |
| index_page_reorg_successful    | Number of successful index page reorganizations |
| index_page_discards            | Number of index pages discarded                 |
+------------------------- ------+-------------------------------------------------+
6 rows in set (0.00 sec)

이 값을 확인하면서 ULID, UUID가 실제 일반적으로 쓰이는 sequencial_id (e.g. Int with Auto_increment)와 비교해 DB 관점에서도 허용 범위인지 아닌지 검토 해 볼 필요가 있을지도 모른다.

 

그리고, rebalance가 많이 보이고 있다면, Threshold를 바꾸면서 index의 작성 성능도 개선해 나갈 수 있다.

ALTER TABLE t1 COMMENT='MERGE_THRESHOLD=40';

여기까지 B-tree index와 ULID, UUID 등의 관계성에 대해 조금 살펴보았다~