0 引言

大数据规模的激增，给数据处理的服务平台带来不可预知的后果。对Web服务日志的分析，不仅能够帮助服务平台有效预防网络异常的产生，也能对服务平台进行压力测试分析，有利于提升服务平台的可靠性。然而Web日志中包含用户隐私信息，企业及政府等机构极少愿意公开日志供研究人员使用；同时，现已公开的Web日志数据年代久远，其特征不符合当前大数据时代特征^[1]。如何仿真生成逼真的Web日志，是学术界的热点问题，也是本文研究的方向。

以中国科学院的可伸缩大数据生成组件(Scalable Big Data Generator Suite,BDGS)^[1]为代表的Web日志生成器不仅能够用于Web服务器压力测试和性能研究，而且具有很高的扩展性。但有一个显著的缺点是:Web日志的时间依赖性表达能力很弱；以动态Web代理缓存负载生成器(Proxy Workload Generator,ProWGen)^[2]为代表的日志生成器能较好地以时间局部性拟合Web文件特征，却是采用静态分布模型。当前随着应用需求的日益扩大，要求生成器的仿真性能较高，这给Web日志生成方法带来了严重的挑战。事实上，当出现热点时，数据会表现为突发性地围绕热点^[3]动态变化。但当前已有的Web日志生成器主要是基于静态数据分布设计的，忽略了分布的动态性和用户行为的复杂性，虽然引入了Web文件的时间局部性，却没有站在时间角度来衡量Web文件的时间局部性。

针对此问题，本文提出一种动态仿真模型——基于用户兴趣迁移的Web日志仿真生成(Web Log Simulation Generation based on user interest migration，WLSG)算法。该WLSG算法对用户属性、Web文件属性分别和时间的依赖关系进行建模，也融入了用户兴趣迁移以及自适应访问兴趣度高的Web文件，能够生成具有强的时间依赖性，用户访问顺序可调，且包含用户的个性化特征的逼真日志数据。

1 相关工作

为了有效地测试Web服务器性能，已经有很多相关的研究。当前模拟生成Web日志的方法主要是日志驱动方法以及数学模拟方法，具体如下：

1) 在日志驱动方法中，对历史日志进行变换来模拟生成新的日志。由标准性能评测协会 (Standard Performance Evaluation Corporation,SPEC)开发的SPECweb99^[4]在连续请求中引入了睡眠时间(OFF time)，但是睡眠时间的长短并没有用可能产生自相似的模型来控制，这也造成产生的流量不具有自相似性。文献^[5]以照片评论的数据为背景，主要提到了关联关系在数据生成中的重要性，按照五种关联关系提取真实数据的分布用来模拟，然而真实数据远不止五种关联，因此生成器还有一定的局限性。基于MapReduce的大数据生成器可以用来测试在线分析系统的处理能力。其中BDGS^[1]模型在体积、速度、多样性、真实性方面来生成数据，它利用隐式狄利克雷分配(Latent Dirichlet Allocation,LDA)模型分布来建立泊松模型分析Web文件，能够生成文本、图和表类型的数据格式，但是没有考虑时间的依赖性。雅虎云计算评测(Yahoo! Cloud Serving Benchmark,YCSB)^[6]的数据生成器嵌入了基于分布的生成器，虽然能够测试系统的性能，但是，它并未考虑复杂的数据间依赖，也无法快速扩展真实数据的数据量。文献^[7]充分考虑单表在构成多表时的属性内部和外部关联，利用时间依赖的LDA技术考虑时间依赖关联,然而没有考虑网络流量中的自相似性特征。

2) 在数学模拟方法中，通过充分地研究Web对象访问特征来建立数学模型来模拟生成Web日志。ProWGen模型^[2]首先提出从Web对象的特征分布角度着手，利用Zipf-like分布与时间局部性原理来建模，为数学模拟方法提供了依据。并行数据生成框架(Parallel Data Generator Framework,PDGF)模型^[8]能够对复杂的语义进行切分，使有依赖的属性之间并行生成，然而用户需要非常了解数据集。文献^[9]指出在多媒体应用中，日志数据的分布并不符合Zipf-like分布，由于缓存技术的提高和多媒体存在大型视频文件的特性，Web日志更加符合广延指数分布，这种分析方式为本文的多种分布特性提供了依据。

