基于多尺度复合金字塔模型的缓存策略研究

王 贺，王志宝，陈良富，赵 亮

(1.东北石油大学 计算机与信息技术学院，黑龙江 大庆 163318；2.中国科学院空天信息创新研究院遥感科学国家重点实验室，北京 100000)

0 引 言

网络地理信息系统(WebGIS)是网络和地理信息系统的结合，以互联网协议和终端为基础形成的客户端地理信息应用系统，与人们的日常生活密不可分。传统的WebGIS系统通过客户端向服务器发送地理信息相关的请求，服务器收到后将相应的数据返回给客户端。该方法受网络速度和服务器配置的影响，存在响应时间长、渲染效率低的缺点。为了提高客户端显示效率，构建金字塔模型是重要的解决方案，在不影响画面视觉效果的同时，构建不同分辨率的多级数据来提高绘制速度，节省绘制所需时间。构建金字塔模型的关键环节是对空间数据进行组织，经过组织后的瓦片数据可以提升检索效率。

在大数据时代，由于瓦片数据的海量特性和用户规模的不断增长，仍然存在网络拥塞、服务器过载等问题。通过研究瓦片缓存策略，以读取缓存数据的方式来减少对服务器的请求数量，可以在数据组织的基础上减轻服务器和网络传输的压力。因此，改进现有的瓦片缓存策略对网络地理信息系统具有重要意义。

在瓦片金字塔的基础上，该文提出了一种多尺度复合金字塔模型。与传统的瓦片金字塔模型相比，它可以统一组织和管理多种类型数据。并在此基础上提出了一种基于多尺度复合金字塔模型的缓存置换策略(multi-scale compound pyramid cache replacement)，相较于现有的瓦片缓存算法，进行了如下优化：(1)支持加载多种类型数据；(2)考虑瓦片数据的空间特性，根据用户操作习惯，动态计算当前命中瓦片相邻及相邻层级瓦片数据的请求频次；(3)引入瓦片保护机制。在瓦片进入到缓存空间后，一段时间内无法被置换。这种方式可以有效解决当缓存空间已满时，新进入到缓存空间的瓦片数据由于价值最低而被置换的问题。

1 构建多尺度复合金字塔模型

对多种类型数据进行组织，传统的做法是将多种类型数据单独建立索引，建立不同的金字塔模型以分开管理。采用这种方式金字塔的构建效率低、管理难度大。所以该文提出了一种能够统一管理各类数据的多尺度复合金字塔模型，如图1所示。

图1 多尺度复合金字塔模型

多尺度复合金字塔模型从金字塔的底层到顶层，分辨率逐渐降低，包含了全球、区域、城市三个尺度数据，在不同尺度下又由多种类型数据共同组成，且多种类型数据在相同层级下表示的地理范围一致。

在多尺度复合金字塔模型中，在每种尺度下分别定义1个层级作为实际物理储存层级，负责储存该尺度范围内的所有信息。如图2所示，地理空间共分为

P

个等级，其中

L

级至

M

-1级为全球尺度；

M

级至

N

-1级为区域尺度；

N

级至

P

-1级为城市尺度。将多种类型数据根据三个尺度进行重新组织，并分别选择

L

级、

M

级、

N

级存储该尺度下的元数据信息。

图2 多尺度组织模型示意图

多尺度复合金字塔模型本质上是利用地理空间划分将同一尺度下不同类型元数据存储到统一的存储单元或单元组中，根据索引实现以空间区域为基础的文件组织管理体系。采用这种数据组织与管理技术可以将用户访问数据的空间区域位置与数据文件本身表达的空间区域位置建立直接关联，提高了海量数据的寻址检索。

2 瓦片缓存机制

