US Patent 9274956 Intelligent cache eviction at storage gateways

Methods and apparatus for intelligent cache eviction at storage gateways are disclosed. A system comprises computing devices configured to determine whether the number of free chunks of storage at a storage appliance for caching portions of a storage object is below a threshold value. If the number is below the threshold, the computing devices identify an eviction set of chunks to be freed, and generate a respective new instance identifier for each chunk of the eviction set. The identifier of a given chunk may be used to determine a validity of a block of the chunk. The devices store, within metadata storage of the appliance, the new instance identifiers of the eviction set, and indicate that the chunks of the eviction set are available for caching data of the storage object.