Web Services১২ মিনিট পাঠ

URL শর্টনার ডিজাইন (Design a URL Shortener)

স্কেলে দীর্ঘ লিংকগুলোকে ছোট করে তুলুন

scope:বাস্তব জগতের সিস্টেম (Real-World System)difficulty:মাঝারি

সমস্যাটি বোঝা

আপনি bit.ly/x7Kp2-এর মতো ছোট লিংকগুলোর কথা তো জানেন, যেগুলো কোনো একটি লম্বা URL-এ রিডিরেক্ট করে নিয়ে যায়? চলুন স্ক্র্যাচ থেকে একটি ডিজাইন করা যাক।

প্রথমে, চলুন রিকোয়ারমেন্টগুলো বা প্রয়োজনীয়তাগুলো ঠিক করি (মনে রাখবেন: ডিজাইন করার আগে সবসময় সব পরিষ্কার করে নিতে হয়!):

ফাংশনাল রিকোয়ারমেন্ট (ব্যবহারিক প্রয়োজনীয়তা):

একটি লম্বা URL দিলে, এটি একটি ছোট, ইউনিক রেসপন্স জেনারেট বা তৈরি করবে।
যখন কোনো ব্যবহারকারী ছোট URL-টিতে ভিজিট করবে, এটি তাকে আসল লম্বা URL-এ রিডিরেক্ট করবে।
ব্যবহারকারীরা ঐচ্ছিকভাবে কাস্টম শর্ট URL সেট করতে পারবে।
একটি নির্দিষ্ট সময় শেষ হওয়ার পর লিংকগুলো এক্সপায়ার (Expire) বা মেয়াদোত্তীর্ণ হয়ে যাবে (ঐচ্ছিক)।

নন-ফাংশনাল রিকোয়ারমেন্ট (অ-ব্যবহারিক প্রয়োজনীয়তা):

রিড-হেভি (Read-heavy): রাইট (link তৈরি) এর চেয়ে অনেক বেশি রিড (রিডিরেক্ট) হবে। রেশিও বা অনুপাত হলো ~১০০:১।
লো ল্যাটেন্সি (Low latency): রিডিরেক্ট খুব দ্রুত হতে হবে (< ১০০ms)। কেউ ধীরগতির রিডিরেক্ট চায় না।
হাই অ্যাভেইলেবিলিটি (High availability): সার্ভিসটি কখনোই ডাউন থাকা যাবে না। ব্রোকেন বা ভাঙা লিংক ব্যবহারকারীদের জন্য খুবই বাজে অভিজ্ঞতা।
প্রেডিক্ট করা বা অনুমান যোগ্য নয়: শর্ট URL গুলো সহজে অনুমান করা যায় এমন হওয়া উচিত নয় (নিরাপত্তার জন্য)।

▸ আইডিয়া: লম্বা URL → ছোট URL

এস্টিমেশন (Estimation) বা অনুমান

চলুন এই সিস্টেমের সাইজ বা আকার অনুমান করি:

প্রতি মাসে ১০০ মিলিয়ন নতুন URL (রাইট/writes): ~৪০ URL/সেকেন্ড
রিড:রাইট অনুপাত ১০০:১: ~৪,০০০ রিডিরেক্ট/সেকেন্ড, সর্বোচ্চ (Peak) ~১২,০০০/সেকেন্ড
প্রতি URL-এর জন্য স্টোরেজ: শর্ট URL (৭ চার বা ক্যারেক্টার) + লং URL (~২০০ চার গড়) + মেটাডেটা (~১০০ বাইট) ≈ ৫০০ বাইট
৫ বছরের জন্য স্টোরেজ: ১০০ মিলিয়ন × ১২ × ৫ × ৫০০B = ৩ TB
ক্যাশ (Cache): যদি আমরা উপরের ২০% হট URL কে ক্যাশ করি (Pareto principle বা প্যারেটো নীতি অনুসারে), তবে তা হবে ~৬০০ GB ক্যাশ

এটি একটি ম্যানেজেবল বা নিয়ন্ত্রণযোগ্য সিস্টেম। এর প্রধান চ্যালেঞ্জগুলো হলো খুব দক্ষভাবে ইউনিক শর্ট কোড তৈরি করা এবং রিড-হেভি ওয়ার্কলোড বা কাজ সামলানো।

API ডিজাইন

এটিকে সহজ রাখার চেষ্টা করুন:

ছোট URL তৈরি করা

এন্ডপয়েন্ট	`POST /api/v1/urls`
রিকোয়েস্ট	`{"long_url": "https://very-long-url.com/...", "custom_alias": "my-link", "expires_at": "2025-12-31"}`
রেসপন্স	`{"short_url": "https://short.ly/x7Kp2", "long_url": "...", "created_at": "..."}`
স্ট্যাটাস	`201 Created`

রিডিরেক্ট

এন্ডপয়েন্ট	`GET /:shortCode`
রেসপন্স	`301 Moved Permanently` অথবা `302 Found`
হেডার	`Location: https://very-long-url.com/...`

৩০১ বনাম ৩০২ (301 vs 302): একটি 301 স্ট্যাটাস ব্রাউজারকে বলে যে এটি চিরতরে রিডিরেক্ট করা হয়েছে — এতে সার্ভারে লোড কম হয়, কিন্তু আপনি ক্লিক অ্যানালিটিক্স বা ট্র্যাকিং করতে পারবেন না। অপরদিকে 302 মানে হলো ব্রাউজার আপনার সার্ভারে প্রতিবার চেক করবে — এতে সার্ভারে লোড বেশি হয়, কিন্তু আপনি ক্লিকগুলো ট্র্যাক করতে পারবেন। বেশিরভাগ URL শর্টনার অ্যানালিটিক্সের জন্য 302 ব্যবহার করে।

▸ রাইট ফ্লো (Write flow): ছোট URL তৈরি করা

Click chart to zoom

রাইট পাথ (Write path): API প্রথমে KGS থেকে একটি প্রি-জেনারেটেড কী সংগ্রহ করে, ডাটাবেসে ম্যাপিং স্টোর করে, এবং এরপর তা ক্যাশ করে

▸ রিড ফ্লো (Read flow): অরিজিনাল বা আসল URL-এ রিডিরেক্ট করা

Click chart to zoom

রিড পাথ (Read path): ক্যাশ-ফার্স্ট বা প্রথমে ক্যাশে চেক করার পদ্ধতিটি হট বা খুব বেশি ব্যবহৃত বা রিকোয়েস্ট করা URL-গুলোর ক্ষেত্রে রিডিরেক্টের সময় ৫-এর কম মিলিসেকেন্ডের ভেতর রাখে

শর্ট URL-গুলোর জন্য Base62 এনকোডিং

import hashlib
import time
import random

BASE62 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

def base62_encode(num: int) -> str:
    """Convert a number to a base62 string."""
    if num == 0:
        return BASE62[0]
    result = []
    while num > 0:
        result.append(BASE62[num % 62])
        num //= 62
    return "".join(reversed(result))

def base62_decode(s: str) -> int:
    """Convert a base62 string back to a number."""
    num = 0
    for char in s:
        num = num * 62 + BASE62.index(char)
    return num

# Method 1: Hash the URL and take the first 7 characters
def hash_approach(long_url: str) -> str:
    """MD5 hash → take first 43 bits → base62 encode."""
    hash_hex = hashlib.md5(long_url.encode()).hexdigest()
    hash_int = int(hash_hex[:11], 16)  # Take first 43 bits
    return base62_encode(hash_int)[:7]

# Method 2: Auto-incrementing counter → base62
def counter_approach(counter: int) -> str:
    """Global counter → base62 encode. Guaranteed unique!"""
    return base62_encode(counter)

# How many unique URLs can 7-char base62 hold?
print(f"7-char base62 capacity: {62**7:,} URLs")  # 3.5 trillion!
print(f"6-char base62 capacity: {62**6:,} URLs")  # 56 billion

# Examples
print(f"\nHash: {hash_approach('https://example.com/very/long/path')}")
print(f"Counter 1000: {counter_approach(1000)}")
print(f"Counter 1000000: {counter_approach(1000000)}")

# Decode round-trip
short = base62_encode(123456789)
print(f"\nEncode 123456789 → {short}")
print(f"Decode {short} → {base62_decode(short)}")

Output

7-char base62 capacity: 3,521,614,606,208 URLs
6-char base62 capacity: 56,800,235,584 URLs

Hash: kPx9dME
Counter 1000: g8
Counter 1000000: 4c92

Encode 123456789 → 8M0kX
Decode 8M0kX → 123456789

কী (Key) তৈরির পদ্ধতি: হ্যাশ (Hash) বনাম কাউন্টার (Counter)