传统的缓存置换算法主要有：先进先出置换算法(FIFO)、最近最少使用瓦片置换算法(LRU)、最不经常使用置换算法(LFU)。国内外学者针对瓦片数据缓存算法做了较多研究，Kang等对瓦片预取和替换方式进行了研究，根据计算结果留下概率高的瓦片；在此基础上，张婷婷提出了基于时空热度的瓦片缓存置换策略，可以快速传输影像数据；Hsiao等将多核gpu共享缓存中的瓦片进行分组，提出了一种基于多核位置感知的缓存置换算法(MLCR)；史孝国通过考虑瓦片的访问频率及瓦片数据大小计算瓦片的保留价值，对置换算法进行了改进；涂振发等提出了一种最小空间数据价值缓存置换算法(GDLVF),基于时间、频率及空间位置计算瓦片价值，将价值最低的瓦片置换；刘佳星等提出了基于地理单元热度的瓦片缓存置换算法(GUH)，通过考虑空间特性，结合贪婪算法置换出热度值最低的瓦片；陆晔等研究了基于主题时空价值的瓦片缓存算法(GDTST)，综合考虑了时间局部性、空间局部性以及用户主题倾向性，置换出主题时空价值最低的瓦片。传统的缓存置换算法没有考虑到瓦片数据的空间位置特性，瓦片命中率效果较差；传统的缓存置换算法只考虑了瓦片进入缓存时间及命中次数，瓦片命中率较差。在上述研究中，依然存在如下三个问题：(1)缓存置换策略都是基于同一类型数据进行研究，不适用于多种类型数据进行加载；(2)部分研究人员虽然考虑了空间位置特性以及请求瓦片对下一时刻其邻近位置瓦片被访问造成的影响，但是在进行研究时没有考虑用户的操作习惯，请求瓦片对临近位置瓦片影响相同；(3)未设置保护机制，新进入缓存的瓦片由于价值低可能会很快被置换出去。

因此，该文提出了一种基于多尺度复合金字塔模型的缓存置换策略MCPCR。MCPCR满足多种类型数据在客户端进行缓存，并充分考虑瓦片数据的空间特性，根据用户操作习惯，动态计算当前命中瓦片相邻及相邻层级瓦片数据的请求频次，当瓦片数据进入缓存时，计算当前瓦片数据价值，当缓存空间已满或达到阈值时，缓存空间中价值最低的瓦片将被替换。同时引入瓦片保护机制，在瓦片进入到缓存空间后，一段时间内无法被置换，避免当缓存空间已满时，进行置换操作时将新进入到缓存空间的瓦片数据剔除。

2.1 瓦片缓存索引设计

当用户在客户端请求数据时，首先要在缓存中查找是否存在相关数据，因此，为了实现缓存中数据的快速检索，需要对缓存索引进行设计，从而提高数据检索速度，本次研究基于多尺度复合金字塔模型设计了索引机制。

服务器端为已经组织好的多分辨率层级的复合瓦片金字塔模型。当客户端请求相应数据时，当缩放层级为Z时，获取到当前显示区域中心点的地理坐标Center(

X

,

Y

)；根据屏幕宽度

W

，屏幕高度

H

，以及浏览器显示的单位像素表示的实际地理距离

D

，以屏幕左下角为原点，计算屏幕左下角(

X

,

Y

)及屏幕右上角(

X

,

Y

)地理坐标:

根据请求数据类型以及在该层级下地理范围对该类型瓦片数据行列号进行转换，并向复合金字塔模型中请求相应数据，将查询到的数据向客户端进行传递。

瓦片金字塔模型中瓦片的生成都是先将栅格数据或矢量数据进行切片，生成瓦片矩阵后再通过分级分块的方式构建多尺度瓦片矩阵集，每张瓦片通过层级与行列号唯一确定。本次研究是对多尺度复合金字塔模型进行研究，具有多种类型瓦片数据，因此做出如下定义:

定义1：多尺度复合金字塔模型包含多种类型数据瓦片金字塔模型，每一张瓦片都可以通过数据类型、层级及行列号唯一确定。TileID代表多尺度复合金字塔模型的瓦片索引值，可以表示为:

TileID=(Type,Layer,Row,Column)

其中，Type表示瓦片数据类型，Layer表示该类型瓦片数据所在层级号，Row表示瓦片在该级下的行号，Column表示瓦片在该级下的列号。为了加快数据定位速度，索引项TileID采用哈希存储。基于多尺度复合金字塔的瓦片索引结构为:

Index=(TileID,Value,Size,Frequency,

LastTime,TimeInterval)

其中，Value表示当前瓦片的价值，Size表示瓦片所占空间的大小，Frequency表示该瓦片的请求频次，LastTime表示瓦片上一次被请求时间，TimeInterval表示瓦片最近两次被请求的时间间隔。

2.2 MCPCR策略

MCPCR策略，当缓存空间已满或达到阈值时，置换出过了保护期限且价值最低的瓦片数据。其中瓦片价值为:

其中，Frequency(a)表示基于用户操作习惯的空间访问频次，TimeInterval(a)表示当前瓦片的历史平均访问间隔，Type(a)表示数据类型权重。

用户在客户端最常用的操作是平移操作和缩放操作。图3所示为瓦片相邻范围示意图。

图3 瓦片相邻范围示意图

当用户操作为平移操作时，可以从上、下、左、右、左上、左下、右上、右下八个方向请求瓦片数据；当用户进行缩放操作时，有放大操作和缩小操作两种情况。放大操作是指向服务器请求当前位置高层级数据；缩小操作是指向服务器请求当前位置低层级数据。也就是说，在某个时间用户访问了瓦片数据，附近的瓦片和相邻级别的瓦片数据在下一次再次被访问的概率更高。故定义瓦片的请求频次Frequency为：

定义2：设Frequency为瓦片请求频次。根据用户操作历史库，分别记录用户操作up、down、left、right、upperLeft、lowerLeft、upperRight、lowerRight、upLayer、nextLayer及操作总次数

T

。当瓦片被命中时，此瓦片Frequency = Frequency+1，缓存中相邻瓦片数据及相邻层级瓦片数据Frequency = Frequency +

t

,其中

t

为用户分别在10个方向上的操作占总操作次数

T

的比例。

Frequency本质上是瓦片的累计访问频率及其相邻范围影响权值的总和。当瓦片被请求时，其相邻瓦片及相邻层级瓦片下一次被请求的概率增加，并根据用户操作习惯将不同方向上的瓦片赋予不同的权重。

通过计算瓦片历史平均间隔实现对瓦片数据命中在时间维度上产生的影响，同时考虑当前访问时间间隔以及历史访问时间间隔。故定义历史平均访问间隔TimeInterval:

定义3:设TimeInterval为历史平均访问间隔，CurrentTime表示当前瓦片访问时间，LastTime表示瓦片上一次访问时间，TimeInterval表示瓦片最近两次被获取的时间间隔，

H

为历史访问权重，

C

为当前访问权重。TimeInterval公式为:TimeInterval=[TimeInterval×

H

+(CurrentTime-LastTime)×

C

]其中，

H

与

C

的和为1，当

H

的越大时，认为历史访问间隔对瓦片请求的影响越大。

由于数据类型多样，针对缓存置换策略的制定需要考虑到数据类型权重，同时考虑到瓦片单个数据大小，对数据类型权重进行定义:

其中，Type(i)表示访问的某一类型数据总和，Type(s)表示访问瓦片全部类型的总数量，并考虑瓦片大小对于缓存置换的影响，单个瓦片数据量越大，影响度越低，当缓存空间已满时，优先置换出数据较大的瓦片。

为了避免在缓存空间已满，新进入的瓦片由于价值最低，下一次置换操作时被移除，引入瓦片保护机制，也就是说，瓦片数据在刚刚进入缓存空间的一段时间内不能被替换。故定义瓦片保护时间ProtectTime:

定义4：设瓦片保护时间为ProtectTime，瓦片数据进入到缓存空间后初始化ProtectTime，进入保护期，并随着时间的增加不断减小，当ProtectTime为0时，保护期结束，瓦片保护时间为ProtectTime=ProtextTime -Time。

其中，Time为当前时间与瓦片进入到缓存空间的时间差。

2.3 MCPCR算法流程

(1)新的瓦片数据进入缓存空间时，需要初始化瓦片信息，包括瓦片类型Type，层级Layer，行列号Row、Column，价值Value以及保护时间ProtectTime；

