2 posts tagged with "引擎"

数值（Numberic）在搜索引擎中通常扮演着重要的角色，例如：

• 等值比较：x = ?
• 大小比较：x > 1
• 集合判断：x in ( 1, 3, 5, 8, 9)
• 范围查询：x in [100 .. 200]
• 距离计算：distance(x,y)

如何通过设计优良的数据结构和算法，搭配统一的执行框架高效的满足以上场景，我们从开源引擎 Lucene Point 的设计来展开分析。本文希望通过通俗易懂的图文方式一步步剖析它的原理进而了解其背后的的设计思想，而不是枯燥的理论知识。

执行框架​

如上图，简要来说：

1. 构建便于快速查询的核心索引结构：由 binary tree index (point) + Leaf(point,docid映射) 组成。
2. 执行检索时基于tree的二分法快速定位匹配的 leaf block。
3. 通过leaf block取出对应的文档列表(docid ...)
4. 为满足不同的查询场景，visitor抽象了数据的访问方式，用于实现不同query的遍历算法。

索引文件结构分析​

Leaf Block文件格式总体分为三大块

• meta: 整块索引的元信息
• body: 叶子列表，一个leaf block 由docid,point组成的pair双数组的集合， pair的长度通常为1024。
• foot: 尾部信息

这里我们可以直观的感受到数值数据经过分块后带来了哪些好处：

1. 检索复杂度降低，如1亿个整数，通过block打包后降到10W个。
2. 提升内存操作效率，在索引创建或加载时，由于block长度统一，整块索引的操作效率要远高于单个数值的操作。
3. 节省磁盘存储空间，由于block内数值是排好序的，可以利用各种压缩算法降低存储空间。

1. meta部分​

• numDims - 维度，例如IntPoint为1维
• maxPointsInLeafNode - 一个叶子包含多少point, 默认1024
• bytesPerDim - 每个维点字节数, 例如IntPoint为4个字节
• numLeaves - 多少个叶子
• minPackedValue - 最小point value
• maxPackedValue - 最大point value
• pointCount - point总数
• docCount - docid 总数
• packedIndex - 压缩字节的索引（新版本都采用此方式，比legacy index format节约40%空间）

2. 单个leaf的文件格式​

• Count: leaf内包含多少point
• DocIds: 无序的docid数组
• Values: 有序的point数组。

核心源码指引

private void writeIndex(IndexOutput out, int countPerLeaf, int numLeaves, byte[] packedIndex) throws IOException {
    
    CodecUtil.writeHeader(out, CODEC_NAME, VERSION_CURRENT); // 从头部写入
    out.writeVInt(numDims); // 存在几个维度
    out.writeVInt(countPerLeaf); // 每个叶子Block的个数 （默认1024）
    out.writeVInt(bytesPerDim); // 每个维点的字节数 (整数为4)

    assert numLeaves > 0;
    out.writeVInt(numLeaves); // 叶子节点数
    out.writeBytes(minPackedValue, 0, packedBytesLength); // 最小值
    out.writeBytes(maxPackedValue, 0, packedBytesLength); // 最大值

    out.writeVLong(pointCount); // point值的个数
    out.writeVInt(docsSeen.cardinality()); // docid的个数
    out.writeVInt(packedIndex.length);
    out.writeBytes(packedIndex, 0, packedIndex.length);
  }

检索流程​

1. 加载BKDReader 有多少个dim文件就创建多少个BKDReader，BKDReader通过读取meta部分完成初始化。
2. 为leaf blocks构建完全平衡二叉树。根据numLeaves计算深度，从左到右填满树。
3. 检索方式 visitor抽象了访问方式，不同类型的查询Query采用不同的检索访问器。

范围检索流程​

例如 newRangeQuery(200, 300) 这里访问器采用PointRangeQuery::内部IntersectVistor， 通过一次次索引块的compare取出所有的docid。

集合检索流程​

例如 newSetQuery(1, 3, 6, 5, 123, 9999); 和Rang的区别MergePointVisitor会携带查询状态一次遍历完整颗树。

如上图，集合类查询有点像坐公交，出发时携带所有参数，迭代过程如遇到匹配的参数则剔除掉再进入下一个block。

取值过程​

取docid过程较为简单，seek各个检索满足条件的值到 PointValueQuery.result里

详细算法见BKDReader :: visitCompressedDocValues

总结​

Point所采用的的 block k-d trees 是一种简单而强大的数据结构。在索引时，它们是通过递归将要索引的N维点的整个空间划分为越来越小的矩形单元，在递归的每个步骤中，沿着最宽的维度均等地分割。然而，与普通的k-d树不同，一旦单元格中的点数少于预先指定的（默认情况下为1024），k-d trees 就停止递归。

此时，该单元中的所有点都被写入磁盘上的一个leaf block中，该块的起始文件指针被保存到堆内binary tree中。在1维的情况下，这仅仅是所有值的完整排序，划分为相邻的叶块。有的k-d树变体可以支持删除值和重新平衡，但Lucene不需要这些操作，因为它为每段的一次写入设计。

