Hacker News Reader

Comment by siscia | Hacker News Reader

I definitely miss something, but...

How it is different from a simple mongodb where I store encrypted documents ?

With mongodb, you either pass your key along with query or lose your ability to search. In our case, we don't pass the key to the server, yet having the ability to query

Can you explain better how ?

And what you mean by "search" ?

For example, full text search over your text queries, or range queries for your numerical data.

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.

OK but aren't you thus pushing much of the intelligence typically part of the database server to the database clients?

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.

Yes, you are right. The server stores indexes (which are actually trees), but the query logic is on clients.

Very interesting. How much additional data, compared to a conventional fat server architecture, needs to be sent across the wire with a fat client? The blog post makes it sound not too bad.

Usually it's order of 100-200 KB per query but caching things like the tree root makes this footprint smaller (e.g. second query is always faster than first one).

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.

Does this architecture open you up to race conditions, where two clients are trying to update the index at the same time?Client 1 downloads the index, Client 2 downloads the same index, they both make updates to the index and try re-uploading — is one of the index upates going to be lost? Or are you using the b-tree/structuring the server in such a way that obviates this risk?

HN doesn't allow to reply too deep in the tree of comments, so I continue here.

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.

Well, I think what makes it interesting is that the simultaneous write issues don't just apply to ZODB, but the indexes (and/or balancing data) inside the encrypted buckets being maintained by the clients to maintain their own bsts, per my question above. You can't just put a transaction around one bucket because they have to, together, form a consistent 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.

I think, your points are largely correct. You indeed need to lock multiple buckets when you commit data which could be slow.

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.

Reply on news.ycombinator.com