Golomb coding

Hacker News 上看到 id=40008133 這篇提到 Golomb coding 覺得很有趣,花了些時間把演算法以及使用的場景搞清楚...

Golomb coding 用在 input 是數字 (或是 fixed size 時硬當作一個數字處理),而且大多數的資料都偏小的情境下,像是「I don't get Golomb / Rice coding: It does make more bits of the input, or does it?」這邊解釋 Golomb coding 時提到的:

they reduce the average length per encoded value compared to fixed-width encoding, if the encoded values are from a large range, but the most common values are generally small (and hence are using only a small fraction of that range most of the time).

Golomb coding 演算法上用到了兩個特殊的表達方式,Unary codingTruncated binary encoding

Unary coding 很簡單,把 n 表達成 n 個 bit 的 1,再加上一個 0,所以 3 表達成 1110,7 表達成 11111110

Unary coding 最主要就是要用到他只用一個 bit 0 來表達 n = 0 的情況。

Truncated binary encoding (中文維基百科剛好有條目:「截斷二進制編碼」) 則是很有趣的一個 encoding 方式。先提到傳統的方式,在表示 n 種可能的組合 (0, 1, ..., n-1) 時,會需要 \lceil\log_2 {n}\rceil bit 表達,像是 n = 5 時,會需要 3 個 bit 表達,從 000001010011100

Truncated binary encoding 則是找到一個方法,編碼成 00 (對應到 0)、01 (1)、10 (2)、110 (3)、111 (4),針對 n = 0~2 的部分只用 2 bits 表示,省下 1 個 bit。

Truncated binary encoding 的重點在於在可能性非 2^n 的情況下,要怎麼省儲存空間。

而 Golomb coding 需要預先指定一個 M,對於每一個 x 輸入,拿 M 去除他,就會得到一個商 q 與餘數 r

x = M * q + r

這邊把商 q 用 Unary coding 表示,餘數 r 用 Truncated binary encoding 表示,就是 Golomb coding 了。

而就如同前面提到的,Golomb coding 會用在資料數字都偏小的情況,當 M 挑的夠好就可以讓 q 常常是 0 或是 10 而省下空間。

這剛好就對到「The simple beauty of XOR floating point compression (clemenswinter.com)」這則提到的東西,在處理 time-series data 時就有機會用這個方式搭配處理...

Google 的 HyperLogLog++

算是接續昨天寫的「Redis 對 HyperLogLog 省空間的實作」,在 RedisHyperLogLog 實作有提到 Google 在 2013 年的論文「HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm」,裡面提出了 HyperLogLog++ (HLL++)。

論文中 Google 提出來的改進主要有三個,第一個是用了 64-bit hash function:

5.1 Using a 64 Bit Hash Function

原因也有提到,當需要處理超過十億筆資料時,32-bit hash 的 4B 上限就有點不太夠用:

To fulfill the requirement of being able to estimate multisets of cardinalities beyond 1 billion, we use a 64 bit hash function.

這點也簡化了原始論文中當 cardinality 接近 232 時的 count 估算修正,因為實務上不太可能遇到 264 上限?

It would be possible to introduce a similar correction if the cardinality
approaches 264, but it seems unlikely that such cardinalities are encountered in practice.

第二個是改善 cardinality 比較低時的 count 估算公式:

5.2 Estimating Small Cardinalities

第三個則是提出了 sparse representation 的概念,在 cardinality 比較低的時候不需要直接用完整的 HLL 資料結構儲存:

5.3 Sparse Representation

另外也是一路往回讀的關係,查資料才了解 (ε, δ)-model 的用法,在「A Quick Introduction to Data Stream Algorithmics」這邊投影片的 Page 17 可以看到指的是,有多少正確性 (randomized) 是給出 ε 內的誤差 (approximation),像是 Page 18 的範例:

Example: Actual answer is within 5 ± 1 with prob ≥ 0.9

Redis 對 HyperLogLog 省空間的實作

HyperLogLog (HLL) 是用統計方式解決 Count-distinct problem 的資料結構以及演算法,不要求完全正確,而是大概的數量。

演算法其實沒有很難懂,在 2007 年的原始論文「HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm」裡面可以讀到演算法是長這樣:

可以看到一開始要決定好 b 的值 (於是就會有 2b 個 register),以及單個 register M[j] 的大小,所以是一開始就會決定好固定大小,無論有多少元素都會先吃掉這麼多空間。

但在 Redis 的文件「HyperLogLog」裡面則是提到很少元素的時候會低於 12KB:

The magic of this algorithm is that you no longer need to use an amount of memory proportional to the number of items counted, and instead can use a constant amount of memory; 12k bytes in the worst case, or a lot less if your HyperLogLog (We'll just call them HLL from now) has seen very few elements.

網路上搜了一下沒看到怎麼做到的,不過直接翻 Redis 的程式碼 hyperloglog.c 可以看到答案。

在檔案開頭的註解可以看到有 16384 個 register (對應到論文裡面的 b = 14,因為 214 = 16384),單個 register 的大小則是 6 bit (對應到論文裡面的 M[j]),相乘後是 12K bytes,剛好符合文件上的說明:

The use of 16384 6-bit registers for a great level of accuracy, using a total of 12k per key.

在「Dense representation」這邊也說明了每個 register 都是 6 bit 的存放方式,到這邊都與 HLL 論文提到的實作一樣。

省空間的方式是在「Sparse representation」這邊做到的,在大多數的 register 都沒有被設定的情況下,用這種方式可以省下大量的空間,而缺點是當元素「有點多」的時候會有比較高的 CPU time:

In the example the sparse representation used just 7 bytes instead of 12k in order to represent the HLL registers. In general for low cardinality there is a big win in terms of space efficiency, traded with CPU time since the sparse representation is slower to access.

依照註解上面的數字,看起來在 10000 個元素以下有機會低於 12KB,然後夠大的時候從 sparse 轉到 dense 上。

本來以為是什麼其他論文可以調整 b 參數 (enlarge),結果是個比較像是 hack 的方式搞定,但的確是蠻有效的...

用 Automerge 處理 CRDT 問題

上個月看到 Automerge 出了 2.0 版的消息:「Automerge 2.0」,Automerge 這個套件可以幫你處理複雜的 CRDT 結構 (Conflict-free replicated data type)。

可以看到 Automerge 在 2.0 之後的效能改善不少,可以跟 yjs 比較了:

所以練了一下手測界面怎麼用,另外也看一下 conflict 時的處理方式。

這邊先產生 hello, world.,然後做了三個操作,第一個是把開頭的 h 改成 H;第二個是把 world 改成 test;第三個是把 world 改成 example

(() => {
  const Automerge = require('@automerge/automerge');

  let doc1 = Automerge.init();

  doc1 = Automerge.change(doc1, 'Init', doc => {
    doc.text = new Automerge.Text();
    doc.text.insertAt(0, 'h', 'e', 'l', 'l', 'o', ',', ' ', 'w', 'o', 'r', 'l', 'd', '.');
  });
  
  let doc2 = Automerge.clone(doc1);
  let doc3 = Automerge.clone(doc1);

  doc1 = Automerge.change(doc1, 'Capitalize', doc => {
    doc.text.deleteAt(0);
    doc.text.insertAt(0, 'H');
  });
  doc2 = Automerge.change(doc2, 'world => test', doc => {
    delete doc.text.deleteAt(7, 5);
    doc.text.insertAt(7, 'test');
  });
  doc3 = Automerge.change(doc3, 'world => example', doc => {
    delete doc.text.deleteAt(7, 5);
    doc.text.insertAt(7, 'example');
  });

  let finalDoc = Automerge.merge(doc1, doc2);
  finalDoc = Automerge.merge(finalDoc, doc3);
  console.log(finalDoc);
})();

這樣最後會產生出 Hello, testexample.

{
  text: Text {
    elems: [
      'H', 'e', 'l', 'l', 'o',
      ',', ' ', 't', 'e', 's',
      't', 'e', 'x', 'a', 'm',
      'p', 'l', 'e', '.'
    ]
  }
}

這結果看起來還行。

只能說以前要是有這些 library 就好了,當初在 KKBOX 做雲端歌單自己搞半天...

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 去換記憶體,算是特化的版本...

Memcached 與 Redis 的比較

在「Memcached vs Redis - More Different Than You Would Expect」這邊看到對 MemcachedRedis 的分析。

這兩套軟體都很常被拿來用作 cache 機制,所以一般來說比較時就是比兩邊都有的東西 (如果你要 pub-sub 之類的東西,在這兩套裡面只有 Redis 有)。

最前面還是先講了對使用者 (開發者) 的差異,很明顯的是 Redis 對各種不同的資聊結構都有支援,這點可以從 Redis 被官方被稱作 Data Structures Server 就可以知道 (在「An introduction to Redis data types and abstractions」這篇可以看到),而 Memcached 只支援了 key-value 架構。

不過如果是以 cache 來說,的確 key-value 架構就還蠻好用的。

後面就開始比較硬的主題了,提到了 Memcached 與 Redis 內部是怎麼使用記憶體的。

Memcached 的部份先提了 page/slab/chunk 的架構以及產生的效能限制與浪費,接著有提到 2020 年 refactor 的部份 (太久沒有看 Memcached 的消息,去年沒跟到這個部份),讓多 CPU 的支援度更好。

Redis 則是靠 jemalloc 來處理這個部份,另外加上 background thread 的機制降低 fragment。

然後是比較 cache expiration 的部份,可以看到兩者用的演算法在現實世界中都夠用 (尤其是當作 cache 來用),這部份跟印象中的架構差不多,應該是沒有太大變化。

最後是比較 cluster 的部份,Memcached 是 share nothing,所以沒什麼好說的,主要是靠 client library 實做 consistent hash 之類的架構打散;而 Redis 的話看起來有實做新的機制出來 (也沒跟到),之後有機會再看看可以做到什麼程度。

不過好像沒提到 proxy 之類的架構,基本上各大公司都有自己幹:

少了這塊對於 cluster 架構的完整性差蠻多的。

文章最後沒有下定論一定要用哪個比較好,兩者都有強項與弱項,還是得看情況來處理。不過我自己還是很喜歡用 Memcached 就是了...

用顏色區分程式碼裡面的括弧

Hacker News Daily 上看到 VSCode 改善了 bracket pair colorization 效率的文章,才想到我的 Vim 好像沒裝這個功能:「Bracket pair colorization 10,000x faster」。

VSCode 這邊主要是引入了新的資料結構改善了計算量,有興趣的可以看一下:

Efficient bracket pair colorization was a fun challenge. With the new data structures, we can also solve other problems related to bracket pairs more efficiently, such as general bracket matching or showing colored line scopes.

我這邊則是去找 Vim 上的套件,目前看到是「Rainbow Parentheses Improved」這個,裝起來拿 PHP 程式碼看了一下還行,這樣就不用在那邊算哪個左括弧對應到右括弧...

Akamai 也推出了 Key-Value 服務 EdgeKV

沒介紹過 Akamai 的一些架構,先講到 Akamai 的 Edge 端 Serverless 架構是 EdgeWorkers,跑的是 JavaScript:

EdgeWorkers lets developers just code — integrating into existing CI/CD workflows and enabling multiple teams to work in parallel using JavaScript. EdgeWorkers eliminates the hassle of managing compute resources and building for scale.

然後這次推出的是 EdgeKV,目前還在 Beta 版:「Serverless Storage at the Edge (EdgeKV Beta)」。

如同名字所說的,架構上 Key-Value 架構,放棄了 CAP theorem 裡面的 C,改走 Eventual Consistency:

EdgeKV uses what is known in distributing computing as an eventual consistency model to perform writes and updates. This model achieves high availability with low read latency by propagating data writes globally. The period of time it takes the system to distribute data globally is called the “inconsistency window”.

隔壁 Cloudflare Workers KV 也是 Eventual Consistency (出自「How KV works」這邊):

KV achieves this performance by being eventually-consistent. Changes are immediately visible in the edge location at which they're made, but may take up to 60 seconds to propagate to all other edge locations.

看起來算是補上競爭對手的產品線...

GTA 的啟動讀取效能問題

這件事情也已經過了一個禮拜,來整理一下發生什麼事情...

起因是 GTA Online 的遊戲開啟速度很慢,而有人一路 reverse engineering 找出問題並且解決:「How I cut GTA Online loading times by 70%」,對應的 Hacker News 討論有提到其他有趣的事情也可以看看:「How I cut GTA Online loading times by 70% (nee.lv)」。

作者的電腦不算太差,但光開啟 GTA Online 就需要六分鐘,網路上甚至有辦投票蒐集大家的等待時間,發現也有很多人反應類似的問題:

接下來就開始 reverse engineering 了,先觀察各種狀態後發現是卡在 CPU,而不是網路或 Disk I/O,然後就拿出 Luke Stackwalker 這個工具 profiling,不過因為沒有 debug symbol 幫忙 group,所以只能人工判斷後,可以看到兩個問題:

第一個問題發現效能是卡在 strlen(),而 call stack 可以看出來是從 sscanf() 一路打進去的:

反追發現是在處理 10MB 的 JSON 檔造成的,裡面 sscanf() 因為拉出 strlen(),於是就造成把整個 10MB 的 JSON 掃過很多次 (一開始是 10MB,掃到後面會愈來愈少,平均下來應該是 5MB):

第二個問題產生的時間會在第一個問題跑完後,另外看問題的性質,應該跟第一個 JSON 處理有關,他會把 JSON 處理過的資料丟進 array,每個 entry 長這樣:

struct {
    uint64_t *hash;
    item_t   *item;
} entry;

丟進 array 是 OK 的,但問題在於他需要判斷 entry 是否重複,卻沒有用 hash 或是 tree 的結構,而這邊大約有 63k 筆資料,用 array 實做就產生了 O(n^2) 的演算法:

But before it’s stored? It checks the entire array, one by one, comparing the hash of the item to see if it’s in the list or not. With ~63k entries that’s (n^2+n)/2 = (63000^2+63000)/2 = 1984531500 checks if my math is right. Most of them useless. You have unique hashes why not use a hash map.

作者在 PoC 的章節裡面描述他怎麼解這兩個問題。

第一個問題比較好的解法是修正 JSON Parser,但這太複雜,所以他用 workaround 解:把 strlen() 包起來,針對長字串加上一層 cache:

  • hook strlen
  • wait for a long string
  • “cache” the start and length of it
  • if it’s called again within the string’s range, return cached value

而第二個問題他直接把檢查是否有重複的跳過,因為資料本身不重複:

And as for the hash-array problem, it’s more straightforward - just skip the duplicate checks entirely and insert the items directly since we know the values are unique.

整個開啟的速度從六分鐘降到一分五十秒,還是偏慢,但算是大幅緩解的 GTA Online 啟動速度的問題了。

不過故事到這邊還沒結束,有人一路去挖,發現其實 sscanf() 的效能地雷已經不是第一次了:YAML 的 Parser 也中過一樣的問題:「Parsing can become accidentally quadratic because of sscanf」,這篇也一樣上了 Hacker News:「Parsing can become accidentally quadratic because of sscanf (github.com/biojppm)」。

然後這又帶出了六年前在 StackOverflow 上就有人問過這個問題:「Why is glibc's sscanf vastly slower than fscanf on Linux?」。

另外也有人整理出來,應該是大家把同樣的演算法拿來實做:

JdeBP 3 days ago

I found this while making a collection of what C implementation does what at https://news.ycombinator.com/item?id=26298300.

There are two basic implementation strategies. The BSD (FreeBSD and OpenBSD and more than likely NetBSD too), Microsoft, GNU, and MUSL C libraries use one, and suffer from this; whereas the OpenWatcom, P.J. Plauger, Tru64 Unix, and my standard C libraries use another, and do not.

The 2002 report in the comp.lang.c Usenet newsgroup (listed in that discussion) is the earliest that I've found so far.

後續的更新動作可以再追一下進度 (包括 GTA Online 與各家的 libc)。

Python 3.7+ 保證 dict 內容的順序

在「Dicts are now ordered, get used to it」這邊看到的,因為 Python 官方 (也就是 CPython) 實做 dict 的方式改變,然後決定把這個特性當作是 social contract,而不是當作 side effect 的特性 (也就是不保證之後版本會有相同特性)。

Changed in version 3.7: Dictionary order is guaranteed to be insertion order. This behavior was an implementation detail of CPython from 3.6.

作者裡面的兩張圖清楚表示出來以前的版本怎麼實做,與 3.7+ 的版本怎麼實做:

這樣就很好理解了。

不過考慮到還是有些系統用 Python 3.5 (像是 Ubuntu 16.04 內建的 python3) 與 Python 3.6 (Ubuntu 18.04 內建的 python3,雖然沒問題,但當時還沒有寫出來),也許還是先不要依賴這個行為會比較好。

不過以插入的順序列出好像不是很常用到...