HyperLogLog 與 Bloom Filter

看到 FacebookPresto 裡增加使用 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, "InnoDB Performance Tuning Tips".

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