数据模型

PacificA算法

ES的数据副本模型基于主从模式（或称主备模式，HDFS和 Cassandra为对等模式），在实现过程中参考了微软的PacificA算法 （借鉴了其中部分思想，并非完全按照这个模型实现）。我们先看一 下PacificA算法的几个特点：

• 设计了一个通用的、抽象的框架，而不是具体的、特定的算法。 模型的正确性容易验证。
• 配置管理和数据副本分离，Paxos负责管理配置，数据副本策略 采取主从模式。
• 将错误检测和配置更新放在数据副本的交互里实现，去中心化。

一些词汇：

• Replica Group：一个互为副本的数据集合称为副本组。其中只 有一个副本是主数据（Primary），其他为从数据（Secondary）。
• Configuration：配置信息中描述了一个副本组都有哪些副本， Primary是谁，以及它们位于哪个节点。
• Configuration Version：配置信息的版本号，每次发生变更时 递增。
• Serial Number：代表每个写操作的顺序，每次写操作时递增， 简称SN。每个主副本维护自己的递增SN。
• Prepared List：写操作的准备序列。存储来自外部请求的列 表，将请求按照 SN 排序，向列表中插入的序列号必须大于列表中最 大的SN。每个副本上有自己的Prepared List。
• Committed List：写操作的提交序列。

设计前提与假设：

• 节点可以失效，对消息延迟的上限不做假设。
• 消息可以丢失、乱序，但不能被篡改，即不存在拜占庭问题。
• 网络分区可以发生，系统时钟可以不同步，但漂移是有限度的。 整个系统框架主要由两部分组成：存储管理和配置管理。
• 存储管理：负责数据的读取和更新，使用多副本方式保证数据的 可靠性和可用性；
• 配置管理：对配置信息进行管理，维护所有配置信息的一致性。

数据副本策略

分片副本使用主从模式。多个副本中存在一个主副本Primary和多 个从副本Secondary。所有的数据写入操作都进入主副本，当主副本 出现故障无法访问时，系统从其他从副本中选择合适的副本作为新的 主副本。

数据写入的流程如下：

• （1）写请求进入主副本节点，节点为该操作分配SN，使用该SN 创建UpdateRequest结构。然后将该UpdateRequest插入自己的 prepare list。
• （2）主副本节点将携带 SN 的 UpdateRequest 发往从副本节 点，从节点收到后同样插入prepare list，完成后给主副本节点回复一 个ACK。
• （3）一旦主副本节点收到所有从副本节点的响应，确定该数据已 经被正确写入所有的从副本节点，此时认为可以提交了，将此 UpdateRequest放入committed list,committed list向前移动。
• （4）主副本节点回复客户端更新成功完成。对每一个Prepare消 息，主副本节点向从副本节点发送一个commit通知，告诉它们自己的 committed point 位置 ， 从副本节点收到通知后根据指示移动 committed point到相同的位置。

因为主副本只有在所有从副本将请求添加进 prepared list 之后 才可以通过移动 committed point的方式将该请求插入committed list中，因此主副本的committed list是任何一个从副本的prepared list的前缀（或者称为子集）。例如，从副本prepared list中SN为1、 2、3、4；主副本committed point中SN一定不会大于4，如1、2、 3。

同时，因为一个从副本只有在主副本将一个请求添加进 committed list后才会把同样的请求添加进committed list中，因此 一个从副本上的committed list是主副本上committed list的前缀， 此不变式称为Commit Invariant。

令P为主副本，R为从副本，以下不变式成立：committed_R ⊆ committed_P ⊆ prepared_R。

配置管理

全局的配置管理器负责管理所有副本组的配置。节点可以向管理 器提出添加/移除副本的请求，每次请求都需要附带当前配置版本号， 只有这个版本号和管理器记录的版本号一致才会被执行，如果请求成 功，则这个新配置会被赋予新的版本号。

错误检测

分布式系统经常存在网络分区、节点离线等异常。全局的配置管 理器维护权威配置信息，但其他各节点上的配置信息不一定同步，我 们必须处理旧的主副本和新的主副本同时存在的情况—旧的主副本可 能没有意识到重新分配了一个新的主副本，从而违反了强一致性。 PacificA使用了租约（lease）机制来解决这个问题。

