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

An object store facilitating contention-free lookup operations by a plurality of threads, the object store comprising a data cache that is managed by a cache manager, and a processor that is configured to implement a method of contention-free lookup by the cache manager, wherein the cache manager:

• maps a key of a cache lookup operation by performing a hash function on the key to determine an expected location, in the data cache, of object data corresponding to a key;
• walks a collision chain of the expected location by determining, with the cache manager, for up to each node of a plurality of nodes of the collision chain, that a cache header signature matches or is different from a collision chain signature of the collision chain, the cache header signature comprising information indicating a state of a cache entry and a state of the object data in the cache entry;
• based on determining that the cache header signature is different from the collision chain signature, again walks the collision chain;
• based on determining that the cache header signature matches the collision chain signature, determines, for up to each of the nodes, that a key in the cache header signature matches or is different from the key of the cache lookup operation;
• based on determining that the key in the cache header signature is different from the key of the cache lookup operation in each of the nodes, reads a cache entry corresponding to the cache lookup operation from a data storage, and repopulates the cache entry into the expected location based on the cache header signature information;
• based on determining that the key in the cache header signature matches the key of the cache lookup operation, acquires an entry lock for holding a lock on a cache entry to protect only contents in the cache entry while a remainder of the collision chain is unlocked, and determines that the key in the cache header signature still matches or no longer matches the key of the cache lookup operation after acquiring the entry lock;
• based on determining that the key in the cache header signature still matches the key of the cache lookup operation after acquiring the entry lock, finds the object data in the expected location;
• and
• based on determining that the key in the cache header signature no longer matches the key of the cache lookup operation after acquiring the entry lock, releases the entry lock, and again walks the collision chain.

A non-transitory computer readable medium implemented on a distributed object store system, the non-transitory computer readable medium having computer code for execution on a processor that implements a method of contention-free lookup by a cache manager of a data cache of the distributed object store system, the method comprising:

• mapping, with the cache manager, a key of a cache lookup operation by performing a hash function on the key to determine an expected location, in the data cache, of object data corresponding to a key;
• walking, by the cache manager, a collision chain of the expected location by determining, with the cache manager, for up to each node of a plurality of nodes of the collision chain, that a cache header signature matches or is different from a collision chain signature of the collision chain, the cache header signature comprising information indicating a state of a cache entry and a state of the object data in the cache entry;
• based on determining that the cache header signature is different from the collision chain signature, again walking, with the cache manager, the collision chain;
• based on determining that the cache header signature matches the collision chain signature, determining, with the cache manager, for up to each of the nodes, that a key in the cache header signature matches or is different from the key of the cache lookup operation;
• based on determining that the key in the cache header signature is different from the key of the cache lookup operation in each of the nodes, reading, with the cache manager, a cache entry corresponding to the cache lookup operation from a data storage, and repopulating, by the cache manager, the cache entry into the expected location based on the cache header signature information;
• based on determining that the key in the cache header signature matches the key of the cache lookup operation, acquiring, by the cache manager, an entry lock for holding a lock on a cache entry to protect only contents in the cache entry while a remainder of the collision chain is unlocked, and determining, by the cache manager, that the key in the cache header signature still matches or no longer matches the key of the cache lookup operation after acquiring the entry lock;
• based on determining that the key in the cache header signature still matches the key of the cache lookup operation after acquiring the entry lock, finding, by the cache manager, the object data in the expected location;
• and
• based on determining that the key in the cache header signature no longer matches the key of the cache lookup operation after acquiring the entry lock, releasing, with the cache manager, the entry lock, and again walking, with the cache manager, the collision chain.