11 ms·

Folders with high file counts

89 points by mrzool 4y ago

bob1029 4y ago
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.
- bfgoodrich 4y ago
  One of the trends on Hacker News right now is the assumption that SQLite fixes everything. It's the Flex Tape of the software world. 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.
  - meindnoch 4y ago
    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?
    - yorwba 4y ago
      Account was banned in 2020: https://news.ycombinator.com/item?id=25399750 https://news.ycombinator.com/item?id=25399750
      - dx034 4y ago
        But why would that affect new comments if they’re able to create comments?
        dang 4y ago
        Banned accounts can post comments; the comments are killed by default.
      - meindnoch 4y ago
        Then how come I see their comments?
        dang 4y ago
        You turned showdead on in your profile.
  - bob1029 4y ago
    > It's the Flex Tape of the software world. 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.
    - username135 4y ago
      A solution to a problem is still a solution regardless of what it is. Might not be the most glorious or flashy solution, but like you mention, getting to the next step is all that really matters, IMO.
    - antisthenes 4y ago
      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.
  - pjc50 4y ago
    This is a weird fight to pick. 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.
  - majkinetor 4y ago
    > 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.
    - didgetmaster 4y ago
      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.
  - toast0 4y ago
    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.
  - dang 4y ago
    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 https://news.ycombinator.com/item?id=25399750. We banned your account because you were egregiously breaking the site guidelines.
- gmuslera 4y ago
  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.
  - bob1029 4y ago
    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.
  - aargh_aargh 4y ago
    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?
    - londons_explore 4y ago
      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.
    - dahauns 4y ago
      Well, NTFS works with B-Trees...so nope, it's not a silver bullet either, the bottleneck will just be somewhere else in the storage stack :) (But we have impressively speedy tools like Wiztree or Everything thanks to it.)
- NovemberWhiskey 4y ago
  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.
jakub_g 4y ago
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).
- totetsu 4y ago
  try adb-sync --reverse /sdcard/DCIM(?) ~/photos.go.here
  - dotancohen 4y ago
    adb-sync has been deprecated, use better-adb-sync instead: https://github.com/SelfAdjointOperator/better-adb-sync https://github.com/SelfAdjointOperator/better-adb-sync
    - totetsu 4y ago
      I saw that but I don't think the command changes as it still says adb-sync in the readme file of that repo you just linked…
- londons_explore 4y ago
  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.
  - qa-tari 4y ago
    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.
jakub_g 4y ago
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. https://randomascii.wordpress.com/2022/09/29/why-modern-software-is-slow-windows-voice-recorder/ https://randomascii.wordpress.com/2022/09/29/why-modern-soft...
makeitdouble 4y ago
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.
zeta0134 4y ago
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?"
ape4 4y ago
Don't modern filesystems handle this nicely - eg btrfs
- londons_explore 4y ago
  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...
  - pixl97 4y ago
    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.
  - klooney 4y ago
    Also `ls` in a big filesystem used to spend all its time allocating tiny chunks of memory- the breakage is pervasive.
- mprovost 4y ago
  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.
  - space_ghost 4y ago
    ReiserFS was my first thought when I read the headline. Fantastic performance on folders with obscene file counts.
- pixl97 4y ago
  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.
jonwinstanley 4y ago
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.
- pixl97 4y ago
  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.
- recuter 4y ago
  Seems perfectly fine. I remember having to do this trick on s3 for similar reasons.
- layer8 4y ago
  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.
jaxrtech 4y ago
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. https://www.kernel.org/pub/linux/utils/fs/xfs/docs/xfs_filesystem_structure.pdf https://www.kernel.org/pub/linux/utils/fs/xfs/docs/xfs_files... (section 16.2 on PDF pg 127)
- pjdesno 4y ago
  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-September/002807.html https://listman.redhat.com/archives/ext3-users/2009-Septembe... There's a talk about it, as well: https://lwn.net/Articles/400629/ 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.
  - aftbit 4y ago
    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.
  - ilaksh 4y ago
etra0 4y ago
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. It was stupidly painful.
- Nextgrid 4y ago
  FYI, "rclone" is a good tool to access proprietary cloud storage platforms from a consistent CLI.
  - Shared404 4y ago
    +1 Mounted a google drive as an FS on a linux box a while ago, worked very nicely.
- crazygringo 4y ago
  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.)
c0l0 4y ago
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 :)
- desro 4y ago
  I'd be very interested in a more detailed write-up of what you did here -- sounds pretty impressive.
  - tryauuum 4y ago
    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
- sixothree 4y ago
  At the same time, nobody would bat an eye at 1 million rows in a database table. People don't really start to notice until you hit 100 million.
  - bluedino 4y ago
    https://www.sqlite.org/fasterthanfs.html https://www.sqlite.org/fasterthanfs.html
  - morelisp 4y ago
    > 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).
