# US 10,372,678 B2 · Files having unallocated portions within content addressable storage > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,372,678 B2 - Document ID: US10372678B2 - Status: Granted - Kind: B2 - Application number: 15/270,462 - Filed: 2016-09-20 - Published: 2017-01-12 - Granted: 2019-08-06 - Earliest claimed: 2013-12-06 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: Ahmed Gheith; Eric Van Hensbergen; James Xenidis - Web page: https://patentgrep.com/patent/US10372678B2 ## CPC - G06F 16/1727: {Details of free space management performed by the file system (saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064)} - G06F 3/061: {Improving I/O performance} - G06F 3/064: {Management of blocks} - G06F 3/0643: {Management of files} - G06F 3/0673: {Single storage device} - G06F 16/13: File access structures, e.g. distributed indices (arrangements of input from, or output to, record carriers G06F3/06) - G06F 16/152: {using file content signatures, e.g. hash values} - G06F 16/182: Distributed file systems - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A request to access to a logical location in a file stored in a content addressable storage (CAS) system can be handled by retrieving first tree data from a first node in a hash tree that represents the file, the first tree data including a first hash tree depth, a first CAS signature, a block size and a file size. Based on the tree data, a second node is selected from a higher level in the hash tree. Second tree data from the second node of the hash tree that represents the file is retrieved, including a second CAS signature. The second CAS signature is determined to match a reserved CAS signature, and in response, an indication that the requested logical location is unallocated within the file is provided. ## Claims ### Claim 1 A computer-implemented method for transferring a portion of a file stored in a non-transitory content addressable storage (CAS) system to a second non-transitory computer readable storage medium, the computer-implemented method comprising: retrieving, in response to a request for the portion of the file, first tree data from a first node in a hash tree that represents the file, the first tree data including a first hash tree depth, a first CAS signature, a block size and a file size, wherein the first node represents a set of data blocks corresponding to the portion of the file; selecting, based on the tree data, a second node from a higher level in the hash tree, wherein the second node represents a subset of data blocks represented by the first node; retrieving second tree data from the second node of the hash tree that represents 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 one or more unallocated data blocks; and providing, to the second non-transitory computer readable storage medium and in response to the request, and in response to determining the second CAS signature matches the reserved CAS signature, an indication that the file contains one or more unallocated data blocks; and transferring a set of data blocks corresponding to the requested portion of the file from the CAS system and to the second non-transitory computer readable storage medium, wherein the set of data blocks does not include the subset of data blocks corresponding to the second node and encoded with the reserved CAS signature. ### Claim 2 (depends on 1) The method of claim 1, wherein the file is a disk image that corresponds to a file system with allocated and unallocated portions. ### Claim 3 (depends on 1) The method of claim 1, wherein selecting a second node from a higher level in the hash tree includes: identifying a data block within the requested portion of the file; and determining, based upon the data block, a path through the hash tree from the first node to the second node, wherein the second node represents one or more data blocks including the identified data block. ### Claim 4 (depends on 1) The method of claim 1, wherein the reserved CAS signature is a predetermined binary number. ### Claim 5 (depends on 4) The method of claim 4, wherein the reserved CAS signature is zero. ### Claim 6 (depends on 1) The method of claim 1, wherein retrieving the first tree data includes sending a request to a CAS datacenter. ### Claim 7 (depends on 6) The method of claim 6, further wherein the request is sent to a web accessible interface of the CAS datacenter. ### Claim 8 A system for generating a content addressable storage (CAS) signature for a file having allocated and unallocated blocks, the system comprising: a client device configured with a client interface module, a non-transitory computer readable storage medium, and a processor that is configured to: generate a first level of CAS signatures by: applying a hash function to allocated blocks of the file to generate CAS signatures, and applying a common CAS signature, wherein the common CAS signature represents one or more unallocated blocks, to each unallocated block; encoding the first level of CAS signatures with a hash tree depth for the first level of CAS signatures, a block size and a file size; and generate a second level of one or more CAS signatures by: combining the first level of CAS signatures into groups, applying a hash function to groups of combined CAS signatures that are derived from at least one allocated block, applying the common CAS signature to at least one group with unallocated blocks, encoding the second level of CAS signatures with a hash tree depth for the second level of CAS signatures, the block size and the file size; and store the first level of CAS signatures and the second level of one or more CAS signatures in the non-transitory computer readable storage medium; wherein the processor is configured to, responsive to a request from the client interface module to restore the file, output a set of blocks corresponding to the file; and wherein the set of blocks does not contain any block encoded with the common CAS signature. ### Claim 9 (depends on 8) The system of claim 8, wherein the file is a disk image that corresponds to a file system with allocated and unallocated portions. ### Claim 10 (depends on 9) The system of claim 9, further comprising determining whether the blocks of the file are allocated or unallocated based upon directory information corresponding to the file system. ### Claim 11 (depends on 8) The system of claim 8, wherein the common CAS signature is a predetermined bit value. ### Claim 12 (depends on 8) The system of claim 8, further comprising generating a root CAS signature for the hash tree. ### Claim 13 (depends on 8) The system of claim 8, wherein the common CAS signature is a predetermined binary number. ### Claim 14 (depends on 13) The system of claim 13, wherein the common CAS signature is zero. ### Claim 15 (depends on 8) The system of claim 8, wherein the client device comprises at least one computer of a CAS datacenter. ### Claim 16 A computer program product for loading a file from a content addressable storage (CAS) system having allocated and unallocated blocks, 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, responsive to a request for the file, first tree data from a first node in a hash tree that represents the file, the first tree data including a first hash tree depth, a first CAS signature, a block size and a file size; retrieve respective tree data from respective higher nodes of the hash tree that represents the file, the respective tree data including respective CAS signatures; determine that at least one respective CAS signature corresponding to a respective node matches a reserved CAS signature, wherein the reserved CAS signature represents one or more unallocated blocks; and output, in response to retrieving respective tree data, a set of blocks corresponding to a set of nodes in the hash tree that represents the file, wherein the set of blocks does not include respective blocks corresponding to respective nodes having a CAS signature matching the reserved CAS signature. ### Claim 17 (depends on 16) The computer program product of claim 16, wherein the program instructions are further configured to cause the processor to: receive a file to store; generate a first level of CAS signatures representing respective blocks of the file by: applying a hash function to allocated blocks of the file to generate CAS signatures, and applying a reserved CAS signature to each unallocated block; encode the first level of CAS signatures with a hash tree depth for the first level of CAS signatures, the block size and the file size; generate a second level of one or more CAS signatures by: combining the first level of CAS signatures into groups, applying a hash function to groups of combined CAS signatures that are derived from at least one allocated block, and applying the reserved CAS signature to at least one group with unallocated blocks; and encode the second level of CAS signatures with a hash tree depth for the second level of CAS signatures, the block size and the file size; and store the first level of CAS signatures and the second level of CAS signatures. ### Claim 18 (depends on 17) The computer program product of claim 17, wherein the program instructions are further configured to cause the processor to: generate additional levels of one or more CAS signatures until a root CAS signature is generated, wherein the root CAS signature comprises a CAS signature representing the file; and store the root CAS signature and all respective CAS signatures of all respective levels. ### Claim 19 (depends on 16) The computer program product of claim 16, wherein the program instructions configured to cause the processor to retrieve respective tree data from respective higher nodes of the hash tree are further configured to cause the processor to: in response to determining that a respective CAS signature of a respective node matches the reserved CAS signature, selecting a different respective node higher than the first node and not associated with a previously selected node having a CAS signature matching the reserved CAS signature; and in response to determining that the CAS signature of a respective node does not match the reserved CAS signature, and in response to determining that the respective node is a top level node, retrieving a block associated with the respective node. ### Claim 20 A computer program product for generating a content addressable storage (CAS) signature for a file having allocated and unallocated blocks, 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 level of CAS signatures by: applying a hash function to allocated blocks of the file to generate CAS signatures, and applying a common CAS signature, wherein the common CAS signature represents one or more unallocated blocks, to each unallocated block; encoding the first level of CAS signatures with a hash tree depth for the first level of CAS signatures, a block size and a file size; and generate a second level of one or more CAS signatures by: combining the first level of CAS signatures into groups, applying a hash function to groups of combined CAS signatures that are derived from at least one allocated block, applying the common CAS signature to at least one group with unallocated blocks, encoding the second level of CAS signatures with a hash tree depth for the second level of CAS signatures, the block size and the file size; and store the first level of CAS signatures and the second level of one or more CAS signatures; wherein the program instructions are configured to cause the processor to, responsive to a request, output a set of blocks corresponding to the file; and wherein the set of blocks does not contain any block encoded with the common CAS signature.