Исследование алгоритмов принятия консенсуса в сети ненадежных вычислителей (1187400), страница 8
Текст из файла (страница 8)
Òàêèì îáðàçîì, â êàæäûé ìîìåíò âðåìåíè èçìåðÿëîñü ìàêñèìàëüíîå ÷èñëî îïåðàöèé â ñåêóíäó, îáðàáàòûâàåìîå êëàñòåðîì èç 10óçëîâ.  íåêîòîðûé ìîìåíò âðåìåíè îòêëþ÷àëñÿ îäèí èç óçëîâ, èìèòèðóÿ îòêàç, à ñïóñòÿ íåêîòîðîå âðåìÿ âêëþ÷àëñÿ îáðàòíî.Êàê âèäíî èç ãðàôèêîâ, îòêàç îáû÷íîãî óçëà íå âûçûâàåò ñèëüíîãîïàäåíèÿ ïðîèçâîäèòåëüíîñòè äëÿ âñåõ òðåõ àëãîðèòìîâ.
Òàêæå, â Raft,ïîñëå âêëþ÷åíèÿ óçëà, íàáëþäàåòñÿ íåçíà÷èòåëüíîå ïàäåíèå ïðîèçâîäèòåëüíîñòè, âûçâàííîå ðåïëèöàöèåé æóðíàëà íà ýòîò óçåë.531800160014001200A1000800600 050100150200250300350400Ðèñ. 5.3: Ïðîèçâîäèòåëüíîñòü êëàñòåðà ñ îòêàçîì îäíîãî îáû÷íîãî óçëà, ñ àëãîðèòìîì Multi-Paxos-With-Leader, ãäå À - ïåðèîä îòêëþ÷åíèÿ óçëà. Ïî âåðòèêàëüíîé îñè- âðåìÿ íà÷àëà ýêñïåðåìåíòà, â ñåêóíäàõ, ïî ãîðèçîíòàëè - ÷èñëî îïåðàöèé â ñåêóíäó.1800160014001200A1000800600 050100150200250300350400Ðèñ.
5.4: Ïðîèçâîäèòåëüíîñòü êëàñòåðà ñ îòêàçîì îäíîãî îáû÷íîãî óçëà, ñ àëãîðèòìîì Multi-Paxos, ãäå À - ïåðèîä îòêëþ÷åíèÿ óçëà. Ïî âåðòèêàëüíîé îñè - âðåìÿíà÷àëà ýêñïåðåìåíòà, â ñåêóíäàõ, ïî ãîðèçîíòàëè - ÷èñëî îïåðàöèé â ñåêóíäó.5418001600A14001200B1000800600 050100150200250300350400Ðèñ. 5.5: Ïðîèçâîäèòåëüíîñòü êëàñòåðà ñ îòêàçîì ëèäåðà, ñ àëãîðèòìîì Raft, ãäå À- ïåðèîä îòêëþ÷åíèÿ ëèäåðà. Ïî âåðòèêàëüíîé îñè - âðåìÿ íà÷àëà ýêñïåðåìåíòà, âñåêóíäàõ, ïî ãîðèçîíòàëè - ÷èñëî îïåðàöèé â ñåêóíäó. Ïèê â íà÷àëå ïåðèîäà âûçâàíîòñóñòâèåì ëèäåðà è íåîáõîäèìîñòüþ ãîëîñîâàíèÿ. Ïèê B, ïîñëå âêëþ÷åíèÿ îòêàçàâøåé íîäû, âûçâàí òåì, ÷òî óçåë îáíîâëÿë ñâîé æóðíàë, êîòîðûé óñòàðåë çà âðåìÿîòêëþ÷åíèÿ.
Ïî ãîðèçîíòàëè - âðåìÿ íà÷àëà ýêñïåðåìåíòà, â ñåêóíäàõ, ïî âåðòèêàëüíîé îñè - ÷èñëî îïåðàöèé â ñåêóíäó.5.4Îòêàç óçëà-ëèäåðàÑèòóàöèÿ îòêëþ÷åíèÿ ëèäåðà âîçìîæíà òîëüêî äëÿ Raft è MultiPaxos-With-Leader. Äëÿ ïðîâåäåíèÿ ýêñïåðåìåíòà, ñòîðîíû êëèåíòà ãåíåðèðîâàëñÿ íåïðåðûâíûé íàáîð êîìàíä, íà êàæäóþ êîìàíäó äàâàëîñü100 ìèëëèñåêóíä íà îáðàáîòêó, â ñëó÷àå íåóäà÷íîé îáðàáîòêè ñèìóëÿòîð óâåëè÷èâàë âðåìåííóþ çàäåðæêó ìåæäêó êîìàíäàìè êëèåíòà, à åñëèêëàñòåð óñïåâàë îáðàáîòàòü êîìàíäó, ñèìóëÿòîð óìåíüøàë çàäåðæêó. Òàêèì îáðàçîì, â êàæäûé ìîìåíò âðåìåíè èçìåðÿëîñü ìàêñèìàëüíîå ÷èñëîîïåðàöèé â ñåêóíäó, îáðàáàòûâàåìîå êëàñòåðîì èç 10 óçëîâ.
 íåêîòîðûéìîìåíò âðåìåíè îòêëþ÷àëñÿ ëèäåðâ, èìèòèðóÿ îòêàç, à ñïóñòÿ íåêîòîðîåâðåìÿ âêëþ÷àëñÿ îáðàòíî.5518001600A140012001000800600 050100150200250300350400Ðèñ. 5.6: Ïðîèçâîäèòåëüíîñòü êëàñòåðà ñ îòêàçîì ëèäåðà, ñ àëãîðèòìîì Multi-PaxosWith-Leader, ãäå À - ïåðèîä îòêëþ÷åíèÿ ëèäåðà. Ïî ãîðèçîíòàëè - âðåìÿ íà÷àëàýêñïåðåìåíòà, â ñåêóíäàõ, ïî âåðòèêàëüíîé îñè - ÷èñëî îïåðàöèé â ñåêóíäó.5.5Ïðîèçâîäèòåëüíîñòü àëãîðèòìîâ ýòîì èññëåäîâàíèè êëèåíò ãåíåðèðîâàë íåïðåðûâíûé íàáîð êîìàíä,íà êîìàíäó äàâàëîñü 100 ìèëëèñåêóíä íà îáðàáîòêó, â ñëó÷àå íåóäà÷íîé îáðàáîòêè ñèìóëÿòîð óâåëè÷èâàë âðåìåííóþ çàäåðæêó ìåæäó êîìàíäàìè êëèåíòà, åñëè êëàñòåð óñïåâàë îáðàáîòàòü êîìàíäó, ñèìóëÿòîðóìåíüøàë çàäåðæêó.
