A New Consensus Algorithm for TokuMX and MongoDB

By Zardosht Kasheff Software Developer, Tokutek @zkasheff

A Technology White,Tokutek, Paper Fall 2014

© Copyright 2014 Tokutek, Inc. All rights reserved.

Executive Summary

Ark is an implementation of a consensus algorithm similar to Paxos and Raft. It is designed to improve replica set failover in the Tokutek distribution of MongoDB: TokuMXTM. While it has many similarities to Raft, it also has some important differences. Ark was designed by Tokutek to fix known issues with the election protocol used in basic MongoDB, and in the Tokutek distribution of MongoDB, TokuMX, as well. Today, the existing protocol is neither AP nor CP, when considered in the context of the CAP theorem. Tokutek will eliminate these inherited issues in TokuMX using Ark.

Tokutek set out primarily to modify the election protocol to make TokuMX a true CP system. That is, in the face of network partitions, TokuMX will maintain consistency. To do so means ensuring that any write that is successfully acknowledged with majority write concern is never lost.

The high level goal of Ark is to improve failover behavior. A Tokutek tech report that details the issues encountered and the approach Tokutek will use for fixing them, can be found at: http://arxiv.org/pdf/1407.4765v1.pdf.

The Ark “fix” will be included in TokuMX v2.0.

DOWNLOAD WHITE PAPER (.PDF): NewConsensusAlgorithm4TokuMX&MongoDB

Additional Resources of Tokutek (link to their web site- registration required):

Documentation, Collateral and White Papers