Google Groups 的 spam 的量又下降了不少...

延續「從 Google Groups 送出來的 spam 數量稍微下降...」這邊的觀察,從 10/22 到 10/29 降了 2/3 左右,再往後拉七天到了 11/5 可以看到又少了 3/4 左右。

另外整個 article volume 看起來也有降很多,從三個不同的 peering 來的量都有降,看起來是從源頭就有做一些事情。

這是 10/22 的量:

這是 10/29 的量:

這是 11/5 的量:

最近 YouTube 在阻擋擋廣告軟體的事情

最近用 uBlock Origin 或是其他擋廣告軟體的都加減會遇到 YouTube 阻擋擋廣告軟體的事情,然後在 HN 上面看到「Youtube’s Anti-adblock and uBlock Origin」,對應的討論在「YouTube's Anti-Adblock and uBlock Origin (andadinosaur.com)」這邊。

先說一下目前的解法可以參考「YouTube Anti-Adblock and Ads - October 16, 2023 (Weekly Thread)」這篇說明,目前的建議就是每天睡醒後更新一下清單 (block list),讓清單是最新的。

這邊的清單不需要全部更新,只需要針對「uBlock filters – Quick fixes」這組就可以了,方法是點一下他的時鐘部分,然後再按上面的 Update Now 更新就可以了 (我是英文版介面,中文版的話應該是中文的...):

基本上就是個貓抓老鼠的過程,最近更新的會很頻繁。

另外一個最近開始用,也很推薦的套件「SponsorBlock for YouTube - Skip Sponsorships」,可以跳過業配片段。

在 Cleanfeed 裡面用 Mail::SpamAssassin 的 Bayesian filter 來擋 Google Groups 的垃圾

本來單純用 Cleanfeed + Mail::SpamAssassin 擋,效果其實不太好:「Google Groups 的巨量 spam」。

後來在 news.software.nntp 討論區裡面有人提到應該要用 sa-learn 訓練:

OK, now you need a ~/.spamassassin directory for your news user and a user_prefs file in that directory. After that you can start adding rules for Usenet spam. You will also need to feed several hundreds of spam and ham articles to sa-learn --spam or sa-learn --ham as the news user. After that, SpamAssassin will gradually improve.

死馬當活馬醫看看,結果看起來效果就出來了:

累積了幾天下來後,單看跑進 comp.lang.c 裡面的 spam 與 Mail::SpamAssassin 這邊擋下來的量,差不多是 99%+ 的量,接下來就是有看到的部分再丟進去 train。

目前看起來唯一的問題就是 Google Groups 的 spam 量真的很大,導致 innd 因為跑 Mail::SpamAssassin 的 bayesian 運算時 CPU usage 會高不少,偶而會撞到 100%,但不是常態所以還好。

繼續觀察看看...

CSS 的 :has() 有新進展了

在「Using :has() as a CSS Parent Selector and much more」這邊看到 Safari 宣佈對 :has() 的支援,查了一下 Can I use... 上面的資料「:has() CSS relational pseudo-class」,看起來是從 15.4 (2022/05/14) 支援的。

隔壁 Google Chrome 將在下一個版本 105 (目前 stable channel 是 104) 支援 :has(),沒意外的話 Microsoft Edge 應該也會跟上去,看起來只剩下 Firefox 要開了。

先前在「Chromium 的 :has() 實做進展」這邊有翻一下進度,看起來 Chromium 這邊要進入收尾階段了。

等普及後一些延伸套件裡的寫法也可以用 :has() 來處理了,就不用自己在 javascript 裡面檢查半天...

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

用 uBlock Origin 過濾 URL 裡面的 tracking parameter

在「ClearURLs – automatically remove tracking elements from URLs (github.com/clearurls)」這邊的討論裡面看到 gorhill (uBlock Origin 的作者) 的回文,裡面提到了 uBlock Origin 目前也有支援 removeparam 了,而且有對應的 filter list 在維護這個表格:

不過他也有提到 CleanURLs 可以清更多東西:

Addendum: to be clear, this is not a replacement for ClearURLs. ClearURLs has more capabilities then just removing query parameters from the URLs of outgoing network requests.

但這樣起來也不錯了 (尤其是對於只裝 uBlock Origin 的情況下),可以訂起來...

比 Bloom filter 與 Cuckoo filter 再更進一步的 Xor filter

Bloom filter 算是教科書上的經典演算法之一,在實際應用上有更好的選擇,像是先前提到的 Cuckoo filter:「Cuckoo Filter:比 Bloom Filter 多了 Delete」。

現在又有人提出新的資料結構,號稱又比 Bloom filter 與 Cuckoo filter 好:「Xor Filters: Faster and Smaller Than Bloom Filters」。

不過並不是完全超越,其中馬上可以看到的差異就是不支援 delete:

Deletions are generally unsafe with these filters even in principle because they track hash values and cannot deal with collisions without access to the object data: if you have two objects mapping to the same hash value, and you have a filter on hash values, it is going to be difficult to delete one without the other.

論文的預印本可以在 arXiv 上下載:「Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters」。

PostgreSQL 的 Bloom index

前幾天才跟人提到 PostgreSQL 的功能與完整性比 MySQL 多不少,剛剛又看到 Percona 的「Bloom Indexes in PostgreSQL」這篇,裡面提到了 PostgreSQL 可以使用 Bloom filter 當作 index。

查了一下資料是從 PostgreSQL 9.6 支援的 (參考「PostgreSQL: Documentation: 9.6: bloom」這邊的說明),不過說明裡面沒看到 DELETE (以及 UPDATE) 會怎麼處理,因為原版的 Bloom filter 資料結構應該沒有能力處理刪除的情況...

另外這幾年比較有名的應該是 Cuckoo filter,不只支援刪除,而且空間與效能都比 Bloom filter 好,不知道為什麼是實做 Bloom filter...

Elasticsearch 的 CJK Bigram 設定

Elasticsearch 應該是目前大家搜尋引擎的首選了。而且預設的搜尋法不像以前的搜尋引擎,以前的搜尋引擎會把所有的中文字串當作一個 term,基本上是搜不到東西的。

不過偶而還是會出現一些問題,像是這樣:(這是在求職天眼通搜尋「訊力科技股份有限公司」的結果)

會發現出現了「104人力銀行_一零四資訊科技股份有限公司」,這是因為預設的搜尋演算法把中文字一個一個拆開,後面的「科技股份有限公司」八個字也都有出現,前面的「訊」與「力」也都有出現,於是就被拉出來了...

這種方式被歸類為 unigram 類的方式,像是「波音737 MAX」這一段就會被切成「波」、「音」、「737」與「MAX」。這個切法還算不錯,但有不少機會會遇到問題。

如果限制在 Elasticsearch 內建的功能,其實有更好的設定可以用,也就是對 CJK 文字改用 bigram 方式切:「CJK Bigram Token Filter」。

遇到英文數字還是照原來的切法,但遇到中文字 (更正確的說應該是 CJK) 會用 bigram 的方式切,像是搜尋詞「訊力科技股份有限公司」就會被切成「訊力」、「力科」、「科技」、「技股」、「股份」、「份有」、「有限」、「限公」與「公司」,而本來的「104人力銀行_一零四資訊科技股份有限公司」裡面就不會出現「訊力」、「力科」,於是就不會抓錯...

當然還是有更好的演算法,不過大多就需要另外安裝了,而 Elasticsearch 的升級又很容易跟這些另外裝的套件卡住,所以在考慮維護成本下,CJK Bigram Token Filter 應該是首選...

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」。