Comment by geoelectric | Hacker News Reader

Comment by geoelectric | Hacker News Reader

Parent Full thread

Well, if the indexes can all be updated with transactional integrity around the whole thing (which I think you need anyway, per thread below about having to do client-side rotates to self-balance the tree and keep log n) in theory this is no worse than a memory overrun/etc. in the original database server.

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.

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

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.

Yeah. You mention ECC, and I was previously thinking some sort of integrity-checking solution modeled on parity bits could work. Problem with that, of course, is I think something needs to have complete knowledge of the data structure to make it work, plus now you have yet another thing to update over network.

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.

> I assume michwill is probably taking notes!

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.

Thank you for making a very good comment!

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.

Reply on news.ycombinator.com