Evaluation: Performance and Effective Access Time

In one line: "we'll use LRU" is an assertion. Effective access time turns it into a measured improvement, and it is the most quantitative thing in this chapter.

What makes it fast

Design choice	Contribution
Consistent hashing	Locates keys in O(log N) time, where N is the number of cache shards
Internal hash tables	Locate keys in constant time on average
LRU eviction	Accesses and updates doubly linked list entries in constant time
TCP and UDP	Fast client-server communication
Replicas	Distribute traffic, preventing degradation from high load on a single machine
Serving from RAM	Low latency — no disk in the read path

Every row is a decision made earlier in the chapter, now paying off. Nothing here is new machinery.

Effective access time

The formula:

EAT = Ratio_hit x Time_hit  +  Ratio_miss x Time_miss

  EAT        = effective access time
  Ratio_hit  = probability of a cache hit
  Ratio_miss = probability of a cache miss
  Time_hit   = time to serve a cache hit
  Time_miss  = time to serve a cache miss

With these assumptions:

Cache hit service time  (99.9th percentile) =  5 ms
Cache miss service time (99.9th percentile) = 30 ms
    (includes database retrieval and cache update)

Comparing two eviction policies — 10% miss rate for MFU, 5% miss rate for LRU:

MFU:  EAT = 0.90 x 5 ms  +  0.10 x 30 ms
          = 4.5 + 3.0
          = 7.5 ms

LRU:  EAT = 0.95 x 5 ms  +  0.05 x 30 ms
          = 4.75 + 1.5
          = 6.25 ms

Policy	Miss rate	EAT	Relative
MFU	10%	7.5 ms	baseline
LRU	5%	6.25 ms	1.25 ms faster — about a 17% improvement

These figures highlight how the eviction algorithm impacts the cache hit rate. You should conduct empirical studies to determine the best algorithm for your specific workload.

Why a 5-point hit-rate change is worth 17% of latency

The leverage comes from the 6x gap between hit and miss cost. A miss costs 30 ms against a hit's 5 ms, so every percentage point moved from miss to hit removes 25 ms of expected latency per hundred requests.

Halving the miss rate from 10% to 5% removes half of a term that was already 40% of the total. The general lesson: the value of a hit-rate improvement scales with how expensive a miss is. Where a miss is cheap, tuning eviction barely matters; where a miss means a cross-region database round trip, it dominates everything.

Run this calculation with your own numbers

The formula takes fifteen seconds and turns an opinion into an argument. In an interview:

"A hit is about 5 ms and a miss about 30 ms. At a 10% miss rate that's 7.5 ms effective; getting the miss rate to 5% takes it to 6.25 ms — a 17% latency reduction from the eviction policy alone. That's why I'd spend time on it rather than treating LRU as a default."

Same move as the back-of-the-envelope chapter: the number is what makes the decision defensible.

The counter-intuitive part of tuning a cache at scale: the in-memory lookup is already the cheapest thing in the request, so optimizing it further buys nothing. The latency lives in getting to the cache and back, which is why batching many keys into one round trip is worth more than any data-structure improvement.

Key takeaway

Six structural choices give constant-time or near-constant-time operations end to end. On top of that, the eviction policy is a tunable multiplier — and EAT is how you show what tuning it is worth.

Interview signal by level

Level	What a strong answer sounds like
L4	"It's fast because it's in memory."
L5	Names the structures: "O(1) hash lookup, O(1) LRU updates, consistent hashing to find the shard, all served from RAM."
Staff+	Quantifies the policy: "with a 5 ms hit and 30 ms miss at p99.9, going from 10% to 5% miss rate takes effective access time from 7.5 to 6.25 ms — 17% off latency from eviction alone. The leverage comes from the 6x hit-miss gap, so it matters more the more expensive a miss is."

Next: the other four requirements.