5 ms·

It looks like the core of the idea is "object stealing". In most consensus algorithms you'll have a single leader, worldwide, that is in charge of sequencing al

by ccleve 9y ago

It looks like the core of the idea is "object stealing". In most consensus algorithms you'll have a single leader, worldwide, that is in charge of sequencing all objects. Either that, or you partition objects across leaders and then coordinate across partitions. In this algorithm you have multiple leaders, where a leader can be in charge of a particular object temporarily by "stealing" it. This brings control to the datacenter that needs it, reducing latency. It's an interesting idea, and I haven't fully absorbed the paper. But I'll comment on it anyway. It's always easier to criticize when you're ignorant of the details :) In general, I don't like these algorithms that only guarantee a partial ordering. In other words, instead of having a single global total ordering of all transactions, you have an ordering of operations that apply to a single object or key or a related group of keys. This means you can't know if object A got updated before object B. You can't know the total state of the system as of a snapshot in time, or as of the moment a node membership change happens. (Maybe. There might be workarounds for these issues, at the cost of some complexity.) This paper is a good contribution, but we ain't there yet.

ccleve 9y ago
Although I will say that this would handle a "follow the sun" workload pretty well.
matthelb 9y ago
I also haven't read through the technical report in detail, but in skimming through parts of it, it looks like WPaxos is supposed to provide linearizability. More specifically, the authors state that: > WPaxos maintains separate logs for every object and provides per-object linearizability. Linearizability is a composable correctness condition, so per-object linearizability implies that the composition of all the objects is linearizable. Thus, WPaxos does in fact provide a single total ordering of all operations. Nearly all of the replicated state machines via consensus protocols (Paxos, EPaxos, Mencius, Generalized Paxos, etc.) provide this same consistency level.
- wickawic 9y ago
  Time to let my ignorance shine: > Linearizability is a composeable correctness condition So if all I know is that A1 precedes A2 and that B1 precedes B2, how do I make assertions about the ordering of A2 and B2? Is “linear” in the context that you are talking about more specific than “orderable”? GP isn’t complaining that the algorithm is incorrect, just that it doesn’t have the property of being replayed or reversed in a deterministic way. Most applications don’t need this property, I am just trying to see if I’m missing a part of your argument.
  - matthelb 9y ago
    Maurice Herlihy and Jeanette Wing introduced linearizability back in 1990 [1]. It stipulates that the result of a concurrent execution of the system is equivalent to a result from a sequential execution where the order of the sequential execution respects the real-time order of operations in the concurrent execution. In this context, you could probably use "linear" and "orderable" to mean the same thing. The idea is that, for any linearizable execution, there exists an equivalent total order of the operations. Because there exists a total order, if a client C1 sees A2 before B2 then a client C2 cannot see B2 before A2. [1] https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf
    - pests 9y ago
      You still haven't answered the question though. The definition of linearizability is not in question. The question is does this specific system we are discussing have global-linearizability or is there separate per-object (or some other bucketing method) linearizability.
      - matthelb 9y ago
        Sorry, I was trying to give the GP more context for my initial comment. As I said in my initial comment, the authors state that WPaxos provides per-object linearizability, which implies that it provides (to use your term, "global"-)linearizability.
grogers 9y ago
I agree to an extent, spanner showed that point in time global snapshots can be practical. But many (most?) applications are fine with just serializable transactions, they don't need the additional real-time preserving guarantee of strict serializability. So I expect to see more of this in the future where constraints are relaxed just slightly.

by ccleve 9y ago

ccleve 9y ago

Although I will say that this would handle a "follow the sun" workload pretty well.

matthelb 9y ago

I also haven't read through the technical report in detail, but in skimming through parts of it, it looks like WPaxos is supposed to provide linearizability. More specifically, the authors state that: > WPaxos maintains separate logs for every object and provides per-object linearizability. Linearizability is a composable correctness condition, so per-object linearizability implies that the composition of all the objects is linearizable. Thus, WPaxos does in fact provide a single total ordering of all operations. Nearly all of the replicated state machines via consensus protocols (Paxos, EPaxos, Mencius, Generalized Paxos, etc.) provide this same consistency level.

wickawic 9y ago
Time to let my ignorance shine: > Linearizability is a composeable correctness condition So if all I know is that A1 precedes A2 and that B1 precedes B2, how do I make assertions about the ordering of A2 and B2? Is “linear” in the context that you are talking about more specific than “orderable”? GP isn’t complaining that the algorithm is incorrect, just that it doesn’t have the property of being replayed or reversed in a deterministic way. Most applications don’t need this property, I am just trying to see if I’m missing a part of your argument.
- matthelb 9y ago
  Maurice Herlihy and Jeanette Wing introduced linearizability back in 1990 [1]. It stipulates that the result of a concurrent execution of the system is equivalent to a result from a sequential execution where the order of the sequential execution respects the real-time order of operations in the concurrent execution. In this context, you could probably use "linear" and "orderable" to mean the same thing. The idea is that, for any linearizable execution, there exists an equivalent total order of the operations. Because there exists a total order, if a client C1 sees A2 before B2 then a client C2 cannot see B2 before A2. [1] https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf
  - pests 9y ago
    You still haven't answered the question though. The definition of linearizability is not in question. The question is does this specific system we are discussing have global-linearizability or is there separate per-object (or some other bucketing method) linearizability.
    - matthelb 9y ago
      Sorry, I was trying to give the GP more context for my initial comment. As I said in my initial comment, the authors state that WPaxos provides per-object linearizability, which implies that it provides (to use your term, "global"-)linearizability.

grogers 9y ago

I agree to an extent, spanner showed that point in time global snapshots can be practical. But many (most?) applications are fine with just serializable transactions, they don't need the additional real-time preserving guarantee of strict serializability. So I expect to see more of this in the future where constraints are relaxed just slightly.