প্রজেক্ট: URL শর্টনার

আগের ছয়টা চ্যাপ্টারে আপনি আলাদা আলাদা যন্ত্রপাতি শিখেছেন। ১ নম্বরে trade-off-এর ভাষা, ২ নম্বরে ঝাপসা দাবিকে requirement-এ নামানো, ৩ নম্বরে খাতা-কলমের হিসাব, ৪ নম্বরে একটা রিকোয়েস্ট কোন পথ ধরে যায়, ৫ নম্বরে কোন ডেটা স্টোর কেন, আর ৬ নম্বরে latency-র সংখ্যা আর percentile।

এই চ্যাপ্টারে প্রথমবার সেগুলো একসাথে ব্যবহার হবে। আমরা একটা URL শর্টনার ডিজাইন করব — গোড়া থেকে শেষ পর্যন্ত।

কিন্তু এই চ্যাপ্টারের আসল বিষয় শর্টনার নয়। আসল বিষয় হলো পদ্ধতি — একজন ডিজাইনার কোন সিদ্ধান্তটা কোন ক্রমে নেয়, আর কেন। উত্তরটা মুখস্থ করে খুব বেশি দূর যাওয়া যায় না; কিন্তু ক্রমটা মাথায় ঢুকে গেলে যেকোনো নতুন সিস্টেমে সেটা কাজে লাগে। তাই প্রতিটা ধাপে আমরা শুধু “কী ঠিক করলাম” বলব না — বলব “এই ধাপে কেন এই প্রশ্নটাই আগে করতে হয়”।

শর্টনারকে প্রথম প্রজেক্ট হিসেবে বেছে নেওয়ার কারণ আছে। এর ব্যবসায়িক লজিক প্রায় শূন্য — একটা লম্বা স্ট্রিং নাও, একটা ছোট স্ট্রিং ফেরত দাও। ফলে ব্যবসায়িক জটিলতা কোনো কিছু আড়াল করতে পারে না, আর যা পড়ে থাকে তা বিশুদ্ধ system design: key কীভাবে বানাবেন, স্টোরেজ কত বাড়বে, read path কত দ্রুত হতে হবে, আর ভাঙলে কোথায় ভাঙবে।

গল্পে বুঝি

বাগদাদের বড় ডাকঘরটা চালান আল-খাওয়ারিজমি। শহরে ঠিকানা লেখার কোনো সংক্ষিপ্ত নিয়ম নেই — মানুষ চিঠির ওপরে আধা পাতা জুড়ে লেখে: “সমরকন্দ থেকে আসা বণিক ইবনে সিনার আড়ত, দক্ষিণ বাজারের তৃতীয় সারি, মশলার দোকানগুলোর পরে চামড়ার গুদামের উল্টো দিকে”। এত লম্বা ঠিকানা কেউ মুখে মুখে বলতে পারে না, কাগজে লিখতে গিয়ে ভুল হয়, আর চিঠি হারায়।

আল-খাওয়ারিজমি একটা ব্যবস্থা চালু করলেন। কেউ ঠিকানা নিয়ে এলে তিনি একটা মোটা খাতায় সেটা তুলে রাখেন, আর সামনে একটা ছোট টোকেন লিখে দেন — যেমন “ক৭৩২”। এরপর চিঠিতে শুধু টোকেনটা লিখলেই চলে। ডাকপিয়ন টোকেন নিয়ে খাতায় খুঁজে আসল ঠিকানা বের করে, তারপর চিঠি পৌঁছে দেয়। খাতাটাই এখানে আসল সত্য, টোকেন শুধু তার দিকে একটা নির্দেশক।

প্রথম প্রশ্ন উঠল — টোকেনের সংখ্যাটা আসবে কোথা থেকে? তিন রকম প্রস্তাব এল, আর তিনটাই আলাদা রোগে ভুগল।

আল-কিন্দি বললেন, একটা গণনার খাতা রাখো — প্রথম ঠিকানা ১, দ্বিতীয়টা ২, এভাবে। সহজ, কখনো দুটো একই টোকেন হবে না। কিন্তু সমস্যা দুটো। এক, ডাকঘরে তিনজন কেরানি একসাথে বসেন, আর তিনজন একই সময়ে গণনার খাতাটা ধরতে গেলে ঝগড়া লাগে, লাইন পড়ে যায়। দুই, টোকেনগুলো ধারাবাহিক বলে যে কেউ “ক৭৩১”, “ক৭৩২”, “ক৭৩৩” লিখে অন্যের ঠিকানা বের করে ফেলতে পারে — যা একটা গোপনীয়তার ফাটল।

ইবনে আল-হাইসাম বললেন, তাহলে গণনা বাদ দাও — একটা কলসিতে হাজার হাজার টোকেন লিখে ফেলে রাখো, আর প্রতিবার চোখ বন্ধ করে একটা তুলে নাও। কেউ পরেরটা অনুমান করতে পারবে না। কিন্তু এখানে নতুন বিপদ: তুলে নেওয়া টোকেনটা আগেই কাউকে দেওয়া হয়ে থাকতে পারে। তাই প্রতিবার তোলার পরে খাতায় খুঁজে দেখতে হয় এটা আগে ব্যবহার হয়েছে কিনা — আর হয়ে থাকলে আবার তুলতে হয়। কলসি যত ভরা থাকে ততক্ষণ এটা বিরল, কিন্তু কলসি খালি হতে থাকলে প্রতিবার কয়েকবার করে তুলতে হয়।

আল-বিরুনি তৃতীয় প্রস্তাব দিলেন: টোকেনটা ঠিকানা থেকেই হিসাব করে বের করো — ঠিকানার অক্ষরগুলোর একটা নির্দিষ্ট গাণিতিক সংক্ষেপ। তাহলে খাতা লাগবেই না, একই ঠিকানা এলে একই টোকেন বেরোবে। শুনতে চমৎকার, কিন্তু দুটো ভিন্ন ঠিকানার সংক্ষেপ একই হয়ে যেতে পারে — আর তখন একজনের চিঠি আরেকজনের বাড়িতে চলে যাবে, যা ডাকঘরের সবচেয়ে ভয়ংকর ভুল। তাছাড়া একই ঠিকানার জন্য দুই বণিক আলাদা টোকেন চাইলে — একজন চায় টোকেনটা মেলার পরে বাতিল হোক, আরেকজন চায় স্থায়ী থাকুক — একই টোকেন দুজনকে দিয়ে সেটা সামলানো যায় না।

শেষে আল-খাওয়ারিজমি আপস করলেন। গণনার খাতাই থাকবে, কিন্তু কেরানিরা একটা করে সংখ্যা নেবেন না — প্রধান কেরানির কাছ থেকে একবারে এক হাজার সংখ্যার একটা ব্লক নিয়ে নিজের টেবিলে রাখবেন, আর সেখান থেকে খরচ করবেন। ব্লক শেষ হলে আবার নতুন ব্লক। ফলে কেন্দ্রীয় খাতাটা দিনে মাত্র কয়েকবার ছোঁয়া হয়, লাইন পড়ে না। আর অনুমান করার সমস্যা ঠেকাতে ঠিক করা হলো, সংখ্যাটা সরাসরি না লিখে একটা নির্দিষ্ট গুণ-নিয়মে ওলটপালট করে লেখা হবে — নিয়মটা জানা থাকলে ফিরিয়ে আনা যায়, না জানলে টোকেনগুলো এলোমেলো দেখায়।

ব্যবস্থাটা চালু হওয়ার পর দেখা গেল আরও কিছু জিনিস। শহরের কয়েকটা টোকেন — বিশেষ করে বড় মসজিদ আর প্রধান বাজারেরগুলো — দিনে হাজার বার জিজ্ঞেস করা হয়। খাতা খুলে প্রতিবার খোঁজা অপচয়, তাই কেরানিরা সেই গুটিকয়েক ঠিকানা মুখস্থ করে ফেললেন এবং টেবিলের ওপর একটা ছোট তালিকায় লিখে রাখলেন। বেশিরভাগ প্রশ্নের উত্তর এখন খাতা না খুলেই দেওয়া যায়।

তারপর দুই ধরনের সাইনবোর্ডের প্রশ্ন এল। মোড়ের মাথায় যদি স্থায়ীভাবে লেখা থাকে “ক৭৩২ মানে দক্ষিণ বাজারের তৃতীয় সারি”, তাহলে ডাকপিয়ন আর ডাকঘরে আসেই না — সোজা চলে যায়। দ্রুত, কিন্তু ডাকঘর তখন জানতেই পারে না ওই টোকেনটা কতবার ব্যবহার হলো, আর ঠিকানা বদলালে সাইনবোর্ডটা পুরনো তথ্য নিয়ে দাঁড়িয়ে থাকে। উল্টোদিকে যদি সাইনবোর্ডে লেখা থাকে “প্রতিবার ডাকঘরে জিজ্ঞেস করো”, তাহলে প্রতিটা চিঠি ডাকঘর হয়ে যায় — ডাকঘরের কাজ বাড়ে, কিন্তু হিসাব থাকে আর ঠিকানা বদলানোও যায়।

আর হিসাবের ব্যাপারটা আল-খাওয়ারিজমি চতুরভাবে সামলালেন। প্রতিটা টোকেন-জিজ্ঞাসার সময় খাতায় দাগ কাটতে গেলে লাইন থেমে যেত। তাই কেরানিরা শুধু একটা ছোট কাগজে দ্রুত টালি মারেন, আর রাতে দোকান বন্ধ করে সেই টালিগুলো একবারে বড় হিসাব-বইতে তোলা হয়। কেউ যদি এই মুহূর্তের নিখুঁত সংখ্যা জানতে চায় — পাবে না; কিন্তু কেউ চায়ও না।

মিলিয়ে নিই: ছোট টোকেন হলো short key, মোটা খাতা হলো আসল ডেটাবেস (source of truth), টোকেন থেকে ঠিকানা বের করা হলো redirect lookup, আল-কিন্দির গণনার খাতা হলো counter-based generation আর তার ঝগড়াটা হলো contention on a global counter, ব্লক করে সংখ্যা নেওয়া হলো range allocation, গুণ-নিয়মে ওলটপালট করা হলো bijective scrambling (যাতে key অনুমানযোগ্য না হয়), কলসি থেকে টোকেন তোলা হলো random key generation আর আগেই ব্যবহৃত টোকেন পাওয়া হলো collision, ঠিকানা থেকে হিসাব করে বের করা হলো hashing আর দুই ঠিকানার একই সংক্ষেপ হলো hash collision, টেবিলের ছোট তালিকা হলো cache, স্থায়ী সাইনবোর্ড হলো 301 permanent redirect আর “প্রতিবার জিজ্ঞেস করো” হলো 302 temporary redirect, আর রাতে একবারে হিসাব তোলা হলো async analytics off the hot path।

পুরো চ্যাপ্টারটা এই একটা ছবিরই ইঞ্জিনিয়ারিং অনুবাদ।

ধাপ ১: রিকোয়ারমেন্ট

২ নম্বর চ্যাপ্টারের নিয়ম — কোড বা ডায়াগ্রামের আগে স্কোপ কাটুন। কী বানাচ্ছি সেটার চেয়ে কী বানাচ্ছি না, সেটা লিখে ফেলা বেশি জরুরি, কারণ পরের প্রতিটা সিদ্ধান্ত এই সীমানার ভেতরেই নেওয়া হবে।

Functional — যা অবশ্যই থাকবে:

