近学习分布式感想随笔 | 珊瑚贝

Abstract

随着大数据人工智能时代的来临，互联网的快速发展。许许多多以前可能并不那么实际或需要的算法、技术也逐渐进入我们的眼中。例如分布式、集群、负载均衡、也越来越 “平民” 化。近期重新再一次的对于分布式理念、思想进行了学习。此随笔也因此而来。请多指教 为什么需要分布式？ 什么是分布式？ 分布式的核心理念是什么？ 如何实现分布式、负载均衡、集群？

Why distributed？

为什么需要分布式、集群、负载均衡？

概念的提出或理论的出现，一定是为了解决对应的问题或避免相对应的问题。使其不断的完善化、稳定化。毕竟 Human nature is lazy 此时此刻可能更需要什么？（3V3H)

• Volume 海量
• Variety 多样
• velocity 实时
• 高并发
• 高可扩
• 高性能

单机可能将会遇到的问题会有

• 系统容量
• 单点故障
• 性能不足
• …

该如何解决此问题？有一种比较功利性的思想 – 缺啥补啥，当然也是比较较为明确的方式。至少我仅仅只需要解决以上中较少问题。 分布式（思想）要解决的问题主要是单机系统中系统容量不足及提高系统可用性。

What‘s Distributed？

什么是分布式？亦或者说满足如何的条件才算分布式？

分布式（系统），简而言之即是由多个处理机通过通信路线互联而构成的松散。一次性近乎解决了所有单点的所有问题。

A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another.[1] The components interact with one another in order to achieve a common goal. Three significant characteristics of distributed systems are: concurrency of components, lack of a global clock, and independent failure of components.[1] Examples of distributed systems vary from SOA-based systems to massively multiplayer online games to peer-to-peer applications.

个人认为高并发、高可扩、高性能以此为主推到出 并发性：一个大的任务可以划分为若干个子任务，分别在不同的主机上执行 可扩性：可弹性增降容 自治性：分布式系统中的各个节点都包含自己的处理机和内存，各自具有独立的处理数据的功能。通常，彼此在地位上是平等的，无主次之分，既能自治地进行工作，又能利用共享的通信线路来传送信息，协调任务处理 全局唯一性：分布式系统中必须存在一个单一的、全局的进程通信机制，使得任何一个进程都能与其他进程通信，并且不区分本地通信与远程通信。

What is the core idea of distribution?

分布式的核心理念是什么？

较于以上的了解，那么最为重要的为： 一致性：各主从机权限可不同、但需有一致性。建立维持自己的通信 容错性：拥有较为自主的稳定性，可能最大保障系统的正常运行

How to realize distributed？

如何实现分布式？

经过了解与探究，相信你已经抓住的有单机到多机（分布式）的命脉，那就是一致性，信号一致性。如果能想到这里，那么恭喜您，你和我一样还是比较需要去学习的。并没有去否定它的正确与否，仅仅是太过于笼统。 那么既然需要实现分布式，那么仅仅需要建立及维护此通信即可。保障它，你我就从单机的电脑插上了网线。是否有点 feel 呢？

分布式优缺点剖析

部分先后，仅从不同角度侧重概述。合而为一即可

闪光点： 稳定性：资源共享。若干不同的节点通过通信网络彼此互联，一个节点上的用户可以使用其他节点上的资源。 性能：加快计算速度 机会点 存在通信网络饱和或信息丢失和网络安全问题

RAFT

简介

Raft 首先选举出一个 server 作为 Leader，然后赋予它管理日志的全部责任。Leader 从客户端接收日志条目，复制给其他 server，并告诉他们什么时候可以安全的将日志条目应用到自己的状态机上。拥有一个 Leader 可以简化 replicated log 的管理。例如，leader 可以决定将新的日志条目放在什么位置，而无需询问其他节点，数据总是简单的从 leader 流向其他节点。Leader 可能失败或者断开连接，这种情况下会选出一个新的 leader。 通过 leader，Raft 将一致性问题分解成三个相当独立的子问题：

• Leader Election：当集群启动或者 leader 失效时必须选出一个新的 leader。
• Log Replication：leader 必须接收客户端提交的日志，并将其复制到集群中的其他节点，强制其他节点的日志与 leader 一样。
• Safety：最关键的安全点就是图 3.2 中的 State Machine Safety Property。如果任何一个 server 已经在它的状态机 apply 了一条日志，其他的 server 不可能在相同的 index 处 apply 其他不同的日志条目。后面将会讲述 raft 如何实现这一点。

基础

