大规模分布式存储如何优化？Facebook说自己的方法能把CPU负载降一半

本篇文章3161字，读完约8分钟

雷科技评论:今天facebook在研究博客上发表了一篇文章，介绍了自己的超大规模图形分区优化算法shp。这是facebook开发的一种方法，用来处理它自己的大规模图划分问题，它在大规模优化问题中确实发挥了作用。研究论文还被数据库领域著名的国际会议vldb 2017(超大型数据库)收集。雷科技评论编辑了这篇介绍文章如下。

对于facebook来说，它每天服务的用户数量是10亿。为了支持这种规模的访问，facebook需要在许多不同的级别设计分布式负载。Facebook在世界各地建立了许多数据中心，以提高用户访问的可靠性和容错能力，并改善延迟。然而，单个托管服务器的容量和计算资源总是有限的。facebook的存储系统需要在多个托管服务器之间共享数据，批处理计算任务也需要在由数千个工作站组成的集群上运行，以增加计算规模并加快计算速度。

这些系统的核心是一系列小的安排，也就是说，如何将任务元素(如请求、数据条目和计算任务)分配给一个计算组(如数据中心、托管服务器或工作站)。分配任务的方式不计其数，但是不同的分配方式带来的响应时间和服务质量是不同的。

要考虑的第一个方面是负载平衡:如果一个计算团队超负荷，它就不能达到最初的响应时间或服务水平。对于给定的负载分布，总是有进一步优化的潜力，因为很多事情可以在同一个地方完成，而不是单独完成。例如，将经常需要同时访问的两个数据放在同一个存储托管服务器上可以提高使用这些数据的查询性能。

平衡图划分为处理任务背后的工作量分配问题提供了一种有用的方法。在该方法中，图中的节点将被分配给多个“桶”中的一个，这意味着计算项目将以平衡的方式被分配给多个计算组中的一个。在整个过程中，任务的一些特征被不断优化，例如单个组内的任务相似性。此前，facebook介绍了他们如何通过使用平衡图划分的方法实现前所未有的系统性能。在他们的新论文《社会散列分割器:一个可扩展的分布式超图分割器》中，facebook介绍了一种分割二部图的新方法，它可以最小化扇出。这种新方法在facebook的许多分布式负载优化任务中发挥了有效的作用。Facebook称该框架基于这种方法社交哈希分区器(shp)，因为它可以在之前的facebook nsdi 2016论文中用作社交哈希框架的超图分区组件。

小水电的以下亮点逐一介绍

减少扇出facebook研究人员研究如何减少扇出。问题的根源是分布式数据集中经常出现的碎片问题。假设有这样一种情况，一个大数据集，其中数据记录分布在许多数据服务器上。在数据集的查询中可以使用几个数据记录。如果这些数据记录分散在几个服务器上，则有必要向每个服务器发送一个查询来回答原始查询。这样，将数据记录分配给不同服务器的方式决定了在处理查询时需要启动的新查询的数量；这个数字被称为这个查询的“扇出”。低扇出的查询可以执行得更快，因为在此过程中它不太可能与较慢的服务器通信，并且通过减少通信计算量来降低整个系统的负载。因此，一个共同的优化目标是为数据集选择一种数据分配方法，以便不同查询所需的数据可以直接存储在同一个地方。

图1显示了用生成的访问请求和实际请求测试后的系统性能。

图1

在图中，纵坐标t代表系统的平均延迟。可以看出，具有高扇出的请求会遭受更高的延迟。具体来说，大约40是非常高的扇出值。如果减少到10，这个查询的延迟可以达到平均值。

碎片存储问题可以建模为一个二分图划分问题。在图2中，数据项和需要访问它们的查询被表示为二分图中的顶点，然后数据被分成k个组；在划分过程中，每个组应该被划分成近似的数据量，每个查询需要连接的不同组的平均数量应该尽可能小。

图2

找到扇出较低的分区

