在 PostgreSQL 裡,當 UUID 當作 Primary Key 時要怎麼處理

繼續清 tab,在「PostgreSQL and UUID as Primary Key (maciejwalkowiak.com)」這邊看到的,原文是討論 PostgreSQL 要怎麼處理 PK 是 UUID 的情況:「PostgreSQL and UUID as primary key」。

文章開頭作者就說了,這篇不是要戰 PK 要不要用 UUID,而是已經決定要用了 (i.e. 通常不是你決定的),在接手以後要怎麼用比較好:

Considering the size of UUID it is questionable if it is a right choice, but often it is not up to us to decide.

This article does not focus on "if UUID is the right format for a key", but how to use UUID as a primary key with PostgreSQL efficiently.

首先是 PostgreSQL 從 8.3 版 (2008 年) 就支援 UUID 的資料型態了,這點從 release note 可以看到:「PostgreSQL 8.3.0」,所以要當 PK 的話沒什麼道理不考慮他。

UUID 的空間上就是 128-bit data (16 bytes),相比於 TEXT 會省蠻多的,尤其 PK 常常會被其他表格 reference 到 (像是 foreign key) 會在其他表格也省下來:

Table that uses text is 54% larger and the index size 85% larger.

第二點則是考慮到 UUID 本身的特性,以前的 UUID 因為是亂數生成的 (通常會用 UUIDv4),對寫入 B-tree 類的資料結構不是很有效率,改用 UUIDv7 (差不多是這兩年陸陸續續發展出來的規格) 會得益於與 timestamp 有關,對 B-tree 寫入的效率會好很多:

Random UUIDs are not a good fit for a B-tree indexes - and B-tree index is the only available index type for a primary key.

B-tree indexes work the best with ordered values - like auto-incremented or time sorted columns.

UUID - even though always looks similar - comes in multiple variants. Java's UUID.randomUUID() - returns UUID v4 - which is a pseudo-random value. For us the more interesting one is UUID v7 - which produces time-sorted values. It means that each time new UUID v7 is generated, a greater value it has. And that makes it a good fit for B-Tree index.

作者的測試可以看到寫入速度與 UUIDv4 相比比快不少:

BUT we can clearly see, that inserting UUID v7 is ~2x faster and inserting regular UUID v4.

總結來說,當 PK 已經決定是 UUID 後,主要就是這兩個重點可以注意的,當然 Hacker News 上更熱鬧的是兩派人馬在吵要用 integer 類的 SERIAL/BIGSERIAL 還是用 UUID,那又是另外一個話題了...

如果早個二十年前對 memory size 斤斤計較的情況下,答案鐵定是 integer 類的,但年代不同了...?

UUID 的 UX

在「The UX of UUIDs (unkey.dev)」這邊看到的紋章,原文在「The UX of UUIDs」。

裡面有不少是有幫助的建議,像是第一個建議是把 UUID 裡面的 - 拿掉,這樣對於 copy 比較方便 (畢竟大多數人應該是 copy UUID,不會是念出來?)。

第二個建議是加上 prefix,這點不一定侷限在 UUID,只要是 token 上面都很適合。這個在不少系統上應該都有看過,像是 GitHub 的 token,或是 AWS 的 token 都算是這類。

文章裡面沒有提到,但這個建議也可以幫助你在 CI 上設定 regex,擋下把 secret token 寫進去的行為。

第三個提到用 base58,一方面是減少長度,另外一方面是想要避免 1IiLl0Oo 的問題,這點我覺得還好... 既然都是 copy & paste 了,我覺得拿 base62 (i.e. 大小寫加上數字) 不錯,這避免特殊字元無法選擇到,也就是文章裡面第一個建議。

第四個建議是建議重新思考 range,因為 UUID 的 128-bit range 很大,但不是所有應用都需要用到這麼大的範圍確保 collision-free (於是可以當 primary key)。

這點讓我想到 X (Twitter) 當初發表的 Snowflake ID,在 Twitter 這種規模下 64-bit range 也已經夠用。

後面的文章內容就是在推銷自家東西,我就... 跳過了。

