حدث قبل أيام قليلة مؤتمر هيدرا. دعا الرجال من مجموعة JUG.ru متحدثي الأحلام (Leslie Lamport! Cliff Click! Martin Kleppmann!) وخصصوا يومين للأنظمة الموزعة والحوسبة. كان Kontur أحد الشركاء الثلاثة في المؤتمر. تحدثنا في الكشك ، وتحدثنا عن التخزين الموزع لدينا ، ولعبنا لعبة البنغو ، وحلنا الألغاز.

هذا منشور يحتوي على تحليل للمهام في منصة Kontur من مؤلف نصهم. من كان في Hydra - هذا هو سبب تذكرك للتجربة الممتعة ، من لم يكن - فرصة لتمديد عقلك يا كبير-الرموز.

حتى أن هناك مشاركين قاموا بتفكيك اللوح الورقي إلى شرائح لتدوين قرارهم. أنا لا أمزح - لقد سلموا هذه المجموعة من الأوراق للتحقق منها:

كانت هناك ثلاث مهام في المجموع:

• حول اختيار النسخ المتماثلة بالأوزان لموازنة التحميل
• حول فرز نتائج الاستعلام مقابل قاعدة بيانات في الذاكرة
• على نقل الحالة في نظام موزع مع طوبولوجيا حلقية

المهمة 1. ClusterClient

كان من الضروري اقتراح خوارزمية للاختيار الفعال لـ K من النسخ المتماثلة المرجحة N لنظام موزع:

تم تكليف فريقك بتطوير مكتبة عميل لمجموعة موزعة بشكل كبير من العقد N. ستقوم المكتبة بتتبع البيانات الوصفية المختلفة المرتبطة بالعقد (على سبيل المثال ، زمن الوصول ، ومعدلات استجابة 4xx / 5xx ، وما إلى ذلك) وتخصيص أوزان النقطة العائمة W1..WN لهم. من أجل دعم استراتيجية التنفيذ المتزامن ، يجب أن تكون المكتبة قادرة على اختيار K من N العقد بشكل عشوائي - يجب أن تكون فرصة الاختيار متناسبة مع وزن العقدة.

اقترح خوارزمية لتحديد العقد بكفاءة. تقدير التعقيد الحسابي لها باستخدام تدوين O الكبير.

لماذا كل شيء باللغة الإنجليزية؟

لأنه في هذا الشكل قاتل المشاركون في المؤتمر معهم ولأن اللغة الإنجليزية كانت اللغة الرسمية في هيدرا. بدت المهام كما يلي:

خذ ورقة وقلم رصاص ، وفكر ، لا تتسرع في فتح المفسدين على الفور 🙂

تحليل الحل (فيديو)

ابتداءً من الساعة 5:53 ، 4 دقائق فقط:

وإليك الطريقة التي طرح بها الأشخاص ذوو اللوحة الورقية الحل:

تحليل الحل (نص)

يكمن الحل التالي على السطح: جمع أوزان جميع النسخ المتماثلة ، وإنشاء رقم عشوائي من 0 إلى مجموع جميع الأوزان ، ثم اختيار نسخة متماثلة i بحيث يكون مجموع أوزان النسخ المتماثلة من 0 إلى (i-1) أقل من رقم عشوائي ، ومجموع أوزان النسخ المتماثلة من 0 إلى i - أكثر منه. لذلك سيكون من الممكن تحديد نسخة متماثلة واحدة ، ولتحديد النسخة التالية ، تحتاج إلى تكرار الإجراء بأكمله دون التفكير في النسخة المتماثلة المحددة. باستخدام مثل هذه الخوارزمية ، يكون تعقيد اختيار نسخة متماثلة واحدة هو O (N) ، وتعقيد اختيار النسخ المتماثلة K هو O (N K) ~ O (N2).

التعقيد التربيعي سيء ، لكن يمكن تحسينه. للقيام بذلك ، سوف نبني شجرة المقطع لمجموع الأوزان. سيتم الحصول على شجرة بعمق lg N ، في أوراقها سيكون هناك أوزان متماثلة ، وفي العقد المتبقية - مبالغ جزئية ، تصل إلى مجموع جميع الأوزان في جذر الشجرة. بعد ذلك ، نقوم بإنشاء رقم عشوائي من 0 إلى مجموع جميع الأوزان ، والعثور على النسخة المتماثلة i ، وإزالتها من الشجرة ، وكرر الإجراء للعثور على النسخ المتماثلة المتبقية. باستخدام هذه الخوارزمية ، يكون تعقيد بناء شجرة هو O (N) ، وتعقيد العثور على النسخة المتماثلة i وإزالتها من الشجرة هو O (lg N) ، وتعقيد اختيار النسخ المتماثلة K هو O (N + K lg N) ~ O (N lg N).

التعقيد الخطي أجمل من التعقيد التربيعي ، خاصة بالنسبة لـ K.

إنها هذه الخوارزمية نفذت في التعليمات البرمجية مكتبات ClusterClient من المشروع "شرق". (هناك ، تم بناء الشجرة في O (N lg N) ، لكن هذا لا يؤثر على التعقيد النهائي للخوارزمية.)

المهمة 2. حمار وحشي

كان من الضروري اقتراح خوارزمية للفرز الفعال للمستندات في الذاكرة عن طريق حقل تعسفي غير مفهرس:

تم تكليف فريقك بتطوير قاعدة بيانات مستندات مجزأة في الذاكرة. قد يكون عبء العمل الشائع هو تحديد أفضل مستندات N مرتبة حسب حقل رقمي عشوائي (غير مفهرس) من مجموعة بحجم M (عادةً N <100 << M). سيكون عبء العمل الأقل شيوعًا هو تحديد أعلى N بعد تخطي أعلى مستندات S (S ~ N).

