边缘计算的存储服务

摘要

随着公共云解决方案的日益普及，通常的趋势是创建新应用程序或将现有应用程序迁移到此环境中。分布式系统也是这一变革的一部分。当机器的计算和存储资源不成问题时，这种范式非常有用。由于最大的云服务提供商提供了多种解决方案，只要客户为使用资源所消耗的时间付费，这些就不再成为障碍。另一方面，有一类新型设备连接到互联网，它们存在于人们的日常生活中。这些设备不具备公共云同等数量的资源，但通过协同工作，它们能够提供比公共云更快、更贴近用户的服务。该网络及其提供的服务构成了边缘云。本文提出一种在边缘设备上运行的分布式去中心化存储服务，以优化资源利用。通过利用这些设备的计算和存储资源，可以减少满足相同需求的公共云解决方案的开支。

CCS概念

• 分布式系统 → 资源管理; 存储服务；
• 分布式系统组织 → 边缘计算；
• 网络 → 网络优化；

关键词

分布式系统，边缘计算，存储服务，复制

1 引言

由于当今应用程序的复杂性不断增加，分布式系统的使用范围也越来越广。根据安德鲁·S·塔能鲍姆和马尔滕·范·斯廷[17]的观点，分布式系统是一组具有独立计算和存储资源的机器，它们协同工作并对用户表现为一个单一连贯系统。这类系统最重要的要求是机器之间必须互连，以便相互传递消息[1]。这些消息用于连接节点之间的协调、配置发现和数据传输。

大多数情况下，这些系统在所使用的机器上需要大量资源，例如大数据应用，如分析应用。由于对具有强大计算和存储资源的机器的需求，投资公共云的想法应运而生。该环境旨在提供所有所需资源，而无需在硬件设备上进行初期投资。因此，只要向云服务提供商支付使用资源所产生的费用，所需的资源即可获得。这笔费用远低于维护本地数据中心自有硬件所需的成本。因此，公共云正变得越来越流行，从基础用户到企业公司都在广泛采用[7]。

还存在另一种设备，它们存在于日常生活中，且资源非常有限。这些设备在人们的生活中极为常见，以至于大多数时候人们并未注意到它们，例如智能电视、机顶盒、智能摄像头、传感器、智能微波炉或智能手表。它们都连接到互联网，被称为物联网（IoT）设备[10]。这些设备能够独立地收集和处理大量数据。

分布式系统范式也可以应用于这些物联网设备。它们无需浪费未使用的资源或将大量数据发送到公共云进行计算或存储，而是可以协同工作，与网络中的所有其他设备共享其 CPU 或内存。这种在数据收集地附近处理数据的分布式系统被称为雾计算和边缘计算[8]。

物联网设备收集的所有数据通常需要由网络中的所有设备共享，以便每个设备都能轻松访问，例如一些图片。此外，这类应用程序需要存储服务的原因在于它们具有特殊的需求和特点，例如低延迟、数据本地化或地理参考。

主要处理时空数据。其整体目标是通过利用这些设备未使用的存储资源，最大限度地发挥这些设备的潜力，而不是在公共云上为同类服务花费资金。该服务的主要功能是向网络中的任何主机插入文件以及从其中检索任何文件。

提出方案是一种运行在此类设备上的分布式去中心化存储服务。该服务将运行在多个边缘节点上，这些节点在架构、操作系统或文件系统方面具有不同的配置。用户通过通用 API 与存储服务进行交互，该 API 可从属于此服务的任何主机访问。该系统中各节点之间的通信通过无线网络完成。文件必须被划分为数据块，然后在多个设备之间共享，以确保冗余和容错能力。该提出方案遵循此前在 ACM 应用计算研讨会最近几届会议上发表的研究成果[2, 6, 12]。

本文的结构如下。引言部分简要概述了问题领域。相关工作部分分析了公共云、雾计算和边缘计算层现有技术的当前状态，并更好地概述了位于网络边缘的物联网设备与云数据中心中的物联网设备之间的主要差异。接着，对现有的分布式存储解决方案进行了比较，并结合这些系统在不同实施位置的具体特性进行了说明。提出方案部分介绍了我们提出的去中心化和分布式存储系统架构，该系统名为 StorEdge，作为平台运行于边缘计算层的网络连接设备上。实验结果部分展示了我们所提出服务获得的结果。最后，给出了主要结论。

