3 ms·

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. I

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.

jacquesm 6y ago
The tricky bit to me is that fundamentally deletion should not be harder than insertion, but because we have historically only focused on the happy path nobody cares at all about the deletion mechanism. Whereas a secure erase-in-place of a field option alone would already take you to 80% or more of a workable solution. Perfection, the way you describe it is for now unattainable. But the bigger problem as far as my practice tells me is that people simply don't care and set the 'deleted' bit and leave the plain text records + backups + log files all untouched. The low hanging fruit is pretty much dragging the ground.
- jandrewrogers 6y ago
  Sure, you can trivially design a data structure where insert and delete have the same cost. This works if you don’t care about query performance; most people care about query performance a great deal. This was litigated in the marketplace decades ago. Even every open source database rejects designs that produce rubbish query performance. It also does not reflect the real-world distribution of operations between insert and delete — we do a lot more inserts. The “erase-in-place” operations you mention were common in databases a few decades ago and abandoned because the typical performance was terrible compared to the alternative. I am old enough I even implemented a few. It isn’t like these designs didn’t exist, they were deeply flawed for reasons that apply today. This has nothing to do with perfection. Database engineers would love if deletes where inexpensive even in the absence of hard delete requirements, as that would make update operations, which people want, dramatically cheaper. But that isn’t the reality. You are essentially re-litigating settled database kernel engineering without understanding why they are designed the way they are. If you thinking there is “low hanging fruit dragging on the ground” then I encourage you to prove it by designing a useful database kernel that can scale deletes while preserving insert and query performance, the two operations that drive all economics in databases. You’ll be instantly famous as a computer scientist because there are some nasty theoretical computer science problems in there.

jacquesm 6y ago

The tricky bit to me is that fundamentally deletion should not be harder than insertion, but because we have historically only focused on the happy path nobody cares at all about the deletion mechanism. Whereas a secure erase-in-place of a field option alone would already take you to 80% or more of a workable solution. Perfection, the way you describe it is for now unattainable. But the bigger problem as far as my practice tells me is that people simply don't care and set the 'deleted' bit and leave the plain text records + backups + log files all untouched. The low hanging fruit is pretty much dragging the ground.

jandrewrogers 6y ago
Sure, you can trivially design a data structure where insert and delete have the same cost. This works if you don’t care about query performance; most people care about query performance a great deal. This was litigated in the marketplace decades ago. Even every open source database rejects designs that produce rubbish query performance. It also does not reflect the real-world distribution of operations between insert and delete — we do a lot more inserts. The “erase-in-place” operations you mention were common in databases a few decades ago and abandoned because the typical performance was terrible compared to the alternative. I am old enough I even implemented a few. It isn’t like these designs didn’t exist, they were deeply flawed for reasons that apply today. This has nothing to do with perfection. Database engineers would love if deletes where inexpensive even in the absence of hard delete requirements, as that would make update operations, which people want, dramatically cheaper. But that isn’t the reality. You are essentially re-litigating settled database kernel engineering without understanding why they are designed the way they are. If you thinking there is “low hanging fruit dragging on the ground” then I encourage you to prove it by designing a useful database kernel that can scale deletes while preserving insert and query performance, the two operations that drive all economics in databases. You’ll be instantly famous as a computer scientist because there are some nasty theoretical computer science problems in there.