# 分布式系统基础

# 定义

分布式系统：利用多台计算机协同解决单台计算机无法解决的计算、存储问题

单个节点<----->网络<----->单个节点<----->网络<----->单个节点

# 常见的异常情况

• 分布式系统的核心问题就是解决各种异常情况
• 机器宕机(机器出问题)：
  • 最常见，一般需要人工介入
  • 节点重启后会丢失内存信息（部分分布式系统中，节点可以通过读取本地存储或其他节点的方式恢复内存信息）
• 网络异常（网络出问题）：
  • 消息丢失
    • 在IP 网络中，网络层不保证数据报文的可靠传递，在发生网络拥塞，路由变动、设备异常等情况时，都可能发生数据丢失的问题
    • 如果某些节点正常，而某些节点始终无法正常通信，则称之为“网络分化”
  • 消息乱序
    • 消息和发送的顺序不一致
    • 应对方法：序列号机制
  • 数据错误
    • 比特错误
    • 应对方法：校验码
  • TCP协议下仍要考虑网络异常：
    • TCP 只能保证传输层可靠，而无法保证上层通信仍可靠

• 分布式系统三态： * 成功 * 失败 * 超时： * 某个节点宕机，无法返回成功信号 * 网络异常，无法发出/收到相应信号

• 存储数据丢失
  • 常见以硬盘作为存储介质，硬盘损坏导致
  • 对策：从其他节点读取，恢复存储
• 其他异常（半死不活类）
  • 磁盘故障导致的IO缓慢，时好时坏的，导致进程无响应
  • 网络不稳定
• 异常一定会发生，分布式系统的样本一般较大：即 小概率 X 大样本 =大概率
  • 比如某系统中每天异常发生的概率为10 的-9 次方，但系统每天处理的请求为 10的8次方，最终这种异常出现的概率就成为了 10%

# 副本：

• 副本 是指在分布式系统中为数据或者服务提供的冗余 * 数据副本是解决数据丢失异常的唯一手段 * 服务副本，是指数个节点提供某种相同的服务，这种服务一般并不依赖节点本地的存储，其所需数据一般来自其他节点 * 例如：GFS 的一个 chunk 的数个副本就是数据副本 * 而 mapreduce 的 job worker则是服务副本

• 副本一致性：分布式系统通过副本控制协议，使得从系统外部读取系统内部的各个副本的数据在一定的约束提哦啊见下相同，称之为 副本一致性（consistency）
  • 强一致性(strong consistency):
    • 任何时刻，任何用户或者节点 都可以读到 最近一次成功更新后的副本数据。
    • 一致性最高，最难实现
  • 单调一致性(monotonic consistency):
    • 任何时刻，任何用户一旦读到某个数据在某次更新后的值，这个用户不会再读到比这个值更旧的值
    • 若于强一致，但是却非常实用；因为通常来说，用户只关心从己方视角观察到的一致性
  • 回话一致性（session consistency）：
    • 任何时刻，任何用户在某一次回话中一旦读到某个数据在某次更新后的值，这个用户在这次回话中不会再读到比这个值更旧的值
    • 通过引入 会话 的概念，在单调一致的基础上更加放松约束。
  • 最终一致性（eventual consistency）
    • 要求一旦更新成功，各个副本上的数据最终将达到完全一致的状态，但是达到最终一致状态所需要的时间不能保障。
    • 对于最终一致的系统而言，一个用户只要始终读取某一个副本的数据，则可以实现类似单调一致的效果
  • 弱一致性（week consistency）:
    • 一旦某个更新成功，用户无法在一个确定的时间内读到这次更新的值，且即使在某个副本上读到了新的值，也不能保证在其他副本上可以读到新的值。
    • 弱一致性在实际中很难使用，需要应用方做很多工作来保证系统可用。

# 衡量分布式系统的指标：

• 性能(performance)：
  • 系统的吞吐量: 指系统在某一时间可以处理的数据总量：
  • 系统的响应延迟：系统完成某一功能需要使用的时间
  • 系统的并发能力： 系统可以同时完成某一功能的能力： QPS（query per second）
  • 三个性能往往会相互制约
• 可用性(avaiability)
  • 指在面对 各种异常情况，可以提供服务的能力
