检索系统的下游管理
腾讯soso 文/黄达文、雷冬冬
搜索引擎的检索系统，是一个复杂的分布式计算系统，往往需要成百上千台机器通过网络连接协同工作，处理用户的检索请求。不仅如此，由于数据分布以及容灾的问题，机器间往往还有上下游、分组、分镜像的关系。本文讲述如何管理这些机器间的拓扑关系。
一、检索系统的整体拓扑
整个检索系统的机器的拓扑关系，类似一个树状的结构，如图1所示。
我们把非叶子节点称为Broker，把叶子节点称为SU(search unit)。图1对整个系统进行了简化，实际情况要复杂一些。我们认为，对整个系统应该采取分层的管理模式，由上层节点管理下层节点。
二、检索服务器的下游关系
对于服务器A，我们将所有主动连接A的机器集合，称为上游；所有由A主动连接的机器集合，称为下游。A只负责管理它的下游。A的所有下游，有类型、分组、分镜像的关系，如图2所示。
在图2中，A是上游，它连接着多种类型的下游(B、C、等等)。B00、B01和B02表明，下游B的数据分布在3台机器上，3台机器的并集是数据的全集。同时，为了实现负载分担和容错，为B搭建了相同的另外两套镜像。我们用Bxy表示B的一台机器。我们称，当x相同时，Bxy属于同一个镜像；当y相同时，Bxy属于同一个分组。
当检索请求到达A后，A可能需要向B获取数据。此时，A需要从B00、B10和B20这个分组中，选择一台机器；从B10、B11和B21中选择一台机器；再从剩余的2号分组中选择一台机器。之后，向这3台机器发送检索请求并接收、合并回应。也许，A需要同时向B和C发送请求，也许，A在向B发送请求的时候，只需选择某个特定分组，或者某个特定镜像，或者某台特定机器。这些复杂的选择逻辑，由应用层控制。
三、分层模型
正常情况下，A需要保持到下游的连接并进行数据收发，并从镜像节点中，选择服务能力最优的节点，提高响应速度。异常情况，A需要屏蔽无法服务的下游节点，并在合适的时候恢复它。另外，当A的下游关系发生变化(比如A的下游由B、C变成C、D)，A需要释放B的连接，需要保持C的连接，需要建立D的连接。这个过程必须能平滑进行，不影响服务。
由此可见，对于A来说，如何管理下游，是一个重要的问题。整个检索系统，从顶部到底部，每一层都由上游管理下游，总体的拓扑关系也就得到了维持，系统可以正常运转。
解决检索系统的下游管理问题，我们采用分层的思想。如图3所示。
处于最底层的是长连接层。该层采用epoll进行网络IO，处理数据收发、超时控制、任务组回应等问题，对上层提供长连接句柄、任务组等数据结构以及创建连接、发送数据等接口。
中间层是下游管理层。下游管理层将长连接层提供的句柄，进行逻辑上的分类。形成B、C、D等下游概念。对于同一下游(比如B)，形成B00、B01、B02的镜像概念，形成B00、B10、B20的分组概念。同时，为上层提供多种镜像选择策略，自动处理服务异常的下游，在其可服务的时候自动恢复等功能。
最上层是应用层。应用层利用下游管理层提供的抽象，能很方便地与网络、下游隔离，专注于业务逻辑的处理。
四、下游管理层
下游管理层由句柄表、探测线程和更新线程组成。句柄表以某种数据结构保存所有的下游连接，对外提供丰富的获取句柄的接口。更新线程根据配置信息，动态更新句柄表的内容，并重建到下游的连接。探测线程用于恢复服务异常的下游点。
在图4中，我们用黑色表示服务正常，用蓝色表示服务异常，用红色表示机器故障。
对于机器故障的B01、B12和B22，下游管理层将其屏蔽，并在机器替换后恢复它们的连接。
对于服务异常的B10和B20，下游管理层采取两种策略：第一，将其长连接句柄屏蔽掉，由探测线程发送探测包进行查看，在确定下游可以服务的时候，解除屏蔽；第二，降低B10和B20的QPS到一个足够低的水平，当它们恢复正常服务的时候，再逐步提升到一个合理的水平。
对于同时存在的镜像点B11和B21，下游管理层提供多种策略，比如轮询、主备、负载均衡等，供应用层选择。各种具体的策略，将在下节介绍。
五、下游选择策略
下游管理层提供了多种策略，用于在可用的镜像点间选择最优的一个。我们以一个简化的下游关系图作为讨论。
B0、B1和B2装载了一样的数据，每次检索，A需要选择其中的一台。B0、B1和B2可能使用不同的机型，因此有不同的服务能力；A到它们的网络的性能，也不一定是相同的。
1、轮询
轮询是一种很常见，也很简单的策略。下游管理层维护一个变量，记录上次选择的下标，然后递增并取模，以此选择下游。该策略主要用于Broker层。
2、主备
主备的意思是，优先选择与A相同镜像号的机器。假设A对于它的上游来说，属于镜像0。那么，在B0可服务的情况下，选择B0；否则，轮询其它机器。该策略主要用于Broker层，它可以将检索系统按镜像切分开。
3、动态负载均衡
动态负载选择策略，指的是根据B0、B1和B2的历史以及当前服务能力，选择最优的机器。由于B0、B1和B2三个镜像之间往往存在各种差异，比如与A之间的网络状态，机器本身的异构性等，这些条件都会影响检索速度。
动态负载均衡的大致思想是在不同的QPS下，服务器A能根据当前B0、B1、B2处理能力按照适当的比例对检索请求进行分发，达到各个镜像服务器响应速度基本相同的目的。这样做能有效防止系统短板，平滑系统检索速度，在检索服务器出现问题时自动减少其请求量，能有效规避一些潜在的问题。
动态负载均衡的基本算法如下：
假设一个A下面有 N 个镜像，分别为Bi，第i个镜像所占的分发权重为Pi；
我们规定在一个范围滑动，比如 1<=Pi <=100，初始值为1。
对于第i个镜像，统计其最近m个请求的平均响应时间，设为 ti 在A层每处理 U 个请求后对下游的负载进行一次更新，U>=m*N。
负载更新的基本思想如下：
a. 我们对N个镜像SU的平均响应时间 ti 按照快慢进行排序，设定其排序序列为：
b. 0镜像B的响应速度最快，在理论上应该给它的负载增加，即：
c. 而镜像1——N的响应时间慢一些，理论上应该减少他们的负载，尽量使得其响应时间 ti 接近 t0
对以上增加和减少的幅度我们按照以下公式来计算，对响应速度最快的B，其增量为：
其中
为一个可设定的调权参数。
当i为1--N时，其减量为：
为可设定的调权参数。
为了防止负载能力调节过快而导致出现震动，对
需要有一定的限制
为设定的参数，它的含义是每次滑动，不能超过总QPS的比例。
通过在线系统的运营情况看，动态负载均衡策略能起到很好的作用，归结为以下几点：
首先，在不同的QPS下，A能动态调整出一个合适的QPS比例分发到下游的镜像点之间。使得各个镜像点之间的处理速度大致相同，对异构性的镜像点有比较好的用处。
其次，检索服务器刚启动时由于IO上的Cache还没有充满，所以检索服务器启动时不能处理大量请求，动态负载均衡策略考虑对其进行预热，逐步增大其请求量，直至一个相对稳定的QPS。
最后，检索服务器出现问题时，比如进程僵死，速度变慢，网络出现问题等，代理层A会自动调节其分发比例，减少其请求量。使检索质量损失最小。
六、总结
检索系统是一个复杂的分布式系统，机器间按照一定的拓扑关系，协同为用户服务。对于如何维持这种拓扑关系，我们有以下观点：
1、将拓扑关系图分层，由处于上层的上游，管理处于下层的下游。
2、将模块分离成长连接层、下游管理层和应用层。各层负责自己的逻辑并对上层提供接口。
3、下游管理层对下游的长连接句柄集合进行封装，形成分类型、分镜像、分组等概念；提供多种选择接口，多种镜像策略；自动处理所有异常情况(比如下游当机、性能异常、网络异常等)。