r/osdev • u/Kind_Skirt2397 • 14h ago
Question - Which Filesystem is best for you?
Like, someone pick ZFS or even ReiserFS... what about your Favorite FS and why?
r/osdev • u/Kind_Skirt2397 • 14h ago
Like, someone pick ZFS or even ReiserFS... what about your Favorite FS and why?
r/osdev • u/nerdycatgamer • 20h ago
Sorry if this too spam-y because I just made a post the other day, but I have had some more Thoughts and wanted to share!
I am currently working on a research project exploring a tag/set-based filesystem. That is, instead of having a hierarchical tree of directories, we have a flat filesystem in which every file has set of associated tags, and files can be queried by set-theoretic operations over tags: the unions and/or intersections of several tags. This is meant to be an abstract generalization of directories, as directories are structural and somewhat related to their implementation, whereas tags/sets are a more general way of grouping files, and the path of a file in a hierarchical filesystem could be translated to this tag/set based model by turning all the directories into tags and treating the "/" as intersection. This filesystem can also be seen as a hypergraph where the vertices are files and the edges are tags (this will come up later!!).
I have recently been chewing over the notion of "namespacing" and how I feel it is lost in this filesystem; in a hierarchical system, because of directories we could have identical subdirectories and files, but if they are hidden from each other by being in different directories then there are no problems. Particularly, I found this troublesome because it seemed that mounting subfilesystems would be tricky, and thus we would miss out on nice things like procfs and devfs. In my frenzy thinking about this, I think I lost the original reason why this was a problem (or maybe I was confused and there was no problem to begin with), because, like I said, paths in a hierarchical system can be translated to the tag system easily, and so there should be not expressive power lost(?) -- however! I did stumble upon something that is also very exciting and cool (possibly for a future research project :D) that I would like to get some feedback about.
As I mentioned before, the tag semantics can be seen as analogous to a hypergraph (which is a generalization of a graph which is a generalization of a tree!), so we can look at generalizations of hypergraphs (particularly the paragraph starting with "Alternatively"). We would also arrive on this structure just by thinking about allowing tags themselves to be tagged, which can get us something like "tag implications" to our boolean algebra of tags (set algebra is isomorphic to boolean algebra, although the analogous operation to implication would be subsets, and in this case it wouldn't be subsetting but rather nesting). In this way, we keep out tagging semantics, but also add hierarchical structure (although I am unsure how much this solves the "namespacing problem", which isn't actually a problem maybe?).
Now on this subreddit you guys are probably also wanting to know about technical implementation details, and I am excited to say that those also look very good. For my current tag based model (without nesting tags or anything, just plain normal hypergraphs), the tags are handled through a set of map structures: a mapping from FileIDs (64 bit integers) to bitmaps of TagIDs (64 bit integers), as well as an inverse mapping from TagIDs to bitmaps of FileIDs, the mapping from FileIDs to their inodes, and mappings from TagIDs to their textual (string) names and back (I have heard this is very similar to the structure the Apple Newton used for its Soup filesystem, if anyone could confirm). For these mappings, I use B+ Trees.
For the generalization, we could simply include another mapping from TagIDs to bitmaps of TagIDs. I was also chewing over the idea of unifying FileIDs and TagIDs as a single type of ID (you could say they share the same "namespace" now ;) but this is a different type of namespace than what I said before and completely unrelated, so please don't say that!) and having a mapping from IDs to bitmaps of IDs, but I don't think this is actually sufficient (we need to be able to identify the incoming and outgoing tags of tags, and files only have incoming tags).
This would be possible under the generalized-hypergraph-filesystem, where directories correspond to tags and "moving" a file or tag into a tag corresponds to adding that tagging it with that tag:
$ mkdir e1 e2
$ mv e1 e2
$ mv e2 e1
$ ls e1
e1/ e2/not useful, but I think it is cute :D there are definitely things to iron out (like preventing infinite loops with edges), and I don't know if this actually gets any additional power/usefulness over the simple tagging system based on normal hypergraphs, but it is interesting!! :D