// أنظمة ثقيلة وتمرين ختامي
صمّم الإكمال التلقائي في البحث
مسار تصميم الأنظمة · 20 دقيقة
- تشرح كيف تجيب شجرة trie، في كل عقدة منها قائمة جاهزة بأفضل الاقتراحات، عن كل ضغطة زر في أجزاء من الملّي ثانية.
- تصمم الخط الذي يعمل في الخلفية ليبني الاقتراحات وينقيها ثم يستبدلها بالقديمة.
- تختار طريقة تقسيم الشجرة على السيرفرات، وتتجنب فخ التقسيم بالحرف الأول.
تدخل المقهى الذي تجلس فيه كل يوم، وقبل أن تكمل جملتك يقول لك النادل: «قهوة مضبوطة كالعادة؟». هو لم يفكر لحظتها. الجواب كان جاهزاً في رأسه من قبل.
خانة البحث تفعل الشيء نفسه. تكتب ثلاثة أحرف فتعرف ما تريد. وتفعل ذلك مع كل ضغطة زر لكل مستخدم، مئات الآلاف من المرات في الثانية، وأمامها نحو 100 ملّي ثانية فقط قبل أن يشعر المستخدم أن الاقتراح تأخر. والسر أن شيئاً تقريباً لا يُحسب وأنت تكتب. الجواب جاهز منذ ساعات.
المطلوب: نعطيك ما كتبه المستخدم حتى الآن (البادئة، أو prefix)، فترجع أفضل 5 اقتراحات حسب شعبيتها، بسرعة تكفي لتظهر قبل الضغطة التالية.
الحجم: محرك بحث كبير يستقبل نحو 100,000 عملية بحث في الثانية. لكن الإكمال التلقائي يعمل مع كل ضغطة زر، لا مع كل بحث، فتوقّع أضعاف ذلك، لنقل من 300,000 إلى 500,000 طلب في الثانية وقت الذروة.
ثلاث صفات ستصمم النظام عنك: النظام للقراءة فقط، ويجب أن يكون سريعاً جداً، ولا مشكلة إن كانت بياناته قديمة ببضع ساعات.
البنية الأساسية هنا هي شجرة trie: شجرة فيها عقدة لكل حرف، فكلمة «weather» تجدها تحت w، ثم we، ثم wea، ثم weat، وهكذا.
الطريقة الساذجة: انزل إلى عقدة البادئة، ثم ابحث في كل الفروع التي تحتها عن أشهر خمسة اقتراحات. هذه التكلفة تكبر مع حجم الفروع، ومع كل ضغطة زر، فتنهار مع الحجم الكبير.
الحيلة المهمة: احفظ قائمة top-k، أي أفضل k اقتراحات (وهنا k تساوي 5)، داخل كل عقدة، محسوبة مسبقاً. الآن البحث يعني أن تنزل عدد أحرف البادئة فقط، ثم تقرأ قائمة جاهزة. بضع خطوات، مهما كان حجم الشجرة.
الثمن هو الذاكرة. الاقتراح المشهور يتكرر في قائمة كل عقدة على طريقه. ومع 20 مليون عقدة، وفي كل منها 5 اقتراحات، ونحو 30 بايت لكل اقتراح، تحتاج قرابة 3 GB من الذاكرة. ولهذا بالضبط تكون k خمسة وليس خمسين.
ليس من الطلبات الحية أبداً. سجلات البحث تذهب إلى خط معالجة يعمل في الخلفية: مهمة تعمل يومياً أو أسبوعياً (MapReduce أو Spark أو ما يستخدمه فريقك)، تعدّ كم مرة بُحث عن كل عبارة، وترتبها، وتبني قائمة أفضل الاقتراحات لكل بادئة.
وقبل أي ترتيب تأتي التنقية. الألفاظ البذيئة والإساءات والعبارات المحذوفة لأسباب قانونية ونصوص الهجمات المعروفة كلها تُحذف داخل هذا الخط، فلا تصل أي عبارة ممنوعة إلى الشجرة، فضلاً عن شاشة المستخدم.
ولماذا لا نحدّث الشجرة مع كل عملية بحث؟ لأن مئات الآلاف من عمليات الكتابة في الثانية ستتصارع حينها مع قراءات تحتاج جوابها خلال 100 ملّي ثانية. وحين تنقل العمل إلى الخلفية، تتجنب هذا الصراع من أساسه.
حين لا تعود الشجرة تتسع في ذاكرة جهاز واحد، تقسّمها على عدة سيرفرات (sharding). أول فكرة تخطر على البال التقسيم بالحرف الأول: من a إلى f على سيرفر، ومن g إلى l على آخر، وهكذا. لكنه تقسيم غير متوازن أبداً. عمليات البحث التي تبدأ بحرف «s» أكثر بكثير من التي تبدأ بـ«x»، فينهار سيرفر بينما يجلس آخر بلا عمل. أما حساب hash للبادئة فيوزع الحمل بالتساوي، كما رأيت في درس البيانات على نطاق واسع.
والتحديث يتم بالحذر نفسه. خط المعالجة يبني الشجرة الجديدة كاملة في الخلفية، ثم يرسلها إلى السيرفرات. وكل سيرفر ينتقل من الشجرة القديمة إلى الجديدة في خطوة واحدة، بتغيير مؤشر. القراءات لا ترى أبداً شجرة نصف جاهزة، وإذا ظهر خطأ في النسخة الجديدة، ترجع المؤشر إلى القديمة.
الإكمال التلقائي جواب محضّر مسبقاً، يُعاد بناؤه حسب جدول. والنظام الحي يفعل شيئاً واحداً: القراءة. وكل جزء صعب، الترتيب والتنقية والتحديث، انتقل إلى مهمة في الخلفية حيث الدقائق رخيصة، ليبقى الطريق الحي مجرد خطوات قليلة داخل الذاكرة.
خطأ شائع أن تحاول جعل الاقتراحات أحدث بأن تكتب كل عملية بحث في الشجرة لحظة حدوثها. تبدو فكرة ذكية على السبورة، لكنها تكسر الشيء الوحيد المهم هنا: سرعة القراءة. وإذا احتجت فعلاً لعبارات رائجة خلال دقائق (خبر عاجل مثلاً)، أضف طبقة صغيرة منفصلة للعبارات الرائجة حديثاً وادمجها وقت القراءة، واترك الشجرة الأساسية تُبنى في الخلفية.
لماذا نحفظ قائمة بأفضل الاقتراحات داخل كل عقدة من الشجرة؟ وما الثمن؟
جاوب في ذهنك أولاً، ثم تأكد.
شجرة trie للشكل، وقائمة أفضل الاقتراحات في كل عقدة للسرعة، وخط معالجة في الخلفية على سجلات البحث للترتيب، وتنقية قبل أن يصل أي شيء إلى الشجرة، وتقسيم بالـhash حين تنفد الذاكرة، واستبدال في خطوة واحدة حتى لا يلاحظ أحد التحديث. الإكمال التلقائي أوضح مثال ستقابله على فكرة: جهّز طريق القراءة مسبقاً.
خذ سجلات البحث من منتجك، أو مجموعة بيانات بحث عامة، وصمم خط المعالجة على الورق: كيف ستعدّ مرات البحث، وماذا ستحذف، وكل كم ستعيد البناء. ثم قدّر حجم الشجرة: كم بادئة عندك، وكم ستكون k، وهل تتسع في ذاكرة جهاز واحد؟ احسبها، فغالباً ستجدها أصغر مما يتوقع الناس.
- تشرح كيف تجيب شجرة trie، في كل عقدة منها قائمة جاهزة بأفضل الاقتراحات، عن كل ضغطة زر في أجزاء من الملّي ثانية.
- تصمم الخط الذي يعمل في الخلفية ليبني الاقتراحات وينقيها ثم يستبدلها بالقديمة.
- تختار طريقة تقسيم الشجرة على السيرفرات، وتتجنب فخ التقسيم بالحرف الأول.
أنظمة ثقيلة وتمرين ختامي