时间轮算法在工控安全态势感知系统中的应用

刁海洋

(西门子(中国)有限公司上海分公司，上海 200082)

0 引言

工控安全态势感知系统不仅关系着工厂内设备和网络的安全，对工厂的整体安全管理、决策控制都有着非常重要的影响。如何保证工控安全态势感知系统及时有效地反映设备和网络的安全状态，保证统计分析类的数据及时得到处理，这些问题在态势感知类的系统中受到极大关注，如何对数据挖掘和分析的处理任务进行协调和调度成为必须解决的难题。时间轮算法的出现对于解决工控态势安全感知系统中的关键问题有着非常重大的意义。

1 工控安全态势感知系统的若干问题

工控安全态势感知系统问题通常涉及多个维度，但是其最根本问题是对数据的挖掘和分析任务进行有效的管理，包括定时任务的类别和数量、定时任务的协调和调度、定时任务的分布式管理等问题[1]。

1.1 定时任务的类别和数量

工业安全环境下，有大量的设备数据和网络流量需要被采集、存储和分析，包括设备的基本信息、应用数据、系统日志、协议解析日志、事件日志以及网络的流量数据等，这些数据都需要被存储到存储引擎中。在工控安全态势感知系统中，以Elastic Search作为原始数据存储引擎[2]，为安全审计和上层的业务逻辑处理提供服务。对于这些种类繁多的数据，需要按照面向对象设计的思想，采用多种不同的定时任务进行处理。比如对于事件类型的日志，系统的事件种类也分多种，如尝试连接事件、系统登录事件等，对于不同的事件上层业务需求是不同的，那么就需要开发大量的定时任务进行业务逻辑处理，这就导致了在整个系统中定时任务的类别和数量较多。

1.2 定时任务的协调和调度

在系统中，有些任务需要每隔一段时间执行的，有些任务有前后依赖关系，有些任务需要在执行一段时间之后根据业务逻辑判断是否取消。虽然在Java官方提供的框架中，有一些专门用来处理定时任务协调的工具，比如Timer，Scheduled Executor Service，这些工具的调度时间复杂度为O(LogN)级别。当包含着业务逻辑的定时任务类别和数量都很多时，这些工具的自身调度耗时将会影响到定时任务实际执行的有效周期，进而会影响到任务本身。如何对这些任务进行高效的协调和调度非常关键。

1.3 定时任务的分布式管理

为了保证服务的高可用性，工控安全态势感知系统是以分布式的方式在工厂内部署，各个服务是以多个服务器来均衡处理前端和数据计算层的服务请求，这些服务器以哈希的方式接收相应的请求，执行业务逻辑并返回结果。定时任务分散在各个服务器中，以特定的条件来触发和执行。那么，在分布式的环境下，如何保障这些大量的定时任务能够定期有序地在服务器之间调度和执行，不会重复和遗漏，是个重要的任务管理问题。

2 时间轮算法

在定时任务体系架构中，有多种调度框架和工具，比如前文提及的Timer，除此之外业界常见的还有时间轮、Quartz、Elastic-Job、XXL-JOB、Spring Task等[3]。在这些框架和工具中，有些在单机环境下以链表的方式按照执行顺序来存储定时任务，然后按照Native的wait方式执行时间的流动和判断，有些则是在分布式环境下以数据库或者Zookeeper来协调分布式定时任务的执行。单机环境下的定时任务调度工具侧重于任务调度相关的效率和可靠性，在此基础之上向使用者提供便捷的配置管理；分布式环境下的定时任务调度工具则更关注多个服务器之间如何同步定时任务的状态信息，一般都是通过第三方组件来执行状态信息的管理。

2.1 实现原理

以环形的队列作为时间格(Timing Wheel)，每个时间格上挂载着以双向链表数据结构存储的任务列表，双向链表中的每一个元素表示需要执行的任务项，这些任务项的执行时间一致，省去了任务调度器逐个判断任务执行时间的开销。通过表盘指针指向当前时间所在的位置，当指针指向到某一个时间格时，则任务调度器就将该链表上的所有任务取出执行。当需要增加新的定时任务时，根据当前指针位置和定时任务的时间偏移量，将该任务加入对应的时间格的任务链表，通过尾部指针的指向将任务添加到双向链表的末端。同时以“时间格×时间跨度”作为当前的时间轮的总时间跨度，当某些任务的时间偏移量超过当前时间轮的总时间跨度时，增加多层时间轮，通过时间轮之间的层次关系以及任务的升维和降维，来标志系统中所有的待执行定时任务。

2.2 优势

从上述实现原理可以看出，任务的写入和执行的时间复杂度都是以O(1)为常数级。通过多层时间轮的方式进行时间的分层，以执行的时间为单元对任务进行划分，将任务按照所属时间轮挂载到对应位置。随着时间的流转，多层时间轮上挂载的任务升级或者降级到对应层级的时间轮位置，这种方式减少了任务的执行时间和系统当前时间的对比次数。除此之外，每个任务被固定以双向链表的方式挂载在时间格中，当需要对任务进行新增、删除、修改和查询时，在双向链表这种数据结构上，可以很方便地执行相应操作，减少调度指针前进和回溯的次数。最后，当需要执行任务的时候整条链表都会被执行，省去了类似于Timer这些工具中的判断时间。时间轮算法的低复杂度能够显著降低任务调度工具的时间开销，提高调度效率，非常适合定时任务数量较多的场景。

图1 基于时间轮算法的定时任务调度

2.3 应用