• একটা লম্বা URL দিলে সিস্টেম একটা ছোট URL ফেরত দেবে
• ছোট URL-এ গেলে ব্যবহারকারী মূল URL-এ redirect হবে
• ব্যবহারকারী চাইলে নিজের পছন্দমতো alias দিতে পারবে (যেমন baghd.ad/rasadkhana)
• একটা লিংকের মেয়াদ (expiry) ঠিক করে দেওয়া যাবে
• লিংকের ক্লিক সংখ্যা ও মৌলিক analytics দেখা যাবে

Functional — যা এই ডিজাইনে ধরছি না:

• ব্যবহারকারীর অ্যাকাউন্ট, টিম, বিলিং — এগুলো আলাদা সিস্টেম
• লিংক এডিট করে গন্তব্য বদলানো (v2-তে, নিচে আলোচনা আছে)
• QR কোড, browser extension, বাল্ক ইমপোর্ট
• A/B টেস্টিং বা geo-ভিত্তিক আলাদা গন্তব্য

Non-functional — এগুলোই আসলে আর্কিটেকচার ঠিক করে দেয়:

ধাপ ২: এস্টিমেশন

৩ নম্বর চ্যাপ্টারের পুরো পয়েন্টটা এখানে। সংখ্যা ছাড়া আর্কিটেকচার নিয়ে তর্ক করা মানে রুচির তর্ক করা। ধরে নিই:

নতুন লিংক তৈরি     = 100,000,000 / মাস
read : write অনুপাত = 100 : 1
গড় URL দৈর্ঘ্য     = 200 বাইট
ডেটা রাখার মেয়াদ    = 5 বছর (কমপক্ষে)

Write throughput:

writes/sec = 100M / (30 * 86,400)
           = 100,000,000 / 2,592,000
           ≈ 39 /sec

peak (3x)  ≈ 120 /sec

৩৯ writes/sec। এটা কার্যত শূন্য — একটা মাঝারি Postgres ইনস্ট্যান্স এটা ঘুমিয়ে ঘুমিয়ে সামলাবে। অর্থাৎ লেখা এই সিস্টেমের সমস্যা নয়, আর এই সিদ্ধান্তটা এখনই নিয়ে ফেলা দরকার, কারণ এটা আপনাকে বাকি চ্যাপ্টারে write path নিয়ে অযথা দুশ্চিন্তা করা থেকে বাঁচাবে।

Read throughput:

reads/sec = 39 * 100          ≈ 3,900 /sec
peak (3x)                     ≈ 12,000 /sec

১২,০০০ reads/sec। এটাও অতিমানবিক কিছু নয়, কিন্তু এটাই সেই সংখ্যা যেটা latency বাজেটের সাথে মিলিয়ে দেখতে হবে। ৬ নম্বর চ্যাপ্টারের টেবিল মনে করুন: মেমরি থেকে পড়া ন্যানোসেকেন্ড, SSD মাইক্রোসেকেন্ড, নেটওয়ার্ক মিলিসেকেন্ড। ১২,০০০ QPS-এ প্রতিটা রিকোয়েস্টে যদি একটা ডিস্ক-ভিত্তিক ডেটাবেস লুকআপ হয় (ধরুন ২ ms), তাহলে ডেটাবেসকে সেকেন্ডে ১২,০০০ random read দিতে হবে — সম্ভব, কিন্তু ব্যয়বহুল আর ভঙ্গুর। মেমরি থেকে দিলে একই কাজ প্রায় বিনামূল্যে হয়। এই এক লাইনের হিসাবই caching-কে ঐচ্ছিক থেকে বাধ্যতামূলক বানিয়ে দিল।

Storage:

প্রতি row:
  short_key       7 B
  long_url      200 B (গড়)
  owner_id        8 B
  created_at      8 B
  expires_at      8 B
  flags/meta     20 B
  index overhead ~50 B
  --------------------
  মোট           ≈ 300 B

100M rows/মাস * 300 B = 30 GB / মাস
                      = 360 GB / বছর
5 বছরে                ≈ 1.8 TB

১.৮ TB। এটা একটা গুরুত্বপূর্ণ সংখ্যা, কারণ এটা একটা মেশিনে ধরে — আজকের একটা সাধারণ ক্লাউড ইনস্ট্যান্সে ৪ TB SSD স্বাভাবিক। অর্থাৎ প্রথম দিন থেকে sharding করার কোনো দরকার নেই, আর যে ডিজাইন প্রথম দিনেই sharding দিয়ে শুরু করে সেটা অতিরিক্ত ইঞ্জিনিয়ারিং।

Key space — এই সিস্টেমের সবচেয়ে নির্ধারক হিসাব:

base62 বর্ণমালা = [a-z A-Z 0-9] = 62টা অক্ষর

62^5 =        916,132,832   (~0.9 বিলিয়ন)
62^6 =     56,800,235,584   (~57 বিলিয়ন)
62^7 =  3,521,614,606,208   (~3.5 ট্রিলিয়ন)

আমাদের হার = 100M/মাস = 1.2 বিলিয়ন/বছর

6 অক্ষরে টিকবে: 57B / 1.2B  ≈ 47 বছর
7 অক্ষরে টিকবে: 3.5T / 1.2B ≈ 2,900 বছর

Bandwidth:

Redirect response ≈ 500 B (হেডার সহ, বডি প্রায় খালি)
12,000 * 500 B ≈ 6 MB/s ≈ 48 Mbps

তুচ্ছ। শর্টনার bandwidth-এর সমস্যা নয়, এটা QPS আর latency-র সমস্যা।

Cache আকার:

দৈনিক read = 3,900 * 86,400 ≈ 340M
80/20 নিয়ম: 20% key 80% ট্রাফিক টানে
দৈনিক সক্রিয় distinct key ≈ 20M ধরি
প্রতি entry (key + url + meta) ≈ 250 B
20M * 250 B ≈ 5 GB

৫ GB — একটা Redis ইনস্ট্যান্সে অনায়াসে ধরে। এই হিসাবটা করে ফেলার পর আপনি জানেন cache cluster লাগবে না, একটা replica-সহ Redis-ই যথেষ্ট।

ধাপ ৩: API সারফেস

এখন — schema বা ডেটাবেসের আগে — API ঠিক করুন। কারণ API হলো সিস্টেমের চুক্তি, আর চুক্তিটা লিখে ফেললে ভেতরের সব সিদ্ধান্ত সেই চুক্তির সেবক হয়ে যায়। উল্টোটা করলে, অর্থাৎ আগে টেবিল বানিয়ে পরে API বানালে, API-তে ডেটাবেসের কাঠামো ফাঁস হয়ে যায়।

POST /v1/links
Authorization: Bearer <api-key>
Content-Type: application/json

{
  "url": "https://kitab.bukhara.org/majmua/rasad/1187/tables?section=zij",
  "alias": "zij",              // ঐচ্ছিক, custom alias
  "expiresAt": "2027-01-01T00:00:00Z",   // ঐচ্ছিক
  "idempotencyKey": "c1f7b2a4-..."       // ঐচ্ছিক কিন্তু পরামর্শযোগ্য
}

201 Created
{
  "shortKey": "9kQ2xVb",
  "shortUrl": "https://baghd.ad/9kQ2xVb",
  "longUrl": "https://kitab.bukhara.org/majmua/rasad/1187/tables?section=zij",
  "createdAt": "2026-03-04T10:12:44Z",
  "expiresAt": "2027-01-01T00:00:00Z"
}

GET /9kQ2xVb
->  302 Found
    Location: https://kitab.bukhara.org/majmua/rasad/1187/tables?section=zij
    Cache-Control: private, max-age=0

GET /v1/links/9kQ2xVb        -> লিংকের মেটাডেটা (redirect নয়)
GET /v1/links/9kQ2xVb/stats  -> ক্লিক analytics
DELETE /v1/links/9kQ2xVb     -> নিষ্ক্রিয় করা

তিনটা সিদ্ধান্ত ব্যাখ্যা করার মতো।

Redirect আর API আলাদা পথে। GET /9kQ2xVb কোনো JSON API নয় — এটা একটা HTTP redirect, আর এটাই সিস্টেমের ৯৯% ট্রাফিক। এটাকে /v1/... এর নিচে না রাখার কারণ শুধু নান্দনিক নয়: short URL যত ছোট হয় তত ভালো, আর গুরুত্বপূর্ণভাবে, এই একটা রুট আলাদা থাকায় সেটাকে আলাদা সার্ভিসে, আলাদা মেশিনে, এমনকি আলাদা ডোমেইনে চালানো যায়।

idempotencyKey। ইউজার ফর্ম সাবমিট করে, রেসপন্স আসতে দেরি হয়, সে আবার সাবমিট করে — এখন দুটো আলাদা short key একই URL-এর জন্য তৈরি হলো। ৪ নম্বর চ্যাপ্টারে দেখেছেন একটা রিকোয়েস্ট পথে কতগুলো জায়গায় timeout হতে পারে; retry অনিবার্য। একটা idempotency key নিয়ে সেটা কয়েক ঘণ্টা মনে রাখলে একই রিকোয়েস্ট দুবার এলে একই উত্তর ফেরত যায়।

একই URL দুবার শর্ট করলে কী হবে? স্বাভাবিক প্রবৃত্তি — একই key ফেরত দেওয়া, স্টোরেজ বাঁচবে। কিন্তু এটা প্রায় সবসময় ভুল সিদ্ধান্ত, কারণ দুই ইউজার একই URL শর্ট করলে তাদের analytics মিশে যাবে, একজনের expiry অন্যজনের লিংক মেরে ফেলবে, আর একজন লিংক ডিলিট করলে অন্যজনেরটাও মরবে। ডিফল্ট হবে: প্রতিটা create রিকোয়েস্ট নতুন key, আর dedupe করতে হলে সেটা করুন শুধু একই owner-এর ভেতরে, এবং সেটাও ঐচ্ছিক ফ্ল্যাগ হিসেবে।

ধাপ ৪: short key তৈরির সমস্যা

এটাই এই প্রজেক্টের কেন্দ্রীয় প্রশ্ন, আর ইন্টারভিউতেও এখানেই বেশিরভাগ সময় যায়। তিনটা পরিবারের সমাধান আছে, আর প্রতিটার আলাদা রোগ।

পথ ১: Counter + base62

একটা ক্রমবর্ধমান সংখ্যা নিন, সেটাকে base62-তে লিখুন। ১ হয় b, ৬২ হয় ba, ৩,৫২১,৬১৪,৬০৬,২০৭ হয় সাত অক্ষরের সর্বোচ্চ key।

যা ভালো: collision গাণিতিকভাবে অসম্ভব, তাই কোনো existence check লাগে না — প্রতি write-এ একটা ডেটাবেস রাউন্ড ট্রিপ বাঁচল। key-গুলো ছোট থেকে বড় হয়, তাই শুরুতে ছোট key পাওয়া যায়। আর সংখ্যা থেকে key আর key থেকে সংখ্যা — দুই দিকেই যাওয়া যায়, যা ডিবাগিংয়ে অপ্রত্যাশিতভাবে কাজে আসে।

যা খারাপ, এক: counter-টা কোথায় থাকবে? একটামাত্র ডেটাবেস sequence-এ রাখলে প্রতিটা app সার্ভারকে প্রতিটা create-এ সেই এক জায়গায় যেতে হবে। ৩৯ writes/sec-এ এটা সমস্যা নয়, কিন্তু এটা একটা single point of failure — counter ডাউন মানে কোনো লিংক তৈরি হবে না।

