Mechanisms for a contention free lookup in a cache with concurrent insertions and deletions

Abstract

A method of contention-free lookup including mapping a key of a cache lookup operation to determine an expected location of object data, walking a collision chain by determining whether a cache header signature matches a collision chain signature, when the cache header signature does not match, again walking the collision chain, when the cache header signature matches, determining whether a key in the cache header signature matches the key of the cache lookup operation, when the key does not match, reading a cache entry corresponding to the cache lookup operation, and repopulating the cache entry, when the key matches, acquiring an entry lock, and determining whether the key still matches after acquiring the entry lock, when the key still matches finding the object data in the expected location, and when the key no longer matches, releasing the entry lock, and again walking the collision chain.