业界主流的Kafka，Dubbo，ZooKeeper，Netty，Caffeine，Akka等框架都有时间轮算法的应用。这些框架中有着较多的延时执行操作，比如延时拉取、延时删除、延时选举、心跳检测、超时处理等任务，这些任务在大容量、高并发的场景下，对调度时间有着非常高的要求。比如Kafka单机环境下最大每秒能生产和消费百万条消息，能够同时支持2万个客户端同时连接，这种情况下需要处理的定时任务将会非常多，而这些任务都依赖于底层的定时任务调度器进行处理。时间轮算法能够非常高效地协调和调度这些任务，为框架应用的持续高性能运行提供保障。

3 时间轮算法在工控安全态势感知系统中的应用策略

将时间轮算法应用到工控安全态势感知系统之中，对时间轮算法的逻辑进行二次开发，根据业务的要求配置时间轮的间隔和轮数，重新实现任务调度的逻辑，对特定的业务进行适当的定制改造，将时间轮算法与原有系统的业务以模块化的方式组合在一起，类似于微服务的形式，对时间轮算法模块的修改和发布不影响原有业务系统的正常运行。在实现二次开发和模块化之后，任务调度模块可以更好地协调和调度工控安全态势感知系统中大量存在的统计分析定时任务，除此之外将原先采用的Spring Task的Scheduled分散处理方式改为集中化管理，定时任务需要先向任务调度模块注册之后才能运行，最后将任务调度模块的具体任务调度逻辑与Redis的分布式锁结合在一起，通过引入第三方组件的方式解决分布式场景下定时任务的调度和执行问题。

图1描绘了引入时间轮算法之后任务调度模块的设计，系统初始化时有3层时间轮，将每层时间轮设置为20格，以秒为基本单位，第一层时间轮的范围为0～20 s，第二层时间轮的范围为20～400 s，第三层时间轮的范围为400～8 000 s。在运行过程中时间轮的层数根据任务的分配时间动态扩展，当系统中需要调度的时间超过8 000 s，则会增加第四层时间轮，以此类推直至可配置的最大范围。在每层对应时间格上挂载相应的定时任务双向链表，每个链表上的任务都相应加了Redis的分布式锁，各个任务的锁都不相同，以任务的唯一ID作为区分。在取出双向链表的所有任务并调度到其中某一个时，调度模块将该任务上的锁与Redis中的锁进行对比判断是否执行该任务。

3.1 统计分析任务分层

在工控安全态势感知系统中，由于原始数据存储在Elastic Search存储引擎中，上层业务需要使用大量的定时任务从原始数据中挖掘出业务需要的信息。原先的设计使用的是实时聚合和少量的定时任务挖掘来实现统计和分析型的业务，这种方式导致了在数据量增长之后系统响应时间变长。在引入时间轮算法之后，对统计分析型的任务进行拆解和分层。根据不同的业务类型，对系统事件、网络流量、资产变化等不同的业务划分多个类别，对于不同的类别再以时间的维度做进一步的分层。在整个统计分析任务分层过程中，以5秒钟、分钟、小时、天、周、月、季度或年为单位进行分层[4]，将这个层级的概念下沉到时间轮算法的实现模块中。由于每种类型的业务对应不同的定时任务，还需要再进行对应时间的分层，那么整体定时任务的数量就会大幅增长，时间轮算法能够非常好地处理大量的定时任务，保证系统的稳定运行。

3.2 任务管理集中化

在之前的设计中，采用的是Spring Task的Scheduled方式，在各个需要定时执行的业务代码的位置加上需要定时处理的注解，就会将调度的逻辑交给Spring框架来处理，这种方式非常简单便捷，但是带来了管理上的问题。引入时间轮算法之后，设计了独立的模块，各个需要执行定时任务的位置都需要在该模块中注册，只有在注册之后才能将定时任务交由时间轮来调度和执行。在注册的子模块中，会对所有注册了的定时任务进行权限的识别、行为的记录，便于后续对定时任务的集中化管理，比如在界面上由管理员手工取消、重启。在交由时间轮算法实现模块集中化管理之后，之前隐藏在代码逻辑中的定时任务完全交由该模块来管理，任务的执行和调度不再受制于业务模块，整体设计上契合面向对象解耦的思想。

3.3 分布式定时任务调度

在工控安全态势感知系统中，实际的部署场景包含分布式多机部署，后台服务被同时部署到多台服务器中以实现负载均衡，定时任务也就会被分散在各个服务器中。在之前的设计中，将定时任务集中部署在某一台服务器单独运行，如果该服务器宕机就会导致整体定时任务出现问题。而单独的时间轮算法仅支持单机环境下的定时任务执行，无法对分布式场景下的定时任务进行调度。在这种场景下，额外引入Redis分布式锁的技术[5]。当时间指针转动到需要执行定时任务的时间格时，需要先将该链表上所有任务取出来，逐个判断该任务是否已经在Redis中加上执行锁；如果已经加上则在当前服务器上放弃执行，否则在Redis上加上新的执行锁，表明当前已经在执行，其他服务器轮转到该任务时，就会发现该任务正在被执行而直接跳过。这样，时间轮算法和Redis分布式锁技术的结合可实现分布式场景下的定时任务调度。

4 结语

本文对如何保证工控安全态势感知系统中定时任务的高效率调度进行了分析和研究。在西门子工厂实际部署前后的对比研究表明，将时间轮算法应用到工控安全态势感知系统中，能够有效提高系统的运行效率，保证任务持续稳定地运行，为用户提供了安全稳定的使用环境。在工业互联网环境下，工控安全态势感知技术已成为工业安全应用趋势，时间轮算法发挥着重大的作用。