基于时空老化模型的服务端瓦片缓存置换算法

汤求毅，王超，杜震洪*，张丰，刘仁义

（1.浙江大学浙江省资源与环境信息系统重点实验室，浙江 杭州 310028； 2.浙江大学地理信息科学研究所，浙江杭州 310027）

0 引 言

近年来，随着遥感影像数据量的快速增长，网络地理信息服务（network geographic information service，NGIS）逐渐向云服务发展［1-3］，进一步促使NGIS 提供高效实时的遥感影像预览、可视化及漫游服务。由于遥感影像单幅数据量过大，不适合在网络中频繁传输，在实际应用中往往用瓦片实现可视化［4］，因此，高效、实时的瓦片服务是支撑高性能NGIS 的基础技术之一。然而，数据量和用户量的激增，导致瓦片服务器服务过载，造成瓦片服务的延迟与低效［4-5］。瓦片缓存可以减少对瓦片服务器直接访问的频率，减轻瓦片服务器的压力。目前，瓦片缓存架构主要分为客户端缓存和服务端缓存2 种，由于前者在云环境下存在应用局限性［6］，Google Earth 建议使用服务端缓存解决瓦片服务延迟的问题［7］。良好的缓存置换算法可以有效提高缓存命中率［5，8］，进一步减轻瓦片服务器压力，因此，设计高命中率的瓦片缓存置换算法成为当前研究的热点和难点［9］。

瓦片缓存置换算法的设计需要考虑瓦片访问模式和瓦片数据特征［10］。瓦片数据在访问模式上存在短期流行度和长期流行度［7，11-12］，能反映瓦片的访问趋势。短期流行度可通过瓦片访问的时间局部性和空间局部性进行表达［13］。时间局部性是指近期被访问过的瓦片被再次访问的概率更高，空间局部性是指与当前被访问瓦片相邻的瓦片被访问的概率更高，时间局部性和空间局部性相互关联、相互影响，对外统一表现为时间局部性［7，11］。长期流行度可通过瓦片访问热度，即瓦片的累计访问频次表达［4，14-15］，热度值高的瓦片被再次访问的概率更高［4］。瓦片数据特征包含瓦片大小特征、瓦片主题特征等，瓦片大小特征是指不同的瓦片存在大小差异。由于缓存过程中大文件越多，缓存命中率越低［16］，因此瓦片大小特征也是不可忽略的因素。

国内外学者基于瓦片访问模式和瓦片数据特征，对瓦片缓存置换算法开展了大量研究。LEE等［17］提出了基于马尔可夫链的瓦片缓存预取和置换算法，通过置入预取概率高的瓦片，置换出转移概率低的瓦片。王浩等［14］提出了基于瓦片存活寿命和访问热度的缓存置换算法，通过计算瓦片平均存活时间得到瓦片年龄，并置换出年龄最高的瓦片缓存。涂振发等［18］提出了基于瓦片数据价值的缓存置换算法，综合考虑时间价值、空间价值和数据大小价值对瓦片数据价值进行定义，并置换出价值最小的瓦片缓存。ULUAT 等［19］基于模糊逻辑的推理引擎，提出了一种基于优先级的瓦片预测方法。LI等［20］对用户进行分组，研究了基于不同用户组访问密集性的瓦片缓存置换算法。刘佳星等［15］利用瓦片金字塔特性，提出了基于地理单元热度的瓦片缓存置换算法。这些算法结合时空特性定义了各自瓦片价值模型，并根据价值大小置换瓦片，在一定程度上提高了缓存命中率［4］。但这些算法在应用于服务端瓦片缓存时还存在以下问题：（1）相较于传统的缓存置换算法，上述算法的复杂性高、效率低，不适合大量瓦片缓存置换的应用场景；（2）大多数为客户端缓存置换算法，不适合基于网络的服务端瓦片缓存置换场景；（3）重点分析了瓦片访问对水平相邻瓦片的影响，未考虑对其上下层瓦片的影响；（4）未考虑瓦片大小差异对缓存命中率的影响。

