实验室一项成果(BPart)被系统领域会议ICPP接收

我们实验室的自主完成的两个维度均衡的图划分算法BPart被计算机系统领域会议ICPP(CCF B类)收录。
论文:

论文题目:Towards Fast Large-scale Graph Analysis via Two-dimensional Balanced Partitioning

论文摘要:

分布式图计算系统需要将一个大图划分为多个子图,并将这些子图加载到集群中不同机器中进行计算。子图划分的好坏会极大的影响分布式图计算系统的计算效率。比如划分的均衡性(包括节点和边两个维度均衡)会极大影响分布式图计算的负载均衡;划分跨子图边数量会极大影响分布式图计算的通信开销。然而当前分布式图计算系统中采用的图划分算法通常只能实现节点均衡或者边均衡,或者能够实现两个维度均衡的算法,其跨子图边数量非常多。因此,在进行子图划分时,需要保证节点和边都划分均衡的同时尽可能地减小跨子图边地数量。

在本文中,我们提出保证节点和边两个维度均衡的划分算法BPart。他的核心思想是,首先将大图划分为多个小的子图,其数量远大于集群中机器的数量,并且在划分时通过设计复合的均衡性指标,使得每个子图中节点和边数量满足反比的关系;然后将这些小的子图按照节点或者边数量排序,并头尾组合为一个大的子图。通过多次的组合,BPart可以实现两个节点和边两个维度的划分均衡。我们将BPart集成到两个当前最优的分布式图处理系统KnightKing和Gemini中,并研究他们在执行图算法时的计算效率。通过实验对比,采用BPart作为划分策略可以减小不同图算法5%-70%的运行时间。

实验室一项成果(Optimal-LRC)被系统领域会议ICPP接收

我们实验室的自主完成的针对最优局部可恢复码(Optimal-LRC)的最优放置策略被计算机系统领域会议ICPP(CCF B类)收录。向各位参与研究工作的老师、同学表示祝贺。

论文题目:Repair-Optimal Data Placement for Locally Repairable Codes with Optimal Minimum Hamming Distance

论文摘要:

现代集群存储系统越来越多地采用纠删码来实现低冗余高可靠的数据存储。局部可恢复码(LRC)是一种在实际系统中被广泛应用的具有高恢复性能的纠删码。在各种LRC的构造中,Optimal-LRC是一种最近被提出的LRC构造,它能达到最优的最小汉明距离,同时恢复代价很低。Optimal-LRC将存储块划分成若干个局部组,并在每个组内增加一个局部校验块,使得任意单个块的恢复都能在一个组内完成。然而,Optimal-LRC在实际存储系统中的恢复性能如何仍是未知的。

在本文中,我们考虑Optimal-LRC在实际集群存储系统中的恢复问题。由于单个存储块的失效概率远高于多个存储块的失效概率,我们考虑单个块的恢复。我们发现传统的扁平数据放置和随机数据放置会在恢复过程中跨集群传输大量的数据,严重降低了数据恢复性能。因此,我们基于Optimal-LRC的容错能力,通过将每一个组的块放置于最少量的集群中,设计了一个最优的数据放置方案。该放置方案可以在保障容单集群故障的条件下,最小化单个块在恢复时所需的跨集群网络带宽。本文进一步在 Memcached上实现了一个基于Optimal-LRC的集群存储系统原型,并验证了本文放置方案的有效性。实验表明,相较于扁平放置和随机放置,最优放置方案可以将降级读时间分别降低83.3%和68.9%,并将恢复吞吐量分别提升7.7倍和5.6倍。

实验室一项成果(SelectiveEC)被计算机存储系统领域顶级期刊(TPDS)接收

我们实验室在纠删码存储系统中设计修复流量调度算法的工作被计算机存储系统领域顶级期刊IEEE Transactions on Parallel and Distributed Systems(TPDS, CCF A类)接收。向各位参与研究工作的老师、同学表示祝贺。

