Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

You're probably aware of this, but for the sake of others reading:

Crashing after an fsync failure isn't sufficient if you're using buffered IO either. Dirty pages in the page cache could cause your consensus implementation to e.g. allow voting for two different leaders for the same term if at some future point that machine crashes and the dirty page contained the log record for that vote. Your process would restart after the machine restarts and no longer have access to the dirty page and potentially vote again if asked.

Edit: Thought I'd add the series of steps for this to happen to make it clearer:

1. Process X receives an RPC from Process Y to vote for Y as leader in term 1.

2. Process X writes log record containing vote information to page cache and calls fsync.

3. Process X receives EIO in response to fsync (if it is lucky...) and crashes.

4. Process X restarts and receives a retry of the same RPC from Process Y for term 1 and this time it responds affirmatively because it can see it already voted in term 1 for Process Y, which _should_ be safe.

5. Process X crashes because the machine hosting X experiences a temporary hardware failure.

6. Process X restarts after the hardware failure and receives an RPC from Process Z and responds affirmatively because the dirty page that was available back at T4 never actually made it to disk.

Consensus is now (potentially) broken from electing two leaders for the same term.



You could replace step 3) with "pull power plug from host" for the same effect.

Think of all the extra disk IO the worlds databases are doing to defend against step 3) :)


In distributed system terms, this is a byzantine failure which most consensus mechanisms are not equipped to handle.


And yet many non-Byzantine consensus protocols are equipped to handle the network fault model, which could be seen as equally Byzantine under this definition.

The problem is really that many formal proofs of consensus have focused only on the network fault model, and neglected the storage fault model.

Both network/storage fault models require practical engineering efforts to get right. I think a better term for this is “near-Byzantine” fault tolerance. It's what non-Byzantine fault tolerance looks like when implemented correctly in the real world—the GP comment is a great example of how to approach and think about this from an engineering perspective.

I dive into this in detail also here: https://www.youtube.com/watch?v=rNmZZLant9o


"near-Byzantine" is not a very clear term you can reason about. A system is either Byzantine-fault-tolerant, in which case it handles all Bizantine faults, or it is not. A system that is tolerant to some faults (that you may want to call "Byzantine") is not BFT.

You don't call plaintext SMS "tamper-resistent" because it resists to some simple tampering. You don't call your house "FBI resistant" because you managed to convince them once to turn around.

A Byzantine fault is clearly defined as a case where a specific node may be doing anything, including not know it has failed, including malicious behavior. It is important that people know what class of faults their system is designed to resist; for Raft/Paxos, it is NOT Byzantine faults. Those systems are pretty great, but trying to pretend they aim at BFT is dangerous misinformation...


What then would you specify as the clearly defined storage fault model for non-Byzantine protocols such as Paxos/RAFT that rely on stable storage for correctness?


Anything is possible with Byzantine faults, on the specific failed node. It will not remember voting, it will not remember to vote, it will not remember its identity, etc. PAXOS/Raft are not tolerant to a minority of nodes exhibiting those kinds of faults, only to a minority of nodes being unreachable or partitioned.

Remember that the Byzantine generals had traitors among them, not merely communication issues.


What I mean is, if you're implementing Paxos/RAFT—what do you expect of the disk, that it's perfect?




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: