CN117813591A

CN117813591A - Deduplication of strong and weak hashes using cache evictions

Info

Publication number: CN117813591A
Application number: CN202180101408.6A
Authority: CN
Inventors: 阿萨夫·纳塔逊; 阿维夫·库温特
Original assignee: Huawei Technologies Co Ltd
Current assignee: Huawei Technologies Co Ltd
Priority date: 2021-09-14
Filing date: 2021-09-14
Publication date: 2024-04-02
Also published as: WO2023041141A1

Abstract

The data management method in the computer-implemented data storage system includes: dividing each data item into a plurality of blocks; compute Jiang Haxi and weak hash; an ID table and a weak hash table are generated. In response to receiving the incoming data item, the method further comprises: dividing an incoming data item into a plurality of blocks; compute Jiang Haxi and weak hash; selecting one or more representative weak hashes; searching a representative weak hash in a weak hash table; a match between one or more of the representative weak hashes and a weak hash in the weak hash table is recorded. The weak hash table includes a cache portion and the cache eviction algorithm is configured to determine whether to reserve or evict each weak hash in the cache portion based on a number of matches for the weak hash records. Thus, the number of accesses to the disk is reduced.

Description

Deduplication of strong and weak hashes using cache evictions

Technical Field

The present disclosure relates generally to the field of data deduplication, and more particularly, to a method of data management in a data storage system, and a data processing apparatus for a data storage system.

Background

In general, data backup operations are used to create a backup of data at a target site in order to protect and restore the data in the event of a data loss at a source site. Examples of data loss events may include, but are not limited to, data corruption, hardware or software failures in the source site, accidental deletion of data, hacking, or malicious attacks. Thus, for security reasons, separate backup stores are widely used to store backups of data present in source sites. However, repeated copies of data shared or stored across a network in a data storage system may unnecessarily increase the storage capacity requirements of the data storage system. In general, it is desirable to use a data deduplication scheme to detect and eliminate duplicate copies of data, thereby significantly reducing storage capacity requirements.

Traditionally, one of the typical processes of a traditional data deduplication scheme is to receive a new write request, segment the data using any segmentation algorithm, calculate a strong hash and a weak hash for each segment, and search Jiang Haxi in a given strong hash cache. If Jiang Haxi is found in a given strong hash cache, a block Identification (ID) is returned. If Jiang Haxi is not found in the given strong hash cache, the weak hash table is searched for. If a weak hash is found in a given weak hash table, the strong hash is retrieved from the given ID table for comparison. If a weak hash is not found in a given weak hash table, the data cannot be deduplicated and a new chunk ID is generated. However, since the given weak hash table is large and the given weak hash table is mostly stored on disk, searching requires reading IOs from disk. Thus, there is a large impact on both latency and read IO throughput. Furthermore, in some scenarios, conventional data deduplication schemes may use separate memory (not part of a given weak hash table) to find a large number of candidates retrieved from the given weak hash table. However, the use of separate memory increases the storage capacity requirements of the data storage system, which is undesirable. In addition, some conventional data deduplication schemes trade off several performance aspects, while degrading performance for other application scenarios. For example, a conventional data deduplication scheme may be optimized for online deduplication scenarios, which provides high throughput, but with relatively high latency. Thus, such conventional data deduplication schemes are not preferred for source-based deduplication scenarios, where very low latency is required. Thus, under a variety of application scenarios (e.g., source-based deduplication and generic online deduplication), there are technical issues with inefficient and ineffective data deduplication schemes that exhibit low performance.

Thus, in light of the above discussion, there is a need to overcome the above-described drawbacks associated with conventional data deduplication schemes.

Disclosure of Invention

The present disclosure provides a data management method in a data storage system, and a data processing apparatus for the data storage system. The present disclosure provides a solution to existing inefficiency and unreliability problems associated with conventional data deduplication schemes, which are complicated by the fact that existing schemes compromise performance in terms of latency, throughput, access rate, and hit rate, for example, under a variety of application scenarios (e.g., source-based deduplication and general online deduplication). It is an object of the present disclosure to provide a solution that at least partially overcomes the problems encountered in the prior art and to provide an improved data deduplication solution that can efficiently utilize the cache eviction process, which exhibits high performance in terms of low latency, high throughput, low access rate, and high hit rate compared to existing systems.

One or more of the objects of the present disclosure are achieved by the solutions provided in the attached independent claims. Advantageous implementations of the present disclosure are further defined in the dependent claims.

In one aspect, the present disclosure provides a method of data management in a computer-implemented data storage system. The method comprises the following steps: dividing each data item in the data storage system into a plurality of blocks; computing a strong hash for each block and generating an ID table comprising a list of Jiang Haxi with pointers to the locations of the corresponding blocks; a weak hash is computed for each strong hash and a weak hash table is generated that includes a list of weak hashes with pointers to locations of the corresponding strong hashes in the ID table. In response to receiving the incoming data item, the method further comprises: dividing the incoming data item in the data storage system into a plurality of blocks; calculating strong hash and weak hash of each block; selecting one or more representative weak hashes for the incoming data item; searching a representative weak hash in a weak hash table; recording a match between one or more of the representative weak hashes and a weak hash in the weak hash table; wherein the weak hash table includes a cache portion and the cache eviction algorithm is configured to determine whether to reserve or evict each weak hash in the cache portion based on a number of matches for the weak hash records.

The method of the present disclosure provides an improved data deduplication scheme by efficiently managing data stored in a data storage system. By the cache portion, the number of disk read accesses is reduced, thus minimizing access rate and latency for IO operations to acquire the data storage system. Furthermore, the methods of the present disclosure can be efficiently used for a variety of scenarios (e.g., source-based deduplication and generic online deduplication), and without degrading and compromising performance (i.e., latency, throughput, access rate, and hit rate) for any scenario. Furthermore, the method allows for an efficient and reliable data deduplication scheme to manage duplicate data and non-duplicate data. The non-duplicate data is stored as new data items in the data storage system. On the other hand, duplicate data is not explicitly stored in the data storage system; instead, the corresponding weak hash is retained in the cache portion based on the number of matches for the weak hash record. Thus, the methods of the present disclosure allow for efficient use of the storage capacity of a data storage system.

In one implementation, selecting the representative weak hash includes selecting a predetermined number of lowest value weak hashes.

Advantageously, the method of selecting a representative weak hash is easy and deterministic in that the same maximum weak hash value or values are selected as representative weak hashes each time for a given maximum weak hash value or values.

In another implementation, selecting the representative weak hash includes selecting one or more weak hashes for which a predetermined number of most significant bits are equal to zero.

Advantageously, the weak hash with the same most significant bit (most significant bit, MSB) is located closely in the cache portion within the weak hash table. Thus, the cache eviction algorithm is able to cache the complete page of the strong hash, which in turn makes searching in the weak hash table more efficient.

In another implementation, the predetermined number is dynamically selected based on a hit rate of the data storage system and an amount of data in the cache portion.

Advantageously, the cache eviction (using a cache eviction algorithm) ensures that a weak hash of an incoming data item searched against a weak hash table of the data storage system is present in the cache portion. Thus, the number of accesses to acquire IO operations from disk is reduced, thus minimizing latency in the data storage system.

In another implementation, in response to a match in the weak hash table, the method further comprises: the associated strong hash is found from the ID table and checked against one or more of the strong Ha Xizhong calculated for the incoming data item.

By checking the associated strong hash against one or more of the strong Ha Xizhong calculated for the incoming data item, the cache eviction algorithm caches the complete page of the strong hash, which allows the search in the weak hash table to be more efficient. Thus, throughput and hit rate of the data storage system are improved.

In another implementation, the method further comprises: the associated strong hash and one or more neighboring strong hashes are loaded into a strong hash cache, wherein the one or more strong hash values calculated for the new incoming data item are checked against a Jiang Haxi cache prior to searching the weak hash table.

By associating the strong hash with one or more neighboring strong hashes in the strong hash cache, the strong hash that saves access to the weak hash table due to multiple hits in the strong hash cache remains in the cache portion of the weak hash table for a longer time.

In another implementation, if there is no match in the weak hash table, the incoming data item is written to the data storage system as a new data item.

Advantageously, the incoming data item is identified as a non-duplicate data item and stored as a new data item in the data storage system.

In another implementation, the cache eviction algorithm is configured to assign a higher priority to preserve a weak hash for which a match of records corresponds to data items received as part of the backup task.

Advantageously, the number of accesses to IO operations from disk is reduced, thus minimizing latency in backup tasks.

In another implementation, the incoming data item is received as part of a backup task.

Advantageously, no additional hardware is required to perform deduplication (e.g., source-based deduplication), and bandwidth and storage capacity requirements are reduced.

In another implementation, the method further comprises: receiving a second incoming data item that is not part of the backup task; dividing a second incoming data item in the data storage system into a plurality of blocks; calculating strong hash and weak hash of each block; searching each weak hash in the weak hash table; recording a match between one or more of the weak hashes and a weak hash in the weak hash table; wherein the cache eviction algorithm is configured to assign a lower priority to preserve a weak hash for which a match of records corresponds to a second data item not received as part of the backup task.

With the second incoming data item, incoming write requests (not part of the backup task) can be efficiently stored in the data storage system.

In another aspect, the present disclosure provides a computer-readable medium configured to store instructions that, when executed by a processor, cause the processor to perform the method of the above aspect.

The computer readable medium realizes all the advantages and effects of the corresponding method of the present disclosure.

In yet another aspect, the present disclosure provides a data processing apparatus for a data storage system. The data processing device comprises a data indexing module, a data query module and a cache eviction module. The data indexing module is configured to: dividing each data item in the data storage system into a plurality of blocks; computing a strong hash for each block and generating an ID table comprising a list of Jiang Haxi with pointers to the locations of the corresponding blocks; a weak hash is computed for each strong hash and a weak hash table is generated that includes a list of weak hashes with pointers to locations of the corresponding strong hashes in the ID table. The data query module is configured to receive an incoming data item, and in response to receiving the incoming data item: dividing an incoming data item in a data storage system into a plurality of blocks; calculating strong hash and weak hash of each block; selecting one or more representative weak hashes for the incoming data items; searching a representative weak hash in a weak hash table; a match between one or more of the representative weak hashes and a weak hash in the weak hash table is recorded. A cache eviction module, wherein the weak hash table includes a cache portion, and the cache eviction module is configured to determine whether to reserve or evict each weak hash in the cache portion based on a number of matches for the weak hash records.

The data processing apparatus of the present disclosure performs the method of the above aspect by efficiently indexing weak hashes in the cache portion of the weak hash table. In addition, the data processing apparatus provides an efficient, reliable data deduplication scheme that manages duplicate data and non-duplicate data. The non-duplicate data is stored as new data items in the data storage system. On the other hand, duplicate data is not explicitly stored in the data storage system; instead, the corresponding weak hash is retained in the cache portion based on the number of matches for the weak hash record. Thus, the data processing apparatus contributes to an efficient use of the storage capacity of the data storage system.

Advantageously, selecting a representative weak hash becomes easy and deterministic because the same maximum weak hash value or values are selected as representative weak hashes each time for a given maximum weak hash value or values.

Advantageously, the weak hash with the same most significant bit (most significant bit, MSB) is located closely in the cache portion within the weak hash table. Thus, the cache eviction module caches the complete page of the strong hash, which allows the search in the weak hash table to be more efficient.

Advantageously, the data querying module ensures that a weak hash of an incoming data item searched against a weak hash table of the data storage system exists in the cache portion. Thus, the number of accesses to acquire IO operations from disk is reduced, thereby minimizing latency in the data storage system.

In another implementation, in response to a match in the weak hash table, the data query module is further configured to: the associated strong hash is found from the ID table and checked against one or more of the strong Ha Xizhong calculated for the incoming data item.

By checking the associated strong hash against one or more of the strong Ha Xizhong calculated for the incoming data item, the cache eviction module is able to cache the complete page of the strong hash, which allows the search in the weak hash table to be more efficient. Thus, throughput and hit rate of the data storage system are improved.

In another implementation, the data query module is further configured to load the associated strong hash and one or more neighboring strong hashes into a strong hash cache, wherein the one or more strong hash values calculated for the new incoming data item are checked against the Jiang Haxi cache before searching the weak hash table.

In another implementation, the cache retirement module is configured to assign a higher priority to preserve a weak hash for which a match of records corresponds to data items received as part of the backup task.

In another implementation, the incoming data is received as part of a backup task.

In another implementation, the data query module is further configured to: receiving a second incoming data item that is not part of the backup task; dividing a second incoming data item in the data storage system into a plurality of blocks; calculating strong hash and weak hash of each block; searching each weak hash in the weak hash table; recording a match between one or more of the weak hashes and a weak hash in the weak hash table; wherein the cache eviction module is configured to assign a lower priority to preserve a weak hash for which a match of records corresponds to a second data item not received as part of the backup task.

It must be noted that all the devices, elements, circuits, units and means described in the present application may be implemented in software or hardware elements or any type of combination thereof. All steps performed by the various entities described in this application, as well as functions described to be performed by the various entities, are intended to indicate that the respective entity is adapted or configured to perform the respective steps and functions. Although in the following description of specific embodiments, specific functions or steps to be performed by external entities are not reflected in the description of specific detailed elements of the entity performing the specific steps or functions, it should be clear to a skilled person that these methods and functions may be implemented in corresponding software or hardware elements or any combination thereof. It should be understood that features of the present disclosure are susceptible to being combined in various combinations without departing from the scope of the present disclosure as defined by the appended claims.

Additional aspects, advantages, features and objects of the present disclosure will become apparent from the accompanying drawings and detailed description of illustrative implementations explained in conjunction with the appended claims.

Drawings

The foregoing summary, as well as the following detailed description of illustrative embodiments, is better understood when read in conjunction with the appended drawings. For the purpose of illustrating the disclosure, there is shown in the drawings exemplary constructions of the disclosure. However, the present disclosure is not limited to the specific methods and instrumentalities disclosed herein. Moreover, those skilled in the art will appreciate that the drawings are not drawn to scale. Wherever possible, like elements are designated by like numerals.

Embodiments of the present disclosure will now be described, by way of example only, with reference to the following drawings, in which:

FIGS. 1A and 1B together are a flow chart of a method of data management in a data storage system according to an embodiment of the present disclosure;

FIG. 2 is a block diagram of a data storage system according to an embodiment of the present disclosure; and is also provided with

