Billion file filesystem(blog.liw.fi)
blog.liw.fi
Billion file filesystem
https://blog.liw.fi/posts/2024/billion/
21 comments
Also, be wary of making general conclusions about the performance of a large operation over zero-length files. There could be a significant gap between that and dealing with 1-byte files because of block allocations for that data. Some filesystems support inlining whereby small files do not require extra allocation⁰, that allocation could be very local (in the file's only inode) or not (elsewhere in the MTF in NTFS, so more local than “anywhere on disk”), so there can be a performance profile change when you hit the inlining limits instead of or as well as one when jumping from nothing to a single byte.
There are circumstances where a great many very small files are present: a mail archive (though with the amount of headers in a modern SMTP delivered message for host transit tracking and spam/other identification process notes, these files are not as small as they once were), similarly a usenet archive, a web cache, source repos, …. Also I've seen some tools use small files as per-user flags or session notes, where that don't want the extra dependency of a DB layer, to parse/update a more complex structure for on-disk updates, or the cost of serialising an in-memory structure in a large regular write. This results in very small or even zero-length files, and could balloon in numbers with a great many users. But it is getting more common for such things to be in a sqlite DB or similar instead.
--
[0] Ext4 can inline minute files, 60 bytes or less, in the inode if the relevant option is enabled¹ on filesystem creation (IIRC it can't be turned on after the fact), NTFS can inline small files (I think about 600 bytes) in the MTF structure.
[1] It isn't enabled by default because of a potential rare issue that results in the chance of corruption during recovery after an unclean unmount (due to power drop for instance). IIRC the conditions are: if you create a small file that is inlined, then append to it enough that it can no longer be inlined so a block is allocated, and the unclean unmount happens immediately after, the new data may be lost.
There are circumstances where a great many very small files are present: a mail archive (though with the amount of headers in a modern SMTP delivered message for host transit tracking and spam/other identification process notes, these files are not as small as they once were), similarly a usenet archive, a web cache, source repos, …. Also I've seen some tools use small files as per-user flags or session notes, where that don't want the extra dependency of a DB layer, to parse/update a more complex structure for on-disk updates, or the cost of serialising an in-memory structure in a large regular write. This results in very small or even zero-length files, and could balloon in numbers with a great many users. But it is getting more common for such things to be in a sqlite DB or similar instead.
--
[0] Ext4 can inline minute files, 60 bytes or less, in the inode if the relevant option is enabled¹ on filesystem creation (IIRC it can't be turned on after the fact), NTFS can inline small files (I think about 600 bytes) in the MTF structure.
[1] It isn't enabled by default because of a potential rare issue that results in the chance of corruption during recovery after an unclean unmount (due to power drop for instance). IIRC the conditions are: if you create a small file that is inlined, then append to it enough that it can no longer be inlined so a block is allocated, and the unclean unmount happens immediately after, the new data may be lost.
It does seem certainly seem atypical, and I'd be curious if anyone has ever encountered something like this in the real world. It seems unlikely because
1. It takes so long to create that many files in the first place. In this case 26 hours of doing nothing but file creation.
2. If the files contained any data at all, you would need a lot of disk space. If each file was 64k, you'd need 640TB of disk. It seems more likely you'd run out of disk space before you reached a billion files.
3. Someone developing such a system where that many files could be created would probably realize that it's a poor design and figure out a way to mitigate it before it ever happened.
Nevertheless, it's fun to think about.
1. It takes so long to create that many files in the first place. In this case 26 hours of doing nothing but file creation.
2. If the files contained any data at all, you would need a lot of disk space. If each file was 64k, you'd need 640TB of disk. It seems more likely you'd run out of disk space before you reached a billion files.
3. Someone developing such a system where that many files could be created would probably realize that it's a poor design and figure out a way to mitigate it before it ever happened.
Nevertheless, it's fun to think about.
> and I'd be curious if anyone has ever encountered something like this in the real world.
Not that many, no, but I can tell you from professional experience that real life Linux systems get really weird when you have merely tens of thousands of files in a directory, and it would be kind of nice if that were fixed.
Not that many, no, but I can tell you from professional experience that real life Linux systems get really weird when you have merely tens of thousands of files in a directory, and it would be kind of nice if that were fixed.
That used to be true, but ext4 htrees fixed most of the Linux issues in 2002. These days, most of the stupid resides firmly in the userspace consumers, making assumptions like "readdir a whole directory into an in-memory list".
https://en.wikipedia.org/wiki/HTree
https://en.wikipedia.org/wiki/HTree
Of all the times for me to not write out GNU/Linux, you're telling me this is the one time the GNU part actually is the important part?:) (Though in fairness, ex. ls did become... kind of functional when run as `ls -f`)
Back in the late 2000’s I was a windows clustering SME for a major tech company on account with a major financial company. One project I was tasked with was migrating a system which had a huge number of small files. I don’t recall the number. IIRC it took a couple weeks to do the initial file copy. Then the task was to sync the changes during the change window which was 8 hours. Every time I tried to sync the changes it took well more than 8 hours.
I did find a tool that could do the job but of course no one wanted to pay for it. Fortunately for me I left that position before the migration and someone else had to figure it out.
So yeah, I’ve encountered something similar in the real world. It was the result of poor software design choices but by the time I got there that path was chosen and I had to deal with the results.
I did find a tool that could do the job but of course no one wanted to pay for it. Fortunately for me I left that position before the migration and someone else had to figure it out.
So yeah, I’ve encountered something similar in the real world. It was the result of poor software design choices but by the time I got there that path was chosen and I had to deal with the results.
10k file creations per second does seem kind of slow no? A typical SSD today can do many millions of operations per second…
It does come up in real world situations. Lots of file based caches in things like Apache, or session stores, like in PHP, etc.
I just tried splitting the Anna's Archive 250GB WorldCat JSON file out into separate files so I could random-access it. My app crashed at 7m files due to some corruption in the source file.
I can tell you, it took a real, real long time to delete seven million files on NTFS. It was not happy.
I can tell you, it took a real, real long time to delete seven million files on NTFS. It was not happy.
NTFS and Windows filesystem IO does poorly with many small files. it's one of the reasons that git for windows (and Linux subsystem version 1) is inevitably slow.
Since the file is sorted you can binary-search it: https://annas-software.org/AnnaArchivist/annas-archive/-/blo...
Looks like sorted by ID, though, sadly? :(
> NTFS was angry that day, my friends!
When it's not angry?
When it's not angry?
In case you ever have to work with a directory that has lots of files in it, sometimes it's useful to remember the -U flag in ls. For example to count the number of files, I sometimes use this:
ls -U1 |wc -l
It would help to explain what it does!
-U: do not sort; list entries in directory orderIf you have GNU find,
find . -mindepth 1 -maxdepth 1 -printf x | wc -c
Ext4 is probably the worst filesystems for such task. 1e9 files is really not that much.
Old Reiserfs3 really excelled in this, Gentoo Portage had many tiny files. Today Btrfs has features like extends, where tiny (or empty) files are stored together in single inode.
For distributing image with several files(such as this example), SquashFs is the best option.
Old Reiserfs3 really excelled in this, Gentoo Portage had many tiny files. Today Btrfs has features like extends, where tiny (or empty) files are stored together in single inode.
For distributing image with several files(such as this example), SquashFs is the best option.
> I’ve done this before, but this time I made it a little simpler for me to do it again: everything in one Rust program rather than clunky scripts.
Warms my heart
Warms my heart
On my AWS service (EFS) many customers do use lots of small files. And for legacy apps there is nothing much you can do, but as a PSA, use the right tool for the job :) many people use file systems as databases when a database would be more appropriate.
Put it this way - moving a sqlite file with 1 million rows is much easier than moving 1 million files.
Put it this way - moving a sqlite file with 1 million rows is much easier than moving 1 million files.
Why though? If you squint a little, a filesystem and a database are the same thing and filesystem semantics are useful and well understood.
Performance is "just" an engineering issue.
Performance is "just" an engineering issue.
Databases are optimized for storing a couple trillion records of a couple dozen bytes each. File systems are optimized for storing a couple million records of a couple Megabytes to Terabytes each, with maybe a hundred bytes or so of metadata attached. They make very different engineering tradeoffs. And while you can invest time to make them better at each other's tasks, there is only so much you can do.
Isn’t that what ZFS is trying to solve? Such that storing a couple billion “ records of a couple Megabytes to Terabytes each” become feasible?
No, ZFS tries to solve the problem of data integrity mainly. It also supports very large volumes and files, but it's not particularly good at storing billions of files in a single one. In that respect it's like any other file system. It'll do it, but you need to design your directory structure well to have fast access, and if you try to copy the directory structure it'll still be very slow.
Even in ZFS, there is more overhead for a file than I would guess a database has for a row. Each file needs a DNode, which is 512 bytes. It also needs an entry in it's parent directory's list of files (a 64 byte micro ZAP entry for example).
[deleted]
> If you squint a little, a file system and a database are the same thing
This is a tale and argument as old as time. It’s the squinting that is the problem. The devil is in the details.
This is a tale and argument as old as time. It’s the squinting that is the problem. The devil is in the details.
BeOS squinted so hard its native file system BeFS came out as an impressionist painting: the live metadata made it very database-like in behaviour with live search results (back in the mid nineties) but fairly lacklustre “actual file system” credentials.
Are database semantics not useful or well understood?
There's also no ways to really make a file system faster when dealing with many small files and directories. If you can avoid doing it by using a database you probably should.
There's also no ways to really make a file system faster when dealing with many small files and directories. If you can avoid doing it by using a database you probably should.
> There's also no ways to really make a file system faster when dealing with many small files and directories.
Depends on the file/directory structure. Traditionally back in the CGI days URI's were links to files on a server. They often still are for static files. If you know the path to a file then the lookup should be very fast.
But yeah any other type of index other then the path isn't really possible.
Depends on the file/directory structure. Traditionally back in the CGI days URI's were links to files on a server. They often still are for static files. If you know the path to a file then the lookup should be very fast.
But yeah any other type of index other then the path isn't really possible.
There's still at least one more context switch than using a database, which dominates the performance for small files. The usage pattern matters more than the structure. That's not even mentioning synchronization costs to make it correct when the file system is mutable.
One can have separate directories with files hard or symbolic linked under different names.
> Are database semantics not useful or well understood?
Sort of, yeah. Consider how many command line programs will accept a file as an input parameter vs. how many will accept an SQL query.
Existing tooling is predominantly designed to work with files so depending on what you're trying to accomplish, you may have a lot more work to do when using a database.
Sort of, yeah. Consider how many command line programs will accept a file as an input parameter vs. how many will accept an SQL query.
Existing tooling is predominantly designed to work with files so depending on what you're trying to accomplish, you may have a lot more work to do when using a database.
Well yes, but also it varies… on IBM AS/400 machines running OS/400 (currently iSeries if I’m not mistaken) the file system is basically a database and commands basically parse queries.
And as well all know, an IBM AS/400 is the most common computer for serious software development in 2024.
Why bother staying silent when one can slide some sarcasm in, eh?
That’s an interesting point, in terms of shrink wrapped software its easily 100x more software that will accept a file input.
say you want to store 10 million records. if you do this as a files in a say, one big directory (or even a sharded directory hiearchy), you have to update the parent directory (inode) when you create a new file (because the directory mtime needs to change) That's extra overhead vs what you can get with appending to a journaled database. POSIX encodes these specifications of what a file system is - so there isn't much ability to innovate here.
And yes - we work really hard to address the performance issues here, but there are constraints.
And yes - we work really hard to address the performance issues here, but there are constraints.
Abandon POSIX and use the filesystem over userspace
But why can't journaled filesystem do the same?
Didn't Log Structured Filesystem work like that?
Or SQLite over Fuse.
well you're very correct that a filesystem is just a kind of database. So the equivalent of moving the sqlite database would be to simply move the filesystem image rather than each file individually. However I think the issue is that the OS and services all run on top of the filesystem, so doing operations at the level of block storage is not practical. But... if the system is virtulized, I guess you could make it work
With LVM you can do block device snapshots with virtualizing the whole system, but I don't think there's any way to get around the fact that, e.g. a 1 TB filesystem with 600 GB of files will have 400 GB of garbage that you end up copying, whereas a SQLite or Postgres DB would vacuum itself periodically and actually take up only 600 GB.
Depends on the FS and tools used. With for example XFS and `xfsdump` / `xfsrestore`, or ZFS and `send` / `receive` you would only copy the data, and something like a "vacuum" would happen also.
without virtualizing*
Tracking atime, atime, and full permissions on every dirent is a lot of work. Most people putting a bunch of small files on disk don't want any of that, and usually misunderstand the actual transaction promises of their filesystem. They would be better off with SQLite and a single table (name, blob).
They are not the same thing. In general Databases allow for querying of the structured contents inside of a “file” but also they tend to exist (now days at least) as an abstraction on top of the file system.
how about a ZFS snapshot of a million files, is that any different than a single file database?
Unless you need filesystem features, object stores are probably a better target.
Or possibly a document based data store.
The monolithic persistence layer is an anti pattern unless you have specific reasons to support it.
ZFS is quite nice as filesystems go but it is still a filesystem.
Or possibly a document based data store.
The monolithic persistence layer is an anti pattern unless you have specific reasons to support it.
ZFS is quite nice as filesystems go but it is still a filesystem.
As the saying goes: If the only tool you have is a hammer, it is tempting to treat everything as if it were a nail.
I like how clean this blog/website is.
Does anyone know if it is a custom engine/theme or not?
Does anyone know if it is a custom engine/theme or not?
At some point, we should stop thinking about engine/theme. This is a "normal" website.
This kind of blog/website can easily be done by writing every blog post in a separate html file then doing a quick script to put together the index.
Your script could also add use a very simple template for each page, template in which you can use your own CSS. (here, it is an external file containing 142 lines of straightforward CSS).
Yes, I did it for my own blog. But I also added the fact that I would like to write my posts in the Gemtext format. So I wrote a parser to convert it to HTML.
And, in the end, it proved to be quicker and easier to do it all by hand myself than to learn any templating engine or any static website generator. Also, I never understood CSS (I’m really really bad at that) but managed to do what I want in exactly 42 lines of CSS. And, guess what, lot of people are asking me where I found my "theme".
I think that everybody working with the Web should be required to do a pure HTML/simple CSS website at least once to realize how easy and straightforward it is to NOT use any engine/theme.
And how much time and energy we are wasting on layers above layers above layers.
This kind of blog/website can easily be done by writing every blog post in a separate html file then doing a quick script to put together the index.
Your script could also add use a very simple template for each page, template in which you can use your own CSS. (here, it is an external file containing 142 lines of straightforward CSS).
Yes, I did it for my own blog. But I also added the fact that I would like to write my posts in the Gemtext format. So I wrote a parser to convert it to HTML.
And, in the end, it proved to be quicker and easier to do it all by hand myself than to learn any templating engine or any static website generator. Also, I never understood CSS (I’m really really bad at that) but managed to do what I want in exactly 42 lines of CSS. And, guess what, lot of people are asking me where I found my "theme".
I think that everybody working with the Web should be required to do a pure HTML/simple CSS website at least once to realize how easy and straightforward it is to NOT use any engine/theme.
And how much time and energy we are wasting on layers above layers above layers.
> [...] a quick script to put together the index.
> Your script could also add use a very simple template for each page, template in which you can use your own CSS. (here, it is an external file containing 142 lines of straightforward CSS).
> Yes, I did it for my own blog [...]
So, you created a custom engine, which is what parent was asking about.
> Your script could also add use a very simple template for each page, template in which you can use your own CSS. (here, it is an external file containing 142 lines of straightforward CSS).
> Yes, I did it for my own blog [...]
So, you created a custom engine, which is what parent was asking about.
It looks like it's ikiwiki (unless I'm mis-reading it -- I had to parse it a couple times). Their first post[1] comments on it
[1] https://blog.liw.fi/posts/welcome/
[1] https://blog.liw.fi/posts/welcome/
The way I read it, he moved on from ikiwiki to his "newest approach", which looks to me like regular hand-written html+css. And why not, it's just a bunch of words, no frameworks necessary. This guy has software running on Mars so making a good old '90s style website by hand seems appropriate.
That's what I interpreted at least one of the times, but if you follow the "new approach" (it's a link) it takes you to a blog that is old (according to dates) and does not match the current styling
I could definitely be wrong, as it's still a bit ambiguous to me
I could definitely be wrong, as it's still a bit ambiguous to me
[deleted]
Doing anything with large numbers of files used to be very painful on Linux prior to Linux 2.6.4 when they added getdents().
From the man page "These are not the interfaces you are interested in."
I was curious what the "per file" overhead was.
Time comes out to 93.6 µs/file or 10 684 files/s created.
Time comes out to 93.6 µs/file or 10 684 files/s created.
% b 26*3600*1000*1000/1000000000
93.60000000000000000000
% b 276*1024*1024*1024/1000000000
296.35274342400000000000Reading this data from a program that writes to a file rather than disk is... of very low utility. It doesn't really tell you about how the filesystem performs. Not to mention that your numbers will very a lot depending on your h/w and the storage setup that hosts the file.
For this use case, it might be better to just store blobs in SQLite: https://www.sqlite.org/fasterthanfs.html
Given that this just creates empty files named "file-#.txt", you can "just" create a Fuse file system that simply exposes a billion files named that way for basically no space on disk and no time spent creating it. In fact given that the author said this took over a day to run I could probably write this code faster than the author was able to run the script once on a concrete file system.
This isn't really a problem about optimizing the storage of a billion empty files, it's about what the file systems do with them.
This isn't really a problem about optimizing the storage of a billion empty files, it's about what the file systems do with them.
Agree, also sqlite might turn out faster than a filesystem even for much more practical cases: https://sqlite.org/fasterthanfs.html
However it still tickles my curiosity and exercises an interesting pathological case. As a kid I've had this idea, what if I could store the data bytes in the file names of empty files, did I just create space out of nowhere? It's always beautiful whenever you rediscover that computers are not magic.
However it still tickles my curiosity and exercises an interesting pathological case. As a kid I've had this idea, what if I could store the data bytes in the file names of empty files, did I just create space out of nowhere? It's always beautiful whenever you rediscover that computers are not magic.
I built https://github.com/anacrolix/squirrel for just this purpose. However you might find that batch inserting empty files might only be 10x faster or so than creating empty files directly on the filesystem if we are to believe the 10k/s the OP achieved.
Thanks!
As part of my undergrad research project I used magnetic simulation software (running on windows and therefore NTFS)
The program output magnetization by timestep so for the simple structure I was investigating, I ended up with about 100K files of a few KB each which were a massive pain to move to my Linux machine for analysis.
I looked into changing the batching but couldn’t figure it out, and this prompted me for the first time to consider how the structure of data on a device could affect processing throughout even if the absolute quantity of data was the same.
The program output magnetization by timestep so for the simple structure I was investigating, I ended up with about 100K files of a few KB each which were a massive pain to move to my Linux machine for analysis.
I looked into changing the batching but couldn’t figure it out, and this prompted me for the first time to consider how the structure of data on a device could affect processing throughout even if the absolute quantity of data was the same.
all filesystems have made tradeoffs. ntfs made a tradeoff that resulted in file operations having a high overhead per file. you really, really feel this when you're working with 100s of thousands of tiny files in a single directory.
Hammer2 might be more suitable to storing billions of files efficiently: it supports online and batched deduplication, snapshots, directory entry indexing, multiple mountable filesystem roots, mountable snapshots, a low memory footprint, compression, encryption, zero-detection, data and metadata checksumming, and synchronization to other filesystems or nodes.
I wonder how ZFS would fare.
But that's just a bunch of inodes. I'm not sure what this person is actually measuring other than inode traversal.
I love rust and all, but essentially one could create a non-clunky shell variant of it. dd an image, mkfs.ext4 out of it, mount it and then a bit more elaborate version (but not much) of: for i in $(seq 1 1000000000); do touch "file-${i}.txt"; done
no? it'd probably die soon.
no? it'd probably die soon.
The author stated:
> I’ve done this before, but this time I made it a little simpler for me to do it again: everything in one Rust program rather than clunky scripts.
The author then used this Python script: http://git.liw.fi/billion-files/tree/create-files
For a shell script version I would like to remind you that you can "touch" multiple files at the same time. There probably is a balance between the length of touch argument list (it takes time to generate it) and running more processes.
> I’ve done this before, but this time I made it a little simpler for me to do it again: everything in one Rust program rather than clunky scripts.
The author then used this Python script: http://git.liw.fi/billion-files/tree/create-files
For a shell script version I would like to remind you that you can "touch" multiple files at the same time. There probably is a balance between the length of touch argument list (it takes time to generate it) and running more processes.
It's been quite a while, but I think extremely redundant information, like mostly zeroes, is one of those cases where compression can be usefully be done repeatedly. I might check to see if it holds true here.
Which file system is best optimized to deal with a huge number of tiny files?
You'd have to quantify what you mean by "best". Lowest storage overhead? Being able to deal with the most files without needing tuning (e.g. not running out of inodes)? Access Latency? For metadata or do you want the actual file? Iterating the directory or accessing random file names? And if you care about speed, are the files in a single folder or in a reasonable directory structure? Do you need the files to be able to change or is readonly enough?
For readonly there are a couple good options, though arguably they are then archives. Many use sqlite because it's widely available and deals with this well. But most average file systems are pretty bad at at least one of those factors.
It's probably easier to identify which file systems are bad for which reasons. For example on NTFS you can't store a file in less than 1kb, and large directories can be an issue because a directory entry contains a sequential list of files. In contrast ext3 introduced a hash table to quickly look up file metadata in huge directories. On the other hand, if your files are e.g. about 800B and spread into directories of reasonable file count NTFS might suddenly outperform ext4 on some metrics, because NTFS can store the first ~900 bytes of the file together with the metadata, ext4 only the first 60. Or if your huge number of tiny files contains lots of identical files a zfs with live deduplication might become interesting.
For readonly there are a couple good options, though arguably they are then archives. Many use sqlite because it's widely available and deals with this well. But most average file systems are pretty bad at at least one of those factors.
It's probably easier to identify which file systems are bad for which reasons. For example on NTFS you can't store a file in less than 1kb, and large directories can be an issue because a directory entry contains a sequential list of files. In contrast ext3 introduced a hash table to quickly look up file metadata in huge directories. On the other hand, if your files are e.g. about 800B and spread into directories of reasonable file count NTFS might suddenly outperform ext4 on some metrics, because NTFS can store the first ~900 bytes of the file together with the metadata, ext4 only the first 60. Or if your huge number of tiny files contains lots of identical files a zfs with live deduplication might become interesting.
> In contrast ext3 introduced a hash table to quickly look up file metadata in huge directories.
Ah, but it has its own consequences. ext4 doesn't dynamically reclaim inodes or garbage collect these directory hash tables, so if you create a directory and cycle a bunch of files through it, like millions and billions of files many times over, you can get into a case where you have sizable portions of your drive as free space, but you get ENOSPC errors because adding files to the directory tries to insert them into the hash table, which fails, because the hash table takes up so much space it causes the drive to be actually full. Oh, don't try actually doing directory operations without the index, either. Something like `du -sh` without that index will take upwards of 10+ minutes on a fast virtio SSD to account for like 10 gigabytes of files.
I recently had a 1TB ext4 drive that got into this state where it had 150GB free but the directory hash indexes were fucking massive, because billions of files had gone through the filesystem and it was basically hosed because even turning off the index and then turning it back on does not drop the hash table index, it only literally turns off the index use in the read path and leaves the index as is. I couldn't find a way to drop and clear the hash indicies. Yeah. Apparently you can get into a similar state if you exhaust the inode count because, again, there is no dynamic inode reclamation.
In this case, I had the `gecko-dev` Git repository, which is absolutely massive, and I was extracting many copies of it onto my drive as part of some testing automation. So that added up fast. It was on a separate drive from my main /home mount, at least.
The lesson I have learned from this is to mostly just use XFS instead of ext4, I guess. Which I was already doing on all my servers, so a bit funny I learned that lesson only on my own personal machine.
Ah, but it has its own consequences. ext4 doesn't dynamically reclaim inodes or garbage collect these directory hash tables, so if you create a directory and cycle a bunch of files through it, like millions and billions of files many times over, you can get into a case where you have sizable portions of your drive as free space, but you get ENOSPC errors because adding files to the directory tries to insert them into the hash table, which fails, because the hash table takes up so much space it causes the drive to be actually full. Oh, don't try actually doing directory operations without the index, either. Something like `du -sh` without that index will take upwards of 10+ minutes on a fast virtio SSD to account for like 10 gigabytes of files.
I recently had a 1TB ext4 drive that got into this state where it had 150GB free but the directory hash indexes were fucking massive, because billions of files had gone through the filesystem and it was basically hosed because even turning off the index and then turning it back on does not drop the hash table index, it only literally turns off the index use in the read path and leaves the index as is. I couldn't find a way to drop and clear the hash indicies. Yeah. Apparently you can get into a similar state if you exhaust the inode count because, again, there is no dynamic inode reclamation.
In this case, I had the `gecko-dev` Git repository, which is absolutely massive, and I was extracting many copies of it onto my drive as part of some testing automation. So that added up fast. It was on a separate drive from my main /home mount, at least.
The lesson I have learned from this is to mostly just use XFS instead of ext4, I guess. Which I was already doing on all my servers, so a bit funny I learned that lesson only on my own personal machine.
I meant regular "consumer" file operations - opening a folder with a few mil files and getting basic data like names/sizes, copying a few million files from one folder to another, renaming, etc.
So definitely not read-only, not identical, not all tiny 0b or even 800b files (maybe <1mb is still tiny?) , and storage overead is a much lower priority vs latency of access and speed of operations
So definitely not read-only, not identical, not all tiny 0b or even 800b files (maybe <1mb is still tiny?) , and storage overead is a much lower priority vs latency of access and speed of operations
Why would a consumer have a billion files in a directory?
Your question reminds me of a famous (some fifteen-twenty years ago) question from MSDN forums.
A poor soul complained that when they put 10K buttons on a form in the designer view in MSVS it comes to a grinding halt. And that's impossible to use the studio anymore. To which a bunch of respondents quickly replied: "but why tho? why do you need so many buttons on the form?" -- From the discussion that followed it became apparent that the poster wanted to reproduce the minesweeper game with a 100x100 board.
What I'm trying to say is: if you have a problem where you think you need a billion of files all in one directory, it's easier to reformulate the problem than to try to find a solution for it.
Your question reminds me of a famous (some fifteen-twenty years ago) question from MSDN forums.
A poor soul complained that when they put 10K buttons on a form in the designer view in MSVS it comes to a grinding halt. And that's impossible to use the studio anymore. To which a bunch of respondents quickly replied: "but why tho? why do you need so many buttons on the form?" -- From the discussion that followed it became apparent that the poster wanted to reproduce the minesweeper game with a 100x100 board.
What I'm trying to say is: if you have a problem where you think you need a billion of files all in one directory, it's easier to reformulate the problem than to try to find a solution for it.
None of them are very good in practice. Databases exist for just this sort of job.
For what it's worth, I've built an entire data ingest pipeline with PostgreSQL that stores tens of millions of PDFs in a giant database table and...it works fine.
Now we are working on scooping up a bunch of small (1-2KB) files we want to index with metadata and chucking them into a SQLite file, because as fast as `grep` is searching through the text the constant open() and close() calls are much more impactful.
Now we are working on scooping up a bunch of small (1-2KB) files we want to index with metadata and chucking them into a SQLite file, because as fast as `grep` is searching through the text the constant open() and close() calls are much more impactful.
But you're not supposed to store "large" blobs in databases, either?
Define "large" because it keeps getting bigger.
Systems I've built generally use a pointer within a database to a secondary location. I've also seen hundreds of megs stored in binary json blobs.
Systems I've built generally use a pointer within a database to a secondary location. I've also seen hundreds of megs stored in binary json blobs.
I know which one I wouldn't pick for five billion files, that's for sure. EXT4 prepays for some of the work at mkfs time, but it also has certain limits. XFS can create as many inodes as you want, if you have the space for it.
A decade ago I was dealing with map tiles for the entire globe, stored each in it's own file, and reiserfs was dramatically better at dealing with all the small files associated with this: there are a lot of solid blue and solid green tiles in the globe. Reiser's idea of what a small file is was 1-2 orders of magnitude smaller than what ext3's idea of a small file was.
More recently our map tiles are limited to a single US state, and we are using XFS, but because of the much smaller data set size I haven't really done any optimization beyond hard linking duplicate files. I inherited that choice, so I don't know what went into that.
More recently our map tiles are limited to a single US state, and we are using XFS, but because of the much smaller data set size I haven't really done any optimization beyond hard linking duplicate files. I inherited that choice, so I don't know what went into that.
Why not just identify the solid tiles differently than ones that have a mix? That should reduce the number of tiles to store. Or is there some drawback to that approach?
This was a design goal for reiserfs, fwiw.
> With a billion empty files, the image uses 276 GiB disk space.
I wonder why one needs to use as much as 296 bytes per empty file.
I wonder why one needs to use as much as 296 bytes per empty file.
>I wonder why one needs to use as much as 296 bytes per empty file.
File systems like ext4/NTFS/APFS/etc require extra disk space for "housekeeping" of data blocks and allocations and metadata (lastwritetime, permission flags, etc) . This reserved space for each file has a minimum fixed amount even if the file's size is zero.
E.g. ">By default, ext4 inode records are 256 bytes," -- from https://ext4.wiki.kernel.org/index.php/Ext4_Disk_Layout#:~:t...
(Scroll up on that page to see all the fields of metadata in each inode record.)
File systems like ext4/NTFS/APFS/etc require extra disk space for "housekeeping" of data blocks and allocations and metadata (lastwritetime, permission flags, etc) . This reserved space for each file has a minimum fixed amount even if the file's size is zero.
E.g. ">By default, ext4 inode records are 256 bytes," -- from https://ext4.wiki.kernel.org/index.php/Ext4_Disk_Layout#:~:t...
(Scroll up on that page to see all the fields of metadata in each inode record.)
And you can override that default by giving the -I <size> option to mkfs.ext4, so you could make a filesystem with 128-byte inodes, and it would require about half the amount of disc space.
> mkfs.ext4, so you could make a filesystem with 128-byte inodes
At the cost of introducing a Y2038 issue. The timestamp fields in the first 128 bytes of an ext2/ext3/ext4 inode are only 32 bits each, they are extended with an extra 32 bits each in the next 128 bytes of the inode.
At the cost of introducing a Y2038 issue. The timestamp fields in the first 128 bytes of an ext2/ext3/ext4 inode are only 32 bits each, they are extended with an extra 32 bits each in the next 128 bytes of the inode.
If you want/need to reduce the metadata, there's some nice solutions for that https://github.com/seaweedfs/seaweedfs
Seaweed uses 40 bytes of metadata per file.
Seaweed uses 40 bytes of metadata per file.
I would suspect it's a combination of the file-pointers, the file-names and other metadata, and the directories.
Directories with lots of files grow very big too. Indexes cost space.
[deleted]
"However, if you can **spend a day**, you can **easily** create one yourself ..."
good ol easy-mode full-day task
good ol easy-mode full-day task
A nice example of how a simple program can be done in Rust.
I think that if some of the setup (mkfs, mount) is left to external tools¹, it show clearly how simple a program in Rust can be.
Sure, in Ruby, python, or even bash, it would be two or three lines, under ten statements and probably under 200 characters while remaining readable. But still it shows us how the idea that "in rust there is a lot of boilerplate" isn't really a practical issue.
I write most of my simple tools in rust lately. Needed a million URLs parsed and matched against denylists last week: my Python code took 5 minutes to run that (way too long for trial-error), the bash cut,sed,awk,grep pipe-chain quickly too wieldy to keep playing around with (yet seconds to run, not minutes). In a few minutes I was running a rust version that used all my cores, well readable and easy to iterate with. I guess go would be the perfect fit, but I don't speak go that well (nor have its tooling ready and up-front).
¹something I'd do regardless. If only to follow the part of the Unix philosophy "do one thing".
I think that if some of the setup (mkfs, mount) is left to external tools¹, it show clearly how simple a program in Rust can be.
Sure, in Ruby, python, or even bash, it would be two or three lines, under ten statements and probably under 200 characters while remaining readable. But still it shows us how the idea that "in rust there is a lot of boilerplate" isn't really a practical issue.
I write most of my simple tools in rust lately. Needed a million URLs parsed and matched against denylists last week: my Python code took 5 minutes to run that (way too long for trial-error), the bash cut,sed,awk,grep pipe-chain quickly too wieldy to keep playing around with (yet seconds to run, not minutes). In a few minutes I was running a rust version that used all my cores, well readable and easy to iterate with. I guess go would be the perfect fit, but I don't speak go that well (nor have its tooling ready and up-front).
¹something I'd do regardless. If only to follow the part of the Unix philosophy "do one thing".
Well, reading the rust code, this is nothing but a couple of exec and one loop
Something like, in bash:
Something like, in bash:
test -f output.img || (fallocate -s 1T output.img && mkfs.ext4 output.img)
mkdir -p toto
mount output.img toto
for i in {1..1000000000}
do
touch toto/$i
done
umount toto
Having a billion files in a single directory versus a more typical tree has its own challenges.
http://be-n.com/spw/you-can-list-a-million-files-in-a-direct...
http://be-n.com/spw/you-can-list-a-million-files-in-a-direct...
Possibly, but at the scale discussed in the article, not so much.
% time ls | wc
10000000 10000000 78888897
ls 1.90s user 0.73s system 99% cpu 2.637 total
wc 0.28s user 0.02s system 11% cpu 2.597 total
% time ls -U | wc
10000000 10000000 78888897
ls -U 0.53s user 0.29s system 99% cpu 0.823 total
wc 0.26s user 0.02s system 33% cpu 0.822 totalTo my experience (and if only the filename is needed) the "-1" option helps saving some time too.
Be aware that output from ls without options differ, if redirected.
time (real user sys) in seconds with 1e6 files in a xfs filesystem. Directory used 27 MB space.
time (real user sys) in seconds with 1e6 files in a xfs filesystem. Directory used 27 MB space.
ls -l > /dev/null : 49.12 23.90 13.47
ls -lU > /dev/null : 46.62 33.11 8.01
ls > /dev/null : 6.36 1.97 3.63
ls -1 > /dev/null : 2.49 1.83 0.36
ls -1U > /dev/null : 0.31 0.18 0.08
(find) : 0.77 0.49 0.19
ls -l > /dev/null : 51.39 34.02 11.39
ls -lU > /dev/null : 47.39 30.72 11.09
ls > /dev/null : 4.83 3.56 0.65
ls -1 > /dev/null : 4.46 3.45 0.50
ls -1U > /dev/null : 0.51 0.18 0.26
(find) : 1.29 0.76 0.36Good info. But isn't `-1` implicit when the output is a pipe?
Good reply, you are right.
I have even written ("Be aware that output from ls without options differ, if redirected") that it is so but was somewhat fooled by my experiment and the different timings for "ls" and "ls -1" when using XFS.
Of course I was not able to reproduce this difference and assume that I did work on the system and it was not idle.
I have repeated the the tests, on another mostly idle system. (Therefor the timing is not comparable to the first test). This time both filesystems live in a loop device and the benchmarks were run with hyperfine (3 warmup loops, 3 measurements each).
Of course I was not able to reproduce this difference and assume that I did work on the system and it was not idle.
I have repeated the the tests, on another mostly idle system. (Therefor the timing is not comparable to the first test). This time both filesystems live in a loop device and the benchmarks were run with hyperfine (3 warmup loops, 3 measurements each).
XFS
ls -l >/dev/null Time (mean ± σ): 5.890 s ± 0.394 s [User: 1.096 s, System: 3.491 s]
ls -lU >/dev/null Time (mean ± σ): 2.254 s ± 0.386 s [User: 0.648 s, System: 1.602 s]
ls >/dev/null Time (mean ± σ): 542.7 ms ± 4.4 ms [User: 443.8 ms, System: 98.7 ms]
ls -1 >/dev/null Time (mean ± σ): 534.4 ms ± 2.3 ms [User: 450.1 ms, System: 84.1 ms]
ls -1U >/dev/null Time (mean ± σ): 115.8 ms ± 1.8 ms [User: 80.9 ms, System: 34.6 ms]
ls -U >/dev/null Time (mean ± σ): 121.0 ms ± 14.6 ms [User: 80.9 ms, System: 40.0 ms]
find >/dev/null Time (mean ± σ): 225.0 ms ± 16.2 ms [User: 150.1 ms, System: 74.7 ms]
EXT4
ls -l >/dev/null Time (mean ± σ): 10.493 s ± 0.392 s [User: 2.495 s, System: 5.032 s]
ls -lU >/dev/null Time (mean ± σ): 8.395 s ± 0.157 s [User: 0.735 s, System: 5.049 s]
ls >/dev/null Time (mean ± σ): 1.966 s ± 0.010 s [User: 1.760 s, System: 0.202 s]
ls -1 >/dev/null Time (mean ± σ): 2.014 s ± 0.032 s [User: 1.798 s, System: 0.216 s]
ls -1U >/dev/null Time (mean ± σ): 221.4 ms ± 1.3 ms [User: 83.7 ms, System: 137.6 ms]
ls -U >/dev/null Time (mean ± σ): 222.5 ms ± 2.0 ms [User: 78.9 ms, System: 143.6 ms]
find >/dev/null Time (mean ± σ): 531.0 ms ± 4.0 ms [User: 377.3 ms, System: 153.7 ms]That is easily implemented with a double loop, where the first one is a directory (integer hexed with printf '%x') and the second is the files in it
However, that was not the point of my reply
However, that was not the point of my reply
For it to be a good example, I'd make some changes. As one example, there are a few places where stderr is thrown away in an error and substituted for a very generic failure message. And some where the failure is assumed to be something that it may not be.
Though, I understand the author wasn't claiming to deliver an example of how to do "scripting" in Rust.
Though, I understand the author wasn't claiming to deliver an example of how to do "scripting" in Rust.
This can be useful up to a point. But be careful of over optimizing for the pathological case at the expense of typical usage. Most of the listed operations are usually done on a small number of files. And even when they seem a lot to the user it's still a teeny tiny fraction of one billion.
And that's before we even mention directories.