TECHNICAL FIELD

The disclosure generally relates to a method of storing a received data page in a data storage device, and more particularly the disclosure relates to a control unit that causes a data storage device to store the received data page in the data storage device. Moreover, the disclosure also relates to a data storage device including the control unit to store the received data page.

BACKGROUND

Modern computers use limited amounts of memory to keep code and data. Computer memories differ in terms of access speed and (non-)volatility. Normally, volatile memories are faster than non-volatile memories and are suitable for coding and data storage for faster computation applications. For example, random access memory (RAM) is often implemented as volatile memory. Some use-cases, e.g. Internet of Things (loT), may require placing mutable application data in non-volatile memory. To increase execution speed, parts of code and data may also be placed into Central Processing Unit (CPU) code cache (C-cache) and data cache (D-cache) that are faster but smaller than RAM. There may be several levels of CPU caches with different sizes and access speeds. As well, small amounts of data may be placed and kept in CPU registers, which are closest to CPU execution units, and are fastest to access.

In current computer design, memory access speed is determined by technological cost, i.e. tradeoff between technologies used and the related costs: for example, registers memory is fastest and most expensive, while non-volatile memory tiers are slowest and least expensive. Registers are statically allocated by compiler, CPU may dynamically reallocate registers on microcode level. CPU memory controller dynamically manages the allocation of caches for executing programs.

When capacity of a RAM is not enough to execute programs memory manager attempts to free memory. Using an existing memory management system, non-mutable RAM pages are dropped out of the RAM, and to be read later if required. The non-mutable RAM pages include pages of programs in the RAM or pages related to kernel code in the RAM. Mutable RAM pages with changed content, with the least recent access or least usage frequency, may be directly swap out of the RAM to the swap device. The RAM pages that have been modified are marked as dirty pages. ZRAM operates with anonymous pages that are subset of dirty pages. The anonymous pages, by the design of ZRAM do not include pages, allocated by file systems for files, etc. The anonymous pages may be compressed and placed in the ZRAM instead of swapping from the ZRAM to the swap device. If the anonymous pages are non-compressible, they may be placed into the ZRAM as is or written as-is to the swap device. In the case of duplicate anonymous pages, pages filled with patterns, compression of such pages does not happen. Duplicate pages are represented by a small amount of metadata that is a reference to an existing page. Pages filled with patterns (say 8 bytes repeated over whole page) are represented by a small number of pattern bytes.

Another existing memory management system implements an adaptability policy for compressed cache to detect when the compressed cache has to change its memory usage to provide more benefits and fewer costs. This existing memory management system is based on a tightly compressed cache, without allocation of superfluous memory. The amount of memory allocated for the compressed cache is only increased when it is full, compacted, and to release a compressed page to store a new page.

Another existing memory management system implements similarity detection algorithms by implementing similarity signatures for large data chunks, and for variablesize chunking.

Another existing memory management system supports sub -page sharing and in-memory compression of infrequently accessed pages. Another existing memory management system employs a parametrized technique/algorithm to identify similar data pages based upon 64-byte portions of each page. In particular, this existing memory management system hashes the contents of (k*s) 64-byte blocks at randomly chosen locations on the page, and then groups these hashes together into k groups of s hashes each. The algorithm uses each group as an index into a hash table. In other words, higher values of s capture local similarity while higher k values incorporate global similarity. Pages that match at least one of the two blocks are chosen as similar. In this technique, the number of candidates specifies how many different pages that the hash table tracks for each hash signature. With one candidate, the existing memory management system only stores the first page found with each hash signature; for larger values, it keeps multiple pages in the hash table for each hash signature.

The existing memory management system swaps out patched and compressed data pages. But, the swapped-out pages are unavailable for referencing. The swapping operation is expensive as disk input or output is involved.

Another existing memory management system maintains a two-dimensional array for the signature of each page as a heatmap. The heatmap has S rows and V columns, where V is the total number of possible signature values for a cache sub-block. Each 4 kilobytes (KB) cache block is divided into eight 512 -bytes sub-blocks resulting in 8 sub-signatures to represent the content of the cache block. Unlike many existing content addressable storage systems, each sub-signature is 1 byte representing the sum of 4 bytes in a subblock at offsets 0, 16, 32, and 64, respectively. In this way, the computation overhead is substantially reduced compared with hash value computation of the whole sub-block. The columns of the heatmap include signature values of a sub-page. Each time a block is read or written, its 8 1-byte sub-signatures are retrieved and the 8 popularity values of corresponding entries in the heatmap are increased by one. This frequency spectrum of contents is the key to identify reference blocks. This existing memory management system identifies reference pages using a frequency spectrum of contents. The existing memory management system fails to identify identical pages compared with the identification of similar pages. Also, the chance of finding similar pages is lower.

Existing data similarity detection techniques/algorithms include fingerprinting, string matching, Bag of words analysis, Citation-based plagiarism detection, Stylometry, etc., which are applied to whole file (e.g. document) to read entire source file to calculate the corresponding similarity characteristic value. Thus, requiring lots of CPU cycles and memory space and incurring tremendous disk accesses. Another existing data similarity detection technique concurrently samples data blocks from the head and the tail of the modulated file to avoid the position shift incurred by the modifications.

However, the aforementioned existing techniques do not use similarity detection in dirty anonymous pages (except when detecting full duplicates) and delta-compression to achieve better compression ratio. Further, the aforementioned existing techniques employ pages deduplication (e.g. ZRAM pages deduplication), compression and pattern detection as separate techniques. Further, The ZRAM and storage swapping techniques do not use dry-run statistics for similarity detection, deduplication, delta-compression of pages in ZRAM, and to decrease writes to swap non-volatile memory device, possibly to improve its life-span.

Therefore, there arises a need to address the aforementioned technical drawbacks in existing technologies that are used in providing efficient similarity detection of data pages in storage systems.

SUMMARY

It is an object of the disclosure to provide a method of storing a received data page in a data storage device, a control unit that causes or controls a data storage device to store the received data page in the data storage device, and the data storage device including the control unit for storing the received data page in the data storage device system while avoiding one or more disadvantages of existing state-of-the-art techniques.

This object is achieved by the features of the independent claims. Further implementation forms are apparent from the dependent claims, the description, and the figures.

The disclosure provides a method of storing a received data page in a data storage device, a control unit that causes a data storage device to store the received data page in the data storage device, and the data storage device including the control unit for storing the received data page in the data storage device system.

According to a first aspect, there is provided a method of storing a received data page in a data storage device. The data storage device includes pre-stored data blocks or pages. The data storage device includes a key-value store having a number of identifiers to the pre-stored data blocks or pages. The identifiers associate a number of pre-calculated hash values calculated from samples of the pre-stored data blocks or pages stored in the data storage device, to one or more blocks or pages from which the hash value was obtained. The data storage device further includes metadata including data that represents a physical address for each of the pre-stored data blocks or pages in the data storage device. The method includes, when a received data page is received, obtaining a set of samples including a first group of samples including two or more samples of the received data page. The samples are regularly spaced. That is, a distance between any sample and any neighbouring sample is the same for all samples. The method includes calculating a hash value, i.e. a new hash value, for each group of the two or more samples. The method includes identifying one or more of the identifiers associating one or more of the precalculated hash value that are in the key-value store and matching the calculated hash value, i.e. the new hash values. The method includes sorting the identified identifiers by a number of times they are identified. The method includes determining a degree of similarity, measured by a number of matching data substrings, between the received data page and one or more pages associating one or more of the sorted identifiers, a substring being a sequence of bytes in the block or page. The method includes handling the received data page in dependence of the degree of similarity.

The method of storing a received data page in a data storage device, e.g. random access memory (RAM), storage class memory (SCM) is provided. The data storage device includes pre-stored data blocks or pages. The data storage device includes a control unit with key-value store for example a hash table. The key-value store uses keys and values as follows. The keys are hash calculated for a sample selected in a page at certain offset. The value is identifier of that page, combined with sample offset. The key-value store allows to associate the keys for multiple samples in pages, pre-stored in the data storage device, with identifiers of these pages, and each page identifier is combined with respective sample offset. The data storage device further includes metadata that maps each page identifier to a physical address of each of the pre-stored data blocks or pages in the data storage device. Optionally, the metadata is organized as vector, B+ -tree, etc.

The method includes, when a data page is received, obtaining a set of samples of the data page including a first group of samples including two or more samples of the received data page. The samples are being at a fixed distance from each other. The method includes calculating a new hash for each of the two or more samples. The method includes determining zero, one or more of the page identifiers of the pre-stored data pages matching each new hash resulted by look-up in the key-value store (e.g. a hash-table). The determined page identifiers for all new hashes, calculated for received page, are sorted by number of their occurrences. For example, if two samples are taken from the received data page, then two hashes are calculated for these two samples. Each hash is used as a key to look-up into the key-value store. For example, for first key, N values, or N page identifiers, are retrieved from the key -value store. For second key, M page identifiers are retrieved from the key-value store. Among N+M retrieved page identifiers, page identifier A occurs x times, and page identifier B occurs y times and no other page identifiers are found, therefore N+M == x+y. Then, assume x < y which makes possible to deterministically sort the page identifiers A and B by number of their occurrences in the set of page identifiers retrieved from the key-value store. The method includes determining a degree of similarity, measured by a number of equal data fragments, found in the received data page and one of the pre-stored data pages corresponding to the page identifiers extracted from the key-value store using hash values calculated for samples of the received data page. Data fragment used for similarity measurement is composed of a number S of sequential bytes, say S==16 bytes, in the data page. The method includes handling the received data page in dependence of the degree of similarity. In particular, if all data fragments of the received data page and one of pre-stored data pages are equal, then two pages are duplicates. If only a part of data fragments is equal in the received data page and in the pre-stored data pages, then pages are similar, and the received page can be delta-compressed relatively to the pre-stored data page. If no data fragments in the received page are equal to any data fragments in the pre-stored data pages, the latter is found by the key-value store look-up, then the received data page is considered unique and is compressed alone (i.e. independent of any pre-stored data pages).

The similarity detection for data pages followed by delta-compression improves latency and throughput of the data storage device. The method enables to perform deduplication or similarity detection of data pages using the same data structures, for example the keyvalue store, and same computations, for example page sampling and calculating hash values for page samples to avoid extra specialized data structures or computations either for deduplication or for similarity detection. Similarity detection, combined with the delta-compression and deduplication increases the effective capacity of the data storage device due to the higher compression ratio of the delta-compression as compared to compression ratio of independently compressed data pages. In addition to the above, the method uses dry run statistics to tune its parameters for similarity detection, deduplication, and delta-compression of data pages to improve efficiency of the similarity detection method.

All the above, the method decreases amount of data written to non-volatile memory, thereby improving the life-span of the data storage device.

According to a second aspect, there is provided a computer program product for controlling the writing of pages to a data storage device. The computer program product includes computer-readable code means which, when a received page is received, will cause the data storage system to perform the above method.

According to a third aspect, a control unit for a data storage device system, said control unit being arranged to, when a page is received, cause the data storage device to perform the method.

According to a fourth aspect, there is provided a data storage device including a control unit. Optionally, the data storage device is a RAM storage such as a ZRAM storage.

Therefore, in contradistinction to the prior art, according to the method for storing the received data page in the data storage device, the control unit that causes the data storage device for storing the received data page in the data storage device, the similarity detection for data pages followed by the delta-compression improves latency and throughput of the data storage device. The method determines a degree of similarity between the received data page and pre-stored data pages, which have been used to handle the received page and the pre-stored data pages efficiently. Based on the degree of similarity, the method can imply delta-compression. The similarity detection, combined with the delta-compression and the deduplication increases the effective capacity of the data storage device due to the higher compression ratio of the deltacompression as compared to compression ratio of independently compressed data pages. In addition to the above, the method uses dry run statistics to tune its parameters for similarity detection, deduplication, and delta-compression of data pages to improve efficiency of the similarity detection method. All the above, the method decreases amount of data written to non-volatile memory, thereby improving the life-span of the data storage device.

These and other aspects of the disclosure will be apparent from and the embodiment(s) described below.

BRIEF DESCRIPTION OF DRAWINGS

Implementations of the disclosure will now be described, by way of example only, with reference to the accompanying drawings, in which:

FIG. 1 is a block diagram that illustrates a control unit for a data storage device in accordance with an implementation of the disclosure;

FIG. 2 is an exemplary view of sampling a received data page in accordance with an implementation of the disclosure;

FIG. 3 is an exemplary view of a key-value store used as a key value store in accordance with an implementation of the disclosure;

FIG. 4 is an exemplary view of determining a degree of similarity of a received data page using a key-value store in accordance with an implementation of the disclosure;

FIGS. 5A and 5B are flow diagrams that illustrate a method of storing a received data page in a data storage device including pre-stored data blocks or pages in accordance with an implementation of the disclosure;

FIGS. 6A-6C are flow diagrams that illustrate a method of handling a received data page in accordance with an implementation of the disclosure; and

FIG. 7 is an illustration of a computing arrangement that is used in accordance with implementations of the disclosure.

DETAILED DESCRIPTION Embodiments of the disclosure provide a method of storing a received data page in a data storage system and a data storage device including the control unit for storing a received data page in the data storage device.

To make the solutions of the disclosure more comprehensible for a person skilled in the art, the following embodiments of the disclosure are described with reference to the accompanying drawings.

Terms such as "a first", "a second", "a third", and "a fourth" (if any) in the summary, claims, and foregoing accompanying drawings of the disclosure are used to distinguish between similar objects and are not necessarily used to describe a specific sequence or order. It should be understood that the terms so used are interchangeable under appropriate circumstances, so that the embodiments of the disclosure described herein are, for example, capable of being implemented in sequences other than the sequences illustrated or described herein. Furthermore, the terms "include" and "have" and any variations thereof, are intended to cover a non-exclusive enclosure. For example, a process, a method, a system, a product, or a device that includes a series of steps or units, is not necessarily limited to expressly listed steps or units but may include other steps or units that are not expressly listed or that are inherent to such process, method, product, or device.

FIG. 1 is a block diagram that illustrates an implementation form of a control unit 104 for a data storage device 102. The data storage device 102 includes a key-value store (e.g. a hash table). The key-value store includes a number of identifiers to the pre-stored data blocks or pages. The identifiers associate a number of pre-calculated hash values calculated from samples of the pre-stored data blocks or pages stored in the data storage device 102 to one or more blocks or pages from which sample was taken and the respective hash value was obtained. The data storage device 102 further includes metadata including data representing a physical address for each of the pre-stored data blocks or pages in the data storage device 102. The control unit 104 is arranged to, when a received data page is received, cause the data storage device 102, obtain a set of samples including a group of samples including two or more samples of the received data page. The samples are being at a fixed distance or equal distance from each other. The data storage device 102 calculates a new hash value for each of the two or more samples. The data storage device 102 identifies one or more of the identifiers associating one or more of the pre-calculated hash values that are in the key-value store. The data storage device 102 sorts the identified identifiers by number of times they are identified. The data storage device 102 determines a degree of similarity, measured by a number of matching data substrings, between the received data page and one or more pages corresponding to one or more of the sorted page identifiers, a substring being a sequence of bytes in the block or page. The data storage device 102 handles the received data page in dependence of the degree of similarity.

The similarity detection, followed by delta-compression of data pages sending to the data storage device or directly swapping out within kernel-level improves latency and throughput of the data storage device. The control unit 104 enables the data storage device 102 to perform deduplication or similarity detection of the received pages using the same data structures, for example the key-value store, and same computations, for example page sampling and calculating hash values for page samples to avoid extra specialized data structures or computations either for deduplication or for similarity detection. Similarity detection, combined with the delta-compression and deduplication increases the effective capacity of the data storage device 102 due to higher compression ratio of delta-compression as compared to compression ratio of independently compressed pages. In addition to the above, the data storage device 102 uses dry run statistics to tune its parameters for similarity detection, deduplication, and deltacompression of pages. All the above, the data storage device 102 decreases amount of data written to non-volatile memory, thereby improving the life-span of the data storage device 102.

Optionally, the step of handling of the received data page further includes (i) if the degree of similarity between the received data page and one or more of the pre-stored data pages is above a first threshold, the data storage device 102 selects one or more of the prestored data pages for which the degree of similarity is above the first threshold. The data storage device 102 performs the following steps for the selected one or more pre-stored data pages, (a) comparing content of the received data page and the one or more selected pre-stored data pages, (b) if the received data page and the selected pre-stored data page are identical, storing a new entry in the metadata for the received page associating it with the selected pre-stored data page, (c) if the received data page and the selected pre-stored data page are similar but not identical, delta-compressing the received data page using the selected pre-stored data page as a dictionary, writing the compression result on storage media, and storing the address of written data page or block in the metadata, as a block/page identifier, and adding one or more entries to the key-value store associating the received page, and both block/page identifier and the offset at what the hash value was calculated. Optionally, if the degree of similarity is below the first threshold above, the data storage device 102 compresses the received data page separately, writes the compressed received page in the data storage device 102, stores the address for the written page in the metadata and adds the new page identifier combined with sample offset, for which hash value was calculated to the key-value store.

