22 ms·

CASPaxos: Linearizable Databases Without Logs

49 points by GordonS 7y ago

siliconc0w 7y ago
Anyone have a link to the actual whitepaper? The one in the OP 404s. Edit: it's https://arxiv.org/pdf/1802.07000.pdf https://arxiv.org/pdf/1802.07000.pdf
- gigatexal 7y ago
  It seems like a riff on replication where you replicate values instead of operations in a traditional database.
- reubenbond 7y ago
  Fixed, thanks for pointing that out. I didn't realize this was posted here.
hardwaresofton 7y ago
Shameless plug for my writeup of all the different paxos varieties: https://vadosware.io/post/paxosmon-gotta-concensus-them-all https://vadosware.io/post/paxosmon-gotta-concensus-them-all (lots of links to papers inside) It's a fascinating field and there are a LOT of variations of Paxos worth investigating. I recently added a ToC so that it's a little easier to navigate/jump around
jupp0r 7y ago
> It is a slight modification of the original Paxos algorithm, which is very simple and typically used as a minimal building block for more complicated algorithms such as Multi-Paxos Wasn't Raft invented as a teaching tool because Paxos was too hard to understand and implement correctly?
- hinkley 7y ago
  > Paxos algorithm, which is very simple and typically used... Madman, cult, or both?
- uluyol 7y ago
  Personally, and I have heard many other people say this as well, I don't think Raft is any simpler than Paxos. The problem with Paxos is that there is no one way to do things. There are a thousand different variants and techniques that are not all compatible with each other. So to actually implement Paxos essentially requires that you become an expert. The advantage of Paxos is that there are many potential optimizations at your fingertips, depending on your workload. Unlike Paxos, Raft is much more prescriptive: do x, y, and z, and everything will be fine. And really, to a large extend, Raft can be viewed as a description of what many production Paxos implementations would look like.
- mrkeen 7y ago
  I learned Paxos but not Raft. From memory, step one of Raft was to come to consensus on a leader. Isn't that in itself entirely what Paxos solves?
rdtsc 7y ago
CASPaxos has nice latency and recovery times on node failures and partition re-joins. The author of the algorithm has a comparison with other popular consistent distributed databases https://github.com/rystsov/perseus https://github.com/rystsov/perseus I particularly like novelty of using a function closures which makes it elegant and approachable. I also found the idea of the hierarchical ballots from the article pretty interesting. ([config ballot, range ballot, file ballot, register ballot]). And I suppose in the spirit of the original paper, it would be a nested set of closures :-) One thing that might not be obvious though, compared to other databases, is that reads essentially follow the same path as the writes and cost about the same, and even might result in spreading the update to other nodes that don't have the latest value.
jamespitts 7y ago
Relevant Tweet by Denis Rystsov, author of "CASPaxos: Replicated State Machines without logs": https://twitter.com/rystsov/status/1118201415577419776 https://twitter.com/rystsov/status/1118201415577419776

49 points by GordonS 7y ago

Anyone have a link to the actual whitepaper? The one in the OP 404s. Edit: it's https://arxiv.org/pdf/1802.07000.pdf https://arxiv.org/pdf/1802.07000.pdf

gigatexal 7y ago
It seems like a riff on replication where you replicate values instead of operations in a traditional database.
reubenbond 7y ago
Fixed, thanks for pointing that out. I didn't realize this was posted here.

hardwaresofton 7y ago

Shameless plug for my writeup of all the different paxos varieties: https://vadosware.io/post/paxosmon-gotta-concensus-them-all https://vadosware.io/post/paxosmon-gotta-concensus-them-all (lots of links to papers inside) It's a fascinating field and there are a LOT of variations of Paxos worth investigating. I recently added a ToC so that it's a little easier to navigate/jump around

jupp0r 7y ago

> It is a slight modification of the original Paxos algorithm, which is very simple and typically used as a minimal building block for more complicated algorithms such as Multi-Paxos Wasn't Raft invented as a teaching tool because Paxos was too hard to understand and implement correctly?

hinkley 7y ago
> Paxos algorithm, which is very simple and typically used... Madman, cult, or both?
uluyol 7y ago
Personally, and I have heard many other people say this as well, I don't think Raft is any simpler than Paxos. The problem with Paxos is that there is no one way to do things. There are a thousand different variants and techniques that are not all compatible with each other. So to actually implement Paxos essentially requires that you become an expert. The advantage of Paxos is that there are many potential optimizations at your fingertips, depending on your workload. Unlike Paxos, Raft is much more prescriptive: do x, y, and z, and everything will be fine. And really, to a large extend, Raft can be viewed as a description of what many production Paxos implementations would look like.
mrkeen 7y ago
I learned Paxos but not Raft. From memory, step one of Raft was to come to consensus on a leader. Isn't that in itself entirely what Paxos solves?

rdtsc 7y ago

CASPaxos has nice latency and recovery times on node failures and partition re-joins. The author of the algorithm has a comparison with other popular consistent distributed databases https://github.com/rystsov/perseus https://github.com/rystsov/perseus I particularly like novelty of using a function closures which makes it elegant and approachable. I also found the idea of the hierarchical ballots from the article pretty interesting. ([config ballot, range ballot, file ballot, register ballot]). And I suppose in the spirit of the original paper, it would be a nested set of closures :-) One thing that might not be obvious though, compared to other databases, is that reads essentially follow the same path as the writes and cost about the same, and even might result in spreading the update to other nodes that don't have the latest value.

jamespitts 7y ago

Relevant Tweet by Denis Rystsov, author of "CASPaxos: Replicated State Machines without logs": https://twitter.com/rystsov/status/1118201415577419776 https://twitter.com/rystsov/status/1118201415577419776