Tag: count

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

自己小修一下 fcitx5-mcbopomofo 的選詞數量

之前有提過「Linux 上 fcitx5 的小麥輸入法」，在我自己桌面都換成 Ubuntu 22.04 後都能裝了，就用了一陣子。

但選字的數量一直覺得怪怪的，本來的數量是九個，像是這樣：

看了一下 Windows 上的新酷音，介面上因為設計成 3x3 的關係，所以看起來就不會不舒服：

所以就在想，如果是一行的為什麼不是十個？翻了翻程式碼，看起來在 src/McBopomofo.cpp 這邊：

  if (keysConfig == SelectionKeys::Key_asdfghjkl) {
    selectionKeys_.emplace_back(FcitxKey_a);
    selectionKeys_.emplace_back(FcitxKey_s);
    selectionKeys_.emplace_back(FcitxKey_d);
    selectionKeys_.emplace_back(FcitxKey_f);
    selectionKeys_.emplace_back(FcitxKey_g);
    selectionKeys_.emplace_back(FcitxKey_h);
    selectionKeys_.emplace_back(FcitxKey_j);
    selectionKeys_.emplace_back(FcitxKey_k);
    selectionKeys_.emplace_back(FcitxKey_l);
  } else if (keysConfig == SelectionKeys::Key_asdfzxcvb) {
    selectionKeys_.emplace_back(FcitxKey_a);
    selectionKeys_.emplace_back(FcitxKey_s);
    selectionKeys_.emplace_back(FcitxKey_d);
    selectionKeys_.emplace_back(FcitxKey_f);
    selectionKeys_.emplace_back(FcitxKey_z);
    selectionKeys_.emplace_back(FcitxKey_x);
    selectionKeys_.emplace_back(FcitxKey_c);
    selectionKeys_.emplace_back(FcitxKey_v);
    selectionKeys_.emplace_back(FcitxKey_b);
  } else {
    selectionKeys_.emplace_back(FcitxKey_1);
    selectionKeys_.emplace_back(FcitxKey_2);
    selectionKeys_.emplace_back(FcitxKey_3);
    selectionKeys_.emplace_back(FcitxKey_4);
    selectionKeys_.emplace_back(FcitxKey_5);
    selectionKeys_.emplace_back(FcitxKey_6);
    selectionKeys_.emplace_back(FcitxKey_7);
    selectionKeys_.emplace_back(FcitxKey_8);
    selectionKeys_.emplace_back(FcitxKey_9);
  }

看起來是為了跟 asdfghjkl 九個鍵對齊設計的，但這樣覺得不舒服... 所以在 selectionKeys_.emplace_back(FcitxKey_9); 後面加上 selectionKeys_.emplace_back(FcitxKey_0);，再重新編 + 裝 + 重啟後再輸入就變成十個了：

這樣自己用是沒問題，但暫時想不到怎麼找出一個好方法併回去... 也許多一組 SelectionKeys::Key_1234567890？

HyperLogLog 與 Bloom Filter

看到 Facebook 在 Presto 裡增加使用 HyperLogLog 計算數量的能力，突然想到常常忘記這兩個拿準確度換速度的資料結構：「HyperLogLog in Presto: A significantly faster way to handle cardinality estimation」。

HyperLogLog (HLL) 是解決 Count-distinct problem 的資料結構，用很少的記憶體就可以給出一個誤差不大的值 (用 1.5KB 的空間處理十億等級的資料，誤差大約在 2%)，所以 Presto 利用這個資料結構引進了 APPROX_DISTINCT() 以及其他的函數，就很容易在 L2/L3 cache 裡運算，藉此大幅提昇速度。

Depending upon the problem at hand, we can achieve speed improvements of anywhere from 7x to 1,000x.

先前也提過 Reddit 也用 HLL 統計資料：「Reddit 在處理 Page View 的方式」。

Bloom Filter 也是在處理大量資料的問題，但這個資料結構的功能不太一樣，是給出「有沒有存在」，使用空間與誤差大約是 10 bits per key (1% false positive)，另外先前也有提到一些變形，可以提供其他功能。像是「Quotient filter」與「Cuckoo Filter：比 Bloom Filter 多了 Delete」。

新版 Instagram 將可以看到影片播放次數了

Mashable 的報導說下個版本的 Instagram 將會提供影片播放次數資訊了：「Instagram videos will get cool new updates to let you see how popular you are」。

The number of times a video is viewed on Instagram will soon no longer be a mystery.

Instagram is adding a new feature that will tally view counts much like parent company Facebook already does, eliminating a major blindspot for marketers attempting to tap into the app's 400-million strong audience organically.

愈來愈多 social network 往 video 這塊著力...

熱 MySQL InnoDB 的方式...

之前寫過一篇「熱 MySQL 的方法...」，主要是利用 InnoDB 在 SELECT COUNT(*) 時會掃過一次 primary key 來熱：

pt-find --charset=utf8 --print -h $1 -u USER -p PASSWORD | xargs -t -P8 -I% -n1 sh -c "echo 'SELECT COUNT(*) FROM %;' | mysql -h $1 > /dev/null"

但想要熱整個表格時 (data 部份)，這個方法就不夠力了，今天才想到可以這樣做：

SELECT COUNT(*) FROM (SELECT * FROM table_name) t;

這方法會把整個表格資料拉出來，但又不會造成大量的網路 i/o (以及洗畫面)。實際測過後發現效果還不錯... (對於 table scan 使用量很大的表格，靠這個把整個表個塞進 InnoDB buffer)

在 InnoDB 下的 COUNT(*)...

MyISAM 在讀取時不會有其他人可以寫入，所以 COUNT(*) 很容易被處理。而 InnoDB 的 COUNT(*) 在不同的 transaction 裡可能會不一樣，如果硬要處理的話會變得複雜，所以目前 InnoDB 的作法是 scan 一次 (出自「Limits on InnoDB Tables」)：

InnoDB does not keep an internal count of rows in a table because concurrent transactions might "see" different numbers of rows at the same time. To process a SELECT COUNT(*) FROM t statement, InnoDB scans an index of the table, which takes some time if the index is not entirely in the buffer pool. If your table does not change often, using the MySQL query cache is a good solution. To get a fast count, you have to use a counter table you create yourself and let your application update it according to the inserts and deletes it does. If an approximate row count is sufficient, SHOW TABLE STATUS can be used. See Section 14.3.14.1, "InnoDB Performance Tuning Tips".

在「Easy SELECT COUNT(*) with split()」這篇提到 InnoDB 下 COUNT(*) 這件事情，當你不需要絕對精確的值時，可以利用 INFORMATION_SCHEMA.TABLES 或是 SHOW TABLE STATUS 的資訊來判斷。