On Tuesday 30 January 2007 10:38, Rudolf Cejka wrote:
> Kern Sibbald wrote (2007/01/30):
> > These are interesting results, but I'm slightly confused. It seems that
> > you have either misinterpreted or changed the original subject (no
> > problem), which was referring to a large FileSet exclusion list for
> > backup.
>
> I'm sorry, I just replied to the fact, that there is just double linked
> list (dlist) implemented in Bacula. I met this problem, when I tried to
> restore a backup with over 3000000 milions files on a server with some
> special purposes, where there are several directories with over
> 100000 files.
Yes, that would be a *big* problem or I should say two big problems (3 million
files and 100K files in several directories).
> I found that dlist::binary_insert() is very optimistic
> in its name, so I started to dig into an implementation with more stable
> time results, however I'm not sure, if it is not better to simply get
> sorted results from database, which should help in my case too.
Yes, binary_insert should probably be called something different. It puts the
items in sorted order so that inserting is much faster. However, it cannot
do a typical binary sort algorithm in the sense that to get to the
next "binary" insertion point, it must walk the list of pointers. What it
does avoid is doing a comparison at each step so it is a big improvement over
a simple dlist for directories containing a large number of files, but
nothing like a binary tree.
> However
> I started to implement a balanced tree (unbalanced would be inadequate
> in Bacula's case), because I believed, that there have to be some other
> places, where a tree instead of a dlist would be much better - and it
> seems that exclusion list would be the case.
You might take a look at the Bacula btree code (src/lib/btree.c and
src/lib/btree.h). I completed it a very long time ago, and all the tests
work fine. It is not designed to remove items, though that could be added.
For doing the restore tree there is no need to remove anything since all the
memory allocations are done is big buffers that are managed by the tree code
and automatically released at the end.
>
> > If I understand correctly, you have implemented an AA (never heard of it)
> > balanced tree for building the restore in memory tree. Is that correct?
>
> Yes. Fortunately, there is very good interface border between data type
> usage, and its implementation, so it was very easy to switch from dlist
> to my tree implementation (however still unfinished yet), thanks ;o)
Ah. That is nice to hear. I had hoped it would be easy to switch them, but
never got to actually looking at the code.
>
> > On Tuesday 30 January 2007 08:57, Rudolf Cejka wrote:
> > Yes, it is probably also kernel caching on the Bacula side as well. I
> > always run the test 10 times sequentially, throw out the first two
> > results and then discard any subsequent test more than 10% from the
> > average, then finally make an average. That usually gives reasonably
> > consistent results.
>
> However in the real life, the first values are very important too, because
> it is often the real case - I do not have to repeat tree restoration more
> than once ;o)
>
> > Yes, if you are talking about the restore memory tree, the big problem is
> > always directories containing large numbers (more than 10000) files.
>
> Since now, it almost "was" ;o)
>
> > Have you looked at using the Bacula red-black tree code? According to
> > the research that I did red-black trees are the fastest of all tree
> > routines.
>
> Yes, AA tree is RB tree with one additional condition, so implementation
> is easier and more transparent. When aa_insert() and aa_remove() are done,
> it is easy to add {rb,avl}_{insert,remove} too. AA tree tends to perform
> more rotations, but its resulting tree happens to be more balanced, so it
> is believed, that AA and RB performances are balanced. AVL trees are even
> more balanced, but not so popular, however this is the only balanced tree,
> which I implemented in the past.
Interesting. I'll have to do a bit of research on AA trees. In any case, IMO,
the Bacula RB tree class code that is needed for the restore tree is
implemented and tested. Of course actual usage may find some problems.
>
> > The second question is have you examined the amount of memory required in
> > the two cases to hold the whole tree (current dlink code and balanced
> > tree code)?
>
> There are additional 8 bytes per file, parent and level items. Parent
> can be omited, but then next() has to be recursive, or has to have some
> internal stack (probably next direction in my tests). Level can be smaller
> in its size, but I do not want to strike alignment problems. I saw memory
> usage around 10 % bigger, 280 MB instead of 250 MB.
It seems to me that only 8 bytes per file is not a bad trade off for an
enormous speed improvement with large directories. I've also been
considering "caching or paging" the large tree buffers (src/lib/tree.c).
In 1982, I wrote paged fread()/fwrite() routines that were extremely fast, and
I don't imagine it would be hard to re-invent that code. This could
potentially reduce the memory requirements significantly for really large
FileSets -- e.g. more than 4 or 5 million files. At the time, I used
environment variables to allow the user to configure it to avoid OS paging
which is 100s of times more expensive.
>
> > The structures needed to setup and maintain a tree (balanced or not) are
> > rather more expensive in terms of bytes than a linked list. It might be
> > interesting to be able to disable any code that balances the tree.
>
> Balanced parts are distinguishable, so I hope, that it would be possible.
>
> > A balanced tree is primarily optimized for searches rather than inserts,
> > and the big time consumer for Bacula is the inserts.
>
> Yes, but every insert means tree search first, so inserts are
> significantly impacted too. In case of insertion of a sorted list
> of items even very significantly.
Yes, I agree, but any tree routine is going to be slower for small directories
and much faster for really big directories. I suspect, but have not verified
that by not balancing the tree, one would eliminate much of the extra
overhead of balanced trees for small directories, yet not hurt the
performance much for large directories.
In taking a quick look at the btree code that I wrote, it seems that I did
take the trouble to keep the tree balanced -- at least that is what the
comments say.
For doing large inclusion/exclusion lists, I have written src/lib/htable.c,
which is hash code. I have always planned to replace the current dlist
structures in the FD with the hash code routines. It should be equally
simple as what you found for tree.c, but I just never got around too it.
At the moment, I am focusing my energy on the bat GUI, but one of the items I
chose for the next release for my personal work is performance, and both the
tree and the inclusion/exclusion lists are items I planned to look at. Of
course, I would be really happy if someone like yourself who needs the code
would do it. :-)
Best regards,
Kern
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys - and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Bacula-users mailing list
Bacula-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bacula-users
