Set Based Filesystem idea

http://www.aleveo.com/ideas/bsc-thesis-set-based-file-system

by dejan • 17 years ago

18 35 17 years ago

chiara• 17 years ago

I am not sure if the paths would be compatible.

It's a set of tags, not a hierarchy of directories. They're unordered, so the "paths" (which are really tag sets) would be equivalent.

silentbicycle11• 17 years ago

To use more conventional terminology, that would be a relational filesystem. Since a filesystem is a kind of database, this is another instance of the break between hierarchial and relational databases. Filesystems seem to have largely favored hierarchial DBs (with exceptions, e.g. http://en.wikipedia.org/wiki/Pick_operating_system), since following pointers to files from a containing directory is more direct than selecting from the whole filesystem. Filesystem extensions like symlinks are attempts to selectively add features that would come free with a relational filesystem, though.

Of course, a relational FS would still be broken up into namespaces (tables!), much like conventional filesystems frequently occupy multiple partitions. /sometable/tag+tag2+tag3 , for example, so searching for a file wouldn't necessarily mean searching every drive. There's no reason that making lots of small tables couldn't be cheap (they don't have to be disk partitions), and that would help constrain searching quite a bit.

Also, research into journaling filesystems has major parallels to database transactions.

alextp• 17 years ago

That's an interesting way of looking at file systems. I think among the pipe dreams of reiser4 there was a plan to make the fs itself more relational-like (but I also think this was relegated to a plugin and then promptly forgotten).

malkia2• 17 years ago

That indeed might be a good system for storing user documents, but not in general...

dejan10• 17 years ago

Why do you think so? I am trying to do a use case and it seems that the usage would not differ that much. The sets are still seen as folders, and have subfolders. The only thing is that the subfolder also owns the parent, but that is not noticeable due to the unique direction.

What I want to say is that Documents -> University or University -> Documents is the same, thus it makes sense. In real life the order doesn't matter.

Thus it opens a path for better HCI: computer, give me all documents from the university (all university documents)..

I am curios in what perspective you see this failing?

silentbicycle11• 17 years ago

They could be partitioned by department, so (for example) searching through math research wouldn't have to search the biology department's archives as well.

malkia2• 17 years ago

Contrived but possible:

src/share/test.cpp share/src/test.cpp

Also certain implicit build systems, rely on the hierarchy to know what is parent, and what is child. You lose that with sets.

I still think it's cool idea, but not for all of your documents...

Besides how would you deal with sharing, inheriting security attributes, etc?

If I have

share/test/something.cpp and share is shared to everyone, would

test/share/something-else.cpp got shared too the same way as the first one?

m0th87• 17 years ago

I've heard of this concept of 'set-based' filesystems (although with different terminology), and I think it's brilliant. And not just for documents either. Generally speaking, websites have moved away from storing data in a hierarchical matter (e.g. old-school Internet directories), and on to flat, tag-oriented categorization (e.g. delicious) because of the abundance of information to categorize. Hierarchies do not scale and are difficult to change, whereas free-form categorization do not suffer from this.

Personal systems have more files on them than ever before, and fitting them to hierarchies that were invented decades ago can be tricky. These issues have been abated for now with things like OS X's Spotlight and Win7's Libraries, but my suspicion is that set-based filesystems would be far simpler than the current paradigm.

A good example off the top of my head is resolving what command-line executables are available. In most operating systems, this is done by setting a PATH variable with a list of directories that contain the executables. While this is trivial for the type of people on HN, it is far from for your average user. Instead, command-line executables could be given a specific tag, and the command-line would be able to execute any application that has that tag.

Now, whether set-based filesystems could replace hierarchical ones is a different question. Such a filesystem would diverge so greatly from current assumptions that people might be too aversive to change. It wouldn't be the first time; I think Plan 9 was light years ahead in so many respects, but it never took off because it was such a radical departure.

mjl2• 17 years ago

luckily, you can implement the idea on top of existing systems. e.g. fuse or plan9/inferno's 9p/styx fs protocol.

"File indexing and searching for Plan 9", http://lsub.org/ls/export/tags.pdf describes mostly text indexing, but the interface to searching is through a file system (unfortunately not described in much detail at first glance).