সমাধান — range allocation। প্রতিটা app সার্ভার কেন্দ্রীয় counter থেকে একবারে ১০,০০০ সংখ্যার একটা ব্লক নিয়ে নেয় (Redis-এ INCRBY 10000, বা ডেটাবেসে একটা ছোট transaction), তারপর সেই ব্লক থেকে মেমরিতে খরচ করে। ফলে কেন্দ্রীয় counter-এ চাপ ১০,০০০ গুণ কমে যায়, আর counter সাময়িকভাবে অগম্য হলেও সার্ভারগুলো হাতে থাকা ব্লক দিয়ে চলতে থাকে। সার্ভার রিস্টার্ট হলে ব্লকের বাকি সংখ্যাগুলো হারায় — কিন্তু ৩.৫ ট্রিলিয়ন key-এর জগতে কয়েক হাজার সংখ্যা নষ্ট হওয়া সম্পূর্ণ অপ্রাসঙ্গিক। এটা একটা চমৎকার উদাহরণ: সস্তা সম্পদ নষ্ট করে দামি coordination কেনা যায় না — বরং উল্টোটা।

যা খারাপ, দুই: key অনুমানযোগ্য। 9kQ2xVa-র পরেরটা 9kQ2xVb। যে কেউ ক্রম ধরে সব লিংক এনুমারেট করে ফেলতে পারবে — যা আমাদের non-functional টেবিলের শেষ সারির সরাসরি লঙ্ঘন।

সমাধান — bijective scrambling। counter-এর মানটা সরাসরি base62 না করে, আগে একটা উল্টানো-যোগ্য গাণিতিক রূপান্তর চালান:

scrambled = (counter * MULTIPLIER + OFFSET) mod 62^7

যদি MULTIPLIER আর 62^7 পরস্পর সহমৌলিক (coprime) হয়, তাহলে এই রূপান্তরটা bijective — অর্থাৎ প্রতিটা counter মান ঠিক একটা আলাদা scrambled মানে যায়, কোনো collision নেই, আর modular inverse দিয়ে সেটা ফিরিয়ে আনা যায়। ফলে collision-মুক্ত থাকার সুবিধা বজায় থাকল, অথচ পরপর দুটো key দেখতে সম্পূর্ণ সম্পর্কহীন লাগবে।

পথ ২: Random key

প্রতিবার ৭টা random base62 অক্ষর বানান, ডেটাবেসে unique constraint-সহ ঢোকানোর চেষ্টা করুন, সংঘর্ষ হলে আরেকবার চেষ্টা করুন।

যা ভালো: কোনো কেন্দ্রীয় coordination নেই — প্রতিটা সার্ভার স্বাধীনভাবে key বানায়। key স্বাভাবিকভাবেই অনুমান-অযোগ্য।

যা খারাপ: collision। কতটা খারাপ, সেটা হিসাব করে দেখা যাক — এবং এই হিসাবটা করতে পারাই আসল দক্ষতা:

key space K   = 62^7 = 3.52 * 10^12
৫ বছর পরে ব্যবহৃত N = 6 * 10^9  (1.2B/বছর * 5)

একটা নতুন random key ইতিমধ্যে ব্যবহৃত হওয়ার সম্ভাবনা
  = N / K
  = 6e9 / 3.52e12
  ≈ 0.0017  =  0.17%   (প্রতি ৫৮৭ বারে একবার)

অর্থাৎ ৫ বছর পরেও ৫৮৭টা create-এর মধ্যে একটাতে একবার retry লাগবে, আর দুবার পরপর collision হওয়ার সম্ভাবনা ৩০ লাখে একবার। এটা সম্পূর্ণ গ্রহণযোগ্য — শর্ত হলো, collision যেন চুপচাপ ভুল উত্তর না দিয়ে জোরে ব্যর্থ হয়। সেটার একমাত্র নির্ভরযোগ্য উপায় হলো ডেটাবেসে short_key কলামে একটা unique index রাখা এবং insert-এর ব্যর্থতা ধরে retry করা। “আগে SELECT করে দেখি আছে কিনা, না থাকলে INSERT” — এটা কাজ করে না, কারণ দুটো সমান্তরাল রিকোয়েস্ট দুটোই “নেই” দেখে দুটোই ঢোকানোর চেষ্টা করবে। এই ধরনের check-then-act রেস কন্ডিশন system design-এর সবচেয়ে প্রচলিত ভুলগুলোর একটা।

দাম: প্রতিটা create-এ অন্তত একটা ডেটাবেস write প্রচেষ্টা, আর মাঝে মাঝে দুটো। ৩৯ writes/sec-এ এটা অদৃশ্য। ৪,০০০ writes/sec-এ এটা লক্ষণীয়।

পথ ৩: Long URL-এর hash

MD5(long_url) বা SHA-256(long_url) নিয়ে প্রথম ৭ base62 অক্ষর নিন।

যা ভালো: deterministic — একই URL সবসময় একই key দেয়, তাই dedupe বিনামূল্যে। কোনো counter নেই, কোনো state নেই।

যা খারাপ, এবং কেন এটা বাতিল:

Hash-কে ৭ অক্ষরে কেটে ফেলার মানে আপনি একটা ২৫৬-বিট আউটপুটকে ৪২ বিটে চাপাচ্ছেন। এতে collision শুধু সম্ভব নয় — birthday paradox অনুযায়ী তা অনিবার্য, এবং random key-এর তুলনায় অনেক আগেই ঘটবে না, বরং একই হারে ঘটবে (গাণিতিকভাবে দুটো একই key space)। কিন্তু ফলাফল সম্পূর্ণ আলাদা: random key-তে collision মানে “আরেকবার চেষ্টা করো”, আর hash-এ collision মানে আপনার হাতে একই key-এর জন্য দুটো ভিন্ন URL — এবং তখন hash-এর মূল প্রতিশ্রুতিটাই (deterministic) ভাঙতে হয়, অর্থাৎ salt যোগ করে আবার hash করতে হয়, আর সেই মুহূর্তে এটা কার্যত random key হয়ে যায় — শুধু বেশি জটিল।

দ্বিতীয় সমস্যাটা আরও মৌলিক, আর এটাই আসল কারণ: deterministic key মানে দুই ইউজারের একই লিংক, যা ধাপ ৩-এ আলোচনা করা সব সমস্যা ডেকে আনে — মিশে যাওয়া analytics, একজনের expiry-তে অন্যজনের লিংকের মৃত্যু, একজনের delete-এ অন্যজনের ভাঙা লিংক।

সিদ্ধান্ত

আমরা নিচ্ছি counter + range allocation + bijective scramble, আর ফলব্যাক হিসেবে unique index-এ retry রাখছি (কারণ ডিফেন্স ইন ডেপথ সস্তা)। কিন্তু সৎ থাকা দরকার: যদি আপনার দল ছোট হয় এবং write throughput কম হয়, random key + unique index একটা সম্পূর্ণ বৈধ এবং অনেক সরল উত্তর — এবং ইন্টারভিউতে সেটা বললে সেই ট্রেড-অফটা স্পষ্ট করে বলাটাই আসল নম্বর পাওয়ার জায়গা। “সবচেয়ে চতুর উত্তর” আর “সবচেয়ে উপযুক্ত উত্তর” এক জিনিস নয়।

ধাপ ৫: ডেটা স্কিমা আর স্টোর

এখন — এবং কেবল এখন — ডেটাবেসের প্রশ্ন। ৫ নম্বর চ্যাপ্টারের নিয়ম: ফ্যাশন দেখে নয়, access pattern দেখে বাছুন। আমাদের access pattern তিনটা, এবং তিনটাই তুচ্ছ:

1. short_key দিয়ে একটা row পড়া — সেকেন্ডে ১২,০০০ বার
2. একটা নতুন row লেখা — সেকেন্ডে ৩৯ বার
3. owner_id দিয়ে নিজের লিংকের তালিকা — সেকেন্ডে হাতে গোনা কয়েকবার

কোনো join নেই, কোনো range scan নেই, কোনো লেনদেন-ভিত্তিক জটিলতা নেই। এটা একটা বিশুদ্ধ key-value access pattern।

CREATE TABLE links (
  short_key    VARCHAR(16)  PRIMARY KEY,       -- base62, সাধারণত 7 অক্ষর
  long_url     TEXT         NOT NULL,
  owner_id     BIGINT,                          -- NULL মানে বেনামী
  created_at   TIMESTAMPTZ  NOT NULL DEFAULT now(),
  expires_at   TIMESTAMPTZ,                     -- NULL মানে কখনো মেয়াদ শেষ নয়
  is_active    BOOLEAN      NOT NULL DEFAULT TRUE,
  is_custom    BOOLEAN      NOT NULL DEFAULT FALSE,
  redirect_code SMALLINT    NOT NULL DEFAULT 302
);

-- "আমার লিংকগুলো দেখাও" — কম ব্যবহৃত, কিন্তু index ছাড়া full scan
CREATE INDEX links_owner_idx ON links (owner_id, created_at DESC);

-- মেয়াদোত্তীর্ণ row পরিষ্কারের জন্য partial index; সব row নয়, শুধু যাদের expiry আছে
CREATE INDEX links_expiry_idx ON links (expires_at) WHERE expires_at IS NOT NULL;

-- Idempotency: একই create রিকোয়েস্ট দুবার এলে একই উত্তর
CREATE TABLE create_requests (
  idempotency_key  UUID        PRIMARY KEY,
  short_key        VARCHAR(16) NOT NULL REFERENCES links(short_key),
  created_at       TIMESTAMPTZ NOT NULL DEFAULT now()
);

-- Key allocator: প্রতিটা app সার্ভার এখান থেকে ব্লক নেয়
CREATE TABLE key_allocator (
  name        TEXT   PRIMARY KEY,      -- 'default'
  next_value  BIGINT NOT NULL
);

চারটা সিদ্ধান্ত ব্যাখ্যা করার মতো।

short_key নিজেই primary key, কোনো আলাদা id কলাম নয়। কারণ ৯৯% query ঠিক এই কলাম দিয়েই আসে, আর primary key-ই সবচেয়ে দ্রুত পথ। একটা bigint id যোগ করে short_key-তে secondary index দিলে প্রতিটা লুকআপে দুটো index hop লাগত।

long_url কখনো ওভাররাইট হয় না এই v1-এ। এটাই is_active-এর কারণ — লিংক বাতিল করতে হলে row মুছে না ফেলে flag নামান। মুছে ফেললে key-টা পরে অন্য কাউকে বরাদ্দ হয়ে যেতে পারে, আর তখন পুরনো ছাপা লিংক ভুল জায়গায় নিয়ে যাবে — একটা নিঃশব্দ কিন্তু গুরুতর বাগ।

expires_at NULL হতে পারে, আর সেই কারণেই index-টা partial। বেশিরভাগ লিংকের expiry নেই; সব row-কে expiry index-এ ঢোকানো মানে অকারণে index-টা দশ গুণ বড় করা।

redirect_code row-প্রতি সংরক্ষিত। ধাপ ৮-এ দেখব ৩০১ আর ৩০২-এর পার্থক্য কতটা ব্যয়বহুল; সেই সিদ্ধান্তটা যেন প্রতি-লিংক ভিত্তিতে নেওয়া যায়, গোটা সিস্টেমের জন্য একবারে নয়।

