Should only delete entries if they conflict with a new one #66

Closed
colin-scott opened this Issue Aug 13, 2015 · 11 comments

Comments

Projects
None yet
2 participants
@colin-scott
Contributor

colin-scott commented Aug 13, 2015

Found through fuzz testing:

Suppose a follower with an empty log receives an AppendEntries containing 2 entries. The follower appends these to its log.

Then the follower subsequently receives an AppendEntries containing only the first of the previous 2 entries. [This message was delayed].

Currently, the follower will inadvertently delete the 2nd entry from its log.

This is not just a performance issue: it can cause raft to violate the "Leader Completeness" safety property: the leader was under the impression that the follower had 2 entries in its log, and may have decided to commit both entries. If another leader then overtakes it, it will not necessarily have both committed entries in its log.

@ktoso

This comment has been minimized.

Show comment
Hide comment
@ktoso

ktoso Aug 13, 2015

Owner

Great catch as always, thanks @colin-scott!
I might actually want to fix this right away, should be easily testable in isolation.

Owner

ktoso commented Aug 13, 2015

Great catch as always, thanks @colin-scott!
I might actually want to fix this right away, should be easily testable in isolation.

@ktoso ktoso self-assigned this Aug 13, 2015

@ktoso

This comment has been minimized.

Show comment
Hide comment
@ktoso

ktoso Aug 13, 2015

Owner

This is actually a bit weird, so allow me to re-cap the exact case the fuzz test found.
Do you mean that the same Leader sends those messages (same Term)?

  • Akka guarantees that delivery order is consistent with send order (for a given pair of Actors A and B).
  • If Leader L, sends the AppendEntries [1], and then AppendEntries [1,2], [1,2] will not be delivered "before" [1]. [1] may never arrive though.

I don't think there is re-delivery of [1] implemented, and at-worst the [1,2] could be re-delivered...

Or are we talking about 2 different leaders sending those 2 messages? Then it seems like the "longest log wins" should be applied, no? I'll dig into it (need to finally get back to hakking on this project, so that's a good reason to get me remember the impl and algorithm ;))

Owner

ktoso commented Aug 13, 2015

This is actually a bit weird, so allow me to re-cap the exact case the fuzz test found.
Do you mean that the same Leader sends those messages (same Term)?

  • Akka guarantees that delivery order is consistent with send order (for a given pair of Actors A and B).
  • If Leader L, sends the AppendEntries [1], and then AppendEntries [1,2], [1,2] will not be delivered "before" [1]. [1] may never arrive though.

I don't think there is re-delivery of [1] implemented, and at-worst the [1,2] could be re-delivered...

Or are we talking about 2 different leaders sending those 2 messages? Then it seems like the "longest log wins" should be applied, no? I'll dig into it (need to finally get back to hakking on this project, so that's a good reason to get me remember the impl and algorithm ;))

@colin-scott

This comment has been minimized.

Show comment
Hide comment
@colin-scott

colin-scott Aug 13, 2015

Contributor

You're absolutely right that this would only be triggered if you moved to UDP instead of TCP -- TCP guarentees in-order delivery, and this bug depends on a delayed message falling behind a later message between the same sender and receiver.

Contributor

colin-scott commented Aug 13, 2015

You're absolutely right that this would only be triggered if you moved to UDP instead of TCP -- TCP guarentees in-order delivery, and this bug depends on a delayed message falling behind a later message between the same sender and receiver.

@colin-scott

This comment has been minimized.

Show comment
Hide comment
@colin-scott

colin-scott Aug 13, 2015

Contributor

It's possible that you could trigger this with 2 different leaders? Not sure. But my fuzz test only involved a single leader sending the AppendEntries messages.

*Is it Akka that guarantees in-order delivery, or is it TCP?

Contributor

colin-scott commented Aug 13, 2015

It's possible that you could trigger this with 2 different leaders? Not sure. But my fuzz test only involved a single leader sending the AppendEntries messages.

*Is it Akka that guarantees in-order delivery, or is it TCP?

@colin-scott

This comment has been minimized.

Show comment
Hide comment
@colin-scott

colin-scott Aug 13, 2015

Contributor

Interesting, akka does appear to guarentee in-order delivery:

http://doc.akka.io/docs/akka/snapshot/general/message-delivery-reliability.html#Discussion__Message_Ordering

I find that to be an interesting design choice. If you ever support UDP akka-remoting, that guarentee comes with a non-trivial performance cost.

Contributor

colin-scott commented Aug 13, 2015

Interesting, akka does appear to guarentee in-order delivery:

