Estimation drills: five systems end to end

# Helpers shared by the five drills: units, rounding to two significant figures, and the sheet's layout.
import math
import textwrap

DAY = 86_400
YEAR = 365 * DAY


def sig(x, digits=2):
    """x rounded to `digits` significant figures (estimates carry no more)."""
    if x == 0:
        return 0
    value = round(x, digits - 1 - math.floor(math.log10(abs(x))))
    return int(value) if abs(value) >= 10 ** (digits - 1) else value


def rate(per_second):
    return f"{sig(per_second):,}/s"


def size(n_bytes):
    for unit, factor in (("PB", 10**15), ("TB", 10**12), ("GB", 10**9), ("MB", 10**6), ("KB", 10**3)):
        if n_bytes >= factor:
            return f"{sig(n_bytes / factor):,} {unit}"
    return f"{sig(n_bytes):,} B"


def bits(bytes_per_second):
    bps = bytes_per_second * 8
    for unit, factor in (("Tbit/s", 10**12), ("Gbit/s", 10**9), ("Mbit/s", 10**6)):
        if bps >= factor:
            return f"{sig(bps / factor):,} {unit}"
    return f"{sig(bps / 10**3):,} kbit/s"


def servers(peak_rps, per_server_rps, target=0.6, spares=2):
    """Servers for the peak at the target utilisation, plus spares for failures and deploys."""
    return math.ceil(peak_rps / (per_server_rps * target)) + spares


def line(label, text):
    """One row of the sheet, wrapped at 78 characters."""
    print(textwrap.fill(text, width=78, initial_indent=f"  {label:<10}", subsequent_indent=" " * 12))

# Drill 1: a link shortener. Create short links; redirect anyone who opens one; links never expire.
import math

from sheet import DAY, bits, line, rate, servers, size

NEW_LINKS_PER_MONTH = 100_000_000
CLICKS_PER_LINK = 100  # redirects per link created (reads : writes = 100 : 1)
PEAK = 3  # busiest hour against the average
RECORD = 500  # bytes per link: code, long URL, owner, times, index entries
COPIES = 3
YEARS = 5
REDIRECT = 400  # bytes of a redirect response
HOT_SHARE = 0.2  # share of a year's links that receive most clicks
ENTRY = 600  # bytes per cached link, with the cache's overhead
APP_RPS = 2_000  # redirects one server sustains (from a load test)

writes = NEW_LINKS_PER_MONTH / (30 * DAY)
reads = writes * CLICKS_PER_LINK
links = NEW_LINKS_PER_MONTH * 12 * YEARS

print("Link shortener")
line("Traffic", f"new links {rate(writes)} on average, {rate(writes * PEAK)} at peak; redirects {rate(reads * PEAK)} at peak")
line("Storage", f"{links / 10**9:.0f} billion links in {YEARS} years x {RECORD} B x {COPIES} copies = {size(links * RECORD * COPIES)}")
line("Bandwidth", f"{bits(reads * PEAK * REDIRECT)} of redirects out at peak")
line("Cache", f"the hottest {HOT_SHARE:.0%} of a year's links: {size(NEW_LINKS_PER_MONTH * 12 * HOT_SHARE * ENTRY)}")
line("Servers", f"{servers(reads * PEAK, APP_RPS)} app servers at 60% of {APP_RPS:,} redirects/s each, plus 2 spares")
line("Decision", f"reads are {CLICKS_PER_LINK} times writes, so a cache in front of the database serves most redirects, while {rate(writes * PEAK)} of writes fit one primary. Codes of 7 characters from 62 letters and digits give {62**7 / links:,.0f} times the codes needed; {math.ceil(math.log(links, 62))} would be the bare minimum.")

Link shortener
  Traffic   new links 39/s on average, 120/s at peak; redirects 12,000/s at
            peak
  Storage   6 billion links in 5 years x 500 B x 3 copies = 9.0 TB
  Bandwidth 37 Mbit/s of redirects out at peak
  Cache     the hottest 20% of a year's links: 140 GB
  Servers   12 app servers at 60% of 2,000 redirects/s each, plus 2 spares
  Decision  reads are 100 times writes, so a cache in front of the database
            serves most redirects, while 120/s of writes fit one primary.
            Codes of 7 characters from 62 letters and digits give 587 times
            the codes needed; 6 would be the bare minimum.