寻找图的最佳划分通常是一个难以计算的问题。一种典型的启发式方法是从一些初始的平衡分区开始，在一个迭代过程中对一些顶点的分布进行局部小调整，以逐渐改善分组效果。在每一次迭代中，每个顶点都将估计其切换到其他组的偏好，这被称为“增益”。如果新收入高于当前分配方法，您可以尝试将此顶点移动到另一个组，同时保持整体负载平衡。

然而，这种方法在扇出优化中的效果非常差。图3是一个问题。图中标记的v1和v2分别为两组。

图3

每个查询(q1、q2、q3)恰好访问两个数据包，因此平均扇出为2。但是，这不是最佳分组，因为如果顶点3、4和5、6被切换，q1和q2查询的扇出将减少到1，平均扇出将减少到1.33。然而，从每个顶点自身的角度来看，将自己变成另一个组不会有更高的好处，因此需要使用该节点的扇出不会得到任何优化。

Facebook的新研究通过使优化目标“平滑”来改善这种情况:它不假设查询需要找出所有所需数据的扇出，而是假设它将以概率p访问每个数据条目。这样，将每个顶点从组I改为组j的增益v表示为:

图4

其中n(v)是访问v的一组查询，ni(q)是I组中查询q访问的数据项的数量..在采用这种收入估计之后，顶点更容易显示它们对包含类似查询的分组的偏好，并且即使在这种替换之后，实际扇出也不会减少。

这样，本文中的算法可以表达如下:

初始化一个平衡组(如随机)

重复以下步骤，直到收敛

对于每个顶点v

根据上面的等式，找到移动收入最高的J组

记录顶点V从当前组I移动到新组j的意愿

对于每对分组I和j

找到从I到J的顶点和从J到I的节点，并替换它们

大规模问题的优化效果和表示扇出最小化问题等价于平衡超图划分问题。目前，有一些超图划分框架，但是facebook的图规模太大，现有框架无法处理。

Facebook在apache giraph中构建了他们的解决方案，并仔细设计了图形的大小和理想的分组数:顶点运动的评估可以以分布式的方式完成，它发生在当前顶点通过任务分配与其他顶点通信之后。类似地，顶点替换操作也可以通过分布式方法来完成。成对的组(I，j)可以分布在不同的托管服务器上，或者替换决策可以通过概率选择来近似。在实践中，facebook的研究人员发现，在不牺牲优化质量的情况下，分布式算法能够处理的图形比其他现有方法能够处理的最大图形大100倍。

图5显示了算法的运行时数据(shp-2和shp-k，shp的两个变体)，并将其与其他现有的分区框架进行了比较。测试内容包括三个不同大小(边数从1000万到50亿不等)和不同组的图形的性能。在小规模优化任务中，小水电往往是最快的；对于大规模的优化任务，shp是唯一能在合理时间内制定出优化计划的参赛者。

图5

图6显示了shp和其他框架之间优化质量的比较。由于目前无法确定网络的真正最佳平均扇出，该图显示了每个结果高于现有最佳算法的百分比。在大规模优化任务中，小水电的效果最好；然而，在小规模优化任务中，shp可能比现有算法的最佳结果差最多12%。

图6

结论和扩展阅读扇出约简模型可以在facebook的许多基本优化问题中发挥作用，如数据碎片化、查询路由和索引压缩等。自从shp成功开发以来，facebook经常使用它来解决具有数十亿个节点和数万亿条边的图的扇出优化问题。内部实验表明，在分布式系统上使用shp的数据分配方案可以减少多达一半的cpu消耗。本文也包含在vldb 2017中。Shp也已经作为giraph应用程序开放，可以用于优化任务和教育。

地址:vldb/pvl db/vol 10/p 1418-pup yrev . pdf。

nsdi 2016分区优化器论文地址:usenix/system/files/conference/nsdi 16/nsdi 16-paper-shalita . pdf。

通过脸书研究博客，雷锋(公开号:雷锋)人工智能技术评论汇编

雷锋文章版权所有。严禁擅自转载。详情请参考转载说明。