🖼️ See the drawing + lab 🏠 Course home 🌿 Branch on GitHub ✏️ View source

🖼️ आकृती आणि labThe drawing + lab पूर्ण पानावर उघडा ↗Open full page ↗

✏️ धडा 17 — सोडवलेल्या रचना: URL shortener · notifications · chat

📍 तुम्ही इथे आहात: 18 पैकी धडा 17 · पुढे: lesson-18-designs-files-video-rag

📦 या ब्रँचमध्ये काय आहे

धडे 01–16, आणि सुरुवातीपासून शेवटपर्यंत वापरलेली पद्धत, तीन वेळा. प्रत्येक रचना त्याच नऊ पायऱ्यांतून जाते: requirements → numbers → API → data → blocks → failure → security → observability → cost. तुम्हाला दिसेल की आकडेच आकार ठरवतात: URL shortener साठी छोटे ids, notifications साठी fan-out, chat साठी connections आणि क्रम.

design/designs.py — url_shortener(), notify(), chat(), order_by_sequence()
design/blocks.py — base62(n)
design/demo.py — python3 design/demo.py designs1
design/test_design.py — check L17

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

एकाच सकाळी दीपिकाच्या planning कार्यालयात तीन नव्या मागण्या येतात.

📎 छोट्या links. शिक्षिका forms च्या खूप लांब links सूचनांमध्ये चिकटवतात. "आम्हाला छोट्या मिळतील का?" कतरिना मोजते: मोठ्या service साठी महिन्याला 100 million नव्या links. प्रत्येक छोटा code म्हणजे 62 चिन्हांनी लिहिलेला एक आकडा (0–9, a–z, A–Z). 56 billion links साठी सहा चिन्हे पुरेशी आहेत.

📣 Notifications. शिक्षिका 40 पालकांच्या वर्गासाठी post करते: लगेच प्रत्येक पालकाच्या ट्रेमध्ये एक प्रत ठेवा. पण जिल्हा कार्यालय सर्व पालकांसाठी post करते — लाखो ट्रे. म्हणून खूप मोठ्या पाठवणाऱ्यांसाठी कार्यालय ट्रे भरत नाही. पालक app उघडतात तेव्हा जिल्ह्याचा फलक पाहतात.

💬 Chat. पालक आणि शिक्षिकांना बोलायचे आहे. phone दिवसभर कार्यालयाशी एक line उघडी ठेवतो. कार्यालयाचा एक server साधारण 50,000 उघड्या lines सांभाळू शकतो. आणि messages उलट्यासुलट्या क्रमाने येऊ शकतात, म्हणून संभाषणातल्या प्रत्येक message ला एक क्रमांक मिळतो: 1, 2, 3. phone पोहोचण्याच्या वेळेनुसार नाही, तर क्रमांकानुसार लावतो.

🗺️ आकृती

flowchart LR
    subgraph url["📎 URL shortener"]
      ug["GET /6y3o5x"] --> uc["📌 cache"] --> ukv[("🗄️ key-value<br/>code → long URL")]
      uc --> r3["301 / 302"]
    end
    subgraph nt["📣 notifications"]
      post["new notice"] -->|"under 100k followers: push"| inbox["📥 inboxes"]
      post -->|"celebrity: pull on read"| board["📋 author's feed"]
      inbox --> qs["📬 queues per channel<br/>push · SMS · email"]
    end
    subgraph ch["💬 chat"]
      ph["📱 1M online"] -->|"WebSocket"| gw["🔌 20 gateways<br/>50k each"]
      gw --> ms[("💾 messages<br/>conversation + seq")]
      gw --> pr["🟢 presence<br/>heartbeat + TTL"]
    end

🗺️ काढलेली आवृत्ती + एक lab: https://school-edh.pages.dev/system-design/lesson-diagrams.html#l17

❓ काय

📎 रचना 1 — URL shortener

पायरी	आराखडा
requirements	लांब URL साठी छोटा code तयार करा; जलद redirect करा; ऐच्छिक expiry; व्याप्तीबाहेर: custom domains
numbers	महिन्याला 100M नव्या links, प्रत्येकी 100 reads → 39 writes/s, 3,858 reads/s, peak 11,690 req/s; 5 वर्षांत 6 billion ids; ~3 TB (प्रत्येक row 500 bytes, एक प्रत)
API	`POST /links {url}` → `201 {code}` · `GET /{code}` → `Location` सह 301 किंवा 302
data	`links(code PK, long_url, owner, created_at, expires_at)` — एकच key lookup: key-value store योग्य (धडा 04)
blocks	id generator → base62 code; store च्या पुढे cache (reads हे writes च्या 100×, लोकप्रिय links खूपच लोकप्रिय)
failure	store replicated आहे; cache ऐच्छिक (miss हळू असतो, चुकीचा नाही); id generator ने एक id कधीही दोनदा देऊ नये
security	प्रत्येक user साठी creation वर rate-limit (धडा 12); phishing आणि malware साठी लांब URLs scan करा; links खाजगी असतील तर codes अंदाजाने ओळखता येऊ नयेत
observability	redirect p99, cache hit ratio, 404 rate (अचानक वाढ म्हणजे कोणीतरी codes अंदाजाने शोधत असेल)
cost	छोटा: key lookups आणि एक cache; egress अगदी थोडा (redirect म्हणजे काहीशे bytes)

Base62 — अंक 0-9a-zA-Z: 62 चिन्हे. n अक्षरे 62ⁿ codes देतात: 62⁶ ≈ 56.8 billion, 62⁷ ≈ 3.5 trillion.
Id तयार करण्याचे पर्याय:
- एक counter (database sequence, Redis INCR) — सोपे; codes क्रमाने येतात, म्हणून पुढचा कोणीही ओळखू शकतो; एक counter अत्यंत available असावा लागतो;
- ranges — प्रत्येक server counter कडून ids चा एक गठ्ठा (एका वेळी 1,000) घेतो आणि स्थानिक पातळीवर वाटतो — कमी calls, server थांबल्यावर काही ids वाया जातात;
- वेळेवर आधारित ids (Snowflake पद्धत: 64 bits मध्ये time + machine + sequence) — मध्यवर्ती counter नाही, पण लांब codes (11 base62 अक्षरांपर्यंत);
- random code + "नसेल तरच insert" — अंदाजाने ओळखता येत नाही; क्वचित collision म्हणजे "पुन्हा प्रयत्न करा"; conditional write लागतो;
- URL चा hash (6–7 अक्षरांपर्यंत कापलेला) — सारख्या URL ला सारखा code मिळतो; कापलेले hashes collide होतात, म्हणून तरीही तपासणी लागते.
301 vs 302 — 301 Moved Permanently: browsers redirect cache करू शकतात, म्हणून नंतरचे clicks तुमच्यापर्यंत पोहोचत नाहीत — स्वस्त, पण click counts गमावता आणि target बदलता येत नाही. 302 Found (किंवा 307): प्रत्येक click तुमच्याकडे येतो — analytics आणि बदलता येणारे targets, जास्त traffic.

📣 रचना 2 — notifications

पायरी	आराखडा
requirements	नवी सूचना followers पर्यंत app मध्ये पोहोचते; तातडीच्या सूचना push आणि SMS नेही; पालक channels निवडतात
numbers	एक वर्ग: 40 पालक; 300 followers असलेली शिक्षिका 3 वेळा post करते → दिवसाला 900 inbox writes; जिल्हा कार्यालय: 2,000,000 followers
API	`GET /me/inbox?cursor=…` · `PUT /me/preferences {push, sms, email}`
data	push authors साठी `inbox(parent_id, created_at, notice_id)`; celebrity posts author च्या स्वतःच्या feed मधून वाचल्या जातात
blocks	hybrid fan-out: मर्यादेखाली (इथे 100,000 followers) write वेळी push, त्यावर read वेळी pull; प्रत्येक channel साठी एक queue
failure	provider बंद → त्या channel ची queue वाढते, बाकीच्या चालू राहतात; backoff सह retries; DLQ; idempotent sends (प्रत्येक notice + parent + channel साठी एक key)
security	वर्गात फक्त वर्गशिक्षिकाच post करू शकते; तातडीचे + अनेक शाळा असेल तर दुसरी मंजुरी लागते (धडा 14); unsubscribe पाळले जाते
observability	post ते delivered पर्यंतचा वेळ, प्रत्येक channel साठी; queue depth; provider error rate
cost	SMS हा महाग channel — SMS फक्त तातडीच्या सूचनांसाठी, आणि ज्या पालकांनी तो निवडला त्यांनाच पाठवा

Push on write — notice id प्रत्येक follower च्या inbox मध्ये कॉपी करा. वाचणे म्हणजे एक lookup. खर्च followers × posts writes.
Pull on read — post एकदाच साठवा; प्रत्येक वाचणारी ती follow करत असलेल्या authors कडून गोळा करते. Post करणे म्हणजे एक write; वाचताना जास्त काम.
Celebrity hybrid — सामान्य authors साठी push, थोड्या प्रचंड authors साठी pull, आणि पालक तिचा inbox उघडते तेव्हा दोन्ही एकत्र करा.
Per-channel queues — push, SMS आणि email या वेगळ्या workers सह वेगळ्या queues आहेत. हळू SMS provider push notifications ला उशीर करू शकत नाही. तातडीच्या सूचना priority queue वर जातात.

