Design a paste service like Pastebin

A paste service stores a block of text, such as a log, a code snippet or a configuration file, and returns a link that shows it. The design splits every paste in two: the text goes to an object store as one object, and a small row in a database records who owns it, who may read it and when it expires. Every read checks that row before it returns any text, which is what keeps expired and removed pastes from coming back. Unlisted links get long random ids, public pastes are served by a CDN, and an abuse report can end in a takedown that has to reach every copy within the hours a law allows. Next to a URL shortener the payload is bigger, from a few bytes to a megabyte, and it has a lifetime.

About 700 reads a second, and storage set by the pastes that never expire

Ask these before drawing anything, and note the answer you assume:

• How large can a paste be? Up to 1 MB of text.
• When does a paste expire? The creator picks: after 10 minutes, an hour, a day, a week, a month, a year, never, or right after its first reading.
• Who can read it? Anyone for a public paste; anyone with the link for an unlisted one; only its signed-in owner for a private one.
• Can a paste change? No. An edit makes a new paste.

Pastebin’s own API offers the same kind of choices: expiry from 10 minutes to a year or never, and the three levels public, unlisted and private (Pastebin API documentation).

The functional requirements: create a paste, read it by id, list your own pastes, delete one, report one. The non-functional ones: reads return in tens of milliseconds and stay available when creates are failing; a paste is never readable after it expires or is removed; nobody can find an unlisted paste without its link; and a takedown reaches every copy within hours.

# The estimate sheet of a paste service (lesson system-design-hld/design-pastebin). Pastes expire, so the number kept
# is set by how long each one lives: Little's law, kept = created per day x days kept, for every expiry choice. The
# pastes that never expire are the exception: they pile up year after year. Sizes are decimal (1 TB = 10**12 bytes).
DAY = 86_400

NEW_PER_DAY = 2_000_000
READS_PER_DAY = 20_000_000  # ten reads per paste on average; a few popular pastes take most of them
PEAK = 3
PASTE_BYTES = 8_000  # the average paste; the service caps a paste at 1 MB
META_BYTES = 300  # one metadata row with its indexes
META_COPIES = 3
YEARS = 5
CDN_SHARE = 0.6  # share of reads the CDN serves: public and unlisted pastes, never private ones

# Share of new pastes for each expiry choice, and how long each lives, in days (None: never expires).
EXPIRY = {"10 minutes": (0.05, 10 / 1440), "1 hour": (0.10, 1 / 24), "1 day": (0.25, 1), "1 week": (0.20, 7),
          "1 month": (0.15, 30), "1 year": (0.10, 365), "never": (0.15, None)}

assert abs(sum(share for share, _ in EXPIRY.values()) - 1) < 1e-9

kept = {}
for name, (share, days) in EXPIRY.items():
    lifetime = YEARS * 365 if days is None else min(days, YEARS * 365)  # nothing is older than the service
    kept[name] = NEW_PER_DAY * share * lifetime
total = sum(kept.values())

print("Paste service: the estimate sheet")
print(f"  Creates    {NEW_PER_DAY / DAY:,.0f}/s on average, {NEW_PER_DAY / DAY * PEAK:,.0f}/s at the peak")
print(f"  Reads      {READS_PER_DAY / DAY:,.0f}/s on average, {READS_PER_DAY / DAY * PEAK:,.0f}/s at the peak,")
print(f"             {READS_PER_DAY / DAY * PEAK * (1 - CDN_SHARE):,.0f}/s of them reach the servers")
print(f"  Deletes    {NEW_PER_DAY * (1 - EXPIRY['never'][0]) / DAY:,.0f}/s on average: every paste that expires")
print(f"  Kept after {YEARS} years, by expiry choice:")
for name, n in kept.items():
    print(f"    {name:<11}{n:>13,.0f}  {n / total:>6.1%}")
print(f"    {'all':<11}{total:>13,.0f}")
print(f"  Content    {total * PASTE_BYTES / 10**12:.1f} TB in the object store")
print(f"  Metadata   {total * META_BYTES / 10**9:,.0f} GB, {total * META_BYTES * META_COPIES / 10**9:,.0f} GB with {META_COPIES} copies")
print(f"  Bandwidth  {READS_PER_DAY / DAY * PEAK * PASTE_BYTES * 8 / 10**6:.0f} Mbit/s of pastes at the peak")

