CONTENT-ADDRESSED STORAGE USING CONTENT-DEFINED TREES
In some aspects, a computing system may generate a content-defined tree. A content-defined tree may be a tree of cryptographic hashes where each leaf is a hash of a chunk (e.g., data chunk) of a data object, and each parent node (e.g., interior node) is the hash of a concatenation of the hashes of the parent's children nodes. To create parent nodes for the leaf nodes, a computing system may group leaf nodes together based on a rolling hash (e.g., a rolling hash of the hashes of the leaf nodes) satisfying a condition. Each parent node may include a hash that represents the concatenation of the hashes of the leaf nodes that fall under the corresponding parent node.
1 . A system for using a content defined tree and a content addressed storage (CAS) tree to efficiently determine and retrieve locations of each portion of a file within a database for reconstruction of the file, the system comprising:
one or more processors; and
a non-transitory, computer readable medium having instructions recorded thereon that, when executed by the one or more processors, cause operations comprising:
obtaining a request for a file in a database, wherein the request comprises an identification of the file;
based on the request and the identification of the file, retrieving a content defined tree corresponding to the file, wherein the content defined tree comprises a set of parent nodes, each parent node corresponding to a set of hashes that have been determined using a rolling hash and a grouping condition, wherein each parent node comprises a hash of a concatenation of each hash in a corresponding set of hashes, wherein the set of parent nodes form a tier of the content defined tree, and wherein each hash in each set of hashes corresponds to a chunk in the file;
determining a first node by traversing the content defined tree;
comparing the first node with a set of CAS tree nodes;
based on a hash of the first node matching a hash of a first CAS tree node of the set of CAS tree nodes, traversing a first CAS tree corresponding to the first CAS tree node, wherein the first CAS tree comprises a set of parent nodes, wherein each parent node comprises a hash of a concatenation of each hash in a corresponding set of hashes, and wherein each hash in each set of hashes corresponds to a chunk stored in the database;
based on traversing the first CAS tree, obtaining a set of child nodes of the first CAS tree node, wherein each child node comprises a hash usable as a key to retrieve a location of a chunk of the file;
retrieving, based on the set of child nodes, a set of file chunks; and
reconstructing the file based on the set of file chunks.
2 . The system of claim 1 , wherein the instructions, when executed by the one or more processors, cause operations further comprising:
determining, based on the content defined tree and the set of CAS tree nodes, that no CAS tree exists for a portion of the file; and
based on no CAS tree existing for the portion of the file, generating a new CAS tree by:
dividing the portion of the file into a set of chunks, each chunk in the set of chunks having a boundary, wherein each boundary is determined based on a first rolling hash satisfying a first condition and each boundary defines a size of a corresponding chunk;
generating a set of hashes comprising a cryptographic hash for each chunk of the set of chunks, wherein the set of hashes form a first tier of the new CAS tree;
generating a set of parent nodes by grouping each hash of the set of hashes based on a second rolling hash satisfying a second condition, and by hashing a concatenation of each resulting group of hashes, wherein the set of parent nodes form a second tier of the content defined tree, wherein a first parent node of the set of parent nodes comprises a hash that is usable as a key to retrieve each hash in a group of hashes that corresponds to the first parent node; and
storing the new CAS tree and the portion of the file in the database.
3 . The system of claim 2 , wherein the instructions, when executed by the one or more processors, cause operations further comprising:
based on determining that the portion of the file is greater than a threshold size, causing generation of the new CAS tree to use a first subpart of the portion of the file that is less than the threshold size; and
generating a second new CAS tree using a second subpart of the portion of the file, wherein content of the first subpart does not overlap with the second subpart.
4 . The system of claim 1 , wherein each parent node of the first CAS tree comprises a hash that may be used to index to one or more locations in the database where a corresponding chunks is stored.
5 . A method for using a content defined tree and a content addressed storage (CAS) tree to efficiently determine and retrieve locations of each portion of a file within a database for reconstruction of the file, the method comprising:
obtaining a request for a file in a database, wherein the request comprises an identification of the file;
based on the request and the identification of the file, retrieving a content defined tree corresponding to the file;
determining a first node by traversing the content defined tree;
comparing the first node with a set of CAS tree nodes;
based on a hash of the first node matching a hash of a first CAS tree node of the set of CAS tree nodes, traversing a first CAS tree corresponding to the first CAS tree node, wherein the first CAS tree comprises a set of parent nodes, wherein each parent node comprises a hash of a concatenation of each hash in a corresponding set of hashes, and wherein each hash in each set of hashes corresponds to a chunk stored in the database;
based on traversing the first CAS tree, obtaining a set of child nodes of the first CAS tree node, wherein each child node corresponds to a chunk of the file;
retrieving, based on the set of child nodes, a set of file chunks; and
reconstructing the file based on the set of file chunks.
6 . The method of claim 5 , wherein the content defined tree comprises a set of parent nodes, each parent node corresponding to a set of hashes that have been determined using a rolling hash and a grouping condition, wherein each parent node comprises a hash of a concatenation of each hash in a corresponding set of hashes, wherein the set of parent nodes form a tier of the content defined tree, and wherein each hash in each set of hashes corresponds to a chunk in the file.
7 . The method of claim 5 , further comprising:
determining, based on the content defined tree and the set of CAS tree nodes, that no CAS tree exists for a portion of the file; and
based on no CAS tree existing for the portion of the file, generating a new CAS tree by:
determining a second set of chunks, wherein a total size of the second set of chunks is less than a threshold size; and
generating leaf nodes of the new CAS tree, wherein each leaf node corresponds to a chunk of the second set of chunks.
8 . The method of claim 5 , wherein each parent node of the first CAS tree comprises a hash that may be used to index to one or more locations in the database where a corresponding chunks is stored.
9 . The method of claim 5 , further comprising:
generating a user interface comprising the set of file chunks and the first CAS tree, wherein the user interface indicates an association between a node in the first CAS tree and a corresponding chunk in the set of file chunks.
10 . The method of claim 5 , further comprising:
determining, based on the content defined tree and the set of CAS tree nodes, that no CAS tree exists for a portion of the file;
based on no CAS tree existing for the portion of the file, generating a new CAS tree by:
generating a set of hashes comprising a hash for each chunk of a set of chunks, wherein the set of hashes form a first tier of the new CAS tree; and
generating a set of parent nodes by grouping each hash of the set of hashes based on a second rolling hash satisfying a second condition; and
storing the new CAS tree and the portion of the file in the database.
11 . The method of claim 10 , further comprising:
based on determining that the portion of the file is greater than a threshold size, causing generation of the new CAS tree to use a first subpart of the portion of the file that is less than the threshold size; and
generating a second new CAS tree using a second subpart of the portion of the file, wherein content of the first subpart does not overlap with the second subpart.
12 . The method of claim 5 , wherein reconstructing the file based on the set of file chunks comprises:
retrieving additional file chunks based on a second set of parent nodes corresponding to a second database remote from the database; and
reconstructing the file based on the set of file chunks and the additional file chunks.
13 . A non-transitory, computer-readable medium comprising instructions that when executed by one or more processors, causes operations comprising:
obtaining a request for a file in a database, wherein the request comprises an identification of the file;
based on the request and the identification of the file, retrieving a content defined tree corresponding to the file;
determining a first node by traversing the content defined tree;
comparing the first node with a set of CAS tree nodes;
based on a hash of the first node matching a hash of a first CAS tree node of the set of CAS tree nodes, traversing a first CAS tree corresponding to the first CAS tree node, wherein the first CAS tree comprises a set of parent nodes, wherein each parent node comprises a hash of a concatenation of each hash in a corresponding set of hashes, and wherein each hash in each set of hashes corresponds to a chunk stored in the database;
based on traversing the first CAS tree, obtaining a set of child nodes of the first CAS tree node, wherein each child node corresponds to a chunk of the file;
retrieving, based on the set of child nodes, a set of file chunks; and
reconstructing the file based on the set of file chunks.
14 . The medium of claim 13 , wherein the content defined tree comprises a set of parent nodes, each parent node corresponding to a set of hashes that have been determined using a rolling hash and a grouping condition, wherein each parent node comprises a hash of a concatenation of each hash in a corresponding set of hashes, wherein the set of parent nodes form a tier of the content defined tree, and wherein each hash in each set of hashes corresponds to a chunk in the file.
15 . The medium of claim 13 , further comprising:
determining, based on the content defined tree and the set of CAS tree nodes, that no CAS tree exists for a portion of the file;
based on no CAS tree existing for the portion of the file, generating a new CAS tree by:
determining a second set of chunks, wherein a total size of the second set of chunks is less than a threshold size; and
generating leaf nodes of the new CAS tree, wherein each leaf node corresponds to a chunk of the second set of chunks.
16 . The medium of claim 13 , wherein each parent node of the first CAS tree comprises a hash that may be used to index to one or more locations in the database where a corresponding chunks is stored.
17 . The medium of claim 13 , further comprising:
generating a user interface comprising the set of file chunks and the first CAS tree, wherein the user interface indicates an association between a node in the first CAS tree and a corresponding chunk in the set of file chunks.
18 . The medium of claim 13 , further comprising:
determining, based on the content defined tree and the set of CAS tree nodes, that no CAS tree exists for a portion of the file;
based on no CAS tree existing for the portion of the file, generating a new CAS tree by:
generating a set of hashes comprising a hash for each chunk of a set of chunks, wherein the set of hashes form a first tier of the new CAS tree; and
generating a set of parent nodes by grouping each hash of the set of hashes based on a second rolling hash satisfying a second condition; and
storing the new CAS tree and the portion of the file in the database.
19 . The medium of claim 18 , further comprising:
based on determining that the portion of the file is greater than a threshold size, causing generation of the new CAS tree to use a first subpart of the portion of the file that is less than the threshold size; and
generating a second new CAS tree using a second subpart of the portion of the file, wherein content of the first subpart does not overlap with the second subpart.
20 . The medium of claim 13 , wherein reconstructing the file based on the set of file chunks comprises:
retrieving additional file chunks based on a second set of parent nodes corresponding to a second database remote from the database; and
reconstructing the file based on the set of file chunks and the additional file chunks.