distributed-system

分布式、集群

属性

可靠性

可靠性（Reliability）是指系统可以无故障地持续运行。与可用性相反，可靠性是根据时间间隔而不是任何时刻来进行定义的。可靠性相关的几个指标如下：

可靠性（Reliability）是指系统可以无故障地持续运行。与可用性相反，可靠性是根据时间间隔而不是任何时刻来进行定义的。可靠性相关的几个指标如下：

MTBF（Mean Time Between Failure）
即平均无故障时间，是指从新的产品在规定的工作环境条件下开始工作到出现第一个故障的时间的平均值。MTBF越长表示可靠性越高，正确工作能力越强 。

MTTR（Mean Time To Repair）
即平均修复时间，是指可修复产品的平均修复时间，就是从出现故障到修复中间的这段时间。MTTR越短表示易恢复性越好。

MTTF（Mean Time To Failure）
即平均失效时间。系统平均能够正常运行多长时间，才发生一次故障。系统的可靠性越高，平均无故障时间越长。

这些指标跟可用性关系
Availability = UpTime/(UpTime+DownTime) = MTBF / (MTBF + MTTR)

可用性

可用性（Availability）被定义为系统的一个属性，它说明系统已准备好，马上就可以使用。换句话说，高度可用的系统在任何给定的时刻都能及时地工作。关注的是服务总体的持续时间，系统在给定时间内总体的运行时间越长，可用性越高。

一致性

区分

可靠性和可用性的区别

我们举个一个例子来说明二者的区别。如果系统在每小时崩溃1ms，那么它的可用性就超过99.9999%，但是它还是高度不可靠，因为它只能无故障运行1小时。与之类似，如果一个系统从来不崩溃，但是每年要停机两星期，那么它是高度可靠的，但是可用性只有96%。

简单来说，可靠性强调正常运行的持续时长，而可用性关注正常运行时间的比例。

分布式和集群的区别

形式

从形式上来说，集群是个物理形态，分布式是一种工作模式。他们并不是同一个维度的概念。

  • 集群一般是物理集中、统一管理的，而分布式则不关心这一点。
  • 分布式是相对中心化而来的，强调的是任务在多个物理隔离的节点上进行。中心化带来的问题是可靠性和可用性，一但中心出问题，整个系统不可用。分布式主要解决这个问题，除此之外，也通常倾向分散负载。但分布式也会带来问题，最主要的是一致性问题。

用通俗的话来说，就是“分头做事”和”一群人“的区别。

作用

  • 分布式：不同的业务模块部署在不同的服务器上或者同一个业务模块分拆多个子业务，部署在不同的服务器上，解决高并发的问题
  • 集群：同一个业务部署在多台机器上，提高系统可用性

分布式是以缩短单个任务的执行时间来提升效率的，而集群则是通过提高单位时间内执行的任务数来提升效率。

Replication Type

Single Leader

  1. Synchronous Replication
  2. Asynchronous Replication
  3. Semisynchronous Replication

起因

什么是分布式系统？

相较于单服务器来说，分布式系统就是拥有多个服务器。多个服务器之间互相通过网络同步，从外界看来就像是使用单机服务器。

为什么要设计分布式系统？

  • 提高性能
  • 更高容错
  • 更易扩展

分布式系统分类

  • 同步系统：synchronous
  • 异步系统：asynchronous
  • 半同步系统：semi-synchronous

分布式的难点

由于是多个服务器，就有多份数据副本，多个副本就理所当然的需要数据同步，数据怎么同步，什么时候同步，这就涉及一致性的问题。

由于分布式不是单机，是遍布各地多个服务器，就需要涉及网络来同步数据，这就涉及到网络的所有可能出现的问题，比如

  • 网络延迟
  • 数据丢失
  • 网络分区

分析下来，主要难点是数据一致性和网络分区的问题。

当如还有其他问题，如

  • 部分服务器故障
  • 服务器没有统一时钟

一致性：Consistency

一致性最早并不是在分布式系统领域提出，而是并发领域。如CPU的缓存一致性，为了缓解CPU和内存的速度差异而出现的CPU缓存，而CPU衍生出多核CPU就出现了CPU缓存一致性的问题。本质是就是多个副本的同步问题。那为什么CPU一致性没有分布式那么难以解决呢？主要是CPU缓存同步不涉及网络，延迟和分区的问题是可以保证的，仅仅通过总线嗅探和MESI协议就可以实现缓存一致性。

以下讨论以分布式系统为例。

一致性模型

有如下常用的模型

  1. 线性一致性：Linearizable Consistency
  2. 顺序一致性：Sequential Consistency
  3. 因果一致性：Causal Consistency
  4. 最终一致性：Eventual Consistency

