19种分布式系统设计模式 - Nishant

19种分布式系统设计模式 - Nishant
涉及与分布式系统相关的常见设计问题的关键模式：

1. 布隆过滤器
布隆过滤器是一种节省空间的概率数据结构，用于测试元素是否是集合的成员。它用于我们只需要知道元素是否属于它应该所在的地方（缓存）。

在BigTable（和 Cassandra）中，任何读取操作都必须从组成 Tablet 的所有 SSTable 中读取。如果这些 SSTables 不在内存中，则读取操作最终可能会执行许多磁盘访问。为了减少磁盘访问次数，BigTable 使用了布隆过滤器。

2. 一致的哈希
一致的散列允许您轻松扩展，从而可以有效地复制数据，从而实现更好的可用性和容错性。
通过对数据项的键进行散列以产生其在环上的位置，然后顺时针遍历环以找到位置大于该项位置的第一个节点，将由键标识的每个数据项分配给一个节点。与节点关联的节点是数据项的位置。

一致性哈希的主要优点是增量稳定性；一个节点离开或到达集群只影响其直接邻居，其他节点不受影响。

3. 法定人数
在分布式环境中，仲裁是在宣布操作总体成功之前需要成功执行分布式操作的服务器的最小数量。

• Cassandra，为了确保数据的一致性，每个写入请求都可以配置为只有在数据已写入至少一个仲裁（或大多数）副本节点时才能成功。
• 对于leader选举，Chubby使用Paxos，它使用quorum来保证强一致性。
• Dynamo将写入复制到系统中其他节点的草率仲裁，而不是像 Paxos 这样的严格多数仲裁。所有读/写操作都在首选项列表中的第一个 NN 健康节点上执行，这可能并不总是在遍历一致哈希环时遇到的第一个 NN 节点。

4. 领导者和追随者
为了在管理数据的系统中实现容错，需要在多个服务器上复制数据。
在集群中选择一台服务器作为领导者。领导者负责代表整个集群做出决策，并将决策传播到所有其他服务器。
三到五个节点的集群，就像在实现共识的系统中一样，领导者选举可以在数据集群本身内实现，而不依赖于任何外部系统。领导者选举发生在服务器启动时。每台服务器在启动时都会开始选举领导者，并尝试选举领导者。除非选出领导者，否则系统不接受任何客户端请求。

5.心跳
Heartbeat 机制用于检测现有的leader是否失败，从而可以开始新的leader选举。

6. Fencing
在leader-follower 设置中，当leader 失败时，不可能确定leader 已经停止工作。例如，慢速网络或网络分区可以触发新的领导者选举，即使之前的领导者仍在运行并认为它仍然是活动的领导者。
Fencing 是在之前活跃的领导者周围设置一个栅栏，这样它就不能访问集群资源，从而停止服务任何读/写请求。
使用了以下两种技术：

• 资源防护：系统阻止以前活跃的领导者访问执行基本任务所需的资源。
• 节点防护：系统阻止先前活动的领导者访问所有资源。执行此操作的常用方法是关闭或重置节点。

7. 预写日志（WAL）

预写日志是针对操作系统中文件系统不一致问题的一种复杂解决方案。受数据库管理系统的启发，这种方法首先将要执行的操作的摘要写到“日志”中，然后再将它们实际写入磁盘。在崩溃的情况下，操作系统可以简单地检查这个日志并从它停止的地方开始。

8. 分段日志

将日志拆分为多个较小的文件，而不是单个大文件，以便于操作。
单个日志文件在启动时读取时可能会增长并成为性能瓶颈。较旧的日志会定期清理，对单个大文件进行清理操作很难实现。
单个日志被分成多个段。日志文件在指定的大小限制后滚动。使用日志分段，需要有一种直接的方法将逻辑日志偏移（或日志序列号）映射到日志段文件。

9. 高水位线High-Water mark
跟踪领导者上的最后一个日志条目，该条目已成功复制到法定数量的追随者。日志中此条目的索引称为高水位线索引。领导者仅将数据公开至高水位线索引。

Kafka：为了处理不可重复读取并确保数据一致性，Kafka 代理会跟踪高水位线，这是特定分区共享的最大偏移量。消费者只能在高水位线之前看到消息。

10. 租赁
租约就像一把锁，但即使在客户端离开时它仍然有效。客户要求租用一段有限的时间，之后租约到期。如果客户端想要延长租约，它可以在租约到期之前更新租约。

Chubby客户端与领导者保持有时间限制的会话租约。在此时间间隔内，领导者保证不会单方面终止会话。

11. Gossip协议
Gossip 协议是点对点通信机制，其中节点定期交换关于自己和他们知道的其他节点的状态信息。
每个节点每秒启动一次 gossip 轮次，以与另一个随机节点交换有关自己和其他节点的状态信息。

