在 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 類的,但年代不同了...?

LLL lattice basis reduction algorithm

短短幾天內看到兩個不同的地方用到了 1982 年發現的「Lenstra–Lenstra–Lovász lattice basis reduction algorithm」。

第一個是「Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG (github.com/spawnmason)」這篇,作者群利用 LLL 去分析 java.util.Random 的內部狀態,進而得到其他玩家的地點資訊:

Every time a block is broken in Minecraft versions Beta 1.8 through 1.12.2, the precise coordinates of the dropped item can reveal another player's location.

"Randar" is an exploit for Minecraft which uses LLL lattice reduction to crack the internal state of an incorrectly reused java.util.Random in the Minecraft server, then works backwards from that to locate other players currently loaded into the world.

另外一個是在 Hacker News 上面的 id=40080651 提到,前幾天 PuTTY 的 p521 問題在底層也用到了 LLL:

LLL lattice reduction is the same algorithm that can be used for cracking PuTTY keys from biased nonces from the CVE a few days ago. 'tptacek explained a bit about the attack (and links to a cryptopals problem for it, which I can almost pretend to understand if I squint) https://news.ycombinator.com/item?id=40045377

從維基百科的內容也可以看出來 application 非常多,不光是密碼學的領域用到,看起來值得花點力氣來了解...

估算 YouTube 影片總量的方式

Hacker News Daily 上看到「How big is YouTube? (ethanzuckerman.com)」這篇,原文在「How Big is YouTube?」。

算是個老問題了,而且應該是統計學上比較簡單的方法。先列出作者最後的成果:「TubeStats」。

作者用的方法是觀察 YouTube 的 vid:

Here’s how this works: YouTube URLs look like this: https://www.youtube.com/ watch?v=vXPJVwwEmiM

可以分析出來 vid 包括了 64-bit 的資訊,這個資料型態對工程師來說,看起來就很像是 uniformly distributed:

That bit after “watch?v=” is an 11 digit string. The first ten digits can be a-z,A-Z,0-9 and _-. The last digit is special, and can only be one of 16 values. Turns out there are 2^64 possible YouTube addresses, an enormous number: 18.4 quintillion. There are lots of YouTube videos, but not that many. Let’s guess for a moment that there are 1 billion YouTube videos – if you picked URLs at random, you’d only get a valid address roughly once every 18.4 billion tries.

然後就是隨機去產生 vid 去掃,這個方法跟 drunk dialing 的行為很像,算是 random sampling 的方式:

We refer to this method as “drunk dialing”, as it’s basically as sophisticated as taking swigs from a bottle of bourbon and mashing digits on a telephone, hoping to find a human being to speak to. Jason found a couple of cheats that makes the method roughly 32,000 times as efficient, meaning our “phone call” connects lots more often. Kevin Zheng wrote a whole bunch of scripts to do the dialing, and over the course of several months, we collected more than 10,000 truly random YouTube videos.

另外在 2011 年就有提出來利用 autocomplete 機制去算:

By comparing our results to other ways of generating lists of YouTube videos, we can declare them “plausibly random” if they generate similar results. Fortunately, one method does – it was discovered by Jia Zhou et. al. in 2011, and it’s far more efficient than our naïve method. (You generate a five character string where one character is a dash – YouTube will autocomplete those URLs and spit out a matching video if one exists.) Kevin now polls YouTube using the “dash method” and uses the results to maintain our dashboard at Tubestats.

目前他們的預估大約是 13B 左右的影片,換算大約是用掉 33.63 bits 了 (233.6):

In our case, our drunk dials tried roughly 32k numbers at the same time, and we got a “hit” every 50,000 times or so. Our current estimate for the size of YouTube is 13.325 billion videos – we are now updating this number every few weeks at tubestats.org.

而這邊提到的 32768 * 50k 會中一次的部分,這邊的大約是 30.61 bits,這樣加起來是差不多 64 bits 沒錯。

不過要注意的是,他們沒有給出 interval,所以 13B 的上下可能是一倍左右的差距 (6.5B~26B 之類的),這邊的數字當作概念比較好...

GNU Make 在 4.4 引入的 --shuffle

Hacker News 首頁上看到的,作者送了一個提案到 GNU Make,後來被採用,在 4.4 版引入了 --shuffle 指令:「New make --shuffle mode」。

這個功能主要是想要找出在 Makefile 裡面沒有被定義好,平常是因為 side effect 而沒有出錯的地方。

像是作者就發現 libgfortran 沒有把 libquadmath 放到 dependency 的問題:

For example gcc’s libgfortran is missing a libquadmath build dependency. It is natural not to encounter it in real world as libquadmath is usually built along with other small runtimes way before g++ or gfortran is ready.

他的基本想法是把 target 的順序打亂掉,也就是在有指定 --shuffle 時,不一定會照 a -> b -> c 的順序往下遞迴,而可能會是 c -> b -> a 或是其他的順序:

all: a b c

這樣對於抓那些在 -j 平行編譯時會出包的套件也很有幫助,不需要在 -j 開很大的情況下才能重製問題,而是平常就有機會在 CI 環境下被抓出來。

