सर्च ऑटोकम्प्लीट सिस्टम डिज़ाइन करें: टाइपअहेड असल में कैसे काम करता है

टीएल;डीआर

समस्या: बड़े पैमाने की वास्तुकला (आर्किटेक्चर) तैयार करने के लिए उपलब्धता, थ्रूपुट और परिचालन जटिलता के बीच संतुलन बनाना आवश्यक है।

मुख्य निष्कर्ष: शुरुआती लोगों के लिए सर्च ऑटोकम्प्लीट: प्रीफ़िक्स, अक्षरों का पेड़ (ट्राइ), टॉप सुझाव, जवाब पहले से क्यों बनाते हैं, और डिन टाइप करते हुए अक्षर-अक्षर की सैर।

परिणाम: उत्पादन वातावरण में विफलता से निपटने और प्रदर्शन लक्ष्यों को हासिल करने की सटीक रूपरेखा।

आप रोज़ सर्च ऑटोकम्प्लीट इस्तेमाल करते हैं। गूगल, अमेज़न या फ़ोन के मैसेज खोलो। कुछ अक्षर टाइप करते ही एंटर दबाने से पहले पूरी वाक्यांशों की छोटी सूची आ जाती है। वह ड्रॉपडाउन जादू नहीं है। यह एक छोटा सिस्टम है जिसका एक ही काम है: अभी तक टाइप किए गए अक्षरों के आधार पर कुछ अच्छे पूरे क्वेरी, बहुत तेज़ लौटाना।

सोचो फ़ोन कीबोर्ड के सुझावों की। जैसे ही तुम din टाइप करते हो, कीबोर्ड शब्द पूरा करने की कोशिश करता है। या सोचो एक शब्दकोश जो सिर्फ़ शब्दों की शुरुआत देखता है, बीच नहीं, और सबसे आम मेल पहले देता है। यही इस पूरे डिज़ाइन का मानसिक मॉडल है।

यह पोस्ट ऑटोकम्प्लीट सिखाता है जैसे मैं व्हाइटबोर्ड पर किसी ऐसे व्यक्ति को समझाऊँ जिसने कभी सर्च नहीं बनाया। सादी भाषा, एक छोटा उदाहरण (din), और सिर्फ़ वे विचार जो इंटरव्यू या पहली प्रोडक्शन वर्शन के लिए चाहिए।

हम क्या बना रहे हैं (और क्या नहीं)

दायरे में

१. यूज़र एक प्रीफ़िक्स टाइप करता है (क्वेरी की शुरुआत)। २. सिस्टम टॉप के सुझाव लौटाता है (अक्सर ५ से १०)। ३. सुझाव मुख्यतः लोगों ने कितनी बार खोजा से रैंक होते हैं। ४. जवाब तुरंत सा लगे (मोटा लक्ष्य: करीब १०० मिलीसेकंड से कम)। ५. असली सर्च लॉग से सूची को उचित रूप से ताज़ा रखते हैं।

बिना पूछे दायरे से बाहर

मशीन लर्निंग वाला गूगल-स्तर का रैंकिंग
टाइपो सुधार (dinnr → dinner)
वाक्य के बीच में मैच ढूँढना
"सिर्फ़ आपके लिए" निजी सूची

इंटरव्यू में इन्हें ज़ोर से नाम लो, ताकि शोध-पत्र में न फँस जाओ।

एक शब्द से शुरू: प्रीफ़िक्स

प्रीफ़िक्स बस किसी स्ट्रिंग की शुरुआत है।

तुमने टाइप किया	यह इनका प्रीफ़िक्स है
`d`	`dinner`, `dinosaur`, `doctor`, ...
`di`	`dinner`, `dinosaur`, `diners near me`, ...
`din`	`dinner recipes`, `dinosaur`, `diners near me`, ...
`dino`	`dinosaur`, `dinosaur toys`, ...

ऑटोकम्प्लीट का मतलब लगभग हमेशा शुरुआत से प्रीफ़िक्स मैच है, "कहीं भी यह टुकड़ा ढूँढो" नहीं।

अगर प्रोडक्ट को सिर्फ़ यही चाहिए, साफ़ कहो। बीच-स्ट्रिंग मैच अलग, ज़्यादा कठिन समस्या है।

