Tag Archives: counting

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 … Continue reading

Posted in CDN, Computer, Murmuring, Network, Programming | Tagged , , , , , , , , , , , , , | Leave a comment

Reddit 在處理 Page View 的方式

Reddit 說明了他們如何處理 pageview:「View Counting at Reddit」。 以 Reddit 的規模有提到兩個重點,第一個在善用 Redis 的 HyperLogLog 這個資料結構,當量大的時候其實可以允許有微小的誤差: The amount of memory varies per implementation, but in the case of this implementation, we could count over 1 million IDs using just 12 kilobytes of space, … Continue reading

Posted in Cassandra, Computer, Database, Murmuring, Network, Programming, Service, Software | Tagged , , , , , , , , , , , , , , , , , , , | Leave a comment