স্টোর কোনটা? এই access pattern-এ Postgres, MySQL, DynamoDB, Cassandra — সবগুলোই কাজ করবে। বাছাইয়ের যুক্তিটা এরকম:

• আমাদের স্কেলে (১.৮ TB, ৩৯ writes/sec) একটা relational ডেটাবেসই সঠিক উত্তর। এটা পরিচিত, লেনদেন দেয় (idempotency টেবিলের জন্য দরকারি), unique constraint দেয় (collision ধরার জন্য দরকারি), আর অপারেশনাল টুলিং পরিপক্ব।
• DynamoDB বা Cassandra তখনই সঠিক যখন write throughput বা ডেটার আকার একটা মেশিন ছাড়িয়ে যায়, বা multi-region লেখা লাগে। ১০০x স্কেলে (ধাপ ১২) এটা প্রাসঙ্গিক হবে।
• শুধু key-value স্টোর (Redis) সত্যের উৎস হিসেবে চলবে না — durability-র দাবিটা মনে আছে? একটা ম্যাপিং হারানো মানে একটা লিংকের স্থায়ী মৃত্যু।

ধাপ ৬: হাই-লেভেল আর্কিটেকচার

আকৃতিটা ইচ্ছাকৃতভাবে অসম, আর সেই অসমতাটাই এই ডিজাইনের মূল বক্তব্য:

• Redirect service — সমস্ত ট্রাফিক, সবচেয়ে কড়া latency বাজেট, সম্পূর্ণ stateless, শুধু পড়ে। এটাকে যত খুশি স্কেল করা যায়, আর এর কোনো instance হারালে কিছুই হারায় না।
• Write API — নগণ্য ট্রাফিক, কিন্তু এখানেই সব জটিলতা: key allocation, idempotency, validation, abuse চেক। ধীর হলে সমস্যা নেই।
• Analytics pipeline — সম্পূর্ণ আলাদা, সম্পূর্ণ async। পুরোপুরি ডাউন থাকলেও একটাও redirect ব্যর্থ হবে না।

এই তিনটাকে আলাদা করা ৯ নম্বর চ্যাপ্টারের বিষয় নয়, এটা এই চ্যাপ্টারেরই মূল শিক্ষা: যে অংশগুলোর স্কেলিং প্রোফাইল আর ব্যর্থতার পরিণতি ভিন্ন, সেগুলোকে আলাদা রাখুন। একই প্রসেসে redirect আর analytics চালালে analytics-এর একটা ধীর লেখা redirect-এর p99 নষ্ট করবে — আর ৬ নম্বর চ্যাপ্টার থেকে আপনি জানেন, p99 কোনো প্রান্তিক ঘটনা নয়।

ধাপ ৭: Redirect hot path আর caching

এটাই সেই ৯৯%। এখানে যা ঘটে সেটাই সিস্টেমের চরিত্র ঠিক করে দেয়।

তিনটা স্তরের ক্যাশ, আর প্রতিটার আলাদা যুক্তি:

স্তর ০ — in-process LRU (প্রতিটা redirect সার্ভারে)। কয়েক লাখ এন্ট্রি, লুকআপ কার্যত শূন্য সময়। ৬ নম্বর চ্যাপ্টারের সংখ্যা মনে করুন: মেমরি রেফারেন্স ১০০ ns, আর ডেটাসেন্টারের ভেতরে একটা Redis রাউন্ড ট্রিপ ০.৫ ms — অর্থাৎ পাঁচ হাজার গুণ ফারাক। ট্রাফিক বণ্টন প্রচণ্ড অসম (কিছু ভাইরাল লিংক লক্ষ লক্ষ ক্লিক পায়), তাই একটা ছোট local cache-ই ট্রাফিকের বড় অংশ শুষে নেয়।

স্তর ১ — Redis (শেয়ার্ড)। ধাপ ২-এ হিসাব করেছি — প্রায় ৫ GB, একটা ইনস্ট্যান্সে ধরে। TTL ২৪ ঘণ্টা। এর কাজ হলো local cache-এর miss গুলোকে ডেটাবেস থেকে দূরে রাখা, আর নতুন redirect সার্ভার চালু হলে তার cold start-কে সহনীয় করা।

স্তর ২ — ডেটাবেস। এখানে ট্রাফিক পৌঁছানোই ব্যর্থতার লক্ষণ। ৯৫%+ cache hit ratio থাকলে ডেটাবেসে যায় সেকেন্ডে কয়েকশো query — নগণ্য।

Negative caching। কেউ baghd.ad/aaaaaaa টাইপ করলে সেটা ডেটাবেসে নেই। কোনো bot যদি এলোমেলো key দিয়ে সেকেন্ডে হাজারটা রিকোয়েস্ট পাঠায়, প্রতিটাই cache miss হয়ে সরাসরি ডেটাবেসে যাবে — অর্থাৎ ক্যাশটা কার্যত বাইপাস হয়ে গেল। সমাধান: “নেই” ফলাফলটাও ক্যাশ করুন, ছোট TTL-এ (যেমন ৬০ সেকেন্ড)। খরচ সামান্য মেমরি, লাভ একটা গোটা শ্রেণির আক্রমণ থেকে মুক্তি।

ক্যাশে কী রাখবেন। পুরো row নয় — শুধু redirect-এর জন্য যা লাগে: long_url, expires_at, is_active, redirect_code। মেটাডেটা আর analytics ক্যাশে রাখার কোনো কারণ নেই, আর entry যত ছোট তত বেশি entry ধরে।

ধাপ ৮: 301 নাকি 302

এটা একটা এক-লাইনের কোড পরিবর্তন যার ব্যবসায়িক ফলাফল বিশাল — আর ঠিক এই কারণেই এটা প্রিয় ইন্টারভিউ প্রশ্ন।

৩০১-এর সমস্যাটা কতটা গভীর সেটা একটা সংখ্যায় বোঝা যায়। ধরুন একটা লিংক ১০০ জন মানুষ গড়ে ৩ বার করে ক্লিক করে। ৩০২-এ আপনি ৩০০টা ক্লিক দেখবেন। ৩০১-এ আপনি দেখবেন ১০০টা — কারণ প্রতিটা ব্রাউজার প্রথমবারের পর আর আপনার সার্ভারেই আসে না। আপনার analytics চুপচাপ, নিয়মমাফিক, তিন গুণ কম দেখাবে, আর কোনো error log-এ কিছুই ধরা পড়বে না।

আরও খারাপ: ৩০১ ব্রাউজারে প্রায় স্থায়ীভাবে বসে থাকে। কেউ ভুল URL দিয়ে লিংক বানিয়ে ফেললে, বা কোনো লিংক পরে ম্যালওয়্যারে পরিণত হলে, আপনি সেটা সার্ভারে বদলে দিলেও যে ব্রাউজারগুলো একবার ৩০১ পেয়েছে তারা পুরনো গন্তব্যেই যেতে থাকবে — এবং ব্যবহারকারীকে ক্যাশ পরিষ্কার করতে বলা ছাড়া আপনার হাতে কিছু নেই।

সিদ্ধান্ত: ডিফল্ট ৩০২, আর Cache-Control: private, max-age=0 দিয়ে সেটা স্পষ্ট করে দিন (কিছু প্রক্সি অন্যথায় ৩০২-ও ক্যাশ করে ফেলে)। ৩০১ থাকুক একটা প্রতি-লিংক opt-in হিসেবে, তাদের জন্য যারা analytics-এর চেয়ে গতি চায় এবং জানে গন্তব্য কখনো বদলাবে না।

ধাপ ৯: Custom alias আর expiry

Custom alias দেখতে ছোট ফিচার, কিন্তু এটা key generation-এর সব হিসাব বদলে দেয়, কারণ এখানে key আসে বাইরে থেকে — অর্থাৎ collision আর সম্ভাবনার ব্যাপার নয়, নিশ্চিত ঘটনা। কেউ zij চাইবে, দশজন চাইবে।

নিয়মগুলো:

• Custom alias আর generated key একই namespace-এ থাকে, তাই একটা alias নিলে সেটা generated key হিসেবে আর কখনো বেরোবে না। এটা unique index স্বয়ংক্রিয়ভাবে নিশ্চিত করে — এবং এই কারণেই দুটোকে আলাদা টেবিলে রাখা একটা ফাঁদ।
• Generated key-গুলো ঠিক ৭ অক্ষরের, আর custom alias-এর ন্যূনতম দৈর্ঘ্য ৩ ও সর্বোচ্চ ৩২ — কিন্তু ৭ অক্ষরের custom alias-ও অনুমোদিত রাখা যায়, কারণ unique index দ্বন্দ্ব ঠেকাবে। (কিছু সিস্টেম custom alias-কে ইচ্ছাকৃতভাবে ৭ অক্ষরের বাইরে রাখে যাতে দুটো space কখনো মেশেই না — এটাও একটা বৈধ পছন্দ, শুধু সচেতনভাবে নিন।)
• একটা সংরক্ষিত শব্দের তালিকা লাগবেই: api, admin, login, static, health, v1, robots.txt — নইলে কেউ baghd.ad/api দখল করে নিয়ে আপনার নিজের রুট ভেঙে দেবে।
• অশ্লীল বা ব্র্যান্ড-নকল alias ফিল্টার করার একটা তালিকা রাখুন। এটা প্রযুক্তিগত নয়, কিন্তু প্রোডাকশনে এটা না থাকলে দ্রুত সমস্যা হয়।

Expiry নিয়ে আসল প্রশ্নটা হলো: মেয়াদ শেষ হওয়া row কে মুছবে, আর কখন?

তিনটা পথ, আর এখানে সঠিক উত্তরটা একটু বিপরীতমুখী:

• Lazy — পড়ার সময় expires_at চেক করুন; পার হয়ে গেলে ৪১০ Gone ফেরত দিন, row থাকুক। খরচ শূন্য, আর row থাকায় ইউজারকে “এই লিংকের মেয়াদ শেষ” বলা যায়।
• Batch cleanup — রাতে একটা job মেয়াদোত্তীর্ণ row মুছে দেয়। স্টোরেজ বাঁচে।
• TTL-ভিত্তিক স্টোর — DynamoDB বা Redis-এর মতো স্টোরকে নিজে থেকেই মুছতে দেওয়া।

ডিফল্ট হবে lazy, আর ব্যাচ cleanup ঐচ্ছিক। কারণ ধাপ ২-এ হিসাব করা হয়েছে — ৫ বছরে ১.৮ TB, যা কোনো সমস্যাই নয়। যে স্টোরেজ সমস্যা নয়, তার জন্য জটিলতা কেনা বোকামি। আর মুছে ফেলার একটা বাস্তব বিপদও আছে: key পুনর্ব্যবহৃত হয়ে পুরনো ছাপা লিংক ভুল জায়গায় নিয়ে যেতে পারে। তাই মুছলেও key-টা একটা “tombstone” তালিকায় রাখুন।

ক্যাশে expiry। একটা লিংকের মেয়াদ যদি ২ ঘণ্টা পরে শেষ হয়, আর ক্যাশ TTL ২৪ ঘণ্টা, তাহলে মেয়াদ শেষ হওয়ার পরেও ২২ ঘণ্টা লিংকটা কাজ করবে। সমাধান সরল: cache TTL = min(default TTL, লিংকের বাকি মেয়াদ)। এটা এক লাইনের কোড, কিন্তু এই ধরনের সূক্ষ্ম অসঙ্গতিই প্রোডাকশনে সবচেয়ে বিভ্রান্তিকর বাগ তৈরি করে।