Fig. 3 is a diagram illustrating various operations of a data deduplication scheme in accordance with an embodiment of the present disclosure.

In the drawings, the underlined numbers are used to denote items where the underlined numbers are located or items adjacent to the underlined numbers. The non-underlined numbers relate to items identified by lines associating the non-underlined numbers with the items. When a number is not underlined and has an associated arrow, the number without the underline is used to identify the general item to which the arrow points.

Detailed Description

The following detailed description describes embodiments of the present disclosure and the manner in which the embodiments may be implemented. While some modes of carrying out the disclosure have been disclosed, those skilled in the art will recognize that other embodiments for carrying out or practicing the disclosure may also exist.

Fig. 1A and 1B together are a flow chart of a method of data management in a data storage system according to an embodiment of the present disclosure. Referring to fig. 1A and 1B, a method 100 is shown. The method 100 is performed by a data processing apparatus such as that described in detail in fig. 2. The method 100 includes steps 102-116.

At step 102, the method 100 includes dividing each data item in the data storage system into a plurality of blocks. The amount of data items (i.e., data files, database files, IO writes, etc.) stored in a data storage system can be enormous. To efficiently manage such huge amounts of data, each data item in a data storage system is broken down into multiple blocks. The process of partitioning, i.e. splitting a large data item into small data items called blocks, is also called partitioning of the data. The plurality of blocks may also be referred to as data segments. Furthermore, dividing each data item into a plurality of blocks may result in fixed length blocks (i.e., equal sized blocks) or variable length blocks (i.e., unequal sized blocks), depending on the manner in which the partitioning is performed.

At step 104, the method 100 further includes computing a strong hash for each block and generating an ID table that includes a Jiang Haxi list with pointers to the locations of the corresponding blocks. For example, the ID table may include a mapping from the ID to a strong hash, and the location on disk of the block corresponding to Jiang Ha. In some examples, the ID is monotonically increasing, so subsequent entries will have consecutive IDs. Likewise, if one ID matches one data item, it is contemplated that subsequent IDs will point to consecutive data items. In general, hashing is the process of converting a given key into a new value. The hash function is used to generate a new value according to a mathematical algorithm. The result of the hash function (i.e., the new value) is referred to as a strong hash, or simply a hash. A strong hash may also be referred to as a fingerprint of a data segment (i.e., a plurality of blocks) because each hash may be the same length, but may be unique on a data block basis. For example, a strong hash of a data block is one that has a very high probability of being unique to the data block. This probability may be so high that even if used for years, there will not be two data blocks stored on a given storage system with the same ID. In other words, a strong hash refers to a value that uniquely describes a block of data. Likewise, the probability that two data blocks with the same strong hash are identical is so high that in an actual system they will be considered identical. In other words, a strong hash is a string of bits representing a block of data being processed. If a given data block is processed by a given hash algorithm, and later if the same hash algorithm is applied on the same data block, the same strong hash is created each time. Thus, if the same copy of the data segment arrives, the same strong hash is generated for all copies. Further, the ID table is generated after the strong hash of each block is calculated. The ID table refers to a complete index that maps block IDs (i.e., strong hashes) to the real addresses of the corresponding blocks. The ID table includes a list of unique data blocks ordered by the ID number of the block. Once a new data block is found, it will be added to the end of the list with a new sequence number, which is the ID number of the data block. Thus, the ID table includes all block IDs of all blocks stored in the data storage system. Since the ID table includes a list of strong hashes, which are unique in nature, when the same strong hash is generated for different blocks, the blocks are identified as duplicate blocks and are not stored repeatedly. Thus, the size of the ID table is reduced.

At step 106, the method 100 further includes computing a weak hash for each strong hash and generating a weak hash table including a list of weak hashes with pointers to locations of the corresponding strong hashes in the ID table. The weak hash is selected by: generating a list of weak hashes for each strong hash, and selecting one or more weak hashes from the list of weak hashes as weak hashes. The weak hash is so named because it includes only a portion of the bits corresponding to the strong hash. For example, for a strong hash with 160 bits, a weak hash may be generated by selecting, for example, 64 bits from a total of 160 bits. Further, the weak hash may be selected from a list of weak hashes in a deterministic manner. For example, two weak hashes are selected from the list of weak hashes such that the two weak hashes have a minimum value. Further, a weak hash table is generated after a weak hash is calculated for each strong hash. The weak hash table refers to a complete index that maps weak hash values into block IDs. The weak hash table is the primary index for deduplication. The weak hash table is a standard key-value data structure. Typically, such data structures are implemented using B-trees, with hashes that are not far apart being stored in contiguous locations on disk. When there is a hit, the data structure will generate a set of keys and values that are located closely on disk. The weak hash table has a built-in caching mechanism for storing the relevant weak hash in the cache portion. Advantageously, the latency and access rate of acquiring read IOs is reduced, and throughput and hit rate are improved. Thus, the overall performance of the data deduplication scheme is optimized.

In response to receiving the incoming data item, the method 100 includes dividing the incoming data item in the data storage system into a plurality of blocks at step 108. An incoming data item in a data storage system refers to a request to store a new data item (i.e., a data file, a database file, an IO write, etc.) as part of a backup task. Incoming data items are mostly sequential and have a large IO. In order to efficiently manage incoming data items (or incoming write requests), the incoming data items are broken down into blocks by a partitioning process (i.e., splitting large incoming data items into small data items called data blocks).

In response to receiving the incoming data item, the method 100 further includes computing a strong hash and a weak hash for each block, step 110. In general, hashing is the process of converting a given key into a new value. The hash function is used to generate a new value according to a mathematical algorithm. The result of the hash function (i.e., the new value) is referred to as a strong hash, or simply a hash. In other words, a strong hash is a string of bits representing a block of data being processed. Here, for each of a plurality of blocks generated for an incoming data item, a corresponding strong hash and weak hash is calculated. In other words, a strong hash refers to a value that uniquely describes a data block of an incoming data item. In addition, the weak hash is so named because it includes only a portion of the bits corresponding to the strong hash. For example, for a strong hash with 160 bits, a weak hash may be generated by selecting, for example, 64 bits from a total of 160 bits.

In response to receiving the incoming data item, the method 100 further includes selecting one or more representative weak hashes for the incoming data item, at step 112. One or more representative weak hashes are selected by: generating a list of weak hashes, each corresponding to a respective strong hash of the incoming data item, and selecting one or more weak hashes from the list of weak hashes as one or more representative weak hashes of the incoming data item. Further, one or more representative weak hashes may be selected from a list of weak hashes in a deterministic manner. For example, two representative weak hashes are selected from the list of weak hashes such that the two representative weak hashes have a minimum value.

According to an embodiment, selecting the representative weak hash includes selecting a predetermined number of lowest value weak hashes. One or more representative weak hashes are selected by: generating a list of weak hashes from the calculated strong hash of each block of the incoming data item, and selecting one or more of the weak hashes as a representative weak hash. Further, the selection of the representative weak hash uses a predetermined procedure. A predetermined process refers to a process that does not involve randomness in the development of the future state of the process. Thus, the predetermined process always produces the same output from a given starting condition or initial state. The predetermined procedure may also be referred to as a probabilistic or deterministic procedure. For example, one or more representative weak hashes are selected from the one or more weak hashes of each block of the incoming data item such that the one or more representative weak hashes have the lowest weak hash value.