सादी शब्द-सूची क्यों काफ़ी नहीं

कल्पना करो हर लोकप्रिय सर्च एक बड़ी टेबल में है:

query                 times_searched
------------------------------------
dinner recipes        98012
dinosaur              77120
diners near me        54001
doctor near me        41000
... millions more ...

प्रीफ़िक्स din के लिए भोला जवाब:

SELECT query
FROM queries
WHERE query LIKE 'din%'
ORDER BY times_searched DESC
LIMIT 5;

लैपटॉप डेमो में चलता है। असली स्केल पर हर कीस्ट्रोक एक रिक्वेस्ट बन सकता है, और प्रति सेकंड हज़ारों रिक्वेस्ट आ सकते हैं। हर अक्षर पर विशाल टेबल स्कैन या सॉर्ट बहुत धीमा और महँगा है।

हमें ऐसी संरचना चाहिए जो अक्षरों को एक-एक करके चलने के लिए बनी हो।

फ़ोन कीबोर्ड का विचार: अक्षरों का पेड़

यहाँ मुख्य तस्वीर है।

एक पेड़ सोचो। जड़ खाली है (कुछ टाइप नहीं हुआ)। नीचे हर कदम एक अक्षर है। साझा शुरुआत साझा रास्ता बाँटती है।

उस पेड़ को ट्राइ कहते हैं (उच्चारण "ट्राई")। लोग इसे प्रीफ़िक्स ट्री भी कहते हैं।

छोटा शब्दकोश: be, bee, beer, best, bet।

पढ़ने का तरीका:

रास्ता b → e प्रीफ़िक्स be है।
रास्ता b → e → e → r शब्द beer है।
जो शब्द शुरुआत बाँटते हैं वे नोड बाँटते हैं, इसलिए be, bee और beer के लिए be के अक्षर तीन बार अलग नहीं रखते।

कीबोर्ड सुझाव जैसी ही बात: कीबोर्ड हर अक्षर पर पूरा शब्दकोश अ से ज्ञ तक नहीं पढ़ता। वह उन अक्षरों के रास्ते पर चलता है जो तुमने पहले टाइप किए, फिर देखता है वहाँ से क्या और बढ़ सकता है।

`din` टाइप करते हुए अक्षर-अक्षर सैर

मान लो d से शुरू होने वाली लोकप्रिय क्वेरी में शामिल हैं:

dinner recipes (स्कोर ९८०१२)
dinosaur (स्कोर ७७१२०)
diners near me (स्कोर ५४००१)
doctor near me (स्कोर ४१०००)
disney movies (स्कोर ३९०००)

कदम १: यूज़र d टाइप करता है

सर्वर एक किनारा चलता है: जड़ → d।

d के नीचे सब उम्मीदवार हैं: डिनर, डायनासोर, डॉक्टर, डिज़्नी और और। अगर सब सूचीबद्ध करें तो सूची विशाल हो जाए। इसलिए इस प्रीफ़िक्स के लिए सिर्फ़ कुछ बेहतरीन रखते हैं (आगे विस्तार)। शायद:

prefix "d" → dinner recipes, dinosaur, diners near me, doctor near me, disney movies

कदम २: यूज़र i टाइप करता है (अब di)

एक और किनारा: d → i।

doctor और जो i से नहीं चलते वे बाहर। di के नीचे अभी भी: डिनर, डायनासोर, डाइनर्स, डिज़्नी जैसे।

prefix "di" → dinner recipes, dinosaur, diners near me, disney movies, ...

कदम ३: यूज़र n टाइप करता है (अब din)

चला: i → n।

अब रास्ता d-i-n है। सिर्फ़ वे क्वेरी रहती हैं जो din से शुरू होती हैं:

prefix "din" → dinner recipes, dinosaur, diners near me, ...

पूरा क्वेरी पथ एक वाक्य में: यूज़र के टाइप किए अक्षरों का पीछा करो, फिर उस नोड के नीचे लटकी बेहतरीन पूरी क्वेरी लौटाओ।

नोड तक पहुँचने का समय टाइप किए अक्षरों की संख्या के अनुपात में है। छोटी सर्च बॉक्स में यह मुट्ठी भर कदम हैं, पूरी टेबल स्कैन नहीं।