ধাপ ১০: Click analytics — hot path থেকে সরান

এই সিস্টেমের সবচেয়ে গুরুত্বপূর্ণ নিয়মটা একটা বাক্যে: redirect রেসপন্স পাঠানোর আগে কোনো analytics লেখা হবে না।

কেন, সেটা ৬ নম্বর চ্যাপ্টারের ভাষায় দেখুন। Redirect-এর কাজটা হলো cache থেকে একটা স্ট্রিং পড়ে একটা হেডার পাঠানো — মাইক্রোসেকেন্ডের ব্যাপার। এর সাথে যদি একটা ডেটাবেস UPDATE links SET clicks = clicks + 1 জুড়ে দেন, তাহলে:

• Latency মাইক্রোসেকেন্ড থেকে মিলিসেকেন্ডে চলে গেল — হাজার গুণ
• একটা read-only পথ হঠাৎ write path হয়ে গেল, অর্থাৎ read replica থেকে সার্ভ করা আর সম্ভব নয়
• ভাইরাল লিংকের একটামাত্র row-তে সেকেন্ডে হাজারটা UPDATE — একটা নিখুঁত hot row, যেখানে সব লেখা একটার পর একটা lock-এর জন্য অপেক্ষা করবে
• ডেটাবেস ধীর হলে redirect-ও ধীর হবে, অর্থাৎ analytics-এর ব্যর্থতা প্রোডাক্টের ব্যর্থতা হয়ে গেল

সঠিক পাইপলাইনটা এরকম:

redirect handler
   -> মেমরিতে একটা ছোট buffer-এ event ঠেলে দাও (non-blocking)
   -> রেসপন্স পাঠাও

background flusher (প্রতি ১ সেকেন্ড বা ১,০০০ event)
   -> batch করে event queue-তে পাঠাও (Kafka / Kinesis / SQS)

analytics worker
   -> queue থেকে পড়, aggregate করো
   -> columnar OLAP স্টোরে লেখো (ClickHouse / BigQuery)
   -> per-link per-hour rollup টেবিল আপডেট করো

এখানে কয়েকটা ব্যবহারিক সিদ্ধান্ত:

Buffer ভরে গেলে event ফেলে দিন, রিকোয়েস্ট ব্লক করবেন না। এটা ইচ্ছাকৃত: analytics হলো “best effort” ডেটা, আর একটা ক্লিক গণনা হারানোর চেয়ে একটা রিকোয়েস্ট ধীর হওয়া অনেক বেশি ক্ষতিকর। এই সিদ্ধান্তটা স্পষ্ট করে ডকুমেন্ট করে রাখুন, নইলে ছয় মাস পরে কেউ “ডেটা মিলছে না” বলে তদন্ত শুরু করবে।

Unique visitor গুনতে HyperLogLog ব্যবহার করুন, প্রতিটা ভিজিটরের আইডি জমিয়ে নয়। এতে ~২% ত্রুটি নিয়ে প্রতি লিংকে মাত্র ১২ KB-তে unique count পাওয়া যায়। কেউ ভিজিটর সংখ্যা নিখুঁতভাবে জানতে চায় না, কিন্তু সবাই সেটা দ্রুত জানতে চায়।

যে ফিল্ডগুলো ধরবেন: টাইমস্ট্যাম্প, short key, referrer, user agent থেকে বের করা device/browser, IP থেকে বের করা দেশ (IP নিজে নয়)। কাঁচা IP জমাবেন না — এটা ব্যক্তিগত ডেটা, আইনি দায়, আর দেশ বের করে ফেলার পরে এর কোনো ব্যবহার নেই।

দুই স্তরের গণনা। ইউজার তার ড্যাশবোর্ডে “মোট ক্লিক” দেখতে চায় — সেটা Redis-এ একটা counter দিয়ে প্রায়-রিয়েল-টাইম রাখুন (write-behind ধাঁচে, প্রতি মিনিটে DB-তে flush)। আর “গত ৩০ দিনের দৈনিক ভাঙানো, দেশভিত্তিক” — সেটা OLAP স্টোর থেকে আসুক। দুটো সম্পূর্ণ ভিন্ন query pattern, দুটোকে এক জায়গা থেকে সার্ভ করার চেষ্টা করলে দুটোই খারাপ হবে।

ধাপ ১১: ইমপ্লিমেন্টেশন

নিচে সিস্টেমের কেন্দ্রীয় অংশটা — base62 কোডেক, bijective scrambler, range-ভিত্তিক key allocator, create path (custom alias আর idempotency সহ), আর single-flight ও negative caching সমেত redirect hot path।

// ---------------------------------------------------------------------------
// URL shortener core:
//   1. base62 codec
//   2. bijective scrambler so sequential counters yield unguessable keys
//   3. range-allocating key generator (one central hit per 10k keys)
//   4. create path: custom alias, idempotency, collision fallback
//   5. redirect path: three cache layers, single-flight, negative caching
// ---------------------------------------------------------------------------

const ALPHABET = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789';
const KEY_LENGTH = 7;
const KEY_SPACE = 62n ** BigInt(KEY_LENGTH); // 3,521,614,606,208

// Any multiplier coprime with KEY_SPACE (= 2^7 * 31^7) makes the map bijective.
// 1046527 is prime and divides neither 2 nor 31, so it qualifies.
const MULTIPLIER = 1_046_527n;
const OFFSET = 987_654_321n;

const BLOCK_SIZE = 10_000;
const CACHE_TTL_SECONDS = 24 * 60 * 60;
const NEGATIVE_TTL_SECONDS = 60;
const LOCAL_CACHE_MAX = 200_000;

const RESERVED = new Set([
	'api',
	'v1',
	'admin',
	'login',
	'logout',
	'static',
	'assets',
	'health',
	'metrics',
	'robots.txt',
	'favicon.ico'
]);

// --- base62 ---------------------------------------------------------------

export function encodeBase62(value: bigint, length = KEY_LENGTH): string {
	let n = value;
	let out = '';
	for (let i = 0; i < length; i++) {
		out = ALPHABET[Number(n % 62n)] + out;
		n /= 62n;
	}
	return out;
}

export function decodeBase62(key: string): bigint {
	let n = 0n;
	for (const ch of key) {
		const idx = ALPHABET.indexOf(ch);
		if (idx === -1) throw new Error(`invalid base62 character: ${ch}`);
		n = n * 62n + BigInt(idx);
	}
	return n;
}

// --- bijective scrambling -------------------------------------------------

/** Extended Euclid: returns x such that (a * x) mod m === 1. */
function modInverse(a: bigint, m: bigint): bigint {
	let [oldR, r] = [a % m, m];
	let [oldS, s] = [1n, 0n];

	while (r !== 0n) {
		const q = oldR / r;
		[oldR, r] = [r, oldR - q * r];
		[oldS, s] = [s, oldS - q * s];
	}
	if (oldR !== 1n) throw new Error('multiplier is not coprime with the key space');
	return ((oldS % m) + m) % m;
}

const MULTIPLIER_INVERSE = modInverse(MULTIPLIER, KEY_SPACE);

/** Sequential counter -> shuffled value. Collision-free by construction. */
export function scramble(counter: bigint): bigint {
	return (counter * MULTIPLIER + OFFSET) % KEY_SPACE;
}

/** Recover the original counter — useful for debugging and for audits. */
export function unscramble(scrambled: bigint): bigint {
	const shifted = (((scrambled - OFFSET) % KEY_SPACE) + KEY_SPACE) % KEY_SPACE;
	return (shifted * MULTIPLIER_INVERSE) % KEY_SPACE;
}

// --- Ports ----------------------------------------------------------------

export interface LinkRow {
	shortKey: string;
	longUrl: string;
	ownerId: string | null;
	createdAt: number;
	expiresAt: number | null;
	isActive: boolean;
	redirectCode: 301 | 302 | 307;
}

/** Only the fields the redirect path needs — small entries mean more entries. */
export interface CachedLink {
	longUrl: string;
	expiresAt: number | null;
	isActive: boolean;
	redirectCode: 301 | 302 | 307;
}

export interface LinkStore {
	/** Must throw a unique-violation error when shortKey already exists. */
	insert(row: LinkRow): Promise<void>;
	findByKey(shortKey: string): Promise<LinkRow | null>;
	findByIdempotencyKey(key: string): Promise<LinkRow | null>;
	recordIdempotencyKey(key: string, shortKey: string): Promise<void>;
	isUniqueViolation(err: unknown): boolean;
}

export interface SharedCache {
	get(key: string): Promise<string | null>;
	setex(key: string, seconds: number, value: string): Promise<void>;
	del(key: string): Promise<void>;
	incrby(key: string, amount: number): Promise<number>;
}

export interface EventSink {
	/** Must never block the request. Dropping under pressure is acceptable. */
	emit(event: ClickEvent): void;
}

export interface ClickEvent {
	shortKey: string;
	at: number;
	referrer: string | null;
	userAgent: string | null;
	country: string | null;
}

// --- Key allocator --------------------------------------------------------

/**
 * Pulls a block of BLOCK_SIZE counters from the shared counter, then serves
 * them from memory. One central round trip per 10,000 keys instead of per key.
 * Unused counters are lost on restart — irrelevant against 3.5 trillion keys.
 */
export class KeyAllocator {
	private next = 0n;
	private end = 0n;
	private refilling: Promise<void> | null = null;

	constructor(
		private cache: SharedCache,
		private counterKey = 'shortener:counter',
		private blockSize = BLOCK_SIZE
	) {}

	async nextKey(): Promise<string> {
		if (this.next >= this.end) await this.refill();
		const counter = this.next++;
		return encodeBase62(scramble(counter));
	}

	private async refill(): Promise<void> {
		// Single-flight: concurrent callers share one refill round trip.
		if (!this.refilling) {
			this.refilling = (async () => {
				const end = await this.cache.incrby(this.counterKey, this.blockSize);
				this.end = BigInt(end);
				this.next = this.end - BigInt(this.blockSize);
				console.log(`[allocator] block ${this.next}..${this.end}`);
			})().finally(() => {
				this.refilling = null;
			});
		}
		await this.refilling;
	}
}

// --- Local LRU ------------------------------------------------------------

class LruCache<V> {
	private map = new Map<string, { value: V; expiresAt: number }>();

	constructor(private max: number) {}

	get(key: string): V | undefined {
		const entry = this.map.get(key);
		if (!entry) return undefined;
		if (Date.now() > entry.expiresAt) {
			this.map.delete(key);
			return undefined;
		}
		// Re-insert to mark as most recently used.
		this.map.delete(key);
		this.map.set(key, entry);
		return entry.value;
	}

	set(key: string, value: V, ttlMs: number): void {
		if (this.map.size >= this.max) {
			const oldest = this.map.keys().next().value;
			if (oldest !== undefined) this.map.delete(oldest);
		}
		this.map.set(key, { value, expiresAt: Date.now() + ttlMs });
	}

	delete(key: string): void {
		this.map.delete(key);
	}
}

// --- Write path -----------------------------------------------------------

export class CreateError extends Error {
	constructor(
		message: string,
		readonly code: 'INVALID_URL' | 'ALIAS_TAKEN' | 'ALIAS_RESERVED' | 'EXHAUSTED'
	) {
		super(message);
	}
}

export interface CreateRequest {
	url: string;
	alias?: string;
	ownerId?: string | null;
	expiresAt?: number | null;
	idempotencyKey?: string;
}

