* [分布式系统理论进阶：Paxos变种和优化 ](docs/distributed/basic/分布式系统理论进阶：Paxos变种和优化.md)

* [分布式系统理论基础：zookeeper分布式协调服务 ](docs/distributed/basic/分布式系统理论基础：zookeeper分布式协调服务.md)

* [搞懂分布式技术：分布式系统的一些基本概念](docs/distributed/practice/搞懂分布式技术：分布式系统的一些基本概念.md )


2 writen(int fd, const void *vptr, size_t n)

3 {

4 size_t nleft;

18 nleft -= nwritten; 19 ptr += nwritten; 20 } 21 return(n); 22 } 23 /* end writen */

24

25 void



2 readn(int fd, void *vptr, size_t n)

3 {

4 size_t nleft;

23 } 24 /* end readn */

25

26 ssize_t 27 Readn(int fd, void *ptr, size_t nbytes) 28 { 29 ssize_t n; 30


本文转自：https://www.cnblogs.com/bangerlee/p/5328888.html

本系列文章将整理到我在GitHub上的《Java面试指南》仓库，更多精彩内容请到我的仓库里查看

如果对本系列文章有什么建议，或者是有什么疑问的话，也可以关注公众号【Java技术江湖】联系作者，欢迎你参与本系列博文的创作和修订。

<!-- more -->

CAP是分布式系统、特别是分布式存储领域中被讨论最多的理论，“[什么是CAP定理？](https://www.quora.com/What-Is-CAP-Theorem-1)”在Quora 分布式系统分类下排名 FAQ 的 No.1。CAP在程序员中也有较广的普及，它不仅仅是“C、A、P不能同时满足，最多只能3选2”，以下尝试综合各方观点，从发展历史、工程实践等角度讲述CAP理论。希望大家透过本文对CAP理论有更多地了解和认识。

CAP由[Eric Brewer](https://en.wikipedia.org/wiki/Eric_Brewer_(scientist))在2000年PODC会议上提出^[1][2]，是Eric Brewer在Inktomi^[3]期间研发搜索引擎、分布式web缓存时得出的关于数据一致性(consistency)、服务可用性(availability)、分区容错性(partition-tolerance)的猜想：

CAP理论提出7、8年后，NoSql圈将CAP理论当作对抗传统关系型数据库的依据、阐明自己放宽对数据一致性(consistency)要求的正确性^[6]，随后引起了大范围关于CAP理论的讨论。

CAP理论看似给我们出了一道3选2的选择题，但在工程实践中存在很多现实限制条件，需要我们做更多地考量与权衡，避免进入CAP认识误区^[7]。

Partition字面意思是网络分区，即因网络因素将系统分隔为多个单独的部分，有人可能会说，网络分区的情况发生概率非常小啊，是不是不用考虑P，保证CA就好^[8]。要理解P，我们看回CAP证明^[4]中P的定义：

P 是必选项，那3选2的选择题不就变成数据一致性(consistency)、服务可用性(availability) 2选1？工程实践中一致性有不同程度，可用性也有不同等级，在保证分区容错性的前提下，放宽约束后可以兼顾一致性和可用性，两者不是非此即彼^[12]。

工程实践中，较常见的做法是通过异步拷贝副本(asynchronous replication)、quorum/NRW，实现在调用端看来数据强一致、被调端最终一致，在调用端看来服务可用、被调端允许部分节点不可用(或被网络分隔)的效果^[15]。

CAP理论对实现分布式系统具有指导意义，但CAP理论并没有涵盖分布式工程实践中的所有重要因素。

例如延时(latency)，它是衡量系统可用性、与用户体验直接相关的一项重要指标^[16]。CAP理论中的可用性要求操作能终止、不无休止地进行，除此之外，我们还关心到底需要多长时间能结束操作，这就是延时，它值得我们设计、实现分布式系统时单列出来考虑。

延时与数据一致性也是一对“冤家”，如果要达到强一致性、多个副本数据一致，必然增加延时。加上延时的考量，我们得到一个CAP理论的修改版本PACELC^[17]：如果出现P(网络分区)，如何在A(服务可用性)、C(数据一致性)之间选择；否则，如何在L(延时)、C(数据一致性)之间选择。

以上介绍了CAP理论的源起和发展，介绍了CAP理论给分布式系统工程实践带来的启示。

[19] [How to beat the CAP theorem](http://nathanmarz.com/blog/how-to-beat-the-cap-theorem.html), nathanmarz , 2011

本文转自 https://www.cnblogs.com/bangerlee/p/5268485.html

本系列文章将整理到我在GitHub上的《Java面试指南》仓库，更多精彩内容请到我的仓库里查看

一致性是分布式理论中的根本性问题，近半个世纪以来，科学家们围绕着一致性问题提出了很多理论模型，依据这些理论模型，业界也出现了很多工程实践投影。下面我们从一致性问题、特定条件下解决一致性问题的两种方法(2PC、3PC)入门，了解最基础的分布式系统理论。

何为一致性问题？简单而言，一致性问题就是相互独立的节点之间如何达成一项决议的问题。分布式系统中，进行数据库事务提交(commit transaction)、Leader选举、序列号生成等都会遇到一致性问题。这个问题在我们的日常生活中也很常见，比如牌友怎么商定几点在哪打几圈麻将：

……

（第二天凌晨3点） 隔壁老王: 没问题！ // 消息延迟

我: ……

我: ……

我: 老李头，今晚7点老地方，搓够48圈不见不散！

_《怦然心动 (Flipped)》，2010_

工程实践上根据具体的业务场景，或保证强一致(safety)，或在节点宕机、网络分化的时候保证可用(liveness)。2PC、3PC是相对简单的解决一致性问题的协议，下面我们就来了解2PC和3PC。

2PC(tow phase commit)两阶段提交^[5]顾名思义它分成两个阶段，先由一方进行提议(propose)并收集其他节点的反馈(vote)，再根据反馈决定提交(commit)或中止(abort)事务。我们将提议的节点称为协调者(coordinator)，其他参与决议节点称为参与者(participants, 或cohorts)：

从coordinator接收到一次事务请求、发起提议到事务完成，经过2PC协议后增加了2次RTT(propose+commit)，带来的时延(latency)增加相对较少。

3PC(three phase commit)即三阶段提交^[6][7]，既然2PC可以在异步网络+节点宕机恢复的模型下实现一致性，那还需要3PC做什么，3PC是什么鬼？

因为有了准备提交(prepare to commit)阶段，3PC的事务处理延时也增加了1个RTT，变为3个RTT(propose+precommit+commit)，但是它防止participant宕机后整个系统进入阻塞态，增强了系统的可用性，对一些现实业务场景是非常值得的。

以上介绍了分布式系统理论中的部分基础知识，阐述了一致性(consensus)的定义和实现一致性所要面临的问题，最后讨论在异步网络(asynchronous)、节点宕机恢复(fail-recover)模型下2PC、3PC怎么解决一致性问题。

[6][Consensus Protocols: Three-phase Commit](http://the-paper-trail.org/blog/consensus-protocols-three-phase-commit/),Henry Robinson, 2008

转自：https://www.cnblogs.com/bangerlee/p/5448766.html

本系列文章将整理到我在GitHub上的《Java面试指南》仓库，更多精彩内容请到我的仓库里查看

现实生活中时间是很重要的概念，时间可以记录事情发生的时刻、比较事情发生的先后顺序。分布式系统的一些场景也需要记录和比较不同节点间事件发生的顺序，但不同于日常生活使用物理时钟记录时间，分布式系统使用逻辑时钟记录事件顺序关系，下面我们来看分布式系统中几种常见的逻辑时钟。

可能有人会问，为什么分布式系统不使用物理时钟(physical clock)记录事件？每个事件对应打上一个时间戳，当需要比较顺序的时候比较相应时间戳就好了。

这是因为现实生活中物理时间有统一的标准，而分布式系统中每个节点记录的时间并不一样，即使设置了[NTP](http://www.zhihu.com/question/24960940)时间同步节点间也存在毫秒级别的偏差^[1][2]。因而分布式系统需要有另外的方法记录事件顺序关系，这就是逻辑时钟(logical clock)。

[Leslie](https://en.wikipedia.org/wiki/Leslie_Cheung)[Lamport](https://en.wikipedia.org/wiki/Leslie_Lamport)在1978年提出逻辑时钟的概念，并描述了一种逻辑时钟的表示方法，这个方法被称为Lamport时间戳(Lamport timestamps)^[3]。

通过以上定义，我们可以对所有事件排序、获得事件的[全序关系](https://en.wikipedia.org/wiki/Total_order)(total order)。上图例子，我们可以从C1到A4进行排序。

Lamport时间戳帮助我们得到事件顺序关系，但还有一种顺序关系不能用Lamport时间戳很好地表示出来，那就是同时发生关系(concurrent)^[4]。例如图1中事件B4和事件C3没有因果关系，属于同时发生事件，但Lamport时间戳定义两者有先后顺序。

如果T_b[Q] > T_a[Q] 并且 T_b[P] < T_a[P]，则认为a、b同时发生，记作 a <-> b。例如图2中节点B上的第4个事件 (A:2，B:4，C:1) 与节点C上的第2个事件 (B:3，C:2) 没有因果关系、属于同时发生事件。

基于Vector clock我们可以获得任意两个事件的顺序关系，结果或为先后顺序或为同时发生，识别事件顺序在工程实践中有很重要的引申应用，最常见的应用是发现数据冲突(detect conflict)。

解决该问题的方法是使用server id取代client id创建vector (因为server的数量相对client稳定)，或设定最大的size、如果超过该size值则淘汰最旧的vector信息^[10][13]。

以上介绍了分布式系统里逻辑时钟的表示方法，通过Lamport timestamps可以建立事件的全序关系，通过Vector clock可以比较任意两个事件的顺序关系并且能表示无因果关系的事件，将Vector clock的方法用于发现数据版本冲突，于是有了Version vector。

[12][Why Vector Clocks Are Hard](http://basho.com/posts/technical/why-vector-clocks-are-hard/), Justin Sheehy, 2010