Case study: URL shortener — ID তৈরি, redirect আর analytics

১ · সমস্যা আর পরিধি — “ছোটলিংক” কী করবে, কী করবে না

মডিউল ১ থেকে ৮-এ আপনি আলাদা আলাদা যন্ত্রাংশ চিনেছেন: load balancer, cache, sharding, queue, consensus, rate limiter. মডিউল ৯-এ সেই যন্ত্রাংশ দিয়ে পুরো গাড়ি বানানো হবে। প্রতিটি case study একই কাঠামো মানবে, যা পর্ব ৬-এ শিখেছেন: পরিধি, হিসাব, API, data model, high-level design, deep dive, ভাঙন আর wrap-up. কোনো ধারণা নতুন করে শেখানো হবে না; প্রতিটির এক লাইনের প্রয়োগ আর মূল পর্বের link থাকবে।

মডিউল ৯ — আটটি case study, একই আট ধাপ

URL shortener দিয়ে শুরু করার কারণ আছে। এর মূল কাজ এক লাইনে বলা যায়: লম্বা একটি ঠিকানার বদলে ছোট একটি code দেওয়া, আর কেউ ছোট code-এ এলে তাঁকে আসল ঠিকানায় পাঠানো (redirect). সরল বলেই এখানে প্রতিটি trade-off পরিষ্কার দেখা যায়। আমাদের কাল্পনিক সেবার নাম “ছোটলিংক”, domain s.example.

Functional requirement — কী করবে

• ছোট link তৈরি: লম্বা URL দিলে ছোট code. ইচ্ছা হলে নিজের পছন্দের নাম (custom alias), যেমন s.example/eid-offer, আর মেয়াদ (expiry).
• Redirect: s.example/4c92-তে গেলে আসল ঠিকানায় পাঠানো; মেয়াদ শেষ, মুছে ফেলা বা নিষিদ্ধ link-এ পরিষ্কার উত্তর।
• Click analytics: link-এর মালিক দেখবেন মিনিট বা দিন ধরে click-এর সংখ্যা, আনুমানিক কতজন আলাদা মানুষ, কোন দেশ বা ডিভাইস থেকে।
• ব্যবস্থাপনা: নিজের link-এর তালিকা, মুছে ফেলা, অপব্যবহারের রিপোর্ট।

Non-functional requirement — কতটা ভালোভাবে

• Redirect দ্রুত: ধরা যাক সার্ভারের ভেতরে p99 কয়েক ms থেকে কয়েক দশ ms; মানুষ link চাপার পর অপেক্ষা টের পাবেন না (পর্ব ৪)।
• Redirect সবসময় চালু: SMS, পোস্টার বা QR code-এ ছাপা link বছর পরেও কাজ করবে; ধরা যাক availability-র লক্ষ্য ৯৯.৯৯% (পর্ব ৫)।
• ভুল ঠিকানায় কখনো নয়: একটি code কখনো দুটি URL-এ যাবে না। এটি correctness-এর শর্ত, গতির চেয়েও জরুরি।
• Analytics একটু দেরিতে চলবে: কয়েক মিনিট দেরি আর সামান্য আনুমানিক ভুল গ্রহণযোগ্য।

পরিধির বাইরে

Link-এর ভেতরের পাতা দেখানো বা host করা, পুরো marketing dashboard, অর্থ লেনদেন, আর link-এর destination পরে বদলানোর সুবিধা (অনুশীলন ২-এ এটি যোগ করবেন)।

ইন্টারভিউয়ার যে প্রশ্নগুলো শুনতে চান

২ · হিসাব — চাপ পড়ার পথে, লেখায় নয়

পর্ব ৩-এ এই সেবারই সংখ্যা ধাপে ধাপে বের করেছিলেন। এখানে একই অনুমান রাখা হলো, শুধু নকশার জন্য তিনটি প্রশ্ন যোগ হলো: cache কত বড়, code কত অক্ষরের, আর কোন পথে কত ভার। সব input কাল্পনিক, “ধরা যাক”। নিচের estimator-এ যেকোনো একটি মান বদলে আবার চালান — কোন ফল কতটা নড়ে, সেটাই আসল শিক্ষা।