mort96 4y ago
> 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.
NDizzle 4y ago
Oh, we ran into this years ago. Using the RedGate libraries to compare SQL database structure (and data) generates temporary files in a folder. A lot of weird shit starts happening once that folder hits about 10 million files.
aftbit 4y ago
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.
wittjeff 4y ago
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.
didgetmaster 4y ago
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. demo video: https://www.youtube.com/watch?v=dWIo6sia_hw https://www.youtube.com/watch?v=dWIo6sia_hw
Joker_vD 4y ago
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?
- pjc50 4y ago
  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.
- crazygringo 4y ago
  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.
  - gwbas1c 4y ago
    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.
thesz 4y ago
Obligatory: https://www.sqlite.org/fasterthanfs.html https://www.sqlite.org/fasterthanfs.html "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..."
guestbest 4y ago
This basically makes konqueror and dolphin unusable for me on Linux. I use pcmanfm instead
cratermoon 4y ago
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. 1 http://www.collyer.net/who/geoff/newspaper.pdf http://www.collyer.net/who/geoff/newspaper.pdf
red_admiral 4y ago
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.
sixothree 4y ago
Honestly, any program that chokes on just 200k files needs to be re-examined.
dmd 4y ago
[laughs in medical imaging] ... we often see folders with 10s of millions of files. Thankfully zfs doesn't bat an eye.
s1mon 4y ago
"Some of these can safely be deleted if you find crazy-high file counts." It would be nice to know which of these library folders can be cleared out.
nayuki 4y ago
> 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.
lairv 4y ago
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 ?
- Someone 4y ago
  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)
  - lairv 4y ago
    Would this get messed up if I write concurrently in the same file ?
    - Someone 4y ago
      Of course, but that can be prevented.
- fIREpOK 4y ago
  If you insist on 10kb files, you could use sub directories to split them up.
angst_ridden 4y ago
At previous job v.2, changed an IoT system that received daily text files from remote devices from dumping millions of them in the top level of the /data partition to using a /data/YYYY/MM/unit_id/ structure. 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.
watersb 4y ago
Bombich.com is a great source of filesystem feature deep dives. He started with running a backup lab, helped people with corner cases and common failure modes. He created a GUI Mac app to guide people through the gnarly bits, and later contributed metadata patches to rsync, for which I am truly grateful. 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.
puffoflogic 4y ago
> 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 Tell me you don't know how data structures work without telling me you don't know how data structures work.
ajuc 4y ago
Back in 2010s in my first job I've seen a bug caused by too many files in one directory. I don't remember the exact details, but it was making me crazy. 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.
lapcat 4y ago
Was this a problem on the older HFS+ file system too, or just APFS? HFS+ has a B-tree catalog and super-fast searchfs().

89 points by mrzool 4y ago

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.

bfgoodrich 4y ago
One of the trends on Hacker News right now is the assumption that SQLite fixes everything. It's the Flex Tape of the software world. 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.
- meindnoch 4y ago
  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?
  - yorwba 4y ago
    Account was banned in 2020: https://news.ycombinator.com/item?id=25399750 https://news.ycombinator.com/item?id=25399750
    - dx034 4y ago
      But why would that affect new comments if they’re able to create comments?
      - dang 4y ago
        Banned accounts can post comments; the comments are killed by default.
    - meindnoch 4y ago
      Then how come I see their comments?
      - dang 4y ago
        You turned showdead on in your profile.
- bob1029 4y ago
  > It's the Flex Tape of the software world. 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.
  - username135 4y ago
    A solution to a problem is still a solution regardless of what it is. Might not be the most glorious or flashy solution, but like you mention, getting to the next step is all that really matters, IMO.
  - antisthenes 4y ago
    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.
- pjc50 4y ago
  This is a weird fight to pick. 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.
- majkinetor 4y ago
  > 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.
  - didgetmaster 4y ago
    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.
- toast0 4y ago
  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.
- dang 4y ago
  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 https://news.ycombinator.com/item?id=25399750. We banned your account because you were egregiously breaking the site guidelines.
gmuslera 4y ago
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.
- bob1029 4y ago
  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.
- aargh_aargh 4y ago
  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?
  - londons_explore 4y ago
    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.
  - dahauns 4y ago
    Well, NTFS works with B-Trees...so nope, it's not a silver bullet either, the bottleneck will just be somewhere else in the storage stack :) (But we have impressively speedy tools like Wiztree or Everything thanks to it.)
NovemberWhiskey 4y ago
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.

jakub_g 4y ago

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).

totetsu 4y ago
try adb-sync --reverse /sdcard/DCIM(?) ~/photos.go.here
- dotancohen 4y ago
  adb-sync has been deprecated, use better-adb-sync instead: https://github.com/SelfAdjointOperator/better-adb-sync https://github.com/SelfAdjointOperator/better-adb-sync
  - totetsu 4y ago
    I saw that but I don't think the command changes as it still says adb-sync in the readme file of that repo you just linked…
londons_explore 4y ago
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.
- qa-tari 4y ago
  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.

