0 概述

边缘计算是一种将计算资源和服务部署在网络边缘的计算节点或智能终端设备上的分布式计算方法^[1]，相较于云计算，边缘计算可以为用户提供更低延迟的服务，在未来的网络发展中将发挥重要的作用。边缘存储技术是边缘计算中的一个重要研究课题，其核心在于边缘网络合理分配存储资源，从而更好地降低用户请求或节点请求的计算时延。

目前，边缘存储按照存储位置的不同可以分为基站存储^[2]和移动设备存储^[3]，其中，由于基站的容量和存储性能高于异构的移动存储设备，因此对基站存储进行研究更具实用价值。在基站存储策略中，现有的研究方案分为协同式和非协同式两类^[4]。

在非协同式的存储策略中，各个存储节点独立地根据收到的请求来存储和调配资源，无需和其他基站进行互动和信息传递。非协同式的存储策略包含基于用户偏好^[5]、基于马尔科夫过程^[6]、基于增强学习^[7]等单点存储策略，它们可以很好地降低时延和传输代价，但是由于信息不共享，各个节点的相同资源副本数量在全局上不可控，对于一些热点内容，其爆炸式增长的副本数量会带来严峻的一致性问题，而一致性问题所引起的时延开销将严重影响用户体验质量。

协同式的存储策略利用基站之间的信息传递，通过合作提供对外服务。文献[8]利用基站间的协同作用，当一个基站缺少内容资源时，会向最近的拥有该内容的基站发出请求，从而降低该基站向云计算中心的请求次数以及总请求延迟，但是，在面临热点问题时，由于热点资源的存储位置对各个存储节点透明，导致整个网络的副本数量依旧不可控，该策略在一致性问题上与非协同策略具有相同的局限性。文献[9-10]分别提出基站间的协同策略，但它们未明确副本管理方法，如果采用中心化的管理方式，副本在各个节点中的存储与删除将大幅提升中心节点的计算压力。此外，除了传统IP寻址，边缘网络中也会包含一些命名对象寻址方式^[11]，如NDN（Named Data Networking）^[12]的命名方式，这为副本管理带来了更多的挑战。因此，现有的存储策略在解决副本一致性问题上都存在不足，在实际应用场景中，一致性问题会带来不可忽视的时延和影响。

本文提出一种基于虚拟传播树（Virtual Spread Tree，VST）的去中心化边缘存储算法，以解决热点资源存储中的多副本一致性问题，保证用户的请求时延可控，同时维护资源的一致性。该算法建立和剪枝VST，限制树的增长，通过贪心的淘汰算法逐渐找到近似最优的资源存储节点。算法中的最大延迟低于两倍树深的传播时间，避免了其他算法中的副本爆炸式增长问题。各个节点只存储少量相邻数据，去中心化的方法能够降低存储和计算开销。此外，各个节点的淘汰算法相互独立，从而进一步降低时间开销。

1 相关知识 1.1 基站存储模型与本文假设

基站存储模型可以通过如下数学模型进行描述：图$ G=(V, U, E) $表示边缘存储网络，其中，$ V=\{{v}_{1}, {v}_{2}, \cdots , {v}_{n}\} $表示基站存储节点，$ U=\{{u}_{1}, {u}_{2}, \cdots , {u}_{m}\} $表示用户节点，$ E=\left\{\right(x, y\left)\right|x\in V, y\in V\bigcup U\} $表示基站和基站之间以及基站与用户节点之间的距离，资源内容用$ I=\{{i}_{1}, {i}_{2}, \cdots , {i}_{k}\} $表示，每个基站$ {v}_{j} $存储的资源$ {I}_{j}\left(t\right)\subset I $随时间发生变化，所有的$ {I}_{j}\left(t\right) $构成资源存储策略。基站存储模型结构如图 1所示。

本文进行如下假设：

1）基站与基站以及基站与用户节点之间的传输时延与节点间的距离成正比。

2）基站之间采用协同式工作策略，即$ t $时刻用户节点$ u $总是向最近的基站$ {v}_{j} $请求资源$ {i}_{s} $，当$ {i}_{s}\notin {I}_{j}\left(t\right) $时，$ {v}_{j} $会向周围基站节点进行资源请求，直至找到最近的拥有资源$ {i}_{s} $的节点$ {v}_{i} $，并将资源返回给用户。

3）各个基站的存储空间足够大，除非主动删除，否则资源$ i $在存储到某个基站$ {v}_{j} $后将会一直保留。

1.2 分布式存储一致性

分布式存储的一致性模型可以分为两类^[13]：一类是面向数据的一致性模型，包括顺序一致性^[14]、因果一致性^[15]和线性一致性^[16]等，它们从并发进程的角度来分析进程读写的执行顺序，从而划分不同的一致性等级；另一类是面向客户的一致性模型，包括最终一致性、读写一致性和写读一致性等，它们是描述客户对同一内容进行多次读写操作的一致性模型。