टॉप सुझाव: हम सब नहीं दिखाते

यूज़र दस हज़ार मैच नहीं चाहता। वह छोटी, उपयोगी सूची चाहता है।

इसलिए प्रोडक्ट कहता है: टॉप के लौटाओ, अक्सर k = 5 या k = 10।

रैंक कैसे?

सबसे सरल इंटरव्यू जवाब: ऐतिहासिक आवृत्ति। गिनो लोग उस सर्च को कितनी बार पूरा कर चुके। ज़्यादा गिनती → ऊँचा रैंक। बाद में वैकल्पिक: हाल के ट्रेंड, सुझावों पर क्लिक, भाषा, स्थान। पहले आवृत्ति रखो ताकि डिज़ाइन साफ़ रहे।

उदाहरण जवाब का रूप:

GET /v1/autocomplete?q=din&limit=5

{
  "prefix": "din",
  "suggestions": [
    {"query": "dinner recipes", "score": 98012},
    {"query": "dinosaur", "score": 77120},
    {"query": "diners near me", "score": 54001}
  ]
}

खाली या एक-अक्षर प्रीफ़िक्स अजीब होते हैं (लगभग पूरा शब्दकोश)। कई प्रोडक्ट सर्वर कॉल से पहले २ या ३ अक्षर का इंतज़ार करते हैं, या बहुत छोटी इनपुट पर विशेष "ट्रेंडिंग" सूची दिखाते हैं।

हम पहले से क्यों बनाते हैं (सबसे ज़रूरी प्रोडक्शन विचार)

हर रिक्वेस्ट पर तुम यह कर सकते हो:

१. प्रीफ़िक्स नोड (din) तक चलो। २. उसके नीचे पूरा सब-ट्री घूमो। ३. हर पूरी क्वेरी इकट्ठा करो। ४. स्कोर से सॉर्ट करो। ५. टॉप ५ लो।

दुर्लभ प्रीफ़िक्स जैसे xylophone पर सब-ट्री छोटा है। आम प्रीफ़िक्स जैसे a या the पर विशाल हो सकता है। १०० मिलीसेकंड बजट में, ऊँचे क्यूपीएस पर, विशाल ढेर सॉर्ट करना टूट जाता है।

इसलिए हम पहले से बनाते हैं (प्रीकम्प्यूट)।

हर महत्वपूर्ण नोड पर (या हर महत्वपूर्ण प्रीफ़िक्स पर) जवाब पहले से रखो:

Node "din":
  top: [dinner recipes, dinosaur, diners near me, ...]

क्वेरी पथ बन जाता है:

१. नोड तक चलो (या प्रीफ़िक्स को मैप में खोजो)। २. पहले से रखी सूची लौटाओ।

तुम मेमोरी देकर लेटेंसी खरीदते हो। यह सौदा जानबूझकर है। ऑटोकम्प्लीट रीड-भारी प्रोडक्ट है जहाँ स्पीड ही प्रोडक्ट है।

वे सूची कब बनती हैं?

यूज़र के सामने हर कीस्ट्रोक पर नहीं। अलग से:

१. लोग सर्च पूरा करते हैं (लॉग)। २. पाइपलाइन आवृत्ति गिनती है (घंटे, दिन, हफ़्ता: प्रोडक्ट का चुनाव)। ३. एक जॉब नया ट्राइ बनाता है (या prefix → top-k मैप)। ४. सर्विंग मशीनें नया स्नैपशॉट लोड करके स्विच करती हैं।

रात को जेबी शब्दकोश छापने, और अगले दिन उसी छपे किताब से जवाब देने जैसा सोचो। समाचार वाले प्रोडक्ट में छोटा "ट्रेंडिंग" पथ भी जोड़ते हो, लेकिन मुख्य बात वही: भारी काम ऑफ़लाइन, ऑनलाइन तैयार सूची से जवाब।

दो पथ: सीखना बनाम जवाब देना

यह बाँट जल्दी खींचो। डिज़ाइन ईमानदार रहता है।

सीखना (धीमा ठीक है)
  पूरी सर्च → गिनती → टॉप-के बनाओ → स्नैपशॉट प्रकाशित

