🎓 A1Learner
🔍
0 of 42 lessons completed

URL Shortener: Scaling the Reads

Scaling the reads means serving far more redirect lookups than one database can answer alone. This lesson deep dives into scaling the reads, the fifth step of the method.

A cache in front of the database

The cache keeps each code it has answered and answers it next time. The printout shows repeated codes answered by the cache, not the database.

store = {"qi": "https://example.com/a", "qj": "https://example.com/b", "qk": "https://example.com/c"}
cache = {}
database_reads = 0
cache_answers = 0

def lookup(code):
    global database_reads, cache_answers
    if code in cache:
        cache_answers = cache_answers + 1
        return "cache"
    database_reads = database_reads + 1
    cache[code] = store[code]
    return "database"

requests = ["qi", "qj", "qi", "qi", "qj", "qk", "qi"]
for code in requests:
    print("lookup", code, "answered by", lookup(code))
print("requests:", len(requests))
print("database reads:", database_reads)
print("cache answers:", cache_answers)

Replicas share the read work

Read replicas are extra database copies that share read work. The printout spreads 9 lookups across 3 replicas, evenly.

replicas = ["replica 1", "replica 2", "replica 3"]
counts = {"replica 1": 0, "replica 2": 0, "replica 3": 0}

for i in range(9):
    replica = replicas[i % len(replicas)]
    counts[replica] = counts[replica] + 1

for replica in replicas:
    print(replica, "handled", counts[replica], "lookups")

A hot code stays in the cache

One popular code can draw most of the requests for a service. Once the cache holds that code, the database reads it only once.

store = {"qi": "https://example.com/a", "qj": "https://example.com/b", "qk": "https://example.com/c"}
cache = {}
reads_for_qi = 0

def lookup(code):
    global reads_for_qi
    if code in cache:
        return "cache"
    if code == "qi":
        reads_for_qi = reads_for_qi + 1
    cache[code] = store[code]
    return "database"

requests = ["qi", "qi", "qj", "qi", "qk", "qi", "qi", "qj", "qi", "qi"]
for code in requests:
    lookup(code)

print("requests for qi:", requests.count("qi"))
print("database reads for qi:", reads_for_qi)

Example

store = {"qi": "https://example.com/a", "qj": "https://example.com/b", "qk": "https://example.com/c", "ql": "https://example.com/d"}
cache = {}
replica_counts = {"replica 1": 0, "replica 2": 0}
database_reads = 0
cache_answers = 0

requests = ["qi", "qj", "qi", "qk", "qi", "qj", "ql", "qi", "qj", "qi"]
for code in requests:
    if code in cache:
        cache_answers = cache_answers + 1
        print("lookup", code, "answered by cache")
    else:
        database_reads = database_reads + 1
        replica = "replica 1" if database_reads % 2 == 1 else "replica 2"
        replica_counts[replica] = replica_counts[replica] + 1
        cache[code] = store[code]
        print("lookup", code, "answered by", replica)

print("requests:", len(requests))
print("cache answers:", cache_answers)
print("database reads:", database_reads)
print("replica 1 reads:", replica_counts["replica 1"])
print("replica 2 reads:", replica_counts["replica 2"])

Key points

  • Read-heavy: the shortener serves far more redirects than new links, at 10 redirects per new link.
  • Cache: a fast store that holds copies of popular records close to the app servers.
  • Cache hit: a lookup the cache answers without a database read.
  • Cache miss: a lookup the cache cannot answer, so the database is read and the answer is kept.
  • Read replica: an extra database copy that shares the read work with the main copy.
  • Hot code: one code asked for far more often than the rest.

In this example, 10 requests bring 6 cache answers and only 4 database reads. The 4 reads split evenly across the replicas, so one database never carries the read load alone.

Note

caching helps most where requests repeat, and redirect requests repeat a great deal.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

What happens on a cache miss?