下载掌阅APP，畅读海量书库
立即打开
对于任何计算机系统，存储系统都是必不可少的组成部分。对于边缘计算平台来说，数据的存储能力也是极为重要的需求。边缘计算存储需要什么样的存储系统呢？答案是，视情况而定。为什么这么说呢？因为边缘计算需要处理的数据量、时延要求、数据传输和存储的总量，对于不同的应用来说，差别是非常大的。不过，对于比较大规模的边缘计算应用，分布式存储技术是关键核心技术。
对于不同的应用，我们需要不同的存储方案。某些简单的应用，比如记录某个区域的温度和湿度范围，只是简单地把数据上传到边缘设备或云端存储和加工。那么，就不需要复杂的分布式存储架构，只需要满足本地文件系统的访问处理就可以。但是，这样简单的应用形式可能不再是未来物联网和边缘计算的发展方向和主流形式了。尽管有很大一部分数据只需要本地存储和处理，但是我们有越来越多的应用需要在广大的地理范围内，比如全国甚至全球范围内共享、存储和读写数据。例如，智能工厂的生产过程，由于其原材料和零部件的供应链遍布全球，可能需要同步获取世界各地其他相关工厂的生产、仓库和物流的实时信息，以决定生产的节奏并协调整个供应体系，从而提高生产效率并降低成本。如何实时、可靠地共享、读写和处理这些数据和信息，变得非常重要。
对于要在广大的地理范围内的物联网系统间共享和读写数据的需求，有一种方案是把数据直接上传到传统的云计算数据中心，这种方案在时延性和可用性要求比较低的场景下是可以考虑的。我们可以搭建传统的单集群分布式存储系统，比如Ceph、ClusterFS、HDFS等存储系统；或者直接采用云计算服务商的存储服务，比如AWS的S3存储。当边缘设备需要访问数据时，直接连接并访问云数据中心来读取需要的数据，产生的新数据再写入云存储。读到这里读者肯定发现了，要是这么做的话，还需要边缘设备的存储干什么呢？在很多网络连接稳定，且对时延要求不高的场景下，这种方案当然是可行的，但是这个模式也是有明显的局限性的。如今，有很多应用对共享数据的实时性和可用性有非常高的要求，而且不同的设备距离数据中心的距离差别非常大，因此访问数据中心的连接速度和时延相差也很大。这对于用户体验和实时性要求很高的应用会影响非常大。
我们再来看看现在常用的分布式存储系统本身是否能够满足跨地理区域，部署在异构系统的要求。传统的分布式存储系统的架构一开始都是以单集群的模式来设计的，即使这样，我们还是有办法把它们扩展到多个集群和云数据中心，可以通过Federation模式来做高可用和灾备。把数据复制到不同的云数据中心，这样就可以解决很大一部分问题。可是尽管这样，云数据中心的存储能力也是有限的。如果有大量的物联网设备产生海量的数据，然后全部传输到云数据中心去存储和处理，也是非常困难的，同时使用多个云数据中心的成本也会很高。仅仅为了高可用性而这样做，往往是不经济的。
综上所述，传统的云存储和其他分布式存储技术可能不是边缘计算存储的最佳解决方案。我们需要有专门为边缘计算设计的，能够跨地理位置，在多个异构集群、边缘机房及云计算中心部署的存储系统。
另外，在物联网和边缘计算领域中，我们还需要考虑一些极端特殊条件下的存储问题。
（1）设备工作在极端恶劣或特殊的环境下，基本上不可能连入网络，与云平台交互数据，比如在火山口附近监测火山活动、在战场收集信息等。
（2）边缘服务和设备端积累了超巨量的数据，例如，遥感卫星公司积累的高精度卫星照片数据。这种数据都是几百PB甚至EB的规模，并保存在本地存储设备中。如果用互联网传输到云数据中心，可能需要几十天甚至几年时间。
提出问题就应该有相应的解决办法，下面笔者会详细介绍解决边缘计算存储的技术和非技术手段。为了比较全面地了解分布式存储技术，笔者会从通用的分布式存储系统的概念开始介绍，然后引入边缘存储需要的分布式存储系统和架构。
本小节是给希望从底层了解和学习分布式存储系统的读者准备的，相对来说会涉及很多理论和数学的知识。笔者会尽量简单明了地介绍这部分内容，不会使用很多公式定理。如果只是希望了解边缘计算分布式系统的使用和选择，可以跳过这一节。
1.哈希算法
（1）朴素哈希算法。
所有的理论和方法一般都是从问题开始的。对于由大量的数据和大规模的节点构成的存储系统，到底应该如何去设计呢？我们可以先假设一个场景，这个场景是存储100万个视频文件，同时我们的存储网络中总共有100万个节点。每个视频大小是1GB，而每个网络节点的存储空间是1TB。
最简单的办法是随机地把视频存储在不同的节点上，并采用一个全局的索引来记录每个视频的存放节点。但是，如果这些节点总是频繁地改变，而又不希望总是频繁地修改全局索引，我们有什么好的解决方案吗？
我们把视频的数量设为m，网络中所有的节点数量设为n。那我们就可以把视频的文件名，或者整个视频文件通过哈希算法（SHA-1、MD5等），得到一个整数型的哈希值h，然后给所有的存储节点编号（0~n-1）。我们对哈希值取n的余数得到k=h%n，那我们就把这个视频文件存储到编号是k的存储节点上。这样每个节点的平均期望存储视频的数量应该是m/n个。
如果前面得到的哈希值h符合独立伯努利随机分布，就可以证明一个节点存储视频数量大于平均期望10%的概率小于1%。因此，在节点比较稳定的情况下，这个算法能够很好地解决分布式存储的寻址问题。
以上是比较朴素的哈希算法，但是在实际的应用中，尤其是在边缘计算或P2P网络中，网络节点往往是不稳定的，随时可能加入或退出。这个不稳定性叫作扰动（Churn）。如果有节点加入或退出网络，那么所有视频的存储位置都要重新计算，然后几乎所有的影片都要移动到其他的存储节点。这会产生大量的网络传输和数据读写，在实际生产环境中显然是无法接受的。
（2）一致性哈希算法。
事实上，有不少朴素哈希算法变种可以解决这个问题，一致性哈希算法就是其中的一种，它在分布式缓存领域中，有非常广泛的应用。在一致性哈希算法中，我们并不是直接给每个网络节点编号，而是设定若干个slot，比如设置2 32 个slot。这个算法分成两步，先对所有节点计算哈希，然后计算文件的哈希以确定存储位置。具体步骤如下。
首先，我们对每个网络节点的IP地址+端口号进行哈希运算，获得一个哈希值H，然后取余数H/2 32 ，这样就能够获得这个节点的slot编号S。对每一个节点都计算出slot编号，可以形成一个逻辑上的有向环形网络。
然后，我们再对网络上需要存储的文件进行哈希计算，获得一个哈希值h，然后取余数h/2 32 ，这样就获得了一个文件的编号K。
我们在所有节点中找到最接近K的节点S，然后把文件K存储到S节点上。这个算法如图3-1所示。
图3-1 一致性哈希算法
图3-1是简化了的一致性哈希算法示例，在这个网络中有3个服务器节点，通过哈希算法获得了编号，分别是0、8和15。需要存储的文件进行哈希计算并取余以后的编号有4、5、7、9、10、12和17。我们看到，文件4、5、7会被保存到节点8；文件9、10、12会被保存到节点15；文件17会被保存到节点0。
当我们在这个网络中加入一个新的服务器节点后，比如加入了编号是6的服务器节点，那么文件4和5就会被调整到节点6存储。
当某个节点被移除时，比如15号节点被移除，文件9、10、12就会被调整到0号存储节点。这样每次加入或移除某个服务器节点，只需要调整存储到这个节点的文件就可以了，大大减少了网络传输和服务器读写的压力。
采用了一致性哈希算法的存储系统有Redis、DynamoDB等分布式存储系统。但如果节点被移除，上面的数据也就没有了。那如何调整呢？其实对于Redis这样的分布式缓存来说，下一次读取这个数据，首先是返回一个缓存未命中消息，然后再去数据库读取该数据并存入缓存。而对于分布式数据库来说，则是通过将同一数据复制几份到不同节点的方式来确保数据的可用性。
2.分布式哈希算法
（1）永不稳定的存储集群。
我们看到，一致性哈希算法能够解决一些扰动的存储集群问题。但在很多情况下，尤其是P2P或大规模的边缘存储应用中，可能每个节点只能可靠地工作一个小时。节点一直都在持续地扰动，不停地加入和离开分布式网络，可能每秒钟都会有数百个甚至数千个节点的变动。传统的分布式集群一旦有节点变动，就必须重建网络拓扑。如果集群中的节点一直都在扰动，那么永远不可能拥有一致性的拓扑图。
这种情况下，我们不可能期望每个节点都能够获得集群的完整视图。于是只要求每个节点认识它邻近的一些节点，这样就能够对抗大型集群的频繁扰动。但是，如果需要查找某个文件的位置，往往需要经过几次跳转才能够获得。当一个节点希望查找某个文件的存储位置时，它首先会询问一个邻近节点，如果这个邻近节点没有这个文件，该节点则会继续询问它的邻近节点，直到找到文件为止。这样的网络实际上在物理网络连接的上层构成了一个覆盖网络（Overlay Network）。
作为理论上的研究，我们应该了解一些覆盖网络的拓扑结构。首先用于大规模的分布式存储的网络应该是一种同质的（Homogeneous）网络，也就是说，没有节点在网络中处于支配地位，网络中的任何节点都不会造成单点故障。网络应该拥有比较小的直径，当不知道某个文件的位置时，只需要通过少量的跳转就能够找到正确的存储节点。
常见的网络结构有树、环、网格及圆环（Tori）。对于树来说，总是存在一个根节点，所以它并不满足同质性。对于分布式存储集群，我们会更倾向于选择网格或环状结构的覆盖网络拓扑。
很多超级计算机的计算节点之间采用了超立方体结构的连接方式，超立方体结构的好处是，每个节点之间的跳转距离是一致的。例如，源节点t 1 到目标节点t n 的差异是K，那么它们之间的距离就是K跳，有K！条路径。可以看出，用超立方体结构构建集群是最完美的方案，节点和节点之间的距离固定，路由非常简单。在通常的网络环境中，维持稳定的超立方体结构几乎是不可能完成的任务，不过使用超立方体结构在某些情况下是可行的方案。如图3-2所示，这五个图形是超立方体结构从0维到4维的变化。
图3-2 超立方体结构
超立方体结构延伸出了很多其他的网络拓扑结构，比如蝴蝶网、立方体-环连接网、混洗交换网、德布鲁因图等，它们在不同领域中都有特定的用途。蝴蝶网在实践中用于排序网络、通信交换和快速傅里叶变换等；德布鲁因图在基因测序算法中发挥了重要作用。由于这些衍生出的网络往往过于特殊，通常用于专门领域，并不适合通用的网络结构，这里就不详细展开了。
（2）分布式哈希表。
分布式哈希表（DHT）是实现分布式存储的数据结构，支持对键值对的搜索、插入和删除操作。DHT通常只需要知道其相邻节点，并且知道的相邻节点通常不会超过100个，然后通过一些算法去查找对应文件的位置。DHT的提出主要是由于早期P2P文件共享网络的出现和应用，P2P文件共享网络协议经历了3次大的变化。
第一次，以Napster为代表的中心索引服务器架构。这是P2P文件共享网络最早出现的形式，由一个服务器来提供所有文件存储位置的信息。当某个节点或客户端希望访问这个文件时，就会先向这个中心服务器发出请求，获得文件所在的机器IP和端口。可以看到，这个索引服务器就成了整个系统的瓶颈，而且不是一个真正意义上的去中性化的网络。
第二次，以Gnutella为代表的Pure Flood模式。通过向其已知的所有节点发送查询请求，收到查询请求的节点如果没有文件，则会继续以这样的模式去查询。当然，我们可以设置TTL，以限制查询转发的次数。但是，这种模式还是会大量消耗网络资源，造成底层TCP/IP网络中的其他服务受到影响。很多电信网络运营商甚至对这种模式的P2P应用进行了屏蔽和封杀，以免影响到整个网络的性能和服务。
第三次，DHT技术的网络存储系统。其具备高效查找网络中文件位置的能力，并且避免了在整个广域网中进行广播风暴。
实现DHT有几种不同的算法，比如Chord、Kademlia等。其核心思想都是每个节点存储一部分键值对，同时保存一张索引表，这个索引表是网络中所有节点索引的一小部分。索引表中的节点就是当前节点的相邻节点，通过一定的规则去查询其中一个相邻节点，然后再通过相同规则接力查询，经过有限的几次跳转，最后获得保存有文件的节点信息。
下面介绍一下Chord算法，这个算法与一致性哈希算法有相似的地方。我们在Chord算法中需要计算节点的ID和资源的ID，称为NID（Node ID）和KID（Key ID）。可以通过哈希IP地址获得NID，通过哈希资源文件获得KID。NID和KID都是m位的二进制数值，我们需要保证m足够大，使ID重复的可能性趋于零。
与一致性哈希算法一样，我们会建立一个Chord环（Chord Ring），将节点按照NID分布到这个环上。
如图3-3所示，这是一个m=3的Chord环，实际的应用中m会大得多，这里只是用来做例子解释原理。上面分布了0、1、3总共3个节点。我们要求资源被分配到编号为min(NID-KID)的节点上。于是如图3-3所示，KID=1的存储节点为Successor(1)=1，同理Successor(2)=3,…。
图3-3 Chord环结构
如果我们需要查找某个资源，就可以顺着环向前查找，复杂度为O(n)。对于海量节点的网络来说，需要的时间还是太长。于是我们可以给每个节点加入Finger Table的路由表，如图3-4所示。
图3-4 Chord节点的路由表
可以看到，我们把节点每个2 n 的Successor记录到表中，其中n的取值范围为[ 0,m )，这个算法的复杂度为O (log N 2 )。
节点加入Chord环分成以下三步。
（1）Join(n0):n0加入一个Chord环，Successor会指向它最近的后继节点n。
（2）Notify(n0):n0会通知后继节点n它的存在，若此时n没有前序节点，或者n0比n现有的前序节点更加靠近n，则n将n0设置为前序节点。
（3）Stabilize()：系统中所有的节点间隔一段时间会执行这个操作，节点会查询其后继节点的前序节点p，来决定其是否还是其后继节点的前序节点（中间没有加入节点进来）。也就是说，当p不是节点本身时，说明和后继节点间已经有新加入的节点了，此时将n的后继节点设置为p，同时让p设置前序节点为n。
（4）Fix_fingers()：修改路由表。
其实可以看到，上面讨论的是在一个stabilization间隔时间段中，两个节点之间一次只加入一个新节点的情况。但是，在两个现有节点之间，如果同时加入好几个新节点，比如在Notify时，有n0、n1、n2三个节点同时加入Chord环，发送Notify消息给后继节点n，那么n只会选择距离最近的一个新节点作为前序节点。n1和n2会在下一次stabilization时发现自己不是n的前序节点了，于是将后继节点指向n0,n0会选择距离最近的n1作为前序节点。第二轮stabilization才会完成n2节点的加入，从而最终完成三个新节点的加入。