Hacker News Reader

Comment by magicalhippo | Hacker News Reader

So if I got it right you're still left with a sort of two-phase system, first receive-work & ack-receive, followed by apply-work & ack-apply. However the worker is free to start with the second phase, and the next transaction after the final ack, as soon as it feels like without further coordination.

This works because all conditional checks required by the combined work are performed identically by each worker.

Doesn't this scale as O(n^2) worst case? If the work touches all the variables, and each variable has a constraint, then each worker must remotely read from every other worker, no?

Also, since as far as I can see the workers need to keep old versions of the variables around (in case a remote worker recovering needs to satisfy a remote read), how are these garbage collected?

Quite possibly dumb questions, this isn't my area at all. Enjoyed the read in any case.

View on HN

(1) I'm not sure I fully understand what you are referring to wrt the "acks" but either way, one major difference is that the acks don't have to be made durable in the alg. described by the post. Also, the other key thing to note is that alg. described by the post does not suffer from the blocking or cloggage problems of 2PC.

(2) The post was already too long, so I didn't cover all the cases. The code rewrite algorithm described in the post is indeed O(n^2) if every shard has the possibility of a state-based abort. However, the number of shards that have possibilities of state-based aborts is known before the transaction begins, and since the same values are being sent everywhere, you can always use standard network broadcast techniques to bring the complexity back to O(n).

(3) Garbage collection can work via a high water mark. You keep track of the highest transaction number for which all transactions less than this number have been completed, and can garbage collect values for those versions.

The point with the acks is, as far as I can see, that the client initiating the transaction has to 1) know when each worker has received the transaction request, and 2) when the first worker has completed it and what the result of the transaction is (failed due to constraints or success).

Point 1 is in case a worker dies before it has durably stored the transaction request.

Point 2 is so that the client can move on.

> However, the number of shards that have possibilities of state-based aborts is known before the transaction begins, and since the same values are being sent everywhere, you can always use standard network broadcast techniques to bring the complexity back to O(n)

Ah, good point. That assumes the workers are within broadcast range, but you'll want that anyway for speed. This means a worker will have to push values to other workers, so they'll maintain a queue of these then?

Anyway, thanks for the responses. Like I said, not my field at all, but really fun stuff to ponder.

Yes, it sounds like it might have higher throughput and lower latency when nothing is contending and it isn't touching every shard per transaction. When those conditions are not met it suffers, possibly pathologically.

Actually the approach described by this post does much better than 2PC under contended workloads because it removes the cloggage problem (see the section entitled "The problems with 2PC").

Reply on news.ycombinator.com