Developers can do a lot to fix this by simply choosing SQLite to store all the local things.
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.
Wow. Indeed, practically all of your comments are dead. None of them seem off-topic though. How is this possible? Is there a gang of users who auto-flag all of your 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.
Once people realized that 90% of things aren't actually #BIGDATA, and SSDs became commonplace, it turned out SQLite is just good enough to solve those 90% things.
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.
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.
> There is zero reason a process would have more than tiny slowdowns with even millions of files in a folder.
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.
Exactly. Applications that are searching for files that have a certain extension (e.g. *.jpg) must read every directory entry and compare the file extension for that pattern. There is no magic call to the FS that says "Give me all the photos" or "Give me all the .jpg files). The application (including any command processors) have to do all that work manually.
If you've got 1M files, your alternatives include:
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.
Your comments are auto-dead because we banned your account. We told you that when we banned you: https://news.ycombinator.com/item?id=25399750. We banned your account because you were egregiously breaking the site guidelines.
Or at least using a multilayered approach i.e. all the files starting with A in the A subfolder. You still have to deal with that amount of files, but you don't lose so much time dealing with filesystem/directory operations.
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.
The multilayered approach is something we also do in one area, but at a certain point you are still playing dangerous games with the filesystem.
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.
I think the question should be why don't we have filesystems handle this implicitly using a tree structure behind the scenes. Are we so many layers above our hardware that it simply doesn't occur to us as the right solution?
The unix filesystem API doesn't let you "give me a list of all files in this directory matching this pattern".
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.
Historically, one of the reasons not to create one massive blob with all your stuff in it is containment of the blast radius of any kind of failure. The filesystem at least has (probably) reasonable consistency checking and repair tools, and you're likely to see integrity problems discovered at a file level, rather than experience catastrophic losses.
As a consumer of Android devices, one thing that's super annoying is that all pictures you take with a camera are stored in a single massive folder.
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).
Isn't that mostly because android devices use the old school "picture transfer protocol" mode, which involves a round trip to the device for every single object in a directory, rather than being able to just retrieve a directory listing in all one request like typical filesystems.
These days it's exclusively MTP as an extension to PTP that can transfer more than pictures, but similar problems with slow directory listings still exist due to the required translation between names and object IDs. Also the protocol does not support multiplexing requests, so you can't copy files while a directory is getting iterated.
I've always loved how shotwell does it: "YYYY/MM/DD/filename.ext"
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.
..and always with super helpful naming scheme like IMG_0001.JPG, IMG_0002.JPG, ... that restarts from the lowest unused number after cleaning up phone storage, ensuring you'll have naming collisions in your backup folder
Getting the images via e.g. Syncthing running on the phone does not seem to encounter this problem. Likely not over USB though, but Wireguard or better Nebula are easy to set up on both your phone and your router / NAS / desktop.
Yes, this is might constant nightmare too! Around 10k photo files Android starts to be painful to use. like app file browser taking huge to show the file list or crashing, and as you said, terrible experience when trying to get files on a computer.
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!
Bruce Dawson often finds issues in software linked to inefficient algorithms, and sometimes they're linked to slow folder enumeration on big folders. Example: Windows Voice Recorder enumerates files in a folder on startup in a interaction-blocking way.
This is an issue that is pretty common when auto generating files.
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.
So we found out the hard way that having MultiViews enabled in Apache, in your otherwise static folder full of image files, is a reeeeeally bad idea if that folder is filled by automation and contains millions of files. That was a fun support call. :) "Why is our site giving 500s after less than 10 minutes? What are all of those workers doing?"
Even if the filesystem handles it nicely, there are lots of applications which don't. So many applications think it's fine to iterate through every file in a directory for various reasons. If there are 10 million files in a directory, that is effectively a linear scan over a huge database table - which is generally advised against...
Heh, in Windows I've seen some applications do worse, they iterate the same file multiple times! Developer never noticed it because they look at 10 test files and never profiled their behavior, then you stick it in the customer environment and they face it at a huge directory and things explode.
ReiserFS handles this really well but I don't know if you can call it modern anymore. I can't think of any other filesystem that followed its design choices though.
Much better especially on SSD, but you still run into issues.
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.
I worked at a place where the directory was split based on a character or two from the start of a hash.
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.
Things like Squid Cache/Proxy did (does?) this so you don't stick millions of files on a buys cache in the same directory and kill performance. Especially back in the old days when things were on spinning disks.
Ideally, you want the number of letter combinations to roughly correspond to the square root of number of files you expect to store, to balance the number of directories with the number of files stored per directory. Assuming 26 letters, two letters allow 676 combinations, so the total expected number of files shouldn’t exceed ~457.000 (676 squared), or else each subdirectory runs the risk of containing more than 676 files on average (making it unbalanced with the number of directories).
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.
Perhaps this is one of the reasons that I've seen Linux deployments use XFS (e.g AWS). If you page through the filesystem documentation, once you hit a certain directory size, it actually switches over to using b+ trees like a RDMS would.
Nowadays ext4 has dir_index enabled by default, so it uses hashed B-trees for its directories.
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.
Thanks for sharing those articles. I found some of the specifics of price and size amusing in retrospect.
> 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.
Yeah, directories with a gazillion files tend to work okay if you already know the name of the file you're working with. ls has a -f flag which turns of sorting and turns off looking at the inode of the underlying files (is it a directory or a socket? ls needs to know to set the right color).
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.
ext4 still has an inode storage quota that is a fixed fraction of the total space available, so for small files, you will run out of inode space before you run out of block storage space. This alone makes xfs (which dynamically allocates inode storage) more reliable in these scenarios.
> ext4 still has an inode storage quota that is a fixed fraction of the total space available, so for small files, you will run out of inode space before you run out of block storage space.
This would explain why Web hosting providers often include inode limits in their terms of service.
Sure, that helps, for looking up a single file. Doesn't however help with ls or du. Even things like what are the 10 biggest files in this directory are painful.
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.
A bit tangential, but, recently my partner had her Google Drive with around ~3.000 files in the root folder (created mostly by Google Classroom), which means the Files app of the iPad couldn't show them all, because for some reason it limits to 500 files only.
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.
In case anybody else ever needs to do this, install the official Google Drive for Desktop client on a Mac or PC, and set it to stream (not mirror). And then just use the command-line to delete everything in one fell swoop.
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.)
At $oldjob, taking care of a busy and successful web estate that is now close to 25 years old, one of the ugliest and longest-standing warts was the "image store". That was a simple, flat directory on a single node, shared over NFS, which had accumulated more than 1.2 million (yes, 1_200_000) inodes/files in a single directory. No-one wanted (read: dared) to properly fix the code to rid it of this once-convenient assumption and (lack of) hierarchy, so I tried to work around the ever-growing pain by tuning the filesystem, the host's kernel (a buffed dentry cache size goes a long way at making this kind of abuse more tolerable, for instance), and the NFS server and clients involved to mitigate emerging problems as much as possible. In the end, a readdirplus()/getdents()-chain invoked over NFS only took a few seconds to finish. It's pretty amazing what Linux can cope with, if you make it have to :)
I think we had something similar at my old place, millions of files in one dir, shared over samba. It worked ok because each file was always retrieved by the full path (filenames were stored in a database) so no readdir was required
> nobody would bat an eye at 1 million rows in a database table
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).
I've dealt with a different situation before and handled it with sharding. It's pretty easy to retrofit in code, and it's not hard to do a one-time move of existing files to the new layout.
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)
The original name can be used to derive the sharded path, so you don't need a lookup database or anything crazy like that.
You end up storing files like:
.../7/7f/7fa/somefile.png
This scales to whatever depth you want: with 3 levels and 1.2 million files, you can expect about 1200000/16^3 = 293 files per directory, which is trivial.
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.dat
This seems like a better solution that just tweaking Linux to make it take only "a few seconds" to pull up an image. I'm curious what downsides/traps there are in this approach vs. sticking with the single flat directory.
Enumerating all images in the system over the network is what took a few seconds. "Pulling up an image" worked nigh-instantly, because contemporary filesystems have (and had) efficient indexes for the file(name)->data mapping(s) involved.
I wonder what the sweet spot is performance-wise regarding hierarchical depth vs. the number of entries in each directory, between the two extremes of putting all files in a single directory (depth 0) and using only one bit per directory (depth log(number of files)).
Depends on the filesystem that you use, like Dynamo vs Postgres
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.
Yes sure, the "successor" system that was eventually implemented to redundantly host BLOBs of all kinds used a very similar scheme - it's a well-known and effective technique for, e.g., on-disk caching in popular HTTP server implementations. The problem that kept us from doing something like this with out pile of 1.2M images was that there were several different codebases (and even a hand full of remote sites which had code that we knew relied on this assumption, and that we could not directly affect or change) that tied into this flat directory full of image junk in various ways (via the local filesystem, NFS, over HTTP, and I think even FTP was in use for a while after I had originally joined), which made it very hard to push through any breaking changes, no matter how architecturally sound they would have been.
The beauty of this is that you can slowly migrate data to the new schema, while serving files.
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.
> Adding a new file, for example, requires that the filesystem compare the new item name to the name of every other file in the folder to check for conflicts
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.
I have worked on a filesystem with 225 million files in a single directory, hosted on ZFS. Operations like `ls` took a minute or so to execute, but creating or accessing a file in this directory was almost the same speed as in an empty directory. I later replaced this filesystem with an sqlite database, which provided a pretty great speedup in table-scan type operations.
It's like they never heard of using a tree structure for filename storage.
NTFS used to (at some point this century) take O(n) time to give user control in the File Save dialog but they fixed that at some point.
This is just another in a long list of problems that existing file system have when built on an architecture that was created before there was sufficient storage to hold more than a few hundred total files (decades ago).
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.
Why is it actually so difficult for filesystems to deal with such folders? I mean, a million is not such a large number, not for a computer anyhow. A table with million rows doesn't generally causes a RDBMS to choke, why should filesystems?
Querying is done "client side", rather than in the filesytem API. If you request all million rows from the database and convert them in your ORM, and then query the ORM, you'll see the same kind of problem.
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.
It's a general issue that occurs whenever you scale from small to large things.
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.
Having a shipped a Windows filesystem driver, I can tell you that Windows's lowest level filesystem APIs "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"
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.
In general, filesystem code isn't optimized to handle millions of files in a single folder. It's generally optimized for thousands, and generally under 100,000 files per folder.
(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.
I think the article is talking about NFS (Network File System). My small experience with it suggests I should never use it due to extreme sluggishness.
"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..."
Way back in the 90s I read "New Need Not Be Slow"[1], about usenet, and one of the issues that came up consistently was performance limits because of the number of inodes and the filesystem. When I was tasked with setting up INN for my organization, I was able to get a DEC running OSF/1 with advfs, which at the time was a highly optimized filesystem, to more or less bypass the performance problems of UFS.
Meanwhile on the Onedrive desktop client, the cost of some operations is proportional not to the number of files in a folder you're trying to open, but in the whole filesystem. Your "root" folder can take a lot longer to load if /some/sub/folder has a ton of files in it.
> Adding a new file, for example, requires that the filesystem compare the new item name to the name of every other file in the folder to check for conflicts, so trivial tasks like that will take progressively longer as the file count increases.
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.
For an app I'm building I need to store each day ~1M json files 10kb each, which I then upload as parquet to S3. What is the alternative to using the filesystem here ? Should I put them in a database ?
Using the file system, but combining multiple json files into a single file might be an option.
- 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)
Your tooling would have to support that, of course (writing each json in a single line might be needed)
117 comments
[ 2.1 ms ] story [ 224 ms ] threadPerforming 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.
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.
Might not be the most glorious or flashy solution, but like you mention, getting to the next step is all that really matters, IMO.
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.
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.
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.
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.
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.
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.)
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
https://github.com/SelfAdjointOperator/better-adb-sync
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.
A faster option is to install an HTTP or FTP server app on the phone, then download the photos through the network.
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!
https://randomascii.wordpress.com/2022/09/29/why-modern-soft...
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.
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.
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.
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.
This would explain why Web hosting providers often include inode limits in their terms of service.
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.
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.)
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).
Simply put, you make an algorithm like:
The original name can be used to derive the sharded path, so you don't need a lookup database or anything crazy like that.You end up storing files like:
This scales to whatever depth you want: with 3 levels and 1.2 million files, you can expect about 1200000/16^3 = 293 files per directory, which is trivial.There's lots of other strategies, too, depending on your needs:
One side-effect is you can't go into a folder and type something like: `cp .doc` or `cp screenshots xxxxx`
Or `find -exec`
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.
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.
Of course, a B-tree is somehow larger than whatever was used to store inode data in the (ext2?) filesystem 25 years ago.
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.
A lot of weird shit starts happening once that folder hits about 10 million files.
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
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.
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.
(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.
"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..."
1 http://www.collyer.net/who/geoff/newspaper.pdf
It would be nice to know which of these library folders can be cleared out.
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.