±à¼ÍƼö: |
±¾ÎÄÖ÷Òª½éÉÜRaftËã·¨µÄÔÀí¡¢¹¤³Ì»¯Ê±Óöµ½µÄÎÊÌâÓë½â¾ö·½°¸¡¢ÒÔ¼°¸Ä½øÐÔÄܵĴëÊ©,,Ï£Íû¶ÔÄúµÄѧϰÓÐËù°ïÖú¡£
±¾ÎÄÀ´×ÔÓÚÔÆÉçÇø£¬ÓÉ»ðÁú¹ûÈí¼þAlice±à¼ÍƼö¡£ |
|
µ¼Óï
RaftËã·¨ÊÇÒ»ÖÖ·Ö²¼Ê½Ò»ÖÂÐÔËã·¨¡£ÓëpaxosÏà±È£¬Ëü¸üÒ×Àí½âºÍ¹¤³Ì»¯¡£ÎÒÃÇÍêÕûʵÏÖÁ˸ÃËã·¨²¢½«ÆäÓ¦ÓÃÔÚ×ÔÑеĸ߿ɿ¿ÏûÏ¢Öмä¼þCMQÖУ¬Í¬Ê±³Áµí³ö¶ÔÍâͨÓõÄRaftËã·¨¿â¡£±¾ÎÄÖ÷Òª½éÉÜRaftËã·¨µÄÔÀí¡¢¹¤³Ì»¯Ê±Óöµ½µÄÎÊÌâÓë½â¾ö·½°¸¡¢ÒÔ¼°¸Ä½øÐÔÄܵĴëÊ©¡£
Ò»¡¢±³¾°½éÉÜ
·Ö²¼Ê½ÏµÍ³ÊÇÖ¸Ò»×é¶ÀÁ¢µÄ¼ÆËã»ú£¬Í¨¹ýÍøÂçÐͬ¹¤×÷µÄϵͳ£¬¿Í»§¿´À´¾ÍÈçͬµ¥Ì¨»úÆ÷ÔÚ¹¤×÷¡£Ëæ×Å»¥ÁªÍøÊ±´úÊý¾Ý¹æÄ£µÄ±¬·¢Ê½Ôö³¤£¬´«Í³µÄµ¥»úϵͳÔÚÐÔÄܺͿÉÓÃÐÔÉÏÒѾÎÞ·¨Ê¤ÈΣ¬·Ö²¼Ê½ÏµÍ³¾ßÓÐÀ©Õ¹ÐÔÇ¿£¬¿ÉÓÃÐԸߣ¬Á®¼Û¸ßЧµÈÓŵ㣬µÃÒԹ㷺ӦÓá£
µ«Óëµ¥»úϵͳÏà±È£¬·Ö²¼Ê½ÏµÍ³ÔÚʵÏÖÉÏÒª¸´ÔӺܶࡣCAPÀíÂÛÊÇ·Ö²¼Ê½ÏµÍ³µÄÀíÂÛ»ùʯ£¬ËüÌá³öÔÚÒÔÏÂ3¸öÒªËØÖУº
Consistency£¨Ç¿Ò»ÖÂÐÔ£©£ºÈκοͻ§¶Ë¶¼¿ÉÒÔ¶ÁÈ¡µ½ÆäËû¿Í»§¶Ë×î½üµÄ¸üС£
Availability£¨¿ÉÓÃÐÔ£©£º ϵͳһֱ´¦ÓÚ¿É·þÎñ״̬¡£
Partition-tolenrance£¨·ÖÇø¿ÉÈÝÈÌÐÔ£©£ºµ¥»ú¹ÊÕÏ»òÍøÂç·ÖÇø£¬ÏµÍ³ÈÔÈ»¿ÉÒÔ±£Ö¤Ç¿Ò»ÖÂÐԺͿÉÓÃÐÔ¡£
Ò»¸ö·Ö²¼Ê½ÏµÍ³×î¶àÖ»ÄÜÂú×ãÆäÖÐ2¸öÒªËØ¡£¶ÔÓÚ·Ö²¼Ê½ÏµÍ³¶øÑÔ£¬PÏÔÈ»ÊDZز»¿ÉÉٵģ¬ÄÇôֻÄÜÔÚAPºÍCPÖ®¼äȨºâ¡£APϵͳÎþÉüǿһÖÂÐÔ£¬ÕâÔÚijЩҵÎñ³¡¾°Ï£¨Èç½ðÈÚÀࣩÊDz»¿É½ÓÊܵģ¬CPϵͳ¿ÉÒÔÂú×ãÕâÀàÐèÇó£¬ÎÊÌâµÄ¹Ø¼üÔÚÓÚ»áÎþÉü¶àÉÙ¿ÉÓÃÐÔ¡£´«Í³µÄÖ÷±¸Ç¿Í¬²½Ä£Ê½ËäÈ»¿ÉÒÔ±£Ö¤Ò»ÖÂÐÔ£¬µ«Ò»µ©»úÆ÷¹ÊÕÏ»òÍøÂç·ÖÇøÏµÍ³½«±äµÃ²»¿ÉÓá£paxosºÍraftµÈÒ»ÖÂÐÔËã·¨µÄÌá³ö£¬ÃÖ²¹ÁËÕâһȱÏÝ¡£ËüÃÇÔÚ±£Ö¤CPµÄǰÌáÏ£¬Ö»ÒªÇó´ó¶àÊý½Úµã¿ÉÒÔÕý³£»¥Áª£¬ÏµÍ³±ã¿ÉÒÔÒ»Ö±´¦ÓÚ¿ÉÓÃ״̬£¬¿ÉÓÃÐÔÉÏÏÔÖøÌá¸ß¡£paxosµÄÀíÂÛÐÔÆ«Ç¿£¬¿ª·¢ÕßÐèÒª×Ô¼º´¦ÀíºÜ¶àϸ½Ú£¬ÕâÒ²ÊÇËüÓкܶà±äÖÖµÄÔÒò£¬Ïà¶Ô¶øÑÔraft¸üÒ×Àí½âºÍ¹¤³Ì»¯£¬Ò»¾Ìá³ö±ã¹ãÊÜ»¶Ó¡£
ÔÚÎÒÃǹØ×¢µÄÏûÏ¢Öмä¼þÁìÓò£¬½ðÈÚÖ§¸¶ÀàÒµÎñÍùÍù¶ÔÊý¾ÝµÄǿһÖÂÐԺ͸߿ɿ¿ÐÔÓÐÑϸñÒªÇó¡£Ç¿Ò»ÖÂÐÔ£ºA¸øBתÕË100Ôª£¬ÏµÍ³·µ»ØAתÕ˳ɹ¦¡£´ËºóB²éѯÓà¶îʱӦ¸ÃÄÜÏÔʾÊÕµ½100Ôª£¬Èç¹û·¢ÏÖ²¢Î´ÊÕµ½»ò¸ôÒ»¶Îʱ¼äºó²ÅÊÕµ½£¬ÄÇÕâÑùµÄϵͳ·ÇǿһÖÂÐÔ£»¸ß¿É¿¿ÐÔ£ºÒ»¸öÇëÇóÈç¹û·µ»Ø¿Í»§³É¹¦£¬ÄÇôÐèÒª±£Ö¤ÇëÇó½á¹û²»¶ªÊ§¡£
ÔÚ¶ÔÖ÷Á÷µÄÏûÏ¢Öмä¼þ½øÐе÷Ñк󣬷¢ÏÖËüÃÇÔÚÓ¦¶ÔÕâÖÖ³¡¾°Ê±¶¼´æÔÚÒ»¶¨µÄ²»×㣺
RabbitMQ£ºÒ»¸öÇëÇóÐèÒªÔÚËùÓнڵãÉÏ´¦Àí2´Î²ÅÄܱ£Ö¤Ò»ÖÂÐÔ£¬ÐÔÄܲ»¸ß¡£
Kafka£º kafkaÖ÷ÒªÓ¦ÓÃÔÚÈÕÖ¾¡¢´óÊý¾ÝµÈ·½Ïò£¬ÉÙÁ¿¶ªÊ§Êý¾ÝÒµÎñ¿ÉÒÔÈÌÊÜ£¬µ«²»ÊʺÏÒªÇóÊý¾Ý¸ß¿É¿¿ÐÔµÄϵͳ¡£
RocketMQ£ºÎ´²ÉÓÃÒ»ÖÂÐÔËã·¨£¬Èç¹ûÅäÖóÉÒ첽ģʽ¿ÉÄܶªÊ§Êý¾Ý£¬Í¬²½Ä£Ê½Ï½ڵã¹ÊÕÏ»òÍøÂç·ÖÇø¶¼»áÓ°Ïì¿ÉÓÃÐÔ¡£
SQS£ºÖ»Ìṩ×îÖÕÒ»ÖÂÐÔ£¬²»±£Ö¤Ç¿Ò»ÖÂÐÔ¡£
¼øÓÚÒÔÉÏ·ÖÎö£¬ÎÒÃÇÉè¼Æ¿ª·¢ÁË»ùÓÚRaftµÄǿһÖ¸߿ɿ¿ÏûÏ¢Öмä¼þCMQ¡£½ÓÏÂÀ´»áÏêϸ½éÉÜraftËã·¨ÔÀíϸ½Ú¡¢ÈçºÎÓ¦ÓÃÔÚCMQÖÐÔÚ±£Ö¤ÏûÏ¢¿É¿¿²»¶ªÊ§ÒÔ¼°ÊµÏÖ¹ý³ÌÖÐÎÒÃÇÔÚÐÔÄÜ·½ÃæËù×÷µÄÓÅ»¯¡£
¶þ¡¢RaftËã·¨ºËÐÄÔÀí
2.1 ¸ÅÊö
raftËã·¨ÊÇDiego Ongaro²©Ê¿ÔÚÂÛÎÄ¡¶In Search of an Understandable
Consensus Algorithm¡·,2014 USENIXÖÐÊ×´ÎÌá³ö£¬Ëã·¨Ö÷Òª°üÀ¨Ñ¡¾ÙºÍÈÕ־ͬ²½Á½²¿·Ö:
µÚÒ»½×¶Î Ñ¡¾Ù£º
´Ó¼¯ÈºÖÐÑ¡³öÒ»¸öºÏÊʵĽڵã×÷ΪLeader¡£
µÚ¶þ½×¶Î ÈÕ־ͬ²½£º
Ñ¡¾Ù³öµÄLeader½ÓÊÕ¿Í»§¶ËÇëÇ󣬽«ÆäתΪraftÈÕÖ¾¡£
Leader½«ÈÕ־ͬ²½µ½ÆäËû½Úµã£¬µ±´ó¶àÊý½ÚµãдÈë³É¹¦ºó£¬ÈÕÖ¾±äΪCommitted£¬Ò»¾CommittedÈÕÖ¾±ã²»»áÔÙ±»´Û¸Ä¡£
Leader¹ÊÕÏʱ£¬Çл»µ½µÚÒ»½×¶Î£¬ÖØÐÂÑ¡¾Ù¡£
ÒÔÏÂÊǹᴩraftËã·¨µÄÖØÒªÊõÓ
Term£º ½Úµãµ±Ç°Ëù´¦µÄÖÜÆÚ£¬¿ÉÒÔ¿´×÷Ò»¸öÎÄÃ÷Ëù´¦µÄʱ´ú¡£
votedFor£º µ±Ç°TermµÄͶƱÐÅÏ¢£¬Ã¿¸ö½ÚµãÔÚ¸ø¶¨µÄTermÉÏÖ»ÄÜͶƱһ´Î¡£
**Entry£º **raftÈÕÖ¾ÖеĻù±¾µ¥Ôª£¬°üº¬index¡¢termºÍuser_data¡£ÆäÖÐindexÔÚÈÕÖ¾ÎļþÖÐ˳Ðò·ÖÅ䣬termΪ´´½¨¸ÃentryµÄleader
term£¬user_data ÒµÎñÊý¾Ý¡£
State : ½Úµã½ÇÉ«£¨Leader¡¢Candidate¡¢FollowerÖ®Ò»£©¡£
CommitIndex£ºÒÑÌá½»µ½µÄÈÕÖ¾Index¡£
State Machine£º×´Ì¬»ú¡£ÒµÎñÄ£¿é£¬ÓëRaft½»»¥¡£
ApplyIndex£ºÒÑÓ¦Óõ½µÄÈÕÖ¾Index¡£
ElectionTime£ºÑ¡¾Ù³¬Ê±Ê±¼ä¡£
½ÚµãÖ®¼äͨ¹ýRPCͨÐÅÀ´Íê³ÉÑ¡¾ÙºÍÈÕ־ͬ²½£¬·¢ËÍ·½ÔÚ·¢ËÍRPCʱ»áЯ´ø×ÔÉíµÄTerm£¬½ÓÊÕ·½ÔÚ´¦ÀíRPCʱÓÐÒÔÏÂÁ½ÌõͨÓùæÔò£º
RPCÖеÄRTerm´óÓÚ×ÔÉíµ±Ç°Term£¬¸üÐÂ×ÔÉíTerm = RTerm¡¢votedFor = null£¬×ªÎªFollower¡£
RPCÖеÄRTermСÓÚ×ÔÉíµ±Ç°Term£¬¾Ü¾øÇëÇó£¬ÏìÓ¦°üÖÐЯ´ø×ÔÉíµÄTerm¡£
2.2 Ñ¡¾Ù
RaftËã·¨ÊôÓÚÇ¿Leaderģʽ£¬Ö»ÓÐLeader¿ÉÒÔ´¦Àí¿Í»§¶ËµÄÇëÇó£¬Leaderͨ¹ýÐÄÌøÎ¬³Ö×ÔÉíµØÎ»£¬³ý·ÇLeader¹ÊÕÏ»òÍøÂçÒì³££¬·ñÔòLeader±£³Ö²»±ä¡£Ñ¡¾Ù½×¶ÎµÄÄ¿µÄ¾ÍÊÇΪÁË´Ó¼¯ÈºÖÐÑ¡³öºÏÊʵÄLeader½Úµã¡£
Ñ¡¾ÙÁ÷³Ì£º
1.½Úµã³õʼ״̬¾ùΪFollower£¬FollowerÖ»±»¶¯½ÓÊÕÇëÇó£¬Èç¹ûElectionTimeµ½ÆÚʱÈÔδÊÕµ½LeaderµÄAppendEntry
RPC£¬FollowerÈÏΪµ±Ç°Ã»ÓÐLeader£¬×ªÎªCandidate¡£
2.CandidateÔÚ¼¯ÈºÖй㲥RequestVote RPC£¬³¢ÊÔ¾ºÑ¡Leader£¬ÆäËû½ÚµãÊÕµ½ºóÊ×ÏÈÅжÏÊÇ·ñͬÒâ±¾´ÎÑ¡¾Ù£¬²¢½«½á¹û·µ»Ø¸øCandidate¡£Èç¹ûCandidateÊÕµ½´ó¶àÊý½ÚµãµÄͬÒâÏìÓ¦£¬×ªÎªLeader¡£
3.Leader½ÓÊÕ¿Í»§¶ËÇëÇ󣬽«ÆäתΪEntry×·¼Óµ½ÈÕÖ¾Îļþ£¬Í¬Ê±Í¨¹ýAppendEntry RPCͬ²½ÈÕÖ¾Entry¸øÆäËû½Úµã¡£
ÏÂÃæÍ¨¹ýÒ»¸ö°¸ÀýÏêϸ˵Ã÷Ñ¡¾ÙÁ÷³Ì¡£
1£©³õʼ״̬£º3¸ö½Úµã×é³ÉµÄ¼¯Èº£¬³õʼ¾ùΪFollower״̬£¬Í¼Öз½¸ñ²¿·Ö´ú±í½ÚµãµÄraftÈÕÖ¾¡£
2£©·¢ÆðÑ¡¾Ù£º½Úµã1Ñ¡¾Ù¶¨Ê±Æ÷Ïȵ½ÆÚ£¬×ªÎªCandidate£¬Term×ÔÔö£¬¸üÐÂvoteFor=1(ͶƱ¸ø×Ô¼º£©£¬½Ó׏㲥RequestVote
RPC¸ø¼¯ÈºÖÐÆäËû½Úµã£¬RequestVote RPC»áЯ´ø½ÚµãµÄÈÕÖ¾ÐÅÏ¢¡£
3£©ÏìӦѡ¾Ù£º½Úµã2ºÍ3ÊÕµ½RequestVote RPCºó£¬¸ù¾ÝRPC¹æÔò£¬¸üÐÂtermºÍvoteFor(term:6
, voteFor:null )£»È»ºóÅжÏÊÇ·ñͬÒâ±¾´ÎÑ¡¾Ù£¬Èç¹ûÒÑͶƱ¸ø±ðÈË£¬Ôò¾Ü¾ø±¾´ÎÑ¡¾Ù£¨ÕâÀïvoteFor£ºnull
δͶƱ£©£¬Èç¹ûRequestVote RPCÖеÄÈÕ־ûÓÐ×ÔÉíÈ«£¬Ò²¾Ü¾ø£¬·ñÔòͬÒ⣨ÕâÀï½Úµã1µÄÈÕÖ¾±È2¡¢3¶¼¸üÈ«£©£»×îºóͨ¹ývoteReply
RPCÏìӦͶƱ½á¹û¡£
4£©Ñ¡¾ÙÍê³É£ºÓÉÓÚ½Úµã2ºÍ3¶¼Í¬Òâ±¾´ÎÑ¡¾Ù£¬ËùÒÔ½Úµã1ÔÚÊÕµ½ÈκÎÒ»¸öµÄvoteReply
RPC±ãתΪLeader£¨´ó¶àÊýͬÒâ¼´¿É£©¡£
Ñ¡¾Ù³¬Ê±Öµ£º
ÔÚÑ¡¾Ùʱ¿ÉÄÜ»á³öÏÖÁ½¸ö½ÚµãµÄÑ¡¾Ù¶¨Ê±Æ÷ͬʱµ½ÆÚ²¢·¢ÆðÑ¡¾Ù£¬¸÷×Եõ½Ò»°ëѡƱµ¼ÖÂÑ¡¾Ùʧ°Ü£¬Ñ¡¾Ùʧ°ÜÒâζ×ÅϵͳûÓÐLeader£¬²»¿É·þÎñ¡£Èç¹ûÑ¡¾Ù¶¨Ê±Æ÷ÊǶ¨Öµ£¬ºÜ¿ÉÄÜÁ½ÕßÔÙ´Îͬʱµ½ÆÚ¡£ÎªÁ˽µµÍ³åÍ»µÄ¸ÅÂÊ£¬Ñ¡¾Ù³¬Ê±Öµ²ÉÓÃËæ»úÖµµÄ·½Ê½¡£´ËÍ⣬ѡ¾Ù³¬Ê±ÖµÈç¹û¹ý´ó»áµ¼ÖÂLeader¹ÊÕÏ»áºÜ¾Ã²Å»áÔÙ´ÎÑ¡¾Ù¡£Ñ¡¾Ù³¬Ê±ÖµÍ¨³£È¡300ms~600msÖ®¼äµÄËæ»úÖµ¡£
2.3ÈÕ־ͬ²½
Ñ¡¾Ù½×¶ÎÍê³Éºó£¬Leader½Úµã¿ªÊ¼½ÓÊÕ¿Í»§¶ËÇëÇ󣬽«ÇëÇó·â×°³ÉEntry×·¼Óµ½raftÈÕÖ¾Îļþĩβ£¬Ö®ºóͬ²½Entryµ½ÆäËûFollower½Úµã¡£µ±´ó¶àÊý½ÚµãдÈë³É¹¦ºó£¬¸ÃEntry±»±ê¼ÇΪcommitted£¬raftËã·¨±£Ö¤ÁËcommittedµÄEntryÒ»¶¨²»»áÔÙ±»Ð޸ġ£
ÈÕ־ͬ²½¾ßÌåÁ÷³Ì£º
1£©LeaderÉÏΪÿ¸ö½Úµãά»¤NextIndex¡¢MatchIndex£¬NextIndex±íʾ´ý·¢Íù¸Ã½ÚµãµÄEntry
index£¬MatchIndex±íʾ¸Ã½ÚµãÒÑÆ¥ÅäµÄEntry index£¬Í¬Ê±Ã¿¸ö½Úµãά»¤CommitIndex±íʾµ±Ç°ÒÑÌá½»µÄEntry
index¡£×ªÎªLeaderºó»á½«ËùÓнڵãµÄNextIndexÖÃΪ×Ô¼º×îºóÒ»ÌõÈÕÖ¾index+1£¬MatchIndexÈ«ÖÃ0£¬Í¬Ê±½«×ÔÉíCommitIndexÖÃ0¡£
2£©Leader½Úµã²»¶Ï½«user_dataתΪEntry×·¼Óµ½ÈÕÖ¾Îļþĩ⣬Entry°üº¬index¡¢termºÍuser_data£¬ÆäÖÐindexÔÚÈÕÖ¾ÎļþÖдÓ1¿ªÊ¼Ë³Ðò·ÖÅ䣬termΪLeaderµ±Ç°µÄterm¡£
3£©Leaderͨ¹ýAppendEntry RPC½«Entryͬ²½µ½Followers£¬FollowerÊÕµ½ºóУÑé¸ÃEntry֮ǰµÄÈÕÖ¾ÊÇ·ñÒÑÆ¥Åä¡£ÈçÆ¥ÅäÔòÖ±½ÓдÈëEntry£¬·µ»Ø³É¹¦£»·ñÔòɾ³ý²»Æ¥ÅäµÄÈÕÖ¾£¬·µ»ØÊ§°Ü¡£Ð£ÑéÊÇͨ¹ýÔÚAppendEntry
RPCÖÐЯ´ø´ýдÈëEntryµÄǰһÌõentryÐÅÏ¢Íê³É¡£
4£©µ±Follower·µ»Ø³É¹¦Ê±£¬¸üжÔÓ¦½ÚµãµÄNextIndexºÍMatchIndex£¬¼ÌÐø·¢ËͺóÐøµÄEntry¡£Èç¹ûMatchIndex¸üк󣬴ó¶àÊý½ÚµãµÄMatchIndexÒÑ´óÓÚCommitIndex£¬Ôò¸üÐÂCommitIndex¡£Follower·µ»ØÊ§°Üʱ»ØÍËNextIndex¼ÌÐø·¢ËÍ£¬Ö±µ½Follower·µ»Ø³É¹¦¡£
5£©Leaderÿ´ÎAppendEntry RPCÖлáЯ´øµ±Ç°×îеÄLeaderCommitIndex£¬FollowerдÈë³É¹¦Ê±»á½«×ÔÉíCommitIndex¸üÐÂΪMin(LastLogIndex,LeaderCommitIndex)¡£
ͬ²½¹ý³ÌÖÐÿ´ÎÈÕÖ¾µÄдÈë¾ùÐèË¢ÅÌÒÔ±£Ö¤å´»úʱÊý¾Ý²»¶ªÊ§¡£
ÏÂÃæÍ¨¹ýÒ»¸öÀý×Ó½éÉÜÈÕ־ͬ²½»ù±¾Á÷³Ì£º
1£©³õʼ״̬ËùÓнڵãµÄTerm=2£¬CommitIndex=2£¬½Ó×ÅLeaderÊÕµ½Ò»Ìõy¡û9µÄÇëÇó£¬×ªÎªEntryдÈëÈÕÖ¾µÄĩ⣬EntryµÄindex
=3 term =1¡£
2£©Leaderͨ¹ýAppendEntry RPCͬ²½¸ÃEntry¸ø2¸öFollower£¬RPCÖаüº¬Ç°Ò»ÌõEntryÐÅÏ¢£¨index=2
term =1£©£¬FollowerÊÕµ½ºóÊ×ÏÈУÑéǰһÌõEntryÊÇ·ñÓë×ÔÉíÆ¥Å䣨ÕâÀïÆ¥Åä³É¹¦£©£¬Ö®ºóдÈë¸ÃEntry£¬·µ»ØLeader³É¹¦¡£
3£©LeaderÔÚÊÕµ½FollowerµÄ»Ø°üºó£¬¸üÐÂÏàÓ¦½ÚµãµÄNextIndexºÍMatchIndex£¬Õâʱ´ó¶àÊý½ÚµãMatchIndexÒѾ´óÓÚCommitIndex£¬ËùÒÔLeader¸üÐÂCommitIndex=3¡£
4£©Leader¼ÌÐø·¢ËÍAppendEntryµ½Follower£¬´ËʱÓÉÓÚûÓÐÐÂEntry£¬ËùÒÔRPCÖÐentryÐÅϢΪ¿Õ£¬LeaderCommitIndexΪ3¡£FollowerÊÕµ½ºó¸üÐÂCommitIndex=3
(Min£¨3,3£©)¡£
ÈÕÖ¾³åÍ»£º
ÔÚÈÕ־ͬ²½µÄ¹ý³ÌÖУ¬¿ÉÄÜ»á³öÏÖ½ÚµãÖ®¼äÈÕÖ¾²»Ò»ÖµÄÎÊÌâ¡£ÀýÈçFollowerдÈÕÖ¾¹ýÂý¡¢LeaderÇл»µ¼Ö¾ÉLeaderÉÏδÌá½»µÄÔàÊý¾ÝµÈ³¡¾°Ï¶¼»á·¢Éú¡£ÔÚRaftËã·¨ÖУ¬ÈÕÖ¾³åͻʱÒÔLeaderµÄÈÕ־Ϊ׼£¬Followerɾ³ý²»Æ¥Å䲿·Ö¡£
ÈçÏÂͼËùʾ£¬Follower½ÚµãÓëLeader½ÚµãµÄÈÕÖ¾¶¼´æÔÚ²»Ò»ÖÂÎÊÌ⣬ÆäÖÐ(a)¡¢(b)½ÚµãÈÕÖ¾²»È«£¬(c)¡¢(d)¡¢(e)¡¢(f)ÓгåÍ»ÈÕÖ¾¡£LeaderÊ×ÏÈ´Óindex=11(×îºóÒ»ÌõEntry
index +1)¿ªÊ¼·¢ËÍAppendEntry RPC,Follower¾ù·µ»Ø²»Æ¥Å䣬LeaderÊÕµ½ºó²»¶Ï»ØÍË¡£(a)¡¢(b)ÔÚÕÒµ½µÚÒ»ÌõÆ¥ÅäµÄÈÕÖ¾ºóÕý³£Í¬²½£¬(c)¡¢(d)¡¢(e)¡¢(f)ÔÚÕâ¸ö¹ý³ÌÖлáÖð²½É¾³ý²»Ò»ÖµÄÈÕÖ¾£¬×îÖÕËùÓнڵãµÄÈÕÖ¾¶¼ÓëLeaderÒ»Ö¡£³ÉΪLeader½Úµãºó²»»áÐ޸ĺÍɾ³ýÒÑ´æÔÚµÄÈÕÖ¾£¬Ö»»á×·¼ÓеÄÈÕÖ¾¡£
2.4 Ëã·¨Ö¤Ã÷
RaftËã·¨µÄ2¸öºËÐÄÊôÐÔ£º
1£©ÒÑÌá½»µÄÈÕÖ¾²»»áÔÙÐ޸ģ»(¿É¿¿ÐÔ)
2£©ËùÓнڵãÉϵÄÊý¾ÝÒ»Ö¡££¨Ò»ÖÂÐÔ£©
¾ßÌåÖ¤Ã÷ÈçÏ£º
1£©Leader Completeness£º¸ø¶¨TermÉÏÌá½»µÄÈÕÖ¾Ò»¶¨´æÔÚÓÚºóÐø¸ü¸ßTermµÄ LeaderÉÏ¡££¨ÈÕÖ¾²»¶ªÊ§£©
Ñ¡¾Ù³öµÄLeaderÒ»¶¨°üº¬µ±Ç°ÒÑÌá½»ËùÓÐÈÕÖ¾£ºÒÑÌá½»µÄÈÕÖ¾´æÔÚÓÚ´ó¶àÊý½ÚµãÉÏ£¬¶øÍ¬ÒâÑ¡¾ÙµÄǰÌáÊǺòÑ¡ÕßµÄÈÕÖ¾±ØÐ빻ȫ»ò¸üС£Ò»¸ö²»°üº¬ÒÑÌá½»ÈÕÖ¾µÄ½Úµã±ØÈ»²»»áµÃµ½´ó¶àÊý½ÚµãµÄѡƱ(ÕâЩ½ÚµãÉ϶¼ÓÐÒÑÌá½»µÄÈÕÖ¾£¬²»Âú×ãÈÕÖ¾×㹻ȫµÄǰÌá)£¬Ò²¾ÍÎÞ·¨³ÉΪLeader¡£
Leader½Úµã²»Ð޸ĺÍɾ³ýÒÑ´æÔÚÈÕÖ¾(Ëã·¨µÄÔ¼Êø)¡£
×ÛÉÏËùÊö£¬Ñ¡¾ÙºÍÈÕ־ͬ²½Ê±¶¼²»»áÆÆ»µÒÑÌá½»µÄÈÕÖ¾£¬µÃÖ¤¡£
2£©State Machine Safety£ºËùÓнڵãµÄÊý¾Ý×îÖÕÒ»Ö¡£
¸ù¾ÝLeader Completeness¿ÉÖªÒÑÌá½»µÄÈÕÖ¾²»»áÔÙÐ޸ģ¬ÒµÎñµÄ״̬»úÒÀ´ÎÈ¡³öEntryÖеÄuser_dataÓ¦Óã¬×îÖÕËùÓнڵãµÄÊý¾ÝÒ»Ö¡£
2.5¼¯Èº¹ÜÀí
RaftËã·¨Öгä·Ö¿¼ÂÇÁ˹¤³Ì»¯Öм¯Èº¹ÜÀíÎÊÌ⣬֧³Ö¶¯Ì¬µÄÌí¼Ó½Úµãµ½¼¯Èº£¬ÌÞ³ý¹ÊÕϽڵãµÈ¡£ÏÂÃæÏêϸÃèÊöÌí¼ÓºÍɾ³ý½ÚµãÁ÷³Ì¡£
Ìí¼Ó½Úµã
ÈçÏÂͼËùʾ£¬¼¯ÈºÖаüº¬A B C£¬AΪLeader£¬ÏÖÔÚÌí¼Ó½ÚµãD¡£
1£©Çå¿ÕD½ÚµãÉϵÄËùÓÐÊý¾Ý£¬±ÜÃâÓÐÔàÊý¾Ý¡£
2£©Leader½«´æÁ¿µÄÈÕ־ͨ¹ýAppendEntry RPCͬ²½µ½D£¬Ê¹DµÄÊý¾Ý¸úÉÏÆäËû½Úµã¡£
3£©´ýDµÄÈÕÖ¾×·ÉϺó£¬Leader A´´½¨Ò»ÌõConfig Entry£¬ÆäÖм¯ÈºÐÅÏ¢°üº¬ABCD¡£
4£©Leader A½«Config Entryͬ²½¸øB C D£¬FollowerÊÕµ½ºóÓ¦Óã¬Ö®ºóËùÓнڵãµÄ¼¯ÈºÐÅÏ¢¶¼±äΪABCD£¬Ìí¼ÓÍê³É¡£
×¢£ºÔÚ²½Öè2¹ý³ÌÖÐ,LeaderÈÔÔÚ²»¶Ï½ÓÊÕ¿Í»§ÇëÇóÉú³ÉEntry£¬ËùÒÔÖ»ÒªDÓëAÈÕÖ¾Ïà²î²»´ó¼´ÈÏΪDÒÑ×·ÉÏ¡£
ɾ³ý½Úµã
ÈçÏÂͼËùʾ£¬¼¯ÈºÖÐÔÀ´°üº¬A B C D£¬AΪLeader£¬ÏÖÔÚÌÞ³ý½ÚµãD¡£
1) Leader A´´½¨Ò»ÌõConfig Entry£¬ÆäÖм¯ÈºÐÅϢΪABC¡£
2) A½«ÈÕ־ͨ¹ýAppendEntry RPCͬ²½¸ø½ÚµãB C¡£
3) A B CÔÚÓ¦ÓøÃÈÕÖ¾ºó¼¯ÈºÐÅÏ¢±äΪABC£¬A²»ÔÙ·¢ËÍAppendEntry¸øD£¬D´Ó¼¯ÈºÖÐÒÆ³ý¡£
4) ´ËʱDµÄ¼¯ÈºÐÅÏ¢ÒÀ¾ÉΪABCD£¬ÔÚÑ¡¾Ù³¬Ê±µ½ÆÚºó£¬·¢ÆðÑ¡¾Ù£¬ÎªÁË·ÀÖ¹DµÄ¸ÉÈÅ£¬ÒýÈë¶îÍâ»úÖÆ£ºËùÓнڵãÔÚÕý³£½ÓÊÕLeaderµÄAppendEntryʱ£¬¾Ü¾øÆäËû½Úµã·¢À´µÄÑ¡¾ÙÇëÇó¡£
5) ½«DµÄÊý¾ÝÇå¿Õ²¢ÏÂÏß¡£
2.6 RaftÓ¦ÓÃ
ÎÒÃÇÓÃState Matchineͳһ±íʾҵÎñÄ£¿é£¬Æäͨ¹ýApplyIndexά»¤ÒÑÓ¦Óõ½µÄÈÕÖ¾index¡£ÒÔÏÂΪRaftÓë״̬»ú½»»¥µÄÁ÷³Ì£º
1£©¿Í»§¶ËÇëÇó·¢ÍùLeader½Úµã¡£
2£©Leader½ÚµãµÄRaftÄ£¿é½«ÇëÇóתΪEntry²¢Í¬²½µ½Followers¡£
3£©´ó¶àÊý½ÚµãдÈë³É¹¦ºóRaftÄ£¿é¸üÐÂCommitIndex¡£
4£©¸÷½ÚµãµÄState Machine˳Ðò¶ÁÈ¡ApplyIndex+1µ½CimmitIndexÖ®¼äµÄEntry£¬È¡³öÆäÖеÄuser_data²¢Ó¦Óã¬Íê³Éºó¸üÐÂApplyIndex¡£
5£©Leader ÉϵÄState Machine֪ͨ¿Í»§¶Ë²Ù×÷³É¹¦¡£
6£©Èç´ËÑ»·¡£
2.7 ¿ìÕÕ¹ÜÀí
ÔÚ½ÚµãÖØÆôʱ£¬ÓÉÓÚÎÞ·¨µÃÖªState Matchineµ±Ç°ApplyIndex(³ý·Çÿ´ÎÓ¦ÓÃÍêÈÕÖ¾¶¼³Ö¾Ã»¯ApplyIndex£¬»¹Òª±£Ö¤ÊÇÔ×Ó²Ù×÷£¬´ú¼Û½Ï´ó)£¬ËùÒÔ±ØÐëÇå¿ÕState
MatchineµÄÊý¾Ý£¬½«ApplyIndexÖÃΪ0,£¬´ÓÍ·¿ªÊ¼Ó¦ÓÃÈÕÖ¾£¬´ú¼ÛÌ«´ó£¬¿ÉÒÔͨ¹ý¶¨ÆÚ´´½¨¿ìÕյķ½Ê½½â¾ö¸ÃÎÊÌâ¡£ÈçÏÂͼËùʾ£º
1£© ÔÚÓ¦ÓÃÍêEntry 5 ºó£¬½«µ±Ç°State MatchineµÄÊý¾ÝÁ¬Í¬EntryÐÅϢдÈë¿ìÕÕÎļþ¡£
2£© Èç¹û½ÚµãÖØÆô£¬Ê×ÏÈ´Ó¿ìÕÕÎļþÖлָ´State Matchine£¬µÈ¼ÛÓÚÓ¦ÓÃÁ˽ØÖ¹µ½Entry
5ΪֹµÄËùÓÐEntry£¬µ«Ð§ÂÊÃ÷ÏÔÌá¸ß¡£
3£© ½«ApplyIndexÖÃΪ5£¬Ö®ºó´ÓEntry 6¼ÌÐøÓ¦ÓÃÈÕÖ¾£¬Êý¾ÝºÍÖØÆôǰһÖ¡£
¿ìÕÕµÄÓŵ㣺
½µµÍÖØÆôºÄʱ£ºÍ¨¹ýsnapshot +¡¡raft log»Ö¸´£¬ÎÞÐè´ÓµÚÒ»ÌõEntry¿ªÊ¼¡£
½ÚÊ¡¿Õ¼ä£º¿ìÕÕ×öÍêºó¼´¿Éɾ³ý¿ìÕÕµã֮ǰµÄRaftÈÕÖ¾¡£
2.8 Òì³£³¡¾°¼°´¦Àí
Raft¾ßÓкÜÇ¿µÄÈÝ´íÐÔ£¬Ö»Òª´ó¶àÊý½ÚµãÕý³£»¥Áª£¬¼´¿É±£Ö¤ÏµÍ³µÄÒ»ÖÂÐԺͿÉÓÃÐÔ£¬ÏÂÃæÊÇһЩ³£¼ûµÄÒì³£Çé¿ö£¬ÒÔ¼°ËûÃǵÄÓ°Ïì¼°´¦Àí£º
Òì³£³¡¾° Ó°Ïì¼°´¦Àí
Leader¹ÊÕÏ ¶ÌÔݲ»¿É·þÎñ£¬×Ô¶¯Ñ¡¾Ù£¬¿Í»§¶ËÐëÖØÊÔ
Follower»òCandidate¹ÊÕÏ ÎÞÓ°Ïì
ÍøÂç·ÖÇø ´ó¶àÊý»¥ÁªÊ±×Ô¶¯Ñ¡¾Ù£¬Î±Leader
½ÚµãÖØÆô ¿ìÕÕ+raftÈÕÖ¾×Ô¶¯»Ö¸´
´ó¶àÊý½Úµã¹ÊÕÏ ²»¿ÉÓ㨱£Ö¤Ç¿Ò»ÖÂÐÔ£©
Ñ¡¾Ù³åÍ» ÔÝʱ²»¿É·þÎñ£¨Ëæ»úÑ¡¾Ùʱ¼ä±£Ö¤¼«ÉÙ³öÏָó¡¾°£©
¿ÉÒÔ¿´µ½Òì³£Çé¿ö¶ÔϵͳµÄÓ°ÏìºÜС£¬¼´Ê¹ÊÇLeader¹ÊÕÏÒ²¿ÉÒÔÔÚ¼«¶ÌµÄʱ¼äÄÚ»Ö¸´£¬ÈκÎÇé¿öÏÂϵͳ¶¼Ò»Ö±±£³ÖǿһÖÂÐÔ£¬Îª´ËÎþÉüÁ˲¿·Ö¿ÉÓÃÐÔ£¨´ó¶àÊý½Úµã¹ÊÕÏʱ£¬¸ÅÂʼ«µÍ£©¡£²»¹ý£¬Leader¹ÊÕÏʱеÄLeader¿ÉÄÜ»á°üº¬¾ÉLeaderδÌá½»»òÒÑÌá½»µ«ÉÐδ֪ͨ¿Í»§¶ËµÄÈÕÖ¾£¬ÓÉÓÚËã·¨¹æ¶¨³ÉΪLeaderºó²»ÔÊÐíɾ³ýÈÕÖ¾£¬ËùÒÔÕⲿ·ÖÈÕÖ¾»á±»ÐÂLeaderͬ²½²¢Ìá½»£¬µ«ÓÉÓÚÁ¬½ÓÐÅÏ¢¶ªÊ§£¬¿Í»§¶ËÎÞ·¨µÃÖª¸ÃÇé¿ö£¬µ±·¢ÆðÖØÊÔºó»á³öÏÖÖØ¸´Êý¾Ý£¬ÐèÒªÓÐÃݵÈÐÔ±£Ö¤¡£´ËÍ⣬raftµÄºËÐÄËã·¨¶¼ÊÇÎ§ÈÆLeaderÕ¹¿ª£¬ÍøÂç·ÖÇøÊ±¿ÉÄܳöÏÖαLeaderÎÊÌ⣬ҲÐèÒªÌØÊ⿼ÂÇ¡£
ÒÔÏÂÊÇÍøÂç·ÖÇøÊ±²úÉúαLeader µÄ¹ý³Ì£º
ÉÏÊöÇé¿öÏ£¬LeaderÓë2¸öFollowerÍøÂçÒì³££¬¶ø2¸öFollowerÖ®¼äͨÐÅÕý³££¬ÓÉÓÚÊÕ²»µ½LeaderµÄÐÄÌø£¬ÆäÖÐÒ»¸öFollower·¢ÆðÑ¡¾Ù²¢³ÉΪLeader£¬ÔLeader³ÉΪαLeader£¬½ÓÏÂÀ´ÎÒÃÇ·ÖÎö¸Ã³¡¾°ÏÂÊÇ·ñ»áÓ°ÏìϵͳµÄÒ»ÖÂÐÔ£º
дһÖÂÐÔ£º·¢ÍùÐÂLeaderµÄдÇëÇó¿ÉÒÔ±»Ìá½»£¬¶ø·¢ÍùαLeaderµÄÇëÇóÎÞ·¨µÃµ½Ìá½»£¬Ö»ÓÐÒ»¸öLeaderÔÚÕý³£´¦ÀíдÇëÇó£¬ËùÒÔ²»Ó°ÏìдһÖÂÐÔ¡£
¶ÁÒ»ÖÂÐÔ£ºÈç¹û¶ÁÇëÇó²»¾¹ýRaftͬ²½£¬ÄÇôµ±¿Í»§¶ËµÄдÇëÇó±»·¢ÍùÐÂLeader²¢Ö´Ðгɹ¦ºó£¬¶ÁÇëÇó·¢ÍùÁËαLeader²¢µÃµ½½á¹û£¬¾Í»áÔì³ÉÊý¾Ý²»Ò»Ö¡£ÓÐÁ½ÖÖ·½°¸¿ÉÒÔ½â¾ö¸ÃÎÊÌ⣺
¶ÁÇëÇóÒ²¾¹ýRaftͬ²½£¬ÕâÑù¾Í²»»áÓв»Ò»ÖµÄÎÊÌ⣬µ«»áÔö¼Óϵͳ¸ºÔØ¡£
¶ÁÇëÇóÊÕµ½ºó£¬Leader½ÚµãµÈ´ý´ó¶àÊý½ÚµãÔÙ´ÎÏìÓ¦ÐÄÌøRPC£¬½Ó×Å·µ»Ø½á¹û¡£
ÒòΪ´ó¶àÊý½ÚµãÏìÓ¦ÐÄÌø£¬ËµÃ÷µ±Ç°Ò»¶¨Ã»ÓÐÁíÒ»¸öLeader´æÔÚ£¨´ó¶àÊý½Úµã»¹Ó뵱ǰLeaderά³Ö×âÔ¼£¬ÐÂLeaderÐèÒªµÃµ½´ó¶àÊýͶƱ£©¡£
2.9 С½á
RaftËã·¨¾ß±¸Ç¿Ò»Ö¡¢¸ß¿É¿¿¡¢¸ß¿ÉÓõÈÓŵ㣬¾ßÌåÌåÏÖÔÚ£º
ǿһÖÂÐÔ£ºËäÈ»ËùÓнڵãµÄÊý¾Ý²¢·ÇʵʱһÖ£¬µ«RaftËã·¨±£Ö¤Leader½ÚµãµÄÊý¾Ý×îÈ«£¬Í¬Ê±ËùÓÐÇëÇó¶¼ÓÉLeader´¦Àí£¬ËùÒÔÔÚ¿Í»§¶Ë½Ç¶È¿´ÊÇǿһÖÂÐԵġ£
¸ß¿É¿¿ÐÔ£ºRaftËã·¨±£Ö¤ÁËCommittedµÄÈÕÖ¾²»»á±»Ð޸ģ¬State MatchineÖ»Ó¦ÓÃCommittedµÄÈÕÖ¾£¬ËùÒÔµ±¿Í»§¶ËÊÕµ½ÇëÇó³É¹¦¼´´ú±íÊý¾Ý²»Ôٸı䡣CommittedÈÕÖ¾ÔÚ´ó¶àÊý½ÚµãÉÏÈßÓà´æ´¢£¬ÉÙÓÚÒ»°ëµÄ´ÅÅ̹ÊÕÏÊý¾Ý²»»á¶ªÊ§¡£
¸ß¿ÉÓÃÐÔ£º´ÓRaftËã·¨ÔÀí¿ÉÒÔ¿´³ö£¬Ñ¡¾ÙºÍÈÕ־ͬ²½¶¼Ö»ÐèÒª´ó¶àÊýµÄ½ÚµãÕý³£»¥Áª¼´¿É£¬ËùÒÔÉÙÁ¿½Úµã¹ÊÕÏ»òÍøÂçÒì³£²»»áÓ°ÏìϵͳµÄ¿ÉÓÃÐÔ¡£¼´Ê¹Leader¹ÊÕÏ£¬ÔÚÑ¡¾Ù³¬Ê±µ½ÆÚºó£¬¼¯Èº×Ô·¢Ñ¡¾ÙÐÂLeader£¬ÎÞÐèÈ˹¤¸ÉÔ¤£¬²»¿ÉÓÃʱ¼ä¼«Ð¡¡£µ«Leader¹ÊÕÏʱ´æÔÚÖØ¸´Êý¾ÝÎÊÌ⣬ÐèÒªÒµÎñÈ¥ÖØ»òÃݵÈÐÔ±£Ö¤¡£
¸ßÐÔÄÜ£ºÓë±ØÐ뽫Êý¾Ýдµ½ËùÓнڵã²ÅÄÜ·µ»Ø¿Í»§¶Ë³É¹¦µÄËã·¨Ïà±È£¬RaftËã·¨Ö»ÐèÒª´ó¶àÊý½Úµã³É¹¦¼´¿É£¬ÉÙÁ¿½Úµã´¦Àí»ºÂý²»»áÑÓ»ºÕûÌåϵͳÔËÐС£
|