Extension of LZ4 compression algorithm for handling scatter-gather buffers in the Linux kernel block layer

Extension of LZ4 compression algorithm for handling scatter-gather buffers in the Linux kernel block layer

Bugaev A.S. (SPBU, St. Petersburg, Russia)
Sichkar G.K. (SPBU, St. Petersburg, Russia)
Vasenina A.I. (SPBU, St. Petersburg, Russia)

Abstract

Block-level storage systems commonly use lossless compression to save disk space. In the Linux kernel block layer, I/O request data is represented by an array of data structures called block I/O vectors (bvecs). A single vector stores a contiguous chunk of data. Data of multiple vectors is commonly scattered in memory. Optimal compression ratio is achieved by compressing all the data in a single run. The current implementation of LZ4 compression algorithm requires contiguous buffers. Therefore, for the best compression all request data must be copied into a large enough preallocated buffer. In this paper we propose a way of compressing all the data of block layer I/O request in a single run without any additional buffer allocation and data copying. The proposed method adapts Linux kernel implementation of LZ4 algorithm to use bvec iterators to navigate through buffers of I/O requests. The performance of the proposed approach was tested in comparison to other applications of LZ4 in the block layer: copying to preallocated buffer, compressing bvecs individually. As a result, our modification achieves the highest compression ratio along with the copy-based approach. Compared to copy-based approach, proposed solution reduces memory usage roughly in half. Overall, extended LZ4 requires the least memory, as well as per-bvec compression. These advantages come at a cost of throughput, which becomes 2–6 times lower compared to other approaches. The obtained profiling metrics show that the throughput reduction is caused by a substantial increase in total number of instructions – up to 10 times. No obvious bottlenecks were found within the algorithm. The performance issue is to be addressed by finding a way to simplify the required calculations. Evaluation results show that our approach is better suited for offline compression and memory-constrained environments.

Keywords

Lossless data compression; transparent compression; Linux kernel block layer; storage efficiency.

Edition

Proceedings of the Institute for System Programming, vol. 38, issue 6, part 1, 2026, pp. 279-298

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2026-38(6)-18

For citation

Bugaev A.S., Sichkar G.K., Vasenina A.I. Extension of LZ4 compression algorithm for handling scatter-gather buffers in the Linux kernel block layer. Proceedings of the Institute for System Programming, vol. 38, issue 6, part 1, 2026, pp. 279-298 DOI: 10.15514/ISPRAS-2026-38(6)-18.

Full text of the paper in pdf Back to the contents of the volume