Keeping resources tidy 2: Towards a metadata-based VFS?

So, in my last post, I have been discussing why I think that having a unified filesystem as a universal way to probe and locate system resources, like UNIX did, is a great thing. I also discussed why it appeared to me that UNIX and its successors designed it the wrong way, by using a hierarchical filesystem metaphor which turns out to be inappropriate when sorting out large amounts of data. I suggested that more clever use of file metadata might get around these problems, but didn’t expand on it yet. This will be the purpose of this post.

The BeOS case

Using metadata to classify files isn’t a new idea. Like tablet computers, it’s been popping up from time to time for decades, waiting for the right implementation to showcase its true capabilities.

For example, in the 90s, BeOS was the poster child for what an operating system with proper integration of file metadata was truly capable of. Through a supportive application ecosystem, where many applications took care to store their metadata about file in extended filesystem attributes, it was able to perform such tricks as building a folder containing all e-mails from a specific sender, or all music from a specific author, in a fashion that was dynamically updated as new content was added to the disk. With responsiveness that modern OSs could only dream of.

All this operating system needed at the time to perform this trick was a couple of standard metadata access primitives, a fast metadata index similar to what one would find in the internals of a modern database system, and most of all, application support. The design of the BeOS attribute and query system was extremely simple, and it needed to be as the computers of its days had extremely weak computing power by current standards. Yet to this day, the speed and relevance of BeOS’ filesystem queries has remained largely unmatched by modern operating systems.

The reason why this is, is that without true OS- and application-level file metadata support, competing OSs had to resort to using search engines instead, that explore the contents of files in order to deduce some metadata about them. This comes with the following caveats:

  • Parsing arbitrary file formats is a lot less efficient than parsing a well-designed metadata database
  • It requires code that is infinitely more complex, due to the amount of formats that must be supported
  • Individual file formats have variable, often pretty limited, metadata support
  • The search engine must be aware of what it’s looking for, and thus also have knowledge of all metadata there is
  • When indexes are used, care must be exercised to ensure they remain in sync with the files they are based on
  • Yet queries must be fast, and computing power must be used sparingly (especially in a battery-powered age)

For this reason, Microsoft have had a project for introducing true metadata support in Windows for decades now. Unfortunately, from the Object File System of the 90s, to WinFS in the early 2000s, they have continuously failed at it.

The problem, as it turns out, is not so much to design a good metadata storage and handling system, but to modify all of the core Windows applications and APIs so that they use it. With the ever-growing burden legacy code slowing them down, it is fair to say that even with the best of intents, Microsoft likely won’t ever succeed at reproducing or outperforming the achievements of an OS from the 90s.

Meanwhile, OSX power users will easily get excited when they get to experience a laggy and scope-limited clone of BeOS’ filesystem queries in the form of “smart folders”, which is essentially a saved search engine query that will only work on the file types that Spotlight agrees to support. It shows that although true support for metadata-based file organization isn’t there, a user base for it is undoubtedly waiting…

Lessons from the past

From the experience of the BeOS and Windows filesystems, along with other data organization software built to this day, there is a few things that one can observe:

First, stapling metadata onto a hierarchical filesystem isn’t going to do the trick. Metadata needs support from the whole application ecosystem in order to work. The reason why is that application developers have a lot less work to do in order to support metadata export for their specific business area, than OS developers have when supporting metadata import from every file format known to man. Developers simply need to be aware of it, and understand that this work is necessary.

Metadata must also be parametric. Fixed-function tags like those used by the OS X Finder or web CMS software are cute, but ultimately, due to their limited expressivity and arbitrary nature, they can only remain a fancy gimmick. A real standard organization primitive must provide users with the power to describe file properties, not merely group data by some ill-defined characteristics. Otherwise, we’re only recreating folders…

Then it appears that metadata schemes must also be future-proof. If you limit the storage capabilities of your metadata schema to what sounds “good enough” for your day, like the creators of the audio tagging scheme ID3v1 did, you’ll end up having to re-engineer it from scratch someday, once people will have attempted to take it far beyond its original purpose.

