How did we get saddled with the (hierarchical) filesystem as the basic data structure?

Question

I'm self-taught and I don't have a CS degree. The more I've been learning about data structure, the more I wonder, in this day and age, how are we still saddled with the filesystem, with directories and files, as the basic data storage structure on the OS?

I understand the simplicity of it, but it seems nowadays that there could be more options available natively. As far as I'm aware, the only project to improve the basic functionality of the filesystem was ReiserFS, where you could tell what line of a file was changed by whom, and when.

For instance, if I could have native tagging for files, where I could tag images, diagrams, word-processing documents, an entire code repository, all as belonging to a single project, that would really be helpful to me. Since I'm stuck in the filesystem paradigm, I know that I could put all those into a single folder/directory, but what if they already exist in disparate directories, and they need to stay there? I know there are programs out there that can do this, but why aren't they on the filesystem?

Something that would be nice to have is some kind of relational feature in the filesystem, like you get with RDBMSes. I understand that that was supposed to be part of Vista/7, but that fell off the feature list too.

Sure, any program can store a binary file and have any data structure it wants in it, by why couldn't the OS offer more complex ways of storing data, beyond the simple heirarchy of the filesystem?

Answer 1

Start with this: http://en.wikipedia.org/wiki/Unix_File_System

Read this: http://www.unix.org/what_is_unix/history_timeline.html

Then read this: http://www.amazon.com/UNIX-Filesystems-Evolution-Design-Implementation/dp/0471164836

There's a simple answer to "why couldn't the OS offer more complex ways of storing data, beyond the simple heirarchy of the filesystem?"

Because it's too much for the OS to do.

That's what libraries and application packages are for.

Oracle, for example, will sell you a file-system-like set of features that you manage with the Oracle toolset.

Python uses the DBM library to create very sophisticated on-disk storage structures.

CouchDB and Mongo (and others) are very sophisticated storage structures that offer some database-like features.

The point is that the OS should do the minimum and everything is an add-on.

Answer 2

The short answer is : Everyday people understand the file system. It reminds them of a file Cabinet. Think about web pages and even Fat apps, why do you think Tabs are so popular? People can identify with them, and understand them quickly.

Imaging trying to teach Grandma to search a DB for File based on property tags.. With the file system, Grandma knows the file is simply where she Put it.

Even with WinFS I don't think MS was going to get rid of the file system look and feel.

Answer 3

There's a little truth in every answer here but I don't think it's the whole truth.

What you list are mostly features that are sorely missed every day by users and developers alike.

People don't understand the tree-based file system any more than they would understand a DAG-based one.

And there's absolutely no excuse for the pathetic appendages of file names called extensions. They are not only completely unsuitable for their purpose (identifying the file type) but also an endless source of nuisance for users.

The reason we're still using them is a mixture of a "that'll do" attitude and the real need to maintain compatibility with older code. A new approach to storing files would mean a radical change in basic file I/O API, rendering most existing code useless. Either that or you have to tiptoe around them, maintaining the legacy API. Remember PROGRA~1.

I think for the reasons above, although the future could hold more specialised file systems for special applications, but while the desktop and laptop PC architectures of present survive, we're stuck with the largely tree-based file system with its lack of metadata and its horrible little extensions.

---

Now I'm going to switch sides.

Because it's all around us, we never really appreciate how mind-bogglingly powerful the tree metaphor is. On my hard drive I've got several hundred thousand files. If I have to find one, it rarely takes more than a minute, even if I know very little about the file. Now imagine the same task without any structure, just a flat list of names, scrolling endlessly.

Yet all the operations are straightforward, there's no spooky action at a distance, nothing that would make me go wtf.

Actually, I did implement a document store with rich metadata and a DAG-based hierarchy once. (It wasn't even a free-form DAG, it was strictly a two-level metastructure and the documents, which could be children of either a level 1 or a level 2 collection. So it's really simple.)

Obviously, the requirement that document names should be unique within a collection had to stay.