主副本定期向其他从副本获取租约。这个过程中可能产生两种情 况：

• 如果主副本节点在一定时间内（lease period）未收到从副本节 点的租约回复，则主副本节点认为从副本节点异常，向配置管理器汇 报，将该异常从副本从副本组中移除，同时，它也将自己降级，不再 作为主副本节点。
• 如果从副本节点在一定时间内（grace period）未收到主副本 节点的租约请求，则认为主副本异常，向配置管理器汇报，将主副本 从副本组中移除，同时将自己提升为新的主。如果存在多个从副本， 则哪个从副本先执行成功，哪个从副本就被提升为新主。

假设没有时钟漂移，只要grace period≥lease period，则租约 机制就可以保证主副本会比任意从副本先感知到租约失效。同时任何 一个从副本只有在它租约失效时才会争取去当新的主副本，因此保证 了新主副本产生之前，旧的主分片已降级，不会产生两个主副本。

其他系统也经常将租约机制作为故障检测手段，如GFS、Bigtable。

PacificA算法的这些概念对应在ES中：

• Master负责维护索引元信息，类似配置管理器维护配置信息。
• 集群状态中的routing_table存储了所有索引、索引有哪些 shard、各自的主分片，以及位于哪个节点等信息，类似副本组。
• SequenceNumber 和 Checkpoint 类似 PacificA 算 法 中 的 Serial Number和Committed Point。

ES的数据副本模型

ES 中的每个索引都会被拆分为多个分片，并且每个分片都有多个 副本。这些副本称为replication group（副本组，与PacificA中的副 本组概念一致），并且在删除或添加文档的时候，各个副本必须同 步。否则，从不同副本中读取的数据会不一致。我们把保持分片副本 之间的同步，以及从中取的过程称为数据副本模型（data replication model）。

ES的数据副本模型基于主备模式（primary-backup model）， 主分片是所有索引操作的入口，它负责验证索引操作是否有效。一旦 主分片接受一个索引操作，主分片的副分片也会接受该操作。

基本写入模型

每个索引操作首先会使用routing参数解析到副本组，通常基于文 档ID。一旦确定副本组，就会内部转发该操作到分片组的主分片中。 主分片负责验证操作和转发它到其他副分片。ES维护一个可以接收该 操作的分片的副本列表。这个列表叫作同步副本列表（in-sync copies），并由Master节点维护。正如它的名字，这个“好”分片副本 列表中的分片，都会保证已成功处理所有的索引和删除操作，并给用 户返回 ACK。主分片负责维护不变性（各个副本保持一致），因此必 须复制这些操作到这个列表中的每个副本。

写入过程遵循以下基本流程：

• （1）请求到达协调节点，协调节点先验证操作，如果有错就拒绝 该操作。然后根据当前集群状态，请求被路由到主分片所在节点。
• （2）该操作在主分片上本地执行，例如，索引、更新或删除文 档。这也会验证字段的内容，如果未通过就拒绝操作（例如，字段串 的长度超出Lucene定义的长度）。
• （3）操作成功执行后，转发该操作到当前in-sync 副本组的所有 副分片。如果有多个副分片，则会并行转发。
• （4）一旦所有的副分片成功执行操作并回复主分片，主分片会把 请求执行成功的信息返回给协调节点，协调节点返回给客户端。

写故障处理

写入期间可能会发生很多错误—硬盘损坏、节点离线，或者某些 配置错误，这些错误都可能导致无法在副分片上执行某个操作，虽然 这比较少见，但是主分片必须汇报这些错误信息。

对于主分片自身错误的情况，它所在的节点会发送一个消息到 Master节点。这个索引操作会等待（默认为最多一分钟）Master节点 提升一个副分片为主分片。这个操作会被转发给新的主分片。注意， Master同样会监控节点的健康，并且可能会主动降级主分片。这通常 发生在主分片所在的节点离线的时候。

在主分片上执行的操作成功后，该主分片必须处理在副分片上潜 在发生的错误。错误发生的原因可能是在副分片上执行操作时发生的 错误，也可能是因为网络阻塞，导致主分片无法转发操作到副分片， 或者副分片无法返回结果给主分片。这些错误都会导致相同的结果： in-sync replica set中的一个分片丢失一个即将要向用户确认的操 作。为了避免出现不一致，主分片会发送一条消息到Master节点，要 求它把有问题的分片从in-sync replica set中移除。一旦Master确认 移除了该分片，主分片就会确认这次操作。注意，Master也会指导另 一个节点建立一个新的分片副本，以便把系统恢复成健康状态。

