基于直方图的数据流降载策略

数据流模型中数据高速流过，现有的存储设备可能无法存储全部海量数据，这就须要对延迟数据采取一定的技术手段来保证系统重新正常运转.使用降载算法，舍弃部分数据，用近似数据源替代精确数据源，可以减缓系统的处理压力，从而为数据流系统的查询操作提供一定保证.为此文献提出在数据流管理系统中进行查询操作时动态地插入和删除降载操作符来解决数据过载的问题.选择降载数据时主要采取两种方法:以随机的方式丢掉一部分数据;根据数据流内容的重要性丢弃一部分相对不太重要的数据.文献提出对于多数据源的数据流要采用分类的方法.使用马尔科夫模型来预测数据流中特征值数据的位置，用贝叶斯决策理论来评判部分数据被删除后的误差.文献提出使用贪心算法来选择要删除的数据，利用矩阵实现对数据精度的控制.

用户在进行数据流查询时，用户关注的是数据的变化、分布和多样性.当数据流中数据过载时，必须删除部分数据来换取系统的正常运转.在数据流中，很多数据数值近似或完全相同.这些大量重复出现的数据代表了数据的冗余.使用直方图可以精简数据流中的冗余数据，减少过量数据对系统资源的压力.这里主要研究了利用直方图技术。实现数据流的降载.为了克服现有方法不足，本文提出了基于距离的直方图降载算法.

1问题描述

数据流中的降载问题是:如何让一个容量有限的缓存尽可能多地容纳实时到达的数据，如何在暂存数据趋向于饱和并且系统处理能力无法无限升级的情况下，在尽可能保留数据特征的同时，删除部分数据，要求这种操作对数据流查询结果的错误率的影响尽量小.由此可见如何选择这部分被舍弃的数据成为函待解决的问题.

基于直方图的数据流降载方法的系统架构如图1所示，具体操作如下:

a.对数据流进行监控，若发现有缓存饱和的趋势或者被延迟处理的数据越来越多，则判断是否发生了过载，若发生了过载，则执行降载操作来保证系统继续运行;

b.求取新到达的数据与邻近桶中代表数据之间的距离，若距离不大，则将新来的数据加入到该桶中，若距离超过阈值，则用新来的数据创建一个新的桶，桶与桶之间的数据不相交;

c.用每个桶的代表数据组成新的数据流参与数据流查询.

2实验评估

使用的数据流为某网站的服务器流量.该网站主要从事电子商务，顾客会为服务器带来流量.平时流量不太大，当网站为商品做促销活动时，流量会突然增大很多倍，甚至超出服务器的承受能力.本实验从流量突然增大前开始采集数据.

实验采用的计算机配置为CPU Intel i5 3470，内存8GB，操作系统Windows XP.

数据流查询操作结果的准确性很大部分取决于数据源.采用降载算法得到的是被压缩后的近似数据流，这些近似数据保留了数据流的多样性.过载发生时数据流中的数据流速，系统压力程度的不同都会导致降载算法对最终的查询结果产生影响.

进行实验时，首先对没有使用降载算法的数据流进行查询，得到精确的查询结构.以1s为时间间隔，对数据流进行了6个查询，计算出每个查询的错误率，计算这6个错误率的平均值并与使用降载算法后的6个查询错误率的平均值进行比较.若系统的负载压力系数p(p0)不同，则在使用不同降载算法后，得到的查询结果精确度也完全不同.若p=3，则表示系统承受的负载是系统容量的3倍.即使系统的负载远大于系统的容量，使用HLS算法后平均错误率也不是很高，远低于随机降载(random laod shedding, RLS)算法.

随着时间的变化，系统数据流流速的快慢也会对算法产生影响.测试数据流最初以较慢的速率流入，每个时间间隔流入的数据量远小于系统的处理能力，这样就不会产生拥塞，查询结果错误率较小.过了一段时间，数据流流入的速率开始加快，逐渐有数据发生延迟处理，错误率开始提高，这时启动数据流过载算法，当数据流的流速进一步加速时，查询结果的错误率却没有提高.很明显，使用HLS算法产生的查询精度错误率要小于RLS算法.