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

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

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

Ribbon filter

RocksDB 的 blog 上看到「Ribbon Filter」這個,主要是 RocksDB 從 6.15 開始支援 Ribbon filter,取代本來的 Bloom filter 機制。

RocksDB 的 wiki 上面是說用 CPU 資源換 memory 的使用量:

A new Bloom filter alternative is available as a drop-in replacement (since version 6.15.0), saving about 30% of Bloom filter space (most importantly, memory) but using about 3-4x as much CPU on filters. Most of the additional CPU time is in the background jobs constructing the filters, and this is usually a good trade because it is common for SST filters to use ~10% of system RAM and well under 1% of CPU.

論文則是在「Ribbon filter: practically smaller than Bloom and Xor」這邊可以看到,Facebook 之前也有提到 Ribbon filter:「Ribbon filter: Practically smaller than Bloom and Xor」,在 Hacker News 上有對應的討論可以翻:「Ribbon filter: Practically smaller than Bloom and Xor (fb.com)」。

在 Ribbon filter 的資料裡面都提到了 Xor filter 當作比較,先前在「比 Bloom filter 與 Cuckoo filter 再更進一步的 Xor filter」這邊有提到 Xor filter。

用 CPU 去換記憶體,算是特化的版本...

DeepMind 的 Player of Games

前幾天在 Hacker News Daily 上看到的消息,DeepMind 發了一篇新的論文,講 Player of Games 這個新的演算法:「Player of Games」,Hacker News 上的討論在這:「Player of Games (arxiv.org)」。

照留言上的討論,Player of Games 的名字由來應該是取自科幻小說《The Player of Games》。

這是一個更一般性的演算法,可以同時駕馭 perfect information 與 imperfect information:

We introduce Player of Games, a general-purpose algorithm that unifies previous approaches, combining guided search, self-play learning, and game-theoretic reasoning. Player of Games is the first algorithm to achieve strong empirical performance in large perfect and imperfect information games -- an important step towards truly general algorithms for arbitrary environments.

論文裡面也提到以前的各種演算法 (包含 DeepMind 自家的一些演算法)。在 perfect information 的例子來說,可以看到沒有 AlphaZero 強 (西洋棋與圍棋),但也已經有一定水準了,算是個起頭的感覺:

主要的成就在於一般性,但論文後面也有提到,目前這個演算法需要的資源還是過大,還有改善的空間...

QOI 圖片無損壓縮演算法

Hacker News Daily 上看到「Lossless Image Compression in O(n) Time」這篇,作者丟出了一個圖片的無損壓縮演算法,壓縮與解壓縮的速度超快,但壓縮率又不輸 PNG 太多,在 Hacker News 上的討論也可以看一下:「QOI: Lossless Image Compression in O(n) Time (phoboslab.org)」。

裡面有提到在遊戲產業常用到的 stb_image.h

Yes, stb_image saved us all from the pains of dealing with libpng and is therefore used in countless games and apps. A while ago I aimed to do the same for video with pl_mpeg, with some success.

作者的簡介也可以看到他的主業也在遊戲這塊:

My name is Dominic Szablewski. I build games, experiment with JavaScript and occasionally tinker with low-level C.

圖片的無損壓縮與解壓縮算是遊戲創作者蠻常用到的功能,所以他想要看看這塊有沒有機會有更好的工具,於是他就用了四個很簡單的演算法幹完了 QOI (然後發現效果很讚):

  • A run of the previous pixel
  • An index into a previously seen pixel
  • The difference to the previous pixel
  • Full rgba values

其實從 Hacker News 的討論也可以看到這組演算法也常被拿出來在現代的壓縮演算法使用,所以雖然作者自稱不是 compression guy,但他用的演算法其實蠻專業的...

然後挑 single thread 主要是可以避免 threading 的複雜度以及 overhead,在「QOI Benchmark Results」這頁可以看到,無論是什麼類型的檔案,壓縮與解壓縮的速度都相當漂亮,而且壓縮率又沒有差 libpng 太多。

而且作者自己有提到,還沒用到 SIMD 指令集加速,這樣猜測應該還有不少空間...

PostgreSQL 14 支援的 LZ4 壓縮

Hacker News 上看到 PostgreSQL 14 新支援的 LZ4 壓縮:「The LZ4 introduced in PostgreSQL 14 provides faster compression (fastware.com)」,在討論裡面反而有提到可以用 ZFS 的壓縮,這樣所有的資料 (包括 index) 都可以被壓縮:

If you are using ZFS, I strongly recommend using LZ4 or ZSTD compression with PostgreSQL. Performance is still awesome. On average I get 2x compressionratio with LZ4 and 4x with ZSTD.

With this, you are compressing everything, not just columns. And ZFS has dynamic block sizes which works really great together with compression. For example a 8kb PostgreSQL page, may be stored as a 1kb compressed block on disk.

而且通常開了壓縮後,整機的效率都會比較好。主要是因為資料庫的資料夠大時 (超過記憶體大小) 通常效能會先卡在 Disk I/O 的部份,這時候 CPU 會太閒;如果挑個輕量的壓縮演算法的話,雖然 CPU 使用率會拉高一些,但會大幅降低 Disk I/O 的量,在很多情況下就會提昇效能...

上面提到主要是 OLTP 的情況下,如果是在 OLAP 的場景下就更明顯了,基本上大家都是預設開著壓縮在處理所有資料。

另外在很多 RPC 類的系統也有類似的現象,資料傳輸量已經太大會超過 Network I/O 可以提供的量,這時候導入一些輕量的壓縮演算法就能大幅提昇系統效能。

以前有讀到一些壓縮演算法的比較,像是先前有翻到的「Evaluating Database Compression Methods: Update」,針對演算法的部份分析,裡面最後一張圖可以看到比較:

從比較圖可以穿來 Snappy 後來被 LZ4 淘汰掉,主要就是 LZ4 的壓縮率比較好,壓與解的速度又比較快,沒有理由繼續 Snappy。

另外 Zstandard 也逐步在淘汰 gzipzlib 類的壓縮,不過畢竟 gzip 與 zlib 的歷史真的太久,這邊淘汰的速度不快...

限制流量的方式 (rate limit)

Lobsters Daily 上看到這篇 2017 年的文章,Figma 的工程師講怎麼做 rate limit:「An alternative approach to rate limiting」,只要大一點的站台就會遇到 spammer 之類的攻擊,就會希望實做自動化的機制擋住 spammer。

文章裡面提到了三種方式,第一種 (類) 提到了經典的 Token bucketLeaky bucket,這邊文章提供的演算法是讓每個使用者都會有一筆資料紀錄在 Redis 裡面 (這邊的用法可以抽換換成 Memcached),裡面記錄了最後一次的 access time 以及還剩下多少 token 可以用,接下來就可以照時間計算 token 的補充與消耗:

但這個演算法的缺點是 race condition,需要另外設計一些機制確保操作的 atomic:

不過大多數的實做就算不管 atomic 也還行 OK,只是會比較不精確一點。

第二個方法他叫做 Fixed window counters,這個方法把時間切齊為單位 (像是 60 秒為一個 window),所以可以把起點的時間也放到 key 裡面,然後 value 就是數量:

這個作法的好處就是簡單,而且 Redis 與 Memcached 都有提供 atomic 的 +1 操作。但缺點是可能會發生兩倍以上的 request,像是 5 reqs/min 的限制有可能會有連續的一分鐘內達到 10 reqs/min:

不過我覺得就 antispam 來說算是夠用了,當年 (大概是 2007 或是 2008 年?) 在 PIXNET 時用 C 寫 Apache module 就是把資料丟到 Memcached 裡面就是這樣實做的,然後每次學術網路的實驗室跑來掃站的就會自動被擋 XDDD

第三種方式他們稱作 Sliding window log,就是把每個 request 的 timestamp 都存起來,這個部份用 Redis 的資料結構會比用 Memcached 方便一些:

這個方式在控制上更精確,不過空間成本上就高很多... 這樣算是把常見的實做方式都提到了。

Git 的 Diff 演算法

Lobsters Daily 上看到「When to Use Each of the Git Diff Algorithms」這篇 2020 的文章 (Lobsters 這邊常冒出一些舊文章),講 Git 的 diff 演算法。

文章裡面題到了四個演算法,看了一下 git-diff 的 manpage 也還是這四個:

--diff-algorithm={patience|minimal|histogram|myers}

另外看 manpage 時還有看到 --anchored 的用法,看起來是用來提示 Git 產生比較好懂的 diff 結果:

--anchored=<text>

Generate a diff using the "anchored diff" algorithm.

This option may be specified more than once.

If a line exists in both the source and destination, exists only once, and starts with this text, this algorithm attempts to prevent it from appearing as a deletion or addition in the output. It uses the "patience diff" algorithm internally.

回頭翻了一下自己的 config repository,看起來 2017 年年底的時候我就加了「Use histogram diff algorithm.」,然後過幾天換成「Use patience algorithm.」,就一直用到現在...

這次改用 minimal 跑一陣子看看好了...

Amazon SES 總算支援 2048 bits RSA key 了

Amazon SES 總算是支援 2048 bits RSA key 了:「Amazon SES now supports 2048-bit DKIM keys」。

然後講一些幹話... 隔壁微軟早在 2019 年就支援 2048 bits RSA key 了:

Until now, Amazon SES supported a DKIM key length of 1024-bit, which is the current industry standard.

另外用 ECC 演算法的一直都沒進 standard,像是已經先 book 了 RFC 8463 位置的 Ed25519,在 draft 狀態放好久了:「A New Cryptographic Signature Method for DomainKeys Identified Mail (DKIM)」,還有用 ECDSA 的「Defining Elliptic Curve Cryptography Algorithms for use with DKIM」也是放著,不知道是卡到什麼東西,可能是專利?

用在 IoT 裝置上的壓縮演算法 Heatshrink

在「Heatshrink – An ultra-lightweight compression library for embedded systems」這邊看到的演算法 Hearshrink,可以看到主打是在記憶體的用量受限的環境下壓縮。

在 2013 年的資料就有壓縮率的比較了:「heatshrink: An Embedded Data Compression Library」。

像是目前常被拿來使用的 ESP32 就只有 320KB 記憶體,gzip 就明顯太肥大了,HS 在這邊就可以犧牲壓縮率來換效能...

另外找了一下資料,發現有 lowzip 這個東西,走 ZIP 格式,記憶體用量也不高,不過軟體本身還掛 alpha:

Current x64 code footprint (for lowzip.c, excluding the test program) is about 3.2kB and RAM footprint is about 1.1kB.

如果之後打算要透過 LPWAN 之類的網路傳東西的話好像有可能會用到,先寫下來...

一個有趣的面試問題

Hacker News Daily 上看到「Performance comparison: counting words in Python, Go, C++, C, AWK, Forth, and Rust」這個有趣的面試問題,在 Hacker News 上的討論也可以看看:「Performance comparison: counting words in Python, Go, C++, C, Awk, Forth, Rust (benhoyt.com)」。

問題是這樣:

Write a program to count the frequencies of unique words from standard input, then print them out with their frequencies, ordered most frequent first. For example, given this input:

The foo the foo the
defenestration the

The program should print the following:

the 4
foo 2
defenestration 1

在面試時,重點不在於用哪個程式語言,而是在面試時一路往下問,像是 profiling 的部份,內部資料結構的部份,可以問得很深。

撇開面試,這個問題其實是個經典問題,當年 Donald KnuthDoug McIlroy 兩位大師都有玩過:

Incidentally, this problem set the scene for a wizard duel between two computer scientists several decades ago. In 1986, Jon Bentley asked Donald Knuth to show off “literate programming” with a solution to this problem, and he came up with an exquisite, ten-page Knuthian masterpiece. Then Doug McIlroy (the inventor of Unix pipelines) replied with a one-liner Unix shell version using tr, sort, and uniq.

不過當年玩的問題有點變形:

Given a text file and an integer k, print the k most common words in the file (and the number of their occurrences) in decreasing frequency.

他們當時其實一個是在示範 Literate programming,而另外一個在展現 pipe 的威力,都是借題發揮而已,跟上面的那些東西倒是沒什麼太大關係。