1. A computer-implemented method, the method comprising: maintaining a metadata set for each cache unit of a cache device, wherein the cache device comprises a plurality of cache units, each cache unit having a plurality of segments, wherein each metadata set includes deletion hints (DH) metadata indicating whether each of the plurality of segments of a corresponding cache unit is valid or deprecated, wherein each of the plurality of segments can chance from being valid to being deprecated, wherein each deprecated segment can change back to being valid; in response to determining that a cache eviction is to be performed: selecting a predetermined number of cache units from the plurality of cache units, and determining a score for each of the selected cache units based on the DH metadata of the respective metadata set; and evicting one or more of the selected predetermined number of cache units based on their respective scores.