71–80 of 88 posts
I think it is interesting but obvious in hindsight that it is necessary to have the distributed system under test report the time/order things actually happened to enable accurate validation against an external model of the system instead of using wall-clock time.
Very impressed with this report. Whenever I read TigerBeetle's claims on reliability and scalability, I'd think "ok, let's wait for the Jepsen report". This report found a number of issues, which might be a cause for concern. But I think it's a positive because they didn't just fix the issues, they've expanded their internal test suite to catch similar bugs in future. With such an approach to engineering I feel like…
Thanks! Yes, we have around 6,000+ assertions in TigerBeetle. A few of these were overtight, hence some of the crashes. But those were the assertions doing their job, alerting us that we needed to adjust our mental model, which we did. Otherwise, apart from a small correctness bug in an internal testing feature we added (only in our Java client and only for Jepsen to facilitate the audit) there was only one correctne…
https://csrc.nist.gov/projects/automated-combinatorial-testi...
My intro to other categories of test generation was usually this paper:
https://cs.stanford.edu/people/saswat/research/ASTJSS.pdf
Maybe see of your team can build combinatorial- or path-based testing in Zig next.
Earlier quoted context omitted.
The scenarios described in our QCon London talk linked above. This surveys the excellent storage fault research from UW-Madison, and in particular: “Can Applications Recover from fsync Failures?” “Protocol-Aware Recovery for Consensus-Based Storage” Finally, I'd recommend watching “Consensus and the Art of Durability”, our talk from SD24 in NYC last year: https://www.youtube.com/watch?v=tRgvaqpQPwE
[disks are] somewhere between non-byzentine fault tolerance and Byzantine fault tolerance ... you expect the disk to be almost an active adversary ... ... so you start to see just a single disk as a distributed system My goodness, not at all! If you can't trust the interface to a local disk then you're lost just at a fundamental level. And even ignoring that, a disk is an implementation detail of a node in a distribu…
It’s a mindbender of a paradigm-shift for how to think about local recovery actions in the context of the global consensus protocol!
Earlier quoted context omitted.
[disks are] somewhere between non-byzentine fault tolerance and Byzantine fault tolerance ... you expect the disk to be almost an active adversary ... ... so you start to see just a single disk as a distributed system My goodness, not at all! If you can't trust the interface to a local disk then you're lost just at a fundamental level. And even ignoring that, a disk is an implementation detail of a node in a distribu…
Recommend you first read the FAST18-winning “Protocol-Aware Recovery for Consensus-Based Storage”. It’s a mindbender of a paradigm-shift for how to think about local recovery actions in the context of the global consensus protocol!
> Disks and flash devices exhibit a subtle and complex failure model: a few blocks of data could become inaccessible or be silently corrupted [8, 9, 32, 59]. Although such storage faults are rare compared to whole-machine failures, in large-scale distributed systems, even rare failures become prevalent [60, 62]. Thus, it is critical to reliably detect and recover from storage faults.
It's not true in general that a node in a distributed system binds its persisted state to a local disk, or flash device, or any specific implementation of any specific kind of storage system. The storage layer is the responsibility of the node to manage, and irrelevant to the wider distributed system in which the node is a participant. Any of those kinds of storage faults need to be accommodated by the node that utilizes those storage layers, but their specific details don't need to be communicated beyond the specific node where they apply. And it's not at all critical for those nodes to detect and recover from any faults in their storage layer; those faults can easily be communicated to the broader distributed system, which necessarily must be able to handle node-specific failures like those without breaking everything down!
> how to think about local recovery actions in the context of the global consensus protocol!
Local recovery actions, or any other kinds of node-specific details, have no relevance or influence on the information communicated thru the the global consensus protocol. A node can persist its state to a local disk, or to RAM, or to an S3 object, or anything else, and none of these details matter at all to the details that node communicates to other nodes in its cluster.
tl;dr: nodes don't necessarily persist state to local disk
Earlier quoted context omitted.
Recommend you first read the FAST18-winning “Protocol-Aware Recovery for Consensus-Based Storage”. It’s a mindbender of a paradigm-shift for how to think about local recovery actions in the context of the global consensus protocol!
I've read that paper for sure! > Disks and flash devices exhibit a subtle and complex failure model: a few blocks of data could become inaccessible or be silently corrupted [8, 9, 32, 59]. Although such storage faults are rare compared to whole-machine failures, in large-scale distributed systems, even rare failures become prevalent [60, 62]. Thus, it is critical to reliably detect and recover from storage faults. It…
In fact, an early version of TigerBeetle implemented one of these from Cowling and Liskov’s VSR’12 paper.
However, since then, we invested in TigerBeetle’s stable storage, for reasons which I won’t go into further here.
If you are curious to learn more about all the stable storage techniques in TigerBeetle in particular (again, this is not trying to suggest that VSR can’t also run without stable storage, or to deny other techniques such as object storage or tiering!), but if these things are interesting for you, and if you do want to learn more, then I’d recommend diving into “Durability and the Art of Consensus”.
Earlier quoted context omitted.
Thanks! Yes, we have around 6,000+ assertions in TigerBeetle. A few of these were overtight, hence some of the crashes. But those were the assertions doing their job, alerting us that we needed to adjust our mental model, which we did. Otherwise, apart from a small correctness bug in an internal testing feature we added (only in our Java client and only for Jepsen to facilitate the audit) there was only one correctne…
The correctness bug was due to combinations of features. I'm curious if you've looked into combinatorial testing which NIST claimed knocks out almost all bugs when 6-way testing was used. https://csrc.nist.gov/projects/automated-combinatorial-testi... My intro to other categories of test generation was usually this paper: https://cs.stanford.edu/people/saswat/research/ASTJSS.pdf Maybe see of your team can build combi…
https://csrc.nist.gov/CSRC/media/Projects/Automated-Combinat...
Earlier quoted context omitted.
The correctness bug was due to combinations of features. I'm curious if you've looked into combinatorial testing which NIST claimed knocks out almost all bugs when 6-way testing was used. https://csrc.nist.gov/projects/automated-combinatorial-testi... My intro to other categories of test generation was usually this paper: https://cs.stanford.edu/people/saswat/research/ASTJSS.pdf Maybe see of your team can build combi…
Edit to add 2019, NIST, intro slides on combinatorial testing since it's a better overview: https://csrc.nist.gov/CSRC/media/Projects/Automated-Combinat...
Earlier quoted context omitted.
I've read that paper for sure! > Disks and flash devices exhibit a subtle and complex failure model: a few blocks of data could become inaccessible or be silently corrupted [8, 9, 32, 59]. Although such storage faults are rare compared to whole-machine failures, in large-scale distributed systems, even rare failures become prevalent [60, 62]. Thus, it is critical to reliably detect and recover from storage faults. It…
I’m not disagreeing that diskless crash recovery protocols exist. In fact, an early version of TigerBeetle implemented one of these from Cowling and Liskov’s VSR’12 paper. However, since then, we invested in TigerBeetle’s stable storage, for reasons which I won’t go into further here. If you are curious to learn more about all the stable storage techniques in TigerBeetle in particular (again, this is not trying to su…
Earlier quoted context omitted.
I’m not disagreeing that diskless crash recovery protocols exist. In fact, an early version of TigerBeetle implemented one of these from Cowling and Liskov’s VSR’12 paper. However, since then, we invested in TigerBeetle’s stable storage, for reasons which I won’t go into further here. If you are curious to learn more about all the stable storage techniques in TigerBeetle in particular (again, this is not trying to su…
I've read that paper, and all of the papers that TigerBeetle mentions in any and all of its docs/blog posts/etc. Stable storage doesn't matter to the points I'm trying to shine a light on here. It's not "diskless" that I'm talking about, in fact I'm not talking about "crash recovery" at all -- !
To be clear, “Durability and the Art of Consensus” is not a paper.
> tl;dr: nodes don't necessarily persist state to local disk
In the consensus literature, this is sometimes referred to as “diskless crash recovery”. For example, see work by Dan Ports.
> Local recovery actions, or any other kinds of node-specific details, have no relevance or influence on the information communicated thru the the global consensus protocol.
This goes directly against the central finding of PAR, which gives counter-examples where your statement does not universally hold true.
Again, it’s not intuitive. And that’s why it won FAST18—because it says “everything we know is wrong”. Complete red pill and mindbender.
Earlier quoted context omitted.
I've read that paper, and all of the papers that TigerBeetle mentions in any and all of its docs/blog posts/etc. Stable storage doesn't matter to the points I'm trying to shine a light on here. It's not "diskless" that I'm talking about, in fact I'm not talking about "crash recovery" at all -- !
> I’ve read that paper To be clear, “Durability and the Art of Consensus” is not a paper. > tl;dr: nodes don't necessarily persist state to local disk In the consensus literature, this is sometimes referred to as “diskless crash recovery”. For example, see work by Dan Ports. > Local recovery actions, or any other kinds of node-specific details, have no relevance or influence on the information communicated thru the t…
More broadly, there's no concept of "crash recovery" at the system level, which has any meaningful utility. Nodes are either there or they're not there, exactly how they crash or recover from their crashes are irrelevant to the overall distributed system, insofar as if a crashed-and-recovered node comes back online, it's gonna need to re-sync with its peers before it can talk to anyone else, and that's not anything to do with "crash recovery" related to local disk or anything like that (which is all implementation details of the node itself) -- it's just normal node synchronization, orthogonal to any state storage stuff of the node.
PAR is something that your system can maybe implement, it's not any kind of rule or definition or requirement that all systems of some classification must satisfy..!