Methods and systems for vectored data de-duplication
View Patent ↗The present invention is directed toward methods and systems for data de-duplication. More particularly, in various embodiments, the present invention provides systems and methods for data de-duplication that may utilize a vectoring method for data de-duplication wherein a stream of data is divided into “data sets” or blocks. For each block, a code, such as a hash or cyclic redundancy code may be calculated and stored. The first block of the set may be written normally and its address and hash can be stored and noted. Subsequent block hashes may be compared with previously written block hashes.
1. A method of data de-duplication, comprising:
determining a code for a block of data being processed;
comparing the code for the block of data being processed to a code for a previously processed block of data;
upon determining that the code for the block of data being processed matches the code for the previously processed block of data, storing a vector in a block of memory allocated for the block of data being processed, where the vector points to the previously processed block of data, where the vector contains fewer bits than the previously processed block of data, where the vector does not contain the code, and where the vector contains fewer bits than the block of memory allocated for the block of data being processed, and
configuring the block of memory allocated for the block of data being processed to store additional data, the additional data being separate from and not a part of the vector.
2. The method of claim 1 , where the code for the block of data being processed and the code for the previously processed block of data are determined using a hash function.
3. The method of claim 1 , where the code for the block of data being processed and the code for the previously processed block of data comprise a cyclic redundancy code.
4. The method of claim 1 , comprising dividing an incoming data stream into blocks of data.
5. The method of claim 4 , where blocks of data comprise the same number of bits.
6. The method of claim 1 , comprising comparing the block of data being processed to the previously processed block of data when the code for the block of data being processed matches the code for the previously processed block of data.
7. The method of claim 6 , where comparing the block of data being processed to the previously processed block of data comprises calculating additional codes for the block of data being processed and the previously processed block of data and comparing the additional codes.
8. The method of claim 7 , where the additional codes comprise codes made up of more bits than the codes used in the first comparison.
9. The method of claim 1 , where the vector comprises a pointer to a previous physical block.
10. The method of claim 1 , where the vector comprises a pointer to a previous logical block.
11. The method of claim 10 , where the vector comprises a start address and an offset.
12. A data de-duplication device, comprising:
a data receiving device configured to receive a stream of data;
a data processing device configured to:
determine a code for a block of data being processed;
compare the code for the block of data being processed to a code for a previously processed block of data;
upon determining that the code for the block of data being processed matches the code for the previously processed block of data, to store a vector in a block of memory allocated for the block of data being processed, where the vector points to the previously processed block of data, where the vector contains fewer bits than the previously processed block of data, and where the vector contains fewer bits than the block of memory allocated for the block of data being processed to store additional data; and
configure the block of memory allocated for the block of data being processed to store additional data associated with a different block of data.
13. The data de-duplication device of claim 12 , where the data processing device determines the code for the block of data being processed and the code for the previously processed block of data using a hash function.
14. The data de-duplication device of claim 12 , where the data processing device determines the code for the block of data being processed and the code for the previously processed block of data using a cyclic redundancy code.
15. The data de-duplication device of claim 12 , where the data processing device divides an incoming data stream into blocks of data.
16. The data de-duplication device of claim 15 , where the data processing device divides the incoming data stream into blocks of data comprising the same number of bits.
17. The data de-duplication device of claim 12 , where the data processing device compares the block of data being processed to the previously processed block of data when the code for the block of data being processed and the code for the previously processed block of data match.
18. The data de-duplication device of claim 17 , where the data processing device compares the block of data being processed to the previously processed block of data by calculating additional codes for the block of data being processed and the previously processed block of data and comparing the additional codes.
19. The data de-duplication device of claim 18 , where the additional codes calculated by the processing device comprise codes made up of more bits than the codes used in the first comparison.
20. The data de-duplication device of claim 12 , where the vector comprises a pointer to a previous physical block.
21. The data de-duplication device of claim 12 , where the vector comprises a pointer to a previous logical block.
22. The data de-duplication device of claim 12 , where the vector further comprises a start address and an offset.
23. The data de-duplication device of claim 12 , where the data processing device comprises one of, a disk drive and a tape drive.
24. The data de-duplication device of claim 12 , where the data associated with the different block of data is a vector associated with the different block of data.
25. The data de-duplication device of claim 12 , where the data processing device comprises a virtual tape drive.
26. A data de-duplication system, comprising:
a data transmission device configured to transmit a stream of data;
a data storage device configured to store blocks of data and codes for blocks of data;
a data de-duplication device comprising:
a data receiving device configured to receive the stream of data;
a data processing device, configured to:
determine a code for a block of data being processed;
compare the code for the block of data being processed to a code for a previously processed block of data;
upon determining that the code for the block of data being processed matches the code for the previously processed block of data, to store a vector in a block of memory allocated for the block of data being processed, where the vector points to the previously processed block of data, where the vector contains fewer bits than the previously processed block of data, and where the vector contains fewer bits than the block of memory allocated for the block of data being processed to store additional data; and
configure the block of memory allocated for the block of data being processed to store additional data associated with one or more additional blocks of data.
27. The data de-duplication system of claim 26 , where the data processing device determines the code for the block of data being processed and the code for the previously processed block of data using a hash function.
28. The data de-duplication system of claim 26 , where the data processing device determines the code for the block of data being processed and the code for the previously processed block of data using a cyclic redundancy code.
29. The data de-duplication system of claim 26 , where the data processing device divides an incoming data stream into blocks of data.