redeploy scenario on 3-instance cluster and split-brain happens. keep-majority strategy

majority-split-brain+redeploy.md

Base scenario

The policy is keep-majority, new instances are started one by one, on redeploy newest instances are downed first (YOUNGEST_FIRST)

• 3 nodes up: N1, N2, N3

Redeploy

1. a redeploy is started, so a new node is spun (N+)
2. N+ is acked by all the nodes, so the Leader (L) is about to set the node to UP
3. split brain separates in 2 partitions of the same size P1 = {N1, N2}, P2 = {N3, N+`}

scenarios

What happens depends on which net partition holds the oldest node (OLD) and the leader (L)

Case # | OldestIn | LeaderIn
   1   |    P1    |    P1    
   2   |    P1    |    P2    
   3   |    P2    |    P1    
   4   |    P2    |    P2    

Case 1 [Converge] P1 survives P2 is shutdown

• P1 eventually sees N+ because L is on P1, it sees that there's a tie but decides to live because OLD is on P1 too
• P2 will not see N+ as UP so it will decide to shutdown, being minority

Case 2 [Converge] P1 survives P2 is shutdown

• P1 will not see N+ because L is on P2, so it will keep living because he's majority
• P2 will see N+ as UP and think we have a tie, but L is here so it will decide to shutdown, because it knows OLD is on P1

Case 3 [Diverge] both P1 and P2 are shutdown

• P1 eventually sees N+ because L is on P1, it sees that there's a tie but decides to shutdown because OLD is on P2
• P2 will not see N+ as UP so it will decide to shutdown, being minority

Case 3 [Diverge - Worst case] both P1 and P2 survive

• P1 will not see N+ because L is on P2, so it will keep living because he's majority
• P2 will eventually see N+ as UP and think we have a tie, but L is here so it will decide to survive, because it knows that OLD too is on P2

@ivanopagano I think your description is correct, but just for completeness .

In case of equally distributed partitions, the one that will survive is the one with the lowest address, not the oldest. Which is surprising for me, because:

1. a new node can get a lowest address
2. the decision never take in consideration who is the leader

On a side note:
Since we want to avoid moving singletons as mush as possible, the partition holding the oldest one should be the one to survive, IMO.
Moreover, the oldest is a stable information, while the one with lowest address not (I'm just rephrasing 1)

Wow, thanks for the clarification, @rcavalcanti, this is even worse than expected. We have no way to ensure the oldest nodes survive then.

considering new information:

• the leader is elected as the lowest address
• lowest address partition wins on a node count tie

the cases simplifies a lot

1. leader/lower is on P1
2. leader/lower is on P2

case 1 [Converge]

• P1 knows about N+ and will survive because, even with a tie, it holds the lower node
• P2 doesn't know about N+ and will shutdown, considering himself minority

case 2 [Diverge]

• P1 doesn't know about N+ and will survive, considering himself majority
• P2 knows about N+ and will survive because, even with a tie, it holds the lower node