批量取回分片文档后恢复全局命中顺序
Elasticsearch 先按分片把已排好序的命中分组取回,再利用原始位置与每个分片的游标恢复最终结果顺序。
工程问题#
搜索协调节点已经知道全局命中次序,但完整文档分布在不同分片。逐条远程取回开销高;按分片批量请求又会打散全局顺序,而且分片内部更适合按文档编号访问。
实际实现#
fillDocIdsToLoad 按 shardIndex 把全局 ScoreDoc 序列稳定分组。分片同步 fetch 把 docId 与请求位置一起保存,按 docId 排序访问,然后将结果写回请求位置。协调节点再次遍历原全局序列,使用对应分片的递增计数器取出下一个文档,从而恢复整体顺序。
处理流程#
- 对已确定的全局命中序列按分片稳定分组
- 每个有命中的分片收到一批 docId 请求
- 分片按 docId 读取,借助原始位置数组恢复请求次序
- 协调节点按全局序列遍历,以分片游标取回对应命中
源码片段#
固定版本 · 原文摘录140 final ScoreDoc[] lastEmittedDocPerShard = context.getRequest().scroll() != null141 ? SearchPhaseController.getLastEmittedDocPerShard(reducedQueryPhase, numShards)142 : null;143 final List<Integer>[] docIdsToLoad = SearchPhaseController.fillDocIdsToLoad(numShards, scoreDocs);144 context.addReleasable(fetchResults);145 final CountedCollector<FetchSearchResult> counter = new CountedCollector<>(146 fetchResults,147 docIdsToLoad.length, // we count down every shard in the result no matter if we got any results or not148 () -> moveToNextPhase(fetchResults.getAtomicArray(), fetchResults::transferCharge, reducedQueryPhase, phaseStartTimeInNanos),149 context150 );在 fetch 阶段把 scoreDocs 按分片拆分,并用计数收集器等待各分片完成;没有命中的分片也需要完成计数。
204 public static List<Integer>[] fillDocIdsToLoad(int numShards, ScoreDoc[] shardDocs) {205 @SuppressWarnings("unchecked")206 List<Integer>[] docIdsToLoad = (List<Integer>[]) new ArrayList<?>[numShards];207 for (ScoreDoc shardDoc : shardDocs) {208 List<Integer> shardDocIdsToLoad = docIdsToLoad[shardDoc.shardIndex];209 if (shardDocIdsToLoad == null) {210 shardDocIdsToLoad = docIdsToLoad[shardDoc.shardIndex] = new ArrayList<>();211 }212 shardDocIdsToLoad.add(shardDoc.doc);213 }214 return docIdsToLoad;215 }依次扫描全局顺序,并 append 到分片列表,保留每个分片命中在全局序列中的相对次序。
129 SearchHit[] searchHits = new SearchHit[docIds.length];130 DocIdToIndex[] docs = new DocIdToIndex[docIds.length];131 for (int index = 0; index < docIds.length; index++) {132 docs[index] = new DocIdToIndex(docIds[index], index);133 }134 // make sure that we iterate in doc id order135 Arrays.sort(docs);136 int currentDoc = docs.length > 0 ? docs[0].docId : -1;137138 try {139 if (docs.length == 0) {140 return new IterateResult(searchHits);141 }142143 int leafOrd = ReaderUtil.subIndex(docs[0].docId, indexReader.leaves());144 LeafReaderContext ctx = indexReader.leaves().get(leafOrd);145 int endReaderIdx = endReaderIdx(ctx, 0, docs);为每个 docId 保存原请求下标,再按 docId 排序;原下标让内部 I/O 顺序与输出顺序可以不同。
156 for (int i = 0; i < docs.length; i++) {157 try {158 if (i >= endReaderIdx) {159 leafOrd = ReaderUtil.subIndex(docs[i].docId, indexReader.leaves());160 ctx = indexReader.leaves().get(leafOrd);161 endReaderIdx = endReaderIdx(ctx, i, docs);162 docsInLeaf = docIdsInLeaf(i, endReaderIdx, docs, ctx.docBase);163 setNextReader(ctx, docsInLeaf);164 }165 currentDoc = docs[i].docId;166 assert searchHits[docs[i].index] == null;167 searchHits[docs[i].index] = nextDoc(docs[i].docId);168 } catch (ContextIndexSearcher.TimeExceededException e) {169 if (allowPartialResults == false) {170 purgeSearchHits(searchHits);171 }172 SearchTimeoutException.handleTimeout(allowPartialResults, shardTarget, querySearchResult);173 assert allowPartialResults;174 onAllHitsIterated();175 return new IterateResult(stripNulls(searchHits));正常读取写入 searchHits[原下标];超时分支会返回部分结果,因此不能省略完整响应这一适用条件。
313 var fetchResults = fetchResultsArray.asList();314 // clean the fetch counter315 for (SearchPhaseResult entry : fetchResults) {316 entry.fetchResult().initCounter();317 }318 int from = ignoreFrom ? 0 : reducedQueryPhase.from;319 int numSearchHits = (int) Math.min(reducedQueryPhase.fetchHits - from, reducedQueryPhase.size);320 // with collapsing we can have more fetch hits than sorted docs321 // also we need to take into account that we potentially have completion suggestions stored in the scoreDocs array322 numSearchHits = Math.min(sortedTopDocs.scoreDocs.length - sortedTopDocs.numberOfCompletionsSuggestions, numSearchHits);323 // merge hits324 List<SearchHit> hits = new ArrayList<>();325 if (fetchResults.isEmpty() == false) {326 for (int i = 0; i < numSearchHits; i++) {327 ScoreDoc shardDoc = sortedTopDocs.scoreDocs[i];328 SearchPhaseResult fetchResultProvider = fetchResultsArray.get(shardDoc.shardIndex);329 if (fetchResultProvider == null) {330 // this can happen if we are hitting a shard failure during the fetch phase331 // in this case we referenced the shard result via the ScoreDoc but never got a332 // result from fetch.333 // TODO it would be nice to assert this in the future334 continue;先清零分片游标,再按 sortedTopDocs 遍历;结果数组用 shardIndex 定位对应分片,缺失分片会跳过。
336 FetchSearchResult fetchResult = fetchResultProvider.fetchResult();337 final int index = fetchResult.counterGetAndIncrement();338 if (index >= fetchResult.hits().getHits().length) {339 // the fetch phase on this shard timed out and returned partial results340 continue;341 }342 SearchHit searchHit = fetchResult.hits().getHits()[index];343 searchHit.shard(fetchResult.getSearchShardTarget());每遇到该分片的一项命中,消费它返回数组中的下一项;核心依据是分组与返回过程都保留分片内相对顺序。
片段保持固定提交的连续原文;完整源码与许可证保存在本地。每段说明交代所在分支,省略部分可通过出处查看。
收益与取舍#
工程分析带来的收益
- 正常完整响应下不需要重新比较分数或对完整文档排序,协调端的分组和重建均为线性遍历
- 分片内部可以按文档编号改善读取局部性,同时保持外部要求的结果次序
付出的代价
- 必须同时保持分片请求的稳定顺序和返回的位置关系;分片结果到达顺序本身不能用作最终排名
- 需要保存命中序列、分片列表和结果数组;分片内部 docId 排序另有成本
- 分片失败或 fetch 超时会进入部分结果分支,完整取回与严格一一对应的前提不再成立;本文不把完整响应结论外推到这些分支
可比较的选择
逐条远程 fetch位置关系直接,但增加请求数量和调度开销。
用文档标识建映射后重排可显式按键定位结果,但需额外映射结构;本路径利用已有顺序协议和分片游标。
版本与适用范围#
对应固定提交的普通同步 fetch 与 SearchPhaseController 合并路径,前提是 query 阶段已确定全局顺序且相关分片完整返回。本文分析文档取回的稳定分组与重建,不把 TopDocs.merge 的调用当作完整堆归并实现;流式 fetch 和部分结果行为不在本文证明范围内。
参考来源#
源码、官方文档与原始论文server/src/main/java/org/elasticsearch/action/search/FetchSearchPhase.java · FetchSearchPhase:批量请求准备
server/src/main/java/org/elasticsearch/action/search/SearchPhaseController.java · fillDocIdsToLoad
server/src/main/java/org/elasticsearch/search/fetch/FetchPhaseDocsIterator.java · FetchPhaseDocsIterator:排序读取
server/src/main/java/org/elasticsearch/search/fetch/FetchPhase.java · 同步 fetch 构造 SearchHits
相关实现与比较#
4 个相关案例nginx 解析 upstream 块时,用 ngx_array_t 连续保存服务器条目;每遇到一条 server 指令便追加一个元素。
Linux IIO 的 kfifo 缓冲在采样进入内核与用户态读取之间暂存数据,按先进先出顺序交付采样记录。
Linux BPF 验证器的 check_cfg 使用显式指令栈执行非递归 DFS,检查跳转目标、可达性及控制流结构。
Git 把内存中的 index 条目指针保存在有序、可增长的数组中,按路径和合并 stage 二分查找位置。