The received data page is compressed when the received data page is similar to the selected pre-stored data page, thereby eliminating extra data structures and saving the memory of the data storage device 102. The compression of the received data page occurs when the received data page is similar to the selected pre-stored data page, without swapping the received data page out, thereby improving overall performance of the data storage device 102. The compressed received data pages are stored in the data storage device 102 also improves the overall performance of the data storage device 102.

Optionally, the degree of similarity between the received data block or page and a specific pre-stored data block or page is determined as the overall size of one or more matching substrings, where comparison is started at the offset of the respective samples in the received and the pre-stored data page and extended to the left and to the right from the respective offsets. The determination of the degree of similarity eliminates extra computations for similarity detection. The comparison in similarity detection results in a determination of one or more parameters. Tuning of the one or more parameters results in achieving a higher data reduction ratio.

Optionally, the threshold value is calculated as static constant for all pages, or dynamically recalculated for any pair of old and new data blocks or pages by calculating overall size matching equal substrings for the new page at the offsets where samples are found to be the same.

Optionally, the selected one or more pre-stored data blocks or pages are selected from the one or more identified pre-stored data pages according to the number of the page identifiers obtained from entries of the key-value store when looking up the key-value store by hash values calculated at respective offsets and samples for the received data page.

The hash values calculated at respective offsets and the number of page identifiers obtained from entries of the key-value store enables to apply similarity detection easily, thereby reducing computational complexity.

Optionally, if the selected pre-stored data page is found to be neither similar nor identical, to the specific pre-stored data block or page, the data storage device 102 updates the keyvalue store with page identifiers calculated for samples of the received data page at offsets, spaced by fixed distances. Each key-value store entry to update may be selected using calculated hash value as index into the key-value store and the selected key-value store entry is updated with combination of the received page identifier and the respective offset, at what the hash value was calculated. When the selected pre-stored data page is neither similar nor identical to the specific pre-stored data block or page, the selected pre-stored data page is not referenced by delta-compression. Eventually, the page identifiers for such selected pre-stored data pages are over-written in key-value store, thereby increasing the data storage device capacity and performance of similarity detection.

Optionally, the metadata for each page includes a reference count indicating the number of identical blocks/pages and the number of data blocks or pages that have previously been delta-compressed using the respective page as reference. The reference count indicating the number of identical blocks/pages is used for delta-compression of the similar blocks/pages, thereby eliminating extra data structures and saving memory in the data storage device 102.

Optionally, if the received page identifier, combined with sample offset should be stored to the key-value store and the key-value store is full, the data storage device 102 compares the reference counts of all entries corresponding to respective hash value, and identifying the lowest reference count and selects an entry that has the lowest reference count and overwriting the entry for this selected page with the combination of received page identifier and combined with sample offset, for which the hash value was calculated. The data pages with a reference count equal to one (minimal constant, selected by implementation) are called as unique pages.

Optionally, if more than one page or block is found to have the lowest reference count, the data storage device 102 selects the entry to overwrite among the pages or blocks having the lowest reference count in dependence of the time since the page was written to storage media. The entry of page or block with the lowest reference count and least recently stored (the “oldest” page or block) is selected for overwriting in the key-value store.

FIG. 2 is an exemplary view of sampling a received data page 202 in accordance with an implementation form. When the received data page 202 is received, a control unit is arranged to cause a data storage device to obtain a set of samples including a first group of samples. For example, the first group of samples may include four samples 204A-D, and each sample is of size 16 bytes. If a first sample 204A of received data page 202 may start at 0 bytes as offset, then a second sample 204B may start from 1024 bytes, a third sample 204C may start from 2048 bytes, and a fourth sample 204D may start from 3072 bytes. The data storage device calculates hash values, i.e. new hash values for the four samples 204A-D. The calculated hash values, i.e. new hash values may be used as an index for searching in a key-value store. The control unit identifies or extracts a page identifier based on the calculated hash values, e.g. extracts zero or more page identifiers from the key-value store for the calculated four hash values, i.e. four new hash values. The identified or extracted page identifiers are grouped by equality (i.e. having the same values). The data storage device creates an array for the calculated (new) hash values and the corresponding extracted page identifiers or the data storage device creates an array for the page identifiers and the four new hash values. If a number of identified or extracted page identifiers for a group of samples is above a threshold, then a respective page with that page identifier may be considered to be similar to the received data page or if a group includes at least minimum page identifiers, then a respective page with that page identifier may be similar to the received data page. The group is referred to as a similarity candidate group. The control unit may sample the received data page 202 repetitively to a maximum number of times by incrementing the offset by 1 to find at least one similarity candidate group. The incremented sampling sets of the samples 0, 1024, 2048, 3072, maybe (1, 1025, 2049, 3073), (2, 1026, 2050, 3074), etc. In case, there are a large number of similarity candidate groups found after sampling, the data storage device sorts similarity candidate groups in descending order based on their size. The result of the sorting is stored in an array. The data storage device places a biggest similarity candidate group at the beginning of the array and a smallest similarity candidate group at the end of the array. The biggest similarity candidate group may be considered as better candidate for similarity. The number of similarity candidate groups may be limited using a parameter. If the parameter is equal to one, then the data storage device considers only one similarity candidate group with a maximum number of page identifiers, data page in selected similarity candidate group may be read from flash or ZRAM. The data storage device compares the received data page with the pre-stored pages for finding a duplicate. If the received data page 202 is duplicate, then the data storage device replaces by a reference to the other page. Otherwise, the data storage device compresses the received data page using the other page as a dictionary. For example, if two pages each of size 4 kilobytes (KB) are copied into 8KB buffer one by one, then the first page is scanned as a dictionary to collect statistics. Then the data storage device compresses the second page using the dictionary that is collected from the first page. The higher compression ratio is achieved using delta-compression. Even if page is non-compressible without dictionary, it may be compressible with dictionary if the latter contains data similar to that in non-compressible data.