As the success of the SQL language and e-shopping website interfaces attest, searching for something by setting increasingly restrictive criteria on its metadata really works. It’s an awesome user interface primitive that everyone can understand.

As the success and shortcomings of SQL also attest, allowing one to query a database using dynamically generated statements in a procedural language is a great idea. But it has important security implications that must be taken into account. Less experienced users will also appreciate being presented with a discoverable GUI interface to such a query system.

An experiment that has been tried over and over again and consistently proved to fail is to put metadata tagging work into the hand of users. Not everyone is a skilled librarian, and not everyone wants to be. All metadata that can be generated in software, should be, and user-set metadata should be input once and remembered until further notice.

Another experiment that has consistently failed is to compensate for the lack of file metadata by better search engines. Not everyone can do the job of Google or Yahoo, and most certainly not your average battery-powered computer.

Similarly, a hard lesson learned by projects like KDE’s late NEPOMUK, is that even in this century, performance still matters. Operations to append, access and alter metadata must be extremely fast, and scale well in CPU and memory use in all envisionable tag growth scenarios. Better fast than sorry.

And finally, a lesson from OS and web development is that caches as a mitigation strategy for low performance have their issues. Maintaining coherency between cached or indexed copies of data and the actual data they originate from, is extremely difficult. And it is also ultimately a performance bottleneck that should be avoided whenever possible.

Design considerations for a metadata-happy future

Today, hierarchical filesystems perform two functions simultaneously. They allow us to organize our data, so that we can find it again subsequently, and they allow us to refer to a specific piece of data through a path entity such as “/bin/bash”.

It appears to me that mixing both of these functionalities is harmful, because it means that the ability for a program to *retrieve* a piece of data is tied down to the way a user has *organized* its data. This makes it very difficult to change the filesystem organization as soon as some piece of software has grown to rely on it, as pretty much anyone who has packaged software for multiple Linux distributions can attest.

Instead, what I’d wish for instead is something like this :

  • Files and other resources should have a universally unique identifier (UUID) that represents them, regardless on which computer they are moved. This number should be at least 128-bit, 256-bit if you’re truly paranoid.
  • When software needs to access to a specific file, it can refer to it by its UUID, which would be returned by standard OS primitives such as GUI “file open” dialogs. This allows file identifiers to always remain the same, regardless of user organization whims, and even if both the file and the program referring to it are moved to a whole different machine
  • Most of the time, however, software should be able to undiscriminately deal with single or multiple file input, much like a number of UNIX commands like “cp”, “rm” and “mv” will readily deal with lists of files as input instead of single files

The latter allows for particularly nice things, like parametrizing file operations by filesystem queries instead of mostly static file paths. Think about good old wildcards like “*”, but taken to a whole new level of awesomeness. BeOS’ “query” command, for example, allowed one to select all files in the filesystem whose age was greater than a certain value.

It also seems important to me  that metadata be only destroyed for good reason. This requires cooperation from application developers, who receive plenty of metadata about the data they manipulate, but it also raises questions on what such a good reason might be, which I’ll touch more upon when discussing metadata security in a moment.

Metadata should also be designed so as to reflect objective information. Things like star-based user ratings should not belong to metadata (well, standard system metadata at least), because they are variable from one user to another, and will thus become useless as soon as files are transmitted from one person to another.

In general, standard system metadata should probably be designed in a cautious and conservative way, even though one must be careful not to alienate end users and application developers in such a way that the non-standard ends up becoming a de facto standard, like in the OpenGL Extension Hell.

A relevant question, to which I have no answer is that of metadata organization. Parametric metadata has a lot more expressive power than folder hierarchies, so theoretically, a small amount of metadata would be enough to characterize a certain file or set of files. However, what metadata exactly is needed varies from one use case to another, and for this reason, it is envisionable that the metadata namespace might still grow quite a bit over the lifetime of a metadata-using operating system.

So, would hierachical namespaces be good enough for metadata itself? I have no answer yet to this question, nor do I have an idea of how to find such an answer. Unless I can, the most failure-proof way I can think of going at things, is to give metadata itself unique, random identifiers, so as to have an organization-agnostic way to point at it.

