Re: File as a directory - back to predicates

Re: File as a directory - back to predicates

[Leo Comerford]

Firstly, I apologise for the absurdly late reply! Secondly, I'm going
to backtrack for a bit here. Let's forget about relations for the
moment, and concentrate solely on single-place predicates. I also
apologise for (partly) repeating myself at length like this, but this
time I have what I hope is a really nice explanation. So:

Consider an absolutely vanilla registry-type thing of the kind that
Joe Code would produce if you asked him to implement a metadata system
for files/objects/documents/whatever. Users can assign arbitrary
name-value pairs to the objects in the registry; they can also
delete/edit the pairs. And, of course, they can view all the
name-value pairs associated with a given object. The names are
strings. The objects are opaque binaries to the registry. So, in use,
a photo object in the registry might have something like the following
pairs associated with it:

date_taken="2004-03-04"
title="My dog Spot"
type="photo"

(The order in which the pairs are listed is obviously arbitrary.)

Now note that the registry system could use Unix-style segmented
path"names" instead of name-value pairs, in the cases where the value
is a sufficiently short string. For example, we can think of

date_taken="2004-03-04"

as alternative to

date_taken/2004-03-04

which could be further parsed up into

date_taken/2004/3/4

. There's nothing magic about name-value pairs: each one simply
asserts a predicate just as a Unix file"name" does. In fact, a
name-value pair where both the name and value are strings is in effect
just a limited Unix path"name" which must have exactly two segments.

So our mark-2 registry system assigns its objects Unix path"names"
instead of name-value pairs, and the photo object might have have the
following ones:

date_taken/2004/3/4
title/My\ dog\ Spot
type/photo

