شروډینګر بلی پرته له بکس څخه: په ویشل شوي سیسټمونو کې د توافق ستونزه

نو، راځئ چې تصور وکړو. په کوټه کې 5 پیشوګانې بندې دي او د دې لپاره چې مالک له خوبه راویښ شي، دوی ټول باید په دې اړه په خپل منځ کې توافق وکړي، ځکه چې دوی یوازې کولی شي دروازه پرانیزي چې پنځه یې په هغې باندې تکیه کوي. که یو پیشو د شروډینګر پیشو وي، او نورې پیشوګانې د هغه د پریکړې په اړه نه پوهیږي، پوښتنه راپورته کیږي: "دوی څنګه کولی شي؟"

په دې مقاله کې، زه به تاسو ته په ساده اصطلاحاتو کې د ویشل شوي سیسټمونو نړۍ نظریاتي برخې او د دوی د عملیاتو اصولو په اړه ووایم. زه به په سطحي ډول د پاکسوس اصلي نظر هم وڅیړم.

کله چې پراختیا کونکي د کلاوډ زیربناوې کاروي، مختلف ډیټابیسونه، او د ډیری نوډونو په کلسترونو کې کار کوي، دوی ډاډه دي چې ډاټا به بشپړ، خوندي، او تل شتون ولري. مګر تضمین چیرته دي؟

په لازمي ډول ، هغه تضمینونه چې موږ یې لرو د عرضه کونکي تضمینونه دي. دوی په اسنادو کې په لاندې ډول تشریح شوي: "دا خدمت خورا معتبر دی، دا یو ورکړل شوی SLA لري، اندیښنه مه کوئ، هرڅه به په ویشلو سره کار وکړي لکه څنګه چې تاسو تمه لرئ."

موږ په غوره کې باور لرو، ځکه چې د لوی شرکتونو سمارټ هلکانو موږ ته ډاډ راکړ چې هرڅه به سم وي. موږ دا پوښتنه نه کوو: ولې، په حقیقت کې، دا کار کولی شي؟ ایا د داسې سیسټمونو د سم فعالیت لپاره کوم رسمي توجیه شتون لري؟

زه پدې وروستیو کې لاړم د توزیع شوي کمپیوټر ښوونځي او د دې موضوع څخه ډیر الهام شوی و. په ښوونځي کې لیکچرونه د کمپیوټر سیسټمونو په پرتله د محاسبې ټولګیو په څیر وو. مګر دا په حقیقت کې څنګه خورا مهم الګوریتمونه چې موږ یې هره ورځ کاروو، پرته له دې چې پوه شو، په یو وخت کې ثابت شوي.

ډیری عصري توزیع شوي سیسټمونه د Paxos اتفاق الګوریتم او د هغې مختلف تعدیلات کاروي. ترټولو ښه خبره دا ده چې اعتبار او په اصولو کې، د دې الګوریتم د شتون احتمال په ساده ډول د قلم او کاغذ سره ثابت کیدی شي. په عمل کې، الګوریتم په لویو سیسټمونو کې کارول کیږي چې په بادلونو کې په ډیری ډیری نوډونو کې روان دي.

یو روښانه بیلګه چې وروسته به بحث وشي: د دوو جنرالانو دندهراځئ چې د تودوخې لپاره یو نظر وګورو د دوو جنرالانو دنده.

موږ دوه لښکرونه لرو - سور او سپین. په محاصره شوي ښار کې سپین سرتیري میشت دي. د A1 او A2 جنرالانو په مشرۍ سور سرتیري د ښار په دواړو خواوو کې موقعیت لري. د ریډ هیډز دنده په سپین ښار برید کول او ګټل دي. په هرصورت، د هر سور جنرال پوځ په انفرادي توګه د سپینو اردو څخه کوچنی دی.

د سور لپاره د بریا شرایط: دواړه جنرالان باید په عین وخت کې برید وکړي ترڅو په سپینو باندې د شمیرې ګټې ولري. د دې کولو لپاره، جنرالان A1 او A2 باید د یو بل سره موافقې ته راشي. که هرڅوک په جلا توګه برید وکړي، سور سرونه به له لاسه ورکړي.