上述模型在理论上对一致性问题进行了系统分析，但是在实际应用中，较为常用的保证副本一致性的算法通常是Paxos^[17]及改进的节点协同算法，如Raft^[18]算法等，它们通过存储节点之间的选举策略和消息传递方式，从而保证各个副本的执行方式相同，即保证副本的一致性。在边缘基站存储中可以使用上述一致性算法，但相较于云分布式存储方式而言，边缘存储中各个副本节点的位置并不固定，且副本数量可能在频繁变化，导致Paxos算法很难执行。因此，需要通过扩散的方式来将一致性信息传递给各个存储节点，而此时副本数量和扩散深度会影响各个副本达到一致性的时间，为了提高用户获得资源的准确性，需要牺牲一定时间的可用性，这段时间便是一致性传播时延。为了更好地提高用户体验质量，需要控制一致性恢复过程中的时延。

2 基于虚拟传播树的边缘存储算法 2.1 虚拟传播树结构

VST从全局来看是一棵K叉树，点集$ {V}_{T}\subset V $，边集$ {E}_{T}\subset E $，对于任意的资源内容$ i $，有且只有一棵$ \mathrm{V}\mathrm{S}{\mathrm{T}}_{i} $与之对应，$ \mathrm{V}\mathrm{S}{\mathrm{T}}_{i} $的节点表示当前时刻K所有拥有资源$ i $的基站存储节点。VST本身是抽象的，任何节点都不存储完整的VST数据结构，每个VST节点只保存其父节点和子节点信息以及一些与资源$ i $相关的访问次数、最近访问时间等少量统计数据信息，额外的存储开销远小于存储整棵VST的开销。VST结构以及VST节点的元数据结构伪代码如图 2所示。

2.2 VST生成算法

VST的生成是由用户对资源的请求而驱动的，当基站$ {v}_{i} $收到一个资源$ {i}_{s} $的请求时，若当前节点没有存储资源$ {i}_{s} $，则会向周围基站节点扩散寻找（若超过一定时间没有找到，会向云存储中心直接请求），直至找到最近的存储该资源的基站节点$ {v}_{j} $，此时$ {v}_{i} $和$ {v}_{j} $建立父子关系，$ {v}_{j} $是$ {v}_{i} $的父节点，同时保存两者之间的传输距离（延迟），并且$ {v}_{i} $从$ {v}_{j} $处复制资源$ {i}_{s} $。以此类推，建立一棵传播树，同时，为了避免节点拥有的子节点个数过多，从而产生额外的查询和存储开销，当父节点的子节点数目达到阈值K时，会隐藏自己拥有资源$ {i}_{s} $的特征，从而保证VST是一棵K叉树。VST生成算法流程如图 3所示。

2.3 VST节点淘汰算法

VST生成算法并不能保证VST树深的稳定，对于热点资源，VST的规模极为庞大，因此，需要相应的节点淘汰算法，简单且有效的方式是将最近访问频率最低的节点删除，但是这对树深的影响不可直接度量。本文采用如下方法进行节点淘汰：当新节点$ {v}_{0} $作为叶子节点插入VST时，若树深刚好超过阈值D，则对从该叶子节点到VST根节点的路径$ ({v}_{0}^{1}, {v}_{0}^{2}, \cdots , {v}_{0}^{l}) $上的每个节点$ {v}_{0}^{j} $分别计算一个保留值$ {Q}_{j} $，计算公式如下：

$ {Q}_{j}^{\left(1\right)}=\frac{2}{1+{\mathrm{e}}^{-n}}-1 $

(1)

$ {Q}_{j}^{\left(2\right)}=\frac{1}{1+{\mathrm{e}}^{-\left(d\right({v}_{0}^{j}, {v}_{0}^{j-1})-{d}_{\mathrm{a}\mathrm{v}\mathrm{g}})}} $

(2)

$ {Q}_{j}=\alpha {Q}_{j}^{\left(1\right)}+(1-\alpha ){Q}_{j}^{\left(2\right)} $

(3)

式（1）中的$ n $为最近一段时间内该节点的被访问次数，$ n $越大，该节点越应该被保留。式（2）中的$ d({v}_{0}^{j}, {v}_{0}^{j-1}) $表示$ {v}_{0}^{j} $和$ {v}_{0}^{j-1} $之间的延迟，$ {d}_{\mathrm{a}\mathrm{v}\mathrm{g}} $表示$ {v}_{0}^{j} $到其父、子节点的平均延迟，$ d({v}_{0}^{j}, {v}_{0}^{j-1}) $越高，说明该节点越不能被其下游节点替换。式（3）中的$ \alpha $是平衡系数，通常取值为0.5。

淘汰保留值最低的节点$ {v}_{0}^{k} $，用其路径上的下游子节点$ {v}_{0}^{k-1} $代替$ {v}_{0}^{k} $，从而减小树深。节点淘汰算法描述如下：

算法1  VST节点淘汰算法

输入  初始的VST树VST_in，新插入节点v₀，树深阈值D

输出  淘汰节点后的VST树VST_out

1.Initialize d=depth（v₀，v_root）；