Paste service: the estimate sheet
  Creates    23/s on average, 69/s at the peak
  Reads      231/s on average, 694/s at the peak,
             278/s of them reach the servers
  Deletes    20/s on average: every paste that expires
  Kept after 5 years, by expiry choice:
    10 minutes           694    0.0%
    1 hour             8,333    0.0%
    1 day            500,000    0.1%
    1 week         2,800,000    0.4%
    1 month        9,000,000    1.4%
    1 year        73,000,000   11.5%
    never        547,500,000   86.5%
    all          632,809,028
  Content    5.1 TB in the object store
  Metadata   190 GB, 570 GB with 3 copies
  Bandwidth  44 Mbit/s of pastes at the peak

This is a small system by traffic: 69 creates and 694 reads a second at the peak, and 5.1 TB of text after five years. The interesting numbers are about time. Pastes that expire within a month are less than 2 % of what is kept, while the 15 % of pastes that never expire make up 86.5 % of it after five years. And expiry is steady work, 20 deletions a second, not an occasional cleanup.

DAY = 86_400


def live_pastes(new_per_day, mix, years):
    """Pastes kept after `years` years; `mix` maps lifetime in days (None: never expires) to a share of new pastes."""
    # Replace this line with your code.
    return 0


def footprint(live, paste_bytes, meta_bytes, meta_copies):
    """Bytes of content in the object store and bytes of metadata with its copies."""
    # Replace this line with your code.
    return {}


def server_reads(reads_per_day, peak, cdn_share):
    """Reads a second at the peak that reach the servers."""
    # Replace this line with your code.
    return 0

import math

from footprint import footprint, live_pastes, server_reads

LESSON_MIX = {10 / 1440: 0.05, 1 / 24: 0.10, 1: 0.25, 7: 0.20, 30: 0.15, 365: 0.10, None: 0.15}
SHORT_MIX = {1: 0.5, 30: 0.3, None: 0.2}


def near(actual, expected):
    """Within 10%, as an estimate should be."""
    return math.isclose(actual, expected, rel_tol=0.10)


def test_live_pastes_lesson():
    """keeps each expiry choice for its lifetime, and never-expiring pastes for the service's age"""
    assert near(live_pastes(2_000_000, LESSON_MIX, 5), 632_800_000)


def test_live_pastes_other_mix():
    """works for another mix and period"""
    assert near(live_pastes(1_000_000, SHORT_MIX, 2), 155_500_000)


def test_young_service():
    """counts a lifetime longer than the service's age as that age"""
    assert near(live_pastes(1_000_000, {365: 1.0}, 0.5), 182_500_000)
    assert near(live_pastes(1_000_000, {365: 0.5, None: 0.5}, 0.5), 182_500_000)


def test_footprint():
    """stores one copy of the content and every copy of the metadata"""
    sizes = footprint(632_800_000, 8_000, 300, 3)
    assert near(sizes["objects"], 5.06e12)
    assert near(sizes["metadata"], 5.7e11)


def test_server_reads():
    """leaves the CDN's share of reads out"""
    assert near(server_reads(20_000_000, 3, 0.6), 278)
    assert near(server_reads(50_000_000, 2, 0.9), 116)

The first design: the row is read before any text

Follow a read through it. The CDN answers public and unlisted pastes it holds; everything else reaches an API server, which reads the paste’s row first and fetches the text from the object store only if the row allows it. A create writes the text, then the row. Background jobs clean up expired pastes and scan new ones, and the abuse desk can mark a paste removed and purgepurge (CDN): Removing a URL, or every response with a tag, from a CDN's caches before its lifetime runs out. It cannot reach the copies that browsers already hold. More in “CDNs and edge caching” it from the CDN. Step through one paste, from its create to its removal:

The questions this design has to answer:

• Why is the text in an object store and not in the row?
• How do 10-minute expiries work when storage lifecycle ruleslifecycle rule: A bucket setting that moves objects to another storage class, or deletes them, once they reach a given age. Each transition is a billed request, and S3 does not move objects smaller than 128 KB by default. More in “Block, file and object storage” count in days?
• What stops an expired or removed paste from coming back out of a cache?
• How many random characters keep an unlisted paste from being found?
• How does a burn-after-reading paste reach exactly one reader?
• How does a takedown reach every copy within the legal deadline?
• What changes at ten and a hundred times the traffic?

Status codes clients and caches act on, and an index for every query Pro: opens with a Pro, Premium or Ultimate pass