论文题目:SelectiveEC: Towards Balanced Recovery Load on Erasure-coded Storage Systems.

纠删码 (EC) 以低存储成本提供高数据可靠性。当发生故障时,批量修复丢失的数据块。由于故障修复任务分批进行,一批内的修复数据分布不均衡,另外随机选择修复任务的源节点和替待节点,使得修复任务在一批内负载不均衡,这严重减慢了故障修复速度。为了解决这个问题,我们提出了SelectiveEC,这是一种新的修复任务调度模块,可为基于 EC 的大规模存储系统提供可证明的网络修复流量的负载平衡。它依赖于二部图来构造修复任务与幸存节点之间的图模型,然后使用完美或最大匹配等理论,并仔细确定地读取幸存块或存储修复块的节点,动态地选择任务以形成批处理。 SelectiveEC支持单节点故障和多节点故障修复,可以部署在同构和异构网络环境中。我们在HDFS中实现SelectiveEC,并在18节点的本地集群和50个虚拟机实例的AWS EC2中评估其修复性能。与同类网络环境中的最先进方法相比,SelectiveEC 将修复吞吐率提高了30.68%。由于均衡调度避免了重构时的掉队任务,它进一步实现了在异构网络环境中传统方法的1.32倍修复吞吐率。

实验室一项成果(DEPART)被存储领域顶级会议 FAST22 接收

经过持续两年的努力,我们ADSL实验室和香港中文大学Patrick P. C. Lee教授合作的DEPART被计算机存储系统领域顶级国际会议 FAST 2022 (CCF A类) 收录。向各位参与研究工作的老师、同学、合作者表示祝贺。

这项研究工作主要利用解耦的思想对分布式键值系统的多副本加剧I/O放大问题进行优化。在基于LSM-tree的分布式键值系统中,为了保证数据的高可靠并容错,多副本机制被广泛应用。然而,已有键值系统都采用统一的LSM-tree索引,对节点上的多副本数据进行统一存储,这会极大地加剧系统的读写放大。因此,我们首次提出在存储层对多副本数据进行解耦的思想,并设计差异化和有序度可调的存储结构进行管理,从而有效降低分布式键值系统的读写放大,并向用户提供可调的读写性能。

近年来,在ADSL实验室负责人许胤龙教授的带领下,我们实验室在计算机系统特别是在健值存储系统方向有了长期稳定的积累,已经连续两年在存储系统领域顶级国际会议 FAST发表键值存储方向的研究成果(在FAST21发表SpanDB),说明ADSL实验室的科研实力向着更高水平迈进。

此项工作得到了国家自然科学基金重点项目、科技部重点研发课题、双一流学科建设的资助,得到了国家高性能计算中心(合肥)、安徽省高性能计算重点实验室的平台支持!

论文题目:DEPART: Replica Decoupling for Distributed Key-Value Storage

论文摘要:Modern distributed key-value (KV) stores adopt replication for fault tolerance by distributing replicas of KV pairs across nodes. However, existing distributed KV stores often manage all replicas in the same index structure, thereby leading to significant I/O costs beyond the replication redundancy. We propose a notion called replica decoupling, which decouples the storage management of the primary and redundant copies of replicas, so as to not only mitigate the I/O costs in indexing, but also provide tunable performance. In particular, we design a novel two-layer log that enables tunable ordering for the redundant copies to achieve balanced read/write performance. We implement a distributed KV store prototype, DEPART, atop Cassandra. Experiments show that DEPART outperforms Cassandra in all performance aspects under various consistency levels and parameter settings.

实验室一项成果被INFOCOM 2022收录

论文题目:Optimal Data Placement for Stripe Merging in Locally Repairable Codes.