// URL shortener estimator. Every input is an assumption (ধরা যাক) - change one and re-run.
const A = {
  newPerDay: 1e7,      // new short links per day
  readsPerWrite: 100,  // read:write = 100:1
  peakFactor: 3,       // busiest hour vs the daily average
  recordBytes: 500,    // code + long URL + owner + times + flags + index share
  redirectBytes: 500,  // one 302 response with headers
  years: 5, copies: 3, // keep 5 years, 3 replicas
  hotDays: 30,         // most clicks go to links created in the last 30 days
  hotShare: 0.2,       // cache the top 20% of those links
  headroom: 100,       // random codes: keep the code space >= 100x the links
};
const wAvg = A.newPerDay / 86400, rAvg = wAvg * A.readsPerWrite;
const n0 = x => Math.round(x).toLocaleString("en-US");
console.log("write QPS  avg " + n0(wAvg) + "   peak " + n0(wAvg * A.peakFactor));
console.log("read  QPS  avg " + n0(rAvg) + "   peak " + n0(rAvg * A.peakFactor));
const egress = rAvg * A.peakFactor * A.redirectBytes * 8 / 1e6;
console.log("peak redirect egress " + egress.toFixed(0) + " Mbit/s");
const links = A.newPerDay * 365 * A.years, tb = links * A.recordBytes / 1e12;
console.log("links after " + A.years + " years " + links.toExponential(3));
console.log("storage " + tb.toFixed(2) + " TB raw, " + (tb * A.copies).toFixed(2) + " TB with " + A.copies + " copies");
const hot = A.newPerDay * A.hotDays * A.hotShare;
console.log("cache: top " + A.hotShare * 100 + "% of " + A.hotDays + " days of links = " +
  hot.toExponential(1) + " links = " + (hot * A.recordBytes / 1e9).toFixed(0) + " GB");
for (const [how, need] of [["counter", links], ["random + headroom", links * A.headroom]]) {
  let L = 1; while (62 ** L < need) L++;
  console.log(how.padEnd(18) + "needs " + L + " chars: 62^" + L + " = " + (62 ** L).toExponential(3) +
    ", 5-year fill " + (100 * links / 62 ** L).toFixed(2) + "%");
}
console.log("62^6 = " + n0(62 ** 6) + ", 62^7 = " + n0(62 ** 7));

write QPS  avg 116   peak 347
read  QPS  avg 11,574   peak 34,722
peak redirect egress 139 Mbit/s
links after 5 years 1.825e+10
storage 9.13 TB raw, 27.38 TB with 3 copies
cache: top 20% of 30 days of links = 6.0e+7 links = 30 GB
counter           needs 6 chars: 62^6 = 5.680e+10, 5-year fill 32.13%
random + headroom needs 7 chars: 62^7 = 3.522e+12, 5-year fill 0.52%
62^6 = 56,800,235,584, 62^7 = 3,521,614,606,208

৩ · API — তিনটি endpoint আর একটি redirect

API-র নকশা পর্ব ৮-এর নিয়ম মানে: resource-এর নাম বিশেষ্য, ঠিক status code, আর POST-এ idempotency key. মোবাইল network-এ উত্তর হারিয়ে গেলে app একই অনুরোধ আবার পাঠায়; key না থাকলে একই link-এর দুটি code তৈরি হতো।

POST /api/v1/links HTTP/1.1
Host: api.s.example
Authorization: Bearer <token>
Idempotency-Key: k-77
Content-Type: application/json

{ "long_url": "https://shop.example/p/1", "alias": null, "expires_in_days": 30 }

HTTP/1.1 201 Created
Content-Type: application/json

{ "code": "4c92", "short_url": "https://s.example/4c92",
  "expires_at": "2026-11-27T00:00:00Z" }

GET /4c92 HTTP/1.1
Host: s.example

HTTP/1.1 302 Found
Location: https://shop.example/p/1
Cache-Control: private, max-age=0

# alias already taken          -> 409 Conflict
# expired or deleted link      -> 404 Not Found (or 410 Gone)
# blocked as malicious         -> a warning page, never a redirect

GET /api/v1/links/4c92/stats?from=2026-10-28&granularity=minute
-> 200 { "clicks": [...], "unique_visitors_approx": 13 }

• Alias-এর নিয়ম: অক্ষরের তালিকা আর দৈর্ঘ্যের সীমা, আর api, login, admin-এর মতো সংরক্ষিত শব্দ বাদ। নইলে কেউ নিজের link-কে সেবার নিজের পাতার মতো দেখাতে পারেন।
• বড়-ছোট হাতের অক্ষর: base62 case-sensitive, তাই 4c92 আর 4C92 আলাদা। মানুষ হাতে টাইপ করবেন বা মুখে বলবেন এমন code-এ 0/O আর l/1/I-এর মতো বিভ্রান্তিকর অক্ষর বাদ দেওয়া base58-এর মতো বর্ণমালা বিবেচনা করা যায় — দাম, প্রতি অক্ষরে একটু কম জায়গা।

৪ · Data model — একটি key, একটি খোঁজ

প্রথমে খোঁজার ধরন, তারপর টেবিল (পর্ব ৬-এর ধাপ ৪)। প্রতি সেকেন্ডে হাজারবার যে খোঁজ চলবে তা একটিই: “code থেকে URL”. বাকিগুলো বিরল: মালিকের নিজের link-এর তালিকা, আর পরিসংখ্যান।

