Caching LoadBalancing

Caching LoadBalancing

[!NOTE] This module explores the core principles of Caching LoadBalancing, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Consistent Hashing (The Scale Problem)

Problem: You have N cache servers. Simple load balancing uses key % N. Disaster: If 1 server crashes, N becomes N-1. key % (N-1) changes the mapping for almost every single key. Your database melts down.

Solution: The Ring.

  1. Map servers to a circle (0 to 232-1).
  2. Map keys to the same circle.
  3. Assign key to the first server clockwise.
  4. Result: If server X crashes, only its keys move to the next neighbor. 90% of cache remains valid.

2. Bloom Filters (The “Maybe” Set)

Problem: Checking if a username exists in a database of 1 billion users. Disk is slow. RAM is expensive. Solution: A probabilistic data structure.

  • Query: “Is ‘user123’ in the set?”
  • Answer:
    1. No: Definitely not. (100% confidence).
    2. Yes: Maybe. (Small probability of False Positive).

Mechanism:

  1. Bit array of size M.
  2. K hash functions.
  3. To add: Hash item K times, set bits to 1.
  4. To check: Hash item K times. If any bit is 0, it’s definitely missing.

3. Mathematical Anchor: False Positive Rate

The probability of a false positive is approximately: P \approx (1 - e-kn/m)k

  • m: Bit array size.
  • n: Number of items.
  • k: Number of hash functions.

Tradeoff: More memory (m) = Fewer false positives.

4. Deep Dive Strategy Lab: Caching Loadbalancing

Intuition Through Analogy

Think of this chapter like running a high-traffic consumer app. The goal is not to memorize a fixed trick, but to repeatedly answer:

  1. What is the bottleneck?
  2. Which constraint dominates (time, memory, latency, correctness)?
  3. Which representation makes the bottleneck easier to eliminate?