Isn't this new registry fundamentally very similar to a Unix
filesystem, in which each file has one or more such path"names"? No,
better than that. It *is* a Unix filesystem, subject to a few caveats.
It has the same syntax (it's built of files and pathnames); it has the
same semantics (pathnames express propositions which are asserted of
files); all it need is an implementation which can expose these to the
OS by being mounted. So a completely simple-minded iteration of the
registry "pattern", without any consideration for namespace
integration, Unix philosophy or what have you, translates almost
effortlessly into a Unix filesystem which uses the standard semantics.

This is strong evidence for the power of that filesystem, using those
semantics, to integrate different namespaces into itself. But more,
our registry is a data-to-metadata system: it is designed to allow the
user to find the metadata that has been associated with a particular
piece of data. ("When was this photo taken?", which in our revised
registry becomes "what date_taken path"name" does this file have?".)
Registry systems in general, file streams, stat blocks, subfile
metadata, and the old Macintosh resource fork are all data-to-metadata
systems. By contrast, the Unix file naming system is a
metadata-to-data system, designed to allow the user to find one or
more pieces of data (files) through the metadata that has been
associated with them. ("What photos were shot in 2004?", becoming
"what files are "in" the directory date_taken/2004 ?") But in the
example above, registry data - the metadata of the classical
data-to-metadata system - is being expressed in Unix filenames using
the standard semantics - the language of Unix's classical
metadata-to-data system. This shows the power of the Unix filesystem
to integrate both "d-to-m" and "m-to-d" systems into the one namespace
- the one language of pathnames-as-predicates. This is not so
surprising when you consider that at the semantic/logical level both
types of system are exactly the same: they both just associate
metadata with data.

At other levels, of course, the differences assert themselves. For one
thing, the normal Unix filesystem API doesn't have calls to, for
instance, check the path"names" asserted of a given file. That's
easily solved; just add the calls. Less easily solved are the
performance issues. rmdir date_taken/2004 is going to be rather slow
on a registry-type volume which contains many files, just as listing
all the pathnames through date_taken to a particular file is going to
be relatively painful on a volume which is closer to a traditional
Unix filesystem implementation. The important thing here is that these
/are/ *performance issues*, although certainly not trivial ones. By
stripping away the superficial differences between m-to-d and d-to-m
systems, we have revealed the real difference, performance. The
situation is similar to general programming languages. No-one would
dream of creating a language which has, say, two radically different
and incompatible function call interfaces, one of which is supposed to
be used by functions whose time performance is O(n) or better, while
the other is for > O(n) time functions. But of course we still have to
pay attention to the performances of our function implementations and
make decisions about them.

So, for example, if we decide to represent shooting-date metadata for
a vast number of photos using date_taken pathnames as above, we then
have to decide whether to place date_taken and its subdirectories on a
volume which will let us quickly find what the shooting date of a
given photo is, or a volume which will let us quickly find which
photos were shot in 2004. (Of course the photos don't, or shouldn't
have to be, in the same volume as the directory information in either
case. I'll need to say more about links again sometime.) This is just
like choosing between the array and the linked-list implementation for
some instance of a collection type. One freedom this gives us is that
we can later change the performance tradeoffs by moving date_taken
onto a different volume without breaking code that understands
date_taken .

Of course, the best choices are the ones you don't need to make. What
we /really/ want is a filesystem implementation that gives us
usually-good-enough worst-case performance both in space and in the
time required for all the common data-to-metadata and metadata-to-data
searches as well as all common changes (including moving directories),
all while providing other important features and not being too
arbitrarily limited. Then most of the time we could defer or avoid
worrying about performance by just putting our data on a volume of the
general-purpose filesystem implementation. (Special-purpose
filesystems offering better performance under certain conditions would
be used for further optimisation when necessary.) But while not having
to make performance trade-offs is convenient when we are laying out
metadata, it's even more valuable when we are using it. After all,
having to choose between being able to say when any specific photo was
taken and being able to find all the photos taken on some date is a
horrible decision. We're likely to want to do either or both. Again,
in reality there's just data and its metadata, so it's no surprise
that metadata doesn't divide conveniently into "d-to-m metadata" and
"m-to-d metadata". Even when we assume that some metadata is only
going to be useful in one "direction", we're quite likely going to be
proven wrong.

I don't know if a good-enough all-purpose filesystem implementation
like this is possible; I don't know what can pass as "good enough"
performance for every filesystem task, and I don't know if the hard
bounds on possible performance allow an implementation which is "good
enough" on all counts to exist. But I do know how great it would be to
have that filesystem if at all possible, or failing that one which
comes close without making too many horrible compromises.

That was the most, and least, important caveat; now for some others.

Just because we know that a file is a photo or that it was taken in
2004-03-04 doesn't mean that we don't want it to be deleted. So we
will usually want pathnames like type/photo and date_taken/2004/3/4 to
link weakly to their files. Symlinks are weak, but symlinks are also
symbolic, and when we don't want that indirection we don't want it. So
we need non-symbolic weak links. (Again, more about links later.)

What if two different photos have the same date_taken? They can't both
be /(whatever)/date_taken/2004/3/4 . One workaround is to append a
different, meaningless extra segment to each of their date_taken
path"names", so one photo is /(whatever)/date_taken/2004/3/4/aardvark
while the other is /(whatever)/date_taken/2004/3/4/zebra . That way,
'/(whatever)/date_taken/2004/3/4' is asserted of both files (recall,
of course, that both '/bin' and '/bin/touch' are asserted of whichever
non-directory file is /bin/touch ). This is of course a horrible
crock. The right solution is to allow final "name" segments to be
blank. Any and all of the links from a directory to its non-directory
children (and any future "opaque" links to directories, but no
ordinary directory-directory links) should be allowed to be blank. (No
more than one blank link should be permitted from the same directory
to the same child.) So we could have:

one file "named"  /(whatever)/date_taken/2004        (taken at some
unknown date in 2004)

two files "named" /(whatever)/date_taken/2004/3/4    (taken on 2004-03-04) and

one file "named"  /(whatever)/date_taken/2004/3/4/am (taken on the
morning of 2004-03-04).

ls /(whatever)/date_taken/2004 would produce something like

3/
1 blank

, while ls /(whatever)/date_taken/2004/3/4 would produce

am
2 blank

. The search "list by title the photos taken in 2004" (that is, list
the opaque descendants of /(whatever)/date_taken/2004/ by their
entries in /(whatever)/title/ ) will produce something like:

My\ cat\ Socks My\ dog\ Spot My\ gerbil\ Patch My\ turtle\ Alberich

Finally, what if the value in one of the registry's name-value pairs
is /not/ a string? For example, what if a photo object has a
name-value pair named "thumbnail" whose value is an image file?
(Similarly, what if a value is a string too long to be a "name"
segment? For example, the photo might also have a name-value pair
named "description" whose value is 150 words of text.) Hans' proposed
solution to (effectively) this problem was to allow non-textual
segments in names, so you get

date_taken/2004/3/4
title/My\ cow\ Daisy
type/photo
thumbnail/ ---------------
          |          (__) |
          |          (oo) |
          |   /-------\/  |
          |  / |     ||   |
          | *  ||----||   |
          |    ~~    ~~   |
           ---------------

. Obviously the technology to process JPEGs into ASCII art for
terminal display is still somewhat experimental. ;) Seriously, this
approach is probably the Right Thing, but it presents some issues.
(For example, would such a segment have a file type (as it were)
associated with it? Not having types would cause problems (who really
wants to rely on file(1) to help interpret a directory listing?), but
having them raises an dilemma: if two different Postscript files
generate identical images, are they the same thing for naming
purposes? If so, that leads to problems with namespace collision, as
there's obviously no hope of reliably detecting such identities.) An
alternative approach is to put the non-textual (or, er, long-textual)
value in a file and relate it to the file it describes using a
relation-directory. (My previous file-and-description-relation example
is of course an instance of this approach.) This is less correct than
Hans' method - it certainly damages the elegance of the translation
from registry to filesystem - and it's subject to one or two of the
same issues. But it's obviously easier to implement, if you have
relation-directories. I think the best solution may be Hans' approach
using relation-directories as part of the underlying implementation.

In sum: All you need, and all you should need, to assert of a file a
single-place predicate like "was shot on 2004-03-04" is to give the
file one (more) ordinary path"name".

Back to relations next.

Leo.

-- 
Leo Richard Comerford - http://www.st-and.ac.uk/~lrc1 - accept no namesakes :)

Re: File as a directory - back to predicates

[Hubert Chan]

On Wed, 24 Aug 2005 07:51:19 +0100, Leo Comerford <leocomerford@gmail.com> said:

[... lots of stuff snipped ...]

> At other levels, of course, the differences assert themselves. For one
> thing, the normal Unix filesystem API doesn't have calls to, for
> instance, check the path"names" asserted of a given file. That's
> easily solved; just add the calls.

It's not so easy.  You need to determine how to figure out the
pathnames.  UN*X filesystems and filesystems for UN*X-like operating
systems don't store uplinks, so there's no quick way to figure out the
pathnames; the only way currently is to traverse the entire tree.

P.S. most of the stuff that you're saying is already in the Future
Vision paper.  At least the main idea of trying to query via metadata.
But it uses a different syntax.

-- 
Hubert Chan <hubert@uhoreg.ca> - http://www.uhoreg.ca/
PGP/GnuPG key: 1024D/124B61FA
Fingerprint: 96C5 012F 5F74 A5F7 1FF7  5291 AF29 C719 124B 61FA
Key available at wwwkeys.pgp.net.   Encrypted e-mail preferred.

Re: File as a directory - back to predicates

[Leo Comerford]

On 8/25/05, Hubert Chan <hubert@uhoreg.ca> wrote:
> On Wed, 24 Aug 2005 07:51:19 +0100, Leo Comerford <leocomerford@gmail.com> said:
> 
> [... lots of stuff snipped ...]
> 
> > At other levels, of course, the differences assert themselves. For one
> > thing, the normal Unix filesystem API doesn't have calls to, for
> > instance, check the path"names" asserted of a given file. That's
> > easily solved; just add the calls.
> 
> It's not so easy.  You need to determine how to figure out the
> pathnames.  UN*X filesystems and filesystems for UN*X-like operating
> systems don't store uplinks,

Yes, I know.

 so there's no quick way to figure out the
> pathnames; the only way currently is to traverse the entire tree.

And that's exactly the point. ("Less easily solved are the performance
issues.") Again, if you took the expanded API and put a typical Unix
filesystem implementation behind it, you would find that its
performance at things like finding pathnames was abysmally slow, while
its performance at doing the traditional Unix-filesystem things was as
good as ever. Conversely, if you mounted some kind of registry system
instead (or as well) you' d find that it was very fast at finding
pathnames, but very slow at many traditional-Unix-filesystem tasks
(for example rename()ing a directory). Again, consider the analogy of
an abstract collection type with two or more different concrete
implementations. The data model is not any of its implementations.
Just because two different data systems have different performance
characteristics doesn't mean they need to present different data
models.

> P.S. most of the stuff that you're saying is already in the Future
> Vision paper.  At least the main idea of trying to query via metadata.

Future Vision is predominantly about searching from metadata to data.
("Which files are emails about Santa?") It says almost nothing about
going from data to metadata. ("Is this file an email?") (This is
especially unfortunate since Future Vision is in large part about how
to improve the effectiveness of search in the real world, and one of
the most ubiquitous, natural and effective real-world search
strategies is to start with an m-to-d search, then apply d-to-m
searching on the results. An example:

"I remember Santa flamed somebody out a while ago. Let's see - search
for emails from Santa. Hm, thirty hits. [m-to-d]

Let's take a look... This one here also relates to elves and a strike
- /that's/ what it was about, I remember now! [d-to-m]

Any other elf strike emails from Santa? No, just the one: bingo!
[m-to-d again]".)

The one thing it /does/ say about data-to-metadata searching is that
file streams are inelegant, and should be replaced by ... pathname
metadata, yet another way to represent "d-to-m metadata" that is
separate from file naming. By contrast, my email argues that unifying
all OS namespaces into the file naming system, as proposed by Hans in
Future Vision, is such a good idea that it ought to be applied
properly to "d-to-m metadata" too. Especially since the only non-bogus
distinction between "m-to-d metadata" and "d-to-m metadata" is their
performance requirements.

[snip]
-- 
Leo Richard Comerford - http://www.st-and.ac.uk/~lrc1 - accept no namesakes :)

Re: File as a directory - back to predicates

[Hubert Chan]

On Sun, 28 Aug 2005 16:33:37 +0100, Leo Comerford <leocomerford@gmail.com> said:

> On 8/25/05, Hubert Chan <hubert@uhoreg.ca> wrote:
>> On Wed, 24 Aug 2005 07:51:19 +0100, Leo Comerford
>> <leocomerford@gmail.com> said:
>> 
>> [... lots of stuff snipped ...]
>> 
>>> At other levels, of course, the differences assert themselves. For
>>> one thing, the normal Unix filesystem API doesn't have calls to,
>>> for instance, check the path"names" asserted of a given
>>> file. That's easily solved; just add the calls.
>> 
>> It's not so easy.  You need to determine how to figure out the
>> pathnames.  UN*X filesystems and filesystems for UN*X-like operating
>> systems don't store uplinks,

> Yes, I know.

>>  so there's no quick way to figure out the
>> pathnames; the only way currently is to traverse the entire tree.

> And that's exactly the point. ("Less easily solved are the performance
> issues.")

Actually, the performance issues are very easily solved in a simple
filesystem model, if you can write a filesystem from scratch: just take
a standard filesystem and add bits to store the uplinks.

(Much harder if you put queries in the filesystem, as proposed by the
Future Vision paper, since any file could potentially have an infinite
number of possible pathnames, and it usually takes a long time to
generate an infinite number of responses.  Of course, you could say that
the "find all pathnames" API is only limited to real non-query
pathnames, but that limits the whole thing very greatly.)

It is much harder to convince everyone to add a new filesystem API.
Especially since performance would suck horribly on almost every other
filesystem, and provides little perceived benefit.  Have you noticed how
hard it's been to try to convince people that file-as-dir is a good
idea?

The problem is not implementing a filesystem where you can get good
normal filesystem performance plus good performance on "find all
pathnames".  The problem is that the "find all pathnames" API would suck
on all current filesystems, and you would face tremendous resistance if
you tried to get it added.

> Again, if you took the expanded API and put a typical Unix filesystem
> implementation behind it, you would find that its performance at
> things like finding pathnames was abysmally slow, while its
> performance at doing the traditional Unix-filesystem things was as
> good as ever. Conversely, if you mounted some kind of registry system

I have no idea what you mean by a "registry system".

> instead (or as well) you' d find that it was very fast at finding
> pathnames, but very slow at many traditional-Unix-filesystem tasks
> (for example rename()ing a directory). Again, consider the analogy of
> an abstract collection type with two or more different concrete
> implementations. The data model is not any of its implementations.
> Just because two different data systems have different performance
> characteristics doesn't mean they need to present different data
> models.

But some times it is better to present different data models to let the
user know of performance issues.  Especially if it is that abysmal.  I
would hope that if I asked my filesystem to find all the pathnames for
some file, then it would say that it was not implemented, instead of
stalling my process for four hours while it searches the entire tree.
IMHO, if an operation takes a horrendously long time, the user should be
forced to implement it themselves if they really, really want to do it.
The system should not aid the user in doing stupid things, unless it has
large flashing warning lights.

>> P.S. most of the stuff that you're saying is already in the Future
>> Vision paper.  At least the main idea of trying to query via
>> metadata.

> Future Vision is predominantly about searching from metadata to data.
> ("Which files are emails about Santa?") It says almost nothing about
> going from data to metadata. ("Is this file an email?")

Is foo an email?
# cat foo/..../mime-type

Much simpler and faster than "find all pathnames, and see if /emails (or
whatever magic path)" is one of them.  And can be done from the command
line too.

The file-as-dir metadata doesn't seem to be in Future Vision, but has
been discussed to death on this mailing list.

> (This is especially unfortunate since Future Vision is in large part
> about how to improve the effectiveness of search in the real world,
> and one of the most ubiquitous, natural and effective real-world
> search strategies is to start with an m-to-d search, then apply d-to-m
> searching on the results. An example:

> "I remember Santa flamed somebody out a while ago. Let's see - search
> for emails from Santa. Hm, thirty hits. [m-to-d]

> Let's take a look... This one here also relates to elves and a strike
> - /that's/ what it was about, I remember now! [d-to-m]

> Any other elf strike emails from Santa? No, just the one: bingo!
> [m-to-d again]".)

> The one thing it /does/ say about data-to-metadata searching is that
> file streams are inelegant, and should be replaced by ... pathname
> metadata, yet another way to represent "d-to-m metadata" that is
> separate from file naming. By contrast, my email argues that unifying
> all OS namespaces into the file naming system, as proposed by Hans in
> Future Vision, is such a good idea that it ought to be applied
> properly to "d-to-m metadata" too. Especially since the only non-bogus
> distinction between "m-to-d metadata" and "d-to-m metadata" is their
> performance requirements.

I don't see any advantage to your scheme over file-as-dir metadata.

(Actually, if you were trying to unify namespaces, you wouldn't be
adding a new API for finding all pathnames.  You would just
"cat foo/..../pathnames".)

BTW, in order to achieve what Future Vision asks for, the underlying
storage system has to be more like a database.  For example, when you
do: "echo message/rfc822 > file/..../mime-type", the filesystem will
automagically store that in an index.  Then, when you do:
"ls ~/[mime-type=message/rfc822]" (or whatever magic path would be
used to search for emails), the filesystem would look in the index for
all the files that have ..../mime-type set to message/rfc822 and
dynamically construct the directory contents.  So you can't think of the
Future Vision filesystem in terms of traditional filesystem storage.  It
will need a bunch of extra data, but should be able to do everything
reasonably quickly, avoiding the "array vs. linked-list" types of
questions (when in reality, the right answer might be a tree).

-- 
Hubert Chan <hubert@uhoreg.ca> - http://www.uhoreg.ca/
PGP/GnuPG key: 1024D/124B61FA
Fingerprint: 96C5 012F 5F74 A5F7 1FF7  5291 AF29 C719 124B 61FA
Key available at wwwkeys.pgp.net.   Encrypted e-mail preferred.

Re: File as a directory - back to predicates

[Hans Reiser]

Leo, did you see my paper on the website, that the future vision button
takes you to?  I think it addresses topics relevant to your email.

Best,

Hans

Re: File as a directory - back to predicates

[michael chang]

On 9/2/05, Hubert Chan <hubert@uhoreg.ca> wrote:
> On Sun, 28 Aug 2005 16:33:37 +0100, Leo Comerford <leocomerford@gmail.com> said:
> 
> > On 8/25/05, Hubert Chan <hubert@uhoreg.ca> wrote:
> >> On Wed, 24 Aug 2005 07:51:19 +0100, Leo Comerford
> >> <leocomerford@gmail.com> said:
> >> It's not so easy.  You need to determine how to figure out the
> >> pathnames.  UN*X filesystems and filesystems for UN*X-like operating
> >> systems don't store uplinks,
> > Yes, I know.
> >>  so there's no quick way to figure out the
> >> pathnames; the only way currently is to traverse the entire tree.
> > And that's exactly the point. ("Less easily solved are the performance
> > issues.")
> Actually, the performance issues are very easily solved in a simple
> filesystem model, if you can write a filesystem from scratch: just take
> a standard filesystem and add bits to store the uplinks.

But that may introduce incompatabilities with older kernels, and cause
kernel panics, and so on... Logically, the idea is that you're
supposed to think of such things the first time around.  Pity people
don't.

> It is much harder to convince everyone to add a new filesystem API.
> Especially since performance would suck horribly on almost every other
> filesystem, and provides little perceived benefit.  Have you noticed how
> hard it's been to try to convince people that file-as-dir is a good
> idea?

People are stubborn -- they don't like change.  What would be the
point of the API, though, if it could only be used on newer somethings
(filesystems, kernels, whatever you want or can think of).  People'd
want backward compatability to filesystems in the 2.2 kernels...

> The problem is not implementing a filesystem where you can get good
> normal filesystem performance plus good performance on "find all
> pathnames".  The problem is that the "find all pathnames" API would suck
> on all current filesystems, and you would face tremendous resistance if
> you tried to get it added.

Could it end up being a user-space/high-level library?  Manually
implementing this as it is will have sucky performance anyways.  The
idea would be to discourage it's use unless it's necessary, at least
on older FSes.  Then the API wouldn't get adopted, however.

> > good as ever. Conversely, if you mounted some kind of registry system
> 
> I have no idea what you mean by a "registry system".

I think he means like an index.  You know, like the kind of index
Windows or Google uses for searches.

> > Just because two different data systems have different performance
> > characteristics doesn't mean they need to present different data
> > models.
> 
> But some times it is better to present different data models to let the
> user know of performance issues.  Especially if it is that abysmal.  I
> would hope that if I asked my filesystem to find all the pathnames for
> some file, then it would say that it was not implemented, instead of
> stalling my process for four hours while it searches the entire tree.

And then someone would make a even higher level function or API that
checks for the function, and upon failure, it would search the tree
manually at the switch of a flag.  It'd still end up taking 4 hours.

> IMHO, if an operation takes a horrendously long time, the user should be
> forced to implement it themselves if they really, really want to do it.
> The system should not aid the user in doing stupid things, unless it has
> large flashing warning lights.

Definately true.

-- 
~Mike
 - Just my two cents
 - No man is an island, and no man is unable.

Re: File as a directory - back to predicates

[Alexander G. M. Smith]

Leo Comerford wrote on Wed, 24 Aug 2005 07:51:19 +0100:
> Firstly, I apologise for the absurdly late reply!

That's OK, my reply is also a bit late due to summer vacations.

> One workaround is to append a different, meaningless extra segment to
> each of their date_taken path"names", so one photo is
> /(whatever)/date_taken/2004/3/4/aardvark while the other is
> /(whatever)/date_taken/2004/3/4/zebra

That reminds me of what I did for the experimental RAM file system.  When you
viewed one of the indices (such as one for a date attribute), it stuck on a
clunky unique serial number (inode actually) string after the string version
of the values.

Mon Sep  5 20:31:24 55 /RAMDisk/.Indices>ls -l last_modified
total 1638
lrwxrwxrwx   0 agmsmith agmsmith        2 Sep 10  2001 1000158923000000 #604cb708 -> /RAMDisk/PineappleData/news/Servers/NLZ/music.in_fidelity
lrwxrwxrwx   0 agmsmith agmsmith        2 Sep 10  2001 1000159028000000 #609da6d8 -> /RAMDisk/PineappleData/saved/Keepsakes/PM999697.pmf
lrwxrwxrwx   0 agmsmith agmsmith        2 Sep 10  2001 1000159085000000 #609d5638 -> /RAMDisk/PineappleData/saved/Keepsakes/PM999691.pmf

The indice's entry of "1000158923000000 #604cb708" corresponds to a date of
1000158923000000 microseconds since 1970 (BeOS kernel doesn't have time zone
conversion code or date printing - thus the raw number string) with a
uniqifier of "#604cb708", just in case multiple files have the same date.

> The search "list by title the photos taken in 2004" (that is, list
> the opaque descendants of /(whatever)/date_taken/2004/ by their
> entries in /(whatever)/title/ ) will produce something like:
> 
> My\ cat\ Socks My\ dog\ Spot My\ gerbil\ Patch My\ turtle\ Alberich

I wouldn't split up the date parts.  They should be one value, so that range
comparisons can work nicely.  That would make finding all files between
December 12 2005 and January 7 2005 an easy less than and greater than
comparison, not some recursive horror.

> Finally, what if the value in one of the registry's name-value pairs
> is /not/ a string? For example, what if a photo object has a
> name-value pair named "thumbnail" whose value is an image file?

In my system all indexed attributes were converted to strings for display and
naming.  Ideally ones that make sense - like readable numbers for numeric ones.
Each attribute raw type (string, int16, int32, float, etc) had functions for
converting it to a string and back.  Pure binary and unknown ones would be
represented as a binary dump of the first few hundred bytes, plus the uniquer -
good enough to find the same file if you use that as the filename to open when
in the index "directory".  Indeed, that clunky uniquer is needed if you wish
to reuse the resulting file names without ambiguity.  Hans has a fancier
naming system, but this is what I had to do to cram indices into the Posix
naming system.

In the other direction, data to metadata (m-d vs d-m is a good concept to
focus the argument around - thanks for pointing it out), you just open the
file as a directory and look inside to see the attributes (date modified,
thumbnail, etc) for that file.  In BeOS there's a separate API for that;
with files as directories, it could be elegantly avoided.

The one big difference is that your scheme somehow has split attribute keys.
The photo is filed under 2004/March, sort of like having a key of years and a
sub-key of months.  Databases do have composite keys, made by concatenating
multiple fields.  Is this useful for general purpose attributes?  I think not,
since you could simulate the effect with a multiple key query, like finding
files where "year_modified==2004 && month_modified==3".  Thus keeping it simpler
(a flat list of all indexed metadata (the .Indices directory in the example))
works well enough.  Otherwise I'd have to have indices in indices or something
else weird.

michael chang wrote on Fri, 2 Sep 2005 11:57:20 -0400:
> Could it end up being a user-space/high-level library?  Manually
> implementing this as it is will have sucky performance anyways.  The
> idea would be to discourage it's use unless it's necessary, at least
> on older FSes.  Then the API wouldn't get adopted, however.

Sounds like LibFerris.  http://witme.sourceforge.net/libferris.web/  If everyone
uses it, fine.  But to get everyone to use it, it's better if the functionality
is in the file system.  Then metadata queries can be used by common tools, like
"ls", "grep" or even "cd".

- Alex

Re: File as a directory - back to predicates

[michael chang]

On 9/5/05, Alexander G. M. Smith <agmsmith@rogers.com> wrote:

> michael chang wrote on Fri, 2 Sep 2005 11:57:20 -0400:
> > Could it end up being a user-space/high-level library?  Manually
> > implementing this as it is will have sucky performance anyways.  The
> > idea would be to discourage it's use unless it's necessary, at least
> > on older FSes.  Then the API wouldn't get adopted, however.
> 
> Sounds like LibFerris.  http://witme.sourceforge.net/libferris.web/  If everyone
> uses it, fine.  But to get everyone to use it, it's better if the functionality
> is in the file system.  Then metadata queries can be used by common tools, like
> "ls", "grep" or even "cd".

All the better, I suppose.  Assuming the stubborns at kernel lists
allow you to put it in. =.="

Still, it's easier if it's done in the next devel cycle for them...
assuming there *IS* a next cycle (that could be quite a ways off,
which is the problem for Reiser4 AFAIK).

Do the linux kernel lists allow a "notice-for-intent-of-filesystem(or
feature)-inclusion-proposal" and then let you attach a preliminary
patch, before the required patch?  That might have been useful,
although I'm rather fond of Namesys's policies for submission and
stuffs.

-- 
~Mike
 - Just my two cents
 - No man is an island, and no man is unable.