综上所述，虽然日志驱动方法有较高的仿真性能，能对真实数据进行量的扩展，但对真实数据的依赖性太强；本文吸收了日志驱动方法的优点，采用数学模拟方法，在用户和Web文件之间加入兴趣度因子，对“用户总是先访问最感兴趣的文件”进行建模，提出一种用户兴趣度迁移算法，以此达到提高Web日志数据自相似性和真实性的目标。

2 理论基础 2.1 日志数据中的重尾分布

文献^[2]通过分析各种真实网络日志数据，发现重尾分布与网络流量自相似特性有很大关联，服从重尾分布的随机变量特点是：随机变量X的抽样值中，小抽样值的数量较多，大抽样值的数量较少，这就形成了重尾现象,其概率密度函数为p(x)=1-(k/x)^a,其中:参数a称为重尾度索引，它决定分布的重尾度; 参数k决定重尾分布的尾起始点。

在Web日志中Pareto分布可以用于描述时间间隔和文件数量的关系。文献^[9]指出当用户请求文件时，服务器发送文件时存在延迟传输问题，因此文献^[10]认为用户请求动作与访问动作之间的时间间隔服从重尾分布以概率p作为参数来求时间间隔Δt，如式(1)所示：

$\Delta t=k/{{(1-p)}^{1/a}};p\in (0,1)$

(1)

其中Δt也能表示Web服务器主动OFF时间。通过设置主动OFF时间，很久之前被访问的文件，当其OFF时间到达时，依然能在下一刻获得被访问的机会，这就能使序列更加均衡。用户的先后到达顺序可以由Web文件的时间局部性决定^[2]。

2.2 用户日志中的威布尔分布

设服务器的用户请求序列为Y={Y_ui|u∈n,i∈m}，其中:n是用户总数，m是页面总数。请求序列按照用户访问的时间先后排序，可以将请求序列划分成多个用户的访问序列。对1995年美国国家航天航空局网站的8月份1569898条请求序列进行统计，如图 1所示，横坐标为两个用户之间的时间间隔。可以看出大部分用户都是在很短的时间间隔内到达，而小部分用户是相隔很长一段时间才能到达。其累积概率分布如图 2所示，横坐标为用户到达的时间间隔。拟合结果表明，用户到达模式近似服从威布尔分布,其累积概率分布函数为p(x)=1-exp[-(x/λ)^k]，其中参数k和参数λ的拟合结果分别为0.29和7。以概率p作为参数可以得到时间间隔ΔT。

$\Delta T=\lambda {{[-{{\ln }^{(1-p)}}]}^{(1/k)}};p\in (0,1)$

(2)

式中ΔT可以表示为Web服务器被动OFF时间。

2.3 用户日志中的齐普夫分布

当用户点击Web服务器某链接发起请求时，浏览器展示给用户的页面是由多种类型的Web文件构成，包括商标图片、flash动画、广告链接等一系列内容构成Web对象^[9]。在分析日志中用户行为时会发现用户在极短时间内连续访问多个文件的现象，显然现有的采用静态分布模型的Web日志生成器没有考虑这个现象。将此现象模拟成用户发送连续请求，通过对美国航空航天局(National Aeronautics and Space Administration,NASA)网站数据分析发现，用户发出连续动作次数概率服从齐普夫分布^[8]。在Web对象中，用户连续访问2个以上文件的概率超过73%，而用户连续访问12个以上文件的概率已经非常接近0。假设用户u的总请求序列是Y_u={Y_u1,Y_u2,…，Y_uk,…，Y_um}，其中Y_uk为用户u访问的第k个Web文件，则第k个Web文件被访问的概率为p(i_uk)=k^ω，利用最小二乘法拟合可得ω=-0.964。

3 基于遗忘曲线的ITDF模型

