7 ms·
Billion file filesystem
- MawKKe 3y ago> 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
- pama 3y agohttps://blog.liw.fi/posts/2020/10/01/a_billion_files/ https://blog.liw.fi/posts/2020/10/01/a_billion_files/
- berkes 3y agoA 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".
- JackSlateur 3y agoWell, reading the rust code, this is nothing but a couple of exec and one loop 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 Or am I missing something ?
- chx 3y agoHaving 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-directory-but-not-with-ls.html http://be-n.com/spw/you-can-list-a-million-files-in-a-direct...
- jeffbee 3y agoPossibly, 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 ETA: and most of that time is spent sorting the output. % 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 total
- sllabres 3y agoTo 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. 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 and for 1e6 files in an ext4 filesystem. Directory used 23 MB space. (but as i had no ext4 fs with one million free inodes on a loop device) 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.36
- jeffbee 3y agoGood info. But isn't `-1` implicit when the output is a pipe?
- 3y ago
- tyingq 3y agoFor 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.
- tromp 3y ago> 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.
- berkes 3y agoI 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.
- jasode 3y ago>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#:~:text=By%20default%2C%20ext4%20inode%20records%20are%20256%20bytes%2C 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.)
- mnw21cam 3y agoAnd 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.
- cesarb 3y ago> 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.
- deleted 3y ago[deleted]
- ChrisSD 3y ago> Of what use is a filesystem with many empty files? You could use it to benchmark things that do things to all the files in a directory tree. For example, what is the fastest way to list all those files? Delete them? Back them up? Create an archive file with all of them? 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.
- dspillett 3y agoAlso, 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.
- eviks 3y agoWhich file system is best optimized to deal with a huge number of tiny files?
- liveoneggs 3y agoNone of them are very good in practice. Databases exist for just this sort of job.
- webstrand 3y agoBut you're not supposed to store "large" blobs in databases, either?
- pizzafeelsright 3y agoDefine "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.
- snuxoll 3y agoFor 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.
- wongarsu 3y agoYou'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.
- RcouF1uZ4gsC 3y agoFor this use case, it might be better to just store blobs in SQLite: https://www.sqlite.org/fasterthanfs.html https://www.sqlite.org/fasterthanfs.html
- rollcat 3y agoAgree, also sqlite might turn out faster than a filesystem even for much more practical cases: https://sqlite.org/fasterthanfs.html 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.
- anacrolix 3y agoI built https://github.com/anacrolix/squirrel 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.
- actionfromafar 3y agoThanks!
- jerf 3y agoGiven 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.
- kevincox 3y agoI was curious what the "per file" overhead was. Time comes out to 93.6 µs/file or 10 684 files/s created. % b 26*3600*1000*1000/1000000000 93.60000000000000000000 Space comes out to 296 bytes per file. % b 276*1024*1024*1024/1000000000 296.35274342400000000000
- crabbone 3y agoReading 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.
- dunno7456 3y agoI like how clean this blog/website is. Does anyone know if it is a custom engine/theme or not?
- deleted 3y ago[deleted]
- bmelton 3y agoIt 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/ https://blog.liw.fi/posts/welcome/
- cgh 3y agoThe 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.
- bmelton 3y agoThat'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
- ploum 3y agoAt 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.
- Throw73747 3y agoExt4 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.
- tyingq 3y agoDoing anything with large numbers of files used to be very painful on Linux prior to Linux 2.6.4 when they added getdents().
- wglb 3y agoFrom the man page "These are not the interfaces you are interested in."
- harshaw 3y agoOn 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.
- svara 3y agoWhy 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.
- edgyquant 3y agoThey 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.
- metalliqaz 3y agowell 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
- 01HNNWZ0MV43FF 3y agoWith 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.
- tempest_ 3y agoI wonder how ZFS would fare.
- antongribok 3y agoIn 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 Can be very fast with lots of files on a modern Linux box.
- ComputerGuru 3y agoIt would help to explain what it does! -U: do not sort; list entries in directory order
- l0b0 3y agoIf you have GNU find, find . -mindepth 1 -maxdepth 1 -printf x | wc -c performs about the same and includes dotfiles (not "." or "..", though) in the count.
- mikrl 3y agoAs 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.
- naikrovek 3y agoall 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.
- qingcharles 3y agoI 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.
- Zardoz84 3y agoNTFS 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.
- Keyframe 3y ago> NTFS was angry that day, my friends! When it's not angry?
- pilimi_anna 3y agoSince the file is sorted you can binary-search it: https://annas-software.org/AnnaArchivist/annas-archive/-/blob/e2057592df482cf0d8d10159e3e068a76dca02aa/allthethings/utils.py#L1463 https://annas-software.org/AnnaArchivist/annas-archive/-/blo...
- qingcharles 3y agoLooks like sorted by ID, though, sadly? :(
- groodjorb 3y agoBut that's just a bunch of inodes. I'm not sure what this person is actually measuring other than inode traversal.
- kerrie 3y agoHammer2 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.
- Proven 3y ago[dead]
- Keyframe 3y agoI 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.
- hawski 3y agoThe 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 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.
- lacoolj 3y ago"However, if you can **spend a day**, you can **easily** create one yourself ..." good ol easy-mode full-day task
- pronoiac 3y agoIt'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.