जवाब (तेज़ होना ज़रूरी)
  यूज़र टाइप → एपीआई → कैश / ट्राइ → टॉप-के सूची → जवाब

अगर हर पूरी सर्च पर दुनिया भर का एक जीवित वैश्विक पेड़ अपडेट करो, तो राइट तूफ़ान, लॉक झगड़े और असंगत रैंक आते हैं। पहले डिज़ाइन में समय-समय पर रीबिल्ड + एटॉमिक स्वैप बेहतर।

छोटी क्षमता कहानी (ताकि स्केल असली लगे)

इंटरव्यू के मोटे नंबर ज़ोर से कह सकते हो:

रोज़ १ करोड़ लोग प्रोडक्ट इस्तेमाल करें
हर व्यक्ति करीब १० बार सर्च करे
हर सर्च में करीब २० अक्षर (अगर हर अक्षर सर्वर पर जाए)

Average QPS ≈ 10M * 10 * 20 / 86400 ≈ 24,000
Peak might be about 2x → ~50,000

प्रोडक्शन में क्लाइंट को डिबाउंस करना चाहिए (आखिरी की के ~१५०-३०० मिलीसेकंड बाद कॉल) और नया अक्षर आने पर पुरानी रिक्वेस्ट रद्द करनी चाहिए। ट्रैफ़िक बहुत कटता है। फिर भी गरम, रीड-भारी एपीआई की योजना बनाओ।

साथ: ब्राउज़र गैर-निजी सुझाव कुछ देर कैश कर सकता है। सर्वर कैश (रेडिस या इन-प्रोसेस) गरम प्रीफ़िक्स जैसे din, how, ब्रांड नाम रखते हैं। मिस पर ट्राइ स्नैपशॉट से लोड।

सुरक्षा और गंदे नतीजे

अकेली लोकप्रियता बुरे सुझाव ला सकती है। नफ़रत भरी भाषा, ठगी या कानूनी हटान अगले हफ़्ते के रीबिल्ड का इंतज़ार नहीं कर सकते।

जवाब पथ पर तेज़ फ़िल्टर रखो:

पूरी क्वेरी और प्रीफ़िक्स की ब्लॉकलिस्ट
यूज़र तक पहुँचने से पहले मैच हटाओ
अगले रीबिल्ड में भी हटाओ ताकि टॉप-के स्लॉट न घेरें

अभी तुरंत छिपाओ, जल्द साफ़ इंडेक्स।

शब्दजाल में डूबे बिना स्केल

एक मशीन हर भाषा और हर लंबी-पूंछ क्वेरी हमेशा नहीं रखेगी।

इंटरव्यू में पसंद आने वाले व्यावहारिक विचार:

विचार	सादा मतलब
प्रीफ़िक्स से शार्ड	`a-m` से शुरू क्वेरी एक मशीन समूह पर, `n-z` दूसरे पर
अक्षर झुकाव ठीक करो	अंग्रेज़ी में `s` और `c` `x` और `z` से ज़्यादा; शुद्ध वर्णमाला टुकड़ों से नहीं, असली ट्रैफ़िक से शार्ड
लोकल ट्राइ	स्पेनिश रैंकिंग हिंदी से अलग; अलग इंडेक्स मदद करते हैं
न्यूनतम अक्षर	खाली स्ट्रिंग के लिए वैश्विक टॉप-के मत दो

दिन एक पर परफेक्ट वैश्विक रियल-टाइम ग्राफ़ की ज़रूरत नहीं। ज़रूरत है प्रीफ़िक्स → टॉप-के सेवा की जो ट्रैफ़िक बढ़ने पर भी तेज़ रहे।

क्लाइंट विवरण जो प्रोडक्ट अच्छा महसूस कराते हैं

विवरण	क्यों
डिबाउंस १५०-३०० मिलीसेकंड	हर की थपथपाहट पर रिक्वेस्ट न भेजो
उड़ती कॉल रद्द	बैकस्पेस पर पुरानी सूची न दिखे
न्यूनतम लंबाई २-३	पूरा शब्दकोश न उंडेलो
स्थानीय हालिया सर्च	ऑफ़लाइन या फ़ेल पर भी उपयोगी
प्रीफ़िक्स लंबाई सीमा	सर्च बॉक्स के लिए ५० अक्षर काफ़ी