FIG. 3 is an exemplary view of a key-value store 300 in accordance with an implementation form. The key-value store 300 includes one or more page identifiers 302AA-NN to pre-stored data blocks or pages associated with a number of pre-calculated hash values. The key-value store 300 includes buckets and is indexed by a page sample hash value. Each bucket includes one or more entries. Each entry includes page identifiers (pagelDs) 302AA-NN. The page identifiers 302AA-NN are combined with offsets of hashed page samples. The pagelDs in a same bucket may correspond to different pages. Same pagelD can be in different buckets. Optionally, while handling a received data page, if the received data page and a selected pre-stored data page are similar but not identical, the received data page is delta- compressed using the selected pre-stored data page as a dictionary, the compression result is written on storage media, and the address of written data page or block is stored in the metadata, as ablock/page identifier. One or more entries are added to the key-value store 300 associating the received data page, and both block/page identifier and the offset at what the hash value was calculated. Optionally, if a degree of similarity is below a first threshold above, the received data page is compressed separately, the compressed received data page is written in a data storage device, the address for the written page is stored in the metadata and the new pagelD combined with sample offset is added to the key-value store 300 associated with the hash value of a sample taken from the received data page.

Optionally, if the selected pre-stored data page is found to be neither similar nor identical, to the specific pre-stored data block or page, the key-value store 300 with the page identifiers 302AA-NN or identifiers calculated for samples of the received page at offsets, spaced by fixed distances, is updated. Key-value store entry to update is selected using calculated hash value as index into the key-value store 300 and the selected keyvalue store entry is updated with combination of the new page identifier and the respective offset, at what the hash value was calculated.

When the received data page is neither similar nor identical to the specific pre-stored data block or page, the received data page is considered unique and compressed separately. Eventually, the page identifiers 302AA-NN may be over-written in key-value store (e.g. hash-table) 300, thereby increasing data storage device capacity and performance of similarity detection.

FIG. 4 is an exemplary view of determining a degree of similarity of a received data page using a key-value store in accordance with an implementation form. The exemplary view includes a data storage device 400. The data storage device 400 includes a key-value store. The key-value store may be a two-dimensional array. The key-value store includes a number of identifiers 404AA-AN, 404CA-CN to pre-stored data blocks or pages associating a number of pre-calculated hash values. The number of pre-calculated hash values are calculated from samples of the pre-stored data blocks or pages stored in the data storage device 400 to one or more blocks or pages from which the hash value is obtained. The data storage device 400 further includes metadata representing a physical address for each of the pre-stored data blocks or pages in the data storage device 400. The exemplary view depicts Logical Block Indirection, LBI, tables, 402A-E. Each LBI table entry is an address of compressed page location either in ZRAM or flash. The page identifiers 404AA-AN identify entries in LBI table.