According to an embodiment, selecting the representative weak hash includes selecting one or more weak hashes for which a predetermined number of most significant bits are equal to zero. One or more representative weak hashes are selected by: a list of weak hashes is generated from the calculated strong hashes for each block of the incoming data item, and one or more of the weak hashes are selected as a representative weak hash. Further, the selection of the representative weak hash uses a predetermined procedure. A predetermined process refers to a process that does not involve randomness in the development of the future state of the process. Thus, the predetermined process always produces the same output from a given starting condition or initial state. The predetermined procedure may also be referred to as a probabilistic or deterministic procedure. For example, one or more representative weak hashes are selected from the one or more weak hashes of each block of the incoming data item such that a predetermined number of most significant bits (most significant bit, MSB) of the one or more weak hashes are equal to zero. Advantageously, the weak hash with the same MSB is located closely in the cache portion within the weak hash table. Thus, the cache eviction algorithm is able to cache a complete page of a strong hash, which allows searching in a weak hash table to be more efficient.

In one implementation, the predetermined number is dynamically selected based on a hit rate of the data storage system and an amount of data in the cache portion. The cache eviction algorithm dynamically decides how many weak hashes to examine for weak hash entries in the cache portion of the weak hash table. For example, at least how many weak hashes to choose, or how many MSBs to examine. The predetermined number is based on the hit rate of the data storage system and the amount of data in the cache portion of the weak hash table, i.e., one or more weak hashes for which a maximum number of matches is found are more likely to be placed in the cache portion of the weak hash table. Advantageously, the cache eviction algorithm ensures that a weak hash of an incoming data item searched against a weak hash table of the data storage system is present in the cache portion. Thus, the number of accesses to acquire IO operations from disk is reduced, thus minimizing latency in the data storage system.

In response to receiving the incoming data item, the method 100 further includes searching the weak hash table for a representative weak hash at step 114. One or more representative weak hashes of an incoming data item (i.e., an incoming write request) are searched in a weak hash table of the data storage system for a match. The weak hash table refers to a complete index that maps all weak hashes of the data storage system into corresponding block IDs. Searching the weak hash table for one or more representative weak hashes of the representative weak hash corresponding to the weak hash check incoming data item in the weak hash table against the data storage system.

In response to receiving the incoming data item, the method 100 further includes recording matches between one or more of the representative weak hashes and weak hashes in a weak hash table, wherein the weak hash table includes a cache portion, and the cache eviction algorithm is configured to determine whether to reserve or evict each of the weak hashes in the cache portion based on the number of matches recorded for the weak hashes, step 116. When there is a hit (i.e., a match between one or more representative weak hashes of the incoming data item and the weak hash of the weak hash table), the data processing apparatus uses the built-in caching mechanism to tightly locate the matching set (the weak hash and its corresponding block ID) on disk. The built-in caching mechanism may create cached portions within the weak hash table. The cache portion refers to a collection of weak hashes and their corresponding block IDs that find a match against one or more representative weak hashes of an incoming data item. The representative weak hashes may be selected by a deterministic method, for example, in which 6 most significant bits are 0, and thus, if the weak hashes are arranged on the disk in the order of their values, adjacent representative weak hashes of each representative weak hash are highly likely to have 6 most significant bits of 0. Likewise, if a representative weak hash is brought into the cache along with its neighbors, then all of these weak hashes are likely to have 6 most significant bits of 0. Thus, each time a weak hash is accessed, the neighboring block IDs of the block IDs are obtained by a single hit in the weak hash table. The hits on the cache portion take into account the number of hits of the weak hash entry obtained from the strong hash cache, i.e. if the block ID of the weak hash is found and there is a hit in the strong hash cache, the hit in the strong hash cache is counted as a hit to the weak hash table. In other words, a weak hash that saves access to the weak hash table due to multiple hits in the strong hash cache may remain in the cache portion of the weak hash table for a longer period of time. Thus, the cache eviction algorithm determines whether to reserve or evict each weak hash in the cache portion based on the number of matches for the weak hash records. Further, the cache eviction algorithm dynamically decides how many weak hashes to examine (e.g., how many hashes to obtain at least or how many most significant bits to examine) for each incoming data item based on the current hit rate and the current amount of data in the cache portion of the weak hash table.

According to an embodiment, in response to a match in the weak hash table, the method 100 further comprises: the associated strong hash is found from the ID table and checked against one or more of the strong Ha Xizhong calculated for the incoming data item. When a match is found between one or more representative weak hashes of the incoming data item and a weak hash in the weak hash table, a strong hash associated with the weak hash is found from the ID table. The ID table refers to a complete index that maps block IDs (i.e., strong hashes) to the real addresses of the corresponding blocks. The ID table includes a list of unique data blocks, which are ordered by the ID number of the block. Thus, the ID table includes all block IDs of all blocks stored in the data storage system. Further, when an associated strong hash is found, the associated strong hash is checked against one or more strong hashes calculated for the plurality of blocks of the incoming data item. By checking the associated strong hash against one or more of the strong Ha Xizhong calculated for the incoming data item, the cache eviction algorithm is able to cache the complete page of the strong hash, which makes searching in the weak hash table more efficient. Thus, throughput and hit rate of the data storage system are improved.

According to an embodiment, the method 100 further comprises loading the associated strong hash and one or more neighboring strong hashes into a strong hash cache, wherein the one or more strong hash values calculated for the new incoming data item are checked against the Jiang Haxi cache before searching the weak hash table. The associated strong hash corresponds to the strong hash of the weak hash association found in the cached portion. One or more adjacent strong hashes correspond to a strong hash located near the associated strong hash in the ID table. The associated strong hash and one or more neighboring strong hashes are loaded into the strong hash cache. The strong hash cache refers to a small index that maps strong hashes to corresponding block IDs. The strong hash cache is stored in memory and used as a memory cache for the strong hash. Further, when a new incoming data item (i.e., a new write request) arrives at the data storage system, one or more strong hash values calculated for the new incoming data item are checked against the strong hash cache of the data storage system prior to searching the weak hash table. The one or more strong hash values calculated for each block of the new incoming data item against the Jiang Haxi cache check correspond to the one or more strong hash values calculated against the Jiang Haxi cache strong hash check. The strong hashes of the strong hash cache include an associated strong hash and one or more adjacent strong hashes. Hits to the strong hash cache take into account the number of hits to the strong hash entry from the strong hash cache, i.e. if the strong hash of the strong hash cache matches the calculated one or more strong hash values of the new incoming data item, the hit from the strong hash cache is counted as a hit to the weak hash table. In other words, the strong hash that saves access to the weak hash table due to multiple hits in the strong hash cache remains in the cache portion of the weak hash table for a longer period of time.

According to one embodiment, if there is no match in the weak hash table, the incoming data item is written to the data storage system as a new data item. One or more representative weak hashes of the incoming data items are checked against the weak hashes of the weak hash table for a match. If no match is found in the weak hash table, the incoming data item is identified as a non-deduplicated data item. Non-duplicate data items correspond to data items in the data storage system for which no match (or fingerprint) is found. In other words, a non-duplicate data item corresponds to a data item that cannot be deduplicated due to absence in the data storage system. A new block ID is generated for the non-duplicate data item and the exact data item (i.e., the non-duplicate data item) is stored as the new data item at an address in the data storage system.

