Re: Feature freeze imminent

On Mon, Feb 26, 2007 at 03:38:57PM +0000, Tuomo Valkonen wrote:
> On 2007-02-26, Sam Mason <[email protected]> wrote:
> > One way to neatly sidestep this problem would be to remove the ordering
> > and just require the set of tags associated with each file to be unique.
> > As far as I can tell, the implementation wouldn't be too complicated,
> 
> That's what I intend. At the file system level, there's no ordering
> as such: files are addressed by sets of tags, and this set is enforced
> to be unique for each file. The programs (or a FUSE plugin, for getdir) 
> can then do some ordering for nicer listings. 

OK, I've just re-read your original note on the subject and I was
originally confused about what you meant---everything seems more
coherent now.

> As for the implementation, yes it shouldn't be too complicated. 
> My present plan is that each tag has a sparse bitmap associated 
> with it, with the bit for each object ID that has that tag set, set
> to one. Then you just 'and' these bitmaps when you search for the
> subset of files having the given tags set. This should be quite
> efficient given a suitable sparse structure for the bitmaps. 

Sounds similar to "bitmap indexes" as used by databases.  For read-only
access they are great but AFAIK every implementation I've every heard of
kills concurrent modification.  It may all work out here, but just to
warn you!

> However, pruning the results (there can be a lot of them), may
> demand a bit more effort. But it should not be a problem in a Riot
> scale application. Note that these tag-based bitmaps could be 'and'ed
> with further filters, such as a date one, that do not, however, 
> constitute a part of the file name, unlike the tags. 

By pruning I'm guessing you mean getting single references out to each
file, if so I think I must be missing something.  I don't see why any
algorithm would ever return more than one reference to the same file and
hence you would ever need to do any pruning.

I agree with keeping the dates separate from tags, and with your rants
on meta-data.  One of my issues is that metadata belong in the file so
it doesn't disappear when you copy the file to a filesystem or over a
protocol that doesn't honour all the latest shiny new features.  I also
think we've all had to deal with recording the same information twice
and them getting out of sync.

> There's, however, another structure needed for looking up a particular
> file with exactly given set of tags. One approach would be to use a 
> binary self-balancing tree (red-black, AVL), but I'm afraid that could
> be too inefficient on a file system, as multiple 'inodes' all around the
> disk would have to be accessed on each lookup.  An alternative, possibly
> more efficient, approach would be to order the identifier sets by tag ID,
> and use a nested B-tree for looking up the files as if they were on a 
> normal hierachical file system. In fact, you could store the files on 
> a normal underlying file system in that hierarchy. 

Your alternative sounds a lot like what I was trying to say in my last
email.

> I do not plan to do
> so, however, although I do intend to use (at least initially) a normal
> FS for storing the files, with an additional file for the indices.

Sounds like a very reasonable way to start.

> I have not looked in detail into how LFS (Logic File System) does this,
> and maybe I could in fact use it, but the last I checked, it was gone,
> and the first time I checked, I couldn't build it.

I started to write an IMAP server that supported a similar method
of tagging messages.  I used a traditional database (Postgres) to
store everything in but didn't get very far as the IMAP spec is so
impressively byzantine and every email client seems to use it's own
subset.

Postgres has reasonable support for BLOBs, providing an interface very
similar to Unix's open/read/write/close.


  Sam