• 可扩展性（scalability）
  • 指分布式系统通过扩展集群机器规模提高系统性能（吞吐、延迟、并发）、存储容量、计算能力的特性。
• 一致性
  • 分布式系统为了提高可用性，总是不可避免的使用副本机制，从而引发副本一致性问题。
  • 越是强的一致性模型，对用户使用起来越简单。

---

# 数据分布方式

---

# 分布式VS单机：

• 最大区别在于 问题的规模，即 计算、存储的区别
• 无论是计算还是存储，其问题的输入对象都是数据，所以如何拆解分布式系统的输入数据成为分布式系统的基本问题，这里把这个问题叫做 数据分布方式：

1. 哈希方式：按照数据的某一特征（如id）计算哈希值，并将哈希值与集群中的机器建立映射关系，从而将不同的哈希值的数据分布到不同的机器上。
   • 优点
     • 只要哈希函数的散列特性好，哈希方式可以比较为均匀的将数据分布到集群中去
     • 需要的元数据信息也简单，只要知道 哈希函数的计算方式及 模的服务器总量 即可
   • 缺点：
     • 可扩展性不高，一旦集群规模需要扩展，则几乎所有的数据都要被迁移 并重新分布
       • 工程中，往往在扩展时，将集群规模成本扩展，按照数据重新计算哈希，这样原本一台机器上的数据只需要迁移一半到对应的机器即可
       • 另一张思路是，将对应关系交由专门的元数据服务器来进行管理。
     • 一旦数据特征值的数据严重不均，容易出现“数据倾斜“（data skew）的问题。例如：若系统以某个id作为哈希分数据，当某个id数据量异常庞大时， 该用户的数据将始终由一台机器处理，造成数据缓慢的问题
     • 解决思路： 重新选取数据特征
2. 按照数据范围分布：将数据按照特征值的值域范围划分为不同的区间（数据区间的数据大小和区间大大小时内有关系的）（动态划分区间）
   • 需要记录数据分布情况
   • 优点：
     • 扩展性比较好
   • 缺点：
     • 需要维护较为复杂的元数据
3. 按数据量分布: 与具体的数据特征无关，将数据整体视为一个顺序增长的文件，然后将文件按照固定的大小分为若干的数据块，不同的数据块分到不同的服务器上
   • 优缺点与按数据范围类似
4. 一致性哈希： 使用一个哈希函数计算数据或数据特征的哈希值，令该哈希函数的输出值域成为一个封闭的环，即哈希函数的输出的最大值是最小值的前序。
   • 优点：
     • 可以任意动态的添加、删除节点
   • 缺点：
     • 随机分布节点的方式使得其很难均匀的分布哈希值域
     • 改进算法是：引入 虚节点的概念（先均匀分布，添加节点时也新添加 虚节点）

# 副本与数据分布

• 以机器为单位VS以文件段为单位：
  • 以文件段为单位的优点：
    • 数据恢复效率高，文件副本将在所有的机器上均有分布
    • 副本分布与机器无关，有利于集群扩展
    • 同样，文件段的方式也会引起元数据的开销过大
• 本地化计算：
  • 尽量将计算和存储都放在同一台物理机上进行

工程应用：

实例	数据分布方案
GFS、HDFS	按数据量分布
mapreduce	本地化计算
big talbe /hbase	按数据范围

# 副本控制协议：

指按照特定的协议流程控制副本数据的读写行为，使得副本满足一定的可用性和一致性要求的分布式协议。 主要包含两大类：1、 中心化 2、 区中心化

# 中心化副本控制协议：

• 由一个中心节点协调副本数据的更新、维护副本之间的一致性
  • 优点：
    • 协议简单，将分布式并发控制问题简化为单机并发控制问题
  • 缺点：
    • 存在停服时间： 系统的可用性依赖于中心化节点，当中心节点异常或与中心节点通信异常时，系统将失去某些服务。

# Primary-secondary协议

在本协议中，副本被分为两大类，其中有且仅有一个副本作为primary副本，除primary的都时secondary副本。维护primary的节点作为中心节点，中心节点负责维护数据的更新、并发控制、协调副本的一致性。

1. 数据更新基本流程：
   1. 外部节点将更新操作发给primary节点
   2. primary节点进行并发控制即确定并发更新操作的先后顺序
   3. primary节点将更新操作发送给secondary节点
   4. primary 根据 secondary 节点的完成情况决定更新是否成功并将结果返回外部节点
2. 数据读取方式：
   1. primary-secondary实现强一致性的几种思路:
      1. 由于数据的更新流程都是由primary控制的，primary副本上的数据一定是最新的，所以如果始终只读primary副本的数据，可以实现强一致性
      2. 由primary控制节点secondary节点的可用性
3. primary副本的确定与切换
   1. 在 primary-secondary 类型的分布式系统中，哪个副本是 primary 这一信息都属于元信息，由专门的元数据服务器维护。执行更新操作时，首先查询元数据服务器获取副本的 primary 信息，从而进一步执行数据更新流程。
   2. 切换副本的难点在于两个方面：
      1. 如何确定节点的状态以发现原 primary 节点异常是一个较为复杂的问题
      2. 切换 primary后，不能影响副本的一致性
   3. 由于分布式系统中可靠的发现节点异常是需要一定的探测时间的，这样的探测时间通常是 10秒级别在这 10 秒时间内，系统不能提供更新服务。从这里可以看到，primary-backup 类副本协议的最大缺点就是由于 primary 切换带来的一定的停服务时间。
4. 数据同步
   1. Primary-secondary 型协议一般都会遇到 secondary 副本与 primary 不一致的问题:
      1. secondary 上的数据落后于 primary 上的数据。
         1. 回放 primary 上的操作日志
      2. secondary 上的数据有脏数据。
         1. 以简单的直接丢弃有脏数据的副本，这样相当于副本没有数据。
         2. 也可以设计一些基于 undo 日志的方式从而可以删除脏数据
      3. secondary 是一个新增加的副本，完全没有数据:
         1. 直接拷贝 primary 副本的数据：快照 + 回放日志
5. 工程应用：
   1. GFS 系统的副本控制协议是典型的 Primary-Secondary 型协议，Primary 副本由 Master 指定，Primary 副本决定并发更新操作的顺序。虽然在 GFS 中，更新操作的数据由客户端提交，并在各个副本之间流式的传输，及由上一个副本传递到下一个副本，每个副本都即接受其他副本的更新，也向下更新另一个副本，但是数据的更新过程完全是由 primary 控制的，所以也可以认为数据是由primary 副本同步到 secondary 副本的。

# 去中心化副本控制协议

与中心化副本系统协议最大的不同是，去中心化副本控制协议没有中心节点，协议中所有的节点都是完全对等的，节点之间通过平等协商达到一致

• 优点：
  • 没有因为中心化节点异常而带来的停服务等问题
• 缺点：
  • 协议过程通常比较复杂。尤其当去中心化协议需要实现强一致性时，协议流程变得复杂且不容易理解 Paxos 是唯一在工程中得到应用的强一致性去中心化副本控制协议

# Lease机制

Lease 机制是最重要的分布式协议，广泛应用于各种实际的分布式系统中

# 简单的例子：

1. 在一个分布式系统中，有一个中心服务器节点，中心服务器存储、维护着一些数据，这些数据是系统的元数据。系统中其他的节点通过访问中心服务器节点读取、修改其上的元数据(那么中心服务器节点的性能成为系统的瓶颈)
2. 心服务器在向各节点发送数据时同时向节点颁发一个 lease。每个 lease 具有一个有效期，和信用卡上的有效期类似，lease 上的有效期通常是一个明确的时间点
3. 在 lease 的有效期内，中心服务器保证不会修改对应数据的值(假设中心服务器与各节点的时钟是同步的)

• lease 机制可以容错的关键是:
  • 服务器一旦发出数据及 lease，无论客户端是否收到，也无论后续客户端是否宕机，也无论后续网络是否正常，服务器只要等待 lease 超时，就可以保证对应的客户端节点不会再继续 cache 数据，从而可以放心的修改数据而不会破坏 cache 的一致性。

# lease机制的本质：

• lease 的定义:
  • Lease 是由颁发者授予的在某一有效期内的承诺
• Lease 机制具有很高的容错能力：
  • 通过引入有效期，Lease 机制能否非常好的容错网络异常： 单向通信
  • Lease 机制能较好的容错节点宕机
  • lease 机制不依赖于存储
  • Lease 机制依赖于有效期，这就要求颁发者和接收者的时钟是同步的：
    • 为防止出现时钟不同步，实践中的通常做法是将颁发者的有效期设置得比接收者的略大，只需大过时钟误差就可以避免对 lease 的有效性的影响