http://doc.akka.io/docs/akka/snapshot/general/message-delivery-reliability.html#Discussion__Message_Ordering

I find that to be an interesting design choice. If you ever support UDP akka-remoting, that guarentee comes with a non-trivial performance cost.

@colin-scott

This comment has been minimized.

Show comment
Hide comment
@colin-scott

colin-scott Aug 13, 2015

Contributor

Ah, and in fact, there is a discussion on that same page about possibly removing that guarentee in the future:

http://doc.akka.io/docs/akka/snapshot/general/message-delivery-reliability.html#How_does_Local_Ordering_relate_to_Network_Ordering

Contributor

colin-scott commented Aug 13, 2015

Ah, and in fact, there is a discussion on that same page about possibly removing that guarentee in the future:

http://doc.akka.io/docs/akka/snapshot/general/message-delivery-reliability.html#How_does_Local_Ordering_relate_to_Network_Ordering

@colin-scott

This comment has been minimized.

Show comment
Hide comment
@colin-scott

colin-scott Aug 13, 2015

Contributor

Well, my fuzzer does support an in-order delivery constraint, so I guess I'll switch to that for the time being.

Contributor

colin-scott commented Aug 13, 2015

Well, my fuzzer does support an in-order delivery constraint, so I guess I'll switch to that for the time being.

@ktoso

This comment has been minimized.

Show comment
Hide comment
@ktoso

ktoso Aug 13, 2015

Owner

Correct - currently remoting is over TCP, and the ordering guarantee of "direct point to point communication" holds there. We are not currently looking into supporting UDP directly (however are very tempted by https://github.com/real-logic/Aeron which does works over UDP however is viewed as a log as well, and that log is ordered).

For reporting problems in akka-raft let's use the in-order delivery mode then, which also means we can close this specific ticket right? :)

Owner

ktoso commented Aug 13, 2015

Correct - currently remoting is over TCP, and the ordering guarantee of "direct point to point communication" holds there. We are not currently looking into supporting UDP directly (however are very tempted by https://github.com/real-logic/Aeron which does works over UDP however is viewed as a log as well, and that log is ordered).

For reporting problems in akka-raft let's use the in-order delivery mode then, which also means we can close this specific ticket right? :)

@ktoso

This comment has been minimized.

Show comment
Hide comment
@ktoso

ktoso Aug 14, 2015

Owner

Hi @colin-scott, we talked about the docs and current implementation in the 2.3 and 2.4 series of Akka. The doc is slightly out of date - we'll update it soon akka/akka#18209

The guarantee holds mostly because of TCP, however since there can be re-established connections Akka does actually have to to a bit more than just rely on TCP (if a new connection comes in, while the old one is still not closed (i.e. "stale")) we ignore messages from the stale connection. Yes, it wouldn't hold for UDP.

Owner

ktoso commented Aug 14, 2015

Hi @colin-scott, we talked about the docs and current implementation in the 2.3 and 2.4 series of Akka. The doc is slightly out of date - we'll update it soon akka/akka#18209

The guarantee holds mostly because of TCP, however since there can be re-established connections Akka does actually have to to a bit more than just rely on TCP (if a new connection comes in, while the old one is still not closed (i.e. "stale")) we ignore messages from the stale connection. Yes, it wouldn't hold for UDP.

@colin-scott

This comment has been minimized.

Show comment
Hide comment
@colin-scott

colin-scott Aug 14, 2015

Contributor

Yeah, feel free to close this issue

Contributor

colin-scott commented Aug 14, 2015

Yeah, feel free to close this issue

@ktoso ktoso closed this Aug 14, 2015

@ktoso

This comment has been minimized.

Show comment
Hide comment
@ktoso

ktoso Aug 14, 2015

Owner

Yup, done :)

Owner

ktoso commented Aug 14, 2015

Yup, done :)

tschottdorf added a commit to tschottdorf/raft that referenced this issue Oct 25, 2015

tschottdorf added a commit to tschottdorf/raft that referenced this issue Oct 26, 2015

tschottdorf added a commit to tschottdorf/raft that referenced this issue Oct 26, 2015

tschottdorf added a commit to tschottdorf/raft that referenced this issue Nov 14, 2015

tschottdorf added a commit to tschottdorf/raft that referenced this issue Jan 1, 2016

tschottdorf added a commit to tschottdorf/raft that referenced this issue Jan 1, 2016

tschottdorf added a commit to tschottdorf/raft that referenced this issue Jan 1, 2016

tschottdorf added a commit to tschottdorf/raft that referenced this issue Mar 20, 2016

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment