Source: https://patents.google.com/patent/US8725705B2/en
Timestamp: 2019-09-17 09:59:35
Document Index: 741933072

Matched Legal Cases: ['application No. 08153870', 'application No. 08153870', 'application No. 05', 'application No. 08', 'art 1', 'art 1', 'Application No. 08153870']

US8725705B2 - Systems and methods for searching of storage data with reduced bandwidth requirements - Google Patents
Systems and methods for searching of storage data with reduced bandwidth requirements Download PDF
US8725705B2
US8725705B2 US11/194,086 US19408605A US8725705B2 US 8725705 B2 US8725705 B2 US 8725705B2 US 19408605 A US19408605 A US 19408605A US 8725705 B2 US8725705 B2 US 8725705B2
US11/194,086
US20060059207A1 (en
2005-07-29 Priority to US11/194,086 priority patent/US8725705B2/en
2005-09-15 Priority claimed from CN2005800390868A external-priority patent/CN101084499B/en
2005-11-16 Assigned to DILIGENT TECHNOLOGIES CORPORATION reassignment DILIGENT TECHNOLOGIES CORPORATION ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: KLEIN, SHMUEL T., BACHMAT, EITAN, ARONOVICH, LIOR, ASHER, RON, BITNER, HAIM, HIRSCH, MICHAEL
2006-03-16 Publication of US20060059207A1 publication Critical patent/US20060059207A1/en
2014-05-13 Publication of US8725705B2 publication Critical patent/US8725705B2/en
Systems and methods enabling search of a repository for the location of data that is similar to input data, using a defined measure of similarity, in a time that is independent of the size of the repository and linear in a size of the input data, and a space that is proportional to a small fraction of the size of the repository. Additionally, remote operations are accomplished with significantly reduced system bandwidth by implementing remote differencing operations.
This application is a continuation-in-part of U.S. patent application Ser. No. 10/941,632, filed Sep. 15, 2004 and titled “Systems And Methods For Efficient Data Searching, Storage And Reduction,” and which is hereby incorporated by reference in its entirety.
This invention relates to systems and methods for searching of and storage of data with reduced bandwidth requirements relative to the amount of data being managed; these systems and methods are particularly useful for generating and maintaining a large scale data repository in backup and restore systems.
Storing large amounts of data efficiently, in terms of both time and space, is of paramount concern in the design of a backup and restore system, particularly where a large repository of digital data must be preserved. For example, a user or group of users might wish to periodically (e.g., daily or weekly) backup all of the data stored on their computer(s) to a repository as a precaution against possible crashes, corruption or accidental deletion of important data. It commonly occurs that most of the data, at times more than 99%, has not been changed since the last backup has been performed, and therefore much of the current data can already be found in the repository, with only minor changes. If this data in the repository that is similar to the current backup data can be located efficiently, then there is no need to store the data again, rather, only the changes need be recorded. This process of storing common data once only is known as data factoring.
In such large systems, the input (backup) data stream to be added to the repository may be, for instance, up to 100 GB or more. It is very likely that this input data is similar to, but not exactly the same as, data already in the repository. Further, the backup data stream may not be arranged on the same data boundaries (e.g., block alignment) as the data already in the repository. In order to make a subsequent factoring step more efficient, the backup and restore system must be able to efficiently find the location of the data in the repository that is sufficiently similar to the input stream without relying on any relative alignment of the data in the repository and the data in the input stream. The backup and restore system must also be able to efficiently add the input stream to the repository and remove from the repository old input streams that have been deleted or superseded.
Generally, it can be assumed that data changes are local. Thus, for instance, if 1% of the data has been changed, then such changes are concentrated in localized areas and in those areas there are possibly major changes, while the vast majority of the data areas have remained the same. Typically (although not necessarily) if, for example, 1% of the data has changed, then viewing the data as a stream of 512-byte blocks rather than as a stream of bytes, a little more than 1% of the blocks have changed. However, because there is no predetermined alignment of the data in the input stream and repository, finding the localized data changes is a significant task.
Searching for similar data may be considered an extension of the classical problem of pattern matching, in which a text T of length n is searched for the appearance of a string P of length m. Typically, text length n is much larger than search string length m. Many publications present search methods which attempt to solve this problem efficiently, that is, faster than the naïve approach of testing each location in text T to determine if string P appears there. By preprocessing the pattern, some algorithms achieve better complexity, for example see:
All of these algorithms work in time that is of order O(n+m), which means that the search time grows linearly with the size of text. One problem with these algorithms is that they are not scalable beyond some restrictive limit. For example, if searching a 1 GB text (the size of about 300 copies of the King James Bible) can be done in 1 second, searching a one Petabyte text would require more than 12 days of CPU time. A backup and restore system with one Petabyte (PB) or more in its repository could not use such an algorithm. Another disadvantage of the above algorithms is that they announce only exact matches, and are not easily extended to perform approximate matching.
For large-scale data repositories, however, O(n√{square root over (k log k)}) is not an acceptable complexity. An input data stream entering the backup and restore system may be, for instance, of length up to 100 GB or more. If one assumes that an almost identical copy of this input stream exists in the repository, with only 1% of the data changed, there are still about 1 GB of differences, that is k=230 bytes. To find the locations of approximate matches in the repository, this algorithm will consume time proportional to about 180,000 times the size of the text n. This is unacceptable where our premise is text length n alone is so large, that an algorithm scanning the text only once, may be too slow.
The general paradigm is as follows: The repository data is broken into blocks, and a hash value, also called a fingerprint or a signature, is produced for each block; all of these hash values are stored in an index. To locate some given input data, called the version, the given input data is also broken into blocks and the same hash function (that has been applied to the repository blocks) is applied to each of the version blocks. If the hash value of a version block is found in the index, a match is announced.
The advantage of CAS over the previous methods is that the search for similar data is now performed on the index, rather than on the repository text itself, and if the index is stored using an appropriate data structure, the search time may be significantly reduced. For instance, if the index is stored as a binary tree, or a more general B-tree, the search time will only be O(log (n/s)), where n is the size of the text, and s is the size of the blocks. If the index is stored in a sorted list, an interpolation search of the sorted list has an expected time of O(log (log(n/s))). If the index is stored in a hash table, the expected time could even be reduced to O(1), meaning that searching the index could be done in a constant expected time, in particular in time independent of the size of the repository text.
There are, however, disadvantages to this scheme. As before, only exact matches are found, that is, only if a block of input data is identical to a block of repository data will a match be announced. One of the requirements of a good hash function is that when two blocks are different, even only slightly, the corresponding hash values should be completely different, which is required to assure a good distribution of the hash values. But in backup and restore applications, this means that if two blocks are only approximately equal, a hashing scheme will not detect their proximity. Searching in the vicinity of the found hash value will also not reveal approximate matches. Moreover, an announced match does not necessarily correspond to a real match between two blocks: a hash function h is generally not one-to-one, so one can usually find blocks X and Y such that X≠Y and h(X)=h(Y).
Still further, the bandwidth requirements needed for repository updates and the transmission of data over a network also present opportunities for improvement.
The present invention is directed to systems and methods for efficient remote data searching and storage where an amount of data transmitted between systems is reduced by implementing robust indexing and remote differencing processes.
A system and method according to certain embodiments provides for reducing the amount of network bandwidth used to store data. The system/method eliminates the need to send data through the network that may already exist at the destination. In one embodiment, a data repository is located at a first location. A second location has new data that it desires to store on the repository. A comparison of the new data and data already at the repository is performed. Advantageously, rather than sending all of the new data to the repository for comparison, and possibly wasting bandwidth by sending data that is already stored at the repository, the comparison of the new data with the repository data is accomplished by sending a representation of the new data, of a size much smaller than the entire new data, but with sufficient information on which a comparison of the new data to the repository data can be based in order to determine similarities or differences.
In one embodiment, a method comprises: determining, at a first location, a set of distinguishing characteristics associated with the first data; transmitting the determined set of first data distinguishing characteristics from the first location to a remote location; comparing, at a remote location, the determined set of first data distinguishing characteristics to one or more sets of remote data distinguishing characteristics to identify remote data stored at the remote location that is similar to the first data, wherein similarity is a function of a similarity threshold; and determining one or more differences between the first data and the identified similar remote data, wherein, once similar remote data has been identified, differences (if any) between the first data and the identified similar remote data are determined without transmitting all of the first data to the remote location and without transmitting all of the identified similar remote data to the first location.
In another embodiment, the first location is a first computer and the remote location is a remote computer different form the first computer, the first and remote computers being in networked communication with one another; and the remote data is stored in a data repository accessed only through the remote computer.
Further, determining one or more differences between the first data and the identified similar remote data comprises operation of a remote differencing procedure.
In another embodiment, a determined reference label, the locations of the differing portions and the respective first data portions are transmitted from the first location to a second location different from the remote location; and the second location recreates the first data as a function of the differing portions and the identified similar remote data.
In an alternate embodiment, recreating the first data comprises the second location retrieving the entire identified similar remote data from the remote location.
In yet another embodiment, the first location is a first computer and the second location is at a second computer different from the first computer, the first and second computers being in networked communication with one another.
A system comprises: means for determining, at a first location, a set of distinguishing characteristics associated with the first data; means for transmitting the determined set of first data distinguishing characteristics from the first location to a remote location; means for comparing, at a remote location, the determined set of first data distinguishing characteristics to one or more sets of remote data distinguishing characteristics to identify remote data stored at the remote location that is similar to the first data, wherein similarity is a function of a similarity threshold; and means for determining one or more differences between the first data and the identified similar remote data, wherein, once similar remote data has been identified, any differences between the first data and the identified similar remote data are determined without transmitting all of the first data to the remote location and without transmitting all of the identified similar remote data to the first location.
In an alternate embodiment, a system comprises: means for receiving, at a remote location, a set of first data distinguishing characteristics from a first location, the set of first data distinguishing characteristics associated with first data as determined at the first location; means for comparing, at the remote location, the set of first data distinguishing characteristics to one or more sets of remote data distinguishing characteristics to identify remote data stored at the remote location that is similar to the first data, wherein similarity is a function of a similarity threshold; and means for determining, via communication between the first location and the remote location, one or more differences between the first data and the identified similar remote data, wherein, once similar remote data has been identified, the differences between the first data and the identified similar remote data are determined without all of the first data being received at the remote location.
A system comprises: a processor; a memory coupled to the processor; and a local data repository coupled to the processor, wherein the processor and the memory are configured to perform a method comprising: receiving a set of first data distinguishing characteristics from a first location, the set of first data distinguishing characteristics associated with first data as determined at the first location; comparing the set of first data distinguishing characteristics to one or more sets of local data distinguishing characteristics to identify local data stored in the local data repository that is similar to the first data, wherein similarity is a function of a similarity threshold; and via communication with the first location, determining one or more differences between the first data and the identified similar local data, wherein, once similar local data has been identified, the differences between the first data and the identified similar local data are determined without receiving all of the first data at the local data repository.
FIG. 14 is a schematic illustration of the same version and repository of FIG. 11, illustrating the step of expanding matches and the correspondence of matches in the version and repository;
FIG. 15 illustrates an exemplary system environment;
FIG. 16 illustrates an alternate general system architecture;
FIG. 17 is a flowchart showing exemplary steps for updating a remote repository using minimal bandwidth; and
FIG. 18 is a flowchart showing exemplary steps for transferring version data from one system to another.
As used in the following embodiments, a repository is a collection of digital data stored in memory and/or storage of a computer reference; there is no limit on its size and the repository can be of the order of one or more PB. In particular applications, the data is stored as binary uninterpretted data. The input data can be of the same type or different from the repository data; the input data is also called the version. In particular applications, the version and repository are each broken into chunks. The chunk size m is a parameter, e.g. 32 MB. The term seed refers to a consecutive sequence of data elements, such as bytes. The seed size s is also a parameter, e.g. 512 bytes, or (in other non-limiting examples) 4 KB or even 8 KB. Generally, the seed size s is much smaller than the chunk size m.
In accordance with certain embodiments of the invention a hash function is used. A hash function maps elements of some large space into elements of some smaller space by assigning elements of the first space a numeric value called the hash value. The hash function is usually an arithmetic function that uses as input some numeric interpretation of the base elements in the first space. A “good” hash function will, most of the time, produce a statistically unrelated hash value for even the slightest change in the elements of the first space.
In the following embodiments a modular hash function is used. This use, however, is a non-limiting example. As is well known, a modular hash function has the property that if the hash value of s consecutive base elements in some stream is known, then the hash value of the s base elements in the stream that start one base element later (and are thus overlapping with the previous sequence of base elements) can be calculated in O(1) operations. In this way, all the hash values of all the seeds in a chunk can be calculated in O(m) operations rather than in O(m*s). Because of this property, this hash function is called a rolling hash function. Note that the present invention is not bound by the use of rolling hash functions in particular or hash functions in general.
An index is a data structure that facilitates efficient searching. It should be space efficient. For some applications (such as the current embodiment) it should support efficient dynamic operations, such as insertion and deletion. An index may be implemented by a hash table, so that searching, insertion and deletion are supported in O(1) operations each. In accordance with certain embodiments of the invention described below, the index is indexed by a key, which is a hash value of some seed, and each key value identifies the seed (or seeds) from which it was generated.
In FIG. 1 there is shown a generalized storage system architecture in accordance with an embodiment of the invention. The invention is, of course, not bound by this specific system architecture. In FIG. 1, a storage area network SAN (12) connects four backup servers (11) to a server (13). Server (13) includes a virtual tape interface (14) and RAM memory (15); an index (16) is stored in RAM (15). The server (13) is connected to a repository (17) which is stored in one or more (possibly external) secondary storage units.
It should be noted that the present invention is not limited to a storage area network (SAN) and its specific technical characteristics, e.g., Fibre Channel. One of ordinary skill in the art will understand that any network technology may be used to facilitate networked communication among the servers including, but not limited to, Internet Protocol (IP) and TCP/IP. While FIG. 1 and the descriptions to follow refer to a SAN, this is only for explanatory purposes and should not be used to limit any embodiment of the present invention unless explicitly set forth in the claims.
In FIG. 2 a flow chart (20) illustrates the steps of a system life cycle in accordance with an embodiment of the invention. As is shown, the process starts with an empty index (21). The content and purpose of the index is detailed below. Next the system enters a wait state until a version (22) is received, and thereafter the version is processed (23) in a manner described in greater detail below. After processing the version, the system returns to a wait state (22) until another version is received. The sequence (22, 23) proceeds as long as more input versions are received. The input version may or may not update the repository and/or the index. In one factoring application described herein, if an input version is recognized as a new one (not sufficiently similar to data in the repository) it is incorporated into the repository as is. If, on the other hand, the input version is recognized as sufficiently similar to already existing data in the repository, it is factored with the repository data, and only the unmatched parts of the version are stored. As is apparent from the foregoing, the longer the system operates, the larger the size of the repository. In certain applications, the repository size ranges from hundreds of gigabytes to multiple petabytes. It is thus necessary to locate or identify the repository data that is sufficiently similar to the input data in an efficient manner; otherwise, the processing time will be too long and the system not economically or commercially feasible.
By way of analogy, as an alternative method of explanation and not meant to be limiting, consider a scenario with two documents, document A and document B, that are very different from one another. In an initialized system, i.e., an empty repository, according to an embodiment of the invention, each of documents A and B is divided into chunks or sections and stored (chunks are discussed below in more detail). For ease of explanation in this scenario, the chunks are sized such that each of documents A and B is four chunks long—with two chunks in each half. The eight chunks are then stored in the repository. It should be noted that, in accordance with this embodiment, these chunks are not stored on a filename basis. These chunks are stored such that the repository is able to recreate the documents from the chunks.
Assume next, that a new document C is created by cutting and pasting the first half of document A (into document C) followed by cutting and pasting the last half of document B (into document C) with no other additional data added. One can see that document C will have substantial similarity to each of documents A and B, but will also have substantially differences from each document.
The present embodiment will break document C into its four chunks and search the repository for similar chunks. Similar chunks will be identified, between the first two chunks of document C and the first two chunks of Document A, and between the last two chunks of document C and the last two chunks of document B. As the system only identifies similar chunks, and not exact chunks, the system will then determine any differences (factoring) between similar chunks. Here, the similar chunks are identical. Thus, in this scenario, document C is effectively already stored (as A and B chunks) and the space necessary to store it, i.e., to be able to recreate it and retrieve it, is much less than storing the entire document C. In a filename based system, the four chunks of document C would be stored again (as document C), which would be redundant as these chunks are already stored in the system.
To recreate document C, the system, according to the present embodiment, will retrieve the two chunks that have been stored for the first half of document A and the two chunks that have been stored for the second half of document B.
In another scenario, a new document D is created by cutting and pasting the first half of document A (into document D) followed by cutting and pasting the last half of document B (into document D). Subsequently, the title of the document is changed from “The Life of John Adams” to “The Loan to Jobs Apple” with no other changes being made. Once again, one can see that there are substantial similarities between documents A and D and between documents B and D, but also substantial differences as well.
The present system will break document D into its four chunks and then look for similar chunks that are already stored. In this case, the system will find the first two chunks from document A and the last two chunks from document B as being similar to the chunks of document D. Next, the system will determine that that there are differences between the first chunk of document D and its respective similar chunk. The differences, i.e., the changed locations in the title, will be determined. Thus, document D will be represented in the repository as the first two chunks from document A and the last two chunks from document B but with an identification, i.e., the delta or difference, of where and how the first chunk from document D differs from the identified similar chunk—the first chunk that was, in this example, associated with document A. The amount of space, therefore, needed to represent document D is then much less than storing all of document D in the repository.
While the foregoing simple scenarios were described with reference to filenames, i.e., documents, various embodiments of the present invention may be transparent to any file system as the comparisons are functions of the chunks and characteristics to be described in further detail below. With the present system, it is possible that documents A, B, C and D are not associated with the same user, as in a file-based or filename-based system, but similarity can be determined and efficient storage can still be accomplished. A backup system, or one attempting to find similarities, based on a file system would be unable to determine the similarities between portions of document A, document B, document C and document D in the above scenarios. Advantageously, the present invention is transparent to most known file systems.
FIG. 3 details one method of processing a version (step 23 in FIG. 2) in accordance with an embodiment of the invention. When a version is received (31) it is divided into smaller chunks (32), say 32 MB per chunk. The first input chunk is selected (33); the input chunk is processed to find a sufficiently similar chunk in the repository and its position (34). This step (34) is described with reference to FIG. 4 in greater detail below. Having found a similar repository chunk, the version chunk is further processed (35), which, according to this embodiment, entails factoring the version chunk with the repository. This process is repeated for additional chunks of the input version (34 to 37), until there are no more chunks in the version and processing is done (38).
In accordance with a different embodiment of the invention, given that an input chunk is matched with certain repository data, the following input chunk is first tested to match the repository data succeeding the matched repository chunk, thus proceeding directly to its application specific processing (35). If, on the other hand, the following input chunk fails this test, it is fully processed to find its similar repository data (34, 35).
An input chunk of size m, say 32 MB, is processed (41) in the following manner. First, a set of k distinguishing characteristics of the version chunk (42) are calculated, where k is a parameter of this algorithm as explained below (typically of the order of a few tens), and where k<<m (chunk size). In accordance with one embodiment (and as will be further described below with respect to a specific example), the set of k distinguishing characteristics can be calculated as follows (not shown in FIG. 4);
(1) Calculate a hash value for every seed of the input data chunk. The seeds can be of any size s substantially smaller than string length m, say 4 KB. By this non-limiting embodiment, the hash value for every seed is calculated using a rolling hash function which moves in each iteration by one byte forward. A hash value is calculated in each iteration with respect to the 4 KB seed size accommodated within this range. By this example, where the input chunk size m=32 MB and seed size s=4 KB, there are 33,550,337 (32 MB−4 KB+1) hash values obtained for each chunk, one at every possible byte offset in the chunk. A rolling hash function has the advantage that once the hash value for a seed of s bytes is known, calculating the hash function for the next s bytes (i.e. s bytes shifted by one byte with respect to the previous s bytes and thus having s−1 overlapping bytes) can be done in O(1) operations, rather than O(s). Note that the invention is not bound by the use of hash functions, nor by hash functions of the rolling type.
(2) Next, the k maximum hash values, i.e., the largest hash values in descending order, of respective k seeds, are selected from among the (33,550,337) calculated hash values; these k seeds constitute the k maximum seeds. Thereafter, the k hash values of respective k seeds that follow by one byte (and overlap by s−1 bytes) the k maximum seeds, respectively, are selected. These k seeds constitute the k distinguishing seeds and their corresponding hash values constitute the k input distinguishing characteristics. Note that the maximum values themselves have a probabilistic distribution that is not uniform. However, if a good hash function is used, the probabilistic distribution of the following k values will be very close to uniform and therefore substantially better for the intended application. By uniform distribution it is meant that the k distinguishing characteristics are substantially uniformly distributed as numbers on some range of numbers.
Note that the invention is not bound by calculating the distinguishing characteristics in the manner described above. Any selection that yields, to a high extent, robust, and well spread characteristics, and is repeatable for a given chunk, can be used in this embodiment of the invention.
Robust: the characteristics assigned to a chunk will remain fairly constant given that the chunk undergoes modest changes (e.g., in up to 25% of its seeds).
Well spread: the characteristic locations are well spread (substantially uniformly) over the chunk (geographically spread).
Repeatable: a certain form of a chunk will substantially always be assigned the same characteristics.
Such methods may consider only a subset of the chunk's seeds. For instance, the selection of characteristics can be at intervals in the chunk the distance between which is defined by an arithmetic or geometric sequence, in accordance with a certain embodiment. Other methods consider all of the chunk's seeds, such as the foregoing method described.
In accordance with this embodiment, a minimum geographic (positional) spread between the characteristics can be enforced, thus improving coverage. In general, any repeatable selection based on mathematical characteristics of the calculated seed values is applicable.
For example, one may choose the k minimal hash values, i.e., the smallest hash values, or the k hash values closest to the median of all the hash values calculated in the chunk, or even the k hash values closest to some predetermined constant. Another example is choosing the k characteristics as the sum of pairs, such that the first pair consists of the minimal value and the maximal value, the second pair consists of the second minimal value and the second maximal value, etc. Other variants are applicable, depending upon the particular application.
For a better understanding of an index structure, FIG. 5 illustrates graphically an index (44) and the correspondence between a set (e.g., five) of distinguishing characteristics (55 i-59 i) in an input chunk (51) and a corresponding set (five) of distinguishing characteristics (55 r-59 r) in a substantially similar repository chunk (52), in accordance with an embodiment of the invention. The repository chunk 52 forms part of a repository (53), which here stores a huge number of chunks 50. The distinguishing characteristics are, as previously described, a selected set of hash values generated from well-spread seeds that are indicated by the five triangles (55 i) to (59 i) in the input chunk (51). The same five distinguishing characteristics (55 r to 59 r) are shown in the substantially similar repository chunk (52). The index (44) holds the distinguishing characteristics of the repository chunks (including the five of chunk (52)) and associated position data, (e.g. the relative location of the chunk (52) in the repository). Thus, during a similarity search, when the values of a repository chunk (52) are found as matching those of an input chunk (51), the location of the sought chunk (52) within the repository will be readily known by extracting the associated position data. The index (44) grows continuously as new versions are incorporated into the repository and the hash values associated with the chunks of each version (calculated in a manner described above) are added to the index.
Returning to FIG. 4, the index (44) is searched for the hash values of the distinguishing characteristics until at most n matches are found (step 43). More specifically, each of the k distinguishing characteristics of the input chunk set is searched in the index in an attempt to find matches, and this continues until at most n distinguishing characteristics are matched. Let j (j<=n) refer to the number of matched distinguishing characteristics. Obviously, if n matches are found before the entire set of k distinguishing characteristics of the input chunk are checked (say only i out of the k values are checked), the need to check the rest (i.e., by this example k−i) is obviated.
In one embodiment, a version chunk that has j≧2 matching distinguishing characteristics is considered as matched with one or more repository chunks. On the other hand, a version chunk that has j≦2 matching distinguishing characteristics is considered to be unmatched with any of the repository chunks. A single match 0=1) is considered not statistically significant because its occurrence may not be a rare event for very large repositories.
In select embodiments, to improve the significance of each match of distinguishing characteristics, a list of highly recurring distinguishing characteristics is maintained. When a distinguishing characteristic is calculated for a number of version chunks that exceeds some threshold, it is considered to belong to some systematic pattern in the data, thus yielding reduced distinguishing information. It is then added to a list of recurring values, to avoid its usage as it occurs for succeeding chunks. Upon calculation of a distinguishing characteristic, its value is checked for existence in the list, and if it exists, it is discarded and another distinguishing characteristic is computed in its place.
In the described embodiment, more than n and up to k distinguishing characteristics are possibly searched for in the index, whilst only n are stored in the index with respect to each repository chunk. By this embodiment, there are two possible effects on maximum hash values that may be caused by changes to the version chunk with respect to the repository: 1) a maximum hash value could disappear because the data that comprises its corresponding seed has been modified; and 2) changed data could introduce a higher maximum value, displacing a still existing maximum. In cases involving the second effect, searching for more distinguishing characteristics provides more stability since a prior maximum has not disappeared, it has only been displaced. These two effects are reasons for selecting the maximum values in descending order, and/or for choosing k>n.
FIG. 6 shows an example of how the distinguishing characteristics may be substantially preserved, despite changes to the data. In this example, the data is mp3 data, the repository size is 20 GB, the version size is tens of thousands of chunks, the chunk size is 32 MB, and the number of distinguishing characteristics calculated for each chunk is 8. In the three-dimensional representation of the search results shown, the horizontal axis (width) denotes the number of keys (distinguishing characteristics) found, and the number searched. The left margin axis (depth) denotes the percentage of data seeds changed, in the version. The right margin axis (height) denotes the number of chunks for which keys were searched and found. Thus, each row (in depth) shows the effect on the number of distinguishing characteristics given some percentage of the seeds that were changed.
For example, in the 5th row, 10% of the data was changed, yet the mean of about 5,000 chunks had 7 of their 8 distinguishing characteristics intact, and over 95% of these chunks had 4 or more of their 8 distinguishing characteristics still present. In the 4th through 1st rows, where respectively 5%, 3%, 2% and 1% of the data was changed, the preservation of distinguishing characteristics is progressively greater. As the percent data change increases, setting a lower threshold (number of minimal matches of distinguishing characteristics in the repository and input) will allow more findings of similar data. In this example, where the peak for a 25% data change (8th row) is centered at about 4 keys found, if the threshold is set at 4 (out of k input distinguishing characteristics) then the similarity search will return substantially all repository locations where up to 25% of the data is changed. If for the same 25% data change the threshold is set higher, e.g., at 6, then the search will return a much lower percentage of similar repository locations. Thus, a graph such as FIG. 6, can assist the user in selecting the values for j, k, m, and n in a particular application.
Returning again to FIG. 4, where one or more sufficiently similar repository chunks are found, the position of each matched repository chunk is extracted from the index (45-46). It is recalled that the position data of the repository chunk (associated with the j found hash values) can be readily retrieved from the index. The succeeding steps may use one or more of the matched repository chunks, and may rank the repository chunks by their level of similarity. In this embodiment, there follows a factoring step involving the version chunk and its matched repository chunks (47), that leads to a storage-efficient incorporation of the version chunk in the repository. In such a factoring backup and restore system, the further steps involve identifying the common (identical) and uncommon (not identical) data in the version and repository, and storing only the uncommon data of the version (keeping the stream consistent by using appropriate pointers), hence saving storage. For example, in a typical backup and restore system, the data may have changed by 1% between backups. The second backup can be added to the repository by adding only 1% of its data to the repository, and maintaining pointers to where the rest of the data can be found, effectively saving 99% of the space required.
In FIG. 4, if no match has been found (i.e., j less than some threshold of matches found) (401-402), the new version chunk is processed by some alternate process since similar repository data was not found (403). In one example, the version chunk can be stored in the repository without factoring. In accordance with an index update policy of the present embodiment, the distinguishing characteristics of the version chunk are added to the index (49). The process (404) is then terminated (in either match success or match fail route described above), until a new version chunk is processed.
Note that the invention is not bound by the foregoing example of an index update policy. For other applications it might be appropriate to keep all of the distinguishing characteristics of both the version chunk and all its matching repository parts; or alternatively, avoid the addition of the version chunk's distinguishing characteristics; or, possibly, update the index with some mixture of the version and the repository chunks' distinguishing characteristics.
It is emphasized that the computational complexity of searching the repository for data that is similar to the version data is proportional to the size of the version, O(version), and is designed to be independent of the size of the repository. This search requires, in accordance with the non-limiting embodiments described above, no more than k hash table searches of O(1) each per version chunk. Since k<m (m being the size of a version chunk), it arises that by the specified embodiments, the computational complexity for finding a similar chunk in the repository does not exceed O(version), the complexity of calculating the distinguishing characteristics, and this is true irrespective of the repository size. The search procedure for similar data is thus very efficient, even for very large repositories.
Furthermore, it is emphasized that the space needed for the index is proportional to the ratio between the number of distinguishing characteristics stored per chunk of repository, and the size of the chunk, i.e., the ratio between n and m. By one embodiment, where n is 8 and m is 32 MB, and the space needed to store each distinguishing characteristic is 16 bytes, a total of 128 bytes is stored in the index for each 32 MB of repository, a ratio of better than 250,000:1. Stated differently, a computer system with a Random Access Memory (RAM) of 4 GB can hold in its memory the index needed for a 1 PB repository, facilitating rapid searching of the index and hence the rapid finding of similar data in a very large repository for an arbitrary input chunk.
The supplemental algorithm may be less efficient (in terms of computational resources) compared to the synchronization (similarity search) algorithm just described. The degraded efficiency may stem from the fact that in the supplemental algorithm all of the data of a given repository chunk is processed, whereas in the similarity search algorithm only partial data associated with the chunk is processed (i.e., data that included the distinguishing characteristics). However, because the supplemental algorithm is applied to only one repository chunk of size m (e.g., 32 MB), or possibly to a few such repository chunks that have already been found to be sufficiently similar to an input chunk, the degraded performance may be relatively insignificant in select applications. This is especially true compared to the alternative of executing the supplemental algorithm on an entire repository, especially one as large as 1 PB or more.
Example 1 Step 1: Build the Index for the Repository
The example uses a rolling hash function to calculate the hash values at every byte offset. It uses a modular hash function, which utilizes, for the sake of illustration, the prime number 8388593; the hash function used is h(X)=X mod 8388593. In this example, the seed size is 8 bytes. Input string “Begin-at-the-beginning-and-go-on-till-you-come-to-the-end;-then-stop.”
Step 1b: Calculate the Maximal Values
Input string: “Start-at-the-beginning-and-continue-to-the-end;-then-cease.” Calculated hash values:
Note that by this example, the threshold for similarity (being the number of minimal matches of distinguishing characteristics) is j≧2. Had this threshold been set to 4, the chunks would not be regarded sufficiently similar, since only three matches were found. Note also that by this example n was set to 4, meaning the number of distinguishing characteristics of a repository chunk is 4, and k was set to 8, meaning the number of distinguishing characteristics calculated for a version chunk is 8. By setting k>n, the search returns the repository location of the number 7735648, which was moved from fourth maximal value in the repository to fifth maximal value in the input and thus would not have been found if k was set to 4 (k=n).
This example illustrates how to find similar chunks in a degenerated case of a repository holding only one chunk. However, even for an index storing distinguishing characteristics of numerous chunks, the search procedure would still be very efficient, since search within the index (e.g., here stored as a hash table) is done in a very efficient manner, even for a large index. Note also that the data stored in respect of each index entry is small (in this example the hash value and position), and accordingly in many applications the index can be accommodated within the internal fast memory (RAM) of the computer, obviating the need to perform slow I/O operations, thereby further expediting the search within the index.
The time needed to calculate the hashes of the seeds of a version chunk is linear in the size of the chunk because a rolling hash is used. The time needed to calculate the k maxima is O(m*log(k)), which is reasonable because k is small. The time needed to search the index for the k distinguishing characteristics, if the index is a binary tree, is O(k*log(r)), where r=(R*k)/m is the number of entries in the index, where R is the size of the repository (up to about 250), k is small (typically 23) and m is the chunk size (typically 225), so r is typically 228, and log(r)=28. Since k is small, searching the index overall is acceptable. The time needed to search the index for the k distinguishing characteristics, if the index is represented as a hash table, is k*O(1). Therefore the chunk search time is dominated by the time it takes to calculate and order the maxima, namely O(m*log(k)), and hence is equivalent to a small number of linear scans of the version chunk. Since k is small, the overall search time is acceptable. Note that this result is a fraction of the complexity of the brute force algorithm, which is O(R*m), the product of the size of the repository R with the size of the chunk m.
One advantage of the present algorithm is use of a seed step size on one interval of the interval pair. While known binary difference or delta algorithms move in byte steps on both intervals, the present algorithm moves in, for example, byte steps only on one interval (the version interval), and in seed size (e.g. multiple byte) steps on the other interval (the repository interval). This technique speeds up processing and reduces space requirements, while not lessening the matching rate (since matches are expanded both backward and forward). Another advantage of the present algorithm is that, while known binary delta algorithms produce both add and copy directives, the present algorithm can be used to produce only copy directives, in sorted order. The add directives can then be implicitly deduced, as needed, from the copy directives, thus decreasing the storage required for the algorithm's output.
ASj Anchor set j, grouping two or more anchors having
the same repository offset estimator.
Step 1—Compute anchor sets (82 in FIG. 9): sort the anchors by ascending order of their version offsets. Traverse the ordered anchors and associate them with anchor sets as follows: a pair of successive anchors Ai and Ai+1 are in the same anchor set if they have the same repository offset estimator, here for example given by: |[O(Ai+1 V)−O(Ai V)]−[O(Ai+1 R)−O(A1 R)]|≦C, where C is a constant selected for desired performance characteristics (discussed further below in regard to complexity). As long as successive anchor pairs belong to the same set, add them to the current set. When a successive pair does not belong to the same set, close the current set, open a new set, and add the later anchor to the new set. Denote the output of this step as {ASj}1 m where m is the number of disjoint anchor sets identified. FIG. 7 illustrates an anchor set ASj including two anchors Ai and Ai+1 linking the version 120 and repository 118. FIGS. 11-14 show a current anchor set 122 in version 120 and repository 118. For each anchor set in {ASj}1 m steps 2-6 described below are performed (step 84 in FIG. 9). Let ASj be the current anchor set (step 91 in FIG. 10).
Step 3—Calculate the repository interval (step 93 in FIG. 10): A repository interval Ij R is associated with the current anchor set ASj. Let Al R (in FIG. L is 124 b) be the left most anchor of ASj and Ar R (in FIG. 11, r is 124 g) be the right most anchor of ASj. Then Ij R=[O(Al R)−(O(Al V)−LO(Ij V)), O(Ar R)+(RO(Ij V)−O(Ar X))]. We term the pair of intervals Ij V and Ij R as corresponding intervals. FIG. 8 illustrates 4 pairs of corresponding intervals (connected by dashed lines between version 120 and repository 118) each associated with a separate anchor set A-D. For each pair of corresponding intervals Ij V and Ij R calculated in this step, the binary difference procedure detailed below (steps 4, 5 and 6) is performed.
Step 4 (refer to FIG. 12)—Expand the anchor matches (step 95 in FIG. 10): Expand the matches around the anchors of the current anchor set ASj forwards and backwards, and code these matches as copy directives. These matches, illustrated in FIG. 12 by area 128 in version 120 and area 129 in repository 118, are called anchor matches. Store these copy directives in a temporary directives buffer. Denote the output of this step as the sets {Ci R}1 n and {Ci V}1 n, where n is the number of anchors in the anchor set.
The systems and methods described herein relate to managed storage medium and representation of data in a managed repository. This may include disks, tapes and any other form of storage medium. The invention is not limited to the use of disks or fixed media, but is also applicable to removable media. For example, a removable disk may be used as a target output device; it may be managed in a similar way to tape, both being removable media.
One approach to design of a system which includes removable media such as tapes, is to have a disk operate as a store for those chunks or elements that are most referenced, and have the least referenced chunks moved onto tape media. This could be balanced by a management system that takes into consideration the newness of any chunk. Also, the system may move related repository chunks to tape as a whole set to be archived and restored from the archive as a set. This would multiply the advantages of the invention. For example, if 100 pieces of media were required to be used without the invention then, for example, ten pieces of media may only be required after utilization of the invention. The media may comprise virtual media that describes itself as a repository.
Various embodiments of the synchronization algorithm and binary difference algorithm described herein have execution time that is linear with respect to a size of the version and space that is constant (depending on the size of the chunk and the anchor set). The reuse of calculated values between the algorithms saves computing time.
In another embodiment of the present invention, the version data, or new data, may be located on one system or computer whereas the repository may be located on another system or computer different from the first system. In such a scenario, the delta information must be determined via communication between the first system and the second or remote system. As described in the foregoing, large amounts of data are being managed and, therefore, the bandwidth used in the system must be minimized wherever possible. In accordance with one aspect of the present invention, a minimum amount of bandwidth is used to accomplish the updating of the repository located remotely from the new or version data.
As shown in FIG. 16, a system (1600) similar to that which is shown in FIG. 1 includes a network (1601), which, as above, can be a SAN or a network based on TCP/IP, to provide communication between a server A (1602), a server B (1604), a server C (1606) and a server D (1608). For explanatory purposes only, server B (1604) has coupled to it a repository B (17B), while server D (1608) has coupled to it a repository D (17A). The repository D (17A) may be a full or partial mirror, backup or replication copy of the repository B (17B) and thus has the same information stored thereon. Server A (1602) and server C (1606) do not have respective repositories.
In one explanatory scenario, the server A (1602) has the new or version data and the repository B (17B) has stored on it the repository data and chunks as described above.
In the explanatory scenario, server A (1602) has new data that needs to be stored in repository B (17B). From the foregoing description, it is understood that the set of distinguishing or identifying characteristics of the new data would be calculated, forwarded to the server B (1604) for use to search the index to find the locations of the repository data that are similar to the new or version data, the older or similar data from the repository B (17B) is retrieved and the new data and the old data are compared to determine the delta or differences.
As server A (1602) contains the new data, in order to determine the delta, one could decide that the similar data from repository B (17B) has to be transmitted through to the server A (1602). This transmission could represent, however, a large percentage of the bandwidth of the network (1601). Once the server A (1602) has determined the delta, in order to update the repository B (17B), the delta information must be transmitted from server A (1602) through the network (1601) to the server B (1604) to be used to update the repository B (17B).
In accordance with one aspect of an embodiment of the present invention, the bandwidth necessary to update the repository B (17B) is reduced. Advantageously, the similar data from repository B (17B) is not transmitted to server A (1602) in order to determine the delta information.
The process of updating the repository B (17B) with minimal bandwidth usage, in accordance with one embodiment of the present invention, will now be described with respect to the method (1700), as shown in FIG. 17. At step (1702), the set of characteristics for the version or new data on server A (1602) is calculated locally at the server A (1602). The server A (1602) transmits the calculated set of characteristics to server B (1604) at step (1704.) The remote server, in this case server B (1604), searches for matches to the received characteristics to identify one or more similar data chunks held in repository B (17B), step (1706.) If a match is found in step (1708,) control passes to step (1710) where the server B (1604) retrieves the similar data chunk from the repository B (17B).
To determine the delta between the new data and the identified similar remote data that was found in repository B (17B), step (1712), a modified version of a remote differencing procedure of low communication cost, e.g., the rsync utility, is used. By using a modified existing remote differencing procedure such as rsync, the amount of network bandwidth that is used to identify the delta information is significantly reduced.
The modified remote differencing procedure determines the differences between the new data and the identified similar remote data without all of the new data and all of the identified similar data having to be on the same system. As a result of the modified procedure, the amount of data that has to be transmitted over the network is reduced. In operation, any one of a number of different remote differencing processes can be modified for this application.
Thus, in one embodiment of the modified remote differencing process, hashes of the new data and the identified similar remote data are calculated, using the same algorithm, by the local system, server A (1602), and the remote system (17B), server B, respectively. These hashes are then compared and those hashes that differ represent portions of respective data that are different. The data for the differing portions are then conveyed from server A to server B for storage on the repository B. The generating and comparing of hashes reduces the amount of data bandwidth necessary to determine the differences in the data.
Subsequent to step (1712), the delta data has been identified and if it is determined, at step (1714,) that the repository B (17B) is to be updated, control passes to step (1716) where the remote repository B (17B) is updated as per the description above.
Returning to step (1708), if no matches are found, control passes to step (1714) where the determination to update the repository B (17B) is made, and if no update is to be performed, then control passes to step (1718.)
In another operating scenario, it may be the situation where server A (1602) has new or version data that it needs to convey to server C (1602). As shown in the system (1600), neither of server A (1602) nor server C (1606) includes a repository. Where the amount of new data may be quite large, in one embodiment of the present invention the amount of data bandwidth necessary to convey the new data from server A (1602) to server C (1606) is minimized.
A method (1800) for transmitting new data from server A (1602) to server C (1606) using a minimal amount of the bandwidth of the network (1601) will be described with respect to FIG. 18. Steps (1702-1712) are the same as have already been described above with respect to FIG. 17. Subsequent to step (1712), at step (1802,) server A (1602) sends the delta information, and identifier information of the similar data, to the second system, i.e., server C (1606). The identifier information of the similar data would include information regarding the location of the repository on which the repository data is located, in this case, repository B (17B), an address of repository B (17B) which may be an IP address of server B (1604), information regarding the specific repository chunk or chunks that have been identified as being similar, e.g., a reference label, and a timestamp identifier to synchronize the state of repository B (17B) from which the differences or delta information was generated at step (1712). This timestamp information may be necessary to ensure that subsequent operations by server C (1606) are with respect to repository B (17B) having a same state at which the differences were determined in step (1712).
At step (1804,) the second system, server C (1606), would use the information received from server A (1602) to retrieve from repository B (17B) the identified similar data chunks. In one embodiment, server C (1606) may request the entire identified repository chunk and replace those portions that are changed with the delta information received from server A (1602) or server C (1606) may request from repository B (17B) only those portions of the repository data that have not changed and then combine with the delta information from server A (1602) to arrive at the new data from server A (1602).
Advantageously, server A (1602) is able to convey the new data to server C (1606) using a minimal amount of bandwidth by only transmitting the delta information along with identifier information for the similar data that is stored at the repository B (17B).
An alternate embodiment of the method 1600, see FIG. 18, will now be described. In this alternate scenario, the receiving server C (1606), at step (1804), accesses repository D (17A) instead of accessing repository B (17B) in order to recreate the data sent from server A (1602). Server C (1606) may be aware that the repository D (17A) has the same data as that in repository B (17B) and may, for any number of reasons, determine that obtaining the similar data from repository D (17A) is a better choice. These reasons could include anyone or more of: system load characteristics; system availability; system response time, and system quality service level contracts. The coordination between server C (1606) and the system D (1608) and repository D (17A) would be the same as that between server C (1606) and server B (1604) and repository B (17B) described above. Once server C (1606) retrieves the information from repository D (17A), repository D (17A) may be updated to reflect the current data that was received from server A (1602) via server C (1606).
In yet another embodiment, once server B (1604) and repository B (17B) have been updated with the difference data from server A (1602), the repository D (17A) can be updated by a transaction with server B (1604) and repository B (17B).
Of course, one of ordinary skill in the art will understand that server C (1606) and server D (1608) may be configured to be the same computer for reasons of system simplification or efficiency.
1. A computer-implemented method, comprising a similarity search followed by an identity comparison:
the similarity search comprising:
at a first location, using a first computer to determine a set of first data distinguishing characteristics associated with each of a plurality of first data chunks of first data stored at the first location, wherein determining the set of first data distinguishing characteristics associated with each first data chunk includes:
calculating a mathematical hash value of each portion of respective data;
determining a subset of k hash values from the calculated mathematical hash values, k being a predetermined number that is smaller than a total number of the calculated mathematical hash values calculated for each portion of the respective data;
identifying a respective data portion for each of the k hash values;
identifying a data portion shifted by a predetermined amount relative to each respective data portion corresponding to the k hash values;
determining a mathematical hash value for each shifted data portion from the calculated mathematical hash values; and
setting the set of first data distinguishing characteristics to be the mathematical hash values for each of the shifted data portions to obtain a more uniform probabilistic distribution than would be obtained using the data portions corresponding to the k hash values;
transmitting the determined sets of first data distinguishing characteristics from the first location to a remote location different than the first location;
at the remote location, using a remote computer to compare a plurality of the determined sets of first data distinguishing characteristics to one or more sets of remote data distinguishing characteristics, and to identify one or more remote data chunks of remote data stored at the remote location that are similar to the first data based on the comparison, wherein the one or more remote data chunks is determined to be similar to the first data when a number of matching distinguishing characteristics is found in the respective sets of distinguishing characteristics for the first and remote chunks which exceeds a similarity threshold; and
the identity comparison comprising:
using the determined similar data chunks, determining one or more differences between the first data and the identified similar remote data, without transmitting all of the first data to the remote location and without transmitting all of the identified similar remote data to the first location.
updating the remote location with the one or more determined differences, wherein a minimum geographic and/or positional spread between the distinguishing characteristics is enforced.
3. The method of claim 1, wherein determining one or more differences between the first data and the identified similar remote data comprises:
determining a reference label for the identified similar remote data;
identifying locations of one or more portions of the identified similar remote data that differ from the first data; and
determining a respective first data portion for each identified differing portion in the remote data.
transmitting the determined reference label, the locations of the differing portions and the respective first data portions from the first location to a second location that is different from the remote location and is also different from the first location; and
a third computer at the second location recreating the first data as a function of the differing portions and the identified similar remote data.
5. The method of claim 4, wherein recreating the first data comprises:
the second location retrieving the entire identified similar remote data from the remote location.
6. The method of claim 4, wherein recreating the first data comprises:
the second location retrieving from the remote location only those portions of the identified similar remote data that are the same as the first data.
7. The method of claim 4, the first and second computers being in networked communication with one another.
the remote computer is different from the first computer, the first and remote computers being in networked communication with one another; and the remote data is stored in a data repository accessed only through the remote computer.
9. The method of claim 1, wherein determining one or more differences between the first data and the identified similar remote data comprises operation of a remote differencing procedure.
10. The method of claim 1, wherein a number n of the first distinguishing characteristics in each subset is less than k.
11. The method of claim 1, wherein the subset of k hash values are selected based on: k maximum hash values, k minimum hash values, k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values so that the set of distinguishing characteristics are robust and well spread over the first data chunk.
12. The method of claim 11, wherein each set of first data distinguishing characteristics associated with the associated first data chunk has no more than n distinguishing characteristics, wherein n<k.
13. The method of claim 1, further comprising determining the one or more sets of remote data distinguishing characteristics, wherein determining each set of remote data distinguishing characteristics includes calculating a mathematical hash value of each portion of data in the remote data chunk, and selecting a subset of the calculated hash values as the set of distinguishing characteristics for the remote data chunk, the subset being less than all of the calculated mathematical hash values.
14. The method of claim 13, wherein the subset of hash values associated with the remote data are selected based on: k maximum hash values, k minimum hash values, k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values, wherein each set of remote data distinguishing characteristics associated with each remote data chunk has no more than n distinguishing characteristics, wherein n≦k.
15. The method of claim 1, wherein the subset of hash values are selected based on at least one of maximum hash values, minimum hash values, hash values closest to a median of all the hash values, hash values closest to a predetermined constant, or a sum of pairs of hash values.
16. The method of claim 15, wherein the selection of the subset further includes applying a positional shift to the data positions of a first selected subset of hash values, to determine second data portions, wherein the hash values of the second data portions are the set of distinguishing characteristics.
17. A computer-implemented method comprising a similarity search followed by an identity comparison:
receiving, at a remote location, sets of first data distinguishing characteristics from a first location different than the remote location, the sets of first data distinguishing characteristics comprising a set of distinguishing characteristics associated with each of a plurality of first data chunks of first data stored at the first location;
at the remote location, using a remote computer to determine one or more sets of remote data distinguishing characteristics, wherein determining each set of remote data distinguishing characteristics includes:
calculating a mathematical hash value of each portion of data in the remote data chunk;
setting the one or more sets of remote data distinguishing characteristics to be the mathematical hash values for each of the shifted data portions, wherein a minimum geographic and/or positional spread between the distinguishing characteristics is enforced;
at the remote location, using the remote computer to compare a plurality of the sets of first data distinguishing characteristics to the one or more sets of remote data distinguishing characteristics, and to identify one or more remote data chunks of remote data stored at the remote location that are similar to the first data based on the comparison, wherein the one or more remote data chunks is determined to be similar to the first data when a number of matching distinguishing characteristics is found in the respective sets of distinguishing characteristics for the first and remote chunks which exceeds a similarity threshold; and
using the determined similar data chunks, determining via communication between the first location and the remote location, one or more differences between the first data and the identified similar remote data, without all of the first data being received at the remote location.
the differences between the first data and the identified similar remote data are determined without transmitting all of the identified similar remote data from the remote location to the first location.
19. The method of claim 17, wherein the subset of hash values associated with the remote data are selected based on: k maximum hash values, k minimum hash values, k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values, wherein each set of remote data distinguishing characteristics associated with each remote data chunk has no more than n distinguishing characteristics, wherein n is less than or equal to k, k being a predetermined number that is smaller than a total number of the mathematical hash values calculated for the associated portion of the remote data.
updating the remote system with the one or more determined differences.
21. A computer-implemented method comprising a similarity search followed by an identity comparison:
setting the one or more sets of remote data distinguishing characteristics to be the mathematical hash values for each of the shifted data portions, wherein a predetermined minimum geographic and/or positional spread between the distinguishing characteristics is enforced;
at the remote location, using the remote computer to compare a plurality of the sets of first data distinguishing characteristics to the one or more sets of remote data distinguishing characteristics, and to identify one or more remote data chunks of remote data stored at the remote location that are similar to the first data based on the comparison, wherein the one or more remote data chunks is determined to be similar to the first data when a number of matching distinguishing characteristics is found in the respective sets of distinguishing characteristics for the first and remote chunks which exceeds a similarity threshold,
wherein the subset of hash values associated with the remote data are selected based on: k maximum hash values, k minimum hash values, k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values,
wherein each set of remote data distinguishing characteristics associated with each remote data chunk has no more than n distinguishing characteristics, wherein n is less than or equal to k, k being a predetermined number that is smaller than a total number of the mathematical hash values calculated for the associated portion of the remote data; and
using the determined similar data chunks, determining via communication between the first location and the remote location, one or more differences between the first data and the identified similar remote data.
22. The method of claim 21, wherein determining one or more differences between the first data and the identified similar remote data comprises operation of a remote differencing procedure.
23. The method of claim 21, wherein the subset of k hash values are selected based on k maximum hash values or k minimum hash values.
24. The method of claim 21, wherein the set of distinguishing characteristics is a subset of hash values generated from the respective data.
25. The method of claim 24, wherein the subset comprises substantially uniformly distributed numbers on a range of numbers.
26. A computer-readable storage medium encoded with instructions that causes a computer to perform a method comprising a similarity search followed by an identity comparison:
determining, at a first location, a set of first data distinguishing characteristics associated with each of a plurality of first data chunks of first data, wherein determining each set of first data distinguishing characteristics includes:
calculating a mathematical hash value of each portion of data in the first data chunk;
setting the set of first data distinguishing characteristics for the first data chunk to be the mathematical hash values for each of the shifted data portions, wherein a minimum geographic and/or positional spread between the distinguishing characteristics is enforced;
comparing, at a remote location, a plurality of the determined sets of first data distinguishing characteristics to one or more sets of remote data distinguishing characteristics, and identifying one or more remote data chunks of remote data stored at the remote location that are similar to the first data based on the comparison, wherein the one or more remote data chunks is determined to be similar to the first data when a number of matching distinguishing characteristics is found in the respective sets of distinguishing characteristics for the first and remote chunks which exceeds a similarity threshold; and
using determined similar data chunks, determining one or more differences between the first data and the identified similar remote data, without transmitting all of the first data to the remote location and without transmitting all of the identified similar remote data to the first location.
updating the remote location with the one or more determined differences.
28. The medium of claim 26, wherein the determining one or more differences between the first data and the identified similar remote data comprises:
recreating, using a third computer at the second location, the first data as a function of the differing portions and the identified similar remote data.
30. The medium of claim 29, wherein the recreating the first data comprises:
retrieving, at the second location, the entire identified similar remote data from the remote location.
31. The medium of claim 29, wherein the recreating the first data comprises:
retrieving, at the second location, from the remote location only those portions of the identified similar remote data that are the same as the first data.
32. The medium of claim 29, wherein the first location is a first computer and the second location is at a second computer different from the first computer, the first and second computers being in networked communication with one another.
33. The medium of claim 26, wherein the subset of hash values associated with the first data are selected based on: k maximum hash values, k minimum hash values, k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values, wherein each set of first data distinguishing characteristics associated with each first data chunk has no more than n distinguishing characteristics, wherein n is less than or equal to k, k being a predetermined number that is smaller than a total number of the mathematical hash values calculated for the associated portion of the first data.
34. The medium of claim 26, wherein the determining one or more differences between the first data and the identified similar remote data comprises operating a remote differencing procedure.
35. The medium of claim 26, wherein the set of distinguishing characteristics are robust and well spread over the chunk.
36. The medium of claim 26, wherein the subset of k hash values are selected based on k maximum hash values or k minimum hash values so that the set of distinguishing characteristics are robust and well spread over the first data chunk.
37. The medium of claim 26, wherein the subset of k hash values are selected based on: k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values so that the set of distinguishing characteristics are robust and well spread over the first data chunk.
38. A computer-readable storage medium encoded with instructions that causes a computer to perform a method comprising a similarity search followed by an identity comparison:
receiving, at a remote location, sets of first data distinguishing characteristics from a first location, the sets of first data distinguishing characteristics comprising a set of distinguishing characteristics associated with each of the plurality of first data chunks of first data stored at the first location;
determining one or more sets of remote data distinguishing characteristics, wherein determining each set of remote data distinguishing characteristics includes:
setting the set of first data distinguishing characteristics for the remote data chunk to be the mathematical hash values for each of the shifted data portions, wherein a minimum geographic and/or positional spread between the distinguishing characteristics is enforced;
comparing, at the remote location using a remote computer, a plurality of the sets of first data distinguishing characteristics to one or more sets of remote data distinguishing characteristics, and identifying one or more remote data chunks of remote data stored at the remote location that are similar to the first data, wherein the one or more remote data chunks is determined to be similar to the first data when a number of matching distinguishing characteristics is found in the respective sets of distinguishing characteristics for the first and remote chunks which exceeds a similarity threshold; and
39. The medium of claim 38, wherein:
40. The medium of claim 38, wherein the subset of hash values associated with the remote data are selected based on: k maximum hash values, k minimum hash values, k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values, wherein each set of remote data distinguishing characteristics associated with each remote data chunk has no more than n distinguishing characteristics, wherein n is less than or equal to k, k being a predetermined number that is smaller than a total number of the mathematical hash values calculated for the associated portion of the remote data.
41. The medium of claim 38, further comprising:
a local data repository coupled to the processor,
wherein the processor and the memory are configured to perform a method comprising a similarity search followed by an identity comparison:
receiving sets of first data distinguishing characteristics from a first location, the sets of first data distinguishing characteristics comprising a set of distinguishing characteristics associated with each of a plurality of first data chunks of first data stored at the first location;
determining one or more sets of local data distinguishing characteristics, wherein determining each set of local data distinguishing characteristics includes:
calculating a mathematical hash value of each portion of data in local data chunk;
determining a subset of k hash values from the calculated mathematical hash values, k being a predetermined number that is smaller than a total number of the calculated mathematical hash values calculated for each portion of the data in the local data chunk;
setting the mathematical hash values for each of the shifted data portions to be the set of distinguishing characteristics for the local data chunk to obtain a more uniform probabilistic distribution than would be obtained using the data portions corresponding to the k hash values, wherein the one or more sets of local distinguishing characteristics are robust and well spread over the local data chunk;
comparing a plurality of the sets of first data distinguishing characteristics to one or more sets of the local data distinguishing characteristics to identify one or more local data chunks of local data stored in the local data repository that are similar to the first data, wherein the one or more local data chunks is determined to be similar to the first data when a number of matching distinguishing characteristics is found in the respective sets of distinguishing characteristics for the first and local chunks which exceeds a similarity threshold; and
using the determined similar data chunks, determining via communication with the first location, one or more differences between the first data and the identified similar local data without receiving all of the first data at the local data repository.
the differences between the first data and the identified similar local data are determined without transmitting all of the identified similar local data to the first location.
44. The system of claim 42, wherein the subset of hash values associated with the local data are selected based on: k maximum hash values, k minimum hash values, k hash values closest to a median of all the hash values, k hash values closest to a predetermined constant, or a sum of pairs of hash values, wherein each set of local data distinguishing characteristics associated with each local data chunk has no more than n distinguishing characteristics, wherein n is less than or equal to k, k being a predetermined number that is smaller than a total number of the mathematical hash values calculated for the associated portion of the local data.
updating the local data repository with the one or more determined differences.
46. A computer-readable storage medium encoded with instructions that causes a computer to perform a method comprising a similarity search followed by an identity comparison:
receiving, at a local location, sets of first data distinguishing characteristics from a first location, the sets of first data distinguishing characteristics comprising a set of distinguishing characteristics associated with each of a plurality first data chunks of first data stored at the first location;
calculating a mathematical hash value of each portion of data in the local data chunk;
setting the mathematical hash values for each of the shifted data portions to be the set of data distinguishing characteristics for the local data chunk, wherein a minimum geographic and/or positional spread between the distinguishing characteristics is enforced;
comparing a plurality of the sets of first data distinguishing characteristics to one or more sets of local data distinguishing characteristics to identify one or more local data chunks of local data stored at a local repository that are similar to the first data, wherein the one or more local data chunks is determined to be similar to the first data when a number of matching distinguishing characteristics is found in the respective sets of distinguishing characteristics for the first and local chunks which exceeds a similarity threshold; and
using the determined similar data chunks determining via communication with the first location, one or more differences between the first data and the identified similar local data, all of the first data being received at the local location.
48. The medium of claim 46, wherein a more uniform probabilistic distribution is obtained than would be obtained using the data portions corresponding to the k hash values.
updating the local repository with the one or more determined differences.
US11/194,086 2004-09-15 2005-07-29 Systems and methods for searching of storage data with reduced bandwidth requirements Expired - Fee Related US8725705B2 (en)
BRPI0515335-2A BRPI0515335A (en) 2004-09-15 2005-09-15 systems and methods for research and data storage
US10/941,632 Continuation-In-Part US7523098B2 (en) 2004-09-15 2004-09-15 Systems and methods for efficient data searching, storage and reduction
US20060059207A1 US20060059207A1 (en) 2006-03-16
US8725705B2 true US8725705B2 (en) 2014-05-13
ID=35431554
US11/194,086 Expired - Fee Related US8725705B2 (en) 2004-09-15 2005-07-29 Systems and methods for searching of storage data with reduced bandwidth requirements
US (1) US8725705B2 (en)
EP (2) EP1805664A1 (en)
JP (1) JP4939421B2 (en)
AU (1) AU2005284737B2 (en)
BR (1) BRPI0515335A (en)
CA (1) CA2581065C (en)
WO (1) WO2006032049A1 (en)
US20170286233A1 (en) * 2016-03-29 2017-10-05 International Business Machines Corporation Similarity based deduplication for secondary storage
US10366072B2 (en) * 2013-04-05 2019-07-30 Catalogic Software, Inc. De-duplication data bank
2005-07-29 US US11/194,086 patent/US8725705B2/en not_active Expired - Fee Related
2005-09-15 CA CA2581065A patent/CA2581065C/en active Active
2005-09-15 AU AU2005284737A patent/AU2005284737B2/en not_active Ceased
2005-09-15 WO PCT/US2005/033363 patent/WO2006032049A1/en active Application Filing
2005-09-15 EP EP05797642A patent/EP1805664A1/en not_active Withdrawn
2005-09-15 JP JP2007532557A patent/JP4939421B2/en active Active
2005-09-15 EP EP08153870A patent/EP1962209A3/en not_active Withdrawn
2005-09-15 BR BRPI0515335-2A patent/BRPI0515335A/en not_active Application Discontinuation
"How Rsync Works a Practial Overview", http://samba.anu.edu.au/rsync/how-rsync-works.html.
Amir et al., "Faster algorithms for string matching with k mismatches," Journal of Algorithms, 50(2):257-275, (2004).
Boyer et al., "A fast string searching algorithm," Communications of the ACM, 20:762-772, (1977).
Carol, "Laplink User Guide Version 11.0", Sep. 2001, p. 2-160, . *
Carol, "Laplink User Guide Version 11.0", Sep. 2001, p. 2-160, <Retrieved from Examiner Files Feb. 3, 2009>. *
European Communication from application No. 08153870.4 dated Aug. 4, 2009.
European Communication from application No. 08153870.4 dated May 3, 2010.
European Examination Report from application No. 05 797 642.5-2201 mailed on May 3, 2010.
European Examination Report from application No. 08 153 870.4-2201 mailed on May 3, 2010.
Examiner's Answer from U.S. Appl. No. 12/407,774 dated Jan. 9, 2013.
Examiner's Answer from U.S. Appl. No. 12/407,779 dated Aug. 8, 2012.
Final Office Action from U.S. Appl. No. 10/941,632 dated Oct. 28, 2008.
Fischer et al., "String matching and other products, in Complexity of Computation," SIAM-AMS Proceedings, 7:113-125, (1974).
Gilfillan. Table Types in MySQL: Part 1-HEAP Tables [online], [retrieved on 2007-02-161. Retrieved from the Internet:. *
Gilfillan. Table Types in MySQL: Part 1—HEAP Tables [online], [retrieved on 2007-02-161. Retrieved from the Internet:<URL: http:|/www.databasejournal.comMeatures|mysqllprint.php/3077531 >. *
J. Hunt et al, "Delta Algorithms: An Empirical Analysis", Apr. 1988, ACM Trans. on Software Engineering and Methodology, p. 192-214, . *
J. Hunt et al, "Delta Algorithms: An Empirical Analysis", Apr. 1988, ACM Trans. on Software Engineering and Methodology, p. 192-214, <Retrieved from Examiner files Feb. 3, 2009>. *
J. MacDonald, "File System Support for Delta Compression", Aug. 2000, Univ of California, Berkeley, 32 pages, . *
J. MacDonald, "File System Support for Delta Compression", Aug. 2000, Univ of California, Berkeley, 32 pages, <Retrieved from Examiner Files Feb. 3, 2009>. *
Knuth et al., "Fast pattern matching in strings," SIAM Journal on Computing, 6:323-350, (1977).
Landau et al., "Fast parallel and serial approximate string matching," Journal of Algorithms, 10(2):157-169, (1989).
Non-Final Office Action from U.S. Appl. No. 10/941,632 dated Dec. 12, 2007.
Non-Final Office Action from U.S. Appl. No. 10/941,632 dated Mar. 18, 2008.
Non-Final Office Action from U.S. Appl. No. 10/941,632 dated Mar. 8, 2007.
Non-Office Action Summary from U.S. Appl. No. 10/941,632 dated Mar. 8, 2007.
Notice of Allowance and Fee(s) Due from U.S. Appl. No. 10/941,632 dated Dec. 10, 2008.
Office Communication from European Application No. 08153870.4 dated Aug. 4, 2009.
Packetsoft, "RTPatch Professional Products", Nov. 12, 2001, 18 pages, . *
Packetsoft, "RTPatch Professional Products", Nov. 12, 2001, 18 pages, <Retrieved from Examiner files Feb. 3, 2009>. *
S. Otlu, "A New Technique: Replace Algorithm to Retrieve a Version From a Repository Instead of Delta Application", Apr. 2004, Thesis, MS, Middle East Tech. University, 83 pages, . *
S. Otlu, "A New Technique: Replace Algorithm to Retrieve a Version From a Repository Instead of Delta Application", Apr. 2004, Thesis, MS, Middle East Tech. University, 83 pages, <Retrieved from Examiner files Feb. 3, 2009>. *
Schleimer, Saul; Wilkerson, Daniel; Aiken, Alex, "Winnowing: Local Algorithms for Document Fingerprinting," pp. 76-85, SIGMOD 2003, Jun. 9-12, 2003, San Diego, CA. *
Tretau et at. IBM Tivoli Storage Management Concepts [online]. IBM Corp., 2003 [retrieved on 2007-02-141. Retrieved from the Internet: Chapter 6.4. *
Tretau et at. IBM Tivoli Storage Management Concepts [online]. IBM Corp., 2003 [retrieved on 2007-02-141. Retrieved from the Internet:< URL: http:|/proquest.safaribooksonline.com|0738499617 > Chapter 6.4. *
Ukkonen, "On-line construction of suffix trees," Algorithmica, 14(3):249-260, (1995).
Weiner, "Linear pattern matching algorithm," Proceedings of the 14th IEEE Symposium on Switching and Automata Theory, pp. 1-11, (1973).
EP1805664A1 (en) 2007-07-11
AU2005284737A1 (en) 2006-03-23
EP1962209A2 (en) 2008-08-27
BRPI0515335A (en) 2008-07-22
JP4939421B2 (en) 2012-05-23
EP1962209A3 (en) 2009-01-07
WO2006032049A1 (en) 2006-03-23
CA2581065A1 (en) 2006-03-23
AU2005284737B2 (en) 2011-03-10
JP2008513891A (en) 2008-05-01
US20060059207A1 (en) 2006-03-16
CA2581065C (en) 2014-03-11
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:HIRSCH, MICHAEL;BITNER, HAIM;ARONOVICH, LIOR;AND OTHERS;REEL/FRAME:017229/0596;SIGNING DATES FROM 20050920 TO 20051111
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:HIRSCH, MICHAEL;BITNER, HAIM;ARONOVICH, LIOR;AND OTHERS;SIGNING DATES FROM 20050920 TO 20051111;REEL/FRAME:017229/0596