# 基于 lease 机制确定节点状态

🌰说明：

1. 在一个 primary-secondary 架构的系统中，有三个节点 A、B、C 互为副本，其中有一个节点为 primary，且同一时刻只能有一个 primary 节点。另有一个节点 Q 负责判断节点 A、B、C的状态，一旦 Q 发现 primary 异常，节点 Q 将选择另一个节点作为 primary。假设最开始时节点 A为 primary，B、C 为 secondary。节点 Q 需要判断节点 A、B、C 的状态是否正常。

2. 由中心节点向其他节点发送 lease，若某个节点持有有效的 lease，则认为该节点正常可以提供服务。用于例 2.3.1 中，节点 A、B、C 依然周期性的发送 heart beat 报告自身状态，节点 Q 收到 heart beat后发送一个 lease，表示节点 Q 确认了节点 A、B、C 的状态，并允许节点在 lease 有效期内正常工作。节点 Q 可以给 primary 节点一个特殊的 lease，表示节点可以作为 primary 工作。一旦节点 Q 希望切换新的 primary，则只需等前一个 primary 的 lease 过期，则就可以安全的颁发新的 lease 给新的primary 节点，而不会出现“双主”问题。

3. 在实际系统中，若用一个中心节点发送 lease 也有很大的风险，一旦该中心节点宕机或网络异常，则所有的节点没有 lease，从而造成系统高度不可用。为此，实际系统总是使用多个中心节点互为副本，成为一个小的集群，该小集群具有高可用性，对外提供颁发 lease 的功能。chubby 和 zookeeper都是基于这样的设计

# lease 的有效期时间选择:

• Lease 的有效期虽然是一个确定的时间点，当颁发者在发布 lease 时通常都是将当前时间加上一个固定的时长从而计算出 lease 的有效期。
• 工程中，常选择的 lease 时长是 10 秒级别，这是一个经过验证的经验值，实践中可以作为参考并综合选择合适的时长

# GFS 中的 Lease

GFS 中使用 Lease 确定 Chuck 的 Primary 副本。Lease 由 Master 节点颁发给 primary 副本，持有Lease 的副本成为 primary 副本。Primary 副本控制该 chuck 的数据更新流量，确定并发更新操作在chuck 上的执行顺序。GFS 中的 Lease 信息由 Master 在响应各个节点的 HeartBeat 时附带传递(piggyback)。对于每一个 chuck，其上的并发更新操作的顺序在各个副本上是一致的，首先 master选择 primary 的顺序，即颁发 Lease 的顺序，在每一任的 primary 任期内，每个 primary 决定并发更新的顺序，从而更新操作的顺序最终全局一致。当 GFS 的 master 失去某个节点的 HeartBeat 时，只需待该节点上的 primary chuck 的 Lease 超时，就可以为这些 chuck 重新选择 primary 副本并颁发 lease。

# Chubby 与 Zookeeper 中的 Lease

# Quorum 机制

# write-all-read-one

是一种最简单的副本控制规则，顾名思义即在更新时写所有的副本，只有在所有的副本上更新成功，才认为更新成功，从而保证所有的副本一致，这样在读取数据时可以读任一副本上的数据。 其实现需要依赖一种假设： 假设有一种 magic 的机制，当某次更新操作 wi 一旦在所有 N 个副本上都成功，此时全局都能知道这个信息，此后读取操作将指定读取数据版本为 vi 的数据，称在所有 N 个副本上都成功的更新操作为“成功提交的更新操作”，称对应的数据为“成功提交的数据”。在 WARO 中，如果某次更新操作 wi 在某个副本上失败，此时该副本的最新的数据只有 vi-1，由于不满足在所有 N 个副本上都成功，则 wi 不是一个“成功提交的更新操作”，此时，虽然其他 N-1 个副本上最新的数据是 vi，但 vi 不是一个“成功提交的数据”，最新的成功提交的数据只是 vi-1 这里需要特别强调的是，在工程实践中，这种 magic 的机制往往较难实现或效率较低。

# Quorum 定义