在转发请求到副分片时，主分片会使用副分片来验证它是否仍是 一个活跃的主分片。如果主分片因为网络原因（或很长时间的 GC）被 隔离，则在它意识到被降级之前可能会继续处理传入的索引操作。来 自陈旧的主分片的操作将会被副分片拒绝。当它接收来自副分片的拒 绝其请求的响应时，它将会访问一下主节点，然后就会知道自己已被 替换。最后将操作路由到新的主分片。

如果没有副分片呢？出现这种场景可能是因为索引配置或所有副分片都发生故障。在 这种情况下，主分片处理的操作没有经过任何外部验证，可能会导致 问题。另一方面，主分片节点将副分片失效的消息告知主节点，主节 点知道主分片是唯一可用的副本。因此我们确保主节点不会提升任何 其他分片副本（过时的）为主分片，并且索引到主分片上的任何操作 都不会丢失。当然，由于只运行单个数据副本，当物理硬件出问题时 可能会丢失数据。可以使用 wait_for_active_shards 缓解此类问 题。

基本读取模型

通过 ID 读取是非常轻量级的操作，而一个巨大的复杂的聚合查询 请求需要消耗大量 CPU和内存资源。主从模式的一个好处是保证所有 的分片副本都是一致的（正在执行的操作例外）。因此，单个in-sync 中的某个副本也可以提供服务。当一个读请求被协调节点接收，这个 节点负责转发它到其他涉及相关分片的节点，并整理响应结果发送给 客户端。接收用户请求的这个节点称为协调节点。

基本流程如下：

• （1）把读请求转发到相关分片。注意，因为大多数搜索都会发送 到一个或多个索引，通常需要从多个分片中读取，每个分片都保存这 些数据的一部分。
• （2）从副本组中选择一个相关分片的活跃副本。它可以是主分片 或副分片。默认情况下， ES会简单地循环遍历这些分片。
• （3）发送分片级的读请求到被选中的副本。
• （4）合并结果并给客户端返回响应。注意，针对通过ID查找的 get请求，会跳过这个步骤，因为只有一个相关的分片。

读故障处理

当分片不能响应一个读请求时，协调节点会从副本组中选择另一 个副本，将请求转发给它。没有可用的分片副本会导致重复的错误。 在某些情况下，例如，_search,ES 倾向于尽早响应，即使只有部分结 果，也不等待问题被解决（可以在响应结果的_shards字段中检查本次 结果是完整的还是部分的）。

引申的含义

基本流程决定了 ES 系统在读和写时的表现。此外，由于读写可 以同时执行，所以这两个基本流程互相有些影响。这有一些固定的含 义。

高效读取

在正常操作下，读操作在相关副本组中只执行一次。只有在出错 的时候，才会在同一个分片的不同副本中执行多次。

在写操作返回应答之前读取

主分片首先在本地进行索引，然后转发请求，由于主分片已经写 成功，因此在并行的读请求中，有可能在写请求返回成功之前就可以 读取更新的内容。

默认两副本

在只有2个副本的情况下，该模型也是可以容错的。这与 quorum-based的系统相反，其容错的最小副本为3。

系统异常

在出现故障时，可能产生下面的情况。

只有单个分片可能降低索引速度

因为每次操作时主分片会等待所有在in-sycn列表中的副本，所以 单个缓慢的副本可能降低整个副本组的写速度。当然，单个缓慢的分 片也会降低读取速度。

脏读

从一个被隔离的主分片进行读取，可能读取没有经过确认的写操 作。这是因为只有主分片向副分片转发请求，或者向主节点发送请求 的时候才会被隔离，此时数据已经在主分片写成功，可以被读取到。 ES 通过定期（默认为1秒）“ping”主节点来降低这种风险，如果没有 已知的主节点，则拒绝索引操作。

Allocation IDs

ES从5.x版本开始引入Allocation IDs的概念，用于主分片选举策 略。每个分片有自己唯一的Allocation ID，同时集群元信息中有一个 列表，记录了哪些分片拥有最新数据。