An obvious design point to keep in mind is that software should never expect a file to have a specific piece of metadata, unless it has set it itself, or it is extremely basic metadata like a UTC modification time. That’s because files may come from a variety of sources, some of which may have no support for metadata itself, and also because a freshly created empty file has no reason to have any significant metadata attached to it.

Conversely, the reason why metadata should be supported at the OS level, rather than implemented in an ad hoc fashion by third-party software like GNOME’s Activity Journal or KDE’s Baloo on Linux, is that metadata is only useful if it is reasonably complete. This completion, in turn, requires the cooperation of all applications that manipulate files. Not just applications following a specific framework, desktop environment, or other computing religion. All applications which advertise compatibility for the OS, including CLI and very obscure ones.

Finally, there is the question of security, which I hinted at earlier. Is there an intrinsic risk in sharing metadata or, in other words, can metadata be private information, much like data itself can? Obviously, the answer is yes. For example, if I know that you’ve used a communication system to call, in rapid succession, a gynecologist, your current sexual partner, and your parents, I can use this metadata to guess private information about you, without having access to the content of the communications themselves.

A quick rule of thumb might be to state that system users should not be able to access the metadata of a file if they have no access to the file itself. But that rule needs further thought for a couple of reasons:

  • In an OS where the preferred method of file lookup is metadata, it means that if you have no access to a file, you have almost no way of knowing that said file even exists. Is this desirable?
  • What if sometimes, we are ready to share some data about a file, but not all the metadata that the OS knows about it? For example, in a metadata system having the very powerful ability to relate files to one another, what if we want to share a report about cancer that we wrote for work, without sharing the OS-recorded relationship between that report and a family member?

A particularly salient issue, in this respect, is that of sharing data with a metadata-oblivious OS : when recording files on an external support, should we also copy the metadata of the files recorded on that support, knowing that the target OS will either be able to read all of it, or none of it?

These are all very interesting questions, to which I have no answer at this point, but which need to be answered before the design for a metadata-based filesystem can be finalized.

Per-file, per-drive, or OS-wide?

Now, all this is all fine and good, but where should the generated file metadata be stored? In a non-hierarchical filesystem design, there are essentially three possible places for storing metadata in a privacy-preserving way:

  • On a per-file basis, using extended file attributes
  • On a per-drive basis, in the form of a big database at the root of each physical storage volume
  • On an OS-wide basis, in the OS’ system files

The per-file option has been the most used in the past, because due to its fine granularity, it has a number of very seducive properties. First, it makes it easiest to keep metadata and the file it points to in sync, even when storage drives are tampered with by metadata-oblivious OSs. For example, when a file is deleted, its metadata is automatically disposed of as well.

Another benefit of per-file metadata is that it addresses some security concerns related to having one huge database of metadata that software either can access as a whole or cannot access. However, note that a disk-wide database of metadata does not have to be composed of a single file. For example, it can be stored as a hidden directory that contains many files, each with their own limited contents and specific access policy.

A drawback of per-file metadata is that sometimes, it is not an efficient way to store metadata. For example, assume that you want to group files together according to some criteria. If you try to express this with per-file metadata only, you’ll need to specify, for each file, which file it is related to, a technical solution that scales as O(N^2) with N the size of the group. Whereas if your metadata database has a proper “file group” primitive, you can achieve O(2*N) scaling, by storing a file group primitive that scales as O(N), and N references to that group in each file. For large groups, this will make a world of difference.

For another example of per-file metadata storage inefficiency, consider some heavy metadata being shared by a number of files. With per-file metadata, it is impossible to store the heavy metadata once, and have every other file point to it. Each tagged file must instead carry a copy of the heavy content. Things get even worse when one realizes that every time the heavy metadata is modified, all files including it have to be modified to, which may be very difficult to do.