According to an embodiment, the cache eviction algorithm is configured to assign a higher priority to preserve a weak hash for which a match of records corresponds to data items received as part of a backup task. The backup task is used to backup data of the target site in order to protect and restore the data when the data of the source site is lost. The backup task (e.g., source-based deduplication) deletes redundant data items before transmitting the data to a target site (e.g., a data storage system) at a client or server. The cache eviction algorithm ensures that the weak hashes searched by the backup task (e.g., source-based deduplication) have a higher priority to remain in the cache portion of the weak hash table based on the number of matches that are the weak hash records. Thus, the number of accesses to acquire IO operations from disk is reduced, thus minimizing latency in backup tasks.

According to an embodiment, an incoming data item is received as part of a backup task. An incoming data item refers to an incoming write request that stores the data item (i.e., data file, database file, input-output (I/O) write, etc.) on a data storage system. The backup task is used to backup data of the target site in order to protect and restore the data when the data of the source site is lost. The backup task (e.g., source-based deduplication) deletes redundant data items before transmitting the data to a target site (e.g., a data storage system) at a client or server. Thus, no additional hardware is required to perform deduplication. In addition, bandwidth and storage capacity requirements are reduced.

According to an embodiment, the method 100 further comprises: receiving a second incoming data item that is not part of the backup task; dividing a second incoming data item in the data storage system into a plurality of blocks; calculating strong hash and weak hash of each block; searching each weak hash in the weak hash table; recording a match between one or more of the weak hashes and a weak hash in the weak hash table; wherein the cache eviction algorithm is configured to assign a lower priority to preserve a weak hash for which a match of records corresponds to a second data item not received as part of the backup task. The second incoming data item refers to an incoming write request to store the data item (i.e., data file, database file, input-output (I/O) write, etc.) on the data storage system. Furthermore, the second incoming data item corresponds to a small random IO operation for universal online deduplication. The second incoming data item is decomposed into a plurality of blocks. Further, a strong hash is computed for each of the plurality of blocks. Further, one or more weak hashes corresponding to each of the calculated strong hashes are calculated. Further, each of the one or more weak hashes is checked against the weak hashes of the weak hash table for a match. Furthermore, if a match is found, the cache eviction algorithm retains the weak hash in the cache portion of the weak hash table. However, the cache eviction algorithm assigns the second incoming data item a lower priority than the incoming data item because the second incoming data item is not part of the backup task.

Thus, the method 100 provides an improved data repetition scheme by efficiently managing data stored in a data storage system by means of a data indexing module. By the cache portion, the number of disk read accesses is reduced, thus minimizing access rate and latency for IO operations to acquire the data storage system. Furthermore, the method 100 of the present disclosure may be efficiently used in a variety of scenarios (e.g., source-based deduplication and generic online deduplication) without degrading performance (i.e., latency, throughput, access rate, and hit rate) in any scenario. Furthermore, the method 100 allows for an efficient, reliable data deduplication scheme for managing duplicate data and non-duplicate data. The non-duplicate data is stored as new data items in the data storage system. On the other hand, duplicate data is not explicitly stored in the data storage system; instead, the corresponding weak hash is retained in the cache portion based on the number of matches for the weak hash record. Thus, the method 100 of the present disclosure allows for efficient use of the storage capacity of a data storage system.

Steps 102 through 116 are merely illustrative and other alternatives may be provided in which one or more steps are added, one or more steps are deleted, or one or more steps are provided in a different order without departing from the scope of the claims herein.

In another aspect, the present disclosure provides a computer-readable medium configured to store instructions that, when executed by a processor, cause the processor to perform the method 100 of the above aspect. Computer readable medium refers to non-transitory computer readable storage medium. Examples of implementations of the computer-readable medium include, but are not limited to, electrically erasable programmable Read-Only Memory (EEPROM), random access Memory (Random Access Memory, RAM), read-Only Memory (ROM), hard Disk Drive (HDD), flash Memory, secure Digital (SD) card, solid-State Drive (SSD), computer-readable storage medium, and/or CPU cache Memory.

FIG. 2 is a block diagram of a data storage system according to an embodiment of the present disclosure. Fig. 2 is described in conjunction with elements of fig. 1A and 1B. Referring to FIG. 2, a block diagram 200 of a data storage system 202 is shown. The data storage system 202 includes control circuitry 204, a transceiver 206, a data processing device 208, and a memory 210. Data processing apparatus 208 also includes a data indexing module 208A, a data querying module 208B, and a cache eviction module 208C.

Data storage system 202 refers to a computer storage system that stores information (i.e., data items, such as data files or database files, I/O writes, etc.) in a storage medium (e.g., a storage disk). Examples of data storage system 202 include, but are not limited to, secondary storage systems, cloud servers, file storage systems, block storage systems, object storage systems, or combinations thereof.

The control circuit 204 includes logic that may be communicatively coupled to the transceiver 206, the data processing device 208, and the memory 210. The control circuitry 204 includes circuitry that controls the operations performed by the data processing device 208 and the flow of data between the different modules of the data processing device 208. Examples of control circuitry 204 may include, but are not limited to, microprocessors, microcontrollers, complex instruction set computing (complex instruction set computing, CISC) processors, application-specific integrated circuit (ASIC) processors, reduced instruction set (reduced instruction set, RISC) processors, very long instruction word (very long instruction word, VLIW) processors, central processing units (central processing unit, CPU), state machines, data processing units, and other processors or control circuits.

The transceiver 206 may comprise suitable logic, circuitry, and/or interfaces that may be configured to transmit/receive IO read/write operations. Examples of transceiver 206 include, but are not limited to, a transmitter/receiver antenna, an Internet of Things (IoT) controller, and the like.

The data processing device 208 refers to a computer component that uses data structure techniques to quickly retrieve records from database files. The data processing device 208 may also be referred to simply as a module or data indexing circuit. The data processing apparatus 208 may comprise suitable logic, circuitry, and/or interfaces that may be configured to perform the method 100 (in conjunction with fig. 1A and 1B). The data processing apparatus 208 includes a data indexing module 208A, the data indexing module 208A configured to index data stored in the data storage system 202. The data processing apparatus 208 also includes a data query module 208B, the data query module 208B configured to receive and index incoming data items in the data storage system 202. The data processing apparatus 208 also includes a cache eviction module 208C, the cache eviction module 208C configured to determine whether to retain or evict a weak hash in the cache portion of the data storage system 202.

The memory 210 may comprise suitable logic, circuitry, and/or interfaces that may be configured to store machine code and/or instructions that may be executed by the data processing apparatus 208. Examples of implementations of memory 210 may include, but are not limited to, hard Disk Drives (HDDs), flash memory, solid-State drives (SSDs), network attached storage (Network Attached Storage, NAS), SSD flash Drive arrays, hybrid flash arrays, cloud storage, and the like.

