Dynamic hash tables [LWN.net]

Dynamic hash tables

Posted Sep 25, 2014 16:55 UTC (Thu) by Wol (subscriber, #4433)
In reply to: Dynamic hash tables by perlwolf
Parent article: Relativistic hash tables, part 1: Algorithms

Yep, I know that, but how important is that?

Standard stats for Pick are that it splits at 80%, merges at 50%, and 95% of accesses hit on the first attempt.

You need some way of handling overflow whatever you do, - how often do you need to rehash these relativistic tables? - how do you handle it overflowing there?

It's a tradeoff - a relativistic rehash is expensive so you need to waste disk/memory to suppress rehashes. Dynamic hashing makes much more efficient use of disk and memory, and reduces the cost of rehashing at, as you say, slightly uneven bucket filling.

But if you need to cope with buckets overfilling anyway, so what about dynamic hashing having uneven buckets ...

Cheers,
Wol

to post comments

Dynamic hash tables

Posted Sep 25, 2014 17:49 UTC (Thu) by perlwolf (guest, #46060) [Link] (10 responses)

The importance is that there is probably no advantage gained by frequently splitting one entry instead of rarely splitting all of them. That's especially true here where splitting a bucket requires waiting a number of delay times as the contents get moved to the new pair of buckets; since splitting all of the buckets can share series of delay periods. Doing individual splits would mean that each one provides a multi-delay period that requires careful processing for additions and deletions.

Consider going from 64 buckets to 128, and assume that the buckets require on the average one time delay for the initial head split and one time delay for the node splitting, (with that average coming from a number of buckets which require no extra delays, many that require one, and a few that require 2 or 3).

Doing the splits individually would have write contention for about 64 operations, each blocking for 1 to 4 delay times. Doing all of the splits at once would require a single blocking period of write contention that lasted 4 delay times.

There's also the cost of setting up the new array of bucket pointers 64 times instead of once - if that is done with an array allocation each time there is a much higher total execution cost.

For dynamic uneven buckets, one possibility might be to have two type of bucket pointer. The normal one points to a linked list, but the alternate form points to a small 2**k bucket list that uses the next bits of the hash code.

Dynamic hash tables

Posted Sep 26, 2014 0:40 UTC (Fri) by Wol (subscriber, #4433) [Link] (9 responses)

I'll need to investigate that. But, equally, it's a tradeoff again. Are you saying the big time-killer is the head-split?

Because with dynamic hashing, if you're not interested in the bucket being split, there's no delay.

What I'd do is - in my example - lock bucket 5 with a "splitting" status. Split or merge it, then free it. So any caller attempting to access that bucket knows that it needs to rehash before trying again. So the state of the head wouldn't matter, the sequence would be to lock bucket 5, split or merge it, update the head, free the lock.

If accessing any other bucket, the hash will be valid at all times. Because head is only updated AFTER the split/merge is complete. And the caller knows that when the lock is freed its original hash is invalid and needs to be recalculated.

So while I take your point that the time for a split seems to be constant for you whether you're splitting one bucket or many, you inconvenience everyone while you're splitting. I only inconvenience callers who are trying to access the actual bucket being split.

Cheers,
Wol

Dynamic hash tables

Posted Sep 26, 2014 1:54 UTC (Fri) by dlang (guest, #313) [Link] (8 responses)

If it's a good hash for the task at hand, all the buckets will be very close to equally full, so if you need to split one, you probably need to split all of them.

Also, please think carefully though all the possibilities that can come up when you have multiple threads accessing things at the same time. not just starting from the head, but the fact that you may have them walking and updating the collision chains as well (I haven't tried to go through your explanation in enough detail to check that)

Dynamic hash tables

Posted Sep 26, 2014 10:34 UTC (Fri) by Wol (subscriber, #4433) [Link] (7 responses)

> Note the assumption that all items falling into the same bucket in the old table will also fall into the same bucket in the new table. That is a requirement for this algorithm to work. In practice, it means that the size of a table can only change by an integer factor; normally that means that the size of a table can only be doubled or halved.

Having carefully read the article (I didn't, originally), I now see that relativistic and dynamic hashing are almost exactly the same technique :-)

It's just that the above quoted statement IS WRONG (the "in practice" bit, not the other bit), and dynamic hashing takes advantage of that fact. So the question is, how is the bucket made up, and will dynamic hashing save memory. If, as it appears, each item in the list is individually allocated memory and the items are physically located randomly in memory, then dynamic hashing won't save you anything.

If, however, the bucket consists of blocks of allocated memory, that contain a linked list inside them (as is the setup with Pick, a bucket is a disk block), then you can save a lot of memory by keeping the buckets optimally full.

What I would do here (and it's why dynamic hashing won't save memory if each item is individually allocated) is to overallocate space for the table so I can grow and shrink the table without needing to lock anything. Unless I need to expand it beyond the available space at which point I hit that problem :-)

So shrinking the table is almost exactly the same - link the bucket you're getting rid of on to the end of the bucket it joins, then decrement the variable that says how big the table is.

Growing it, likewise. "Duplicate" the bucket being split into its new position, increment the variable that says how big the table is, then unzip the two buckets. With exactly the same wait periods as before.

So in other words, relativistic and dynamic hashing are almost identical! I just don't think dynamic would gain anything here because it saves on wasted storage when you store multiple items in a single block of allocated space, which doesn't seem to be the case here. The only thing it could save is on the space allocated for the table, which is peanuts in comparison to the entire list.

Thanks for the enlightenment :-)

Cheers,
Wol

Dynamic hash tables

Posted Sep 26, 2014 14:37 UTC (Fri) by perlwolf (guest, #46060) [Link] (6 responses)

What is the point of having an allocated table that is only partly used?

When you shrink that table by merging the last element with its "parent", but keep the same original table, you are occupying the same total amount of storage space, while slowing down access to one of the buckets. There is zero benefit here to offset that occasional slowdown. (Reduced memory usage from shrinking the bucket table size is the *only* benefit of reducing the number of buckets and you throw that away if you keep unused slots in the table.)

Splitting all of the buckets ensures that you split the longest/worst one(s) rather than simply splitting the last one (which might be one of the smallest buckets).

A dynamic split that can split buckets other than the last one have their own cost. The simple hash-index-listsearch becomes hash-index-maybeanotherindex-listsearch which is a small cost (extra code and time to determine whether this is a dynamically split list) that offsets somewhat the shorter list traversals. (Taken to an extreme, you would have a binary tree, with each node being either a tree node that takes the next bit from the has and chooses the appropriate sub-tree or an element node that is either the desired value or the desired value is not in the hash. But at that extreme, it has switched from an O(1) table index to an O(log n) series of tree traversals. That can be balanced by having each tree node use a variable number of hash bits to get back to O(1) behaviour.

Dynamic hash tables

Posted Sep 26, 2014 17:38 UTC (Fri) by Wol (subscriber, #4433) [Link]

> What is the point of having an allocated table that is only partly used?

When the table points to buckets, and space is allocated at the bucket level, not the item level. So having more buckets than you need wastes a LOT of space. Which is cheaper - a few bytes for unused pointers in the table, or many kb for unused space in the buckets?

Each entry in a hash table points to a bucket. A bucket is a linked list of blocks. And a block can contain (in the generic case) any number of items. In this case, a block contains 1 item so there are no savings to be made. But in the Pick case, a block can contain maybe 5 typical items, so the difference between a file with an average 4 items per block or 2 items per block is huge.

Which is why dynamic hashing would make a lot of sense for storing i-nodes in a directory! If doubling the size of the hash table doubles the disk space used by the directory, and each block has space for, say, 10 i-nodes then that's a perfect use-case!

I initially didn't twig that memory was allocated at the item level, and dynamic hashing has been around for absolutely years (probably longer than a lot of people here have been alive!).

So this idea of dynamically splitting a hash table has been around for 40+ years, and in WIDESPREAD commercial use for over 30 of them to my personal knowledge. What's new is the trick of splitting them while they are being actively accessed - Pick databases will lock the bucket while they split it. But they only lock one bucket at a time, and reads only need to outnumber writes by a small amount before the cost of splitting is overwhelmed by the benefits of permanent near-perfect hashing. As your hash file gets bigger, the chances of any individual read tripping over a split/merge operation tends to zero ...

Cheers,
Wol

Dynamic hash tables

Posted Sep 26, 2014 17:53 UTC (Fri) by Wol (subscriber, #4433) [Link] (4 responses)

> A dynamic split that can split buckets other than the last one have their own cost. The simple hash-index-listsearch becomes hash-index-maybeanotherindex-listsearch which is a small cost

True. But the cost is an if, a right-shift, and a mask. Probably faster, actually, than your typical mod(file modulo) operation!

For any given file modulo M, the Pick algorithm is to find N such that
2^(N-1) < M <= 2^N (or have I got my < and <= the wrong way round. Never mind.)
Then
hash = hashfunction( key)
bucket = and( hash, (2^N)-1 )
if bucket >= M then bucket = and( hash, (2^(N-1))-1 )

This is easily optimised by precomputing (2^N)-1, and right-shifting it by one for the second and. It only needs to be recalculated if M hits 2^N or 2^(N-1) on a split or merge.

Cheers,
Wol

Dynamic hash tables

Posted Sep 26, 2014 19:55 UTC (Fri) by perlwolf (guest, #46060) [Link] (3 responses)

The cost is more significant where it is some random buckets that have been split rather than having a clean break between the unsplit and the split buckets. There, you have to take the linked list pointer and add a flag to determine whether it is really pointing to a linked list or if it is actually a link to a split bucket structure. So, the code has a boolean test before traversing the list for an unsplit bucket, or before the logic to process the lower level split in some way, eventually getting down (perhaps) to a linked list to traverse.

Dynamic hash tables

Posted Sep 26, 2014 20:50 UTC (Fri) by Wol (subscriber, #4433) [Link] (2 responses)

> The cost is more significant where it is some random buckets that have been split

Which is exactly what my algorithm does NOT do.

Chances are, my algorithm converts the key to the bucket rather faster than a standard hash algorithm (it uses and(), not mod().). And there's no fancy logic past that - the bucket is the right bucket, first time, EVERY TIME. There's no such thing as a "split bucket" structure.

(And if it hits a linked list, it's a failure mode ... it's intended to identify the right disk block first time every time - a disk miss is *expensive*. It handles it - it has to - but because it's expensive it's not a good idea. The miss rate is typically 5%)

Cheers,
Wol

Dynamic hash tables

Posted Sep 26, 2014 21:17 UTC (Fri) by perlwolf (guest, #46060) [Link] (1 responses)

Ok, you are back to the structure that always splits the last of the large buckets. That is unlikely to be the bucket that has the longest chain, the one most in need of being split, so the split gains no significant benefit. A useful dynamic splitter would split a bucket when it reaches some threshold, but that is unlikely to be conveniently placed as the last large bucket. You either get a fast determination of which buckets have an extra split, or the ability to split the bucket that needs it, but not both.

Dynamic hash tables

Posted Sep 26, 2014 23:27 UTC (Fri) by Wol (subscriber, #4433) [Link]

Yes, but the thing is, it works. Statistically, the split bucket is likely to have a longer-than-average chain. And, on average, at *no* time does *any* bucket have a chain :-) So it's quite possible for me that a "split the largest bucket" would fail because it wouldn't find a "largest" bucket to split!

And in my use case (multiple items per allocation block) it doesn't seem to matter. If the average block is 80% full, I'll find the item I'm looking for in the first block I try 19 times out of 20. That's pretty good ...

It's all a tradeoff. I trade uneven clumping for a simple algorithm and a perfect modulo. I also trade multiple items per allocation block to reduce chains.

You're trading unrestricted access most of the time, and accepting that you have an imperfect modulo and every now and then you're going to get a bit of a hit as the table resizes.

I'm trading the cost of scanning a bucket, and the occasional stall as I hit a locked bucket, for the fact that most of the time I have no chains, and it's damn bad luck if a read hits a bucket that's splitting.

Both trades are appropriate for our use circumstances - a chain causes me an unwanted disk i/o stall, you're not worried about memory usage but need to prevent chains getting too long.

Cheers,
Wol