每秒钟每台服务器与一个随机选择的服务器交换信息

12. Phi 累积故障检测
该算法利用历史心跳信息使阈值自适应。通用 Accrual Failure Detector 不会告诉服务器是否处于活动状态，而是输出有关服务器的怀疑级别。

Cassandra使用 Phi Accrual Failure Detector 算法来确定集群中节点的状态。

13. 脑裂
分布式系统具有两个或多个活动领导者的常见场景称为裂脑。
脑裂是通过使用Generation Clock来解决的，Generation Clock只是一个单调递增的数字来指示服务器的世代。
每次选举新的领导者时，世代数都会增加。这意味着如果旧领导者的代号为“1”，则新领导者的代号为“2”。这个世代号包含在从领导者发送到其他节点的每个请求中。这样，节点现在可以通过简单地信任具有最高数量的领导者来轻松区分真正的领导者。

• Kafka：为了处理脑裂（我们可以有多个活动的控制器代理），Kafka 使用“纪元数”，它只是一个单调递增的数字来指示服务器的世代。
• HDFS：ZooKeeper 用于确保任何时候只有一个 NameNode 处于活动状态。每个事务 ID 都会保留一个 epoch 编号，以反映 NameNode 的生成

14.校验和Checksum
在分布式系统中，在组件之间移动数据时，从节点获取的数据可能会损坏。
计算校验和并将其与数据一起存储。
为了计算校验和，使用了 MD5、SHA-1、SHA-256 或 SHA-512 等加密哈希函数。哈希函数获取输入数据并产生一个固定长度的字符串（包含字母和数字）；这个字符串称为校验和。
当系统存储一些数据时，它会计算数据的校验和，并将校验和与数据一起存储。当客户端检索数据时，它会验证从服务器接收到的数据是否与存储的校验和相匹配。如果没有，那么客户端可以选择从另一个副本中检索该数据。

HDFS和Chubby将每个文件的校验和与数据一起存储

15. CAP 定理
CAP 定理指出，分布式系统不可能同时提供以下所有三个理想属性：
一致性 (C)、可用性 (A) 和分区容差 (P)
根据 CAP 定理，任何分布式系统都需要从三个属性中选择两个。三个选项是 CA、CP 和 AP。

• Dynamo：在 CAP 定理术语中，Dynamo 属于 AP 系统的类别，旨在以牺牲强一致性为代价实现高可用性。
• BigTable：根据 CAP 定理，BigTable 是一个 CP 系统，即具有严格一致的读写。

16. PACELEC 定理
PACELC 定理指出，在复制数据的系统中：

• 如果存在分区（'P'），分布式系统可以在可用性和一致性（即'A'和'C'）之间进行权衡；
• else（'E'），当系统在没有分区的情况下正常运行时，系统可以在延迟（'L'）和一致性（'C'）之间进行权衡。

定理的第一部分（PAC）与CAP定理相同，ELC是扩展。整个论文假设我们通过复制保持高可用性。因此，当出现故障时，CAP 定理占上风。但如果不是，我们仍然需要考虑复制系统的一致性和延迟之间的权衡。

17. 提示切换Hinted Handoff
如果节点出现故障，系统会保留它们错过的所有请求的提示（或注释）。一旦故障节点恢复，请求将根据存储的提示转发给它们。
当一个节点宕机时，领导者在本地磁盘上的一个文本文件中写入一个提示。该提示包含数据及其所属的节点信息。当领导者意识到它持有提示的节点已经恢复时，它会将每个提示的写入请求转发给该节点。

18.读取修复
在分布式系统中，数据跨多个节点复制，一些节点最终可能会拥有陈旧的数据。
在读取操作期间修复陈旧数据，因为此时我们可以从多个节点读取数据进行比较并找到具有陈旧数据的节点。这种机制称为读取修复。一旦知道具有旧数据的节点，读取修复操作会将较新版本的数据推送到具有较旧版本的节点。

Cassandra和Dynamo使用“读取修复”将最新版本的数据推送到具有旧版本的节点。

19. 默克尔树Merkle
读取修复在处理读取请求时消除了冲突。但是，如果副本明显落后于其他副本，则可能需要很长时间才能解决冲突。
副本可以包含大量数据。天真地分割整个范围来计算校验和进行比较是不太可行的；有太多的数据要传输。相反，我们可以使用 Merkle 树来比较范围的副本。
Merkle 树是哈希的二叉树，其中每个内部节点是其两个子节点的哈希，每个叶节点是原始数据的一部分的哈希。

比较 Merkle 树在概念上很简单：

1. 比较两棵树的根哈希。
2. 如果它们相等，则停止。
3. 递归左右孩子。

为了反熵和解决后台冲突，Dynamo使用 Merkle 树。