> > I think we can expanding hash table without a "global lock", and i am going > to explain why(I hope my English is good enough to make it clearly :) ). > > As the current hash expanding algorithm doing, now it is going to expand > the power of hashtable from hashpower to hashpower+1, and moving > old_bucket[0]~old_bucket[2**hashpower-1] to > new_bucket[0]~new_bucket[2**(hashpower+1)-1]. (2**x is pow(2,x)). > > All the items in old_bucket[i] will only have two destination in > new_bucket. Because the old bucket-id i = hash(key) & hashmask(hashpower), > and the bucket-id in new_bucket is new_i = hash(key) & hashmask(hashpower+1). > It means adding a highest bit to the i, so new_i = i + (0 or > 1)*(2**hashpower), so new_i = i or new_i = i + 2**hashpower. > > For every bucket in the hash table that is going to expand, we just have to > get two locks: item_locks[(i) % item_lock_count] and item_locks[(i + > 2**hashpower) % item_lock_count]. It seems no need a "global lock". > > Tell me if I make some mistake, and any suggestion is appreciated. > > reference: > http://en.wikipedia.org/wiki/Linear_hashing > http://en.wikipedia.org/wiki/Extendible_hashing >
Normally this wouldn't work because of deadlocks; you can't guarantee that two threads won't grab each other's locks? If thread A tries to grab locks 1 and 2 Then thread B tries to grab locks 2 and 1 (Because the whole calculation is a modulus against item_lock_count), they can deadlock. The same deadlock exists even if the item locks and the hash buckets both expanded at the same time, and are the same size. Since two different keys can, at hashpower 20, occupy different buckets, then at hashpower 21, occupy the same bucket. They'd still deadlock. Since as of a few verisons ago item_locks uses item_lock_count instead of (stupidly, sorry) hashpower, you could maybe change the logic while under expansion to do trylock() instead of lock(). Sleep for random nanoseconds then try again if you fail to acquire the second lock? That would make the "unlikely" case of a collision resolve itself with a little slowdown, perhaps. However hash table expansion happens pretty quickly and people with sensitive loads should still use the presize argument. It'd be nice to be rid of the global lock dance but I've definitely been putting it off in favor of work that's easier to reason with :) So, yeah. maybe something like that. -- --- You received this message because you are subscribed to the Google Groups "memcached" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
