专栏首页arxiv.org翻译专栏通过可编程开关加速大数据排序(CS DB)

通过可编程开关加速大数据排序(CS DB)

排序是一个已深入研究的基本问题,已经得到了广泛的研究。排序在数据库领域起着重要作用,因为如果首先对关系进行排序,则可以更快地处理许多查询。数据库中最流行的排序算法之一是合并排序。 在现代数据中心中,数据存储在存储服务器中,而处理则在计算服务器中进行。因此,为了计算对数据的查询,它必须通过网络从存储服务器传播到计算服务器。这为利用可编程开关执行部分分类以加速服务器端的分类过程创造了潜力。这是可能的,因为如上所述,无论如何,数据包在到达服务器的任何情况下都将通过交换机。遗憾的是,可编程开关提供了非常严格且非直观的编程模型,这就是为什么要实现这一目标并不容易。

我们设计了一种新颖的部分排序算法,该算法适合编程模型和可编程交换机的限制,并且可以加快服务器上的合并排序。我们还利用交换机中的内置并行性将数据划分为连续范围。因此,服务器需要分别对每个范围进行排序,然后将它们串联为一个排序的流。这样,服务器需要对较小的部分进行排序,并且这些部分中的每个部分都已经部分排序。因此,服务器的工作量减少了,访问模式变得对虚拟内存更友好。

我们评估了在不同开关配置的几种数据流组合中使用我们的部分排序算法时获得的性能改进。与使用原始方法进行普通分拣相比,使用我们的方法时,我们的研究显示分拣运行时间提高了20%-75%。

原文题目:Accelerating Big-Data Sorting Through Programmable Switches

原文: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.

原文链接:https://arxiv.org/abs/2103.14071

原文作者:Yamit Barshatz-Schneor, Roy Friedman

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis应用及安装

    Redis听到最多的一句话就是Redis的使用难吗?不难,Redis用好容易吗?不容易,有时候觉得这句话说的挺好,但又是让读者挺心里咯噔一下的,还不如不说! 概...

    牛嗷嗷
  • 某大厂游测开懵逼面试精选四题

    TCP的可靠性体现在传输数据之前,三次握手建立连接(四次挥手释放连接),并且在数据传递时,有确认、窗口、重传、拥塞控制机制,数据传完之后,断开连接用来节省系统资...

    测试小兵
  • 奖学金评分系统(系统分析与设计版与Delphi实现代码)

    在奖学金评比过程中,学生综合测评是学校普遍采用的评比手段。对学生实施综合素质测评的目的在于正确评价学生的综合素质,为评奖学金提供依据,实现学生教育管理工作的标准...

    用户1621453
  • 如何高效的进行腾讯云上的资源编排,一起来聊一聊Terraform

    “腾讯云IaC最佳实践”系列文章希望通过介绍Terraform、Chef和Ansible等生态产品工具及相关案例,使用户能够更好地在腾讯云上实践IaC,为腾讯云...

    生态产品团队
  • 16位汇编第三讲 分段存储管理思想

          内存分段 一丶分段(汇编指令分段) 1.为什么分段?   因为分段是为了更好的管理数据和代码,就好比C语言为什么会有内存4区一样,否则汇编代码都写...

    IBinary
  • 汇编基础

    ​ cup与所有内存之间:地址总线,数据总线,控制总线,每条线对应不同信息,指令与数据分开

    Dean0731
  • x86汇编语言之8086语法和指令集

    上面使用db或者dw定义数据的方式,定义数据的同时就已经定义好了数据所在的物理地址, 如果我们想要从指定的内存地址中写入或者读取数据的话,需要借助段寄存器来实现...

    乱码三千
  • 8086汇编语言之代码分段

    以上代码存在一个问题, 由于数据是在代码段中定义, cpu默认将数据识别为代码, 将导致数据不可用,那么解决办法为,增加入口标记:

    乱码三千
  • 商业渗透工具 Core impact 初探

    关于 Core impact (就是收购 CS 的那家公司的产品)稍微介绍一下吧,Core impact 简单来说就是一款商业渗透测试工具,它不同于普通的RAT...

    信安之路
  • 史上最全分布式数据库概述

    墨墨导读:在集中式数据库系统不能完全符合实际需要的形势下,集中式DB的“集中计算”概念向“分布计算”概念发展。分布计算主要体现在客户机/服务器模式的分布式数据库...

    数据和云
  • 数据库课程设计指南(BS or CS 及所需知识储备)

    •B/S架构的全称为Browser/Server,即浏览器/服务器结构。Browser指的是Web浏览器,无须特别安装

    种花家的奋斗兔
  • 双活数据中心建设-应用层双活设计(part-1)

    根据应用的工作模式来划分将应用分为B/S类(浏览器/服务器模式)、C/S类(客户端/服务器模式)。

    ICT售前新说
  • 未整理的计组复习笔记?

    计组是我听过的最脑阔疼的课。不过已经考过了orz以及,大家学的计组内容可能不一样,这篇复习包括的内容应该是比较简略的。

    gojam
  • 《汇编语言》课程设计2

    jz指令:https://zhidao.baidu.com/question/564008138.html

    Hk_Mayfly
  • C/S和B/S两种架构的概念、区别和联系

    这篇文章主要介绍了C/S和B/S两种架构的概念、区别和联系,本位还同时讲解了主流的Web程序应用平台、Web工作原理等内容,需要的朋友可以参考下

    习惯说一说
  • Go语言技巧 - 7.【GORM实战剖析】基本用法和原理解析

    GORM库作为Go语言最受欢迎的ORM框架,提供了非常丰富的功能,大家可以通过阅读中文官网的相关介绍。

    junedayday
  • C/S和B/S两种架构区别与优缺点分析

    C/S和B/S,是再普通不过的两种软件架构方式,都可以进行同样的业务处理,甚至也可以用相同的方式实现共同的逻辑。既然如此,为何还要区分彼此呢?那我们就来看看二者...

    IT大咖说
  • 汇编笔记

    1)、MOV BL, CX: 可行但mov的源比目标长度大,会导致数据丢失。警告:Operand types must match

    饶文津
  • GitHub 标星 5w+,计算机小白到大牛的学习之路!

    计算机科学一直是近年来高考报考的热门专业,是一门研究计算机相关规律的学科。近年来,随着开源社区的蓬勃发展,以及人工智能对各行各业的影响,很多人希望能够通过系统全...

    五分钟学算法

扫码关注云+社区

领取腾讯云代金券