标题：奥德赛：在分布式时序相似性检索的大陆上的一场旅行
【奥德赛一周目毕业玩家飘过:)】

编者的总结

1. 本文针对的是现代分布式集群上的【内存型】时序索引，查询模式是精确knn查询，主要度量指标就是平均时延。
2. 整体的架构设计是比较完整的，应该是第一个真正意义上的内核索引。
3. 核心算法还是iSAX索引，本文给出了一个水平分片+垂直冗余的架构设计，满足查询时负载均衡的数据放置策略，基于简单的代价估计做动态查询负载均衡，设计了任务偷取加强负载均衡。一套组合拳，但技术上难度均不大。

编者的思考

1. 因为之前的分布式时序索引TARDIS不支持精确knn查询，所以本文可以说是补了这个空。MESSI主要的点在并行方面，没有做到完全的分布式。本文虽然没提近似搜索的内容，但应该也能扩展。
2. 之前时序索引的核心思路是把相近的序列放到一起，但本文的想法是把相似的序列分散着放来保证查询时的负载均衡。我觉得前者可能对吞吐量友好，毕竟总的代价是比较低的，后者也就是本文，对平均时延会更友好一些。这里也许还值得再探索一下。
3. 由于本文是C+MPI来编写的，又不涉及采样等操作，所以理论上应该能支持动态数据集，这相比于TARDIS又减少了一个限制。
4. 基于磁盘的能支持精确knn的时序索引还是一个坑，如果能拓展到云环境下则会更好。

1 Introduction

• 本文的目的就是把一个现代分布式集群的算力榨干，获得最牛的索引性能;
• 一个很重要的目标是可伸缩性，节点数量增加，查询时间代价应该能接近同比减少。要达到这个目标要解决两个问题：
  1. scheduling: 查询任务调度，要尽量公平的分配查询任务；要想能有调度，就必须有查询代价估计，这一点目前还没有工作；
  2. load-balance：查询负载均衡，先完成的节点要去帮助那些没完成的节点；要想足够公平，冗余些数据是常见的解决方案，但无可避免引入些索引构建代价；

3 The Odyssey Framework

Odyssey的整体框架分5步：

1. 第一步首先数据分区，分成节点个数那么多的区，然后塞给每个节点一个分区；
2. 第二步在节点内构建本地索引；然后构建复制组，复制组内的节点都是同样的数据；组内有一个协调者，负责查询调度；
3. 第三阶段是代价估计，代价高的先执行，动态地将查询下发给组协调者；
4. 第四阶段是节点来做具体查询，在此阶段作者也提出了一些新的并行技术；
5. 第五阶段是局部结果的汇总。

image.png

3.1 Query Scheduling

给定一组query，要想得到精确结果，必须首先选择一组覆盖全部数据集的节点，称为cluster（cluster内各节点的数据不重合）。让哪一组去执行哪一些query，就是调度要做的内容。

• 调度很重要的一个前提是代价估计，否则很容易造成负载不均衡的情况；

• 如何做代价估计，过往的工作提示我们，第一个叶子节点带来的初始BSF就是query难度/查询代价的一个重要indicator，见下图：

  
  image.png

作者提供了三种方法进行调度：

1. 静态不排序分配：以贪婪的方式直接进行分配，把当前Query发送给累计代价最小的cluster；
2. 静态排序分配：首先将query按照代价降序排列，剩下的和1是相同的；
3. 动态排序分配（最佳）：首先排序，然后每个cluster分配一个任务，之后的任务分配按照完成时间来确定，即按照真实代价来分配。

3.2 Load Balancing

3.2.1 Single-Node Query Answering

首先讲单节点是如何做查询的。