• Store বাছাই: খোঁজ একটিই, join নেই, transaction নেই — key-value store বা wide-column store স্বাভাবিক পছন্দ (পর্ব ২০)। Shard-এ ভাগ করা SQL database-ও ঠিকঠাক চলবে; সিদ্ধান্তের কারণ খোঁজার ধরন, ফ্যাশন নয়।
• Partition key: code, hash partitioning-এ (পর্ব ২৩)। Counter-এর code পরপর আসে, তাই range partitioning করলে সব নতুন লেখা একটি shard-এ জমত; hash সেটি ছড়িয়ে দেয়।
• Owner index: partition key code হলে “owner 7-এর সব link” প্রশ্ন সব shard ঘুরবে। তাই আলাদা global index, যা অল্প দেরিতে মেলে (পর্ব ২১)।
• Alias-এর অনন্যতা: “আগে দেখি আছে কি না, তারপর লিখি” দুই ধাপে করলে দুজন একসাথে একই alias পেতে পারেন। সমাধান একটি conditional write: “না থাকলে তবেই লেখা”, যা store নিজেই atomic-ভাবে করে।

নিচের SQLite demo একটি মেশিনে এই টেবিল আর দুটি নিয়ম দেখায়: alias-এর সংঘাত, আর redirect-এর সময় মেয়াদ ও status যাচাই। SQLite distributed নয়; এটি শুধু নিয়মগুলো দেখায়, shard বা replica নয়।

-- Single-node SQLite demo of the link table (production shards it by code).
CREATE TABLE links (
  code       TEXT PRIMARY KEY,       -- short code or custom alias
  long_url   TEXT NOT NULL,
  owner_id   INTEGER NOT NULL,
  created_at TEXT NOT NULL,
  expires_at TEXT,                   -- NULL = never expires
  status     TEXT NOT NULL DEFAULT 'active'   -- active | blocked | deleted
) WITHOUT ROWID;

INSERT INTO links VALUES ('4c92', 'https://shop.example/p/1', 7, '2026-10-01', NULL, 'active');
INSERT INTO links VALUES ('eid-offer', 'https://shop.example/eid', 7, '2026-10-01', '2026-10-20', 'active');
INSERT INTO links VALUES ('x9Lp2', 'https://bad.example/win', 9, '2026-10-02', NULL, 'blocked');

-- user 9 asks for the same alias: insert only if the code is free
INSERT INTO links VALUES ('eid-offer', 'https://other.example/', 9, '2026-10-28', NULL, 'active')
  ON CONFLICT(code) DO NOTHING;
SELECT changes() AS rows_inserted;

-- redirect decision at "now" = 2026-10-28
SELECT code,
  CASE WHEN status <> 'active' THEN 'warning page'
       WHEN expires_at IS NOT NULL AND expires_at <= '2026-10-28' THEN '404 expired'
       ELSE '302 ' || long_url END AS answer
FROM links ORDER BY code;

৫ · High-level design — দুটি পথ, একটি ছবি

পুরো নকশা তিনটি আলাদা পথে ভাগ হয়: নীল পথে redirect (পড়া), সবুজ পথে নতুন link (লেখা), আর কমলা ড্যাশ পথে click-এর খবর। তিনটিকে আলাদা রাখাই মূল সিদ্ধান্ত — একটির ভিড় বা বিভ্রাট যেন অন্যটিকে না ডোবায়।

• Redirect service stateless: কোনো সার্ভার নিজের কাছে কিছু মনে রাখে না, তাই ভিড়ে শুধু সংখ্যা বাড়ান (পর্ব ১৩), সামনে load balancer ভাগ করে দেয় (পর্ব ১৪)।
• সত্যের উৎস একটিই: KV store. Cache আর edge শুধু কপি রাখে; নিষিদ্ধ করার খবর সেখানে দেরিতে পৌঁছায় (অংশ ৭)।

লেখার পথ — একটি নতুন link

নিচে “পরে” চাপুন। একটি নতুন link-এর অনুরোধ পাঁচটি স্তর পেরিয়ে কীভাবে code পায়, প্রতিটি ধাপে কী যাচাই হয়, দেখুন।

POST /api/v1/links
Idempotency-Key: k-77
{ "long_url": "https://shop.example/p/1",
  "expires_in_days": 30 }

token      user 7        OK
rate limit 18/20 tokens  OK   (পর্ব ৪৯)
idem k-77  আগে দেখা নেই  নতুন কাজ

normalize  https://shop.example/p/1
blocklist  নেই                 OK
scheme     https only          OK
alias      চাওয়া হয়নি -> ID লাগবে

block      [1,000,000 .. 1,000,999]
next id    1,000,000
base62     4c92        (অংশ ৬-এর stepper)

PUT links/4c92 IF NOT EXISTS   OK
{ long_url, owner 7, expires 2026-11-27, active }
replica-তে কপি   (পর্ব ২২)

201 Created  { "short_url": "https://s.example/4c92" }
idem k-77 -> 4c92   (২৪ ঘণ্টা রাখা)
event link_created  -> stream, outbox দিয়ে

পড়ার পথ — প্রথমবার miss, তারপর hit

