Near-constant time directory index for Ext2

Earlier this month a runaway installation script decided to mail all its problems to root. After a couple of hours the script aborted, having created 65535 entries in Postfix's maildrop directory. Removing those files took an awfully long time. The problem is that Ext2 does each directory access using a simple, linear search though the entire directory file, resulting in n**2 behaviour to create/delete n files. It's about time we fixed that.

Last fall in Miami, Ted Ts'o mentioned some ideas he was playing with for an Ext2 directory index, including the following points:

- Fixed-size hash keys instead of names in the index
- Leaf blocks are normal ext2 directory blocks
- Leaf blocks are sequental, so readdir doesn't have to be changed

Having thought about it on and off since then, I came up with the following additional design elements:

- Logical addressing
The cost of logical addressing of disk blocks is scarcely higher than physical addressing, and logical access through the page cache is actually faster than physical addressing because you don't have to traverse a tree: you can go straight to the logical block you are interested in and only traverse the tree if it's not there. The payoff in terms of not breaking Ext2's existing allocation strategy is huge, not to mention friendliness to tools such as e2fsck and e2resize. Finally, logical addressing means Tux2 will support this feature without modification. :-)

- 8 bytes is sufficient for an index entry
This gives a branching factor of 512 for 4K filesystem blocks resulting in log512(n) access time, performance that is almost indistinguishable from constant-time. The 8 bytes allows for a 32 bit hash key (31 bits actually used, see below) and a 4 byte logical block number, both sufficient for handling billions of directory entries.

- Uniform-depth tree
Usually, some form of balanced tree is used for a directory index. I found that a simple, uniform-depth tree provides equivalent performance with far simpler code. Just two tree levels can handle millions of directory entries, and for all practical purposes, such a tree is never out of balance.

So to give this a name, it's a "uniform-depth hash tree", or htree for short. (It's not a btree.) Such a structure inherits properties of both trees and hash tables. From the hash table side, the htree inherits the advantage of compact, fixed-size keys which gives a high branching factor and enables the use of binary search in interior index nodes.

It also inherits a big disadvantage of hash tables: key collisions. Though rare, collisions give rise to a number of corner cases that are not particularly easy to deal with. (see below)

Index Structure
---------------

The root of the index tree is in the 0th block of the file. Space is reserved for a second level of the index tree in blocks 1 though 511 (for 4K filesystem blocks). Directory leaf blocks are appended starting at block 512, thus the tail of the directory file looks like a normal Ext2 directory and can be processed directly by ext2_readdir. For directories with less than about 90K files there is a hole running from block 1 to block 511, so an empty directory has just two blocks in it, though its size appears to be about 2 Meg in a directory listing.

So a directory file looks like:

0: Root index block
1: Index block/0
2: Index block/0
...
511: Index block/0
512: Dirent block
513: Dirent block
...

Each index block consists of 512 index entries of the form:

hash, block

where hash is a 32 bit hash with a collision flag in its least significant bit, and block is the logical block number of an index of leaf block, depending on the tree level.

The hash value of the 0th index entry isn't needed because it can always be obtained from the level about, so it is used to record the count of index entries in an index block. This gives a nice round branching factor of 512, the evenness being a nicety that mainly satisfies my need to seek regularity, rather than winning any real performance. (On the other hand, the largeness of the branching factor matters a great deal.)

The root index block has the same format as the other index blocks, with its first 8 bytes reserved for a small header:

1 byte header length (default: 8)
1 byte index type (default: 0)
1 byte hash version (default:0)
1 byte tree depth (default: 1)

The treatment of the header differs slightly in the attached patch. In particular, only a single level of the index tree (the root) is implemented here. This turns out to be sufficient to handle more than 90,000 entries, so it is enough for today. When a second level is added to the tree, capacity will incease to somewhere around 50 million entries, and there is nothing preventing the use of n levels, should there ever be a reason. It's doubtfull that a third level will ever be required, but if it is, the design provides for it.

Lookup Algorithm
----------------

Lookup is straightforword:

- Compute a hash of the name
- Read the index root
- Use binary search (linear in the current code) to find the first index or leaf block that could contain the target hash (in tree order)
- Repeat the above until the lowest tree level is reached
- Read the leaf directory entry block and do a normal Ext2 directory block search in it.
- If the name is found, return its directory entry and buffer
- Otherwise, if the collision bit of the next directory entry is set, continue searching in the successor block

Normally, two logical blocks of the file will need to be accessed, and one or two metadata index blocks. The effect of the metadata index blocks can largely be ignored in terms of disk access time since these blocks are unlikely to be evicted from cache. There is some small CPU cost that can be addressed by moving the whole directory into the page cache.

Insert Algorithm
----------------

Insertion of new entries into the directory is considerably more complex than lookup, due to the need to split leaf blocks when they become full, and to satisfy the conditions that allow hash key collisions to be handled reliably and efficiently. I'll just summarize here:

- Probe the index as for lookup
- If the target leaf block is full, split it and note the block that will receive the new entry
- Insert the new entry in the leaf block using the normal Ext2 directory entry insertion code.

The details of splitting and hash collision handling are somewhat messy, but I will be happy to dwell on them at length if anyone is interested.

Splitting
---------

In brief, when a leaf node fills up and we want to put a new entry into it the leaf has to be split, and its share of the hash space has to be partitioned. The most straightforward way to do this is to sort the entrys by hash value and split somewhere in the middle of the sorted list. This operation is log(number_of_entries_in_leaf) and is not a great cost so long as an efficient sorter is used. I used Combsort for this, although Quicksort would have been just as good in this case since average case performance is more important than worst case.

An alternative approach would be just to guess a median value for the hash key, and the partition could be done in linear time, but the resulting poorer partitioning of hash key space outweighs the small advantage of the linear partition algorithm. In any event, the number of entries needing sorting is bounded by the number that fit in a leaf.

Key Collisions
--------------

Some complexity is introduced by the need to handle sequences of hash key collisions. It is desireable to avoid splitting such sequences between blocks, so the split point of a block is adjusted with this in mind. But the possibility still remains that if the block fills up with identically-hashed entries, the sequence may still have to be split. This situation is flagged by placing a 1 in the low bit of the index entry that points at the sucessor block, which is naturally interpreted by the index probe as an intermediate value without any special coding. Thus, handling the collision problem imposes no real processing overhead, just come extra code and a slight reduction in the hash key space. The hash key space remains sufficient for any conceivable number of directory entries, up into the billions.

Hash Function
-------------

The exact properties of the hash function critically affect the performance of this indexing strategy, as I learned by trying a number of poor hash functions, at times intentionally. A poor hash function will result in many collisions or poor partitioning of the hash space. To illustrate why the latter is a problem, consider what happens when a block is split such that it covers just a few distinct hash values. The probability of later index entries hashing into the same, small hash space is very small. In practice, once a block is split, if its hash space is too small it tends to stay half full forever, an effect I observed in practice.

After some experimentation I came up with a hash function that gives reasonably good dispersal of hash keys across the entire 31 bit key space. This improved the average fullness of leaf blocks considerably, getting much closer to the theoretical average of 3/4 full.

But the current hash function is just a place holder, waiting for an better version based on some solid theory. I currently favor the idea of using crc32 as the default hash function, but I welcome suggestions.

Inevitably, no matter how good a hash function I come up with, somebody will come up with a better one later. For this reason the design allows for additional hash functiones to be added, with backward compatibility. This is accomplished simply, by including a hash function number in the index root. If a new, improved hash function is added, all the previous versions remain available, and previously created indexes remain readable.

Of course, the best strategy is to have a good hash function right from the beginning. The initial, quick hack has produced results that certainly have not been disappointing.

Performance
-----------

OK, if you have read this far then this is no doubt the part you've been waiting for. In short, the performance improvement over normal Ext2 has been stunning. With very small directories performance is similar to standard Ext2, but as directory size increases standard Ext2 quickly blows up quadratically, while htree-enhanced Ext2 continues to scale linearly.

Uli Luckas ran benchmarks for file creation in various sizes of directories ranging from 10,000 to 90,000 files. The results are
pleasing: total file creation time stays very close to linear, versus quadratic increase with normal Ext2.

Time to create:

		Indexed		Normal
		=======		======

10000 Files: 0m1.350s 0m23.670s
20000 Files: 0m2.720s 1m20.470s
30000 Files: 0m4.330s 3m9.320s
40000 Files: 0m5.890s 5m48.750s
50000 Files: 0m7.040s 9m31.270s
60000 Files: 0m8.610s 13m52.250s
70000 Files: 0m9.980s 19m24.070s
80000 Files: 0m12.060s 25m36.730s
90000 Files: 0m13.400s 33m18.550s