اقترح خوارزمية لتنفيذ مثل هذه الاستفسارات بكفاءة. تقدير التعقيد الحسابي لها باستخدام تدوين O الكبير في الحالة المتوسطة وسيناريوهات الحالة الأسوأ.

تحليل الحل (فيديو)

ابتداءً من الساعة 34:50 ، 6 دقائق فقط:

تحليل الحل (نص)

حل Surface: قم بفرز جميع المستندات (على سبيل المثال مع ملفات تصنيف سريع) ، ثم خذ مستندات N + S. في هذه الحالة ، يكون تعقيد الفرز في المتوسط ​​O (M lg M) ، في أسوأ الأحوال O (M2).

من الواضح أن فرز جميع مستندات M ثم أخذ جزء صغير منها أمر غير فعال. من أجل عدم فرز جميع المستندات ، فإن الخوارزمية مناسبة حدد مسرعا، والتي ستحدد N + S من المستندات المطلوبة (يمكن فرزها بواسطة أي خوارزمية). في هذه الحالة ، سينخفض ​​التعقيد إلى O (M) في المتوسط ​​، بينما ستبقى الحالة الأسوأ كما هي.

ومع ذلك ، يمكنك القيام بذلك بشكل أكثر كفاءة - استخدم الخوارزمية كومة ثنائية تتدفق. في هذه الحالة ، تتم إضافة مستندات N + S الأولى إلى min- أو max-heap (اعتمادًا على اتجاه الفرز) ، ثم تتم مقارنة كل مستند تالٍ بجذر الشجرة ، الذي يحتوي على الحد الأدنى أو الحد الأقصى الحالي للمستند ، ويضاف إلى الشجرة إذا لزم الأمر. في هذه الحالة ، يكون التعقيد في أسوأ الحالات ، عندما تضطر إلى إعادة بناء الشجرة باستمرار ، هو O (M lg M) ، والتعقيد في المتوسط ​​هو O (M) ، كما هو الحال مع التحديد السريع.

ومع ذلك ، تبين أن دفق الكومة أكثر كفاءة نظرًا لحقيقة أنه من الناحية العملية يمكن تجاهل معظم المستندات دون إعادة بناء الكومة بعد مقارنة واحدة مع عنصر الجذر الخاص بها. يتم تنفيذ هذا الفرز في قاعدة بيانات مستندات Zebra في الذاكرة التي تم تطويرها واستخدامها في Kontur.

المهمة 3. مقايضات الدولة

كان من الضروري اقتراح الخوارزمية الأكثر كفاءة لتغيير الحالات:

تم تكليف فريقك بتطوير آلية تبادل حالة خيالية لمجموعة موزعة من العقد N. يجب نقل حالة العقدة i إلى العقدة (i + 1) ، ويجب نقل حالة العقدة N إلى العقدة الأولى. العملية الوحيدة المدعومة هي تبديل الحالة عندما تتبادل عقدتان حالتهما ذريًا. من المعروف أن مقايضة الدولة تستغرق مللي ثانية. كل عقدة قادرة على المشاركة في مبادلة حالة واحدة في أي لحظة.

كم من الوقت يستغرق نقل حالات جميع العقد في الكتلة؟

تحليل الحل (نص)

الحل السطحي: تبادل حالتي العنصر الأول والثاني ، ثم الأول والثالث ، ثم الأول والرابع ، وهكذا. بعد كل تبادل ، ستكون حالة عنصر واحد في الموضع المطلوب. عليك إجراء تباديل O (N) وقضاء وقت O (N M).

الوقت الخطي طويل ، لذا يمكنك تبادل حالات العناصر في أزواج: الأولى بالثانية ، والثالثة بالرابع ، وهكذا. بعد كل تبادل دولة ، سيكون كل عنصر ثان في الموضع الصحيح. عليك إجراء تباديل O (lg N) وقضاء وقت O (M lg N).

ومع ذلك ، من الممكن جعل التحول أكثر كفاءة - ليس في الخطي ، ولكن في الوقت الثابت. للقيام بذلك ، في الخطوة الأولى ، تحتاج إلى استبدال حالة العنصر الأول بالعنصر الأخير ، والثاني بالعنصر قبل الأخير ، وهكذا. ستكون حالة العنصر الأخير في الموضع الصحيح. والآن نحتاج إلى استبدال حالة العنصر الثاني بالعنصر الأخير ، والثالث مع العنصر قبل الأخير ، وهكذا. بعد هذه الجولة من التبادلات ، ستكون حالات جميع العناصر في الموضع الصحيح. سيكون هناك O (2M) ~ O (1) في المجموع.

مثل هذا الحل لن يفاجئ عالم الرياضيات الذي لا يزال يتذكر أن الدوران هو تكوين من تماثلين محوريين. بالمناسبة ، يتم تعميمه بشكل تافه للتحول ليس بواحد ، ولكن من خلال مواضع K <N. (اكتب في التعليقات كيف بالضبط.)

هل تحب الألغاز؟ هل تعرف حلول أخرى؟ شارك في التعليقات.

وإليك بعض الروابط المفيدة في النهاية:

• تعلم المزيد عن تطوير البنية التحتية في كفاف
• انظر السجلات الداخلية نشرة إعلانية مع التقارير حول الأنظمة الموزعة
• مشاهدة سلسلة محاضرات الفيديوخوارزميات غير عادية للناس العاديين»
• اشترك في موقعنا قناة في Telegram

المصدر: www.habr.com