3 ms·

Secure delete is not implemented in databases because it is extraordinarily expensive, and destroys the performance of all other non-delete operations. When you

Secure delete is not implemented in databases because it is extraordinarily expensive, and destroys the performance of all other non-delete operations. When you say “encrypt data”, you are ignoring the fact that it can’t be implemented as “same data structures, just encrypted”. Encryption puts constraints on data structures and data representation that are fundamentally incompatible with and adverse to the design and functioning of most databases in existence, even ignoring the other ugly operational issues with that approach which no one thinks about. It would require radically redesigning the internals of most database engines, which is not really a practical option. I’ve thought a lot about what it would take to design a “delete optimized” database kernel every since GDPR became a thing. In principle it is possible, but I seriously doubt anyone would use a database that is literally orders of magnitude slower and less scalable for everything except delete operations. Would it be acceptable to increase the resource intensity of databases by 10x (and environmental footprint implied) to get “real” deletes? That is the tradeoff here. This has precedent in SQL databases designed for high-assurance applications with ultra-fine access and visibility controls. When the average software engineer understands how they work, it sounds like a great idea for having more secure data and they wonder why it doesn’t seem to exist. The reality is that they do exist but they are so abysmally slow for even elementary things that no one would ever dream of using it unless there is a narrow government requirement.

jacquesm 6y ago
The law doesn't really care about your notion of what can be done effeciently, if it can be done then you should probably do it or risk being found in violation of the law. There is some very specific language to that effect in the GDPR to make sure that it is clear that 'whatever you could reasonably do' needs to be done. You can then go and argue that you felt it wasn't reasonable but I doubt that will fly. But you're totally right that this is a tricky problem and hard to do properly. On the plus side, field level encryption is something that we've been doing for ages and that already works quite well. If you design carefully you can even get some processing done on those fields though it will take some major breakthroughs in DB engine design before you can have your cake and eat it too, in the sense that you can be both legally compliant and do all the kinds of processing you can do today. I even doubt if that is desirable, lots of those examples of processing should probably not be done in the first place.
- jandrewrogers 6y ago
  Encryption at record granularity introduces two technical problems that no one has come up with a tractable solution for, and a solution likely doesn't exist. It is actually a discussion of fundamental tractability, not "efficiency". The law can declare that we should be able to break AES encryption too but that doesn't manufacture plausibility. First, encryption has a block size. Data field storage in databases is typically measured in bits, as closed to the information theoretic limit as practical. Storing an 11-bit datum for some column as a 256-bit AES block represents a 20x expansion in storage cost. We could go back to the old row storage model, which would allow the record to be encrypted as contiguous memory, but that would both bloat storage (for different reasons) and we get to relive the golden age of very poor query performance. Modern databases are built on succinct representations because throughput is memory-bandwidth bound. Even in conventional databases, ignoring this design detail will cost you 100x in throughput. Second, keys and key schedules thoroughly thrash the CPU cache for scan operators. In a typical data model, a single row will be much smaller than the key schedule for decrypting that row. Every single row, several thousand per page, will require an unpredictable cache line fill to access the required key. Then you have two choices: compute a new key schedule for each row, which will be computationally expensive, or precompute the key schedule and take the even larger RAM hit. In large scale-out databases, many gigabytes of key infrastructure will need to be locally cached in RAM on each server -- you can't afford a network hop or page fault -- to decrypt each row in a page scan. Key management state consumes most of your runtime resources and crowds out the data model. I've worked on the design of such schemes in real systems, you end up devoting almost all of your cache/RAM to key state to the exclusion of the actual data model. Also burns up quite a bit of precious memory bandwidth without doing any real work. Any database built on encryption for record-level physical deletion will be unusable for almost any modern application for well-studied technical reasons. It will work, in theory, if you can run your business on a database that performs and scales like it is 1995. The best technical solution for physical deletion today is to rewrite cold storage, which is still extremely expensive and has extremely low delete operation throughput if you do it synchronously but at least it doesn't break database computer science. The only high-throughput and economical way to implement rewriting is asynchronously with very long deferrals e.g. over 30 days. Which is how databases have always worked, but with the deferral being indefinite.
toast0 6y ago
> When you say “encrypt data”, you are ignoring the fact that it can’t be implemented as “same data structures, just encrypted”. Encryption puts constraints on data structures and data representation that are fundamentally incompatible with and adverse to the design and functioning of most databases in existence, even ignoring the other ugly operational issues with that approach which no one thinks about. It would require radically redesigning the internals of most database engines, which is not really a practical option. You can't do effective per-user encryption on columns the database software needs to read (things you'll query or join on), but the database rarely needs message/post content and image content (often not even stored in the database). So encrypting those could be privacy helpful, if you can make the per-user encrypted store better at deletes than in general. For person to person messages, if you have a separate record for the sender and the receiver, you can do some per-user transformation on the other correspondent, but that might be indexed, so data without keys would still show messaging patterns.

jacquesm 6y ago

The law doesn't really care about your notion of what can be done effeciently, if it can be done then you should probably do it or risk being found in violation of the law. There is some very specific language to that effect in the GDPR to make sure that it is clear that 'whatever you could reasonably do' needs to be done. You can then go and argue that you felt it wasn't reasonable but I doubt that will fly. But you're totally right that this is a tricky problem and hard to do properly. On the plus side, field level encryption is something that we've been doing for ages and that already works quite well. If you design carefully you can even get some processing done on those fields though it will take some major breakthroughs in DB engine design before you can have your cake and eat it too, in the sense that you can be both legally compliant and do all the kinds of processing you can do today. I even doubt if that is desirable, lots of those examples of processing should probably not be done in the first place.

jandrewrogers 6y ago
Encryption at record granularity introduces two technical problems that no one has come up with a tractable solution for, and a solution likely doesn't exist. It is actually a discussion of fundamental tractability, not "efficiency". The law can declare that we should be able to break AES encryption too but that doesn't manufacture plausibility. First, encryption has a block size. Data field storage in databases is typically measured in bits, as closed to the information theoretic limit as practical. Storing an 11-bit datum for some column as a 256-bit AES block represents a 20x expansion in storage cost. We could go back to the old row storage model, which would allow the record to be encrypted as contiguous memory, but that would both bloat storage (for different reasons) and we get to relive the golden age of very poor query performance. Modern databases are built on succinct representations because throughput is memory-bandwidth bound. Even in conventional databases, ignoring this design detail will cost you 100x in throughput. Second, keys and key schedules thoroughly thrash the CPU cache for scan operators. In a typical data model, a single row will be much smaller than the key schedule for decrypting that row. Every single row, several thousand per page, will require an unpredictable cache line fill to access the required key. Then you have two choices: compute a new key schedule for each row, which will be computationally expensive, or precompute the key schedule and take the even larger RAM hit. In large scale-out databases, many gigabytes of key infrastructure will need to be locally cached in RAM on each server -- you can't afford a network hop or page fault -- to decrypt each row in a page scan. Key management state consumes most of your runtime resources and crowds out the data model. I've worked on the design of such schemes in real systems, you end up devoting almost all of your cache/RAM to key state to the exclusion of the actual data model. Also burns up quite a bit of precious memory bandwidth without doing any real work. Any database built on encryption for record-level physical deletion will be unusable for almost any modern application for well-studied technical reasons. It will work, in theory, if you can run your business on a database that performs and scales like it is 1995. The best technical solution for physical deletion today is to rewrite cold storage, which is still extremely expensive and has extremely low delete operation throughput if you do it synchronously but at least it doesn't break database computer science. The only high-throughput and economical way to implement rewriting is asynchronously with very long deferrals e.g. over 30 days. Which is how databases have always worked, but with the deferral being indefinite.

toast0 6y ago

> When you say “encrypt data”, you are ignoring the fact that it can’t be implemented as “same data structures, just encrypted”. Encryption puts constraints on data structures and data representation that are fundamentally incompatible with and adverse to the design and functioning of most databases in existence, even ignoring the other ugly operational issues with that approach which no one thinks about. It would require radically redesigning the internals of most database engines, which is not really a practical option. You can't do effective per-user encryption on columns the database software needs to read (things you'll query or join on), but the database rarely needs message/post content and image content (often not even stored in the database). So encrypting those could be privacy helpful, if you can make the per-user encrypted store better at deletes than in general. For person to person messages, if you have a separate record for the sender and the receiver, you can do some per-user transformation on the other correspondent, but that might be indexed, so data without keys would still show messaging patterns.