Folders with high file counts
bombich.com
bombich.com
Simply put, you make an algorithm like:
let hash = md5(filename)
let folderPath = path.join(root, hash.substr(0,1), hash.substr(0,2), hash.substr(0,3), filename)
You end up storing files like:
.../7/7f/7fa/somefile.png
There's lots of other strategies, too, depending on your needs:
# filename are already GUIDs or hashes:
.../1/1f/1fd/1fd2dd27-d307-47b2-b37d-11903fd0f03d.png
# date-based to make cleaning up old files easy:
.../2023/01/19/app.log
# hash by existing numeric identifier (like customerid) using modulus:
.../customers/4/94/52194/customerfile.datOne side-effect is you can't go into a folder and type something like: `cp .doc` or `cp screenshots xxxxx`
Or `find -exec`
The updated code first looks up a new path (pretty fast), if it's not found, it looks up the old path. Only the original file name is required, and the code change is literally 10-20 lines, including the function that derives the new path.
OP’s post probably involved an old filesystem. For example, ext2 did not index the files within a directory, but ext3 introduced H-trees which made big directories much more feasible.
They often would if they tried to access them like they usually do a filesystem, but for some reason people know a full table scan and N+1 queries are bad, but don't bat an eye at readdir and stat each entry in a directory (or worse, scandir+sort+stat).
Of course, a B-tree is somehow larger than whatever was used to store inode data in the (ext2?) filesystem 25 years ago.
When you connect to the device from your computer over USB (which is usually USB 2.0 even if USB-C, except in major 2021+ models), it will take forever to enumerate the files in that folder. Once you start copying, there's big chance it hangs, so you need to disconnect the device, and go through that painful process again.
(I know, I'm oldschool, I don't have automatic cloud backup enabled).
adb-sync --reverse /sdcard/DCIM(?) ~/photos.go.here
This is mostly because of the mtp protocol that is really shitty, supporting only a single channel at a time and having to send the whole list of all files in one time. But also because Android implementation of it is very buggy.
I was always stunned that for a dozen years, Google stupidly spend millions in reworking uselessly the UX twenty times but never solved real pmserious usability problems like this one!
A faster option is to install an HTTP or FTP server app on the phone, then download the photos through the network.
The only downside has always been that merging your photo libraries when you did two different things can give some funny results. Shotwell will split the events based on the import, but if you browse the files without shotwell or reimport them later you lose that.
YYYY/YYYY-MM/YYYY-MM-DD/YYYY-MM-DD.SHASUM.IMG_NNNN.EXT
https://randomascii.wordpress.com/2022/09/29/why-modern-soft...
So naturally the next step was to try to clean the directory. We tried through the webpage, deleting by chunks of 300 files consumed around ~8GB of RAM... and it was slow as hell, and her laptop is a bit old. I moved onto my desktop and selecting 500 files consumed ~10GB of RAM, it was still slow.
I thought of using Google Colab to access to the Drive as filesystem but no dice there either because the google account wasn't managed by her.
At the end, we tried the iPad app, it took like 8 minutes to be able to select all files, and when deleting them, it took about an hour to actually do it, I imagine it was submitted by batches.
It was stupidly painful.
Mounted a google drive as an FS on a linux box a while ago, worked very nicely.
GUI file managers are generally not designed for many thousands of files, especially web/mobile ones.
That's very strange that Classroom was creating files in root, however. It's supposed to create them in a single "Classroom" folder in root. You can move the folder if you like (e.g. as a subfolder) but there shouldn't even be any way to point Classroom to use the root-level folder for classes/assignments. (Plus the internal folder structure is hierarchical by class/assignment, so there also shouldn't be thousands of files/folders in a folder in any part of it.)
https://www.kernel.org/pub/linux/utils/fs/xfs/docs/xfs_files... (section 16.2 on PDF pg 127)
Ric Wheeler posted this nearly a decade and a half ago: "Strangely enough, I have been testing ext4 and stopped filling it at a bit over 1 billion 20KB files on Monday (with 60TB of storage)." and goes on to describe some performance numbers - which would be a lot better on modern hardware. https://listman.redhat.com/archives/ext3-users/2009-Septembe... There's a talk about it, as well: https://lwn.net/Articles/400629/
Unfortunately it seems like a lot of applications (unfortunately including ls) default to rather inefficient ways of enumerating files in a directory.
> With regard to solid-state storage, Ric noted only that 1Tb still costs a good $1000. So rotating media is likely to be with us for a while.
Here in 2023, 1 TB fast flash costs ~$50-100.
> What if you wanted to put together a 100Tb array on your own? They did it at Red Hat; the system involved four expansion shelves holding 64 2Tb drives. It cost over $30,000, and was, Ric said, a generally bad idea. Anybody wanting a big storage array will be well advised to just go out and buy one.
Nowadays, you can get 16 TB spinning rust disks for ~$15/TB, so a 96 TB array (without redundancy) would take 6 disks and cost $1500. If you wanted to use mirrors for speed and simple redundancy, you could build a full NAS that fits in 2U with a flash cache in front of 12 x 16 TB disks for well under $5000.
The there's also fun to be had when you start deleting those things. I've lost count of the number of times people are surprised that a delete is as expensive as a create or other io operation.
I've seen numerous efforts (Microsoft and BeOS spring to mind) to replace the filesystem with a database. Not aware of any big successes though.
The old image level 3 servers at Amazon were just image files layed down in a filesystem (hashed, with a directory heirarchy so that massive numbers of files per directory were not the issue). The problem that it reached was that you couldn't ever take one of them offline and you couldn't stream off of one of the block devices, so you were stuck enumerating through all the files. Those were something like 32kB average filesystem (or possibly slightly smaller). And that was on spinning rust with something like a 4ms seek time between files, and the end result was something like a couple months to go through the whole filesystem.
This is why the GoogleFS paper uses chunk sizes of something like 64MB so that data can be efficiently streamed.
This would explain why Web hosting providers often include inode limits in their terms of service.
They had millions of profile images but didn't want them all in one directory, so they hashed profile ID and used the first 2 letters as the name of a sub-directory. So you end up with sub-directories called aa, ab, ac, ad etc.
It's not perfect but I suppose the original creator had seen issues in the past when directories have too many files in them.
More realistically, you would use base32 or hex encoding. For example, if you want to store up to around 16 million files (2^24) and use a 64-bit hash with hex encoding (16 hex characters), you would use the first three hex characters (12 bits) for the directory name (since 2^12 is the square root of 2^24), and the remaining 13 hex characters for the file name. As a result, the 16 million files would be stored in 4096 directories with roughly 4000 files each.
Performing backups of our production apps used to take hours (especially in cheap clouds) because of all the loose files. Today, it takes about 3-5 minutes since there are just a handful of consolidated files to worry about.
And that might be better for accessing individual files outside the app instead of a big binary blob that you may have no clue on its format (or corruption/deletion of that single file). Thats why there are no universal solutions, there are many different use cases.
Nor does it let you start iterating through a directory with getdents(), then pause, then come back to iterate the rest of the files later. You have to receive every file name in the order the OS wants to give them to you.
That prevents applications really being able to make use of clever storage mechanisms - you can never find the most recent 3 files in a big directory with anything cheaper than a linear scan.
(But we have impressively speedy tools like Wiztree or Everything thanks to it.)
The most recent innovation for us is to use a lot of smaller SQLite databases, each scoped to a specific customer, session or unit of work. This is still far superior to loose records on disk, but you also get clear separation and reasonable firewalls between system entities.
There is zero reason a process would have more than tiny slowdowns with even millions of files in a folder. Finder has problems if you're trying to look at that folder, for obvious reasons, but it's a bit of a self-own for a backup co to claim that 200,000 files causes their solution to break. That speaks to serious algorithmic issues.
DISCLAIMER: This comment will be auto-dead because of moderation choices by dang (e.g. his pernicious need to pander to the anti-science, far-right crowd). This is a badge of honor. Never vouch for my comments.
I assume you are using Flex Tape as a derogatory comparison here. That said, I do view SQLite as a kind of "fix all" in the software world.
It's cheap (free), fast, everywhere and applicable to virtually every type of problem domain. AAA game assets to B2B line of business app storage. It's the most tested and used software on earth.
It doesn't fix everything, but it certainly gives you a fighting chance to make it to the next step.
Things like contact lists or game assets or even web history on individual computers will never grow to multi-TB sizes, hence no reason to over engineer them.
Might not be the most glorious or flashy solution, but like you mention, getting to the next step is all that really matters, IMO.
What kind of BS is this? Have you ever worked with one such folder? If you did, you would know that almost every app not doing some magic slows down to the point of being unsable (or even not working as described in original post). This is true for both Linux and Windows file systems.
a) 1M files in a single directory
b) 1k directories with 1k files in each
c) 1k aggregate files with 1k files in each
d) 1 aggregate file with 1M files in it
I think there's some filesystems that will work with option a, but any filesystem should work ok with the other options. Options c and d will make rsync much faster as you eliminate millions of syscalls.
It's usually a problem for any software that enumerates a directory for any reason, because that ends up being O(n) and often at least N system calls to e.g. get file information.
For instance when generating receipt PDF it could feel natural to store them in folders by account ID. Except there will be a bunch of accounts generating 20 or 30 receipts a day, which isn't much on the face of it. But within months it becomes a pain to list receipts across accounts, within a year or two even individual account receipts become a nightmare to list, and fixing the situation requires a few tricks to avoid all the tools that assume directory listing cost nothing.
I have been working on a new data manager that could replace existing file systems with something much better. You can store hundreds of millions of files in a single container (I call them pods instead of volumes) and put tags on everything. Folders can hold millions of files with virtually no degradation in performance. Searches to find subsets of files based on tags or other criteria is lightning fast.
The software has been in beta for about a year and is available for free download at www.Didgets.com yet interest has been very moderate in spite of problems like the one discussed in this thread.
demo video: https://www.youtube.com/watch?v=dWIo6sia_hw
Generally speaking, things that are expected to be "small" are processed as whole units. Memory is allocated to store the whole thing, a function won't return until it's processed the whole thing, the whole thing gets copied multiple times, and any kind of sorting/lookups often just scan the whole thing because with small things that's fastest/simplest.
When you expect something to be large, you architect things totally differently -- you buffer/stream rather than allocate, you pass pointers rather than copying data, you use indexes/hashes for lookups rather than full scans, and so forth.
And generally, filesystem paradigms are designed around small-number assumptions for number of files in directories, and hierarchy depths, and filename lengths, etc. Because these are all things you interact with using "human-scale" tools like GUI file managers and 'ls' commands. Whereas file sizes and disk sizes use large-number assumptions, because a video file is easily 10 GB or much more.
Memory was a lot more limited when those APIs were designed!
Then again, many programming languages expose simplified APIs for the exact reasons you describe. It's a lot easier to encapsulate all of the above when all you care about is getting an array of filenames in a directory, and then performing your own application logic to filter it further.
Quite a lot of systems use linked lists which make everything O(n).
And the worst part is this is unfixable without migrating away from APIs which have been frozen for about 40 years at every level in every single piece of software you're using.
(I used to work on an industry-leading sync product, Syncplicity)
In general, the UI in Explorer and Finder isn't designed to handle more then a couple-hundred, or low thousand, files in a folder. The whole UI metaphors just fall apart when you have millions of files in a folder. There's plenty of other applications that can handle such situations better.
Thus why optimize the filesystem? It's not a database, and if you need a database, you should use a database. SQLite is a wonderful database, and there are plenty more.
But, getting back to the APIs: Even though the Windows kernel and lower-level APIs will let you enumerate files in a folder via paging and filters, there's nothing that forces an application to use paging or OS filters. It might not even be possible: The Windows kernel sends wildcard strings to the filesystem driver; but it doesn't send regexes. So, if you need to filter files in a directory by names that match a regex, you have to load all filenames into your process.
A database like SQLite will have indexes and better filtering capabilities.
Furthermore, filesystems generally are block storage. Each file takes up, on disk, the number of blocks that it needs, rounded up. For example, your 10k file will take up a whole 100k block, if 100k is your block size. Again, a database like SQLite, (or a zip file,) will be much more efficient.
Anyone know of an alternative.
Basically we wrote temporary files into one big directory and later printed them. And sometimes our code returned "File not found" errors despite the fact that ls filename had showed the file is there and has correct permissions.
And when I tried to cat filename from shell - it also caused the same error :) But if you created another file with a different name in the same directory - it worked correctly :) There was also space on the disk, and the number of files was high, but not crazy high (a few hundred thousand I think)?
It turns out this particular filesystem (it was ext2 or ext3 with specific parameters IIRC) can behave like that when there's too many similarly-named files in one directory, because there's some metadata with hash of filenames in the filesystem and there can be collisions and it only can handle so many of them before failing.
The solution was to remove the files after printing them of course, so that they don't accumulate forever.
At the end of the day the filesystem is only part of the issue, quite often it's stupid application interaction where the designer of the application thinks they'll only ever see a few hundred or maybe a thousand files and you present the app with a million files.
Back in 2004, I played with file systems, metadata archives, directories with 20,000+ files in them.
Learned that at that time, GNU ls had a polynomial-time sort algorithm. I didn't dig into it as much as I should have, but there are sort algorithms that have already-sorted input as worst-case for runtime.
The claim was that the original files needed to be kept for audits, even after database ingest.
Management didn't care, but I made the change because I wanted to have my terminal not die if I accidentally typed "ls" in the wrong directory.
Is this true? I would've assumed that filesystems have smarter ways to find a file in a folder than to do a linear search through every entry.
That doesn't take away from this post, those smarter datastructures and algorithms will still grow slower with more entries, just not linearly so.
Not necessarily. Any file system worth its salt is using B-trees or hash tables, where file name existence can be checked in respectively O(log n) or O(1) time.
It would be nice to know which of these library folders can be cleared out.
Tell me you don't know how data structures work without telling me you don't know how data structures work.
- Open ‘current.json’ for append,
- write the new json,
- check file size,
- if it’s over a threshold (say 100MB):
- rename file (use UUID or timestamp)
A lot of weird shit starts happening once that folder hits about 10 million files.
"SQLite reads and writes small blobs (for example, thumbnail images) 35% faster¹ than the same blobs can be read from or written to individual files on disk using fread() or fwrite().
"Furthermore, a single SQLite database holding 10-kilobyte blobs uses about 20% less disk space than storing the blobs in individual files..."