Исследование алгоритмов принятия консенсуса в сети ненадежных вычислителей (1187400), страница 2
Текст из файла (страница 2)
Ñíÿòèå íàëè÷-8íûõ ìîãëî áû áûòü âûïîëíåíî ÷åðåç âûïîëíåíèå êîíå÷íûì àâòîìàòîìêîìàíäû, êîòîðàÿ óìåíüøàëà áû áàëàíñ îïðåäåë¼ííîãî ñ÷¼òà òîãäà èòîëüêî òîãäà, êîãäà áàëàíñ áûë áû áîëüøå ñóììû ñíÿòèÿ, à çàòåì ãåíåðèðîâàëà áû ñòàðûé è íîâûé áàëàíñ â êà÷åñòâå ðåçóëüòàòà îáðàáîòêèêîìàíäû àâòîìàòà äëÿ êëèåíòà.Ðåàëèçàöèÿ, èñïîëüçóþùàÿ èçáðàííûé öåíòðàëüíûé ñåðâåð, íå ÿâëÿåòñÿ îòêàçîóñòîé÷èâîé, òàê êàê â ñëó÷àå îòêàçà öåíòðàëüíîãî ñåðâåðà, ñèñòåìà ïåðåñòàíåò îáðàáàòûâàòü êîìàíäû êëèåíòîâ.
Òàêèì îáðàçîì, äëÿòîãî, ÷òîáû îáåñïå÷èòü îòêàçîóñòîé÷èâîñòü, ñèñòåìå ñëåäóåò èñïîëüçîâàòü íàáîð ñåðâåðîâ, êàæäûé èç êîòîðûõ ïðåäñòàâëÿåò ñîáîé êîíå÷íûéàâòîìàò. Òàê êàê êîíå÷íûé àâòîìàò - äåòåðìèíèðîâàííûé, âñå ñåðâåðûîáÿçàíû âûïîëíÿòü îäèíàêîâûå ïîñëåäîâàòåëüíîñòè ïåðåõîäîâ ñîñòîÿíèé ïðè óñëîâèè îäèíàêîâûõ âõîäíûõ äàííûõ. Êëèåíò, äëÿ êîòîðîãî âûïîëíÿåòñÿ êîìàíäà, ìîæåò èñïîëüçîâàòü ëþáîé ñåðâåð.Àëãîðèòìû ïðèíÿòèÿ êîíñåíñóñà, êàê ïðàâèëî, âîçíèêàþò â êîíòåêñòå ïðèìåíåíèÿ ðàñïðåäåëåííûõ êîíå÷íûõ àâòîìàòîâ. Ïðè òàêîì ïîäõîäå, êîíå÷íûå àâòîìàòû, ðàñïîëîæåííûå íà ìíîæåñòâå ñåðâåðîâ êëàñòåðàâûïîëíÿþò èäåíòè÷íóþ êîìàíäó, íàõîäÿñü â îäíîì è òîì æå ñîñòîÿíèè òàêèì îáðàçîì, êëàñòåð ìîæåò ïðîäîëæàòü ðàáîòó, äàæå åñëè íåêîòîðûåèç åãî ñåðâåðîâ îòêàçûâàþò.
Òàêèì îáðàçîì, ðàñïðåäåëåííûå àâòîìàòûèñïîëüçóþòñÿ äëÿ ðåøåíèÿ ðàçíîîáðàçíûõ ïðîáëåì îòêàçîóñòîé÷èâîñòèâ ðàñïðåäåëåííûõ ñèñòåìàõ.Ðàñïðåäåëåííûå àâòîìàòû, êàê ïðàâèëî, ðåàëèçóåòñÿ ñ ïîìîùüþ ðåïëèöèðîâàííîãî æóðíàëà, êàê ïîêàçàíî íà ðèñóíêå2.1. Íà êàæäîì ñåðâåðå õðàíèòñÿ ðåïëèöèðóåìûé æóðíàë, ñîäåðæàùèé ïîñëåäîâàòåëüíîñòüêîìàíä, êîòîðûå åãî ñîáñòâåííûé êîíå÷íûé àâòîìàò âûïîëíÿåò â ôèêñèðîâàííîì ïîðÿäêå. Êàæäûé æóðíàë ñîäåðæèò îäèíàêîâûå êîìàíäû, â9DКлиентАлгоритмпринятияконсенсусаBAКонечный автоматРеплицируемый журналpush 1movpopC...СерверÐèñ. 2.1: Àðõèòåêòóðà ñèñòåìû ñ èñïîëüçîâàíèåì ðàñïðåäåëåííîãî êîíå÷íîãî àâòîìàòà.
Àëãîðèòì ïðèíÿòèÿ êîíñåíñóñà óïðàâëÿåò ðåïëèöèðîâàííûì æóðíàëîì, êîòîðûé ñîäåðæèò êîìàíäû äëÿ êîíå÷íîãî àâòîìàòà, êîòîðûå ïðèøëè îò êëèåíòîâ. Êîíå÷íûå àâòîìàòû ñ èäåíòè÷íûì ñîñòîÿíèåì âûïîëíÿþò èäåíòè÷íóþ ïîñëåäîâàòåëüíîñòü êîìàíä èç ðåïëèöèðîâàííîãî æóðíàëà, ïîýòîìó îíè ïîðîæäàþò îäèíàêîâûåâûõîäíûå äàííûå.îäíîì è òîì æå ïîðÿäêå, òàê ÷òî êàæäûé ðåïëèöèðîâàííûé êîíå÷íûé àïïàðàò îáðàáàòûâàåò èäåíòè÷íóþ ïîñëåäîâàòåëüíîñòü êîìàíä. Ïîñêîëüêóêîíå÷íûå àâòîìàòû ÿâëÿþòñÿ äåòåðìèíèðîâàííûìè, êàæäûé îáðàáàòûâàåò èäåíòè÷íóþ êîìàíäó ïðè èäåíòè÷íîì ñîñòîÿíèè è ïîëó÷àåò èäåíòè÷íûå ðåçóëüòàòû ðàáîòû.Ïîääåðæàíèå ðåïëèöèðîâàííîãî æóðíàëà ñîãëàñîâàííûì ÿâëÿåòñÿíåïîñðåäñòâåííîé çàäà÷åé àëãîðèòìà ïðèíÿòèÿ êîíñåíñóñà.
Ìîäóëü àëãîðèòìà ïðèíÿòèÿ êîíñåíñóñà íà ñåðâåðå ïîëó÷àåò êîìàíäû îò êëèåíòîâ(A) è äîáàâëÿåò èõ â ñâîé æóðíàë (B). Îí îáùàåòñÿ ñ ìîäóëÿìè àëãîðèòìà ïðèíÿòèÿ êîíñåíñóñà íà äðóãèõ ñåðâåðàõ, ÷òîáû ãàðàíòèðîâàòü,÷òî êàæäûé æóðíàë â êîíå÷íîì èòîãå ñîäåðæèò îäíè è òå æå êîìàíäû âîäèíàêîâîì ïîðÿäêå, äàæå åñëè íåêîòîðûå ñåðâåðû îòêàçàëè. Ïîñëå òîãî,êàê êîìàíäà êëèåíòà óñïåøíî ðåïëèöèðóåòñÿ, êîíå÷íûé àâòîìàò êàæäî-10ãî ñåðâåðà îáðàáàòûâàåò èõ ñîãëàñíî æóðíàëó (C), ðåçóëüòàòû ðàáîòûâîçâðàùàþòñÿ êëèåíòàì (D).
 ðåçóëüòàòå êëàñòåð ñåðâåðîâ âûãëÿäèòäëÿ êëèåíòà êàê åäèíûé, âûñîêîíàäåæíûé è ðàñïðåäåëåííûé êîíå÷íûéàâòîìàò.Àëãîðèòìû ïðèíÿòèÿ êîíñåíñóñà ïðè ïðàêòè÷åñêîì ïðèìåíåíèè îáëàäàþò ñëåäóþùèìè ñâîéñòâàìè:•îáåñïå÷èâàþò áåçîïàñíîñòü (íèêîãäà íå âîçâðàùàþò íåïðàâèëüíûéðåçóëüòàò) ïðè âñåõ óñëîâèÿõ (èñêëþ÷àÿ âèçàíòèéñêèå îøèáêè), âòîì ÷èñëå ïðè çàäåðæêàõ â ñåòè, ïîòåðüÿõ ñîîáùåíèé, èõ äóáëèðîâàíèè è èçìåíåíèè ïîðÿäêà;•ïîëíîñòüþ ôóíêöèîíàëüíû (ñèñòåìà îñòàåòñÿ äîñòóïíîé) äî òåõïîð, ïîêà áîëüøèíñòâî ñåðâåðîâ ìîãóò âçàèìîäåéñòâîâàòü è äðóã ñäðóãîì, è ñ êëèåíòàìè. Íàïðèìåð, òèïè÷íûé êëàñòåð èç ïÿòè ñåðâåðîâ ìîæåò ïåðåæèòü îòêàç äâóõ óçëîâ.
