Accelerating Data Chunking in Deduplication Systems using Vector Instructions DOI: XXXXXXX.XXXXXXX CCS: Information systems Cloud based storage CCS: Networks Cloud computing CCS: Information systems Deduplication CCS: Computer systems organization Single instruction, multiple data

Sreeharsha Udayashankar, Abdelrahman Baba, Samer Al-Kiswany · 2025

Read Accelerating Data Chunking in Deduplication Systems using Vector Instructions DOI: XXXXXXX.XXXXXXX CCS: Information systems Cloud based storage CCS: Networks Cloud computing CCS: Information systems Deduplication CCS: Computer systems organization Single instruction, multiple data by Sreeharsha Udayashankar, Abdelrahman Baba, Samer Al-Kiswany (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-05797.txt.

Introduction

Sreeharsha Udayashankar, Abdelrahman Baba, and Samer Al-Kiswany present a 2025 paper on faster data storage. Deduplication systems save space by storing each chunk of data once. Content-defined chunking picks the chunk borders by scanning each file in full. That scan is slow and often the main bottleneck. Hashless chunking methods rely on two scan patterns: hunting extreme bytes and scanning ranges.

Their method, called VectorCDC, speeds both patterns with vector CPU commands. Those commands work on many bytes at once. Three top hashless methods were sped up with the approach. Gains ran from about eight to twenty-six times base speed across Intel, AMD, ARM, and IBM chips. Storage teams get chunking that keeps its space savings without eating the compute budget. Faster scans lift the whole backup and archive pipeline.

Catalog record

CREATORSreeharsha Udayashankar, Abdelrahman Baba, Samer Al-Kiswany
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-05797

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Accelerating Data Chunking in Deduplication Systems using Vector Instructions DOI: XXXXXXX.XXXXXXX CCS: Information systems Cloud based storage CCS: Networks Cloud computing CCS: Information systems Deduplication CCS: Computer systems organization Single instruction, multiple data Sreeharsha Udayashankar, Abdelrahman Baba, Samer Al-Kiswany Abstract . Content-defined Chunking (CDC) algorithms dictate the overall space savings that deduplication systems achieve. However, due to their need to scan each file in its entirety, they are slow and often the main performance bottleneck within data deduplication. We present VectorCDC, a method to accelerate hashless CDC algorithms using vector CPU instructions, such as SSE / AVX. Our evaluation shows that VectorCDC is effective on Intel, AMD, ARM, and IBM CPUs, achieving 8.35 × − 26.2 × 8.35\times-26.2\times higher throughput than existing vector-accelerated techniques without affecting the deduplication space savings. 1. Introduction The amount of data generated and stored on the Internet is growing at an exponential rate ( statista2024 ) , and is expected to exceed 180 zettabytes per year in 2025. Storage capacity alone is not well positioned to handle this data influx, with the total installed storage capacity in 2020 only being 6.7 zettabytes ( statista2024 ) . Cloud storage providers instead support this data growth using alternatives such as novel storage paradigms ( software_defined_storage ; raid ) , distributed file systems ( hadoop ; ceph ) and caches ( memcached ; facebook_tao ) , mechanisms such as data deduplication ( dedup_intro ; comprehensive_dedup ) , alongside additional investments in data protection ( data_security ) . Previous studies by Microsoft ( primary_dedup ) and EMC ( backup_workload_charz ) show that a large amount of redundancy exists in the data stored on the cloud, especially in file system backups ( primary_dedup ; dedup_intro ) , virtual machine backups ( backup_workload_charz ; wandeltacomp ) and shared documents ( documentduplication_2011 ) . The redundancy ratios in these workloads are significant, ranging from 50\% to 75\% . Mechanisms such as data deduplication ( dedup_intro ) and compression ( wandeltacomp ) are used to conserve storage space by identifying redundant data, eliminating it, and minimizing its storage impact, thereby improving efficiency and reducing costs. Data deduplication consists of four phases ( comprehensive_dedup ) ; Data Chunking , Chunk Fingerprinting , Metadata Creation , and Data Storage . Data chunking and chunk fingerprinting are the most computationally intensive ( dedup_intro ; dedupbench ) of these. While chunk fingerprinting has received significant optimization attention, with faster hashing algorithms ( tunable_encrypted_dedup ; scalable_incremental_checkpt ) and GPUs ( gpu_dedup ; storegpu ) , data chunking optimizations have not kept up (§ 3.1 ). In the data chunking phase, the incoming data is divided into small chunks, typically of size 1-64 KB. Numerous data chunking algorithms exist in current literature ( ae ; fastcdc ; gear_hash ; lbfs ; ram ; tttd ) and can be broadly classified into hash-based and hashless algorithms ( dedupbench ) . As chunking occurs whenever new data is uploaded, this phase is on the critical path, and directly impacts system performance. Previous efforts explored accelerating chunking through using vector instructions. SS-CDC ( sscdc ) uses vector instructions to accelerate hash-based data chunking algorithms, such as Rabin-Karp chunking ( lbfs ) and Gear-based chunking ( gear_hash ) . Unfortunately, this approach only leads to modest improvements in chunking throughput, up to 3.13\times , as shown in § 3.2 . Parallelizing hash-based chunking using vector instructions is complicated because these algorithms use the rolling hash of a sliding window of bytes to detect boundaries, inherently creating a computational dependency between adjacent bytes. Consequently, SS-CDC processes different regions of the data in parallel. This approach relies on slow scatter / gather vector instructions, limiting its performance (§ 3.2 ). We posit that hashless chunking algorithms are better candidates for vector acceleration. Although they achieve slightly lower space savings compared to their hash-based counterparts (§ 6 ), they are up 2\times faster and use simple mathematical operations (e.g., finding a maximum value) that can be accelerated more efficiently using vector instructions. We analyzed state-of-the-art hashless algorithms to understand their design and identify opportunities to leverage vector instructions. We identified that all state-of-the-art hashless algorithms consist of two processing patterns. The first pattern involves finding local minima or maxima in a data region, which we call Extreme Byte Search , and the second pattern involves scanning a range of bytes to find values that are greater or lesser than a target value, which we call Range Scan . We found that, unlike rolling hash functions, these patterns can be efficiently accelerated using vector instructions. Using these insights, we present VectorCDC, a technique for accelerating hashless chunking algorithms using vector instructions. VectorCDC uses a novel design to accelerate the two aforementioned patterns. We accelerate the extreme byte searches with a novel tree-based search that divides a region of bytes into multiple sub-regions, processes each region using vector instructions, and uses a tree-based approach to combine their results. We accelerate range scans with packed scanning , which packs multiple adjacent bytes into vector registers and compares them using a single vector operation. We implemented VectorCDC using five different vector instruction sets: SSE-128, AVX-256, and AVX-512 on Intel / AMD CPUs; NEON-128 on ARM CPUs; and VSX-128 on IBM Power CPUs. We used VectorCDC to accelerate three state-of-the-art hashless chunking algorithms. We implemented VRAM , VAE , and VMAXP , which are accelerated versions of the RAM ( ram ) , AE ( ae ) , and MAXP ( maxp ) algorithms, respectively. We compared the performance of our accelerated algorithms against state-of-the-art hash-based algorithms, hashless algorithms, and SS-CDC ( sscdc ) accelerated algorithms using 10 diverse datasets. Our evaluation (§ 6 ) shows that VectorCDC achieves 8.35\times – 26.2\times higher chunking throughput than SS-CDC’s approach, without affecting the space savings achieved by hashless algorithms. VectorCDC-based algorithms achieve up to 5.51\times – 17.6\times higher throughput compared to their unaccelerated counterparts. Furthermore, algorithms accelerated using VectorCDC retain their performance advantage with all five vector instruction sets. We have made our code publicly available by integrating it with DedupBench 1 1 1 https://github.com/UWASL/dedup-bench ( dedupbench ) . Due to the large sizes of our datasets (§ 6 ), we were unable to release them all. We have instead provided detailed descriptions to facilitate their recreation for future experiments, similar to previous literature ( fastcdc ; ae ; ram ) . In addition, to facilitate reproducing our results, we have publicly released one of our datasets ( DEB ) on Kaggle 2 2 2 https://www.kaggle.com/datasets/sreeharshau/vm-deb-fast25 ( deb_dataset ) . The rest of this paper is organized as follows: we discuss relevant background about deduplication and vector instructions in Section 2 . Section 3 motivates our work by discussing deduplication performance bottlenecks and the inefficiencies encountered by previous work when accelerating hash-based CDC algorithms. Section 4 outlines VectorCDC’s design while Section 6 details our evaluation efforts on diverse datasets. We discuss related work in Section 7 and conclude our paper in Section 8 . 2. Background Data deduplication consists of four phases ( comprehensive_dedup ) : • Data Chunking : Data is divided into small chunks typically of size 1-64 KB using a chunking algorithm. All chunking algorithms have configurable parameters that control

Read the complete text