type
status
date
slug
summary
tags
category
icon
password
Created by
URL
#1. Bloom Filters(布隆过滤器)
布隆过滤器是一种节省空间的概率数据结构，应用于测试一个元素是否是一个集合成员。它应用于我们需要检测元素属于对象的场景。 在BigTable(和Cassandra)中，任何读操作都需要从Tablet组成的SSTable中读取数据。如果这些SSTable不在内存中，读操作可能会执行很多磁盘操作以便读取所需的SSTable。为了减少磁盘访问次数，BigTable使用了布隆过滤器。
#2. Consistent Hashing（一致性哈希）
一致性哈希允许你容易扩展，从而允许以有效的方式复制数据，从而实现更好的可用性和容错能力。 通过哈希数据项的键来得到它在换上的位置，然后顺时针遍历环以找到位置大于该项位置的第一个节点，从而将每个由键表示的数据项分配给一个节点。与节点关联的节点是数据项的位置。 一致性安徽新的主要优点是增量的稳定性：一个节点离开或达到集群只影响相邻的节点，其他节点不受影响。
#3. Quorum(仲裁集)
在分布式环境中，仲裁集是在确认操作成功之前需要成功执行此分布式操作的最小服务器数。 Cassandra，为了确保数据一致性，每个写入请求都可以配置为仅当数据已写入至少一个仲裁集（或大多数）副本节点时才成功。 对于领导者选举，Chubby使用Paxos，它使用仲裁集来确保强大的一致性。 Dynamo将写操作复制到系统中其他节点的任意仲裁集，而不是像Paxos那样严格的多数仲裁集。所有的读/写操作都是在首选项列表中的第一个NN健康节点上执行，该节点可能并不总是在遍历一致哈希环时遇到的第一个NN节点。
#4. Leader and Follower(领导追随者)
为了实现系统数据管理的容错，需要在多个服务器上复制数据。 在集群中选择一个服务器作为领导者。领导者负责代表整个集群做出决策，并将决策传播到所有其他服务器。 在三到五个节点的集群中，就像在系统中达成共识类似，领导者选举可以在数据集群内部完成，而不依赖任何外部。领导者选举是在服务器启动时进行。每个服务在启动时都会启动领导者选举，并尝试选出一个领导者。在选出领导者之前，系统不接受任何客户端请求。
#5. Heatbeat(心跳)
心跳机制用于检测现有领导者是否出现异常，以便可以启动心得领导者选举。
#6. Fencing（屏障）
在领导追随者模式中，当领导者失败后，无法确定领导者是否已停止工作。比如，网络较慢或者网络分区会触发新的领导者选举，即使先前领导者仍在运行并认为它是活跃的领导者。 屏障是指在以前处于活跃状态的领导者周围设置围栏，使其无法访问集群资源，从而停止为任何读/写请求提供服务。 使用了如下两种技术：
- 资源屏障：系统会阻止先前处于活跃状态的领导者访问执行基本任务所需的资源。
- 节点屏障：系统会阻止先前处于活跃状态的领导者访问所有资源。执行此操作的常见方法是关闭节点电源或重置节点。
#7. WAL (预写日志)
Write-ahead logging是解决操作系统中文件系统不一致的问题的复制解决方案。受数据管理系统启发， 这种方法首先将要执行的操作的摘要记录到“日志”中，然后将它们实际写入磁盘。在发生崩溃的时候，操作系统可以简单检查这个日志并从它停止的地方重新开始。
#8. Segmented Log(分段日志)
为了更容易操作，我们可以把一个较大的文件拆分成多个小文件。 单个日志文件在启动时读取可能会增长并成为性能瓶颈。旧的日志会定期清理，而对单个大文件进行清理操作很难。 单个日志被拆分成多个段。日志文件会在特定大小进行滚动。使用日志分段，需要有一种简单的方法将逻辑日志偏移量（或日志序列号）映射到日志段文件。
#9. High-Water mark（高水位标记）
跟踪领导者上的最后一个日志条目，该条目已成功复制到追随者的仲裁集。日志中此条目的索引称为高水位标记索引。领导者只暴露到高水位标记索引的数据。 Kafka：为了吹了不可重复读取并确保数据一致，Kafka broker会跟踪高水位标记，即特定分区共享的最大偏移量。消费者只能看到高水位标记之前的消息。
#10. Lease（租约）
租约就像一把锁，即使客户端断开，它也能工作。客户端请求有一定期限的租约，超过这个期限租约就到期了。如果客户端想延长租约，可以在租约到期之前续订租约。 Chubby客户端与领导者保持有时间限制的会话租约。在此期间，领导者保证不会单向终止会话。
#11. Gossip Protocol（流言传播协议）
Gossip协议是一种点对点的通信机制，在这种机制中，节点定期交换关于自己和它们所知道的其他节点的状态信息。 每个节点每秒启动一轮Gossip轮转，来与另一个随机节点交换有关自己和其它节点的状态信息。
#12. Phi Accrual Failure Detection（Phi累计故障检测）
此算法使用历史心跳信息使阈值自适应。一般的累计故障检测器不会判断服务器是否处于活动状态，而是输出有关服务器的可疑级别。 Cassandra 使用Phi 累计故障检测器算法来确定集群中节点的状态。
#13. Split-brain（脑裂）
分布式系统中有两个或多个活跃领导者的场景被称为脑裂。 通过使用生成时钟可以解决脑裂问题，它只是一个单调递增的数字，用来表示服务器的生成。 每次选出新领导者，时钟数字就会增加一次。这意味着，如果老的领导者的时钟数为“1”，则新领导者的时钟数为“2”。这个生成的数字会包含在从领导者发送到其他节点的每个请求中。通过这种方式，节点现在可以轻松地区分真正的领导者。 Kafka：为了处理脑裂（我们可以有多个active controller broker），Kafka使用“纪元数”(Epoch number)，这只是一个单调递增的数字来表示服务器的生成。 HDFS：Zookeeper用于保证任何时候只有一个NameNode处于活动状态。一个纪元号作为每个事务ID的一部分进行维护，以反映NameNode的生成。
#14. Checksum（校验和）
在分布式系统中，在组件之间移动数据时，获取到的数据可能会损坏。 计算校验和并将其与数据一起存储。 要计算校验和，可以使用MD5、SHA-1、SHA-256或SHA-51等加密哈希函数。哈希函数接受输入数据并生成一个固定长度的字符串（包含字母和数字），这个字符串称为校验和。 当系统存储一些数据时，它计算数据的校验和，并将校验和与数据一起存储。当客户端检索数据时，它会校验服务器接收到的数据是否与存储的校验和匹配。如果不匹配，客户端可以选择从另一个副本检索该数据。 HDFS和Chubby将每个文件的校验和与数据一起存储。
#15. CAP Theorem（CAP定理）
CAP定理指出，分布式系统不可能同时满足以下三个属性： 一致性（C）、可用性(A)和分区容错性(P)。 根据CAP定理，任何分布式系统都需要从三个属性中选择两个。这三个选项是CA、CP和AP。 Dynamo：在CAP定理中，Dynamo属于AP类的系统，它会通过牺牲强一致性来实现高可用。 BigTable：根据CAP定理，BigTable是一个CP系统，它具有严格一致的读取和写入。
#16. PACELEC Theorem（PACELEC定理）
PACELC定理指出，在复制数据的系统中：
- 如果有一个分区(P)，在分布式系统可以在可用性和一致性（即A和C）之间进行权衡
- 否则(E)，当系统在没有分区的情况下正常运行时，系统可以在延迟(L)和一致性(C)之间进行权衡 定理(PAC)的第一部分与CAP定理相同，ELC是扩展。整个论点假设我们通过复制来保持高可用性。因此，当失败时，CAP定理占上风。但如果没有，我们仍然必须考虑复制系统的一致性和延迟之间的权衡。
#17. Hinted Handoff(提示移交)
如果节点关闭，系统会保留它们错过的所有请求的提示（或注释）。故障恢复后，将根据存储的提示将请求转发给它们。 当节点关闭时，领导者会在本地磁盘上的文本文件中写入提示。此提示包含数据及其所属的节点信息。当领导者意识到它为其保留提示的节点已恢复时，它会将每个提示的写入请求转发到该节点。
#18. Read Repaire（读修复）
在分布式系统中，数据跨多个节点复制，某些节点最终可能会拥有过时的数据。 在读取操作期间修复过时的数据，因为此时，我们可以从多个节点读取数据以进行比较并找到具有过时数据的节点，此机制称为“读修复”。一旦知道具有旧数据的节点，读修复操作就会将较新版本的数据推送到具有较旧版本的节点。 Cassandra和Dynamo使用“读修复”将最新版本的数据推送到具有旧版本的节点。
#19. Merkle Trees（梅克尔树）
“读修复”可以在处理读取请求时消除冲突。但是，如果某个副本明显落后于其他副本，则可能需要很长时间才能解决冲突。 副本可以包含大量数据。简单的拆分整个范围来计算校验和进行比较不太可行，因为要传输的数据实在太多。相反，我们可以使用梅克尔树来比较一个范围的副本。 梅克尔树是哈希的二叉树，其中每个内部节点是其两个子节点的哈希，每个叶节点是原始数据一部分哈希。 比较梅克尔树在概念上很简单：
- 比较两棵树的根哈希
- 如果它们相等，就停止。
- 在左右孩子节点上递归检测。 为了实现反熵和后台解决冲突，Dynamo使用了梅克尔树。