Verifying data consistency using verifiers in a content management system for a distributed key-value database

Patent metadata

Field	Value
Publication number	US-12050591-B2
Application number	US-202318354626-A
Country	US
Kind code	B2
Filing date	Jul 18, 2023
Priority date	Jun 30, 2021
Publication date	Jul 30, 2024
Grant date	Jul 30, 2024

Abstract

A consistency verification system that verifies data consistency in a content item management system. The system processes a write request. The write request includes a set of preconditions, a key, and data to write in a write operation. Processing the write request includes determining that the set of conditions are met, committing the write request at a commit time, and assigning a timestamp indicating the commit time to the write request. The system verifies data consistency associated with the write request. The verifying data consistency includes sending a replay request corresponding to the write request. The system determines whether results of the replay are consistent with results of the write request. Responsive to determining whether results of the replay are consistent with results of the write request, the system outputs information describing data inconsistency.

First claim

What is claimed is:

1. A method for checking data consistency in a distributed key-value pair database, the method comprising:
processing, by a content item management system, a write request, the write request comprising a set of one or more preconditions, a key, and data to write in a write operation, wherein processing the write request comprises:
determining that the set of one or more preconditions are met;
committing the write request at a commit time; and
assigning a timestamp indicating the commit time to the write request;

verifying data consistency associated with the write request, the verifying data consistency comprising sending a replay request corresponding to the write request;
determining whether one or more results of the replay request are consistent with one or more results of the write request; and
responsive to determining that the one or more results of the replay request are not consistent with the one or more results of the write request, outputting information describing data inconsistency.

2. The method of claim 1 , wherein verifying data consistency associated with the write request further comprises checking whether the set of one or more preconditions are met.

3. The method of claim 2 , wherein checking whether the set of one or more preconditions is met comprises:
sending a read request, the read request specifying a read operation associated with an earlier timestamp before the timestamp indicating the commit time to the write request;
receiving a response; and
determining whether the response is consistent with the set of one or more preconditions.

4. The method of claim 3 , wherein the set of one or more preconditions comprise a precondition associated with a key, a value, and the earlier timestamp, and checking whether the precondition is met comprises checking whether data associated with the key equals to the value at the earlier timestamp.

5. The method of claim 3 , wherein the set of one or more preconditions comprise a precondition associated with a range of keys.

6. The method of claim 1 , wherein verifying the data consistency associated with the write request further comprises checking whether the write operation was applied successfully.

7. The method of claim 6 , wherein checking whether the write operation was applied successfully comprises:
sending a read request, the read request specifying a read operation associated with a status of the write operation;
receiving a response; and
determining whether the write operation was applied successfully based on the response.

8. The method of claim 1 , wherein the timestamp is a first timestamp, the replay request is sent at a second timestamp after the first timestamp, and the first timestamp and the second timestamp are separated by a predefined holdoff period.

9. The method of claim 8 , wherein verifying data consistency associated with the write request further comprises:
verifying a latest timestamp associated with the write request by checking whether the latest timestamp is greater than or equal to the timestamp; and
verifying whether data associated with the timestamp is affected at the latest timestamp.

10. The method of claim 1 , wherein verifying data consistency associated with the write request further comprises:
checking metadata of a data record to determine whether a state transition is valid, the metadata comprising a plurality of invariants associated with the database, the plurality of invariants satisfying a set of rules during a state transition process; and
responsive to at least one invariant of the plurality of invariants failing to satisfy a rule of the set of rules during the state transition process, sending information describing the failing.

11. A non-transitory computer-readable storage medium storing executable computer instructions that, when executed by one or more processors, cause the one or more processors to:
process, by a content item management system, a write request, the write request comprising a set of one or more preconditions, a key, and data to write in a write operation, wherein processing the write request comprises:
determining whether the set of one or more preconditions are met at a first time;
responsive to determining that the set of one or more preconditions are met at the first time, committing the write request at a commit time that is later than the first time; and
assigning a timestamp indicating the commit time to the write request;

verify data consistency associated with the write request, the verifying data consistency comprising sending a replay request corresponding to the write request;
determine whether one or more results of the replay request are consistent with one or more results of the write request; and
responsive to determining that the one or more results of the replay request are not consistent with the one or more results of the write request, output information describing data inconsistency.

12. The non-transitory computer-readable storage medium of claim 11 , wherein verifying data consistency associated with the write request further comprises checking whether the set of one or more preconditions are met.

13. The non-transitory computer-readable storage medium of claim 12 , wherein checking whether the set of preconditions is met comprises:
sending a read request, the read request specifying a read operation associated with an earlier timestamp before the timestamp indicating the commit time to the write request;
receiving a response; and
determining whether the response is consistent with the precondition.

14. Non-transitory computer-readable storage medium of claim 13 , wherein the set of one or more preconditions comprise a precondition associated with a key, a value, and the earlier timestamp, and checking whether the precondition is met comprises checking whether data associated with the key equals to the value at the earlier timestamp.

15. The non-transitory computer-readable storage medium of claim 13 , wherein the set of one or more preconditions comprise a precondition associated with a range of keys.

16. The non-transitory computer-readable storage medium of claim 11 , wherein verifying the data consistency associated with the write request further comprises checking whether the write operation was applied successfully.

17. The non-transitory computer-readable storage medium of claim 16 , wherein checking whether the write operation was applied successfully comprises:
sending a read request, the read request specifying a read operation associated with a status of the write operation;
receiving a response; and
determining whether the write operation was applied successfully based on the response.

18. The non-transitory computer-readable storage medium of claim 11 , wherein the timestamp is a first timestamp, the replay request is sent at a second timestamp after the first timestamp, and the first timestamp and the second timestamp are separated by a predefined holdoff period.

19. The non-transitory computer-readable storage medium of claim 18 , wherein verifying data consistency associated with the write request further comprises:
verifying a latest timestamp associated with the write request by checking whether the latest timestamp is greater than or equal to the timestamp; and
verifying whether data associated with the timestamp is affected at the latest timestamp.

20. A system comprising:
one or more processors configured to execute instructions; and
a memory storing instructions for executio

Assignees

• Dropbox Inc

Inventors

• Le Preslav
• Walker Braden
• Tu Leslie
• Lathia Tanay
• Sosa Alexander
• He Lihao

Classifications

• G06F16/2272 Primary

  Management thereof · CPC title

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title