/*depth（v₀，v_root）表示叶子节点v₀到根节点v_root的深度*/

2.if d≤D then

3.path=（v$ {}_{0}^{1} $，v$ {}_{0}^{2} $，…，v$ {}_{0}^{\mathrm{l}} $）

for v$ {}_{0}^{\mathrm{j}} $ ∈ path do

4.计算Q$ {}_{0}^{\mathrm{j}} $/*根据式（1）~式（3）*/

5.end for

6.v$ {}_{0}^{\mathrm{k}} $=argmin（Q$ {}_{0}^{\mathrm{j}} $）/*获得Q值最小的节点*/

7.删除v$ {}_{0}^{\mathrm{k}} $，并用v$ {}_{0}^{\mathrm{k}-1} $代替

输出VST_out

8.else

9.VST_out=VST_in

10.end

2.4 一致性边缘存储策略

结合VST的特性，可以设计一种解决边缘存储一致性问题的存储策略。在边缘存储已建立最大深度为D的VST后，当某个节点触发写操作，需要将更新传播到全部副本节点时，将执行一致性边缘存储策略。

由于边缘网络环境下各个副本位置的不可控，传统的Paxos等一致性算法难以直接应用，本文通过锁定服务和传播更新信息的方式实现一致性共识，从而保证用户的读写一致性。

在节点发生写操作时，系统会迅速地对存储资源进行加锁操作以锁定服务，并将相应的更新信息沿着VST的路径向父节点和子节点进行传播，由于VST树深不超过D，则传播完整棵树的时长不超过2D，平均时长为1.5D，从锁定服务到最终传播更新的时间是可控的。此外，可以通过边传播边解锁服务的方式，使得节点完成更新时就可以接收资源请求。

上述过程是在传统IP网络寻址方式的基础上进行的，但是边缘存储中可能存在信息中心网络（ICN）^[19]等特殊命名方式的网络部署，因此，在这种场景下需要对算法进行一定的改进。本文针对拥有层次解析的ICN网络场景，对所提基于VST的去中心化边缘存储算法进行改进，如图 4所示。

解析节点可以解析当前容器内所有点的位置，但副本资源存储节点可以跨容器，本文所提基于VST的去中心化边缘存储算法建立在最底层的解析容器中，针对ICN场景的改进算法包括以下3个步骤：

1）节点A发起副本一致性请求，A向其所在的解析容器中的解析节点B以及A的VST父、子节点发送信息。

2）B解析出当前容器内的副本位置，下发一致性信息。

3）所有收到一致性信息的节点将自己视作A，重复上述2个步骤，直至所有副本节点收到一致性信息。

通过容器内的解析扩散和容器间的VST扩散，系统延迟时间将进一步降低。

3 实验结果与分析

为验证VST的有效性，本文搭建相应的仿真系统，模拟基站和用户间的资源访问关系。如图 5所示，按照热点资源在时间上遵循Zipf ^[20]分布的特征搭建多副本场景。为了验证本文算法的普适性，在一致性场景和非一致性场景下分别进行相应的实验，并重点分析请求延迟和存储开销等性能。实验过程中VST算法的参数设置如表 1所示。

3.1 不考虑一致性的仿真实验

在不考虑一致性的前提下，对比协同式（CV）和非协同式（NCV）的基站存储算法以及本文算法（VST）在时延、存储空间等方面的性能，结果如图 6所示。

从图 6可以看出：随着副本数量的增加，在平均时延方面，VST算法和CV算法表现基本一致，优于NCV算法；在存储开销方面，VST算法的存储开销远小于CV算法。综上，在不考虑一致性的场景中，VST算法稳定且性能良好。

3.2 考虑一致性的仿真实验

为了考虑一致性问题，实验过程中需要添加部分对副本的写操作，并且直至所有副本都更新写操作后才可以响应用户请求，因此，需要观察副本数量和写操作频率对用户请求时延的影响。图 7所示为副本数量分别为20、50和150情况下，在不同写操作频率时用户获取准确内容的时延情况。

从图 7可以看出，在副本数量固定时，随着写操作的频繁发生，CV算法与NCV算法的时延逐渐升高，最终会出现时延过高而无法响应用户请求的情况，尤其在副本数量为150时情况尤为严重。而本文VST算法的时延虽然也会随着写操作频率的升高而升高，但由于其树深稳定，延迟时间将逐渐趋于平稳，在副本数量很大时，VST算法仍然可以响应高频写场景的用户请求，保证用户获取资源的一致性。

4 结束语

本文提出一种基于VST的边缘协同式基站存储算法，以解决边缘网络热点资源请求所带来的多副本不一致性问题，优化用户响应延迟。实验结果表明，在不考虑一致性的仿真场景中，与主流的协同式算法及非协同式算法相比，该算法在时延与存储开销上性能表现更优，在考虑一致性的仿真场景中，该算法的存储性能明显优于其他2种算法，在多副本高频写场景中，本文算法仍然可以提供良好的一致性服务。下一步考虑将本文算法与边缘存储策略相结合，从而为用户提供更好的边缘存储服务。