Scalable low-loss disaster recovery for data stores

A method, comprising:

• performing, by one or more computing devices of a backup site:
• determining, by a backup shard of the backup site, that a recovery is in progress, wherein the backup site comprises a plurality of backup shards and associated shard replicas;
• based on the determination that the recovery is in progress, determining, by the backup shard, a timestamp of an update that was most recently committed by the backup shard, wherein the update was received by the backup shard from a remote network of a primary site;
• sending, by the backup shard to a watermark service, the timestamp;
• receiving, by the backup shard from the watermark service, a final global watermark timestamp, wherein the final global watermark timestamp indicates a time up to which all of the backup shards have committed updates;
• and
• applying, by the backup shard, at least another update to the backup shard based on the final global watermark timestamp, wherein a timestamp of at least the other update is less than or equal to the final global watermark timestamp, and wherein at least the other update was received by the backup shard from the remote network of the primary site.

One or more non-transitory computer-accessible storage media storing program instructions that when executed on or across one or more processors of a backup site cause the one or more processors to:

• determine, by a backup shard of the backup site, that a recovery is in progress, wherein the backup site comprises a plurality of backup shards and associated shard replicas;
• based on the determination that the recovery is in progress, determine, by the backup shard, a timestamp of an update that was most recently committed by the backup shard, wherein the update was received by the backup shard from a remote network of a primary site;
• send, by the backup shard to a watermark service, the timestamp;
• receive, by the backup shard from the watermark service, a final global watermark timestamp, wherein the final global watermark timestamp indicates a time up to which all of the backup shards have committed updates;
• and
• apply, by the backup shard, at least another update to the backup shard based on the final global watermark timestamp, wherein a timestamp of at least the other update is less than or equal to the final global watermark timestamp, and wherein at least the other update was received by the backup shard from the remote network of the primary site.