Tokutek Announces New Consensus Algorithm for MongoDB
Tokutekhas announced work on a new consensus algorithm with the goal of replacing the existing leader election algorithm inMongoDB. Ark, as the algorithm is named, is being developed for use inTokuMX, Tokutek’s fork of MongoDB, and addresses a number of issues with the existing MongoDB algorithm.
The design is heavily influenced by theRaftandPaxosalgorithms and aims to provide the same provably strong consistency guarantees. It differs from Raft to enable it to support the MongoDB architecture and programming model, implementing an asynchronous, pull-based replication model. This, the developersclaim,
…supports a wider range of client semantics that allows application developers to choose points along a trade- off between safety and latency. In addition, Ark supports different replication topologies like chained replication and multi-data center replication with more flexibility than Raft does with its synchronous push model.
Tokutek explained the need for this new algorithm by pointing out two issues with the existing MongoDB leader election algorithm. The primary issue is one of correctness. In theblog post announcing Ark,Zardosht Kasheffpoints out that it is possible for updates that succeed with themajoritywrite concern to roll back.
Our main goal is to modify the election protocol to make TokuMX a true CP system. That is, in the face of network partitions, TokuMX will remain consistent. To do so means ensuring that any write that is successfully acknowledged with majority write concern is never lost in the face of a network partition. This isnot currently the casefor TokuMX and MongoDB.
The secondary issue that Tokutek draws attention to is one of availability. In the accompanyingtech reportZardosht and coauthorLeif Walshexplain that it is possible for a MongoDB replica set to be unavailable for 30 seconds or more during failover.
MongoDB’s election protocol requires that a member may not vote “yes” in more than one election in any 30-second period. … [T]his 30 second threshold can be problematic in practice, especially if an election fails: this necessarily makes the set unavailable for at least 30 seconds, maybe more if successive elections fail.
Ark addresses these flaws by exploiting the structure of the TokutekDB global transaction identifier (GTID). The GTID consists of a pair of 64-bit integers, (term, opid), where opid is incremented each time an operation commits on the primary, and the term is incremented each time a new primary is elected, and at this point the opid is reset to 0. The term in the GTID serves the same purpose as the term concept in the Raft protocol and that similarity allows Ark to employ many of the same solutions that Raft uses to provide its strong consistency guarantees.
While Ark is an implementation of a consensus protocol that works in a real database system, it is also evidence of the flexibility in the Raft consensus algorithm. It was relatively straightforward to tweak Raft in safe ways to make it fit the MongoDB architecture and programming model, and we think this is an important feature of Raft.
There is an Arkdevelopment branchavailable and Tokutek is actively soliciting feedback on both the design and the implementation.