Re: [Gnu-arch-users] Re: [ANNOUNCEMENT] /Arch/ embraces `git'

From: duchier@ps.uni-sb.de <duchier@ps.uni-sb.de>
Date: Apr 21, 2005, 11:46 UTC
Message-ID: <878y3ce4ii.fsf@star.lifl.fr>
In-Reply-To: <1114078877.5886.37.camel@perun.redhat.usu>

Tomas Mraz <t8m@centrum.cz> writes:

Show 12 quoted lines

>> Btw, if, as you indicate above, you do believe that a 1 level indexing should
>> use [0:2], then it doesn't make much sense to me to also suggest that a 2 level
>> indexing should use [0:1] as primary subkey :-)
>
> Why do you think so? IMHO we should always target a similar number of
> files/subdirectories in a directories of the blob archive. So If I
> always suppose that the archive would contain at most 16 millions of
> files then the possible indexing schemes are either 1 level with key
> length 3 (each directory would contain ~4096 files) or 2 level with key
> length 2 (each directory would contain ~256 files).
> Which one is better could be of course filesystem and hardware
> dependent.

First off, I have been using python slice notation, so when I write [0:2] I mean a key of length 2 (the second index is not included). I now realize that when you wrote the same you meant to include the second index.

I believe that our disagreement comes from the fact that we are asking different questions. You consider the question of how to best index a fixed database and I consider the question of how to best index an ever increasing database.

Now consider why we even want multiple indexing levels: presumably this is because certain operations become too costly when the size of a directory becomes too large. If that's not the case, then we might as well just have one big flat directory - perhaps that's even a viable option for some filesystems.[1]

  [1] there is the additional consideration that a hierarchical system
  implements a form of key compression by sharing key prefixes.  I don't know at
  what point such an effect becomes beneficial, if ever.

Now suppose we need at least one level of indexing. Under an assumption of uniform distribution of bits in keys, as more objects are added to the database, the lower levels are going to fill up uniformly. Therefore at those levels we are again faced with exactly the same indexing problem and thus should come up with exactly the same answer.

This is why I believe that the scheme I proposed is best: when a bottom level directory fills up past a certain size, introduce under it an additional level, and reindex the keys. Since the "certain size" is fixed, this is a constant time operation.

One could also entertain the idea of reindexing not just a bottom level directory but an entire subtree of the database (this would be closer to your idea of finding an optimal reindexing of just this part of the database). However this has the disadvantage that the operation's cost grows exponentially with the depth of the tree.

Cheers,

--Denys