export class ShortenerWriteService {
	constructor(
		private store: LinkStore,
		private allocator: KeyAllocator
	) {}

	async create(req: CreateRequest): Promise<LinkRow> {
		const longUrl = normaliseUrl(req.url);

		// Replayed request? Return the original answer, not a second link.
		if (req.idempotencyKey) {
			const existing = await this.store.findByIdempotencyKey(req.idempotencyKey);
			if (existing) return existing;
		}

		const row = req.alias
			? await this.createWithAlias(req, longUrl)
			: await this.createGenerated(req, longUrl);

		if (req.idempotencyKey) {
			await this.store.recordIdempotencyKey(req.idempotencyKey, row.shortKey);
		}
		return row;
	}

	private async createWithAlias(req: CreateRequest, longUrl: string): Promise<LinkRow> {
		const alias = req.alias as string;

		if (RESERVED.has(alias.toLowerCase())) {
			throw new CreateError(`alias "${alias}" is reserved`, 'ALIAS_RESERVED');
		}
		if (!/^[A-Za-z0-9_-]{3,32}$/.test(alias)) {
			throw new CreateError(`alias "${alias}" has an invalid shape`, 'ALIAS_TAKEN');
		}

		const row = buildRow(alias, longUrl, req);
		try {
			await this.store.insert(row);
			return row;
		} catch (err) {
			if (this.store.isUniqueViolation(err)) {
				// Custom aliases share one namespace with generated keys, so the
				// unique index is the only thing that has to be right here.
				throw new CreateError(`alias "${alias}" is already taken`, 'ALIAS_TAKEN');
			}
			throw err;
		}
	}

	private async createGenerated(req: CreateRequest, longUrl: string): Promise<LinkRow> {
		// The allocator cannot collide by construction, but a custom alias may
		// have already claimed the same string. Defence in depth is cheap.
		for (let attempt = 0; attempt < 5; attempt++) {
			const shortKey = await this.allocator.nextKey();
			const row = buildRow(shortKey, longUrl, req);
			try {
				await this.store.insert(row);
				return row;
			} catch (err) {
				if (!this.store.isUniqueViolation(err)) throw err;
				console.warn(`[create] key ${shortKey} already taken, retrying`);
			}
		}
		throw new CreateError('could not allocate a free key after 5 attempts', 'EXHAUSTED');
	}
}

function buildRow(shortKey: string, longUrl: string, req: CreateRequest): LinkRow {
	return {
		shortKey,
		longUrl,
		ownerId: req.ownerId ?? null,
		createdAt: Date.now(),
		expiresAt: req.expiresAt ?? null,
		isActive: true,
		redirectCode: 302
	};
}

function normaliseUrl(raw: string): string {
	let parsed: URL;
	try {
		parsed = new URL(raw);
	} catch {
		throw new CreateError(`"${raw}" is not a valid absolute URL`, 'INVALID_URL');
	}
	if (parsed.protocol !== 'http:' && parsed.protocol !== 'https:') {
		throw new CreateError(`unsupported scheme: ${parsed.protocol}`, 'INVALID_URL');
	}
	// Lower-case host, drop the default port, keep path and query untouched.
	parsed.hostname = parsed.hostname.toLowerCase();
	if (
		(parsed.protocol === 'http:' && parsed.port === '80') ||
		(parsed.protocol === 'https:' && parsed.port === '443')
	) {
		parsed.port = '';
	}
	return parsed.toString();
}

// --- Read path ------------------------------------------------------------

export type Resolution =
	| { status: 'found'; longUrl: string; redirectCode: 301 | 302 | 307 }
	| { status: 'not_found' }
	| { status: 'gone' };

const NEGATIVE = 'missing';

export class RedirectService {
	private local = new LruCache<CachedLink | null>(LOCAL_CACHE_MAX);
	private inflight = new Map<string, Promise<CachedLink | null>>();

	constructor(
		private store: LinkStore,
		private cache: SharedCache,
		private events: EventSink
	) {}

	async resolve(shortKey: string, ctx: RequestContext): Promise<Resolution> {
		const link = await this.lookup(shortKey);

		if (!link || !link.isActive) return { status: 'not_found' };
		if (link.expiresAt !== null && Date.now() > link.expiresAt) return { status: 'gone' };

		// Fire and forget. Analytics must never sit on the redirect path.
		this.events.emit({
			shortKey,
			at: Date.now(),
			referrer: ctx.referrer,
			userAgent: ctx.userAgent,
			country: ctx.country
		});

		return { status: 'found', longUrl: link.longUrl, redirectCode: link.redirectCode };
	}

	private async lookup(shortKey: string): Promise<CachedLink | null> {
		// Layer 0: in-process, ~100 ns.
		const localHit = this.local.get(shortKey);
		if (localHit !== undefined) return localHit;

		// Single-flight: one database call per key, however many callers wait.
		const existing = this.inflight.get(shortKey);
		if (existing) return existing;

		const promise = this.loadThrough(shortKey).finally(() => {
			this.inflight.delete(shortKey);
		});
		this.inflight.set(shortKey, promise);
		return promise;
	}

	private async loadThrough(shortKey: string): Promise<CachedLink | null> {
		// Layer 1: shared Redis, ~0.5 ms.
		const raw = await this.cache.get(cacheKey(shortKey));
		if (raw === NEGATIVE) {
			this.local.set(shortKey, null, NEGATIVE_TTL_SECONDS * 1000);
			return null;
		}
		if (raw) {
			const link = JSON.parse(raw) as CachedLink;
			this.local.set(shortKey, link, localTtlMs(link));
			return link;
		}

		// Layer 2: the database. Reaching here should be rare.
		const row = await this.store.findByKey(shortKey);

		if (!row) {
			// Negative caching stops random-key scanners from hammering the DB.
			await this.cache.setex(cacheKey(shortKey), NEGATIVE_TTL_SECONDS, NEGATIVE);
			this.local.set(shortKey, null, NEGATIVE_TTL_SECONDS * 1000);
			return null;
		}

		const link: CachedLink = {
			longUrl: row.longUrl,
			expiresAt: row.expiresAt,
			isActive: row.isActive,
			redirectCode: row.redirectCode
		};

		await this.cache.setex(cacheKey(shortKey), ttlSecondsFor(link), JSON.stringify(link));
		this.local.set(shortKey, link, localTtlMs(link));
		return link;
	}

	/** Called after an update or a takedown so stale entries do not linger. */
	async invalidate(shortKey: string): Promise<void> {
		this.local.delete(shortKey);
		await this.cache.del(cacheKey(shortKey));
	}
}

export interface RequestContext {
	referrer: string | null;
	userAgent: string | null;
	country: string | null;
}

function cacheKey(shortKey: string): string {
	return `link:v1:${shortKey}`;
}

/**
 * Never cache a link for longer than it has left to live, and add jitter so a
 * batch of entries written together does not expire together (stampede).
 */
function ttlSecondsFor(link: CachedLink): number {
	const jitter = 0.9 + Math.random() * 0.2;
	let ttl = CACHE_TTL_SECONDS * jitter;
	if (link.expiresAt !== null) {
		const remaining = (link.expiresAt - Date.now()) / 1000;
		ttl = Math.min(ttl, Math.max(remaining, 1));
	}
	return Math.floor(ttl);
}

function localTtlMs(link: CachedLink): number {
	return Math.min(60_000, ttlSecondsFor(link) * 1000);
}

// --- HTTP handler ---------------------------------------------------------

export async function handleRedirect(
	service: RedirectService,
	shortKey: string,
	ctx: RequestContext
): Promise<Response> {
	const result = await service.resolve(shortKey, ctx);

	switch (result.status) {
		case 'found':
			return new Response(null, {
				status: result.redirectCode,
				headers: {
					Location: result.longUrl,
					// 302 must not be cached by proxies, or analytics silently vanish.
					'Cache-Control':
						result.redirectCode === 301 ? 'public, max-age=86400' : 'private, max-age=0',
					'Referrer-Policy': 'unsafe-url'
				}
			});
		case 'gone':
			return new Response('This link has expired.', { status: 410 });
		default:
			return new Response('No such link.', { status: 404 });
	}
}

package shortener

import (
	"context"
	"encoding/json"
	"errors"
	"fmt"
	"log"
	"math/rand"
	"net/http"
	"net/url"
	"regexp"
	"strings"
	"sync"
	"time"

	"golang.org/x/sync/singleflight"
)

// ---------------------------------------------------------------------------
// URL shortener core:
//   1. base62 codec
//   2. bijective scrambler so sequential counters yield unguessable keys
//   3. range-allocating key generator (one central hit per 10k keys)
//   4. create path: custom alias, idempotency, collision fallback
//   5. redirect path: three cache layers, single-flight, negative caching
// ---------------------------------------------------------------------------

const (
	alphabet         = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
	keyLength        = 7
	keySpace  uint64 = 3_521_614_606_208 // 62^7

	// Any multiplier coprime with keySpace (= 2^7 * 31^7) makes the map
	// bijective. 1046527 is prime and divides neither 2 nor 31.
	multiplier uint64 = 1_046_527
	offset     uint64 = 987_654_321

	blockSize        = 10_000
	cacheTTL         = 24 * time.Hour
	negativeTTL      = 60 * time.Second
	localCacheMax    = 200_000
	negativeSentinel = "\x00missing"
)

var reserved = map[string]bool{
	"api": true, "v1": true, "admin": true, "login": true, "logout": true,
	"static": true, "assets": true, "health": true, "metrics": true,
	"robots.txt": true, "favicon.ico": true,
}

var aliasPattern = regexp.MustCompile(`^[A-Za-z0-9_-]{3,32}$`)

// --- base62 ---------------------------------------------------------------

func EncodeBase62(value uint64, length int) string {
	buf := make([]byte, length)
	n := value
	for i := length - 1; i >= 0; i-- {
		buf[i] = alphabet[n%62]
		n /= 62
	}
	return string(buf)
}

func DecodeBase62(key string) (uint64, error) {
	var n uint64
	for _, ch := range key {
		idx := strings.IndexRune(alphabet, ch)
		if idx < 0 {
			return 0, fmt.Errorf("invalid base62 character: %q", ch)
		}
		n = n*62 + uint64(idx)
	}
	return n, nil
}

// --- bijective scrambling -------------------------------------------------

// modInverse returns x such that (a * x) mod m == 1, via extended Euclid.
func modInverse(a, m uint64) (uint64, error) {
	oldR, r := int64(a%m), int64(m)
	oldS, s := int64(1), int64(0)

	for r != 0 {
		q := oldR / r
		oldR, r = r, oldR-q*r
		oldS, s = s, oldS-q*s
	}
	if oldR != 1 {
		return 0, errors.New("multiplier is not coprime with the key space")
	}
	return uint64(((oldS % int64(m)) + int64(m)) % int64(m)), nil
}

var multiplierInverse = mustModInverse(multiplier, keySpace)

func mustModInverse(a, m uint64) uint64 {
	inv, err := modInverse(a, m)
	if err != nil {
		panic(err)
	}
	return inv
}

// Scramble maps a sequential counter to a shuffled value. Collision-free by
// construction: multiplier and keySpace are coprime, so the map is a bijection.
func Scramble(counter uint64) uint64 {
	// counter < keySpace (3.5e12) and multiplier ~1e6, so the product stays
	// below 3.7e18 and fits comfortably in uint64.
	return (counter%keySpace*multiplier + offset) % keySpace
}

