在线查询系统中，业务逻辑将服务划分为树状结构，每个节点通过水平扩展增加自身服务能力，最终形成下图所示拓扑结构：
当一次查询从某一入口进入系统后，自上而下查询各个服务，每个服务又有多个节点可供选择，最简单的负载均衡策略是轮询或者一致性hash，各个节点接相同流量，但是这种策略下如果集群中出现了坏节点，则会导致部分用户查询无结果或者超时，严重时导致故障。
复杂一些的系统通过服务发现做坏节点检测，例如阿里的cm2和vipserver。以cm2为例，cm2会通过http心跳探测检查下挂节点的健康度，如果一个节点能够响应cm2的心跳探测，则认为是健康节点，cm2会将该节点发布给在线系统查询；节点异常时，心跳探测失败，cm2通知在线系统该节点需要删除，该节点流量跌0，从而避免坏节点干扰流量，如下图所示：
通过心跳检测发现坏节点主要有一下两个问题：
- 心跳检测与实际查询的网络通路是不同的，心跳检测成功说明名字服务与目标服务之间的网络正常，但线上系统经常出现某条网络通路延迟高或者不通的情况，外部心跳检测解决不了这类问题。
- 外部心跳检测无法发现服务自身的业务问题，或者说外部探测只能屏蔽部分进程、系统层面的问题（进程core掉、系统crash等）。例如搜索场景中，某个上层服务本身是健康的，但是他的下挂服务无结果率升高，这时候外部探测发现上层服务是健康的，流量还是会导向这个有问题的子系统，这常见于灰度发布、按机房发布等场景中。
以上问题的原因实际上是一致的：在线系统决策能力弱，完全依靠外部系统辅助决策查询路径。为了解决这些问题，我们开发了gig。
gig（Graph IrriGator）的核心思想是在线实时决策流量流向，不再局限于外部系统探测这种隔靴搔痒的方式，而是作为一个高可用的RPC lib嵌入到在线应用中，代理应用对底层服务的访问，实时统计每个节点的延迟和错误率，屏蔽高延迟节点、高错误率节点，在下游节点延迟上升到无法接受之前主动限流，让流量流向此刻此节点看到的健康路径上去。
从上图的角度来看，外部探测的方式是面向节点的，即每一个节点有一个健康度，而gig是面向边的，每一条边都有一个健康度。显然，边的个数要远大于节点个数，对系统状态的刻画也更加全面，同时，嵌入到在线系统有一个天然的优势：gig可以感知业务层面的错误，并能够据此屏蔽服务异常集群。
1 gig原理
gig的核心功能之一是解决包含网络异常在内的坏节点问题，而不同的系统对异常的定义不同，gig选择了所有在线系统都有的一个核心指标"查询延迟"作为节点好坏的评判标准，节点队列堵塞、网络超时、操作系统负载高等异常情况均能在latency上反应出来。同样，系统负载也能从latency上体现，因而gig的降级（限流）策略和负载均衡策略也是基于latency的。
如果将在线树状系统想象成一个大的水利灌溉系统（gig名字的由来），灌溉者的功能是将水导向系统中阻力最小的部分，既不能让入口水流堵塞，也不能让干旱发生，到gig这里，水即是流量，阻力则可以近似认为是latency，阻塞是系统吞吐量下跌，干旱则是负载不均衡。所以gig会统计上图中每一条边的平均latency，并据此导流，更进一步，gig还通过控制流量高低来控制每一条边的latency。
1.1 基于PID控制器的latency负反馈控制
在线绝大多数场景下，查询latency与流量呈正相关，即流量越大，latency越高，类似下图：
流量控制的目的是为了稳定每一个节点的latency，各个节点的latency差异控制在合理范围内，对于高latency的节点应该予以屏蔽。为了稳定各个节点的latency，我们设计了如下图所示的负反馈控制器: 
图中的PID控制器实际上只使用了I(Integral)部分，即一个带抗饱和功能的积分器，整体是一个过阻尼系统，这样设计的原因是线上各个系统的Latency-qps关系变化很大，积分本身虽然相应速度慢，但由于在线系统的响应速度快（流量升高时latency会瞬间上升），latency达到预期值后积分器瞬间停止积分，不会超调导致下游节点CPU被打满。
系统稳定后，限流阀从入口流量中分得固定比例的流量给该下游节点，同时，下游节点的平均latency能够被控制到与Input Latency一致。gig将上述控制器应用到所有下游节点，最后剩下的问题就是latency的给定值（Input Latency）如何设置。
有两种方式：用户指定和系统自动推导。用户指定实际上比较困难，多数时候应用的latency是随流量和业务变化的，提前指定几乎是不可能的。
gig采用的是系统自动推导方式，推导方式也很简单：取所有节点的平均latency的最小值作为所有节点的Input Latency。这样做符合流控和负载均衡的初衷，流量总是倾向于向低延迟节点流动。最终形成如下图所示结构：
整个系统由入口流量驱动，系统能够保持各个节点的latency分布在一个较小的区间内，这个区间之外的节点流量跌0。
1.2 降级功能
有了平均latency后降级功能也很容易实现，gig以平均latency作为系统负载的指标，允许用户设定系统运行的最高latency（实际上是两个值，一个是开始降级的beginDegradeLatency，一个是100%降级的fullDegradeLatency），当系统所有节点的平均latency最小值超出beginDegradeLatency后，gig将根据超出部分占区间[beginDegradeLatency, fullDegradeLatency]的比例限流，直到完全限流。所以应用的latency是不可能超过fullDegradeLatency的。
2 适用场景
实现了对latency的精准控制后，许多场景的问题便迎刃而解：
2.1 部分节点网络超时
节点网络超时时，该节点的latency变高，控制器将该节点的流量下调，如果是网络自身问题导致超时，则流量调整为0后latency仍然不能恢复，系统保持该节点不接流，达到屏蔽该节点的功能。网络恢复时，gig探测发现节点延迟下降，该节点流量自动恢复。关于gig探测机制，请参考文末gig用户文档。
2.2 部分节点服务能力下降
节点的服务能力受系统负载或者其他应用干扰，该节点因latency上升而流量下跌，如果节点服务能力跌0，则流量跌0，如果节点服务能力减半，则流量减半后系统稳定，最终实现"多大能力接多大流量"的效果。
2.3 新加节点需要预热
许多服务新启动后需要预热，如具有jit功能应用（java、tensorflow xla）、磁盘io类应用等，这些类型的应用系统服务能力是随着接流时长而增加的，服务刚启动时，新节点latency高，流量跌0进而触发gig探测，节点latency逐渐下降，满足用户设定倍数时，流量自动恢复。
2.4 异构集群
CPU和GPU异构计算集群中，基于不同硬件的节点可以提供相同服务，但服务能力存在差异，gig的latency均衡机制能够均衡两个集群的流量比例，将两者的latency控制在一定差异以内，避免流量分配不合理造成单一集群负载过高而超时。
对于主动降级场景，latency-qps变化曲线不再是正相关，latency控制变为正反馈而失效，gig内部设计了专有错误码避免这种情况的发生。
3 gig针对多列应用的优化
大数据场景下，单机很难存放所有数据，因而很多应用对数据分列，形成多列多副本的拓扑结构，我们称为多行多列应用。查询时，应用逻辑要求查询一个完整行，即每一列都查一次。gig中将这种类型的应用抽象为多个列，每个列提供同质的服务，列内部各个机器之间做上述流控操作，于此同时，gig还针对多列应用的特点，做了三个优化：提前终止（early terminate，简称et）、重试（retry）、缺列降级。
3.1 early terminate
et是指在某一列未返回结果时，丢弃该列的结果提前返回，应用层拿到的数据会少一部分，这对于搜索等场景是可以接受的，拿到部分结果要优于整个query超时。
3.2 retry
retry是指当某些列的结果未返回时，gig会重查该列的另一个replica，如果另一个replica及时返回，则查询结果仍然是完整的。
et和retry的目的是为了防止单机抖动时造成query超时或失败，其核心假设是数据均匀分布，各个列处理同一个query的时间是相近的，一台机器是否异常可以通过与另一列比较得到。例如，如果第一列用了10ms返回，那么第二列应该很可能在5-15ms内返回，如果第二列用了50ms仍未返回，那这一列有大概率是出现了瞬时抖动，此时gig会根据用户配置采取retry或者et操作，又或者是两者同时启用。
3.3 缺列降级
在多列的情况下，gig主动限流不再是直接丢掉整个query，而是丢掉query中某些列的查询，这样能够最大限度保证服务质量。例如，一个10列应用，如果触发了10%降级，则有10%的query缺失1列的查询结果。随着降级程度的增加，缺列的query比例会增加，缺少的列也会增加，直到整query限流。
et和retry的详细作用机制及配置方法参考gig用户文档，缺列降级只要多列用户配置了降级就会自动启用。
HA3使用了et和retry功能后，在单台searcher core掉的情况下，能够做到前端用户无感知。
4 gig组网：多级级联系统
gig本身的设计是针对一个服务调用另一个服务的，但是gig同样能够组成如下图所示的级联系统：
考虑到中间层的部分gig节点可能会因为自身负载等原因触发gig降级，且降级后因latency并无大变化而持续接流，这样集群中就会一直存在一个降级节点，影响服务质量，因而gig专门定义了降级相关的错误码，上层gig收到该错误码后会降低该节点的流量。
级联以后，除图中红色节点以外，剩余节点发生异常时均可以被屏蔽。
5 生产流量copy
在系统新版本上线、压测或者性能优化时，往往希望能够获得与生产系统完全一致的流量，包括流量大小和组成成分，gig支持将生产流量copy到一个完全独立的集群，copy功能会增加在线系统的网络带宽，但copy集群的结果不会服务在线流量，copy集群自身挂掉也不会干扰在线系统的运行。
6 多协议支持
gig现阶段支持三种协议：arpc(阿里内部rpc协议)、http、自定义tcp，用户可以根据自身应用特点选择。
7 双十一应用情况
今年双十一期间，搜索内部上线gig的服务包括：主搜索和tmall搜索后端HA3、RankService、SP、Igraph和DII等多个搜索业务引擎，gig峰值调用超过千万QPS。部分应用使用或触发了预热、降级等相关功能，其中RankService集群还使用了gig的预热功能和异构（CPU和GPU）均衡功能，结构上HA3和SP引擎构成了两级gig级联系统。
8 总结与展望
gig的存在提高了搜索线上应用的鲁棒性，显著降低了服务质量对外部环境的依赖，后续我们会持续优化gig的流控策略，包括改进latency的统计、添加错误率统计和对java应用的支持等，同时最近service mesh异常火热，gig的功能很多与service mesh的理念相吻合，后续gig也会考虑往云和微服务场景发力。
欢迎对gig原理感兴趣的同学联系我们，大家一起探讨。同时也欢迎对超大规模实时数据处理、检索和计算服务感兴趣的同学加入我们团队：https://job.alibaba.com/zhaopin/position_detail.htm?positionId=42997
