Sandvine 對全球網路流量的分析,那兩個是怎麼上榜的...

看到「Netflix Dominates Internet Traffic Worldwide, BitTorrent Ranks Fifth」這篇報導了 Sandvine 對全球網路流量的分析,主要是這張:

大多數的應用都不算意外 (只是差在各地區的使用習慣),但 AMERICAS 的第十名 (XBOX LIVE UPDATE) 跟 EMEA 的第七名 (PLAYSTATION DOWNLOAD) 是怎麼一回事 XDDD

Quotient filter

之前有提過「Cuckoo Filter:比 Bloom Filter 多了 Delete」,最近在「A general purpose counting filter: making every bit count」這邊看到 Quotient filter,也是類似 Bloom filter 的資料結構,但想要解決更多問題。

一般的 Bloom filter (BF) 會有這些問題:

  • The inability to delete items
  • Poor scaling out of RAM
  • The inability to resize dynamically
  • The inability to count the number of occurrences of each item, especially with skewed input distributions.

而文章裡提到的 Quotient filter (QF) 就是要解這些問題。另外還提到了 Rank-and-Select-based Quotient filter (RSQF) 以及 Counting Quotient filter (CQF)。雖然多了一些空間需求,但看起來解掉不少問題... (尤其是刪除的能力)

效能上也還不錯,尤其是讀取速度的部份... 不過不知道相對於 Cuckoo filter 差多少。