Scalable, concurrent resizing of hash tables

摘要

A system, method and computer program product for resizing a hash table while supporting hash table scalability and concurrency. The hash table has one or more hash buckets each containing one or more items that are chained together in a linked list. Each item in the hash table is processed to determine if the item requires relocation from a first bucket associated with a first table size to second bucket associated with a second table size. If the item requires relocation, it is linked to the second bucket without moving or copying the item in memory. The item is unlinked from the first bucket after waiting until there is no current hash table reader whose search of the hash table could be affected by the unlinking, again without moving or copying the item in memory.

主权项

1. In a system having one or more processors, a memory operatively coupled to said one or more processors, and a hash table in said memory having hash buckets each containing items that are chained together in a linked list, a method for resizing said hash table, comprising:
processing each item in said hash table to determine if said item requires logical relocation from a first bucket associated with a first table size that exists at commencement of resizing to a second bucket associated with a second table size that will exist at completion of resizing; if said item requires logical relocation, linking said item to said second bucket without moving or copying said item in memory; waiting until there are no current hash table readers whose search of said hash table could be affected by unlinking said item from said first bucket; and unlinking said item from said first bucket without moving or copying said item in memory.