Near-constant time directory index for Ext2
Just looking at R5 I knew it wasn't going to do well in this application because it's similar to a number of hash functions I tried with the same idea in mind: to place similar names together in the same leaf block. That turned out to be not very important compared to achieving a relatively high fullness of leaf blocks. The problem with R5 when used with my htree is, it doesn't give very uniform dispersal.
The bottom line: dx_hack_hash is still the reigning champion.
Now that you provide source for r5 and dx_hack_hash, let me feed my collections to them.
r5: catastrophicdx_hack_hash: not bad, but the linear hash is better.
E.g.:
Actual file names:
Linear hash, m=11, sz=2048, min 262, max 283, av 272.17, stddev 12.25 dx_hack_hash: sz=2048, min 220, max 330, av 272.17, stddev 280.43 r5: sz=2048, min 205, max 382, av 272.17, stddev 805.18
Linear hash, m=11, sz=65536, min 0, max 24, av 8.51, stddev 8.70
dx_hack_hash: sz=65536, min 0, max 23, av 8.51, stddev 8.51 r5: sz=65536, min 0, max 26, av 8.51, stddev 8.89
Generated consecutive names:
Linear hash, m=11, sz=2048, min 262, max 283, av 272.17, stddev 12.25
dx_hack_hash: sz=2048, min 191, max 346, av 272.17, stddev 636.11 r5: sz=2048, min 0, max 3587, av 272.17, stddev 755222.91
Linear hash, m=11, sz=65536, min 2, max 14, av 8.51, stddev 2.79
dx_hack_hash: sz=65536, min 0, max 26, av 8.51, stddev 12.24 r5: sz=65536, min 0, max 120, av 8.51, stddev 738.08
Andries
Quoted 8 lines · [email protected] wrote:
Just looking at R5 I knew it wasn't going to do well in this application because it's similar to a number of hash functions I tried with the same idea in mind: to place similar names together in the same leaf block. That turned out to be not very important compared to achieving a relatively high fullness of leaf blocks. The problem with R5 when used with my htree is, it doesn't give very uniform dispersal.
Quoted 6 lines
The bottom line:
dx_hack_hashis still the reigning champion.Now that you provide source for r5 and
dx_hack_hash, let me feed my collections to them.
r5: catastrophicdx_hack_hash: not bad, but the linear hash is better.
I never expected dx_hack_hash to be particularly good at anything, but we might as well test the version without the mistake in it - I was previously using < 0 to test the sign bit - on an unsigned variable :-/
unsigned dx_hack_hash (const char *name, int len)
{
u32 hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
while (len--)
{
u32 hash = hash1 + (hash0 ^ (*name++ * 71523));
if (hash & 0x80000000) hash -= 0x7fffffff;
hash1 = hash0;
hash0 = hash;
}
return hash0;
}The correction gained me another 1% in the leaf block fullness measure. I will try your hash with the htree index code tomorrow.
--
Daniel
Quoted 4 lines
Now that you provide source for r5 and
dx_hack_hash, let me feed my collections to them.
r5: catastrophicdx_hack_hash: not bad, but the linear hash is better.
<snip verbose results>
So, not only does the linear hash normally provide a shorter worst-case chain, its' results are actually more consistent than the other two. Looks like simple is good here, but is it still possible to produce "pathological" sets for the linear hash to see how badly it falls down? I'm no mathematician, so I'll leave that to the gurus...
Meanwhile, let's go back to Linus' comment on compatibility and so on. He has a *very* good point, which I'll expand on slightly here:
Suppose some stone-age Linux user, running 2.0.35 or something equally old (which runs ext2), decides to finally bite the bullet and upgrade to the all-new 2.6.1 (OK, this is some time in the future). 2.6.1 implements some "enhanced" version of ext2 which makes some incompatible modifications to the directory structure. However, since the process of upgrading through such a massive range of kernels also involves upgrading most other software to boot, this user forgot one or two pieces, and reboots to 2.0.35 to regain a sufficiently working system that he can build the updated software
- or not, because 2.0.35's old ext2 code suddenly can't read the filesystem, which was modified by 2.6.1 before the boot process stalled. e2fsck is no help here either, because he now has an unbootable system with old software that doesn't understand the new stuff.
I hope people understand this as well as I do - if a filesystem upgrade is desirable, let the user perform some *specific* action to upgrade it, when he has an otherwise-working setup *and* sufficient backups. I for one do not want to be caught out like the hypothetical user I mentioned above.
OTOH, I have my own opinions on the direction of ext2:
- Currently, it's a stable and universally-utilised filesystem which offers very good performance for most applications. I'm specifically drawing attention to certain benchmarks which place ext2's disk-based performance ahead of many commercial UNIX' ram-based filesystem performance.
- There are specific problems with performance when reading and/or modifying large directories. I haven't tested for this personally, but I have noticed slowness when using 'rm -rf' on a large *tree* of directories. The problem appeared to be one of disk access, but may be a side-effect of poor storage distribution (I haven't examined the ext2 code). Related to this, rebuilding the slocate database on all my systems appears to be disk-bound rather than CPU-bound, and takes too long for my liking.
One of the current suggestions, if I've interpreted it correctly, is to introduce an extension to ext2 which essentially makes a "fast index" of a large directory, attaches it to the directory in some backwards-compatible manner, and uses it *in conjunction with* the regular directory structure. This is probably a good idea, but it needs some thought:
- How much overhead does the "fast index" introduce for modification of the directory? Large directories are the most likely to have stuff added and deleted, and it doesn't help if during an "rm *" operation the saving on the search is negated by the overhead on the unlink.
- If the index gets out of sync with the directory, how is this detected and recovered from? Assuming the index merely points to the correct position in the regular directory, some simple sanity checks will suffice for most cases (is this entry in the directory the same as I asked for?), and if the entry is not in the index then a standard search of the real directory can be done. In either case, the index can be marked as invalid (and removed?) and rebuilt whenever necessary.
- At what threshold of directory size does the index come into play? (fairly obviously, the index is useless for tiny directories)
- What happens when an old kernel encounters a directory which has an index attached to it? Does it look like a virtual file, which has no special properties but whose name is reserved for system use? (cf. lost+found) Or is it some inidentifiable bits in the directory structure and a few lost clusters on the disk? If the latter, it will have to be done in a way that older versions of e2fsck can clean it up easily and older versions of ext2 won't throw up on it, which could be kinda hard. If the former, an 'unused' name will have to be found to avoid conflicts but the big advantage is *no* inconsistency with old systems.
Answers on a postcard...
--------------------------------------------------------------
from: Jonathan "Chromatix" Morton mail: [email protected] (not for attachments) big-mail: [email protected] uni-mail: [email protected]
The key to knowledge is not to rely on people to teach you it.
Get VNC Server for Macintosh from http://www.chromatix.uklinux.net/vnc/
-----BEGIN GEEK CODE BLOCK-----
Version 3.12
GCS$/E/S dpu(!) s:- a20 C+++ UL++ P L+++ E W+ N- o? K? w--- O-- M++$ V? PS PE- Y+ PGP++ t- 5- X- R !tv b++ DI+++ D G e+ h+ r- y+
-----END GEEK CODE BLOCK-----
Quoted 7 lines · Jonathan Morton
Meanwhile, let's go back to Linus' comment on compatibility and so on. He has a *very* good point, which I'll expand on slightly here:
Suppose some stone-age Linux user, running 2.0.35 or something equally old (which runs ext2), decides to finally bite the bullet and upgrade... ... 2.0.35's old ext2 code suddenly can't read the filesystem, which was modified by 2.6.1 before the boot process stalled.
One of the proposals on the table for the indexed directories is read AND WRITE compatible with older kernels. For 1.0 through 2.4 kernels the read compatibility is very safe (it will generate some errors on reads because of "sparse" directory blocks, but the code will continue on correctly, <= 1.2 won't even generate an error). For < 2.2 kernels deleting a file from an indexed directory will work, but would leave the index out of date. For < 2.2 kernels adding a new file to an indexed directory would always overwrite the index, so it is also safe.
Quoted 4 lines
I hope people understand this as well as I do - if a filesystem upgrade is desirable, let the user perform some *specific* action to upgrade it, when he has an otherwise-working setup *and* sufficient backups. I for one do not want to be caught out like the hypothetical user I mentioned above.
I am on the side of maintaining compatibility. There _may_ be a _small_ performance (more like capacity) impact on indexed directories for this compatibility, but it is well worth it, IMHO.
Quoted 4 lines
- Currently, it's a stable and universally-utilised filesystem which offers very good performance for most applications. I'm specifically drawing attention to certain benchmarks which place ext2's disk-based performance ahead of many commercial UNIX' ram-based filesystem performance.
Totally agree.
Quoted 3 lines
- There are specific problems with performance when reading and/or modifying large directories. I haven't tested for this personally, but I have noticed slowness when using 'rm -rf' on a large *tree* of directories.
That is what the index change will address. Actually, "rm -r" may not be speeded up very much, but "rm *" definitely would be ("rm -r" deletes files in directory order, but "rm *" deletes each file individually in alphabetical order).
Quoted 4 lines
One of the current suggestions, if I've interpreted it correctly, is to introduce an extension to ext2 which essentially makes a "fast index" of a large directory, attaches it to the directory in some backwards-compatible manner, and uses it *in conjunction with* the regular directory structure.
Yes, this is essentially true. The on-disk directory entries are exactly the same. The index itself (in the compatible layout) appears to simply be empty directory blocks (at the cost of 8 bytes = 1 index entry per block).
Quoted 4 lines
- How much overhead does the "fast index" introduce for modification of the directory? Large directories are the most likely to have stuff added and deleted, and it doesn't help if during an "rm *" operation the saving on the search is negated by the overhead on the unlink.
The index will improve the performance for file add, stat, and delete. For all of these operations you need to find a directory entry (add needs to check if a file of the same name already exists before a new file is added).
Quoted 7 lines
- If the index gets out of sync with the directory, how is this detected and recovered from? Assuming the index merely points to the correct position in the regular directory, some simple sanity checks will suffice for most cases (is this entry in the directory the same as I asked for?), and if the entry is not in the index then a standard search of the real directory can be done. In either case, the index can be marked as invalid (and removed?) and rebuilt whenever necessary.
On an index-aware kernel, the index can obviously not get out of sync. All 2.2+ kernels that don't understand indexing will clear the "has index" flag if they modify that directory, and the index will disappear. Since the index is "hidden" (in my proposal at least) inside a totally normal directory block, it will simply be overwritten by new entries. As I mentioned above, 1.x and 2.0 kernels will overwrite the index on an add, but not on a delete, and will not clear the "has index" flag. This means we need some extra magic at the start of the index to ensure we have a valid index header.
Quoted 2 lines
- At what threshold of directory size does the index come into play? (fairly obviously, the index is useless for tiny directories)
This remains to be seen. Definitely not for directories 1 block in size (which is 85%? of all directories). It looks like directories with about 250-300 files or more are needed for indexing to be useful. The good news is that since indexing is optional, it can be tuned to only improve performance of directories.
Quoted 9 lines
- What happens when an old kernel encounters a directory which has an index attached to it? Does it look like a virtual file, which has no special properties but whose name is reserved for system use? (cf. lost+found) Or is it some inidentifiable bits in the directory structure and a few lost clusters on the disk? If the latter, it will have to be done in a way that older versions of e2fsck can clean it up easily and older versions of ext2 won't throw up on it, which could be kinda hard. If the former, an 'unused' name will have to be found to avoid conflicts but the big advantage is *no* inconsistency with old systems.
This has also been discussed already for the indexing code. The index is actually stored inside the directory, so no hidden files or anything, and no "lost blocks" either. The original indexing code wasn't 100% compatible with the older layout, but a proposal has been made to make it totally compatible with older kernels (excluding some error messages that all ext2 directory code handles properly).
If (for whatever reason) you started using an indexed ext2 kernel, created a huge directory of files, and then never used it again, the only thing wasted would be your time (when you try to delete the files in the huge directory without the indexed directory ;-). The ext2 code has NEVER releases directory blocks, even if all of the files are gone. All blocks used by the index also appear (in the proposed layout) as regular directory blocks, so a non-index kernel can use them at any time (of course the index is destroyed in this case).
As an aside, lost+found is NOT a "special" name in any way to the filesystem. The only thing that it is used for is e2fsck - to the kernel it is just a regular directory.
Basically, I think the compatibility is excellent for the functionality delivered. Another reason why I think ext2 will continue to have a long and prosperous life, without making sacrifices for performance.
Cheers, Andreas
Signature · 3 lines
Andreas Dilger \ "If a man ate a pound of pasta and a pound of antipasto,
\ would they cancel out, leaving him still hungry?"
http://www-mddsp.enel.ucalgary.ca/People/adilger/ -- Dogbert