Re: [Gnu-arch-users] Re: [GNU-arch-dev] [ANNOUNCEMENT] /Arch/ embraces `git'
On Wed, 2005-04-20 at 16:04 -0700, Tom Lord wrote: I think that to a large extent you are seeing artifacts of the questionable trade-offs that (reports tell me) the ext* filesystems make. With a different filesystem, the results would be very different. Tom, please stop this ext* filesystem bashing ;-) Even with filesystem which compresses the tails of files into one filesystem block it wouldn't make a difference that there are potentially (and very probably even with blob numbers in order of 10) 65536 directories on the first level. This doesn't help much in fast reading the first level. I'm imagining a blob database containing may revisions of the linux kernel. It will contain millions of blobs. It's fine that some filesystems and some blob operations work fine on a directory with millions of files but what about other operations on the database? I pity the poor program that has to `readdir' through millions of files. Even with milions of files this key structure doesn't make much sense - the keys on the first and second levels are too long. However you're right that the original structure proposed by Linus is too flat. -- Tomas Mraz [EMAIL PROTECTED] - To unsubscribe from this list: send the line unsubscribe git in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [Gnu-arch-users] Re: [GNU-arch-dev] [ANNOUNCEMENT] /Arch/ embraces `git'
Tomas Mraz [EMAIL PROTECTED] writes: If we suppose the maximum number of stored blobs in the order of milions probably the optimal indexing would be 1 level [0:2] indexing or 2 levels [0:1] [2:3]. However it would be necessary to do some benchmarking first before setting this to stone. As I have suggested in a previous message, it is trivial to implement adaptive indexing: there is no need to hardwire a specific indexing scheme. Furthermore, I suspect that the optimal size of subkeys may well depend on the filesystem. My experiments seem to indicate that subkeys of length 2 achieve an excellent compromise between discriminatory power and disk footprint on ext2. 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 :-) Cheers, -- Dr. Denys Duchier - IRI LIFL - CNRS, Lille, France AIM: duchierdenys - To unsubscribe from this list: send the line unsubscribe git in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [Gnu-arch-users] Re: [GNU-arch-dev] [ANNOUNCEMENT] /Arch/ embraces `git'
On Thu, 2005-04-21 at 11:09 +0200, Denys Duchier wrote: Tomas Mraz [EMAIL PROTECTED] writes: If we suppose the maximum number of stored blobs in the order of milions probably the optimal indexing would be 1 level [0:2] indexing or 2 levels [0:1] [2:3]. However it would be necessary to do some benchmarking first before setting this to stone. As I have suggested in a previous message, it is trivial to implement adaptive indexing: there is no need to hardwire a specific indexing scheme. Furthermore, I suspect that the optimal size of subkeys may well depend on the filesystem. My experiments seem to indicate that subkeys of length 2 achieve an excellent compromise between discriminatory power and disk footprint on ext2. 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. Of course it might be best to allow adaptive indexing but I think that first some benchmarking should be made and it's possible that some fixed scheme could be chosen as optimal. -- Tomas Mraz [EMAIL PROTECTED] - To unsubscribe from this list: send the line unsubscribe git in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [Gnu-arch-users] Re: [GNU-arch-dev] [ANNOUNCEMENT] /Arch/ embraces `git'
Tomas Mraz [EMAIL PROTECTED] writes: 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 - To unsubscribe from this list: send the line unsubscribe git in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [Gnu-arch-users] Re: [GNU-arch-dev] [ANNOUNCEMENT] /Arch/ embraces `git'
Using your suggested indexing method that uses [0:4] as the 1st level key and [0:3] [4:8] as the 2nd level key, I obtain an indexed archive that occupies 159M, where the top level contains 18665 1st level keys, the largest first level dir contains 5 entries, and all 2nd level dirs contain exactly 1 entry. That's just a mistake in the spec. The format should probably be multi-level but, yes, the fanout I suggested is currently quite bogus. When I write that part of that code (today or tomorrow) I'll fix it. A few people pointed that out. Thanks. -t - To unsubscribe from this list: send the line unsubscribe git in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [Gnu-arch-users] Re: [GNU-arch-dev] [ANNOUNCEMENT] /Arch/ embraces `git'
Yes, it really doesn't make much sense to have so big keys on the directories. It's official... i'm blushing wildly thank you for the various replies that pointed out my thinko. That part of my spec hasn't been coded yet --- i just wrote text. It really was the silly late-night error of sort: hmm...let's see, 4 hex digits plus 4 hex digits that's 16 bits sounds about right. Really, I'll fix it. -t - To unsubscribe from this list: send the line unsubscribe git in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [Gnu-arch-users] Re: [GNU-arch-dev] [ANNOUNCEMENT] /Arch/ embraces `git'
[your 0:3/4:7 directory hierarchy is horked] Absolutely. Made a dumb mistake the night I wrote that spec and embarassed that I initially defended it. I had an arithmetic error. Thanks, this time, for your persistence in pointing it out. -t - To unsubscribe from this list: send the line unsubscribe git in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [Gnu-arch-users] Re: [GNU-arch-dev] [ANNOUNCEMENT] /Arch/ embraces `git'
Tom, please stop this ext* filesystem bashing ;-) For one thing... yes, i'm totally embarassed on this issue. I made a late-night math error in a spec. *hopefully* would have noticed it on my own as I coded to that spec but y'all have been wonderful at pointing out my mistake to me even though I initially defended it. As for ext* bashing it's not bashing exactly. I/O bandwidth gets a little better, disks get a bunch cheaper --- then ext* doesn't look bad at all in this respect. And we're awefully close to that point. Meanwhile, for times measured in years, I've gotten complaints from ext* users about software that is just fine on other filesystems over issues like the allocation size of small files. So ext*, from my perspective, was a little too far ahead of its time and, yes, my complaints about it are just about reaching their expiration date. Anyway, thanks for all the sanity about directory layout. Really, it was just an I'm too sleepy to be doing this right now error. -t - To unsubscribe from this list: send the line unsubscribe git in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [Gnu-arch-users] Re: [GNU-arch-dev] [ANNOUNCEMENT] /Arch/ embraces `git'
On Wed, 2005-04-20 at 19:15 +0200, [EMAIL PROTECTED] wrote: ... As data, I used my /usr/src/linux which uses 301M and contains 20753 files and 1389 directories. To compute the key for a directory, I considered that its contents were a mapping from names to keys. I suppose if you used the blob archive for storing many revisions the number of stored blobs would be much higher. However even then we can estimate that the maximum number of stored blobs will be in the order of milions. When constructing the indexed archive, I actually stored empty files instead of blobs because I am only interested in overhead. Using your suggested indexing method that uses [0:4] as the 1st level key and [0:3] [4:8] as the 2nd level key, I obtain an indexed archive that occupies 159M, where the top level contains 18665 1st level keys, the largest first level dir contains 5 entries, and all 2nd level dirs contain exactly 1 entry. Yes, it really doesn't make much sense to have so big keys on the directories. If we would assume that SHA1 is a really good hashing function so the probability of any hash value is the same this would allow storing 2^16 * 2^16 * 2^16 blobs with approximately same directory usage. Using Linus suggested 1 level [0:2] indexing, I obtain an indexed archive that [0:1] I suppose occupies 1.8M, where the top level contains 256 1st level keys, and where the largest 1st level dir contains 110 entries. The question is how many entries in directory is optimal compromise between space and the speed of access to it's files. If we suppose the maximum number of stored blobs in the order of milions probably the optimal indexing would be 1 level [0:2] indexing or 2 levels [0:1] [2:3]. However it would be necessary to do some benchmarking first before setting this to stone. -- Tomas Mraz [EMAIL PROTECTED] - To unsubscribe from this list: send the line unsubscribe git in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [Gnu-arch-users] Re: [GNU-arch-dev] [ANNOUNCEMENT] /Arch/ embraces `git'
On Wed, 2005-04-20 at 19:15 +0200, [EMAIL PROTECTED] wrote: ... As data, I used my /usr/src/linux which uses 301M and contains 20753 files and 1389 directories. To compute the key for a directory, I considered that its contents were a mapping from names to keys. I suppose if you used the blob archive for storing many revisions the number of stored blobs would be much higher. However even then we can estimate that the maximum number of stored blobs will be in the order of milions. When constructing the indexed archive, I actually stored empty files instead of blobs because I am only interested in overhead. Using your suggested indexing method that uses [0:4] as the 1st level key and [0:3] [4:8] as the 2nd level key, I obtain an indexed archive that occupies 159M, where the top level contains 18665 1st level keys, the largest first level dir contains 5 entries, and all 2nd level dirs contain exactly 1 entry. Yes, it really doesn't make much sense to have so big keys on the directories. If we would assume that SHA1 is a really good hashing function so the probability of any hash value is the same this would allow storing 2^16 * 2^16 * 2^16 blobs with approximately same directory usage. Using Linus suggested 1 level [0:2] indexing, I obtain an indexed archive that [0:1] I suppose occupies 1.8M, where the top level contains 256 1st level keys, and where the largest 1st level dir contains 110 entries. The question is how many entries in directory is optimal compromise between space and the speed of access to it's files. If we suppose the maximum number of stored blobs in the order of milions probably the optimal indexing would be 1 level [0:2] indexing or 2 levels [0:1] [2:3]. However it would be necessary to do some benchmarking first before setting this to stone. -- Tomas Mraz [EMAIL PROTECTED] - To unsubscribe from this list: send the line unsubscribe git in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