老化算法原本用于页面缓存置换，同时具备最近最少使用（least recently used，LRU）和最不经常使用（least frequently used，LFU）2 种算法的优点，在短期流行度拟合和运行性能方面具备优势，且具扩展性和移植性［21-22］。本文将老化算法引入服务端瓦片缓存置换场景，综合瓦片访问的长短期流行度和瓦片大小特征对老化算法进行改造，提出时空老化模型，并设计了基于时空老化模型的服务端瓦片缓存置换算法（server-side cache replacement algorithm based on spatiotemporal aging model for tiles，SSAT），具有以下优势：（1）运行效率高，适用于大量瓦片缓存置换场景；（2）可更好地拟合瓦片访问的时间局部性；（3）兼顾瓦片访问对水平和垂直2 个空间维度的影响，更全面地体现其空间局部性；（4）顾及瓦片大小特征，进一步提高瓦片缓存命中率。

1 基于时空老化模型的服务端瓦片缓存置换算法

1.1 老化算法

老化算法是一种操作系统页面缓存置换算法［22］，其数据结构和工作流程如图1 所示。R 位用于标记页面在时钟周期内的引用情况，若页面被引用，则将R 位设置为1，若页面进入新的时钟周期，则将R 位设置为0。计数器C 用于记录页面在各时钟周期内的访问情况，值越大，表示该页面被访问时间间隔越短［23］。计数器的长度一般取决于处理器的位数，老化表是所有计数器的集合。

假设缓存中有页面P1、P2和P3。在初始时刻，3个页面的R 位和计数器C 均为0。假设在时钟周期T1内，只有P1和P3被引用，则需将R1和R3设置为1。当时钟从T1进入T2时，先如图1 中黄色箭头所示，将所有计数器C1、C2、C3右移一位，接着如图1 中绿色箭头所示，将R1、R2、R3分别设置为计数器的最高位，最后将R1、R2、R3重新设置为0。算法在时钟周期T3、T4、T5内的操作过程相同。

图1 老化算法工作流程Fig.1 Aging algorithm workflow

当内存不足时，老化算法会根据计数器C 的大小置换页面［23］。C 越大，其高位为1 的概率越大，表明其被访问的时间间隔越短。假设在T5内需要进行缓存置换，算法会根据计数器C1、C2、C3的大小，找出最小值C2，并置换出其对应页面的P2缓存。老化算法的优点是，最新引用的页面比频繁引用的页面具有更高的优先级［24］。

页面缓存置换算法只需要考虑时间局部性［22］，而瓦片数据有空间局部性和大小差异，因此在应用时需要对老化算法进行扩展。

1.2 时空老化模型

时空老化模型以老化算法的计数器周期性移位为基准，综合考虑瓦片访问长短期流行度和瓦片大小，并将其作为比重进行调节，得到瓦片时空老化程度，记为V（ssat）。当缓存空间不足时，SSAT 会置换出V（ssat）最低的瓦片缓存。时空老化模型的表达式为

V（ssat）=V（age）≫（V（heat）+V（size）），（1）其中，≫为右移运算符，V（age）为瓦片时间老化程度，V（heat）为瓦片空间访问热度价值，V（size）为瓦片大小价值。V（heat）和V（size）通过影响V（age）右移的方式参与调节。

1.2.1 瓦片时间老化程度

老化算法在原理上利用了时间局部性［24］，因此直接用老化表计数器值表示瓦片访问的短期流行度，定义如下：

定义1 瓦片老化表。每张瓦片各自对应一个32 位的计数器，瓦片老化表是计数器的集合。

定义2 瓦片老化时钟周期。与老化算法的时钟周期相对应，记为T。每经过时间T，瓦片老化表中每个计数器的值右移一位。

定义3 瓦片时间老化程度。可用计数器的值表示，值越小，表示瓦片时间老化程度越高。

1.2.2 瓦片空间访问热度价值

空间位置相邻的瓦片，在访问时间上也倾向于相邻瓦片。正确定义单张瓦片影响的邻域空间范围，是提高瓦片缓存命中率的关键。因此，定义如下：

定义4 瓦片水平邻域。以被访问的瓦片为中心，在同层中与该瓦片直接相邻的8 张瓦片。

定义5 瓦片垂直邻域。在下一层级中，由被访问的瓦片分裂得到的4 张瓦片。