• 单节点逐个处理收到的查询请求；
• 一个创新的设计就是工作偷取(work-stealing)，在同一个复制组内，一个节点活干完了会主动告知其他节点，每个节点都会有一个专门为work-stealing服务的线程，专门处理这类消息；
• 节点内查询主流程如下图：按照Root subtree分割工作量，共分工作线程个数份即可，每个线程取一个RS-batch，遍历一遍进行剪枝，剪不掉的放进优先级队列；
• 一个特殊的设计是优先级队列有大小限制TH，满了的话新启一队；
• 其它线程遍历结束之后可以帮助未完成线程遍历；【编者觉得这部分并不是bottleneck，这里设计stealing意义不大】
• 之后将所有线程的PQ排个序，按照首元素的距离从小到大排序；
• 工作线程从队列中取出节点，逐个处理，如可更新BSF则立即更新，并在集群中广而告之。

image.png

• 作者认为PQ的size能否接近相同是一个关键的问题，大概用一个sigmoid拟合模型拟合了下和代价评估之间的关系，然后定下TH这个参数。【编者却认为，从最终的消费模型来看，即使有些不平衡，先结束的worker也会抢先去取下一个PQ，所以整体来看应该大抵还是平衡的，所以这一个定参的意义不太确定】

3.2.2 Work-Stealing Algorithm

节点之间的work-stealing机制其实也很简单，一个节点空闲了之后，会随机选择同组内未完成复制的节点发送请求，该节点如果被帮助次数不超过N_send的话，就发过去一个排在PQ array最后一位的，也是最有可能没什么用的PQ所在的RS batch，让其帮忙协同处理。

• 注意由于PQ array仅仅是按照首元素距离排序的，所以也有可能有一些knn在里面的。
• 另外KNN是及时共享的，所以同步上也没有太大问题。

3.3 Data Replication

这里有一个trade-off，复制越多，查询性能越好，但是可伸缩性就会变差。两个极端是完全不复制（均等分割数据集）和每个节点都包含数据集全集。Odyssey会在这里取一个折衷。

• 数据放置架构如下图，cluster个数称为复制度，表示冗余了几倍的数据；纵向的表示相同的数据的几份放置，称为1个复制组；
• 总节点数=复制组数*cluster数
• 复制组数为1时，cluster数就是节点数，就是每个节点都拥有数据全集；
• cluster数为1时，就是完全不复制，均等分割数据集。

image.png

3.4 Data Partitioning

每条Query都会发送给每个复制组进行查询，不同复制组之间通过一个共享的BSF通道进行同步，周期性地获取当前的BSF。

3.4.1 DENSITY-AWARE Data Partitioning

在分区这一步，作者首先考虑的是负载均衡，即对任意一条query，它在各个节点上的工作量应该差不多，如果一个节点有特别多的knn，其他节点几乎没有，就会产生工作量的倾斜，最终影响时延。

• 具体来说，作者通过对iSAX的格雷码排序，让相近的iSAX码分配到不同的buffer里面，就可以在一定程度上解决倾斜的问题，因为相似的序列被安排在多个节点上。

  
  image.png
• 另一方面，为了保证存储上的负载均衡（也会间接影响查询负载均衡），作者选择首先把个最大的（包含序列最多）iSAX码先用格雷码的方式分区掉，避免它们过于集中；然后是其余小iSAX码进行分区。
• 最后检查是否平衡，如果不平衡，就把最大的那个节点的最大iSAX进一步分区，直到平衡为止。

5 Experimental Evaluation

• a cluster of 16 SR645 nodes, connected through an HDR 100 Infiniband network.
  Each node has 128 cores (with no hyper-threading), 200GB RAM.

• C语言编写，MPI库支持分布式

• 数据集见下表，用的是比较大的；

  
  image.png

• 基于预测的动态查询调度还是有用的，work-stealing也是有用的，这个应该是意料之中了；

  
  image.png

• 在高负载的情况下能做到线性伸缩，不会因为过载而退化

  
  image.png

• 复制的两个极端了，复制的程度越多，速度越快，但是内存消耗也越大

  
  image.png

• 吞吐量和索引大小的实验。

  
  image.png

• 复制的越多（FULL），查询的越快，内存消耗越多，构建越慢

  
  image.png