Removing a row is not enough

A deletion that removes the row and nothing else leaves the system with no memory of the decision. Replicas that were offline, writes queued before the deletion, and restores taken from an earlier snapshot all still carry the old value, and any of them can put it back without anyone noticing.

Leave a small record in the row's place, holding the key and the moment of the deletion. Its purpose is narrow: when a late write arrives, compare the moment it was created against the moment of the deletion and let the later decision win.

def permitted(store, incoming):
    gone = store.deletion_of(incoming["key"])
    if gone and incoming["created_at"] <= gone["removed_at"]:
        return False
    return True

A write from before the deletion is turned away, and the record of the deletion stays where it is. Accepting it would reverse a decision that was already taken.

Two fields are enough. There is no need to keep the payload that was removed, only the fact that something was removed and when.