কোর চ্যালেঞ্জ বা মূল সমস্যা হলো: আপনি কীভাবে এমন ইউনিক এবং ছোট কী তৈরি করবেন যা কেউ অনুমান করতে পারবে না?

পদ্ধতি ১: URL হ্যাশ (Hash) করা

লম্বা URL-টি হ্যাশ করা হয় (MD5 বা SHA-256 দিয়ে), তারপর প্রথম ৭টি অক্ষর (base62-তে এনকোডেড) নেয়া হয়।
সমস্যা: কলিশন (Collisions) বা সংঘর্ষ! দুটি ভিন্ন URL থেকে একই শর্ট কোড জেনারেট হতে পারে। আপনাকে ডাটাবেসে চেক করতে হবে এবং যদি কলিশন ঘটে তবে একটি সল্ট (salt) যোগ করে পুনরায় চেষ্টা করতে হবে।
সুবিধা: একই লম্বা URL সবসময় একই শর্ট URL রিটার্ন করতে পারে (ডুপ্লিকেশন ঠেকায়)।

পদ্ধতি ২: অটো-ইনক্রিমেন্টিং কাউন্টার (Auto-incrementing counter) + base62

একটি গ্লোবাল বা সেন্ট্রাল কাউন্টার ব্যবহার করা হয় (যেমন একটি ডাটাবেস সিকোয়েন্স বা Twitter Snowflake-এর মতো ডিস্ট্রিবিউটেড আইডি জেনারেটর)। তারপর কাউন্টারটিকে base62-তে রূপান্তর করা হয়।
সমস্যা: সিকোয়েনশিয়াল (Sequential) বা ধারাবাহিকভাবে আইডি বের হওয়ায় এটি খুব সহজেই প্রেডিক্ট বা অনুমান করা যায়। কোনো আক্রমণকারী যদি /x7Kp2-এর কথা জানে, তবে সে /x7Kp3-ও অনুমান করতে পারে। এর সমাধান: বিটগুলো শাফেল বা অদলবদল করা বা র‍্যান্ডমনেস (randomness) যোগ করা।
সুবিধা: ইউনিক হওয়ার শতভাগ গ্যারান্টি। রাইট করার সময় কোনো কলিশন চেক করার দরকার নেই।

পদ্ধতি ৩: প্রি-জেনারেটেড কী সার্ভিস (KGS - Pre-generated Key Service)

একটি আলাদা সার্ভিস লাখ লাখ র‍্যান্ডম বা র্যান্ডম ইউনিক কী আগে থেকেই তৈরি করে জমিয়ে রাখে। যখন কোনো নতুন URL তৈরি করার দরকার হয়, তখন এটি সেই পুল বা ভাণ্ডার থেকে একটি কী সংগ্রহ করে।
রাইট করার সময় কোনো কলিশনের ভয় নেই। কোনো সিকোয়েনশিয়াল প্যাটার্নের ভয় নেই। এটি অত্যন্ত দ্রুত।
KGS-কে শুধু এতটুকু নিশ্চিত করতে হয় যে ব্যবহৃত কীগুলো পুনরায় ব্যবহার করা হচ্ছে না (সেগুলোকে অ্যাটমিকভাবে "used" চিহ্নিত করতে হয়)।
ইন্টারভিউয়ের জন্য এটিই সবচেয়ে ভালো উপায় — এটি সহজেই সিস্টেমের বিভিন্ন অংশের কাজকে আলাদা করে।

▸ Base62 এনকোডিংয়ের মাধ্যমে কী (Key) জেনারেট

হাই-লেভেল আর্কিটেকচার

চলুন সবকিছু একটি সাথে যুক্ত করা যাক:

রাইট পাথ (Write path) - ছোট URL তৈরি করা:

ক্লায়েন্ট লম্বা URL-এর সাথে POST /api/v1/urls রিকোয়েস্ট করে।
API সার্ভার কী জেনারেশন সার্ভিস (Key Generation Service) থেকে বা কাছ থেকে একটি ইউনিক কী রিকোয়েস্ট করে।
API সার্ভার ডাটাবেসে ম্যাপিংটি (short_key → long_url) স্টোর বা সংরক্ষণ করে।
API সার্ভার ক্যাশে সেই ডেটা স্টোর করে (write-through)।
এর পর এটি ক্লায়েন্টকে ছোট URL-টি রিটার্ন করে।

