अपूर्ण सिस्टम के फायदे: Bluesky की lossy timeline

• सिस्टम डिज़ाइन करते समय perfect consistency, availability, low latency और high throughput को एक साथ पूरी तरह हासिल करना व्यावहारिक रूप से बहुत कठिन होता है
  • एप्लिकेशन के अनुरूप सही balance point ढूंढकर उपयुक्त डिज़ाइन चुनना महत्वपूर्ण है
• Bluesky ने following feed/timeline डिज़ाइन में write performance बेहतर करने के लिए consistency का कुछ हिस्सा त्यागने वाला trade-off अपनाया
  • इसके परिणामस्वरूप, उपयोगकर्ताओं पर नकारात्मक असर डाले बिना P99 latency 96% से अधिक घट गई

टाइमलाइन fanout

• Bluesky में जब कोई उपयोगकर्ता पोस्ट करता है, तो सिस्टम उसे index करता है, database में store करता है, और API response के माध्यम से उपलब्ध कराता है
• साथ ही यह पोस्ट हर follower की timeline table में insert करने की “fanout” प्रक्रिया से गुजरती है
• इसमें follower list को fetch करने के बाद, हर follower की timeline table में reverse-order insertion किया जाता है
• timeline table उपयोगकर्ता-आधारित partitioning के साथ distributed DB (ScyllaDB) में store होती है, और high availability के लिए कई shards में replicate की जाती है
  • हर उपयोगकर्ता अलग shard पर assign हो सकता है
• storage space बचाने के लिए, एक निश्चित लंबाई से आगे बढ़ने वाली timelines से पुराने post references को नियमित रूप से हटाया जाता है

hot shard समस्या

• Bluesky के लगभग 3.2 करोड़ उपयोगकर्ता हैं, और timeline database सैकड़ों shards में विभाजित है
• लाखों उपयोगकर्ताओं वाले सिस्टम में, ऐसे उपयोगकर्ता मौजूद हो सकते हैं जिनके following संबंध असामान्य रूप से बहुत अधिक हों
  • उदाहरण: ऐसा उपयोगकर्ता जो लाखों नहीं तो कम से कम कई लाख accounts को follow करता हो
• एक shard में कई उपयोगकर्ताओं की timelines साथ में store होती हैं
• यदि कोई विशेष उपयोगकर्ता बहुत अधिक writes उत्पन्न करता है, तो वह shard overload होकर “hot shard” बन जाता है
• ऐसे hot shards पर write या read operations की भीड़ लग जाती है, और उसी shard के दूसरे उपयोगकर्ताओं तक भी latency फैल जाती है

latency का संचय

• यदि किसी उपयोगकर्ता के 2,000,000 followers हों, तो writes को क्रमवार करने पर 20 मिनट से अधिक लग सकते हैं
• इसे कम करने के लिए fanout को parallel करने पर average latency कम हो जाती है
• लेकिन P99 latency (लगभग 15 milliseconds या उससे अधिक) बार-बार होने पर पूरा parallel job धीमा हो सकता है
• followers बहुत अधिक होने पर, P99 या P99.9 latency के कारण कुल fanout time सबसे खराब स्थिति में कई मिनट से लेकर कई दसियों मिनट तक बढ़ सकता है

Lossy timeline

• जिन उपयोगकर्ताओं की following संख्या अत्यधिक अधिक है, उन्हें हर पोस्ट को बिल्कुल सही क्रम में दिखाना व्यवहारिक रूप से संभव नहीं है
• इंसान के लिए भी वास्तव में सभी पोस्ट consume करना कठिन है
• इसलिए, एक निश्चित threshold (उदाहरण: reasonable_limit) से अधिक following वाले उपयोगकर्ताओं की timeline में कुछ writes को probabilistically “drop” करने का तरीका अपनाया गया
• loss_factor = min(reasonable_limit / num_follows, 1) फ़ॉर्मूला उपयोग किया जाता है
• fanout के दौरान random value बनाई जाती है, और यदि वह loss_factor से बड़ी हो, तो timeline write छोड़ दी जाती है
• इससे किसी विशेष उपयोगकर्ता की timeline पर होने वाली अत्यधिक writes सीमित होती हैं और पूरे shard की performance गिरने से बचती है

caching के बारे में

• timeline writes प्रति सेकंड दस लाख से अधिक हो सकती हैं, इसलिए हर write पर उपयोगकर्ता की following count सीधे DB से पूछना बहुत भारी पड़ता है
• इसके बजाय Redis में high-following accounts को sorted set के रूप में cache किया जाता है
• fanout service instances हर 30 सेकंड में इस cached जानकारी को memory में load करते हैं
• नतीजतन, fanout प्रक्रिया के दौरान भी high-following उपयोगकर्ताओं की जानकारी तेज़ी से प्राप्त की जा सकती है
• क्योंकि cached जानकारी का पूरी तरह ताज़ा होना ज़रूरी नहीं है, यह थोड़ा-सा अपूर्णता स्वीकार कर performance और scalability बढ़ाने का तरीका है

परिणाम

• lossy timeline लागू करने के बाद Timelines database में hot shards लगभग पूरी तरह गायब हो गए
• fanout के एक page को process करने में लगने वाली P99 latency 90% से अधिक कम हो गई
• कुल fanout job time में, P99 के आधार पर 5~10 मिनट लेने वाला काम 10 सेकंड से कम में सिमट गया
• इससे यह दिखता है कि consistency का कुछ हिस्सा त्यागकर भी service users की अपेक्षाएँ पूरी की जा सकती हैं और large-scale scalability बनाए रखी जा सकती है
• Bluesky timeline architecture में अभी भी सुधार की गुंजाइश है, लेकिन इस बदलाव ने write throughput और scalability को काफी बढ़ा दिया है

[GN⁺]

Hacker News राय

• सिस्टम पसंद करने वाले व्यक्ति के रूप में, मुझे इस तरह के लेख पसंद आते हैं। "सब कुछ परफेक्ट होना चाहिए" वाली सोच में फँसना आसान है

  • Blekko search engine के backend में एक 'eventually consistent' index बनाया था। इससे users को updates जल्दी मिलते हैं, लेकिन एक ही query चलाने वाले दो users को थोड़ा अलग results मिल सकते हैं
  • इसमें काफी system theory लागू होती है, और positive feedback होने पर oscillation की संभावना रहती है। Search engine में user जिन links पर click करते हैं, उन्हें weight देने वाला ranker positive feedback देता है
  • सिस्टम को "critically damped" बनाए रखना महत्वपूर्ण था। इससे वह जल्दी converge करता है
  • user timeline के sharding होने और feedback loop (जैसे 'like' या 'repost') मौजूद होने का तरीका एक दिलचस्प problem space लगता है

• यह hybrid तरीके से account की popularity के आधार पर timeline implement क्यों नहीं करते, यह जानने की जिज्ञासा है

  • celebrity accounts के लिए, हर message को लाखों followers तक fan-out करने की बजाय, followers की timeline serve करते समय celebrity की posts को fetch करके merge करना सस्ता होगा
  • अगर लाखों followers ऐसा करें, तो hot cache से read-only fetch करना सस्ता होगा

• दिलचस्प समस्या के लिए दिलचस्प समाधान है। इसे साझा करने के लिए धन्यवाद

  • लेखक जहाँ "celebrity" से "bot" पर शिफ्ट होता है, उस हिस्से को समझने में कठिनाई हुई
  • ऐसा लगा कि लेखक ने "lossy timeline" का एक बिल्कुल अलग concept पेश कर दिया

• consistency को sacrifice करने वाली इस strategy को लेकर जिज्ञासा है। पढ़ने या लिखने के समय full fan-out के अलावा किसी और तरीके पर विचार है या नहीं, यह जानना चाहता हूँ

  • हर user की timeline पर लिखने की बजाय, कम से कम एक follower वाले shard पर सिर्फ एक बार लिखने का तरीका कल्पना कर सकता हूँ
  • read के समय, दिए गए user का content fetch करके वास्तविक followers को filter किया जा सकता है
  • read shard के भीतर ही होने से latency कम रहती है
  • mega-followers के मामले में page पुराने items नहीं देखेगा

• सभी users जिन हजारों users को follow करते हैं, उनके हर post को पूरी तरह chronological order में देना ज़रूरी नहीं है, लेकिन timeline में हमेशा नया content बना रहे, इसके लिए पर्याप्त content देना तर्कसंगत है

  • समाधान imperfect chronology नहीं, बल्कि feed में posts miss होने जैसा लगा

• hot shard समस्या से बचने के लिए followers की संख्या सीमित करने का तरीका कैसे काम करेगा, यह जानने की जिज्ञासा है

  • हर user के पास हर 1000 followers पर एक अलग timeline हो, और client उन्हें merge करे
  • ज़रूरत होने पर, lossy हिस्से को लागू करने के लिए वास्तविक timeline का सिर्फ कुछ हिस्सा load किया जा सकता है

• AWS के पास इस समस्या के लिए एक अच्छा सामान्य तरीका है

  • हर user को कई shards में assign किया जाता है ताकि दूसरे users के सभी shards साझा करने की संभावना कम हो
  • अगर शुरुआत से shuffle sharding किया गया होता, तो बहुत से दूसरे users को प्रभावित किए बिना नई समस्याओं को हल किया जा सकता था

• जो accounts लाखों users को follow करते हैं, वे साफ तौर पर content scrape करने वाले bot accounts हैं। मैं तो उन्हें block करके बात खत्म कर देता

  • मुझे technical challenges के बारे में पढ़ना पसंद है। Twitter के पास लाखों followers वाले celebrities के लिए एक विशेष architecture है
  • अगर Bluesky वैसा ही similar clone है, तो उसने वही रास्ता क्यों नहीं अपनाया, यह जानने की जिज्ञासा है

• जब सीधे user profile पर जाकर सभी posts देखते हैं, तो कभी-कभी ऐसे posts मिलते हैं जो timeline में होने चाहिए थे लेकिन नहीं थे

  • यह बताता है कि Bluesky पर 100 से कम users को follow करने के बावजूद, कभी-कभी timeline में किसी user की posts क्यों नहीं दिखतीं

• यह जानने की जिज्ञासा है कि fan-out को इस तरह क्यों implement किया गया जहाँ हर "page" अगला page fetch करने को block करता है

  • page fetch activity में followers को क्रमिक रूप से fetch करना चाहिए, और page के सभी items update होने तक इंतज़ार नहीं करना चाहिए
  • दिमाग में यह विचार आता है कि एक fetch component हो जो page fetch करके उसे S3 में store करे, और metadata व S3 location को queue (SQS) में publish करे
  • इस सिस्टम में concurrency को बेहतर तरीके से control किया जा सकता है, और shard को key की तरह इस्तेमाल कर queue में partitioning करके काम को "धीमा" किया जा सकता है