时序相关任务的并行计算解决方案讨论 (1)

时序相关任务的并行计算解决方案讨论

(Parallel computing solution for chronologically correlative tasks)

 

现实问题描述

想象一个设备网络，包括许多交换机、路由器、网关服务器、Radius服务器，等等。如果要集中式的监控各个设备的工作状态，就需要在网络中部署一个网络设备管理系统。从网管系统侧看来，所有设备都直接或间接与之相连，并通过各种可达的通信协议，诸如但不限于SNMP，定时或不定时的不间断的报告各自当前或历史和工作状态相关的数据。网管系统需要对所获得的设备信息进行计算，以维护和刷新系统内部用于表征实际设备的模型对象(该对象可能会包括至少一个有限状态机，和若干统计量)，所有抽象对象构成一个映射实际网络的设备拓扑模型，这是系统实现设备管理和监控的基础。

就设备信息的计算而言，可能会有如下特征：

l     计算必须迅速，以保证分析结果的时效性；

l     同一时间切片上的数据量可能很大，主要取决于网络规模的大小；

l     基于前面两点，我们会考虑采用并行计算提高数据处理速度。而且不同设备产生的数据的处理不具有相关性，在保证时效性的前提下，对它们的处理顺序的改变不会影响计算结果。这是得以采用并行计算的前提；

l     但是同一设备的数据产生在时间上是有序的；网管系统对其处理顺序也需与其一致，否则可能会影响计算结果(后面将举例说明这点)。所以时序相关的数据计算必须保证被偏序执行－比如串行计算；

l     而且每个设备的数据随着时间的推移理论上是个无限集，它可以映射为正整数集(以系统运行后收到的该设备第一份数据为D(1)，第二份为D(2)，依此类推)。所以要在全集上进行重新排序然后再处理，是不可能的；

l     网管系统数据获取接口通常为一个或几个，和实际网络中的设备形成一对多的关系。也就是说每个接口获取的数据并不必然来自一个设备，必须在处理它们前分析其相关性，以决定何种计算方式。

在此举一个简化了的例子来说明考虑数据处理时序相关特征的重要性。想象只有正常、故障两种状态的一个设备。和该设备状态相关的只有一种告警信息，状态转换和事件的关系如图1所示。假设设备目前在正常状态下，先产生一个“告警产生”事件，紧接着又产生一个“告警消除”事件，设备应该最终仍旧处于正常状态。但由于某种原因，第二个事件先于第一个事件被处理，这种情况下，由于设备当前状态为正常，它会丢弃“告警消除”事件，然后“告警产生”事件会将设备转变为故障状态。

 

 

图1        网络设备状态机简化示例

 

一般性归纳

为了便于推演，使本文的讨论适用于同一类问题，这里试着对问题进行一般性归纳，以确保后面的讨论是在问题的一般性特征基础上，而不是基于具体的网管问题。

处理对象数据(target data)

 是从数据源(设备)到处理机(网管系统，后面详细讨论)，供处理机运算的信息。假设集合V={v_i | i>0, i<=n}是数据源提供的所有n个描述自身的数据指标(或称变量)的全集。则每一个具体的数据消息D={v | v ∈ V}包含了V的一个子集的指标值，可能各有差异。但对于每一个D，必须包含可以用于计算相关性的指标，可以称为相关键(correlativity key)；以及标识其时序特征的指标，可以称为数据的时间标签(timestamp)。

相关键(correlativity key)

任意两个数据D, D’，针对具体的处理算法，其相关性必须是确定的：

Correlativity (D, D’) ∈ {0, 1}

其中1表示全相关，0标识不相关。并非D中所有指标都需参与相关性计算，而是一个子集，可以称为相关键。在前面讨论的问题中，来自同一个设备的数据相关，否则就不相关。相关键就是标识数据源身份的指标，比如设备ID，设备IP，或者设备的Mac地址等。要注意具体问题中，相关键并不一定都由单指标组成，如果上述设备网络跨多个局域网，设备只有内网IP地址，考虑到属于不同局域网设备的IP地址可能重复，用设备IP地址和局域网网管地址组成相关键是可行的选择之一。