定义6 瓦片空间访问热度权重。由于瓦片访问存在空间局部性，瓦片空间访问热度权重表示被访问瓦片对其水平邻域和垂直邻域的影响程度，记为vol。

定义7 瓦片空间访问热度。可用瓦片的累计被访问频次表示，记为heat。当瓦片被访问命中后，每增加1 heat，其水平邻域和垂直邻域中的瓦片heat增加vol，计算过程如图2 所示。

图2 瓦片水平邻域和瓦片垂直邻域Fig.2 Tile horizontal neighborhood and vertical neighborhood

定义8 瓦片空间访问热度价值。由瓦片空间访问热度进行归一化处理得到。在调节V（age）的过程中，heat 不同的瓦片之间应体现出适当的差距，因此，定义V（heat）：

其中，maxHeat 为缓存中最大的瓦片空间访问热度，Me 为缓存中所有heat 的中位数。设置Me 是为了避免当heat 与maxHeat 相差较大时，对V（age）产生过大的移位影响。假设缓存中有3 张瓦片A，B和C，其heat 分别为1 000，500 和10，缓存中maxHeat 为10 000，Me 为100。 此时瓦片A 的V（heat）≈3，瓦片B 的V（heat）≈4，在时空老化模型中，瓦片A 将影响V（age）右移3 位，瓦片B 将影响V（age）右移4 位，即heat 值相差2 倍的瓦片，相当于一个瓦片时钟周期没有被访问。而瓦片C 的heat 与maxHeat 相差1 000 倍，若直接用heat 计算，将得到V（heat）≈9，这对于32 位的V（age）来说，产生的移位影响过大，会造成V（age）信息丢失。若取heat=Me，则得到V（heat）≈6，这既体现了差距，又避免了对V（age）信息产生移位污染。总的来说，V（heat）的计算方式可以满足应用需求。

1.2.3 瓦片大小价值

遥感影像金字塔瓦片的大小可能相差近百倍，如果小瓦片拥有更高的优先级，则会提高瓦片缓存命中率［22］。将不同大小的瓦片所对应的优先级称为瓦片大小价值，记为V（size）。与V（heat）的作用类似，V（size）也是以移位的形式对老化表计数器进行调节。在调节过程中，大小不同的瓦片之间应该体现出适当的差距。定义V（size）为

1.3 基于老化算法的服务端瓦片缓存索引

在运行过程中，缓存服务器可逐渐保存大量瓦片。当客户端的请求到达缓存服务器时，需要高效的索引机制，检索其是否存在目标瓦片。根据瓦片服务的统一资源定位符（uniform resource locator，URL）规则，参照老化算法原理设计了一种以瓦片为粒度的缓存索引方法，如图3 所示。

图3 服务端瓦片缓存索引结构Fig.3 Server-side tile cache index structure

该索引方法基于键值对的哈希索引结构，对URL 中的level、row 和col 进行CityHash64 编码，将得到的64 位散列值作为哈希键（HashKey），对应的哈希值（HashValue）包括瓦片信息（tileNode）、R 位（referenceBit）、计数器（counter）、空间访问热度值（tileSpatailHeat）和瓦片大小（size）。

1.4 SSAT 流程

SSAT 在执行过程中需要陆续启动一个程序主线程和2 个工作线程。程序主线程随缓存服务器的启动而启动，负责初始化算法运行环境。工作线程包括定时器线程和瓦片请求响应线程，定时器线程主要负责瓦片老化表周期性移位；瓦片请求响应线程主要负责处理客户端的瓦片访问请求、查询瓦片缓存以及置入、换出瓦片等，步骤如下。

（1）启动瓦片缓存服务器主程序，建立缓存索引和瓦片老化表，设置瓦片老化时钟周期T，创建定时器线程，监听用户请求；

（2）执行定时器线程周期，每经过一个T，先将所有计数器的值右移一位，再将瓦片的R 位置于计数器的最高位，最后将所有的R 位清零；

（3）当收到瓦片请求时，瓦片请求响应线程启动，对URL 的level、row、col 进行编码，并通过编码值查找缓存索引，若命中，则转至步骤（6），否则，转至步骤（4）；