ES通过在集群中保留多个数据副本的方式提供故障转移功能，当 出现网络分区或节点挂掉时，更改操作可能无法在所有副本上完成， 此时我们希望把写失败的副本标记出来。

ES的数据副本模型会假定其中一个数据副本为权威副本，称之为 主分片。所有的索引操作写主分片，完成后，主分片所在节点会负责 把更改转发到活跃的备份副本，称之为副分片。如果当前主分片临时 或永久地变为不可用状态，则另一个分片副本将被提升为主分片。因 为主分片是权威的数据副本，因此在这个模型中，只把含有最新数据 的分片作为主分片是至关重要的。如果将一个旧数据的分片作为主分 片，则它将作为最终副本，从而导致这个副本之后的数据将会丢弃。 如何追踪到那个可以安全地被选为主分片的副本，也称 之为同步（in-sync）分片副本。

安全地分配主分片

分片分配就是决定哪个节点应该存储一个活跃分片的过程。分片 决策过程在主节点完成，并记录在集群状态中，该数据结构还包含了 其他元数据，如索引设置及映射。分配决策包含两部分：哪个分片应 该分配到哪个节点，以及哪个分片作为主分片，哪些作为副分片。主 节点广播集群状态到集群的所有节点。这样每个节点都有了集群状 态，它们就可以实现对请求的智能路由。因为每个节点都知道主副分 片分配到了哪里。

每个节点都会通过检查集群状态来判断某个分片是否可用。如果 一个分片被指定为主分片，则这个节点只需要加载本地分片副本，使 之可以用于搜索即可。如果一个分片被分配为副分片，则节点首先需 要从主分片所在节点复制差异数据。当集群中可用副分片不足时（在 索引设置中指定：index.number_of_replicas），主节点也可以将副 分片分配到不含任何此分片副本的节点，从而指示这些节点创建主分 片的完整副本。

在创建新索引时，主节点在选择哪个节点作为主分片方面有很大 的灵活性，会将集群均衡和其他约束（如分配感知及过滤器）考虑在 内。分配已存在的分片副本为主分片是比较少见的情况，例如，集群 完全重启（full restart），所有分片都是未分配状态，或者短时间内 所有活跃副本都变为不可用。在这种情况下，主节点询问所有节点， 找到磁盘中存在的分片副本，根据找到的副本，决定是否将其中一个 作为主分片。为了确保安全，主节点必须确保被选为主分片的副本含 有最新数据。为此，ES 使用 Allocation IDs 的概念，这是区分不同 分片的唯一标识（UUIDS）。

Allocation IDs由主节点在分片分配时指定，并由数据节点存储在 磁盘中，紧邻实际的数据分片。主节点负责追踪包含最新数据副本的 子集。这些副本集合称为同步分片标识（in-sync allocation IDs）， 存储于集群状态中。集群状态存在于集群的主节点和所有数据节点。 对集群状态的更改由zen discovery模块实现一致性支持。它确保集 群中有共同的理解，即哪些分片副本被认为是同步的（in-sync），隐 式地将那些不在同步集合中的分片副本标记为陈旧（stale）。

也就是说，Allocation IDs存储在shard级元信息中，每个shard 都有自己唯一的Allocation ID，同时集群级元信息中记录了一个被认 为 是 最 新 shard 的 Allocation ID 集 合 ， 这 个 集 合 称 为 in-sync allocation IDs 。

当分配主分片时，主节点检查磁盘中存储的 Allocation ID 是否 会在集群状态的 in-sync allocations IDs集合中出现，只有在这个集 合中找到了，此分片才有可能被选为主分片。如果活跃副本中的主分 片挂了，则in-sync集合中的活跃分片会被提升为主分片，确保集群的 写入可用性不变。

将分配标记为陈旧

在 Elasticsearch 中，数据副本和元信息副本使用不同的副本策 略，元信息的改变需要在集群层面达成一致，而数据副本使用简单的 主备方法。系统的这两个层面可以使数据副本更简单、更快。只有在 特殊情况下才需要与集群一致（consensus）层交互。处理写请求过 程中，当网络产生分区、节点故障，或者部分节点未启动，主分片本 地执行完写操作，转发到副分片时，转发操作可能在一个或多个副分 片上没能执行成功，这意味着主分片中含有一些没有传播到所有分片 的数据，如果这些副分片仍然被认为是同步的，那么即使它们遗漏了 一些变化，它们也可能稍后被选为主分片，结果丢失数据。