(2)判断缓存空间能否容纳新瓦片，当缓存空间充足时，将瓦片存储在缓存空间中并执行步骤(3)；当缓存空间不足时，则执行步骤(5)；

(3)将瓦片数据发送至客户端，同时得到该瓦片相邻瓦片数据信息及相邻层级瓦片数据信息，将已经在缓存空间中的瓦片数据执行步骤(4),否则一次性从服务器中获取所有瓦片；

(4)更新缓存中瓦片价值Value；

(5)判断ProtectTime是否为0，若已经为0，说明已经过期，同时不再更新；若不为0，则继续更新；

(6)计算缓存空间中保护机制过期且价值最低的瓦片，按顺序进行移除直至缓存空间充足；

(7)MCP算法结束。

3 实验与分析

3.1 实验环境

实验通过Fiddler采集客户端获取瓦片日志数据，根据获取到的瓦片数据计算用户操作，模拟用户瓦片数据操作记录，共计1 267 154条记录。其中最大的瓦片大小为48.4 KB，最小的瓦片大小为232 B。实验环境为Intel(R) Core i5-8300H @ 2.30 GHz，4核CPU，12 GB内存。根据用户请求记录，获得瓦片的类型、层级、行列号、大小及时间等数据，模拟用户在客户端的行为。

在MCPCR算法中，需要设置历史访问权重

H

以及当前访问权重

C

，通过实验测试，当历史访问权重设置为0.7，当前访问权重设置为0.3时，实验效果较好。实验共由两个部分组成，首先分别选取三种数据类型单独进行实验，第二部分同时选取三种类型数据进行实验，统计缓存空间中的字节命中率及瓦片命中率，并与传统缓存策略FIFO、LRU、LFU进行对比。

3.2 实验结果与分析

将用户请求的日志结果分别设为数据集a、b、c、d，其中数据集a、b、c仅包含单一类型数据，数据集d包含a、b、c数据中三种类型数据。在设置客户端缓存大小为20 M、40 M、60 M、80 M、100 M时，利用FIFO、LRU、LFU、MCPCR四种缓存置换策略进行模拟调度。比较相应的字节命中率及瓦片命中率，图4中(a)、(b)、(c)、(d)分别代表数据集a、b、c、d字节命中率点线图，图5中(a)、(b)、(c)、(d)分别代表数据集a、b、c、d瓦片命中率点线图。

(a)数据集a字节命中率

(a)数据集a瓦片命中率

(d)数据集d瓦片命中率

通过实验可知，在三种不同的数据集下，四种缓存置换策略的命中率都会随着缓存空间大小的增加而逐渐增加，曲线最终趋近于平缓。由四种缓存置换策略进行对比可知，在对单一类型数据加载时，FIFO缓存置换策略命中率最低，LRU缓存策略淘汰最后被访问时间最久的数据，要优于FIFO，LFU缓存置换策略能够避免LRU周期性或者偶发性的操作导致缓存命中率下降的问题，整体优于LRU，MCPCR由于在考虑时间和空间因素的基础上，引入用户操作习惯因素及保护机制，在不同缓存空间大小下的命中率要优于其他三个缓存置换策略。在对不同类型数据进行加载时，传统缓存置换策略命中率下降明显，MCPCR依旧能够保持良好的缓存命中率，通过实验证明，MCPCR策略能够有效支持多种类型数据同时进行缓存，并能够有效提升缓存命中效率。

4 结束语

该文提出了一种多尺度复合金字塔数据组织模型，能够有效地组织和管理不同类型的瓦片数据。基于该模型，设计了瓦片缓存索引。考虑到用户的操作习惯、历史访问对瓦片价值的影响并引入瓦片保护机制，提出了一种基于多尺度复合金字塔模型的缓存替换策略MCPCR。实验结果表明，对同一种瓦片数据类型进行加载时，MCPCR在不同大小的缓存空间中命中率均优于其他几种算法，在对多种类型瓦片数据进行加载时，MCPCR仍然能够保持良好的命中率。可以有效支持不同类型瓦片数据加载，从而提高用户的响应速度。