In operation, data processing apparatus 208 performs method 100 by efficiently managing data items in data storage system 202 via data indexing module 208A, data querying module 208B, and cache eviction module 208C. Operations of data indexing module 208A include: dividing each data item in the data storage system 202 into a plurality of blocks; computing a strong hash for each block, generating an ID table comprising a list of Jiang Haxi with pointers to the locations of the corresponding blocks; a weak hash is computed for each strong hash and a weak hash table is generated that includes a list of weak hashes with pointers to locations of the corresponding strong hashes in the ID table. In response to receiving the incoming data item, operations of the data query module 208B include: dividing an incoming data item in the data storage system 202 into a plurality of blocks; calculating strong hash and weak hash of each block; selecting one or more representative weak hashes for the incoming data items; searching a representative weak hash in a weak hash table; a match between one or more of the representative weak hashes and a weak hash in the weak hash table is recorded. The weak hash table includes a cache portion, and the cache eviction module 208C is configured to determine whether to reserve or evict each weak hash in the cache portion based on the number of matches for the weak hash records.

According to an embodiment, selecting the representative weak hash includes selecting a predetermined number of lowest value weak hashes. Further, selecting the representative weak hash also includes selecting one or more weak hashes for which a predetermined number of most significant bits are equal to zero. Further, the predetermined number is dynamically selected based on the hit rate of the data storage system 202 and the amount of data in the cache portion.

In response to a match in the weak hash table, according to an embodiment, the data query module 208B is configured to find the associated strong hash from the ID table and check the associated strong hash against one or more strong hashes calculated for the incoming data item. The data query module 208B is further configured to load the associated strong hash and one or more neighboring strong hashes into a strong hash cache, wherein the one or more strong hash values calculated for the new incoming data item are checked against the Jiang Haxi cache prior to searching the weak hash table. Furthermore, if there is no match in the weak hash table, the incoming data item is written to the data storage system 202 as a new data item.

According to an embodiment, an incoming data item is received as part of a backup task. Further, the cache eviction module 208C is configured to assign a higher priority to preserve a weak hash for which a match of records corresponds to data items received as part of the backup task.

According to an embodiment, the data query module 208B is further configured to: receiving a second incoming data item that is not part of the backup task; dividing a second incoming data item in the data storage system 202 into a plurality of blocks; calculating strong hash and weak hash of each block; searching each weak hash in the weak hash table; a match between one or more of the weak hashes and the weak hash in the weak hash table is recorded. Further, the cache eviction module 208C is configured to assign a lower priority to preserve a weak hash for which a match of records corresponds to a second data item that was not received as part of the backup task.

Thus, the data processing apparatus 208 provides an efficient, reliable data deduplication scheme for managing duplicate data and non-duplicate data. The non-duplicate data is stored as new data items in the data storage system. On the other hand, duplicate data is not explicitly stored in the data storage system 202; instead, the corresponding weak hash is retained in the cache portion based on the number of matches for the weak hash record. Thus, the data processing device 208 facilitates efficient use of the storage capacity of the data storage system 202.

Fig. 3 is a diagram illustrating various operations of a data deduplication scheme in accordance with an embodiment of the present disclosure. Fig. 3 is described in conjunction with the elements of fig. 1A, 1B, and 2. Referring to fig. 3, a process 300 describing various operations of a data deduplication scheme is shown. Also shown are an incoming write request 302, a strong hash cache 304, a weak hash table 306, and an ID table 308. Strong hash cache 304 also includes strong hash 304A and block ID 304B. Weak hash table 306 also includes weak hash 306A, block ID 306B, and cache portion 306C. ID table 308 also includes block ID 308A, strong hash 308B, reference count 308C, and disk address 308D. Process 300 may correspond to method 100 (in conjunction with fig. 1A and 1B).

The incoming write request 302 refers to a request to store an incoming data item (i.e., a data file, a database file, an I/O write, etc.) in the data storage system 202.

Strong hash cache 304 refers to a small index that maps strong hash 304A to block ID 304B. The strong hash cache 304 is stored in the storage 210 and serves as an in-memory cache for the strong hash.

Weak hash table 306 refers to the complete index that maps weak hash 306A to block ID 306B. In order to provide good deduplication rates (i.e., the ratio of the original data size to the deduplicated data size), the size of weak hash table 306 is large, and therefore weak hash table 306 is stored on disk storage. Weak hash table 306 is a standard key-value data structure. Typically, such data structures are implemented using B-trees, with hashes that are not far apart being stored in contiguous locations on disk. When there is a hit, the data structure will generate a set of keys and values that are located closely on disk. Weak hash table 306 has a built-in caching mechanism for storing relevant weak hashes in cache portion 306C. Cache portion 306C is the primary index for deduplication. Advantageously, the latency and access rate of acquiring read IOs is reduced, and throughput and hit rate are improved. Thus, the overall performance of the data deduplication scheme is optimized.

The ID table 308 refers to a complete index that maps the block ID 308A of the strong hash 308B to the actual address of the data (i.e., disk address 308D). The ID table 308 includes all block IDs of all blocks stored in the data storage system 202. Thus, the size of the ID table 308 is large. Thus, the ID table 308 is stored on disk storage. In addition, ID table 308 maintains a count of references (i.e., pointers) to duplicate data items in reference count 308C.

In operation, the incoming write request 302 is divided into a plurality of blocks and strong and weak hashes are calculated for each block. The incoming write request 302 may include very large sized data items (i.e., data files, database files, I/O writes, etc.). To efficiently manage such large-sized data items (i.e., incoming write requests 302), the data items are broken up into multiple blocks. Dividing a data item into a plurality of blocks may result in blocks of fixed length (i.e., equal size blocks) or variable length (i.e., unequal size blocks), depending on the division algorithm being performed. Further, a strong hash is computed for each block of the data item (i.e., incoming write request 302). The computed strong hash for each chunk refers to the fingerprint of the corresponding chunk, which uniquely describes the corresponding chunk of the data item. In other words, the computed strong hash for each block is a string of bits representing the corresponding block of the data item. Further, a weak hash is calculated for each calculated strong hash. The calculated weak hash refers to a portion of the bits of the corresponding calculated strong hash of the incoming write request 302.

The computed strong hash for each block is checked against Jiang Haxi cache 304. Checking the computed strong hash for each block against Jiang Haxi cache 304 corresponds to checking the computed strong hash for each block against strong hash 304A of Jiang Haxi cache 304. If a match is found between the computed strong hash and Jiang Haxi 304A, the cache eviction algorithm retains the computed weak hash corresponding to Jiang Haxi 304A in cache portion 306C for a longer period of time. On the other hand, if no match is found between the computed strong hash and Jiang Haxi a, control is sent to the weak hash table 306 for further processing.

At weak hash table 306, one or more representative weak hashes selected for incoming write request 302 are checked against weak hash table 306. One or more representative weak hashes are selected by: a list of weak hashes is generated from the computed strong hashes for each block of the incoming write request 302, and one or more of the weak hashes are selected as the representative weak hash. The one or more representative weak hashes are checked against weak hash table 306, corresponding to checking the one or more representative weak hashes of incoming write request 302 against cache portion 306C of weak hash table 306, for a match. Based on the number of matches for the weak hash record, the cache portion 306C includes a weak hash from the weak hash 306A of the weak hash table 306. Further, if a match for one or more representative weak hashes is found in the cache portion 306C, the associated strong hash is retrieved from the ID table 308 and the weak hash is retained in the cache portion 306C. The associated strong hash refers to the strong hash corresponding to the weak hash found in the cache portion 306C that matches. Thus, each time a weak hash is accessed, the neighboring block IDs of the block ID are obtained by a single hit in weak hash table 306. The hit to the cache portion 306C considers the number of hits of the neighboring strong hash of the strong hash obtained from the strong hash cache 304, i.e., the hit of the neighboring block ID of the block ID brought into the strong hash cache 304 is counted as a hit to the weak hash table 306. In other words, a weak hash that saves access to weak hash table 306 due to multiple hits in strong hash cache 304 may remain in cache portion 306C of the weak hash table for a longer period of time. On the other hand, if no match for one or more representative weak hashes is found in the cache portion 306C, the incoming write request 302 is written to the data storage system 202 as a new data item.

