Merging identical data from the memory pages compressed with the Linux kernel module

Authors: Romanov A.V.
Published in issue: #7(84)/2023
DOI: 10.18698/2541-8009-2023-7-923
Category: Informatics, Computer Engineering and Control | Chapter: System Analysis, Control, and Information Processing, Statistics
Keywords: operating systems, Linux kernel, memory management, zram, data compression, data deduplication, algorithms, data structures, block devices, zsmalloc
Published: 31.07.2023

The article is devoted to optimizations in the Linux kernel memory management subsystem. Main concepts of memory management in the Linux kernel are briefly described. Data structures and operation algorithm of the zram kernel module responsible for compressing the RAM pages are presented. An algorithm was developed for combining the RAM pages containing the identical data, which were previously compressed by the Linux kernel corresponding module. Results of the developed algorithm operation were analyzed on various processor architectures and on different input data. Based on the study results, it was concluded that the developed method was ineffective for systems with a small amount of identical data (duplicate data was 1 % or less of the total system memory). Conversely, operation speed was increasing with a decrease in the zram kernel module RAM consumption for the systems containing repeated moderate data amount (duplicate data was 25 % or more of the total system memory).

References

[1] Khalid Sayood. Introduction to Data Compression. Amsterdam, Morgan Kaufmann, 2001, 680 p.

[2] Dan Feng. Overview of the Data Deduplication. Data Deduplcation of High Performance Storage System, 2022, pp. 9–23. http://doi.org/10.1007/978-981-19-0112-6_2

[3] Bovet D.P., Cesati M. Understanding the Linux Kernel. USA, O’Reilly Media, 2006. (Russ. ed.: Bovet D., Chezati M. Yadro Linux. Sankt-Petersburg, BKhV-Peterburg Publ., 2007, 217 p.).

[4] Love R. Linux Kernel Development. NJ, Addison-Wesley, 2010, 468 p. (Russ. ed.: Love R. Yadro Linux. Opisanie protsessa razrabotki. Moscow, Vil’yams Publ., 2013, 155 p.).

[5] Tanenbaum A.S., Bos H. Modern Operating Systems. Pearson Education, 2015, 1138 p. (Russ. ed.: Tanenbaum E., Bos Kh. Sovremennye operatsionnye sistemy. Sankt-Petersburg, Piter Publ., 2015, 845 p.).

[6] zram: Compressed RAM-based block devices. URL: https://docs.kernel.org/admin-guide/blockdev/zram.html (accessed April 15, 2023).

[7] zsmalloc. URL: https://docs.kernel.org/mm/zsmalloc.html (accessed April 15, 2023).

[8] Babenko M.A., Levin M.V. Vvedenie v teoriyu algoritmov i struktur dannykh [Introduction to the theory of algorithms and data structures]. Moscow, MTsNMO Publ., 2016, 47 p. (In Russ.).

[9] Romanov A. zram: introduce merge identical pages mechanism. URL: https://lore.kernel.org/all/20221121190020.66548-1-avromanov@sberdevices.ru/ (accessed April 15, 2023).