2 相关工作

由于对更快、更优的计算和存储资源的需求不断增加，传统个人计算机或数据中心已不再是可行的解决方案。其主要缺点在于所有设备的初期投资成本高昂。因此，云主机变得如此流行。它们的资源是无限的，成本仅限于实际使用的时间。如今，大多数围绕人们的设备都可以被视为云的延伸部分。

公共云[13]的出现是为了满足客户在短时间内获取所需全部资源的需求。它类似于电子商务平台，用户只需点击几下即可选择产品、付款并使用，只不过在这里提供的产品是 CPU 和内存。使用这一层的唯一要求是具备良好的互联网连接。由于云中的资源可能位于很远的位置，客户应预期到数据处理或存储时会引入较低的传输速度和延迟。此外，某些公司可能具有安全规则[14]，禁止通过互联网传输数据或将数据存储在无法完全控制的远程系统中。由于这些问题，另外两种计算层应运而生。

雾[4] 是距离公共云最近的一层。它代表了边缘层设备与云设备之间的边界。这一层的设备通常由路由器组成，具有强大的 CPU 资源。它可以被视为进入云之前的缓冲层，因为来自设备的数据可以在雾层进行汇聚和处理，仅将相关数据传输到云。通过这种方式，由于减少了通过互联网传输的数据量，延迟得以降低，同时利用已有的计算资源也降低了成本，而无需在公共云中付费使用这些资源。通过使用此类设备还可以解决安全问题，因为数据在其生成的同一网络中进行处理，能够更好地控制哪些人可以与数据交互。

该层的设备是产生需要处理数据的设备。这里可以识别出两种类型的设备。其中一种是由仅专门用于收集数据但不具备任何处理能力所需资源的设备组成。最典型的例子是传感器，它们从不同地点收集数据并将其发送到雾或公共云层进行分析以提取有价值的信息。另一种类型的设备除了收集数据外，还能解释这些数据并立即做出响应。自动驾驶汽车或飞机收集大量需要实时处理的信息。将数据发送到其他地方进行处理并不可行。因此，必须在这些边缘设备上进行处理[15]。

这三个计算层级之间的主要差异也在表1中列出。公共云设备与物联网设备之间的主要差异在表2中列出。这些分布式存储系统解决方案之间的差异如表3所示。

大多数现有的云服务提供商现在都提供多种分布式存储服务（例如 Amazon S3、Microsoft Azure Blob 存储、Google Cloud 等）以及许多其他服务。选择最合适的存储服务需要在成本、可扩展性和可用性之间找到平衡。

一种在全球大数据应用中广泛使用的分布式存储解决方案是 Hadoop 分布式文件系统（HDFS）[5]。其主要特性是可扩展性和容错性。另一个优势在于它可以在任何类型的机器上进行配置，无论这些机器是位于本地数据中心还是公共云中。该系统专为高吞吐量而设计，因此应用程序应通过读取或写入大量数据块来与其交互。为了更细粒度地访问信息，可以采用键值存储方案，例如 HBase[9]，它通过后端与 HDFS 通信，以较大的数据块写入数据，从而提高效率。

HDFS 架构由两个名称节点、至少三个以上的奇数个日志节点以及一组数据节点组成。顾名思义，数据节点是实际存储数据的位置，数据通常以三倍因子进行复制，以确保容错特性。名称节点不会同时处于活动状态。其中一个应为活动状态，负责处理所有的写入和同步请求，类似于传统分布式架构中的主节点。另一个处于待机模式，但始终与最新更改保持同步，以便在需要时随时转为活动状态。名称节点之间的这种同步机制由日志节点提供，所有需要的元数据都存储在日志节点中，以确保在活动名称节点需要被待机节点替换时实现平滑过渡。这种类型的分布式存储系统非常适合没有功耗或资源稀缺限制的计算机。

此外，其功能依赖于节点所在机器的弹性。该节点需要大部分时间保持运行，且不能频繁更换，否则系统将花费过多时间进行数据复制，而非处理用户请求。因此，此解决方案不适用于边缘层的设备。

一个去中心化分布式系统的典型例子是区块链[16]。它在经济领域中用于数字货币比特币。因此，它是所有涉及比特币交易的公共账本。该系统基于使用加密协议的点对点网络。节点自愿加入网络，确保去中心化特性，它们成为区块链的管理员之一。借助数字签名，可以识别和授权一个节点的身份，使其参与未来交易的计算和验证过程。多个节点同时处理同一笔交易的相同步骤，以确保容错性。然而，最终只有一个节点成功完成该交易并获得相应奖励。决定哪个节点最先且正确地完成交易的过程即为共识问题[18]。这种竞争机制要求参与该过程的节点具备高性能的计算和存储资源，从而限制了只有云层中的设备才能参与其中。

可扩展性、复制、容错性和共识等特性也必须在边缘层的此类解决方案中得到保障。

3 提出方案

我们提出一种在边缘层设备上运行的去中心化和分布式存储服务，该服务由五个模块组成：客户端接口、发现引擎、复制引擎、安全引擎和备份引擎。这些设备可以是手机、智能电视、树莓派计算机[19]以及任何位于同一网络中并共享计算和存储资源的其他机器。仅使用局域网的理念与用户在此系统中存储内容的数据隐私相关。

因此，StorEdge 是一个可通过 API 访问的去中心化和分布式平台。它通过提供在系统中存储数据（POST）以及从网络中任何其他设备检索数据（GET）的方法，为用户提供统一接口。该方案还需满足边缘应用的要求（如数据局部性）以及任何分布式存储系统的要求（如数据复制和容错性）。

3.1 发现服务

当新设备加入局域网并希望参与 StorEdge 平台时，将使用此服务。它解决了此类系统的移动性问题，允许它们根据需要随时离开和重新加入。

因此，新设备必须扫描本地网络，寻找同样属于 StorEdge 系统的最近邻居，并与其执行握手操作，以加入平台。该握手机制提供了必要的安全层，通过阻止恶意实体来保护客户端数据的隐私。

3.2 存储服务

存储机制负责管理客户端在 StorEdge 系统上执行的 POST 和 GET 操作。

第一个功能允许用户在系统中添加新文件以进行存储。由于系统必须确保数据复制和容错性，因此首先执行的操作是将文件分割成较小的数据块，并根据需要创建相应数量的副本，以满足上述需求。然后，原始数据块和复制的数据块被分发到 StorEdge 平台上的不同设备上。所有接收存储文件数据块的设备都包含一些元数据，以便在需要时能够重建文件。因此，如果其中一个设备出现问题或离开网络，随之丢失的数据块将从其余设备中恢复，并再次进行复制以满足需求。

第二种操作允许用户通过在平台中传播请求来从系统中检索文件，以组装其所有分布式数据块。所提出的架构实现了 Gossip 协议[3]。因此，当一个设备被要求从系统中提供文件时，它会查找文件的哪些部分存储在其本地内存中，并询问所有邻居是否了解剩余数据块的信息。当邻居无法找到所有必要部分时，这些请求也会被进一步传播，直到找到文件的所有数据块并返回给发起搜索的设备。最后，组装完成的文件将提供给请求该文件的用户。

3.2.1 发现引擎

发现引擎负责在网络中查找希望加入分布式存储系统的新设备。它会定期扫描网络，并使用握手协议来发现和认证新设备。当前的实现在局域网中通过以太网或 Wi-Fi 扫描设备，但可以扩展至蓝牙或其他物联网设备使用的通信类型。

3.2.2 复制引擎

复制引擎负责确保复制和容错性特性。网络中的每个节点根据 StorEdge 系统的配置，将其拥有的文件划分为分片，然后根据复制因子将这些分片的副本发送到系统中的其他节点。分片存储在节点的文件系统的磁盘上。每个分片包含文件名、分片总数、自身的分片编号、该节点上现有副本的数量以及对应分片的文件数据。所有这些信息都用于复制算法中，同时在聚合过程和文件合成时也需要，以便在需要时交付给用户。

3.2.3 安全引擎

安全引擎决定哪些设备允许存储敏感信息，哪些不允许。如前所述，它可以采用仅允许插入式设备的默认规则，或由网络管理员配置的其他规则。它在复制引擎中起着重要作用，因为它禁止将敏感文件的分片存储在不安全设备上，同时也禁止从此类设备检索敏感文件。

3.2.4 备份引擎

备份引擎由系统中的一个或多个节点组成，具备足够的计算资源和稳定的互联网连接，以便在不同的预定时间段内将系统中存储的所有数据上传到公共云存储解决方案，例如亚马逊网络服务（AWS）提供的简单存储服务。该机制可确保在大量设备短时间内离开网络且 StorEdge 系统中没有保留足够文件分片的情况下，数据不会丢失。此时，该文件将从公共云存储系统中检索。

因此，所有上述引擎可以分为两个系统：由客户端接口和备份引擎组成的交互系统，以及由发现、复制和安全引擎组成的处理系统。根据排队论书籍[10]中的分类，前者是一个开放系统，而后者是一个封闭系统。

3.3 交互系统

交互系统被视为一个开放系统，因为它具有外部的到达和离开。每个节点处理针对其暴露的网页 API 所发出的请求，这意味着并非所有节点共享一个中央队列。

每个服务器都有一个请求队列，这些请求按照先到先服务顺序（FCFS）进行处理。表征此类系统的主要参数是平均到达率（λ），表示任务到达服务器的平均速率，以及平均服务率（μ），表示服务器处理任务的速率。因此，用户向 StorEdge 系统上传或下载文件的请求是独立事件，可视为泊松过程。排队论指出，速率为 λ 的泊松过程是一系列事件，其到达间隔时间是速率为 λ 和 N（0）的独立同分布的指数随机变量，并且 = 0（系统初始为空）[11]。这种指数分布的变量 X = Exp（λ）具有如公式1所述的概率密度函数 f（x），其均值为 E[X]。

$$
f(x)=
\begin{cases}
\lambda e^{-\lambda x} & \text{if } x \geq 0 \
0 & \text{if } x < 0
\end{cases}
\quad \text{and} \quad E[X] = \int_{-\infty}^{\infty} x f(x) dx = \frac{1}{\lambda}.
\tag{1}
$$

确保这些事件在任意时刻到达相互独立的是指数分布的无记忆性，如方程2所示。

$$
P{X > s + t \mid X > s} = \frac{P{X > s + t}}{P{X > s}} = \frac{e^{-\lambda(s+t)}}{e^{-\lambda s}} = e^{-\lambda t} = P{X > t}.
\tag{2}
$$

前述方面表明，根据排队论，每个节点都可以建模为一个 M/M/1 队列系统，其服务时间为独立同分布的指数随机变量 1/μ，用户请求以速率为 λ 的泊松过程到达队列。

在肯德尔记号中，第一个字符（M=无记忆）表示到达事件的到达时间间隔分布，第二个字符表示服务时间的分布，最后一个字符对应于该队列系统中的服务器数量，在此情况下为一个[11]。该记号还可以包含队列的边界作为第四个字符，用于表示某一时刻队列中可容纳的最大事件数。为了避免出现无限长的到达队列，到达率必须低于服务率。即便如此，由于到达过程存在波动，队列并不总是空的。考虑到这一点，无法确切知道我们的系统队列应设置多大的最大事件数并加以限制。

如果因队列已满而直接丢弃用户上传图像的部分请求，则会导致不可接受的数据丢失场景，这对于可靠存储系统而言是不能接受的。

用户通过上传或下载文件的请求提交的任务大小与在节点的文件系统上写入文件或数据块的检索与组合所花费的时间相关。这是服务需求参数，记为 S，其均值为 E[S]，且等于 $ \frac{1}{\mu} $。