FIGS. 5A and 5B are flow diagrams that illustrate a method of storing a received data page in a data storage device including pre-stored data blocks or pages in accordance with an implementation form. The data storage device includes a key-value store having a number of identifiers to the pre-stored data blocks or pages. The identifiers associate a number of pre-calculated hash values calculated from samples of the pre-stored data blocks or pages stored in the data storage device, to one or more blocks or pages from which sample was taken and the respective hash value was obtained. The data storage device further includes metadata including data representing a physical address for each of the pre-stored data blocks or pages in the data storage device. At a step 502, when a received data page is received, a set of samples including a group of samples including two or more samples of the received data page is obtained. The samples are being a fixed distance from each other. At a step 504, a new hash value for each of the two or more samples is calculated. At a step 506, one or more of the identifiers associating one or more of the pre-calculated hash value that are in the key-value store are identified. At a step 508, the identified identifiers are sorted by number of times they are identified. At a step 510, a degree of similarity, measured by a number of matching data substrings, between the received data page and one or more pages corresponding to one or more of the sorted identifiers, a substring being a sequence of bytes in the block or page is determined. At a step 512, the received page is handled in dependence of the degree of similarity.

The similarity detection for data pages followed by delta-compression improves latency and throughput of the data storage device. The method enables to perform deduplication or similarity detection of data pages using the same data structures, for example the keyvalue store, and same computations, for example page sampling and calculating hash values for page samples to avoid extra specialized data structures or computations either for deduplication or for similarity detection. Similarity detection, combined with the delta-compression and deduplication increases the effective capacity of the data storage device due to the higher compression ratio of the delta-compression as compared to compression ratio of independently compressed data pages. In addition to the above, the method uses dry run statistics to tune its parameters for similarity detection, deduplication, and delta-compression of data pages to improve efficiency of the similarity detection method. All the above, the method decreases amount of data written to non-volatile memory, thereby improving the life-span of the data storage device.

FIGS. 6A-6C are flow diagrams that illustrate a method for handling a received data page in accordance with an implementation form. When the received data page is received, the control unit handles the received data page. At a step 602, hashes for N samples in 4 KiloBytes(KB), received data page are calculated. At a step 604, if a degree of similarity between the received data page and one or more of the pre-stored data pages is above a first threshold, one or more of the pre-stored data pages for which the degree of similarity is above the first threshold is selected. At a step 606, for the selected one or more prestored data pages, content of the received data page and the one or more selected prestored data pages are compared. At a step 608, if the sample hashes of the received data page are the same as sample hashes of one or more selected pre-stored data pages, then the respective pre-stored data page is read. At a step 610, the received data page and the one or more pre-stored data pages are compared for identifying degree of similarity. At a step 612, if duplicate is not identified, then comparison for similarity is applied. At a step 614, if any similarity is not identified, then at a step 616, a unique page is compressed and stored to the data storage device, a key-value store with the middle set of samples is also updated. At a step 618, if the received data page and the selected pre-stored data page are identical, a new entry in the metadata for the received page associating it with the selected pre-stored data page is stored. At a step 620, if the received data page and the selected pre-stored data page are similar but not identical, the received data page is delta-compressed using the selected pre-stored data page as a dictionary, the compression result is written on storage media, and the address of written data page or block is stored in the metadata, as a block/page identifier, and one or more entries are added to the key- value store associating the received page identifier and the offset at what the hash value was calculated.

The compression of the received data page occurs when the received data page is similar to the selected pre-stored data page, without swapping the received data page out, thereby improving overall performance of the data storage device.

Optionally, the degree of similarity between the received data block or page and a specific pre-stored data block or page is determined as the overall size of one or more matching substrings, where comparison is started at the offset of the respective samples in the received and the pre-stored data page and extended to the left and to the right from the respective offsets.

The threshold value may be calculated as static constant for all pages, or dynamically recalculated for any pair of old and new data blocks or pages by calculating overall size matching equal substrings for the new page at the offsets where samples are found to be the same.

The selected one or more pre-stored data blocks or pages may be selected from the one or more identified pre-stored data pages according to the number of the page identifiers obtained from entries of the key-value store when looking up the key-value store by hash values calculated at respective offsets and samples for the received data page.

Optionally, if the selected pre-stored data page is found to be neither similar nor identical to the specific pre-stored data block or page, updating the key-value store with page identifiers calculated for samples of the received page at offsets, spaced by fixed distances is done as follows: each key-value store entry to update is selected using calculated hash value as index into key-value store and the selected key-value store entry is updated with combination of the received page identifier and the respective offset, at what the hash value was calculated.

Optionally, the metadata for each page, may include a reference count indicating the number of identical blocks/pages and the number of data blocks or pages that have previously been delta-compressed using the respective page as reference. The reference count indicating the sum of the number of identical blocks/pages is used for delta-compression of the similar blocks/pages, thereby eliminating extra data structures and saving memory in the data storage device.

