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 的方式搞定,但的確是蠻有效的...

RFC 定義的 application/problem+json (或是 xml)

剛剛在 Clubhouse 上聽到保哥提到了 RFC 7807 這個東西 (Problem Details for HTTP APIs),剛剛翻瀏覽器累積的 tab,發現原來先前有看到,而且有打算要出新版的消息:

RFC 7807 裡面這樣定義的方式可以讓 client 端直接判斷 Content-Type 知道這個回傳資料是不是錯誤訊息,不然以前都是 JSON 就得再另外包裝。用 Content-Type 的作法可以讓判斷條件變得清晰不少。

除了 application/problem+jsonapplication/problem+xml 以外,在「3.1. Members of a Problem Details Object」裡面則是說明 JSON (或是 XML) 裡面有哪些必要以及可選的資訊要填,然後「3.2. Extension Members」這邊則大概描述一下怎麼擴充。

先有個印象,之後新規劃的東西可以考慮進去...

二戰時德國坦克製造速度的估算問題

看到「The German Tank Problem」這篇在講二戰很有名的統計應用。這個主題在中文的維基百科寫得還蠻完整的,讀起來應該會更快一些:「德國坦克問題」:

在統計學理論的估計中,用不放回抽樣來估計離散型均勻分布最大值問題中著名的德國坦克問題(英語:German tank problem),它因在第二次世界大戰中用於估計德國坦克數量而得名。

如同上面所說的,這個方法是因為估算的準確度極高而知名:

對坦克車輪的分析產生了對使用中的車輪模具數量的估計。在與英國車輪製造商討論過後,他們估計了這麼多的模具可以生產多少車輪,進而是每個月可生產的坦克數量。對兩輛坦克(每輛32個車輪,總計64個車輪)車輪的分析的結果是1944年2月的生產數量估計在270左右,大大超出此前預期。

德國戰後公布的記錄顯示,1944年2月一個月的生產量是276輛。統計方法結果的精確度是常規情報收集方法所遠遠不能達到的,而「德國坦克問題」這個詞也成為了這種統計分析問題的標誌。

而且之後被拿來推敲經典的 Commodore 64 的數量也還蠻準的:

該公式在非軍事中也有使用,如估計Commodore 64計算機的總數,其結果(1.25億)與官方數字相當匹配。

IPv6 表示法的包袱

IPv6 address 表示法的確有不少問題,說「包袱」是因為應該是很難改了。

在「The IPv6 Numeric IP Format is a Serious Usability Problem」這篇文章裡作者討論 IPv6 address 表示法的問題,像是因為用 colon 切割造會跟 url 裡的 port 混淆,於是引入了 bracket 的 workaround:

An IPv4 URL of the form http://127.0.0.1:1234/ indicates that HTTP should be used to access a service at 127.0.0.1 port 1234. But what does http://dead:beef::1:1234/ mean? To fix the ambiguity, brackets were introduced. Now you have to type http://[dead:beef::1]:1234/.

Address Shortening Obfuscation 這邊講的就有點過火了,不過的確是不好讀,一眼看過去不是很容易切開一個 colon 與兩個 colon 的部份。

作者有提出一些建議方法,不過看起來只是 murmuring... XD

Small Characteristic DLP (Discrete Log Problem) 被解決

最近幾天在密碼學領域還蠻紅的話題 (雖然預印本在去年就發了),EUROCRYPT 2014 上發表對 DLP (Discrete Log Problem) 的重大進展。

論文在 arXiv 上可以取得:「A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic」。

針對使用小特徵值的有限域 (finite field) 的 DLP 問題 (也就是 Zqk 上) 直接從 sub-exponential 降到 nO(logn) (quasi-polynomial)。最常見到的應該是 Z2n

雖然現有被廣泛使用的密碼系統在使用 DLP 建構時都是用 Zp,但這次的成果絕對寫下了 DLP cryptoanalysis 上的里程碑...