WARO 牺牲了更新服务的可用性，最大程度的增强读服务的可用性。下面将 WARO 的条件进 行松弛，从而使得可以在读写服务可用性之间做折中，得出 Quorum 机制: 在 Quorum 机制下，当某次更新操作 wi 一旦在所有 N 个副本中的 W 个副本上都成功，则就称该更新操作为“成功提交的更新操作”，称对应的数据为“成功提交的数据”。令 R>N-W，由于更新操作 wi 仅在 W 个副本上成功，所以在读取数据时，最多需要读取 R 个副本则一定能读到 wi 更新后的数据 vi 。如果某次更新 wi 在 W 个副本上成功，由于 W+R>N，任意 R 个副本组成的集合一定与成功的W个副本组成的集合有交集，所以读取R个副本一定能读到wi更新后的数据vi。如图 2-10，Quorum 机制的原理可以文森图表示。

仅仅依赖 quorum 机制是无法保证强一致性的。因为仅有 quorum 机制时无法确定最新已成功提交的版本号，除非将最新已提交的版本号作为元数据由特定的元数据服务器或元数据集群管理，否则很难确定最新成功提交的版本号

Quorum 机制的三个系统参数 N、W、R 控制了系统的可用性，也是系统对用户的服务承诺:数据最多有 N 个副本，但数据更新成功 W 个副本即返回用户成功。对于一致性要求较高的 Quorum 系统，系统还应该承诺任何时候不读取未成功提交的数据，即读取到的数据都是曾经在 W 个副本上成功的数据。

# quorum 机制下达到强一致系统

1. 限制提交的更新操作必须严格递增，即只有在前一个更新操作成功提交后才可以提交后一个更新操作，从而成功提交的数据版本号必须是连续增加的。
2. 读取 R 个副本，对于 R 个副本中版本号最高的数据，
   1. 若已存在 W 个，则该数据为最新的成功提交的数据
   2. 若存在个数据少于 W 个，假设为 X 个，则继续读取其他副本，直若成功读取到 W 个该版本的副本，则该数据为最新的成功提交的数据;如果在所有副本中该数据的个数肯定不满足 W 个，则 R 中版本号第二大的为最新的成功提交的副本。
3. 可以看出，在单纯使用 Quorum 机制时，若要确定最新的成功提交的版本，最多需要读取 R+(W-R-1)=N 个副本，当出现任一副本异常时，读最新的成功提交的版本这一功能都有可能不可用。

# 基于 Quorum 机制选择 primary

在 primary-secondary 协议中，当 primary 异常时，需要选择出一个新的 primary，之后 secondary副本与 primary 同步数据。通常情况下，选择新的 primary 的工作是由某一中心节点完成的，在引入quorum 机制后，常用的 primary 选择方式与读取数据的方式类似，即中心节点读取 R 个副本，选择R 个副本中版本号最高的副本作为新的 primary。新 primary 与至少 W 个副本完成数据同步后作为新的 primary 提供读写服务。首先，R 个副本中版本号最高的副本一定蕴含了最新的成功提交的数据。再者，虽然不能确定最高版本号的数是一个成功提交的数据，但新的 primary 在随后与 secondary 同步数据，使得该版本的副本个数达到 W，从而使得该版本的数据成为成功提交的数据。

# GFS 中的 Quorum

GFS 使用 WARO 机制读写副本，即如果更新所有副本成功则认为更新成功，一旦更新成功，则可以任意选择一个副本读取数据;如果更新某个副本失败，则更显失败，副本之间处于不一致的状态。GFS 系统不保证异常状态时副本的一致性，GFS 系统需要上层应用通过 Checksum 等机制自行判断数据是否合法。值得注意的是 GFS 中的 append 操作，一旦 append 操作某个 chunck 的副本上失败，GFS 系统会自动新增一个 chunck 并尝试 append 操作，由于可以让新增的 chunck 在正常的机器上创建，从而解决了由于 WARO 造成的系统可用性下降问题。进而在 GFS 中，append 操作不保证一定在文件的结尾进行，由于在新增的 chunk 上重试 append，append 的数据可能会出现多份重复的现象，但每个 append 操作会返回用户最终成功的 offset 位置，在这个位置上，任意读取某个副本一定可以读到写入的数据。这种在新增 chunk 上进行尝试的思路，大大增大了系统的容错能力，提高了系统可用性，是一种非常值得借鉴的设计思路。