2019 年 Percona 對 UUID 當作 Primary Key 的看法

前陣子的「為資料庫提案新的 UUID 格式」這邊提到了有人提案要增加新的 UUID 格式,Percona 的老大 Peter ZaitsevTwitter 上貼了「UUIDs are Popular, but Bad for Performance — Let’s Discuss」這篇在 2019 年時他們家的文章,題到了 MySQL 使用 UUID 當作 Primary Key 的事情:

要注意的是這篇文章沒有要從頭解釋 UUID 對於 Primary Key 的壞處,如果你想要先了解的話,在這篇文章的開頭給了一堆其他文章的連結,裡面就有討論過了。

這篇主要是在討論,如果硬要用 UUID 當 Primary Key 時,可以有什麼方法降低對 InnoDB 的衝擊,剛好回應最近的提案。

開頭還是先花了一些篇幅大概講一下 UUID 的種類,然後在「What is so Wrong with UUID Values?」這邊提到了字串比較的差異,如果 UUID 是到最後一碼才不同的話 (這邊是跑 df878007-80da-11e9-93dd-00163e000002 與 df878007-80da-11e9-93dd-00163e000003 與比較一億次):

1 row in set (27.67 sec)

但如果是一開始就不同的話 (這邊是選擇 df878007-80da-11e9-93dd-00163e000002ef878007-80da-11e9-93dd-00163e000003) 會快很多:

1 row in set (2.45 sec)

但如果與數字相比的話 (這邊是 2=3 這樣的條件去比):

1 row in set (0.96 sec)

可以看數字在這邊的優勢,另外也是在說明,如果你用的是 time-based ordering 的 UUID,要考慮會遇到這個可能會發生的效能問題。

再來是玩 UUID 的三種不同的儲存方式對於寫入效能的差異,分別是 CHAR(36) (32 bytes 的 hex 加上四個 -)、base64 (用 CHAR(22) 存) 與 BINARY(16),可以看出來 BINARY(16) 因為佔用空間比較小的關係,是可以高速寫入持續最久的,再來是 base64,最差的是 CHAR(36)

後面給了兩個 workaround,第一個算是定義了另外一種產生 128 bits 的方式,第二個則是想辦法把 UUID 對應到數字。

這在 MySQL 的環境裡面算是被討論的很久的主題了。(我猜在 PostgreSQL 應該也是,不過 PostgreSQL 的社群沒跟那麼久...)

為資料庫提案新的 UUID 格式

前幾天在 Hacker News Daily 上看到的東西,今年四月的時候有人針對資料庫提案新的 UUID 格式:「New UUID Formats – IETF Draft (ietf.org)」。

在 draft 開頭有說明這個提案的目標:

This document presents new time-based UUID formats which are suited for use as a database key.

A common case for modern applications is to create a unique identifier for use as a primary key in a database table. This identifier usually implements an embedded timestamp that is sortable using the monotonic creation time in the most significant bits. In addition the identifier is highly collision resistant, difficult to guess, and provides minimal security attack surfaces. None of the existing UUID versions, including UUIDv1, fulfill each of these requirements in the most efficient possible way. This document is a proposal to update [RFC4122] with three new UUID versions that address these concerns, each with different trade-offs.

另外在 Hacker News 上有人整理出來,可以直接理解提案所提出的新格式是什麼:

A somewhat oversimplified summary of the new UUID formats:

UUID6: a timestamp with a weird epoch and 100 ns precision like in UUID1, but in a big-endian order that sorts naturally by time, plus some random bits instead of a predictable MAC address.

UUID7: like UUID6, but uses normal Unix timestamps and allows more timestamp precision.

UUID8: like UUID7, but relaxes requirements on where the timestamp is coming from. Want to use a custom epoch or NTP timestamps or something? UUID8 allows it for the sake of flexibility and future-proofing, but the downside is that there's no standard way to parse the time from one of these -- the time source could be anything monotonic.

這在不同的 storage engine 上面會有不同的討論,這邊先討論 MySQL 系列的 InnoDB,至於 PostgreSQL 的 engine 以及其他資料庫系統,就另外讓更熟悉的人討論了。