论文摘要:纠删码技术因具备优秀的存储性能而被广泛部署于当今集群存储系统中。纠删码将数据存储为数量众多的条带;每个条带包含数据块和校验块,并被放置于多个机架的多个物理节点上。在众多种纠删码策略中,局部可修复码(LRC)是一类被广泛采用的、具有高效修复性能的纠删码。为了有效响应业务负载的动态性能和可靠性需求,存储系统需要对纠删码数据进行容错转换,即改变纠删码的编码参数,以实现不同的访问性能和数据可靠性。因此,如何提高LRC码的容错转换性能,是一类非常重要的问题。
在本文中,我们采用条带合并的方式来实现LRC码的容错转换,即通过合并多个小的LRC条带,形成一个大的LRC条带。通过条带合并,系统可以实现更高的存储效率及更高的可靠性。然而,我们指出,多个小LRC条带的随机放置策略,会在容错转换时引起巨大的跨机架网络负载。因此,我们基于LRC码的节点与机架级别容错能力,通过仔细决定哪些小条带的数据需聚集于同一机架、哪些数据需分散于多个机架,进而为多个小LRC条带设计了一个最优放置方案。该放置方案在容错转换时可以实现最小化的跨机架网络传输开销,同时也维持了转换前后的修复效率。本文进一步设计实现了一个基于LRC码的集群存储系统原型,并验证了本文放置方案的有效性。实验表明,相较于随机放置策略,最优放置方案能将容错转换时间减小43.2%。

实验室一项成果(SpanDB)被存储领域顶级期刊(ACM TOS)接收

我们实验室在基于混合存储介质优化LSM-tree键值存储的工作被存储领域顶级期刊ACM TOS (CCF推荐A类)接收。向各位参与研究工作的老师、同学、合作者表示祝贺。

论文题目:Leveraging NVMe SSDs for Building A Fast, Cost-EffectiveLSM-tree Based KV Store

论文摘要:Key-Value (KV) stores support many crucial applications and services. They perform fast in-memory process-ing, but are still often limited by I/O performance. The recent emergence of high-speed commodity NVMeSSDs has propelled new KV system designs that take advantage of their ultra-low latency and high bandwidth.Meanwhile, to switch to entirely new data layouts and scale up entire databases to high-end SSDs requiresconsiderable investment.As a compromise, we propose SpanDB, an LSM-tree-based KV store that adapts the popular RocksDB sys-tem to utilizeselective deployment of high-speed SSDs. SpanDB allows users to host the bulk of their data oncheaper and larger SSDs (and even HDDs with certain workloads), while relocating write-ahead logs (WAL)and the top levels of the LSM-tree to a much smaller and faster NVMe SSD. To better utilize this fast disk,SpanDB provides high-speed, parallel WAL writes via SPDK, and enables asynchronous request processingto mitigate inter-thread synchronization overhead and work efficiently with polling-based I/O. To ease thelive data migration between fast and slow disks, we introduce TopFS, a stripped-down file system provid-ing familiar file interface wrappers on top of SPDK I/O. Our evaluation shows that SpanDB simultaneouslyimproves RocksDB’s throughput by up to 8.8×and reduces its latency by 9.5-58.3%. Compared with KVell, a system designed for high-end SSDs, SpanDB achieves 96-140% of its throughput, with a 2.3-21.6×lowerlatency, at a cheaper storage configuration.

实验室一项成果被SOSP2021收录

经过持续三年多的努力,我们ADSL实验室与美国内华达大学的颜枫教授(今年获得NSF CAREER Award)带领的IDS实验室、德国贝尔实验室陈瑞川博士合作完成的HiPress系统被计算机系统领域国际顶会——第28届“ACM操作系统原理大会”(SOSP: ACM Symposium on Operating Systems Principles)收录,向各位参与研究工作的老师、同学、合作者表示祝贺。

在此项研究中,我们关注深度神经网络模型大规模数据并行训练的可扩展性问题。我们通过高效GPU梯度压缩算法自动化生成、压缩感知的梯度聚合协议、代价模型驱动的梯度选择性压缩和分片机制等优化方法,搭建了支持各类梯度压缩算法的高性能数据并行训练框架,横向兼容MXNet、TensorFlow、PyTorch等主流深度学习系统。最终,在业界常用模型上的训练速度相较最新系统有较为明显的性能提升,具有较高的实际应用潜力。