बैकएंड डिज़ाइन मोबाइल ऐप और वेब दोनों के लिए एक जैसा।

सिरा-से-सिरा तस्वीर जो बचाई जा सके

प्रोडक्ट: लोकप्रियता से प्रीफ़िक्स टॉप-५, पीक पर हज़ारों क्यूपीएस, पी९९ ~१०० मिलीसेकंड से कम, पहले अंग्रेज़ी, समय-समय रीबिल्ड, तेज़ मॉडरेशन।

टुकड़े:

१. ऑटोकम्प्लीट एपीआई (स्टेटलेस, कई कॉपी) २. मेमोरी / रेडिस में ट्राइ या prefix → top-k स्नैपशॉट ३. टिकाऊ स्नैपशॉट स्टोर (संस्करण वाले बिल्ड) ४. लॉग → एग्रीगेट → बिल्ड वर्कर ५. रीड पथ ब्लॉकलिस्ट ६. ब्रेकिंग न्यूज़ के लिए वैकल्पिक छोटी-विंडो ट्रेंड मर्ज

क्वेरी: वैलिडेट → कैश → पहले से बना टॉप-के → फ़िल्टर → जवाब।

सीखना: पूरी सर्च सैंपल → एग्रीगेट → बनाओ → प्रकाशित → कैश गरम → वर्शन फ्लिप।

दोस्त के लिए सार

रात के खाने पर एक मिनट में समझाना हो तो:

ऑटोकम्प्लीट सर्च के लिए फ़ोन कीबोर्ड सुझाव जैसा है। तुम वाक्यांश की शुरुआत टाइप करते हो (प्रीफ़िक्स)। सिस्टम इतिहास की हर सर्च फिर नहीं पढ़ता। वह अक्षरों का पेड़ रखता है (ट्राइ)। हर कदम एक अक्षर। जब तुम d, फिर i, फिर n टाइप करते हो, वह d → i → n चलता है और उस रास्ते के नीचे सबसे लोकप्रिय पूरी क्वेरी की छोटी पहले-से-बनी सूची देखता है, जैसे dinner recipes और dinosaur। हम वे टॉप सूची असली सर्च गिनती से ऑफ़लाइन बनाते हैं ताकि हर कीस्ट्रोक सस्ता और तेज़ रहे। जवाब देना और नई सर्च से सीखना दो अलग काम हैं। हर सर्च पर एक ही जीवित अपडेट में मिलाना ही इन सिस्टम को धीमा और उलझा बनाता है।

यही डिज़ाइन है। बाकी (शार्ड, कैश, ट्रेंड, फ़िल्टर) उसी कहानी के आसपास विस्तार हैं।

शिप (या इंटरव्यू खत्म) से पहले चेकलिस्ट

प्रोडक्ट से सिर्फ़ प्रीफ़िक्स मैच तय
k और रैंकिंग नियम कहे (पहले आवृत्ति)
क्लाइंट डिबाउंस, रद्द, न्यूनतम अक्षर
नोड या प्रीफ़िक्स मैप पर टॉप-के संग्रहित
ऑफ़लाइन या समय-समय बिल्ड, एटॉमिक स्वैप
रीड पथ सुरक्षा फ़िल्टर, तेज़ अपडेट
गरम प्रीफ़िक्स के लिए कैश परतें
ऑटोकम्प्लीट एंडपॉइंट पर रेट लिमिट
डैशबोर्ड: लेटेंसी, कैश हिट दर, खाली नतीजे, बिल्ड लैग

समापन

सर्च ऑटोकम्प्लीट कोई दिखावटी एआई डेमो नहीं। यह नरम रियल-टाइम इंडेक्स वाला प्रीफ़िक्स टॉप-के सेवा है। प्रोडक्ट से मेल खाने वाली संरचना अक्षरों का पेड़ है। प्रोडक्शन चलाने वाला तरकीब उन नोड पर पहले से बनी छोटी सूची है जहाँ लोग सच में चलते हैं। सीखने का पथ और जवाब का पथ अलग रखो, सिस्टम तेज़ भी रहता है और समझ में भी आता है।