Project: URL Shortener တစ်ခု တည်ဆောက်ခြင်း

နားလည်ထားရမယ့် အချက်

URL shortener တစ်ခုမှာ long URL တစ်ခုချင်းစီကို short ပြီး unique ဖြစ်တဲ့ code တစ်ခုအဖြစ် ပြောင်းပေးဖို့နဲ့ ဒီ code ကနေ original URL ကို ပြန်ချိတ်ပေးဖို့ လိုအပ်တယ်။ naive approach ဖြစ်တဲ့ long URL ကို hash လုပ်တာ (MD5 ကို truncate လုပ်တာလိုမျိုး) က deterministic ဖြစ်လို့ ကောင်းပုံရပေမယ့် hash တွေဟာ collision ဖြစ်တတ်တယ် - URL နှစ်ခုက short hash တူသွားနိုင်ပြီး write တိုင်းမှာ collision check နဲ့ retry loop ထပ်ထည့်ရတာက write path ကို latency နဲ့ complexity တိုးစေတယ်။ ပိုကောင်းတဲ့ design ကတော့ collision ကို အစကတည်းက ရှောင်လိုက်တယ် - URL အသစ်တိုင်းကို auto-incrementing counter ရဲ့ နောက်တန်ဖိုးပေးပြီး ဒီ integer ကို base62 (digit + uppercase + lowercase letter) နဲ့ encode လုပ်လိုက်ရင် short ပြီး URL-safe ဖြစ်တဲ့ unique code ရရှိတယ် - collision detection ဘယ်တော့မှ မလိုတော့ဘူး။ storage ကတော့ short_code ကနေ long_url ဆီ ရိုးရှင်းတဲ့ key-value mapping ပဲဖြစ်ပြီး scale သေးငယ်တဲ့အခါ hash map လုံလောက်ပြီး production မှာဆို algorithm မပြောင်းဘဲ database ဒါမှမဟုတ် key-value store နဲ့ အစားထိုးလို့ရတယ်။ နောက်ထပ် key insight ကတော့ traffic pattern ဖြစ်တယ် - redirect (read) တွေက shortening (write) အသစ်တွေထက် လက်တွေ့မှာ အများကြီးများနေတာမို့ resolve path ကို မြန်မြန်ဆန်ဆန် ဈေးသက်သက်နဲ့ လုပ်ဖို့လိုပြီး ဒါကြောင့်ပဲ hot short code တွေကို cache လုပ်တာက ဒီနေရာမှာ အရေးအကြီးဆုံးဖြစ်လာတာပါ။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

ဒါဟာ Tutorial Platform က lesson တစ်ခုချင်းစီအတွက် share လုပ်လို့ရတဲ့ short link ထုတ်ပေးနိုင်တဲ့ system ရဲ့ scale-down version တစ်ခုဖြစ်တယ် - /tutorials/rust/ownership-and-borrowing လို long URL ကို chat ထဲ ဒါမှမဟုတ် certificate ပေါ်မှာ paste လုပ်မယ့်အစား learner တစ်ယောက်က thta.io/aB3xZ လို short code ကို ရရှိမယ်။ counter-plus-base62 approach ဟာ database ထဲက platform ရဲ့ auto-incrementing lesson ID ရှိပြီးသားနဲ့ တိုက်ရိုက်ကိုက်ညီတာမို့ ID scheme အသစ်ထပ်လိုအပ်မှာမဟုတ်ဘူး။ ပြီးတော့ lesson link တွေက ဖန်တီးတာထက် share ဖြစ်ပြီး click ခံရတာက ပိုများတာမို့ ဒီနေရာက read-heavy traffic pattern ဟာ platform ရဲ့ တကယ့် link-resolution endpoint ရှေ့မှာ cache layer ထည့်ဖို့ အကြောင်းပြချက်ပေးနေတဲ့ pattern အတိုင်းပဲဖြစ်တယ်။

• Auto-incrementing counter ကို base62 ဖြင့် encode လုပ်ခြင်းက URL ကို hash လုပ်တာနဲ့မတူဘဲ collision handling လုံးဝမလိုအောင် unique code ကို အာမခံပေးတယ်။
• short_code ကနေ long_url ကို ချိတ်ဆက်တဲ့ mapping ဟာ key-value store တစ်ခုပဲဖြစ်တယ် - အခုဆို hash map၊ scale ကြီးလာရင် database။
• Read (redirect) အရေအတွက်က write (shortening) ထက် အများကြီးများတာမို့ resolve path ကိုပဲ cache လုပ်ဖို့နဲ့ optimize လုပ်ဖို့ အရေးအကြီးဆုံးဖြစ်တယ်။

အတူတူ စမ်းရေးကြည့်မယ်

import string

class URLShortener:
    ALPHABET = string.digits + string.ascii_lowercase + string.ascii_uppercase  # base62

    def __init__(self):
        self._next_id = 1
        self._code_to_url = {}   # short_code -> long_url
        self._url_to_code = {}   # long_url -> short_code (avoid duplicate codes for same URL)

    def _encode_base62(self, num: int) -> str:
        if num == 0:
            return self.ALPHABET[0]
        digits = []
        base = len(self.ALPHABET)
        while num > 0:
            num, rem = divmod(num, base)
            digits.append(self.ALPHABET[rem])
        return "".join(reversed(digits))

    def shorten(self, long_url: str) -> str:
        if long_url in self._url_to_code:
            return self._url_to_code[long_url]
        short_code = self._encode_base62(self._next_id)
        self._next_id += 1
        self._code_to_url[short_code] = long_url
        self._url_to_code[long_url] = short_code
        return short_code

    def resolve(self, short_code: str) -> str:
        if short_code not in self._code_to_url:
            raise KeyError(f"Unknown short code: {short_code}")
        return self._code_to_url[short_code]


if __name__ == "__main__":
    shortener = URLShortener()
    urls = [
        "https://thutalearning.com/tutorials/rust/ownership-and-borrowing",
        "https://thutalearning.com/tutorials/system-design/project-url-shortener",
        "https://thutalearning.com/tutorials/elasticsearch/full-text-search",
    ]
    codes = [shortener.shorten(u) for u in urls]
    for url, code in zip(urls, codes):
        print(f"{url} -> {code}")
    for code in codes:
        print(f"{code} -> {shortener.resolve(code)}")

long URL တစ်ခုချင်းစီရဲ့ဘေးမှာ ရရှိတဲ့ short code (1, 2, 3 ကို base62 ဖြင့် encode လုပ်ထားတာ) ကို print ထုတ်ပြီး code တစ်ခုချင်းစီက original long URL ကို ပြန်ချိတ်ပေးတာကို print ထုတ်ပြသတယ်။

Wikipedia — URL shortening — System Design