jakub_g 4y ago

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. https://randomascii.wordpress.com/2022/09/29/why-modern-software-is-slow-windows-voice-recorder/ https://randomascii.wordpress.com/2022/09/29/why-modern-soft...

makeitdouble 4y ago

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.

zeta0134 4y ago

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?"

ape4 4y ago

Don't modern filesystems handle this nicely - eg btrfs

londons_explore 4y ago
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...
- pixl97 4y ago
  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.
- klooney 4y ago
  Also `ls` in a big filesystem used to spend all its time allocating tiny chunks of memory- the breakage is pervasive.
mprovost 4y ago
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.
- space_ghost 4y ago
  ReiserFS was my first thought when I read the headline. Fantastic performance on folders with obscene file counts.
pixl97 4y ago
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.

jonwinstanley 4y ago

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.

pixl97 4y ago
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.
recuter 4y ago
Seems perfectly fine. I remember having to do this trick on s3 for similar reasons.
layer8 4y ago
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.

jaxrtech 4y ago

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. https://www.kernel.org/pub/linux/utils/fs/xfs/docs/xfs_filesystem_structure.pdf https://www.kernel.org/pub/linux/utils/fs/xfs/docs/xfs_files... (section 16.2 on PDF pg 127)

pjdesno 4y ago
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-September/002807.html https://listman.redhat.com/archives/ext3-users/2009-Septembe... There's a talk about it, as well: https://lwn.net/Articles/400629/ 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.
- aftbit 4y ago
  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.
- ilaksh 4y ago

etra0 4y ago

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. It was stupidly painful.

Nextgrid 4y ago
FYI, "rclone" is a good tool to access proprietary cloud storage platforms from a consistent CLI.
- Shared404 4y ago
  +1 Mounted a google drive as an FS on a linux box a while ago, worked very nicely.
crazygringo 4y ago
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.)

c0l0 4y ago

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 :)

desro 4y ago
I'd be very interested in a more detailed write-up of what you did here -- sounds pretty impressive.
- tryauuum 4y ago
  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
sixothree 4y ago
At the same time, nobody would bat an eye at 1 million rows in a database table. People don't really start to notice until you hit 100 million.
- bluedino 4y ago
  https://www.sqlite.org/fasterthanfs.html https://www.sqlite.org/fasterthanfs.html
- morelisp 4y ago
  > 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).

mort96 4y ago

> 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.

NDizzle 4y ago

Oh, we ran into this years ago. Using the RedGate libraries to compare SQL database structure (and data) generates temporary files in a folder. A lot of weird shit starts happening once that folder hits about 10 million files.

aftbit 4y ago

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.

wittjeff 4y ago

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.

didgetmaster 4y ago

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. demo video: https://www.youtube.com/watch?v=dWIo6sia_hw https://www.youtube.com/watch?v=dWIo6sia_hw

Joker_vD 4y ago

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?

pjc50 4y ago
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.
crazygringo 4y ago
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.
- gwbas1c 4y ago
  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.

thesz 4y ago

Obligatory: https://www.sqlite.org/fasterthanfs.html https://www.sqlite.org/fasterthanfs.html "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..."

guestbest 4y ago

This basically makes konqueror and dolphin unusable for me on Linux. I use pcmanfm instead

cratermoon 4y ago

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. 1 http://www.collyer.net/who/geoff/newspaper.pdf http://www.collyer.net/who/geoff/newspaper.pdf

red_admiral 4y ago

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.

sixothree 4y ago

Honestly, any program that chokes on just 200k files needs to be re-examined.

dmd 4y ago

[laughs in medical imaging] ... we often see folders with 10s of millions of files. Thankfully zfs doesn't bat an eye.

s1mon 4y ago

"Some of these can safely be deleted if you find crazy-high file counts." It would be nice to know which of these library folders can be cleared out.

nayuki 4y ago

> 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.

lairv 4y ago

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 ?

Someone 4y ago
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)
- lairv 4y ago
  Would this get messed up if I write concurrently in the same file ?
  - Someone 4y ago
    Of course, but that can be prevented.
fIREpOK 4y ago
If you insist on 10kb files, you could use sub directories to split them up.

angst_ridden 4y ago

At previous job v.2, changed an IoT system that received daily text files from remote devices from dumping millions of them in the top level of the /data partition to using a /data/YYYY/MM/unit_id/ structure. 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.

watersb 4y ago

Bombich.com is a great source of filesystem feature deep dives. He started with running a backup lab, helped people with corner cases and common failure modes. He created a GUI Mac app to guide people through the gnarly bits, and later contributed metadata patches to rsync, for which I am truly grateful. 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.

puffoflogic 4y ago

> 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 Tell me you don't know how data structures work without telling me you don't know how data structures work.

ajuc 4y ago

Back in 2010s in my first job I've seen a bug caused by too many files in one directory. I don't remember the exact details, but it was making me crazy. 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.

lapcat 4y ago

Was this a problem on the older HFS+ file system too, or just APFS? HFS+ has a B-tree catalog and super-fast searchfs().