上面提到，数据同步的问题。而一致性就是系统给予用户对于数据的保证。这个怎么理解呢？

  • 拿线性一致性来说，系统会将所有用户的请求按顺序进行操作，这就保证了所有用户都能看到最新的结果，是最符合咱们理解的一致性。

  • 而顺序一致性只保证了当个用户的请求的顺序，系统保证了某

  • 用户的请求的顺序。但是不同用户的请求的顺序不能保证。举个例子，你的好友A优先请求，随后你看到A请求了，跟着请求。但系统的执行顺序可能是有限执行你的请求。但你的下一个请求，一定是在你的上一个请求之前执行。

  • 因果一致性就只保证了有逻辑关系的请求的顺序。

  • 最终一致性只保证所有服务器最终会达成相同状态。

以上的一致性都是站在多个客户端的角度来说的，还有一部分一致性模型是以客户端为中心的模型，如

  • 单调读：每次读都保证后续的读读到非历史的值。
  • 单调写
  • 读你所写
  • PRAM（Pipelined RAM）
  • 读后写

一致性与现实

顺序一致性：拿网购为例，现在我和A都在抢一个商品，商品仅剩一件。如果我优先发起订单，按照常理来说，一定是我买到了这件商品。但是，如果没有一致性保证，就不一定是我买到了。例如，顺序一致性。它可能优先处理A的订单，也就导致虽然我先发起订单，但没有买到，反而是后发起订单的A买到了该商品。

最终一致性：再举个例子，假如你账户上余额为0元，你给账户充值了100，然后查询，看到自己账户余额已经变成了100，安心离开。过一会你想取点钱，一查，账户变为0元了。这时你会怎么想？我明明已经充值了100，会不会是被盗刷了？而实际上，可能是系统返回了之前账户充值100元之前的余额，也就是0元。

要研究一致性，科研人员提出了一些定理对于一致性进行约束。

告诉什么情况是不可能的，不要在这方面浪费时间精力，如CAP， FLP，PACELC等定理。

给出了一些建议性的定理，如BASE，Quorum定理。

CAP定理

CAP指的如下三个性质

  • Consistency（一致性（在这里指线性一致性））：每次都能获取最新数据。
  • Availability（可用性）：每次请求都能获取到非错的响应，但可能不是最新。
  • Partition Tolerance：分区容错性。如果网络分区（网路不可达），就需要在C和A之间做出取舍。

CAP指出，对于分布式系统只能满足三项中的两项而不可能满足全部三项。

当没有分区时，就可以满足C和A。但出现网络分区时，要保证分区容错的话，就只能C和A二选一。

举个例子，服务器A接到新请求，准备同步给其他服务器，但此时A，B之间发生了网络分区。A接到的新请求无法被B看见，此时，B服务器来了个一个查看请求，就需要在Consistency和Availability之前做取舍，是选择Availability，直接返回当前查询的结果（不是最新的），还是保证Consistency，即等服务器A和B之前的网络分区消失，网络恢复正常，B再返回最新的结果。

CAP定理告诉我们不要将精力浪费在如何设计能满足三者的完美分布式系统，而是应该进行取舍。

PACELC定理

PACELC定理是CAP定理的扩展，字母PAC即CAP， 而E是else， L代表Delay， C是Consistency。

CAP主要说的是网络分区时的取舍，PACELC还扩展了非分区的情况。

  • 网络分区时，选择Consistency还是Availability。
  • 网络正常时，选择Delay（网络延迟）还是Availability。

还是上面那个服务器AB的例子，当A接受到新请求时，B随后接受到查询请求，这时候B是选择直接返回当前结果（Availability），还是等A同步完数据再返回。（Delay）。

BASE定理

BASE（Basically Availability, Soft State, Eventual Consistency.）是基本可用、软状态、最终一致性的首字母缩写。是在网络分区时，采用最终一致性，选择了高可用性。

虽然网络分区听起来很严重，但大部分情况只会存在一小段时间，可能几秒或者几分钟。所以最终一致性是一种可以接受的方案，适用于一些允许延迟的场景，如帖子点赞数等。

Quorum冗余机制

Quorum指的是，在一个由N个节点组成的系统中，我们要求至少W个节点写入成功，并且需要同时从R个节点读取数据，只要W+R > N且W > N / 2, 则读取的R个返回值至少包含一个最新的值。

**简单说明: **

  • 由N个节点和至少W个节点写入成功，则失败的最多为 N - W个，而读取要求是 W+R > N即， R > N - W，这就保证了读取的R个数据中至少包含一个最新的数据。
  • 而W > N / 2 是为了节点们只能同时决策一个请求，用于串行化。

共识：Consensus

共识指的是分布式中服务器对一个数据达成一致。

共识算法指的是分布式系统同步数据，达成共识的方式。

共识可以解决分布式系统的一些困难，如

  • 原子提交
  • 选主
  • 互斥

FLP不可能定理

FLP不可能定理指的是，在一个完全异步的网络环境中，即使只有一个进程出现故障，也无法实现任何安全的共识算法。

FLP强调的是一个在一个完全异步的网络环境，因此，对于同步网络是可以设计算法达成共识的。

