I also thought of the deadlock issue. It is not difficult to deal with, as you have pointed out the solution, which is called "pessimistic locking strategy" in database system. It safe and a little slow, but should be faster than the global lock. In fact, I don't think the speed of expanding is very important. I think the global lock is a little dangerous, as I have explained in issue 370 and reproduced at .20 in pull #73(maybe you still have no glance at it), and i also think it is difficult to understand(I am so awkward that have to spend a lot of time to understand how and why the global lock works). I think it is another option to solve the issue 370, and make the code more clear~
On Monday, August 11, 2014 12:38:43 PM UTC+8, Dormando wrote: > > > > > 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.
