Hacker News Reader

Comment by nieve | Hacker News Reader

If memory serves the original EToys.com code treated the filesystem as tree-structured database using atomic operations (though no transactions). It worked just fine, then the rewrite with an RDBMS that should have been stabler and faster resulted in the famous meltdowns. Admittedly this is cheating a bit since you can name folders & files with semi-arbitrary or internally structured string keys. By 1997 standards pure disk access without having to walk the filesystem heirarchy was blazingly fast compared to many of the databases I was using.

[Source: I was friends with the guy who wrote it as well as other EToys employees. God that was a trainwreck.]

View on HN

Interesting, is there a blog around discussing this in detail ? If not would be kind enough to go more into detail.

I don't think anyone posted about their particular system, but it's not unknown now. If you google "filesystem as a database" there are some relevant hits. One super simple and probably not ideal, but at least balanced version uses a hash of some primary key like customer row id as the file index, then partitions the items into directories with all permutations at each level (or only populated ones) based on successive parts of the hash. For example an item key that hashes to a32c4214585e9cb7a55474133a5fc986 would be located somewhere like this:

  a32c/4214/585e/9cb7/a554/74133a5fc986
    a32c/
      4214/
        585e/
          9cb7/
            a554/
              74133/a5fc986

The advantage of this kind of structure is that you never need to manually scan a directory since you know exactly what path you're trying to open. You still incur the OS lookup time for the inode-equivalent in the directory entry, but a deeper heirarchy keeps that faster. You can trade off time to traverse the heirarchy versus number of entries in the final directories by adjusting the length of the hash chunk you use at each level. Two characters will put vastly fewer entries at a given level, but vastly increase your directory depth.

Basically if you're manually scanning the heirarchy for anything but a consistency check or garbage collection you've already lost.

One important note: make sure you carefully consider using atomic renames and such for manipulating the files! Overwrite in place is a great way to end up with a corrupted item if something goes desperately wrong and you're not protected by COW or data journaling.

Usually you write these sorts of things as append only with an optional garbage collect. You get a minimal sort of Atomicity with that.

That's how git stores its objects:

    18:35 $ tree .git/objects/
    .git/objects/
    ├── 02
    │   └── 9581d0c8ecb87cf1771afc0b4c2f1d9f7bfa82
    ├── 3b
    │   └── 97b950623230bd218cef6aebd983eb826b2078
    (...)
    ├── info
    └── pack
        ├── pack-b1fe2364423805afb6b1c03be0811c93b19dedc9.idx
        └── pack-b1fe2364423805afb6b1c03be0811c93b19dedc9.pack

    10 directories, 10 files

I was thinking of doing something similar as a lightweight embedded datastore: apply structure to the file system like you would a redis key.

Would love to talk to anyone on the EToys team or anyone who has done something similar.

I'm @akamaozu on twitter.

Unfortunately eToys imploded a couple of years later (2001) and there were only a few people involved at that stage so it's possible none of them are in the industry anymore. You might start by looking at email servers, I believe there are a few that use a deeply nested directory heirarchy for much the same reasons. IIRC Apple also does something similar with the interior of the sparsebundles used in Time Machine backups, but I don't know if any of that code is opensource.

Reply on news.ycombinator.com