| title | categories | tags | abbrlink | date | ||||
|---|---|---|---|---|---|---|---|---|
分布式理论 |
|
|
41166861 |
2021-11-08 00:15:33 -0800 |
- 性能：用于衡量一个系统处理各种任务的能力。
- 吞吐量：系统在一定时间内可以处理的任务数。
- QPS，即每秒查询数
- TPS，即每秒事务数
- 响应时间：系统响应一个请求或输入需要花费的时间。
- 吞吐量：系统在一定时间内可以处理的任务数。
- 可用性：指的是系统在面对各种异常时可以正确提供服务的能力。系统的可用性可以用系统停止服务的时间与总的时间之比衡量。
- 可扩展性：指的是分布式系统通过扩展集群机器规模提高系统性能 (吞吐、响应时间、 完成时间)、存储容量、计算能力的特性，是分布式系统的特有性质。
- 分布式计算：解决应用的分布式计算问题。基于分布式计算模式，包括批处理计算、离线计算、在线计算、融合计算等，根据应用类型构建高效智能的分布式计算框架。
- 分布式存储：解决数据的分布式和多元化问题。包括分布式数据库、分布式文件系统、分布式缓存等，支持不同类型的数据的存储和管理。
- 分布式通信：解决进程间的分布式通信问题。通过消息队列、远程调用等方式，实现简单高效的通信。
- 分布式资源管理：解决资源的分布式和异构性问题。将 CPU、内存、IO 等物理资源虚拟化，新城逻辑资源池，以便统一管理。
CAP 定理是加州大学计算机科学家埃里克·布鲁尔提出来的猜想，后来被证明成为分布式计算领域公认的定理。
CAP 定理，指的是：在一个分布式系统中， 最多只能同时满足其中两项。
CAP 就是取 Consistency、Availability、Partition Tolerance 的首字母而命名。
- 一致性（Consistency）：在任何给定时间，网络中的所有节点都具有完全相同（最近）的值。
- 可用性（Availability）：对网络的每个请求都会收到响应，但不能保证返回的数据是最新的。
- 分区容错性（Partition Tolerance）：即使任意数量的节点出现故障，网络仍会继续运行。
一致性（Consistency）指的是多个数据副本是否能保持一致的特性。
在一致性的条件下，分布式系统在执行写操作成功后，如果所有用户都能够读取到最新的值，该系统就被认为具有强一致性。
数据一致性又可以分为以下几点：
- 强一致性 - 数据更新操作结果和操作响应总是一致的，即操作响应通知更新失败，那么数据一定没有被更新，而不是处于不确定状态。
- 最终一致性 - 即物理存储的数据可能是不一致的，终端用户访问到的数据可能也是不一致的，但系统经过一段时间的自我修复和修正，数据最终会达到一致。
举例来说，某条记录是 v0，用户向 G1 发起一个写操作，将其改为 v1。
接下来，用户的读操作就会得到 v1。这就叫一致性。
问题是，用户有可能向 G2 发起读操作，由于 G2 的值没有发生变化，因此返回的是 v0。G1 和 G2 读操作的结果不一致，这就不满足一致性了。
为了让 G2 也能变为 v1，就要在 G1 写操作的时候，让 G1 向 G2 发送一条消息，要求 G2 也改成 v1。
这样的话，用户向 G2 发起读操作，也能得到 v1。
可用性指分布式系统在面对各种异常时可以提供正常服务的能力，可以用系统可用时间占总时间的比值来衡量，4 个 9 的可用性表示系统 99.99% 的时间是可用的。
在可用性条件下，系统提供的服务一直处于可用的状态，对于用户的每一个操作请求总是能够在有限的时间内返回结果。
分区容错性（Partition Tolerance）指 分布式系统在遇到任何网络分区故障的时候，仍然需要能对外提供一致性和可用性的服务，除非是整个网络环境都发生了故障。
在一个分布式系统里面，节点组成的网络本来应该是连通的。然而可能因为一些故障，使得有些节点之间不连通了，整个网络就分成了几块区域。数据就散布在了这些不连通的区域中，这就叫分区。
假设，某个数据项只在一个节点中保存，那么分区出现后，和这个节点不连通的部分就访问不到这个数据了。这时分区就是无法容忍的。
提高分区容错性的办法就是一个数据项复制到多个节点上，那么出现分区之后，这一数据项就可能分布到各个区里。容错性就提高了。
然而，要把数据复制到多个节点，就会带来一致性的问题，就是多个节点上面的数据可能是不一致的。要保证一致，每次写操作就都要等待全部节点写成功，而这等待又会带来可用性的问题。
总的来说就是，数据存在的节点越多，分区容错性越高，但要复制更新的数据就越多，一致性就越难保证。为了保证一致性，更新所有节点数据所需要的时间就越长，可用性就会降低。
大多数分布式系统都分布在多个子网络，每个子网络就叫做一个区（Partition）。分区容错的意思是，区间通信可能失败。比如，一台服务器放在中国，另一台服务器放在美国，这就是两个区，它们之间可能无法通信。
上图中，G1 和 G2 是两台跨区的服务器。G1 向 G2 发送一条消息，G2 可能无法收到。系统设计的时候，必须考虑到这种情况。
一般来说，分区容错无法避免，因此可以认为 CAP 的 P 总是成立。CAP 定理告诉我们，剩下的 C 和 A 无法同时做到。
在分布式系统中，分区容错性必不可少，因为需要总是假设网络是不可靠的。因此，CAP 理论实际在是要在可用性和一致性之间做权衡。
由于分布式数据存储（如区块链）的性质，分区容错性是一个既定的事实；网络中总会有失败/无法访问的节点（尤其是因为互联网的不稳定特性）。 CAP 定理指出，当存在 P（分区）时，必须在 C（一致性）或 A（可用性）之间进行选择。
（1）AP 模式
AP 模式：对网络的每个请求都会收到响应，即使网络由于网络分区故障而无法保证它是最新的。
选择 AP 模式，实现了服务的高可用。用户访问系统的时候，都能得到响应数据，不会出现响应错误；但是，当出现分区故障时，相同的读操作，访问不同的节点，得到响应数据可能不一样。
（2）CP 模式
CP 模式：如果由于网络分区（故障节点）而无法保证特定信息是最新的，则系统将返回错误或超时。
选择 CP 模式，这样能够提供一部分的可用性。采用 CP 模型的分布式系统，一旦因为消息丢失、延迟过高发生了网络分区，就影响用户的体验和业务的可用性。因为为了防止数据不一致，集群将拒绝新数据的写入。
BASE 定理是对 CAP 中一致性和可用性权衡的结果。
BASE 是 基本可用（Basically Available）、软状态（Soft State） 和 最终一致性（Eventually Consistent） 三个短语的缩写。
BASE 理论的核心思想是：即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性。
- **基本可用（Basically Available）**分布式系统在出现故障的时候，保证核心可用，允许损失部分可用性。例如，电商在做促销时，为了保证购物系统的稳定性，部分消费者可能会被引导到一个降级的页面。
- 软状态（Soft State）指允许系统中的数据存在中间状态，并认为该中间状态不会影响系统整体可用性，即允许系统不同节点的数据副本之间进行同步的过程存在延时。
- 最终一致性（Eventually Consistent）强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能达到一致的状态。
BASE 的理论的核心思想是：即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性。
ACID 要求强一致性，通常运用在传统的数据库系统上。而 BASE 要求最终一致性，通过牺牲强一致性来达到可用性，通常运用在大型分布式系统中。
在实际的分布式场景中，不同业务单元和组件对一致性的要求是不同的，因此 ACID 和 BASE 往往会结合在一起使用。
随着时间的推移，每一条都会被证明是错误的，也都会导致严重的问题，以及痛苦的学习体验：
- 网络是稳定的
- 网络传输的延迟是零
- 网络的带宽是无穷大
- 网络是安全的
- 网络的拓扑不会改变
- 只有一个系统管理员
- 传输数据的成本为零
- 整个网络是同构的
为什么我们要深刻地认识这 8 个错误？
是因为，这要我们清楚地认识到——在分布式系统中，错误是不可能避免的。既然错误无可避免，那么，我们应该做的是，将容错也作为功能去实现。
拜占庭将军问题是由莱斯利·兰波特在其同名论文中提出的分布式对等网络通信容错问题。
在分布式计算中，不同的节点通过通讯交换信息达成共识而按照同一套协作策略行动。但有时候，系统中的节点可能出错而发送错误的信息，用于传递信息的通讯网络也可能导致信息损坏，使得网络中不同的成员关于全体协作的策略得出不同结论，从而破坏系统一致性。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。
一群拜占庭将军各领一支军队共同围困一座城市。
为了简化问题，军队的行动策略只有两种：进攻（Attack，后面简称 A）或 撤退（Retreat，后面简称 R）。如果这些军队不是统一进攻或撤退，就可能因兵力不足导致失败。因此，将军们通过投票来达成一致策略：同进或同退。
因为将军们分别在城市的不同方位，所以他们只能通过信使互相联系。在投票过程中，每位将军都将自己的投票信息（A 或 R）通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以分析出共同的投票结果而决定行动策略。
这个抽象模型的问题在于：将军中可能存在叛徒，他们不仅会发出误导性投票，还可能选择性地发送投票信息。
由于将军之间需要通过信使通讯，叛变将军可能通过伪造信件来以其他将军的身份发送假投票。而即使在保证所有将军忠诚的情况下，也不能排除信使被敌人截杀，甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通讯可靠性来解决问题。
假使那些忠诚（或是没有出错）的将军仍然能通过多数决定来决定他们的战略，便称达到了拜占庭容错。在此，票都会有一个默认值，若消息（票）没有被收到，则使用此默认值来投票。
上述的故事可以映射到分布式系统中，将军代表分布式系统中的节点；信使代表通信系统；叛徒代表故障或异常。
兰伯特针对拜占庭将军问题，给出了两个解决方案：口头协议和书面协议。
本文介绍一下口头协议。
在口头协议中，拜占庭将军问题被简化为将军 - 副官模型，其核心规则如下：
- 忠诚的副官遵守同一命令。
- 若将军是忠诚的，所有忠诚的副官都执行他的命令。
- 如果叛徒人数为 m，将军人数不能少于 3m + 1 ，那么拜占庭将军问题就能解决了。
示例一、叛徒人数为 1，将军人数为 3
这个示例中，将军人数不满足 3m + 1，无法保证忠诚的副官都执行将军的命令。
示例二、叛徒人数为 1，将军人数为 4
这个示例中，将军人数满足 3m + 1，无论是副官中有叛徒，还是将军是叛徒，都能保证忠诚的副官执行将军的命令。
- Wiki - 拜占庭将军问题
- 拜占庭将军问题视频讲解 - 李永乐老师讲解的通俗易懂
- Fallacies of Distributed Computing - 分布式系统新手常犯的 8 个错误，并探讨了其会带来的影响。
- Distributed Systems for Fun and Profit - 一本学习小册，涵盖了分布式系统中的关键问题，包括时间的作用和不同的复制策略。
- A Note on Distributed Systems - 这是一篇经典的论文，讲述了为什么在分布式系统中，远程交互不能像本地对象那样进行。
- Amazon’s Highly Available Key-value Store
- CAP Theorem
- CAP twelve years later: How the "rules" have changed
- CAP 定理的含义 - by 阮一峰
- 神一样的 CAP 理论被应用在何方
- BASE: An Acid Alternative