Document memory behaviour and give tips for dealing with many files

[nh2]

Hi,

I sometimes have the need to archive hundreds of millions of small files.

Lots of software fails on that with out-of-memory, for example:

• Out-of-memory when mksquashfs'ing 200M files plougher/squashfs-tools#238

It would be fantastic if somewhere in the mkdwarfs man page you could document its memory scaling behaviour.

For example:

• How does memory usage grow with the number of files, and their size?
  • E.g. expected needed RAM per 1M involved files
• Are there options that can affect this?
  • E.g. in some systems, you can turn off deduplication to get constant, streaming memory usage.
  • Similar with hardlink detection.
• Are there flags that can speed up the process?
  • For example, reading 100 files in parallel would drastically help on e.g. distributed, networked file systems over spinning disk, where a single IO might take 10 ms but it supports many of them in parallel. --num-scanner-workers looks like such an option, are there others recommended for the "many small files" use case?

As a quick benchmark, 500 k small files took 2 GB maxresident RAM for me with default options and --num-scanner-workers 100, on a 32-core machine.

--file-hash=none --max-similarity-size=0 --window-size 0 --memory-limit 100Mdid not significantly reduce it, but maybe that changes at higher scale.

But it is definitely curious that the used memory was 20x higher than the requested memory limit; its documentation says approximately, but this is a case that further motivates knowing what the other factors are in memory consumption.

It would be awesome if the scaling behaviour could be documented, so that one doesn't have to benchmark it to find out what would havppen for 500 M files.

[mhx]

Hi! Totally agree it'd be good to document the current state of things. I don't think it's easily possible at the moment to influence the amount of memory used per-file, though (I'd have to take a closer look to be completely sure). The memory limit option will only affect how many filesystem blocks can be queued for compression, so that isn't going to help with the memory consumed per-file. I'll get back with more info when I find some time to look into this more closely.

[mhx]

Okay, I'm going to use this issue to collect info / random thoughts as I go through the code and hopefully this will spark further discussion before summarizing this in the docs and / or coming up with plans for future improvements.

• mkdwarfs has a section on internal operation that's useful to understand where it might be using memory. There's also a high-level sequence diagram.

• As mentioned in the mksquashfs issue, things like keeping track of hardlinks and de-duplicating files require a global view of all files. Basically, most features that significantly differentiate DwarFS from other read-only file systems require that global view (e.g. similarity ordering). So a core question is whether you'd like to be able to turn off all these features in order to create a DwarFS image with billions of files, or whether you'd still want these features to somehow work. Personally, I'd be in favour of the latter.

• In its current shape and form, it'll be really hard to create a DwarFS image for which the unpacked metadata does not fit into memory. Once the metadata is packed and written to disk, it can be memory-mapped without every unpacking it, so accessing a file system image should not run into memory issues. Assuming that all memory-consuming features would be disabled, we'd still have to build huge lists for inodes / directory entries / chunks and keep them in memory. These would consume at least 64 bytes per file, assuming 32-bit numeric values (as is currently the case). So for 1 billion files, you'd be looking at at least 64 GB RAM just for the metadata (and this is really just a lower bound after a quick glance at the data structures).

• Is the ability to pack a billion files a hard requirement? If so, why? By disabling all advanced features, there's likely not a huge benefit (in terms of space) in having a single image over, say, 20 images each holding a subset of the data and merge-mounting them. (And yeah, it might be one potential solution to just have mkdwarfs somehow start a new sub-image when exceeding a certain number of input files and then transparently merge this sub-images when reading the image.)

• I came across STXXL recently, which might make it possible to move larger data structures from RAM to disk (optionally, of course). But I have zero experience with it and most certainly, this would have an impact on performance. It might even be possible to use these types to represent the unpacked metadata.

[mhx]

• Another option might be to allocate "static" and infrequently used data in disk-backed, memory-mapped files.

[nh2]

So a core question is whether you'd like to be able to turn off all these features in order to create a DwarFS image with billions of files, or whether you'd still want these features to somehow work. Personally, I'd be in favour of the latter.

I think it would be fantastic if there was a way to get a "constant-memory operation" mode.

Sometimes you just have too many files, and it's the number of files that's the problem (e.g. causing disk seeks upon reads or disk scrubs, payment-per-request on cloud storage systems, and so on). Then you basically want constant-memory tar but without the drawbacks (no concurrent reads => slow, lack of fast extraction due to lack of index, lack of easy mountability to read the data without unpacking, lack of intelligent file-dependent streaming compression).

So I think it would be valuable to be able to disable dwarfs's other features already for gaining those.

But in addition, it would be even cooler to be able to opt into some of dwarfs's more advanced feature in a "constent-memory" mode, e.g. deduplicating against only the last N MB read, or the hashes of the last N million files. This would unlock most of dwarfs's space-saving features while still being able to set up an automatic job and knowing it will never run out of RAM.

So in this case, you could gradually tune between the "a few KB memory needed" mode of tar, and "a few GB needed, configurable" mode of dwarfs which would already get massive space saving gains.