یوې موافقې ته د رسیدو لپاره، جنرالان A1 او A2 کولی شي د سپینې ښار د خاورې له لارې یو بل ته پیغامونه واستوي. رسول ممکن په بریالیتوب سره یو متحد جنرال ته ورسیږي یا ممکن د دښمن لخوا ودرول شي. پوښتنه: ایا د سور ویښتانو جنرالانو ترمنځ د اړیکو داسې لړۍ شتون لري (د A1 څخه A2 ته د پیغام رسولو لړۍ او برعکس A2 څخه A1 ته)، په کوم کې چې دوی په X ساعت کې د برید په اړه موافقه کوي. دلته، د تضمین معنی دا ده چې دواړه جنرالان به مبهم تصدیق ولري چې یو متحد (بل جنرال) به په ټاکل شوي وخت X باندې یقینا برید وکړي.

فرض کړئ چې A1 د پیغام سره A2 ته یو میسنجر لیږي: "راځئ چې نن په نیمه شپه برید وکړو!" جنرال A1 نشي کولی د جنرال A2 له تایید پرته برید وکړي. که د A1 څخه میسنجر راغلی وي، نو جنرال A2 د پیغام سره تایید لیږي: "هو، نن ورځ سپین وژني." خو اوس جنرال A2 نه پوهیږي چې ایا د هغه میسنجر راغلی او که نه، هغه هیڅ تضمین نلري چې برید به په ورته وخت کې وي. اوس جنرال A2 بیا تایید ته اړتیا لري.

که موږ د دوی ارتباطات نور هم تشریح کړو، دا روښانه کیږي چې د پیغامونو د تبادلې څو دورې شتون نلري، د دې تضمین کولو لپاره هیڅ لاره نشته چې دواړه جنرالان خپل پیغامونه ترلاسه کړي (فرض کوي چې یا یې رسول مداخله کولی شي).

د دوه جنرالانو ستونزه د یو خورا ساده توزیع شوي سیسټم یوه ښه بیلګه ده چیرې چې دوه نوډونه شتون لري چې د باور وړ نه وي. دا پدې مانا ده چې موږ 100٪ تضمین نلرو چې دوی همغږي شوي. ورته ستونزې یوازې په لویه کچه وروسته په مقاله کې بحث کیږي.

موږ د توزیع شوي سیسټمونو مفهوم معرفي کوو

ویشل شوی سیسټم د کمپیوټرونو یوه ډله ده (له دې وروسته به دوی ته نوډونه وایو) چې کولی شي پیغامونه تبادله کړي. هر انفرادي نوډ یو ډول خپلواکه اداره ده. نوډ کولی شي کارونه پخپله پروسس کړي، مګر د نورو نوډونو سره د اړیکو لپاره، دا اړتیا لري چې پیغامونه واستوي او ترلاسه کړي.

په سمه توګه پیغامونه څنګه پلي کیږي، کوم پروتوکولونه کارول کیږي - دا پدې شرایطو کې زموږ لپاره د علاقې وړ ندي. دا مهمه ده چې د ویشل شوي سیسټم نوډونه د پیغامونو په لیږلو سره یو بل سره ډیټا تبادله کولی شي.

تعریف پخپله ډیر پیچلی نه ښکاري، مګر موږ باید په پام کې ونیسو چې یو ویشل شوی سیسټم یو شمیر ځانګړتیاوې لري چې زموږ لپاره به مهم وي.

د ویشل شوي سیسټمونو ځانګړتیاوې

