संक्षेप (टीएल;डीआर)
- समस्या: होम फीड को हर उपयोगकर्ता को उन सैकड़ों खातों की सबसे नई और प्रासंगिक पोस्ट दिखानी है जिन्हें वह फॉलो करता है, २०० मिलीसेकंड से कम में, करोड़ों उपयोगकर्ताओं के लिए, जबकि कुछ खातों के करोड़ों फॉलोअर हैं।
- डिजाइन: पोस्ट बनते ही हर फॉलोअर की रेडिस सूची में पोस्ट आईडी डालकर टाइमलाइन पहले से तैयार करें (लिखते समय फैलाव), सिवाय बहुत बड़े खातों के, जिनकी पोस्ट पढ़ते समय खींचकर मिलाई जाती हैं। एक फीड सेवा दोनों स्रोत मिलाती है, उम्मीदवारों की रैंकिंग करती है, कैश से पोस्ट और उपयोगकर्ता की जानकारी भरती है और कर्सर से पन्ने देती है।
- नतीजा: फीड पढ़ना एक सस्ती सूची खोज और जानकारी भरना बन जाता है, लेखन को वर्कर असिंक्रोनस रूप से संभालते हैं, और मशहूर हस्तियों की समस्या लेखन की आंधी से बदलकर पढ़ते समय का एक छोटा मेल बन जाती है।
न्यूज फीड सिस्टम डिजाइन की वह समस्या है जो एक खास समझ को सबसे ज्यादा इनाम देती है। बाकी सब (कैश, बंटवारा, रैंकिंग) सहायक भूमिका में हैं। समझ यह है: आपको तय करना है कि फीड जोड़ने का काम कब होगा, लिखते समय या पढ़ते समय, और जवाब है "दोनों, इस पर निर्भर कि पोस्ट किसने की।"
यह लेख उसी फैसले के इर्द-गिर्द फीड बनाता है।
जरूरतें और संख्याएं
कार्यात्मक: उपयोगकर्ता पोस्ट करते हैं (टेक्स्ट, चित्र, वीडियो); उपयोगकर्ता फॉलो किए खातों की पोस्ट वाली होम फीड देखते हैं, सबसे नई या सबसे प्रासंगिक पहले; अंतहीन स्क्रॉल।
गैर-कार्यात्मक: फीड लोड का पी९९ २०० मिलीसेकंड से कम; नई पोस्ट सेकंडों में फॉलोअर की फीड में दिखे (जरूरी नहीं कि तुरंत); किसी मशहूर हस्ती के पोस्ट करने पर सिस्टम टिका रहे।
| मान्यता | मान | नतीजा |
|---|---|---|
| रोज के सक्रिय उपयोगकर्ता | ३० करोड़ | |
| हर उपयोगकर्ता के रोज फीड लोड | १० | रोज ३ अरब पठन, औसतन लगभग ३५ हजार प्रति सेकंड, शिखर पर लगभग १ लाख |
| रोज की पोस्ट | ५ करोड़ | औसतन लगभग ६०० प्रति सेकंड |
| हर लेखक के औसत फॉलोअर | २०० | रोज १० अरब टाइमलाइन प्रविष्टियां, लगभग १.१५ लाख प्रति सेकंड |
| रखी गई टाइमलाइन की लंबाई | ८०० पोस्ट आईडी गुणा ८ बाइट | प्रति उपयोगकर्ता लगभग ६.४ केबी, सबके लिए रेडिस के अतिरिक्त खर्च से पहले लगभग २ टीबी |
दो बातें तुरंत दिखती हैं। अनुरोधों की संख्या में फीड पठन हावी हैं। लेकिन फैलाव लेखन को फॉलोअर संख्या से गुणा कर देता है, इसलिए पोस्ट बनाना नहीं, टाइमलाइन में प्रविष्टियां डालना सबसे बड़ा लेखन भार है। हर डिजाइन को इसका हिसाब रखना होगा।
ट्विटर ने २०१२ में इसी शक्ल की संख्याएं बताई थीं: हर सेकंड लगभग ३ लाख टाइमलाइन पठन, जबकि हर सेकंड लगभग ६,००० ट्वीट लिखे जाते थे, होम टाइमलाइन रेडिस में ८०० प्रविष्टियों तक सीमित, और करोड़ों फॉलोअर वाले खातों के फैलाव में कई मिनट लगते थे।
मुख्य फैसला: फीड कब बनती है?
| लिखते समय फैलाव (पुश) | पढ़ते समय फैलाव (पुल) | |
|---|---|---|
| काम कब होता है | पोस्ट करते समय, हर फॉलोअर की टाइमलाइन में पोस्ट आईडी डालो | पढ़ते समय, हर फॉलो किए खाते की हाल की पोस्ट लाओ और मिलाओ |
| पढ़ने की लागत | एक सूची पढ़ना | एन खोजें, हर फॉलो किए खाते के लिए एक, और मिलाना |
| लिखने की लागत | हर फॉलोअर के लिए एक प्रविष्टि | एक प्रविष्टि |
| ताजगी | फैलाव में कुछ सेकंड की देरी | हमेशा ताजा |
| बेकार काम | उन उपयोगकर्ताओं की टाइमलाइन जो ऐप खोलते ही नहीं | कोई नहीं |
| कहां टूटता है | करोड़ों फॉलोअर वाली मशहूर हस्तियां | हजारों खाते फॉलो करने वाले उपयोगकर्ता |
कोई भी शुद्ध तरीका असली सोशल ग्राफ के सामने नहीं टिकता। पुश किसी मशहूर हस्ती की एक पोस्ट को करोड़ों लेखनों में बदल देता है। पुल हर फीड लोड को सैकड़ों खोजों में बदल देता है।
मिला-जुला तरीका, जिस पर उत्पादन सिस्टम पहुंचते हैं: सामान्य खातों के लिए पुश, बहुत बड़े खातों के छोटे समूह के लिए पुल, और पढ़ते समय मेल। ट्विटर ने ठीक यही बताया था। फेसबुक का मल्टीफीड पढ़ते समय जोड़ने की ओर और आगे गया, जहां फीड मांगे जाने पर एकत्रक सर्वर हर उपयोगकर्ता के गतिविधि स्टोर से पूछते हैं। दोनों सही हैं; मिला-जुला तरीका इंटरव्यू में बचाव करने और मध्यम पैमाने पर चलाने में आसान है।
पोस्ट करने का रास्ता
- लेखक। पोस्ट करता है। मीडिया पहले सीधे ऑब्जेक्ट स्टोरेज में जाता है (पहले से हस्ताक्षरित यूआरएल); पोस्ट सिर्फ उसका हवाला देती है।
- एपीआई गेटवे। प्रमाणीकरण, दर सीमा, अनुरोध की जांच।
- पोस्ट सेवा। समय से क्रमबद्ध आईडी देती है (स्नोफ्लेक शैली, देखें अद्वितीय आईडी लेख), पोस्ट लिखती है और उपयोगकर्ता को तुरंत जवाब देती है। फैलाव का इंतजार नहीं करती।
- पोस्ट डेटाबेस (आईडी से बंटा)। पोस्ट की सामग्री का सच्चा स्रोत। समय से क्रमबद्ध आईडी के कारण
(author_id, post_id)पर सूचकांक के साथ "लेखक एक्स की हाल की पोस्ट" एक सस्ती सीमा खोज बन जाती है। - पोस्ट बनने की घटनाएं। एक टिकाऊ लॉग उपयोगकर्ता के अनुरोध को महंगे फैलाव से अलग करता है। फैलाव पीछे रह जाए तब भी पोस्ट करना चलता रहता है।
- फैलाव वर्कर। घटनाएं लेते हैं, लेखक के फॉलोअर को कुछ हजार के बैच में देखते हैं, और हर एक की टाइमलाइन में पोस्ट आईडी डालते हैं। हफ्तों से निष्क्रिय फॉलोअर छोड़े जा सकते हैं; लौटने पर उनकी फीड मांग पर दोबारा बनती है।
- सोशल ग्राफ (फॉलोअर)। "एक्स को कौन फॉलो करता है" और "वाई किसे फॉलो करता है" के लिए बना स्टोर। फेसबुक का टीएओ बड़े पैमाने का क्लासिक उदाहरण है। छोटे पैमाने पर दो सूचकांकों वाली किनारों की बंटी हुई तालिका काफी है।
- रेडिस टाइमलाइन। हर उपयोगकर्ता की हाल की पोस्ट आईडी की एक सूची। नई आईडी
LPUSHकरें,LTRIMसे ८०० तक काटें। सिर्फ आईडी, पूरी पोस्ट कभी नहीं, ताकि पोस्ट बदलने या मिटाने पर करोड़ों सूचियां न छूनी पड़ें।
लाल नोट मशहूर हस्तियों का नियम है: फॉलोअर की एक सीमा से ऊपर (दस लाख से शुरुआत ठीक है), फैलाव पूरी तरह छोड़ दें और पढ़ने वालों को खींचने दें।
पढ़ने का रास्ता
१. डाली गई आईडी पढ़ें उपयोगकर्ता की रेडिस टाइमलाइन से। २. मशहूर हस्तियों की पोस्ट खींचें। उपयोगकर्ता जिन गिने-चुने बड़े खातों को फॉलो करता है, उनकी हाल की पोस्ट आईडी "लेखक की हाल की पोस्ट" वाले भारी कैश वाले स्टोर से लाएं। क्योंकि बहुत से पाठक उन्हीं हस्तियों को फॉलो करते हैं, इस कैश की हिट दर बेहतरीन होती है। ३. रैंक करें। दोनों सूचियों को उम्मीदवारों के एक समूह (कुछ सौ पोस्ट) में मिलाकर रैंकिंग सेवा को भेजें, जो लेखक से जुड़ाव, पोस्ट की उम्र, अब तक की प्रतिक्रिया और सामग्री के प्रकार जैसे संकेतों से अंक देती है। ४. जानकारी भरें। सबसे ऊपर के नतीजों की पोस्ट सामग्री, लेखक प्रोफाइल और काउंटर एक ही बैच कॉल में कैश से लाएं। ५. कर्सर के साथ एक पन्ना लौटाएं। मीडिया यूआरएल सीडीएन की ओर इशारा करते हैं, इसलिए चित्र और वीडियो कभी फीड सेवा से नहीं गुजरते।
हरा नोट पन्ने बांटने के बारे में है, जिसे गलत करना आसान है। ऑफसेट नहीं, कर्सर इस्तेमाल करें। ऑफसेट के साथ पहले और दूसरे पन्ने के बीच आई नई पोस्ट सब कुछ एक जगह खिसका देती है, और उपयोगकर्ता दोहराव देखते हैं। कर्सर के साथ ("आईडी एक्स से पुरानी पोस्ट", या रैंकर की जगह बताने वाला अपारदर्शी टोकन) पन्ने स्थिर रहते हैं।
रैंकिंग, सरल से असली तक
| चरण | तरीका | लागत |
|---|---|---|
| संस्करण १ | पोस्ट आईडी से उल्टा कालक्रम | कुछ नहीं। समय से क्रमबद्ध आईडी इसे मुफ्त बनाती हैं |
| संस्करण २ | अनुमान आधारित अंक: जुड़ाव गुणा सामग्री का भार गुणा समय के साथ घटाव | हर उम्मीदवार के कुछ संकेत; समझाना आसान |
| संस्करण ३ | दो चरणों वाली मशीन लर्निंग रैंकिंग: सस्ते में उम्मीदवार चुनना, फिर कुछ सौ पर सीखा हुआ मॉडल | फीचर स्टोर, मॉडल सर्विंग, प्रयोग मंच |
फेसबुक का शुरुआती एजरैंक ठीक इसी शक्ल का संस्करण २ वाला अनुमान था। आज ज्यादातर बड़ी फीड संस्करण ३ हैं। इंटरव्यू में संस्करण १ से शुरू करें, संस्करण २ बताएं, और कहें कि संस्करण ३ मौजूद है। पूछे बिना मशीन लर्निंग सिस्टम डिजाइन न करें।
रैंकिंग जो भी हो, उसे लेखन के रास्ते से बाहर रखें। रैंकिंग पाठक, दिन के समय और उस प्रतिक्रिया पर निर्भर है जो अभी हुई ही नहीं, इसलिए उसकी जगह पढ़ते समय है।
डेटा मॉडल का खाका
| स्टोर | कुंजी | मान | टिप्पणी |
|---|---|---|---|
| पोस्ट डेटाबेस | post_id |
लेखक, टेक्स्ट, मीडिया हवाले, बनने का समय | लेखक की टाइमलाइन के लिए (author_id, post_id) पर सूचकांक |
| सोशल ग्राफ | (follower_id, followee_id) |
बनने का समय | दोनों दिशाएं सूचीबद्ध: एक्स के फॉलोअर, वाई किसे फॉलो करता है |
| रेडिस टाइमलाइन | timeline:{user_id} |
पोस्ट आईडी की सूची | ८०० तक सीमित; निष्क्रिय उपयोगकर्ताओं के लिए टीटीएल |
| पोस्ट कैश | post:{post_id} |
क्रमबद्ध पोस्ट | बनने पर सीधा लेखन, बदलने या मिटाने पर अमान्य |
| काउंटर | post:{post_id}:likes |
पूर्णांक | पोस्ट से अलग; असिंक्रोनस रूप से अपडेट |
क्या गलत होता है
| समस्या | लक्षण | इलाज |
|---|---|---|
| मशहूर हस्तियों की पोस्ट | फैलाव की कतार मिनटों तक अटकी | फॉलोअर सीमा; पढ़ते समय पुल |
| गर्म पोस्ट | एक पोस्ट के काउंटर और कैश कुंजी पर अतिभार | बंटे काउंटर; स्थानीय कैश; अनुमानित गिनती |
| मिटाई गई पोस्ट फिर भी दिखे | आईडी करोड़ों टाइमलाइन में बनी रहती हैं | जानकारी भरते समय छानें: गायब या मिटाई पोस्ट हटाएं |
| फैलाव में देरी | नई पोस्ट देर से दिखती हैं | हाल में सक्रिय फॉलोअर को पहले फैलाव |
| रेडिस नोड खोना | कुछ टाइमलाइन खाली | फॉलो किए लेखकों से खींचकर मांग पर दोबारा बनाएं; रेडिस प्रतिकृतियां |
| हजारों को फॉलो करने वाले | अगर कई "मशहूर" हैं तो बड़े मेल | खींचे जाने वाले लेखकों की सीमा; बाकी के लिए पुश पर भरोसा |
| फीड में एक ही पोस्ट दो बार | ऑफसेट से पन्ने | कर्सर से पन्ने |
इंटरव्यू का समापन
एक मजबूत जवाब इस क्रम में आता है:
१. जरूरतें और पढ़ने-लिखने की संख्याएं, फैलाव का गुणक भी। २. पुश बनाम पुल की तालिका, और क्यों अकेला कोई नहीं चलता। ३. मशहूर हस्तियों की सीमा के साथ मिला-जुला तरीका। ४. असिंक्रोनस फैलाव वर्कर और सिर्फ आईडी वाली टाइमलाइन के साथ पोस्ट का रास्ता। ५. पढ़ने का रास्ता: मिलाना, रैंक करना, जानकारी भरना, कर्सर। ६. एक या दो विफलताएं (मशहूर हस्तियां, मिटाना)।
उत्पादन जांच सूची
- फैलाव असिंक्रोनस है; पोस्ट करना कभी उसका इंतजार नहीं करता
- टाइमलाइन सिर्फ आईडी रखती हैं, लंबाई सीमित, निष्क्रिय उपयोगकर्ताओं के लिए टीटीएल
- मशहूर हस्तियों की सीमा तय और उस पर नजर (लेखक के आकार के हिसाब से फैलाव की देरी)
- फैलाव में निष्क्रिय फॉलोअर छोड़े जाते हैं; मांग पर दोबारा बनाना काम करता है
- जानकारी भरते समय मिटाई, निजी और ब्लॉक की गई सामग्री छानी जाती है
- कर्सर आधारित पन्ने
- रैंकिंग लेखन रास्ते से अलग, और रैंकर बंद हो तो कालक्रम वाला विकल्प
- डैशबोर्ड: फीड पी९९, फैलाव कतार की देरी, टाइमलाइन कैश हिट दर, जानकारी भरने के बैच का आकार
जो बचा रह गया
फीड वह जगह है जहां आपके सोशल ग्राफ की असमानता इंजीनियरिंग समस्या बन जाती है। ज्यादातर लोगों के कुछ सौ फॉलोअर हैं। कुछ के करोड़ों। एक डिजाइन दोनों की सेवा नहीं कर सकता, इसलिए आप दो बनाते हैं और उन्हें आखिरी संभव पल में सिल देते हैं।
इस वक्त फैलाव की कतार में कहीं किसी दस फॉलोअर वाले व्यक्ति की पोस्ट किसी पॉप स्टार के पीछे इंतजार कर रही है। मिला-जुला तरीका इसीलिए है कि वह पोस्ट भी समय पर पहुंचे।
स्रोत
- हाई स्केलेबिलिटी: १५ करोड़ सक्रिय उपयोगकर्ताओं और ३ लाख प्रति सेकंड के लिए ट्विटर का आर्किटेक्चर (रफी क्रिकोरियन की वार्ता)
- ब्रॉन्सन और साथी, टीएओ: सोशल ग्राफ के लिए फेसबुक का वितरित डेटा स्टोर (यूजेनिक्स एटीसी २०१३)
- फेसबुक इंजीनियरिंग: फेसबुक मल्टीफीड परोसना
- रेडिस दस्तावेज: सूचियां
- इसी श्रृंखला में: अद्वितीय आईडी जनरेटर डिजाइन करें, चैट सिस्टम डिजाइन करें, शून्य से लाखों उपयोगकर्ताओं तक