ZeroDB – A Peek Under the Hood
blog.zerodb.io
blog.zerodb.io
When a given bucket is requested and decrypted by the client, it will have the data as well as the references that let the client treat them as a B-tree, presumably because the clients put them there?
I'm taking that assumption from "The server doesn’t know how individual objects are organized within a tree structure, or whether they even belong to a tree structure at all."
What does this mean for adding a node? Does the client have to traverse the whole B-tree (requesting log(n) entries) down to the point of addition? How about rebalancing, etc? It seems like the clients would be wholly responsible for maintaining the tree.
Are you addressing this in any way?
Most fatal errors just mean you lose an entire atomic update, and the type where you "successfully" write bad data imply the same sort of repairs as server-side maintenance would.
In practice, I think the biggest issue is that if you had to restore a backup, there'd be no way to restore only -your- tree, since the server doesn't know structure or ownership of the buckets. You'd have to roll back everyone in the bucket store.
I don't want to be too negative, because I think having something like this is a good idea. It's plain there are challenges to be solved here though.
Edit: though I do catch your point that N clients all maintaining the same index tree is potentially like having a non-redundant N-wide storage array--failure rate is cumulative. Think you could possibly mitigate this with a single-source-of-truth per table/index client-side design, but that's an obvious potential bottleneck.
That's right. Except, if clients maintain the tree, there must be some "maintenance" client, or each client must do some maintenance (find and fix things that go wrong).
My issue is, indeed, the cumulative failure rate; and I have enough experience with faulty hardware, especially memory, to know that important data needs reliable memory (e.g. ECC), and a "client does maintenance" model basically makes that impossible, unless you can mandate that all connecting clients have ECC memory - essentially, server class machines.
The problem with clients maintaining indices runs very deep: Uniqueness constraints are often implemented through index. If the index integrity is violated (easy to do - you have 1000 clients, anything that goes wrong in any of them - power surge, virus, ..., may corrupt the index), then it is possible for the entire database integrity to be violated.
I'm sure there are way to mitigate this, reducing the probability down to negligible (which is what ECC does - it reduces memory error probability to negligible, not to zero which is impossible); for example, you could have every client maintain their own index, not relying on any other client's index but only on their immutable rows. That would still let a client violate database integrity, but any other client would immediately notice and refuse to work with the database.
However, I have so far not seen any reference to these issues by the ZeroDB guys. I am waiting patiently.
I'm not sure that ZeroDB will necessarily have all the answers here prepackaged. I'm still waiting to see exactly how intelligent their client modules are. I doubt they're just delivering a bucket store, so I assume they'll have client-side code that'll encapsulate the BST handling. The question is whether it's naive or accounts for some of this. If nothing else, I assume michwill is probably taking notes!
At any rate, my hope is this ends up being an interesting enough solution to build some degree of pattern or best practice over to handle some of these aspects. These might be as simple (and limiting) as "one table, one source of truth, period," or "Use for write-seldom; read-often applications only," or some other thing like that.
Even if so, this could be quite useful for -some- subset of applications, or at the very least a useful step on the way to figuring out how to do this sort of thing.
Certainly there are other challenges here as well. Beyond integrity issues, there's still the information leakage issues. It's already been mentioned that a binary search leaks order information to begin with, but if you know what kind of tree is being used you leak a lot of order information as the rotates happen.
But again, maybe surmountable. I'm eagerly awaiting the source implementation so we can dig in.
Yes, you're correct! ;-)
> "one table, one source of truth, period," or "Use for write-seldom; read-often applications only,"
Right. Another model - "write and read only your private information". So, three use-cases here
> information leakage issues
I already think, for solving this we probably should just switch to ORAM. Very valid concern! That said, we cannot really deduce the order of objects referenced in leaf nodes (and there could be a thousand of them).
In any case. Expect our implementation to be extremely simple (but useful) first. Probably suitable for "users record their private info" application. Then we'll be addressing scalability issues, information leakage etc.
One thing which we will probably inherit from ZODB is server-side versioning of all objects. E.g. if something gets corrupted, it's easy enough to roll back to a previous version.
If the model is "each user has its very own private tree" applies (would be the case for gmail or evernote-like application), I think clients quite can maintain it (having the version history, of course). If it's groups of users having access to the same objects, we should have some maintenance clients.
Have experienced nightmarrish scenarios when updating codebases.
While that's ok for Zope/ZODB developers, it's not for an average user. We need to wrap it up to make easily usable, without requiring developers to read tons of documentation and "Design patterns" in advance!
And, obviously, some universal json query language is needed
I guess, we can have another type of behavior where all new fields are indexed. It doesn't sound like a "clean way" to me, however some developers could desire that
It looks like ZeroDB abstracts away these issues, luckily. Is it intended to be a full-scale application data store, or something more specialized like a secrets store?
We plan to make it a full-scale database. For that, we obviously require to have some convenient query language (similar or even compatible with Mongo's).
We've talked to original developers of ZODB and they (independently) suggested that having a language-independent query language is something they constantly thought of :-) In fact, it seems like many of them dream to take ZODB (or a db based on it ;-) where Mongo is now.
The server can however infer quite a lot from the order of bucket request, especially which buckets constitute a tree.
Do they cater to different uses?
In our db, random observer cannot see how data are ordered or whether elements are equal to each other.
Homomorfic encryption would be ideal of course, but it is slow and impractical for the moment
But as michwill states (and CryptDB acknowledges), their approach either leaks information or precludes classes of expressions. For example, their order-preserving encryption could be susceptible to a brute-force attack via 'a > b' ... '(a+1) > b' ... '(a+2) > b'
Edit: I phrased that wrong. How do you usefully query other user's data with only your keys?
The use case - any private data which you'd like to encrypt on the server while preserving ability to search. Medical records, financial data, emails are some examples.
Easier to say what this database is not for. Big data applications where you need to use a significant portion of data in the db (like 10%) in map-reduce queries is probably not what ZeroDB would be practical for.
The final outstanding question I have though is: How do you deal with data you aren't the owner of? Is this strictly targeted at scenarios where you are the sole owner?
The other is when the owner of the data is some group (like JP Chase). In this case we can have server-side quotas for handling cases when one or several clients are compromised. So, in this case it's more about distributing trust
How it is different from a simple mongodb where I store encrypted documents ?
And what you mean by "search" ?
The idea is that data in databases is organized in B-Trees, so we traverse those from a remote client. It is fast enough because usually only logarithmic fraction of a tree needs to be seen by the client.
In this case, the "database server" is basically a dumb remote B-tree server, right? It's not running queries of any sort, or maintaining indices?
Not putting it down, just clarifying that the structure of this database system is very different. Or appears so, at least.
We tested it with pretty ad-hoc parameters (just to check if it's practical at all!), will soon write an automatic optimizer for them, minimizing query time.
ZODB on which we base is ACID-complaint, so it cares about simultaneous writes. You either don't use cache, or get invalidation requests if you do (so that you have up-to-date tree if you want to update).
Though, it sounds like the ideal situation is when each user has his own private data, so there are not so many simultaneous writes into the same tree.
That's especially true when you consider that to maintain log n the tree will have to be a self-balancing tree, so any given modification can touch a larger number of nodes during rotation.
I might be missing something obvious, but if the client has to maintain the tree I have a hard time seeing how you wouldn't have to queue access into the tree for modifying operations. That seems like it could be a pretty significant issue for some applications.
My point is that you can tolerate that if your application is something like gmail. Client A has his own tree saved on the server, not intersecting with the tree of client B. Client A probably is not going to write from multiple places simultaneously too often.
But if you have groups of clients writing to the same tree, I think it's better to have some writing client which handles multiple commits of others.