💬 रचना 3 — chat

पायरी	आराखडा
requirements	एकास एक आणि वर्गाचे group chats; साधारण एका सेकंदात delivery; history; "online" ठिपके; offline users ना push मिळतो
numbers	एकाच वेळी 1M online, प्रत्येक server वर 50,000 WebSocket connections → 20 gateway servers; प्रत्येक user दिवसाला 40 messages → 463 msg/s, 200 bytes ला 8 GB/day
API	send/receive साठी WebSocket; history साठी REST: `GET /conversations/{id}/messages?before_seq=…`
data	`messages(conversation_id, seq, sender, body, sent_at)`, key (conversation_id, seq) — wide-column किंवा partitioned table
blocks	gateways connections सांभाळतात; registry user → gateway जोडते (Redis); message service `seq` देते आणि साठवते; registry मधून fan-out
failure	gateway बंद पडतो → त्याचे phones दुसऱ्याशी reconnect होतात (load balancer त्यांना पसरवतो); client acknowledge न झालेले messages त्याच client id सह पुन्हा पाठवतो (idempotent)
security	संभाषणात फक्त सदस्यच वाचू किंवा post करू शकतात (प्रत्येक object साठी authorization); reports आणि blocking; प्रत्येक sender साठी rate limits
observability	प्रत्येक gateway वरचे connections, message delivery latency, reconnect rate
cost	bytes नाही, connections: 20 servers, प्रत्येक थोडेसेच CPU काम करतो; storage दिवसाला 8 GB वाढते

WebSocket gateways — प्रत्येक phone साठी दीर्घकाळ टिकणारे दुतर्फी connection. server ची मर्यादा memory आणि file descriptors असते, CPU नाही. मोजलेल्या आकड्याने आखणी करा (इथे 50,000).
Per-conversation sequence numbers — message service प्रत्येक message ला त्याच्या संभाषणातला पुढचा क्रमांक देते. Clients त्यानुसार लावतात, गाळलेले शोधतात ("माझ्याकडे 1 आणि 3 आहेत, 2 आणा") आणि घड्याळांवर कधीच अवलंबून राहत नाहीत. जागतिक क्रम लागत नाही आणि तो bottleneck ठरेल.
Storage — messages संभाषणानुसार, नवीनतम आधी वाचले जातात: conversation_id नुसार partition करा, seq नुसार sort करा.
Presence — प्रत्येक phone दर ~30 s ला heartbeat पाठवतो; "online" म्हणजे Redis मधली छोट्या TTL ची key. Presence बदल फक्त ज्यांनी ते संभाषण उघडले आहे त्यांनाच पाठवा — प्रत्येक contact ला नाही.

🤔 का

कारण प्रत्येक रचनेत एक आकडा असतो जो तिचा आकार ठरवतो, आणि तो फक्त गणित करूनच सापडतो. Shortener साठी तो ids ची संख्या (→ code ची लांबी) आणि read ratio (→ cache). Notifications साठी follower count (→ push की pull). Chat साठी एकाच वेळचे connections (→ gateways) आणि क्रम (→ प्रत्येक संभाषणाचा sequence). नऊ पायऱ्या खात्री करतात की कोणताही box विसरला जात नाही.

🔧 कसे (या repo मध्ये)

design/designs.py मध्ये:

url_shortener(new_per_month, reads_per_write, bytes_per_row, years) estimate() ला बोलावते (धडा 02, एक प्रत) आणि 62ⁿ ≥ ids needed असलेली सर्वात छोटी base62 लांबी शोधते.
notify(followers, posts_per_day, celebrity_threshold=100_000) push किंवा pull निवडते.
chat(online_users, connections_per_server, messages_per_user_day, bytes_per_message) gateway servers, सेकंदाला messages आणि दिवसाचे storage परत करते.
order_by_sequence(messages) (conversation, seq, text) tuples sort करते.

base62(n) design/blocks.py मध्ये आहे. design/demo.py मधले designs1() तिन्ही चालवते.

🧪 करून पाहा

python3 design/demo.py designs1
python3 - <<'EOF'
import sys; sys.path.insert(0, "design"); from blocks import base62; from designs import url_shortener, notify, chat, order_by_sequence
for n in (1, 61, 62, 3843, 3844, 56_800_235_583, 56_800_235_584):
    print(f"id {n:>14,} → {base62(n)!r} ({len(base62(n))} chars)")
for per_month in (1_000_000, 100_000_000, 1_000_000_000):
    u = url_shortener(new_per_month=per_month)
    print(f"{per_month:>13,} links/month → {u['code_length']} chars · peak {u['peak_rps']:>7,} req/s · {u['storage_tb']} TB in 5 years")
