Granted Patent B2

US 12,481,703 · App. 16/834,891 · Granted Nov 25, 2025

Inventor: Jeronimo Irazabal (Buenos Aires, AR)

Assignee: International Business Machines Corporation

G06F16/9027G06F16/9014H04L9/0643H04L9/50

Abstract

Claims (67)

1 . An apparatus, comprising:

a database partitioned into a plurality of shards; and

a hardware-implemented processor configured to:

store a plurality of fragments of an object across a subset of shards of the plurality of shards, wherein

each fragment of the plurality of fragments is stored in a respective shard of the subset of shards;

assign each fragment of the plurality of fragments stored in the respective shard to a corresponding hash tree, of a plurality of hash trees, associated with the respective shard;

generate a first local hash value for each shard of the subset of shards based on the assignment of each fragment of the plurality of fragments;

combine the first local hash value of each shard of the subset of shards into a first sequence to generate a plurality of intermediate hash values;

roll up the plurality of intermediate hash values via a Merkle tree to generate a first root hash value for the object;

at a first time, generate a first snapshot of the database, wherein the first snapshot comprises the first root hash value and a first global hash value associated with the first root hash value;

at a second time later than the first time:

combine a second local hash value of each shard of the subset of shards into a second sequence to generate a second root hash value for the object;

generate a second global hash value based on the second root hash value, the first global hash value of the first snapshot, and a number value of the first snapshot; and

generate a second snapshot of the database, wherein

the second snapshot comprises the second root hash value and the second global hash value, and

the second snapshot is cryptographically linked to the first snapshot based on the second global hash value.

2 . The apparatus of claim 1 , wherein a storage format of each shard of the subset of shards comprises one of a log-structured merge tree or a b-tree.

3 . The apparatus of claim 1 , wherein the hardware-implemented processor is further configured to:

hash a plurality of key-value pairs stored in each shard of the subset of shards, wherein

the plurality of key-value pairs in each shard of the subset of shards is associated with a respective fragment of the plurality of fragments; and

assign at least one hashed key-value pair of the plurality of hashed key-value pairs to a respective leaf node of a plurality of leaf nodes of the corresponding hash tree.

4 . The apparatus of claim 1 , wherein the hardware-implemented processor is further configured to:

assign the first local hash value of each shard of the subset of shards to a respective leaf node of a plurality of leaf nodes of the Merkle tree; and

determine a root hash value of the Merkle tree as the first root hash value for the object based on the assignment of the first local hash value of each shard of the subset of shards.

5 . A method, comprising:

storing an object within a database partitioned into a plurality of shards, wherein

the storing of the object comprises storing each fragment of a plurality of fragments of the object in a respective shard of a subset of shards of the plurality of shards of the database;

assigning each fragment of the plurality of fragments stored in the respective shard to a corresponding hash tree, of a plurality of hash trees, associated with the respective shard;

generating a first local hash value for each shard of the subset of shards based on the assigning of each fragment of the plurality of fragments;

combining the first local hash value of each shard of the subset of shards into a first sequence to generate a plurality of intermediate hash values;

rolling up the intermediate hash values via a Merkle tree to generate a first root hash value for the object;

at a first time, generating a first snapshot of the database, wherein the first snapshot comprises the first root hash value and a first global hash value associated with the first root hash value;

at a second time later than the first time:

combining a second local hash value of each shard of the subset of shards into a second sequence to generate a second root hash value for the object;

generating a second global hash value based on the second root hash value, the first global hash value of the first snapshot, and a number value of the first snapshot; and

generating a second snapshot of the database, wherein

the second snapshot comprises the second root hash value and the second global hash value, and

the second snapshot is cryptographically linked to the first snapshot based on the second global hash value.

6 . The method of claim 5 , wherein a storage format of each shard of the subset of shards comprises one of a log-structured merge tree or a b-tree.

7 . The method of claim 5 , further comprising:

hashing a plurality of key-value pairs stored in each shard of the subset of shards, wherein

the plurality of key-value pairs in each shard of the subset of shards is associated with a respective fragment of the plurality of fragments; and

assigning at least one hashed key-value pair of the plurality of hashed key-value pairs to a respective leaf node of a plurality of leaf nodes of the corresponding hash tree.

8 . The method of claim 5 , further comprising:

assigning the first local hash value of each shard of the subset of shards to a respective leaf node of a plurality of leaf nodes of the Merkle tree; and

determining a root hash value of the Merkle tree as the first root hash value for the object based on the assigning of the first local hash value of each shard of the subset of shards.

9 . A non-transitory computer-readable medium comprising instructions that, when executed by a processor, cause the processor to perform:

storing an object within a database partitioned into a plurality of shards, wherein

the storing of the object comprises storing each fragment of a plurality of fragments of the object in a respective shard of subset of shards of the plurality of shards of the database;

assigning each fragment of the plurality of fragments stored in the respective shard to a corresponding hash tree, of a plurality of hash trees, associated with the respective shard;

generating a first local hash value for each shard of the subset of shards based on the assigning of each fragment of the plurality of fragments;

combining the first local hash value of each shard of the subset of shards into a first sequence to generate a plurality of intermediate hash values;

rolling up the intermediate hash values via a Merkle tree to generate a first root hash value for the object;

at a first time, generating a first snapshot of the database, wherein the first snapshot comprises the first root hash value and a first global hash value associated with the first root hash value;

at a second time later than the first time:

combining a second local hash value of each shard of the subset of shards into a second sequence to generate a second root hash value for the object;

generating a second global hash value based on the second root hash value, the first global hash value of the first snapshot, and a number value of the first snapshot; and

generating a second snapshot of the database, wherein

the second snapshot comprises the second root hash value and the second global hash value, and

the second snapshot is cryptographically linked to the first snapshot based on the second global hash value.

10 . The non-transitory computer-readable medium of claim 9 , wherein the instructions further cause the processor to perform:

hashing a plurality of key-value pairs stored in each shard of the subset of shards, wherein

the plurality of key-value pairs in each shard of the subset of shards is associated with a respective fragment of the plurality of fragments; and

assigning at least one hashed key-value pair of the plurality of hashed key-value pairs to a respective leaf node of a plurality of leaf nodes of the corresponding hash tree.

11 . The non-transitory computer-readable medium of claim 9 , wherein the instructions further cause the processor to perform:

assigning the first local hash value of each shard of the subset of shards to a respective leaf node of a plurality of leaf nodes of the Merkle tree; and

determining a root hash value of the Merkle tree as the first root hash value for the object based on the assigning of the first local hash value of each shard of the subset of shards.

Assignments (1)

Continuity (1)

References Cited (103)