Исследование алгоритмов принятия консенсуса в сети ненадежных вычислителей (1187400), страница 7
Текст из файла (страница 7)
Âòîðîå4512111111111111push 1 movpush 1 movpush 1 mo v31pop1pop1pop452222226add 2 movadd 2 movadd 2 mov3pop78индексжурнала33лидерadd 3 pop3pop3pop3add 3ведомыеpush 1 movpush 1 movpush 1 mov1pop1pop2add 222add 2 mov3pop33add 3 popÐèñ. 4.4: Æóðíàëû ñîñòîÿò èç çàïèñåé, êîòîðûå íóìåðóþòñÿ ïîñëåäîâàòåëüíî. Êàæäàÿ çàïèñü ñîäåðæèò íîìåð ýïîõè, â êîòîðîé îí áûë ñîçäàí è êîìàíäó äëÿ êîíå÷íîãîàâòîìàòà.ñâîéñòâî ãàðàíòèðóåòñÿ ïðîñòîé ïðîâåðêîé ñîãëàñîâàííîñòè â ðåàëèçàöèè ïðîöåäóðû AppendEntries. Ïðè îòïðàâêå çàïèñè ñ ïîìîùüþ âûçîâà AppendEntries, ëèäåð äîáàâëÿåò èíäåêñ è íîìåð ýïîõè çàïèñè, êîòîðàÿ íåïîñðåäñòâåííî ïðåäøåñòâóåò íîâîé çàïèñè.
Åñëè âåäîìûé íå íàõîäèò çàïèñü â ñâîåì æóðíàëå ñ òàêèì æå èíäåêñîì è ýïîõîé, òî îí îòêàçûâàåòñÿ ïðèíèìàòü íîâóþ çàïèñü.  ðåçóëüòàòå, âñÿêèé ðàç, êîãäàAppendEntries óñïåøíî çàâåðøàåòñÿ, ëèäåð çíàåò, ÷òî æóðíàë âåäîìîãîèäåíòè÷åí åãî ñîáñòâåííîìó æóðíàëó.Âî âðåìÿ îæèäàåìîé íîðìàëüíîé ðàáîòû, æóðíàëû ëèäåðà è âåäîìûõ îñòàþòñÿ ñîãëàñîâàííûìè, ïîýòîìó â AppendEntries ïðîâåðêà ñîãëàñîâàííîñòè íèêîãäà íå çàêîí÷èòñÿ íåóäà÷íî. Îäíàêî, â íåòðèâèàëüíûõñèòóàöèÿõ, íàïðèìåð òàêèõ, êàê îòêàç ëèäåðà, æóðíàë ìîæåò îêàçàòüñÿ âíåñîãëàñîâàííîì ñîñòîÿíèè (ñòàðûé ëèäåð ìîã íå óñïåòü ðåïëèöèðîâàòü46123456789101112индекс журналалидер с эпохой 8111445566(a)111445566(b)1114(c)11144556666(d)11144556667(e)1114444(f)1112223336ведомые7Ðèñ.
4.5: Êîãäà ëèäåð (ââåðõó) ïîáåæäàåò â âûáîðàõ, òî âîçìîæíû êàêèå-ëèáî èçñöåíàðèåâ (a-f ) â æóðíàëàõ âåäîìûõ. Êàæäûé áëîê ïðåäñòàâëÿåò ñîáîé îäíó çàïèñüæóðíàëà, ÷èñëî âíóòðè áëîêà - íîìåð ýïîõè ñîîòâåñòâóþùåé çàïèñè. Âåäîìûé ìîæåòíå èìåòü íåêîòîðûõ çàïèñåé (a-b), ìîæåò èìåòü äîïîëíèòåëüíûå íåçàôèêñèðîâàííûåçàïèñè (c-d), èëè îáà òèïà äåôåêòîâ (e-f ).
Íàïðèìåð, ñöåíàðèé (f ) ìîæåò ïðîèçîéòè,åñëè ñåðâåð áûë ëèäåðîì â ýïîõå 2 è äîáàâëÿë íåñêîëüêî çàïèñåé â ñâîé æóðíàëå, íîîòêàçàë ïðåæäå, ÷åì óñïåë çàôèêñèðîâàòü êàêèå-ëèáî èç íèõ; çàòåì ïåðåçàïóñòèëñÿ,ñòàë ëèäåðîì íà ýïîõó 3 è äîáàâèë íåñêîëüêî çàïèñåé â ñâîé æóðíàëå; ïðåæäå, ÷åìêàêàÿ-ëèáî èç çàïèñåé â ýïîõå 3 èëè 2 áûëà çàôèêñèðîâàííà, çàòåì ëèäåð ñíîâàîòêàçàë è íå ðàáîòàë â òå÷åíèå íåñêîëüêèõ ýïîõ.âñå çàïèñè â ñâîåì æóðíàëå).
Ýòè íåñîîòâåòñòâèÿ ìîãóò íàêàïëèâàòñÿâ ñëåäñòâèè ñåðèè îòêàçîâ ëèäåðîâ è âåäîìûõ. Ðèñóíîê 6 èëëþñòðèðóåò ñèòóàöèè, â êîòîðûõ æóðíàëû âåäîìûõ ìîãóò îòëè÷àòüñÿ îò íîâîãîëèäåðà. Âåäîìûé ìîæåò íå èìåòü çàïèñè, êîòîðûå ïðèñóòñòâóþò ó ëèäåðà (òàê êàê ëèäåð íå óñïåë ðåïëèöèðîâàòü âñå çàïèñè), îí ìîæåò èìåòüäîïîëíèòåëüíûå çàïèñè, êîòîðûå íå ïðèñóòñòâóþò ó ëèäåðà (òàê êàê ñòàðûé ëèäåð íà÷àë ðåïëèêàöèþ çàïèñè, íî îòêàçàë âî âðåìÿ âûïîëíåíèÿýòîé îïåðàöèè), òàê æå ìîãóò áûòü çàïèñè, êîòîðûå îòñóñòâóþò â îáîèõñåðâåðàõ.
Ïîñòîðîííèõ çàïèñåé â æóðíàëå ìîæåò áûòü íåñêîëüêî. Raft ëèäåð îáåñïå÷èâàåò íåïðîòèâîðå÷èâîñòü, çàñòàâëÿÿ æóðíàëûâåäîìûõ äóáëèðîâàòü åãî æóðíàë. Ýòî îçíà÷àåò, ÷òî êîíôëèêòóþùèå çàïèñè â æóðíàëàõ âåäîìûõ áóäóò ïåðåçàïèñàíû ñ ýëåìåíòàìè èç æóðíàëàëèäåðà.×òîáû ñîãëàñîâàòü æóðíàë, ëèäåð äîëæåí íàéòè ïîñëåäíþþ çàïèñü47â æóðíàëå, ãäå äâà æóðíàëà ñîâïàäàëè, ñòåðåòü âñå çàïèñè â æóðíàëå âåäîìîãî ïîñëå ýòîé òî÷êè, è îòïðàâèòü âåäîìîìó âñå çàïèñè ëèäåðàïîñëå ýòîé òî÷êè. Âñå ýòè äåéñòâèÿ ïðîèñõîäÿò âî âðåìÿ ïðîâåðêè ñîãëàñîâàííîñòè, âûïîëíÿåìîé AppendEntries.
Ëèäåð õðàíèò ïåðåìåííóþnext_index äëÿ êàæäîãî âåäîìîãî, îíà õðàíèò èíäåêñ çàïèñè æóðíàëàëèäåðà, êîòîðàÿ áóäåò îòïðàâëåíà ýòîìó âåäîìîìó ñëåäóþùåé. Êîãäàñåðâåð âïåðâûå ñòàíîâèòñÿ ëèäåðîì, îí èíèöèàëèçèðóåò âñå çíà÷åíèÿnext_index íîìåðîì ñâîåé ïîñëåäíåé çàïèñè â ñâîåì æóðíàëå ïëþñ îäèí.Åñëè æóðíàë âåäîìîãî ïðîòèâîðå÷èò ëèäåðó, ïðîâåðêà ñîãëàñîâàííîñòèâ ïðîöåäóðå AppendEntries îòêàæåò ïðè ñëåäóþùåì âûçîâå. Ïîñëå îòêàçà, ëèäåð óìåíüøàåò next_indexè ïîâòîðÿåò AppendEntries.  êîíöåêîíöîâ çíà÷åíèå AppendEntries äîñòèãíåò òî÷êè, ãäå ëèäåð è âåäîìûéèìåþò èäåíòè÷íûå æóðíàëû. Êîãäà ýòî ïðîèçîéäåò, ïðîâåðêà ñîãëàñîâàííîñòè AppendEntries óñïåøíî âûïîëíèòñÿ, çàòåì ïðîöåäóðà óäàëèòêîíôëèêòóþùèå çàïèñè â æóðíàëå âåäîìîãî, çàòåì äîáàâèò çàïèñè èçæóðíàëà ëèäåðà (åñëè òàêîâûå èìåþòñÿ).
Ïîñëå óñïåøíîãî âûïîëåíèÿïðîöåäóðû AppendEntries æóðíàë âåäîìîãî áóäåò ñîãëàñîâàí ñ ëèäåðîì,êàê ìèíèìóì äî êîíöà òåêóùåé ýïîõèÑ ýòèì ìåõàíèçìîì ëèäåðó íå íóæíî ïðåäïðèíèìàòü íèêàêèõ ñïåöèàëüíûõ äåéñòâèé äëÿ âîññòàíîâëåíèÿ æóðíàëà, êîãäà îí ïðèõîäèò êâëàñòè. Åìó äîñòàòî÷íî íà÷àòü îáû÷íóþ ðàáîòó, è æóðíàëû àâòîìàòè÷åñêè áóäóò ñîãëàñîâàííû ïðè îòêàçå ïðîâåðêè ñîãëàñîâàííîñòè ïðîöåäóðûAppendEntries. Ëèäåð íèêîãäà íå ïåðåçàïèñûâàåò èëè óäàëÿåò çàïèñè âñâîåì æóðíàëå.Ýòîò ìåõàíèçì ïîçâîëÿåò Raft ìîæåò ïîëó÷àòü, ðåïëèöèðîâàòü, èôèêñèðîâàòü íîâûå çàïèñè, ïîêà áîëüøèíñòâî èç ñåðâåðîâ ðàáîòàþò.48Ðåçóëüòàòû èññëåäîâàíèé5.Íà îñíîâå îïèñàíûõ àëãîðèòìîâ Raft è Paxos, áûë íàïèñàí ñèìóëÿòîð, ðåàëèçóþùèé ðåïëèöèðîâàííûé êîíå÷íûé àâòîìàò (ñ ðàñïðåäåëåííûì æóðíàëîì), îïèñàííûé â ãëàâå 1.
Ñîçäàíèå ñèìóëÿòîðà áûëî íà÷àòîñ ìîäåëèðîâàíèÿ óçëîâ è è ñâÿçåé ìåæäó íèìè, ñ äîáàâëåíèåì âîçìîæíîñòè îòêëþ÷àòü/ïðèîñòàíàâëèâàòü îïðåäåëåííûå óçëû è èìèòèðîâàòüïðîáëåìû â ñâÿçè ìåæäó íèìè: åñòü âîçìîæíîñòü äóáëèðîâàòü ñîîáùåíèÿ, ïðîïóñêàòü èõ èëè ïåðåóïîðÿäî÷èâàòü. Òàêæå, ñèìóëÿòîð ïîääåðæèâàåò âûïîëíÿåò ìîäåëèðîâàíèå ñîáûòèé â ðåàëüíîì âðåìåíè, ò.å. ñïîìîùüþ ìåõàíèçìà òàéìåðîâ, ïðåäàñòàâëÿåìîé ÎÑ.Îñíîâíûìè êîìïîíåíòàìè ñèìóëÿòîðà ÿâëÿþòñÿ:•Ñîáûòèÿ: cîçäàíèå ñîáûòèé ïðîèñõîäèò â îïðåäåëåííîì óçëå, âîïðåäåëåííûé ìîìåíò âðåìåíè, êîòîðûé ìîæåò ïðèâåñòè ê èçìåíåíèþ ñîñòîÿíèÿ óçëà èëè ãåíåðàöèè íåñêîëüêèõ ñîáûòèé, êîòîðûåïðîèñõîäÿò â ïîñëåäóþùèå ìîìåíòû âðåìåíè, îíè ìîãóò âîçíèêíóòü íà äðóãîì óçëå (ââèäó ïåðåäà÷è ñîîáùåíèé ìåæäó óçëàìè);•Ñïèñîê ñîáûòèé äëÿ îáðàáîòêè: â ñèñòåìå ñóùåñòâóåò î÷åðåäüñ ïðèîðèòåòàìè äëÿ ñîáûòèé, êîòîðûå äîëæíû áûòü îáðàáîòàíûñèìóëÿòîðîì;•Óçåë ñ ñîñòîÿíèåì: ïðåäñòàâëÿåò ñîáîé ëîêàëüíûå äàííûå äëÿðåàëèçàöèè àëãîðèòìà, ñâÿçàííîãî ñ êàæäîãî óçëîì è êëèåíòîì,49âçàèìîäåéñòâóþùèì ñ íèì;•×àñû: ìîíîòîííî âîçðàñòàþùàÿ ôóíêöèÿ, ãäå ñîáûòèÿ ÿâëÿþòñÿ ìãíîâåííûìè.
Öåëü ÷àñîâ ñîñòîèò èñêëþ÷èòåëüíî â òîì, ÷òîáûîáåñïå÷èâàòü ÷àñòè÷íîãî ïîðÿäêà äëÿ ñîáûòèé â ñïèñêå ñîáûòèé.•Íåäåòåðìèíèðîâàííîñòü: ãåíåðàòîð ñëó÷àéíûõ ÷èñåë, òðåáóþùèéñÿ àëãîðèòìó,òàêæå èñïîëüçóåòñÿ äëÿ ìîäåëèðîâàíèÿ çàäåðæêè è ïîòåðü ïàêåòîâ, îòêàçîâ óçëîâ.Îñíîâíîé öèêë ñèìóëÿòîðà ïåðåáèðàåò ñîáûòèÿ èç ñïèñêà ñîáûòèé.Êàæäîå ñîáûòèå îáðàáàòûâàåòñÿ ñèìóëÿòîðîì, ñ ó÷åòîì òåêóùåãî ñîñòîÿíèÿ ñâÿçàííîãî óçëîì, ðåçóëüòàò îáðàáîòêè âîçâðàùàåòñÿ â âèäå íîâûõñîáûòèé è íîâîãî ñîñòîÿíèÿ çàäåéñòâàííîãî óçëà; Âñå íîâûå ñîáûòèÿ äîáàâëÿþòñÿ â ñïèñîê ñîáûòèé.Ðåïëèöèðîâàííûéêîíå÷íûéàâòîìàòñèìóëèðîâàëèçìåíåíèåíåñêîëüêèõ öåëî÷èñëåííûõ ðåãèñòðîâ, êîìàíäû ñî ñòîðîíû êëèåíòà ïîçâîëÿþò çàäàâàòü çíà÷åíèÿ ýòèõ ðåãèñòðîâ, óâåëè÷èâàòü èèëè óìåíüøàòüèõ íà çàäàííóþ âåëè÷èíó.505.1Èññëåäîâàíèå ïîâåäåíèÿ àëãîðèòìîâÂñåãî ðàññìàòðèâàëîñü òðè ðåàëèçàöèè:•Raft, ïîëíîñòüþ ñîîòâåñòâóþùèé îïèñàíèþ, äàííîìó âûøå.•Multi-Paxos, ãäå êàæäûé óçåë ÿâëÿåòñÿ èíèöèàòîðîì.•Multi-Paxos-With-Leader, ñ èçáðàííûì èíèöèàòîðîì.Äëÿ âñåõ ýòèõ àëãîðèòìîâ ñóùåñòâóþò êàê îáùèå ñèòóàöèè, êàê íàïðèìåð, îòêàç îïðåäåëåííîãî óçëà, òàê è õàðàêòåðíûå òîëüêî äëÿ îïðåäåëåííûõ àëãîðèòìîâ.
Òàì, ãäå ýòî áûëî âîçìîæíî, àëãîðèòìû ñðàâíèâàëèñü â èäåíòè÷íûõ ñèòóàöèÿõ, êàê íàïðèìåð â çàìåðå ïðîèçâîäèòåëüíîñòè áûëî îäèíàêîâîå ÷èñëî óçëîâ è ÷èñëî çàïðîñîâ îò êëèåíòà â ñåêóíäó.5.2Ñèòóàöèÿ îòêàçà ëèäåðàÎäíà èç ïåðâûõ ðàññìàòðèâàåìûõ ñèòóàöèé äëÿ àëãîðèòìîâ Raft èMulti-Paxos-With-Leader - îòêàç èçáðàííîãî ëèäåðà.  ñëó÷àå åãî îòêàçà,â îñòàâøèõñÿ óçëàõ íà÷èíàåò îò÷èòûâàòüñÿ âíóòðåííèé òàéìåð, ïî ñðàáàòûâàíèþ êîòîðîãî óçåë èíèöèðóåò ãîëîñîâàíèå.
Ñàìà ñèòóàöèÿ ðàçáèâàåòñÿ íà äâå ÷àñòè: ïåðèîä äî ãîëîñîâàíèÿ, êîòîðûé ïðîäîëæàåòñÿ äîòåõ ïîð, ïîêà íå ñðàáîòàåò îäèí èç òàéìåðîâ îñòàâøèõ ïîñëå îòêàçà ëèäåðà óçëîâ. Êàê âèäíî èç ãðàôèêîâ 11 è 12, ìåõàíèçì âûáîðîâ ëèäåðîâîòðàáàòûâàåò áûñòðî è ñðàâíèì ïî ïîðÿäêó ñ âûáðàííîì äèàïàçîíîìñðàáàòûâàíèÿ òàéìåðîâ.51100%80%60%12−2425−5050−10040%100−200150−30020%0%050100150200250300(a) Ôóíêöèÿ ðàñïðåäåëåíèÿ âðåìåíè (â ìèëëèñåêóíäàõ) ñðàáàòûâàíèÿ òàéìåðîâîñòàâøèõñÿ ïîñëå îñòàíîâêè ëèäåëà óçëîâ, ïðè ðàçíûõ äèàïàçîíàõ ñðàáàòûâàíèÿðàíäîìèçèðîâàííûõ òàéìåðîâ. Êàê âèäíî èç ãðàôèêà, ïðîöåíò ñðàáîòàâøèõ óçëîâýêñïîíåíöèàëüíî ðàñòåò, çà ïåðâóþ òðåòü ñðàáàòûâàåò áîëåå 80% óçëîâ.100%80%12−2460%25−5050−10040%100−200150−30020%0%050100150200250300(b) Ôóíêöèÿ ðàñïðåäåëåíèÿ âðåìåíè îêîí÷àíèÿ ãîëîñîâàíèÿ, ïðè ðàçíûõ äèàïàçîíàõñðàáàòûâàíèÿ ðàíäîìèçèðîâàííûõ òàéìåðîâ.
Êàê âèäíî èç ãðàôèêà, ÷åðåç 250 ìèëëèñåêóíä äëÿ ïîñëå íà÷àëà ãîëîñîâàíèÿ, ïîáåäèòåëü áóäåò îïðåäåëåí ñ âåðîÿíòîñòüþíå ìåíüøå 99%.Ðèñ. 5.1: Ôóíêöèÿ ðàñïðåäåëåíèÿ â ñëó÷àå îòêàçà ëèäåðà. Ðàçìåð êëàñòåðà - 100óçëîâ.5.3Îòêàç îáû÷íîãî óçëàÄëÿ âñåõ òðåõ àëãîðèòìîâ âîçìîæíà ñèòóàöèÿ âûõîäà èç ñòðîÿ îäíîãî óçëîâ.  ñëó÷àå Raft è Multi-Paxos-With-Leader âûáèðàåòñÿ óçåë,êîòîðûé íå ÿâëÿåòñÿ ëèäåðîì. Äëÿ ïðîâåäåíèÿ ýêñïåðåìåíòà, ñòîðîíûêëèåíòà ãåíåðèðîâàëñÿ íåïðåðûâíûé íàáîð êîìàíä, íà êàæäóþ êîìàíäóäàâàëîñü 100 ìèëëèñåêóíä íà îáðàáîòêó, â ñëó÷àå íåóäà÷íîé îáðàáîòêè ñèìóëÿòîð óâåëè÷èâàë âðåìåííóþ çàäåðæêó ìåæäêó êîìàíäàìè êëè-521800160014001200BA1000800600 050100150200250300350400Ðèñ.
5.2: Ïðîèçâîäèòåëüíîñòü êëàñòåðà ñ îòêàçîì îäíîãî îáû÷íîãî óçëà, ñ àëãîðèòìîì Raft, ãäå À - ïåðèîä îòêëþ÷åíèÿ óçëà, âèäíî óìåíüøåíèå ïðîèçâîäèòåëüíîñòè.Ïèê B, ïîñëå âêëþ÷åíèÿ îòêàçàâøåé íîäû, âûçâàí òåì, ÷òî óçåë îáíîâëÿë ñâîé æóðíàë, êîòîðûé óñòàðåë çà âðåìÿ îòêëþ÷åíèÿ. Ïî âåðòèêàëüíîé îñè - âðåìÿ íà÷àëàýêñïåðåìåíòà, â ñåêóíäàõ, ïî ãîðèçîíòàëè - ÷èñëî îïåðàöèé â ñåêóíäó.åíòà, à åñëè êëàñòåð óñïåâàë îáðàáîòàòü êîìàíäó, ñèìóëÿòîð óìåíüøàëçàäåðæêó.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
