Hacker News Reader

Comment by c0l0 | Hacker News Reader

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

View on HN

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.

I have used that method many times with success.

One side-effect is you can't go into a folder and type something like: `cp .doc` or `cp screenshots xxxxx`

./**/*.doc

Or `find -exec`

Except that will be very slow when you have millions of files

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.

Right; you're basically using the filesystem to implement an index based on the attributes of the file according to the expected usage pattern.

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.

Of course it depends on the filesystem. I’d be interested in what it is concretely, for each of the commonly used desktop filesystems.

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.

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.

https://www.sqlite.org/fasterthanfs.html

> 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'd be very interested in a more detailed write-up of what you did here -- sounds pretty impressive.

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

It's amazing how 1.2M entries in a directory is a pathologically slow case for a file system, but a trivial number of table rows for a database.

Of course, a B-tree is somehow larger than whatever was used to store inode data in the (ext2?) filesystem 25 years ago.

Reply on news.ycombinator.com