4.4 מקצר URLs הרצאה

מקרה בוחן: עיצוב מקצר URLs

מקצר URLs (כמו bit.ly) הוא שאלת system design קלאסית בראיונות עבודה. נעבור על כל שלבי העיצוב.

---

שלב 1: הגדרת דרישות

שאלות שצריך לשאול:

דרישות פונקציונליות:
- משתמש מכניס URL ארוך ומקבל URL קצר
- מי שנכנס ל-URL הקצר מועבר (redirect) ל-URL המקורי
- האם URL הקצר הוא אקראי או ניתן לבחירה? (ניתן לבחירה - אופציה)
- מהו תוקף ה-URL? (לצמיתות)
- האם צריך analytics על כמה קליקים?

דרישות לא-פונקציונליות:
- 100 מיליון URLs במערכת
- יחס קריאה/כתיבה: 10:1 (הרבה יותר redirects מהקצרות)
- latency נמוך ל-redirect (< 10ms)
- זמינות גבוהה

---

שלב 2: הערכת נפח

כתיבות:
- 100 מיליון URLs
- נניח 10 מיליון כתיבות חדשות בחודש
- זה ~4 כתיבות בשנייה

קריאות:
- יחס 10:1 → 40 redirects בשנייה
- בשיא: בוא נניח 1000 redirects בשנייה

אחסון:
- URL ארוך: 2KB ממוצע
- 100 מיליון × 2KB = 200GB

לא מסיבי - שרת אחד יכול להכיל, אבל נצטרך scaling לביצועים.

---

שלב 3: עיצוב ה-API

POST /api/shorten
Request:  { "long_url": "https://www.example.com/very/long/path/..." }
Response: { "short_url": "https://short.ly/abc123", "short_code": "abc123" }

GET /{short_code}
Response: HTTP 301/302 Redirect → long_url

301 לעומת 302:
- 301 Permanent Redirect: דפדפן שומר ולא שולח בקשה לשרת שלנו פעמיים - פחות עומס אבל אין analytics
- 302 Temporary Redirect: כל קליק מגיע לשרת שלנו - יש analytics

---

שלב 4: מבנה הנתונים

CREATE TABLE urls (
    id          BIGINT PRIMARY KEY AUTO_INCREMENT,
    short_code  VARCHAR(8) UNIQUE NOT NULL,
    long_url    TEXT NOT NULL,
    created_at  TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    user_id     BIGINT,  -- אם מחוברים
    click_count BIGINT DEFAULT 0
);

CREATE INDEX idx_short_code ON urls(short_code);

---

שלב 5: יצירת short code

אפשרות 1: Hash + Truncation

import hashlib
import base64


def generate_short_code(long_url: str) -> str:
    hash_bytes = hashlib.md5(long_url.encode()).digest()
    encoded = base64.urlsafe_b64encode(hash_bytes).decode()
    return encoded[:7]  # 7 תווים = 62^7 = 3.5 טריליון קומבינציות

בעיה: התנגשויות (collisions) - שתי URLs שונות יכולות לקבל אותו code.

אפשרות 2: ID + Base62 Encoding

BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"


def encode_base62(num: int) -> str:
    if num == 0:
        return BASE62[0]
    result = []
    while num:
        result.append(BASE62[num % 62])
        num //= 62
    return "".join(reversed(result))


def decode_base62(code: str) -> int:
    result = 0
    for char in code:
        result = result * 62 + BASE62.index(char)
    return result


# דוגמה
print(encode_base62(12345678))  # "4qbEW"
print(decode_base62("4qbEW"))   # 12345678

יתרון: אין התנגשויות. ID מהDB → code ייחודי.

---

שלב 6: ארכיטקטורה

Client → [Load Balancer]
              ↓
         [API Servers] (stateless, ניתן לscale אופקי)
              ↓
    ┌─────────┼─────────┐
    ↓         ↓         ↓
[Redis     [Primary  [Read
 Cache]      DB]     Replicas]

Redirect Flow - מהיר

async def redirect(short_code: str):
    # שלב 1: בדוק cache ראשון
    long_url = await redis.get(f"url:{short_code}")

    if not long_url:
        # שלב 2: DB
        row = db_replica.execute(
            "SELECT long_url FROM urls WHERE short_code=?", (short_code,)
        ).fetchone()
        if not row:
            raise HTTPException(404)
        long_url = row[0]
        # שלב 3: שמור בcache ל-24 שעות
        await redis.setex(f"url:{short_code}", 86400, long_url)

    # שלב 4: עדכן counter (async, לא blocking)
    background_tasks.add_task(increment_click_count, short_code)

    return RedirectResponse(url=long_url, status_code=302)

Shorten Flow

def shorten(long_url: str) -> str:
    # בדוק אם כבר קיים
    existing = db_primary.execute(
        "SELECT short_code FROM urls WHERE long_url=?", (long_url,)
    ).fetchone()
    if existing:
        return existing[0]

    # הכנס לDB - קבל ID
    cursor = db_primary.execute(
        "INSERT INTO urls (long_url) VALUES (?)", (long_url,)
    )
    url_id = cursor.lastrowid

    # המר ID לshort code
    short_code = encode_base62(url_id)

    # עדכן שדה short_code
    db_primary.execute(
        "UPDATE urls SET short_code=? WHERE id=?", (short_code, url_id)
    )

    return short_code

---

שלב 7: Bottlenecks ופתרונות

הכי חשוב: redirects מהירים. Cache hit rate גבוה = מהיר.

מה לאחסן בcache: URLs פופולריות מאוד (20% מה-URLs = 80% מהקליקים, Zipf's Law).

Cache eviction: LRU (Least Recently Used) - URLs שלא נגישו הכי הרבה - יוצאות ראשונות.

Rate Limiting: מניעת spam - לא יותר מ-100 קיצורים לדקה למשתמש.

---

סיכום הארכיטקטורה

רכיב	תפקיד
Load Balancer	פיזור תעבורה
API Servers (×3)	stateless, ניתן לscale
Redis	cache ל-redirects
PostgreSQL Primary	כתיבות
PostgreSQL Replicas	קריאות
Base62 Encoder	short code generation