Let the record of a deletion age out

Keeping a mark for every removed row forever is its own problem, because the store fills with entries for data nobody will send again. Drop the mark once the longest period in which an old copy could return has passed.

Take that period from the schedule rather than from instinct. Look at how long a snapshot may rest before it is restored, and how far a replica may fall behind, then use the larger of the two.

def sweep(store, now, horizon):
    for gone in store.all_marks():
        if now - gone["removed_at"] > horizon:
            store.drop_mark(gone["key"])

Count the writes that were turned away and record where each came from. A turned-away write means some producer is still sending data that was deleted, which is worth correcting at that producer.

Say so out loud. A count that stays at zero shows the guard is doing its job, and a count that starts rising is the earliest warning that a replica has fallen behind.