for f in (40, 99_999, 100_000):
    print(f"{f:>7,} followers, 3 posts → {notify(f, 3)}")
for online, per in ((1_000_000, 50_000), (1_000_000, 10_000), (10_000_000, 50_000)):
    print(f"{online:>10,} online, {per:>6,} per server → {chat(online, per)}")
msgs = [("5B", 2, "ok"), ("3A", 3, "see you"), ("5B", 1, "trip?"), ("3A", 1, "hi"), ("3A", 2, "hello")]
print([f"{c}#{s} {t}" for c, s, t in order_by_sequence(msgs)])
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

designs1 हे छापते:

── URL shortener: 100M new links/month, 100 reads each → 39 writes/s, 3,858 reads/s, peak 11,690 req/s
   6,000,000,000 ids in 5 years → base62 needs 6 characters (62^6 ≈ 56.8 billion) · the last one, id 5,999,999,999 → '6y3o5x'
   read path: cache → key-value store → 301/302 redirect · write path: id generator → store
── notifications: an author with       300 followers posts 3 times → {'mode': 'push on write', 'inbox_writes_per_day': 900}
── notifications: an author with 2,000,000 followers posts 3 times → {'mode': 'pull on read (celebrity)', 'inbox_writes_per_day': 0}
── chat: 1M online, 50k WebSocket connections per server → 20 gateway servers · 463 msg/s · 8.0 GB/day
   arrival order ['see you', 'hi', 'hello'] → by sequence number ['hi', 'hello', 'see you']

तुमचा snippet हे छापतो:

id              1 → '1' (1 chars)
id             61 → 'Z' (1 chars)
id             62 → '10' (2 chars)
id          3,843 → 'ZZ' (2 chars)
id          3,844 → '100' (3 chars)
id 56,800,235,583 → 'ZZZZZZ' (6 chars)
id 56,800,235,584 → '1000000' (7 chars)
    1,000,000 links/month → 5 chars · peak     117 req/s · 0.03 TB in 5 years
  100,000,000 links/month → 6 chars · peak  11,690 req/s · 3.04 TB in 5 years
1,000,000,000 links/month → 7 chars · peak 116,898 req/s · 30.42 TB in 5 years
     40 followers, 3 posts → {'mode': 'push on write', 'inbox_writes_per_day': 120}
 99,999 followers, 3 posts → {'mode': 'push on write', 'inbox_writes_per_day': 299997}
100,000 followers, 3 posts → {'mode': 'pull on read (celebrity)', 'inbox_writes_per_day': 0}
 1,000,000 online, 50,000 per server → {'gateway_servers': 20, 'messages_per_s': 463, 'storage_gb_day': 8.0}
 1,000,000 online, 10,000 per server → {'gateway_servers': 100, 'messages_per_s': 463, 'storage_gb_day': 8.0}
10,000,000 online, 50,000 per server → {'gateway_servers': 200, 'messages_per_s': 4630, 'storage_gb_day': 80.0}
['3A#1 hi', '3A#2 hello', '3A#3 see you', '5B#1 trip?', '5B#2 ok']

Tests मध्ये ✅ L17 6 billion short links fit in 6 base62 characters आहे.

🏁 तुम्ही आत्ताच काय सिद्ध केले

Base62 मध्ये 62 च्या प्रत्येक घाताला एक अक्षर वाढते: Z म्हणजे 61, 10 म्हणजे 62, ZZZZZZ हा सहा अक्षरांचा शेवटचा code (56,800,235,583). म्हणून 6 billion links ना 6 अक्षरे लागतात, आणि दहा पट जास्त traffic ला फक्त 7 — तर peak load आणि storage प्रत्येकी दहा पट वाढतात (116,898 req/s, 30.42 TB). Fan-out ची मर्यादा हा एक कडा आहे: 99,999 followers म्हणजे दिवसाला ~300,000 inbox writes, 100,000 म्हणजे शून्य — म्हणून read वेळचे merge स्वस्त असायला हवे. Chat servers चा आकार connections ठरवतात: त्याच 463 msg/s साठी प्रत्येकी 50,000 connections ला 20 gateways, किंवा 10,000 ला 100. आणि (conversation, seq) नुसार sort केल्याने प्रत्येक संभाषणाचा क्रम कोणत्याही घड्याळाशिवाय ठरतो.

⚠️ नेहमीच्या चुका