分布式系统原理介绍

# 日志技术

日志技术是宕机恢复的主要技术之一

# Redo Log:

Redo Log 更新流程

1. 将更新操作的结果(例如 Set K1=1，则记录 K1=1)以追加写(append)的方式写入磁盘的日志文件
2. 按更新操作修改内存中的数据
3. 返回更新成功
4. Redo 写入日志的是更新操作完成后的结果 Redo Log 的宕机恢复 1. 从头读取日志文件中的每次更新操作的结果，用这些结果修改内存中的数据。

从 Redo Log 的宕机恢复流程也可以看出，只有写入日志文件的更新结果才能在宕机后恢复。这也是为什么在 Redo Log 流程中需要先更新日志文件再更新内存中的数据的原因

# Check point:

宕机恢复流量的缺点是需要回放所有 redo 日志，效率较低，假如需要恢复的操作非常多，那么这个宕机恢复过程将非常漫长。解决这一问题的方法即引入 check point 技术。在简化的模型下，checkpoint 技术的过程即将内存中的数据以某种易于重新加载的数据组织方式完整的 dump 到磁盘，从而减少宕机恢复时需要回放的日志数据。

# Paxos 协议：

Paxos 协议是少数在工程实践中证实的强一致性、高可用的去__中心化分布式协议__ Paxos 协议的流程较为复杂，但其基本思想却不难理解，类似于人类社会的投票过程。Paxos 协议中，有一组完全对等的参与节点(称为 accpetor)，这组节点各自就某一事件做出决议，如果某个决议获得了超过半数节点的同意则生效。Paxos 协议中只要有超过一半的节点正常，就可以工作，能很好对抗宕机、网络分化等异常情况。

• 节点角色: Paxos 协议中，有三类节点:
  • Proposer:提案者。Proposer 可以有多个，Proposer 提出议案(value)。所谓 value，在工程中可以是任何操作，例如“修改某个变量的值为某个值”、“设置当前 primary 为某个节点”等等。Paxos协议中统一将这些操作抽象为 value。不同的 Proposer 可以提出不同的甚至矛盾的 value，例如某个Proposer 提议“将变量 X 设置为 1”，另一个 Proposer 提议“将变量 X 设置为 2”，但对同一轮 Paxos过程，最多只有一个 value 被批准。
  • Acceptor:批准者。Acceptor 有 N 个，Proposer 提出的 value 必须获得超过半数(N/2+1)的 Acceptor批准后才能通过。Acceptor 之间完全对等独立。
  • Learner:学习者。Learner 学习被批准的 value。所谓学习就是通过读取各个 Proposer 对 value的选择结果，如果某个 value 被超过半数 Proposer 通过，则 Learner 学习到了这个 value。回忆(2.4 )不难理解，这里类似 Quorum 机制，某个 value 需要获得 W=N/2 + 1 的 Acceptor 批准，从而学习者需要至少读取 N/2+1 个 Accpetor，至多读取 N 个 Acceptor 的结果后，能学习到一个通过的 value。 上述三类角色只是逻辑上的划分，实践中一个节点可以同时充当这三类角色。

# CAP 理论

# CAP 理论的定义

CAP 三个字母分别代表了分布式系统中三个相互矛盾的属性:

• Consistency (一致性):CAP 理论中的副本一致性特指强一致性
• Availiablity(可用性):指系统在出现异常时已经可以提供服务
• Tolerance to the partition of network (分区容忍):指系统可以对网络分化这种异常情况进行容错处理; CAP 理论指出:无法设计一种分布式协议，使得同时完全具备 CAP 三个属性，即
• 1)该种协议下的副本始终是强一致性
• 2)服务始终是可用的
• 3)协议可以容忍任何网络分区异常
• 分布式系统协议只能在 CAP 这三者间所有折中

# CAP理论的意义：

热力学第二定律说明了永动机是不可能存在的，不要去妄图设计永动机。与之类似，CAP 理论的意义就在于明确提出了不要去妄图设计一种对 CAP 三大属性都完全拥有的完美系统，因为这种系统在理论上就已经被证明不存在。

参考：[分布式系统原理·刘杰]