US Patent 10275363 Cuckoo caching

A cuckoo cache has plural buckets of plural cells each. The cells within a bucket are ranked to approximate relative usage recency. New items can be inserted into empty cells; when a bucket is full, room for a new item can be made by laterally transferring an older item to an alternative bucket. When empty cells and lateral transfers are unavailable, an item is selected for eviction based on the usage recency rank of the containing cell. When a match is found, depending on the embodiment, the hit item can be promoted within its bucket, to its alternative bucket, or to a separate tier of the cuckoo cache. The items can be key-value pairs. No metadata is required to track usage recency so that the cuckoo cache can be a very space efficient tool for finding cached values by their keys.