File versions within content addressable storage
AssigneeInternational Business Machines Corporation
InventorsAhmed Gheith, Eric Van Hensbergen, James Xenidis
Life of this patent
Estimating the term…
Abstract
A request to access to a logical location in a file stored in a content addressable storage (CAS) system can be processed by retrieving first tree data from a first node in a first hash tree that represents a first version of the file. Based on the first tree data, a second node is selected from which a CAS signature is compared to a reserved CAS signature to determine the proper file version. In response to a match, a third node is accessed in a second hash tree that represents a second version of the file. Tree data is retrieved from a third node.
Claims20
A computer-implemented method for processing a request to access a logical location in a file stored in a non-transitory content addressable storage (CAS) system, the computer-implemented method comprising:
- retrieving, in response to the request, first tree data from a first node in a first hash tree that represents a first version of the file, the first tree data including a first hash tree depth, a first CAS signature, a block size and a file size;
- selecting, based on the first tree data, a second node from a higher level in the first hash tree;
- retrieving second tree data from the second node in the first hash tree that represents the first version of the file, the second tree data including a second CAS signature;
- determining that the second CAS signature matches a reserved CAS signature, wherein the reserved CAS signature represents a second version of the file;
- retrieving, in response to determining the second CAS signature matches the reserved CAS signature, a third node in a second hash tree corresponding to the second node in the first hash tree, wherein the second hash tree represents the second version of the file;
- retrieving third tree data from the third node in the second hash tree, the third tree data including a third hash tree depth, a third CAS signature, the block size and the file size;
- and
- traversing, based on the third tree data, the second hash tree to a leaf node corresponding to the logical location of the request;
- and
- transferring a data block corresponding to the leaf node of the second version of the file, and corresponding to the logical location of the request from the CAS system, to a second non-transitory computer readable storage medium.
A system for storing content addressable storage (CAS) signatures for different versions of a file, the system comprising:
- a client device configured with a non-transitory computer readable storage medium, a client interface module, and a processor that is configured to:
- generate a first hash tree for a first version of the file, the first hash tree having a first root CAS signature that is encoded with a depth for the first hash tree, a block size for the first hash tree and a file size for the file;
- and
- generate a second hash tree for a second version of the file by:
- categorizing, relative to corresponding blocks in the first version of the file, a first set of one or more blocks in the second version of the file as modified and a second set of one or more blocks in the second version as unmodified,
- generating a first level of CAS signatures for the second hash tree by:
- applying a hash function to the first set of one or more blocks categorized as modified, and
- applying a common CAS signature to the second set of one or more blocks categorized as unmodified, wherein the common CAS signature represents the first version of the file;
- generating a second root CAS signature from the first level of CAS signatures, the second root CAS signature encoded with a depth for the second hash tree, a block size for the second hash tree and a file size for the file;
- and
- store the first hash tree and the second hash tree in the non-transitory computer readable storage medium, wherein the processor is further configured to restore one or more versions of the file responsive to a request from the client interface module.
A computer program product for accessing data from a non-transitory content addressable storage (CAS) system storing different versions of a file, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to:
- retrieve, in response to a request to access a logical location of the file, first tree data from a first node in a first hash tree that represents a first version of the file, the first tree data including a first hash tree depth, a first CAS signature, a block size and a file size;
- select, based on the first tree data, a second node from a higher level in the first hash tree;
- retrieve second tree data from the second node in the first hash tree that represents the first version of the file, the second tree data including a second CAS signature;
- determine that the second CAS signature matches a reserved CAS signature, wherein the reserved CAS signature represents a second version of the file;
- retrieve, in response to determining the second CAS signature matches the reserved CAS signature, a third node in a second hash tree corresponding to the second node in the first hash tree that represents the second version of the file;
- retrieve third tree data from the third node in the second hash tree, the third tree data including a third hash tree depth, a third CAS signature, the block size and the file size;
- traverse, based on the third tree data, the second hash tree to a top-level node corresponding to the request to access the logical location;
- and
- output a block corresponding to the top-level node responsive to the request.
A computer program product for storing content addressable storage (CAS) signatures for different versions of a file, the computer program product comprising a computer readable storage medium, having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to:
- generate a first hash tree for a first version of the file, the first hash tree having a first root CAS signature that is encoded with a depth for the first hash tree, a block size for the first hash tree and a file size for the file;
- and
- generate a second hash tree for a second version of the file by:
- categorizing, relative to corresponding blocks in the first version of the file, a first set of one or more blocks in the second version of the file as modified and a second set of one or more blocks in the second version as unmodified,
- generating a first level of CAS signatures for the second hash tree by:
- applying a hash function to the first set of one or more blocks categorized as modified, and
- applying a common CAS signature to the second set of one or more blocks categorized as unmodified, wherein the common CAS signature represents the first version of the file;
- generating a second root CAS signature from the first level of CAS signatures, the second root CAS signature encoded with a depth for the second hash tree, a block size for the second hash tree and a file size for the file;
- and
- store the first hash tree and the second hash tree, wherein the program instructions are further configured to cause the processor to restore one or more versions of the file responsive to a request.
Dependencies are inferred from the claim text.