এবার একই link দুজন মানুষ দুই সেকেন্ডের ব্যবধানে খুলছেন। Cache কীভাবে দ্বিতীয়জনকে KV store-এ যাওয়া থেকে বাঁচায়, সারি ধরে দেখুন (latency-গুলো মোটামুটি মাত্রা, মাপা নয়)।

৬ · Deep dive ১ — ID তৈরি: ছোট, অনন্য, আর সহজে অনুমেয় নয়

প্রথম কঠিন প্রশ্ন: কোটি কোটি link-এর প্রতিটির জন্য এমন একটি ছোট code, যা আর কারও নয়। কেন্দ্রীয় counter ছাড়া unique ID-র কৌশলগুলো পর্ব ২৩ আর সময়ক্রমের ID পর্ব ৩৯-এ দেখেছেন। এখানে শুধু প্রশ্ন: URL shortener-এর শর্তে কোনটি টেকে?

দৈর্ঘ্যের অঙ্ক আর birthday-র ফাঁদ

L অক্ষরের base62 code-এ মোট সম্ভাবনা M = ৬২^L: ৬ অক্ষরে ৫৬,৮০,০২,৩৫,৫৮৪ আর ৭ অক্ষরে ৩৫,২১,৬১,৪৬,০৬,২০৮। Counter হলে M পর্যন্ত কোনো collision নেই। কিন্তু code এলোমেলো হলে (hash বা random) জায়গা ফাঁকা থাকলেও collision আসে অনেক আগে — একে বলে birthday paradox: ২৩ জনের একটি দলেই দুজনের জন্মদিন একই হওয়ার সম্ভাবনা ৫০%-এর বেশি।

এবার নিজে মাপুন। নিচের কোড ১০ লাখ কাল্পনিক URL-কে একটি সরল hash দিয়ে ৫৩ bit সংখ্যা বানায়, তারপর ৫, ৬ বা ৭ অক্ষরে কেটে দেখে কতগুলো code আগেই নেওয়া। ৫ অক্ষরের ছোট জায়গাটি রাখা হয়েছে যাতে ফোনেও অল্প কাজে বড় সংখ্যায় সূত্র মেলানো যায়; ১ কোটির হিসাব শেষ লাইনে শুধু সূত্র থেকে। Hash-টি cyrb53 — দ্রুত, কিন্তু cryptographic নয়; বাস্তবে MD5 বা SHA-256-এর প্রথম কয়েক bit নিলেও হিসাব একই। চালাতে প্রায় এক সেকেন্ড লাগে।

// Hash-then-truncate vs a counter: how many short codes collide?
// cyrb53 = a simple, well-known 53-bit string hash (fast, NOT cryptographic).
function cyrb53(s) {
  let h1 = 0xdeadbeef, h2 = 0x41c6ce57;
  for (let i = 0; i < s.length; i++) { const c = s.charCodeAt(i);
    h1 = Math.imul(h1 ^ c, 2654435761); h2 = Math.imul(h2 ^ c, 1597334677); }
  h1 = Math.imul(h1 ^ (h1 >>> 16), 2246822507) ^ Math.imul(h2 ^ (h2 >>> 13), 3266489909);
  h2 = Math.imul(h2 ^ (h2 >>> 16), 2246822507) ^ Math.imul(h1 ^ (h1 >>> 13), 3266489909);
  return 4294967296 * (2097151 & h2) + (h1 >>> 0);
}
function repeats(codes) {             // codes already taken by an earlier link (bucket by low 20 bits)
  const B = 1 << 20, start = new Uint32Array(B + 1), out = new Float64Array(codes.length);
  for (const x of codes) start[x % B + 1]++;
  for (let b = 0; b < B; b++) start[b + 1] += start[b];
  const pos = start.slice(0, B);
  for (const x of codes) out[pos[x % B]++] = x;
  let r = 0;
  for (let b = 0; b < B; b++) for (let i = start[b] + 1; i < start[b + 1]; i++)
    for (let j = start[b]; j < i; j++) if (out[i] === out[j]) { r++; break; }
  return r;
}
const ABC = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
const base62 = n => { let s = ""; do { s = ABC[n % 62] + s; n = Math.floor(n / 62); } while (n > 0); return s; };
console.log("chars    links  space 62^L   collisions  birthday n^2/2M  P(>=1)");
const N = 1e6, h = new Float64Array(N);
for (let i = 0; i < N; i++) h[i] = cyrb53("https://shop.example/item/" + i);   // 1 million long URLs
for (const [L, n] of [[5, 1e5], [5, 1e6], [6, 1e6], [7, 1e6]]) {
  const M = 62 ** L, got = repeats(h.subarray(0, n).map(x => x % M)), exp = n * n / (2 * M);
  console.log(String(L).padStart(5), String(n / 1e6 + "M").padStart(8), M.toExponential(2).padStart(11),
    String(got).padStart(12), exp.toFixed(1).padStart(16), (1 - Math.exp(-exp)).toFixed(4).padStart(7));
}
console.log("counter + base62: 0 collisions; id 1,000,000 ->", base62(1e6), "; id 10,000,000 ->", base62(1e7),
  "; id 56,800,235,583 ->", base62(62 ** 6 - 1));
