Sorting is a fundamental and well studied problem that has been studied extensively. Sorting plays an important role in the area of databases, as many queries can be served much faster if the relations are first sorted. One of the most popular sorting algorithm in databases is merge sort. In modern data-centers, data is stored in storage servers, while processing takes place in compute servers. Hence, in order to compute queries on the data, it must travel through the network from the storage servers to the compute servers. This creates a potential for utilizing programmable switches to perform partial sorting in order to accelerate the sorting process at the server side. This is possible because, as mentioned above, data packets pass through the switch in any case on their way to the server. Alas, programmable switches offer a very restricted and non-intuitive programming model, which is why realizing this is not-trivial. We devised a novel partial sorting algorithm that fits the programming model and restrictions of programmable switches and can expedite merge sort at the server. We also utilize built-in parallelism in the switch to divide the data into sequential ranges. Thus, the server needs to sort each range separately and then concatenate them to one sorted stream. This way, the server needs to sort smaller sections and each of these sections is already partially sorted. Hence, the server does less work, and the access pattern becomes more virtual-memory friendly. We evaluated the performance improvements obtained when utilizing our partial sorting algorithm over several data stream compositions with various switch configurations. Our study exhibits an improvement of 20%-75% in the sorting run-time when using our approach compared to plain sorting on the original stream.
翻译:排序是一个已经广泛研究过的基本和研究周密的问题。 排序在数据库领域扮演着重要的角色, 因为许多查询如果首先对关系进行排序, 可以更快地处理。 数据库中最受欢迎的排序算法之一是合并。 在现代数据中心, 数据存储在存储服务器中, 处理在计算服务器中进行。 因此, 为了计算数据查询, 它必须从存储服务器到计算服务器。 这为利用可编程开关来进行部分排序以加快服务器一侧的排序进程提供了潜力。 如上所述, 许多查询可以更快地处理。 这是因为, 数据库中最受欢迎的排序算法是合并。 数据库中最受欢迎的一个算法是合并。 在计算服务器时, 数据存储服务器的输入方式非常有限, 而处理程序开关则不那么简单。 我们设计了一个新的部分排序算法, 程序开关的配置模式和限制在计算服务器上可以加速合并排序。 我们同时使用内部的同步算法, 将数据转换为排序为顺序范围。 因此, 需要将每个服务器的运行范围分别用来排序,, 将数据排序到这些服务器的排序为排序范围 。