3 ms·

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

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.
gwbas1c 4y ago
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.
ilaksh 4y ago
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. Anyone know of an alternative.

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.

gwbas1c 4y ago

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.

ilaksh 4y ago

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. Anyone know of an alternative.