const est = (L, n) => (n * n / (2 * 62 ** L)).toFixed(1);
console.log("formula only, 10M links: 6 chars ~" + est(6, 1e7) + ", 7 chars ~" + est(7, 1e7) + " collisions");

chars    links  space 62^L   collisions  birthday n^2/2M  P(>=1)
    5     0.1M     9.16e+8            6              5.5  0.9957
    5       1M     9.16e+8          545            545.8  1.0000
    6       1M    5.68e+10            6              8.8  0.9998
    7       1M    3.52e+12            0              0.1  0.1324
counter + base62: 0 collisions; id 1,000,000 -> 4c92 ; id 10,000,000 -> FXsk ; id 56,800,235,583 -> ZZZZZZ
formula only, 10M links: 6 chars ~880.3, 7 chars ~14.2 collisions

Counter-এর block আর base62 — ধাপে ধাপে

প্রতিটি link-এর জন্য কেন্দ্রীয় counter-কে ডাকলে সেটিই single point of failure আর bottleneck. তাই প্রতিটি সার্ভার একবারে ১,০০০টি সংখ্যার একটি block নেয়। Counter থাকে একটি নির্ভরযোগ্য, consensus-ভিত্তিক store-এ (পর্ব ৪২), যেমন etcd বা ZooKeeper.

অনুমেয়তা — code গুনে গুনে link খুঁজে বের করা

Counter-এর code পরপর: 4c92-এর পরে 4c93. তাহলে যে কেউ code গুনে গুনে সব link-এর destination দেখে ফেলতে পারেন — একে বলে enumeration. বহু মানুষ ছোট link-কে “গোপন” ভেবে ব্যক্তিগত ফাইল বা ঠিকানা শেয়ার করেন, তাই এটি privacy-র ঝুঁকি। সুরক্ষার উপায়:

• Counter-কে এলোমেলো দেখানো: encode করার আগে একটি গোপন key-সহ এক-এক মিল (keyed permutation, যেমন ছোট একটি Feistel network) দিয়ে সংখ্যাটি ঘুরিয়ে দেওয়া। অনন্যতা থাকে, পরপর সংখ্যা আর পরপর code হয় না। এটি আড়াল, নিরাপত্তা নয়।
• 404-এর হারে সীমা: একই উৎস থেকে অনেক অস্তিত্বহীন code খোঁজা হলে rate limit (পর্ব ৪৯) আর alert.
• ছোট code কখনো গোপন চাবি নয়: ব্যক্তিগত শেয়ারে login-ভিত্তিক অনুমতি, অথবা অনেক লম্বা random token — ২২ অক্ষরের base62-এ প্রায় ১৩১ bit — যা গুনে শেষ করা কার্যত অসম্ভব (পর্ব ৫২)।

৭ · Deep dive ২ — Redirect-এর পথ: 301 না 302, cache আর edge

চারটি redirect code — কোনটি কখন

HTTP-তে redirect-এর চারটি প্রধান code, এখন RFC 9110-এ (২০২২) একসাথে বর্ণিত; 308 যোগ হয়েছিল RFC 7538-এ (২০১৫)। বিস্তারিত Computer Networks-এর HTTP পর্বে।

মূল trade-off একটি: 301 সার্ভারের ভার কমায়, কিন্তু নিয়ন্ত্রণ কেড়ে নেয়। Browser একবার 301 মনে রাখলে link নিষিদ্ধ করলেও সেই browser পুরোনো destination-এ যেতেই থাকবে, আর click গোনা হবে না। আমাদের requirement-এ click গোনা জরুরি, আর ক্ষতিকর link দ্রুত বন্ধ করা দরকার — তাই 302 আর Cache-Control: private, max-age=0.

KV store-এর সামনে cache

• Cache-aside, TTL-সহ: miss-এ store থেকে এনে ভরা (পর্ব ২৮)। Link মুছলে বা নিষিদ্ধ হলে key-টি সরাসরি মুছে ফেলা, আর TTL হলো বাড়তি নিরাপত্তা (পর্ব ২৯)।
• অস্তিত্বহীন code: কেউ লাখো ভুল code খুঁজলে প্রতিটিই store-এ যায় (cache penetration). ছোট TTL-এর negative caching, বা সব বৈধ code-এর একটি Bloom filter (পর্ব ৪৫) সামনে রাখা যায়।

কত বড় cache-এ কত লাভ? Link-এর জনপ্রিয়তা সাধারণত Zipf-এর মতো: অল্প link বিপুল click টানে, বাকিরা প্রায় কিছুই না। নিচের simulator ১০,০০০টি link-এর ওপর seeded Zipf-ধাঁচের ১০ লাখ redirect চালায় (গড়ে প্রতি link-এ ১০০টি পড়া, ঠিক ১০০:১-এর মতো), আর নানা আকারের LRU cache-এর hit rate মাপে।