InnoDB 採用了 clustered index (可以參考「Database index」這邊的說明),也就是資料本體是以某種定義的大小順序存放。

在 InnoDB 裡面則是用 primary key 的順序來存放資料 (沒有指定 primary key 時會有 fallback 行為),其他的 unique key 與 index key 則是指到 primary key,所以你可以看到 primary key 的大小也會影響到其他的 index key。

所以 128 bits 的 UUID 在大型的 MySQL ecosystem 實在不怎麼受歡迎,在 2010 年的時候 FlickrTwitter 都有發表過 ticket system:「Ticket Servers: Distributed Unique Primary Keys on the Cheap」、「Announcing Snowflake」,兩個系統有不同的需求,但都是產生 64 bits 的 unique id。

其中 Flickr 的系統算是很簡單的,沒有要保證時間順序 (i.e. 先取的號碼一定比較小,以及後取的號碼一定比較大),就用兩台 MySQL 跑 active-active 架構,然後錯開產生的值:

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

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

到現在還是一個蠻簡單的解法...

增加工作效率:關閉 Mac 上切換視窗時的動畫效果

把各種動畫效果時間減少主要是因為要降低對「短期記憶」的影響,尤其年紀大了以後特別有感覺:

短期記憶(英語:Short-term memory,也稱為primary memory或者active memory)是記憶的一種類型,它可以在頭腦中讓少量資訊保持啟用狀態,在短時間內可以使用。短期記憶的持續時間(在沒有複述或者啟用的情況下)以秒計算。與長期記憶相比,短期記憶對資訊的儲存時間較短,資訊儲存的容量也很有限。關於短期記憶的容量,一個常常參照的數字是7 ± 2 個元素。

在這個基礎下,半秒鐘到一秒鐘的動畫效果對於短期記憶的影響其實非常大,所以花了些時間找看看怎麼關掉...

後來在「How can I disable animation when switching desktops in Lion?」這篇翻到,裡面主要有兩個方法,一個是用 command line 的方法,但我測了不會動 (在 10.14.3 上),另外一個方法是已經被整合進系統了:

改了以後快不少,但要習慣一下...

InnoDB 對 Primary Key 的選擇

前幾天 Ant 在「淺入淺出 MySQL & PostgreSQL」剛好有提到,結果 Percona 這兩天也丟出了這個題目,不過這邊討論的是空間的問題:「Illustrating Primary Key models in InnoDB and their impact on disk usage」。

一樣的作法,Primary Key 的選擇有三種:

  • INT + AUTO_INCREMENT
  • BINARY(16) (Ordered UUID)
  • CHAR(36) (Random UUID)

用的是 Jeremy Colespace-lsn-age-illustrate 畫出 LSN 的值 (InnoDB 的 Log Sequence Number,由於嚴格遞增,可以藉由這個值知道每個 page 最新被修改的時間):

I then used the powerful tool innodb_space’s function space-lsn-age-illustrate (from Jeremy Cole’s innodb_ruby project) to plot the LSN (InnoDB’s Log Sequence Number, an always-incrementing value) pages from each table that uses the different Primary Keys via ASCII colour (so hot, right? Thanks Jeremy!!).

測試是 INSERT-only 的 case,雖然不太能理解為什麼要用 CHAR(36) 存 UUID,而非與 BINARY(16),但可以看出一些 pattern。

有順序的 INT + AUTO_INCREMENT 與 BINARY(16) (Ordered UUID) 都可以看出層次 (一直往後寫),而且也看得出來 BINARY(16) 比 INT 大了不少:

而 CHAR(36) 當然是最大的,而且寫入的 i/o 也最隨機:

Amazon DynamoDB 筆記

Amazon DynamoDB 頁面上的介紹:

Amazon DynamoDB is a fast and flexible NoSQL database service for all applications that need consistent, single-digit millisecond latency at any scale.

資料型態的部份就跳過去了,這篇筆記的重點在於 index 的部份 (了解他如何 scale),尤其是對 RDBMS 有了解的人要如何從他所設計的架構理解 DynamoDB 的 index。

