Исследование алгоритмов принятия консенсуса в сети ненадежных вычислителей (1187400)
Текст из файла
Ìèíèñòåðñòâî îáðàçîâàíèÿ è íàóêè Ðîññèéñêîé ÔåäåðàöèèÔåäåðàëüíîå ãîñóäàðñòâåííîå àâòîíîìíîå îáðàçîâàòåëüíîåó÷ðåæäåíèå âûñøåãî ïðîôåññèîíàëüíîãî îáðàçîâàíèÿ¾Ìîñêîâñêèé ôèçèêî-òåõíè÷åñêèé èíñòèòóò (ãîñóäàðñòâåííûé óíèâåðñèòåò)¿Ôàêóëüòåò óïðàâëåíèÿ è ïðèêëàäíîé ìàòåìàòèêèÊàôåäðà òåîðåòè÷åñêîé è ïðèêëàäíîé èíôîðìàòèêèÈññëåäîâàíèå àëãîðèòìîâïðèíÿòèÿ êîíñåíñóñàâ ñåòè íåíàäåæíûõ âû÷èñëèòåëåéÂûïóñêíàÿ êâàëèôèêàöèîííàÿ ðàáîòà(ìàãèñòåðñêàÿ äèññåðòàöèÿ)Íàïðàâëåíèå ïîäãîòîâêè: 01.09.56Ìàòåìàòè÷åñêèå è èíôîðìàöèîííûå òåõíîëîãèèÂûïîëíèë: ñòóäåíò 973 ãðóïïûËàíöîâ Àëåêñàíäð Âàëåðüåâè÷Íàó÷íûé ðóêîâîäèòåëü:ä.ô.-ì.í., ïðîôåññîðÒîðìàñîâ Àëåêñàíäð Ãåííàäüåâè÷Íàó÷íûé êîíñóëüòàíò:Íåïîðàäà Àíäðåé Ëåîíèäîâè÷Ìîñêâà 2015ÑîäåðæàíèåÑîäåðæàíèå21Ââåäåíèå42Ïîñòàíîâêà çàäà÷è52.1Îïèñàíèå çàäà÷è ïðèíÿòèÿ êîíñåíñóñà .
. . . . . . . . . . .52.2Âîçìîæíûå òèïû îøèáîê. . . . . . . . . . . . . . . . . . .62.3CAP-òåîðåìà. . . . . . . . . . . . . . . . . . . . . . . . . .72.4Ðàñïðåäåëåííûé êîíå÷íûé àâòîìàò34. . . . . . . . . . . . .Àëãîðèòì Paxos8123.1Ïðîöåäóðà ïðèíÿòèÿ ðåøåíèÿ. . . . . . . . . .
. . . . . .143.2Îïèñàíèå ôàç àëãîðèòìà Paxos . . . . . . . . . . . . . . . .233.3Ïîëó÷åíèå èíôîðìàöèè î ïðèíÿòîì ðåøåíèè . . . . . . . .243.4Îáðàáîòêà ñèòóàöèè âçàèìîáëîêèðîâêè. . . . . . . . . . .263.5Îñîáåííîñòè ðåàëèçàöèè . . . . . . . . . . . . . . .
. . . . .273.6Ïåðåõîä îò Single-Paxos ê Multi-Paxos . . . . . . . . . . . .28Àëãîðèòì Raft324.1Íåäîñòàòêè Paxos ñ òî÷êè çðåíèÿ Raft . . . . . . . . . . . .344.2Raft êàê àëãîðèòì ïðèíÿòèÿ êîíñåíñóñà . . . . . . . . . . .364.3Îñíîâûå ñîñòîÿíèÿ . . . . . . . . . . . . . . . . . . . . . . .3824.44.556Ïðîöåäóðà âûáîðîâ ëèäåðà. . . . . . . . .
. . . . . . . . .404.4.1Ïîáåäà â âûáîðàõ . . . . . . . . . . . . . . . . . . . .414.4.2Ïîáåäà äðóãîãî êàíäèäàòà . . . . . . . . . . . . . . .434.4.3Íè÷üÿ. . . . . . . . . . . . . . . . . . . . . . . . . .43Ðåïëèêàöèÿ æóðíàëà . . . . . . . . . . . . . . . . . . . . . .44Ðåçóëüòàòû èññëåäîâàíèé495.1Èññëåäîâàíèå ïîâåäåíèÿ àëãîðèòìîâ . . . . . . . . . .
. . .515.2Ñèòóàöèÿ îòêàçà ëèäåðà . . . . . . . . . . . . . . . . . . . .515.3Îòêàç îáû÷íîãî óçëà . . . . . . . . . . . . . . . . . . . . . .525.4Îòêàç óçëà-ëèäåðà555.5Ïðîèçâîäèòåëüíîñòü àëãîðèòìîâ. . . . . . . . . . . . . . . . . . . . . . .Çàêëþ÷åíèå. . . . . . .
. . . . . . . .5658Ñïèñîê ëèòåðàòóðû5931.ÂâåäåíèåÝòà ðàáîòà îïèñûâàåò, àíàëèçèðóåò, óòî÷íÿåò è ñðàâíèâàåò àëãîðèò-ìû ïðèíÿòèÿ êîíñåíñóñà Raft è Paxos, êîòîðûå ñëóæàò äëÿ ïîñòðîåíèÿîòêàçîóñòîé÷èâûõ ïðèëîæåíèé íà êëàñòåðå èç íåñêîëüêèõ óçëîâ, èñïîëüçóÿ êîíöåïöèþ ðàñïðåäåëåííîãî êîíå÷íîãî àâòîìàòà.Àëãîðèòì ïðèíÿòèÿ êîíñåíñóñà ïîçâîëÿåò ñòðîèòü íàäåæíûå ñèñòåìû èç íåíàäåæíûõ êîìïîíåíòîâ, ïîýòîìó ÿâëÿåòñÿ îñíîâîé ìíîãèõ ðàñïðåäåëåííûõ ñèñòåì.
Ýòà àêòóàëüíàÿ òåìà íàõîäèò ñâîå ïðèìåíåíèå âîòêàçîóñòîé÷èâûõ áàçàõ äàííûõ, ãðóïïîâûõ ñèñòåìàõ, è äðóãèõ ñèñòåìàõ. Íàñòîÿùàÿ ðàáîòà ñðàâíèâàåò ðåàëèçàöèè àëãîðèòìîâ Raft è Paxosâ ðàçëè÷íûõ ñèòóàöèÿõ, êàê îòêàç ïðîñòûõ óçëîâ, îòêàç ëèäåðà; ñðàâíèâàåò èõ ïðîèçâîäèòåëüíîñòü.Àëãîðèòì Ëåñëè Ëàìïîðòà Paxos [11] ÿâëÿåòñÿ îäíèì èç ãëàâíûõ èññëåäóåìûõ àëãîðèòìîâ ðåøåíèÿ çàäà÷è êîíñåíñóñà. Íåñìîòðÿ íà ýòî, åãîòðóäíî ïîíÿòü è ðåàëèçîâàòü, ïîòîìó ÷òî îí ïîñòðîåí íà íåèíòóèòèâíîìïîäõîäå. Äðóãîé ïðîáëåìîé ÿâëÿåòñÿ òî, ÷òî îòñóòñòâóåò ïîëíîå ÷åòêîåîïèñàíèå àëãîðèòìà Multi-Paxos [16].Àëãîðèòì Raft [18], ñîçäàííûé Äèåãî Oíãàðî è Äæîíîì Àóñòåðõîðòîì, ÿâëÿåòñÿ àëãîðèòìîì ðåøåíèÿ çàäà÷è êîíñåíñóñà, êîòîðûé, áóäó÷èîñíîâàí íà òåõ æå ïðåäïîëîæåíèÿõ, îáåñïå÷èâàåò òå æå ãàðàíòèè, ÷òîè Multi-Paxos.
Åãî ïëþñîì ÿâëÿåòñÿ îòíîñèòåëüíàÿ ïðîñòîòà, èíòóèòèâíîñòü è äîêàçàííàÿ áåçîïàñíîñòü.4Ïîñòàíîâêà çàäà÷è2.Êàê óæå óïîìèíàëîñü, çàäà÷à ïðèíÿòèÿ êîíñåíñóñà ÿâëÿåòñÿ îäíîé èçîñíîâîïîëàãàþùèõ äëÿ ñîâðåìåííûõ ðàñïðåäåëåííûõ êîìïüþòåðíûõ ñèñòåì. Çàäà÷à äîñòèæåíèÿ êîíñåíñóñà - ýòî çàäà÷à ïîëó÷åíèÿ ñîãëàñîâàííîãî çíà÷åíèÿ ãðóïïîé ó÷àñòíèêîâ, ÷ëåíû êîòîðîé íàçûâàþòñÿ óçëàìè,â ñèòóàöèè, êîãäà âîçìîæíû îòêàçû îòäåëüíûõ ó÷àñòíèêîâ, ïðåäîñòàâëåíèÿ èì íåêîððåêòíîé èíôîðìàöèè èëè èñêàæåíèÿ ïåðåäàííûõ çíà÷åíèéñðåäîé ïåðåäà÷è äàííûõ.Ãëàâíûìè çàäà÷àìè ýòîé ðàáîòû áûëî èññëåäîâàòü ñêîðîñòü ðàáîòû àëãîðèòìîâ Raft è Multi-Paxos, ñêîðîñòü âîññòàíîâëåíèÿ ïîñëå ðàçëè÷íûõ îøèáîê îòíîñèòåëüíî äðóã äðóãà.
Èçìåðåíèÿ ïðîèçâîäèëèñü ïðèðàçíîì ÷èñëå óçëîâ â êëàñòåðå.2.1Îïèñàíèå çàäà÷è ïðèíÿòèÿ êîíñåíñóñàÊîíñåíñóñ äîëæåí óäîâëåòâîðÿòü ñëåäóþùèì óñëîâèÿì:1. Ñîãëàñîâàííîñòü: âñå êîððåêòíûå ðàáîòàþùèå óçëû ïðèíèìàþòîäíî è òîæå çíà÷åíèå (ñâîéñòâî áåçîïàñíîñòè );2. Êîððåêòíîñòü: âûáðàííîå çíà÷åíèå äîëæíî áûòü îäíèì èç òåõ,êîòîðîå áûëî ïðåäëîæåíî êàêèì-ëèáî êîððåêòíî ðàáîòàþùèì óçëîì (ñâîéñòâî íåòðèâèàëüíîñòè );53. Êîíå÷íîñòü: êàæäûé êîððåêòíî ðàáîòàþùèé óçåë äîëæåí äåëàòüâûáîð çà êîíå÷íîå êîëè÷åñòâî øàãîâ (ñâîéñòâî çàâåðøåííîñòè ).Òåîðåìà Ôèøåðà, Ëèí÷à è Ïàòåðñîíà ãëàñèò, ÷òî íå ñóùåñòâóåò àñèíõðîííîãî äåòåðìèíèðîâàííîãî àëãîðèòìà ïðèíÿòèÿ êîíñåíñóñà, êîòîðûéáûë áû óñòîé÷èâ ê âûõîäó èç ñòðîÿ îäíîãî óçëà è ãàðàíòèðîâàë áû âñåñâîéñòâà êîíñåíñóñà[5].
Àñèíõðîíèçì îçíà÷àåò, ÷òî íåëüçÿ äîñòîâåðíîðàçëè÷èòü ðàáîòàåò ëè óçåë ìåäëåííî, èëè äîëãî èäåò ñîîáùåíèå, èëèæå îòêàçàë óçåë, äàæå åñëè ïðåäïîëîæèòü, ÷òî ñâÿçü ÿâëÿåòñÿ íàäåæíîé. Àëãîðèòìû Raft è Paxos ãàðàíòèðóþò òîëüêî ñâîéñòâî áåçîïàñíîñòèè íåòðèâèàëüíîñòè, íî íå âñåãäà óäîâëåòâîðÿþò ñâîéñòâó çàâåðøåííîñòè.2.2Âîçìîæíûå òèïû îøèáîêÑòàíäàðòíàÿ çàäà÷à êîíñåíñóñà òðåáóåò, ÷òîáû â àñèíõðîííîé ñèñòåìå áûëî âûïîëíåíî ñâîéñòâî áåçîïàñíîñòè è ñâîéñòâî íåòðèâèàëüíîñòè,âíå çàâèñèìîñòè îò êîëè÷åñòâà íåâèçàíòèéñêèõ îøèáîê, è ÷òîáû âñå òðèñâîéñòâà áûëè âûïîëíåíû ïðè ÷èñëå íåâèçàíòèéñêèõ îøèáîê ìåíüøå,÷åì ïîðîãîâîå çíà÷åíèå.
×èñëî êîððåêòíî ðàáîòàþùèõ óçëîâ, ïðè êîòîðûõ àëãîðèòì ðàáîòàåò êîððåêòíî, íàçûâàåòñÿ ðàçìåðîì êâîðóìà. ÄëÿMulti-Paxos è Raft äîïóñòèìî íå áîëåå F îøèáîê ïðè ðàçìåðå êâîðóìàF + 1 äëÿ êëàñòåðà èç 2F + 1 óçëîâ. Î÷åâèäíî, ÷òî äâà ëþáûõ êâîðóìà(ìíîæåñòâà èç âñåõ êîððåêòíî ðàáîòàþùèõ óçëîâ) äëÿ êëàñòåðà èç 2F +1 óçëîâ áóäóò ïåðåñåêàòüñÿ ïî êðàéíåé ìåðå â îäíîì óçëå. Òàêèì îáðàçîì, åñëè åñòü êâîðóì, òî ïî êðàéíåé ìåðå îäèí óçåë ëþáîãî áóäóùåãîêâîðóìà áóäåò ïðèíàäëåæàòü òåêóùåìó êâîðóìó, à çíà÷èò, áóäåò çíàòüâñå åãî îïåðàöèè. êîíòåêñòå çàäà÷è êîíñåíñóñà ñóùåñòâóþò ðàçíûå òèïû îøèáîê:61. Îñòàíîâêà ñ ñèãíàëîì: óçåë ïðåêðàùàåò ðàáîòó, à çàòåì ñîîáùàåò äðóãèì óçëàì î ñâîåì ñáîå.
Ýòîò òèï îøèáêè ïîçâîëÿåò òî÷íîîïðåäåëèòü, îòêàçàë ëè óçåë èëè íåò; òàêèå îøèáêè ïðåäîñòàâëÿþòñàìûå óäîáíûå äëÿ ðåàëèçàöèè ïðåäïîëîæåíèÿ îòíîñèòåëüíî ñáîåââ ñèñòåìå;2. Îñòàíîâêà: óçåë ïðåæäåâðåìåííî ïðåêðàùàåò êàêóþ-ëèáî àêòèâíîñòü, íåñìîòðÿ íà òî, ÷òî äî îñòàíîâêè îí ðàáîòàë ïîëíîñòüþêîððåêòíî. Ïîñëå îñòàíîâêè ýòîò óçåë ïðèîñòàíàâëèâàå åãî ðàáîòó.Ïðåäïîëàãàåòñÿ, ÷òî óçåë ìîæåò âîññòàíàâëèâàåòñÿ ïîñëå îñòàíîâêè è âêëþ÷àåòñÿ â ðàáîòó êëàñòåðà;3. Ïîòåðè ñîîáùåíèé: ïðè îòñûëêå è ïðè îòïðàâëåíèè ñîîáùåíèéìîãóò ïðîèñõîäèòü ïîòåðè ñîîáùåíèé, ïðîòèâîïîëîæíàÿ ñòîðîíàíèêàê íå ìîæåò óçíàòü, ÷òî ñîîáùåíèå, ïðåäíàçíà÷åííîå äëÿ íå¼,áûëî ïîòåðÿíî;4.
Âèçàíòèéñêèÿ îøèáêà: íàèáîëåå ñåðüåçíûé òèï îøèáêè, ïðîöåññ íà÷èíàåò ñåáÿ âåñòè íåêîððåêòíî. Íàïðèìåð, îí ìîæåò ïîñûëàòü ëèøíèå èëè ïðîòèâîðå÷èâûå ñîîáùåíèÿ, íå ðàáîòàòü êàêîå-òîâðåìÿ è òàê äàëåå. Äàííûé òèï îøèáîê â ðàáîòå íå ðàññìàòðèâàåòñÿ, òàê êàê Raft âîîáùå íå ïðèñïîñîáëåí äëÿ ðàáîòû ñ íàëè÷èåìâèçàíòèéñêèõ îøèáîê, à Paxos òðåáóåò çíà÷èòåëüíûõ èçìåíåíèé[7].2.3CAP-òåîðåìàCAP-òåîðåìà áûëà ñôîðìóëèðîâàíà Ýðèêîì Áðþýðîì â 2000 ãîäó, à÷åðåç äâà ãîäà îôèöèàëüíî äîêàçàíà. CAP-òåîðåìà óòâåðæäàåò, ÷òî ìîæíî ñîçäàòü ðàñïðåäåëåííóþ ñèñòåìó, êîòîðàÿ áóäåò óäîâëåòâîðÿòü ñâîé-7ñòâó ñîãëàñîâàííîñòè (òî åñòü å¼ îïåðàöèè çàïèñè àòîìàðíû, âñå ïîñëåäóþùèå îïåðàöèè ÷òåíèÿ âèäÿò íîâîå çíà÷åíèå), ñâîéñòâó äîñòóïíîñòè(ñèñòåìà ðàáîòàåò, ïîêà ðàáîòàåò õîòÿ áû îäèí ó÷àñòíèê), è óñòîé÷èâîéê ïîòåðè ñâÿçíîñòè (ñèñòåìà ïðîäîëæàåò ðàáîòó, äàæå åñëè ñâÿçè ìåæäóñåðâåðàìè âðåìåííî îòñóòñòâóþò), íî îäíîâðåìåííî ìîæíî ãàðàíòèðîâàòü òîëüêî äâà èç ýòèõ òðåõ ñâîéñòâ[6].Åñëè äâà óçëà ïîëó÷àþò äâà ïðîòèâîðå÷èâûå çàïðîñà îò êëèåíòîâ,îíè îáà äîëæíû ïðèíÿòü è îáðàáîòàòü çàïðîñû, òàêèì îáðàçîì, ïîä ñòàâÿïîä óãðîçó ñâîéñòâî ñîãëàñîâàííîñòè èëè, ïî êðàéíåé ìåðå îäèí èç íèõíå äîëæåí ïðèíèìàòü çàïðîñ, òàêèì îáðàçîì, ñòàâÿ ïîä óãðîçó ñâîéñòâîäîñòóïíîñòè.Êàê áóäåò âèäíî äàëåå, àëãîðèòìû Raft è Paxos ïîëíîñòüþ ïîä÷èíÿþòñÿ ýòîé òåîðåìå, îíè íå âñåãäà ìîãóò áûòü äîñòóïíû, íî âñåãäà ãàðàíòèðóþò ñîãëàñîâàííîñòü.2.4Ðàñïðåäåëåííûé êîíå÷íûé àâòîìàòÏðîñòåéøèé ñïîñîá ðåàëèçîâàòü ðàñïðåäåë¼ííóþ ñèñòåìó - ñîçäàòüíàáîð êëèåíòîâ, êîòîðûå ïîñûëàþò êîìàíäû èçáðàííîìó öåíòðàëüíîìóóçëó-ñåðâåðó.
Ñåðâåð äîëæåí áûòü îïèñàí êàê äåòåðìèíèðîâàííûé êîíå÷íûé àâòîìàò, êîòîðûé âûïîëíÿåò â îïðåäåëåííîì ïîðÿäêå êîìàíäûîò êëèåíòîâ. Êîíå÷íûé àâòîìàò èìååò ñîáñòâåííîå òåêóùåå ñîñòîÿíèå;øàã ðàáîòû àâòîìàòà ñîñòîèò â îáðàáîòêå î÷åðåäíîé êîìàíäû, â ðåçóëüòàòå àâòîìàò âîçâðàùàåò îòâåò êëèåíòó è ìåíÿåò ñâî¼ òåêóùåå ñîñòîÿíèå.Íàïðèìåð, êëèåíòàìè ðàñïðåäåë¼ííîé áàíêîâñêîé ñèñòåìû ìîãóòáûòü êëåðêè, à ñîñòîÿíèå äåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà ìîæåò ñîñòîÿòü èç ñ÷åòîâ è áàëàíñîâ ïîëüçîâàòåëåé áàíêà.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
