Scaling Counting Infrastructure at Quora - Chun-Ho Hung and Nikhil Gar, SEs at Quora

Ideas you will meet

Distributed Systems

Consensus, time, failure and the fundamentals of scale-out.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• Core Concepts: How Things Actually Work · 7 minBloom filters and other probabilistic structuresAnswering 'have I seen this?' and 'how many distinct items?' in tiny amounts of memory, at the price of small, controlled errors.Read hereClose

  Trading exactness for space

  Sometimes you need an answer that is almost always right using a tiny fraction of the memory. Probabilistic data structures do that, with errors that are small and predictable.

  Bloom filter: "have I seen this?"

  A Bloom filter is a bit array plus several hash functions.

  • Add an item: hash it k ways, and set those k bits to 1.
  • Check an item: hash it the same way. If any bit is 0, it was never added. If all are 1, it was probably added.

  100%

  Figure SDA-CORE-16-1 · Bloom filter: "have I seen this?" · © forcsguy.com

  Properties:

  • No false negatives: an item you added is always reported present.
  • Possible false positives: other items may have set the same bits. The rate depends on the array size, the number of items and the number of hashes. About 10 bits per item gives roughly 1%.
  • Tiny and fast: constant-time operations and a fixed memory footprint.
  • No deletion in the basic version (use a counting Bloom filter or a cuckoo filter).

  Typical uses

  • Avoid expensive lookups: databases check a Bloom filter before reading disk, skipping files that cannot contain the key (as in log-structured storage).
  • Cache penetration: reject requests for keys that do not exist before they hit the database.
  • Crawlers: remember which URLs were visited.
  • Safe browsing checks and "username already taken" fast paths.

  100%

  Figure SDA-CORE-16-2 · How a false positive happens · © forcsguy.com

  Counting distinct items: HyperLogLog

  Counting unique visitors exactly needs memory proportional to the number of visitors. HyperLogLog estimates the count of distinct items in a few kilobytes with about 1 to 2% error, by observing patterns in hashed values. It is built into Redis, and sketches can be merged, so you can combine counts from many servers.

  Frequency estimates: count-min sketch

  A count-min sketch estimates how often each item appears, using a small table of counters and several hashes. It can over-estimate but never under-estimate. Useful for finding heavy hitters ("top trending terms") in a stream.

  When to use them

  Use probabilistic structures when the data is huge, memory is the constraint, and a small error is acceptable. If you must be exact (money, permissions), do not.

  Real-world reading

  Related reading

  • O'Reilly MySQL CE 2011: Jeremy Cole, "Big and Small Data at @Twitter"TwitterYouTube
  • Reduce Memcached Memory Usage by 50% at TrivagoTrivago engineers · TrivagoCase Studies
  • Reducing Memory Footprint at SlackSlack engineers · SlackCase Studies
  • Prefetch Caching of Items at eBayeBay engineers · eBayCase Studies

  Show 6 moreShow fewer

  • Service Architecture (3 parts: Domain Gateways, Value-Added Services, BFF) at SoundCloudSoundCloud engineers · SoundCloudCase Studies
  • Scaling Counting Infrastructure at Quora - Chun-Ho Hung and Nikhil Gar, SEs at QuoraQuora engineers · QuoraCase Studies
  • Debugging Java Memory Leaks at AllegroAllegro engineers · AllegroCase Studies
  • Neural Architecture Search (NAS) for Prohibited Item Detection at MercariMercari engineers · MercariCase Studies
  • Distributed Cache at ZalandoZalando engineers · ZalandoCase Studies
  • ClickHouseClickHouse · GitHubGitHub

  Open this lesson with its quiz and exercise