URL Shortener / Pastebin Design - ছোট link, পুরো একটা design

০০ যে প্রশ্নগুলোর উত্তর খুঁজবো

এতদিন আমরা টুকরো টুকরো শিখেছি। Cache, replica, shard, CDN, queue: প্রতিটা আলাদা সেশনে, আলাদা সমস্যার সমাধান হিসেবে। এবার সেই টুকরোগুলো জোড়া লাগিয়ে একটা আস্ত system বানানোর পালা।

শুরুর জন্য URL shortener সবচেয়ে ভালো বন্ধু। Idea টা এক লাইনের: লম্বা link দিলে ছোট link পাবেন। কিন্তু একটু ভেতরে ঢুকলেই প্রায় সব বড় প্রশ্ন সামনে আসে: কত traffic, কোথায় data রাখবো, কীভাবে দুইজনকে একই code দেওয়া ঠেকাবো। Interview তেও এটা সবচেয়ে বেশি আসা প্রশ্নগুলোর একটা। তাই এই সেশনে আমরা ধীরে ধীরে, প্রতিটা ধাপ হাতে কলমে করে এগোবো।

এটা স্টেজ ০৯ এর প্রথম case study। তাই আগে কাঠামোটা দেখে নিন। এই স্টেজের প্রতিটা সেশন, আর একটা ভালো system design interview, এই সাতটা ধাপ মেনে এগোয়:

অনেকে প্রশ্ন শুনেই box আঁকতে শুরু করেন। আমরা তা করবো না। আগে জানবো কী বানাতে হবে, তারপর হিসাব করবো কত বড় বানাতে হবে। দেখবেন, হিসাবটা নিজেই বলে দেয় design এর কঠিন অংশ কোথায়।

এই স্টেজের design গুলো সহজ থেকে কঠিনের দিকে সাজানো। আজ একটা key আর একটা cache দিয়ে শুরু। তারপর rate limiter আর search, তারপর feed এর fan-out, chat এর real-time connection, YouTube এর বিশাল data, আর শেষে Uber, যেখানে আগের প্রায় সবকিছু একসাথে লাগে। প্রতিটা সেশন আগেরটার উপর দাঁড়িয়ে থাকবে।

০১ URL shortener এর functional requirement আর non-functional requirement কী কী?

বৃহস্পতিবার বিকেল। অর্ক “কোড ক্যাফে” club এর general secretary। Cafeteria-র সামনের notice board এ সে এইমাত্র hackathon এর poster টা লাগিয়ে একটু দূরে দাঁড়িয়েছে। Poster এর নিচে registration এর Google Form link, পুরো ৮০ অক্ষরের। একজন first-year student phone বের করে link টা টাইপ করতে শুরু করলো। 1FAIpQLSd এ এসে সে থমকে গেলো: এটা বড় হাতের I, নাকি ছোট হাতের l? দুইবার ভুল হলো। তারপর phone টা পকেটে রেখে সে চলে গেলো।

অর্কের মনটা খারাপ হয়ে গেলো। এমন কতজন যে এভাবে ফিরে যাচ্ছে, সে জানেও না। সেদিন রাতেই সে ঠিক করলো, club এর নিজের একটা ছোট link লাগবে: cc.lnk/hack26। মাত্র ১৩ অক্ষর, ভুল হওয়ার সুযোগই নেই।

ছোট link আসলে কীভাবে কাজ করে

Idea টা সহজ। কেউ cc.lnk/hack26 খুললে আমাদের server একটা table এ hack26 খোঁজে। সেখানে লম্বা link টা পায়। তারপর browser কে বলে দেয়: “আসল ঠিকানা ওইটা, ওখানে যান।” Browser কে এভাবে অন্য ঠিকানায় পাঠিয়ে দেওয়ার নাম redirect।

Requirement: আগে ঠিক করুন কী বানাচ্ছেন

Design শুরু করার আগে প্রথম কাজ হলো দুটো প্রশ্নের উত্তর লিখে ফেলা। System টা কী কী করবে? আর কতটা ভালোভাবে করবে? প্রথম প্রশ্নের উত্তরগুলোকে বলে functional requirement, মানে feature এর তালিকা। দ্বিতীয়টার উত্তরগুলোকে বলে non-functional requirement, মানে গতি, নির্ভরযোগ্যতা আর আকারের শর্ত।

অর্কের system এর functional requirement:

1. ছোট link বানানো: লম্বা URL দিলে একটা ছোট, unique link পাওয়া যাবে।
2. Redirect: ছোট link খুললে আসল URL এ পৌঁছে যাবে।
3. Custom alias: চাইলে নিজের পছন্দের নাম দেওয়া যাবে, যেমন hack26।
4. Expiry: চাইলে link এর একটা মেয়াদ দেওয়া যাবে। Registration শেষ হলে link আর কাজ করবে না।
5. Analytics: কোন link এ কতবার click পড়লো, দেখা যাবে। অর্ক জানতে চায়, poster থেকে আসলে কতজন এলো।

আর non-functional requirement:

• Redirect খুব দ্রুত হবে: Server এর ভেতরের কাজ ১০ millisecond এর মধ্যে শেষ হবে। User যেন টেরই না পায় মাঝখানে একটা ধাপ ছিলো।
• সবসময় চালু থাকবে (high availability): আমাদের service down হলে দেশের সব poster এর সব link একসাথে অকেজো হয়ে যায়। তাই availability অন্তত 99.9% (SLA এর কথা সেশন ০১ এ দেখেছেন)।
• Link হারাবে না: একবার বানানো link বছরের পর বছর কাজ করবে, কারণ poster তো দেয়ালে থেকেই যায়।
• Code আন্দাজ করা কঠিন হবে: কেউ যেন hack26 এর পরের code টা অনুমান করে অন্যের private link খুঁজে না পায়।

একটা জিনিস এখনই চোখে পড়ে। একটা link বানানো হয় একবার, কিন্তু click পড়ে শত শত বার। অর্থাৎ এই system এ write কম, read অনেক বেশি। এমন system কে বলে read-heavy। এই একটা কথাই পুরো design এর দিক ঠিক করে দেবে।

০২ Back-of-envelope estimation: দিনে কত link, সেকেন্ডে কত QPS, কত storage?

এক মাসের মধ্যে আরো তিরিশটা club অর্কের কাছে এলো: “ভাই, আমাদেরও একটা দিন না।” তারপর পাশের university, তারপর অনলাইন দোকান আর কোচিং সেন্টার। ধরুন কয়েক বছরে service টা সারা দেশে ছড়িয়ে গেলো। তখন কত বড় machine লাগবে? কয়টা? এই প্রশ্নের উত্তর পেতে নিখুঁত হিসাবের দরকার নেই। শুধু মাত্রাটা বুঝলেই চলে: সংখ্যাটা কি হাজারে, লাখে, নাকি কোটিতে?

এই মোটা দাগের হিসাবকে বলে back-of-envelope estimation: খামের পেছনে পাঁচ মিনিটে করা যায় এমন হিসাব। পুরোনো দিনের engineer রা এমন হিসাব সত্যিই খামের উল্টো পিঠে করতেন, নামটা সেখান থেকেই এসেছে। এই স্টেজের প্রতিটা design এ আমরা এই হিসাবটা করবো, তাই এখানে প্রতিটা ধাপ হাতে করে দেখবো। হিসাবে একটা শব্দ বারবার আসবে: QPS (queries per second), মানে সেকেন্ডে কতগুলো request আসে। আর peak মানে দিনের সবচেয়ে ব্যস্ত সময়, যখন traffic গড়ের চেয়ে কয়েক গুণ বেশি থাকে।

ধরে নিই (assumption)
  নতুন short link প্রতিদিন   : 1 কোটি = 10,000,000
  read : write              : 100 : 1   (link বানানো হয় একবার, click হয় বহুবার)
  peak                      : গড়ের 3 গুণ

Write QPS (নতুন link)
  10,000,000 / 86,400 sec    ≈ 116 write/sec
  peak এ                     ≈ 350 write/sec

Read QPS (redirect)
  116 × 100                  ≈ 11,600 read/sec
  peak এ                     ≈ 35,000 read/sec

Storage (প্রতিটা row ~500 byte: URL ~200, বাকি column আর index ~300)
  10,000,000 × 500 B         = 5 GB / দিন
  5 GB × 365                 ≈ 1.8 TB / বছর
  5 বছরে                      ≈ 9 TB
  5 বছরে মোট link             = 10,000,000 × 365 × 5 = 18,250,000,000 (18.25 billion)

Cache (সব নয়, শুধু hot link)
  দিনে আলাদা আলাদা link এ click   ≈ 5 কোটি (ধরে নিলাম)
  সবচেয়ে hot 20%                ≈ 1 কোটি link × 500 B ≈ 5 GB  → একটা Redis এই এঁটে যায়

Bandwidth
  35,000 redirect/sec × ~500 B  ≈ 17.5 MB/sec  → খুবই সামান্য

সংখ্যাগুলো এবার design এর ভাষায় পড়া যাক:

০৩ API, data model আর high-level design কেমন হবে?

API: বাইরের দুনিয়ার সাথে চুক্তি

API হলো বাইরের দুনিয়ার সাথে আমাদের চুক্তি: কোন ঠিকানায় কী পাঠালে কী ফেরত আসবে। অর্কের system এ চারটা কাজ দরকার:

# ১) নতুন short link বানানো
POST /api/v1/urls
Authorization: Bearer <token>
{
  "long_url":     "https://docs.google.com/forms/d/e/1FAIpQLSd.../viewform",
  "custom_alias": "hack26",                 // না দিলেও চলে
  "expires_at":   "2026-12-31T23:59:59Z"    // না দিলেও চলে
}
→ 201 Created
{ "short_url": "https://cc.lnk/hack26" }

# ২) Redirect (system এর আসল কাজ)
GET /hack26
→ 302 Found
Location: https://docs.google.com/forms/d/e/1FAIpQLSd.../viewform

# ৩) Click এর হিসাব দেখা
GET /api/v1/urls/hack26/stats
→ 200 OK
{ "total_clicks": 1240, "today": 312 }

# ৪) Link মুছে ফেলা
DELETE /api/v1/urls/hack26
→ 204 No Content

খেয়াল করুন, redirect এর ঠিকানাটা /api/v1/ এর নিচে নেই। ওটা সরাসরি cc.lnk/hack26, কারণ এই ঠিকানাটাই poster এ ছাপা হয়। যত ছোট, তত ভালো।

Data model: কী store করবো

আমাদের data খুবই সরল। একটা code এর বিপরীতে একটা লম্বা URL, আর তার সাথে কয়েকটা তথ্য:

CREATE TABLE urls (
    short_code   VARCHAR(16)  PRIMARY KEY,   -- "1005ban" বা custom "hack26"
    long_url     TEXT         NOT NULL,      -- গড়ে ~200 byte, সর্বোচ্চ 2,048
    user_id      BIGINT,                     -- কে বানিয়েছে
    created_at   TIMESTAMP    NOT NULL,
    expires_at   TIMESTAMP                   -- NULL মানে মেয়াদ নেই
);

CREATE TABLE users (
    user_id      BIGINT       PRIMARY KEY,
    email        VARCHAR(255) UNIQUE,
    created_at   TIMESTAMP    NOT NULL
);

-- click এর হিসাব এখানে নেই; সেটা আলাদা analytics store এ থাকে

এখানে short_code হলো primary key। ফলে একই code দুইবার INSERT হতে পারে না, database নিজেই সেটা আটকায়। এই সুবিধাটা আমরা সেকশন ০৮ এ কাজে লাগাবো।

SQL নাকি NoSQL? আমাদের প্রায় সব query একই রকম: একটা short_code দিয়ে একটা row খোঁজা। কোনো join নেই, জটিল query নেই। শুরুতে PostgreSQL বা MySQL একদম যথেষ্ট। Data অনেক বড় হলে DynamoDB বা Cassandra এর মতো key-value store ও ভালো চলে, কারণ এদের ভাগ করে অনেক machine এ ছড়িয়ে দেওয়া সহজ।

High-level design: প্রথম খসড়া

এবার box আঁকার পালা। প্রথম খসড়াটা ইচ্ছা করেই সরল রাখা হলো:

দুটো আলাদা service কেন? কারণ দুটোর চাপ একদম আলাদা। Write API সেকেন্ডে ৩৫০টা request পায়, Redirect Service পায় ৩৫,০০০টা। আলাদা থাকলে শুধু redirect server এর সংখ্যা বাড়ানো যায়, write এর গায়ে হাত না দিয়েই। Load balancer request এর path দেখে ঠিক service এ পাঠায় (load balancer এর কথা সেশন ০২ এ দেখেছেন)।

এই খসড়ায় একটা বড় প্রশ্নের উত্তর এখনো নেই। Write API নতুন link এর জন্য 1005ban বা 2LrsIyw এর মতো code টা পাবে কোথা থেকে? পরের দুই সেকশন এই প্রশ্ন নিয়েই।

০৪ Short code কীভাবে বানাবো? (base62 আর counter)

ভালো short code এর চারটা গুণ থাকা দরকার। Code ছোট হবে। Unique হবে, মানে দুইটা link কখনো একই code পাবে না। URL এ লেখা নিরাপদ হবে। আর আন্দাজ করা কঠিন হবে।

Base62: অল্প অক্ষরে বড় সংখ্যা

আমরা সাধারণত দশটা অঙ্ক দিয়ে গুনি: 0 থেকে 9। একে বলে base 10। Base62 মানে ৬২টা “অঙ্ক” দিয়ে গোনা: দশটা সংখ্যা, ২৬টা ছোট হাতের অক্ষর আর ২৬টা বড় হাতের অক্ষর। প্রতিটা ঘরে ১০টার বদলে ৬২টা সম্ভাবনা থাকে, তাই অল্প কয়েকটা অক্ষরেই বিশাল সংখ্যা লেখা যায়।

তাহলে base64 কেন নয়? Base64 এ আরো দুটো চিহ্ন থাকে: + আর /। URL এ / মানে নতুন path, আর + অনেক জায়গায় space হয়ে যায়। Base62 এ এমন কোনো ঝামেলা নেই।

Alphabet: 62টা অক্ষর
  0-9   → 10টা
  a-z   → 26টা
  A-Z   → 26টা
  মোট   → 62টা   "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

কত অক্ষরে কতগুলো আলাদা code
  62^5  =           916,132,832   (প্রায় 92 কোটি)
  62^6  =        56,800,235,584   (প্রায় 5,680 কোটি)
  62^7  =     3,521,614,606,208   (প্রায় 3.5 লাখ কোটি)

5 বছরে দরকার 18.25 billion
  62^6 এ ঢোকে, কিন্তু এক-তৃতীয়াংশ ভরে যায়
  62^7 এ জায়গা প্রায় 190 গুণ বেশি   → তাই 7 অক্ষর

উদাহরণ: 1,000,000 সংখ্যাটাকে base62 তে লেখা (বারবার 62 দিয়ে ভাগ)
  1,000,000 ÷ 62 = 16,129   ভাগশেষ  2   → '2'
     16,129 ÷ 62 =    260   ভাগশেষ  9   → '9'
        260 ÷ 62 =      4   ভাগশেষ 12   → 'c'
          4 ÷ 62 =      0   ভাগশেষ  4   → '4'
  ভাগশেষগুলো নিচ থেকে উপরে পড়ুন      → "4c92"

মিলিয়ে দেখা
  4×62³ + 12×62² + 9×62 + 2
  = 953,312 + 46,128 + 558 + 2
  = 1,000,000  ✓

হিসাবটা বলছে, ৭ অক্ষরেই প্রায় সাড়ে তিন লাখ কোটি আলাদা code বানানো যায়। আমাদের ৫ বছরে দরকার ১,৮২৫ কোটি। তাই ৭ অক্ষর নিশ্চিন্তে বহু বছর চলবে।

Counter: প্রতিটা link কে একটা ক্রমিক নম্বর দেওয়া

সবচেয়ে সরল উপায় হলো একটা counter রাখা। নতুন link এলে counter এক বাড়ে, আর সেই সংখ্যাটা base62 তে লিখে দেওয়া হয়। দুইটা link কখনো একই সংখ্যা পায় না, তাই collision এর প্রশ্নই ওঠে না।

একটা ছোট কৌশল আছে। Counter টা 1 থেকে শুরু করলে প্রথম দিকের code হবে 1, 2, 3। তাই counter শুরু করা হয় 62^6 থেকে, মানে 56,800,235,584 থেকে। এই সংখ্যার base62 রূপ 1000000, পুরো ৭ অক্ষরের। এরপরের প্রতিটা code ও ৭ অক্ষরের হয়। অর্কের hackathon link যেমন পেলো 56,801,470,151 নম্বর, যার base62 রূপ 1005ban।

কিন্তু counter এর দুটো সমস্যা আছে।

1. একটা counter মানে একটা SPOF: সব write server কে প্রতিটা link এর জন্য একই counter এর কাছে যেতে হয়। Counter down হলে কেউ নতুন link বানাতে পারে না (SPOF এর কথা সেশন ০১ এ দেখেছেন)।
2. Code আন্দাজ করা যায়: 1005ban এর পরের code 1005bao। কেউ একটা ছোট script লিখে পরপর সব code খুলে দেখতে পারে। তার মধ্যে কারো private Google Doc এর link থাকতেই পারে।

প্রথম সমস্যার সমাধান হলো counter থেকে একটা একটা সংখ্যা না নিয়ে একবারে একটা range নেওয়া:

দ্বিতীয় সমস্যার সমাধান হলো সংখ্যাটাকে base62 তে লেখার আগে একটা গোপন নিয়মে এলোমেলো করে নেওয়া। নিয়মটা এমন হতে হবে যাতে দুইটা আলাদা সংখ্যা কখনো একই ফল না দেয়। তাহলে uniqueness ও থাকে, আবার পাশাপাশি দুইটা link এর code ও একদম আলাদা দেখায়।

০৫ Hash দিয়ে বানালে hash collision এর কী হবে, আর key generation service কেন?

দ্বিতীয় উপায়: URL এর hash

Hash function যেকোনো লম্বা লেখা থেকে একটা নির্দিষ্ট মাপের “আঙুলের ছাপ” বানায়। একই লেখা দিলে সবসময় একই ছাপ আসে। MD5 এমন একটা hash function, যেটা সবসময় ১২৮ bit এর ফল দেয়। অর্কের Google Form link এর MD5 নিয়ে base62 তে লিখলে ২২ অক্ষর হয়। আমরা শুধু প্রথম ৭টা অক্ষর রাখি:

long_url = "https://docs.google.com/forms/d/e/1FAIpQLSd-hackathon.../viewform"   (80 অক্ষর)

MD5(long_url)        = 5adb277d61f7bf90c664c4722f3962bb   (128 bit, 32টা hex অক্ষর)
সংখ্যাটা base62 তে    = 2LrsIyw...                          (মোট 22 অক্ষর)
প্রথম 7 অক্ষর         = 2LrsIyw                             ← short code

5 বছর পরে collision এর সম্ভাবনা
  database এ আগে থেকেই আছে   = 18,250,000,000 code
  মোট জায়গা (62^7)           = 3,521,614,606,208
  নতুন code আগেরটার সাথে মিলে যাওয়ার সম্ভাবনা
                              ≈ 18.25 billion / 3.52 trillion
                              ≈ 0.52%
  মানে প্রায় প্রতি 190টা নতুন link এ 1টা collision

সমস্যাটা ঐ কেটে ফেলার মধ্যেই। ১২৮ bit এর পুরো hash এ দুইটা আলাদা URL এর ফল মিলে যাওয়া প্রায় অসম্ভব। কিন্তু ৭ অক্ষরে কাটার পর জায়গা অনেক ছোট হয়ে যায়। তখন দুইটা আলাদা URL একই ৭ অক্ষরের code পেতেই পারে। একে বলে hash collision। উপরের হিসাবে ৫ বছর পরে প্রায় প্রতি ১৯০টা নতুন link এ একটা collision হবে। এটা উপেক্ষা করার মতো সংখ্যা নয়।

তাই hash পদ্ধতিতে প্রতিবার database এ খোঁজ নিতে হয়:

Collision হলে URL এর শেষে একটা ছোট বাড়তি লেখা জুড়ে দেওয়া হয়, যাকে বলে salt। Salt বদলালে hash ও পুরোপুরি বদলে যায়, তাই নতুন code পাওয়া যায়। এই পদ্ধতির আরো দুটো downside আছে। প্রতিটা নতুন link এর জন্য একটা বাড়তি database read লাগে। আর একই URL দুইজন আলাদা মানুষ দিলে দুজনেই একই code পায়। তখন দুজনের জন্য আলাদা expiry বা আলাদা click এর হিসাব রাখা যায় না।

তৃতীয় উপায়: key আগে থেকেই বানিয়ে রাখা

বাসের টিকিট কাউন্টারের কথা ভাবুন। কাউন্টারের লোকটা প্রতিটা যাত্রীর জন্য ছাপাখানায় দৌড়ায় না। তার হাতে আগে থেকে ছাপানো টিকিটের একটা বান্ডিল থাকে। যাত্রী এলে সে একটা টিকিট ছিঁড়ে দেয়। বান্ডিল শেষ হলে অফিস থেকে আরেকটা বান্ডিল নিয়ে আসে।

Key generation service (KGS) ঠিক এই কাজটাই করে। একটা offline job আগে থেকেই কোটি কোটি random ৭ অক্ষরের key বানিয়ে একটা table এ রেখে দেয়। App server গুলো KGS এর কাছ থেকে একবারে ১,০০০টা key এর একটা বান্ডিল নিয়ে নিজের memory তে রাখে। নতুন link এলে শুধু একটা key তুলে দেয়:

KGS এর চারটা খুঁটিনাটি মনে রাখা দরকার:

• একই key দুইজন পায় না: Key তোলা আর “used” হিসেবে mark করা একই transaction এ হয় (transaction এর কথা সেশন ০৫ এ দেখেছেন)। তাই দুইটা server একসাথে চাইলেও আলাদা বান্ডিল পায়।
• Server crash করলে কিছু key নষ্ট হয়: তার memory তে থাকা ১,০০০টা key আর কেউ ব্যবহার করে না। কিন্তু সাড়ে তিন লাখ কোটির মধ্যে কয়েক হাজার key কিছুই না।
• KGS নিজেও একটা SPOF: তাই একটা standby KGS রাখা হয়, যেটা প্রথমটা down হলে দায়িত্ব নেয় (failover এর কথা সেশন ০৩ এ দেখেছেন)।
• Storage সামান্য: একটা key ৭ byte। একশো কোটি key রাখতে লাগে মাত্র ৭ GB।

তিনটা পদ্ধতি পাশাপাশি রাখলে:

০৬ 301 redirect নাকি 302 redirect? Click analytics কোথায় জমা হবে?

Hackathon এর registration চলছে। অর্ক প্রতিদিন সন্ধ্যায় একবার দেখে, poster থেকে কতজন এলো। এই সংখ্যাটা পাওয়া যাবে কিনা, তা নির্ভর করে একটা ছোট্ট সিদ্ধান্তের উপর: server কোন redirect code পাঠাবে।

HTTP তে 3xx দিয়ে শুরু হওয়া status code গুলো browser কে বলে, “যা খুঁজছেন, সেটা অন্য ঠিকানায় আছে।” নতুন ঠিকানাটা থাকে response এর Location header এ। এদের মধ্যে দুটো আমাদের কাজের:

• 301 redirect (Moved Permanently): “ঠিকানাটা চিরদিনের জন্য বদলে গেছে।” Browser এটা মনে রেখে দেয়। পরের বার একই ছোট link খুললে সে আমাদের server কে আর জিজ্ঞেস করে না, সোজা আসল ঠিকানায় চলে যায়।
• 302 redirect (Found): “এই মুহূর্তে জিনিসটা ওখানে আছে।” Browser এটা মনে রাখে না। প্রতিবার আগে আমাদের server এ এসে জেনে নেয়।

অর্কের দুটো জিনিসই দরকার। Click গুনতে হবে। আর registration শেষ হলে link টাকে “registration বন্ধ” page এ ঘুরিয়ে দিতে হবে। দুটোই শুধু 302 দিয়ে সম্ভব। তাই অর্ক 302 বেছে নিলো, যদিও এতে server এ চাপ বেশি পড়ে।

Click এর হিসাব কোথায় লিখবো

প্রথম ভাবনা হতে পারে: প্রতিটা click এ database এর একটা counter এক বাড়িয়ে দিই। কিন্তু peak এ সেকেন্ডে ৩৫,০০০টা click আসে। মানে সেকেন্ডে ৩৫,০০০টা write, যেখানে link বানানোর write মাত্র ৩৫০টা! তার উপর প্রতিটা redirect কে ঐ write শেষ হওয়ার জন্য অপেক্ষা করতে হতো।

এর বদলে click এর খবরটা একটা queue তে রেখে দেওয়া হয় (queue এর কথা সেশন ০৮ এ দেখেছেন)। Redirect সাথে সাথে ফেরত যায়:

Worker queue থেকে event গুলো তুলে এক মিনিটের সব click একসাথে যোগ করে। তারপর hack26 এর জন্য একটাই write করে: “এই মিনিটে আরো ৪২টা click।” ফলে ৩৫,০০০টা ছোট write কমে গিয়ে প্রতি মিনিটে কয়েক হাজার write এ নেমে আসে।

০৭ Read-heavy traffic এ cache, replica আর shard কোথায় বসবে?

Cache: সবচেয়ে বড় লাভ

সেকেন্ডে ৩৫,০০০টা read এর প্রতিটা database এ পাঠালে database হাঁপিয়ে উঠবে। কিন্তু এখানে একটা সুখবর আছে। সব link সমান জনপ্রিয় নয়। আজ সন্ধ্যায় hack26 এ হাজার click পড়ছে, অথচ গত বছরের একটা পিকনিকের link এ কেউ click করছে না। অল্প কিছু link ই বেশিরভাগ click পায়।

তাই সবচেয়ে জনপ্রিয় link গুলো Redis এ রাখা হয়। সেশন ০৪ এর cache-aside নিয়মটাই এখানে খাটে:

URL shortener এ cache রাখা অন্য system এর চেয়ে সহজ। একটা code এর URL প্রায় কখনো বদলায় না। তাই cache এর data পুরোনো হয়ে যাওয়ার (cache invalidation) ঝামেলা প্রায় নেই। শুধু link ডিলিট হলে বা মেয়াদ শেষ হলে Redis থেকে key টা মুছে দিলেই চলে। Memory ভরে গেলে LRU নিয়মে সবচেয়ে কম ব্যবহার হওয়া link গুলো বাদ পড়ে। Estimation বলছে, hot link গুলো রাখতে মাত্র ৫ GB লাগে।

Replica: database এর read ভাগ করা

Cache miss গুলো যায় database এর read replica তে (replica এর কথা সেশন ০৩ এ দেখেছেন)। Write যায় primary তে, read ছড়িয়ে পড়ে কয়েকটা replica তে।

একটা ছোট ফাঁদ আছে। অর্ক link বানিয়েই সাথে সাথে WhatsApp group এ পাঠালো। কেউ এক সেকেন্ডের মধ্যে click করলো। Replica তে তখনো row টা পৌঁছায়নি (replication lag)। ফলে সে পেলো “link খুঁজে পাওয়া যায়নি”! এর সহজ সমাধান হলো, নতুন link বানানোর সময়েই সেটা Redis এ লিখে দেওয়া। তাহলে প্রথম click টা replica তে যাওয়ার আগেই cache এ উত্তর পায়।

Shard: ৯ TB ভাগ করে রাখা

৫ বছরে ৯ TB data একটা machine এ রাখা কষ্টকর। তাই data কয়েকটা shard এ ভাগ করা হয় (সেশন ০৫)। Shard key হিসেবে short_code সবচেয়ে ভালো, কারণ প্রতিটা redirect এর সাথে code টা থাকেই। hash(short_code) দেখে বোঝা যায় row টা কোন shard এ আছে। ফলে কোনো query কে সব shard ঘুরে আসতে হয় না।

Viral link: একটা hot key

ধরুন কোনো জনপ্রিয় গায়ক তার নতুন গানের link cc.lnk/gaan share করলেন। এক মিনিটে দশ লাখ click! সব click একই key তে, তাই একটা Redis node এর উপরেই সব চাপ পড়ে। এটাই সেশন ০৫ এর hot key সমস্যা। সমাধান হলো প্রতিটা redirect server এর নিজের memory তে কয়েক সেকেন্ডের জন্য একটা ছোট cache রাখা। তাহলে বেশিরভাগ click Redis পর্যন্ত যায়ই না। চাইলে CDN এর edge server ও এমন redirect এর উত্তর অল্প সময়ের জন্য রেখে দিতে পারে (CDN এর কথা সেশন ০৬ এ দেখেছেন)।

০৮ Expiry, custom alias আর abuse কীভাবে সামলাবো?

Expiry: মেয়াদ শেষ হলে কী হবে

Hackathon এর registration ৩১ ডিসেম্বর রাতে শেষ। তারপর কেউ poster দেখে link খুললে কী দেখবে? অর্ক চায়, সে যেন একটা ভদ্র বার্তা দেখে: “Registration শেষ, পরের বার দেখা হবে।”

মেয়াদ শেষ হওয়া row গুলো দুই ভাবে সামলানো হয়। প্রথমত, প্রতিটা click এর সময় expires_at দেখে নেওয়া হয়। একে বলে lazy expiry, কারণ মেয়াদ যাচাই হয় কেবল তখনই, যখন কেউ link টা চায়। দ্বিতীয়ত, প্রতি রাতে একটা cleanup job মেয়াদ শেষ হওয়া row গুলো মুছে দেয় (cron job এর কথা সেশন ০৯ এ দেখেছেন):

-- ১) প্রতিটা click এর সময় (lazy check)
SELECT long_url, expires_at FROM urls WHERE short_code = 'hack26';
-- expires_at < now() হলে: redirect নয়, "410 Gone" আর একটা সুন্দর page

-- ২) প্রতি রাত ৩টায় cleanup job (cron, সেশন ০৯)
DELETE FROM urls
WHERE  expires_at < now()
LIMIT  10000;
-- একবারে ১০,০০০ row; কিছু না পাওয়া পর্যন্ত বারবার চলে,
-- যাতে বড় একটা DELETE database কে অনেকক্ষণ আটকে না রাখে

মেয়াদ শেষ হলে 410 Gone ফেরত দেওয়া হয়। এর মানে “জিনিসটা ছিলো, কিন্তু এখন আর নেই।” 404 এর চেয়ে এটা বেশি সৎ উত্তর।

মেয়াদ শেষ হওয়া code কি আবার অন্য কাউকে দেওয়া উচিত? না, অন্তত তাড়াতাড়ি নয়। অর্কের poster হয়তো আরো ছয় মাস দেয়ালে থাকবে। ততদিনে hack26 অন্য কারো link হয়ে গেলে student রা অচেনা কোনো page এ পৌঁছাবে। Code এর জায়গা তো সাড়ে তিন লাখ কোটি, তাই পুরোনো code ফেরত নেওয়ার কোনো দরকারই নেই।

Custom alias: নিজের পছন্দের নাম

cc.lnk/hack26 মনে রাখা cc.lnk/1005ban এর চেয়ে অনেক সহজ। এই নিজের দেওয়া নামকে বলে custom alias। তবে কয়েকটা নিয়ম লাগে। নাম ৪ থেকে ১৬ অক্ষরের হবে, শুধু base62 এর অক্ষর আর - চলবে। api, admin, login এর মতো কিছু শব্দ আগে থেকেই সংরক্ষিত থাকবে, কারণ ওগুলো আমাদের নিজের path।

আসল বিপদটা লুকিয়ে আছে সময়ের মধ্যে। ধরুন একই মুহূর্তে দুইটা club hack26 নামটা চাইলো:

দুইটা server যদি আগে খুঁজে দেখে “নামটা খালি কিনা”, দুজনেই খালি দেখবে। তারপর দুজনেই INSERT করতে যাবে। তাই “খুঁজে দেখি, তারপর লিখি” নিয়মে কাজ হয় না। সিদ্ধান্তটা দিতে হয় database এর primary key কে। যার INSERT আগে পৌঁছায়, সে নামটা পায়। অন্যজন 409 Conflict পায়, মানে “এই নামটা ইতিমধ্যে নেওয়া হয়ে গেছে।”

আরেকটা সূক্ষ্ম জায়গা আছে। KGS এর random key আর কারো custom alias একই হয়ে যেতে পারে। দুটো একই table এ থাকে, আর short_code primary key। তাই এমন হলে KGS এর key দিয়ে INSERT fail করে, আর server পরের key টা নিয়ে আবার চেষ্টা করে। কোনো link হারায় না।

Abuse: ছোট link এর পেছনে খারাপ মানুষ

ছোট link এর একটা অন্ধকার দিক আছে। Link দেখে বোঝা যায় না সেটা কোথায় নিয়ে যাবে। কেউ একদিন cc.lnk/bonus500 বানিয়ে ছড়িয়ে দিলো, যার পেছনে একটা নকল মোবাইল ব্যাংকিং page। মানুষ সেখানে PIN দিয়ে টাকা হারালো। এমন প্রতারণাকে বলে phishing। তিনটা সহজ ব্যবস্থা অনেকটা আটকায়:

• Link বানানোর সময় যাচাই: পরিচিত খারাপ website এর একটা তালিকার (blocklist) সাথে URL টা মিলিয়ে দেখা হয়।
• Rate limit: একজন user বা একটা IP ঘণ্টায় কতগুলো link বানাতে পারবে, তার একটা সীমা থাকে (সেশন ২১)। তাতে একজন লাখ লাখ spam link বানাতে পারে না।
• Report আর বন্ধ করা: যে কেউ একটা link কে report করতে পারে। যাচাই করে link টা বন্ধ করে দেওয়া হয়।

০৯ Pastebin এ কী বদলায় (object storage), আর পুরো design এর bottleneck কোথায়?

Pastebin: link এর বদলে পুরো লেখা

Hackathon এর দিন অর্ক আরেকটা জিনিস চাইলো। Contest এর problem statement আর sample input গুলো একটা ছোট link এ সবাইকে দেওয়া। এমন service কে বলে Pastebin: আপনি একটা লেখা paste করেন, একটা ছোট link পান, আর link খুললে সেই লেখাটাই দেখা যায়।

এখানে বেশিরভাগ design একই থাকে। Short code, KGS, expiry, cache সব আগের মতোই কাজ করে। পার্থক্য একটাই: আগে একটা row তে ২০০ byte এর URL থাকতো, এখন থাকবে ১০ KB থেকে ১০ MB এর লেখা। হিসাবটা দেখুন:

ধরে নিই
  নতুন paste প্রতিদিন    : 10 লাখ = 1,000,000
  গড় paste এর size      : 10 KB   (সর্বোচ্চ 10 MB)
  read : write           : 10 : 1

Storage
  1,000,000 × 10 KB      = 10 GB / দিন
  10 GB × 365            ≈ 3.6 TB / বছর
  → URL shortener এর 10 ভাগের 1 ভাগ item, অথচ storage প্রায় 2 গুণ

Read
  1,000,000 × 10 / 86,400   ≈ 116 read/sec
  116 × 10 KB               ≈ 1.2 MB/sec   (একটা viral paste এ এটা অনেক গুণ বাড়ে)

এত বড় লেখা database এর row তে রাখা ভালো নয়। Database এর row ছোট রাখার জন্যই বানানো। বড় row থাকলে backup ধীর হয়, replica তে copy হতেও বেশি সময় লাগে। তাই আসল লেখাটা রাখা হয় object storage এ। এটা এমন একটা storage, যেখানে একটা নাম (key) দিয়ে পুরো একটা file রাখা আর তোলা যায়। Amazon S3 এর মতো। পরের সেশনগুলোতে ছবি আর video রাখতেও আমরা এই object storage ই ব্যবহার করবো। Database এ থাকে শুধু ছোট তথ্য: paste এর id, file এর নাম, size আর মেয়াদ। এই ছোট তথ্যকে বলে metadata।

পুরো ছবি

সব টুকরো জোড়া লাগালে অর্কের system দাঁড়ায় এমন:

১০ মগজে প্রেশার দিন

আগে নিজে ভাবুন। তারপর উত্তর খুলে দেখুন: বেশিরভাগ মানুষ কীভাবে ভাবে, সেই চিন্তায় কী বাদ পড়ে, আর আসল কথাটা কোথায়।

১১ যে টার্মগুলো শিখলাম

১২ শর্ট সামারি

১৩ মনে রাখুন

• Box আঁকার আগে requirement আর estimation করুন। কোথায় চাপ পড়বে, সেটা সংখ্যাই আগে বলে দেয়।
• Code এর দৈর্ঘ্য হিসাব করে ঠিক করুন। ৫ বছরের মোট link এর সংখ্যা ৬২ এর ঘাতের সাথে মিলিয়ে দেখলেই ৭ অক্ষরের উত্তর বেরিয়ে আসে।
• Hash কেটে ছোট করলে collision ফিরে আসে। তাই hash পদ্ধতিতে প্রতিবার database এ খুঁজতে হয়, নয়তো KGS ব্যবহার করুন।
• Analytics লাগলে 302, না লাগলে 301। 301 খরচ কমায়, কিন্তু click আর destination বদলানোর ক্ষমতা কেড়ে নেয়।
• Redirect এর পথে শুধু খোঁজার কাজটুকু রাখুন। গোনা আর বাকি সব হিসাব queue তে পাঠিয়ে পরে করুন।
• Uniqueness এর সিদ্ধান্ত database এর unique constraint কে দিন। “আগে খুঁজি, তারপর লিখি” নিয়ম একসাথে আসা দুইটা request এর সামনে টেকে না।
• বড় content database এ নয়, object storage এ রাখুন। Database এ থাকুক শুধু metadata।