1. همغږۍ - په سیسټم کې د یوځل یا هم مهاله پیښو احتمال. سربیره پردې، موږ به هغه پیښې په پام کې ونیسو چې په دوه مختلف نوډونو کې واقع کیږي تر هغه چې موږ د دې پیښو د پیښې روښانه ترتیب نلرو. مګر، د یوې قاعدې په توګه، موږ دا نه لرو.
2. نړیوال ساعت نشته. موږ د نړیوال ساعت د نشتوالي له امله د پیښو روښانه ترتیب نلرو. د خلکو په عادي نړۍ کې، موږ د دې حقیقت سره عادت یو چې موږ ساعتونه او وخت په بشپړه توګه لرو. هرڅه بدلیږي کله چې د توزیع شوي سیسټمونو خبره راځي. حتی خورا دقیق اټومي ساعتونه تیریږي، او ممکن داسې شرایط شتون ولري چې موږ نشو ویلای چې د دوو پیښو څخه کوم لومړی پیښ شوي. له همدې امله، موږ نشو کولی په وخت تکیه وکړو.
3. د سیسټم نوډونو خپلواکه ناکامي. بله ستونزه شتون لري: یو څه غلط کیدی شي په ساده ډول ځکه چې زموږ نوډونه د تل لپاره دوام نلري. هارډ ډرایو ممکن ناکام شي ، په بادل کې مجازی ماشین ممکن ریبوټ شي ، شبکه ممکن ړنګه شي او پیغامونه به ورک شي. سربیره پردې، داسې شرایط شتون لري چې نوډونه کار کوي، مګر په ورته وخت کې د سیسټم په وړاندې کار کوي. د ستونزو وروستۍ ټولګي حتی یو جلا نوم ترلاسه کړ: ستونزه بازنطینی جنرالان. د دې ستونزې سره د توزیع شوي سیسټم ترټولو مشهور مثال بلاکچین دی. مګر نن به موږ د دې ځانګړې طبقې ستونزې په پام کې ونیسو. موږ به په داسې شرایطو کې لیوالتیا ولرو چې په ساده ډول یو یا څو نوډونه ناکام شي.
4. د نوډونو تر مینځ د مخابراتو ماډلونه (د پیغام رسولو ماډلونه).. موږ لا دمخه تاسیس کړی چې نوډونه د پیغامونو په تبادله سره اړیکه نیسي. د پیغام رسولو دوه مشهور ماډلونه شتون لري: همغږي او غیر متناسب.

په ویشل شوي سیسټمونو کې د نوډونو ترمنځ د اړیکو ماډلونه

همغږي موډل - موږ په ډاډه توګه پوهیږو چې د وخت یو محدود پیژندل شوی ډیلټا شتون لري چې په جریان کې یو پیغام له یو نوډ څخه بل ته د رسیدو تضمین کیږي. که دا وخت تیر شوی وي او پیغام ندی رسیدلی، موږ کولی شو په خوندي توګه ووایو چې نوډ ناکام شوی. پدې ماډل کې موږ د وړاندوینې وړ انتظار وختونه لرو.

اسینکرونوس ماډل - په غیر متناسب موډلونو کې موږ فکر کوو چې د انتظار وخت محدود دی، مګر د وخت داسې ډیلټا شتون نلري چې وروسته یې موږ تضمین کړو چې نوډ ناکام شوی. هغوی. د نوډ څخه د پیغام لپاره د انتظار وخت په خپله خوښه اوږد کیدی شي. دا یو مهم تعریف دی، او موږ به یې په اړه نور خبرې وکړو.

په ویشل شوي سیسټمونو کې د توافق مفهوم

مخکې له دې چې د اجماع مفهوم په رسمي توګه تعریف کړو، راځئ چې د یو حالت مثال په پام کې ونیسو چیرې چې موږ ورته اړتیا لرو، یعنې: د دولتي ماشین نقل.

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

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

په رسمی توګه، موږ کولی شو د توافق الګوریتم (یا په ساده ډول د توافق الګوریتم) د یو مشخص فعالیت په توګه تعریف کړو چې یو ویشل شوی سیسټم له A حالت څخه B ته لیږدوي. سربیره پردې، دا حالت د ټولو نوډونو لخوا منل کیږي، او ټول نوډونه کولی شي تصدیق کړي. لکه څنګه چې دا معلومه شوه، دا دنده دومره کوچنۍ نه ده لکه څنګه چې په لومړي نظر کې ښکاري.

