Practise the calculations and building blocks behind system design: estimates, availability, caches, rate limiters, hashing, quorums and percentiles. Every solution has been run with Python and shows its real output.
Review first: Back-of-the-Envelope Estimation, Availability and Reliability, Caching, Rate Limiting, Sharding and Consistent Hashing, Consistency and the CAP Theorem, Monitoring and Observability, Message Queues and Async Work, Design a URL Shortener
An app has 2 million daily users, each making 15 requests. Print the average QPS, and the peak at 3 times the average, as whole numbers.
Divide by 86,400 seconds.
users = 2_000_000
requests = users * 15
avg = requests / 86_400
print(f"Average: {avg:.0f}")
print(f"Peak: {avg * 3:.0f}")Average: 347
Peak: 1042Users upload 500,000 images a day, each 3 MB. Print the storage needed for 5 years in terabytes, with 3 copies of each file.
Items, times size, times days, times copies.
per_day_mb = 500_000 * 3
total_tb = per_day_mb * 365 * 5 * 3 / 1_000_000
print(f"{total_tb:,.0f} TB")8,212 TBWrite a function that returns the minutes of downtime a year for a given availability, and print it for 99.5 and 99.95.
Minutes in a year, times the failed share.
def downtime(pct):
return 365 * 24 * 60 * (100 - pct) / 100
for pct in (99.5, 99.95):
print(f"{pct}%: {downtime(pct):,.0f} minutes")99.5%: 2,628 minutes
99.95%: 263 minutesThree services with 99.9%, 99.95% and 99.99% availability are all needed for a request. Then the first is doubled, as two independent copies. Print the total availability before and after.
Multiply parts in a chain. Two copies fail only if both fail.
a, b, c = 0.999, 0.9995, 0.9999
print(f"Before: {a * b * c:.4%}")
doubled = 1 - (1 - a) ** 2
print(f"After: {doubled * b * c:.4%}")Before: 99.8401%
After: 99.9399%Write encode(n) that turns a number into base62, using digits, then lower case, then upper case. Print the result for 100 and 1,000,000.
Repeatedly use divmod(n, 62).
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def encode(n):
out = ""
while n:
n, r = divmod(n, 62)
out = ALPHABET[r] + out
return out or "0"
print(encode(100))
print(encode(1_000_000))1C
4c92Build an LRU cache with capacity 2, using OrderedDict. Put a and b, read a, put c, and print the remaining keys.
move_to_end on use, and popitem(last=False) to evict.
from collections import OrderedDict
cache = OrderedDict()
def put(key, value):
cache[key] = value
cache.move_to_end(key)
if len(cache) > 2:
cache.popitem(last=False)
put("a", 1)
put("b", 2)
cache.move_to_end("a")
put("c", 3)
print(list(cache))['a', 'c']A cache hit takes 2 ms, and a miss takes 50 ms. Print the average latency at hit ratios of 70%, 90% and 99%.
Weight each time by its share.
for hit in (0.7, 0.9, 0.99):
avg = hit * 2 + (1 - hit) * 50
print(f"{hit:.0%}: {avg:.1f} ms")70%: 16.4 ms
90%: 6.8 ms
99%: 2.5 msWrite a token bucket with capacity 2 that refills 1 token a second. For requests at times 0, 0, 0, 2, 2, 2, print True or False for each.
Add (t - last) * rate tokens, capped at capacity.
tokens, last = 2.0, 0
results = []
for t in [0, 0, 0, 2, 2, 2]:
tokens = min(2, tokens + (t - last))
last = t
if tokens >= 1:
tokens -= 1
results.append(True)
else:
results.append(False)
print(results)[True, True, False, True, True, False]Using hashlib.md5, count how many of the keys user0 to user9999 fall on each of 3 shards. Print the counts in shard order.
Convert the hex digest to an integer, then use % 3.
import hashlib
from collections import Counter
counts = Counter(int(hashlib.md5(f"user{i}".encode()).hexdigest(), 16) % 3 for i in range(10_000))
print([counts[s] for s in range(3)])[3327, 3315, 3358]Write is_strong(n, r, w), which is true when reads always overlap writes. Test it with (3, 2, 2), (5, 2, 3) and (5, 3, 3).
R + W must be greater than N.
def is_strong(n, r, w):
return r + w > n
for args in [(3, 2, 2), (5, 2, 3), (5, 3, 3)]:
print(args, is_strong(*args))(3, 2, 2) True
(5, 2, 3) False
(5, 3, 3) TrueFrom times = [10, 12, 11, 14, 13, 15, 12, 11, 300, 12, 13, 14, 16, 11, 12, 13, 15, 14, 12, 900], print the mean, the median and the p95.
Sort the list. p95 is the value 95% of the way through.
import statistics
times = sorted([10, 12, 11, 14, 13, 15, 12, 11, 300, 12, 13, 14, 16, 11, 12, 13, 15, 14, 12, 900])
print("Mean:", statistics.mean(times))
print("Median:", statistics.median(times))
print("p95:", times[int(len(times) * 0.95) - 1])Mean: 71.5
Median: 13.0
p95: 300Process messages m1, m2, m1, m3, m2, each adding 10 to a total, so that duplicates are ignored. Print the total and the number of duplicates.
Keep a set of processed IDs.
seen = set()
total = 0
duplicates = 0
for message in ["m1", "m2", "m1", "m3", "m2"]:
if message in seen:
duplicates += 1
continue
seen.add(message)
total += 10
print("Total:", total)
print("Duplicates:", duplicates)Total: 30
Duplicates: 2