SOSP与OSDI并称为计算机系统领域的最高水平学术会议,两年召开一次,已有54年的悠久历史。本次SOSP大会共有348篇论文投稿,54篇被接收,接收率为15.5%,竞争十分激烈。大会将于10月25日至28日召开,本实验室博士生白有辉将代表参研师生向国内外同行介绍相关成果。

近年来,在实验室负责人许胤龙教授的带领下,在李诚特任研究员、李永坤副教授、吕敏副教授、吴思特任副研究员和诸多实验室同学的共同努力下,ADSL实验室在并行与分布式机器学习系统方向有了深入的认识和长期稳定的积累,这项工作的发表,标志着我们在该领域的认识和积累被国际领域认可,标志着我们实验室的科研水平迈入更高的层次。

此项工作得到了国家自然科学基金重点项目、青年项目、科技部重点研发课题、双一流学科建设、111协同创新、合肥市留学回国人员创新计划的资助,得到了国家高性能计算中心(合肥)、安徽省高性能计算重点实验室、超算中心、亚马逊云计算的平台支持。

论文题目:Gradient Compression Supercharged High-Performance Data Parallel DNN Training

论文摘要:Gradient compression is a promising approach to alleviating the communication bottleneck in data parallel deep neural network (DNN) training by significantly reducing the data volume of gradients for synchronization. While gradient compression is being actively adopted by the industry (e.g., Facebook and AWS), our study reveals that there are two critical but often overlooked challenges: 1) inefficient coordination between compression and communication during gradient synchronization incurs substantial overheads, and 2) developing, optimizing, and integrating gradient compression algorithms into DNN systems imposes heavy burdens on DNN practitioners, and ad-hoc compression implementations often yield surprisingly poor system performance.

In this paper, we first propose a compression-aware gradient synchronization architecture, CaSync, which relies on a flexible composition of basic computing and communication primitives. It is general and compatible with any gradient compression algorithms and gradient synchronization strategies, and enables high-performance computation-communication pipelining. We further introduce a gradient compression toolkit, CompLL, to enable efficient development and automated integration of on-GPU compression algorithms into DNN systems with little programming burden. Lastly, we build a compression-aware DNN training framework HiPress with CaSync and CompLL. HiPress is open-sourced and runs on mainstream DNN systems such as MXNet, TensorFlow, and PyTorch. Evaluation in a 16-node cluster with 128 NVIDIA V100 GPUs and 100Gbps network shows that HiPress improves the training speed up to 106.4% over the state-of-the-art across six popular DNN models.

实验室一项成果被计算机存储领域期刊TC接收

我们实验室在纠删码存储系统中设计均匀数据布局以及高效故障修复算法的工作被计算机存储系统领域顶级期刊IEEE Transactions on Computers(TC, CCF A类)接收。向各位参与研究工作的老师、同学表示祝贺。

论文题目:A Data Layout and Fast Failure Recovery Scheme for Distributed Storage Systems with Mixed Erasure Codes.

论文摘要:纠删码在分布式存储系统(DSS)中变得越来越流行,以提供高可靠性和低存储开销。然而,传统的随机数据放置在故障修复过程中会导致大量的跨机架流量和严重的负载不平衡,这显着降低了修复性能。此外,在DSS中并存的各种纠删码加剧了上述问题。在本文中,我们提出了基于PBD的数据布局 PDL,以优化DSS中的故障修复性能。PDL是基于Pairwise Balanced Design构建的,这是一种具有均匀数学特性的组合设计方案,从而为混合纠删码呈现统一的数据布局。接着我们提出了rPDL,一种基于PDL的故障修复方案。rPDL通过均匀地选择替换节点和检索确定的可用块来修复丢失的块,有效地减少了跨机架流量并提供了几乎均衡的跨机架流量分布。
我们在 Hadoop 3.1.1中实现了PDL和rPDL。与HDFS中现有的数据布局和修复方案相比,rPDL实现了更高的修复吞吐量:单节点故障修复速率为6.27倍,多节点故障修复速率为5.14倍以及单机架故障修复速率为1.48倍。它还将退化读延迟平均降低了62.83%,并在节点故障的情况下为前端应用程序提供了更好的支持。

