基于多维Markov预测的互联网视频文件处理调度策略研究与实现
何增辉 包逸之 高诗建
（国家新闻出版广电总局监管中心）
摘 要： 违规视频文件之间的关联性对分布式系统的整体处理速率有重要影响。本文在分析违规视频文件关联性的基础上，提出了基于多维Markov预测的互联网视频文件处理负载均衡调度策略（P-MM）。根据视频文件关联性，预测后续到达文件在各节点的分布情况，快速调整相应参数，实现分布式系统中各服务器节点之间的负载均衡。实验表明，引入P-MM调度策略后，缩短了系统的响应时间，提高了分布式系统的处理速率。关键词： Markov 互联网视频文件处理 负载均衡0 引言
提供互联网视频服务的网站数量迅速增加，随之而来的是海量的视频信息，各种违规信息(血腥暴力，淫秽色情，低俗趣味等)充斥互联网空间。分布式搜索系统虽然可以借助于现有搜索技术[1]，完成各种违规信息的搜索汇总，但服务器集群中各节点要花费较长的时间去分析和处理，效率较低，同时需借助人工干预进行甄别，耗费了大量的技术资源和人力资源。在分布式搜索系统中，不同的节点被赋予不同的任务，同时提供一部分共性服务。提高系统的处理速率有两种方法：增加节点数量，提高单个节点配置来提高处理速率；通过优化各节点间的负载调度策略，提高整个系统中各节点的处理速率。考虑到成本，在现有的分布式系统中，通过不断增加节点的数量，提高服务器配置，来提高系统的处理速率不太现实。根据违规视频文件的关联性,优化节点负载调度策略[2] [3]，提高服务器集群中各节点的处理速率，快速完成视频文件的分析和处理，以提高分布式系统的性能。目前分布式系统中各节点采用的调度策略，对相邻文件之间的关联性考虑不足。实际搜索到的违规视频文件之间存在一定的关联性，符合多维马尔科夫链分布特征，在此基础上提出了基于多维马尔科夫预测的互联网视频文件处理负载均衡调度策略（P-MM）。1 分布式搜索系统中的节点负载调度策略
当搜索到的视频文件到达各个服务器节点后，文件的大小和各节点的处理速度均存在差异，各节点上的队列长度各不相同。服务器节点之间的调度一般采用FCFS或RR，仅考虑了任务的时间特性，没有考虑到视频文件的关联性。2 基于多维马尔科夫预测的负载均衡调度策略
2.1 多维Markov链在负载均衡中的应用对搜索到的视频文件进行分析（如：搜索“3D***”），发现搜索到的各文件之间存在一定的关联性，分析结果见表1。各文件到达服务器集群时，在服务器集群内部各节点上的分布存在一定的规律性：关联文件集中在某些特定的服务器节点或某一些特定的程序上执行。表1 前300个相邻违规视频文件关联性
| 搜索引擎 | Baidu | YaHoo | 360搜索 | Bing搜索 | Sougou | you-dao | |
| 返回数 | 24400000 | 1010000 | 182,00 | 51300 | 110000 | 12266 | 42700 |
| 关联率 | 96% | 97% | 91% | 84% | 90% | 87% | 85% |
图1 存在相同服务的两个节点
由于节点在处理不同文件时的处理速率存在差异，产生两种不同的速率，速率之比为1:X 。在此假定：节点1提供A类文件处理服务，标记为S1；节点2提供B类文件处理服务，标记为S2。A在到达服务器集群时，以概率P进入节点1，以1-P的概率进入节点2；B在到达服务器集群时，以概率P*进入节点2，以1-P*的概率进入节点1。当节点的负载未满时，允许新到的文件迁移到本节点，以维持集群中各节点的负载均衡，降低文件请求时间。两个节点均满载时，为避免节点之间反复迁移文件出现溢出现象，做以下规定：若节点1已有视频文件迁移到节点2上，当节点2负载满时节点1中又有新的文件请求迁移进节点2，则将新迁移来的视频文件“退回”到原来的节点上，此时若节点1上的负载也处于“满负载”状态时，该工作负载将被“阻塞”。假设视频文件的到达率符合以下定义：文件到达率符合均值为λ1与λ2的泊松分布；A在节点1、2中的请求服务时间服从期望为?1、?1*的指数分布；B在节点1、2中的请求服务时间服从期望为?2*、?2的指数分布；A、B在节点1、2上的分布密度分别定义为:T1=λ1/?1, T2=λ2/?2，T1*=λ1/?1*, T2*=λ2/?2*因此，节点1、2的负载状态可以用2个Markov过程来模拟，如图2，图3所示。图2 节点1 中有工作负载迁移到节点2
图3 节点2 中有工作负载迁移到节点1
讨论各节点状态的概率前，做以下定义：设S(i1,i2)为服务器节点当前的负载状态，表示节点1中已有i1个工作负载文件等待处理，节点2中已有i2个工作负载文件等待处理；P(0,0)表示集群中各节点处于空闲状态S(0,0)时的概率，综合考虑集群中的负载均衡情况，2个节点存在3种负载状态，其概率分别为：（1）集群内两服务器节点上的负载都未达到最大时，其概率为:（2）集群内两服务器节点上，只有一个服务器节点上的负载达到最大时，其概率为:（3）集群中两个服务器节点上的负载都达到最大时，其概率为:此时的概率存在3种情况：2个节点之间无负载转移；节点1中有负载文件转移到节点2中；节点2中有负载转移到节点1种，此时的概率情况为：以上3种状态，包含了集群中只有2个节点时二维 Markov链的所有情况，所以，当且仅当T1/C1<1∩T2/C2<1时：P1+P2+P3=1（2.4）
根据公式2.1至2.4可以算出P(0,0)。因此，对于服务器节点1来说，其上视频文件的阻塞率可以表示为：同理，服务器节点2的视频文件阻塞率，可以表示为：2.2.2 集群中存在两个服务器节点，但两节点均未采用负载均衡策略两个节点均未采用负载均衡策略，则每个服务器节点的负载状态，可以用一个独立的一维Markov 链表示。节点1处于空闲状态的概率用P1(0)表示，节点2处于空闲状态的概率用P2(0)表示，对两种状态进行分析，可得：由此可以从(2.7)、(2.8)中计算出2个节点的空闲概率P1(0)和P2(0)。节点1和节点2上的工作负载阻塞率用Pb1和Pb2表示，则两个节点上文件的阻塞率可以表示为：2.2.3 多集群多服务器节点负载均衡根据以上结果，把负载均衡策略扩展至多集群和多服务器节点。在分布式系统中，根据不同的处理任务，划分出不同的服务器集群，每个集群中有多个节点，总共有n个节点。不同的集群和集群中的不同节点根据自身的负载情况在各节点之间均衡负载。若第j个集群中有ij个工作负载，其总容量为Cj，负载密度为Tj。用P(0)表示所有服务器节点内工作负载为0的初始状态。则n个服务器间的负载状态及相互迁移情况用n维的Markov链描述，共包含以下3种情况：（1）所有节点任务均未超载时，其概率表示为:（2.9）
（2）集群中只有一个节点任务超载的概率用P1表示（2.10）
（3）有s(s<n)个节点任务超载的概率用Ps表示（2.11）
（4）所有n个节点的任务均超载的概率表示（2.12）
同理，由Markov过程的特性可知:P0+P1+P2+…Ps+…Pn=1（2.13）
则可求得P(0)的值，从而求出所有集群都超载的概率值。2.3 算法思想根据多维Markov链中相邻文件的关联性，设计算法，对进入分布式系统的视频文件进行调度，以预测[6]新到视频文件将要被分配到哪个节点中执行。其核心算法的伪码描述表示为：Initialize Cj,Tj, RQi ,P：While (Get- taski)Assign taski to serverj based on Task Types;If (serverj is overload) P=Max {P1…Ps, Pn};If (P= P1) Migration (n-1);Else if (P= Ps) Migration (n-s);Else if (P= Pn) Put taski in the RQ;End ifEnd while;Migration (k):Assign the file to a server based on Task Types and Min (RQ) from servers (k);Get- taski表示进入分布式系统的视频文件；Cj表示服务器集群中节点数量；Tj表示每个节点的权重; RQi表示等待队列长度；Migration表示任务的迁移。3 系统和负载模型
Li Xiao等开发地分布式系统模拟器[7] [8]，能够模拟集群内不同节点的负载调度情况。本文扩展了该系统的功能，使其能够同时模拟15个不同的集群（每个集群中包含10台服务器节点）运行负载调度情况，实验参数如表2所示。系统中每一个任务只能处于以下几种状态中的一种：“就绪状态”、“执行状态”、“页失效状态”、“数据传输状态”和“完成状态”。系统有以下的规定和假设：表2 实验中分布式系统中的节点和网络参数
| CPU的速度 | 100 MIPS | 内存页面大小 | 4KBytes |
| 内存的大小(MS) | 64 MBytes | 以太网速度 | 10Mbps |
| 系统使用的内存大小(U-sys) | 16 MBytes | 页失效的处理时间 | 10ms |
| 用户可用的内存空间大小 | MS-U-sys | 一个CPU时间片的时间 | 6ms |
| CPU内容跳转的时间 | 0.1ms | 远程执行的额外代价 | 0.1sec |
4 性能分析
基于分布式系统中集群节点的负载状况，将视频文件的平均响应时间作为衡量系统性能的主要指标，分别讨论表3中所示的4种负载均衡调度策略，在引入基于多维马尔科夫预测的互联网视频文件处理负载均衡调度策略前后的性能表现，考虑到分布式系统处理视频文件的特点，选取内存需求为4Mbytes的日志文件进行比较。表3 实验中负载共享策略与节点调度机制
| 1 | CPU-MEM_FCFS | 基于CPU-MEM负载共享和先来先服务调度机制的策略 |
| 2 | CPU-MEM_RR | 基于CPU-MEM负载共享和轮询调度机制的策略 |
| 3 | CPU-MEM-RR_MMMCS | 基于CPU-MEM负载共享和多内存多时间片轮询调度机制策略 |
| 4 | RR_MMMCS-A-P | 基于工作负载预测的自适应多内存需求多时间片轮询调度机制策略 |
图4引入P-MM前8个日志任务平均响应时间
图5引入P-MM 后8个日志任务平均响应时间
表4 实验中P-MM策略性能提高比率
| 调度算法 | 日志平均响应时间①（单位：ms） | 日志平均响应时间②（单位：ms） | 加速系数 |
| CPU-MEM_FCFS | 1295.46 | 584.49 | 1.91 |
| CPU-MEM_RR | 866.39 | 673.88 | 1.29 |
| CPU-MEM-RR_MMMCS | 856.48 | 710.2475 | 1.21 |
| RR_MMMCS-A-P | 738.79 | 596.56 | 1.24 |
5 结束语
如何在资源有限的情况下，快速的对违规视频信息进行分析和处理是目前分布式系统面临的主要问题。通过对互联网违规视频文件进行分析，在此基础上提出了基于多维Markov预测的互联网视频文件处理负载均衡调度策略。P-MM负载均衡调度策略较好的调配了分布式系统的资源，缩减了视频文件的调度和处理时间，提高了分布式系统的性能；增加了预测机制，该策略在平均响应时间上都有较好的表现。进一步的工作是在分析视频文件之间关联性的基础上，结合分布式系统节点内的调度策略对调度算法进行优化。 参考文献[1] 周利民,童珉,陈燕双.面向互联网视频主题管理的搜索引擎关键技术研究与实现[J].广播与电视技术,2014,41(6).
[2] Puccinelli, D. Haenggi, M. Lifetime benefits through load balancing in homogeneous sensor networks[C]. Budapest: Wireless Communications and Networking Conference, 2009.
[3] Ling Jin, Hui Zhang, Longxiang Yang, Hongbo Zhu. A Novel Adaptive Load Balancing Algorithm in Heterogeneous Wireless Networks [J]. Journal of Information & Computational Science, 2014, 11(7).
[4] Abdallah Al Sabbagh, A Markov Chain Model for Load-Balancing Based and Service Based RAT Selection Algorithms in Heterogeneous Networks[C]. World Academy of Science: Engineering and Technology, 2011.
[5] Chun-Cheng Lin, Hui-Hsin Chin , Der-Jiunn Deng. Dynamic Multiservice Load Balancing in Cloud-Based Multimedia System [J]. IEEE Systems Journal,.2013,8(1).
[6] 石磊, 何增辉. 基于预测机制的自适应负载均衡算法[J].计算机应用, 2010, 30(7).
[7] Xiao Li, Xiaodong Zhang, Yanxia Qu. Effective load sharing on heterogeneous networks of workstations[C]. Cancun, Mexico: Parallel and Distributed Processing Symposium, 2000.
[8] 石磊, 孙雨岩. 基于CPU-MEM的负载共享调度机制研究[J].计算机应用研究,2008, 25(5).
编辑：中国新闻技术工作者联合会
评论 点击评论