الأحمال الثقيلة وبروفتك
صمّم الإكمال التلقائي للبحث
تكتب ثلاثة أحرف ومحرك البحث يعرف سلفاً ما تريد. يفعل هذا مئة ألف مرة في الثانية، مع كل ضغطة زر من كل مستخدم، وبميزانية نحو 100 ميلي ثانية قبل أن تصبح الاقتراحات باهتة. الحيلة أن شيئاً يكاد لا يُحسب لحظة الكتابة — الإجابة كانت جاهزة قبل ساعات.
المتطلبات: أعطِ بادئة (prefix) فتستعيد أفضل 5 اقتراحات مرتبة بحسب الشعبية، بسرعة تكفي لعرضها قبل الضغطة التالية. فحص الحجم: محرك بحث كبير يستقبل نحو 100 ألف استعلام في الثانية — والإكمال التلقائي يعمل مع كل ضغطة زر لا مع كل بحث، فتوقّع أضعاف ذلك، لنقل 300–500 ألف طلب في الثانية عند الذروة. قراءة فقط، حساسية قصوى للزمن، وتسامح مع بيانات عمرها ساعات: هذه الخصائص الثلاث ستصمم النظام عنك.
البنية الأساسية هي trie: عقدة لكل حرف من كل بادئة، فكلمة «weather» تعيش تحت w ثم we ثم wea ثم weat… الخطوة الساذجة هي المشي إلى عقدة البادئة ثم مسح الشجرة الفرعية كلها لإيجاد أكثر خمسة استعلامات تكراراً — هذا O(حجم الشجرة الفرعية) لكل ضغطة زر، ويموت عند الحجم الكبير. التحسين الجوهري: خزّن اقتراحات top-k داخل كل عقدة، محسوبة مسبقاً. الآن البحث هو: امشِ p حرفاً واقرأ قائمة واحدة — O(طول البادئة)، بضع قفزات مؤشرات لا أكثر. الثمن هو الذاكرة: الكلمة الرائجة تظهر في قوائم ما يصل إلى p عقدة على مسارها، ومع 20 مليون عقدة بادئة وk = 5 و~30 بايت للمدخل، فأنت تنظر إلى عدة GB من الذاكرة. لهذا السبب تحديداً k تساوي 5 وليست 50.
أبداً ليست مباشرة. سجلات الاستعلامات تتدفق إلى pipeline غير متصل — مهمة batch يومية أو أسبوعية تجمع تكرارات كل استعلام (MapReduce أو Spark أو ما تستخدمه الشركة)، وترتّبها، وتنتج قائمة top-k لكل بادئة. وقبل أن يدخل أي شيء ذلك الترتيب، يمر عبر الترشيح (filtering): الألفاظ البذيئة وأنماط الإساءة والمحذوفات القانونية وهجمات الحقن المعروفة تُستبعد في مرحلة الـpipeline، بحيث لا تصل عبارة محظورة إلى الـtrie أصلاً — فضلاً عن شاشة مستخدم. أما محاولة تحديث الـtrie مع كل استعلام فتعني كتابات تتسابق بمئات الآلاف في الثانية ضد قرّاء يشترطون 100 ميلي ثانية: كابوس تنافس على الأقفال اخترت ببساطة ألا تعيشه.
عندما يتجاوز حجم الـtrie ذاكرة جهاز واحد، تقسّمه (sharding). التقسيم الساذج بنطاقات الحرف الأول — a–f هنا وg–l هناك — وهو منحرف: حرف «s» يحمل حركة أكبر بكثير من «x»، فيذوب shard بينما آخر عاطل. أما تطبيق hash على البادئة فيوزّع الحمل بالتساوي، بثمن فقدان محلية النطاقات التي لم تكن تحتاجها أصلاً. والتحديثات بنفس الحسّ المدروس: الـpipeline يبني الـtrie الجديد كاملاً دون اتصال، ويرسله إلى خوادم التقديم، ويستبدل كل خادم البنية القديمة بالجديدة ذرّياً — قلب مؤشر، أو تبديل دليل البيانات. القرّاء لا يرون أبداً trie نصف مبني، والبناء الفاسد يُتراجع عنه بإعادة قلب المؤشر.
الإكمال التلقائي إجابة محسوبة مسبقاً، يُعاد بناؤها دون اتصال وفق جدول. النظام المباشر يفعل شيئاً واحداً: يقرأ. كل جزء صعب — الترتيب والترشيح والحداثة — نُقل إلى مهمة batch حيث الدقائق رخيصة، ليبقى مسار التقديم مجرد مشية في الذاكرة تُقاس بالميكروثانية.
لماذا نخزّن قائمة top-k داخل كل عقدة من الـtrie، وما الثمن؟ (بدونها، الإجابة عن بادئة تعني مسح الشجرة الفرعية كاملة بحثاً عن أكثر k استعلامات تكراراً — O(حجم الشجرة الفرعية) لكل ضغطة زر، وهذا غير قابل للعمل مع مئات آلاف الطلبات في الثانية. ومعها، البحث O(طول البادئة): امشِ البادئة واقرأ قائمة جاهزة. الثمن هو الذاكرة — كل كلمة رائجة مكررة في قوائم ما يصل إلى p عقدة — إضافة إلى إعادة بناء offline في كل مرة تحتاج القوائم تحديثاً.)
شجرة trie للشكل، وtop-k في كل عقدة للسرعة، وpipeline غير متصل لسجلات الاستعلامات من أجل الترتيب، وترشيح قبل أن ترى الـtrie أي كلمة، وتقسيم بـhash البادئة عندما تنفد الذاكرة، واستبدال ذرّي كي لا ترمش التحديثات أبداً. الإكمال التلقائي أنقى مثال على «احسب مسار القراءة مسبقاً» ستصممه في حياتك.
خذ سجلات البحث من منتجك — أو مجموعة استعلامات عامة — وابنِ الـpipeline على الورق: كيف ستعدّ التكرارات، وماذا سترشّح، وكم مرة ستعيد البناء. ثم قدّر حجم الـtrie: كم بادئة، وأي k ستختار، وهل يسعها ذاكرة جهاز واحد. الأرقام ستفاجئك أقل مما تظن — وهذا هو المقصود.
الأحمال الثقيلة وبروفتك