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