Browse Prior Art Database

A Method for Implementing a Lock Free Hash Table

IP.com Disclosure Number: IPCOM000205877D
Publication Date: 2011-Apr-06
Document File: 5 page(s) / 66K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for developing a new class of open addressing hashing schemes that would allow efficient resizing of tables and support concurrent operations using lock-free internal data structures.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 39% of the total text.

Page 01 of 5

A Method for Implementing a Lock Free Hash Table

A hash table is a well-known data structure that stores a set of keys or key/value pairs in an array of buckets. Location of a key in the array is computed by a hash function of the key, resulting in almost constant running time for basic operations such as FIND, INSERT, and REMOVE.

The hashing scheme in accordance with the method disclosed herein builds on the idea of cuckoo hashing. With k tables, often of the same size, the cuckoo hashing is an open addressing scheme where k different locations are probed, one from each table, to find a vacancy for a key to be inserted, using k hash functions. Alternatively, k distinct locations can be probed within a single table using a hash function that generates k distinct values. In either case, if all k locations are occupied, a new key displaces one of the k locations anyway, pushing the previous occupant to an alternative location.

Now consider a general setting, assuming that a hash table is stored in linearly addressable memory with an infinite number of slots at the higher end, as shown in Figure 1.

Figure 1

It is assumed that a slot is of the size of a single machine word, so that it can be read and updated atomically. The memory is randomly accessible only within a segment between two markers: a head marker at the lower end pointing to a ?rst accessible slot, and a tail marker at a higher address pointing to a slot next to a last accessible one. The addresses outside of the range are not accessible. The segment can be very large, for example, with millions or billions of available slots. However, for each key, within the accessible segment, only a small number of eligible slots can be used. Therefore, with little probing, a key and its associated data can be retrieved from the hash table. The set of eligible addresses for a key is generated by a hash function. It is assumed that the hash function is well designed, so that the probability of two different keys having exactly the same set of addresses is extremely small.

As in the original cuckoo hashing scheme, a new key is stored in one of its eligible slots, possibly by displacing a chain of existing keys to their alternative locations. For example, in fig. 1, a new key N whose eligible slots (lightly shaded) are all taken has to displace the key A which in turn displaces the key J into a vacant slot. If the memory segment is crowded, the chain of displacement could be long, or even impossible to ?nd. In this case, more memory can be allocated and more slots can be added to an end of the segment.

The entire scheme is not difficult to implement. However, with multiple threads

1

(This page contains 00 pictures or other non-text object)


Page 02 of 5

operating on the same segment without a global lock, the situation becomes much more complicated. Suppose one thread is searching a key by probing its eligible slots, while another is displacing the same key to an alternative slot. Since t...