理論基礎是 Amazon 在 2007 年丟出的論文「Dynamo: Amazon’s Highly Available Key-value Store」,這篇論文影響了很多 open source project。

DynamoDB 的 index 有 Primary Key、Local Secondary Index Key (LSI) 以及 Global Index Key (GSI),在「DynamoDB Data Model」這篇有介紹。

這邊會拿 Blogger.com 這種多人的 Blog Hosting 當例子:

  • 一個 user 可以有很多 blog。(table user)
  • 一個 blog 可以有很多 post。(table blog)
  • 一篇 post 可以有很多 comment。(table post)

接下來就從 Primary Key 開始講。

Primary Key

Primary Key 保證唯一,這也是 DynamoDB 裡面可以達到 RDBMS 的 UNIQUE KEY 效果的最佳方式。

有兩種 Primary Key 的型態,一種叫做 Hash,另外一種叫做 Hash-Range。

兩種都需要指定某一個欄位是 Hash-based column,當作切割 (partition) 的依據。

第一種:Hash

以 table user 來說,可以拿 user_id 來當作 Hash-based column,裡面有 blog_id 的 list。

以 table blog 來說,可以拿 blog_id 來當作 Hash-based column,裡面有 post_id 的 list。

要注意的是,如果表格 PK 是 Hash,那麼就不能使用 LSI 與 GSI 了。只有另外一種型態 (Hash-Range) 才可以用 LSI 與 GSI。

相對的,Hash-based 的表格因為功能有限,效率通常很好 XDDD

第二種:Hash-Range

其實 Hash-Range 是一種別的 LSI,兩者最大的差異就是唯一性了。

另外一種 Primary Key 是 Hash-Range,他需要指定兩個欄位,其中其中 Hash 的欄位就如同上面的解釋,當作資料切割的依據。這邊的唯一性是指 (Hash column, Range column) 唯一,而非只有 Hash 唯一或是 Range 唯一。

剛剛說到需要指定的另外一個欄位,被稱為「Range」的原因是因為他可以有效率的以 hash + range query 查詢資料。

以 table post 來說,可以拿 blog_id 當作 Hash-based column,再拿 post_id 當作 Range-based column,等下我們介紹 LSI 時再拿發表時間欄位排序。

同理,table comment 可以拿 (post_id, commend_id) 當 PK。

Query

PK 是 Hash 的當然就是指定 Hash-based column 直接查,條件只能是等號。

PK 是 Hash-Range 的除了可以用 Hash-based column 直接查 (還是只能用等號),另外可以用 Hash-based column + Range-based column 查。

以 SQL 的想法就像是 WHERE hash_col = 123 AND range_col BETWEEN (123, 456) 的感覺。反正 Hash-based column 一定要等號。

講到這邊,其實讀過上面提到的 Amazon 那篇論文應該就大概有感覺架構是怎麼搞的了:(這是推敲出來的,未必是實際架構)

  • 用 Hash-based column 切 consistent hash ring 塞到不同機器上。PK 是 Hash 的到這邊就搞定了。
  • PK 是 Hash-Range 的,還是照上面一條提到的,用 Hash-based column 切開,所以同樣的 Hash-based column 的資料都會塞到同一台機器上,於是就可以用有效率的 ordered tree 來存放 Range-based column 的資料,這樣就可以提供 query 了。

當然,考慮到需要實做 rebalance 機制以逐步擴充,這邊 consistent hash ring 的部份的作法可以更細膩,不過就不是這篇要談的重點了。

接下來要講重頭戲 LSI 與 GSI 了。

Local Secondary Index (LSI) 與 Global Secondary Index (GSI)

前面有提到 LSI 與 GSI 必須 PK 是 Hash-Range 的情況下能用,兩者都不強制唯一性。

LSI 與 GSI 都是 (Hash-column based, Range-column based) 的形式,差別在 LSI 的 Hash-column based column 必須跟 PK 的相同,GSI 的可以不用一樣。

所以對於 table post 可以加一個 LSI (blog_id, post_datetime),就可以用 WHERE blog_id = 123 ORDER BY post_datetime DESC 拉出對應的文章了。