د توافق الګوریتم ملکیتونه

د توافق الګوریتم باید د سیسټم شتون ته دوام ورکولو لپاره درې ملکیتونه ولري او له یو دولت څخه بل ته په حرکت کې یو څه پرمختګ ولري:

1. تړون - ټول په سمه توګه عملیاتي نوډونه باید ورته ارزښت ولري (په مقالو کې دا ملکیت د خوندیتوب ملکیت هم ویل کیږي). ټول نوډونه چې اوس مهال فعالیت کوي (د نورو سره اړیکه ناکامه شوې یا له لاسه ورکړې) باید یوې موافقې ته راشي او یو څه وروستی عام ارزښت ومني.

   دلته پوهیدل مهم دي چې په ویشل شوي سیسټم کې نوډونه چې موږ یې په پام کې نیسو موافقه کول غواړي. دا دی، موږ اوس د سیسټمونو په اړه خبرې کوو په کوم کې چې یو څه په ساده ډول ناکام کیدی شي (د بیلګې په توګه، ځینې نوډ ناکامیږي)، مګر پدې سیسټم کې یقینا هیڅ نوډونه شتون نلري چې په قصدي توګه د نورو په وړاندې کار کوي (د بازنطین جنرالانو دنده). د دې ملکیت له امله، سیسټم ثابت پاتې کیږي.

2. بشپړتیا - که ټول په سمه توګه کار کوي نوډونه ورته ارزښت وړاندې کوي v، پدې معنی چې هر سم عملیاتي نوډ باید دا ارزښت ومني v.
3. ختمول - ټول په سمه توګه عملیاتي نوډونه به بالاخره یو ټاکلی ارزښت (د ژوند ملکیت) واخلي، کوم چې الګوریتم ته اجازه ورکوي چې په سیسټم کې پرمختګ وکړي. هر فرد په سمه توګه عملیاتي نوډ باید ژر یا وروسته وروستی ارزښت ومني او دا تایید کړي: "زما لپاره، دا ارزښت ریښتیا دی، زه د ټول سیسټم سره موافق یم."

د اجماع الګوریتم څنګه کار کوي یوه بیلګه

پداسې حال کې چې د الګوریتم ملکیتونه ممکن په بشپړ ډول روښانه نه وي. له همدې امله، موږ به د یو مثال سره روښانه کړو چې کوم مرحلې د ساده موافقې الګوریتم په سیسټم کې د همغږي پیغام رسولو ماډل سره تیریږي، په کوم کې چې ټول نوډونه د توقع سره سم فعالیت کوي، پیغامونه له لاسه نه ورکوي او هیڅ شی نه ماتیږي (ایا دا واقعا واقع کیږي؟).

1. دا ټول د واده وړاندیز (پروپوز) سره پیل کیږي. راځئ چې فرض کړو چې یو پیرودونکي د "نوډ 1" په نوم نوډ سره وصل شوی او معامله یې پیل کړې، نوډ - O ته نوی ارزښت لیږدوي. له اوس څخه به موږ "نوډ 1" ته ووایو. وړاندیز کول. د وړاندیز کونکي په توګه، "نوډ 1" باید اوس ټول سیسټم ته خبر ورکړي چې دا تازه معلومات لري، او دا نورو ټولو نوډونو ته پیغامونه لیږي: "وګورئ! د "O" معنی ماته راغله او زه غواړم دا ولیکم! مهرباني وکړئ تایید کړئ چې تاسو به په خپل لاګ کې "O" هم ثبت کړئ.

   

