# US 11,308,036 B2 · Selection of digest hash function for different data sets > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,308,036 B2 - Document ID: US11308036B2 - Status: Granted - Kind: B2 - Application number: 16/381,303 - Filed: 2019-04-11 - Published: 2020-10-15 - Granted: 2022-04-19 - Earliest claimed: 2019-04-11 - Assignees: EMC IP Holding Company LLC - Applicants: EMC IP Holding Company LLC - Inventors: Istvan Gonczi; Ivan Bassov; Sorin Faibish - Web page: https://patentgrep.com/patent/US11308036B2 ## CPC - G06F 16/1752: {based on file chunks} - G06F 3/0608: {Saving storage space on storage systems} - G06F 3/0634: {by changing the state or mode of one or more devices} - G06F 3/0683: {Plurality of storage devices} - G06F 16/137: {Hash-based (content-based indexing of textual data G06F16/31)} - G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} - H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC} - H04L 9/3239: {involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD} - G06F 3/0641: {De-duplication techniques} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Techniques for processing data may include: receiving a plurality of data chunks for a data set; performing data deduplication processing for the plurality of data chunks; determining, in accordance with one or more criteria, whether a frequency distribution of a frequency histogram of digest byte frequencies is sufficiently uniform; and responsive to determining that the frequency distribution of the frequency histogram is not sufficiently uniform, performing processing to update data deduplication settings for the data set. Updating the data deduplication settings may include using a stronger hash algorithm and/or a larger size digest when generating subsequent digests. The data deduplication processing may include: determining, using a current hash algorithm, a plurality of digests for the plurality of data chunks of the data set; and updating the frequency histogram of digest byte frequencies for the data set in accordance the plurality of digests. ## Claims ### Claim 1 A method of processing data comprising: receiving a plurality of data chunks for a data set; performing data deduplication processing for the plurality of data chunks, wherein said data deduplication processing includes: determining, using a current hash algorithm, a plurality of digests for the plurality of data chunks of the data set; and updating a frequency histogram for the data set in accordance the plurality of digests, wherein the frequency histogram is a digest byte value histogram that tracks frequencies or counter values of different observed byte values for each individual byte position in digests computed for chunks of the data set, wherein each of the plurality of digests is a current digest size that is a specified number of bytes, wherein said updating includes performing update processing that updates the frequency histogram for each of the plurality of digests and, for each byte located at each byte position of said each digest, performs processing comprising: determining a byte value for said each byte located at said each byte position of said each digest; and incrementing a cell of the frequency histogram denoting a frequency or counter value corresponding to said byte value for said each byte position; determining, in accordance with one or more criteria, whether a frequency distribution of the frequencies or counter values corresponding to the observed byte values for the individual byte positions of the frequency histogram is sufficiently uniform; and responsive to determining that the frequency distribution of the frequencies or counter values corresponding to the observed byte values for the individual byte positions of the frequency histogram is not sufficiently uniform, performing processing to update data deduplication settings for the data set. ### Claim 2 (depends on 1) The method of claim 1, wherein the data deduplication settings include the current hash algorithm and the current digest size. ### Claim 3 (depends on 2) The method of claim 2, wherein the processing to update the data deduplication settings for the data set includes modifying any of the current hash algorithm and the current digest size. ### Claim 4 (depends on 3) The method of claim 3, wherein modifying the current hash algorithm includes selecting a new hash algorithm to be used in connection with generating digests for data deduplication processing performed for subsequent data chunks of the data set. ### Claim 5 (depends on 4) The method of claim 4, wherein the new hash algorithm is a stronger hash algorithm than the current hash algorithm and the new hash algorithm is expected to generate a second distribution of frequencies with respect to byte values for bytes of generated digests whereby the second distribution of frequencies is expected to be more uniform than the frequency distribution of the frequency histogram generated using the current hash algorithm. ### Claim 6 (depends on 5) The method of claim 5, wherein the current hash algorithm is a non-cryptographic hash algorithm that is replaced with the new hash algorithm that is a cryptographic hash algorithm. ### Claim 7 (depends on 3) The method of claim 3, wherein modifying the current digest size includes selecting a new digest size to be used in connection with generating digests for data deduplication processing performed for subsequent data chunks of the data set. ### Claim 8 (depends on 1) The method of claim 1, wherein the frequency histogram has a plurality of dimensions including a first dimension denoting the specified number of bytes. ### Claim 9 (depends on 8) The method of claim 8, wherein the plurality of dimensions of the frequency histogram further includes a second dimension denoting a number of allowable byte values for each byte of a digest having the current digest size. ### Claim 10 (depends on 9) The method of claim 9, wherein the plurality of dimensions of the frequency histogram further includes a third dimension of counter values or frequencies for each different allowable byte value of each byte for a digest having the current digest size. ### Claim 11 (depends on 1) The method of claim 1, wherein the one or more criteria indicates that, for the frequency distribution to be sufficiently uniform, at least one statistical metric for the frequency distribution is less than a specified maximum threshold. ### Claim 12 (depends on 11) The method of claim 11, wherein the at least one statistical metric includes any of variance and standard deviation. ### Claim 13 (depends on 1) The method of claim 1, wherein the data set includes any of a logical device, a database, one or more selected portions of a database, data used by a particular application stored on one or more logical devices, selected portions of one or more logical devices, one or more files, one or more directories, one or more file systems, particular portions of one or more directories, and particular portions of one or more file systems. ### Claim 14 (depends on 1) The method of claim 1, wherein the method is performed as part of inline processing of the plurality of data chunks in connection with an I/O path or data path when servicing I/Os accessing the plurality of data chunks. ### Claim 15 (depends on 1) The method of claim 1, wherein the method is performed offline and not as part of inline processing of the plurality of data chunks in connection with an I/O path or data path when servicing I/Os accessing the plurality of data chunks. ### Claim 16 (depends on 1) The method of claim 1, further comprising: determining, in accordance with the one or more criteria, whether the frequency distribution of the frequency histogram has maintained a specified level of uniformity for a specified time period; and responsive to determining the frequency distribution of the frequency histogram has maintained a specified level of uniformity for a specified time period, performing first processing to update the data deduplication settings for the data set, wherein said first processing includes performing any of: updating the current hash algorithm to a new hash algorithm that is computationally less intensive that the current hash algorithm whereby the new hash algorithm is expected to take less processor time than the current hash algorithm to generate a same digest; and reducing a current digest size of digests generated using the current hash algorithm. ### Claim 17 (depends on 1) The method of claim 1, wherein said determining whether the frequency distribution of the frequencies or counter values corresponding to the observed byte values for the individual byte positions of the frequency histogram is sufficiently uniform includes determining whether the frequencies or counter values of the frequency histogram approximate an even or uniform distribution within a specified tolerance, threshold or limit. ### Claim 18 (depends on 17) The method of claim 17, wherein said determining whether the frequencies or counter values of the frequency histogram approximate an even or uniform distribution within a specified tolerance, threshold or limit includes determining whether all the frequencies or counter values of the frequency histogram vary by more than a specified number of one or more standard deviations from a mean of all the frequencies or counter values of the frequency histogram. ### Claim 19 A system comprising: at least one processor; and a memory comprising code stored thereon that, when executed, perform a method of processing data comprising: receiving a plurality of data chunks for a data set; performing data deduplication processing for the plurality of data chunks, wherein said data deduplication processing includes: determining, using a current hash algorithm, a plurality of digests for the plurality of data chunks of the data set; and updating a frequency histogram for the data set in accordance the plurality of digests, wherein the frequency histogram is a digest byte value histogram that tracks frequencies or counter values of different observed byte values for each individual byte position in digests computed for chunks of the data set, wherein each of the plurality of digests is a current digest size that is a specified number of bytes, wherein said updating includes performing update processing that updates the frequency histogram for each of the plurality of digests and, for each byte located at each byte position of said each digest, performs processing comprising: determining a byte value for said each byte located at said each byte position of said each digest; and incrementing a cell of the frequency histogram denoting a frequency or counter value corresponding to said byte value for said each byte position; determining, in accordance with one or more criteria, whether a frequency distribution of the frequencies or counter values corresponding to the observed byte values for the individual byte positions of the frequency histogram is sufficiently uniform; and responsive to determining that the frequency distribution of the frequencies or counter values corresponding to the observed byte values for the individual byte positions of the frequency histogram is not sufficiently uniform, performing processing to update data deduplication settings for the data set. ### Claim 20 A non-transitory computer readable medium comprising code stored thereon that, when executed, performs a method of processing data comprising: receiving a plurality of data chunks for a data set; performing data deduplication processing for the plurality of data chunks, wherein said data deduplication processing includes: determining, using a current hash algorithm, a plurality of digests for the plurality of data chunks of the data set; and updating a frequency histogram for the data set in accordance the plurality of digests, wherein the frequency histogram is a digest byte value histogram that tracks frequencies or counter values of different observed byte values for each individual byte position in digests computed for chunks of the data set, wherein each of the plurality of digests is a current digest size that is a specified number of bytes, wherein said updating includes performing update processing that updates the frequency histogram for each of the plurality of digests and, for each byte located at each byte position of said each digest, performs processing comprising: determining a byte value for said each byte located at said each byte position of said each digest; and incrementing a cell of the frequency histogram denoting a frequency or counter value corresponding to said byte value for said each byte position; determining, in accordance with one or more criteria, whether a frequency distribution of the frequencies or counter values corresponding to the observed byte values for the individual byte positions of the frequency histogram is sufficiently uniform; and responsive to determining that the frequency distribution of the frequencies or counter values corresponding to the observed byte values for the individual byte positions of the frequency histogram is not sufficiently uniform, performing processing to update data deduplication settings for the data set. ### Claim 21 (depends on 20) The non-transitory computer readable medium of claim 20, wherein the data deduplication settings includes the current hash algorithm and the current digest size. ### Claim 22 (depends on 21) The non-transitory computer readable medium of claim 21, wherein the processing to update the data deduplication settings for the data set includes modifying any of the current hash algorithm and the current digest size.