（4）根据level、row、col 信息，从磁盘上读取目标瓦片，同时返回请求；

（5）判断缓存剩余空间是否充足，若充足，则将命中的瓦片直接放入缓存，创建索引，然后转至步骤（6）；否则，转至步骤（7）；

（6）将命中瓦片的R 位设置为1，空间访问热度值增加1，同时将缓存中存在的该瓦片水平邻域和垂直邻域中其他瓦片的空间访问热度值增加vol；

（7）当缓存空间不足时，先按照时空老化模型计算每个瓦片的V（ssat），再置换V（ssat）最小的瓦片，删除缓存索引，直至空间充足。

2 实验与分析

2.1 实验环境与实验过程

实验数据为谷歌地图瓦片，整套瓦片共21 层（最高为0 层，最低为20 层），共6 077 501 张、6.84 GB，其中最大的瓦片为1 492 KB，最小的瓦片为6 KB。实验使用了3 台配置为Windows Server 2012 操作系统，Intel（R）Core（TM）i7-8750H CPU @2.2 GHz，512 GB SSD 和8 GB RAM 的服务器。

实验过程遵循控制变量法，（1）设置最大可用缓存空间为500 MB，并以50 MB 为间隔设置10 个不同的缓存空间；（2）不使用缓存直接访问瓦片服务，生成152 841 条瓦片请求日志，提取日志中的瓦片层级、行列号和请求时间，生成瓦片访问次序列表；（3）按照列表顺序，依次访问瓦片缓存服务，统计总访问次数、请求命中次数、访问时长等信息。

2.2 实验结果与分析

在SSAT 中，需要设置瓦片时钟周期T和瓦片空间访问热度权重vol。本文在缓存空间为500 MB的条件下进行实验，分别记录了T和vol 对缓存命中率的影响，结果如图4 所示。由图4（a）可知，SSAT的缓存命中率随T的增大呈现先减小后保持不变的特征，其主要原因是，T增大，表示老化表周期性移位的时间间隔增大，进而造成瓦片在单个时钟周期内被访问的概率增加。由于R 位仅能表示某个周期内瓦片是否被访问，无法表示瓦片被访问频次，T增大会使各瓦片在V（age）上的差异减小，因此缓存命中率减小。当T＞45 s 时，V（age）不再是主要影响因子，因此，缓存命中率不随T的变化而变化。

由图4（b）可知，SSAT 的缓存命中率随vol 的增大呈现先增大后减小的特征，其主要原因是，瓦片访问会使目标瓦片空间访问热度增加，当vol＜0.3 时，瓦片访问命中对周围瓦片的影响较小，V（heat）不会对V（age）产生有效的移位影响，因此缓存命中率较低且变化不明显；随着vol 的增大，瓦片访问命中对周围瓦片的影响增大，V（heat）对V（age）产生有效的移位影响，因此缓存命中率不断增大；当vol＞1时，访问命中使周围瓦片获得的热度大于被命中瓦片自身获得的热度，V（heat）对V（age）产生的移位影响过大，因此缓存命中率不断减小。

图4 瓦片时钟周期和瓦片空间访问热度权重值对SSAT 缓存命中率的影响Fig.4 Impact of T and vol on cache hit ratio of SSAT

综合实验结果，当T=10 s，vol=1 时，请求命中率和字节命中率最高，因此，选择该组合值作为SSAT 算法的实验参数。

图5 展示了在同时设置V（heat）和V（size）、仅设置V（heat）、仅设置V（size）3 个条件下，SSAT 的请求命中率和字节命中率随缓存空间的变化。可知，随着缓存空间的增大，SSAT 在3 种条件下的请求命中率和字节命中率均不断增大，且增长趋势大致相同。在不同的缓存空间中，同时设置V（heat）和V（size）的SSAT 所得请求命中率和字节命中率最大；仅设置V（heat）的SSAT 所得请求命中率和字节命中率下降约22%；仅设置V（size）的SSAT所得请求命中率和字节命中率下降约43%。结果表明，瓦片空间访问热度价值和瓦片大小价值能有效提高SSAT 的缓存命中率。

