假如我来设计scroll－Elasticsearch的遍历操作分析

Es低版本（1.x）的scroll操作还有一个变种：scan，其在指定size时真实返回的是size * num_of_shards条数据，比如scan请求返回size=10条数据，而索引本身有5个shard，那么一次scan将返回10*5=50条数据，另外在第一次请求时只执行初始化操作，不会返回数据，在第二次请求时才会返回数据。

到了Es最近版本（5.x，写作时6.0也正式发布了），取消了scan变种，只留下scroll操作，在指定size时只会返回size条数据，而且第一次请求即会返回。

因为索引一般是分片的，也就是有多个shard，shard之间的数据通过文档的_id＋一致性hash来分配，假设要取出索引的前10条数据并按照指定字段排序，只能是在每个shard都取出10条数据，然后通过优先级队列或者其他容器merge这些数据，排序后取出前10条作为结果返回。

为了性能考虑，跳过merge步骤直接把收集到原始数据返回确实是最有效率的方法，所以到了Es5版本竟然没了scan确实有点惊讶于这版本Es的实现。 

自己的实现

静下心来仔细想想之后，发现要实现这个其实也并不复杂，我甚至想起曾经在一个搜索结果merge需求中自己设计过的方法。

假设有n个搜索结果集（ResultSet），每个结果集均按照score字段排序，要求：

1. 从n个结果集中取出m个结果合并为一个结果集（m与n无固定关系）

2. n个结果集中的数据必须至少有一条包含在最终结果中

3. 任意结果集中按照score大小顺序取值

4. 结果合并必须支持分页

（如图为需要合并的结果集）

方案设计其实也很简单，因为结果集中的数据都是有序的，首页的结果只要循环按顺序从n个结果集中取一条数据合并就可以满足；再抽象一下，根据这种固定模式，通过任意一次请求的from来计算每个结果集的偏移量offset，从每个结果集的第offset+1个结果开始顺序取结果就能满足如上要求了。

（按图示，RS0～4依次循环取doc合并即可得到最终结果，

其中RS0的下一次请求偏移量为2，其余均为1）

代码实现还是比较简短的，首先是计算每个分片（shard）内的请求需要的偏移量（newfrom）和返回结果数（newsize）：

private void procOffset(int from, int size, int shards) {
    // 演示计算，newfrom／newsize表示最终计算得到的每个分片的偏移量
    int[] newfrom = new int[shards];
    int[] newsize = new int[shards];
    for (int i = 0; i < newfrom.length; i++) {
        newfrom[i] = 0;
    }
    for (int i = 0; i < newsize.length; i++) {
        newsize[i] = 0;
    }
    while (from > 0 || size > 0) {
        for (int i = 0; i < shards; i++) {
            // 计算每个分片的偏移量
            if (from > 0) {
                // 先处理from偏移
                newfrom[i]++;
                from--;
            } else {
                // from偏移处理完成后再处理size,保证size偏移的起点紧接于from偏移的终点
                newsize[i]++;
                size--;
            }
            if (from == 0 && size == 0) {
                break;
            }
        }
    }
}

然后是取得结果后的结果合并操作：

// Item表示每个shard返回的结果集，Hit表示单结果
private QuerySerDer mergeResult(Item[] items) {
    List<Hit> results = new LinkedList<>();
    // 表示遍历子查询结果的数组位置，一轮变一次
    int index = 0;
    boolean hasNext;
    for (; ; ) {
        hasNext = false;
        for (Item item : items) {
            if (item.isFailure()) {
                // 子查询失败，跳过
                continue;
            }
            if (null == item.getHits() || item.getHits().length == 0) {
                // 如果子查询没有结果，跳入下一个子查询
                continue;
            }
            if (item.getHits().length <= index) {
                // 如果子查询的长度不足（总长度小于本轮偏移量），进入下一个子查询结果
                continue;
            }
            hasNext = true;
            Hit hit = item.getHits()[index];
            results.add(hit);
        }
        if (!hasNext) {
            break;
        }
        // 全部子查询遍历之后偏移量＋1
        index++;
    }

return results;
}

