英语原文共 26 页，剩余内容已隐藏，支付完成后下载完整资料
通过可编程开关加速大数据排序
施耐德，罗伊，弗里德曼
计算机科学系
以色列理工学院
摘要
排序是一个被广泛研究的基本问题。排序在数据库领域起着重要的作用，因为如果首先对关系进行排序，许多查询可以更快地提供服务。数据库中最流行的排序算法之一是合并排序。
在现代的数据中心中，数据存储在存储服务器中，而处理则在计算服务器中进行。因此，为了计算对数据的查询，它必须通过网络从存储服务器传输到计算服务器。这就创造了一种利用可编程交换机来执行部分排序的潜力，以加速服务器端的排序过程。这是可能的，因为如上所述，数据包在任何情况下都会在到达服务器的路上通过交换机。唉，可编程开关提供了一个非常有限和非直观的编程模型，这就是为什么实现这不是平凡的。
我们设计了一种新的部分排序算法，适合可编程开关的编程模型和限制，可以加快服务器上的合并排序。我们还利用交换机中内置的并行性来将数据划分为顺序范围。因此，服务器需要分别对每个范围进行排序，然后将它们连接到一个已排序的流中。这样，服务器就需要对较小的部分进行排序，并且每个部分都已经进行了部分排序。因此，服务器所做的工作更少，并且访问模式变得对虚拟内存更加友好。
我们评估了当使用我们的部分排序算法在多个数据流组合与不同的开关配置时所获得的性能改进。我们的研究显示，与原始流上的普通排序相比，使用我们的方法在排序运行时方面提高了20%-75%。
1介绍
可编程交换机，顾名思义，可以动态编程以执行用户定义的功能。主要的交换机供应商[1,2,3]都支持此功能。特别是，程序员可以定义实时收集数据包信息的方法，然后分析流量，推导网络统计和遥测，进行网络负载均衡和检测攻击，从而实时提高网络性能。
最近的工作已经演示了如何使用可编程交换机在数据中心设置[19]中加速SQL查询。在数据中心中，数据通常存储在存储服务器上，而计算则在单独的计算服务器上执行。因此，数据通过网络从存储服务器传输到计算服务器。这将通过在连接到计算服务器的开关上执行至少一些计算，从而创造了加速查询计算的潜力。
在这项工作中，我们专注于排序，因为它构成了查询回答的一个基本部分。许多查询需要排序，由于大数据集和排序的复杂性，这需要消耗时间和CPU。我们的目标是通过使用智能交换机的资源和计算能力来加速需要排序的大数据查询。我们关注合并排序方法，因为它在数据库中非常常见，因为它比其他排序方法具有优越的经验运行时。我们提出并研究了一种新的方法，通过在可编程开关上执行部分排序来加速服务器端的查询。在我们的方法中，由于可编程交换机的限制，我们只对数据进行部分排序，这足以大大减少在服务器上完成排序任务的运行时间。
我们的贡献
在这项工作中，我们开发了一个部分合并排序算法，适合大多数可编程开关采用的流行的PISA模型，利用它的多管道能力。具体来说，我们将数据输入划分为不重叠的范围。交换机中的每个管道都处理自己的范围，每个值都用其管道标识符传递给服务器。这已经创建了部分排序，因为服务器可以对每个范围分别排序，然后按原始顺序连接这些范围。
此外，关于合并排序的一个已知观察结果是，它的运行时间在很大程度上取决于初始输入的排序方式。具体来说，合并排序是基于运行的概念，这是输入中最大排序的子序列。这些预排序的运行时间越长，它们的数量就越低，因此排序过程就越快。为了生成更长时间的初始运行，我们开发了合并马拉松算法。在合并马拉松中，我们不是按原始顺序传递数据，而是使用交换机的可编程功能来改变流的顺序，并以更长的运行时间输出数据。这个输出成为计算服务器的新输入；它是相同的流，但排序的顺序更好。
合并马拉松为每个管道阶段添加了一些简单的操作，但有一个较小的延迟，遵循开关的限制和限制。我们评估了在使用合并马拉松时，可以在计算服务器上获得的性能改进。在我们的评估中，我们模拟了各种开关配置，并检查了多个数据集。结果表明，使用合并马拉松可以将服务器端合并排序的运行时间减少20%-75%。我们还表示了管道数的并行性和它们的长度与延迟和在服务器上的排序运行时之间的权衡。
2、背景及相关工作
在软件定义网络(SDN)中，控制平面与数据平面[11]进行物理分离。控制平面上的逻辑指示使用开放接口，如openFlow[14]，转发策略和转表格到数据平面（如交换机和路由器）。这使得网络控制器能够确定跨交换机网络的网络数据包的路径。这种网络管理方法能够动态地重新配置网络的控制器来提高网络，以提高其性能。图1显示了SDN体系结构的说明。
可编程开关正处于SDN的先进技术水平，并在过去几年中获得了普及。特别是，可编程交换机已经有了重大的发展，包括抽象和平台、专用编程语言和硬件以及此类智能交换机的芯片。除了路由数据包之外，可编程开关还可以被编程以执行各种操作和应用，如从数据包中收集数据、分析数据、计算某些统计数据等。
在硬件的速度和软件的可编程性所提供的灵活性之间有一个很自然的权衡，我们需要注意这些问题。例如，使交换机能够执行相当复杂的分割操作，将牺牲交换机的速度并增加其延迟。为了在不显著牺牲速度的情况下使用可编程开关，建议使用可重构匹配表(RMT)抽象的[11]。随着编程协议独立的包处理器(P4)语言[10]的出现，将软件和硬件的能力结合起来，从而享受它们的好处的能力已经变得可行。
2.1RMT和PISA
RMT是可编程交换机的一种高性能抽象技术。在这个模型中，数据包通过提取其字段的解析器，然后通过执行管道。最后，是经过一个离港员，
图1：软件定义的网络——SDN，其控制器与网络设备分离。每个设备都配置了它从控制器接收到的规则。
它包了头，然后包可以去它的下一个目的地。图2说明了可编程交换机中传入数据包的路径。管道中的每个阶段都是一个匹配操作表，它首先匹配数据包，然后可以修改它。
该模型能够为交换机添加功能，利用其管道和并行性，而不降低数据包处理的速度，由于该模型的以下限制：首先，管道阶段的数量有限，以避免长延迟。其次，每个管道阶段只有少量的静态随机存取存储器(SRAM)来执行有状态处理。由于强制定时要求，它还可以访问内存区域中的一些地址，但不能访问整个内存。此外，为了避免管道体系结构（数据包是并行处理的）的危害，两个不同的管道阶段不能访问相同的内存区域。只有一个特定的管道阶段被允许访问有状态的内存块。第三，每个阶段只能执行原始的算术动作。不支持复杂的操作，如划分。此外，也不支持在内存中包含许多元素的数组中寻找最小值或最大值。通常，该模型不支持全局计算函数。此外，在管道阶段内的分支也非常有限。图3说明了一个管道流，以演示并行执行的数据包的处理。图4显示了由于RMT模型而对这一过程造成的限制。
协议独立交换机体系结构(PISA)是一种高速可编程数据包转发的体系结构。遵循PISA模型的可编程交换机由多个管道组成，一个网络数据包通过它们依次传递。这些管道包含具有不相交内存的阶段，当数据包通过它们[4,5,19]时，可以执行有限的一组操作。在PISA中，一个数据包被解析为单独的报头。标题和中间结果可用于匹配和操作，并可以修改、添加或删除。最后，包被离开，如图2所示。
2.2PISA和P4
RMT是可编程交换机的抽象环境，而P4是一种新型的高级编程环境，被设计为可重新配置、协议独立和目标独立的，因此它可以使用PISA作为目标。P4提高了网络编程的抽象级别，提供了一个API
因为P4不是一种图灵完整的编程语言，而且由于RMT对可编程开关的限制和限制，某些算法根本不能用P4来实现，而其他算法可能需要一些更改和调整来实现。例如，HashPipe[17]是一种算法，它能够识别数据平面中具有大量或多个大流量的重打击器流。它使节省空间的[15]适应于P4。
节省空间是一种基于反数的方法，解决了顶部k和频率估计问题。基于计数器的算法为每个流维护一个唯一的计数器。节省空间可以返回一个估计，关于哪些是前k个流的流标识符，以及产生超过总数据包的给定百分比的流。这一点，除了每个流的计数。节省空间是通过维护一个计数器数量有限的表，这些计数器被分配给计数最高的流。每当来自没有计数器的流的数据包到达时，该流将得到最小计数器。当查询流的频率时，如果表中存在对应的计数器，则返回对应的计数器的值，或表中最小计数器的值。节省空间提供了有保证的性能，并被证明是类似方法中最好的[13]。
HashPipe能够识别数据平面中具有大流量的重打击器流。它在P4中实现了一个哈希表的管道，它为重流保留计数器，同时随着时间的推移驱逐较轻的流。数据包可能需要两次通过这个管道：一次，以确定计数器
图4：每个阶段说明了RMT的不同限制或限制：限制阶段的数量(k)。阶段1显示，每个阶段都有自己有限的内存和地址，不能访问整个内存。阶段2、3是不能访问相同内存区域的两个不同阶段。在阶段4中，动作和分支是有限的，不允许复杂的操作。
与d个插槽之间的最小值，并进行第二次更新该计数器。第二遍是可能通过“再循环”[17]。
P4自适应的另一个例子是精度[9]，这是一种top-k和频率估计的算法，用P4实现，基于RAP[8]算法，这是对节省空间的改进。RAP是一种基于新的计数器的频率和顶部k估计问题算法。RAP利用了一个概率接纳滤波器。也就是说，一个新的流接收到一个计数器，它与最小计数器的概率成反比。因此，如果流量很重，最终它将收到一个计数器，一个对应于当时最小监测流量的计数器。光流不太可能收到一个计数器。在原始的RAP中，我们需要在所有被监控的流中找到最小的计数器，以计算未被监控的流接收到计数器的概率。由于同级内存访问限制[9]，可编程交换机的架构不允许找到（和替换）所有计数器中的最小元素。因此，精度也使用再循环，即，如果一个包与任何流计数器不匹配，它被概率再循环要求一个具有新包的流ID的条目。请注意，并不是所有的概率公式都可以在P4中计算出来，因此它们是近似的。
序列归零是一种新的有效的可编程开关算法，用于检测重打击者的间隔。它基于模草图，这是一种计算间隔的方法，使每个数据包经过几个阶段来更新其计数器。它像一个工作时钟，当增加第二阶段的计数器时，它归零第一阶段的计数器，以此类推。带有模块草图的顺序窗口算法使用几个草图来计数数据包，并在整个草图每次满时重置最老的流计数器，以类似于滑动视图。顺序归零技术将调度的归零方法与顺序窗口相结合。它使用子间隔，并通过调度从顺序窗口的最后一个子间隔中删除过时的流计数。这是通过将这些阶段划分为子阶段并应用调度来实现的。
2.3数据库和排序
数据库是许多应用程序的核心，如数据仓库和分析[18]。在现代数据中心中，存储和计算通常被分离到不同的服务器上，数据需要将网络从存储服务器传输到计算服务器。随着工作负载的增长，数据库系统面临着为大型分布式数据集上的查询提供高性能的挑战。因此，像SparkSQL[7]这样的现代查询处理引擎通过将任务分配给工作人员来优化查询完成时间，这样每个工作人员只处理一个数据分区。然后在主工作者上聚合结果。
猎豹是一种新型的查询处理系统，它可以将查询部分卸载到可编程交换机[19]上。然而，它只卸载查询的一部分，而不是启用查询。通过这种方式，它通过修剪来加速SparkSQL[7]——一种过滤来自工人的数据的抽象。然后，主服务器在修剪后的数据集上运行查询，所接受的结果与在完整数据集上的结果相同，但完成时间大大减少。例如，开关可以通过删除一些重复项来加速不同的查询，并让主服务器删除其余的而不是所有的查询。基于剪枝技术，已经为其他更复杂的查询开发了额外的算法，如JOIN和组BY。
许多查询的处理需要排序，要么是因为查询显式地请求一个已排序的答案，要么是为了大大加快复杂操作符的执行。例如，众所周知，如果两个关系都是排序[16]，JOIN可以在线性时间内实现。排序是一个研究得很好的问题，并且已经提出了许多解决方案，如，快速排序，气泡排序，桶排序和更多的[12]。在数据库领域，合并排序是一种非常流行的算法，因此是我们研究的重点。
3.关于问题的陈述和解决方法
如前所述，许多数据库查询都需要排序，而排序是一项CPU密集型的任务。我们的目标是通过使用可编程开关的电源对服务器的输入进行预处理来加速排序。由于合并排序，我们关注它在数据库中的流行。为了完整起见，我们首先重新介绍合并排序算法，然后提供关于可编程开关可能如何提供帮助的直觉。
资料编号：[588115]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
