欢迎回来！如果您错过了第1部分, 您可以在这里查看。
由微软亚洲研究院提出的 pacifica 算法是一种用于日志复制系统的分布式一致性算法。界定该公约的论文于2008年发表 (太平洋文件)。es 已正式声明, 其复制模型基于该算法。
弹性搜索数据复制模型是基于原始备份模型的, 在微软研究的太平洋论文中得到了很好的描述。该模型基于复制组中的单个副本, 该副本充当主分片。其他副本称为副本分片。主索引作为所有索引操作的主要入口点。它负责验证它们, 并确保它们是正确的。一旦索引操作被主操作接受, 主操作还负责将该操作复制到其他副本。
互联网上提供该算法细节的文章很少, 因此, 本文简要介绍了基于太平洋纸业的算法。该算法具有以下功能:
- 具有较强的一致性。
- 将单个主节点中的数据与多个辅助节点同步。
- 使用其他一致性组件进行配置维护。
- 即使有少数副本节点可用, 也支持写入。
术语表
首先, 让我们看一下此算法使用的一些术语:
- 副本组: 一个数据集, 其中的每个数据块都是另一个数据的副本, 每个副本都是一个副本节点。”副本组中只有一个副本” 是 “主节点”; “其余为辅助节点。
- 配置: 副本组的配置描述了哪些副本包含在副本组中, 哪些副本是主要副本。
- 配置版本: 配置的版本号。每当发生配置更改时, 版本号都会增加1。
- 配置管理器: 这将管理全局配置组件, 从而确保配置数据的一致性。配置更改请求由 “副本” 节点启动, 然后与版本一起发送到配置管理器。配置管理器验证版本是否正确。否则, 更改请求将被拒绝。
- 查询和更新: 有两种类型的副本组操作: 查询和更新。查询不会更改数据, 而 “更新” 则会更改数据。
- 序列号 (sn): 这表示每个更新操作执行的顺序。它为每个更新操作增加 1, 并且它是一个连续的数字。
- 准备列表: 这是更新操作的准备顺序。
- 提交列表: 这是更新操作的提交序列。提交序列中的操作肯定会生效 (除非所有副本都崩溃)。在同一副本节点上, “已提交列表” 必须排在 “准备列表” 之前
2;颜色: rgb(34, 38, 53);保证金上衣: 20px;边际底部: 5px;字体大小:25 px;清楚的: 两者;字体样式: 正常;字体-变种连字: 正常;字体变量帽: 正常;字母间距: 正常;孤儿: 2;文本对齐: 开始;文本缩进: 0px;文本转换: 无;空白: 正常;寡妇: 2;字间距: 0px;-webkit-text-宽度: 0px;背景颜色: rgb(255, 255, 255);文本装饰风格: 初始;文本装饰颜色: 初始; “> 主要不变
利用 PacificA 算法, 需要一种误差检测机制来满足以下不变。
当 “副本” 节点在任何时候都将自己视为 “主节点” 时, 配置管理器中维护的配置也将其视为当前的 “主” 节点。在任何时候, 只有一个副本节点认为自己是此副本组中的主节点。
主不变可以确保, 当一个节点本身视为主节点时, 它必须是当前的主节点。如果无法满足主变量, 则可能会将查询请求发送到旧主版, 这将导致读取旧数据。
如何确保满足主不变？根据本文的研究, 采用租赁机制可以实现这一点, 租赁机制是分布式系统中常用的方法。具体来说, 主节点定期获得租约, 一旦成功获得租约, 它就认为自己是设定时间段内唯一的主节点。如果期限到期后, 它未获得新的租约, 则它将失去主状态。只要每台计算机中的 cpu 没有明显的时钟偏差, 租赁机制的有效性就可以得到保证。
如本文所述, 租约机制使主节点向所有辅助节点发送检测信号以获取租约, 而不是让所有节点从集中组件获取租约。使用此分散模型可确保没有集中式组件, 如果失败, 将导致所有节点丢失其租约。
查询
查询过程相对简单。查询只能发送到主节点, 并且 “主节点” 返回基于最新提交的数据的相应值。由于此算法要求满足主不变条件, 因此查询始终读取最新提交的数据。
更新
更新过程如下所示:
- 主节点将序列号 (sn) 分配给更新请求。
- 主节点将此更新请求添加到其自己的准备列表中。同时, 它将准备请求发送到所有辅助节点, 要求它们将此更新请求添加到其准备的列表中。
- 当所有副本节点完成准备时, 即当所有副本节点的准备列表包含更新请求时, 主节点开始提交请求, 将更新请求添加到已提交列表并应用更新
当 “主节点” 将下一个请求发送到 “辅助” 节点时, “主要” 的当前 “提交点” 将附加到该请求, 并且 “辅助” 节点将增加其提交点。
我们可以从更新过程中推导出以下不变:
承诺的不变
我们将 “已提交的辅助节点列表” 标记为 “已提交的” 列表 “、” 已编制的列表 “(” 已编制 “列表) 和” 提交的一级节点列表 “(” 提交的 “一级委员会列表”)。名单必须在原始委员会列表之前, 而优先委员会列表必须在第二届预案列表之前。
重新配置: 二次故障、主故障、新添加的节点
1. 二次故障
当辅助节点失败时, 主节点将重新配置请求发送到配置管理器, 从副本组中删除失败的节点。删除 “副本” 节点后, 它将不再属于 “副本组”, 并且不再向其发送请求。
假定网络故障发生在 “主节点” 和 “辅助” 节点之间。在这种情况下, 两者仍然可以连接到配置管理器。此时, 主节点检测到没有来自 “辅助” 节点的响应, 同样, “辅助” 节点也检测到没有来自 “主节点” 的响应。两者都尝试发送重新配置请求, 以便将另一个请求从副本组中删除。此处应用的策略是 “第一次赢” 原则: 配置管理器收到的第一个请求生效, 并且发件人仍保留在副本组中;因为另一个节点不再属于副本组, 所以它不能再更新配置。由于 “主节点” 请求 “辅助” 节点的租约, 因此 “辅助” 节点在租约有效时不会执行重新配置, 并且 “主” 节点的探测间隔必须小于租约探测间隔。在此情况下, 似乎倾向于主节点执行重新配置以删除辅助节点。
2. 主故障
当 “主节点” 失败时, “辅助” 节点将停止接收来自 “主节点” 的检测信号。如果租约已过期, 辅助节点将发送重新配置请求, 以删除主节点, 这也遵循 “赢首” 原则: 发送成功请求的辅助节点将成为新的主节点。
辅助节点成为主节点后, 必须先经历一个名为 “对帐” 的阶段, 然后才能提供服务。由于上面提到的 “提交不变”, 前一个主节点的 “提交列表” 必须在新主节点的 “准备列表” 之前。这意味着, 当我们将新主节点的 “准备好的列表” 内容与当前副本组中的其他节点对齐 (这相当于在所有节点上重新提交此节点的未提交记录) 时, 必须包括所有以前的 “提交” 记录。这将导致下一个不变:
-
重新配置不变:当新的主节点在 t 时间完成对帐时, t 时间之前的任何节点的 “提交列表” (包括原始主节点) 都优先于新主节点的当前 “提交列表”
3. 新添加的节点
新添加的节点必须首先成为辅助候选节点, 然后主节点开始向其发送 “准备请求”。同时, 此节点尝试赶上以前未同步的记录。一旦它赶上记录, 它就会发送一个请求作为辅助节点, 之后主节点会向配置管理器发送配置更改请求, 以便将该节点添加到副本组。
还有另一种情况: 一个节点位于副本组中, 并且由于临时故障而被删除, 现在需要重新添加到副本组。此时, 此节点上的 “提交列表” 中的数据必须已提交, 而 “已准备列表” 中的数据可能尚未提交。因此, 应删除未提交的数据, 并从提交点的 “主起点” 开始请求数据。
太平洋算法综述
PacificA 是一种具有很强一致性的算法, 既满足读又写要求。它将数据一致性与配置一致性分开, 并使用其他一致性组件 (配置管理器) 来维护配置一致性。这样, 当数据副本不到一半时, 仍然可以编写新的数据, 并确保强有力的一致性。
es 设计是指太平洋 a 算法。它通过 master 维护 index meta, 这类似于配置管理器的配置维护, 如本文所述。在索引 meta 中, InSyncAllocationIds 表示当前可用的碎片, 这类似于纸张中的副本组维护。接下来, 我们将在 es 中引入序列号和检查点。这两个类类似于太平洋 a 算法中的序列号和提交点。然后, 我们比较了 es 实现与太平洋的异同。
序列号、检查点和故障发现
文中介绍了 es 所采用的一致性算法模型–太平洋 a。请务必注意, 每个太平洋更新操作都有相应的序列号, 指示执行顺序。在以前版本的 es 中, 某些功能是有限的, 因为每个写入操作都缺少序列号或类似的机制。2015年, es 官员开始计划为每个写入操作添加序列号, 并假定会有许多应用程序方案。
更多详情可在以下两个链接中找到:
-
接下来, 我们简要介绍了序列和检查点的定义, 并讨论了它们的应用场景。
术语和序列号
为每个写入操作分配两个值: 术语和序列号。每当主更改时, 术语都会增加 1, 这类似于太平洋 a 论文中的配置版本。每个操作后序列号增加 1, 这类似于太平洋纸中的序列号。
因为读取请求总是发送到主节点, 所以它分配术语和序列号。将同步请求发送到 “副本” 节点时, 将附加这两个值。
本地检查点和全局检查点
本地检查点指示此分片中的所有值小于此值的请求都已处理。
全局检查点指示所有副本节点上处理的值小于此值的所有请求都已处理。全局检查点由主节点维护。每个副本节点将其本地检查点报告到主节点, 然后主节点将根据该信息增加全局检查点。
global俄点是一个全局安全点, 指示 “副本” 节点已正确处理之前的所有请求, 并可用于在从节点故障中恢复后重新填充数据。全局检查点也可用于 tranlog gc, 因为不再需要保存以前的操作记录。但是, es 中的 tranlog gc 策略是基于大小或时间应用的, 而全局检查点似乎没有使用。
快速故障恢复
当副本节点出现故障时, es 会将其删除。当故障超过特定时间段时, es 会将新的副本节点分配给新的节点。此时, 需要完全数据同步。但是, 如果以前失败的副本节点返回, 只需在故障恢复后重新填充数据, 并在赶上记录后将该节点重新添加, 就会导致快速恢复故障第一个条件可以通过保存 tranlog 特定的时间来满足;第二个条件可以满足使用检查点, 最终实现快速故障恢复。这是使用序列号和检查点的第一个重要应用程序方案。
弹性搜索与太平洋 a 的比较
相似 之 处
- 元一致性和数据一致性是单独处理的: 在 PacificA 中, 配置一致性是通过配置管理器来维护的;在 es 中, 元一致性是通过 master 保持的。
- 同步维护副本集合: 在太平洋, 将维护副本组; 在太平洋, “复制” 组保持 “在 es 中, 保持同步分配器。
- 序列号: 在 pacica 和 es 中, 写入操作都使用序列号来记录操作顺序。
差异
主要区别在于 es 符合太平洋 a;但其实现仍未满足算法的所有要求, 意味着严格的强一致性不能保证。要点如下:
- 元一致性: 我们在上一节中分析了 es 中的元一致性问题, 我们可以看到 es 不能保证元一致性, 因此它肯定不能严格保证数据一致性。
- 准备阶段: PacificA 具有准备阶段, 可确保在所有节点上成功准备数据并确保未丢失提交的数据之前不会提交数据。在 es 中, 数据是直接写入的, 因为它缺少此阶段。
- 读取一致性: 在 es 中, 可以读取所有不同步副本节点, 从而提高数据可读性;但是, 也可以读取旧数据。另一方面, 即使只可以读取主节点, es 也需要类似租约的机制, 这样旧主节点也不会被读取。考虑到 es 是一个近乎实时的系统, 对读取一致性的要求可能不是很严格。