解决这种问题有两种方法：

• （1）让写请求失败，已经写的做回滚处理。
• （2）确保差异的（divergent）分片不再被视为同步。

ES 在这种情况下选择了写入可用性：主分片所在节点命令主节点 将差异分片的 Allocation IDs从同步集合（in-sync set）中删除。然 后，主分片所在节点等待主节点删除成功的确认消息，这个确认消息 意味着集群一致层（consensus layer）已成功更新，之后才向客户 端确认写请求。这样确保只有包含了所有已确认写入的分片副本才会 被主节点选为主分片。

不会丢失全部

发生严重灾难时，集群中可能会出现只有陈旧副本可用的情况。 ES不会把这些分片自动分配为主分片，集群将持续保持Red状态。如 果所有in-sync副本都消失了，则集群仍有可能使用陈旧副本进行恢 复，但这需要管理员手工干预。

理解分片问题的第一步是使用 cluster allocation explain API。它显示节点是否具有分片的副本， 以及相应的副本是否处于同步集合中。在文件系统损坏的情况下，它 也显示了访问磁盘信息时抛出的异常。

reroute API提供了一个子命令allocate_stale_primary，用于将 一个陈旧的分片分配为主分片。使用此命令意味着丢失给定分片副本 中缺少的数据。如果同步分片副本只是暂时不可用，则使用此命令意 味着会丢失同步分片副本中最近更新的数据。应该把它看作使集群至 少运行一些数据的最后一种措施。在所有分片副本都不存在的情况 下，还可以强制 ES 使用空分片副本分配主分片，这意味着丢失与该 分片相关联的所有先前数据。不言而喻，allocate_empty_primary 命令只能用于最糟糕的情况，其含义很好理解。

Sequence IDs

ES从6.0版本开始引入了Sequence IDs概念，使用唯一的ID来标 记每个写操作。通过这个ID我们有了索引操作的总排序。

写操作先到达主分片，主分片写完后转发到副分片，在转发到副 分片之前，增加一个计数器，为每个操作分配一个序列号是很简单 的。但是，由于节点离线随时可能发生，例如，网络分区等，主分片 可能被其他副分片取代，仅仅由主分片分配一个序列号无法保证全局 唯一性和单调性。因此，我们把当前主分片做一个标记，放到每个操 作中，这就是Primary Terms。这样，来自旧的主分片的迟到的操作 就可以被检测到然后拒绝（虽然Allocation IDs可以让主分片分配在拥 有最新数据的分片上，但仍然可能存在某些情况下主分片上的数据并 非最新，例如，手工分配主分片到有旧数据的副本）。

Primary Terms和Sequence Numbers

第一步是能够区分新旧两种主分片，我们必须找到一种方法来识 别是来自较旧的主分片操作还是来自较新的主分片的操作。最重要的 是，整个集群需要达成一致。为此，我们添加了Primary Terms。它 由主节点分配，当一个主分片被提升时，Primary Terms递增。然后 持久化到集群状态中，从而表示集群主分片所处的一个版本。有了 Primary Terms，操作历史中的任何冲突都可以通过查看操作的 Primary Terms来解决。新的Terms优先于旧Terms，拒绝过时的操 作，避免混乱的情况。

一旦我们有了Primary Terms的保护，就可以添加一个简单的计 数器，给每个操作分配一个Sequence Numbers（序列号）。 Sequence Numbers使我们能够理解发生在主分片节点上的索引操作 的特定顺序，接下来讨论Sequence Numbers带来的各种好处。可以 在Response中看到分配的Sequence Numbers和Primary Terms。

• Primary Terms由主节点分配给每个主分片，每次主分片发生变 化时递增。这和 Raft 中的 term ， 以 及 Zab 中 Viewstamped Replication的view-number概念很相似。

• Sequence Numbers标记发生在某个分片上的写操作。由主分 片分配，只对写操作分配。假设索引website有2个主分片和1个副分 片，当分片website[0]的序列号增加到5时，它的主分片离线，副分 片被提升为新的主分片，对于后续写操作，序列号从6开始递增。分片 website[1]有自己独立的序列号计数器。

