Back to results
US 9,141,554 B1Granted
Methods and apparatus for data processing using data compression, linked lists and de-duplication techniques
AssigneeCisco Technology, Inc.
InventorJames Candelaria
Life of this patent
Estimating the term…
Abstract
Data processing methods and apparatus for efficiently storing and retrieving data, e.g., blocks of data, to and from memory. The data processing including, e.g., techniques such as using linked lists and/or tables for tracking duplicate data blocks received for storage, the use of lossless data compression, and de-duplication based on comparing hash values, compressed data block sizes, and/or bit by bit comparisons of the block of data to be stored and previously stored blocks of data.
Claims22
A data processing method, the method comprising:
- generating a hash value from a block of data to be stored and a hash function;
- compressing the block of data to be stored to generate a compressed block of data, said compressed block of data being of a first size;
- comparing said generated hash value to hash values corresponding to previously stored blocks of data;
- when said generated hash value matches a hash value of a previously stored block of data, determining if the block of data to be stored matches the previously stored block of data with the matching hash value, wherein the determining includes comparing said first size to the size of said previously stored block of data with the matching hash value and determining that said block of data to be stored does not match said previously stored block of data when said first size does not match the size of said stored block of data;
- and
- when it is determined that said block of data to be stored does not match a previously stored block of data, updating an existing physical block address linked list entry, for said previously stored block of data with the matching hash value, to change a next physical block address value in said existing linked list entry from null to a new physical block address indicating a physical memory location used for storing said generated compressed block of data.
3 more elements
A data processing apparatus comprising:
- a hash value generation module configured to generate a hash value from a block of data to be stored and a hash function;
- a compression module configured to compress the block of data to be stored to generate a compressed block of data, said compressed block of data being of a first size;
- a comparison module configured to compare said generated hash value to hash values corresponding to previously stored blocks of data;
- a determination module configured to determine, when a comparison performed by said comparison module indicates that said generated hash value matches a hash value corresponding to a previously stored block of data, if the block of data to be stored matches the previously stored block of data with the matching hash value, wherein said determination module includes a size comparison module configured to compare said first size to a size of said previously stored block of data with the matching hash value, and wherein said determination module determines that said block of data to be stored does not match said previously stored block of data when said size comparison module indicates that the first size does not match the size of said stored block of data;
- and
- an update module configured to update an existing physical block address linked list entry, for said previously stored block of data with the matching hash value, to change a next physical block address value in said existing linked list entry from null to a new physical block address indicating a physical memory location used for storing said generated compressed block of data, said update module being configured to perform the update when it is determined that said block of data to be stored does not match a previously stored block of data.
3 more elements
A non-transitory computer readable medium for use in a data processing apparatus, the non-transitory computer readable medium comprising:
- instructions which when executed by a computer control said apparatus to generate a hash value from a block of data to be stored and a hash function;
- instructions which when executed by the computer control said apparatus to compress the block of data to be stored to generate a compressed block of data, said compressed block of data being of a first size;
- instructions which when executed by the computer control said apparatus to compare said generated hash value to hash values corresponding to previously stored blocks of data;
- instructions which when executed by the computer control said apparatus to determine, when said generated hash value matches a hash value of a previously stored block of data, if the block of data to be stored matches the previously stored block of data with the matching hash value, wherein said instructions which control said apparatus to determine if the block of data to be stored matches the previously stored block of data with the matching hash value include instructions which when executed by the computer control said apparatus to compare said first size to the size of said previously stored block of data with the matching hash value, and wherein said apparatus determines that said block of data to be stored does not match said previously stored block of data when a comparison indicates that said first size does not match the size of said stored block of data;
- and
- instructions which when executed by the computer control said apparatus to update, when it is determined that said block of data to be stored does not match a previously stored block of data, an existing physical block address linked list entry for said previously stored block of data with the matching hash value to change a next physical block address value in said existing linked list entry from null to a new physical block address indicating a physical memory location used for storing said generated compressed block of data.
3 more elements
Dependencies are inferred from the claim text.