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

Patent metadata

Field	Value
Publication number	US-11748333-B2
Application number	US-202117364606-A
Country	US
Kind code	B2
Filing date	Jun 30, 2021
Priority date	Jun 30, 2021
Publication date	Sep 5, 2023
Grant date	Sep 5, 2023

Abstract

A consistency verification system that verifies data consistency in a content item management system. The system maintains a plurality of verifiers for checking data consistency, each verifier comprising instructions for verifying consistency for a type of requests. The system may verify the original request by selecting a verifier from the plurality of verifiers based on a type of the original request. Using the selected verifier, the consistency verification system may send verification requests to the content item management system at a second timestamp that is a period of time after the original timestamp. The system may determine whether the second response is consistent with the first response. If the responses are not consistent, the system may output information describing data inconsistency. If the responses are consistent, the system may output results and perform further verifications to help ensure data accuracy.

First claim

What is claimed is:

1. A method for checking data consistency in a distributed key-value pair database, the method comprising:
maintaining a plurality of verifiers for verifying data consistency in the database, wherein each verifier comprises a set of instructions for verifying data consistency for a type of request;
processing, by a content item management system, a plurality of requests, wherein processing each request comprises performing, by the content item management system one or more operations;
selecting a request from the processed plurality of requests, wherein the selected request was processed at a first timestamp, received a first response, and specified a set of one or more parameters;
identifying a verifier from the plurality of verifiers to verify data consistency associated with the selected request; and
verifying, by the identified verifier, data consistency associated with the selected request, the verification comprising:
sending a replay request corresponding to the selected request, the replay request including the set of parameters, wherein the replay request is sent at a second timestamp after the first timestamp, the first timestamp and the second timestamp separated by a predefined holdoff period;
receiving a second response associated with the replay request;
determining whether the second response is consistent with the first response; and
based on a determination that the second response is not consistent with the first response, outputting information describing data inconsistency.

2. The method of claim 1 , wherein the selected verifier is a write verifier, and the selected request is a write request associated with a precondition, wherein the write request commits a write operation at the first timestamp.

3. The method of claim 2 , wherein the verification further comprises:
verifying the precondition associated with the write request; and
verifying a latest timestamp associated with the write request by checking whether the latest timestamp is greater than or equal to the first timestamp.

4. The method of claim 3 , wherein verifying the precondition comprises:
sending a read request, the read request specifying a read operation associated with a timestamp before the first timestamp;
receiving a response; and
determining whether the response is consistent with the precondition.

5. The method of claim 1 , wherein the set of parameters comprise a key and a timestamp.

6. The method of claim 1 , wherein the set of parameters comprise a range of keys.

7. The method of claim 1 , further comprising:
checking whether a plurality of invariants associated with the database satisfy 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 failure.

8. 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 perform steps comprising:
maintaining a plurality of verifiers for verifying data consistency in a database, wherein each verifier comprises a set of instructions for verifying data consistency for a type of requests;
receiving, by a content item management system, a plurality of requests, wherein the content item management system performs operations in response to each request;
selecting a request from the plurality of requests, wherein the selected request was processed at a first timestamp and is associated with a first response, the request specifying a set of parameters;
identifying a verifier from the plurality of verifiers to verify data consistency of the data processed in response to the selected request; and
verifying, by the identified verifier, data consistency of the data processed in response to the selected request, the verification comprising:
sending a replay request corresponding to the selected request, the replay request including the set of parameters, wherein the replay request is sent at a second timestamp after the first timestamp, the first timestamp and the second timestamp separated by a predefined holdoff period;
receiving a second response associated with the replay request;
determining, based on the first and the second response, whether to output information describing data inconsistency to the content item management system.

9. The non-transitory computer-readable storage medium of claim 8 , wherein the selected verifier is a write verifier that is selected based on a type associated with the request, and the selected request is a write request associated with a precondition, wherein the write request commits a write operation at the first timestamp.

10. The non-transitory computer-readable storage medium of claim 9 , wherein the verification further comprises:
verifying the precondition associated with the write request; and
verifying a latest timestamp associated with the write request by checking whether the latest timestamp is greater than or equal to the first timestamp.

11. The non-transitory computer-readable storage medium of claim 10 , wherein verifying the precondition comprises:
sending a read request, the read request specifying a read operation associated with a timestamp before the first timestamp;
receiving a response; and
determining whether the response is consistent with the precondition.

12. The non-transitory computer-readable storage medium of claim 8 , wherein the steps further comprising:
checking whether a plurality of invariants associated with the database satisfy 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 failure.

13. A system comprising:
one or more processors configured to execute instructions; and
a memory storing instructions for execution on the one or more processors, including instructions causing the one or more processors to:
maintain a plurality of verifiers for verifying data consistency in a database, wherein each verifier comprises a set of instructions for verifying data consistency for a type of requests;
receive, by a content item management system, a plurality of requests, wherein the content item management system performs operations in response to each request;
select a request from the plurality of requests, wherein the selected request was processed at a first timestamp and is associated with a first response, the request specifying a set of parameters;
identify a verifier from the plurality of verifiers, based on a type of the request, to verify data consistency of data processed in response to the selected request; and
verify, by the identified verifier, data consistency of the data processed in response to the selected request, wherein the verification comprises sending a second request and receiving a second response, wherein the second request is sent at a second timestamp after the first timestamp, the first timestamp and the second timestamp separated by a predefined holdoff period; and
determine, based on the first response and the second response, whether to output information describing data inconsistency.

14. The system of claim 13 , wherein the selected verifier is a write verifier, and the selected request is a write request associated with a precondition, wherein the write request commits a write operation at the first timestamp.

15. The system of claim 14

Assignees

• Dropbox Inc

Inventors

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

Classifications

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title

• G06F16/2272 Primary

  Management thereof · CPC title