// Seeded Zipf-like redirect traffic through an LRU cache: hit rate and database QPS.
function rng(seed) {                                    // mulberry32: seeded, repeatable
  return () => { seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
}
const LINKS = 10000, REQS = 1000000, S = 0.9, PEAK_READS = 34722;   // assumptions
const cdf = new Float64Array(LINKS); let sum = 0;
for (let k = 0; k < LINKS; k++) { sum += 1 / (k + 1) ** S; cdf[k] = sum; }  // rank k+1 popularity
function pick(u) {                                      // binary search in the CDF
  let lo = 0, hi = LINKS - 1, x = u * sum;
  while (lo < hi) { const mid = (lo + hi) >> 1; if (cdf[mid] < x) lo = mid + 1; else hi = mid; }
  return lo;
}
const rand = rng(54), trace = new Int32Array(REQS);
for (let i = 0; i < REQS; i++) trace[i] = pick(rand());
console.log("share of clicks on the top 1% / 20% of links: " +
  (100 * cdf[LINKS / 100 - 1] / sum).toFixed(1) + "% / " + (100 * cdf[LINKS / 5 - 1] / sum).toFixed(1) + "%");
console.log("cache size (links)   hit rate   DB reads/s at peak");
for (const pct of [1, 5, 10, 20, 50]) {
  const cap = LINKS * pct / 100, lru = new Map(); let hits = 0, counted = 0;
  for (let i = 0; i < REQS; i++) {
    const key = trace[i], warm = i >= REQS / 10;           // skip the first 10% (cold start)
    if (lru.has(key)) { lru.delete(key); if (warm) hits++; }
    else if (lru.size >= cap) lru.delete(lru.keys().next().value);  // evict least recent
    lru.set(key, 1); if (warm) counted++;
  }
  const hr = hits / counted;
  console.log((pct + "% = " + cap).padStart(16) + (100 * hr).toFixed(1).padStart(12) + "%" +
    Math.round(PEAK_READS * (1 - hr)).toLocaleString("en-US").padStart(18));
}

share of clicks on the top 1% / 20% of links: 41.0% / 76.2%
cache size (links)   hit rate   DB reads/s at peak
        1% = 100        26.2%            25,639
        5% = 500        45.6%            18,893
      10% = 1000        55.7%            15,376
      20% = 2000        67.2%            11,398
      50% = 5000        84.9%             5,255

Hot link — একটি পোস্ট ভাইরাল হলে

ঈদের আগে বাসের টিকিটের একটি লিংক লাখো মানুষের কাছে একসাথে গেল। তখন সব অনুরোধ একই key-এ, তাই একটি cache node-এ — একটি hot key. প্রতিকার পর্ব ৩০ থেকে: redirect service-এর নিজের memory-তে কয়েক সেকেন্ডের ছোট local cache, hot key-এর কয়েকটি কপি আলাদা node-এ, আর miss-এ একসাথে আসা অনুরোধগুলোকে একটিতে মেলানো (request coalescing), যাতে store-এ একটিই পড়া যায়।

Edge-এ redirect

আরও এগোলে redirect-এর উত্তর CDN-এর edge-এ রাখা যায় (পর্ব ১৭): edge 302-কে ধরা যাক ৬০ সেকেন্ডের s-maxage দিয়ে রাখে, অথবা edge function একটি replicate করা KV-র কপি থেকে নিজেই উত্তর দেয়। লাভ কম latency আর origin-এ কম ভার। দাম দুটি। এক, click গোনা তখন edge-এর log থেকে করতে হয়। দুই, link নিষিদ্ধ করলে edge-এর কপি TTL শেষ হওয়া বা purge পর্যন্ত চলতে থাকে — তাই TTL-ই “নিষিদ্ধ link সর্বোচ্চ কতক্ষণ চলবে” প্রশ্নের উত্তর।

৮ · Deep dive ৩ — Click analytics: redirect না থামিয়ে গোনা

মূল নিয়ম: redirect কখনো analytics-এর জন্য অপেক্ষা করবে না। প্রতিটি click-এ database-এ UPDATE clicks = clicks + 1 করলে ভাইরাল link-এর সারিটি একটি hot row হয়ে lock-এ আটকাবে, আর analytics-এর store ধীর হলে redirect-ও ধীর হবে। তাই click একটি event হয়ে আলাদা পথে যায়:

1. Event: {event_id, code, ts, visitor, country, device}. Visitor হলো IP আর browser-এর তথ্যের hash, প্রতিদিন বদলানো salt-সহ, যাতে কাঁচা IP জমা না থাকে (PII, পর্ব ৫২)।
2. Log-এ লেখা: redirect service ছোট batch-এ Kafka-ধাঁচের একটি log-এ পাঠায়; partition key code, যাতে একটি link-এর সব event একই partition-এ ক্রমে থাকে (পর্ব ৩৩)। Log বিকল হলে event হারানো মেনে নেওয়া যায়, redirect-এর ব্যর্থতা নয়।
3. Stream processing: consumer group event পড়ে, event time ধরে এক মিনিটের tumbling window-এ গোনে, আর watermark পেরোলে window বন্ধ করে (পর্ব ৩৬)।
4. Analytics store: মিনিট, ঘণ্টা আর দিনের সারাংশ একটি column store-এ (পর্ব ১৯), যেখানে “গত ৭ দিনে দেশ ধরে click” দ্রুত চলে।

At-least-once আর dedup

Log থেকে পড়ার সাধারণ নিশ্চয়তা at-least-once: consumer কাজ করে offset commit করার আগে crash করলে একই event আবার আসে (পর্ব ৩৪)। Counter-এ যোগ idempotent নয়, তাই event id দিয়ে dedup লাগে। নিচে একটি event-এর জীবন দেখুন।

Unique visitor — নির্ভুল না আনুমানিক

প্রতিটি link আর দিনের জন্য সব visitor-এর একটি set রাখলে জনপ্রিয় link-এ লাখো entry, প্রতিটি কয়েক দশ byte. HyperLogLog (পর্ব ৪৫) কয়েক KB-তে প্রায় ১%-এর মতো ভুলে একই উত্তর দেয় — Redis-এর বাস্তবায়নে documentation অনুযায়ী প্রতি key প্রায় ১২ KB আর standard error প্রায় ০.৮১%. আরও দুটি সুবিধা: মিনিটের HLL মিলিয়ে ঘণ্টা বা দিনের HLL বানানো যায় (union), আর একই visitor দুবার এলেও ফল বদলায় না। ছোট link-এ, যেখানে visitor কম, নির্ভুল set-ই সস্তা।

নিচের ছোট stream-এ দুটোই দেখুন: ৬০টি আসল click-এর ১৫%-এর মতো দুবার এসেছে, যেমন consumer retry-তে হয়। Dedup ছাড়া আর dedup-সহ মিনিটের সংখ্যা, আর প্রতি link-এর নির্ভুল unique visitor:

// Click analytics on a small seeded stream: clicks per link per minute, with and without dedup,
// plus exact unique visitors. The stream is at-least-once, so some events arrive twice.
function rng(seed) {                                    // mulberry32: seeded, repeatable
  return () => { seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
}
const rand = rng(2026), codes = ["eid24", "job7Q", "x9Lp2"], events = [];
for (let id = 1; id <= 60; id++) {
  const code = codes[Math.floor(rand() ** 2 * 3)];      // eid24 is the most popular
  const ev = { id, code, minute: "10:0" + Math.floor(rand() * 3), visitor: "v" + Math.floor(rand() * 15) };
  events.push(ev);
  if (rand() < 0.15) events.push({ ...ev });             // redelivered after a consumer retry
}
const raw = {}, clean = {}, seen = new Set(), uniq = {};
for (const e of events) {
  const k = e.code + " " + e.minute;
  raw[k] = (raw[k] || 0) + 1;
  if (seen.has(e.id)) continue;                          // dedup on event id
  seen.add(e.id);
  clean[k] = (clean[k] || 0) + 1;
  (uniq[e.code] = uniq[e.code] || new Set()).add(e.visitor);
}
console.log("events received " + events.length + ", distinct " + seen.size);
console.log("link  minute  raw  dedup");
for (const k of Object.keys(raw).sort())
  console.log(k.replace(" ", "  ") + String(raw[k]).padStart(5) + String(clean[k]).padStart(7));
for (const c of codes) {
  const clicks = events.filter(e => e.code === c).length;
  console.log(c + ": unique visitors " + uniq[c].size + " (raw clicks " + clicks + ")");
}

events received 71, distinct 60
link  minute  raw  dedup
eid24  10:00   19     17
eid24  10:01   16     12
eid24  10:02   11      8
job7Q  10:00    4      3
job7Q  10:01    4      4
job7Q  10:02    7      6
x9Lp2  10:00    3      3
x9Lp2  10:01    3      3
x9Lp2  10:02    4      4
eid24: unique visitors 13 (raw clicks 46)
job7Q: unique visitors 9 (raw clicks 15)
x9Lp2: unique visitors 8 (raw clicks 10)

ভাইরাল link-এর সব event একটি partition-এ গেলে সেটি গরম হয়; redirect service নিজের memory-তে প্রতি সেকেন্ডের গণনা জমিয়ে একটি event পাঠালে (pre-aggregation) ভার অনেক কমে।

৯ · ভাঙন, trade-off আর বিস্তার

কোনটি মারা গেলে কী হয়

১০ গুণ বড় হলে

দিনে ১০ কোটি নতুন link মানে peak-এ সেকেন্ডে প্রায় ৩,৪৭,২২২টি redirect আর ৫ বছরে তিন কপিতে প্রায় ২৭৪ TB. Write তখনও সেকেন্ডে প্রায় ৩,৫০০ — সামলানো যায়, তবে ID-র block বড় করতে হয়। প্রথম চাপ পড়বে cache-এর RAM আর hot key-এ, তাই edge-এ redirect রাখার যুক্তি শক্ত হয়। Analytics store-ই সম্ভবত সবচেয়ে বড় খরচ হয়ে দাঁড়াবে, কারণ কাঁচা click event আর মিনিটের সারাংশ দ্রুত জমে; তাই পুরোনো ডেটা ঘণ্টা বা দিনের সারাংশে নামানো আর retention-এর নিয়ম লাগে।

অপব্যবহার থেকে সুরক্ষা (প্রতিরক্ষার দিক থেকে)

• ক্ষতিকর URL-এর যাচাই: তৈরির সময় পরিচিত phishing আর malware ঠিকানার তালিকার সাথে মেলানো (URL reputation), কিছুদিন পরপর আবার যাচাই, আর ব্যবহারকারীর রিপোর্টে দ্রুত পর্যালোচনা। সন্দেহজনক link-এ সরাসরি redirect নয়, সতর্কতার পাতা।
• Rate limiting: link তৈরিতে account আর IP ধরে সীমা, নাম-পরিচয়হীন ব্যবহারে কড়া সীমা; অস্তিত্বহীন code-এর খোঁজেও সীমা (পর্ব ৪৯)। বিপুল ঢলে edge-এর DDoS ছাঁকনি।
• নিষিদ্ধ করার গতি: নিষিদ্ধ link-এর key cache থেকে মুছে ফেলা আর CDN-এ purge; edge আর browser-এ যত লম্বা TTL, link তত বেশি সময় চলবে — এজন্যই 302.

মেয়াদ শেষে পরিষ্কার

দুই স্তরে কাজ। পড়ার সময়ই মেয়াদ যাচাই (lazy) — অংশ ৪-এর SQL-এর মতো, তাই মেয়াদোত্তীর্ণ link কখনো redirect হয় না। আর রাতে কম ভিড়ের সময় একটি background job ধীরে ধীরে সেগুলো মুছে ফেলে (পর্ব ৩৭); কিছু KV store-এ নিজস্ব TTL-ও আছে (পণ্যভেদে আলাদা)। Code আবার ব্যবহার করবেন না: পুরোনো SMS বা পোস্টারের QR code তখন নতুন কারও পাতায় নিয়ে যাবে। ৭ অক্ষরের জায়গায় পুনর্ব্যবহারের দরকারও নেই।

একাধিক region-এ পড়া

প্রতিটি region-এ KV store-এর কপি, asynchronous replication-এ (পর্ব ২২)। ফাঁদ: ঢাকার কাছের region-এ link তৈরি হলো, আর কয়েক মুহূর্ত পরে অন্য region-এর কেউ খুললেন — replication lag-এর কারণে সেখানে এখনো নেই, ফল 404. প্রতিকার: local miss হলে link-এর মূল region-কে জিজ্ঞেস করা (code-এর ভেতরে region-এর চিহ্ন রাখলে সহজ), আর 404-কে খুব অল্প সময়ের জন্যই negative cache করা। লেখার দিক আর alias-এর বিশ্বজোড়া অনন্যতা ভাবনার প্রশ্ন ৫-এ।

কী মাপবেন, কিসে alert

• Redirect-এর সফলতার হার আর p99 latency — এটিই মূল SLO (পর্ব ৫০)।
• Cache hit ratio হঠাৎ কমা; 404-এর হার হঠাৎ বাড়া (ভুল deploy, বা কেউ code গুনছে)।
• Analytics consumer-এর lag; URL যাচাইয়ের অপেক্ষমাণ তালিকা; ID block শেষ হওয়ার গতি।

১০ · AI-এর যুগে — AI-র URL shortener নকশা যাচাই

AI-কে URL shortener চাইলে কয়েক সেকেন্ডে পরিচ্ছন্ন, চেনা ছাঁচের একটি উত্তর আসে। ভুলগুলো লুকায় ছাঁচের ফাঁকে:

AI-র নকশা হাতে পেলে — যাচাইয়ের চেকলিস্ট

• QPS, storage, cache আর ৬২^L-এর হিসাব নিজে আবার করেছি
• Random বা hash code হলে n²/(2M) দিয়ে collision গুনেছি, আর প্রতিটি লেখা conditional
• Redirect code-এর পছন্দ requirement-এর সাথে মেলে: analytics, নিষিদ্ধ করার গতি, TTL
• Analytics redirect-এর পথের বাইরে, dedup আর unique গোনার পদ্ধতি স্পষ্ট
• প্রতিটি অংশ বিকল হলে কী হয়, লেখা আছে; অপব্যবহার, মেয়াদ আর region-এর lag বাদ যায়নি
• পণ্যের সীমা documentation-এ মিলিয়েছি, আর অন্তত একটি simulation বা ছোট load test চালিয়েছি