实现了上面四点要求就已经可以满足scroll按需返回size条记录了。 

为什么不能用深翻页

上面讲了那么多，如果要根据条件取全部结果，为什么不直接用翻页解决呢？

假设有n个分片（shard），现要求取第from条结果开始的size条数据，首先需要从每个分片取from+size条数据，然后在client节点merge，总共n * (from + size)条数据，然后取第from条结果后的size条数据，那么有效数据占总获取数据量的比率是：

• size / (n * (from + size))

来算算实际场景下的有效数据占比，假设索引分片数为5，每页返回10条数据：

可以看到在页数到达1000页时，有效数据仅占全部取出数据的0.02%，加上前后页的跳转（从第99页翻到第100页再到第101页，也就是三次巨大浪费的计算），将会造成大量的内存垃圾并浪费相当的计算资源，不仅挤占其他索引的资源，也加快了gc触发频率，甚至可能引起full gc，带来严重的性能损耗。

所以我们说深翻页（deep pagination）不可取，生产业务最好禁止此类查询，除了性能上的考量，也可以提升系统的稳定性。 

无序scroll分析

说了这么多，回到正题，首先来简单介绍下Es的scroll过程：

1. 发送一个普通的query至服务端，同时在请求中带上scroll参数表明这是一个scroll请求

2. 服务端返回结果，并带上特殊的scroll_id来记录请求上下文

3. 调用特殊的_scroll请求并带上最新的scroll_id来继续后续请求

先来分析下Es1版本对scan的处理，上面说到了scan其实是从每个shard中都取size条数据汇总后一起返回，并且结果是无序的。这样的话，每次scan请求返回的数据就可以跳过merge阶段直接返回，可以说每次请求的有效数据占比达到了100%，确实相当高效。

再来到Es5版本，这个版本号称对_doc排序做了特殊优化，可以保证翻页高效，因此取消了scan操作，引用下原文：“Scroll requests sorted by _doc have been optimized to more efficiently resume from where the previous request stopped.”

简单来说就是_doc排序的scroll请求可以高效利用上次请求结束时的偏移量，_doc代表的是lucene内部对索引文档标记的唯一键，是一个自增的int值，外部是感知不到的，而且_doc在每次对文档进行写操作时都会变，对我们来说，其实就表示返回的结果是无序的。

假设一个索引分为n个shard，每个shard在Es内部都有shardId属性，也就是shard是可以排序的，那么只要按顺序挨个从每个shard中取出size条数返回，然后在scroll_id中记录当前取到的shardId或者每个shard的结果偏移量，也可以保证每次scroll请求达到100%的有效数据占比。

• size / (1 * size + (n - 1) * 0) = 1

注：scroll操作可以把有效数据比率公式中的from理解为恒等于0，因为记录了偏移量，所以不需要取全部结果从头合并。

再进一步，假设scroll一次请求100万数据，那么上面分析的方法就有问题，通过n个分片并行操作，每个分片取一部分数据，因为磁盘io的关系，显然是比单个分片内取全部数据来的快。这时候可以将参考上文中的第一种实现方法，根据上下文计算每个分片的偏移量和结果数，将请求分发给每个shard并行处理，然后将各结果合并即可，虽然多了合并过程，但是并不需要对结果进行排序，只简单的扔到一个容器内即可，还是可以满足100%的有效数据比。

注：如果size＝10，那么多个分片并行取数可能在网络开销上耗费的时间更多，极致的性能优化需要根据请求的size数来决策控制各分片的偏移量和结果数。

有序scroll分析

说完高效的无序scroll，再来说说带排序条件的scroll请求，一个索引的shard之间的数据一般是根据_id通过一致性hash来分配的，_id可以理解为索引文档的唯一键（可以用户自行设置或者让Es自动生成），也就是索引数据在各个shard之间是随机分布的，那么如果要返回按指定顺序排列的结果，只能通过combine多个shard的数据并重排序，scroll操作也不例外。

（如图所示，以请求2个结果为例，最终结果来自shard4+shard1，