# Drill 2: one-to-one and small-group chat. Send messages, deliver them to online recipients at once, keep history.
import math

from sheet import DAY, bits, line, rate, servers, size

DAU = 50_000_000
SENT = 40  # messages each user sends a day
DELIVERED = 80  # messages each user receives or loads a day
PEAK = 3
MESSAGE = 200  # bytes stored per message: text, ids, times, index entries
COPIES = 3
KEEP_DAYS = 365  # history kept on the servers
ONLINE_AT_PEAK = 0.25  # share of daily users connected at the busiest moment
PER_CONNECTION_SERVER = 100_000  # open connections one server holds (from a load test)
PRIMARY_WRITES = 5_000  # durable writes one database primary sustains (an assumption to measure)

writes = DAU * SENT / DAY
reads = DAU * DELIVERED / DAY
connections = DAU * ONLINE_AT_PEAK
partitions = math.ceil(writes * PEAK / PRIMARY_WRITES)

print("Chat")
line("Traffic", f"messages sent {rate(writes)} on average, {rate(writes * PEAK)} at peak; deliveries {rate(reads * PEAK)} at peak")
line("Storage", f"{size(DAU * SENT * MESSAGE * COPIES)} a day with copies, {size(DAU * SENT * MESSAGE * COPIES * KEEP_DAYS)} for a year of history")
line("Bandwidth", f"{bits(reads * PEAK * MESSAGE)} of messages out at peak")
line("Servers", f"{connections / 10**6:.1f} million open connections need {servers(connections, PER_CONNECTION_SERVER)} connection servers (60% of {PER_CONNECTION_SERVER:,} each, plus 2 spares); message storage needs {partitions} write partitions")
line("Decision", f"{rate(writes * PEAK)} of message writes at peak is {writes * PEAK / PRIMARY_WRITES:.0f} times what one primary takes, so partition the messages by conversation; the open connections, not the bytes, set the size of the delivery fleet.")

Chat
  Traffic   messages sent 23,000/s on average, 69,000/s at peak; deliveries
            140,000/s at peak
  Storage   1.2 TB a day with copies, 440 TB for a year of history
  Bandwidth 220 Mbit/s of messages out at peak
  Servers   12.5 million open connections need 211 connection servers (60% of
            100,000 each, plus 2 spares); message storage needs 14 write
            partitions
  Decision  69,000/s of message writes at peak is 14 times what one primary
            takes, so partition the messages by conversation; the open
            connections, not the bytes, set the size of the delivery fleet.

# Drill 3: a video platform. Upload videos, transcode them into several sizes, stream them to viewers.
from sheet import DAY, bits, line, size

DAU = 50_000_000
WATCH_SECONDS = 60 * 60  # an hour of viewing per user a day
BITRATE = 3 * 10**6 / 8  # bytes per second of an average stream (3 Mbit/s)
PEAK = 2
UPLOADS_PER_DAY = 100_000
ORIGINAL = 500 * 10**6  # bytes of an average uploaded video
RENDITIONS = 1.5  # transcoded copies at several sizes, as a multiple of the original
COPIES = 3
CDN_HIT = 0.95  # share of bytes served from caches near viewers

egress = DAU * WATCH_SECONDS * BITRATE / DAY
ingress = UPLOADS_PER_DAY * ORIGINAL / DAY
stored_per_day = UPLOADS_PER_DAY * ORIGINAL * (1 + RENDITIONS) * COPIES

print("Video platform")
line("Traffic", f"{DAU * WATCH_SECONDS / DAY * PEAK / 10**6:.1f} million streams playing at the busiest moment")
line("Storage", f"{size(stored_per_day)} a day with renditions and copies, {size(stored_per_day * 365)} a year")
line("Bandwidth", f"in {bits(ingress * PEAK)} at peak; out {bits(egress * PEAK)} at peak, of which the origin serves {bits(egress * PEAK * (1 - CDN_HIT))}")
line("Decision", f"egress is {egress / ingress:,.0f} times ingress and dwarfs everything else: stream from a CDN, and size the origin for its cache misses, not for the viewers.")

Video platform
  Traffic   4.2 million streams playing at the busiest moment
  Storage   380 TB a day with renditions and copies, 140 PB a year
  Bandwidth in 9.3 Gbit/s at peak; out 12 Tbit/s at peak, of which the origin
            serves 630 Gbit/s
  Decision  egress is 1,350 times ingress and dwarfs everything else: stream
            from a CDN, and size the origin for its cache misses, not for the
            viewers.