রিড পাথ (Read path) - আসল URL-এ রিডিরেক্ট করা:

ক্লায়েন্ট GET /x7Kp2 লিকে ভিজিট করে।
API সার্ভার ক্যাশ (Redis) চেক করে। ক্যাশে পাওয়া গেলে (Cache hit)? দেরি না করে বা সাথে সাথে 302 রিডিরেক্ট রেসপন্স দেয়।
ক্যাশে না পাওয়া গেলে (Cache miss)? ডাটাবেসে খোঁজ করে, তারপর সেটিকে ক্যাশ করে এবং 302 রিডিরেক্ট করে।

কম্পোনেন্টসমূহ (Components):

লোড ব্যালান্সার — সমস্ত ট্র্যাফিককে API সার্ভারগুলোর মাঝে লোড ব্যাল্যান্স করে।
API সার্ভারসমূহ (স্টেটলেস) — URL তৈরি এবং রিডিরেক্ট করার মূল লজিক নিয়ন্ত্রণ করে।
কী জেনারেশন সার্ভিস (KGS) — এটি নিজে থেকেই প্রয়োজনীয় ছোট ইউনিক কী আগে থেকে তৈরি করে রাখে।
ডাটাবেস — URL গুলোর ম্যাপিং স্টোর করে। এখানে NoSQL (DynamoDB, Cassandra) খুবই দুর্দান্ত কাজ করে — কারণ এতে কোনো জটিল কুয়েরি ছাড়াই খুব সাধারণ কী-ভ্যালু (key-value) এর মাধ্যমে ডেটা পাওয়া যায়।
ক্যাশ (Cache) (যেমন, Redis) — এটি হট URL (Hot URL) বা যে সমস্ত URL গুলো খুব বেশি ব্যবহৃত হয় সেগুলোর ম্যাপিং ক্যাশ করে। 80/20 নিয়ম অনুযায়ী, ২০% হট URL ক্যাশ করলেই ~৮০% রিড খুব সহজেই সামলানো যায়।
অ্যানালিটিক্স সার্ভিস — ব্যবহারকারীদের লিংকের ওপর ক্লিকের স্ট্যাট ট্র্যাক করার জন্য মেসেজ কিউ এর মাধ্যমে অ্যাসিঙ্ক্রোনাস লগিং-এর কাজ করে।

▸ সম্পূর্ণ আর্কিটেকচার: সবগুলো কম্পোনেন্ট একসাথে

Note: কী জেনারেশন সার্ভিসটিকে আপনি একটি ব্যাংকের সিরিয়াল টিকিট প্রিন্ট করার মেশিনের মতো ভাবতে পারেন। এটি আগে থেকেই প্রতিটি টিকিটে নম্বর প্রিন্ট করার জন্য প্রস্তুত থাকে। যখন কোনো কাস্টমার আসে, আপনি শুধু তাকে পরের সিরিয়াল টিকিটটি দিয়ে দেন — আপনাকে সেই মুহূর্তে নতুন কোনো নম্বর নিয়ে ভাবতে হয় না। এটি অত্যন্ত দ্রুত, ইউনিক এবং সিম্পল কাজ করে।

ডাটাবেস নির্বাচন এবং স্কিমা (Schema)

এটি মূলত একটি কী-ভ্যালু ওয়ার্কলোড: একটি নির্দিষ্ট ছোট কী-র (key) বিপরীতে লম্বা URL-টি ফেরত দেয়। এখানে NoSQL ডাটাবেস যেমন DynamoDB বা Cassandra দারুণভাবে কাজ করে।

যদি সহজভাবে বোঝার জন্য SQL ব্যবহার করা হয়, তবে এর স্কিমা হবে অনেকটা এরকম:

urls টেবিল:

short_key (VARCHAR 7, PRIMARY KEY) — ছোট কোডটি
long_url (TEXT) — আসল লম্বা URL-টি
user_id (BIGINT) — কে এটি তৈরি করেছে (nullable)
created_at (TIMESTAMP) — এটি কখন তৈরি হয়েছে
expires_at (TIMESTAMP) — এর মেয়াদ কখন শেষ হবে (nullable)
click_count (BIGINT) — কতবার রিডিরেক্ট হয়েছে বা ক্লিক হয়েছে

ডুপ্লিকেট চেক (Duplicate check) করতে চাইলে long_url-এর ওপর ইনডেক্স ব্যবহার করতে পারেন (এতে একই লম্বা URL এর জন্য দুটি ভিন্ন শর্ট কোড তৈরি হবে না)।