Optionally, if the received page identifier, combined with sample offset, should be stored to the key-value store and the key-value store is full the method further includes: (i) comparing the reference counts of all entries corresponding to respective hash value, and identifying the lowest reference count, and (ii) selecting an entry that has the lowest reference count and overwriting the entry for this selected page with the combination of received page identifier, combined with sample offset, for which the hash value was calculated.

Optionally, if more than one page or block is found to have the lowest reference count, selecting the entry to overwrite among the pages or blocks having the lowest reference count in dependence of the time since the page was written to storage media.

In an implementation, a computer program product for controlling the writing of pages to a data storage device. The computer program product includes computer-readable code means which, when a received page is received, will cause the data storage system to perform the above methods.

FIG. 7 is an illustration of an exemplary computing arrangement 700 in which the various architectures and functionalities of the various previous implementations may be implemented. As shown, the computing arrangement 700 includes at least one processor 704 that is connected to a bus 702, wherein the computing arrangement 700 may be implemented using any suitable protocol, such as PCI (Peripheral Component Interconnect), PCI-Express, AGP (Accelerated Graphics Port), HyperTransport, or any other bus or point-to-point communication protocol (s). The computing arrangement 700 also includes a memory 706.

Control logic (software) and data are stored in the memory 706 which may take the form of random-access memory (RAM). In the description, a single semiconductor platform may refer to a sole unitary semiconductor-based integrated circuit or chip. It should be noted that the term single semiconductor platform may also refer to multi-chip modules with increased connectivity which simulate on-chip modules with increased connectivity which simulate on-chip operation, and make substantial improvements over utilizing a conventional central processing unit (CPU) and bus implementation. Of course, the various modules may also be situated separately or in various combinations of semiconductor platforms per the desires of the user.

The computing arrangement 700 may also include a secondary storage 710. The secondary storage 710 includes, for example, a hard disk drive and a removable storage drive, representing a floppy disk drive, a magnetic tape drive, a compact disk drive, digital versatile disk (DVD) drive, recording device, universal serial bus (USB) flash memory. The removable storage drive at least one of reads from and writes to a removable storage unit in a well-known manner.

Computer programs, or computer control logic algorithms, may be stored in at least one of the memory 706 and the secondary storage 710. Such computer programs, when executed, enable the computing arrangement 700 to perform various functions as described in the foregoing. The memory 706, the secondary storage 710, and any other storage are possible examples of computer-readable media.

In an implementation, the architectures and functionalities depicted in the various previous figures may be implemented in the context of the processor 704, a graphics processor coupled to a communication interface 712, an integrated circuit (not shown) that is capable of at least a portion of the capabilities of both the processor 704 and a graphics processor, a chipset (i.e., a group of integrated circuits designed to work and sold as a unit for performing related functions, etc.).

Furthermore, the architectures and functionalities depicted in the various previous figures may be implemented in the context of a general computer system, a circuit board system, a game console system dedicated for entertainment purposes, an application-specific system. For example, the computing arrangement 700 may take the form of a desktop computer, a laptop computer, a server, a workstation, a game console, an embedded system. Furthermore, the computing arrangement 700 may take the form of various other devices including, but not limited to a personal digital assistant (PDA) device, a mobile phone device, a smart phone, a television, etc. Additionally, although not shown, the computing arrangement 700 may be coupled to a network (e.g., a telecommunications network, a local area network (LAN), a wireless network, a wide area network (WAN) such as the Internet, a peer-to-peer network, a cable network, or the like) for communication purposes through an I/O interface 708.

It should be understood that the arrangement of components illustrated in the figures described are exemplary and that other arrangement may be possible. It should also be understood that the various system components (and means) defined by the claims, described below, and illustrated in the various block diagrams represent components in some systems configured according to the subject matter disclosed herein. For example, one or more of these system components (and means) may be realized, in whole or in part, by at least some of the components illustrated in the arrangements illustrated in the described figures.

In addition, while at least one of these components are implemented at least partially as an electronic hardware component, and therefore constitutes a machine, the other components may be implemented in software that when included in an execution environment constitutes a machine, hardware, or a combination of software and hardware.

Although the disclosure and its advantages have been described in detail, it should be understood that various changes, substitutions and alterations can be made herein without departing from the spirit and scope of the disclosure as defined by the appended claims.