实验室一项成果(DR-RAID)被系统领域会议ICPP接收

我们实验室自主完成的基于RAID2.0的大规模磁盘阵列的快速修复算法被计算机系统领域会议ICPP(CCF B类)收录。向各位参与研究工作的老师、同学表示祝贺。

论文题目:Fast Reconstruction for Large Disk Enclosures Based on RAID2.0

论文摘要:
随着数据的爆炸式增长,越来越多的企业使用RAID2.0来提供大容量的数据存储。由于内存、CPU、磁盘带宽等资源的限制,当RAID2.0中发生磁盘故障时,数据重构一般是分批进行的。RAID2.0中随机数据布局和重构方案使得在每一批修复的IO负载在幸存磁盘上的分布是不均衡的。这种方式极大地降低了数据重构的速度。为了解决这个问题,我们提出了一种快速修复算法DR-RAID,能够有效地避免在重构过程中IO负载不均衡的情况。相比于在RAID2.0中顺序的执行待重构的任务,DR-RAID动态的从所有的待重构任务中选择一批有着均衡读负载的任务。同时,我们将重构数据分布到幸存磁盘的问题转换为一个二分图模型,并通过在二分图模型中找最大匹配的方式实现了写负载的均衡分布。此外,DR-RAID可以应用在同构和异构的重构带宽的场景中。与目前RAID2.0中的的重构方案进行实验相比,DR-RAID在离线修复中最大能够提升61.90%的重构吞吐量,在变化重构带宽的场景下最大能够提升59.28%的重构吞吐量。DR-RAID能够在不依赖数据布局的情况下有效地消除数据重构过程中局部的IO负载不均衡,极大地缩短了重构负载对用户请求的干扰时间。

实验室一项成果(PMA)被系统领域会议ICPP接收

我们实验室的自主完成的虚拟化环境中的动态内存调节原型系统被计算机系统领域会议ICPP(CCF B类)收录。向各位参与研究工作的老师、同学表示祝贺。

论文题目:Progressive Memory Adjustment with Performance Guarantee in Virtualized Systems

论文摘要:
在虚拟化环境中,多个虚拟机之间共享主机的各种资源(如内存、CPU等)。为了工作负载的动态变化,虚拟机中的应用程序通常申请比实际使用更多的内存来应对峰值内存需求,因此通过回收虚拟机中的非活跃内存来调整系统内存资源的分配是实现内存超卖的有效方法并且可以有效降低成本。然而,现有的方案是基于一次性调整设计的,可能在一次操作中会回收虚拟机较多的内存,并且现有方案不能感知应用程序的访存动态性以及内存敏感性,因此通常会导致过度回收虚拟机的内存并导致其性能严重下降。为了解决这个问题,我们提出了 PMA,一种渐进式内存调节方案,它同时考虑了虚拟机(包括其中的应用程序)的访存动态性和内存敏感性,并利用性能反馈逐步回收虚拟机的非活跃内存以尽量避免性能损失。此外,PMA 是基于ballooning(即balloon driver)设计的,因此它能够保证虚拟机和主机之间的隔离性。我们还在主机的用户空间实现了原型系统,实验表明 PMA 有效地限制了内存超卖情况下虚拟机的性能下降(例如,在内存超卖率高达 33%时每个虚拟机的性能损失在 10% 以内),这已经是非常接近最佳的效果(即每个虚拟机都拥有足够内存时的性能),因此 PMA 可以有效地在全虚拟化系统中兼顾内存超卖和虚拟机的性能。