// Unscramble recovers the original counter — useful for debugging and audits.
func Unscramble(scrambled uint64) uint64 {
	shifted := (scrambled + keySpace - offset%keySpace) % keySpace
	return shifted % keySpace * multiplierInverse % keySpace
}

// --- Ports ----------------------------------------------------------------

type LinkRow struct {
	ShortKey     string
	LongURL      string
	OwnerID      string
	CreatedAt    time.Time
	ExpiresAt    *time.Time
	IsActive     bool
	RedirectCode int
}

// CachedLink holds only what the redirect path needs — small entries mean
// more entries fit in the same memory.
type CachedLink struct {
	LongURL      string     `json:"longUrl"`
	ExpiresAt    *time.Time `json:"expiresAt"`
	IsActive     bool       `json:"isActive"`
	RedirectCode int        `json:"redirectCode"`
}

type LinkStore interface {
	// Insert must return an error satisfying IsUniqueViolation when the key exists.
	Insert(ctx context.Context, row LinkRow) error
	FindByKey(ctx context.Context, shortKey string) (*LinkRow, error)
	FindByIdempotencyKey(ctx context.Context, key string) (*LinkRow, error)
	RecordIdempotencyKey(ctx context.Context, key, shortKey string) error
	IsUniqueViolation(err error) bool
}

type SharedCache interface {
	Get(ctx context.Context, key string) (string, error) // "" means miss
	SetEx(ctx context.Context, key string, ttl time.Duration, value string) error
	Del(ctx context.Context, key string) error
	IncrBy(ctx context.Context, key string, amount int64) (int64, error)
}

type ClickEvent struct {
	ShortKey  string    `json:"shortKey"`
	At        time.Time `json:"at"`
	Referrer  string    `json:"referrer"`
	UserAgent string    `json:"userAgent"`
	Country   string    `json:"country"`
}

// EventSink must never block the request. Dropping under pressure is fine.
type EventSink interface {
	Emit(e ClickEvent)
}

// --- Key allocator --------------------------------------------------------

// KeyAllocator pulls a block of counters from the shared counter, then serves
// them from memory: one central round trip per 10,000 keys instead of per key.
// Unused counters are lost on restart — irrelevant against 3.5 trillion keys.
type KeyAllocator struct {
	mu         sync.Mutex
	next       uint64
	end        uint64
	cache      SharedCache
	counterKey string
	blockSize  int64
}

func NewKeyAllocator(cache SharedCache, counterKey string) *KeyAllocator {
	return &KeyAllocator{cache: cache, counterKey: counterKey, blockSize: blockSize}
}

func (a *KeyAllocator) NextKey(ctx context.Context) (string, error) {
	a.mu.Lock()
	defer a.mu.Unlock()

	if a.next >= a.end {
		end, err := a.cache.IncrBy(ctx, a.counterKey, a.blockSize)
		if err != nil {
			return "", err
		}
		a.end = uint64(end)
		a.next = a.end - uint64(a.blockSize)
		log.Printf("[allocator] block %d..%d", a.next, a.end)
	}

	counter := a.next
	a.next++
	return EncodeBase62(Scramble(counter), keyLength), nil
}

// --- Local LRU ------------------------------------------------------------

type lruEntry struct {
	link      *CachedLink // nil means a cached negative
	expiresAt time.Time
}

type localCache struct {
	mu    sync.Mutex
	items map[string]lruEntry
	max   int
}

func newLocalCache(max int) *localCache {
	return &localCache{items: make(map[string]lruEntry, max), max: max}
}

func (c *localCache) Get(key string) (*CachedLink, bool) {
	c.mu.Lock()
	defer c.mu.Unlock()

	entry, ok := c.items[key]
	if !ok {
		return nil, false
	}
	if time.Now().After(entry.expiresAt) {
		delete(c.items, key)
		return nil, false
	}
	return entry.link, true
}

func (c *localCache) Set(key string, link *CachedLink, ttl time.Duration) {
	c.mu.Lock()
	defer c.mu.Unlock()

	// Random eviction rather than strict LRU: with a skewed access pattern the
	// hot keys are re-inserted constantly anyway, and this stays allocation-free.
	if len(c.items) >= c.max {
		for k := range c.items {
			delete(c.items, k)
			break
		}
	}
	c.items[key] = lruEntry{link: link, expiresAt: time.Now().Add(ttl)}
}

func (c *localCache) Delete(key string) {
	c.mu.Lock()
	defer c.mu.Unlock()
	delete(c.items, key)
}

// --- Write path -----------------------------------------------------------

type CreateErrorCode string

const (
	ErrInvalidURL    CreateErrorCode = "INVALID_URL"
	ErrAliasTaken    CreateErrorCode = "ALIAS_TAKEN"
	ErrAliasReserved CreateErrorCode = "ALIAS_RESERVED"
	ErrExhausted     CreateErrorCode = "EXHAUSTED"
)

type CreateError struct {
	Code    CreateErrorCode
	Message string
}

func (e *CreateError) Error() string { return string(e.Code) + ": " + e.Message }

type CreateRequest struct {
	URL            string
	Alias          string
	OwnerID        string
	ExpiresAt      *time.Time
	IdempotencyKey string
}

type WriteService struct {
	store     LinkStore
	allocator *KeyAllocator
}

func NewWriteService(store LinkStore, allocator *KeyAllocator) *WriteService {
	return &WriteService{store: store, allocator: allocator}
}

func (s *WriteService) Create(ctx context.Context, req CreateRequest) (LinkRow, error) {
	longURL, err := normaliseURL(req.URL)
	if err != nil {
		return LinkRow{}, err
	}

	// Replayed request? Return the original answer, not a second link.
	if req.IdempotencyKey != "" {
		existing, err := s.store.FindByIdempotencyKey(ctx, req.IdempotencyKey)
		if err != nil {
			return LinkRow{}, err
		}
		if existing != nil {
			return *existing, nil
		}
	}

	var row LinkRow
	if req.Alias != "" {
		row, err = s.createWithAlias(ctx, req, longURL)
	} else {
		row, err = s.createGenerated(ctx, req, longURL)
	}
	if err != nil {
		return LinkRow{}, err
	}

	if req.IdempotencyKey != "" {
		if err := s.store.RecordIdempotencyKey(ctx, req.IdempotencyKey, row.ShortKey); err != nil {
			return LinkRow{}, err
		}
	}
	return row, nil
}

func (s *WriteService) createWithAlias(ctx context.Context, req CreateRequest, longURL string) (LinkRow, error) {
	if reserved[strings.ToLower(req.Alias)] {
		return LinkRow{}, &CreateError{ErrAliasReserved, "alias " + req.Alias + " is reserved"}
	}
	if !aliasPattern.MatchString(req.Alias) {
		return LinkRow{}, &CreateError{ErrAliasTaken, "alias " + req.Alias + " has an invalid shape"}
	}

	row := buildRow(req.Alias, longURL, req)
	if err := s.store.Insert(ctx, row); err != nil {
		if s.store.IsUniqueViolation(err) {
			// Custom aliases share one namespace with generated keys, so the
			// unique index is the only thing that has to be right here.
			return LinkRow{}, &CreateError{ErrAliasTaken, "alias " + req.Alias + " is already taken"}
		}
		return LinkRow{}, err
	}
	return row, nil
}

func (s *WriteService) createGenerated(ctx context.Context, req CreateRequest, longURL string) (LinkRow, error) {
	// The allocator cannot collide by construction, but a custom alias may
	// have already claimed the same string. Defence in depth is cheap.
	for attempt := 0; attempt < 5; attempt++ {
		shortKey, err := s.allocator.NextKey(ctx)
		if err != nil {
			return LinkRow{}, err
		}

		row := buildRow(shortKey, longURL, req)
		if err := s.store.Insert(ctx, row); err != nil {
			if s.store.IsUniqueViolation(err) {
				log.Printf("[create] key %s already taken, retrying", shortKey)
				continue
			}
			return LinkRow{}, err
		}
		return row, nil
	}
	return LinkRow{}, &CreateError{ErrExhausted, "could not allocate a free key after 5 attempts"}
}

func buildRow(shortKey, longURL string, req CreateRequest) LinkRow {
	return LinkRow{
		ShortKey:     shortKey,
		LongURL:      longURL,
		OwnerID:      req.OwnerID,
		CreatedAt:    time.Now(),
		ExpiresAt:    req.ExpiresAt,
		IsActive:     true,
		RedirectCode: http.StatusFound,
	}
}

func normaliseURL(raw string) (string, error) {
	parsed, err := url.Parse(raw)
	if err != nil || !parsed.IsAbs() {
		return "", &CreateError{ErrInvalidURL, raw + " is not a valid absolute URL"}
	}
	if parsed.Scheme != "http" && parsed.Scheme != "https" {
		return "", &CreateError{ErrInvalidURL, "unsupported scheme: " + parsed.Scheme}
	}

	// Lower-case host, drop the default port, keep path and query untouched.
	host := strings.ToLower(parsed.Hostname())
	port := parsed.Port()
	if (parsed.Scheme == "http" && port == "80") || (parsed.Scheme == "https" && port == "443") {
		port = ""
	}
	if port != "" {
		host = host + ":" + port
	}
	parsed.Host = host

	return parsed.String(), nil
}

// --- Read path ------------------------------------------------------------

type ResolutionStatus string

const (
	StatusFound    ResolutionStatus = "found"
	StatusNotFound ResolutionStatus = "not_found"
	StatusGone     ResolutionStatus = "gone"
)

type Resolution struct {
	Status       ResolutionStatus
	LongURL      string
	RedirectCode int
}

type RequestContext struct {
	Referrer  string
	UserAgent string
	Country   string
}

type RedirectService struct {
	store  LinkStore
	cache  SharedCache
	events EventSink
	local  *localCache
	group  singleflight.Group
}

func NewRedirectService(store LinkStore, cache SharedCache, events EventSink) *RedirectService {
	return &RedirectService{
		store:  store,
		cache:  cache,
		events: events,
		local:  newLocalCache(localCacheMax),
	}
}

func (s *RedirectService) Resolve(ctx context.Context, shortKey string, rc RequestContext) (Resolution, error) {
	link, err := s.lookup(ctx, shortKey)
	if err != nil {
		return Resolution{}, err
	}

	if link == nil || !link.IsActive {
		return Resolution{Status: StatusNotFound}, nil
	}
	if link.ExpiresAt != nil && time.Now().After(*link.ExpiresAt) {
		return Resolution{Status: StatusGone}, nil
	}

	// Fire and forget. Analytics must never sit on the redirect path.
	s.events.Emit(ClickEvent{
		ShortKey:  shortKey,
		At:        time.Now(),
		Referrer:  rc.Referrer,
		UserAgent: rc.UserAgent,
		Country:   rc.Country,
	})

	return Resolution{Status: StatusFound, LongURL: link.LongURL, RedirectCode: link.RedirectCode}, nil
}

func (s *RedirectService) lookup(ctx context.Context, shortKey string) (*CachedLink, error) {
	// Layer 0: in-process, ~100 ns.
	if link, ok := s.local.Get(shortKey); ok {
		return link, nil
	}

	// Single-flight: one database call per key, however many callers wait.
	v, err, _ := s.group.Do(shortKey, func() (any, error) {
		return s.loadThrough(ctx, shortKey)
	})
	if err != nil {
		return nil, err
	}
	link, _ := v.(*CachedLink)
	return link, nil
}

