一种服务器缓存的预取方法和系统与流程

1.本发明涉及网络中代理服务器的缓存预取方法。更具体地，涉及一种服务器缓存的预取方法和系统。


背景技术：

2.缓存是解决web响应速度问题的一个重要途径，代理服务器作为用户和远端服务器之间的中间站，可以将用户下一步想要读取的数据提前缓存在本地，避免每次都从远端服务器访问数据而造成当下过多的网络开销。缓存命中率越高，用户体验到的网络延时就越小。
3.目前缓存预取方法大量利用马尔可夫模型，因为马尔可夫模型有着较高的准确率和较强的实时性。以马尔可夫模型为基础的预取方法需先建立一个预测模型，该模型一般采用树型形式，将每个web页面作为树中的结点，依据现有的缓存日志将这些访问序列添加至树中，从根到某一叶子结点的串联序列被定义为用户的一个访问路径。通过该预测模型，可以对新输入的用户访问路径做出下一步预测，提前将该预测到的页面放入缓存，提高代理服务器的缓存命中率。同时，本次访问也将作为日志添加到预测模型中。
4.但通常采用的基于马尔可夫模型的预测方法具有如下不足：1、预测模型构建时，结点通常采用单一化的访问频率作为其目标函数，影响因子不够全面；2、预测模型无法实时动态调整。
5.因此，需要提供一种服务器缓存的预取方法和系统。


技术实现要素：

6.本发明的目的在于提供一种服务器缓存的预取方法和系统，以解决上述缺点的至少一个。
7.为达到上述目的，本发明采用下述技术方案：
8.一种服务器缓存的预取方法，步骤包括：
9.建立预测模型，依据现有的缓存日志将访问序列添加至所述预测模型，将待加载页面设为所述预测模型结点；
10.为预测模型中的结点添加目标函数；
11.响应于用户访问操作，在预测模型中查找可能遇到的多个后继结点；
12.基于目标函数评价各后继结点预测成功的可能性；
13.选择可能性最大的后继结点作为预取结果，对该结点的待加载页面进行缓存；
14.根据实际被访问页面，实时调整所述预测模型。
15.可选地，所述目标函数为
16.φ＝(1+λ)ξ117.其中，
18.φ为预测成功可能性；
19.ξ1为用户的访问频率；
20.λ为页面大小和访问时间差相关的变量。
21.可选地，所述目标函数进一步包括
22.ξ1＝1/[1+η
·
ln2(f
p
/fc)]
[0023][0024]
其中，
[0025]
fc为该结点的访问次数；
[0026]fp
为该结点的父结点的访问次数；
[0027]
η为参数，随f
p
/fc的改变而变化；
[0028]
sa为常数，表示经常缓存的页面大小；
[0029]sp
为该结点页面大小；
[0030]
δt为该结点页面本次访问和上次访问之间的时间差；
[0031]
t1为时间差下限；
[0032]
t2为时间差上限；
[0033]
θ为页面大小差值绝对值的上限。
[0034]
可选地，根据实际被访问页面，实时调整所述预测模型进一步包括，
[0035]
当预取结果错误时，若所述预测模型中存在实际被访问页面的结点，则调整所述结点的目标函数，以增大其预测成功可能性，提高所述结点的被预测能力；
[0036]
若所述预测模型中不存在实际被访问页面的结点，则将该页面作为新结点插入预测模型中。
[0037]
一种服务器缓存的预取系统，包括
[0038]
建模单元，用于搭建预测模型，依据现有的缓存日志将访问序列添加至所述预测模型，并将待加载页面设为所述预测模型结点；
[0039]
预取单元，用于响应于用户访问操作，根据所述预测模型预测该用户即将访问的下一个页面，并对所述页面进行缓存；
[0040]
更新单元，用于根据实际被访问页面，实时调整所述预测模型。
[0041]
可选地，所述建模单元包括
[0042]
数据存储模块，用于根据服务器历史缓存日志存储页面标识和用户访问路径；
[0043]
模型构建模块，用于依据现有的数据存储记录对预测模型初步构建，并将待加载页面设为所述预测模型结点；
[0044]
目标函数构建模块，用于对预测模型中的结点添加目标函数，完成预测模型构建。
[0045]
可选地，所述预取单元包括
[0046]
预测模块，用于响应于用户访问操作在预测模型中查找可能遇到的多个后继结点，并基于目标函数评价各后继结点预测成功的可能性；
[0047]
预存模块，用于选择可能性最大的后继结点作为预取结果，对该结点的待加载页面进行缓存。
[0048]
可选地，所述更新单元，用于根据实际被访问页面，实时调整所述预测模型，当预
[0067]
其中，
[0068]
φ为预测成功可能性；
[0069]
ξ1为用户的访问频率；
[0070]
λ为页面大小和访问时间差相关的变量。
[0071]
在一种可能的实现方式中，所述目标函数进一步包括
[0072]
ξ1＝1/[1+η
·
ln2(f
p
/fc)]
[0073][0074]
其中，
[0075]
fc为该结点的访问次数；
[0076]fp
为该结点的父结点的访问次数；
[0077]
η为参数，随f
p
/fc的改变而变化；
[0078]
sa为常数，表示经常缓存的页面大小；
[0079]sp
为该结点页面大小；
[0080]
δt为该结点页面本次访问和上次访问之间的时间差；
[0081]
t1为时间差下限；
[0082]
t2为时间差上限；
[0083]
θ为页面大小差值绝对值的上限。
[0084]
在一种可能的实现方式中，根据实际被访问页面，实时调整所述预测模型进一步包括，
[0085]
当预取结果错误时，若所述预测模型中存在实际被访问页面的结点，则调整所述结点的目标函数，以增大其预测成功可能性，提高所述结点的被预测能力；
[0086]
若所述预测模型中不存在实际被访问页面的结点，则将该页面作为新结点插入预测模型中。
[0087]
在一个具体的实施例中，根据模型目标使用多参量的目标函数，在概率计算的基础上将缓存替换策略的相关参量组成页面访问热度值，直接有效地提高代理服务器的缓存命中率，最后用动态的容错机制来完善模型，以进行更精确地预测。
[0088]
具体的，结点目标函数在常用的访问次数参量的基础上，线性组合用户等级和访问热度，目标函数描述为：
[0089]
φ＝(1+λ)ξ1[0090]
其中，ξ1表示与访问频率相关的归一化参量(用户的访问频率)，λ表示页面大小和访问时间差相关的变量，为ξ1作补充完善。其表达式为：
[0091][0092]
对于参量ξ1：
[0093][0094]
ξ1表示用户的访问频率，fc表示该结点的访问次数，f
p
表示该结点的父结点的访问次数，η是一个参数，随f
p
/fc的改变而变化。
[0095]
根据结点的访问频率等于该结点的访问次数与所有子结点总访问次数之比，可知，ξ1＝fc/fa，其中fa是该结点的父结点的所有子结点的访问次数，则可得到ξ1＝1/[1+(f
a-fc)/fc]。
[0096]
为了节省计算，可以使用f
p
代替f
a-fc，因为f
a-fc《fa≤f
p
，则ξ1＝1/(1+f
p
/fc)会偏小，所以需要减小f
p
/fc的值.当f
p
一定时，随着fc增大，f
p
/fc偏大的趋势越来越小，因此使用对数函数的平方η
·
ln2(f
p
/fc)来表示这个逐渐缩小的趋势.通过对fc求导，可知f
p
/fc以平方阶减小，而ln2(f
p
/fc)的变化趋势要小于f
p
/fc，所以需要通过一个变动的参数η来补偿.经过计算，可得到参数η的简约取值：
[0097]
η＝i-1，其中i≥1且ei≤fp/fc《ei+1；当0《i《1时，i＝1。
[0098]
对于参量λ：(页面大小和访问时间差相关的变量)
[0099][0100]
sa是一个常数，表示经常缓存的页面大小，s
p
表示当前页面的大小，δt表示该页面本次访问和上次访问之间的时间差，t1，t2和θ表示参量计算的上下限，均为定值。
[0101]
本实施例的目标是提高代理服务器缓存的命中率，除了对历史浏览记录进行分析之外，还将缓存替换策略思想运用在预取技术中，使缓存中web页面特性对预取结果产生影响。
[0102]
为更准确描述目标函数，本文考虑了页面本次访问和上次访问之间的时间差以及该页面大小(size)的因素.显而易见，时间差代表该页面的新鲜程度；而web页面大小(size)会影响缓存的命中率(命中率是根据命中的个数来决定的)。因为web页面的size差别很大，有的页面会占用非常多的缓存空间和传输带宽，如果缓存这样的web页面，可能会减低缓存的命中率，反之如果把相同的空间存入一些较小size的页面，则可以保持缓存命中率不被降低，用户预取的传输带宽也能得到有效利用。
[0103]
在该公式中，sa可以选用页面的均值、中数或众数等统计值表示，s
a-s
p
表示当前页面和经常访问页面的size之差。这个差有正负之分，当该页面较小时，差为正值，即在ξ1的基础上加一个正值，且页面越小，差值越大，当δt一定时，λ越大；当该页面较大时，差为负值，即在ξ1的基础上加一个负值.
[0104]
当前页面size或时间差过大时，λ＝-θ/t1，即在ξ1的基础上减去λ绝对值的最大值。
[0105]
预测模型结点的目标函数构建完成后，为该模型设定一个多阶匹配的动态预测方法：
[0106]
当匹配成功时，可得到的预测结果y
j+l
往往不只有一个后继分支，此时根据上一节所计算得到的φ值来选择，φ值较大的结点预测成功可能性较大，所以选择该结点所代表的web页面作为预取结果。
[0107]
基于带有目标函数φ值的预测树模型，考虑其动态变化.当预取到一个结点u时，预测结果可能有两种：第一种是预测正确，模型的计算结果符合真实的情况，可以信任；第二种是预测错误，那么预测模型就需要进行适当的调整.
[0108]
当预测错误时，依然有两种情况：第一种是实际被访问的页面作为预测结点u的兄弟结点v，已经在预测树中存在；第二种是这一结点w没有在预测树的适当位置出现。
[0109]
当结点v已经存在，那么就需要调整v的目标函数，以增大其φ值，提高该结点的被预测能力.当这一结点w并未存在于预测树中时，建立一个反馈补偿机制，
[0110]
将该页面作为新结点插入预测树中。
[0111]
本实施例提出一种服务器缓存的预取方法，针对目前缓存预取工作度量指标单一化的薄弱环节，提出一个多参量的动态web预测模型，结合缓存替换策略为预测树结点构造包含多个参量的目标函数，并使该模型能够随新的输入进行自适应调整。提升了服务器的工作效率，带给用户更好的使用体验。
[0112]
本发明另一个实施例提供了一种服务器缓存的预取系统，包括
[0113]
建模单元，用于搭建预测模型，依据现有的缓存日志将访问序列添加至所述预测模型，并将待加载页面设为所述预测模型结点；
[0114]
预取单元，用于响应于用户访问操作，根据所述预测模型预测该用户即将访问的下一个页面，并对所述页面进行缓存；
[0115]
更新单元，用于根据实际被访问页面，实时调整所述预测模型。
[0116]
在一种可能的实现方式中，所述建模单元包括
[0117]
数据存储模块，用于根据服务器历史缓存日志存储页面标识和用户访问路径；
[0118]
模型构建模块，用于依据现有的数据存储记录对预测模型初步构建，并将待加载页面设为所述预测模型结点；
[0119]
目标函数构建模块，用于对预测模型中的结点添加目标函数，完成预测模型构建。
[0120]
在一种可能的实现方式中，所述预取单元包括
[0121]
预测模块，用于响应于用户访问操作在预测模型中查找可能遇到的多个后继结点，并基于目标函数评价各后继结点预测成功的可能性；
[0122]
预存模块，用于选择可能性最大的后继结点作为预取结果，对该结点的待加载页面进行缓存。
[0123]
在一种可能的实现方式中，所述更新单元，用于根据实际被访问页面，实时调整所述预测模型，当预取结果错误时，若所述预测模型中已存在实际被访问页面的结点，则调整所述结点的目标函数，以增大其预测成功可能性，提高所述结点的被预测能力；
[0124]
若所述预测模型中不存在实际被访问页面的结点，则将该页面作为新结点插入预测模型中。
[0125]
一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现上述方法。
[0126]
一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现上述方法。
[0127]
显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定，对于所属领域的普通技术人员来说，在上述说明的基础上还可
以做出其它不同形式的变化或变动，这里无法对所有的实施方式予以穷举，凡是属于本发明的技术方案所引伸出的显而易见的变化或变动仍处于本发明的保护范围之列。

