Transparent content addressable data storage and compression for a file system

A system of transparent content addressable data storage and compression for a file system comprising:

• means for providing a data structure that associates file identifiers and retrieval keys for memory blocks for storing file contents;
• means for storing in the data structure one or more file identifiers;
• 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 black;
• 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, means for providing a retrieval key for the memory block as a retrieval key for the matching segment, and means for storing in the data structure the retrieval key for the matching segment in association with a file identifier;
• and
• means for identifying an unmatched portion of the chunk that does not match the memory block, means for storing the unmatched portion, means for providing a retrieval key for the unmatched portion, and means for storing in the data structure the retrieval key for the unmatched portion in association with the file identifier.

A computer program product of transparent content addressable data storage and compression for a file computer program product comprising:

• a recording medium;
• means, recorded on the recording medium, for providing a data structure tat associates file identifiers and retrieval keys for memory blocks for storing file contents;
• means, recorded on the recording medium, for storing in the data structure one or more file identifiers;
• means, recorded on the recording medium, far 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, means, recorded on the recording medium, for providing a retrieval key for the memory block as a retrieval key for the matching segment, and means, recorded on the recording medium, for storing in the data structure the retrieval key for the matching segment in association with a file identifier;
• and
• means, recorded on the recording medium, for identifying an unmatched portion of the chunk that does not match the memory block, means, recorded on the recording medium, for storing the unmatched portion, means, recorded on the recording medium, for providing a retrieval key for the unmatched portion, and means, recorded on the recording medium, for storing in the data structure the retrieval key for the unmatched portion in association with the file identifier.