为了更好地理解用户兴趣与时间依赖，以OFF时间来构建用户请求序列，如图 3所示，t₀时刻为用户u_k到达时间，u_k向Web服务器发送连续请求，每次请求之间存在服务器主动OFF时间Δt，u_k的连续请求构成一个Web对象，u_k本次访问结束时刻为t₁。在第k+1名用户u_k+1到来之前服务器处于等待状态，也即服务器被动OFF时间ΔT，u_k+1在t₂时刻开始向Web服务器发送请求。为了使OFF时间更加合理，考虑请求序列的负载均衡改进OFF时间，具体做法如下：

对于流行度高的Web文件的OFF时间间隔会很短，这样会造成短时间内同一个Web文件被频繁访问，因此对流行度高的Web文件的Δt加入惩罚因子1/ln(1+Pop_i)，其中Pop_i表示文件i的流行度。改进式(1)为式(3)；同理，对活跃度高的用户的ΔT加入惩罚因子1/ln(1+Act_u)，其中Act_u表示用户u的活跃度。改进式(2)为式(4)：

$\Delta t=\lambda {{[-{{\ln }^{(1-p)}}]}^{(1/k)}}/{{\ln }^{1+\mathbf{Po}{{\mathbf{p}}_{i}}}}$

(3)

$\Delta T=\lambda {{[-{{\ln }^{(1-p)}}]}^{(1/k)}}/{{\ln }^{1+\mathbf{Ac}{{\mathbf{t}}_{u}}}}$

(4)

接着将用户和Web文件利用时间局部性关联，根据时间局部性定义：“最近刚刚访问过的文件比很久以前访问的文件更有可能在不久的将来被再次访问”^[2]，这里也由局部性特征而带来一个缺陷，即如果最近访问的是用户不感兴趣的Web文件，那么再次被访问的可能性会降低。文献^[11]认为同种数据在不同时刻的关系符合艾宾浩斯遗忘曲线。在本文中提到的用户与Web文件的兴趣同样也和艾宾浩斯遗忘曲线相似，不是简单的逐步衰减，而是非线性的先快后慢。用户在短期内的兴趣度会有大幅度下降，而在长期中却能保持一个稳定的兴趣。

艾宾浩斯遗忘曲线描述了人们在学习时遗忘的过程是不均衡的，呈先快后慢的变化规律。如图 4所示，图中横坐标表示经过的天数，纵坐标表示用户的记忆量百分比。可以发现在第一天内记忆量就从100%迅速下降到33.7%，之后缓慢地下降。用最小二乘法模拟的艾宾浩斯遗忘曲线如图 3所示，其模拟函数如式(5)所示:

${{W}_{ui}}=a{{t}^{-b}};t>0$

(5)

其中：a=31.75,b=0.1306。

用户的兴趣度和记忆量变化极为相似，因此本文基于艾宾浩斯遗忘曲线构建的用户兴趣迁移与时间依赖(user Interest transferring and Time-Depending based on Forgetting curve，ITDF)关系的模型可以用来控制用户的兴趣漂移。用式(5)中的W_ui表示用户u对文件i的兴趣度，t表示用户u当前访问文件i的时间与上次访问的时间间隔。

4 基于ITDF模型的WLSG算法

已知用户集合U={u₁,u₂,…,u_n}和Web文件集合I={i₁,i₂,…,i_m}，通过分析网络流量中用户和Web文件的关系可知，用户的活跃度和Web文件的流行度存在重尾分布现象^[2]，可以通过活跃度和流行度的累计概率来关联用户和Web文件，构成原始用户请求序列Y={Y₁,Y₂,…,Y_u,…,Y_n}，然后再考虑用户的兴趣影响并加入OFF时间，将用户请求序列重新组合为新的Y′={Y₁′,Y₂′,…,Y_u′,…,Y_n′}。WLSG算法描述如算法1所示:

1) for (u∈U)

2)  exit=false;

3)  currentTime+=ΔT;//用户到达时间

4)  while(!exit)// 计算用户连续访问数量

5)   k=Y_u.length;

6)   d=double(0,k);//0到k之间的随机浮点数

7)   p=$\left\lceil \text{d} \right\rceil $^ω;

