-
Notifications
You must be signed in to change notification settings - Fork 683
/
Copy path分布式一致性算法 Raft.md.html
1282 lines (650 loc) · 43.9 KB
/
分布式一致性算法 Raft.md.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<!-- saved from url=(0046)https://kaiiiz.github.io/hexo-theme-book-demo/ -->
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1.0, user-scalable=no">
<link rel="icon" href="/static/favicon.png">
<title>分布式一致性算法 Raft.md.html</title>
<!-- Spectre.css framework -->
<link rel="stylesheet" href="/static/index.css">
<!-- theme css & js -->
<meta name="generator" content="Hexo 4.2.0">
</head>
<body>
<div class="book-container">
<div class="book-sidebar">
<div class="book-brand">
<a href="/">
<img src="/static/favicon.png">
<span>技术文章摘抄</span>
</a>
</div>
<div class="book-menu uncollapsible">
<ul class="uncollapsible">
<li><a href="/" class="current-tab">首页</a></li>
</ul>
<ul class="uncollapsible">
<li><a href="../">上一级</a></li>
</ul>
<ul class="uncollapsible">
<li>
<a href="/文章/AQS 万字图文全面解析.md.html">AQS 万字图文全面解析.md.html</a>
</li>
<li>
<a href="/文章/Docker 镜像构建原理及源码分析.md.html">Docker 镜像构建原理及源码分析.md.html</a>
</li>
<li>
<a href="/文章/ElasticSearch 小白从入门到精通.md.html">ElasticSearch 小白从入门到精通.md.html</a>
</li>
<li>
<a href="/文章/JVM CPU Profiler技术原理及源码深度解析.md.html">JVM CPU Profiler技术原理及源码深度解析.md.html</a>
</li>
<li>
<a href="/文章/JVM 垃圾收集器.md.html">JVM 垃圾收集器.md.html</a>
</li>
<li>
<a href="/文章/JVM 面试的 30 个知识点.md.html">JVM 面试的 30 个知识点.md.html</a>
</li>
<li>
<a href="/文章/Java IO 体系、线程模型大总结.md.html">Java IO 体系、线程模型大总结.md.html</a>
</li>
<li>
<a href="/文章/Java NIO浅析.md.html">Java NIO浅析.md.html</a>
</li>
<li>
<a href="/文章/Java 面试题集锦（网络篇）.md.html">Java 面试题集锦（网络篇）.md.html</a>
</li>
<li>
<a href="/文章/Java-直接内存 DirectMemory 详解.md.html">Java-直接内存 DirectMemory 详解.md.html</a>
</li>
<li>
<a href="/文章/Java中9种常见的CMS GC问题分析与解决（上）.md.html">Java中9种常见的CMS GC问题分析与解决（上）.md.html</a>
</li>
<li>
<a href="/文章/Java中9种常见的CMS GC问题分析与解决（下）.md.html">Java中9种常见的CMS GC问题分析与解决（下）.md.html</a>
</li>
<li>
<a href="/文章/Java中的SPI.md.html">Java中的SPI.md.html</a>
</li>
<li>
<a href="/文章/Java中的ThreadLocal.md.html">Java中的ThreadLocal.md.html</a>
</li>
<li>
<a href="/文章/Java线程池实现原理及其在美团业务中的实践.md.html">Java线程池实现原理及其在美团业务中的实践.md.html</a>
</li>
<li>
<a href="/文章/Java魔法类：Unsafe应用解析.md.html">Java魔法类：Unsafe应用解析.md.html</a>
</li>
<li>
<a href="/文章/Kafka 源码阅读笔记.md.html">Kafka 源码阅读笔记.md.html</a>
</li>
<li>
<a href="/文章/Kafka、ActiveMQ、RabbitMQ、RocketMQ 区别以及高可用原理.md.html">Kafka、ActiveMQ、RabbitMQ、RocketMQ 区别以及高可用原理.md.html</a>
</li>
<li>
<a href="/文章/MySQL · 引擎特性 · InnoDB Buffer Pool.md.html">MySQL · 引擎特性 · InnoDB Buffer Pool.md.html</a>
</li>
<li>
<a href="/文章/MySQL · 引擎特性 · InnoDB IO子系统.md.html">MySQL · 引擎特性 · InnoDB IO子系统.md.html</a>
</li>
<li>
<a href="/文章/MySQL · 引擎特性 · InnoDB 事务系统.md.html">MySQL · 引擎特性 · InnoDB 事务系统.md.html</a>
</li>
<li>
<a href="/文章/MySQL · 引擎特性 · InnoDB 同步机制.md.html">MySQL · 引擎特性 · InnoDB 同步机制.md.html</a>
</li>
<li>
<a href="/文章/MySQL · 引擎特性 · InnoDB 数据页解析.md.html">MySQL · 引擎特性 · InnoDB 数据页解析.md.html</a>
</li>
<li>
<a href="/文章/MySQL · 引擎特性 · InnoDB崩溃恢复.md.html">MySQL · 引擎特性 · InnoDB崩溃恢复.md.html</a>
</li>
<li>
<a href="/文章/MySQL · 引擎特性 · 临时表那些事儿.md.html">MySQL · 引擎特性 · 临时表那些事儿.md.html</a>
</li>
<li>
<a href="/文章/MySQL 主从复制 半同步复制.md.html">MySQL 主从复制 半同步复制.md.html</a>
</li>
<li>
<a href="/文章/MySQL 主从复制 基于GTID复制.md.html">MySQL 主从复制 基于GTID复制.md.html</a>
</li>
<li>
<a href="/文章/MySQL 主从复制.md.html">MySQL 主从复制.md.html</a>
</li>
<li>
<a href="/文章/MySQL 事务日志(redo log和undo log).md.html">MySQL 事务日志(redo log和undo log).md.html</a>
</li>
<li>
<a href="/文章/MySQL 亿级别数据迁移实战代码分享.md.html">MySQL 亿级别数据迁移实战代码分享.md.html</a>
</li>
<li>
<a href="/文章/MySQL 从一条数据说起-InnoDB行存储数据结构.md.html">MySQL 从一条数据说起-InnoDB行存储数据结构.md.html</a>
</li>
<li>
<a href="/文章/MySQL 地基基础：事务和锁的面纱.md.html">MySQL 地基基础：事务和锁的面纱.md.html</a>
</li>
<li>
<a href="/文章/MySQL 地基基础：数据字典.md.html">MySQL 地基基础：数据字典.md.html</a>
</li>
<li>
<a href="/文章/MySQL 地基基础：数据库字符集.md.html">MySQL 地基基础：数据库字符集.md.html</a>
</li>
<li>
<a href="/文章/MySQL 性能优化：碎片整理.md.html">MySQL 性能优化：碎片整理.md.html</a>
</li>
<li>
<a href="/文章/MySQL 故障诊断：一个 ALTER TALBE 执行了很久，你慌不慌？.md.html">MySQL 故障诊断：一个 ALTER TALBE 执行了很久，你慌不慌？.md.html</a>
</li>
<li>
<a href="/文章/MySQL 故障诊断：如何在日志中轻松定位大事务.md.html">MySQL 故障诊断：如何在日志中轻松定位大事务.md.html</a>
</li>
<li>
<a href="/文章/MySQL 故障诊断：教你快速定位加锁的 SQL.md.html">MySQL 故障诊断：教你快速定位加锁的 SQL.md.html</a>
</li>
<li>
<a href="/文章/MySQL 日志详解.md.html">MySQL 日志详解.md.html</a>
</li>
<li>
<a href="/文章/MySQL 的半同步是什么？.md.html">MySQL 的半同步是什么？.md.html</a>
</li>
<li>
<a href="/文章/MySQL中的事务和MVCC.md.html">MySQL中的事务和MVCC.md.html</a>
</li>
<li>
<a href="/文章/MySQL事务_事务隔离级别详解.md.html">MySQL事务_事务隔离级别详解.md.html</a>
</li>
<li>
<a href="/文章/MySQL优化：优化 select count().md.html">MySQL优化：优化 select count().md.html</a>
</li>
<li>
<a href="/文章/MySQL共享锁、排他锁、悲观锁、乐观锁.md.html">MySQL共享锁、排他锁、悲观锁、乐观锁.md.html</a>
</li>
<li>
<a href="/文章/MySQL的MVCC（多版本并发控制）.md.html">MySQL的MVCC（多版本并发控制）.md.html</a>
</li>
<li>
<a href="/文章/QingStor 对象存储架构设计及最佳实践.md.html">QingStor 对象存储架构设计及最佳实践.md.html</a>
</li>
<li>
<a href="/文章/RocketMQ 面试题集锦.md.html">RocketMQ 面试题集锦.md.html</a>
</li>
<li>
<a href="/文章/SnowFlake 雪花算法生成分布式 ID.md.html">SnowFlake 雪花算法生成分布式 ID.md.html</a>
</li>
<li>
<a href="/文章/Spring Boot 2.x 结合 k8s 实现分布式微服务架构.md.html">Spring Boot 2.x 结合 k8s 实现分布式微服务架构.md.html</a>
</li>
<li>
<a href="/文章/Spring Boot 教程：如何开发一个 starter.md.html">Spring Boot 教程：如何开发一个 starter.md.html</a>
</li>
<li>
<a href="/文章/Spring MVC 原理.md.html">Spring MVC 原理.md.html</a>
</li>
<li>
<a href="/文章/Spring MyBatis和Spring整合的奥秘.md.html">Spring MyBatis和Spring整合的奥秘.md.html</a>
</li>
<li>
<a href="/文章/Spring 帮助你更好的理解Spring循环依赖.md.html">Spring 帮助你更好的理解Spring循环依赖.md.html</a>
</li>
<li>
<a href="/文章/Spring 循环依赖及解决方式.md.html">Spring 循环依赖及解决方式.md.html</a>
</li>
<li>
<a href="/文章/Spring中眼花缭乱的BeanDefinition.md.html">Spring中眼花缭乱的BeanDefinition.md.html</a>
</li>
<li>
<a href="/文章/Vert.x 基础入门.md.html">Vert.x 基础入门.md.html</a>
</li>
<li>
<a href="/文章/eBay 的 Elasticsearch 性能调优实践.md.html">eBay 的 Elasticsearch 性能调优实践.md.html</a>
</li>
<li>
<a href="/文章/不可不说的Java“锁”事.md.html">不可不说的Java“锁”事.md.html</a>
</li>
<li>
<a href="/文章/互联网并发限流实战.md.html">互联网并发限流实战.md.html</a>
</li>
<li>
<a href="/文章/从ReentrantLock的实现看AQS的原理及应用.md.html">从ReentrantLock的实现看AQS的原理及应用.md.html</a>
</li>
<li>
<a href="/文章/从SpringCloud开始，聊微服务架构.md.html">从SpringCloud开始，聊微服务架构.md.html</a>
</li>
<li>
<a href="/文章/全面了解 JDK 线程池实现原理.md.html">全面了解 JDK 线程池实现原理.md.html</a>
</li>
<li>
<a href="/文章/分布式一致性理论与算法.md.html">分布式一致性理论与算法.md.html</a>
</li>
<li>
<a class="current-tab" href="/文章/分布式一致性算法 Raft.md.html">分布式一致性算法 Raft.md.html</a>
</li>
<li>
<a href="/文章/分布式唯一 ID 解析.md.html">分布式唯一 ID 解析.md.html</a>
</li>
<li>
<a href="/文章/分布式链路追踪：集群管理设计.md.html">分布式链路追踪：集群管理设计.md.html</a>
</li>
<li>
<a href="/文章/动态代理种类及原理，你知道多少？.md.html">动态代理种类及原理，你知道多少？.md.html</a>
</li>
<li>
<a href="/文章/响应式架构与 RxJava 在有赞零售的实践.md.html">响应式架构与 RxJava 在有赞零售的实践.md.html</a>
</li>
<li>
<a href="/文章/大数据算法——布隆过滤器.md.html">大数据算法——布隆过滤器.md.html</a>
</li>
<li>
<a href="/文章/如何优雅地记录操作日志？.md.html">如何优雅地记录操作日志？.md.html</a>
</li>
<li>
<a href="/文章/如何设计一个亿级消息量的 IM 系统.md.html">如何设计一个亿级消息量的 IM 系统.md.html</a>
</li>
<li>
<a href="/文章/异步网络模型.md.html">异步网络模型.md.html</a>
</li>
<li>
<a href="/文章/当我们在讨论CQRS时，我们在讨论些神马？.md.html">当我们在讨论CQRS时，我们在讨论些神马？.md.html</a>
</li>
<li>
<a href="/文章/彻底理解 MySQL 的索引机制.md.html">彻底理解 MySQL 的索引机制.md.html</a>
</li>
<li>
<a href="/文章/最全的 116 道 Redis 面试题解答.md.html">最全的 116 道 Redis 面试题解答.md.html</a>
</li>
<li>
<a href="/文章/有赞权限系统(SAM).md.html">有赞权限系统(SAM).md.html</a>
</li>
<li>
<a href="/文章/有赞零售中台建设方法的探索与实践.md.html">有赞零售中台建设方法的探索与实践.md.html</a>
</li>
<li>
<a href="/文章/服务注册与发现原理剖析（Eureka、Zookeeper、Nacos）.md.html">服务注册与发现原理剖析（Eureka、Zookeeper、Nacos）.md.html</a>
</li>
<li>
<a href="/文章/深入浅出Cache.md.html">深入浅出Cache.md.html</a>
</li>
<li>
<a href="/文章/深入理解 MySQL 底层实现.md.html">深入理解 MySQL 底层实现.md.html</a>
</li>
<li>
<a href="/文章/漫画讲解 git rebase VS git merge.md.html">漫画讲解 git rebase VS git merge.md.html</a>
</li>
<li>
<a href="/文章/生成浏览器唯一稳定 ID 的探索.md.html">生成浏览器唯一稳定 ID 的探索.md.html</a>
</li>
<li>
<a href="/文章/缓存 如何保证缓存与数据库的双写一致性？.md.html">缓存 如何保证缓存与数据库的双写一致性？.md.html</a>
</li>
<li>
<a href="/文章/网易严选怎么做全链路监控的？.md.html">网易严选怎么做全链路监控的？.md.html</a>
</li>
<li>
<a href="/文章/美团万亿级 KV 存储架构与实践.md.html">美团万亿级 KV 存储架构与实践.md.html</a>
</li>
<li>
<a href="/文章/美团点评Kubernetes集群管理实践.md.html">美团点评Kubernetes集群管理实践.md.html</a>
</li>
<li>
<a href="/文章/美团百亿规模API网关服务Shepherd的设计与实现.md.html">美团百亿规模API网关服务Shepherd的设计与实现.md.html</a>
</li>
<li>
<a href="/文章/解读《阿里巴巴 Java 开发手册》背后的思考.md.html">解读《阿里巴巴 Java 开发手册》背后的思考.md.html</a>
</li>
<li>
<a href="/文章/认识 MySQL 和 Redis 的数据一致性问题.md.html">认识 MySQL 和 Redis 的数据一致性问题.md.html</a>
</li>
<li>
<a href="/文章/进阶：Dockerfile 高阶使用指南及镜像优化.md.html">进阶：Dockerfile 高阶使用指南及镜像优化.md.html</a>
</li>
<li>
<a href="/文章/铁总在用的高性能分布式缓存计算框架 Geode.md.html">铁总在用的高性能分布式缓存计算框架 Geode.md.html</a>
</li>
<li>
<a href="/文章/阿里云PolarDB及其共享存储PolarFS技术实现分析（上）.md.html">阿里云PolarDB及其共享存储PolarFS技术实现分析（上）.md.html</a>
</li>
<li>
<a href="/文章/阿里云PolarDB及其共享存储PolarFS技术实现分析（下）.md.html">阿里云PolarDB及其共享存储PolarFS技术实现分析（下）.md.html</a>
</li>
<li>
<a href="/文章/面试最常被问的 Java 后端题.md.html">面试最常被问的 Java 后端题.md.html</a>
</li>
<li>
<a href="/文章/领域驱动设计在互联网业务开发中的实践.md.html">领域驱动设计在互联网业务开发中的实践.md.html</a>
</li>
<li>
<a href="/文章/领域驱动设计的菱形对称架构.md.html">领域驱动设计的菱形对称架构.md.html</a>
</li>
<li>
<a href="/文章/高效构建 Docker 镜像的最佳实践.md.html">高效构建 Docker 镜像的最佳实践.md.html</a>
</li>
</ul>
</div>
</div>
<div class="sidebar-toggle" onclick="sidebar_toggle()" onmouseover="add_inner()" onmouseleave="remove_inner()">
<div class="sidebar-toggle-inner"></div>
</div>
<script>
function add_inner() {
let inner = document.querySelector('.sidebar-toggle-inner')
inner.classList.add('show')
}
function remove_inner() {
let inner = document.querySelector('.sidebar-toggle-inner')
inner.classList.remove('show')
}
function sidebar_toggle() {
let sidebar_toggle = document.querySelector('.sidebar-toggle')
let sidebar = document.querySelector('.book-sidebar')
let content = document.querySelector('.off-canvas-content')
if (sidebar_toggle.classList.contains('extend')) { // show
sidebar_toggle.classList.remove('extend')
sidebar.classList.remove('hide')
content.classList.remove('extend')
} else { // hide
sidebar_toggle.classList.add('extend')
sidebar.classList.add('hide')
content.classList.add('extend')
}
}
function open_sidebar() {
let sidebar = document.querySelector('.book-sidebar')
let overlay = document.querySelector('.off-canvas-overlay')
sidebar.classList.add('show')
overlay.classList.add('show')
}
function hide_canvas() {
let sidebar = document.querySelector('.book-sidebar')
let overlay = document.querySelector('.off-canvas-overlay')
sidebar.classList.remove('show')
overlay.classList.remove('show')
}
</script>
<div class="off-canvas-content">
<div class="columns">
<div class="column col-12 col-lg-12">
<div class="book-navbar">
<!-- For Responsive Layout -->
<header class="navbar">
<section class="navbar-section">
<a onclick="open_sidebar()">
<i class="icon icon-menu"></i>
</a>
</section>
</header>
</div>
<div class="book-content" style="max-width: 960px; margin: 0 auto;
overflow-x: auto;
overflow-y: hidden;">
<div class="book-post">
<p id="tip" align="center"></p>
<div><h1>分布式一致性算法 Raft</h1>
<h3><strong>一、Raft 算法背景</strong></h3>
<p>在学术理论界，分布式一致性算法的代表还是 Paxos，但是少数理解的人觉得很简单，尚未理解的觉得很难，大多数人还是一知半解。Paxos 的可理解性 & 工程落地性的门槛很高。斯坦福学者花了很多时间理解 Paxos，于是他们研究出来 Raft。本文主要是介绍 Raft 算法的基本原理。</p>
<h3><strong>二、Raft 算法基本原理</strong></h3>
<p>共识算法就是保证一个集群的多台机器协同工作，在遇到请求时，数据能够保持一致。即使遇到机器宕机，整个系<strong>统仍然能够对外保持</strong>服务的可用性。</p>
<p>Raft 将共识问题分解三个子问题：</p>
<ol>
<li><strong>Leader election 领导选举</strong>：有且仅有一个 leader 节点，如果 leader 宕机，通过选举机制选出新的 leader；</li>
<li><strong>Log replication 日志复制</strong>：leader 从客户端接收数据更新/删除请求，然后日志复制到 follower 节点，从而保证集群数据的一致性；</li>
<li><strong>Safety 安全性</strong>：通过安全性原则来处理一些特殊 case，保证 Raft 算法的完备性；</li>
</ol>
<p>所以，Raft 算法核心流程可以归纳为：</p>
<ul>
<li>首先选出 leader，leader 节点负责接收外部的数据更新/删除请求；</li>
<li>然后日志复制到其他 follower 节点，同时通过安全性的准则来保证整个日志复制的一致性；</li>
<li>如果遇到 leader 故障，followers 会重新发起选举出新的 leader；</li>
</ul>
<p>这里先介绍一下日志同步的概念：服务器接收客户的数据更新/删除请求，这些请求会落地为命令日志。只要输入状态机的日志命令相同，状态机的执行结果就相同。所以 Raft 的核心就是 leader 发出日志同步请求，follower 接收并同步日志，最终保证整个集群的日志一致性。</p>
<p><img src="assets/v2-02b6004fd2b7886d10ccd611b6d66d6c_1440w.jpg" alt="img" /></p>
<h3><strong>2.1 Leader Election 领导选举</strong></h3>
<p>集群中每个节点只能处于 Leader、Follower 和 Candidate 三种状态的一种:</p>
<ol>
<li><strong>follower 从节点</strong>：</li>
</ol>
<ul>
<li>节点默认是 follower；</li>
<li>如果**刚刚开始 ** 或 <strong>和 leader 通信超时</strong>，follower 会发起选举，变成 candidate，然后去竞选 leader；</li>
<li>如果收到其他 candidate 的竞选投票请求，按照<strong>先来先得</strong> & <strong>每个任期只能投票一次</strong> 的投票原则投票;</li>
</ul>
<ol>
<li><strong>candidate 候选者</strong>：</li>
</ol>
<ul>
<li>follower 发起选举后就变为 candidate，会向其他节点拉选票。candidate 的票会投给自己，所以不会向其他节点投票</li>
<li>如果获得超过<strong>半数</strong>的投票，candidate 变成 leader，然后马上和其他节点通信，表明自己的 leader 的地位；</li>
<li>如果选举超时，重新发起选举；</li>
<li>如果遇到更高任期 Term 的 leader 的通信请求，转化为 follower；</li>
</ul>
<ol>
<li><strong>leader 主节点</strong>：</li>
</ol>
<ul>
<li>成为 leader 节点后，此时可以接受客户端的数据请求，负责日志同步；</li>
<li>如果遇到更高任期 Term 的 candidate 的通信请求，这说明 candidate 正在竞选 leader，此时之前任期的 leader 转化为 follower，且完成投票；</li>
<li>如果遇到更高任期 Term 的 leader 的通信请求，这说明已经选举成功新的 leader，此时之前任期的 leader 转化为 follower；</li>
</ul>
<p>具体的节点状态转换参考下图：</p>
<p><img src="assets/v2-537082d871c75e59f6b7556b48cee932_1440w.jpg" alt="img" /></p>
<p>Raft 算法把时间轴划分为不同任期 Term。每个任期 Term 都有自己的编号 TermId，该编号全局唯一且单调递增。如下图，每个任务的开始都** Leader Election 领导选举**。如果选举成功，则进入维持任务 Term 阶段，此时 leader 负责接收客户端请求并，负责复制日志。Leader 和所有 follower 都保持通信，如果 follower 发现通信超时，TermId 递增并发起新的选举。如果选举成功，则进入新的任期。如果选举失败，TermId 递增，然后重新发起选举直到成功。</p>
<p>举个例子，参考下图，Term N 选举成功，Term N+1 和 Term N+2 选举失败，Term N+3 重新选举成功。</p>
<p><img src="assets/v2-4b0b8661f85d76f662d742ba5b2abcb9_1440w.jpg" alt="img" /></p>
<p>具体的说，Leader 在任期内会周期性向其他 follower 节点发送心跳来维持地位。follower 如果发现心跳超时，就认为 leader 节点宕机或不存在。随机等待一定时间后，follower 会发起选举，变成 candidate，然后去竞选 leader。选举结果有三种情况：</p>
<ol>
<li><strong>获取超过半数投票，赢得选举</strong>：</li>
</ol>
<ul>
<li>
<p>当 Candidate 获得超过半数的投票时，代表自己赢得了选举，且转化为 leader。此时，它会马上向其他节点发送请求，从而确认自己的 leader 地位，从而阻止新一轮的选举；</p>
</li>
<li>
<p><strong>投票原则</strong>：当多个 Candidate 竞选 Leader 时：</p>
</li>
<li>
<ul>
<li>一个任期内，follower 只会<strong>投票一次票</strong>，且投票<strong>先来显得</strong>；</li>
<li>Candidate 存储的日志至少要和 follower 一样新（<strong>安全性准则</strong>），否则拒绝投票；</li>
</ul>
</li>
</ul>
<ol>
<li><strong>投票未超过半数，选举失败</strong>：</li>
</ol>
<ul>
<li>当 Candidate 没有获得超过半数的投票时，说明多个 Candidate 竞争投票导致过于分散，或者出现了丢包现象。此时，认为当期任期选举失败，任期 TermId+1，然后发起新一轮选举；</li>
<li>上述机制可能出现多个 Candidate 竞争投票，导致每个 Candidate 一直得不到超过半数的票，最终导致无限选举投票循环；</li>
<li><strong>投票分散问题解决：</strong> Raft 会给每个 Candidate 在固定时间内随机确认一个超时时间（一般为 150-300ms）。这么做可以尽量避免新的一次选举出现多个 Candidate 竞争投票的现象；</li>
</ul>
<ol>
<li><strong>收到其他 Leader 通信请求</strong>：</li>
</ol>
<ul>
<li>如果 Candidate 收到其他声称自己是 Leader 的请求的时候，通过任期 TermId 来判断是否处理；</li>
<li>如果请求的任期 TermId 不小于 Candidate 当前任期 TermId，那么 Candidate 会承认该 Leader 的合法地位并转化为 Follower；</li>
<li>否则，拒绝这次请求，并继续保持 Candidate；</li>
</ul>
<p>简单的多，<strong>Leader Election 领导选举</strong> 通过若干的投票原则，保证一次选举有且仅可能最多选出一个 leader，从而解决了脑裂问题。</p>
<h3><strong>2.2 Log Replication 日志复制</strong></h3>
<p>选举 leader 成功后，整个集群就可以正常对外提供服务了。Leader 接收所有客户端请求，然后转化为 log 复制命令，发送通知其他节点完成日志复制请求。每个日志复制请求包括状态机命令 & 任期号，同时还有前一个日志的任期号和日志索引。状态机命令表示客户端请求的数据操作指令，任期号表示 leader 的当前任期。</p>
<p>follower 收到日志复制请求的处理流程：</p>
<ol>
<li>follower 会使用前一个日志的任期号和日志索引来对比自己的数据：</li>
</ol>
<ul>
<li>如果相同，接收复制请求，回复 ok；</li>
<li>否则回拒绝复制当前日志，回复 error；</li>
</ul>
<ol>
<li>leader 收到拒绝复制的回复后，继续发送节点日志复制请求，不过这次会带上更前面的一个日志任期号和索引；</li>
<li>如此循环往复，直到找到一个共同的任期号&日志索引。此时 follower 从这个索引值开始复制，最终和 leader 节点日志保持一致；</li>
<li>日志复制过程中，Leader 会无限重试直到成功。如果超过半数的节点复制日志成功，就可以任务当前数据请求达成了共识，即日志可以 commite 提交了；</li>
</ol>
<p>综上， <strong>Log Replication 日志复制</strong>有两个特点：</p>
<ol>
<li>如果在不同日志中的两个条目有着相同索引和任期号，则所存储的命令是相同的，这点是由 leader 来保证的；</li>
<li>如果在不同日志中的两个条目有着相同索引和任期号，则它们之间所有条目完全一样，这点是由日志复制的规则来保证的；</li>
</ol>
<p>举个例子，最上面表示日志索引，这个是保证唯一性。每个方块代表指定任期内的数据操作，目前来看，LogIndex 1-4 的日志已经完成同步，LogIndex 5 的正在同步，LogIndex6 还未开始同步。Raft 日志提交的过程有点类似两阶段原子提交协议 2PC，不过和 2PC 的最大区别是，Raft 要求超过一般节点同意即可 commited，2PC 要求所有节点同意才能 commited。</p>
<p><img src="assets/v2-2f3ad84935c439bf16b0018351162173_1440w.jpg" alt="img" /></p>
<p><strong>日志不一致问题</strong>：在正常情况下，leader 和 follower 的日志复制能够保证整个集群的一致性，但是遇到 leader 崩溃的时候，leader 和 follower 日志可能出现了不一致的状态，此时 follower 相比 leader 缺少部分日志。</p>
<p>为了解决数据不一致性，Raft 算法规定 <strong>follower 强制复制 leader 节日的日志</strong>，即 follower 不一致日志都会被 leader 的日志覆盖，最终 follower 和 leader 保持一致。简单的说，从前向后寻找 follower 和 leader 第一个公共 LogIndex 的位置，然后从这个位置开始，follower 强制复制 leader 的日志。但是这么多还有其他的安全性问题，所以需要引入<strong>Safety 安全性</strong>规则 。</p>
<h3><strong>2.3 Safety 安全性</strong></h3>
<p>当前的 <strong>Leader election 领导选举</strong> 和 <strong>Log replication 日志复制</strong>并不能保证 Raft 算法的安全性，在一些特殊情况下，可能导致数据不一致，所以需要引入下面安全性规则。</p>
<h3><strong>2.3.1 Election Safety 选举安全性：避免脑裂问题</strong></h3>
<p>选举安全性要求一个任期 Term 内只能有一个 leader，即不能出现脑裂现象，否者 raft 的日志复制原则很可能出现数据覆盖丢失的问题。Raft 算法通过规定若干投票原则来解决这个问题：</p>
<ul>
<li>一个任期内，follower 只会<strong>投票一次票</strong>，且先来先得；</li>
<li>Candidate 存储的日志至少要和 follower 一样新；</li>
<li>只有获得超过半数投票才有机会成为 leader；</li>
</ul>
<h3><strong>2.3.2 Leader Append-Only 日志只能由 leader 添加修改</strong></h3>
<p>Raft 算法规定，所有的数据请求都要交给 leader 节点处理，要求：</p>
<ol>
<li>leader 只能日志追加日志，<strong>不能覆盖日志</strong>；</li>