-
Notifications
You must be signed in to change notification settings - Fork 683
/
Copy path分布式一致性理论与算法.md.html
1487 lines (1390 loc) · 133 KB
/
分布式一致性理论与算法.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>分布式一致性理论与算法.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 class="current-tab" href="/文章/分布式一致性理论与算法.md.html">分布式一致性理论与算法.md.html</a>
</li>
<li>
<a 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>分布式一致性理论与算法</h1>
<p>本文在一开始会简单的讲述一下系统的演进和分布式系统面临的问题；接着解释几个分布式系统下的常见概念，如 CAP、BASE、拜占庭将军问题、一致性等；最后通过一个“数据复制”的实际问题来看一下 Paxos 和 Raft 算法。</p>
<blockquote>
<p>本篇文章过长，大约 4w 字，正常速度读完、不加思考也一小时以上，大家谨慎服用。</p>
</blockquote>
<h3>1. 序</h3>
<p>分布式一致性是一个很大的概念，我们经常会听到分布式缓存、分布式事务、分布式文件系统、分布式锁等等和“分布式”有关的概念。它们之间有什么异同？解决了哪些问题？为什么会有分布式的出现？</p>
<h4>1.1 传统的单体应用</h4>
<p>在互联网早期，流量还很少的时候，一个系统所需要的所有资源都放在同一台服务器上。包括数据库、文件存储、反向代理、应用等等，这个时代的代表是 LNMP 或者 LAMP 系统。现在依然有大量的 LNMP 系统存在，比如很多博主的博客网站、一些公司的门户网站等等。</p>
<p>只需要一台服务器，即可完成一切的操作。显然，这样做是存在一些风险的：</p>
<ul>
<li>所有的数据都在同一台服务器上，一旦这台服务器有损，所有的数据都有丢失的风险;</li>
<li>同一台服务器跑多个进程，可能会存在互相争抢资源的情况</li>
<li>不同的进程对资源的需求也是不同的，有的需要高 CPU，有的需要高内存，一台机器很难满足这种差异化需求。</li>
</ul>
<p><img src="assets/2e361d70-465e-11ea-814b-0d3e32b9c16f.jpg" alt="在这里插入图片描述" /></p>
<p>而随着服务被越来越多的访问，“all in one”的形式所带来的弊端就表现的更加明显。</p>
<h4>1.2 进程的拆分</h4>
<p>这个时候，开始将不同的进程分拆到不同的机器上去。比如将数据库和文件存储用一台专门的服务器部署。应用服务器通过 TCP 和这些服务器进行通信。</p>
<p><img src="assets/430b5df0-465e-11ea-936b-cfa88a589a44.jpg" alt="在这里插入图片描述" /></p>
<p>但是这也带来了一定的问题。</p>
<p>原本所有的服务都在一台机器上，通信都在本机直接完成，失败的可能性很低，几乎可以忽略。但是当服务拆分到不同的服务器并通过网络进行通信后，问题就出现了。首先网络总是不可靠的，丢包、延迟、篡改总是不可避免；同时还存在服务宕机的问题；对于某些重要的数据，只存放在一台服务器上显然也是不满足数据完整性要求的，因为磁盘可能会破损。</p>
<p>这就出现了几个问题：</p>
<ul>
<li>单实例都存在宕机无法提供服务问题</li>
<li>文件存储服务器磁盘不够用</li>
<li>数据库单实例存在数据丢失问题</li>
<li>单个应用服务器无法承载越来越大的流量</li>
</ul>
<h4>1.3 文件服务器集群化</h4>
<p>随着文件越来越多，单实例机器很难通过外挂磁盘来解决存储问题，同时单实例也存在严重的数据丢失和宕机风险。为了让文件系统具备更高的可用性及扩展性，将文件系统集群化成为一种解决方案。通过一些手段，将不同机器的磁盘整合起来，统一对外提供存储服务。内部将数据 sharding 到不同的机器上进行存储，同时根据需要进行多副本备份。</p>
<p>这样就解决了文件存储的问题。</p>
<h4>1.4 数据库主备模式</h4>
<p>对于数据完整性要求比较高的服务，比如 MySQL。一台服务器对外正常提供服务，同时有一台备机，平时只同步主机的数据。一旦主机宕机了，直接切换到备机，继续提供服务。</p>
<p>因为数据有了备份，所以当一台机器磁盘破损的时候，可以从另一台机器把数据恢复。两台机器丢失同一份数据的几率还是很少见的，所以准备模式可以极大的保证数据的完整性，如果是一主多备，那完整性将会更高。当前业界一般会把同一份数据做三个备份。</p>
<h4>1.5 服务水平扩展</h4>
<p>数据安全暂时有了保证，但是随着业务的不断发展，当流量越来越高的时候，一台应用服务器难以承载大量请求，应用层的可用性怎么保证？</p>
<p>这时候开始将服务进行水平扩展，也就是通常说的：加机器。一台机器承载不了，那就再加一台。</p>
<p>对于一些小型的项目，到这里其实已经能够满足 99% 的需求了，但是当业务需求越来越多，系统越来越复杂，所有的功能都跑在一个进程里的模式，开始冒出了很多的弊端。</p>
<p>首先，研发效率降低了，系统越来越臃肿，每次开发、调试、部署都会耗费大量的时间；其次，代码可维护性降低了，所有的功能全部集中在一起，牵一发而动全身；还有包括代码结构越来越不清晰、添加一个新功能需要更多的 hook 和时间、新员工很难快速理解代码并投入开发在内的各种各样问题。</p>
<h4>1.6 从单体应用到微服务</h4>
<p>这个时候，开始对系统进行微服务化改造。将原本一个大的单体应用，拆分为多个小的系统，系统之间通过 HTTP 或者 RPC 进行调用，系统各司其职。</p>
<p><img src="assets/5586a8e0-465e-11ea-8138-55f994072888.jpg" alt="在这里插入图片描述" /></p>
<p>至此，系统的演进告一段落，但是真正要面临的问题才刚刚开始。微服务、分布式的好处显而易见，但与此同时，除了享受便利，还需要解决便利所带来的问题。</p>
<h3>2. 分布式带来的挑战</h3>
<p><strong>多个服务器的磁盘如何高效利用？</strong></p>
<p>为了有更大的空间存储文件，不得不将多个服务器组合起来，这就是分布式文件系统所解决的问题。NFS、DFS、GFS 等都是分布式文件系统领域最核心的模型。在此之上衍生出了许许多多工业级的分布式文件系统，比如 FastDFS、HDFS 等。</p>
<p><strong>数据的复制怎么保证一致？</strong></p>
<p>前面有提到，一个 MySQL 实例无法保证数据不丢失，所以需要一个甚至多个副本，这就不可避免的要做数据同步。多副本同步数据时，如何保证数据同步完成后，所有实例的数据能够保持一致，是一件非常难的事情。</p>
<p>这个也是本文的主要内容，后面会做详细的分析。</p>
<p><strong>多个数据库如何执行事务？</strong></p>
<p>对于微服务来说，一个请求操作不同的数据库是很常见的。一些很重要的操作，需要保证严格的事务，单个数据库比较好操作。但是如果操作的是多个数据库，就需要一些特殊的手段来达成这个目的。</p>
<p>分布式事务的解决方案有很多，比如二阶段提交、三阶段提交、XA、saga 柔性事务等等。分布式事务不是本篇文章主要讨论的问题。</p>
<p><strong>如何使缓存更加高效？</strong></p>
<p>单机环境下，做本地缓存就可以了。但是当机器越来越多的时候，如果每台机器都做本地缓存，那么就会出现数据冗余，降低了缓存的可用性。这个时候，就需要一个独立于应用之外的分布式缓存出现。所有的应用都共享一个分布式缓存，这样就可以避免同一份数据被多次缓存的问题。</p>
<p><strong>分布式环境下如何执行定时任务？</strong></p>
<p>有一些任务需要定时执行，单机环境下直接定时执行就好了。但是分布式环境下，多个机器可能会同时执行同一个定时任务，会造成重复执行，不仅可能造成数据错误，而且浪费了资源。所以需要有一种方式可以让一个分布式集群中只有一台机器可以执行这个任务。一般情况下，通过分布式锁来解决这个问题。</p>
<p>全局只有一把锁，哪台机器获取到了这个锁，哪台机器就可以执行这个任务。</p>
<p><strong>小结</strong></p>
<p>为了解决分布式带来的挑战，分布式存储系统、分布式缓存、分布式锁、分布式事务等被一个一个的提出来。每一个技术都解决了一种特定的业务。</p>
<ul>
<li>分布式文件系统：解决了大文件的存储问题</li>
<li>分布式缓存：解决了缓存共享的问题</li>
<li>分布式事务：解决了一次请求访问多个数据库的问题</li>
</ul>
<p>本篇文章主要内容不会涉及到上述技术，而是侧重于“数据同步”这个细分领域。本文的主角 Paxos 解决的是分布式的共识问题，通俗的说就是多个机器如何对一个值达成一致；而 Raft 解决的是复制状态机问题。</p>
<h3>3. 分布式基础理论</h3>
<h4>3.1 分布式面临的问题</h4>
<p>应用由单体应用切换到分布式后，首先面临的就是网络问题。原本本机内通信的方式改成了使用网络通信，而网络是不可靠的。网络可能因为一些硬件或者其他原因导致网络不可用；数据包可能会丢失，可能会被篡改；网络还有延迟。单体应用下，一个操作只会是成功或者失败，而分布式环境下，还多了一个超时。超时的操作可能成功也可能没有成功，这个时候就很难做出判断。</p>
<p>其次，是并发的问题。两个节点同时对外提供服务，两个客户端分别请求两个节点，对同一个数据进行修改，最终可能就会导致数据不一致。</p>
<p><img src="assets/65e9c230-465e-11ea-af25-415462abed23.jpg" alt="在这里插入图片描述" /></p>
<p>最后还有顺序问题。一个值先 <code>add 1</code>，再 <code>get</code>，对于单体应用来说很好判断结果，但是对于分布式应用来说就很难。因为网络存在延迟、请求路由存在不确定性，最终 <code>get</code> 到的值就很难断定。所以，两个操作之间需不需要有顺序 、如何确定两个操作的顺序，是需要考虑的。</p>
<h4>3.2 拜占庭将军问题</h4>
<h5><strong>3.2.1 问题的提出</strong></h5>
<p>由于网络的不可靠性，从 A 发出的请求，到达 B 后，可能会被篡改或者由于计算机系统自身的原因导致数据混乱，最终 B 收到错误的信息，进而导致整个集群数据不一致。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。Lamport 在他的论文中，通过一个“攻占拜占庭城邦”的故事首先提出了这种问题。</p>
<blockquote>
<p>一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。</p>
<p>系统的问题在于，将军中可能出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。假设有 9 位将军投票，其中 1 名叛徒。8 名忠诚的将军中出现了 4 人投进攻，4 人投撤离的情况。这时候叛徒可能故意给 4 名投进攻的将领送信表示投票进攻，而给 4 名投撤离的将领送信表示投撤离。这样一来在 4 名投进攻的将领看来，投票结果是 5 人投进攻，从而发起进攻；而在 4 名投撤离的将军看来则是 5 人投撤离。这样各支军队的一致协同就遭到了破坏。</p>
<p>由于将军之间需要通过信使通讯，叛变将军可能通过伪造信件来以其他将军的身份发送假投票。而即使在保证所有将军忠诚的情况下，也不能排除信使被敌人截杀，甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通讯可靠性来解决问题。</p>
<p>假使那些忠诚（或是没有出错）的将军仍然能通过多数决定来决定他们的战略，便称达到了“拜占庭容错”。在此，票都会有一个默认值，若消息（票）没有被收到，则使用此默认值来投票。</p>
</blockquote>
<p>上述的故事映射到计算机系统里，将军便成了计算机，而信差就是通信系统。虽然上述的问题涉及了电子化的决策支持与信息安全，却没办法单纯的用密码学与数字签名来解决。因为电路错误仍可能影响整个加密过程，这不是密码学与数字签名算法可以解决的问题。因此计算机就有可能将错误的结果提交，最终导致错误的决策。</p>
<h5><strong>3.2.2 拜占庭容错</strong></h5>
<p>如何解决拜占庭将军问题，业界提出了很多种理论和算法。</p>
<ul>
<li>其中一个解决方案认为即使出现了伪造或错误的消息。只要有问题的将军的数量不到三分之一，仍可以达到“拜占庭容错”。原因是在背叛的将军不足三分之一的情况下，有问题的将军可以很容易的被纠出来。但是超过或等于三分之一时就很难判断了，比如有将军A，将军 B 与将军 C。当 A 要求 B 进攻，却要求 C 撤退时。就算 B 与 C 交换所收到的命令，B 与 C 仍不能确定是否 A 有问题，因为 B 或 C 可能将窜改了的消息传给对方。以函数来表示，将军的总数为 n，n 里面背叛者的数量为 t，则只要 n > 3t 就可以容错。</li>
<li>另一个解决方案需要有无法消去的签名。在现今许多高度信息安全要求的关键系统里，数字签名就经常被用来实现拜占庭容错，找出有问题的将军。</li>
<li>此外，1980 年代还有其他用来达到拜占庭容错的架构被提出，如：FTMP、MMFCS 与 SIFT。</li>
<li>1999 年，卡斯托（Miguel Castro）与李斯克夫（Barbara Liskov）提出了实用拜占庭容错（PBFT）算法。该算法能提供高性能的运算，使得系统可以每秒处理成千的请求，比起旧式系统快了一些。</li>
<li>在 PBFT 之后，许多用于拜占庭容错（BFT）的通信协议也被提出来改善其通信的强健性与效率。比如 Q/U、HQ、Zyzzyva 与 ABsTRACTs，用来提升效率</li>
<li>区块链技术中，比特币核心技术 pow，其实也是为了解决拜占庭将军问题。</li>
</ul>
<blockquote>
<p>拜占庭将军问题不是本文的主要内容，后续讲的 Paxos、Raft 算法也是在不考虑拜占庭将军问题的前提下提出的。上述有关拜占庭将军问题的内容大部分摘自<a href="https://zh.wikipedia.org/wiki/拜占庭将军问题">维基百科</a>相关词条，我做了一些修改和补充。</p>
</blockquote>
<h4>3.3 分区的产生</h4>
<p>分布式系统中，节点与节点之间通过网络进行通信，而网络的不可靠可能会导致节点与节点“失联”。</p>
<p><img src="assets/72547830-465e-11ea-895e-2fe851c47874.jpg" alt="在这里插入图片描述" /></p>
<p>由于网络的中断，导致一个大的集群变成了两个子子群，这两个子集群就是两个不同的分区。分区出现后，在 A 分区对 X 进行的操作，B 分区是不可见的，这样一来，数据就会不一致。</p>
<p>所以，当分区出现的时候，如果分区依旧对外提供服务，那么就会导致数据不一致；如果一定要求数据保持一致，那么当分区出现的时候，就不能允许继续对外提供服务。</p>
<p>这就是 CAP 定理的由来。</p>
<h4>3.4 CAP 定理</h4>
<p>CAP 定理是针对分布式系统的一个定理。其中，C 指 Consistency（一致性），A 指 Availability（可用性），P 指Partitition tolerance（分区容忍性）。</p>
<p>CAP 定理认为，同一时间最多只能满足三个条件中的两个，无法同时满足三个条件。</p>
<h5><strong>3.4.1 来源</strong></h5>
<p>这个定理起源于加州大学柏克莱分校的计算机科学家 Eric A. Brewer 在 2000 年的“分布式计算原理研讨会”上提出的一个猜想。2002 年，麻省理工学院的 Seth Gilbert 和 Nancy Lynch 发表了“CAP 猜想”的证明，使之成为一个定理。</p>
<p>Gilbert 和 Lynch 证明的“CAP 定理”、比“CAP猜想”在某种程度上更加狭义。定理讨论了在两个互相矛盾的请求到达彼此连接不通的两个不同的分布式节点的时候的处理方案。</p>
<h5><strong>3.4.2 内容</strong></h5>
<p><strong>Consistency（一致性）</strong></p>
<p>分布式系统中存在大量的<strong>并发</strong>读写操作，这些并发操作衍生出了对一致性的需求。</p>
<p>CAP 定理中的一致性指的是：一个节点进行数据更新操作后，结果必须立即对其他所有节点可见，也就是线性一致性，下文会有详细的论述。</p>
<p>如图所示：</p>
<p><img src="assets/7f699f00-465e-11ea-814b-0d3e32b9c16f.jpg" alt="在这里插入图片描述" /></p>
<p>对 node-a 进行 set 操作后，要求对 node-b 和 node-c 进行读取时，一定可以读取到最新值。</p>
<p>这种一致性是一种强一致性，也被称之为线性一致性。</p>
<p><strong>Availability（可用性）</strong></p>
<p>可用性指的是：用户对集群的任何读写操作都是<strong>成功</strong>的。</p>
<p>也就是说，集群对外统一提供的服务应该一直可用，即使集群内部出现各种宕机、网络抖动等问题。但是现实中有些问题可能无法避免，比如因机房起火、地震等因素导致的服务不可用是很难通过纯技术来解决的。一般会用“几个 9”来描述一个系统的可用性，通常会根据全年停机时间来进行计算。</p>
<table>
<thead>
<tr>
<th align="center">可用性</th>
<th align="center">可用水平（%）</th>
<th align="center">年可容忍停机时间</th>
</tr>
</thead>
<tbody>
<tr>
<td align="center">容错可用性</td>
<td align="center">99.9999</td>
<td align="center">< 1 min</td>
</tr>
<tr>
<td align="center">极高可用性</td>
<td align="center">99.999</td>
<td align="center">< 5 min</td>
</tr>
<tr>
<td align="center">具有故障自动恢复能力的可用性</td>
<td align="center">99.99</td>
<td align="center">< 53 min</td>
</tr>
<tr>
<td align="center">高可用性</td>
<td align="center">99.9</td>
<td align="center">< 8.8 h</td>
</tr>
<tr>
<td align="center">商品可用性</td>
<td align="center">99</td>
<td align="center">< 43.8 h</td>
</tr>
</tbody>
</table>
<p>通常，说某个系统可用性可以达到 5 个 9，意思就是说他的可用水平是 99.999%，即全年停机时间不超过 <code>(1-0.99999)*365*24*60 = 5.256 min</code>，这是一个极高的要求。 在 CAP 定理中，不考虑自然因素的影响，可用性指的是 100% 可用。</p>
<p><strong>Partitition tolerance（分区容忍性）</strong></p>
<p>分区容忍性指的是：集群因为某种原因产生分区后，各分区仍然能够独立对外提供服务。</p>
<p>分区指的是由于某些原因，比如网络不通等，导致一个集群被分成多个不可通信的子集群，这个时候如果依然允许子集群对外正常提供服务，那么就说这个集群是分区容忍的。</p>
<blockquote>
<p>分区和宕机不同，宕机的节点无法接收网络请求，负载均衡设备可以自动将流量切走；但是分区的节点本身是正常的，依然可以正常接收网络请求，负载均衡设备很难决定是否执行切流。这就会造成子集群的出现。</p>
</blockquote>
<h5><strong>3.4.3 定理证明</strong></h5>
<p>由于网络总是不可靠的，而分布式集群的基础就是多机网络通信，所以<strong>分区是不可避免的</strong>。</p>
<p>因为分区总可能出现，如果允许在分区出现的时候，各子集群可以正常对外提供服务，那么：</p>
<p><strong>CP</strong></p>
<p>分区之间无法通信，数据互相不可达，对于写请求，是无法让所有的节点都更新成最新值的。</p>
<p>如果要保证一致性，那写请求就只能返回失败，这就违反了可用性。</p>
<p>此时系统满足 CP。</p>
<blockquote>
<p>CP 系统，出现分区，不能保证数据写入到所有节点，返回写入失败，违反可用性。</p>
</blockquote>
<p><strong>AP</strong></p>
<p>如果一定要保证可用性，那么写请求的数据就只能存在当前分区的节点上，而其他分区的节点无法更新为最新值，每个分区内同一数据的值可能都是不一样的，这样就违反了一致性。</p>
<p>此时系统满足 AP。</p>
<blockquote>
<p>CP 系统，出现分区，为保证可用性，导致各个分区内同一个数据的值不一样，违反一致性。</p>
</blockquote>
<p><strong>CA</strong></p>
<p>如果当分区出现时候，直接不对外提供服务，那么可以同时满足 CA。</p>
<blockquote>
<p>CA 系统，不允许出现分区，一致性和可用性都可以满足，违反分区容忍性。</p>
</blockquote>
<p><strong>结论</strong></p>
<p>根据上述推算，一个分布式系统无法同时满足 CAP 三个条件，只能选择其中两个，这就是 CAP 定理。</p>
<h5><strong>3.4.5 缺陷</strong></h5>
<p>虽然 CAP 是一个定理，但是也并不意味着所有的分布式系统都满足 CAP 或者必须按照 CAP 来设计。原因是 CAP 是一个很理想的定理，而现实总是很残酷。</p>
<p>比如可用性，真实世界里是没有办法满足 100% 可用的，即使三地五中心也可能会导致数据全部丢失，只不过可能性微乎其微而已。</p>
<p>CAP 中要求在 C 和 A 之间一定要做一个选择，对于实际的应用而言很难接受，也是不必要的。要一致性就不能满足可用性，要可用性就不能满足一致性，这种非黑即白的设计很难满足大多数系统的要求。工业界更多的选择是在 C 和 A 之间找到一个平衡。这也就有了“最终一致性”，“BASE 理论”等概念。</p>
<h4>3.5 BASE 理论</h4>
<p>BASE 理论是 eBay 架构师结合 CAP 定理与实际分布式应用设计总结出的新的理论，核心思想是，在满足分区容忍与适当的可用性的条件下，根据自身的业务特点，采用适当的方式来使系统达到最终一致性。</p>
<p>其中，“BASE”是“Basically Available（基本可用）”、“Soft State（软状态）”和“Eventually Consistent（最终一致性）”三个短语的缩写。</p>
<blockquote>
<p>CAP 是一个<strong>定理</strong>，而 BASE 是一个<strong>理论</strong>。BASE 理论本质上是 CAP 定理满足 P 的条件下，在 C 和 A 之间找到一个符合特定系统实际情况的平衡。</p>
</blockquote>
<h5><strong>3.5.1 来源</strong></h5>
<p>对于一个实际的分布式系统而言，失去一致性与可用性中的任何一个，都是难以接受的。而且在某些场景下，强一致性与 100% 可用性并不是非要不可。</p>
<p>来考虑这样一个场景：12306 售票。</p>
<p>在 12306 买票的时候，要先选择车次，看是否有余票，如果还有票，那么可以下单购买。这个场景分为两步：1.检查是否有余票（get num）；2.下单购买（get num & num--）。因为火车的座次是一人一座的，所以必须保证同一个座位同一个时间的票只能售卖一次。</p>
<p>从检查是否有余票到真正完成下单之间是有一段时间的，很有可能在开始检查余票的的时候还有票，但是在犹豫要不要买的时候，票被被人买了；这个时候我依然可以下单，但是根据票和座的关系，购买操作会被拒绝。</p>
<p>对于“检查是否有余票”这个操作来说，这个余票的数字（get num）不一定要求是最新的，比如实际只有一张票了，但是返回还有 2 张也没有关系，这个数据可以不是强一致性的。</p>
<p>而对于“下单购买”这个操作来说，余票的数字就必须是最新的（get num & num--），此时数据要满足强一致性。</p>
<p>在春运抢票的时候，因为系统容量问题，无法承载所有请求，这个时候如果不进行特殊处理，那服务器一定会被打垮，这和是否 CAP 没有关系，CAP 并不能解决流量洪峰问题。所以只能对流量进行限流，保护应用服务器。而限流会造成用户的当前请求不可用，但并不会导致整个 APP 不可用，这就是一个基本可用的状态。</p>
<p>所以，强一致性和完全可用对于某些业务场景来说，并不是必需品。CAP 定理固然是一个事实，但是解决实际问题的时候，还是应该考虑实际情况。而 BASE 理论就是根据实际的业务诉求与 CAP 定理相结合而总结出来的。</p>
<h5><strong>3.5.2 内容</strong></h5>
<p><strong>Basically Available（基本可用）</strong></p>
<p>分布式系统在出现不可预知故障的时候，允许损失部分<strong>可用性</strong>（系统整体依然可用）：</p>
<ul>
<li>响应时间的损失。查询余票正常情况下 1s 即可拿到结果，但是出现故障的时候，可能需要 2s。</li>
<li>系统功能的损失：抢票的时候，对用户进行限流，虽然无法完成既定功能，但是提升了用户体验。</li>
</ul>
<p><strong>Soft State（软状态）</strong></p>
<p>允许系统中的数据存在中间状态，并认为该状态不影响系统的整体可用性，即允许数据异步同步过程中存在延迟。</p>
<p><strong>Eventually Consistent（最终一致性）</strong></p>
<p>允许数据同步存在延迟，但是需要保证在规定的时间内，数据最终会达到一致。时间期限需要综合实际情况进行设计。</p>
<h4>3.6 一致性</h4>
<p>上面解释了分区和可用性，但是对于一致性还没有一个明确的定义。当谈到一致性的时候，会遇到这样几个词：CAP 定理中的 consistency；ACID 中的 consistency；cache 一致性协议中的 coherence；以及 Paxos 中的 consensus。</p>
<p>coherence、consensus 和 consistency 一般都被翻译为“一致性”，那么它们有什么异同呢？</p>
<h5><strong>3.6.1 什么是一致性</strong></h5>
<p>当谈到一致性的时候，会遇到这样几个词：CAP 定理中的 consistency；ACID 中的 consistency；cache 一致性协议中的 coherence；以及 Paxos 中的 consensus。</p>
<p>coherence、consensus 和 consistency 一般都被翻译为“一致性”，那么它们有什么异同呢？</p>
<p><strong>coherence</strong></p>
<p>Coherence 只出现在 <a href="https://en.wikipedia.org/wiki/Cache_coherence">Cache Coherence</a> 一词中，作为”缓存一致性”被提出。现代计算机一般都是多核机器，每个 CPU 各自拥有 L1 和 L2 缓存，同机的所有 CPU 共享一个 L3 缓存。当编写并发程序并产生竞态数据时，如何保证一个 CPU 可以读立即读到另一个 CPU 刚刚写入的数据，成为一个需要考虑的问题。而“Cache Coherence”就是用来解决这个问题的。</p>
<p><strong>consensus</strong></p>
<p>准确的说，consensus 应该被翻译为“共识”，它主要解决的是如何使多个节点对同一个事件达成共识的问题。一般来说，在分布式系统中，解决的是复制状态机的问题。</p>
<p><strong>ACID 中的 consistency</strong></p>
<p>ACID 中的一致性是指数据库的一致性约束，ACID 一致性完全与数据库规则相关，包括约束、级联、触发器等。分布式事务用来保证分布式系统下对多个数据库进行操作的 ACID。</p>
<p><strong>CAP 定理中的 consistency</strong></p>
<p>CAP 中的一致性指的是在多个节点之间如何保证数据的强一致。 CAP 中的 consistency 一般指的是“线性一致性”。</p>
<p>但是 CAP 定理在解决实际问题中作用有限，因为 CAP 中的强一致性与百分百可用性本身就很难甚至无法实现，要求再这两者之间必须选一放一对于一个真实的应用来说过于苛刻。所以在 CAP 定理的基础上，有人根据实际问题的解决方案提出了“BASE 理论”，也就是“Basically Available（基本可用）”、“Soft State（软状态）”和“Eventually Consistent（最终一致性）”。</p>
<p>BASE 理论不要求数据的强一致性，转而采用一致性要求更低的最终一致性，从而使系统具有更高的可用性。</p>
<h5><strong>3.6.2 怎样可以称之为“一致”</strong></h5>
<p>一个系统是由<strong>状态</strong>和一些<strong>导致状态转移的操作</strong>组成的。在系统运行期间，它将随着操作的不断进行从一个状态转移到另一个状态。需要保证这种状态的改变是可控的，从而可以判断出经过状态改变后的最终状态是否正确。也就是说，需要一种规则，可以更加清晰的判断出最终状态是否正确。</p>
<blockquote>
<p>满足规定的结果，即“正确”，就说这个状态的改变是“一致”的。</p>
</blockquote>
<p>比如：</p>
<pre><code class="language-shell">set x = 1
get x
set x = 2
set x = 3
get x
</code></pre>
<p>上面这几行伪代码执行之后，输出的结果应该是 <code>1 3</code>，这个应该没有什么问题，下意识的就可以得出这个结论。但是为什么不可能是 <code>5 6</code>，甚至不可能是 <code>helloword</code> 呢？</p>
<p>这是因为，上述结果默认了一种“正确性规则”：设置一个状态的值之后，读取到的一定是最新设定的值。所以读到 <code>1 3</code> 是正确的，而读到其他内容是错误的。</p>
<p>当然，也可以重新定义一种规则，比如：设置一个状态的值之后，读取到的一定是最新设定的值 +1，那么读到 <code>2 4</code> 才是正确的。</p>
<p>但是无论规则是什么，总是要有一种规则来使计算机的状态改变变得可控并且可被判断，否则这个程序是没有意义的，这就是“正确性”的价值所在。</p>
<p><strong>而满足“正确性”的规则，就是现在所讨论的“一致性模型”。</strong></p>
<blockquote>
<p>一旦把变量写为某个值，比如 a，那么读操作就应该返回 a，直到再次改变变量。读到的值应该总是返回最近写入的值。一般会把这种系统称为“单一<strong>寄存器</strong>”（并不特指硬件寄存器）。</p>
</blockquote>
<h5><strong>3.6.3 顺序</strong></h5>
<p>顺序指的是，多条命令之间的先后顺序。比如在一个单进程单线程模型中：</p>
<pre><code class="language-shell">let x = 0
set x = 1
get x
// x = 1
</code></pre>
<p>x 显而易见是 1。</p>
<p>但是当上述代码变为多线程执行后，x 的值就很难确定了。</p>
<pre><code class="language-shell">let x = 0
A: set x = 1
B: get x
// 0 or 1
</code></pre>
<p>因为 A 和 B 同时执行，顺序未知，所以 x 的值是不确定的。这个时候就需要进行并发控制，比如锁、原子类、内存屏障等等。这些操作的目的，是让某个线程对某个变量的修改，可以立刻被其他线程所看到。</p>
<p>分布式环境下，请求的处理和多线程模型很相似。所以也需要进行“并发控制”。但是正如上面“BASE 理论”中所讲的一样，有些情况下并不一定需要“修改立刻可见”，这也就出现了不同的“一致性”概念。</p>
<h5><strong>3.6.5 一致性分类</strong></h5>
<blockquote>
<p>这里以及下文所讨论的一致性都是是 CAP 定理中的 consistency。</p>
</blockquote>
<p>在单机单 CPU 环境下，一致性是很容易被满足的，因为所有的状态改变都是顺序执行的，只有执行完第一个操作以后，才会执行第二个操作。这就使得满足一致性变得非常简单。</p>
<p>但是在分布式环境下，同一个状态在多个节点分别被修改，如何使得在某一个节点上的修改被其他节点所看见，是一个必须考虑的问题，否则就会出现不一致的现象。</p>
<p>一致性根据强弱大体可以分为以下几类：</p>
<ul>
<li>
<p>完全一致性</p>
</li>
<li>
<p>强一致性</p>
<ul>
<li>线性一致性</li>
</ul>
</li>
<li>
<p>较强一致性</p>
<ul>
<li>顺序一致性</li>
</ul>
</li>
<li>
<p>弱一致性</p>
<ul>
<li>最终一致性
<ul>
<li>因果一致性</li>
<li>读己之所写一致性</li>
<li>会话一致性</li>
<li>单调读一致性</li>
<li>单调写一致性</li>
</ul>
</li>
</ul>
</li>
</ul>
<p>完全一致性</p>
<p>完全一致性指的是 A 对 x 做的修改，立刻可以被 B 观察到，不存在读取到旧值的情况。完全一致性几乎没有办法实现，对于硬件来说，对一个值得修改，从寄存器到磁盘到缓存总是需要一定时间的，既然存在一定的时间消耗，哪怕几微秒，也无法达到完全一致性。从网络上来说，网络存在开销，这个开销比硬件的开销要大的多得多得多，就更不可能实现了。</p>
<p>所以，完全一致性只是一种理论上的模型。</p>
<p><strong>线性一致性</strong></p>
<p>线性一致性是当前计算机体系中可以达到的最强的一致性模型。一般说的强一致性就指的是线性一致性。要求：<strong>变更是原子的，发生在请求和响应之间的某个时间点，并且变更后内容立即对其他节点可见。</strong></p>
<p>下面看一个例子：</p>
<p><img src="assets/8e392000-465e-11ea-895e-2fe851c47874.jpg" alt="在这里插入图片描述" /></p>
<p>首先设置 x 的值为 1；一共有 6 个进程对 x 进行操作，其中 C 进程修改了 x 的值。线段 t 表示全局时间，A-F 进程中的线段分别表示每个线程的执行时间跨度，线段的起点表示命令开始执行的时间点，线段的终点表示命令执行完成、可以获取到返回值的时间点。图中两条竖直的虚线 t1 和 t2 表示 C 进程对 x 做修改的开始时间和结束时间。</p>
<p>**因为变更是原子的、发生在请求和响应之间的某个时间点，所以 x=2 一定发生在 t1 和 t2 中间的某一刻，而不可能发生在 t1 之前或者 t2 之后。**来分别看一下各个读线程可能读到的值。</p>
<ul>
<li>进程 A：开始时间和结束时间都小于 t1，所以只能读到 1，不可能读到 2。</li>
<li>进程 B：开始时间小于 t1，结束时间大于 t1，所以可能读到 1，也可能读到 2，取决于“真正执行 B 的时间点”和“真正执行 C 的时间点”的关系。</li>
<li>进程 D：开始时间大于 t1 但是小于 t2，结束时间大于 t2，可能读到 1，也可能读到 2。</li>
<li>进程 E：开始时间大于 t2，所以只能读到 2。</li>
<li>进程 F：开始时间小于 t1，结束时间大于 t2，可能读到 1，也可能读到 2。</li>
</ul>
<p>综上，如果要求满足线性一致性，那么 A 只能读到 1，E 只能读到 2，其他线程读到 1 和 2 都可能。</p>
<p><strong>漏斗模型</strong></p>
<p>上面使用一个线段来表示命令的执行，有人提出了一种漏斗模型，来更确切的进行描述。</p>
<p><img src="assets/98c5ee40-465e-11ea-90d3-f11cd86d32dc.jpg" alt="在这里插入图片描述" /></p>
<p>漏斗模型使用一个折线来表示命令的执行情况，起点和终点依然表示开始和结束时间，中间的拐点表示“该命令真正执行的时间”，也就是线性一致性所要求的“<strong>发生在请求和响应之间的某个时间点</strong>”。</p>
<p>在漏斗模型中，可以很清楚的知道，命令真正生效的时间，按上图来看：</p>
<ul>
<li>进程 A：只能读到 1</li>
<li>进程 B：只在读到 1</li>
<li>进程 D：只能读到 2</li>
</ul>
<p>漏斗模型更能体现出线性一致性的要求，但是从实际情况来看，很难甚至无法明确出拐点到底出现在哪个时间点。所以，一般从生产情况出发，进<strong>程 B 和</strong>进<strong>程 D 读到 1 和 2 都是可以满足线性一致性的。</strong></p>
<blockquote>
<p>漏斗模型是一种理论价值很足的模型，但是很难用于生产。</p>
</blockquote>
<p><strong>顺序一致性</strong></p>
<blockquote>
<p>Sequential consistency 的是 Lamport 在 1979 年首次提出的。（参看他的论文 How to make a multiprocessor computer that correctly executes multiprocess programs）</p>
</blockquote>
<p>线性一致性的实现成本是很高的，顺序一致性的要求比线性一致性低一些。<strong>要求：变更是原子的，不要求执行顺序按照真实发生的时间进行，但是单个进程内的操作顺序必须与编码时相同。</strong></p>
<p>怎么理解呢？线性一致性要求所有的操作在全局是有序的，而顺序一致性弱化了这个要求，只需要在进程内有序即可，不需要全局有序。</p>
<p>下面来看一个例子：</p>
<p><img src="assets/a3876110-465e-11ea-906f-ed3ee39936fa.jpg" alt="在这里插入图片描述" /></p>
<p>假设 x 值为 1，有 A、B、C 三个进行分别对 x 进行一次货多次操作。一共有 6 个操作，箭头依旧表示操作的起止时间。</p>
<p>操作落到计算机上，最终是会有一个执行顺序的，比如 123456，或者 654321。6 个操作可以任意排列组合。线性一致性要求“变更立刻可见”，对于读操作，顺序其实不重要，但是一旦涉及到写，那就一定有先后顺序。比如“操作 1”一定不可能读到 x=3，因为“操作 3”在全局看来发生在“操作 1”之后。</p>
<p>顺序一致性弱化了这个对顺序的要求。只要最终操作执行的顺序，符合单个进行内操作的顺序即可。对于上图来说就是：2 3 4 一定按照这个顺序执行，5 6 一定按照这个顺序执行，至于 2 和 5 谁先谁后无所谓。比如：</p>
<ul>
<li>1 2 3 4 5 6：这个顺序满足顺序一致性要求。</li>
<li>1 2 5 3 6 4：这个顺序满足顺序一致性要求。</li>
<li>1 5 6 2 3 4：这个顺序满足顺序一致性要求。</li>
</ul>
<p>但是 2 3 4 和 5 6 的顺序不能变：</p>
<ul>
<li>1 2 4 3 5 6：这个就不满足顺序一致性。</li>
</ul>
<p><strong>扩展：多核 CPU 下的一致性</strong></p>
<p>上面有提到“缓存一致性”，是用来解决多核 CPU 缓存问题的。当前，多核 CPU 架构共有三级缓存，每一个 CPU 有自己独立的一级和二级缓存，所有 CPU 共享一个三级缓存。</p>
<p>当只有读操作的时候，显然没有什么问题，缓存里的内容就是内存里的内容。但是一旦涉及到写操作，事情就有点复杂了。CPU 的写有直写和回写两种方式。直写可以简单理解为直接写入内存，让缓存过期。而回写，为了提高速率，只写入自己的缓存，等到一定时间之后，再回写到内存。</p>
<p>如果不做任何处理，回写会有并发的问题，一个 CPU 的修改只保存在自己的缓存上，其他的 CPU 看不到，就会出现脏读。</p>
<p>为了解决这个问题，需要使用一种机制，可以让回写的数据可以被其他 CPU 读到，这就是 MESI 协议（当然还有一些其他协议）。</p>
<p>一般 CPU 的设计，比如 x86 架构下，是允许指令重排的，这就导致顺序一致性可能会被破坏。CPU 一般不禁止指令重排，而把它抛给上层去控制，这也就是为什么会有 CAS、内存屏障、原子变量等技术，编码人员根据自己的需要，插入内存屏障阻止指令重排，最终达到顺序一致性。</p>
<p>感兴趣的同学可以去了解一下 MESI 协议和缓存一致性技术，这里简单提一下，就不扩展了。</p>
<p><strong>最终一致性</strong></p>
<p>最终一致性是弱一致性里最常见的一种，一般系统的设计都会考虑设计为最终一致性。最终一致性有分为以下几种：</p>
<ul>
<li>因果一致性：两个有因果关系的事件要保证在全局看来有序，比如知乎提问和回答。当你能看到回答的时候，一定可以看得到问题。达到因果一致性需要一个向量时钟来表示两个操作之间的因果关系，其中比较有名的是 Lamport 提出来的“Lamport 时间戳”，感兴趣的可以自行搜索学习。</li>
<li>读己之所写：可以立即读到我自己写入的数据，但是别人不需要立即读到。比如我发一个朋友圈，我自己必须一直可以看到，但是我的好友可以晚一点看到。实现这种一致性的一种方式是做会话保持，都从同一个节点读取。</li>
<li>会话一致性：这个是读己之所写的一种特殊场景。</li>
<li>单调读：如果一个进程读取数据项 a 的值，那么该进程对 a 执行的任何后续读操作总是得到第一次读取的那个值或更新的值，为了避免出现时光倒流的现象。</li>
<li>单调写：保证来自同一个进程的写操作顺序执行。</li>
</ul>
<p>每一种一致性铺开了讲都能写好几篇文章出来，这里就简单的概括总结一下，感兴趣的同学可以自行深入学习。</p>
<h3>4. 从数据复制看一致性</h3>
<p>上面的内容都是一些背景和理论，到这里才算是进入了本篇文章的核心内容：数据复制。首先来看这样一个问题：</p>
<p><img src="assets/ab62caf0-465e-11ea-869e-dd0ddfb7a363.jpg" alt="在这里插入图片描述" /></p>
<p>有很多场景需要做数据同步，比如：数据要备份，存多个副本；MySQL 主备数据同步；zookeeper 节点之间数据同步等等。但是由于网络不可靠、机器宕机、磁盘破损等问题的存在，数据同步的可靠性大大的降低。如何能够将数据完整的同步到所有的节点？</p>
<h4>4.1 主从异步复制</h4>
<p><img src="assets/b1e3ade0-465e-11ea-936b-cfa88a589a44.jpg" alt="在这里插入图片描述" /></p>
<p>主从异步是最容易想到的方式，主收到请求后，直接返回 success，然后异步的将数据同步到 slave 节点。但是，如果在主节点还没有同步之前，主节点磁盘破损，或者网络故障导致没有同步成功，那么就会导致数据丢在或者集群数据不一致等问题。</p>
<h4>4.2 主从同步复制</h4>
<p>既然异步存在同步不成功的问题，那么直接改成同步的：</p>
<p><img src="assets/b9fd3230-465e-11ea-90d3-f11cd86d32dc.jpg" alt="在这里插入图片描述" /></p>
<p>master 节点收到配置以后，先同步到所有的 slave 节点，全部成功以后再向客户端返回成功。但是由于整个过程都是同步阻塞的，rt 会变高甚至超时。如果是同步数据的请求超时，很难判断是成功了还是失败了，这样只能全部回滚，增加了很多不必要的处理。</p>
<h4>4.3 主从半同步复制</h4>
<p>既然全同步会影响 rt，异步会导致无法判断时候同步成功，那么一半同步一半异步来处理，即主从半同步方式：</p>
<p><img src="assets/bf7bc050-465e-11ea-8138-55f994072888.jpg" alt="在这里插入图片描述" /></p>
<p>只要有 x 个节点返回了同步成功，那么就认为是成功了。这样的问题是，可能任意一个节点的数据都是不完整的。为了解决这个问题，在主从半同步的基础上，提出了一种多数派读写的方式。</p>
<blockquote>
<p>事实上，很多系统的数据同步都使用的是异步或者半同步的方式，比如 MySQL 的数据备份、主从同步等。但是数据同步并不是一个简单的 HTTP 请求，更多的是一些二阶段提交协议。比如 MySQL 通过二阶段 + binlog + redolog 来完成数据的同步，感兴趣的同学可以自行搜索学习。</p>
</blockquote>
<h4>4.4 多数派（quorum）读写</h4>
<h5><strong>4.4.1 初识</strong></h5>
<p><img src="assets/c826af30-465e-11ea-90d3-f11cd86d32dc.jpg" alt="在这里插入图片描述" /></p>
<p>此时，不分主备，客户端向所有的节点发起读写请求。对于写请求：只要一半返回成功，就认为是成功的；对于读请求，选择占比在一半以上的返回值。</p>
<p>比如有三个节点 A(x=1)、B(x=1)、C(x=1)。</p>
<p>执行 <code>set x = 2</code> 后，A 和 B 执行成功，此时 A(x=2)、B(x=2)、C(x=1)。</p>
<p>执行 <code>get x</code>，A、B、C 分别返回 2、2、1，因为 2 占比一半以上，所以最后 x = 2。</p>
<p>quorum 机制的数据逻辑在于：两个一半以上一定有一个共同的值，所以一定可以读到最新的。</p>
<h5><strong>4.4.2 版本号</strong></h5>
<p>但是只记录值是不能满足需求的，来看这样一个场景：</p>
<p><img src="assets/d7b7f990-465e-11ea-a2f4-17bdc34f15cb.jpg" alt="在这里插入图片描述" /></p>
<p>右侧为集群中的三个节点，其中黄色表示响应，蓝色表示未响应。当执行到第三步时，客户端拿到了 1 和 2 两个值，此时 1 和 2 的数量都不满足半数以上的条件，如果没有其他参数，那么客户端将无法区分哪个是最新值。所以需要一个版本来进行标识，版本号全局递增，版本号大的为最新的值。这样一来，第三步的结果就可以确定了：x = 2。</p>
<h5><strong>4.4.3 并发问题</strong></h5>
<p>但是多数派读写也是存在并发问题的：</p>
<p><img src="assets/dfe88850-465e-11ea-90d3-f11cd86d32dc.jpg" alt="在这里插入图片描述" /></p>
<p>如上图：x 初始化为 1，两个进程分别对 x 进行操作，左边执行 <code>x += 1</code>， 右边执行 <code>x += 2</code>，期望最终的结果是 4。</p>
<ul>
<li>两个进行同时执行多数派读，都得到 x = 1；</li>
<li>左边的进程执行 <code>x += 1</code>，后，执行多数派写，此时集群中，x = 2；</li>
<li>右边的进程执行 <code>x += 2</code>，后，如果此时执行多数派写，那么集群中的值将被改写为 3；</li>
</ul>
<p>这样就出现了并发问题。</p>
<p>所以，为了解决这个问题，每个版本号只能被修改一次。在执行多数派写之前，应该再执行一次多数派读来查询当前要写入的版本号是否过期，如果过期了，那就重新进行一次多数派读。如下图：</p>
<p><img src="assets/e64679f0-465e-11ea-a2f4-17bdc34f15cb.jpg" alt="在这里插入图片描述" /></p>
<p>正常流程走下来的话，没有问题。但是这里依然存在一个隐藏的并发问题：如果右边进程和左边进程同时查询 v2 版本的写权限，那么依然会出现版本覆盖问题，因为两个进程都认为自己有 v2 版本的写权限。</p>
<p>所以，让客户端来控制是否写入是没有办法避免并发问题的，只能把判断是否有写入权限的能力交给集群本身。而这就需要集群具有区分客户端的能力。也就是是，每个客户端需要有一个唯一 ID，集群来决定某个客户端是否可以对值进行修改。</p>
<h5><strong>4.4.4 客户端版本号</strong></h5>
<p>如图：这里使用下划线表示节点允许哪个客户端进行操作，节点下方有蓝色的线，表明允许左侧进程执行写操作；有黄色的线表明允许右侧进行执行写操作。</p>
<p><img src="assets/eb4306d0-465e-11ea-814b-0d3e32b9c16f.jpg" alt="在这里插入图片描述" /></p>
<p>简单地解释一下，左侧进程为 A，右侧进程为 B，节点分别为 a、b、c：</p>
<ol>
<li>A 执行多数派读，获得 a 和 b 的写权限。</li>
<li>B 执行多数派读，获得 b 和 c 的写权限。这里 b 叛变了，此时 A 失去了 b 的写权限。</li>
<li>A 和 B 分别执行写前查询，判断 v2 是否已经写过，得到可以写入的回应。</li>
<li>A 开始执行写操作，但是因为只有 a 允许 A 写入，不满足大多数，所以 A 写入失败。</li>
<li>B 开始执行写操作，b 和 c 都具有写入权限，写入成功。</li>
</ol>
<p>如果更进一步的提高算法性能，第三步中，A 其实已经不具备写入权限了，不应该执行第 4 步。</p>
<p>A 失败以后会怎么样呢? 提升自己的写入版本号，重新发起写入流程。此时写入的就是 v3 版本，在新的流程中，A 会拿到 v2 版本的值，再进行计算。所以最终会得到正确的结果，不会存在并发问题。</p>
<p>而这：就是 Paxos 的来源。</p>
<h3>5. Paxos</h3>
<h4>5.1 初识</h4>
<p>Paxos 是 Lamport（没错又是他） 1998 年在 <em>The Part-Time Parliament</em> 论文中描述的一个算法，最初使用希腊的一个小岛 Paxos 作为比喻（拜占庭将军问题的描述手法），描述了 Paxos 岛中通过决议的流程，并以此命名这个算法，但是这个描述理解起来比较困难，也没有引起很大的反响。2001 年，Lamport 觉得同行不能理解他的幽默感，于是重新发表了朴实的算法描述版 本<em>Paxos Made Simple</em>，简单直接的讲解了该算法。</p>
<p>Paxos 解决的是分布式系统下的共识问题：一个集群如何对一个 key 的 value 是什么达成共识，确定出一个唯一值。</p>
<h4>5.2 特点和前提</h4>
<h5><strong>5.2.1 特点</strong></h5>
<ul>
<li>解决分布式系统如何对一个值达成共识的问题</li>
<li>保证分布式系统中值的正确性</li>
<li>基于多数派读写</li>
<li>使用两轮 RPC 进行决策</li>
<li>一个值被确定后不能修改</li>
<li>强一致性</li>
</ul>
<h5><strong>5.2.2 前提</strong></h5>
<ul>
<li>假设磁盘可靠</li>
<li>假设不存在拜占庭将军问题</li>
<li>允许消息丢失</li>
<li>允许消息乱序</li>
</ul>
<h4>5.3 算法描述</h4>
<p>Paxos 使用两阶段 RPC 来对一个值达成共识，第一阶段 RPC 主要是用来确定自己是否有权限执行"写入"操作；第二阶段 RPC 是执行"写入"操作，和上一部分所讲的多数派读写基本一致。</p>
<p>其中，发请求的节点被称之为 Proposer，而接收请求的节点称之为 Acceptor，当 Acceptor 最终确定了一个值后，会发送给所有的 Learner，最终集群中所有的节点都持有最新被确定的值。</p>
<h5><strong>5.3.1 算法成员</strong></h5>
<ul>
<li>Proposer：发起 Paxos 的进程；</li>
<li>Acceptor：存储节点，接受、处理和存储消息；</li>
<li>Learner：学习 Acceptor已经接受的值。多数情况下，Acceptor 就是 learner。</li>
</ul>
<p>Paxos 并没有规定哪些节点时 Proposer，哪些节点时 Acceptor，也没有规定各个角色的数量。所以每一轮 Paxos 的角色数量任意，节点属于哪个角色也任意，同时允许身兼数职。</p>
<h5><strong>5.3.2 算法里的一些概念</strong></h5>
<ul>
<li>Round：1 轮 Paxos，包含 2 个阶段: Phase-1 和 Phase-2。</li>
<li>rnd：每 1 轮的编号，单调递增; 后写胜出; 全局唯一（用于区分 Proposer）。</li>
<li>last_rnd：Acceptor 收到的最大 rnd，记住这个值来识别哪个 Proposer 拥有写入权限。</li>
<li>value：Acceptor 接受的值。</li>
<li>v-rnd：Acceptor 接受的 value 所在的 rnd。</li>
<li>Quorum（Acceptor 的多数派）：n/2+1 个 Acceptors。</li>
</ul>
<h5><strong>5.3.3 具体算法</strong></h5>
<p><strong>一阶段</strong></p>
<p>Proposer：</p>
<ul>
<li>全局 rnd + 1，发送一阶段 RPC，并等待应答；</li>
<li>如果应答中的某个 last_rnd 大于发出的 rnd，提升 rnd 重新开始；</li>
<li>如果应答不够多数派，提升 rnd 重新开始；</li>
<li>发送二阶段 RPC。</li>
</ul>
<p>Acceptor</p>
<ul>
<li>如果请求中 rnd 比 Acceptor 的 last_rnd 小，跳转到第三步；</li>
<li>设置 last_rnd 为 rnd，并承诺从此这个 Acceptor 只接受不小于这个 rnd 的 phase-2 请求；</li>
<li>返回当前 last-rnd、v 和 v-rnd 的值。</li>
</ul>
<p>如下图：假设存在 1 个 Proposer p 和 3 个 Acceptor a、b、c（集群成员数一般都是基数，这里为了简化算法，所以只有 4 个），每一个 Acceptor 需要记录三个值：lase_rnd、value 和 v-rnd。</p>
<p><img src="assets/f3ca8f30-465e-11ea-b539-4302b67c89d7.jpg" alt="在这里插入图片描述" /></p>
<ol>
<li>Proposer p 提升全局 rnd 为 1，向所有 Acceptor 发送一阶段 RPC；</li>
<li>Acceptor a 和 b 收到请求，但是 c 没有收到，a 和 b 按照要求修改自己的 last_rnd 并返回；</li>
<li>Proposer p 收到了大多数的响应并且所有的 last_rnd 都不大于自己的，所以准备发起二阶段。</li>
</ol>
<p><strong>二阶段</strong></p>
<p>Proposer：</p>
<ul>
<li>从所有应答中选择 vrnd 最大的 v；</li>
<li>如果所有应答的 v 都是空，可以自由选择自己要写入的 v ；</li>
<li>发起二阶段 RPC 并等待响应；</li>
<li>如果获得了半数以上的成功响应，本轮 Paxos 结束；</li>
<li>否则继续提升 rnd，重新开启一轮 Paxos。</li>
</ul>
<p>Acceptor</p>
<ul>
<li>拒绝 rnd 小于 last_rnd 的请求；</li>
<li>将请求中的 v 和 rnd 写入本地，此时，v 为本节点“接受的值”。</li>
</ul>
<p><img src="assets/0028c210-465f-11ea-90d3-f11cd86d32dc.jpg" alt="在这里插入图片描述" /></p>
<p>如图：</p>
<ul>
<li>Proposer p 的一阶段响应中所有的 v 都是空，所以自己可以决定要写入的值；</li>
<li>Proposer p 发起二阶段 RPC，v = 1，rnd = 1；</li>
<li>Acceptor a 和 b 收到请求，rnd 符合要求，于是写入 v 和 v-rnd，并返回成功，c 依然没有收到请求。</li>
<li>Proposer p 收到了半数以上的写入成功响应，本轮 Paxos 结束。</li>
</ul>
<p>上面就是很简单的 Paxos 共识算法的过程，下面来看一下一个 5 节点 2 Proposer 的完整 Paxos 流程。</p>
<h5><strong>5.3.4 完整的 Paxos 流程</strong></h5>
<p>如下图：左右两侧是两个 Proposer x 和 y， 中间是三个 Acceptor a、b、c。其中，x 希望值为 1 而 y 希望值为 2。</p>
<p><img src="assets/105031f0-465f-11ea-90d3-f11cd86d32dc.jpg" alt="在这里插入图片描述" /></p>
<p>第一轮 Paxos：</p>
<ul>
<li>x 发起一阶段 RPC，rnd = 1；</li>