一种适用于证券交易系统的低时延分布式流控方法

摘要

本发明涉及数据处理技术领域，具体来说是一种适用于证券交易系统的低时延分布式流控方法，若当前时间now小于下一次允许单个请求通过的时间openTime，则拒绝当前的请求；若当前时间now大于等于下一次允许单个请求通过的时间openTime，则允许当前请求通过，并按时间处理方法重新计算下一次允许单个请求通过的时间openTime，同时更新当前窗口currWindow的请求计数值currWindow.count和新增请求量计数值currWindow.changes。本发明同现有技术相比，其优点在于：使得限流操作可以在多个入口节点间协同进行；限流计算在处理超限请求时，只有一条时间的比较判断指令，可以用最低的计算成本过滤流量洪峰，降低合法订单响应时延；异步同步时间窗口计数值，增加分布式限流能力的同时，避免了处理时延的增加。

说明书

技术领域

本发明涉及数据处理技术领域，具体来说是一种适用于证券交易系统的低时延分布式流控方法。

背景技术

证券交易系统的交易主机每秒所能处理的订单数量存在一个物理上限，这是由交易系统的物理硬件容量和软件算法效率决定的。例如一张万兆网卡搭配Linux内核，每秒所能递交给应用程序的UDP包数量大约为50万个，其中还包括大量的控制消息包，每个数据包应用层需要20微秒处理，实际能处理的报单数据包大约为5万个每秒。为了避免超量的数据包造成大量丢包、系统资源浪费在重传控制和乱序处理上，我们需要限制每秒到达每个交易主机的订单数量。限制每秒到达交易系统的订单数量也可以给市场提供公平的交易机会，避免单一席位(链接)上的客户突发报送大量订单抢涨停板等事件的发生。

行业内的限流算法基本可以划分为4类：

固定窗口限流：固定窗口限流最为简单，把时间划分为多个窗口，每窗口内有一次订单就将计数器加一，如果计数器超过限制，则该事件窗口内新到的请求将会被拒绝。这个算法的问题是它可能会让两倍流量在窗口边界时间点通过。

滑动窗口限流：滑动窗口限流是在固定窗口限流的基础上，将窗口进行细分，并且按先入先出的原则把过期窗口删除，这种算法不会有两倍突发流量的问题，但其需要耗费O(N)的空间(N为窗口数量)用于保存每个小窗口上的计数。

漏桶算法：漏桶算法则是以固定的间隔去除排队中的请求，新到的请求如果超过了桶内排队的容量则直接拒绝。这个算法的问题是新的请求无论如何也会等待一个固定间隔才被处理，增加了处理时延。

令牌桶算法：令牌桶算法按固定速率生成令牌放入桶内，取到令牌的请求将被处理，取不到的则被拒绝。令牌桶对于单点服务能比较好的限流，但无法对分布式的多入口进行协同限流，导致到达目标服务上的请求数超出限制。

在现有的交易系统中，对竞价交易主机采用的流控策略主要是在途订单数控制，其不会对某条链路上每秒可发订单进行限制，只限制某一时刻该链路上还有多少订单在等待交易主机处理，可以理解这种流控模式为漏桶算法的变种，和业务字段进行了紧密的绑定，因为要根据从交易主机返回的结果处理是否需要删除排队中的请求订单。

如图1所示，每个交易网关会维持一个在途队列，每个通信服务器(记作CS)也会维护各自的一个在途订单队列，并且按和上游网关的连接来区分子队列，所有已经发送给交易主机的订单被记录在这些队列中，当收到交易主机回应的订单执行报告时再从队列中查询出对应的订单并删除它，并允许一个新订单传送给下一层并最终发送往交易主机。

其存在的问题是，所有CS达到最大在途订单数时，如果品种集中，其发送频率可能超过单个交易主机的每秒处理能力，导致CS在途队列满，订单在队列中等待时间会增加10-15秒，严重增加交易系统响应时延，触发上游券商系统的报警。

在队列满时，CS会停止读取与交易网关之间通信连接中的数据，导致双方心跳超时，主动断开连接并触发重连操作，给网络及操作系统层雪上加霜。

由于拥挤的订单处在CS的在途订单列表中，必须等订单到达交易主机中后才可以撤单，这导致10-15秒内无法对在途订单进行撤单。

发明内容

本发明的目的在于解决现有技术的不足，提供一种适用于证券交易系统的低时延分布式流控方法，以满足证券交易系统的需求。