Òàêèì îáðàçîì â êàæäûé ìîìåíò âðåìåíè èçìåðÿëàñü ïðîèçâîäèòåëüíîñòü êëàñòåðà. Êàê âèäíî èç ãðàôèêà, ïðîèçâîäèòåëüíîñòü àëãîðèòìîâ Raft è Multi-Paxos-With-Leader ïðèáëèçèòåëüíî îäèíàêîâà, à Multi-Paxos ðàáîòàåò ìåäëåííåå. Ýòî âûçâàííî òåì, ÷òî÷èñëî RPC-âûçîâîâ â ïîñëåäíåì ñëó÷àå ïðîïîðöèàíàëüíî êâàäðàòó îò÷èñëà óçëîâ, êàæäûé óçåë ÿâëÿåòñÿ èíèöèàòîðîì, êàæäûé èíèöèàòîððàññûëàåò ñîîáùåíèÿ êàæäîìó âûáîðùèêó.561500140013001200RaftMulti−Paxos−With−Leader1100Multi−Paxos100090046810121416Ðèñ. 5.7: Ïðîèçâîäèòåëüíîñòü êëàñòåðà ñ ðàçëè÷íûìè àëãîðèòìàìè êîíñåíñóñà. Ïîâåðòèêàëüíîé îñè - ÷èñëî îïåðàöèé â ñåêóíäó, ïî ãîðèçîíòàëè - ðàçìåð êëàñòåðà.576.Çàêëþ÷åíèå1.
Äàíî îïðåäåëåíèå çàäà÷è ðåøåíèÿ êîíñåíñóñà, è åãî ðîëè â ïîñòðîåíèè êëàñòåðîâ.2. Ðàçðàáîòàí è ðåàëèçîâàí ñèìóëÿòîð ðàñïðåäåëåííîé ñèñòåìû íà îñíîâå ðåïëèöèðîâàííîãî êîíå÷íîãî àâòîìàòà.3. Ïðèâåäåíû àëãîðèòìû Raft è Paxos ñ èõ ïîëíûì îïèñàíèåì, ïîêàçîí âûâîäàëãîðèòìà Multi-Paxos èç Single-Paxos.4. Ïîêàçàííî, ÷òî ââåäåíèå ìåõàíèçìà èçáðàííîãî ëèäåðà óëó÷øàåò ïðîèçâîäèòåëüíî ñòàíäàðòíîãî Multi-Paxos àëãîðèòìà, åãî ïðîèçâîäèòåëüíîñòü ñòàíîâèòñÿ ñðàâíèìîé ñ àëãîðèòìîì Raft.5.
Ïîêàçàííî, êàêîâû âðåìåííûå ïîðÿäêè âîññòàíîâëåíèÿ êëàñòåðà ïðè îòêàçå âûáðàííîãî ëèäåðà äëÿ àëãîðèòìîâ Multi-Paxos (ñ ëèäåðîì-èíèöèàòîðîì),Raft.6. Ïîêàçàííî, ÷òî îòêàç îäíîãî óçëà â êëàñòåðå, êîòîðûé íå ÿâëåòñÿ ëèäåðîì(åñëè ýòî àëãîðèòì ñ âîçìîæíîñòü ïðîâåäåíèÿ ãîëîñîâàíèÿ, â ïðîòèâíîì ñëó÷àå ïðîñòî ëþáîé óçåë), íåçíà÷èòåëüíî âëèÿåò íà ïðîèçâîäèòåëüíîñòü ñèñòåìûâöåëîì.7. Ïðîäåìîíñòðèðîâàííî, ÷òî â ñëó÷àå, êîãäà êàæäûé óçåë ÿâëÿåòñÿ è èíèöèàòîðîì è âûáîðùèêîì â Multi-Paxos, ÷èñëî ñîîáùåíèé ïðîïîðöèîíàëüíî êâàäðàòóðàçìåðó êëàñòåðà, ÷òî íåãàòèâíî ñêàçûâàåòñÿ íà ïðîèçâîäèòåëüíîñòè êëàñòåðàâöåëîì.58Ñïèñîê ëèòåðàòóðû[1] M. J.
Fischer,The Consensus Problem in Unreliable Distributed Systems. Proceedingsof the 1983 International FCT-Conference on Fundamentals of Computation Theory,1983[2] B. W. Lampson,How to build a highly available system using consensus.. DistributedAlgorithms, Eds. Springer-Verlag, 1996[3] J. Gray, L. Lamport,[4] J. Turek, D.
Shasha,Consensus on Transaction Commit.Microsoft Research, 2004The many faces of consensus in distributed systems. J. Computer25, 2, 1992[5] M. Fisher, N. Lynch, M. Paterson,Faulty Process.Impossibility of Distributed Consensus with OneJ. ACM 32, 2, 1985[6] S. Gilbert, N. Lynch, A. Nancy,Perspectives on the CAP Theorem.J. Computer 45,2, 2012[7] L. Lamport, M.
Fischer,Byzantine generals and transaction commit protocols.Microsoft Research, 1982[8] L. Lamport,Time, clocks, and the ordering of events in a distributed system. J. ACM21, 7, 1978[9] L. Lamport,The part-time parliament.[10] Ê. Êîðîòàåâ,J. ACM 16, 2, 1998Ñèñòåìà ðàñïðåäåëåííîãî, ìàñøòàáèðóåìîãî è âûñîêîíàäåæíîãîõðàíåíèÿ äàííûõ äëÿ âèðòóàëüíûõ ìàøèí.[11] L. Lamport,Paxos made simple.[12] L. Lamport, N. Lynch,Êîíôåðåíöèÿ HighLoad, 2012J. ACM 32, 4, 2001Generalized Consensus and Paxos. Microsoft Research , 200559Fast Paxos.[13] L. Lamport,DDistributed Computing 19, 2, 2005[14] C.
Tushar, G. Robert, R Joshua,Paxos Made Live An Engineering Perspective.PODC '07: 26th ACM Symposium on Principles of Distributed Computing, 2007[15] M Burrows,The Chubby Lock Service for Loosely-Coupled Distributed Systems.OSDI'06: Seventh Symposium on Operating System Design and Implementation,Seattle, 2006.[16] R. Renesse,[17] F.B.Paxos made moderately complex.Schneider,Cornell University, 2012.Implementing fault-tolerant services using the state machineapproach: a tutorial.J. ACM 22, 4, 1990[18] D. Ongaro, J. Ousterhout,In Search of an Understandable Consensus Algorithm.Stanford University, 2013[19] H. Howard, M. Schwarzkopf, A.
Madhavapeddy, J. Crowcroft,Have Consensus?.[20] H.Howard,Raft Reoated: Do WeSIGOPS Operating Systems Review, January 2015ARC: Analysis of Raft Consensus.Laboratory, UCAM-CL-TR-857, 2014.60University of Cambridge, Computer.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