主分片每次向副分片转发写请求时，会带上这两个值。 为了实现将操作排序，当我们比较两个操作o1和o2时，如果o1 ＜ o2，那么意味着：

s1.seq# < s2.seq#

或者

（s1.seq# == s2.seq# and s1.term < s2.term）

本地及全局检查点

有了Primary Terms和Sequence Numbers，我们就有了在理 论上能够检测出分片之间差异，并在主分片失效时，重新对齐它们的 工具。旧主分片就可以恢复为与拥有更高 Primary Terms值的新主分 片一致：从旧主分片中删除新主分片操作历史中不存在的操作，并将 缺少的操作索引到旧主分片。

遗憾的是，当同时为每秒成百上千的事件做索引时，比较数百万 个操作的历史是不切实际的。存储成本非常昂贵，直接进行比较的计 算工作量太大。为了解决这个问题，ES维护了一个名为“全局检查点” （global checkpoint）的安全标记。

全局检查点是所有活跃分片历史都已对齐的序列号，换句话说， 所有低于全局检查点的操作都保证已被所有活跃的分片处理完毕。这 意味着，当主分片失效时，我们只需要比较新主分片与其他副分片之 间的最后一个全局检查点之后的操作即可。当旧主分片恢复时，我们 使用它知道的全局检查点，与新主分片进行比较。这样，我们只有小 部分操作需要比较，不用比较全部。

主分片负责推进全局检查点，它通过跟踪在副分片上完成的操作 来实现。一旦它检测到所有副分片已经超出给定序列号，它将相应地 更新全局检查点。副分片不会跟踪所有操作，而是维护一个类似全局 检查点局部变量，称为本地检查点。

本地检查点也是一个序列号，所有序列号低于它的操作都已在该 分片上处理（Lucene 和translog写成功，不一定刷盘）完毕。当副 分片确认（ACK）一个写操作到主分片节点时，它们也会更新本地检 查点。使用本地检查点，主分片节点能够更新全局检查点，然后在下 一次索引操作时将其发送到所有分片副本。

全局检测点和本地检查点在内存中维护，但也会保存在每个 Lucene提交的元数据中。

某索引有1个主分片、2个副分片，初始状态没有数据，全局检查 点和本地检查点都在0位置，如下图所示。

主分片写入一条数据成功后，本地检查点向前推进，如下图所 示。

主分片将写请求转发到副分片，副分片本地处理成功后，将本地 检查点向前推进，如下图所示。

主分片收到所有副分片都处理成功的消息，根据汇报的各副本上 的本地检查点更新全局检查点，如下图所示。

在下一次索引操作时，主分片节点将全局检查点发送到所有分片 副本，如下图所示。

全局检查点还有另外一个很好的属性—它代表了已经保证存盘的 操作边界（存储在所有活跃分片中）。如果主分片故障，则数据没有 来得及复制到副分片，该区域（大于全局检测点的）可以包含可能需 要回滚的操作。这是一个微妙且重要的属性，对于未来的更改API或跨 数据中心复制功能来说至关重要。

用于快速恢复（Recovery）

当ES恢复一个分片时，需要保证恢复之后与主分片一致。对于冷 数据来说，synced flush可以快速验证副分片与主分片是否相同，但 对于热数据来说，恢复过程需要从主分片复制整个Lucene分段，如果 分段很大，则是非常耗时的操作。

现在我们使用副本所知道的最后一个全局检查点，重放来自主分 片事务日志（translog）中的相关更改。也就是说，现在可以计算出 待恢复分片与主分片数据的差异范围，因此避免复制整个分片。同 时，我们多保留一些事务日志（默认为512MB,12小时），直到“太 大”或“太老”。如果不能从事务日志恢复，则使用旧的恢复模式。

version

每个文档都有一个版本号（_version），当文档被修改时版本号 递增。ES 使用这个_version来确保变更以正确顺序执行。如果旧版本 的文档在新版本之后到达，则它可以被简单地忽略。例如，索引 recovery阶段就利用了这个特性。

版本号由主分片生成，在将请求转发给副本片时将携带此版本 号。

版本号的另一个作用是实现乐观锁，如同其他数据库的乐观锁一 样。我们在写请求中指定文档的版本号，如果文档的当前版本与请求 中指定的版本号不同，则请求会失败。