खाजगी links साठी क्रमवार short codes — कोणीही ते सगळे एकामागोमाग पाहू शकतो
301 redirect, आणि मग प्रत्येक click च्या analytics ची मागणी — browsers नी विचारणे थांबवले आहे
जिल्हाभराची सूचना एकाच वेळी 5 million inboxes मध्ये push करणे
सगळ्या channels साठी एक queue — हळू SMS provider प्रत्येक push notification ला उशीर करतो
idempotency key शिवाय notifications पाठवणे — retry झालेला job दुसरा SMS पाठवतो
chat messages phone च्या घड्याळानुसार लावणे — phones ची घड्याळे जुळत नाहीत
प्रत्येक heartbeat ला प्रत्येक contact ला "online" पाठवणे — chat पेक्षा presence traffic मोठा
chat gateways चा आकार उघड्या connections ऐवजी CPU वरून ठरवणे

🏭 प्रत्यक्ष वापरात

खऱ्या account वर — DynamoDB मध्ये "code आधीपासून नसेल तरच insert करा" (random codes साठी, किंवा कोणत्याही generator साठी सुरक्षा जाळे):

aws dynamodb put-item --table-name links \
    --item '{"code":{"S":"6y3o5x"},"long_url":{"S":"https://forms.school.example/trip-2026?class=3A"}}' \
    --condition-expression "attribute_not_exists(code)"

छोट्या cache वेळेसह 302 redirect, म्हणजे clicks मोजले जातात आणि target बदलता येते:

HTTP/1.1 302 Found
Location: https://forms.school.example/trip-2026?class=3A
Cache-Control: private, max-age=60

Per-channel queues: "notice posted" साठी एक SNS topic, प्रत्येक channel साठी एक SQS queue, त्याला subscribe केलेली:

aws sns subscribe --topic-arn arn:aws:sns:ap-south-1:111122223333:notice-posted \
    --protocol sqs --notification-endpoint arn:aws:sqs:ap-south-1:111122223333:notify-push
aws sns subscribe --topic-arn arn:aws:sns:ap-south-1:111122223333:notice-posted \
    --protocol sqs --notification-endpoint arn:aws:sqs:ap-south-1:111122223333:notify-sms \
    --attributes '{"FilterPolicy":"{\"urgent\":[\"true\"]}"}'

API Gateway WebSocket APIs वर chat: backend एका उघड्या connection ला message पाठवतो:

aws apigatewaymanagementapi post-to-connection \
    --endpoint-url https://a1b2c3d4e5.execute-api.ap-south-1.amazonaws.com/prod \
    --connection-id "L0SM9cOFvHcCIhw=" \
    --data '{"conversation":"3A","seq":3,"text":"see you"}' --cli-binary-format raw-in-base64-out

प्रत्येक संभाषणाचा sequence number, Redis मध्ये atomic:

INCR seq:conversation:3A        → 3

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: प्रत्येक रचनेसाठी तिचा एक निर्णायक आकडा पानाच्या वर लिहा. तो आकडा दहा पट बदलला की रचना पुन्हा उघडा — फक्त आकारमान नाही, आकारही बदलू शकतो.

⏭️ पुढे

छोट्या messages च्या तीन रचना. आता जड data च्या तीन रचना: पूर्ण files, video, आणि AI search. सोडवलेल्या रचना: file storage, video आणि RAG.

git checkout lesson-18-designs-files-video-rag

✏️ Lesson 17 — Worked designs: URL shortener · notifications · chat

📍 You are here: Lesson 17 of 18 · Next: lesson-18-designs-files-video-rag

📦 What's in this branch

Lessons 01–16, plus the method used end to end, three times. Each design walks the same nine steps: requirements → numbers → API → data → blocks → failure → security → observability → cost. You will see the numbers decide the shape: short ids for the URL shortener, fan-out for notifications, connections and ordering for chat.

design/designs.py — url_shortener(), notify(), chat(), order_by_sequence()
design/blocks.py — base62(n)
design/demo.py — python3 design/demo.py designs1
design/test_design.py — check L17

🧒 Explain like I'm 5

Three new requests arrive at Dipika's planning office on the same morning.

📎 Short links. Teachers paste very long links to forms into notices. "Can we have short ones?" Katrina counts: 100 million new links a month for a large service. Each short code is a number written with 62 symbols (0–9, a–z, A–Z). Six symbols are enough for 56 billion links.

📣 Notifications. A teacher posts to a class of 40 parents: put a copy in each parent's tray at once. But the district office posts to all parents — millions of trays. So for very big senders, the office does not fill trays. Parents look at the district board when they open the app.

💬 Chat. Parents and teachers want to talk. A phone keeps a line open to the office all day. One office server can hold about 50,000 open lines. And messages may arrive out of order, so each message in a conversation gets a number: 1, 2, 3. The phone sorts by the number, not by arrival time.

🗺️ Diagram