图5 在3 种条件下SSAT 的请求命中率和字节命中率随缓存空间的变化Fig.5 Changes of request hit ratio and byte hit ratio of SAAT with cache space under three conditions

图6（a）和（b）分别为SSAT、LRU、LFU、先进先出（first in first out，FIFO）4 种算法的请求命中率和字节命中率随缓存空间的变化。可知，当缓存空间为100 MB 时，4 种算法均表现出小于7%的请求命中率和小于10% 的字节命中率。当缓存空间为500 MB 时，4 种算法的缓存命中率显著提高，其中请求命中率分别为73%，65%，55%和44%，字节命中率分别为76%，66%，56%和47%。图6（c）和（d）分别为4 种算法在不同缓存空间下的请求命中增长率和字节命中增长率。当缓存空间小于100 MB时，4 种算法的请求命中增长率和字节命中增长率均较低，其中SSAT 每MB 的请求命中增长率和字节命中增长率分别为0.06%和0.07%。在缓存空间为100～300 MB 时，4 种算法每MB 的请求命中率和字节命中率迅速增加，命中增长率均大于0.15%，其中SSAT 的请求命中增长率和字节命中增长率每MB 分别达0.24%和0.23%。当缓存空间为300～500 MB 时，缓存空间对命中增长率的影响降低，因此4 种算法每MB 的命中增长率再次趋于平缓，平均降至0.05% 左右。总的来说，在不同缓存空间下，SSAT 的缓存命中率及命中增长率均最高，且随缓存空间的增大缓存命中率优势更加显著。

图6 4 种算法的缓存命中率及命中增长率随缓存空间的变化Fig.6 Changes of tile request hit ratio，tile byte hit ratio and their growth of four algorithms with cache space

瓦片平均访问时长和平均访问时长节省率可以直观地体现瓦片服务的性能。平均访问时长越短，平均访问时长节省率越高，则访问延迟率越低。图7 为4 种算法在不同缓存空间下的瓦片平均访问时长及其节省率，可知，4 种算法的平均访问时长随缓存空间的增大而减小，平均访问时长节省率随缓存空间的增大而增大。当缓存空间大于300 MB 时，缓存置换算法可有效缩短瓦片请求的平均访问时长，降低延迟率，且SSAT 的延迟率最低。

图7 4 种算法的平均访问时长和平均访问时长节省率随缓存空间的变化Fig.7 Change of average visit time and save ratio of average visit time of four algorithms with cache space

瓦片缓存置换算法为NGIS 带来了更高效的瓦片服务，但同时也会提高CPU 占用率。图8 展示了当缓存空间为500 MB 时4 种算法的CPU 占用率及累计占用率的统计结果。可知，4 种算法的CPU 占用率从大到小依次为LRU，SSAT，LFU 和FIFO。LRU 有良好的缓存命中率，但资源消耗过大；FIFO占用的CPU 资源最小，但缓存命中率过低；LFU 和SSAT 的资源消耗适中，但LFU 的缓存命中率远低于SSAT；SSAT 能兼顾性能和资源消耗，是一种良好的服务端瓦片缓存置换算法。

图8 4 种算法的CPU 占用率和累计占用率Fig.8 CPU usage ratio and sum usage ratio of four algorithms

3 结 论

综合分析了瓦片访问的时空局部性、长短期流行度和瓦片大小特征，将老化算法引入NGIS，提出了基于时空老化模型的服务端瓦片缓存置换算法（SSAT），并进行仿真实验。结果表明，相较于传统算法，SSAT 能显著提高瓦片请求命中率和字节命中率，缩短平均访问时长，且能兼顾对计算机资源的消耗，是一种较有效的瓦片缓存置换算法。

SSAT 仍有待优化。首先，本实验是在单机上进行的，如何将SSAT 扩展为分布式缓存置换算法，令其在多节点、多副本的场景下保持良好性能，进一步提高遥感影像的共享能力是未来重点关注的研究方向。此外，除瓦片大小特征外，瓦片数据特征还包括瓦片类型特征和瓦片格式特征等多种信息，未来将从多个维度分析瓦片数据特征对缓存命中率的影响，为高性能地理信息服务提供更全面的理论支撑。