According to an embodiment, selecting the representative weak hash includes selecting a predetermined number of lowest value weak hashes. Further, selecting the representative weak hash also includes selecting one or more weak hashes for which a predetermined number of most significant bits are equal to zero. Further, the predetermined number is dynamically selected based on the hit rate of the data storage system 202 and the amount of data in the cache portion 306C.

In response to a match in weak hash table 306, process 300 further includes: the associated strong hash is found from the ID table 308 and checked against one or more of the strong Ha Xizhong calculated for the incoming data item. The process 300 also includes loading the associated strong hash and one or more neighboring strong hashes into the strong hash cache 304, wherein the one or more strong hash values calculated for the new incoming data item are checked against the Jiang Haxi cache 304 prior to searching the weak hash table 306. Furthermore, if there is no match in the weak hash table 306, the incoming data item is written to the data storage system 202 as a new data item.

According to an embodiment, an incoming data item is received as part of a backup task. Further, the cache eviction algorithm is configured to assign a higher priority to preserve a weak hash for which a match of records corresponds to data items received as part of the backup task.

According to an embodiment, the process 300 further comprises: receiving a second incoming data item that is not part of the backup task; dividing a second incoming data item in the data storage system 202 into a plurality of blocks; calculating strong hash and weak hash of each block; searching each weak hash in weak hash table 306; recording a match between one or more of the weak hashes and the weak hash in weak hash table 306; wherein the cache eviction algorithm is configured to assign a lower priority to preserve a weak hash for which a match of records corresponds to a second data item not received as part of the backup task.

In conventional systems, in one example, the main flow of a conventional data deduplication scheme is typically to receive a new write request, segment the data using any segmentation algorithm, compute a strong hash and a weak hash for each segment, and search Jiang Haxi in a given strong hash cache. If Jiang Haxi is found in the given strong hash cache, the block ID is returned. If Jiang Haxi is not found in the given strong hash cache, the weak hash table is searched for. If a weak hash is found in a given weak hash table, the strong hash is retrieved from the given ID table for comparison. If a weak hash is not found in a given weak hash table, the data cannot be deduplicated and a new chunk ID is generated. However, since the given weak hash table is large and the given weak hash table is mostly stored on disk, searching requires reading IOs from disk. Thus, there is a large impact on both latency and read IO throughput.

In contrast to conventional systems, the data repetition scheme of the present disclosure uses a cache eviction algorithm to preserve or evict weak hashes in cache portion 306C based on the number of matches for the weak hash records. The cache portion 306C of the present disclosure reduces the number of disk read accesses, thus minimizing latency in the data deduplication scheme.

Table 1 shows a comparison of disk read access times for a conventional data deduplication scheme and the data deduplication scheme of the present disclosure. Table 1 includes data sets such as "Files28Full", "VMware 28Full", "Oracle 28Full", "Files 4F24Inc", "VMware 4F24Inc" and "Oracle4F24Inc". Table 1 also includes disk read access times and improvements of the conventional data deduplication scheme and the data deduplication scheme of the present disclosure. It can be observed from table 1 that the data deduplication scheme of the present disclosure can save more than 95% of disk read accesses for most data sets.

Table 2 shows a comparison of deduplication rates achieved based on source deduplication and the data deduplication scheme of the present disclosure. Table 2 includes data sets such as "Files28Full", "VMware 28Full", "Oracle 28Full", "Files 4F24Inc", "VMware 4F24Inc" and "Oracle4F24Inc". Table 2 also includes the deduplication rate achieved based on the deduplication of the source and the data deduplication scheme of the present disclosure. As can be observed from table 2, the data deduplication scheme of the present disclosure achieves a deduplication rate very similar to that achieved by source-based deduplication. Thus, the deduplication rate of the data deduplication scheme of the present disclosure is not reduced.

Table 1: comparison of disk read Access times for traditional data deduplication schemes and data deduplication schemes of the present disclosure

Table 2: comparison of deduplication rates achieved based on source deduplication and the data deduplication scheme of the present disclosure

Data set	Source-based deduplication	Data deduplication scheme of the present disclosure
			Files 28Full	25.84	25.32
VMware 28Full	35.47	32.44
			Oracle 28Full	23.17	22.67
Files 4F24Inc	7.01	6.94
			VMware 4F24Inc	6.25	6.17
Oracle 4F24Inc	4.69	4.69

"Inc" refers to a weekly (7-day) full backup that lasts for 4 weeks, i.e., a 28-day incremental backup. "Full" refers to a 28 day Full backup.

Thus, process 300 corresponds to a method for managing data items in data storage system 202 to provide an improved data repetition scheme. With the cache portion 306C, the number of disk read accesses is reduced, thus minimizing the access rate and latency of IO operations to the data storage system 202. Furthermore, process 300 may be efficiently used for multiple scenarios (e.g., source-based deduplication and generic online deduplication) without degrading performance (i.e., latency, throughput, access rate, and hit rate) in any scenario. Furthermore, process 300 allows for an efficient, reliable data deduplication scheme for managing duplicate data and non-duplicate data. The non-duplicate data is stored as new data items in the data storage system 202. On the other hand, duplicate data is not explicitly stored in the data storage system 202; instead, the corresponding weak hash is retained in the cache portion 306C based on the number of matches for the weak hash record. Thus, process 300 allows for efficient utilization of the storage capacity of data storage system 202.

Accordingly, various embodiments of the present disclosure provide a method of data management (i.e., method 100) in a computer-implemented data storage system 202. The method 100 comprises the following steps: dividing each data item in the data storage system 202 into a plurality of blocks; computing a strong hash for each block and generating an ID table comprising a list of Jiang Haxi with pointers to the locations of the corresponding blocks; calculating a weak hash for each strong hash and generating a weak hash table comprising a list of weak hashes with pointers to locations of the corresponding strong hashes in the ID table; in response to receiving the incoming data item: dividing the incoming data item in the data storage system 202 into a plurality of blocks; calculating strong hash and weak hash of each block; selecting one or more representative weak hashes for the incoming data item; searching a representative weak hash in a weak hash table; recording a match between one or more of the representative weak hashes and a weak hash in the weak hash table; wherein the weak hash table includes a cache portion and the cache eviction algorithm is configured to determine whether to reserve or evict each weak hash in the cache portion based on a number of matches for the weak hash records.

