# US 2021/0342271 A1 · Cache retention for inline deduplication based on number of physical blocks with common fingerprints among multiple cache entries > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2021/0342271 A1 - Document ID: US20210342271A1 - Status: Published application - Kind: A1 - Application number: 16/863,433 - Filed: 2020-04-30 - Published: 2021-11-04 - Earliest claimed: 2020-04-30 - Assignees: EMC IP Holding Company LLC - Applicants: EMC IP Holding Company LLC - Inventors: Sorin Faibish; Philip Shilane; Philippe Armangau - Web page: https://patentgrep.com/patent/US20210342271A1 ## CPC - G06F 12/0868: Data transfer between cache memory and other subsystems, e.g. storage devices or host systems - G06F 12/0891: using clearing, invalidating or resetting means - G06F 3/0608: {Saving storage space on storage systems} - G06F 3/0641: {De-duplication techniques} - G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]} - G06F 12/0864: using pseudo-associative means, e.g. set-associative or hashing - G06F 12/109: for multiple virtual address spaces, e.g. segmentation (G06F12/1036 takes precedence) - G06F 12/128: adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel - G06F 12/0895: of parts of caches, e.g. directory or tag array - G06F 2212/152: Virtualized environment, e.g. logically partitioned system - G06F 2212/214: Solid state disk - G06F 2212/283: Plural cache memories - G06F 2212/312: In storage controller - G06F 2212/401: Compressed data - G06F 2212/466: Metadata, control data - G06F 2212/601: Reconfiguration of cache memory - G06F 2212/651: Multi-level translation tables - G06F 2212/657: Virtual address space management - G06F 2212/7201: Logical to physical mapping or translation of blocks or pages - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Techniques are provided for inline deduplication based on a number of physical blocks having common fingerprints among multiple entries of a buffer cache. One method comprises storing input/output operations in a first cache comprising a plurality of entries each corresponding to a physical storage entity comprising a plurality of physical blocks. A given entry is maintained in the first cache based on a first number of physical blocks of the given entry having a duplicate fingerprint with at least one physical block of another entry in the first cache. A second number is determined of the physical blocks of each entry having a fingerprint in a second cache, and a first ratio is determined for two entries in the first cache using the second number and the first number. A comparison of the first ratios can be performed to sort and possibly evict entries in the first cache based on the comparison. ## Claims ### Claim 1 A method, comprising: storing input/output operations in a first cache associated with a storage system, wherein the first cache comprises a plurality of entries, wherein each entry in the first cache corresponds to a physical storage entity comprising a plurality of physical blocks; and maintaining a given entry in the first cache based at least in part on a first number of physical blocks of the given entry having a substantially duplicate fingerprint, using one or more duplicate fingerprint criteria, with a fingerprint of at least one physical block of another entry in the first cache, wherein the method is performed by at least one processing device comprising a processor coupled to a memory. ### Claim 2 (depends on 1) The method of claim 1, wherein a fingerprint of a given physical block comprises a hash function applied to data associated with the given physical block. ### Claim 3 (depends on 1) The method of claim 1, wherein the maintaining further comprises determining a second number of the physical blocks of each entry in the first cache having a fingerprint in a second cache. ### Claim 4 (depends on 3) The method of claim 3, further comprising determining a first ratio for two entries in the first cache based at least in part on the second number and the first number. ### Claim 5 (depends on 4) The method of claim 4, further comprising sorting the entries in the first cache based at least in part on the first ratios for the entries. ### Claim 6 (depends on 5) The method of claim 5, further comprising evicting one or more entries from the sorted first cache using an eviction policy. ### Claim 7 (depends on 5) The method of claim 5, further comprising determining a similarity function for a given pair of entries based at least in part on a first weight assigned to a first one of the given pair of entries and a second weight assigned to a second one of the given pair of entries, wherein the first weight and the second weight are assigned based at least in part on a comparison of the second number of each of the given pair of entries, wherein the first weight is determined based at least in part on a second ratio of the first ratio of the first one of the given pair of entries and the first ratio of the second one of the given pair of entries. ### Claim 8 (depends on 7) The method of claim 7, further comprising updating the first ratio for a given one of the two entries using a value of the similarity function for one or more of the given pair of entries. ### Claim 9 (depends on 1) The method of claim 1, wherein the storage system comprises a logical address space comprising pointers to entries in a plurality of virtual blocks in a virtual block level of the logical address space, wherein the virtual blocks comprise pointers to entries in a plurality of physical blocks in a physical block level of the logical address space. ### Claim 10 An apparatus comprising: at least one processing device comprising a processor coupled to a memory; the at least one processing device being configured to implement the following steps: storing input/output operations in a first cache associated with a storage system, wherein the first cache comprises a plurality of entries, wherein each entry in the first cache corresponds to a physical storage entity comprising a plurality of physical blocks; and maintaining a given entry in the first cache based at least in part on a first number of physical blocks of the given entry having a substantially duplicate fingerprint, using one or more duplicate fingerprint criteria, with a fingerprint of at least one physical block of another entry in the first cache. ### Claim 11 (depends on 10) The apparatus of claim 10, wherein the maintaining further comprises determining a second number of the physical blocks of each entry in the first cache having a fingerprint in a second cache. ### Claim 12 (depends on 11) The apparatus of claim 11, further comprising determining a first ratio for two entries in the first cache based at least in part on the second number and the first number. ### Claim 13 (depends on 12) The apparatus of claim 12, further comprising sorting the entries in the first cache based at least in part on the first ratios for the entries. ### Claim 14 (depends on 13) The apparatus of claim 13, further comprising evicting one or more entries from the sorted first cache using an eviction policy. ### Claim 15 (depends on 13) The apparatus of claim 13, further comprising determining a similarity function for a given pair of entries based at least in part on a first weight assigned to a first one of the given pair of entries and a second weight assigned to a second one of the given pair of entries, wherein the first weight and the second weight are assigned based at least in part on a comparison of the second number of each of the given pair of entries, wherein the first weight is determined based at least in part on a second ratio of the first ratio of the first one of the given pair of entries and the first ratio of the second one of the given pair of entries; and updating the first ratio for a given one of the two entries using a value of the similarity function for one or more of the given pair of entries. ### Claim 16 A non-transitory processor-readable storage medium having stored therein program code of one or more software programs, wherein the program code when executed by at least one processing device causes the at least one processing device to perform the following steps: storing input/output operations in a first cache associated with a storage system, wherein the first cache comprises a plurality of entries, wherein each entry in the first cache corresponds to a physical storage entity comprising a plurality of physical blocks; and maintaining a given entry in the first cache based at least in part on a first number of physical blocks of the given entry having a substantially duplicate fingerprint, using one or more duplicate fingerprint criteria, with a fingerprint of at least one physical block of another entry in the first cache. ### Claim 17 (depends on 16) The non-transitory processor-readable storage medium of claim 16, wherein the maintaining further comprises determining a second number of the physical blocks of each entry in the first cache having a fingerprint in a second cache. ### Claim 18 (depends on 17) The non-transitory processor-readable storage medium of claim 17, further comprising determining a first ratio for two entries in the first cache based at least in part on the second number and the first number. ### Claim 19 (depends on 18) The non-transitory processor-readable storage medium of claim 18, further comprising sorting the entries in the first cache based at least in part on the first ratios for the entries and evicting one or more entries from the sorted first cache using an eviction policy. ### Claim 20 (depends on 19) The non-transitory processor-readable storage medium of claim 19, further comprising determining a similarity function for a given pair of entries based at least in part on a first weight assigned to a first one of the given pair of entries and a second weight assigned to a second one of the given pair of entries, wherein the first weight and the second weight are assigned based at least in part on a comparison of the second number of each of the given pair of entries, wherein the first weight is determined based at least in part on a second ratio of the first ratio of the first one of the given pair of entries and the first ratio of the second one of the given pair of entries; and updating the first ratio for a given one of the two entries using a value of the similarity function for one or more of the given pair of entries.