Finally, what is in my opinion the final nail in the per-file metadata coffin is that extended attribute support is very inegal across disk filesystems. Popular filesystems such as FAT32 or HFS+ have either limited support for extended attributes, such as arbitrary size limitations, or no support at all. Worse yet, implementations of these filesystems may not even handle their extended attributes properly. For example, many Windows backup programs inadvertently destroy NTFS’ Alternate Data Streams, which are the NTFS way to store extended file attributes.

Many popular communication channels, such as e-mail, also have no complete support for the transmission of file metadata. I’ll expand more on the issues that this raises in a bit.

This leaves the choice between per-drive and OS-wide metadata, where the difference essentially lies in whether disk drives carry metadata along with the files it points to, or whether metadata is an OS-managed entity that must be explicitly exported by a user to a drive. Here, the right choice is not so clear: external drives seemingly require per-drive metadata storage to be useful, but as discussed above, such external metadata storage has unfortunate security implications that should be further studied. Moreover, the proper way to manage metadata that crosses physical disk drive boundaries remains then unclear. Should it be duplicated upon drive disconnect, and synced back upon drive reconnection?

Interactions with metadata-oblivious systems

I have previously mentioned that not every data storage and transmission protocol has built-in support for storing metadata. In the case of disk drives, a way to manage this situation is to store metadata in a database that is built using very basic filesystem primitives, such as files and hierarchical folders. Such a database must be resilient to drive tampering by a metadata-oblivious OS, which can be achieved by taking the following precautions:

  • Metadata should be bound to a file using file identifiers that a metadata-oblivious OS do not usually tamper with. For example, in UNIX filesystems like the extX family, inode numbers could play that role, so long as it can be established that implementations will not reuse inode numbers too quickly after a file is deleted. Where even limited extended file attribute support is available, storing file UUIDs inside of them could be a more robust option.
  • If a piece of metadata has security implications, it should be encrypted. Alien OSs cannot be trusted to respect file access permissions.
  • When metadata ends up orphaned and pointing to no real file after tampering by another OS, the metadata-aware OS should dispose of the metadata through the appropriate way to dispose of user data (e.g. “trashing”).

Preventing foreign OSs from breaking everything they touch is only part of the story, though. Another important concern is to ensure that they can access metadata-indexed data with reasonable ease. This could be achieved by mapping metadata-based organization onto legacy folder hierarchies, through automatic generation of such folder hierarchies by queries into the metadata filesystem.

For example, for music files, such an automated folder hierarchy could take the form of <Artist>/<Album>/<Track number> – <Track name>.<Legacy file extension>. This is actually what most library-based music players do when tasked with the need to store their music files on a hierarchical filesystem, in a user-accessible way.

This obviously requires more thought than a single blog post allows for, in order to take into account all possible use cases.

Because of a need for compatibility with existing OSs, tampering with file formats in a fashion that makes them metadata-friendly, such as by wrapping metadata and data together in a tar archive file, is also out of question. This means that when metadata-tagged data is sent through a metadata-oblivious communication channel, such as e-mail attachments or web file upload dialogs, metadata should either be sent separately, or not sent at all.

External storage considerations

Finally, there is the question of how to handle removable storage media, and other kinds of blind sharing with other computers, in a metadata-based filesystem. When an external media is removed from a computer, it means that the data and metadata it contains are physically decoupled from that of the computer it originates from, and may change independently.

Consequently, at the time where the drive is plugged back in, the metadata databases of the host OS and the guest drive should be considered out of sync, and only merged with one another after proper consistency checks have been performed. For example, if the metadata of an external drive is changed, it should not result in an alteration of the metadata database of the host OS, unless the user has explicitly agreed through such a syncing endeavor.

Synchronization pains can also appear when files themselves contain metadata, as is the case with audio files (ID3 tags), office suite documents, and many other kinds of files. The interaction of such file-specific metadata with a unified metadata database can also be a significant source of headaches, as we have seen by discussing the failure of OS search engines earlier.

There is no general way to solve this last problem, as an OS cannot extract metadata from arbitrary files of unknown format. However, for known file types, one might envision applications providing simple OS extensions that feed the metadata database with file-specific metadata, similar to how BeOS let any file type be translated to any other analogous file type through the use of simple application-provided “translator” system components. Of course, as any time applications are allowed to plug into operating system features, the security implications of such a pluggable metadata framework must be thoroughly considered.

