څو ورځې وړاندې پیښه شوه د هیدرا کنفرانس. د JUG.ru ګروپ هلکانو د خوب سپیکرانو ته بلنه ورکړه (لیسلي لامپورټ! کلف کلیک! مارټین کلیپمن!) او دوه ورځې یې توزیع شوي سیسټمونو او کمپیوټر ته وقف کړل. کونتور د کنفرانس له دریو شریکانو څخه یو و. موږ په بوت کې خبرې وکړې، زموږ د توزیع شوي ذخیره کولو په اړه یې خبرې وکړې، بینګو لوبه وکړه، او حل شوي پزلونه.

دا د دوی د متن لیکوال څخه د کونټور موقف کې د دندو تحلیل سره پوسټ دی. څوک په هایډرا کې و - دا ستاسو د خوښې تجربې په یادولو کې دلیل دی، څوک نه و - ستاسو د دماغ پراخولو فرصت لوی او- یادښت.

حتی ګډون کونکي هم وو چې د خپلې پریکړې لیکلو لپاره یې فلیپ چارټ په سلایډونو کې ویجاړ کړ. زه ټوکې نه کوم - دوی د تصدیق لپاره د کاغذ دا ډډ ته وسپارل:

په مجموع کې درې دندې وې:

• د بار د توازن لپاره د وزن په واسطه د نقلونو غوره کولو په اړه
• د میموري ډیټابیس په وړاندې د پوښتنو پایلو ترتیب کولو په اړه
• په ویشل شوي سیسټم کې د دولتي لیږد په اړه د حلقوي ټوپولوژي سره

دنده 1. ClusterClient

دا اړینه وه چې د توزیع شوي سیسټم د N وزن لرونکي نقلونو څخه د K د مؤثره انتخاب لپاره د الګوریتم وړاندیز وکړو:

ستاسو ټیم دنده لري چې د N نوډونو پراخه توزیع شوي کلستر لپاره د پیرودونکي کتابتون رامینځته کړي. کتابتون به د نوډونو سره تړلي مختلف میټاډاټا تعقیب کړي (د بیلګې په توګه د دوی ځنډونه، د 4xx/5xx غبرګون نرخونه، او نور) او دوی ته د فلوټینګ پوائنټ وزن W1..WN وټاکي. د دې لپاره چې د ورته اجرا کولو ستراتیژۍ مالتړ وکړي، کتابتون باید وکوالی شي د N نوډونو K په تصادفي ډول غوره کړي — د انتخاب کیدو چانس باید د نوډ وزن سره متناسب وي.

د نوډونو غوره کولو لپاره د الګوریتم وړاندیز وکړئ. د لوی O نوټیشن په کارولو سره د دې کمپیوټري پیچلتیا اټکل کړئ.

ولې هر څه په انګلیسي کې دي؟

ځکه په دې بڼه د کنفرانس ګډونوال له دوی سره جنګېدل او دا ځکه چې انګلیسي د هایدرا رسمي ژبه وه. دندې داسې ښکاري:

کاغذ او پنسل واخلئ، فکر وکړئ، سمدستي د سپیلرونو خلاصولو ته بیړه مه کوئ 🙂

د حل تحلیل (ویډیو)

په 5:53 پیل کیږي، یوازې 4 دقیقې:

او دلته دا دی چې څنګه د فلیپ چارټ سره هلکانو خپله حل لاره غوره کړه:

د حل تحلیل (متن)

لاندې حل په سطح کې پروت دی: د ټولو نقلونو وزنونه راټول کړئ، د 0 څخه د ټولو وزنونو مجموعې ته یو تصادفي شمیره رامینځته کړئ، بیا یو i-replica غوره کړئ چې د نقل وزنونو مجموعه له 0 څخه (i-1)th پورې وي. د تصادفي شمیر څخه کم دی، او د نقل وزن له 0 څخه تر i-th پورې - له هغې څخه ډیر دی. نو دا به ممکنه وي چې یو نقل وټاکئ، او د بل غوره کولو لپاره، تاسو اړتیا لرئ چې د انتخاب شوي نقل په پام کې نیولو پرته ټوله پروسه تکرار کړئ. د داسې الګوریتم سره، د یو نقل غوره کولو پیچلتیا O(N) ده، د K نقلونو غوره کولو پیچلتیا O(N K) ~ O(N2) ده.