A graph is posted at:

http://www.innominate.org/~phillips/htree/performance.png

All of these tests are CPU-bound, which may come as a surprise. The directories fit easily in cache, and the limiting factor in the case of standard Ext2 is the looking up of directory blocks in buffer cache, and the low level scan of directory entries. In the case of htree indexing there are a number of costs to be considered, all of them pretty well bounded. Notwithstanding, there are a few obvious optimizations to be done:

- Use binary search instead of linear search in the interior index nodes.

- If there is only one leaf block in a directory, bypass the index probe, go straight to the block.

- Map the directory into the page cache instead of the buffer cache.

Each of these optimizations will produce a noticeable improvement in performance, but naturally it will never be anything like the big jump going from N**2 to Log512(N), ~= N. In time the optimizations will be applied and we can expect to see another doubling or so in performance.

There will be a very slight performance hit when the directory gets big enough to need a second level. Because of caching this will be very small. Traversing the directories metadata index blocks will be a bigger cost, and once again, this cost can be reduced by moving the directory blocks into the page cache.

Typically, we will traverse 3 blocks to read or write a directory entry, and that number increases to 4-5 with really huge directories. But this is really nothing compared to normal Ext2, which traverses several hundred blocks in the same situation.

Current Implementation
----------------------

The current implementation has only a single level of the htree (the root) and is sufficient to handle a little more than 90,000 files. This good enough for benchmarking. There has not been a lot of stability testing yet and indeed there are a number of unhandled error conditions in the code, and possibly some buffer leaks as well.

This patch is for kernel 2.4.1, but it should be entirely applicable to the 2.2 series as well. There it should find a friend: Stephen Tweedie's Ext3 journalling extension.

To-do List
----------

There is still a fair amount of work remaining before this patch is ready for regular use. Here is the to-do list as of today:

- finalize the file format
- endianness
- improve the hash function
- INCOMPAT flag handling
- second tree level
- bullet proofing
- testing under load

Additionally, some (small) changes will be required in ext2utils. The ETA for completion of the items on the to-do list is... pretty soon.

Credits
-------

Thanks to Ted Ts'o for providing the inspiration and essential design elements. Many thanks to Uli Luckas for spending large number of hours drinking beer^H^H^H^H^H^H^H^H^H^H walking through the code with me, suggesting a number of design improvements and understanding and fixing at least one part of the code which remains, quite frankly, beyond me. :-)

Applying and Running the patch
------------------------------

The patch adds a symbol to ext2_fs.h, CONFIG_EXT2_INDEX, which controls whether the htree index feature is enabled or not - it defaults to on.

- Use a test machine, not your workstation :-)
- cd to the 2.4.1 source root
- patch -p0 <this.email
- build and install - should have no effect on normal operation
- mount /dev/hdxxx /test -t ext2 -o index

All new directories in the mounted partition will be created indexed.

Here is the patch:

@@ -67,22 +67,24 @@
 {
 	int error = 0;
 	unsigned long offset, blk;
-	int i, num, stored;
-	struct buffer_head * bh, * tmp, * bha[16];
-	struct ext2_dir_entry_2 * de;
-	struct super_block * sb;
-	int err;
+	int i, num, stored = 0, err;
+	struct buffer_head *bh = NULL, *tmp, *bha[16];
+	struct ext2_dir_entry_2 *de;
 	struct inode *inode = filp->f_dentry->d_inode;
+	struct super_block *sb = inode->i_sb;
+	unsigned blockshift = EXT2_BLOCK_SIZE_BITS(sb);
+#ifdef CONFIG_EXT2_INDEX
+	int dir_base = is_dx(inode)? dx_dir_base(sb): 0;
+#else
+	int dir_base = 0;
+#endif
 
-	sb = inode->i_sb;
-
-	stored = 0;
-	bh = NULL;
 	offset = filp->f_pos & (sb->s_blocksize - 1);
 
-	while (!error && !stored && filp->f_pos < inode->i_size) {
-		blk = (filp->f_pos) >> EXT2_BLOCK_SIZE_BITS(sb);
-		bh = ext2_bread (inode, blk, 0, &err);
+	while (!error && !stored && filp->f_pos < inode->i_size - (dir_base << blockshift))
+	{
+		blk = (filp->f_pos) >> blockshift;
+		bh = ext2_bread (inode, dir_base + blk, 0, &err);
 		if (!bh) {
 			ext2_error (sb, "ext2_readdir",
 				    "directory #%lu contains a hole at offset %lu",

@@ -95,9 +97,9 @@
 		 * Do the readahead
 		 */
 		if (!offset) {
-			for (i = 16 >> (EXT2_BLOCK_SIZE_BITS(sb) - 9), num = 0;
-			     i > 0; i--) {
-				tmp = ext2_getblk (inode, ++blk, 0, &err);
+			for (i = 16 >> (blockshift - 9), num = 0; i > 0; i--)
+			{
+				tmp = ext2_getblk (inode, dir_base + ++blk, 0, &err);
 				if (tmp && !buffer_uptodate(tmp) && !buffer_locked(tmp))
 					bha[num++] = tmp;
 				else

@@ -140,8 +142,7 @@
 			de = (struct ext2_dir_entry_2 *) (bh->b_data + offset);
 			if (!ext2_check_dir_entry ("ext2_readdir", inode, de,
 						   bh, offset)) {
-				/* On error, skip the f_pos to the
-                                   next block. */
+				/* On error, skip the f_pos to the next block. */
 				filp->f_pos = (filp->f_pos | (sb->s_blocksize - 1))
 					      + 1;
 				brelse (bh);

@@ -188,6 +188,12 @@
 				printk("EXT2 Check option not supported\n");
 #endif
 		}
+		else if (!strcmp (this_char, "index"))
+#ifdef CONFIG_EXT2_INDEX
+			set_opt (*mount_options, DXTREE);
+#else
+			printk("EXT2 Index option not supported\n");
+#endif
 		else if (!strcmp (this_char, "debug"))
 			set_opt (*mount_options, DEBUG);
 		else if (!strcmp (this_char, "errors")) {

@@ -40,6 +40,12 @@
 #define EXT2FS_VERSION		"0.5b"
 
 /*
+ * Hash Tree Directory indexing
+ * (c) Daniel Phillips, 2001
+ */
+#undef CONFIG_EXT2_INDEX
+
+/*
  * Debug code
  */
 #ifdef EXT2FS_DEBUG

@@ -53,7 +59,7 @@
 #endif
 
 /*
- * Special inodes numbers
+ * Special inode numbers
  */
 #define	EXT2_BAD_INO		 1	/* Bad blocks inode */
 #define EXT2_ROOT_INO		 2	/* Root inode */

@@ -197,7 +203,7 @@
 #define EXT2_NOCOMP_FL			0x00000400 /* Don't compress */
 #define EXT2_ECOMPR_FL			0x00000800 /* Compression error */
 /* End compression flags --- maybe not all used */	
-#define EXT2_BTREE_FL			0x00001000 /* btree format dir */
+#define EXT2_INDEX_FL			0x00001000 /* btree format dir */
 #define EXT2_RESERVED_FL		0x80000000 /* reserved for ext2 lib */
 
 #define EXT2_FL_USER_VISIBLE		0x00001FFF /* User visible flags */

@@ -314,6 +320,7 @@
 #define EXT2_MOUNT_ERRORS_PANIC		0x0040	/* Panic on errors */
 #define EXT2_MOUNT_MINIX_DF		0x0080	/* Mimics the Minix statfs */
 #define EXT2_MOUNT_NO_UID32		0x0200  /* Disable 32-bit UIDs */
+#define EXT2_MOUNT_DXTREE		0x0400  /* Enable dx trees */
 
 #define clear_opt(o, opt)		o &= ~EXT2_MOUNT_##opt
 #define set_opt(o, opt)			o |= EXT2_MOUNT_##opt

@@ -518,6 +525,16 @@
 #define EXT2_DIR_ROUND 			(EXT2_DIR_PAD - 1)
 #define EXT2_DIR_REC_LEN(name_len)	(((name_len) + 8 + EXT2_DIR_ROUND) & \
 					 ~EXT2_DIR_ROUND)
+
+/*
+ * Hash Tree Directory indexing
+ * (c) Daniel Phillips, 2001
+ */
+#ifdef CONFIG_EXT2_INDEX
+#define is_dx(dir) (dir->u.ext2_i.i_flags & EXT2_INDEX_FL)
+#define dx_entries_per_block(sb) (EXT2_BLOCK_SIZE(sb) >> 3)
+#define dx_dir_base(sb) (dx_entries_per_block(sb) - 1 + 1)
+#endif
 
 #ifdef __KERNEL__
 /*

Daniel

In article <01022020011905.18944@gimli>,

Interesting.

However, if you're playing with the directory structure, please consider getting rid of the "struct buffer_head"-centricity, and using the page cache instead. The page cache has much nicer caching semantics, and looking up data in the page cache is much faster because it never needs to do the "virtual->physical" translation.

Talk to Al Viro about this - he's already posted patches to move the regular ext2 directory tree into the page cache, and they weren't applied to 2.4.x only because there was no great feeling of "we _must_ do this for correctness".

I see that you already considered this issue, but I wanted to bring it up again simply because something like this certainly looks like a potential candidate for 2.5.x, but I will _refuse_ to add code that increases our reliance of "struct buffer_head" as a caching entity. So I'd rather see the page cache conversion happen sooner rather than later...

Also, just out of interest: if you've already been worrying about hashes, what's the verdict on just using the native dentry hash value directly? It has other constraints (_really_ low latency and absolutely performance critical to calculate for the common case, which is not needing a real lookup at all), but maybe it is good enough? And if not, and you have done some statistics on it, I'd love to hear about it ;)

Linus

In the case of your script I'm not sure this will help, but:
I've seen /home directories organised like /home/a/adamsonj, /home/a/arthurtone, /home/b/barrettj, etc.
this way (crude) indexing only costs areas where it's needed, without kernel modification. (app does it) What other placed would we need indexing *in* the filesystem?

the way i'm reading this, the problem is there's 65535 files in the directory /where/postfix/lives. rm * or what have you, is going to take forever and ever, and bog the machine down while its doing it. My understanding is you could do the rm *, and instead of it reading the tree over and over for every file that has to be deleted, it just jumps one or two blocks to the file that's being deleted, instead of thousands of files to be scanned for each file deleted.

Oh yes, I was planning on it. I started with the buffers version for two main reasons version: 1) it's simple and solid and 2) it provides the basis for a backport to 2.2 - after the 2.4/2.5 version is complete of course.

You are preaching to the converted.

You mean full_name_hash? I will un-static it and try it. I should have some statistics tomorrow. I have a couple of simple metrics for measuring the effectiveness of the hash function: the uniformity of the hash space splitting (which in turn affects the average fullness of directory leaves) and speed.

Let the hash races begin.

Daniel

I was more thinking about just using "dentry->d_name->hash" directly, and not worrying about how that hash was computed. Yes, for ext2 it will have the same value as "full_name_hash" - the difference really being that d_hash has already been precomputed for you anyway.

Note that dentry->d_name->hash is really quick (no extra computation), but I'm not claiming that it has anything like a CRC quality. And it's probably a bad idea to use it, because in theory at least the VFS layer might decide to switch the hash function around. I'm more interested in hearing whether it's a good hash, and maybe we could improve the VFS hash enough that there's no reason to use anything else..

Linus

Reiserfs seems to have done a lot of work on this and be using tea, which is also nice as tea is non trivial to abuse as a user to create pessimal file searches intentionally

The default in reiserfs is now the R5 hash, but you are right that lots of efforts went into finding this hash. This includes testing various hashes on real directory structures to see which one worked best. R5 won.

Ed Tomlinson

In article <[email protected]>,

That's interesting. The R5 hash is easily also the only one of the reiser hashes that might be useable for the generic VFS hashing. It's not so different in spirit from the current one, and if you've done the work to test it, it's bound to be a lot better.

(The current VFS name hash is probably _really_ stupid - I think it's still my original one, and nobody probably ever even tried to run it through any testing. For example, I bet that using a shift factor of 4 is really bad, because it evenly divides a byte, which together with the xor means that you can really easily generate trivial bad cases).

What did you use for a test-case? Real-life directory contents? Did you do any worst-case analysis too?

Linus

Yep, 4 is not good as a shifting factor. Prime number are the better choice for this stuff.
The issue to have a good distribution is not only to have a good hashing function, but also to give this function not correlated data.
Good hashing function for a Domain A may not be so good for a Domain B.

- Davide

In article <[email protected]>,

Oh, absolutely.

It looks like the hash function was done rather early on in the dcache lifetime (one of the first things), back when nobody cared about whether it was really good or not because there were many much more complicated questions like "how the h*ll will this all ever work" ;)

And at no point did anybody ever go back and verify whether the hash function made much sense or not.

We had another boo-boo with the actual _folding_ of the "full" hash value into the actual hash chain pointer that is done when the name cache is actually looked up, which was even more embarrassing: even if the hash ended up being ok, we would remove most of the valid bits from it because it would under certain circumstances (512MB of RAM on x86) basically xor itself with itself.

That took quite a while to find too - the code still worked fine, it just had a horrible distribution on machines with half a gig of memory.

This is not something we can do all that much about. The data we get is generated by the user, and can basically be a random string of characters. HOWEVER, there are certainly tons of _usual_ data, and while there's no way to select the data we can at least try to make sure that the distribution is good for the normal case (ie regular ASCII filenames, not forgetting the fact that many people use more interesting encodings)

Linus

Followup to:  <[email protected]>
By author:    [email protected] (Linus Torvalds)
In newsgroup: linux.dev.kernel

Actually, the VFS name hash I think is derived from the "Dragon Book" hash (via autofs), so it's not like it's completely untested.

-hpa

<[email protected]> at work, <[email protected]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt

It was not me personally.   I just remembered the thread (from june 2000) on the reiserfs list...  I have summerized the results for you below.

For the program see: http://www.jedi.claranet.fr/hash_torture.tar.gz

Ed

PS.  I am still seeing hangs with (2.4.2pre2 then I switched to ac7 or so and have had hangs with all pre and ac(s) tried and that is most of them)  ac20 plus the latest reiserfs fixes has stayed up 8 hours so far - it can take two or three days  to trigger the hang though.  When it hangs it really dead,  a UPS connected via a serial port cannot shut it down.   pings to the box fail. A+SysRQ is dead, and the software watchdog does not trigger a reboot. ideas?

some test results from june 2000 with Hans's summary first.
---------------------------------------------------------------
(reiserfs) Re: r5 hash
From: Hans Reiser <[email protected]>
To: "Yury Yu. Rupasov" <[email protected]>
Cc: Jedi/Sector One <[email protected]>, Petru Paler <[email protected]>, "[email protected]" <[email protected]>, Yury Shevchuk <[email protected]>

Ok, based on this benchmark let's put rupasov5 in, and warn users who choose the
currently used rupasov1 hash that rupasov5 has obsoleted it.  Do this in both 3.6 and 3.5, and fix the the delimiting key check in 3.5 REISERFS_CHECK bug at the same time.  Cut the patch, start testing, and see if you can release by Monday.  Make rupasov5 the default.  sizif, review the documentation he creates
for users.

Jedi, if you disagree with the benchmarks let me know.  You might try concatenating two filenames together instead of adding a digit to them, or running find on a really large FS, to improve these tests.  Thanks for helping us with analyzing the different hash methods available Jedi.

Hans

---------------------------------------------------------------
(reiserfs) Re: r5 hash
From: "Yury Yu. Rupasov" <[email protected]>
To: Hans Reiser <[email protected]>
Cc: Jedi/Sector One <[email protected]>, Petru Paler <[email protected]>, "[email protected]" <[email protected]>, Yury Shevchuk <[email protected]>

Ok, here is the results for real names :

# find / -type d -exec ls {} \; | sort | uniq > allfiles.txt

# wc -l allfiles.txt
161101 allfiles.txt

Collisions for 161 101 names:

tea_hash  : 784 total,  2 dangerous
jedi_hash2: 957 total,  2 dangerous
r5_hash   :1191 total,  2 dangerous
r7_hash   :8439 total, 18 dangerous

The speed for 161 101 real names :

create 161101 files of 10 bytes with names from allfiles.txt

# time create d1 allfiles.txt
# time cp d1 d2 -r
# time rm d1 -r

              create      copy        remove
             --------------------------------
tea_hash   : 1m27.223s   5m43.069s  2m33.449s
jedi_hash2 : 1m26.062s   5m40.872s  2m32.795s
r5_hash    : 1m16.729s   4m14.967s  1m53.037s
r7_hash    : 1m10.665s   3m34.950s  1m39.756s

As you can see the results are differ, but not too much. :) The situation changes dramatically if we will test 1 million files.

The same test, but at the end of each name from allfiles.txt added numbers from 0 to 6 (1 127 707 files):

              create      copy        remove
             --------------------------------
tea_hash   : 81m44.449s
jedi_hash2 : 79m46.419s
r5_hash    : 15m56.037s
r7_hash    : 15m30.680s

Dual Celeron 500, 128 MB RAM, 8 GB scsi HDD
Reiserfs-3.5.21, Linux-2.2.15

Thanks,
Yura.
---------------------------------------------------------------
body { font-family: "helvetica" } p { font-size: 12pt } a { color: #0000ff;
text-decoration: none; }(reiserfs) Torture results
From: Jedi/Sector One <[email protected]>
To: [email protected]

  Here are the results of the hash torture on a Celeron 300. Once again, you can substract 1 from the dangerous collisions numbers. Xuan, can you provide a test for the case Rupasov hash was designed for ?
  Anyway, I don't really see why large directories should have similar file names, rather that keywords.

  Best regards,

         Frank DENIS aka Jedi/Sector One aka DJ Chrysalis <[email protected]>
                 -> Software : http://www.jedi.claranet.fr <-
      If Bill Gates had a dime for every time a Windows box crashed...
                  ...oh, wait a minute -- he already does.


********************** /usr/dict/words test **********************

Trying with   45402 words


-------------[Benchmarking tea hash]-------------

Collisions : 45
Dangerous :       1      ffff980
Timing :

real     0m0.145s
user     0m0.120s
sys      0m0.010s

-------------[Benchmarking rupasov hash]-------------

Collisions : 553
Dangerous :       1      ffffe00
Timing :

real     0m0.297s
user     0m0.260s
sys      0m0.020s

-------------[Benchmarking r5 hash]-------------

Collisions : 185
Dangerous :       1      ffae000
Timing :

real     0m0.124s
user     0m0.080s
sys      0m0.030s

-------------[Benchmarking r7 hash]-------------

Collisions : 2528
Dangerous :       1      fffd400
Timing :

real     0m0.121s
user     0m0.100s
sys      0m0.000s

-------------[Benchmarking jedi hash]-------------

Collisions : 54
Dangerous :       1      fff9780
Timing :

real     0m0.122s
user     0m0.100s
sys      0m0.010s

-------------[Benchmarking jedi2 hash]-------------

Collisions : 93
Dangerous :       1      fff9780
Timing :

real     0m0.122s
user     0m0.090s
sys      0m0.020s

-------------[Benchmarking lookup2 hash]-------------

Collisions : 63
Dangerous :       1      ffff480
Timing :

real     0m0.123s
user     0m0.100s
sys      0m0.000s

********************** Squid names test **********************

Trying with  458752 squid cache entries

-------------[Benchmarking tea hash]-------------

Collisions : 6237
Dangerous :       1      fffff80
Timing :

real     0m1.138s
user     0m1.090s
sys      0m0.030s

-------------[Benchmarking rupasov hash]-------------

Collisions : 377520
Dangerous :       1      e32700
Timing :

real     0m2.588s
user     0m2.550s
sys      0m0.020s

-------------[Benchmarking r5 hash]-------------

Collisions : 309991
Dangerous :       1      55406b80
Timing :

real     0m0.940s
user     0m0.880s
sys      0m0.040s

-------------[Benchmarking r7 hash]-------------

Collisions : 449006
Dangerous :       2      22b16580
Timing :

real     0m0.928s
user     0m0.840s
sys      0m0.070s

-------------[Benchmarking jedi hash]-------------

Collisions : 2771
Dangerous :       1      fffef80
Timing :

real     0m0.928s
user     0m0.860s
sys      0m0.050s

-------------[Benchmarking jedi2 hash]-------------

Collisions : 0
Dangerous :       1      ffff80
Timing :

real     0m0.879s
user     0m0.810s
sys      0m0.050s

-------------[Benchmarking lookup2 hash]-------------

Collisions : 6203
Dangerous :       1      fffdc00
Timing :

real     0m0.930s
user     0m0.840s
sys      0m0.080s

********************** Real names test **********************

Trying with   89830 files

-------------[Benchmarking tea hash]-------------

Collisions : 237
Dangerous :       1      fff5580
Timing :

real     0m0.276s
user     0m0.250s
sys      0m0.000s

-------------[Benchmarking rupasov hash]-------------

Collisions : 6288
Dangerous :       1      ffee080
Timing :

real     0m0.582s
user     0m0.560s
sys      0m0.010s

-------------[Benchmarking r5 hash]-------------

Collisions : 3920
Dangerous :       1      fff4600
Timing :

real     0m0.230s
user     0m0.190s
sys      0m0.020s

-------------[Benchmarking r7 hash]-------------

Collisions : 11801
Dangerous :       1      fff580
Timing :

real     0m0.225s
user     0m0.180s
sys      0m0.030s

-------------[Benchmarking jedi hash]-------------

Collisions : 269
Dangerous :       1      fff9f80
Timing :

real     0m0.226s
user     0m0.200s
sys      0m0.010s

-------------[Benchmarking jedi2 hash]-------------

Collisions : 415
Dangerous :       1      fff9f80
Timing :

real     0m0.225s
user     0m0.200s
sys      0m0.010s

-------------[Benchmarking lookup2 hash]-------------

Collisions : 223
Dangerous :       1      ffff480
Timing :

real     0m0.230s
user     0m0.210s
sys      0m0.000s

----------------------------------------------------------------------------------------

body { font-family: "helvetica" } p { font-size: 12pt } a { color: #0000ff; 
text-decoration: none; }(reiserfs) hash torture results
From: Petru Paler <[email protected]>
To: [email protected]


Machine: AMD Athlon/650MHz, 128Mb RAM, Quantum Fireball lct15 IDE hdd
(UDMA/66 but that doesn't matter). Kernel 2.4.0-test1-ac10.

The results are interesting, but more interesting would be to see how fast
reiserfs actually is with each of these hashes.

Script output:

********************** /usr/dict/words test **********************

Trying with   45402 words


-------------[Benchmarking tea hash]-------------

Collisions : 45
Dangerous :       1      ffff980
Timing :
0.00user 0.01system 0:00.08elapsed 11%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking rupasov hash]-------------

Collisions : 553
Dangerous :       1      ffffe00
Timing :
0.00user 0.00system 0:00.18elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking r5 hash]-------------

Collisions : 185
Dangerous :       1      ffae000
Timing :
0.00user 0.00system 0:00.08elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking r7 hash]-------------

Collisions : 2528
Dangerous :       1      fffd400
Timing :
0.00user 0.01system 0:00.07elapsed 12%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking jedi hash]-------------

Collisions : 54
Dangerous :       1      fff9780
Timing :
0.00user 0.00system 0:00.08elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking jedi2 hash]-------------

Collisions : 93
Dangerous :       1      fff9780
Timing :
0.00user 0.00system 0:00.07elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking lookup2 hash]-------------

Collisions : 63
Dangerous :       1      ffff480
Timing :
0.00user 0.00system 0:00.07elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

********************** Squid names test **********************

Trying with  262144 squid cache entries

-------------[Benchmarking tea hash]-------------

Collisions : 2019
Dangerous :       1      ffff880
Timing :
0.00user 0.01system 0:00.47elapsed 2%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking rupasov hash]-------------

Collisions : 210912
Dangerous :       1      a88f00
Timing :
0.00user 0.02system 0:01.03elapsed 1%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking r5 hash]-------------

Collisions : 171912
Dangerous :       1      54ca7680
Timing :
0.00user 0.03system 0:00.41elapsed 7%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking r7 hash]-------------

Collisions : 256171
Dangerous :       6      22aa0600
Timing :
0.00user 0.03system 0:00.41elapsed 7%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking jedi hash]-------------

Collisions : 589
Dangerous :       1      fffda00
Timing :
0.00user 0.02system 0:00.42elapsed 4%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking jedi2 hash]-------------

Collisions : 0
Dangerous :       1      ffff80
Timing :
0.00user 0.00system 0:00.40elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking lookup2 hash]-------------

Collisions : 2041
Dangerous :       1      fffdc00
Timing :
0.00user 0.01system 0:00.40elapsed 2%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

********************** Real names test **********************

find: /proc/31112/fd/4: No such file or directory
Trying with   94836 files

-------------[Benchmarking tea hash]-------------

Collisions : 235
Dangerous :       1      fff5e80
Timing :
0.00user 0.00system 0:00.20elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking rupasov hash]-------------

Collisions : 2016
Dangerous :       1      fffab80
Timing :
0.01user 0.00system 0:00.46elapsed 2%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking r5 hash]-------------

Collisions : 495
Dangerous :       1      fff8780
Timing :
0.00user 0.00system 0:00.17elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking r7 hash]-------------

Collisions : 8162
Dangerous :       1      fff580
Timing :
0.00user 0.02system 0:00.17elapsed 11%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking jedi hash]-------------

Collisions : 331
Dangerous :       1      ffe400
Timing :
0.00user 0.00system 0:00.17elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking jedi2 hash]-------------

Collisions : 341
Dangerous :       1      ffe400
Timing :
0.00user 0.00system 0:00.17elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-------------[Benchmarking lookup2 hash]-------------

Collisions : 298
Dangerous :       1      fffb700
Timing :
0.00user 0.00system 0:00.17elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (83major+13minor)pagefaults 0swaps

-Petru

I _thought_ that's what you meant, but then I was also thinking that the dentry hash was on the full path name and not just the filename? This wouldn't be any good for use in the directory index, in case the directory is renamed. If this is _not_ the case, then it is a definite candidate.

I was thinking about this as well. Since the setup Daniel has allows us to store a hash version, we could run the hash function on a fixed string at SB init time to give us a hash "version" number. If the hash function changes we will get a new hash "version". We could inline each new dentry hash function into the ext2 code (so we can unpack the directories), or as a cop-out if any directory has a hash version not equal to the current one we re-hash all the entries in the directory.

Cheers, Andreas

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

In the first heat of hash races - creating 20,000 files in one directory
- dentry::hash lost out to my original hack::dx_hash, causing a high percentage of leaf blocks to remain exactly half full and slowing down the whole thing by about 5%. (This was under uml - I haven't tried it native yet but I expect the results to be similar.)

	  Contender			Result
	  =========			======
	dentry::hash		Average fullness = 2352 (57%)
	hack::dx_hash		Average fullness = 2758 (67%)

This suggests that dentry::hash is producing distinctly non-dispersed results and needs to be subjected to further scrutiny. I'll run the next heat of hash races tomorrow, probably with R5, and CRC32 too if I have time.

--
Daniel

I'd love to hear the results from R5, as that seems to be the reiserfs favourite, and I'm trying it out in 2.4.2 because it was so easy to plug in..

Linus

Quick details, since I don't think I've seen them on l-k yet. r5 was chosen because it is more tuned to the reiserfs disk format. The location of a directory item on disk is determined by the hash of the name, and r5 is designed to put similar names close to each other on disk.

The benchmark that shows this best is creating X number of files in a single dir (named 0001, 0002, 0003 etc). r5 greating increases the chances the directory item for 00006 will be right next to the item for 00007. If the application accesses these files in the same order they were created, this has benefits at other times than just creation. The benchmarks Ed posted give a general idea for other naming patterns, but this one is best case:

Time to create 100,000 files (10 bytes each) with r5 hash: 48s Time to create 100,000 files (10 bytes each) with tea: 3m58s

The percentage increase just gets bigger as you create more and more files. That doesn't mean this is a real world case, but it is what the hash was designed for.

-chris

In this round there were two new contenders:

- ReiserFS's R5
- Bob Jenkins' hash

Eirik Fuller pointed me to the latter, the subject of a very interesting article in Dr. Dobbs, available online here:

http://burtleburtle.net/bob/hash/doobs.html

As before, the runs are for 20,000 creates and I report only the fullness, because I'm still running these under UML. Suffice to say that the total running time is roughly related to the average fullness with a variance of about 15% from the best to the worst. Eventually I will rerun the entire series of tests natively and provide more detailed statistics. Here are the results from the second heat of hash races:

	     Contender			Result
	     =========			======
	dentry::hash		Average fullness = 2352 (57%)
	daniel::hack_hash	Average fullness = 2758 (67%)
	bob::hash		Average fullness = 2539
(61%)                                                                                                                 
	reiserfs::r5		Average fullness = 2064 (50%)

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 But according
to Chris Mason (see his post) it does work very well for ReiserFS. This provides a little more evidence that my htree scheme is a quite different from other approaches.

	u32 r5_hash (const char *msg, int len)
	{
	  u32 a=0;
	  while(*msg) { 
	    a += *msg << 4;
	    a += *msg >> 4;
	    a *= 11;
	    msg++;
	   } 
	  return a;
	}

I expected more from bob::hash since it's very carefully well-thought out in terms of dispersal and avoidance of 'funnelling' (the property that determines the probabililty collision), but it still fell short of hack_hash's performance. Oh well. Tomorrow I'll try CRC32.

The bottom line: dx_hack_hash is still the reigning champion. OK, come out and take a bow:

	unsigned dx_hack_hash (const char *name, int len)
	{
		u32 hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
		while (len--)
		{
			u32 hash = hash1 + (hash0 ^ (*name++ * 71523));
			if (hash < 0) hash -= 0x7fffffff;
			hash1 = hash0;
			hash0 = hash;
		}
		return hash0;
	}

--
Daniel

I thought about it again, and the proformance problem with "rm *" is that the shell reads and sorts the directory, passes each file as a separate argument to rm, which then causes the kernel to lookup each file from a random directory block (random because of previous sort), modify that directory block, then read another... after a few seconds the modified blocks start to be written back to disk while new ones are looked up... disk seek contention. and this becomes hard on the dir. block cache (wherever this is) since from source each dir entry is just over 256 bytes (?) 65535 files would require 16MB to cache dir entries. Plus it has to read in all the inodes, modify, then write, taking up xxMB more. You're probably swapping out, with swap partition on same disk, the disk may explode.

If it were truly doing a linear scan, it might be faster. Two successive mods to same dir block would be merged onto same write.

Perhaps rm -rf . would be faster? Let rm do glob expansion, without the sort. Care to recreate those 65535 files and try it?

or use ls with the nosort flag pipe through xargs then to rm... again loose sorting but don't delete directory or subdirs.

Perhaps, but I think that form is still fairly slow. It takes an "uncomfortable" amount of time to remove a complex directory structure using, eg. "rm -rf /usr/src/linux-obsolete" or "rm -rf downloads/XFree86-old-and-buggy". I'm not sure, but I would guess it's not as much quicker than removing each file individually as you might think.

If I had more time on my hands, I'd run some quick benchmarks on some of my systems.

--------------------------------------------------------------

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-----

Indeed, rm -rf is faster. It does a readdir to get all the directory entries in internal order, then calls unlink to remove them, one at a time. This removes each entry from the front of the file, shortening the time that has to be spent scanning forward in the file to find the target entry. Manfred Spraul observed that this could be speeded up with by caching the file position, and sent me a patch to do that. It did speed things up - about 20%.

But actually, rm is not problem, it's open and create. To do a create you have to make sure the file doesn't already exist, and without an index you have to scan on average half the directory file. Open requires a similar scan. Here we are talking about using an index to speed that up quadraticly when operating on N files. That is the real gravy.

Daniel

Unless you use a File System which is better for that, like Reiser-FS. Of course a even better solution is to distribute those files in hashed subdirs.

Greetings
Bernd

Ahem. Please read the first post in the thread. ;-)

Daniel

Have You tried to use skiplists ?
In 93 I've coded a skiplist based directory access for Minix and it gave very interesting performances.
Skiplists have a link-list like performance when linear scanned, and overall good performance in insertion/seek/delete.

- Davide

Hello!

Skip list search/insert/delete is O(log N) in average as skip lists are just a dynamic version of interval bisection. Good hashing is O(1).

Have a nice fortnight

Martin `MJ' Mares <[email protected]> <[email protected]> http://atrey.karlin.mff.cuni.cz/~mj/
Entropy isn't what it used to be.

To have O(1) you've to have the number of hash entries > number of files and a really good hasing function.

To be sincere, here is pretty daylight :)

- Davide

Hello!

No, if you enlarge the hash table twice (and re-hash everything) every time the table fills up, the load factor of the table keeps small and everything is O(1) amortized, of course if you have a good hashing function. If you are really smart and re-hash incrementally, you can get O(1) worst case complexity, but the multiplicative constant is large.

:)
Martin

My personal preference goes to skiplist coz it doesn't have fixed ( or growing ) tables to handle. You've simply a stub of data togheter with FS data in each direntry.
And performance ( O(log2(n)) ) are the same for whatever number of entries.

- Davide

Hello!

Another problem with skip lists is that they require variable sized nodes, so you either need to keep free chunk lists and lose some space in deleted nodes kept in these lists, or you choose to shift remaining nodes which is slow and complicated as you need to keep the inter-node links right. With hashing, you can separate the control part of the structure and the actual data and shift data while leaving most of the control part intact.

I don't understand this complexity estimate -- it cannot be the same for whatever number of entries as the complexity function depends on the number of entries.

Have a nice fortnight

Martin `MJ' Mares <[email protected]> <[email protected]> http://atrey.karlin.mff.cuni.cz/~mj/
P.C.M.C.I.A. stands for `People Can't Memorize Computer Industry Acronyms'

An entry in skip list table is a u32 direntry offset and You've not to keep free entries, simply the height of the node will change depending on the number of entries.

n == number of entries

For constant I mean the formula not the result.

- Davide

Followup to:  <[email protected]>
By author:    Martin Mares <[email protected]>
In newsgroup: linux.dev.kernel

Not true. The rehashing is O(n) and it has to be performed O(log n) times during insertion. Therefore, insertion is O(log n).

-hpa

<[email protected]> at work, <[email protected]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt

Hello!

Rehashing is O(n), but the "n" is the _current_ number of items, not the maximum one after all the insertions.

Let's assume you start with a single-entry hash table. You rehash for the first time after inserting the first item (giving hash table of size 2), then after the second item (=> size 4), then after the fourth item (=> size 8) and so on. I.e., when you insert n items, the total cost of rehashing summed over all the insertions is at most 1 + 2 + 4 + 8 + 16 + ... + 2^k (where k=floor(log2(n))) <= 2^k+1 = O(n). That is O(1) operations per item inserted.

Have a nice fortnight

Martin `MJ' Mares <[email protected]> <[email protected]> http://atrey.karlin.mff.cuni.cz/~mj/
MIPS: Meaningless Indicator of Processor Speed.

You're right. However, for each hash table operation to be O(1) the size of the hash table must be >> n.

I suggested at one point to use B-trees with a hash value as the key. B-trees are extremely efficient when used on a small constant-size key.

-hpa

<[email protected]> at work, <[email protected]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt

Hello!

If we are talking about average case complexity (which is the only possibility with fixed hash function and arbitrary input keys), it suffices to have hash table size >= c*n for some constant c which gives O(1/c) cost of all operations.

Although from asymptotic complexity standpoint hashing is much better than B-trees, I'm not sure at all what will give the best performance for reasonable directory sizes. Maybe the B-trees are really the better alternative as they are updated dynamically and the costs of successive operations are similar as opposed to hashing which is occassionally very slow due to rehashing unless you try to rehash on-line, but I don't know any algorithm for on-line rehashing with both inserts and deletes which wouldn't be awfully complex and slow (speaking of multiplicative constants, of course -- it's still O(1) per operation, but "the big Oh is really big there").

Have a nice fortnight

Martin `MJ' Mares <[email protected]> <[email protected]> http://atrey.karlin.mff.cuni.cz/~mj/
"#define QUESTION ((bb) || !(bb))"  -- Shakespeare

True. Note too, though, that on a filesystem (which we are, after all, talking about), if you assume a large linear space you have to create a file, which means you need to multiply the cost of all random-access operations with O(log n).

Well, once you multiply with O(log n) for the file indirection (which B-trees don't need, since they inherently handle blocking and thus can use block pointers directly) then the asymptotic complexity is the same as well, and I think the B-trees are the overall winner.

-hpa

<[email protected]> at work, <[email protected]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt

Hello!

One could avoid this, but it would mean designing the whole filesystem in a completely different way -- merge all directories to a single gigantic hash table and use (directory ID,file name) as a key, but we were originally talking about extending ext2, so such massive changes are out of question and your log n access argument is right.

Have a nice fortnight

Martin `MJ' Mares <[email protected]> <[email protected]> http://atrey.karlin.mff.cuni.cz/~mj/
COBOL -- Completely Outdated, Badly Overused Language

[email protected] (Martin Mares) wrote on 22.02.01 in <[email protected]>:

s/hash table/btree/ and you have just described the Macintosh HFS file system. (Incidentally, it stores file extent indices in a similar manner, with key = (file id, fork, offset).)

MfG Kai

It would still be tricky since you have to have actual files in the filesystem as well.

-hpa

<[email protected]> at work, <[email protected]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt

Novell, NTFS, HFS all do this.

Roger.

** [email protected] ** http://www.BitWizard.nl/ ** +31-15-2137555 **
*-- BitWizard writes Linux device drivers for any device you may have! --*
* There are old pilots, and there are bold pilots. 
* There are also old, bald pilots. 

A gigantic hash table has serious problems with non-locality of reference. Basically any regular access pattern you started with is destroyed. This is a problem with pageable RAM, let alone disks with millisecond seek times.

-- Jamie

Have you looked at the structure and algorithms I'm using? I would not call this a hash table, nor is it a btree. It's a 'hash-keyed uniform-depth tree'. It never needs to be rehashed (though it might be worthwhile compacting it at some point). It also never needs to be rebalanced - it's only two levels deep for up to 50 million files.

This thing deserves a name of its own. I call it an 'htree'. The performance should speak for itself - 150 usec/create across 90,000 files and still a few optmizations to go.

Random access runs at similar speeds too, it's not just taking advantage of a long sequence of insertions into the same directory.

BTW, the discussion in this thread has been very interesting, it just isn't entirely relevant to my patch :-)

--
Daniel

Daniel,

I'm all but saying that Your algo is not good.
I use something very like to it in my mail server ( XMail ) to index mail queue files that has a two level depth fs splitting.
The mine was only an hint to try different types of directory indexing.

- Davide

I'm curious how you do that. It seems each level would have to be 64K large in order to do that, with a minimum disk space consumption of 128K for a directory. That seems extremely painful *except* in the case of hysterically large directories, which tend to be the exception even on filesystems where they occur.

I think I'd rather take the extra complexity and rebalancing cost of a B-tree.

-hpa

<[email protected]> at work, <[email protected]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt

Easy, with average dirent reclen of 16 bytes each directory leaf block can holds up to 256 entries. Each index block indexes 512 directory blocks and the root indexes 511 index blocks. Assuming the leaves are on average 75% full this gives:

	(4096 / 16) * 512 * 511 * .75 = 50,233,344

I practice I'm getting a little more than 90,000 entries indexed by a *single* index block (the root) so I'm not just making this up.

Do you still think so?

--
Daniel

I was just doing the math for 1k ext2 filesystems, and the numbers aren't nearly as nice. We get:

	(1024 / 16) * 127 * .75 = 6096		# 1 level
	(1024 / 16) * 128 * 127 * .75 = 780288	# 2 levels

Basically (IMHO) we will not really get any noticable benefit with 1 level index blocks for a 1k filesystem - my estimates at least are that the break even point is about 5k files. We _should_ be OK with 780k files in a single directory for a while. Looks like we will need 2-level indexes sooner than you would think though. Note that tests on my workstation showed an average filename length of 10 characters (excluding MP3s at 78 characters), so this would give 20-byte (or 88-byte) dirents for ext3, reducing the files count to 4857 and 621792 (or 78183 and 40029696 for 4k filesystems) at 75% full.

Cheers, Andreas

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

I've had a news server with 2000000 files in one directory. Such a filesystem is likely to use small blocks, too, because each file is generally small.

This is an important connection: filesystems which have lots and lots of small files will have large directories and small block sizes.

-hpa

<[email protected]> at work, <[email protected]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt

I mentioned this earlier but it's worth repeating: the desire to use a small block size is purely an artifact of the fact that ext2 has no handling for tail block fragmentation. That's a temporary situation - once we've dealt with it your 2,000,000 file directory will be happier with 4K filesystem blocks. There will be a lot fewer metadata index blocks in your directory file, for one thing. Another practical matter is that 4K filesystem blocks map directly to 4K PAGE_SIZE and are as a result friendlier to the page cache and memory manager.

--
Daniel

Well, that's something I really don't expect to see anymore -- this "purely temporary situation" is now already 7 years old at least.

-hpa

<[email protected]> at work, <[email protected]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt

Peter, you're barking up the wrong tree - Daniel has had an ext2 tail merging patch around for 6 months or more... However, from the sounds of it, Linus may not want such a thing in ext2 (at least not until he is convinced otherwise). It will be interesting to compare ext2 + ongoing patches vs. new filesystems like reiserfs, XFS, JFS -- not only speed, but reliability as well. XFS and JFS have previous implementations to work with (although the JFS code is not the AIX JFS code), but reiserfs has a long way to go, just from the standpoint of being run on millions of machines, and being looked at by thousands of programmers.

I think people will be surprised at how ext2 + patches will continue to improve. One of the reasons (despite Linus' misgivings, IMHO) is that ext2 is continually being improved by small measures, has lots of eyes on the code, and it offers a stable base for each improvement - which means each improvement is stable and reliable much quicker than if you were to code a new filesystem from scratch for each new feature.

Cheers, Andreas

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

In article <[email protected]>,

I'd rather see a whole new filesystem than have ext2 do tail-block fragmentation.

Once you do tail fragments, you might as well do the whole filesystem over and have it do fancier stuff than just handling sub-blocking.

Another way of saying this: if you go to the complexity of no longer being a purely block-based filesystem, please go the whole way. Make the thing be extent-based, and get away from the notion that you have to allocate blocks one at a time. Make the blocksize something nice and big, not just 4kB or 8kB or something.

And don't call it ext2.

Linus

Oh yes, another thing: a B-tree directory structure does not need metadata index blocks.

-hpa

<[email protected]> at work, <[email protected]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt

Before people get excited about complex tree directory indexes, remember to solve the other 95% before implementation - recovering from lost blocks, corruption and the like

Thus spake Alan Cox ([email protected]):

And don't forget the trouble with NFS handles after the tree was rebalanced.

Trees are nice only theoretically. In practice, the benefits are outweighed by the nastiness in form of fsck and NFS and bigger code (normally: more complex -> less reliable).

Felix

In article <[email protected]>,

Btw, this is also going to be a VM and performance issue some time in the future. Tgere are already CPU's that would _love_ to have 64kB pages etc, and as such a filesystem that doesn't play with the old silly "everthing is a block" rules would be much appreciated with the kind of people who have multi-gigabyte files and want to read in big chunks at a time.

So either you have a simple block-based filesystem (current ext2, no extents, no crapola), or you decide to do it over. Don't do some half-way thing, please.

Linus

Hi Linus,
Hi LKML people,

For this we need a block remapper layer that can map any blocksize n to any blocksize m with only the following constraints:

- n and m are powers of 2
- n is a multiple of m

Both should use the page cache ( of size p) of course, so it becomes 2 layers, if n > p.

- translating a buffer of n into some pages
- translating a page into buffers of m (current buffercache)

We could limit the translation to 5 powers of 2 obove and 5 powers of 2 below PAGE_CACHE_SIZE so that we can maintain a validity bitmap (2^5 = 32 bits) for each layer if access is too expensive[1].

Some subsystems could certainly benefit from it.

   -  loop device (with all the crypto stuff)
   -  LVM
   -  FSes that support block sizes != PAGE_CACHE_SIZE
   -  Devices with blocksize != 512 (they don't have to care

being special anymore). There are even some rumors about very pervert blocksizes of 1M and the like.

Since these remapped buffers will look like merged requests, I see even no problems with the elevator any more.

The question is, where we implement this infrastructure, esp. if we consider the last user (devices with blocksize != 512).

This has to be answered by the main architects of Linux before anyone could start.

Daniel (and others) uses ext2 as as a playground, because it is implemented, tested and not that hard to understand and verify.

Hope they will switch to some own design later, once they sufficiently played around with^W^W^Wtested their ideas.

Regards

Ingo Oeser

[1] In buffer cache we use read-modify-write for partial pages, which hurts performance for them and is annoying for media with limited write cycles like flash and CD-RW[2].

[2] Yes I know about packet writing mode ;-)

10.+11.03.2001 - 3. Chemnitzer LinuxTag <http://www.tu-chemnitz.de/linux/tag>
         <<<<<<<<<<<<       come and join the fun       >>>>>>>>>>>>

No, nothing like that at all..

What you can _trivially_ do is to basically act to the VFS and VM layer as if you're a 1kB block filesystem (or something), and then when you get called to do a "bmap()" (which only happens for kernel installing and LILO, not under normal load), you just return the "offset" into a larger block.

The VFS and MM layers do not care what the _real_ underlying blocksize of the filesystem is. They will just do "readpage()" and "write()" calls, and you can implement those any way you want to - never showing that you are chunking out page-sized pieces from a bigger allocation block.

It's not all that hard. You just have to think a bit differently: don't think of it as a block-based filesystem that has to have fixed blocks. The VFS and MM layer don't care. They just want to access it.

I realize that. But I get _very_ nervous when people talk about adding stuff to ext2, because there are a lot of people who do not want to ever even by mistake run code that is "new" on their filesystem.

Note that I had the same issue with ext3 - for the longest time, Stephen Tweedie wanted to just extend ext2, and make it an invisible upgrade where the filesystem would just magically become journalled when the user asked for it. It _sounds_ appealing, but it doesn't take into account (a) inevitable bugs and (b) the fact that Reiserfs actually got a head start at least partly because it didn't need to worry about backwards compatibility at all (there were other reasons too).

Basically, if there is one thing I've learnt over ten years of Linux, it's that it is absolutely _evil_ to add more "linkages" or dependencies than you absolutely have to. It is _much_ easier to create a new filesystem, and slowly phase out old code that is no longer used. It's been done several times (both with filesystems and with drivers), and every time we've had a "new X, phase out old X" kind of situation it has been very smooth.

In comparison, if you have "new features in X, which also handles the old cases of X" situation, you not only bind yourself to backwards compatibility, but you also cause yourself to be unable to ever phase out the old code. Which means that eventually the whole system is a piece of crap, full of old garbage that nobody needs to use, but that is part of the new stuff that everybody _does_ use.

Linus

But you are getting over 3/4 million files in one directory on a 1K blocksize system, and you really shouldn't be using 1K blocks on a filesystem under that big a load. Is it just to reduce tail block fragmentation? That's what tail merging is for - it does a much better job than shrinking the block size.

But if you are *determined* to use 1K blocks and have more than 1/2 million files in one directory then I suppose a 3rd level is what you need. The uniform-depth tree still works just fine and still doesn't need to be rebalanced - it's never out of balance.

--
Daniel

I would rather simply go to some chained block scheme at that point. ext2 is already fairly fast at linear searching, so if we index a HUGE directory we are still linearly searching only 1/2^16 of the directory (at worst for 1k blocks, 1/2^20 for 4k blocks).

I just had a clever idea - on a single-level index you put the header and index data in block 0, and put the directory data in the first indirect block (11 sparse blocks, instead of 511). If you need to go to a second-level index, you can simply shift the indirect data block to be a double-indirect block, and start the level-2 index in the first indirect block. If we ever need a third-level index, you basically do the same thing - move the double-indirect blocks to triple-indirect, and put the level-3 index in the double-indirect block. It will always fit, because the index branching level is 1/2 of the indirect block branching level because the index has the extra 4-byte hash values.

Andreas:

Daniel:

One of the (many) benefits of ext2 is that it has tried to maintain compatibility as much as possible, if possible. In this case, I don't see that there is an overwhelming reason to NOT keep compatibility, and I think Ted agrees:

Having real dirents for "." and ".." only costs 16 more bytes (2 index leaves), compared to only keeping the inode numbers.

Andreas:

(in directory block 0)

Daniel:

You don't always have the luxury to go back to an old kernel (for whatever reason), and if an incompat flag is set the kernel will refuse to mount your old filesystem. If this is your root, you can't even run fsck. Yes, I know - have a rescue disk/partition - but _sometimes_ you are just stuck and it would be good to not get into that situation in the first place.

Andreas:

Daniel:

Andreas:

Daniel:

But you still need to handle the case for an arbitrary-sized non-indexed directory, if you want to be able to upgrade an existing ext2 filesystem. Since you need this, you may as well only turn indexing when you are actually getting a speed benefit, because doing anything else still wastes space. It may even be that indexing a large existing directory and _then_ doing the lookup is still faster than doing the lookup on the original un-indexed directory...

This is what I also suggested for second-level index blocks above. However, for a single-level index, blocks 1-511 (1-127 on a 1k filesystem) will be sparse, because they will be unused - we don't want to have 511 (or 127) real empty dir blocks just for compatibility on a single-level index. The ext2 dir code handles the case of a sparse directory block with an ext2_error() and continues. By default ext2_error() is just a printk, and on the only system I have seen where it is otherwise (Debian), it is remount-ro for root only.

Yes, I had something like this on the tip of my brain as well. When you boot with a non-index ext2 kernel, it will naturally find free space in the first block, immediately after "." and ".." (with the setup above). Not only will it clear BTREE_FL, it will also overwrite the index magic (if we have one) so we definitely know that the index is not valid. Since the index head is only using 4 of the 8 bytes needed for alignment, we could stick in a 4 byte magic before or after the index header, and still be assured that it will be overwritten by a new dirent.

Full COMPAT support would be a win, IMHO. You could leave it to e2fsck to do reindexing, or the next time a file is added (or even removed) from a candidate directory it could do the reindexing, which it needs to be able to do for compatibility with old filesystems.

Cheers, Andreas

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

That's a three-level tree, not a two-level tree.

I think so.

-hpa

<[email protected]> at work, <[email protected]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt

Also sprach H. Peter Anvin:
} Martin Mares wrote:
} >
} > Hello!
} >
} > > True. Note too, though, that on a filesystem (which we are, after all, } > > talking about), if you assume a large linear space you have to create a } > > file, which means you need to multiply the cost of all random-access } > > operations with O(log n).
} >
} > One could avoid this, but it would mean designing the whole filesystem in a } > completely different way -- merge all directories to a single gigantic } > hash table and use (directory ID,file name) as a key, but we were originally } > talking about extending ext2, so such massive changes are out of question } > and your log n access argument is right.
} >
}
} It would still be tricky since you have to have actual files in the } filesystem as well.
}
But that's just a user space issue, isn't it.

(Just kidding :-)

|| Bill Wendling			[email protected]

Daniel,

Nice work!

A couple of comments. If you make the beginning of each index block look like a an empty directory block (i.e, the first 8 blocks look like this):

	32 bits: ino == 0
	16 bits: rec_len == blocksize
	16 bits: name_len = 0

... then you will have full backwards compatibility, both for reading *and* writing. When reading, old kernels will simply ignore the index blocks, since it looks like it has an unpopulated directory entry. And if the kernel attempts to write into the directory, it will clear the BTREE_FL flag, in which case new kernels won't treat the directory as a tree anymore. (Running a smart e2fsck which knows about directory trees will be able to restore the tree structure).

Is it worth it? Well, it means you lose an index entry from each directory block, thus reducing your fanout at each node of the tree by a worse case of 0.7% in the worst case (1k blocksize) and 0.2% if you're using 4k blocksizes.

- Ted

:-) That's really nice, now I see what you were thinking about with all those bit clears.

I'll leave that up to somebody else - we now have two alternatives, the 100%, no-compromise INCOMPAT solution, and the slightly-bruised but still largely intact forward compatible solution. I'll maintain both solutions for now code so it's just as easy to choose either in the end.

Daniel

From: Daniel Phillips <[email protected]>
Date: Thu, 22 Feb 2001 08:24:08 +0100
Content-Type: text/plain

I'll leave that up to somebody else - we now have two alternatives, the 100%, no-compromise INCOMPAT solution, and the slightly-bruised but still largely intact forward compatible solution. I'll maintain both solutions for now code so it's just as easy to choose either in the end.

Well, the $64,000 question is exactly how much performance does it cost? My guess is that it will be barely measurable, but only benchmarks will answer that question.

- Ted

One important question as to the disk format is whether the "." and ".." interception by VFS is a new phenomenon in 2.4 or if this also happened in 2.2? If so, then having these entries on disk will be important for 2.2 compatibility, and you don't want to have different on-disk formats between 2.2 and 2.4.

Cheers, Andreas

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

From: Andreas Dilger <[email protected]>
Date: Thu, 22 Feb 2001 11:16:32 -0700 (MST)

One important question as to the disk format is whether the "." and ".." interception by VFS is a new phenomenon in 2.4 or if this also happened in 2.2? If so, then having these entries on disk will be important for 2.2 compatibility, and you don't want to have different on-disk formats between 2.2 and 2.4.

Well, you need to have the '.' and '..' there for compatibility if you
for the full backwards compatibility. That's clear.

If you don't care about backwards compatibility, it's important that there be a way to find the parent directory, but there doesn't have to be explicit '.' and '..' entries.

So if Daniel is going to try implementing it both ways then that's one place where the #ifdef's might get a bit more complicated. After it's done, we should do some benchmarks comparing it both ways; if the difference is negligible, I'd argue for simply always providing backwards compatibility. One of the key advantages of ext2/ext3 is its backwards compatibility, and so if it's not too costly to preserve it (as I suspect will be the case), we should try to do so.

- Ted

The answer is 'yes', it's been in since at least the beginning of 2.2:

http://innominate.org/cgi-bin/lksr/linux/fs/namei.c?rev=1.1&content-type=text/x-cvsweb-markup&cvsroot=v2.2

Search for '.'.

By the way, out whole linux cvsweb tree is here:

	http://lksr.org/ 

will all versions of linux back to linux-0.97.pl5, with a makefile that starts out with:

#
# Makefile for linux.
# If you don't have '-mstring-insns' in your gcc (and nobody but me has
:-)

	# remove them from the CFLAGS defines.
	#

Getting back on topic, this makes the idea of getting rid of the actual on-disk "." and ".." entries a little less scary, though I am keeping in mind the fact that having those entries on disk could in some extreme circumstance help fsck recover a a corrupted directory tree little better and more automatically.

I resolve not to take a position on this subject, and I will carry forward both a 'squeaky clean' backward-compatible version that sets an INCOMPAT flag, and a 'slightly tarnished' but very clever version that is both forward and backward-compatible, along the lines suggested by Ted. Both flavors have the desireable property that old versions of fsck with no knowledge of the new index structure can remove the indices automatically, with fsck -y.

--
Daniel

From: Daniel Phillips <[email protected]>
Date: Fri, 23 Feb 2001 00:04:02 +0100

I resolve not to take a position on this subject, and I will carry forward both a 'squeaky clean' backward-compatible version that sets an INCOMPAT flag, and a 'slightly tarnished' but very clever version that is both forward and backward-compatible, along the lines suggested by Ted. Both flavors have the desireable property that old versions of fsck with no knowledge of the new index structure can remove the indices automatically, with fsck -y.

Note that in the long run, the fully comatible version should probably have a COMPAT feature flag set so that you're forced to use a new enough version of e2fsck. Otherwise an old e2fsck may end up not noticing corruptions in an index block which might cause a new kernel to have serious heartburn.

- Ted

Actually, having a COMPAT flag also helps in other ways:

1) Turning indexing on and off is not a mount option as it currently is (or automatically done) so it will quell Linus' fears about priniciple of least surprise (i.e. not converting a filesystem without user action). A superblock COMPAT flag is more in keeping with other ext2 features.

2) Running a new e2fsck on a COMPAT_INDEX filesystem could create the index for existing "large" directories that don't have the BTREE/INDEX flag set, so the kernel only ever has to deal with incremental indexing after the first block. The kernel would just do linear access on existing multi-block directories until e2fsck is run.

3) Clearing the COMPAT flag would make e2fsck remove the indexes, if the user so desires. I think this would be the behaviour of existing e2fsck anyways.

Cheers, Andreas

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

[email protected] (Daniel Phillips) wrote on 20.02.01 in <01022020011905.18944@gimli>:

I once liked those things, too - but I've learned better since.

Quoting _Handbook_of_Algorithms_and_Data_Structures_ (Gonnet/Baeza-Yates, ISBM 0-201-41607-7, Addison-Wesley):

--- snip ---

3.3.1 Practical hashing functions

[...]

A universal class of hashing functions is a class with the property that given any input, the average performance of all the functions is good. [...] For example, h(k) = (a * k + b) mod m with integers a != 0 and b is a universal class of hash functions.
[...]
Keys which are strings or sequences of words (including those which are of variable length) are best treated by considering them as a number base b. Let the string s be composed of k characters s1s2...sk. Then

        h(s) = ( sum(i=0..k-1) B^i*s(k-i) ) mod m

To obtain a more efficient version of this function we can compute

        h(s) = ( ( sum(i=0..k-1) B^i*s(k-i) ) mod 2^w ) mod m

where w is the number of bits in a computer word, and the mod 2^w operation is done by the hardware. For this function the value B = 131 is recommended, as B^i has a maximum cycle mod 2^k for 8<=k<=64.

Hashing function for strings

        int hashfunction(s)
        char *s;

        { int i;
          for(i=0; *s; s++) i = 131*i + *s;
          return(i % m);
        }

--- snip ---

I've actually used that function for a hash containing something like a million phone numbers as keys, and there were *very* few collisions. Similarly for another hash containgng megabytes of RFC 822 message-ids.

MfG Kai