Cuckoo caching
US10877902B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 11, 2019 |
| Grant date | Dec 29, 2020 |
| Priority date | — |
| Expiry date | Apr 11, 2039 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2212/1024
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.