Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

GoshawkDB: A distributed, transactional, fault-tolerant object store

goshawkdb.io

Post reply on HN
Print view View original

41–46 of 46 posts

Re: GoshawkDB: A distributed, transactional, fault-tolerant object store

#41

Post by msackman »

rystsov wrote: post #40
msackman wrote: post #37

Earlier quoted context omitted.

I don't think that's the problem though. The problem that I'm thinking of is that when a cluster grows in size, due to the use of consistent hashing, there'll be a set of objects that need to move between nodes. Calculating and achieving that movement is what concerns me. The exact properties are explained early on in http://arxiv.org/abs/1503.04988 I'm not expecting to ever need to model a global property of "these…

By the way, I always was wondering why the schemas with consistent hashing maintained via the ring are more popular approach than treating key space as a line (-∞,+∞), maintaining the explicit map from segments and rays of keys to the replica groups and split the group/segment when replica group becomes too hot or heavy. IMHO the perfect hashing solves the problem of distributing the data but the load may follow comp…

Yes, you're right. Now where that paper finishes is pretty much where GoshawkDB starts. Because with GoshawkDB, the server controls the object UUId, you can push as much entropy in there as necessary so the problem identified in the paper is gone. However, ultimately what GoshawkDB ends up generating is basically a set of numbers that you interpret as a way to construct an order of the different nodes (it's the path down the tree, as described in the paper). This set of numbers you could intentionally change in order to change the load balancing to exploit locality.

So yes, currently it'll rigorously enforce a uniform balancing. However, it should be possible to move objects around if/when necessary. I doubt that'll be in for 0.2 though!

Re: GoshawkDB: A distributed, transactional, fault-tolerant object store

#43

Post by lmm »

msackman wrote: post #27
lmm wrote: post #24

Earlier quoted context omitted.

> The point I was trying to make is the decoupling between cluster size and F. ZK, for example, requires that the cluster size is exactly 2F+1, not is minimum 2F+1. That means that as the cluster size increases, performance will decrease as more nodes have to be contacted. How does this work? Suppose we set F=2 and have 7 nodes, A-G. Client 1 tries to write, contacting 5 nodes, A-E. A and B are down at this point, bu…

Ok, so F=2, so 2F+1 is 5. So client 1 creates a txn that writes to object x. x has replicas on A-E, but not F and G. So client 1's txn gets sent to F+1 drawn from A-E. In your scenario A and B are down so that only leaves C, D and E. So they vote on the txn and vote to Commit. This vote forms a Paxos round as per Gray and Lamport's paper "Consensus on transaction commit". Assuming that all these votes get received an…

But isn't it the restriction to single-row transactions that makes it possible to isolate a given transaction to a particular subset of the cluster? If you allow a transaction across any set of rows, how can you possibly do consistent hashing of that, when the next transacting might involve a different (but maybe overlapping) set of rows?

Re: GoshawkDB: A distributed, transactional, fault-tolerant object store

#44

Post by msackman »

lmm wrote: post #43
msackman wrote: post #27

Earlier quoted context omitted.

Ok, so F=2, so 2F+1 is 5. So client 1 creates a txn that writes to object x. x has replicas on A-E, but not F and G. So client 1's txn gets sent to F+1 drawn from A-E. In your scenario A and B are down so that only leaves C, D and E. So they vote on the txn and vote to Commit. This vote forms a Paxos round as per Gray and Lamport's paper "Consensus on transaction commit". Assuming that all these votes get received an…

But isn't it the restriction to single-row transactions that makes it possible to isolate a given transaction to a particular subset of the cluster? If you allow a transaction across any set of rows, how can you possibly do consistent hashing of that, when the next transacting might involve a different (but maybe overlapping) set of rows?

Well I have no idea of how Cassandra works, so I can't comment on that.

GoshawkDB gets every object touched in the transaction to vote on the outcome of the transaction, in parallel, and guarantees that if two transactions touch the same object, there must be at least one copy of that object that gets to vote on both transactions, thus can enforce any dependencies as necessary.

Edit: further clarity: the use of consistent hashing in GoshawkDB is to ensure that each node has an equal number of object copies. It is the Paxos Synod algorithm that ensures a majority of those copies of any object get to vote on every transaction that touches that object, thus ensures that for any two transactions touching the same object, there is at least one copy of the object that gets to vote on both.

Re: GoshawkDB: A distributed, transactional, fault-tolerant object store

#45

Post by lmm »

msackman wrote: post #44
lmm wrote: post #43

Earlier quoted context omitted.

But isn't it the restriction to single-row transactions that makes it possible to isolate a given transaction to a particular subset of the cluster? If you allow a transaction across any set of rows, how can you possibly do consistent hashing of that, when the next transacting might involve a different (but maybe overlapping) set of rows?

Well I have no idea of how Cassandra works, so I can't comment on that. GoshawkDB gets every object touched in the transaction to vote on the outcome of the transaction, in parallel, and guarantees that if two transactions touch the same object, there must be at least one copy of that object that gets to vote on both transactions, thus can enforce any dependencies as necessary. Edit: further clarity: the use of consi…

Ok. So in practice a multi-row transaction will have to contact >2F+1 nodes (2F+1 for each object involved, likely overlapping but not completely)?

Re: GoshawkDB: A distributed, transactional, fault-tolerant object store

#46

Post by msackman »

lmm wrote: post #45
msackman wrote: post #44

Earlier quoted context omitted.

Well I have no idea of how Cassandra works, so I can't comment on that. GoshawkDB gets every object touched in the transaction to vote on the outcome of the transaction, in parallel, and guarantees that if two transactions touch the same object, there must be at least one copy of that object that gets to vote on both transactions, thus can enforce any dependencies as necessary. Edit: further clarity: the use of consi…

Ok. So in practice a multi-row transaction will have to contact >2F+1 nodes (2F+1 for each object involved, likely overlapping but not completely)?

Not quite. Only F+1 are required per object to vote. As I explain in the blog post (https://goshawkdb.io/blog.html#20151224), the remaining F can be sent after the outcome is known.
Post reply on HN