One of the headaches of system design in this area is how do you deal with backups. Lets say you do regular backups to s3, glacier, tape, stone tablets. When y

One of the headaches of system design in this area is how do you deal with backups. Lets say you do regular backups to s3, glacier, tape, stone tablets. When you tell your customer "we have deleted all your data", are you loading all your backups and scrubbing their data from there as well? Probably not as it would probably be too expensive, and depending on your size, your backups may cease to be backups as users request for data deletion daily. Ok, then you might say when you restore backups, you reference all the data to a master "deletion" list and before a backup is restored then you reference that deletion list. Still though you are dependent on the company promising to reference the deletion list. When someone "really really" needs data from a week ago and gets a one off backup, it has deleted customer data in it. Next, my idea was you encrypt all user data with a user specific key, and when the customer requests to delete that, you just delete the key. Perfect. Up until it's time to backup the encryption keys database and you are back at square one. I understand this solution is probably 95% of the way there but if anyone knows any designs which, when implemented, are fairly foolproof and don't require your customers to be "smart" (e.g. have them hold the encryption key).