zookeeper
zookeeper copied to clipboard
apache
ZOOKEEPER-4643, ZOOKEEPER-4646 & ZOOKEEPER-4394: Committed txns lost / NullPointerException in Learner.syncWithLeader()
This fix aims to fix a bunch of issues in follower's syncWithLeader(). e.g., ZOOKEEPER-4394: NullPointerException when follower receives COMMIT after replying NEWLEADER ack in syncWithLeader(). Explanation: In syncWithLeader(), a follower may receive the COMMIT message after replying NEWLEADER ack. e.g., a follower receives the following messages in order: DIFF -> PROPOSAL -> COMMIT -> PROPOSAL -> NEWLEADER -> COMMIT -> UPTODATE
NullPointerException will occur if the corresponding PROPOSAL has been processed and removed from the "packetsNotCommitted" during the follower process NEWLEADER.
To fix this, when the follower receives NEWLEADER, it does the following things in order:
- take snapshot if needed;
- persist and process the committed txns according to "packetsCommitted" synchronously (these txns have been committed by leader). Note that leave the outstanding proposals in "packetsNotCommitted" (not in "packetsCommitted") to be processed later;
- update currentEpoch;
- reply NEWLEADER ack.
After the follower replies UPTODATE ack, it persist the txns in "packetsNotCommitted" and commit the txns in "packetsCommitted" asynchronously.
Besides, this fixes some other issues in Learner.syncWithLeader():
ZOOKEEPER-3023: Flaky test: Zab1_0Test#testNormalFollowerRunWithDiff
ZOOKEEPER-4643: Committed txns lost when follower crashes after updating currentEpoch
ZOOKEEPER-4646: Committed txns lost when follower crashes after replying NEWLEADER ack
ZOOKEEPER-4685: Leader shutdown due to follower replies PROPOSAL ack before NEWLEADER ack in Synchronization phase
We have leveraged the TLA+ specifications of ZooKeeper and verified the correctness of this fix.
When the follower processes the NEWLEADER message, it only persists and processes the txns that the leader asks it to COMMIT. This guarantees no loss of committed txns because the follower syncs the leader's committed history before replying NEWLEADER ack (ZOOKEEPER-4646).
Besides, this fix removes the redundant acks for the PROPOSALs of committed txns in SYNCHRONIZATION phase. In fact, there is no need to reply PROPOSAL acks for these committed txns. Because these txns have been committed by the leader, their PROPOSAL acks are redundant for the leader (See Leader#processAck).
Analysis of #2111 and #1848:
#2111 can avoid ZOOKEEPER-4643, but it cannot fix other issues like ZOOKEEPER-4394: the NullPointerException problem when the follower receives COMMIT after replying NEWLEADER ack in syncWithLeader().
In #1848, when receiving NEWLEADER, the follower only persists and processes the packets according to "packetsCommitted". It still keeps the outstanding proposals in "packetsNotCommitted" to avoid NullPointerException when receiving COMMIT packet(s) right after replying NEWLEADER ack (ZOOKEEPER-4394).
Take #2111 and #1848 into consideration, this fix avoids a group of issues in SYNCHRONIZATION, including ZOOKEEPER-4643, ZOOKEEPER-4646, ZOOKEEPER-4685, ZOOKEEPER-4394 and the problem of flaky tests ZOOKEEPER-3023.
Add a test case: Zab1_0Test#testNormalFollowerRun_ProcessCommitInSyncAfterAckNewLeader. This checks the case when the follower receives PROPOSAL, NEWLEADER, COMMIT & UPTODATE in order during Learner.syncWithLeader().
One curiosity:
We have leveraged the TLA+ specifications of ZooKeeper and verified the correctness of this fix.
Who is 'we' ? Can you share your tests?
One curiosity:
We have leveraged the TLA+ specifications of ZooKeeper and verified the correctness of this fix.
Who is 'we' ?
We are a research team dedicated to the verification of distributed systems using TLA+. We participated in the development of the TLA+ specifications for Zab & ZooKeeper.
Based on ZooKeeper's existing specification, we refine the actions according to the code implementation to explore the possible interleaving of multi-node and multi-threading events with failures. Then we check the specification to see whether it violates some invariants (derived from Zab paper and code) with the model checker.
For example, when we specify Learner.syncWithLeader(..) in version 3.9.1, the model checking found the issue traces of ZOOKEEPER-4643, ZOOKEEPER-4646, ZOOKEEPER-4394, ZOOKEEPER-4685 and ZOOKEEPER-3023.
When specifying Learner.syncWithLeader(..) in version 3.9.2 (fixed by #2111), the issue traces of ZOOKEEPER-4394 and ZOOKEEPER-3023 can be detected.
More details of the specifications can be found in this repo.
Can you share your tests?
We verify this fix with the TLA+ specification zk_pr_2152.
Some details in this specification: according to the fix in this PR, the logic when a follower receives NEWLEADER is specified into three actions:
- FollowerProcessNEWLEADER_pr2152_1: Take snapshot if needed; persist and commit requests according to "packetsCommitted".
- FollowerProcessNEWLEADER_pr2152_2: Update currentEpoch.
- FollowerProcessNEWLEADER_pr2152_3: Reply NEWLEADER ack.
The verification statistics are provided here. No violation is found during the checking with various configurations.
Hi, this is great!
As luck would have it, I had to rebase my fork onto 3.9.2 a few weeks ago, and due to conflicts with #2111 I already reviewed that commit. My conclusion then was that the NPE this PR fixes still remained an issue, and I think there are additional fixes in #1925 related to shutdown of the ZK database/server, that would also lead to (mostly harmless) duplicate series in the transaction log.
I've dedicated some time for reviewing this PR, and will also make sure to mint a fresh PR with any outstanding fixes from #1925, in the hope that I may finally close that fork.
I think the changes in this PR look good 👍
From what I can tell, the union of #2111, this, and #2154 (which I just opened) should together cover #1925, which is now a battle-proven patch, used by vespa.ai for the last year and a half.
Hi, @kezhuw. thanks a lot for your careful review! I've updated the code fix in this pr. Could u please take some time to check the new commit and see if there is anything else that needs improvement? Thanks!
Hi @eolivelli. Sorry for bother you, but would you mind take a look at this pr and consider merging it?
This pr fixes a bunch of issues in follower's syncWithLeader() that stay unresolved for a long time. Besides, it can drive the following fixes like https://github.com/apache/zookeeper/pull/2154.
It is built based on the latest fix https://github.com/apache/zookeeper/pull/2111. It has been checked by the new added test case Zab1_0Test#testNormalFollowerRun_ProcessCommitInSyncAfterAckNewLeader and the TLA+ specification verification results.
Will this fix be backported in the 3.8 train? We just hit this bug on one of our clusters, it's a shame we've had various fixes up for review for over 20 months, I would appreciate you guys pushing this through the finish line so this critical issue can be closed. Thanks!
Hi folks, is there any interest in merging this fix soon and cutting a release?
I will setup some time to review it early next week.
Hi @li4wang, thanks for your participation in reviewing this pr! Do you think it ok to merge this fix?
Hi @kezhuw. Really appreciate your careful review of this pr the other days! Would u mind take some time to check the pr and see if it could be merged or not? Thanks a lot!
@AlphaCanisMajoris I think we need one more binding approval to gain confidence. Most of no trivial prs need two binding approvals by convention.
@kezhuw Thanks for your review and approval! By the way, is it possible to invite or assign some developers familiar to ZooKeeper's design logic to review this fix so we can accelerate the merge progress and close this issue before cutting the next release? (Which is strongly desired by multiple developers >..<)
I would appreciate the maintainers' attention here, this is a critical data corruption bug in ZK. We just ran into it again on one of our dev clusters.
@tsuna Which ZooKeeper version did you run ? I saw messages you posted on ZOOKEEPER-4394. I guess it is 3.8.2.
ZOOKEEPER-4785 has been landed in 3.8.4 and 3.9.2. Though, ZOOKEEPER-4394 was still left behind, but I think the txn loss ZOOKEEPER-4643 and ZOOKEEPER-4646 reported has already been fixed if I understand correctly. Hmm, there might be still paths to data inconsistency as ZOOKEEPER-4541 and ZOOKEEPER-4712 reported.
@eolivelli @anmolnar @symat @maoling @tisonkun @li4wang @cnauroth Could anyone please take a look at this ? After #2111(ZOOKEEPER-4785) merged, this is basically an alternative to #1930 (@jeffrey-xiao)
ZOOKEEPER-4394 describes the issue, following is my understandings:
-
Learner::syncWithLeaderassumes/demands no outstandingPROPOSALbeforeNEWLEADER. - But leader requires only quorum acks of
NEWLEADERto issue outstandingPROPOSALs. This means learner is possible to see uncommitted proposal on receivingNEWLEADER. - The combination of above two breaks following up
COMMIT.
Besides above, this patch reverts Zab1_0Test.testNormalFollowerRunWithDiff to prior ZOOKEEPER-2678 which I think it is a good as I expressed in ZOOKEEPER-3023.
@tsuna Which ZooKeeper version did you run ? I saw messages you posted on ZOOKEEPER-4394. I guess it is 3.8.2.
Yes ZK 3.8.2. I was under the impression, based on the earlier comment from @AlphaCanisMajoris, that the "fix for ZOOKEEPER-4643 cannot fix other issues like ZOOKEEPER-4394" hence why I have been waiting for a new ZK 3.8.x release with this fix merged in.
It's been so long at this point we are debating just patching the fix in and running a custom build. 🫤
@kezhuw Thanks for your review and approval! By the way, is it possible to invite or assign some developers familiar to ZooKeeper's design logic to review this fix so we can accelerate the merge progress and close this issue before cutting the next release? (Which is strongly desired by multiple developers >..<)
Hi @kezhuw. Sorry to bother you again on the progress of this pr. Is it possible to assign someone to review this pr? Thanks!
@AlphaCanisMajoris Sorry for the long waiting. There is no such "assign" since most of us if not all are volunteers. But I think you cloud send a request of review along with brief detail of the proposal to dev mailing list.
Is there a thread on the dev mailing list for this proposal? I don't see one.
Is there a thread on the dev mailing list for this proposal? I don't see one.
Hi @anmolnar. Is it possible to merge this pr in the upcoming release of version 3.9.3? This critical issue has stayed unresolved for a long time, and it bothers developers a lot.
@kezhuw @AlphaCanisMajoris @tsuna Please close all outstanding PR's which are superseded by this patch. Also please help organizing outstanding patches to wrap up the release. Thanks!
Done. Thanks @AlphaCanisMajoris ! What is your jira id?
Please double check the branch-3.9 backport commit, there was a small conflict that I had to resolve.
Done. Thanks @AlphaCanisMajoris ! What is your jira id?
Please double check the
branch-3.9backport commit, there was a small conflict that I had to resolve.
OK I'll have a check.
Done. Thanks @AlphaCanisMajoris ! What is your jira id?
Please double check the
branch-3.9backport commit, there was a small conflict that I had to resolve.
Reverted, because it broke the build. https://ci-hadoop.apache.org/view/ZooKeeper/job/zookeeper-multi-branch-build/job/branch-3.9/465/
@AlphaCanisMajoris Would you please create separate pull request for 3.9 branch?
Done. Thanks @AlphaCanisMajoris ! What is your jira id? Please double check the
branch-3.9backport commit, there was a small conflict that I had to resolve.Reverted, because it broke the build. https://ci-hadoop.apache.org/view/ZooKeeper/job/zookeeper-multi-branch-build/job/branch-3.9/465/
@AlphaCanisMajoris Would you please create separate pull request for 3.9 branch?
OK I'll create a new pr for branch-3.9.