同理,table comment 是 (post_id, comment_datetime)。

資料庫裡 Primary Key 的選擇...

Ingram Chen 寫的「Obvious Choice」這篇舉的例子剛好是在討論資料庫裡 Primary Key 的設計。

這個問題之前在 interview 的時候曾經拿出來問。問到資料庫相關的題目時,有些人在設計 schema 會多放一個 id 欄位,有些人則不會放。

有放 id 欄位的我就會問「為什麼要放」,沒有 id 欄位的我就會問「為什麼不這樣設計」。重點不在於哪個才是正確的,而是在於要能夠說明為何這樣選擇。

不過大多數人都是「看別都這樣做,所以我就這樣做」,可惜...

用 InnoDB 時關於 PRIMARY KEY 的建議

Percona 的「InnoDB scalability issues due to tables without primary keys」這篇文章在討論 InnoDB 在沒有 PRIMARY KEY 時的效能問題。

在討論效能問題前,應該先讀過 MySQL 官方文件裡提到 InnoDB index 架構的文章,其中就有提到 PRIMARY KEY 以及其他的 INDEX KEY 的底層架構:「InnoDB Table and Index Structures」。

InnoDB 是 clustered index 架構 (關於 clustered index 的完整說明,可以參考維基百科的「Database index」條目),也就是說,資料本身 (row data) 存放時會按照某個順序存放,這邊的順序是按照這樣的方式定義的:

  • 如果你有指定 PRIMARY KEY,那麼就會直接用 PRIMARY KEY 當作 clustered index。
  • 如果沒有指定 PRIMARY KEY,但有 UNIQUE INDEX,而且所有欄位都是 NOT NULL,那麼就用這組 UNIQUE INDEX (NOT NULL) 當作 clustered index。
  • 如果都沒有指定 PRIMARY KEY,那麼就會產生一個隱藏的欄位,是一個 6 bytes 的 auto increment 的數字,用這個欄位當 clustered index。也因為如此,在這種情況下,資料會依照建立的順序存放。

另外,InnoDB 的 secondary index 會指到 PRIMARY KEY (B+Tree 的 value 部分是放 PRIMARY KEY)。

所以,一般在規劃資料庫時建議的作法是:

  • 所有的表格都要有 PRIMARY KEY。
  • PRIMARY KEY 必須是 INT UNSIGNED (4 bytes),只有在需要 BIGINT UNSIGNED (8 bytes)的時候才用 BIGINT UNSIGNED。

對於有大量 secondary index 的表格更應該這樣做 (因為可以省下大量空間)。而對於現代的 ORM 來說,也都幾乎要求要有 PRIMARY KEY,甚至有些 ORM 要求 PRIMARY KEY 必須是 single column。

如果你都能了解後,再去看 Percona 討論沒有 PRIMARY KEY 的情況時,才能了解他們想要討論什麼事情... 裡面還包含了 InnoDB 格式的差異。

把 MySQL MyISAM 換到 Galera Cluster 的 InnoDB 上...

在「Switching from MySQL/MyISAM to Galera Cluster」這邊看到一個 script 可以檢查 MySQL MyISAM 換到 InnoDB,而且預定要換成 Galera Cluster 時的問題。

常見的問題都有檢查到,還蠻有用的:

  • 針對沒有 Primary Key 的表格提出警告,讓管理者規劃補上 Primary Key。
  • 針對 MyISAM 換成 InnoDB 後造成 Primary Key 太長的表格提出警告,讓管理者想辦法修改。

Galera Cluster 無法處理沒有 Primary Key 表格的刪除動作:(可以參考「MariaDB Galera Cluster - Known Limitations」這邊的說明)

DELETE operation is unsupported on tables without primary key. Also rows in tables without primary key may appear in different order on different nodes. Don't use tables without primary key.

不過每個表格都要有 Primary Key 並不難,因為如果有正規化時通常都會達到目標。就算不去用他也還是可以設計一個 INT UNSIGNED PRIMARY KEY AUTO_INCREMENT 放著。(過大的時候再換成 BIGINT UNSIGNED)