一个 Raft 集群会包含数个 server，5 是一个典型值，可以容忍两个节点失效。在任何时候每个 server 都会处于 Leader、Candidate、Follower 三种状态中的一种。在正常情况下会只有一个 leader，其他节点都是 follower，follower 是消极的，他们不会主动发出请求而仅仅对来自 leader 和 candidate 的请求作出回应。leader 处理所有来自客户端的请求 (如果客户端访问 follower，会把请求重定向到 follower)。Candidate 状态用来选举出一个 leader。 多个 candidate 想要成为 leader，如果一个 candidate 赢得选举，它将会在剩余的 term 中作为 leader。在一些情况下选票可能会被瓜分，导致没有 leader 产生，这个 term 将会以没有 leader 结束，一个新的 term 将会很快产生。Raft 确保每个 term 至多有一个 leader。Term 在 Raft 中起到了逻辑时钟的作用，它可以帮助 server 检测过期信息比如过期的 leader。每一个 server 都存储有 current term 字段，会自动随时间增加。当 server 间通信的时候，会交换 current term，如果一个节点的 current term 比另一个小，它会自动将其更新为较大者。如果 candidate 或者 leader 发现了自己的 term 过期了，它会立刻转为 follower 状态。如果一个节点收到了一个含有过期的 term 的请求，它会拒绝该请求。 Raft 节点之间通过 RPC 进行通信，基本的一致性算法仅仅需要两种 RPC。RequestVote RPC 由 candidate 在选举过程中发出，AppendEntries RPC 由 leader 发出，用于复制日志和提供心跳。每一个请求类型都有对应的 response，Raft 假定 request 和 response 都可能会丢失，因此要求请求者有超时重试的能力。为了性能，RPC 请求会并行发出，而且不保证 RPC 的到达顺序。

Leader election

Raft 使用心跳机制来触发 leader 选举。当 server 启动的时候是处于 follower 状态，当它可以收到来自 leader 或者 candidate 的有效 RPC 请求时就会保持 follower 的状态。Leader 发送周期性的心跳 (不含日志的 AppendEntries RPC) 给所有的 follower 来确保自己的权威。如果一个 follower 一段时间 (称为 election timeout) 没有收到消息，它就会假定 leader 失效并开始新的选举。 为了开始新一轮选举，follower 会提高自己当前的 term 并转为 candidate 状态。它会先给自己投一票然后并行向集群中的其他 server 发出 RequestVote RPC，candidate 会保持这个状态，直到下面三种事情之一发生：

1. 赢得选举。当 candidate 收到了集群中相同 term 的多数节点的赞成票时就会选举成功，每一个 server 在给定的 term 内至多只能投票给一个 candidate，先到先得。收到多数节点的选票可以确保在一个 term 内至多只能有一个 leader 选出。一旦一个 candidate 赢得选举，它就会成为 leader。它之后会发送心跳消息来建立自己的权威，并阻止新的选举。
2. 另一个 server 被确定为 leader。在等待投票的过程中，candidate 可能收到来自其他 server 的 AppendEntries RPC，声明它才是 leader。如果 RPC 中的 term 大于等于 candidate 的 current term，candidate 就会认为这个 leader 是合法的并转为 follower 状态。如果 RPC 中的 term 比自己当前的小，将会拒绝这个请求并保持 candidate 状态。
3. 没有获胜者产生，等待选举超时。candidate 没有选举成功或者失败，如果许多 follower 同时变成 candidate，选票就会被瓜分，形不成多数派。这种情况发生时，candidate 将会超时并触发新一轮的选举，提高 term 并发送新的 RequestVote RPC。然而如果不采取其他措施的话，选票将可能会被再次瓜分。

Raft 使用随机选举超时来确保选票被瓜分的情况很少出现而且出现了也可以被很快解决。election timeout 的值会在一个固定区间内随机的选取 (比如 150-300ms)。这使得在大部分情况下仅有一个 server 会超时，它将会在其他节点超时前赢得选举并发送心跳。candidate 在发起选举前也会重置自己的随机 election timeout，也可以帮助减少新的选举轮次内选票瓜分的情况

Log Replication

一旦一个 leader 被选举出来，它开始为客户端请求服务。每一个客户端请求都包含着一个待状态机执行的命令，leader 会将这个命令作为新的一条日志追加到自己的日志中，然后并行向其他 server 发出 AppendEntries RPC 来复制日志。当日志被安全的复制之后，leader 可以将日志 apply 到自己的状态机，并将执行结果返回给客户端。如果 follower 宕机或运行很慢，甚至丢包，leader 会无限的重试 RPC (即使已经将结果报告给了客户端)，直到所有的 follower 最终都存储了相同的日志。 日志按下图的方式进行组织，每一条日志储存了一条命令和 leader 接收到该指令时的 term 序号。日志中的 term 序号可以用来检测不一致的情况，每一条日志也拥有一个整数索引用于定位。

总结

RAFT 算法终究实现了什么？

• 实现了信号一致性
• 动态的 Leader、Accessible or work 角色及节点管理，最大限度的保障了稳定性。
• 他的核心为保障大多数都可用，即可正常运行。

寄语： 如果您是一位非常有经验的管理者或您有相对稳健的算法与数据结构基础， 是否与您所存在的了解的结构有所大多相似呢？- 有效管理 直接上司管辖直属同事，算法中的 BFS 在稍稍加入较为智能的选 Leader，若大多数 leader 停止了工作，worker 将会进行相对应的 “休息”，并没有接受到任务，简单的计算机选择做不如不做。毕竟 Human nature is lazy