د کواډراټیک پیچلتیا خرابه ده، مګر دا ښه کیدی شي. د دې کولو لپاره، موږ به جوړ کړو قطعه ونه د وزنونو لپاره. د lg N ژوره ونې به ترلاسه شي، په پاڼو کې به د نقل وزنونه وي، او په پاتې نوډونو کې - د ونې په ریښه کې د ټولو وزنونو مجموعې پورې، جزوي مقدارونه. بیا، موږ یو تصادفي شمیره له 0 څخه د ټولو وزنونو مجموعې ته تولیدوو، i-th نقل پیدا کړو، له ونې څخه یې لرې کړو، او د پاتې نقلونو موندلو لپاره کړنلاره تکرار کړو. د دې الګوریتم سره، د ونې د جوړولو پیچلتیا O(N) ده، د i-th نقل موندلو او له ونې څخه د لرې کولو پیچلتیا O(lg N) ده، د K نقلونو غوره کولو پیچلتیا O(N + K) ده. lg N) ~ O(N lg N) .

د خطي لاګ پیچلتیا د څلور اړخیز پیچلتیا په پرتله ښه ده، په ځانګړې توګه د لوی K لپاره.

دا الګوریتم دی په کوډ کې پلي کیږي د پروژې څخه د کلستر کلینټ کتابتونونه "ختیځ". (هلته، ونه په O(N lg N) کې جوړه شوې، مګر دا د الګوریتم وروستی پیچلتیا اغیزه نه کوي.)

دنده 2. زیبرا

دا اړینه وه چې په حافظه کې د اسنادو د مؤثره ترتیب کولو لپاره د الګوریتم وړاندیز وکړو چې د خپل سري غیر شاخص شوي ساحې لخوا:

ستاسو ټیم ته دنده سپارل شوې چې د حافظې دننه د اسنادو ډیټابیس رامینځته کړي. یو عام کاري بار به د لوړ N سندونو غوره کول وي چې د اندازې M (معمولا N <100 << M) ټولګه څخه د خپل سري (غیر شاخص شوي) شمیرې ساحې لخوا ترتیب شوي وي. یو څه لږ عام کاري بار به د پورتنۍ S سندونو (S ~ N) له پریښودو وروسته د پورتنۍ N غوره کول وي.

یو الګوریتم وړاندیز کړئ چې دا ډول پوښتنې په اغیزمنه توګه ترسره کړي. په اوسط قضیه کې د لوی O نوټیشن په کارولو سره د دې کمپیوټري پیچلتیا اټکل وکړئ او ترټولو بد حالت سناریو.

د حل تحلیل (ویډیو)

په 34:50 پیل کیږي، یوازې 6 دقیقې:

د حل تحلیل (متن)

د سطحې حل: ټول اسناد ترتیب کړئ (د مثال په توګه څوکه)، بیا د N+S اسناد واخلئ. په دې حالت کې، د ترتیب کولو پیچلتیا په اوسط ډول O (M lg M)، په بدترین O (M2) کې ده.

دا څرګنده ده چې د ټولو M اسنادو ترتیب کول او بیا د دوی یوازې لږه برخه اخیستل غیر موثر دي. د دې لپاره چې ټول اسناد ترتیب نه کړئ، یو الګوریتم مناسب دی چټک انتخاب، کوم چې به د غوښتل شوي اسنادو N + S غوره کړي (دوی د هر ډول الګوریتم لخوا ترتیب کیدی شي). په دې حالت کې، پیچلتیا به په اوسط ډول O (M) ته راټیټ شي، پداسې حال کې چې بدترین حالت به ورته پاتې وي.

په هرصورت، تاسو کولی شئ دا حتی په اغیزمنه توګه ترسره کړئ - د الګوریتم څخه کار واخلئ د بائنری هیپ جریان. په دې حالت کې، لومړی N+S سندونه په min- یا max-heap کې اضافه کیږي (د ترتیب په لور پورې اړه لري)، او بیا هر راتلونکی سند د ونې له ریښې سره پرتله کیږي، کوم چې اوسنی لږترلږه یا اعظمي سند لري، او د اړتیا په صورت کې ونې ته اضافه کیږي. په دې حالت کې، پیچلتیا په بدترین حالت کې، کله چې تاسو په دوامداره توګه د ونې بیارغونه کوئ، O(M lg M) دی، پیچلتیا په اوسط ډول O (M) ده، لکه څنګه چې د چټک انتخاب سره.