Still, solving this problem sounds worthwhile, as it would be a reasonable way to avoid storing multiple metadata copies, that will end up being out of sync like any duplicated data does.

Finally, a last issue to take into account when external storage is added to the equation is that of file access latencies. In a unified virtual file system, the speed of filesystem-wide data searches is limited by the slowest link, which in the case of networked filesystems or slow physical drives can really be extremely slow. This may make unified virtual filesystems impractical if metadata is to be used as a unified storage metaphor, favoring more stringent physical medium separation as is performed on the Windows operating system, but further research is needed to confirm or invalidate this conclusion.

Cool perspectives

Now, by enumerating all the ways in which metadata-based filesystems are a lot more complex than their hierarchical cousins, I may give the impression that they are an unnecessary hassle, and that folder hierarchies, although largely unusable for large amounts of files, are the best practical option for computer data storage. Obviously, that is not my intent, so let me also show how awesome a working metadata-aware virtual filesystem could get.

  • In a true metadata-aware virtual filesystem, file extensions and their namespace collisions are a shadow of the past. File types can be specified in great details in the file metadata, using MIME and post-MIME schemes. In fact, it’s possible to envision efficiently storing entire file format specifications in shared file metadata.
  • Due to metadata’s greater expressiveness, many file type ambiguities that cannot be discriminated by space-constrained extensions can be removed. For example, by embedding locale information into CSV files, it is possible to solve the longstanding comma versus dot number manipulation bug that every user of non-English number formats is painfully aware of.
  • Since file documentation can be stored in the file metadata, traditional UNIX-style configuration files filled to the brim with self-documentation comments can finally die and rid the world of their ridiculous parsing inefficiency.
  • If files have unique identifiers, there’s nothing preventing the user-visible file organization to change. So we can envision going as far as to dynamically generate folder hierarchies based on filesystem queries, as discussed previously in the specific context of interoperability with metadata-oblivious systems. For example, drilldown-based user filesystem searches could be saved for future use in the form of a folder hierarchy representing the successive metadata parameters that were being drilled down.
  • Metadata can be used to dynamically generate other metadata. For example, file modification timestamps can be turned into more directly useful file age metadata, representing how long it’s been since a file was last written to.
  • Another kind of metadata that can be dynamically generated, rather than static, is situational tags, that relate to the current properties of a piece of data, rather than its intrinsic properties. For example, in a UNIX-style single-root filesystem, the storage media which a piece of data is stored on could be expressed as such situational metadata.
  • Favoring programs which can take multiple file input opens interesting opportunities for OS interaction metaphor. For example, one could envision using parallel map/reduce as a paradigm for bulk file processing, instead of relying on UNIX-style sequential pipes of filename inputs.
  • While a well-designed metadata system with application cooperation greatly reduces the need for manual file organization, it can also make it a lot more powerful. Knowledgeable users can use metadata to store data in as elaborate a custom organization scheme as they want, rather than being stuck into the limited framework of a static folder hierarchy.

Hoping that this will convince you that metadata-based filesystems are not just difficult and a necessary evil, but rather a formidable opportunity to dramatically improve the way we organize data and other system resources, I will, for now, conclude this post here !


Footnotes

  1. These days, future-proof standard for addressable entities in physical filesystems and addressable computers on the internet both call for 128-bit numbers. In this situation, if you’re as paranoid as people designing such mission-critical infrastructure, traditional 128-bit UUIDs with 122 bits of truly (pseudo)random data might start to feel a little vulnerable to collisions for resource identifiers that must be unique across the entire universe. To address such concerns once and for all, a solution is to move to the next power of two and use 256-bit UUIDs. These may be obtained, for example, by combining the locally unique identifier of a resource on a computer, with a globally unique identifier for the computer which generated said resource id. However, this solution also has unfortunate privacy-violating implications, and I would thus find random 256-bit UUIDs preferrable if lack of backwards compatibility with existing UUID implementations is not an issue.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s