8)   if (k=1){s=1;exit=true;}

9)   if (p>d-$\left\lceil \text{d} \right\rceil $){s=$\left\lceil \text{d} \right\rceil $;exit=true;}

10)  end while

11)  for(i∈Y_u){get W_ui();}//计算用户兴趣迁移

12)  descSort(Y_u);//根据用户对文件的兴趣度降序排序

13)  Y_ui.time=currentTime+Δt;// 用户访问时间

14)  Y_u′.add(Y_u1~Y_ud);//加入新的用户访问序列

15)  Y_u.remove(Y_u1~Y_ud);

16) end for

在算法1中：步骤3)计算当前用户u的到达时间currentTime；步骤4)~10)获取用户u的连续访问序列长度s；步骤11)计算用户兴趣迁移值；步骤12)~15)将用户请求序列重新组合为新的Y_u′。

5 实验与结果分析 5.1 数据集

在生成Web日志之后需要观察模拟Web日志的仿真性能，采用真实数据集作为参照比对。实验采用NASA、劳伦斯伯克利实验室TCP流量(Lawrence Berkeley Laboratory-TCP traffic,LBL-TCP-3)数据集以及MovieLens 1M数据集。其中NASA为31天采集的1569898条日志数据； LBL-TCP-3为两小时采集的1789995条报文数据；MovieLens 1M为6040个用户对3952个电影的1000209条评分记录。其中NASA数据集合LBL-TCP-3数据集为Web日志特征研究^[13-14]中广泛使用的数据集。MovieLens 1M数据集由GroupLens项目组收集，由于它具有明显的用户行为特征而被广泛用于个性化推荐领域^[15]，而且文中提到的用户活跃度和物品流行度的关系在其中表现更加明显，因此MovieLens 1M数据集适用于验证Web日志仿真性能。

5.2 评测指标 5.2.1 自相似性

研究人员发现自相似性广泛存在于不同的网络环境中^[3]，使用流量自相似性作为流量突发性的衡量指标更能反映网络流量的特性,网络流量的突发过程更符合渐近或严格的自相似模型。可见，自相似性模型在网络流量仿真生成方面有重要的地位，尤其是在基于时间序列的网络流量中，自相似性的时间平稳性特征表现得更加明显。用于描述自相似特性的参数为H(Hurst,赫斯特)指数^[12]，H∈(0.5,1)，H越大，聚集过程的自相似程度越高。下面介绍如何利用Hurst指数计算请求序列的自相似性

5.2.2 Hurst指数

由自相似性的定义知，要验证生成的Web日志是否满足自相似过程，必须满足两个条件:1)当聚集过程m阶的m→∞时，有r^(m)(k)与r(k)的特性相同；2)满足r^(m)(k)= r(k)~αk^-β，0 ＜β＜1且H=2-2β，其中H∈(0.5,1)。具体做法是，对于新请求序列Y′按照固定的时间间隔分段，计算每个分段中的请求数量，获得一个广义平稳过程X={x₁,x₂,…,x_i,…,x_n}，其中n表示将X共分成n个时间段，x_i表示第i个分段中的请求数量。样本均值为μ，样本方差为σ²。当样本时间分段跨度为k时，任意两个请求数量x_i与x_i+k的自相似系数r(k)可由式(6)计算得到,再用最小二乘法来模拟r(k)与k的函数关系可求出参数β进一步求得参数H。而x_i的m阶聚集过程可用式(7)表示，且在m已知时,可以求得i∈[1,n/m],k∈[(m-1)*n/m,n-1]，可以发现当m越大，k的取值范围越小。为了更准确地拟合自相似性过程，应该避免将m取较大的值。

$\text{r}\left( \text{k} \right)=E\left[ \left( {{X}_{t}}-\mu \right)\left( {{X}_{t+k}}-\mu \right) \right]/{{\sigma }^{2}}$

(6)

$\mathbf{X}_{k}^{(m)}=\frac{1}{m}\sum\limits_{j=km-m+1}^{km}{{{\mathbf{X}}_{j}}}$

(7)

5.3 实验结果及分析