# Drill 4: a news feed. People post; each follower's feed shows the newest posts of the accounts they follow.
from sheet import DAY, bits, line, rate, size

DAU = 20_000_000
FEED_LOADS = 50  # feed reads per user a day
POSTS = 0.5  # posts per user a day
FOLLOWERS = 200  # average followers of an account that posts
PEAK = 2.5
FEED_PAGE = 20 * 1_000  # bytes of a feed page: 20 items of about 1 KB
TIMELINE_ENTRY = 16  # bytes to store "post id, time" in one follower's timeline
KEEP_PER_USER = 500  # timeline entries kept for each user
COPIES = 3

posts = DAU * POSTS / DAY
inserts = posts * FOLLOWERS  # fan-out on write: one insert per follower
reads = DAU * FEED_LOADS / DAY

print("News feed")
line("Traffic", f"posts {rate(posts * PEAK)} at peak; feed loads {rate(reads * PEAK)} at peak")
line("Fan-out", f"each post goes to {FOLLOWERS} timelines: {rate(inserts)} inserts on average, {rate(inserts * PEAK)} at peak")
line("Storage", f"timelines of {KEEP_PER_USER} entries for {DAU / 10**6:.0f} million users: {size(DAU * KEEP_PER_USER * TIMELINE_ENTRY * COPIES)} with copies")
line("Bandwidth", f"{bits(reads * PEAK * FEED_PAGE)} of feed pages out at peak")
line("Decision", f"writing each post into every follower's timeline multiplies {rate(posts * PEAK)} of posts into {rate(inserts * PEAK)} of inserts, but makes each feed load one cheap read; accounts with millions of followers are better merged in when the feed is read.")

News feed
  Traffic   posts 290/s at peak; feed loads 29,000/s at peak
  Fan-out   each post goes to 200 timelines: 23,000/s inserts on average,
            58,000/s at peak
  Storage   timelines of 500 entries for 20 million users: 480 GB with copies
  Bandwidth 4.6 Gbit/s of feed pages out at peak
  Decision  writing each post into every follower's timeline multiplies 290/s
            of posts into 58,000/s of inserts, but makes each feed load one
            cheap read; accounts with millions of followers are better merged
            in when the feed is read.

# Drill 5: real-time payments between bank accounts. Every payment must be recorded exactly once, durably.
import math

from sheet import DAY, line, rate, sig, size

DAU = 30_000_000
PAYMENTS = 2  # payments per user a day
STATUS_READS = 4  # status and history reads per user a day
PEAK = 4
WRITES_PER_PAYMENT = 4  # the payment, a debit and a credit entry, and an event for other systems
RECORD = 1_500  # bytes per payment across those rows, with index entries
COPIES = 3
KEEP_YEARS = 10
PRIMARY_WRITES = 5_000  # durable writes one database primary sustains (an assumption to measure)

payments = DAU * PAYMENTS / DAY
writes = payments * WRITES_PER_PAYMENT
reads = DAU * STATUS_READS / DAY

print("Real-time payments")
line("Traffic", f"payments {rate(payments)} on average, {rate(payments * PEAK)} at peak; status reads {rate(reads * PEAK)} at peak")
line("Writes", f"{WRITES_PER_PAYMENT} durable writes per payment: {rate(writes * PEAK)} at peak")
line("Storage", f"{size(DAU * PAYMENTS * RECORD * COPIES * 365)} a year with copies, {size(DAU * PAYMENTS * RECORD * COPIES * 365 * KEEP_YEARS)} over {KEEP_YEARS} years")
line("Decision", f"about {sig(writes * PEAK):,} durable writes a second at peak, so one primary database will not be enough: partition the ledger into at least {math.ceil(writes * PEAK / PRIMARY_WRITES)} partitions by payment id, so that each payment's {WRITES_PER_PAYMENT} writes stay inside one of them.")

Real-time payments
  Traffic   payments 690/s on average, 2,800/s at peak; status reads 5,600/s
            at peak
  Writes    4 durable writes per payment: 11,000/s at peak
  Storage   99 TB a year with copies, 990 TB over 10 years
  Decision  about 11,000 durable writes a second at peak, so one primary
            database will not be enough: partition the ledger into at least 3
            partitions by payment id, so that each payment's 4 writes stay
            inside one of them.