2. بله مرحله د وړاندیز شوي ارزښت لپاره رایه ورکول دي (رایه ورکول). دا د څه لپاره دی؟ دا ممکن وي چې نور نوډونه نور وروستي معلومات ترلاسه کړي، او دوی د ورته لیږد په اړه معلومات لري.

   
   
   کله چې نوډ "نوډ 1" خپل وړاندیز لیږي، نور نوډونه د دې پیښې د معلوماتو لپاره خپل لاګونه ګوري. که چیرې کوم تناقض شتون ونلري، نوډونه اعلان کوي: "هو، زه د دې پیښې لپاره نور معلومات نلرم. د "O" ارزښت وروستي معلومات دي چې موږ یې مستحق یو.

   په بل هر حالت کې، نوډونه کولی شي "نوډ 1" ته ځواب ووايي: "واورئ! زه د دې لیږد په اړه نور وروستي معلومات لرم. نه 'O'، مګر یو څه ښه."

   د رایې ورکولو په مرحله کې، نوډونه یوې پریکړې ته راځي: یا دوی ټول ورته ارزښت مني، یا یو یې په مقابل کې رایه ورکوي، دا په ګوته کوي چې هغه وروستي معلومات لري.

3. که چیرې د رایې ورکولو پړاو بریالی و او هرڅوک یې په ګټه وي، نو سیسټم نوي پړاو ته ځي - د ارزښت منل. "نوډ 1" د نورو نوډونو او راپورونو څخه ټول ځوابونه راټولوي: "هرڅوک د "O" ارزښت باندې موافقه وکړه! اوس زه په رسمي توګه اعلان کوم چې "O" زموږ نوې معنی ده، د هرچا لپاره ورته! په خپل کوچني کتاب کې یې ولیکئ، مه هېروئ. په خپل لوښي کې یې ولیکئ!

   

4. پاتې نوډونه تایید لیږي (منل شوي) چې دوی د "O" ارزښت لیکلی دی؛ پدې وخت کې هیڅ نوی ندی راغلی (یو ډول دوه مرحلې ژمنې). د دې مهمې پیښې وروسته، موږ فکر کوو چې ویشل شوي لیږد بشپړ شوی.
   

په دې توګه، په یوه ساده قضیه کې د توافق الګوریتم څلور مرحلې لري: وړاندیز کول، رایه ورکول (رایه ورکول)، منل (منل)، د منلو تایید (منل).

که په یو ګام کې موږ موافقې ته ورسیږو، نو الګوریتم بیا پیل کیږي، د نوډونو لخوا چمتو شوي معلومات په پام کې نیولو سره چې د وړاندیز شوي ارزښت تایید کولو څخه یې ډډه کړې.

په یو غیر متزلزل سیسټم کې د توافق الګوریتم

مخکې له دې، هرڅه سم وو، ځکه چې موږ د یو همغږي پیغام رسولو ماډل په اړه خبرې کولې. مګر موږ پوهیږو چې په عصري نړۍ کې موږ هر څه په غیر متناسب ډول ترسره کولو عادت شوي یو. ورته الګوریتم څنګه په سیسټم کې د غیر متناسب پیغام رسولو ماډل سره کار کوي ، چیرې چې موږ باور لرو چې د نوډ څخه د ځواب لپاره د انتظار وخت په خپل سر اوږد کیدی شي (په لاره کې ، د نوډ ناکامي هم د مثال په توګه په پام کې نیول کیدی شي کله چې نوډ کولی شي په خپل سري ډول د اوږدې مودې لپاره ځواب ووايي).

اوس چې موږ پوهیږو چې د توافق الګوریتم څنګه په اصولو کې کار کوي، د هغو پلټونکو لوستونکو لپاره یوه پوښتنه چې دا یې تر دې دمه کړې ده: د غیر متناسب پیغام ماډل سره د N نوډونو سیسټم کې څومره نوډونه ناکام کیدی شي ترڅو سیسټم لاهم توافق ته ورسیږي؟

سم ځواب او توجیه د سپیلر تر شا دي.سم ځواب: 0. که حتی په غیر متمرکز سیسټم کې یو نوډ ناکام شي، سیسټم به ونشي کولی توافق ته ورسیږي. دا بیان د FLP تیورم کې ثابت شوی، په ځینو حلقو کې ښه پیژندل شوی (1985، فیشر، لینچ، پیټرسن، د مقالې په پای کې اصلي سره اړیکه لري): "د ویشل شوي اجماع ترلاسه کول ناممکن که لږترلږه یو نوډ ناکام شي. "