Óçëû, êàê ïðåäïîëàãàåòñÿ,ïðè âûõîäå èç ñòðîÿ îñòàíàâëèâàþòñÿ; îíè ìîãóò ïîçæå âîññòàíîâèòñÿ è ïðèñîåäèíèòüñÿ ê êëàñòåðó;•íå çàâèñÿò îò âðåìåíè, ÷òîáû îáåñïå÷èòü ñîãëàñîâàííîñòü æóðíàëîâ: íåèñïðàâíûå ÷àñû èëè áîëüøèå çàäåðæêè ñîîáùåíèé ìîãóò, âõóäøåì ñëó÷àå, áûòü ïðè÷èíîé ïðîáëåì äîñòóïíîñòè;•êîìàíäà ñ÷èòàåòñÿ çàâåðøåííîé êàê òîëüêî áîëüøèíñòâî ñåðâåðîâîòâåòèëî ñ ïîäòâåðæäåíèåì óñïåøíîãî âûïîëíåíèÿ êîìàíäû; ìåíüøèíñòâî ìåäëåííûõ óçëîâ-ñåðâåðîâ íå äîëæíî ïîâëèÿòü íà îáùóþïðîèçâîäèòåëüíîñòü ñèñòåìû.113.Àëãîðèòì PaxosÊàê èçâåñòíî, ñîãëàñîâàííîñòü â ðàñïðåäåë¼ííîé ñèñòåìå ìîæíî ïîä-äåðæèòü îäíèì èç ïðîòîêîëîâ ðàñïðåäåë¼ííûõ òðàíçàêöèé[2, 3]. Îäèí èçòàêèõ ïðîòîêîëîâ - ïðîòîêîë äâóõôàçíîãî ïîäòâåðæäåíèÿ òðàíçàêöèé,àêòèâíî ïðèìåíÿåìûé â òðàíçàêöèîííûõ ñèñòåìàõ.
Äðóãèì àëãîðèòìîìðàñïðåäåë¼ííûõ òðàíçàêöèé ÷àñòî íàçûâàþò Paxos, îäíàêî ñëåäóåò ïîíèìàòü, ÷òî Paxos ÿâëÿåòñÿ ïðîòîêîëîì ïðèíÿòèÿ ðåøåíèé, à íå ïîäòâåðæäåíèÿ òðàíçàêöèé, òàê êàê åãî òðåáîâàíèÿ ê ó÷àñòíèêàì îòëè÷àþòñÿîò òðåáîâàíèé ê ó÷àñòíèêàì â ïðîòîêîëå äâóõôàçíûõ áëîêèðîâîê.Àëãîðèòì Paxos òàêæå äàåò èíûå ãàðàíòèè: â ñëó÷àå äâóõôàçíîãî ïðîòîêîëà áëîêèðîâîê, ðåçóëüòàòîì ÿâëÿåòñÿ ïîäòâåðæäåíèå ACIDòðàíçàêöèè íà êàæäîì èç ñåðâåðîâ.  ñëó÷àå Paxos ðåçóëüòàòîì ÿâëÿåòñÿ ðåøåíèå, ïðèíÿòîå â êëàñòåðå è âåðíîå ëèøü äëÿ êëàñòåðà â öåëîì åñëè ñëó÷èòñÿ òàê, ÷òî â ðåçóëüòàòå ñåðèè îòêàçîâ âûæèâåò ëèøü îäèí èçóçëîâ, êîòîðûé îòñóòñòâîâàë â êëàñòåðå ïî ïðè÷èíå ñáîÿ âî âðåìÿ ïðîöåññà ïðèíÿòèÿ ðåøåíèÿ, òî ðåøåíèå íà ýòîì ñåðâåðå îêàæåòñÿ íåïðèíÿòûì, ÷òî ÿâëÿåòñÿ ñóùåñòâåííî áîëåå ñëàáûì ðåçóëüòàòîì ïî ñðàâíåíèþñ äâóõôàçíûìè áëîêèðîâêàìè.Ðàññìàòðèâàåòñÿ íàáîð ïðîöåññîâ, êîòîðûå äåëàþò äðóã äðóãó ïðåäëîæåíèÿ, êàæäîå èç êîòîðûõ ïðåäñòàâëåíî íåêîòîðûì çíà÷åíèåì.
Çàäà÷à àëãîðèòìà êîíñåíñóñà ñîñòîèò â òîì, ÷òîáû ãàðàíòèðîâàòü, ÷òî òîëüêîîäíî èç ñäåëàííûõ ïðåäëîæåíèé ïðèíÿòî. Òàêæå, åñëè íèêàêèõ ïðåäëî-12æåíèé íå ïîñòóïàëî, òî íè÷åãî è íå äîëæíî áûòü ïðèíÿòî. Åñëè îïðåäåë¼ííîå ïðåäëîæåíèå, ïðåäñòàâëåííîå íåêîòîðûì çíà÷åíèåì, áûëî âûáðàíî, òîãäà êàæäûé ó÷àñòíèê äîëæåí èìåòü âîçìîæíîñòü óçíàòü î ôàêòåïðèíÿòèÿ ðåøåíèÿ è åãî çíà÷åíèè.Èç äàííîãî îïèñàíèÿ çàäà÷è âûòåêàþò ñëåäóþùèå òðåáîâàíèÿ:•ïðèíÿòî ìîæåò áûòü òîëüêî îäíî èç ïðåäëîæåííûõ çíà÷åíèé•ïðîöåññ íå ìîæåò ïðèäòè ê âûâîäó, ÷òî ïðåäëîæåíèå áûëî ïðèíÿòî,åñëè òîëüêî ýòî äåéñòâèòåëüíî íå ïðîèçîøëîÀëãîðèòì Paxos íå ïûòàåòñÿ òî÷íî îáîçíà÷èòü íàñêîëüêî îïåðàòèâíîäîëæåí ïðîèñõîäèòü ïðîöåññ ïðèíÿòèÿ ðåøåíèÿ.
Îäíàêî, öåëüþ àëãîðèòìà ÿâëÿåòñÿ îáåñïå÷åíèå ãàðàíòèé òîãî, ÷òî îäíî èç ïðåäëîæåííûõçíà÷åíèé â êîíöå êîíöîâ áóäåò âûáðàíî, è, êîãäà âûáîð áûë ñäåëàí, ëþáîé ïðîöåññ èìåòü âîçìîæíîñòü óçíàòü ýòî çíà÷åíèå.Ëþáîé ïðîöåññ ìîæåò âûñòóïàòü â îäíîé èç òð¼õ ðîëåé: èíèöèàòîð,âûáîðùèê, èñïîëíèòåëü.  ðåàëüíîñòè îäèí è òîò æå ïðîöåññ ìîæåò âûñòóïàòü â ðàçíûõ ðîëÿõ â ðàçíûõ ñèòóàöèÿõ.Ïðåäïîëàãàåòñÿ, ÷òî äëÿ ïðèíÿòèÿ ðåøåíèé, ïðîöåññû êîììóíèöèðóþò äðóã ñ äðóãîì, ïîñûëàÿ äðóã äðóãó ñîîáùåíèÿ. Paxos îïèðàåòñÿ íààñèíõðîííóþ ìîäåëü ïåðåñûëêè ñîîáùåíèé, íî áåç âèçàíòèéñêèõ îøèáîê, òî åñòü:•ïðîöåññû ðàáîòàþò ñ ïðîèçâîëüíîé ñêîðîñòüþ, ìîãóò îñòàíîâèòüñÿèëè ïåðåçàïóñòèòüñÿ. Òàê êàê ïðîöåññ ìîæåò çàâåðøèòüñÿ àâàðèéíî ïîñëå ó÷àñòèÿ â ïðèíÿòèè ðåøåíèÿ ïî îäíîìó èç ïðåäëîæåíèé,íî äî òîãî êàê îí óçíàåò î ïðèíÿòîì ðåøåíèè, ïðîöåññ íå ñìîæåòóçíàòü î ïðèíÿòîì ðåøåíèè, åñëè íå áóäåò ñïîñîáà ïåðñèñòåíòíî13cîõðàíèòü åãî ñîñòîÿíèå â îòíîøåíèè ýòîãî êîíêðåòíîãî ðåøåíèÿíà ïåðèîä ìåæäó çàâåðøåíèåì è ïåðåçàïóñêîì•ñîîáùåíèÿ ìîãóò áûòü äîñòàâëåíû ñ ïðîèçâîëüíîé ñêîðîñòüþ, ìîãóò äóáëèðîâàòüñÿ è ìîãóò áûòü íå äîñòàâëåíû âîîáùå, íî èõ ñîäåðæèìîå íå ìîæåò áûòü ïîâðåæäåíî3.1Ïðîöåäóðà ïðèíÿòèÿ ðåøåíèÿÎäíèì èç ñàìûõ ïðîñòûõ ñïîñîáîâ ïðèíÿòèÿ ðåøåíèÿ â ïîñòàâëåííûõóñëîâèÿõ áûëî áû êàêèì-òî îáðàçîì îïðåäåëèòüñÿ îòíîñèòåëüíî îäíîãîïðîöåññà, êîòîðûé áû âñåãäà âûñòóïàë â ðîëè âûáîðùèêà.
Òîãäà, ëþáîéäðóãîé ïðîöåññ ñìîæåò ïîñëàòü ñâî¼ ïðåäëîæåíèå âûáîðùèêó è óçíàòüîò íåãî ðåçóëüòàò - áûëî ëè äàííîå ïðåäëîæåíèå ïðèíÿòî. Âûáîðùèê, âñâîþ î÷åðåäü, áóäåò âûáèðàòü ïåðâîå ïðåäëîæåíèå, êîòîðîå îí ïîëó÷èò.Ê ñîæàëåíèþ, õîòÿ ýòî ðåøåíèå è î÷åíü ïðîñòîå, îíî íåâîçìîæíî íàïðàêòèêå,òàê êàê â ñëó÷àå âûõîäà èç ñòðîÿ âûáîðùèêà íèêàêèå ïðåäëîæåíèÿ áîëüøå íå ñìîãóò áûòü ïðèíÿòû.Äðóãèì ñïîñîáîì ïðèíÿòèÿ ðåøåíèÿ áûëî áû âìåñòî îäíîãî âûáîðùèêà èñïîëüçîâàòü íåñêîëüêî. Èíèöèàòîð ïîñûëàåò ïðåäëîæåíèå ñî ñâîèì çíà÷åíèåì íåñêîëüêèì âûáîðùèêàì,êàæäûé èç íèõ ìîæåò åãî ïðèíÿòü. Ðåøåíèå ñ÷èòàåòñÿ ïðèíÿòûì, êîãäà äîñòàòî÷íî áîëüøîå êîëè÷åñòâî âûáîðùèêîâ ñîøëèñü íà îäíîì è òîì æå ïðåäëîæåíèè.Äëÿ òîãî, ÷òîáû ãàðàíòèðîâàòü ÷òî òîëüêî îäíî ïðåäëîæåíèå èç ìíîæåñòâà âàðèàíòîâ áûëî âûáðàíî, íåîáõîäèìî îáåñïå÷èòü ïðîñòîå áîëüøèíñòâî â ïîëüçó äàííîãî ïðåäëîæåíèÿ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