only now do i remember that wrote something related once: attfs, http://www.ueber.net/code/r/attrfs. that's for inferno, using the styx/9p protocol. i never polished it, am not currently using it, and the interface the file system provides is not ready for casual file browsing, though that's mostly a detail (from an amount of code point of view). the things stored are strings though, not files. but the illusion that it stores files is easy to build.

silentbicycle11• 17 years ago

There's also libixp, a port of plan9's 9p to Unix. (http://libs.suckless.org/libixp)

I've only ever used it with wmii, but I've been looking for an excuse to write a Lua wrapper for it. :)

uriel• 17 years ago

There are many 9P implementations (most of which run on *nix systems): http://9p.cat-v.org/implementations

I think somebody was working on one in lua, but I don't know if they finished it.

If you write a Lua implementation or a lua wrapper for an existing C implementation let me know.

mjl2• 17 years ago

hah, and then i remembered hearing this talk at the iwp9 in madrid:

"ConcepOntoFs: A Semantic File System for Inferno", http://lsub.org/iwp9/cready/abheyshahplan9.pdf

this paper also has references to other papers on the topic.

dejan10• 17 years ago

Seems they make stuff just much more complicated there. I'll give it a better shot, but for now, new commands for the filesystem, it's just crazy. I want my grandparents to know how to use this, and I remember I always had to explain the concepts of cabinets, folders and files.

This is why I over stress the need for use cases.

The reasoning behind this idea is how I use my files, the intuitive processes to organize and later find, the flow of thought and command.

Hexstream• 17 years ago

"Obviously, with sets, the location can be described in several ways, so it is not a Unique Resource Locatior - only RL."

Wouldn't it be possible to implement the filesystem with tags and then specify an ordering of the tags to map the graph into the usual hierarchy? The first part of the URI would specify the mapping (maybe just a name for a particular mapping), and the second would traverse the hierarchical view in the usual way.

This way, legacy apps could still think in terms of a tree while exposing a more powerful structure to new apps.

dejan10• 17 years ago

Yes it would, but then the need for it is dim.

This was my biggest concern, to be backward compatible with legacy apps. And it is possible.

"C:\Program Files\X\Y\Z" - "C"+"Program Files"+"X"+"Y"+"Z" "/usr/local/files/" - "usr"+"local"+"files"

The only thing is that "usr" owns the file and so do "local" and "files" but the app doesn't care about that.

Legacy apps do not access the files directly but through the filesystem. If the filesystem knows how to convert these conventional paths into sets, there is no problem.

silentbicycle11• 17 years ago

I think worrying too much about reverse compatibility may be a bad idea. With access to relational features, the filesystems would probably be organized completely differently. Probably better to have a clean break.

dejan10• 17 years ago

I agree, but it seems natural using the same paths. No patches to the concept would be needed.

omouse• 17 years ago

>no one dares to reevaluate the underlying concepts that bound those layers. One of those underlying concepts is the hierarchical file system found on every personal computer of today as well mobile device.

I see someone hasn't read a single thing that Ted Nelson has written just yet.

dejan10• 17 years ago

The text is a bit too strong, and should be revised from the arrogance of 2006 :D Just copy-pasted it.

Indeed I haven't. I have to change that, thanks for the tip.

vicaya• 17 years ago

Actually, you can write a wrapper in your favorite language around your favorite database and call it your favorite filesystem, which is really a CMS.

dejan10• 17 years ago

not really. CMS is essentially different than a fs, but I see your point. While I won't go into explaining why it is, I have to say that some concepts from both should be brought closer. File should not be seen as a unit, but a set of tightly bound data. I wrote about this too recently, I'll post soon for opinions.

bayareaguy• 17 years ago

I recall this was one of the original goals of "namesys" (the file system that eventually became ReiserFS) but the paper describing it seems to be lost. The only reference I found after a short search are a few pages in a power point presentation[1] comparing it to Cyc. For the curious, the set "grouping" construct is on slide 7.

1- http://psy.st-andrews.ac.uk/foldiak/NamesysAndCyc1.ppt

skwaddar• 17 years ago

You want to make your way in the CS field? Simple. Calculate rough time of amnesia (hell, 10 years is plenty, probably 10 months is plenty), go to the dusty archives, dig out something fun, and go for it. It's worked for many people, and it can work for you.

-- Ron Minnich

Set Based Filesystem idea

Related Stories