And then the problems started to flow. What if you open a collection and change the name of the document to something that clashes in a different collection the document also belongs to? We displayed an error message but the users were completely baffled. (These are the very same users who had asked for this requirement.)

They tried to delete a document, but all that did was remove it from the collection. So it still showed up in search results. We tried it the other way around too, but then they were complaining that they deleted a document from collection A and it magically disappeared from collection B. So we needed both an "unlink" and a hard delete operation.

Eventually we conceded defeat, fortunately still in time.

The extra search facets the metadata made possible worked an absolute treat though.

Answer 4

To be honest, I barely touch metadata on my files on the Mac. I think in the last 5 years of using OSX (which supports comments and so forth), I've used metadata on maybe 2 files. Not saying it's a bad idea.

I'm just not sure how the overhead of tagging is pragmatic for me.

I think the nicest filesystem feature that I know of would be a filesystem level versioning system... that works cross partitions. It was done on VAXen in the 70s and early 80s, not sure why it didn't catch on with Unix and NTFS/Windows.

Answer 5

I've worked with non-hierarchical file systems on older minis like HP3000 and Encore/Gould. You didn't have directories; you had a group and an account, and files were named as "group . account . file", like "users.jbode.myfile1", "dev.jbode.main", etc.

Now, these are old systems, where individual disk space quotas were in the single megabytes, so it's not like you needed too many levels to organize your stuff, but from a user's and programmer's perspective hierarchical systems are much nicer.

Answer 6

I don't see where (at least some) current file systems really need to do much [Edit: anything, to be honest] to support tags. When you get down to it, supporting tags means little more than some extra data associated with a file, but isn't written into the stream of bytes for that file.

NTFS (to choose one example that's in wide use) can do that just fine: as far as NTFS cares, a file isn't necessarily a single stream of bytes. On NTFS you can associate an arbitrary number of streams of data with a single file name. Each file has a (possibly empty) "primary stream" that doesn't have a name. It can also, however, have an arbitrary number of other streams, each of which must have a name. Using this, it would be truly trivial to add a stream named (just for example) "tags" to an existing file, and (obviously enough) write your tags to that stream.

After that comes the somewhat more difficult part: getting your tools to make use of the tags you put there. Ideally, you'd probably want to index them for fast searching, so you'd be able to do things like create a "virtual directory" of all the files with a specific tag.

At least from my perspective, the file system already has what's needed though -- it's supposed to store and retrieve the data, and it can do that perfectly well right now. Making use of that data is the job of other tools. Those tools don't currently exist, but the file system infrastructure to support them does.

If I'm allowed to be cynical for a moment, I'd say it was inevitable that this feature of NTFS would remain almost completely ignored and unknown. After all, it's simple to use and doesn't require any special API or anything else. You can use it quite nicely in completely portable C, C++, or anything else that will let you specify an arbitrary file name. Here's a quick bit of code to demonstrate creating a file with an AFS:

#include <fstream>

int main() {
    std::ofstream out("test.txt");
    std::ofstream tag("test.txt:tags");

    out << "This is the output file";
    tag << "tag1 tag2";

    return 0;
}

And, here's some code to read and display the tags:

#include <fstream>
#include <iterator>
#include <iostream>
#include <string>

int main() { 
    std::ifstream tags("test.txt:tags");

    std::copy(std::istream_iterator<std::string>(tags),
          std::istream_iterator<std::string>(),
          std::ostream_iterator<std::string>(std::cout, " "));
    return 0;
}

All very simple and easy. Note that although I've only written a trivial bit of data there, you can treat an AFS just like any other file -- all the usual "stuff" works just like with anything else. In a normal directory display, all that will show up is the primary stream (e.g., the size shown for the file will be the size of the primary stream), but if you want to see it, dir can show information about alternate streams as well with the /R flag. For example, a listing for the file created above looks like this:

03/16/2011  08:22 PM                23 test.txt
                                     9 test.txt:tags:$DATA
               1 File(s)             23 bytes