هلکانو، بیا موږ ستونزه لرو، موږ د هر څه غیر متناسب کیدو سره عادت یو. او دلته دا دی. څنګه ژوند ته دوام ورکړو؟

موږ یوازې د تیوري په اړه خبرې کولې، د ریاضیاتو په اړه. "اجماع نشي ترلاسه کولی" څه معنی لري، د ریاضي ژبې څخه زموږ - انجینري ته ژباړل؟ دا پدې مانا ده چې "تل نشي ترلاسه کیدی"، د بیلګې په توګه. داسې یوه قضیه ده چې اجماع د لاسته راوړلو وړ نه ده. دا څه ډول قضیه ده؟

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

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

په عمل کې، موږ د یو څه همغږي ارتباطي موډلونو سره معامله کوو. جزوي همغږي په لاندې ډول پیژندل کیږي: په عمومي حالت کې، موږ یو غیر متزلزل ماډل لرو، مګر د "نړیوال ثبات وخت" یو مشخص مفهوم د یو ټاکلي وخت په رسمي توګه معرفي کیږي.

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

د Paxos الګوریتم د موافقې ستونزې حل کوي

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

مګر ثبوت له کوچني څخه لرې وګرځید. لومړۍ خپرونه یوازې په 1998 کې خپره شوه (33 مخونه) چې د الګوریتم تشریح کوي. لکه څنګه چې دا معلومه شوه، دا خورا ستونزمنه وه چې پوه شي، او په 2001 کې د مقالې تشریح خپور شو، چې 14 پاڼې یې اخیستې. د خپرونو حجم د دې لپاره ورکړل شوی چې وښیې چې په حقیقت کې د اجماع ستونزه هیڅ ساده نه ده، او د دې ډول الګوریتمونو تر شا د هوښیار خلکو لخوا خورا لوی کار دی.

دا په زړه پورې ده چې لیسلي لامپورټ پخپله په خپل لیک کې یادونه وکړه چې په دویمه توضیحي مقاله کې یو بیان دی، یوه کرښه (هغه مشخص نه کړه کوم یو)، کوم چې په مختلفو لارو تفسیر کیدی شي. او د دې له امله، د عصري Paxos پلي کولو لوی شمیر په بشپړ ډول سم کار نه کوي.

د Paxos د کار مفصل تحلیل به له یو څخه ډیر مقالې واخلي، نو زه به هڅه وکړم چې د الګوریتم اصلي نظر په لنډ ډول بیان کړم. زما د مقالې په پای کې لینکونو کې تاسو به پدې موضوع کې د نور ډوبولو لپاره مواد ومومئ.

په Paxos کې رولونه

د Paxos الګوریتم د رولونو مفهوم لري. راځئ چې درې اصلي په پام کې ونیسو (د اضافي رولونو سره بدلونونه شتون لري):

1. وړاندیز کونکي (اصطلاحات هم کارول کیدی شي: مشران یا همغږي کوونکي). دا هغه هلکان دي چې د کارونکي څخه د یو څه نوي ارزښت په اړه زده کوي او د مشر رول په غاړه اخلي. د دوی دنده دا ده چې د نوي ارزښت لپاره د وړاندیزونو لړۍ پیل کړي او د نوډونو نور فعالیتونه همغږي کړي. سربیره پردې، Paxos په ځینو شرایطو کې د ډیری مشرانو شتون ته اجازه ورکوي.
2. رایه ورکوونکي (رایه ورکوونکي). دا نوډونه دي چې د یو ځانګړي ارزښت منلو یا ردولو لپاره رایه ورکوي. د دوی رول خورا مهم دی، ځکه چې پریکړه په دوی پورې اړه لري: د توافق الګوریتم راتلونکي مرحلې وروسته سیسټم به (یا به نه) کوم حالت ته ځي.
3. زده کونکي. نوډونه چې په ساده ډول د نوي منل شوي ارزښت منل او لیکي کله چې د سیسټم حالت بدل شوی وي. دوی پریکړې نه کوي، دوی یوازې ډاټا ترلاسه کوي او کولی شي د وروستي کارونکي ته ورکړي.