৩ TB ডেটা সামলানো জন্য ডাটাবেসটিকে শার্ড (shard) করতে হবে। short_key-এর ওপর ভিত্তি করে হ্যাশ-বেজড (Hash-based) শার্ডিং ব্যবহার করলে ডাটাবেসগুলো সমানভাবে ডিস্ট্রিবিউট বা ভাগ হয় এবং লুকাপ (lookups)-এর সময় \(O(1)\) হয় — কারণ তখন আপনি ঠিক ঠিক জানেন কোন শার্ডে ডেটাটি খুঁজে পাবেন বা খোঁজা উচিত।

বাড়তি বিষয়: রেট লিমিটিং এবং অ্যানালিটিক্স

রেট লিমিটিং: স্প্যামিং রোধ করতে একজন ব্যবহারকারী এক ঘণ্টায় কতগুলো URL তৈরি করতে পারে তার একটা সীমা নির্ধারণ করে দিন। এর জন্য টোকেন বাকেট (Token bucket) বা স্লাইডিং উইন্ডো (Sliding window) অ্যালগরিদম ব্যবহার করুন (বিস্তারিত জানতে রেট লিমিটার পাঠটি দেখুন)। যে সমস্ত ইউজাররা লগিন ছাড়া বা আন-অথেনটিকেটেড (Unauthenticated) রয়েছে, তাদের ক্ষেত্রে রেট লিমিট বা সীমা আরও একটু শক্তভাবে প্রয়োগ করা উচিত।

অ্যানালিটিক্স: আনসিঙ্ক্রোনাসভাবে লিংকের ক্লিকগুলো ট্র্যাক করুন। যখন কোনো রিডিরেক্ট ঘটে, তখন একটি মেসেজ কিউতে (যেমন Kafka) একটি নতুন ক্লিক ইভেন্ট পাবলিশ করুন। পরবর্তীতে একটি আলাদা বা সেফারেট অ্যানালিটিক্স সার্ভিস এই ইভেন্টগুলোকে সংগ্রহ বা কনজিউম (consume) করে পরিসংখ্যান (যেমন প্রতিদিনের ক্লিক, ভৌগলিক বিবরণ, কে রেফার করেছে বা ব্যবহার করেছে ইত্যাদি) তৈরি করে। এই প্রক্রিয়ার কারণে মূল রিডিরেক্ট পাথটি যথেষ্ট দ্রুত থাকে — যার ফলে অ্যানালিটিক্সের জন্য ডাটাবেসে সিঙ্ক্রোনাস বা একই সাথে রাইট করতে সময় নষ্ট করতে হয় না।

মেয়াদ বা Expiration: একটি পর্যায়ক্রমিক ক্লিনআপ জব চালান যা মেয়াদ উত্তীর্ণ URL গুলো ডিলিট করে দেয় এবং পুনরায় ব্যবহার করার জন্য এদের কী গুলো KGS পুলে ফেরত পাঠায়। এই কাজটি রিড রিকোয়েস্টের সময় রিডিরেক্টের সাথে একই সাথে (inline) করবেন না — শুধুমাত্র এক্সপায়ারি টাইম বা expires_at চেক করুন এবং মেয়াদ উত্তীর্ণ হলে 404 স্ট্যাটাস রিটার্ন করুন।

Note: সাক্ষাৎকারের টিপস: URL শর্টনার-এর ক্ষেত্রে মূল আলোচনার বিষয়গুলো হলো: (১) Base62 এনকোডিংয়ের গাণিতিক ব্যাখ্যা, (২) কী (Key) জেনারেশন করার টেকনিক ও কৌশল (যেমন KGS-এর কথা উল্লেখ করা), (৩) রিড-হেভি ডেটাবেসের জন্য ক্যাশিং স্ট্র্যাটেজি ইত্যাদি, (৪) অ্যানালিটিক্সের জন্য 301 বনাম 302 রিডিরেক্ট স্ট্যাটাসের তুলনামূলক পার্থক্য ও সুবিধা-অসুবিধা। এগুলো সুন্দরভাবে আলোচনা করতে পারলে প্রমাণ হবে যে এই বৃহৎ সিস্টেমের চ্যালেঞ্জ ও এর সমস্যাগুলোর ব্যাপারে আপনার যথেষ্ট ধারণা রয়েছে।