但是没有拿到全部结果前是无法判断的，而剩余的8条记录都是废弃不用的）

因为上下文记录了各个shard的结果偏移量，所以只需要分别从各个shard中取出排序之后的第from至from+size条数据，然后再汇总结果重排序后取size条结果，同时重置上下文记录各shard新的结果偏移量返回即可，虽然相对无序scroll确实效率要低一些，但是比起深翻页来还是能保证相对高的有效数据占比，而且不会随着翻页深度增加而变低：

• size / (n * size) = 1 / n

还是以size＝10，n＝5为例，有效数据占比恒定在20%，也就是普通翻页查询时有效数据占比的最高点。 

scroll的限制

到这里，我们回来看看scroll请求的前提条件：

1. 记录每次请求的上下文

2. 保证遍历的数据稳定不变

每次scroll请求都需要知道上次请求停止的点（偏移量），所以上下文是必须要记录的。一般情况下，索引数据是在不断变更过程中的，也就是scroll过程其实是伴随着数据的增删改操作的，如果以这种状态去根据上下文取数据，很有可能就会发生数据丢失的情况：

（如图所示，假设数据可变，如果两次请求间第2条数据被删除，

那么第2次请求带上偏移量5的上下文就会导致第6条数据在本次遍历中被跳过）

scroll其实遍历的是索引接收到scroll请求当时的一个快照（snapshot）数据，一个快照对应一个search context，如果context不关闭，searcher已经打开的段文件（segment）是无法删除的，即使这个段文件因为后台的段合并过程而已经变成了废弃状态。因此scroll是限定了一个过期时间（expiry time）的，就是为了保证废弃段文件能够被及时删除，避免过多的段文件导致操作系统文件句柄耗尽。

理论上通过scroll上下文，是可以做到往回翻页的（偏移量回退size个），个人感觉原因之一也是为了保证snapshot数据及时过期吧，毕竟单向翻页可以预期到过程结束，如果是双向翻页就不一定能那么快结束了。 

shard内部排序

从分片内查询结果并排序后，才能进行下一步的结果集合并，影响scroll取数性能表现的基础就是分片内的查询效率。

上面说到_doc，虽然外部无法感知而且每次索引写操作后_doc都会发变化，但是在一个快照（snapshot）时间内，索引文档可以认为是维持不变的，所以_doc可以保证文档顺序，就可以保证多次scroll请求之间不会拉取重复数据。

细说这个_doc，我们知道索引文档在索引文件内部是按顺序排列的，_doc其实就是索引文件内部索引文档的排列顺序，在分片内部执行constant_score查询（匹配分恒等于1）后的结果顺序天然就是按照_doc排序的，所以_doc排序请求连分片内部的排序步骤也省去了，真是做到了极致。

相对的，有序scroll在分片内部执行查询时，虽然查询步骤相同，但是还需要增加一个按指定字段重排序的步骤，相应的取数效率就低了一些。 

在Es中创建索引都是可以配置分片（shard）个数的，合理的配置分片数量是保证索引查询性能的关键因素之一，过多的shard数会导致merge的结果集数量过多，导致merge效率降低；而过少的shard虽然不影响merge效率，但是在索引数据量很大的情况下，会导致单shard内文档数量过多，会因为字段缓存（体积太大）和中间结果合并（单位条件命中的倒排结果集过大，影响取交性能）等因素影响分片内查询性能，也就拖慢了整体的查询响应。

另外合理的size设置也是需要考虑的一个方面，过大的size导致过重的io操作，容易变成慢查询，过小的size设置又会带来过多的网络传输开销，一般建议size设置在100～1000之间，相信Es应该也有默认的范围限制过大的size。

当然通过上面的分析，能通过无序scroll遍历数据就通过无序scroll操作也是提高性能表现的好手段。 

至此对Es的scroll操作分析结束，本想翻些源码来印证，然而只翻到结果合并部分代码，所以不敢妄言Es的scroll设计就是如此，不过我想应该也大概如此吧，如果有熟悉Es源码的高手，还请不吝赐教。 

欢迎大家长按关注跳跳爸的微信公众号：