یو نوډ کولی شي په مختلفو شرایطو کې ډیری رولونه یوځای کړي.

د کورم مفهوم

موږ فرض کوو چې موږ یو سیسټم لرو N نوډونه او له دوی څخه اعظمي F نوډونه ممکن ناکام شي. که F نوډونه ناکام شي، نو موږ باید لږترلږه ولرو 2F+1 د منلو وړ نوډونه.

دا اړینه ده چې موږ تل اکثریت ولرو، حتی په بدترین حالت کې، د "ښه" نوډونو څخه چې په سمه توګه کار کوي. هغه دی F+1 "ښه" نوډونه چې موافق دي، او وروستی ارزښت به ومنل شي. که نه نو، کیدای شي داسې یو حالت وي چې زموږ مختلف محلي ډلې مختلف معنی لري او په خپل منځ کې موافق نه شي. له همدې امله موږ د رایې ګټلو لپاره مطلق اکثریت ته اړتیا لرو.

د Paxos موافقت الګوریتم څنګه کار کوي عمومي نظر

د Paxos الګوریتم دوه لوی مرحلې لري، کوم چې په پایله کې په دوو مرحلو ویشل شوي دي:

1. مرحله 1a: چمتو کول. د چمتووالي په مرحله کې، مشر (وړاندیز کوونکی) ټولو نوډونو ته خبر ورکوي: "موږ د رایې ورکولو نوی پړاو پیل کوو. موږ یو نوی پړاو لرو. د دې دورې شمیر n دی. اوس به رایه ورکول پیل کړو.» د اوس لپاره، دا په ساده ډول د نوي دورې پیل راپور ورکوي، مګر د نوي ارزښت راپور نه ورکوي. د دې مرحلې دنده دا ده چې یو نوی پړاو پیل کړي او هرڅوک د خپل ځانګړي شمیر څخه خبر کړي. ګردي شمیره مهمه ده، دا باید د ټولو پخوانیو مشرانو څخه د رایې ورکولو د ټولو پخوانیو شمیرو څخه ډیر ارزښت ولري. ځکه چې دا د ګردي شمیرې څخه مننه ده چې په سیسټم کې نور نوډونه به پوه شي چې د مشر معلومات څومره وروستي دي. احتمال شته چې نور نوډونه لا دمخه د ډیرو وروستیو پړاوونو څخه د رایې ورکولو پایلې ولري او په ساده ډول به مشر ته ووایي چې هغه د وخت تر شا دی.
2. لومړی پړاو ب: ژمنه. کله چې د منلو وړ نوډونه د رایې ورکولو د نوي پړاو شمیره ترلاسه کړي، دوه پایلې ممکن دي:
   • د نویو رایو شمیره د هرې پخوانۍ رایې له شمیر څخه ډیره ده چې د منلو وړ برخه اخیستې وه. بیا منل کونکی مشر ته ژمنه لیږي چې هغه به په نورو رایو کې برخه وانخلي چې د ن څخه کم شمیر ولري. که چیرې منونکي دمخه یو څه ته رایه ورکړې وي (یعنې په دوهم پړاو کې یې دمخه یو څه ارزښت منلی وي) نو دا منل شوی ارزښت او د هغه رایې شمیره چې په هغه کې یې برخه اخیستې وه د خپلې ژمنې سره ضمیمه کوي.
   • که نه نو، که چیرې منونکي دمخه د لوړې شمیرې رایې په اړه پوه شي، دا کولی شي په ساده ډول د چمتووالي مرحله له پامه غورځوي او مشر ته ځواب ورنکړي.