为了实现上述目的，设计一种适用于证券交易系统的低时延分布式流控方法，所述的方法对于每一个资源实例Res，分别设有限流器，所述的限流器包括当前窗口currWindow和前向窗口prevWindow；每个当前窗口currWindow和前向窗口prevWindow均设有时间跨度timeSpan，所述的时间跨度timeSpan，在时间跨度timeSpan内设有流控值limit；所述的前向窗口prevWindow包含一个起始时间prevWindow.start，和一个请求计数值prevWindow.count；所述的当前窗口currWindow包含一个起始时间currWindow.start、一个请求计数值currWindow.count和一个新增请求量计数值currWindow.changes；若当前时间now小于下一次允许单个请求通过的时间openTime，则拒绝当前的请求；若当前时间now大于等于下一次允许单个请求通过的时间openTime，则允许当前请求通过，并按时间处理方法重新计算下一次允许单个请求通过的时间openTime，同时更新当前窗口currWindow的请求计数值currWindow.count和新增请求量计数值currWindow.changes。

所述的时间跨度timeSpan的值设置为同步窗口计数到memDb的时间间隔interval的值的2-N倍，N为大于等于2的正整数。

将当前窗口currWindow的起始时间和前向窗口prevWindow的起始时间，通过下式对齐到时间跨度timeSpan的边界：t＝t-t％timeSpan；式中，t为当前窗口currWindow的起始时间或前向窗口prevWindow的起始时间。

如果当前时间对于时间跨度timeSpan的边界nowStart等于currWindow.start+timeSpan，则把当前窗口currWindow的数据保存至前向窗口prevWindow中，并重置当前窗口currWindow；如果当前时间对于时间跨度timeSpan的边界nowStart大于currWindow.start+timeSpan，则重置前向窗口prevWindow和当前窗口currWindow。

所述的时间处理方法通过下式获得下一次允许单个请求通过的时间openTime为：

openTime＝currWindow.start+timeSpan–((limit-currWindow.count-1)/prev.count)*timeSpan。

在更新当前窗口currWindow的请求计数值currWindow.count和新增请求量计数值currWindow.changes后，异步更新至内存数据库实例memDb。

若上次异步更新计数的时间lastUpdateTime距离现在是否已经超过了interval，则进行内存数据库实例memDb的计数更新操作。

所述的内存数据库实例memDb的计数更新操作通过远程内存数据库方法AddAndGet实现。

在内存数据库实例memDb的计数更新操作完成后，更新本地的当前窗口currWindow。

发明的有益效果

本发明同现有技术相比，其优点在于：

1、本发明的方案使得限流操作可以在多个入口节点间协同进行。

2、本发明中的限流计算在处理超限请求时，只有一条时间的比较判断指令，可以用最低的计算成本过滤流量洪峰，降低合法订单响应时延。

3、本发明异步同步时间窗口计数值，增加分布式限流能力的同时，避免了处理时延的增加。

附图说明

图1是现有技术的示意图。

图2是本发明的限流器的示意图。

图3是本发明的服务交互关系示意图。

图中：1.交易主机 2.通信服务器 3.交易网关 4.在途订单队列 5.订单 6.前向窗口 7.当前虚拟时间窗口 8.前向窗口计数期望所占时间段 9.当前窗口 10.现实世界时间轴的未来方向 11.现实世界的时间轴 12.现实世界时间轴的过去方向 13.内存数据库实例 14.交易主机在通信服务器这一层的流控资源在内存数据库中的主键前缀 15.交易主机在交易网关这一层的流控资源在内存数据库中的主键前缀。

具体实施方式

下面结合附图对本发明作进一步说明，这种方法的原理对本专业的人来说是非常清楚的。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

本实施方式提供了一种异步加权平均滑动窗口限流方法，以满足对交易的低时延要求和对订单的平滑限流要求，可以在多个入口服务器处进行分布式协同限流。

其总体思想参见图2所示，对于每一个被限流访问的资源实例，设置和保存相连的两个时间窗口计数，利用独立的内存数据库实例作为集群各节点同步其中一个时间窗口计数的媒介，对计数进行原子递增；在集群各节点内部，求出下一个请求可以通过的时间点，来原子性地过滤掉对于当前虚拟时间窗口virtualWindow来说超限的请求，让系统可以高效地抵御流量洪峰。

系统各服务交互关系如图3所示,以下结合图2和图3所示，对本实施方式的具体实现方法进行示例说明。

运行一个内存数据库实例memDb作为流控窗口计数的远程集中保存处，其中，内存数据库可以是支持原子递增操作的任意数据库，例如Redis，Etcd等。

对于每一个被限流访问的资源实例Res，创建两个统计时间窗口构成一个限流器：一个是当前窗口currWindow，一个是前向窗口prevWindow。其中，每个窗口的时间跨度timeSpan，可以根据需求设定，例如可以为1秒、100毫秒、1毫秒等等，将timeSpan设置为同步窗口计数到memDb的时间间隔interval的2-N倍大小，N为大于等于3的正整数，可配置较大的倍数以增加当前窗口计数的同步频率，例如在一个实施方式中将这个值配置为十倍大小，实测表现中能使得集群各服务器之间能够充分同步当前窗口计数，保持总流量在timeSpan内得到有效控制，即：

timeSpan＝interval*10 (公式1)。

在一个时间跨度timeSpan范围内允许处理的请求数量，即流控值limit，超出这个数量的请求将会被拒绝。

并且，所述的前向窗口prevWindow包含一个起始时间prevWindow.start，和一个请求计数值prevWindow.count；所述的当前窗口currWindow包含一个起始时间currWindow.start、一个请求计数值currWindow.count和一个新增请求量计数值currWindow.changes。

其中，两个窗口的起始时间(公式中用t代表)，在计算时均按以下公式对齐到时间跨度timeSpan的边界：

t＝t-t％timeSpan (公式2)。

定义每个资源实例Res的限流器在内存数据库实例memDb中的当前限流窗口键名winKey为Res.name+currWindow.start，即伪代码表示为：

winKey＝Sprintf(“％s％d”,Res.name,currWindow.start)；

将下一次允许单个请求通过的时间记作openTime，当每次有新请求到来时，通过以下方法计算该请求是否应该被限制并拒绝：

S1.获取当前时间now。

S2.比较openTime和当前时间now的大小，如果当前时间now小于openTime，则直接拒绝这个请求。

S3.如果当前时间now大于等于openTime，则允许这个请求通过，并按下列步骤计算出一个新的openTime。

S3.1.使用公式2获取当前时间对于时间跨度timeSpan的边界nowStart。

S3.2.如果当前时间对于时间跨度timeSpan的边界nowStart等于currWindow.start+timeSpan，说明当前的时间已经处于一个新的时间窗口，把现有的当前窗口currWindow的数据保存至前向窗口prevWindow中：

prevWindow.start＝currWindow.start；

prevVindow.count＝currWindow.count；

同时重置当前窗口currWindow为新的值：

currWindow.start＝nowStart；

currWindow.conut＝0；

currWindow.changes＝0；

如果当前时间对于时间跨度timeSpan的边界nowStart大于currWindow.start+timeSpan，说明当前的时间已经处于一个无法连续到已有流控窗口的新时间窗口，直接重置prevWindow和currWindow：

prevWindow.start＝nowStart-timeSpan；

prevWindow.count＝0；

currWindow.start＝nowStart；

currWindow.count＝0；

currWindow.changes＝0；

并按下述公式计算新的下一次允许单个请求通过的时间openTime：

openTime＝currWindow.start+timeSpan–((limit-currWindow.count-1)/prev.count)*timeSpan (公式3)

所述的公式3的推理过程如下：其中((limit–currWindow.count–1)/prev.count)是前向窗口的计数在当前窗口所占的权重值，只有小于此权重值时，当前窗口已发生的计数才不会超过流控限制，根据这个期望权重我们计算出前向窗口计数期望所占时间段：

prevRemain＝((limit–currWindow.count–1)/prev.count)*timeSpan (公式4)

当前窗口结束时的时间点currWindow.start+timeSpan减去前向窗口计数期望所占时间段(即公式4中的prevRemain)，就是我们允许下一个请求被处理的时间点，早于这个时间点到达的请求都应该被拒绝。

openTime＝(currWindow.start+timeSpan)–prevRemain (公式5)；

同时更新当前窗口的计数：

currWindow.changes＝currWindow.changes+1；

currWindow.count＝currWindow.count+1；

而后，尝试触发异步更新计数到内存数据库实例memDb的操作，异步更新计数可以消除限流计算可能造成的时延：

首先，判断上次异步更新计数的时间lastUpdateTime距离现在是否已经超过了interval，如果未超过，则不执行下面的异步更新动作，如果已超过，即满足：

now-lastUpdateTime>interval；

则将currWindow.count和currWindow.changes发送给独立线程，执行更新动作；

将memDb中的当前窗口计数记作remoteCurrWindow.count，保存在memDb中键名为“Res+currWindow.start”的数据中，并将这个键的过期时间设置为2倍的timeSpan。

采用原子操作AddAndGet(winKey,currWindow.changes)获取累加了本地自上次同步操作以来新增的请求后的计数值：

remoteCurrWindow.count＝remoteCurrWindow.count+currWindow.changes

此行为原子操作远程内存数据库AddAndGet的实现。

在更新完memDb后，还需更新本地的currWindow，使这个实例看到所有涉及这个Res的流控窗口分布式实例的累计计数值:

currWindow.count＝remoteCurrWindow.count；

currWindow.changes＝0。