但不论相关键CK简单或复杂，为了解决问题的方便，我们可以寻找一种映射关系CF，将CK映射到一个相关因子(correlativity factor)集I上，使得

i = Cf (CK(D)), i ∈ I

I可以是正整数(或整数)子集，在网管问题中，给每一个设备编号，即形成设备ID，就是一种简单可行的Cf映射关系。

这样，数据相关性判断就可以归结为相关因子的比较：

Correlativity (D, D’) = (i = = i’ ? 1 : 0)

这里并非为了故弄玄虚。相关键的归纳是为了让讨论适用于可能更多的问题，而不仅仅局限于网络设备网管数据处理。相关因子的引入则是为了后面调度算法的简化－以相关因子作为输入的调度算法不用再考虑随具体情况变化的相关键，更具有通用性。

时间标签(timestamp)和时序索引(chronologic index)

在许多具体问题中，数据本身就带有其产生的时间，可以称为内置时间标签(inline timestamp)，比如网管问题中的告警、心跳信息、话单数据等。但内置时间标签并不见得可用。考虑到其它具体问题中，时序相关的数据不见得一定要来自同一物理源，所以可能会出现有的数据有内置时间标签而有的没有的情况。或者即便有，由于不同源，它们的标准可能不一样(比如和不同的NTP服务器同步，甚至是系统时间)，从而不具有可比性。

另一个选择就是数据到达处理器的时间，或称提交时间。虽然提交时间顺序并不总是和数据的本质时序严格一致，但实际应用证明，提交时序通常能比较好的反应数据的本质时序。在没有更好的选择的前提下，采用提交时序不失为一种次优的选择，而且可以简化问题的解决(将在后面讨论)。

在具体问题的解决过程中，我们并不一定(有时也会，将在后面讨论)关心数据的时间标签(TS)，而更关心基于时间标签的数据顺序。在此引入时序索引j = CI ( TS(D) )，对于任意两个时序相关的D, D’，如果TS(D) < TS(D’)，则可以j < j’，时序索引可以落在一个正整数(或非付整数)集合J上。数据的时序索引可以让我们知道先处理哪个，后处理哪个－当然，如果它们时序相关的话。

时序相关(chronologically correlative)

在此需要专门强调的是，时序相关并非数据的固有特征，即便它们包括了时间标签，时序相关取决于数据处理的业务逻辑或处理算法(前面我们表述为数据处理的时序相关的，或者数据针对具体处理算法的相关性)。比如，前面的网管问题中，同样是以设备告警为对象数据，告警次数的统计就是非时序相关的，而基于告警的设备状态计算就可能是时序相关的了。

任务(Task)和处理器(Processor)

加速数据处理的解决方案就是对数据处理的流程进行划分，分解成小任务，再映射到处理器上，实现并行计算甚至分布式计算。这里所说的处理器并非物理上的，而是虚拟处理器，如线程(Thread)，不跨或跨物理边界的进程(intra/inter-box process)。对于离散的到达处理器的每一份数据D _ij，可以定义对应的处理任务Task _ij，其中i指任务的相关因子，j则是基于相关因子的任务时序索引值，如前所述。

鉴于并行计算中任务间的偏序关系可以用有向无环图DAG(directional acyclic graph)描述，刻画任务时序相关关系的DAG(T, E, A, D)是一个如图2所示的特殊距阵：

 

图2        时序相关任务距阵

 

其中T = {Task _ij | i ∈ [1, m], j ∈ [1, ∞]}为任务集，E = { e _ij = e[Task _ij, Task _ij+1] | i ∈ [1, m], j ∈ [1, ∞]} 为任务间时序关系集合。A = {a _ij | i ∈ [1, m], j ∈ [1, ∞]}为任务计算量集合，D = {d _ij | i ∈ [1, m], j ∈ [1, ∞]}是对应任务的通信量。

在执行过程中，任务间的通信方式依赖于虚拟机类型，比如可以采用队列、共享内存，套接字连接等，实现技术都很成熟，这里不展开讨论。时序相关任务解决方案要回答的问题主要有两个：

l     怎样组织虚拟处理器。处理器拓扑结构也可以用一个DAG表示。

l     将任务DAG映射到虚拟器DAG，即任务调度算法，将每一个任务分配给一个确定的处理器执行。