Content addressable data storage and compression for computer memory
First Claim
Patent Images
1. A method of content addressable data storage and compression for computer memory comprising:
- searching at a repeating memory interval through a search section of a chunk for a segment of the chunk that matches a memory block from computer memory, including;
calculating a weak checksum for the memory block;
calculating rolling weak checksums for segments of the search section of the chunk;
comparing the rolling weak checksums for the segments with the checksum for the memory block; and
if a segment is found with a rolling weak checksum equal to the weak checksum of the memory block;
calculating a strong checksum for the memory block;
calculating a strong checksum for the segment with the matching rolling weak checksum;
comparing the strong checksum of the memory block and the strong checksum for the segment with the equal rolling weak checksum;
determining that the search has found a segment having contents that match the contents of the memory block if the strong checksum of the memory block and the strong checksum for the segment with the matching wiling weak checksum are equal;
if a matching segment is found;
discarding the matching segment and providing a retrieval key for the memory block as a retrieval key for the matching segment;
identifying an unmatched portion of the chunk that does not match the memory block; and
storing the unmatched portion and providing a retrieval key for the unmatched portion.
1 Assignment
0 Petitions
Accused Products
Abstract
Methods, systems, and products of content addressable data storage and compression for computer memory are disclosed as providing a chunk of data comprising a quantity of input data; retrieving a memory block from computer memory; searching for a segment of the chunk that matches the memory block; and if a matching segment is found: discarding the matching segment and providing a retrieval key for the memory block as a retrieval key for the matching segment; identifying an unmatched portion of the chunk that does not match the memory block; and storing the unmatched portion and providing a retrieval key for the unmatched portion.
-
Citations
42 Claims
-
1. A method of content addressable data storage and compression for computer memory comprising:
-
searching at a repeating memory interval through a search section of a chunk for a segment of the chunk that matches a memory block from computer memory, including;
calculating a weak checksum for the memory block;
calculating rolling weak checksums for segments of the search section of the chunk;
comparing the rolling weak checksums for the segments with the checksum for the memory block; and
if a segment is found with a rolling weak checksum equal to the weak checksum of the memory block;
calculating a strong checksum for the memory block;
calculating a strong checksum for the segment with the matching rolling weak checksum;
comparing the strong checksum of the memory block and the strong checksum for the segment with the equal rolling weak checksum;determining that the search has found a segment having contents that match the contents of the memory block if the strong checksum of the memory block and the strong checksum for the segment with the matching wiling weak checksum are equal; if a matching segment is found; discarding the matching segment and providing a retrieval key for the memory block as a retrieval key for the matching segment; identifying an unmatched portion of the chunk that does not match the memory block; and storing the unmatched portion and providing a retrieval key for the unmatched portion. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A system of content addressable data storage and compression for computer memory comprising:
-
means for searching at a repeating memory interval through a search section of a chunk for a segment of the chunk that matches a memory block from computer memory, including means for;
calculating a weak checksum for the memory block;
calculating rolling weak checksums for segments of the search section of the chunk;
comparing the rolling weak checksums for the segments with the checksum for the memory block; and
if a segment is found with a rolling weak checksum equal to the weak checksum of the memory block;
calculating a strong checksum for the memory block;
calculating a strong checksum for the segment with the matching rolling weak checksum;
comparing the strong checksum of the memory block and the strong checksum for the segment with the equal rolling weak checksum;means for determining that the search has found a segment having contents that match the contents of the memory block if the strong checksum of the memory block and the strong checksum for the segment with the matching rolling weak checksum are equal; means for discarding a matching segment and providing a retrieval key for the memory block as a retrieval key for the matching segment; means for identifying an unmatched portion of the chunk that does not match the memory block; and means for storing the unmatched portion and providing a retrieval key for the unmatched portion. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
-
-
29. A computer program product of content addressable data storage and compression for computer memory comprising:
-
a recording medium; means, recorded on die recording medium, for searching at a repeating memory interval through a search section of a chunk for a segment of the chunk that matches a memory block from computer memory, including means, recorded on the recording medium, for;
calculating a weak checksum for the memory block;calculating rolling weak checksums for segments of the search section of the chunk;
comparing the rolling weak checksums for the segments with the checksum for the memory block; and
if a segment is found with a rolling weak checksum equal to the weak checksum of the memory block;
calculating a strong checksum for the memory block;
calculating a strong checksum for the segment with the matching rolling weak checksum;
comparing the strong checksum of the memory block and the strong checksum for the segment with the equal rolling weak checksum;means, recorded on the recording medium, for determining that the search has found a segment having contents that match the contents of the memory block if the strong checksum of the memory block and the strong checksum for the segment with the matching rolling weak checksum are equal; means, recorded on the recording medium, for discarding a matching segment and providing a retrieval key for the memory block as a retrieval key for the matching segment; means, recorded on the recording medium, for identifying an unmatched portion of the chunk that does not match the memory block; and means, recorded on the recording medium, for storing the unmatched portion and providing a retrieval key for the unmatched portion. - View Dependent Claims (30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42)
-
Specification