在搜索时，进行相同的递归，在每个level测试所请求的查询条件是否与每个维度分割的左或右子树相交，如果是，则递归。在1维情况下，查询形状只是一个数字范围，而在2D和3D情况下，它是一个地理空间形状（圆形、环形、矩形、多边形、立方体等）

Vistor 抽象了遍历算法，感兴趣的同学可以根据该框架自行扩展，而不会破坏核心的执行框架。

纳速云 XDCR(Cross DataCenter Replication)​

XDCR 跨集群复制通常用于以下场景：

• 异地高可用 (HA)：对于许多核心链路应用程序，都需要能够承受住数据中心或区域服务中断的影响。通过 XDCR 中的原生功能即可满足跨数据中心的 DR/HA 要求，且无需其他技术。
• 就近访问：将数据复制到更靠近用户或应用程序服务器的位置，可以减少延迟，降低成本。例如，可以将产品列表或参考数据集复制到全球 20 个或更多数据中心，最大限度地缩短数据与应用程序服务器之间的距离。

CCR vs XDCR​

Elastic 官方的 CCR (cross-clusterreplication）也提供了类似的功能，CCR 属于xpack增强包中的功能，需要白金级、企业级证书才可使用。而XDCR 诞生于蚂蚁金服，由城破带领的搜索内核团队打造，该方案实际上比社区的 CCR 早半年落地，通过不断的踩坑和优化，最终满足了金融场景下对数据可用性和容灾能力极为严苛的要求。

本文从原理及设计层面阐述两者的不同之处。

顶层设计​

面向分布式系统，一款优秀的高可用方案从顶层设计层面要抓住以下几点：

1. 面向错误设计

分布式环境的复杂性往往会遇到不可预期的异常，如网络错误、格式冲突、节点hang住、异常流量、用户操作打断等等。设计层面要充分考虑这些因素，当异常发生时做到：

• 核心服务解耦：主备集群相互无干扰。
• 无状态化：复制任务保证原子性和无状态，任务之间无关联，失败后可重试。
• 无干预：异常恢复时，任务可自动调度恢复，无需人为介入。

2. 数据一致性

任何情况下，即便是数据丢失也比错误的数据可接受。

• 采用更简单的单主模式，放弃双AA。
• 始终通过operation_log恢复，保证数据一致性。
• 垃圾数据可丢弃、可强制覆盖。

3. 可扩展性

从平台层面，面向不可预期的业务数据增长：

• 复杂度可控：不会随着索引的增加导致任务的指数级增加。
• 资源可控：计算资源始终控制在合理的资源池内。

4. 可观测性

通过接口暴露底层任务状态，通过外围工具辅助监控报警，做到第一时间能发现现场：

• 任务实时状态
• 计算消耗状态

设计架构​

CCR和XDCR都是采用拉模式（Pull Mode）：即备集群创建协调任务，主动从主集群拉取数据差异并写回备集群 :

拉模式相对于推模式的方案更为简洁：

1. 主集群处理逻辑简单，只需要控制好拉请求的资源保护即可。
2. 备集群通过任务的无状态化设计，保障断点续传的可靠性即可。

实现层面差异​

CCR​

核心任务处理逻辑

代码片段

    
    void start(...) {
        ...
        // 更新备集群mapping，提供了Leader的mapping version，并确保相同。
        updateMapping(0L, leaderMappingVersion -> {
            synchronized (ShardFollowNodeTask.this) {
                currentMappingVersion = Math.max(currentMappingVersion, leaderMappingVersion);
            }
            updateSettings(leaderSettingsVersion -> {
                synchronized (ShardFollowNodeTask.this) {
                    currentSettingsVersion = Math.max(currentSettingsVersion, leaderSettingsVersion);
                }
                // 协调读，取出数据差异进行复制。
                coordinateReads();
            });
        });
    }

CCR跨集群复制，将元数据同步和数据同步串联在主链路上，在分片数量不多的情况下能稳定的运行，但试想下如果是平台级的集群级同步，有成千上万个shard同步任务并行运行时，读取master的集群状态开销就不可小视了。

XDCR​

XDCR从架构层面将元数据同步和Shard数据同步进行了分拆，如下图所示：

核心差异

1. 备集群始终只维护一个全局的元数据同步任务，用于同步所有已注册同步的索引mapping和setting。
2. 分片同步只处理数据同步，如遇到mapping,setting不一致则抛出异常，通过不断重试等待元数据同步后恢复。

从现象上来看，当主集群的索引mapping或setting更新时，XDCR相对CCR会停顿几秒 然后跟上。但带来的好处是：

1. 在大规模的同步场景下，集群的master压力直线下降，且不会随着分片的增长而增加。
2. 分片复制任务更为精简，功能原子性更强，更易于后期的架构演变。

本文阐述了两者的核心差异，当然还有更多的细节差异，如有兴趣的同学可以阅读XDCR源码分析。