A method for replication lag-constrained deletion of data in a distributed data storage system, the method performed by a computing system comprising one or more processors and memory, the method comprising: serially submitting a first plurality of commands to a first database server to delete data from a first database including pausing for a first pause interval after each submission of a command of the first plurality of commands; determining a local database replication lag metric for a local database replication process involving the first database server and the first database and a second database server and a second database that are co-located with the first database server and the first database in the same data center; determining a geographic database replication lag metric for a geographic database replication process involving the first database server and the first database and a third database server and a third database, where the first database server and the first database and the third database server and the third database are located in different data centers; based at least in part on determining that the local database replication lag metric is above a local database replication lag threshold and that the geographic database replication metric is above a geographic database replication lag threshold, increasing the first pause interval to a second pause interval, where the geographic database replication lag threshold is greater than the local database replication lag threshold; and serially submitting a second plurality of commands to the first database server to delete data from the first database including pausing for the second pause interval after each submission of a command of the second plurality of commands. serially submitting a first plurality of commands to a first database server to delete data from a first database including pausing for a first pause interval after each submission of a command of the first plurality of commands; determining a local database replication lag metric for a local database replication process involving the first database server and the first database and a second database server and a second database that are co-located with the first database server and the first database in the same data center; determining a geographic database replication lag metric for a geographic database replication process involving the first database server and the first database and a third database server and a third database, where the first database server and the first database and the third database server and the third database are located in different data centers; based at least in part on determining that the local database replication lag metric is above a local database replication lag threshold and that the geographic database replication metric is above a geographic database replication lag threshold, increasing the first pause interval to a second pause interval, where the geographic database replication lag threshold is greater than the local database replication lag threshold; and serially submitting a second plurality of commands to the first database server to delete data from the first database including pausing for the second pause interval after each submission of a command of the second plurality of commands.