flowchart LR
    subgraph url["📎 URL shortener"]
      ug["GET /6y3o5x"] --> uc["📌 cache"] --> ukv[("🗄️ key-value<br/>code → long URL")]
      uc --> r3["301 / 302"]
    end
    subgraph nt["📣 notifications"]
      post["new notice"] -->|"under 100k followers: push"| inbox["📥 inboxes"]
      post -->|"celebrity: pull on read"| board["📋 author's feed"]
      inbox --> qs["📬 queues per channel<br/>push · SMS · email"]
    end
    subgraph ch["💬 chat"]
      ph["📱 1M online"] -->|"WebSocket"| gw["🔌 20 gateways<br/>50k each"]
      gw --> ms[("💾 messages<br/>conversation + seq")]
      gw --> pr["🟢 presence<br/>heartbeat + TTL"]
    end

🗺️ Drawn version + a lab: https://school-edh.pages.dev/system-design/lesson-diagrams.html#l17

❓ What

📎 Design 1 — URL shortener

step	the plan
requirements	create a short code for a long URL; redirect fast; optional expiry; out of scope: custom domains
numbers	100M new links/month, 100 reads each → 39 writes/s, 3,858 reads/s, peak 11,690 req/s; 6 billion ids in 5 years; ~3 TB (500 bytes a row, one copy)
API	`POST /links {url}` → `201 {code}` · `GET /{code}` → 301 or 302 with `Location`
data	`links(code PK, long_url, owner, created_at, expires_at)` — one key lookup: a key-value store fits (lesson 04)
blocks	id generator → base62 code; cache in front of the store (reads are 100× writes, popular links are very popular)
failure	the store is replicated; the cache is optional (a miss is slower, not wrong); the id generator must never give one id twice
security	rate-limit creation per user (lesson 12); scan long URLs for phishing and malware; do not make codes guessable if links are private
observability	redirect p99, cache hit ratio, 404 rate (a spike may be someone guessing codes)
cost	small: key lookups and a cache; egress is tiny (a redirect is a few hundred bytes)

Base62 — digits 0-9a-zA-Z: 62 symbols. n characters give 62ⁿ codes: 62⁶ ≈ 56.8 billion, 62⁷ ≈ 3.5 trillion.
Id generation options:
- one counter (a database sequence, Redis INCR) — simple; codes are in order, so anyone can guess the next one; one counter must be highly available;
- ranges — each server takes a block of ids (1,000 at a time) from the counter and hands them out locally — fewer calls, a few ids lost when a server stops;
- time-based ids (Snowflake style: time + machine + sequence in 64 bits) — no central counter, but longer codes (up to 11 base62 characters);
- random code + "insert if absent" — not guessable; a rare collision means "try again"; needs a conditional write;
- hash of the URL (cut to 6–7 characters) — the same URL gets the same code; cut hashes collide, so it still needs a check.
301 vs 302 — 301 Moved Permanently: browsers may cache the redirect, so later clicks do not reach you — cheaper, but you lose click counts and cannot change the target. 302 Found (or 307): every click comes to you — analytics and changeable targets, more traffic.

📣 Design 2 — notifications

step	the plan
requirements	a new notice reaches followers in-app; urgent ones also by push and SMS; parents choose channels
numbers	a class: 40 parents; a teacher with 300 followers posting 3 times → 900 inbox writes a day; the district office: 2,000,000 followers
API	`GET /me/inbox?cursor=…` · `PUT /me/preferences {push, sms, email}`
data	`inbox(parent_id, created_at, notice_id)` for push authors; celebrity posts read from the author's own feed
blocks	hybrid fan-out: push on write under a threshold (here 100,000 followers), pull on read above it; one queue per channel
failure	provider down → that channel's queue grows, others go on; retries with backoff; DLQ; idempotent sends (one key per notice + parent + channel)
security	only the class teacher may post to a class; urgent + many schools needs a second approval (lesson 14); unsubscribe honoured
observability	time from post to delivered, per channel; queue depth; provider error rate
cost	SMS is the expensive channel — send SMS only for urgent notices, and only to parents who chose it

Push on write — copy the notice id into every follower's inbox. Reading is one lookup. The cost is followers × posts writes.
Pull on read — store the post once; each reader collects from the authors she follows. Posting is one write; reading does more work.
Celebrity hybrid — push for normal authors, pull for the few huge ones, and merge the two when a parent opens her inbox.
Per-channel queues — push, SMS and email are separate queues with separate workers. A slow SMS provider cannot delay the push notifications. Urgent notices go on a priority queue.

💬 Design 3 — chat