Accordingly, various embodiments of the present disclosure also provide a data processing apparatus 208 for use with the data storage system 202. The data processing apparatus 208 includes a data indexing module 208A, the data indexing module 208A configured to: dividing each data item in the data storage system 202 into a plurality of blocks; computing a strong hash for each block and generating an ID table comprising a list of Jiang Haxi with pointers to the locations of the corresponding blocks; a weak hash is computed for each strong hash and a weak hash table is generated that includes a list of weak hashes with pointers to locations of the corresponding strong hashes in the ID table. The data processing apparatus 208 further includes a data query module 208B, the data query module 208B being configured to receive an incoming data item, in response to receiving the incoming data item: dividing the incoming data item in the data storage system 202 into a plurality of blocks; calculating strong hash and weak hash of each block; selecting one or more representative weak hashes for the incoming data item; searching a representative weak hash in a weak hash table; a match between one or more of the representative weak hashes and a weak hash in the weak hash table is recorded. The data processing apparatus 208 also includes a cache eviction module 208C, wherein the weak hash table includes a cache portion, and the cache eviction module 208C is configured to determine whether to reserve or evict each weak hash in the cache portion based on a number of matches for the weak hash records.

Modifications may be made to the embodiments of the disclosure described above without departing from the scope of the disclosure as defined in the appended claims. Expressions such as "comprising," "including," "incorporating," "having," "being" and "being" are intended to be interpreted in a non-exclusive manner, i.e., to allow items, components, or elements not explicitly described to be present as well. Reference to the singular is also to be construed to relate to the plural. The word "exemplary" is used herein to mean "serving as an example, instance, or illustration. Any embodiment described as "exemplary" is not necessarily to be construed as preferred or advantageous over other embodiments, and/or as excluding combinations of features of other embodiments. The word "optionally" as used herein means "provided in some embodiments and not provided in other embodiments. It is appreciated that certain features of the disclosure, which are, for clarity, described in the context of separate embodiments, may also be provided in combination in a single embodiment. Conversely, various features of the disclosure that are, for brevity, described in the context of a single embodiment, may also be provided separately or in any suitable combination or as a suitable subcombination of any other described embodiments of the disclosure.

Claims

1. A method (100) of data management in a computer-implemented data storage system (202), the method (100) comprising:

dividing each data item in the data storage system (202) into a plurality of blocks;

computing a strong hash for each block and generating an ID table comprising a list of Jiang Haxi with pointers to the locations of the corresponding blocks;

calculating a weak hash for each strong hash and generating a weak hash table comprising a list of weak hashes with pointers to locations of the corresponding strong hashes in the ID table; and

in response to receiving the incoming data item:

dividing the incoming data item in the data storage system (202) into a plurality of blocks;

calculating strong hash and weak hash of each block;

selecting one or more representative weak hashes for the incoming data items;

searching the weak hash table for the representative weak hash; and

recording a match between one or more of the representative weak hashes and a weak hash in the weak hash table;

wherein the weak hash table includes a cache portion and a cache eviction algorithm is configured to determine whether to reserve or evict each weak hash in the cache portion based on a number of matches for the weak hash records.

2. The method (100) of claim 1, wherein selecting the representative weak hash comprises selecting a predetermined number of lowest value weak hashes.

3. The method (100) of claim 1, wherein selecting the representative weak hash comprises selecting one or more weak hashes for which a predetermined number of most significant bits are equal to zero.

4. A method (100) according to claim 2 or 3, wherein the predetermined number is dynamically selected based on a hit rate of the data storage system (202) and an amount of data in the cache portion.

5. The method (100) according to any one of the preceding claims, further comprising:

in response to a match in the weak hash table, an associated strong hash is found from the ID table and checked against one or more of the Jiang Haxi calculated for the incoming data item.

6. The method (100) of claim 5, further comprising: loading the associated strong hash and one or more adjacent strong hashes into a strong hash cache, wherein one or more strong hash values calculated for a new incoming data item are checked against the Jiang Haxi cache prior to searching the weak hash table.

7. The method (100) of any of the preceding claims, wherein if there is no match in the weak hash table, the incoming data item is written to the data storage system (202) as a new data item.

8. The method (100) of any one of the preceding claims, wherein the cache eviction algorithm is configured to assign a higher priority to preserve a weak hash for which a match of records corresponds to a data item received as part of a backup task.

9. The method (100) of any of the preceding claims, wherein the incoming data item is received as part of a backup task.

10. The method (100) of claim 9, further comprising:

receiving a second incoming data item that is not part of the backup task;

dividing the second incoming data item in the data storage system (202) into a plurality of blocks;

calculating strong hash and weak hash of each block;

searching each weak hash in the weak hash table;

recording a match between one or more of the weak hashes and a weak hash in the weak hash table;

wherein the cache eviction algorithm is configured to assign a lower priority to preserve a weak hash for which a match of records corresponds to the second data item not received as part of a backup task.

11. A computer readable medium configured to store instructions that, when executed by a processor, cause the processor to perform the method (100) of any of the preceding claims.

12. A data processing apparatus (208) for a data storage system (202), comprising:

a data indexing module (208A) configured to:

calculating a weak hash for each strong hash and generating a weak hash table comprising a list of weak hashes with pointers to locations of the corresponding strong hashes in the ID table;

a data query module (208B) configured to receive an incoming data item, and in response to receiving the incoming data item:

calculating strong hash and weak hash of each block;

selecting one or more representative weak hashes for the incoming data items;

searching the weak hash table for the representative weak hash;

A cache eviction module (208C), wherein the weak hash table includes a cache portion, and the cache eviction module 208C is configured to determine whether to reserve or evict each weak hash in the cache portion based on a number of matches for the weak hash records.

13. The data processing apparatus (208) of claim 12, wherein selecting the representative weak hash comprises selecting a predetermined number of lowest value weak hashes.

14. The data processing apparatus (208) of claim 12, wherein selecting the representative weak hash comprises selecting one or more weak hashes for which a predetermined number of most significant bits are equal to zero.

15. The data processing apparatus (208) of claim 13 or 14, wherein the predetermined number is dynamically selected based on a hit rate of the data storage system (202) and an amount of data in the cache portion.

16. The data processing apparatus (208) of any one of claims 12 to 15, wherein the data query module (208B) is further configured to: in response to a match in the weak hash table, an associated strong hash is found from the ID table and checked against one or more of the Jiang Haxi calculated for the incoming data item.

17. The data processing apparatus (208) of claim 16, wherein the data query module (208B) is further configured to: loading the associated strong hash and one or more adjacent strong hashes into a strong hash cache, wherein one or more strong hash values calculated for a new incoming data item are checked against the Jiang Haxi cache prior to searching the weak hash table.

18. The data processing apparatus (208) of any of claims 12 to 17, wherein the incoming data item is written to the data storage system (202) as a new data item if there is no match in the weak hash table.

19. The data processing apparatus (208) of any of claims 12 to 18, wherein the cache eviction module (208C) is configured to assign a higher priority to preserve a weak hash for which a match of records corresponds to a data item received as part of a backup task.

20. The data processing apparatus (208) of any of claims 12 to 19, wherein the incoming data is received as part of a backup task.

21. The data processing apparatus (208) of claim 20, wherein the data query module (208B) is further configured to:

Receiving a second incoming data item that is not part of the backup task;

calculating strong hash and weak hash of each block;

searching each weak hash in the weak hash table;

wherein the cache eviction module (208C) is configured to assign a lower priority to preserve a weak hash for which a match of records corresponds to the second data item not received as part of a backup task.