Data indexing and deduplication using content-defined trees
AssigneeHugging Face, Inc.
InventorsYucheng Low, Ajit Banerjee, Rajat Arya
Life of this patent
Estimating the term…
Abstract
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.
Claims20
A system for storing large data objects in a format that can be efficiently modified through use of content-defined trees, 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 data object comprising a string of bytes;
- dividing the string of bytes 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 content-defined tree by:
- 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 content-defined 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 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 a portion of the content-defined tree in a database.
A computer-implemented method for storing large data objects in a format that can be efficiently modified through use of content-defined trees, the method comprising executing, by one or more processors, operations comprising:
- obtaining a data object comprising a string of bytes;
- dividing the string of bytes 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 content-defined tree by:
- 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 content-defined 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 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;
- and
- storing a portion of the content-defined tree in a database.
A non-transitory, computer-readable medium comprising instructions that when executed by one or more processors, causes operations comprising:
- obtaining a data object comprising a string of bytes;
- dividing the string of bytes 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 content-defined tree by:
- 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 content-defined 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 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;
- and
- storing a portion of the content-defined tree in a database.
Dependencies are inferred from the claim text.