step	the plan
requirements	one-to-one and class group chats; delivery in about a second; history; "online" dots; offline users get a push
numbers	1M online at once, 50,000 WebSocket connections per server → 20 gateway servers; 40 messages per user a day → 463 msg/s, 8 GB/day at 200 bytes
API	a WebSocket for send/receive; REST for history: `GET /conversations/{id}/messages?before_seq=…`
data	`messages(conversation_id, seq, sender, body, sent_at)`, key (conversation_id, seq) — wide-column or a partitioned table
blocks	gateways hold connections; a registry maps user → gateway (Redis); a message service assigns `seq` and stores; fan-out through the registry
failure	a gateway dies → its phones reconnect to another (the load balancer spreads them); the client re-sends unacknowledged messages with the same client id (idempotent)
security	only members may read or post in a conversation (authorization per object); reports and blocking; rate limits per sender
observability	connections per gateway, message delivery latency, reconnect rate
cost	connections, not bytes: 20 servers doing little CPU work each; storage grows 8 GB a day

WebSocket gateways — a long-lived two-way connection per phone. A server's limit is memory and file descriptors, not CPU. Plan with a measured number (50,000 here).
Per-conversation sequence numbers — the message service gives each message the next number in its conversation. Clients sort by it, find gaps ("I have 1 and 3, fetch 2") and never depend on clocks. A global order is not needed and would be a bottleneck.
Storage — messages are read by conversation, newest first: partition by conversation_id, sort by seq.
Presence — each phone sends a heartbeat every ~30 s; "online" is a key with a short TTL in Redis. Send presence changes only to people who have that conversation open — not to every contact.

🤔 Why

Because each design has one number that decides its shape, and you find it only by doing the sums. For the shortener it is the count of ids (→ code length) and the read ratio (→ cache). For notifications it is the follower count (→ push or pull). For chat it is concurrent connections (→ gateways) and ordering (→ sequence per conversation). The nine steps make sure no box is forgotten.

🔧 How (in this repo)

In design/designs.py:

url_shortener(new_per_month, reads_per_write, bytes_per_row, years) calls estimate() (lesson 02, one copy) and finds the shortest base62 length with 62ⁿ ≥ ids needed.
notify(followers, posts_per_day, celebrity_threshold=100_000) picks push or pull.
chat(online_users, connections_per_server, messages_per_user_day, bytes_per_message) returns gateway servers, messages per second and storage per day.
order_by_sequence(messages) sorts (conversation, seq, text) tuples.

base62(n) is in design/blocks.py. designs1() in design/demo.py runs all three.

🧪 Try it

python3 design/demo.py designs1
python3 - <<'EOF'
import sys; sys.path.insert(0, "design"); from blocks import base62; from designs import url_shortener, notify, chat, order_by_sequence
for n in (1, 61, 62, 3843, 3844, 56_800_235_583, 56_800_235_584):
    print(f"id {n:>14,} → {base62(n)!r} ({len(base62(n))} chars)")
for per_month in (1_000_000, 100_000_000, 1_000_000_000):
    u = url_shortener(new_per_month=per_month)
    print(f"{per_month:>13,} links/month → {u['code_length']} chars · peak {u['peak_rps']:>7,} req/s · {u['storage_tb']} TB in 5 years")
for f in (40, 99_999, 100_000):
    print(f"{f:>7,} followers, 3 posts → {notify(f, 3)}")
for online, per in ((1_000_000, 50_000), (1_000_000, 10_000), (10_000_000, 50_000)):
    print(f"{online:>10,} online, {per:>6,} per server → {chat(online, per)}")
msgs = [("5B", 2, "ok"), ("3A", 3, "see you"), ("5B", 1, "trip?"), ("3A", 1, "hi"), ("3A", 2, "hello")]
print([f"{c}#{s} {t}" for c, s, t in order_by_sequence(msgs)])
EOF

✅ Verify — what you should see

designs1 prints:

── URL shortener: 100M new links/month, 100 reads each → 39 writes/s, 3,858 reads/s, peak 11,690 req/s
   6,000,000,000 ids in 5 years → base62 needs 6 characters (62^6 ≈ 56.8 billion) · the last one, id 5,999,999,999 → '6y3o5x'
   read path: cache → key-value store → 301/302 redirect · write path: id generator → store
── notifications: an author with       300 followers posts 3 times → {'mode': 'push on write', 'inbox_writes_per_day': 900}
── notifications: an author with 2,000,000 followers posts 3 times → {'mode': 'pull on read (celebrity)', 'inbox_writes_per_day': 0}
── chat: 1M online, 50k WebSocket connections per server → 20 gateway servers · 463 msg/s · 8.0 GB/day
   arrival order ['see you', 'hi', 'hello'] → by sequence number ['hi', 'hello', 'see you']

Your snippet prints:

id              1 → '1' (1 chars)
id             61 → 'Z' (1 chars)
id             62 → '10' (2 chars)
id          3,843 → 'ZZ' (2 chars)
id          3,844 → '100' (3 chars)
id 56,800,235,583 → 'ZZZZZZ' (6 chars)
id 56,800,235,584 → '1000000' (7 chars)
    1,000,000 links/month → 5 chars · peak     117 req/s · 0.03 TB in 5 years
  100,000,000 links/month → 6 chars · peak  11,690 req/s · 3.04 TB in 5 years
1,000,000,000 links/month → 7 chars · peak 116,898 req/s · 30.42 TB in 5 years
     40 followers, 3 posts → {'mode': 'push on write', 'inbox_writes_per_day': 120}
 99,999 followers, 3 posts → {'mode': 'push on write', 'inbox_writes_per_day': 299997}
100,000 followers, 3 posts → {'mode': 'pull on read (celebrity)', 'inbox_writes_per_day': 0}
 1,000,000 online, 50,000 per server → {'gateway_servers': 20, 'messages_per_s': 463, 'storage_gb_day': 8.0}
 1,000,000 online, 10,000 per server → {'gateway_servers': 100, 'messages_per_s': 463, 'storage_gb_day': 8.0}
10,000,000 online, 50,000 per server → {'gateway_servers': 200, 'messages_per_s': 4630, 'storage_gb_day': 80.0}
['3A#1 hi', '3A#2 hello', '3A#3 see you', '5B#1 trip?', '5B#2 ok']

The tests include ✅ L17 6 billion short links fit in 6 base62 characters.

🏁 What you just proved

Base62 grows one character at each power of 62: Z is 61, 10 is 62, ZZZZZZ is the last six-character code (56,800,235,583). So 6 billion links need 6 characters, and ten times more traffic needs only 7 — while peak load and storage grow ten times each (116,898 req/s, 30.42 TB). The fan-out threshold is a cliff: 99,999 followers means ~300,000 inbox writes a day, 100,000 means zero — so the merge on read must be cheap. Chat servers are sized by connections: the same 463 msg/s needs 20 gateways at 50,000 connections each, or 100 at 10,000. And sorting by (conversation, seq) fixes the order per conversation, without any clock.

⚠️ Common mistakes

sequential short codes for private links — anyone can walk through all of them
a 301 redirect, then a request for per-click analytics — browsers stopped asking
pushing a district-wide notice into 5 million inboxes at once
one queue for all channels — a slow SMS provider delays every push notification
sending notifications without an idempotency key — a retried job sends a second SMS
ordering chat messages by the phone's clock — phones' clocks disagree
broadcasting "online" to every contact on every heartbeat — presence traffic larger than the chat
sizing chat gateways by CPU instead of open connections

🏭 In production

On a real account — "insert the code only if it does not exist yet" in DynamoDB (random codes, or a safety net for any generator):

aws dynamodb put-item --table-name links \
    --item '{"code":{"S":"6y3o5x"},"long_url":{"S":"https://forms.school.example/trip-2026?class=3A"}}' \
    --condition-expression "attribute_not_exists(code)"

A 302 redirect with a short cache time, so clicks are counted and the target can change:

HTTP/1.1 302 Found
Location: https://forms.school.example/trip-2026?class=3A
Cache-Control: private, max-age=60

Per-channel queues: one SNS topic for "notice posted", one SQS queue per channel, subscribed to it:

aws sns subscribe --topic-arn arn:aws:sns:ap-south-1:111122223333:notice-posted \
    --protocol sqs --notification-endpoint arn:aws:sqs:ap-south-1:111122223333:notify-push
aws sns subscribe --topic-arn arn:aws:sns:ap-south-1:111122223333:notice-posted \
    --protocol sqs --notification-endpoint arn:aws:sqs:ap-south-1:111122223333:notify-sms \
    --attributes '{"FilterPolicy":"{\"urgent\":[\"true\"]}"}'

Chat on API Gateway WebSocket APIs: the backend sends a message to one open connection:

aws apigatewaymanagementapi post-to-connection \
    --endpoint-url https://a1b2c3d4e5.execute-api.ap-south-1.amazonaws.com/prod \
    --connection-id "L0SM9cOFvHcCIhw=" \
    --data '{"conversation":"3A","seq":3,"text":"see you"}' --cli-binary-format raw-in-base64-out

A per-conversation sequence number, atomic in Redis:

INCR seq:conversation:3A        → 3

🏭 Why this matters in production: for each design, write its one deciding number at the top of the page. When that number changes by ten times, reopen the design — the shape may change, not only the size.

⏭️ Next

Three designs with small messages. Now three designs with heavy data: whole files, video, and AI search. Worked designs: file storage, video and RAG.

git checkout lesson-18-designs-files-video-rag

← Previouscost and adrs Next →designs files video rag

This page is the lesson's README from the lesson-17-designs-short-notify-chat branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.