3. مرحله 2a: منل. مشر باید د کورم څخه ځواب ته انتظار وکړي (په سیسټم کې د نوډونو اکثریت) او که چیرې د ځوابونو اړین شمیر ترلاسه شي، نو هغه د پیښو پراختیا لپاره دوه اختیارونه لري:
   • یو شمیر منونکي هغه ارزښتونه لیږلي چې دمخه یې ورته رایه ورکړې وه. په دې حالت کې، مشر د ډیرو رایو سره ارزښت ټاکي. راځئ چې دې ارزښت ته x ووایو، او دا ټولو نوډونو ته یو پیغام لیږي لکه: "مننه (n، x)"، چیرې چې لومړی ارزښت د خپل پروپوز مرحلې څخه د رایې ورکولو شمیره ده، او دویم ارزښت هغه څه دي چې هرڅوک یې راټول کړي، i.e هغه ارزښت چې موږ یې په حقیقت کې رایه ورکوو.
   • که چیرې د منلو وړونکو څخه هیڅ یو ارزښت ونه لیږل شي، مګر دوی په دې پړاو کې یوازې د رایې ورکولو ژمنه کړې، مشر کولی شي دوی ته بلنه ورکړي چې د دوی ارزښت ته رایه ورکړي، هغه ارزښت چې هغه په ​​​​لومړي ځای کې مشر شو. راځئ چې دا y ووایو. دا ټولو نوډونو ته پیغام لیږي لکه: "مننه (n، y)"، د تیرې پایلې سره ورته.
4. مرحله 2b: منل شوی. برسېره پردې، د منلو وړ نوډونه، د مشر څخه د "منل (...)" پیغام ترلاسه کولو سره، ورسره موافق دي (ټولو نوډونو ته تایید واستوئ چې دوی د نوي ارزښت سره موافق دي) یوازې که دوی د ځینو (نورو) ژمنه نه وي کړې) مشر به په رایه اچونه کې د ګول شمیرې سره برخه واخلي n' > n، که نه نو دوی د تایید غوښتنه له پامه غورځوي.

   که د نوډونو اکثریت مشر ته ځواب ووایی، او ټول یې نوی ارزښت تایید کړی، نو نوی ارزښت منل شوی ګڼل کیږي. هورې! که اکثریت نه وي رسیدلی یا داسې نوډونه شتون لري چې د نوي ارزښت منلو څخه انکار کوي، نو بیا هرڅه پیل کیږي.

دا څنګه د Paxos الګوریتم کار کوي. په دې پړاوونو کې هر یو ډیری نیمګړتیاوې لري، موږ په عملي توګه د ناکامیو ډولونه، د ډیری مشرانو ستونزې او نور ډیر څه په پام کې نه نیولي، مګر د دې مقالې موخه یوازې دا ده چې لوستونکي د ویشل شوي کمپیوټر نړۍ ته په لوړه کچه معرفي کړي.

دا هم د یادونې وړ ده چې Paxos د خپل ډول یوازینی نه دی، نور الګوریتمونه شتون لري، د بیلګې په توګه، رافټ، مګر دا د بلې مقالې لپاره موضوع ده.

د نورو مطالعاتو لپاره د موادو لینک

د پیل کچه:

• ویشل شوی توافق څنګه کار کوي؟, پریتي کاسیریډي، په منځني کې د بلاګ مقاله
• Paxos ساده کړي. د رښتیا لپاره، اډی کنچرلا، په منځنی کې د بلاګ مقاله
• غیر متمرکز فکرونه, Ittai ابراهیم، ​​بلاګ
• همغږي، اسینکروني او جزوي همغږي, Ittai ابراهیم، ​​د بلاګ مقاله

د لیسلي لامپورټ کچه:

• د یوې غلطې پروسې سره د توزیع شوي توافق ناممکنیت (FLP ناممکن)فیشر، لینچ او پیټرسن، څیړنیزه مقاله، 1985
• د پارلېمان پارلېمانلیسلي لامپورټ، څیړنیزه مقاله، 1998
• Paxos ساده کړيلیسلي لامپورټ، څیړنیزه مقاله، 2001

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