Replication lag-constrained deletion of data in a large-scale distributed data storage system

Patent metadata

Field	Value
Publication number	US-11226954-B2
Application number	US-201815971792-A
Country	US
Kind code	B2
Filing date	May 4, 2018
Priority date	May 22, 2017
Publication date	Jan 18, 2022
Grant date	Jan 18, 2022

Abstract

Computer-implemented techniques for replication-lag constrained deletion of data in a distributed data storage system. In some aspects, the techniques improve the operation of a computing system by preventing too high of a delete rate that causes severe replication lag while at the same time increasing and decreasing the delete rate over time to a maximum allowable delete rate constrained by measured replication lag in terms of both local replication lag and geographic replication lag. In one implementation, the delete rate is adjusted by increasing or decreasing a pause interval that determines how long a database data deletion process pauses between submitting database deletion commands to a database server.

First claim

The invention claimed is:

1. A system, comprising:
one or more processors;
a memory; and
instructions stored in the memory and which, when executed by the system, cause the system to perform:
determining a first replication lag metric based on a first replication process involving a first database and a second database located at a first geographic distance from the first database, wherein determining the first replication lag metric is based on a measured time delay between a storage of database data in the first database and a storage of replicated database data in the second database;
determining a second replication lag metric based on a second replication process involving a third database and the second database located at a second distance from the third database, wherein the first distance is different than the second distance, wherein determining the second replication lag metric is based on a measured time delay between a storage of database data in the second database and a storage of replicated database data in the third database;
performing a first determination of whether the first replication lag metric is greater than a first replication lag threshold;
performing a second determination of whether the second replication metric is greater than a second replication lag threshold, wherein the second replication lag threshold is different than the first replication lag threshold;
performing a third determination of whether at least one of the first determination and the second determination is true; and
based at least in part on the third determination, deleting data from the second database at an adjusted delete rate thereby:
increasing or decreasing replication lag of a first subsequent replication process between the second database and the first database, and
increasing or decreasing replication lag of a second subsequent replication process between the second database and the third database based on whether the adjusted delete rate is increased or decreased.

2. The system of claim 1 , further comprising instructions stored in the memory, and which, when executed by the system, cause the system to perform:
based at least in part on comparing the first replication lag metric to the first replication lag threshold and comparing the second replication lag metric to the second replication lag threshold, adjusting a pause interval resulting in an adjusted pause interval; and
serially submitting a plurality of commands to a database server using the adjusted pause interval, the database server configured to execute the plurality of commands against the second database to delete data from the second database.

3. The system of claim 2 , further comprising instructions stored in the memory, and which, when executed by the system, cause the system to perform:
based at least in part on a determining that both: (a) the first replication lag metric is above the first replication lag threshold and (b) the second replication lag metric is below the second replication lag threshold, determining the adjusted pause interval by increasing the pause interval.

4. The system of claim 1 , further comprising instructions stored in the memory, and which, when executed by the system, cause the system to perform:
based at least in part on determining that both: (a) the second replication lag metric is below the second replication lag threshold and (b) the first replication lag metric is below the first replication lag threshold, serially submitting at least some commands of a plurality of commands to a database server to delete data from the second database without sleeping for a pause interval after a submission of a command of the plurality of commands.

5. The system of claim 2 , wherein a command of the plurality of commands is a Structured Query Language (SQL) delete command.

6. The system of claim 2 , further comprising instructions stored in the memory, and which, when executed by the system, cause the system to perform determining the adjusted pause interval by decreasing the pause interval.

7. The system of claim 2 , further comprising instructions stored in the memory, and which, when executed by the system, cause the system to perform determining the adjusted pause interval by increasing the pause interval based, at least in part, on the determining that both: (a) the second replication lag metric is above the second replication lag threshold and (b) the first replication lag metric is above the first replication lag threshold.

8. The system of claim 2 , further comprising instructions stored in the memory, and which, when executed by the system, cause the system to perform selecting the pause interval as a maximum of the second replication lag metric and the first replication lag metric.

9. The system of claim 2 , wherein the serially submitting, using the adjusted pause interval, the plurality of commands to the database server to delete data from the second database is based, at least in part, on not sleeping for a pause interval after a submission of a command of the plurality of commands.

10. The system of claim 1 , wherein the adjusted delete rate is decreased based, at least in part, on determining both: (a) the first replication lag metric is above the first replication lag threshold and (b) the second replication lag metric is above the second replication lag threshold, or the adjusted delete rate is increased based, at least in part, on determining both: (a) the first replication lag metric is below the first replication lag threshold and (b) the second replication lag metric is below the second replication lag threshold.

11. The system of claim 1 , wherein the adjusted delete rate is determined based on a pause interval that has been increased or decreased by a predetermined amount.

12. The system of claim 11 , wherein the predetermined amount comprises a predetermined increment amount equal to a maximum of the first replication lag metric and the second replication lag metric or a predetermined decrement amount that ranges between a minimum of the first replication lag metric and the second replication lag metric.

13. A method performed by a computing system comprising one or more processors and a memory, the method comprising:
determining a first replication lag metric based on a first replication process involving a first database and a second database located at a first geographic distance from the first database, wherein determining the first replication lag metric is based on a measured time delay between a storage of database data in the first database and a storage of replicated database data in the second database;
determining a second replication lag metric based on a second replication process involving a third database and the second database located at a second distance from the third database that is less than the first geographic distance and based on a measured time delay between a storage of database data in the second database and a storage of replicated database data in the third database;
performing a first determination of whether the first replication lag metric is greater than a first replication lag threshold;
performing a second determination of whether the second replication metric is greater than a second replication lag threshold, wherein the second replication lag threshold is different than the first replication lag threshold;
performing a third determination of whether at least one of the first determination and the second determination is true;
based at least in part on the third determination, deleting data from the second database at an adjusted delete rate thereby:
increasing or decreasing replicati

Assignees

• Dropbox Inc

Inventors

• Baid Mehant
• Munteanu Bogdan
• Tahara Daniel K

Classifications

• G06F16/2308 Primary

  Concurrency control (transaction processing G06F9/466) · CPC title

• G06F16/27

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title

• G06F16/2322

  using timestamps · CPC title

• G06F16/275

  Synchronous replication · CPC title