Out-of-core similarity matching

摘要

A method for storing data in a data storage system by partitioning the data into a plurality of data chunks and generating representative data for each of the plurality of chunks by applying a predetermined algorithm to each chunk of the plurality of chunks. Subsequently, the representative data is compared and sorted. Representative data for base data chunks and representative data for other data chunks that can be stored relative to the base data chunks are identified by evaluating the sorted set of representative data. Finally, each of the other data chunks identified as those that can be stored relative to a base data chunk are stored in the data storage system as the difference between the data chunk and a base data chunk.

主权项

1. A computer-implemented method for data deduplication, the method comprising:
in response to a request for compressing data in a data storage system, partitioning the data into a plurality of data chunks, including a target data chunk and a base data chunk; generating representative data for the target data chunk and the base data chunk by applying a predetermined algorithm to the target data chunk and the base data chunk; sorting the representative data for the target data chunk and the base data chunk based on similarity of bit patterns of the target data chunk and the base data chunk to form a sorted representative data list, wherein sorting the representative data further includes dividing representative data of the plurality of data chunks into a plurality of bin files where directly adjacent representative data of the plurality of data chunks are placed in a same bin file, each of the plurality of bin files sized to fit within main memory of a data storage system, reading into main memory each of the plurality of bin files, and comparing and sorting each of the plurality of bin files according to a first feature defined in representative data of the plurality of data chunks; generating a delta data chunk as the difference between the target data chunk and the base data chunk where the representative data of the target chunk is directly adjacent to the representative data of the base data chunk in the sorted representative data list; and storing the delta data chunk and the base data chunk in the data storage system, wherein the delta data chunk and the base data chunk represent the target data chunk.