संक्षेप (टीएल;डीआर)
- समस्या: शॉर्टनर में दो रास्ते होते हैं जिनका स्वभाव बिल्कुल अलग है: कभी-कभार चलने वाला, लिखने वाला निर्माण रास्ता, और पढ़ने वाला रास्ता जो सौ गुना ज्यादा गर्म, देरी के प्रति संवेदनशील और उपयोगकर्ताओं को दिखने वाली इकलौती चीज होता है।
- डिजाइन: दस-दस लाख आईडी के किराए वाले ब्लॉक से आईडी बनाएं, उन्हें फाइस्टल नेटवर्क से मिलाएं, ७ बेस६२ अक्षरों में बदलें,
code -> urlको कोड के आधार पर बंटे स्टोर में रखें, और रीडायरेक्ट सीडीएन और रेडिस से परोसें, डेटाबेस सिर्फ कैश चूकने पर। क्लिक एनालिटिक्स एक कतार के जरिए गर्म रास्ते से बाहर जाती है।- नतीजा: आईडी आवंटन के लिए हर दस लाख लिंक पर एक डेटाबेस लेखन, किनारे पर २० मिलीसेकंड से कम का पी९९ रीडायरेक्ट, ऐसी एनालिटिक्स जो पीछे रह सकती है या घटनाएं गिरा सकती है पर कभी रीडायरेक्ट धीमा नहीं करती, और हर विफलता के लिए साफ जवाब।
सिस्टम डिजाइन इंटरव्यू की हर सूची में यूआरएल शॉर्टनर ऊपर होता है, और ज्यादातर लेख उसे वार्म-अप की तरह लेते हैं। वह वार्म-अप नहीं है। यह उन सबसे साफ उदाहरणों में से है जहां पढ़ने और लिखने के रास्ते अलग आर्किटेक्चर के हकदार हैं, और जहां छोटे फैसले (कौन सा रीडायरेक्ट कोड, काउंटर कहां रहता है) तय करते हैं कि कोई लिंक वायरल होने पर सिस्टम बचेगा या नहीं।
यह लेख इसे वैसे डिजाइन करता है जैसे मैं उत्पादन के लिए करता, फिर बताता है कि इंटरव्यू में क्या बदलता है।
जरूरतें और उन्हें आकार देने वाली संख्याएं
कार्यात्मक
१. POST /links एक लंबा यूआरएल लेता है और छोटा लौटाता है। कस्टम उपनाम और समाप्ति वैकल्पिक।
२. GET /{code} लंबे यूआरएल पर भेजता है, या कोड अज्ञात, समाप्त या हटाया गया हो तो ४०४ लौटाता है।
३. मालिक क्लिक की गिनती देख सकते हैं। अनुमानित और थोड़ी देर से आई गिनती चलेगी।
गैर-कार्यात्मक
- रीडायरेक्ट तेज और हमेशा उपलब्ध होने चाहिए। टूटा छोटा लिंक हर क्लिक करने वाले को दिखता है।
- निर्माण कॉल के
201लौटाने के बाद मैपिंग कभी खोनी नहीं चाहिए। उपयोगकर्ता लिंक कहीं चिपका चुका है। - कोड आसानी से गिने न जा सकें।
मोटा हिसाब
| मान्यता | मान | नतीजा |
|---|---|---|
| हर महीने नए लिंक | १० करोड़ | औसतन लगभग ४० लेखन प्रति सेकंड, १० गुना शिखर पर लगभग ४०० |
| पढ़ना:लिखना अनुपात | १००:१ | औसतन लगभग ४,००० रीडायरेक्ट प्रति सेकंड, शिखर पर लगभग ४०,००० |
| पंक्ति का आकार (कोड, यूआरएल, मालिक, समय, स्थिति) | लगभग ५०० बाइट | लगभग ५० जीबी प्रति महीना, ५ साल में लगभग ३ टीबी |
| गर्म हिस्सा | लगभग २०% लिंक को लगभग ८०% क्लिक | कुछ जीबी का code -> url रेडिस में आराम से समाता है |
| ७ बेस६२ अक्षरों का कोड स्थान | ६२^७ ≈ ३.५ लाख करोड़ | १० करोड़ प्रति महीने पर सदियों की गुंजाइश |
इस तालिका से दो बातें तुरंत निकलती हैं। स्टोरेज कठिन हिस्सा नहीं है: ३ टीबी एक मामूली डेटाबेस है। और रीडायरेक्ट रास्ता डेटाबेस से कहीं ज्यादा कैश की समस्या है।
आर्किटेक्चर
इसे बाएं से दाएं पढ़िए।
- क्लिक करने वाला / बनाने वाला। दो बहुत अलग ग्राहक। क्लिक करने वाले गुमनाम, दुनिया भर में फैले और बेसब्र हैं। बनाने वाले प्रमाणित उपयोगकर्ता या एपीआई एकीकरण हैं, संख्या में बहुत कम।
- सीडीएन किनारा। उपयोगकर्ता के पास टीएलएस खत्म करता है और लोकप्रिय कोड के रीडायरेक्ट जवाब कैश कर सकता है। वायरल लिंक के ज्यादातर क्लिक आपके मूल सर्वर तक पहुंचने ही नहीं चाहिए।
- एपीआई गेटवे। बनाने वालों को प्रमाणित करता है, प्रति उपयोगकर्ता और प्रति आईपी निर्माण सीमा लागू करता है, और बहुत बड़े या गलत अनुरोधों को खर्च होने से पहले ठुकरा देता है।
- रीडायरेक्ट सेवा। एक छोटी, बिना स्थिति वाली सेवा जिसका एक ही काम है: कोड हल करो और रीडायरेक्ट लौटाओ। पहले रेडिस पढ़ती है, चूकने पर मैपिंग डेटाबेस पर जाती है, और क्लिक घटना भेजकर उसका इंतजार नहीं करती।
- निर्माण एपीआई। यूआरएल जांचता है (अनुमत योजनाओं की सूची, लंबाई की सीमा, प्रतिबंध सूची), अपने किराए के ब्लॉक से अगली आईडी लेता है, उसे एन्कोड करता है और मैपिंग डालता है।
- आईडी रेंज आवंटक। निर्माण एपीआई के पॉड को दस-दस लाख आईडी के ब्लॉक देता है। हर दस लाख लिंक पर एक बार छुआ जाता है, इसलिए यह किसी साधारण रिलेशनल डेटाबेस की एक पंक्ति भर हो सकता है।
- रेडिस (
code -> url)। गर्म कैश। प्रविष्टियों का टीटीएल होता है, और "नहीं मिला" वाले नतीजे थोड़ी देर कैश किए जाते हैं ताकि स्कैनर डेटाबेस पर हथौड़ा न चलाएं। - मैपिंग डेटाबेस। सच्चाई का स्रोत, कोड के आधार पर बंटा हुआ। हर रीडायरेक्ट खोज
codeपर प्राथमिक कुंजी से पढ़ना है, और यही वह इकलौता तरीका है जिसे इस सिस्टम को सस्ता बनाना है। - क्लिक घटनाएं, रोलअप वर्कर, क्लिक गिनती। रीडायरेक्ट एक लॉग (काफ्का, काइनेसिस या ऐसा कुछ) में घटनाएं भेजते हैं। वर्कर उन्हें ओलैप स्टोर में प्रति लिंक, प्रति दिन की गिनती में जोड़ते हैं। अगर यह पूरा हिस्सा जल भी जाए, रीडायरेक्ट चलते रहते हैं।
चित्र का हरा नोट अनुबंध है: किनारे पर २० मिलीसेकंड से कम पी९९, और जब अनुरोध को रेडिस या डेटाबेस तक जाना पड़े तो ५० मिलीसेकंड से कम।
कोड बनाना: किराए के ब्लॉक, फाइस्टल मिश्रण, फिर बेस६२
छोटा कोड बनाने के तीन आम तरीके हैं:
| तरीका | कैसे काम करता है | ताकत | कमजोरी |
|---|---|---|---|
| यूआरएल का हैश | यूआरएल का शा-२५६, पहले ४० बिट लो, बेस६२ में बदलो | एक ही यूआरएल को एक ही कोड मिल सकता है | टकराव पर दोबारा कोशिश; दो उपयोगकर्ताओं का एक कोड साझा करना स्वामित्व और एनालिटिक्स उलझा देता है |
| बेतरतीब कोड | ७ बेतरतीब बेस६२ अक्षर, अद्वितीय बाध्यता के साथ डालो | अनुमान लगाना असंभव | टकराव पर दोबारा कोशिश; हर निर्माण पूरी तालिका पर अद्वितीयता जांच है |
| काउंटर + एन्कोड | अद्वितीय पूर्णांक, फिर बेस६२ | न टकराव, न दोबारा कोशिश | क्रमिक कोड मिलाए न जाएं तो गिने जा सकते हैं |
मैं काउंटर पसंद करता हूं, दो सुधारों के साथ।
किराए के ब्लॉक। एक वैश्विक काउंटर एक गर्म पंक्ति बन जाता। इसके बजाय निर्माण एपीआई का हर पॉड दस लाख आईडी का ब्लॉक किराए पर लेता है (UPDATE counter SET next = next + 1000000 RETURNING next) और उन्हें मेमोरी से बांटता है। यानी हर दस लाख लिंक पर एक डेटाबेस लेखन। अगर कोई पॉड गिर जाए, तो उसके ब्लॉक का बाकी हिस्सा कभी इस्तेमाल नहीं होता। खाली जगहें ठीक हैं; दोहराव नहीं।
फाइस्टल मिश्रण। क्रमिक आईडी क्रमिक कोड बनाती हैं, जिससे हर लिंक गिनना आसान हो जाता है। फाइस्टल नेटवर्क एक तय बिट चौड़ाई पर कुंजी वाला, उलटा जा सकने वाला क्रमचय है: हर ४० बिट का इनपुट ठीक एक ४० बिट के आउटपुट से जुड़ता है, इसलिए अद्वितीयता बनी रहती है, पर पड़ोसी पड़ोसी जैसे नहीं दिखते। यह कूट-लेखन वाली गोपनीयता नहीं है। यह सस्ता छलावा है जो सबसे आसान स्क्रैपिंग हमले को हटा देता है।
बेस६२। 0-9a-zA-Z यूआरएल में बिना एस्केप के सुरक्षित है। ४० बिट का स्थान (लगभग १.१ लाख करोड़ आईडी, १० करोड़ लिंक प्रति महीने पर लगभग ९०० साल) ७ बेस६२ अक्षरों में समा जाता है, क्योंकि ६२^७ लगभग ३.५ लाख करोड़ है। ४२ बिट का स्थान नहीं समाता: २^४२ लगभग ४.४ लाख करोड़ है, और उसका ऊपरी चौथाई हिस्सा ८ अक्षरों में चला जाता।
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
HALF_BITS, MASK = 20, (1 << 20) - 1 # 40-bit permutation, always < 62**7
def feistel(n: int, keys=(0x5bd1e, 0x1b873, 0x2f1d3)) -> int:
left, right = n >> HALF_BITS, n & MASK
for k in keys:
left, right = right, left ^ (((right * 0x9E3779B1) ^ k) & MASK)
return (left << HALF_BITS) | right
def encode(n: int, width: int = 7) -> str:
out = []
while n:
n, r = divmod(n, 62)
out.append(ALPHABET[r])
return "".join(reversed(out)).rjust(width, "0")
code = encode(feistel(8_000_123)) # 7 chars, unique per ID
कस्टम उपनाम उसी code कॉलम में उसी अद्वितीय बाध्यता के साथ जाते हैं, आरक्षित शब्दों (api, admin, login, health) की जांच और अपशब्द तथा नकल पहचानने वाले फिल्टर के बाद।
स्टोरेज
स्कीमा जानबूझकर उबाऊ है:
| कॉलम | प्रकार | टिप्पणी |
|---|---|---|
code |
varchar(16) प्राथमिक कुंजी |
विभाजन कुंजी; हर रीडायरेक्ट इसी पर एक बिंदु पठन है |
long_url |
text |
निर्माण के समय जांचा गया, पढ़ते समय कभी नहीं बदला जाता |
owner_id |
bigint |
"मेरे लिंक" डैशबोर्ड के लिए द्वितीयक सूचकांक |
created_at, expires_at |
समय मुहर | expires_at खाली का मतलब हमेशा के लिए |
status |
सूची: सक्रिय, निष्क्रिय, हटाया गया | इतिहास मिटाए बिना लिंक बंद करने देता है |
एसक्यूएल या कुंजी-मान? दोनों चलते हैं। प्रबंधित कुंजी-मान स्टोर (डायनेमोडीबी, कसांड्रा, बिगटेबल) बिंदु पठन को आसानी से बढ़ाते हैं और समाप्त होने वाले लिंक के लिए उनमें अपना टीटीएल होता है। code के हैश से विभाजित पोस्टग्रेस कई टेराबाइट तक काफी है, और आवंटक के लिए लेनदेन तथा मालिक वाली खोज मुफ्त में देता है। गलत चुनाव वह है जो GET को कोड से एक से ज्यादा चक्कर बना दे।
मालिक से नहीं, कोड से बांटें। मालिक से बांटने पर किसी मशहूर व्यक्ति के सारे लिंक एक गर्म हिस्से पर आ जाएंगे। कोड के हैश से बांटने पर भार बराबर फैलता है, और मालिक का डैशबोर्ड द्वितीयक सूचकांक या अलग तालिका से चल सकता है।
मैपिंग पंक्ति पर कभी काउंटर न रखें। हर रीडायरेक्ट पर UPDATE links SET clicks = clicks + 1 आपके सबसे गर्म पठन को एक ही पंक्ति पर होड़ वाले लेखन में बदल देता है। वायरल लिंक उस पंक्ति को पिघला देगा। गिनती एनालिटिक्स पाइपलाइन में होनी चाहिए।
रीडायरेक्ट रास्ता, सटीक रूप से
१. सीडीएन अपना कैश देखता है। मिल गया: कैश किया रीडायरेक्ट लौटाओ। खत्म। २. रीडायरेक्ट सेवा रेडिस देखती है। मिल गया: जवाब दो। ३. चूक: प्राथमिक कुंजी से मैपिंग डेटाबेस पढ़ो। अगर पंक्ति नहीं है, समाप्त है या सक्रिय नहीं है, तो थोड़ी देर का "नहीं मिला" कैश करो और ४०४ लौटाओ। वरना रेडिस भरो और जवाब दो। ४. क्लिक घटना असिंक्रोनस रूप से लॉग में भेजो। अगर लॉग धीमा है, घटना छोड़ दो। रीडायरेक्ट कभी मत रोको।
कौन सा स्थिति कोड? इस फैसले के असली नतीजे हैं:
| स्थिति | अर्थ (आरएफसी ९११०) | कैशिंग | कब इस्तेमाल करें |
|---|---|---|---|
| ३०१ स्थायी रूप से हटा | स्थायी | ब्राउजर और प्रॉक्सी जमकर कैश करते हैं | जब मूल सर्वर पर कम से कम भार चाहिए और सटीक क्लिक गिनती की जरूरत नहीं |
| ३०२ मिला | अस्थायी | डिफॉल्ट रूप से कैश नहीं | जब एनालिटिक्स के लिए हर क्लिक आप तक आना चाहिए, या लिंक बदल सकते हैं |
| ३०७ / ३०८ | अस्थायी / स्थायी, तरीका बना रहता है | ऊपर जैसा | शॉर्टनर में कम; तब अहम जब गैर-जीईटी अनुरोध रीडायरेक्ट हों |
मेरा डिफॉल्ट है ३०२ और सीडीएन पर छोटा, साफ Cache-Control: max-age (मान लीजिए ६० से ३०० सेकंड)। लोकप्रिय लिंक किनारे से परोसे जाते हैं, एनालिटिक्स काफी हद तक ईमानदार रहती है (सीडीएन लॉग भी गिनिए), और हटाने का आदेश मिनटों में फैल जाता है, किसी के ब्राउजर कैश में हमेशा के लिए नहीं टिका रहता।
कैश भगदड़। जब कोई ठंडा लिंक अचानक वायरल होता है, तो एक ही कुंजी के लिए हजारों साथ-साथ चूकें डेटाबेस पर टूट सकती हैं। रीडायरेक्ट सेवा में अनुरोध एकीकरण (एक पठन, कई इंतजार करने वाले) या रेडिस में छोटा ताला लगाइए।
दुरुपयोग रोकना मुख्य सुविधा है, अतिरिक्त नहीं
शॉर्टनर आपके डोमेन की साख हर उस यूआरएल को उधार देता है जो कोई चिपका दे। अगर आप इसके खिलाफ डिजाइन नहीं करते, तो यह फिशिंग का औजार बन जाता है।
- निर्माण के समय गंतव्य जांचें गूगल सेफ ब्राउजिंग जैसी साख सूची से, और लोकप्रिय लिंक समय-समय पर दोबारा जांचें, क्योंकि बनने के बाद गंतव्य बदल जाते हैं।
- निर्माण सीमित करें प्रति खाता, प्रति आईपी और प्रति गंतव्य डोमेन।
- पूर्वावलोकन पेज दें (बिटली की परंपरा में
sho.rt/aB3xY9q+) ताकि सावधान उपयोगकर्ता जाने से पहले गंतव्य देख सकें। - हटाना तेज बनाएं:
status = taken_downकरें, रेडिस कुंजी मिटाएं, सीडीएन का रास्ता साफ करें। ३०२ और छोटे किनारे टीटीएल के साथ यह मिनटों का काम है, दिनों का नहीं। - प्रति आईपी रीडायरेक्ट सीमित करें ताकि गिनती धीमी पड़े, मिलाए गए कोड के बावजूद।
विफलताएं और क्या होना चाहिए
| विफलता | अपेक्षित व्यवहार |
|---|---|
| रेडिस बंद | रीडायरेक्ट डेटाबेस पर गिरते हैं। देरी बढ़ती है, सही नतीजे बने रहते हैं। डेटाबेस सीमा के पास हो तो किनारे पर भार घटाएं |
| डेटाबेस का एक हिस्सा बंद | उस हिस्से के कोड विफल; बाकी सब चलता है। प्रतिकृतियों को सेकंडों में जगह लेनी चाहिए |
| क्लिक लॉग अनुपलब्ध | रीडायरेक्ट चलते रहते हैं; घटनाएं गिराई या स्थानीय रूप से जमा की जाती हैं। उस समय की गिनती कम रहेगी |
| आईडी आवंटक अनुपलब्ध | पॉड अपने मौजूदा ब्लॉक से आईडी बनाते रहते हैं। दस लाख के ब्लॉक से यह घंटों की गुंजाइश है |
| रीडायरेक्ट सेवा की खराब तैनाती | असर हर लिंक पर। ट्रैफिक के छोटे हिस्से पर कैनरी चलाएं और सेवा छोटी रखें ताकि वापसी तेज हो |
| कोई लिंक वायरल हो जाए | ज्यादातर भार सीडीएन सोखता है; अनुरोध एकीकरण पहली चूक वाली आंधी से डेटाबेस बचाता है |
इंटरव्यू में क्या बदलता है
४५ मिनट में फाइस्टल नेटवर्क और सीडीएन टीटीएल पर बात करने का समय नहीं मिलेगा। प्राथमिकता:
१. पढ़ना:लिखना अनुपात और क्षमता का हिसाब दो वाक्यों में बताएं। २. दोनों रास्ते अलग-अलग बनाएं। ३. काउंटर और बेस६२ चुनें, और गिनती के खतरे तथा मिश्रण वाले हल का जिक्र करें। ४. समझाएं कि क्लिक काउंटर मैपिंग पंक्ति पर क्यों नहीं रहते। ५. ३०१ बनाम ३०२ पर अपनी राय रखें।
समझ दिखाने के लिए इतना काफी है। बाकी बातचीत है।
उत्पादन जांच सूची
- क्षमता का हिसाब लिखा हुआ, पढ़ना:लिखना अनुपात और शिखर गुणक के साथ
- आईडी ब्लॉक में किराए पर; आवंटक दोबारा शुरू होने पर टिका रहता है; खाली जगहें स्वीकार्य के रूप में दर्ज
- एन्कोडिंग से पहले कोड मिलाए गए; कस्टम उपनाम वही अद्वितीय बाध्यता साझा करते हैं
- निर्माण पर अनुमत योजना सूची, लंबाई सीमा और साख जांच
- रीडायरेक्ट रास्ता: सीडीएन, फिर टीटीएल और नकारात्मक कैश वाला रेडिस, फिर प्राथमिक कुंजी से डेटाबेस
- ठंडी कुंजी की भगदड़ के लिए अनुरोध एकीकरण
- ३०२ और छोटा किनारा टीटीएल, या ३०१ के लिए लिखी हुई वजह
- क्लिक घटनाएं असिंक्रोनस, छोड़ी जा सकने वाली, और मैपिंग पंक्ति पर कभी नहीं
- हटाना एक ही काम में डेटाबेस स्थिति, रेडिस और सीडीएन साफ करता है
- डैशबोर्ड: रीडायरेक्ट पी९९, कैश हिट दर, ४०४ दर, प्रति खाता निर्माण दर
जो बचा रह गया
इस सिस्टम का दिलचस्प हिस्सा एन्कोडिंग की तरकीब नहीं है। वह रीडायरेक्ट रास्ते को उबाऊ बनाए रखने का अनुशासन है। हर नई सुविधा की मांग (असली समय की गिनती, ए/बी गंतव्य, भौगोलिक रूटिंग) उसमें तर्क ठूंसने की कोशिश करेगी।
ज्यादातर को मना कीजिए। जो लिंक किसी ने तीन साल पहले किसी ग्रुप चैट में चिपकाया था, वह कल सुबह भी चलना चाहिए, आपकी कॉफी से पहले और इससे पहले कि किसी को याद भी आए कि वह है।