Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-12-31
2002-03-19
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06360220
ABSTRACT:
TECHNICAL FIELD
The present invention relates to methods and systems for accessing and storing information in an indexed computer data structure. More particularly, the present invention relates to lock-free methods and systems for accessing and storing information in an indexed computer data structure having modifiable entries.
BACKGROUND OF THE INVENTION
In computer programs, such as cache memory management systems, it is desirable to decrease the retrieval time of frequently accessed information. In order to decrease the retrieval time of frequently accessed information, cache memory systems may store the frequently accessed information in an indexed data structure, such as a hash table. As used herein, the phrase “indexed computer data structure” or “indexed data structure” refers to a set of elements referred to as entries, wherein each and every entry is uniquely selectable based on a selection function that produces an index. A hash table is an indexed data structure that may be stored in computer memory to reduce the number of comparisons required to locate and retrieve information. For example, a hash table may comprise an array of records or entries containing the information desired to be located. Each entry may also contain a key used by processes or threads performing lookup or search algorithms to locate the entry. A key is a unit of data that is compared with a search key to determine whether an entry contains the data of interest. A hash table reduces the number of keys that must be compared to locate a given entry using a hash function. A hash function is a mathematical algorithm that receives a key as an input and ideally computes a unique index as an output. For example, the hash function may always produce the same index for a given key. However, different keys may result in the same index, if the hash function is not perfect. If the hash table is stored in an array, the index may represent an offset from the table base address and a potential location for the entry containing a key that matches the search key. Thus, for a given entry e in the table with key k, INDEX=hash(k). If the table including the entry e is an array, e and the key k may be stored at array[INDEX].
Because hashing different keys may result in the same index, an entry may not be located at the index corresponding to the hash of the key for the entry. For example, when different keys hash to the same index, the first key may be stored at the location corresponding to hash(key). The second key may be stored at another location, e.g., a location corresponding to hash(key)+1. Thus, even though hashing reduces the number of comparisons required to locate an entry, more than one comparison may be required. For example, in order to locate an entry in a hash table, a thread may first hash a search key to determine an initial index. The thread then locates the entry corresponding to the index and compares the key in the entry with the search key. If the keys match, the thread may extract the desired information or a pointer to the desired information from the entry. If the keys do not match, the thread may search the remaining entries in the table to locate a matching key. In certain cases the hash table may be constructed or used in such a way as to eliminate the potential for duplicate hash results, i.e., as in the case of perfect hash functions. In such a case, only a single comparison may be required to locate an entry because each entry is stored exactly at the location corresponding to the hash of the key value for the entry.
If the hash table is stored in a fast memory device and used to cache data stored in another slower memory device, when a thread fails to locate an entry having a matching key in the hash table, the thread may extract the data from the slower memory device and attempt to insert the data into the hash table. Inserting the data in the hash table may include attempting to store the data at the location corresponding to the hash of the search key. If the entry at that location is uninitialized, i.e., if it has not been previously used to store information, the thread may insert the data in the entry. If the entry has been initialized, the thread may search for an empty entry in the table to store the new data. If the table is full, the thread may replace an existing entry with the new data. Once the new data is stored in the hash table, subsequent searches of the hash table for the entry will succeed, unless another process removes the new entry.
A problem with conventional methods for accessing and storing data in hash tables and other data structures used in cache memory systems is that these methods may require locking when multiple threads or multiple processes access a data structure to ensure the validity of information retrieved during a search. For example, in one conventional cache memory system, when a first thread accesses a cache, for example to perform a lookup operation, the first thread locks the cache, preventing other threads from performing any cache operations. When the first thread completes the search operation, the first thread unlocks the cache, allowing other threads to access the cache. Allowing a single thread to block all other attempted accesses to a cache is undesirable because the first thread may block during its access to the cache and prevent other threads from accessing the cache indefinitely. Even if the first thread does not fail or block, the remaining threads are delayed for at least the time for the first thread to lock the cache, perform the lookup operation, and unlock the cache. These operations introduce latency into cache accesses by the other threads. Thus, allowing a single thread to lock the entire cache may be undesirable in high-speed computer memory systems whenever there is likely to be contention among multiple threads for accesses to the cache.
In another conventional memory system, rather than locking an entire cache, a thread may lock each individual cache entry when the thread accesses the entry and unlock the entry when the thread completes the access to the entry. For example, in a lookup operation, a thread may search through entries or records in a table. In order to access each entry, the thread locks the entry, reads the information in the entry, determines whether the information matches the search key, and unlocks the entry. This process is repeated for each entry in the table until a match is found. Other threads may be prevented from accessing the entry due to the lock. Because the first thread locks, reads, compares, and unlocks each entry before another thread can access the entry, latency may be introduced into cache operations performed by other threads. In addition, locking and unlocking each entry during a search may introduce latency into memory operations performed by the first thread. Thus, a cache memory system that requires locking and unlocking of entries by each thread may be unsuitable for high-speed operations.
SUMMARY OF THE INVENTION
As described above, the phrase “indexed computer data structure” refers to a set of elements referred to as entries, wherein each entry is uniquely selectable utilizing a selection function that produces an index. The selection function may comprise any mathematical function that maps data from a first domain into a second domain, wherein the second domain is a set of indices capable of selecting all of the entries. Exemplary indexed computer data structures to which the lock-free methods and systems according to the present invention may apply include hash tables and linked lists. A hash table may be indexed using a perfect or an imperfect hash function. The lock-free methods and systems for accessing an indexed computer data structure are applicable to hash tables accessible by both perfect and imperfect hash functions. A linked list may be indexed by computing an index to a first entry in the list and following pointers to locate the data of interest. The lock free methods and systems for accessing an indexed computer data structure acc
Black Thomas
Leydig , Voit & Mayer, Ltd.
Microsoft Corporation
Wang Mary
LandOfFree
Lock-free methods and systems for accessing and storing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Lock-free methods and systems for accessing and storing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lock-free methods and systems for accessing and storing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2889272