4 ms·

A good use case for this might be a filesystem with a large number of files where one could quickly find recently changed files without having to sequential sca

A good use case for this might be a filesystem with a large number of files where one could quickly find recently changed files without having to sequential scan the whole system. Presumably the access and modified time would be stored as separate indexed attributes.

e12e 12y ago
I was going to reply with something along the lines of "modern filesystems should already have meta-data indexes".... because I thought I'd read about that in connection to ext4, btrfs and/or zfs. Now I'm no longer certain ... all I came up with was the following, which might be of interest: BabuDB (related to extreemfs.org): http://dl.acm.org/citation.cfm?id=1849822 http://dl.acm.org/citation.cfm?id=1849822 Spyglass: http://www.ssrc.ucsc.edu/pub/leung09-fast.html http://www.ssrc.ucsc.edu/pub/leung09-fast.html And more from the same researchers: "Scalable File System Indexing": http://www.ssrc.ucsc.edu/proj/fsindexing.html http://www.ssrc.ucsc.edu/proj/fsindexing.html Perhaps I'm thinking of reiser4? See also: TokuFS: https://www.usenix.org/conference/hotstorage12/workshop-program/presentation/esmet https://www.usenix.org/conference/hotstorage12/workshop-prog... https://github.com/esmet/tokufs https://github.com/esmet/tokufs I'm still certain I've seen talk of indexing metadata, and I thought it was in an actual, open, system...
- 286c8cb04bda 12y ago
  > I'm still certain I've seen talk of indexing metadata... This reminded me of BFS: https://en.wikipedia.org/wiki/Be_File_System https://en.wikipedia.org/wiki/Be_File_System
  - e12e 12y ago
    That could be it... thanks. I went as far afield as Hammer (DragonflyBSD) -- but didn't think to look at BeFS...
- XorNot 12y ago
  Metadata indexing isn't really a filesystem-level problem though, depending what you're trying to do. An index can be anywhere, and the data you want to keep is somewhat arbitrary - so why not just use a file on the filesystem anyway? There's also an important difference: metadata indices can be considered disposable in a lot of cases. File data isn't which means the constraints are different: with metadata you want to pack it all into the tiniest, most local part of the disk you can. With file-data (and the actual filesystem) you want to distribute and replicate that data as widely as possible to minimize the chances that a cluster of failures wipes out important structures.
  - e12e 12y ago
    The typical example (lifted from one of the links, I forget which) -- is looking at a huge filesystem, quickly seeing the files changed since a given date, which have the "archive"-bit set, query after files by name (unknown path -- ie, run "find") etc. Indexing on other meta-data, like tags for images and music files -- can be considered a filesystem level problem -- if one considers approaches like Mac (or Amiga) resource forks/info-files. Perhaps I should have stated "file metadata" as opposed to "just" metadata... One could of course claim that the only thing the filesystem does is take an exact path, and return the data at that path. In such a case, you could replace the path+name with a guiid, and store the filename and path-name info in a file... and update file whenever you accessed a file... and then you end up building some of that into the filesystem interface. So the question really is where the filesystem ends and the "system" starts...

e12e 12y ago

I was going to reply with something along the lines of "modern filesystems should already have meta-data indexes".... because I thought I'd read about that in connection to ext4, btrfs and/or zfs. Now I'm no longer certain ... all I came up with was the following, which might be of interest: BabuDB (related to extreemfs.org): http://dl.acm.org/citation.cfm?id=1849822 http://dl.acm.org/citation.cfm?id=1849822 Spyglass: http://www.ssrc.ucsc.edu/pub/leung09-fast.html http://www.ssrc.ucsc.edu/pub/leung09-fast.html And more from the same researchers: "Scalable File System Indexing": http://www.ssrc.ucsc.edu/proj/fsindexing.html http://www.ssrc.ucsc.edu/proj/fsindexing.html Perhaps I'm thinking of reiser4? See also: TokuFS: https://www.usenix.org/conference/hotstorage12/workshop-program/presentation/esmet https://www.usenix.org/conference/hotstorage12/workshop-prog... https://github.com/esmet/tokufs https://github.com/esmet/tokufs I'm still certain I've seen talk of indexing metadata, and I thought it was in an actual, open, system...

286c8cb04bda 12y ago
> I'm still certain I've seen talk of indexing metadata... This reminded me of BFS: https://en.wikipedia.org/wiki/Be_File_System https://en.wikipedia.org/wiki/Be_File_System
- e12e 12y ago
  That could be it... thanks. I went as far afield as Hammer (DragonflyBSD) -- but didn't think to look at BeFS...
XorNot 12y ago
Metadata indexing isn't really a filesystem-level problem though, depending what you're trying to do. An index can be anywhere, and the data you want to keep is somewhat arbitrary - so why not just use a file on the filesystem anyway? There's also an important difference: metadata indices can be considered disposable in a lot of cases. File data isn't which means the constraints are different: with metadata you want to pack it all into the tiniest, most local part of the disk you can. With file-data (and the actual filesystem) you want to distribute and replicate that data as widely as possible to minimize the chances that a cluster of failures wipes out important structures.
- e12e 12y ago
  The typical example (lifted from one of the links, I forget which) -- is looking at a huge filesystem, quickly seeing the files changed since a given date, which have the "archive"-bit set, query after files by name (unknown path -- ie, run "find") etc. Indexing on other meta-data, like tags for images and music files -- can be considered a filesystem level problem -- if one considers approaches like Mac (or Amiga) resource forks/info-files. Perhaps I should have stated "file metadata" as opposed to "just" metadata... One could of course claim that the only thing the filesystem does is take an exact path, and return the data at that path. In such a case, you could replace the path+name with a guiid, and store the filename and path-name info in a file... and update file whenever you accessed a file... and then you end up building some of that into the filesystem interface. So the question really is where the filesystem ends and the "system" starts...