په هرصورت، د هپ سټریمینګ د دې حقیقت له امله ډیر اغیزمن وګرځید چې په عمل کې ډیری اسناد د هغې د اصلي عنصر سره د یو واحد پرتله کولو وروسته د هپ بیا جوړولو پرته رد کیدی شي. دا ډول ترتیب د زیبرا په حافظه کې د اسنادو ډیټابیس کې پلي کیږي چې په کنټور کې رامینځته شوی او کارول کیږي.

دنده 3. د دولت تبادله

دا اړینه وه چې د حالتونو بدلولو لپاره ترټولو اغیزمن الګوریتم وړاندیز وکړو:

ستاسو ټیم ته دنده سپارل شوې چې د N نوډونو توزیع شوي کلستر لپاره د غوره دولتي تبادلې میکانیزم رامینځته کړي. د i-th نوډ حالت باید (i+1) -th نوډ ته ولیږدول شي، د N-th نوډ حالت باید لومړي نوډ ته ولیږدول شي. یوازینی ملاتړ شوی عملیات د دولت تبادله ده کله چې دوه نوډونه خپل ایالتونه په اټومي ډول تبادله کوي. دا معلومه ده چې د دولت تبادله M ملی ثانیه نیسي. هر نوډ کولی شي په هر وخت کې د یو واحد دولت تبادله کې برخه واخلي.

په کلستر کې د ټولو نوډونو ایالتونو لیږد څومره وخت نیسي؟

د حل تحلیل (متن)

د سطحې حل: د لومړي او دویم عنصر حالتونه تبادله کړئ، بیا لومړی او دریم، بیا لومړی او څلورم، او داسې نور. د هر تبادلې وروسته، د یو عنصر حالت به په مطلوب موقعیت کې وي. تاسو باید د O (N) اجازه ورکړئ او د O (N M) وخت مصرف کړئ.

خطي وخت اوږد دی، نو تاسو کولی شئ د عناصرو حالتونه په جوړه کې تبادله کړئ: لومړی د دویم سره، دریم د څلورم سره، او داسې نور. د هر دولت تبادلې وروسته، هر دویم عنصر به په سم حالت کې وي. تاسو باید د O(lg N) اجازه ورکړئ او O(M lg N) وخت مصرف کړئ.

په هرصورت، دا ممکنه ده چې بدلون نور هم اغیزمن کړي - نه په خطي کې، مګر په دوامداره وخت کې. د دې کولو لپاره ، په لومړي ګام کې ، تاسو اړتیا لرئ د لومړي عنصر حالت له وروستي سره تبادله کړئ ، دوهم د پای پای سره ، او داسې نور. د وروستي عنصر حالت به په سم حالت کې وي. او اوس موږ اړتیا لرو چې د دوهم عنصر حالت له وروستي سره تبادله کړو، دریم له پایه لرونکي سره، او داسې نور. د تبادلې له دې پړاو وروسته، د ټولو عناصرو دولتونه به په سم حالت کې وي. په مجموع کې به O(2M) ~ O(1) تخفیفونه وي.

دا ډول حل به یو ریاضي پوه ته حیران نه کړي چې لاهم په یاد لري چې گردش د دوه محوري سمیټریونو ترکیب دی. د لارې په توګه، دا د بدلون لپاره په معمولی توګه عمومي شوی نه د یو لخوا، مګر د K <N پوستونو لخوا. (په نظرونو کې ولیکئ چې دقیقا څنګه.)

ایا تاسو معما خوښوی؟ ایا تاسو نور حلونه پیژنئ؟ په نظرونو کې شریک کړئ.

او دلته په پای کې ځینې ګټور لینکونه دي:

• په اړه نور معلومات زده کړئ د زیربنا پراختیا په شکل کې
• داخلي ریکارډونه وګورئ د راپورونو سره الوتونکی د ویشل شوي سیسټمونو په اړه
• د ویډیو لیکچرونو لړۍ وګورئد عادي خلکو لپاره غیر معمولي الګوریتمونه»
• زموږ سره ګډون وکړئ په ټیلیګرام کې چینل

سرچینه: www.habr.com