Jason Tackaberry wrote: > On Thu, 2005-04-21 at 09:30 +0200, Dirk Meyer wrote: >> True. Maybe it is possible to merge both ideas. Keep two >> databases. One pickle for fast directory listings and one sqlite for >> vfs listings on Artist/Album, etc. Maybe not, I'm not sure how to do >> things. > > Possible, but I think it's a bad idea. Maintaining two backends is > going to yield a messy, crufty design. Better to pick one approach and > bolt on the things you need. Of course, you can't bolt on performance, > so the pickle-plus-query-logic approach might end up being better.
Yes, I know. That's why I still think of a pickled based query logic.
> This whole discussion can be summed up in two competing designs:
> 1. Use a pickle backend and build query logic on top of that.
> 2. Use an sqlite backend and just use SQL for querying.
>
> So let's discuss these designs.
Yes
> #1 - We know the performance is good with a pickle backend. Another
> advantage it has over sqlite is that it is conceptually very easy to
> understand, and doesn't add another external dependency to the design.
> One concern, for me at least, is concurrency issues. Other processes
> cannot adjust the pickled object on disk while the main vfs process has
> it in memory, otherwise it gets the rug pulled out from underneath it.
Yes and No. My code checks the mtime of the cache file and reloads it
when it is changed. When changes are made, the pickle is stored (not
for each file, but from time to time). But I get a problem when I have
an item with the info, pickle in the background with a new process and
after that save something using the item. The memory is now differnet
From the file. So yes, that is a problem I now have.
> This problem can be solved by designating one process to control the vfs
> data, and communicating to it via a well-defined interface (using your
> favorite mechanism to do so).
Correct, still thinking about it. But sending data from process to
process also takes time. You think it is fast, but think of 10k of
files.
> Querying is not gotten for free, so it will need to be added to the
> design. It's not 5 lines of Python or anything, but it's also not
> terribly complicated either. And if we limit our scope to accommodate
> the most common use-cases, it can be made much simpler. We don't need
> the full power of SQL querying here. That is, we can imagine a user is
> going to want to search for things like (artist = 'Enya') or (genre =
> 'New Age'). These are the simplest and likely most common cases. More
> complicated queries might look like (genre = 'Rock' and ranking > 7), or
> perhaps, (director = 'Kevin Smith' or actor = 'Ben Afleck'). How about:
> (genre = 'Action' and rating > 'PG' and (actor = 'Denzel Washington' or
> actor = 'Jean Reno'))
Yes, the query is simple compared to what sql can do.
> I imagine the vfs data being stored as a 3-dimensional dictionary
> (dirname -> filename -> metadata), which probably makes most sense.
> Each directory would be pickled as a separate file.
Correct, that's what I'm doing now. I have a pickle file for each
directory containing some basic informations like cover file (so you
don't need to add that to every file without one). Inside a dict of
files with the metadata. To keep unpickle fast, some stuff like the
above cover is only stored when it is different from the directory
information. Also the mmpython data is pickled as string inside
it. You need to unpickle it again, but you can save that because this
information is not needed when creating the menu, only when you select
the item you want.
> In order to simplify the algorithm, we'll duplicate the dirname and
> filename inside the metadata dict. Our query algorithm then looks
> something like:
>
> def query(qlist):
> result_set = []
> for dirname in vfsdirs:
> for filename in vfsdirs[dirname]:
> for subquery in qlist:
> if query_and(vfsdirs[dirname][filename], subquery):
> result_set.append(vfsdirs[dirname][filename])
>
> So query_and() does most of the real work. But how it behaves is fairly
> predictable given the above context.
>
> We can see immediately that query time scales linearly based on the
> number of elements in qlist (i.e. how many expressions get ANDed
> together). So (artist = 'Enya' and ranking > 7) takes twice as long as
> just (artist = 'Enya'). Since we can expect a similar iteration over
> subquery elements in query_and(), we can see that this algorithm grows
> linearly based on the total number of separate expressions in the query.
> This algorithm is intuitive and probably quite crude. There are likely
> some tricks we can borrow from database design to optimize things -- or
> maybe not, since I have no idea about databases.
To bad, I also have no ideas about databases. But maybe the directory
pickle could also contain some sort of index. We know what we search
for in most cases, so maybe keep an artist and album index. Maybe
not. Maybe use no dict but a B-Tree....maybe not, I have no idea.
But do we want to keep the whole pickle db in memeory all the time?
Maybe not (my pickled dir is about 6MB). So maybe load to memory
first.
> So the main benefit of the sqlite approach isn't _what_ we can do with
> our queries, but rather that we don't need to concern ourselves with
> writing the logic to do those queries. sqlite also handles matters of
> concurrency by means of proper file locking. In practice, though, I
> would want a designated process that acts as an interface to the vfs
> metadata even in the sqlite case, because as soon as you do an insert on
> a database it begins a transaction and locks it, so other processes
> would get blocked until all the inserts are done. One way around this
> is to commit() after every insert, but that's too slow. The other way
> around this is as above: use a constant interface (i.e. a process via
> IPC) to the backend.
The lock is a primary problem. You don't know if it would block.
> I then implemented the same type of thing with sqlite. The design is
> rather different because we require multiple tables and multiple
> selects. The flexible approach is to have a files table which holds
> common data for all files, and then separate type-specific tables. It
> would vastly simplify things to use a single files table that holds all
> the metadata we'd need, but this won't work for MeBox, anyway, where I
> require the ability for plugins to add support for new file types.
That also was a big problem for me as you can see in my WIP mediadb
test. Even worse: you don't know what entries a table has for a
type. A plugin may want to store something to the video table and you
don't know the variable while you write the vfs.
> There is no one-shot way to query the database for the results we want.
> What tables we SELECT on will depend on what data the user is looking
> for. In the test code I wrote (see t2.py), we do a select on both the
> video and audio tables and create a union of the result set.
Yes, I know the problem. And each select takes time.
> The bottom line is that query performance is similar. On a query of
> 100,000 files that returns a result set of 200 files, the in-memory
> search of dicts (approach #1) takes 0.87 seconds on my system. With
> sqlite (approach #2) it takes 0.73 seconds. This test is not
> comprehensive. It might even be unfair. My results could benefit from
> scrutiny.
Aha, so a dict isn't even slower. But 100k files may be a small
system, I guess some people have more files. But I get the point.
> Over the course of writing this email and doing all this testing,
> I'm beginning to think approach #1 is the way to go. Comments,
> please.
I did similar tests some weeks ago and came to the same conclusion.
>> That's what I don't like with pickle. I want to to do stuff like
>> mediadb.Listing('artist like "Enya"'). I can't do that with
>> pickle. I'm thinking of how it could be possible, but all ideas I have
>> don'y sounds that good that I even started coding.
>
> I think the method I came up with above is the most obvious one. Did
> you think of this and dismiss it? If so, why?
The main problem with that is the size of the database in memory. The
whole db of my system takes 16MB. Maybe we can live with that.
>> code for both. Or maybe we come up with a vfs design that both
>> projects could use. One simple pyvfs module. You are a good
>> programmer, it would be great if we could share as much code as
>> possible.
>
> I think it's unavoidable that the MeBox vfs is going to be tightly
> coupled with my IPC stuff, and also it will use a signal class I use for
> callbacks. But if we use the same design, we can definitely benefit
> from the evolution of that, and also certain specific code snippets like
> query logic.
I hope so. As I wrote on IRC I have a test version here with creating
metadata in the background. Very nice and very fast.
Dischi
--
printk("; corrupted filesystem mounted read/write - your computer
will explode within 20 seconds ... but you wanted it so!\n");
2.4.3 linux/fs/hpfs/super.c
pgpiYLEpIPpKz.pgp
Description: PGP signature