首先，利用WLSG算法模拟生成时间跨度为10 h的一百万条Web日志，以1秒为时间间隔令m分别等于1,2,100,1000(当m太大时，k的数量变得非常少，不利于观察其趋势)来观测r(k)的变化，在图 5中，横坐标为时间段跨度k，纵坐标为自相似系数r(k)。在m取不同值时，随着k的增大，r(k)都是呈现出先快速后缓慢的减小趋势。

其次，考察真实数据集的Hurst指数情况，按照不同时间间隔来获取不同时间尺度下的请求序列，最后用Hurst指数来估计各个不同时间尺度序列的自相似特性。如表 1所示，可以发现对于每个真实数据集，随着时间尺度增大，Hurst指数在减小。这是因为时间尺度的增大，自相似系数r(k)的取值就变少。在拟合的过程中，也就造成拟合效果不佳。

同理，对量级为一万、十万、千万的模拟日志数据也作如上统计，发现在取不同m值时，仍然呈现相同的趋势。同时统计了三种真实数据集的自相似性变化趋势，如图 6所示。通过图 6可以发现，虽然由于数据集的差异会导致趋势存在不同，但自相似性都是符合呈现出先快速后缓慢的减小趋势。因此可以判断，对于仿真数据，当聚集过程m阶的m→∞时，有r^(m)(k)与r(k)的特性相同，符合自相似性第一条件。

现在考察仿真数据的Hurst指数情况，用Hurst-WLSG 表示考虑用户兴趣迁移的仿真算法(WLSG)数据的Hurst指数值，用Hurst-ProWGen算法表示不考虑用户兴趣迁移的ProWGen^[2]算法数据的Hurst指数值。ProWGen算法由于基于客观数学模型，在时间局部性和重尾分布特性上具有良好表现，但是其时间局部性存在缺陷，因此将ProWGen算法作为对比实验。在不同数据量级和不同时间尺度下分别对WLSG和ProWGen算法作20组实验，然后取平均值记录，如表 2所示。首先，随着时间尺度的增大，无论Hurst-WLSG和Hurst-ProWGen都会减小，这与真实数据集的Hurst变化是相符合的，说明仿真数据的自相似性良好。其次，在相同数据量级和相同时间尺度下，Hurst-WLSG大于Hurst-ProWGen；而且在相同数据量级下，随着时间尺度的增大，Hurst-WLSG的减小趋势比Hurst-ProWGen更加缓慢，在千万量级中最大提升自相似性约5.41%，总平均自相似性提升约为2.86%。这说明考虑用户兴趣迁移能够带来更好的自相似性。

最后，为了更加细致地比较表 2中WLSG和ProWGen算法的自相似性特征不同，本文从请求序列的突发性和自相似性变化趋势两个角度来比较。采用百万量级时间尺度为1 s条件下由WLSG和ProWGen算法生成的仿真数据。

由图 7(a)和图 7(a)的对比发现，在请求数量大于300时，WLSG算法中的时间点更多，这表明WLSG算法的突发性更强。

通过图 8(a)和图 8(b)的对比发现：1)ProWGen算法的自相似系数在k=20000时就趋近于0，而WLSG算法的自相似系数在k=30000时趋近于0，这说明在很长时间后，WLSG算法的自相似性依然能够保持；2)WLSG算法的自相似系数下降得更加平稳，说明其时间平稳性能更佳，也即自相似性能更强^[3]。

6 结语

针对传统Web日志仿真算法无法从时间上更客观地模拟Web日志的缺陷，结合艾宾浩斯遗忘曲线对用户的兴趣度动态调整，本文提出了一种与已有方法完全不同的基于用户兴趣迁移的Web日志仿真新算法，使得Web日志在时间序列条件下自相似性更加符合实际应用。实验结果表明，该模型通过用户的兴趣迁移，改变用户的访问序列，能够较好地模拟Web日志，可以有效地应用于Web日志的仿真生成。然而，在仿真生成Web日志时，当数据量达到一亿级别时，计算用户兴趣具有更高的时间复杂度。因此，如何更快以及更大量地生成Web日志是下一步要做的工作。