技术特征：
1.一种服务器缓存的预取方法，其特征在于，步骤包括：建立预测模型，依据现有的缓存日志将访问序列添加至所述预测模型，将待加载页面设为所述预测模型结点；为预测模型中的结点添加目标函数；响应于用户访问操作，在预测模型中查找可能遇到的多个后继结点；基于目标函数评价各后继结点预测成功的可能性；选择可能性最大的后继结点作为预取结果，对该结点的待加载页面进行缓存；根据实际被访问页面，实时调整所述预测模型。2.根据权利要求1所述服务器缓存的预取方法，其特征在于，所述目标函数为φ＝(1+λ)ξ1其中，φ为预测成功可能性；ξ1为用户的访问频率；λ为页面大小和访问时间差相关的变量。3.根据权利要求2所述服务器缓存的预取方法，其特征在于，所述目标函数进一步包括ξ1＝1/[1+η
·
ln2(f
p
/f
c
)]其中，f
c
为该结点的访问次数；f
p
为该结点的父结点的访问次数；η为参数，随f
p
/f
c
的改变而变化；s
a
为常数，表示经常缓存的页面大小；s
p
为该结点页面大小；δt为该结点页面本次访问和上次访问之间的时间差；t1为时间差下限；t2为时间差上限；θ为页面大小差值绝对值的上限。4.根据权利要求3所述服务器缓存的预取方法，其特征在于，根据实际被访问页面，实时调整所述预测模型进一步包括，当预取结果错误时，若所述预测模型中存在实际被访问页面的结点，则调整所述结点的目标函数，以增大其预测成功可能性，提高所述结点的被预测能力；若所述预测模型中不存在实际被访问页面的结点，则将该页面作为新结点插入预测模型中。5.一种用于权利要求1-4任一项所述方法的服务器缓存的预取系统，其特征在于，包括建模单元，用于搭建预测模型，依据现有的缓存日志将访问序列添加至所述预测模型，并将待加载页面设为所述预测模型结点；预取单元，用于响应于用户访问操作，根据所述预测模型预测该用户即将访问的下一
个页面，并对所述页面进行缓存；更新单元，用于根据实际被访问页面，实时调整所述预测模型。6.根据权利要求5所述服务器缓存的预取系统，其特征在于，所述建模单元包括数据存储模块，用于根据服务器历史缓存日志存储页面标识和定义用户访问路径；模型构建模块，用于依据现有的数据存储记录对预测模型初步构建，并将待加载页面设为所述预测模型结点；目标函数构建模块，用于对预测模型中的结点添加目标函数，完成预测模型构建。7.根据权利要求5所述服务器缓存的预取系统，其特征在于，所述预取单元包括预测模块，用于响应于用户访问操作在预测模型中查找可能遇到的多个后继结点，并基于目标函数评价各后继结点预测成功的可能性；预存模块，用于选择可能性最大的后继结点作为预取结果，对该结点的待加载页面进行缓存。8.根据权利要求5所述服务器缓存的预取系统，其特征在于，所述更新单元，用于根据实际被访问页面，实时调整所述预测模型，当预取结果错误时，若所述预测模型中已存在实际被访问页面的结点，则调整所述结点的目标函数，以增大其预测成功可能性，提高所述结点的被预测能力；若所述预测模型中不存在实际被访问页面的结点，则将该页面作为新结点插入预测模型中。9.一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现如权利要求1-4中任一项所述的方法。10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现如权利要求1-4中任一项所述的方法。

技术总结
本发明公开一种服务器缓存的预取方法和系统，所述方法步骤包括：建立预测模型，依据现有的缓存日志将访问序列添加至所述预测模型，将待加载页面设为所述预测模型结点；为预测模型中的结点添加目标函数；响应于用户访问操作，在预测模型中查找可能遇到的多个后继结点；基于目标函数评价各后继结点预测成功的可能性；选择可能性最大的后继结点作为预取结果，对该结点的待加载页面进行缓存；根据实际被访问页面，实时调整所述预测模型。本方法是在经典马尔可夫预测树的基础上，创造性地提出了一种多参量的动态Web预取模型，并设置动态调整的容错机制，有效提高缓存命中率且实现模型实时更新，自适应新的场景，以进行更精确地预测。预测。预测。


技术研发人员：王卓君 张宇 顾韶竹
受保护的技术使用者：北京电子工程总体研究所
技术研发日：2023.04.28
技术公布日：2023/9/5