Granted Patent B2

US 12,353,362 · App. 18/413,183 · Granted Jul 8, 2025

Inventors: Avinash Lakshman (Fremont, CA); Lasaro Camargos (Uberlandia, BR); Deepak Jain (Santa Clara, CA)

Assignee: Commvault Systems, Inc.

G06F16/178G06F11/1464G06F16/137G06F16/24573G06F16/2471G06F16/182G06F16/275

Abstract

Claims (46)

1. A system comprising: a plurality of computer nodes, wherein each computer node in the plurality of computer nodes comprises at least one hardware processor and one or more data storage drives, and wherein one computer node among the plurality of computer nodes is configured to:

retrieve a plurality of first hash values from a computer node among the plurality of computer nodes,

wherein each first hash value corresponds to a first region of first metadata that is stored at a first computer node among the plurality of computer nodes,

wherein the first metadata includes a first plurality of key-value-timestamp triples each of which relates to corresponding data that was stored at a computer node among the plurality of computer nodes, and

wherein each first region of the first metadata comprises at least part of a key-value-timestamp triple among the first plurality of key-value-timestamp triples;

wherein second metadata, which is identified in the system as a replica of the first metadata, includes a second plurality of key-value-timestamp triples;

retrieve a plurality of second hash values from a computer node among the plurality of computer nodes,

wherein each second hash value corresponds to a second region of the second metadata, and

wherein each second region of the second metadata comprises at least part of a key-value-timestamp triple among a second plurality of key-value-timestamp triples in the second metadata;

determine that the plurality of second hash values lacks a first hash value that is present in the plurality of first hash values, wherein the first metadata comprises a key-value-timestamp triple that corresponds to the first hash value; and

cause the second metadata to be updated with the key-value-timestamp triple that corresponds to the first hash value that is lacking from the plurality of second hash values.

2. The system of claim 1 , wherein the one computer node among the plurality of computer nodes is further configured to:

determine that the plurality of first hash values lacks a second hash value that is present in the plurality of second hash values, wherein the second metadata comprises a key-value-timestamp triple that corresponds to the second hash value lacking from the plurality of first hash values; and

cause the first metadata to be updated with the key-value-timestamp triple that corresponds to the second hash value lacking from the plurality of first hash values.

3. The system of claim 2 , wherein the one computer node among the plurality of computer nodes is further configured to: determine whether all second hash values in the plurality of second hash values are present among the plurality of first hash values.

4. The system of claim 1 , wherein the first hash value lacking from the plurality of second hash values corresponds to at least one missing region of the second metadata.

5. The system of claim 1 , wherein the second metadata is stored at a second computer node among the plurality of computer nodes, wherein the second computer node is configured to compact the updated second metadata resulting in a new version of the second metadata.

6. The system of claim 1 , wherein the first metadata and the second metadata are located on different computer nodes among the plurality of computer nodes, and wherein the first metadata and the second metadata have a same identifier that indicates that the second metadata is a replica of the first metadata.

7. The system of claim 1 , wherein the one computer node among the plurality of computer nodes is the first computer node.

8. The system of claim 1 , wherein the plurality of first hash values and plurality of second hash values are retrieved from a same computer node among the plurality of computer nodes.

9. The system of claim 1 , wherein each first hash value is part of a start-length-hash value triple that uniquely corresponds to a first region of the first metadata as stored on a data storage drive at the first computer node.

10. The system of claim 1 , wherein the first metadata is organized as a string-sorted-table (SST) comprising the first plurality of key-value-timestamp triples sorted by key; and wherein the second metadata is organized as a string-sorted-table (SST) comprising the second plurality of key-value-timestamp triples sorted by key.

11. A computer-implemented method comprising:

by one computer node among a plurality of computer nodes in a distributed data storage system, wherein each computer node in the plurality of computer nodes comprises at least one hardware processor and one or more data storage drives:

retrieving a plurality of first hash values from a computer node among the plurality of computer nodes,

wherein each first hash value corresponds to a first region of first metadata that is stored at a first computer node among the plurality of computer nodes,

wherein the first metadata includes a first plurality of key-value-timestamp triples each of which relates to corresponding data that was stored at a computer node among the plurality of computer nodes, and

wherein each first region of the first metadata comprises at least part of a key-value-timestamp triple among the first plurality of key-value-timestamp triples;

wherein second metadata, which is identified in the distributed data storage system as a replica of the first metadata, includes a second plurality of key-value-timestamp triples;

retrieving a plurality of second hash values from a computer node among the plurality of computer nodes,

wherein each second hash value corresponds to a second region of the second metadata, and

wherein each second region of the second metadata comprises at least part of a key-value-timestamp triple among a second plurality of key-value-timestamp triples in the second metadata;

determining that the plurality of second hash values lacks a first hash value that is present in the plurality of first hash values, wherein the first metadata comprises a key-value-timestamp triple that corresponds to the first hash value; and

causing the second metadata to be updated with the key-value-timestamp triple that corresponds to the first hash value that is lacking from the plurality of second hash values.

12. The computer-implemented method of claim 11 , further comprising:

determining that the plurality of first hash values lacks a second hash value that is present in the plurality of second hash values, wherein the second metadata comprises a key-value-timestamp triple that corresponds to the second hash value lacking from the plurality of first hash values; and

causing the first metadata to be updated with the key-value-timestamp triple that corresponds to the second hash value lacking from the plurality of first hash values.

13. The computer-implemented method of claim 12 , further comprising:

determining whether all second hash values in the plurality of second hash values are present among the plurality of first hash values.

14. The computer-implemented method of claim 11 , wherein the first hash value lacking from the plurality of second hash values corresponds to at least one missing region of the second metadata.

15. The computer-implemented method of claim 11 , wherein the second metadata is stored at a second computer node among the plurality of computer nodes, wherein the second computer node is configured to compact the updated second metadata resulting in a new version of the second metadata.

16. The computer-implemented method of claim 11 , wherein the first metadata and the second metadata are located on different computer nodes among the plurality of computer nodes, and wherein the first metadata and the second metadata have a same identifier that indicates that the second metadata is a replica of the first metadata.

17. The computer-implemented method of claim 11 , wherein the one computer node among the plurality of computer nodes is the first computer node.

18. The computer-implemented method of claim 11 , wherein the plurality of first hash values and plurality of second hash values are retrieved from a same computer node among the plurality of computer nodes.

19. The computer-implemented method of claim 11 , wherein each first hash value is part of a start-length-hash value triple that uniquely corresponds to a first region of the first metadata as stored on a data storage drive at the first computer node.

20. The computer-implemented method of claim 11 , wherein the first metadata is organized as a string-sorted-table (SST) comprising the first plurality of key-value-timestamp triples sorted by key; and wherein the second metadata is organized as a string-sorted-table (SST) comprising the second plurality of key-value-timestamp triples sorted by key.

Assignments (2)

Continuity (4)

References Cited (153)