因此，一个请求从提交时刻到最终被处理完毕所花费的总时间由 E[T] 参数表示，它等于 E[S] 与在队列中等待的时间 E[Tq] 之和。结合这些参数以及利特尔定律，我们还可以确定系统中的任务数量，记为 E[N]，它等于平均到达率 λ 与任务在系统中的平均停留时间 E[T] 的乘积。

3.4 处理系统

由于系统中的任务数量始终保持不变，且没有外部到达或离开，一个节点在完成前一个任务后立即开始处理下一个任务，因此该处理系统被视为封闭系统。该任务数量记为 N，在我们的系统中等于参与 StorEdge 系统的进程数量的两倍，记为 k。这是因为，在每次分片再平衡步骤中，每个节点在确认其两个邻居有足够的存储空间后，会向这两个邻居发送一些分片。在节点完成处理来自邻居的请求（即响应时间 R）之后，到下一次再平衡步骤之前，存在一段被称为思考时间的时间，记为 Z。在此期间，每个节点会对其当时存储的所有分片进行库存盘点，并确定哪些分片需要被复制，并在下一步发送给邻居。这些原因使得该系统被视为封闭交互式系统。因此，系统中的耗时等于之前各项的总和：
$$
E[T] = E[R] + E[Z].
$$

该封闭系统的吞吐量记为 X，它取决于服务率 μ。这是封闭系统与开放系统之间的主要区别之一，因为在开放系统中，X 不依赖于 μ。因此，在封闭系统中，如果我们增加所有服务率，将会导致吞吐量的变化，同时保持 N 不变。参数 X 也可以通过封闭系统的利特尔定律计算，等于多道程序设计水平 N 除以任务在系统中的平均时间[11]。这也为我们提供了平均响应时间的公式
$$
E[R] = \frac{N}{X} - E[Z].
$$

作为一个封闭系统，我们可以确定吞吐量 X 的某些渐近界。为此，我们使用 Di 参数，该参数表示一个任务所有访问期间在设备 i 上的总服务需求。对于较长的观察周期，该参数等于设备繁忙的总时间除以系统中的作业完成数。因此，吞吐量受限于公式3中给出的公式。这意味着当多道程序设计水平 N 较大时，吞吐量受限于 $ \frac{1}{D_{\text{max}}} $，这使得 $ D_{\text{max}} $ 成为瓶颈设备；而当 N 值较小时，吞吐量受限于 $ \frac{N}{D + E[Z]} $。该公式有助于发现系统中哪些部分需要改进以提高系统性能。基于相同的原因，公式3和公式4也给出了平均响应时间 E[R] 的渐近界。

$$
X \leq \min\left( \frac{N}{E + E[Z]}, \frac{1}{D_{\text{max}}} \right).
\tag{3}
$$

$$
E[R] \geq \max(D, N \times D_{\text{max}} - E[Z]).
\tag{4}
$$

4 实验结果

对于所提出的模型，我们测试了文件上传的吞吐量（见图2）、文件下载的吞吐量（见图3）以及敏感文件和非敏感文件的检索时间（见图4）。

敏感文件的检索时间较长是正常现象，因为只有可信设备（数量少于不可信设备）才能响应并提供这些文件的数据块。此外，较高的复制因子会降低检索时间，因为这些数据块在更多设备上存在副本，但这会给系统带来更大的压力，并增加其成本。

5 结论

提出方案是一种在边缘计算层中此类设备上运行的去中心化存储服务，该服务由五个层组成：客户端接口、发现引擎、复制引擎、安全引擎和备份引擎。这些层可以分为两个独立的系统：交互系统和处理系统。前者被视为一个开放系统，其中请求根据泊松过程到达；而后者是一个封闭系统，循环中始终具有相同数量的任务。

用户通过通用 API 与存储服务进行交互，该 API 可从属于此服务的任何主机访问。构成此平台的节点使用相同的无线网络。系统中存储的数据必须被分割成分片，并在多个设备之间共享，以确保冗余和容错。根据计划，系统中的文件由具有较强计算资源和互联网连接的节点定期上传到公共云存储系统作为备份，以防大量设备突然离线导致数据丢失。