Linux 打算合併 /dev/random 與 /dev/urandom 遇到的問題

Hacker News 上看到「Problems emerge for a unified /dev/*random (lwn.net)」的,原文是「Problems emerge for a unified /dev/*random」(付費內容,但是可以透過 Hacker News 上的連結直接看)。

標題提到的兩個 device 的性質會需要一些背景知識,可以參考維基百科上面「/dev/random」這篇的說明,兩個都是 CSPRNG,主要的分別在於 /dev/urandom 通常不會 block:

The /dev/urandom device typically was never a blocking device, even if the pseudorandom number generator seed was not fully initialized with entropy since boot.

/dev/random 不保證不會 block,有可能會因為 entropy 不夠而卡住:

/dev/random typically blocked if there was less entropy available than requested; more recently (see below, different OS's differ) it usually blocks at startup until sufficient entropy has been gathered, then unblocks permanently.

然後順便講一下,因為這是 crypto 相關的設計修改,加上是 kernel level 的界面,安全性以及相容性都會是很在意的點,而 Hacker News 上的討論裡面很多是不太在意這些的,你會看到很多「很有趣」的想法在上面討論 XDDD

回到原來的文章,Jason A. Donenfeld (Linux kernel 裡 RNG maintainer 之一,不過近期比較知名的事情還是 WireGuard 的發明人) 最近不斷的在改善 Linux kernel 裡面這塊架構,這次打算直接拿 /dev/random 換掉 /dev/urandom:「Uniting the Linux random-number devices」。

不過換完後 Google 的 Guenter Roeck 就在抱怨在 QEMU 環境裡面炸掉了:

This patch (or a later version of it) made it into mainline and causes a large number of qemu boot test failures for various architectures (arm, m68k, microblaze, sparc32, xtensa are the ones I observed). Common denominator is that boot hangs at "Saving random seed:". A sample bisect log is attached. Reverting this patch fixes the problem.

他透過 git bisect 找到發生問題的 commit,另外從卡住的訊息也可以大概猜到在虛擬機下 entropy 不太夠。

另外從他們三個 (加上 Linus) 在 mailing list 上面討論的訊息可以看到不少交流:「Re: [PATCH v1] random: block in /dev/urandom」,包括嘗試「餵」entropy 進 /dev/urandom 的 code...

後續看起來還會有一些嘗試,但短期內看起來應該還是會先分開...

Linux Kernel 裡的 RNG 從 SHA-1 換成 BLAKE2s

Hacker News Daily 上看到的消息,Linux Kernel 裡的 RNG,裡面用到的 SHA-1 演算法換成 BLAKE2s 了:

SHA-1 已知的問題是個隱患,不過換成 BLAKE2s 應該是 maintainer 的偏好,Jason Donenfeld 在 WireGuard 裡面也是用 BLAKE2s...

MySQL 在不同種類 EBS 上的效能

Percona 的人寫了一篇關於 MySQL 跑在 AWS 上不同種類 EBS 的效能差異:「Performance of Various EBS Storage Types in AWS」,不過這篇的描述部份不是很專業,重點是直接看測試資料建立自己的理解。

他的方法是在 AWS 上建立了相同參數的 gp2gp3io1io2 空間,都是 1TB 與 3000 IOPS,但他提到這應該會一樣:

So, all the volumes are 1TB with 3000 iops, so in theory, they are the same.

但這在「Amazon EBS volume types」文件上其實都有提過了,先不管 durability 的部份,光是與效能有關的規格就不一樣了。

在 gp2 的部份直接有提到只有保證 99% 的時間可以達到宣稱的效能:

AWS designs gp2 volumes to deliver their provisioned performance 99% of the time.

而 gp3 則是只用行銷宣稱「consistent baseline rate」,連 99% 都不保證:

These volumes deliver a consistent baseline rate of 3,000 IOPS and 125 MiB/s, included with the price of storage.

io* 的部份則是保證 99.9%:

Provisioned IOPS SSD volumes use a consistent IOPS rate, which you specify when you create the volume, and Amazon EBS delivers the provisioned performance 99.9 percent of the time.

另外在測試中 gp2gp3 的 throughput 看起來也沒調整成一樣的數字。在 1TB 的 gp2 中會給 250MB/sec 的速度,1TB 的 gp3 則是給 125MB/sec,除非你有加買 throughput。

另外從這句也可以看出來他對 AWS 不熟:

The tests were only run in a single availability zone (eu-west-1a).

在「AZ IDs for your AWS resources」這邊有提過不同帳號之間,同樣代碼的 AZ 不一定是一樣的區域,需要看 AZ ID:

For example, the Availability Zone us-east-1a for your AWS account might not have the same location as us-east-1a for another AWS account.

To identify the location of your resources relative to your accounts, you must use the AZ ID, which is a unique and consistent identifier for an Availability Zone. For example, use1-az1 is an AZ ID for the us-east-1 Region and it is the same location in every AWS account.

在考慮到只有設定大小與 IOPS 的情況下,剩下的測試結果其實跟預期的差不多:io2 貴但是可以得到最好的效能,io1 的品質會差一些,gp3 在大多數的情況下其實很夠用,但要注意預設的 throughput 沒有 gp2 高。

Kaspersky Password Manager 的漏洞

Hacker News Daily 上看到「Kaspersky Password Manager: All your passwords are belong to us」這篇,講 Kaspersky Password Manager (KPM) 嚴重的安全漏洞,另外在 Hacker News 上的討論「Kaspersky Password Manager: All your passwords are belong to us (ledger.com)」也有提到一些有趣的東西。

標題的 All your passwords are belong to us 是出自「All your base are belong to us」這個梗的變形。

這包安全問題主要的原因是因為 KPM 沒有使用 CSPRNG,而且也沒有正確 seed,所以極為容易被猜出密碼本身。

KPM 的 Web 版使用了 Math.random(),在各家瀏覽器主要是用 xorshift128+ 實做 Math.random(),作者沒有針對這塊再花時間研究,但很明顯的 Math.random() 不是個 CSPRNG:

The underlying PRNG used by Chrome, Firefox and Safari for Math.random() is xorshift128+. It is very fast, but not suitable to generate cryptographic material. The security consequences in KPM has not been studied, but we advised Kaspersky to replace it with window.crypto.getRandomValues(), as recommended by the Mozilla documentation page previously mentioned.

Note: Math.random() does not provide cryptographically secure random numbers. Do not use them for anything related to security. Use the Web Crypto API instead, and more precisely the window.crypto.getRandomValues() method.

而桌機版則是用了 MT19937,理論上取得 624 bytes 的輸出後就可以重建整個 PRNG 的內部狀態 (於是就可以預測後續的 output),但這代表你要知道其他網站的密碼,這點其實有點困難。

但作者發現 KPM 在產生 MT19937 的 seed 只跟時間有關,超級容易被預測:

So the seed used to generate every password is the current system time, in seconds. It means every instance of Kaspersky Password Manager in the world will generate the exact same password at a given second.

於是可以直接暴力解出所有的可能性:

The consequences are obviously bad: every password could be bruteforced. For example, there are 315619200 seconds between 2010 and 2021, so KPM could generate at most 315619200 passwords for a given charset. Bruteforcing them takes a few minutes.

Hacker News 上有不少陰謀論的討論,像是:

Getting some DUAL_EC prng vibes.

Insert Kaspersky owned by Russia intelligence conspiracy here...

另外 Kaspersky 跟俄羅斯軍方的關係也是很知名,這些東西大概要到十來年後才會知道...

Dan Kaminsky 過世

Hacker News 首頁上看到震驚的消息,Dan Kaminsky 過世:「Dan Kaminsky has died (twitter.com/marcwrogers)」,目前還沒看到過世的原因...

Dan Kaminsky 最有名的「成果」應該是在 2008 年發現當時大多數的 DNS resolver 軟體實做有問題,可以被 DNS cache poisoning 攻擊,當年我有寫下來提到,但寫的很短:「DNS 伺服器安全性更新」。

攻擊手法是先發一個 DNS query 到 DNS resolver,然後馬上再送出一個偽造的 DNS response packet 給 DNS resolver 收,運氣好的話這個偽造的結果就會被 cache 起來。

記得當年的 168.95.1.1168.95.192.1 沒有太直接受到影響 (相較於其他的 DNS resolver),是因為這兩個 DNS resolver 後面有 server cluster 會打散流量,所以未必能猜對去查詢時用的 DNS server 所使用的 IP address,有點類似下面提到的緩解方案 (只是沒那麼有效)。

而記得後來的緩解方式是透過亂數化 source port (讓 DNS resolver 查詢時不要從 port 53 出去問),這個方式讓攻擊機率大幅下降 (大約降到 1/2^{16} 的機率)。

後來 DNS 加上 nonce 機制再繼續壓低攻擊成功的機率 (再降一次 1/2^{16},變成大約 1/2^{32}),最後則是 DNSSEC 的支援度逐漸普及,才解決掉這個問題。

資安領域的重大損失,尤其在 DNS 這塊...

用 SSD 的 I/O 暴力解

這篇「Achieving 11M IOPS & 66 GB/s IO on a Single ThreadRipper Workstation」用了 AMD 平台上的 PCI-e 4.0 硬幹出 4K 隨機讀取 11M IOPS 的速度,另外在大區塊讀取可以到 66GB/sec,後面這個速度應該是可以把 DDR4 記憶體頻寬吃滿...

硬體的部份,作者用了 8*1TB + 2*500GB 的 M.2 SSD 來建這組系統,然後接到卡上:

不過他好像沒提到這組機器的價錢 (雖然每個單品都查的到),大概算了一下 storage 的部份其實不怎麼貴,Samsung 980 Pro PCIe 4.0 M.2 SSD 的部份,1TB 每一條要 USD$160,500GB 要 USD$120,旁邊那些 CPU 與記憶體反而貴不少... 不過整台機器應該有機會在 USD$10000 搞定?

感覺拿來給剪片的人用很爽?至少在處理讀寫的時候應該是很順...