于是，有了如下方式改异步为同步，绕过FLP不可能定理。

  • 故障屏蔽。例如，如果一个进程崩溃，很长没收到回应。也认为他会恢复后（自动重启或者人工恢复）回应，只不过可能时间长一点。
  • 使用故障检测器。例如超时故障检测，当一段时间内服务器没有回应，就认为该服务器崩溃。
  • 使用随机性算法

条件

要设计一种分布式共识算法，需要满足以下三个条件

  • Termination: 所有正常的进程都会认同同一个值，不会出现一直在循环的进程。
  • Agreement: 所有正常的进程选择的值都是一样的。
  • Validity: 任何正常的进程确定的值v’, 那么v’肯定是某个进程提交的。比如随机数生成器就不满足这个性质.

后来演变成更精炼、更常用的两个属性

  • Safety：安全性，即所有正确的进程都认同一个值
  • Liveness：活性，即分布式系统最终会认同某一个值。

Raft

Raft是一种分布式共识算法。

解决分布式难题

上面我们提到三个分布式系统设计的难题，

  • 部分服务器故障
  • 服务器没有统一时钟
  • 网络延时

而Raft采用状态机复制解决上述问题

  • 网络延时、分区、丢包、重复、和重排序的情况下，不会返回错误的结果。
  • 状态机不依赖时钟。
  • 服务器故障问题，高可用性。一般来说，只要集群中超过半数节点正常运行，能够互相通信且同客户端通信，该集群就可用。

那Raft是怎么保证安全性和活性的呢？

安全性

活性

  • 选主活性：每个节点的选举超时时间都在一个范围随机波动，让无限次分割选票的概率无限小。
  • 日志活性：总有一个有效的leader被选出，而leader会将日志复制到其他节点。
  • 状态机活性：状态机 会将已提交的日志应用到状态机。

总结

一致性和共识的关系

一致性指的是多个节点数据之间的相同性。由于节点之间需要网络来同步数据，引入网络来同步数据的同时也引入了一些困难，而共识算法就是设计算法来解决这种些困难，保证数据的一致性。

即，一致性依赖于共识算法。

为什么要区分这两者呢？

从用户角度来说，只需要了解该分布式系统提供了怎么样的一致性，而无须关心怎么实现（共识算法）。

一致性哈希

要了解一致性哈希，就要了解它解决了什么问题。此次引用小林的文章。

作者：小林coding

原文地址：https://xiaolincoding.com/os/8_network_system/hash.html

哈希算法可以用于数据分片的分布式系统的负载均衡，将请求哈希后取模映射到对于的服务器节点上。

但普通的哈希算法，在应对节点扩容时，需要移动大量数据到新位置，最差情况下所有的数据都要移动。

一致性哈希就是为了解决这种问题。

一致性哈希要进行两步哈希：

  • 第一步：对存储节点进行哈希计算，也就是对存储节点做哈希映射，比如根据节点的 IP 地址进行哈希；
  • 第二步：当对数据进行存储或访问时，对数据进行哈希映射；

对数据哈希映射后，顺时针找到第一个节点，即该数据的服务节点。

一致性哈希是怎么解决节点增删的问题呢？

我们只需要将新节点加入哈希环，顺指针寻找上一个服务器，将自己负责的那部分数据复制过来，上一个服务器即可删除。删除节点同理，就完成了节点增删的过程。

从上述过程中不难发现，一致性哈希仅涉及一个原节点的数据变更。

但是一致性哈希算法并不保证节点能够在哈希环上分布均匀，这样就会带来一个问题，会有大量的请求集中在一个节点上。

这时候有一半以上的数据的寻址都会找节点 A，也就是访问请求主要集中的节点 A 上，这肯定不行的呀，说好的负载均衡呢，这种情况一点都不均衡。

另外，在这种节点分布不均匀的情况下，进行容灾与扩容时，哈希环上的相邻节点容易受到过大影响，容易发生雪崩式的连锁反应。

比如，上图中如果节点 A 被移除了，当节点 A 宕机后，根据一致性哈希算法的规则，其上数据应该全部迁移到相邻的节点 B 上，这样，节点 B 的数据量、访问量都会迅速增加很多倍，一旦新增的压力超过了节点 B 的处理能力上限，就会导致节点 B 崩溃，进而形成雪崩式的连锁反应。

所以，一致性哈希算法虽然减少了数据迁移量，但是存在节点分布不均匀的问题。

于是，就有了引入虚拟节点的一致性哈希算法。

虚拟节点

一个服务器节点不是对应单个哈希环中的节点，而是对应多个虚拟节点。

映射到虚拟节点的数据都交给对应服务器节点处理。

多个虚拟节点就更好的均匀了哈希环。

除此之外，还可以根据不同服务器的性能，给不同服务器分别不同的虚拟节点个数，性能更高的分配更多的虚拟节点，更好地实现负载均衡。

因此，带虚拟节点的一致性哈希方法不仅适合节点规模会发生变化的场景，而且适合硬件配置不同的节点的场景。

Articles
distributed-system
https://messenger1th.github.io/2024/07/24/Articles/distributed-system/
作者
Epoch
发布于
2024年7月24日
许可协议