func (s *RedirectService) loadThrough(ctx context.Context, shortKey string) (*CachedLink, error) {
	ck := cacheKey(shortKey)

	// Layer 1: shared Redis, ~0.5 ms.
	raw, err := s.cache.Get(ctx, ck)
	if err != nil {
		log.Printf("[cache] get failed for %s: %v", shortKey, err)
	}
	if raw == negativeSentinel {
		s.local.Set(shortKey, nil, negativeTTL)
		return nil, nil
	}
	if raw != "" {
		var link CachedLink
		if err := json.Unmarshal([]byte(raw), &link); err == nil {
			s.local.Set(shortKey, &link, localTTL(&link))
			return &link, nil
		}
	}

	// Layer 2: the database. Reaching here should be rare.
	row, err := s.store.FindByKey(ctx, shortKey)
	if err != nil {
		return nil, err
	}

	if row == nil {
		// Negative caching stops random-key scanners from hammering the DB.
		_ = s.cache.SetEx(ctx, ck, negativeTTL, negativeSentinel)
		s.local.Set(shortKey, nil, negativeTTL)
		return nil, nil
	}

	link := &CachedLink{
		LongURL:      row.LongURL,
		ExpiresAt:    row.ExpiresAt,
		IsActive:     row.IsActive,
		RedirectCode: row.RedirectCode,
	}

	if encoded, err := json.Marshal(link); err == nil {
		_ = s.cache.SetEx(ctx, ck, ttlFor(link), string(encoded))
	}
	s.local.Set(shortKey, link, localTTL(link))
	return link, nil
}

// Invalidate is called after an update or a takedown so stale entries do not linger.
func (s *RedirectService) Invalidate(ctx context.Context, shortKey string) error {
	s.local.Delete(shortKey)
	return s.cache.Del(ctx, cacheKey(shortKey))
}

func cacheKey(shortKey string) string { return "link:v1:" + shortKey }

// ttlFor never caches a link for longer than it has left to live, and adds
// jitter so entries written together do not expire together (stampede).
func ttlFor(link *CachedLink) time.Duration {
	jitter := 0.9 + rand.Float64()*0.2
	ttl := time.Duration(float64(cacheTTL) * jitter)

	if link.ExpiresAt != nil {
		remaining := time.Until(*link.ExpiresAt)
		if remaining < time.Second {
			remaining = time.Second
		}
		if remaining < ttl {
			ttl = remaining
		}
	}
	return ttl
}

func localTTL(link *CachedLink) time.Duration {
	if ttl := ttlFor(link); ttl < time.Minute {
		return ttl
	}
	return time.Minute
}

// --- HTTP handler ---------------------------------------------------------

func (s *RedirectService) Handler() http.HandlerFunc {
	return func(w http.ResponseWriter, r *http.Request) {
		shortKey := strings.TrimPrefix(r.URL.Path, "/")
		if shortKey == "" {
			http.NotFound(w, r)
			return
		}

		res, err := s.Resolve(r.Context(), shortKey, RequestContext{
			Referrer:  r.Referer(),
			UserAgent: r.UserAgent(),
			Country:   r.Header.Get("CF-IPCountry"),
		})
		if err != nil {
			http.Error(w, "temporarily unavailable", http.StatusServiceUnavailable)
			return
		}

		switch res.Status {
		case StatusFound:
			// 302 must not be cached by proxies, or analytics silently vanish.
			if res.RedirectCode == http.StatusMovedPermanently {
				w.Header().Set("Cache-Control", "public, max-age=86400")
			} else {
				w.Header().Set("Cache-Control", "private, max-age=0")
			}
			w.Header().Set("Referrer-Policy", "unsafe-url")
			http.Redirect(w, r, res.LongURL, res.RedirectCode)
		case StatusGone:
			http.Error(w, "This link has expired.", http.StatusGone)
		default:
			http.Error(w, "No such link.", http.StatusNotFound)
		}
	}
}

ধাপ ১২: ১০x আর ১০০x-এ কী বদলায়

একটা ডিজাইন সম্পূর্ণ হয় না যতক্ষণ না আপনি বলতে পারেন সেটা কোথায় ভাঙবে। এই অভ্যাসটাই সিনিয়র আর জুনিয়র উত্তরের মধ্যে সবচেয়ে বড় পার্থক্য।

১০x — ১২০,০০০ reads/sec, ৩৯০ writes/sec

মূল পরিবর্তনটা আসলে আর্কিটেকচারাল নয় — পরিমাণগত। ডিজাইনের আকৃতি একই থাকে। এটাই একটা ভালো ডিজাইনের লক্ষণ: ১০x স্কেলে যদি বাক্সগুলো একই থাকে আর শুধু সংখ্যাগুলো বাড়ে, তাহলে আপনি সঠিক সীমানায় ভাগ করেছেন।

১০০x — ১,২০০,০০০ reads/sec, ৩,৯০০ writes/sec

এখানে আকৃতি বদলায়।

Redirect edge-এ চলে যায়। ৬ নম্বর চ্যাপ্টারের ভৌত সীমাটা মনে করুন: ঢাকা থেকে ভার্জিনিয়া round trip ~২৪০ ms, আর কোনো অপটিমাইজেশন সেটা কমাবে না। এই স্কেলে ইউজাররা বিশ্বজুড়ে, তাই redirect লজিকটা CDN edge-এ (Cloudflare Workers, Lambda@Edge) চালানো উচিত, একটা replicated edge KV স্টোর সহ। তখন ৯০%+ redirect কখনো origin-এ পৌঁছায়ই না, আর latency ২৪০ ms থেকে ২০ ms-এ নামে। এটাই সবচেয়ে বড় একক উন্নতি — এবং লক্ষ করুন, এটা কোনো ডেটাবেস অপটিমাইজেশন নয়, এটা ভূগোল।

ডেটাবেস shard হয়। ১৮০ TB আর কোনো একক মেশিনে ধরে না। Shard key স্বাভাবিকভাবেই short_key — কারণ ৯৯% query ঠিক ওই একটা কলাম দিয়েই আসে, আর key-গুলো scramble করা বলে সেগুলো এমনিতেই সমানভাবে ছড়ানো। এটা একটা বিরল সৌভাগ্য: এই সিস্টেমের access pattern sharding-এর জন্য নিখুঁত, কোনো cross-shard query নেই, কোনো hot shard নেই।

Key allocator বহু-অঞ্চলে ভাগ হয়। একটামাত্র global counter নিয়ে বিশ্বজুড়ে coordination করার কোনো মানে নেই। সমাধান — counter-এর উপরের কয়েকটা বিট region-এর জন্য বরাদ্দ করুন, যাতে প্রতিটা region সম্পূর্ণ স্বাধীনভাবে key বানাতে পারে আর তবুও কখনো সংঘর্ষ না হয়। (এটা মূলত snowflake id-র একই ধারণা, আর ১৪ নম্বর চ্যাপ্টারে সেটা আবার দেখবেন।)

Analytics-এ sampling ঢোকে। সেকেন্ডে ১২ লাখ event মানে দিনে ১০০ বিলিয়ন — এগুলো সবই সংরক্ষণ করা অর্থনৈতিকভাবে অযৌক্তিক। জনপ্রিয় লিংকে ১% নমুনা নিয়ে ১০০ দিয়ে গুণ করলে যথেষ্ট নির্ভুল উত্তর পাওয়া যায়, আর কম-ট্রাফিক লিংকে ১০০% রাখা যায়। এই মিশ্র কৌশলটা বাস্তব সব বড় analytics সিস্টেমে আছে।

Abuse প্রতিরোধ আর ঐচ্ছিক থাকে না। এই স্কেলে শর্টনার স্প্যামার আর ফিশারদের প্রিয় যন্ত্র। লাগবে: create-এ per-API-key rate limit, নতুন লিংকের গন্তব্য একটা ম্যালওয়্যার-তালিকার বিরুদ্ধে যাচাই, সন্দেহজনক লিংকের জন্য interstitial সতর্কতা পাতা, আর একটা দ্রুত takedown পথ যা cache-ও তৎক্ষণাৎ invalidate করে।

ফেইলিওর মোড

চ্যাপ্টার ১–৬ কোথায় কাজে লাগল

এই ডিজাইনের একটাও সিদ্ধান্ত শূন্য থেকে আসেনি। মিলিয়ে নিন:

চ্যাপ্টার ১ — সিস্টেম ডিজাইন আসলে কী। পুরো চ্যাপ্টারে একটাও “সেরা” সমাধান ছিল না, ছিল কেবল trade-off। counter বনাম random, ৩০১ বনাম ৩০২, lazy expiry বনাম batch cleanup — প্রতিটাতেই প্রশ্নটা ছিল “কোনটা ভালো” নয়, “আমাদের সীমাবদ্ধতায় কোনটা উপযুক্ত”।

চ্যাপ্টার ২ — Requirements ও Constraints। ধাপ ১-এ functional আর non-functional আলাদা করা, আর বিশেষ করে redirect ও create-এর জন্য আলাদা availability লক্ষ্য বসানো — সেই আলাদা করাটাই পরে ধাপ ৬-এ দুটোকে আলাদা সার্ভিসে ভাগ করার যুক্তি দিয়েছে। Non-functional requirement আর্কিটেকচার ঠিক করে, functional requirement শুধু ফিচার ঠিক করে।

চ্যাপ্টার ৩ — Estimation। ধাপ ২-এর হিসাবগুলো পুরো ডিজাইন চালিয়েছে। read:write ১০০:১ থেকে এসেছে “সব শক্তি read path-এ”। ১.৮ TB থেকে এসেছে “sharding লাগবে না”। ৬২^৭ থেকে এসেছে “৭ অক্ষর”। ৫ GB cache থেকে এসেছে “একটা Redis যথেষ্ট”। একটাও সংখ্যা বাদ দিলে সেই সিদ্ধান্তটা আন্দাজে নিতে হতো।

চ্যাপ্টার ৪ — একটা রিকোয়েস্টের শরীরবৃত্ত। Redirect hot path-এর প্রতিটা হপ — load balancer, app, local cache, Redis, DB — সেই চ্যাপ্টারের মানচিত্রেরই একটা উদাহরণ। আর idempotency key-র প্রয়োজনীয়তা এসেছে সেখান থেকেই: যেখানে timeout সম্ভব, সেখানে retry অনিবার্য, আর যেখানে retry আছে সেখানে duplicate অনিবার্য।

চ্যাপ্টার ৫ — ডেটা স্টোর বেছে নেওয়া। ধাপ ৫-এ আমরা প্রথমে access pattern লিখেছি, তারপর স্টোর বেছেছি — উল্টোটা নয়। আর সিদ্ধান্তটা ছিল “সরলতম যেটা কাজ করে”: একটা relational ডেটাবেস, কারণ ১.৮ TB আর ৩৯ writes/sec-এ আর কিছুর দরকার নেই।

চ্যাপ্টার ৬ — Latency Numbers ও Percentile। তিন স্তরের ক্যাশের যুক্তিটা সরাসরি সেই টেবিল থেকে: মেমরি ১০০ ns, Redis ০.৫ ms, ডিস্ক ১৫০ µs, ক্রস-রিজিয়ন ২৪০ ms। আর analytics-কে hot path থেকে সরানোর কারণটাও সেখান থেকেই — p99 কোনো প্রান্তিক ঘটনা নয়, এবং একটা read path-এ একটা write জুড়ে দিলে সেই p99 আর কখনো ঠিক হবে না।