Introduction

Jepsen is a suite of open-source testing tools aimed at verifying the safety of Distributed systems like databases, queues and consensus implementations. Jepsen also includes a series of amazing conference talks and blog posts which offer keen insights into the correctness of such systems under effects of faults like network partitions, split brains etc. To find such errors in the distributed systems, Jepsen uses something known as consistency models to ensure that observed effects of operations are consistent with a given model.

What is a consistency model?

This gives a very good overview of all the important concepts that formulate a consistency model. Briefly put, a consistency model is a set of allowed operation and result sequences, also known as a history. It can tell us if an observed sequence of operations and its results are agreeing to a model or are violating it.

Consider the ++ operation in a language like C. A consistency model for this operation would probably look like subset of integers in increasing order. Like so,

#{[1 2 3 4 5 6 7] [4 5 6 7 8 9] [0 1 2 3 4 5 6 7] [-7 -6 -5 -4...]},

which means that if we apply the ++ operation to a variable, we should see incrementally increasing integers. Now if we run this operation on a variable from multiple threads and we observe values like [1 2 1 2 3], this tells us that our code is not consistent with the ++ model.

Motivations

This blog post, and hopefully a part 2!, aims to explain some of the details of what a Jepsen test looks like, how it actually works and how you may extend it for testing your own Distributed system! Hopefully this understanding will also enable you to make more sense of the results explained in blog posts like these and take educated decisions on default configurations and expected behaviors.

Why did I decide to explore this? Because I wanted to run such analyses locally and play around with the test-cases. There were a couple of important factors why running these tests locally was important :

  1. We @HelpshiftEng were looking to incorporate multi-document ACID transactions with MongoDB and wanted to understand what behaviors we could expect about correctness.
  2. The version of MongoDB that we were targeting was older than the one used in Jepsen’s analyses and also it used a sharded setup whereas we are using a replica-set setup.
  3. As a student of distributed systems, this kind of work is very interesting to me and I hoped to learn more about the nature of such systems, which I certainly did!

References Github page Official tutorial

Design overview

Every Jepsen test runs on a system of connected nodes. The main driver of the test is a Clojure program running on a control node. Other nodes in the systems represent the db nodes i.e nodes running the system under test. The test driver performs setup for all the db nodes, including OS related configurations and version management of the db.

Once a test starts, the control node spins up a set of logically single-threaded processes, each with its own client for the distributed system. A generator generates new operations for each process to perform. Processes then apply those operations to the system using their clients. The start and end of each operation is recorded in a history. While performing operations, a special nemesis process introduces faults into the system–also scheduled by the generator.

Finally, the DB and OS are torn down. Jepsen uses a checker to analyze the test’s history for correctness, and to generate reports, graphs, etc.

Let’s get into some details on the components described above!

What is a Jepsen test

A Jepsen test is essentially a map with some pre-defined keys which are required by the test runner. The jepsen.cli namespace has some APIs like cli/single-test-cmd which can take a test-fn. The test-fn function should return a map with the test information that Jepsen needs.

Typically such a test map consists of the following keys :

;; noop-test
{:nodes     ["n1" "n2" "n3" "n4" "n5"]
 :name      "noop"
 :os        os/noop ;; implementation of the os/OS protocol, represents the operating system
 :db        db/noop ;; implementation of the db/DB protocol, represents the database to configure / test
 :net       net/iptables
 :remote    control/ssh
 :client    client/noop ;;  implementation of the client/Client protocol
 :nemesis   nemesis/noop ;; an implementation or combination of nemesis/Nemesis protocol
 :generator nil ;; a generator which creates stream of operations which are processed by clients and applied to the DB
 :checker   (checker/unbridled-optimism) ;; implementation of the checker/Check protocol,
                                         ;; verifies that the history of generated operations is valid
 }

Every test map derives from the jepsen.tests/noop-test.

Major components of the test

os

jepsen.os/OS protocol contains functionality for operating system setup and teardown. It has the following functions

(setup! [os test node])
(teardown! [os test node])

db

jepsen.db/DB protocol encapsulates code for setting up and tearing down a database, queue, or other distributed system we want to test.

  • This protocol specifies two functions that all databases must support: (setup! db test node) and (teardown! db test node)

net jepsent.net/Net protocol contains the functions for manipulating the network between the different DB nodes. If has the following functions

(drop! [net test src dest])
(heal! [net test])
(slow! [net test]
       [net test opts])
(flaky! [net test])
(fast! [net test])

client

jepsen.client/Client is the protocol which represents a client for accessing the database. It has the following functions.

(open! [this test node])
(setup! [this test])
(invoke! [_ test op])
(teardown! [this test])
(close! [_ test])

A Jepsen client takes invocation operations and applies them to the system being tested, returning corresponding completion operations, meaning we can define ops like read, write etc in terms of maps for example

(defn r   [_ _] {:type :invoke, :f :read, :value nil})
(defn w   [_ _] {:type :invoke, :f :write, :value (rand-int 5)})

These are functions that construct Jepsen operations: an abstract representation of things you can do to a database. :invoke means that we’re going to try an operation–when it completes, we’ll use a type like :ok or :fail to tell the system what happened. The :f tells us what function we’re applying to the database–for instance, that we want to perform a read or a write. These can be any values–Jepsen doesn’t know what they mean. These ops are passed to the invoke! function in the client where we have to write code for what it means to execute these operations.

generator Generators are functions which generate a stream of operations which are then processed by the clients. For example, a generator like the one below, generates a mix of read and write operations, scheduled every 1 second, with no nemesis and runs for 15 seconds.

{:generator (->> (gen/mix [r w])
                 (gen/stagger 1)
                 (gen/nemesis nil)
                 (gen/time-limit 15))}

nemesis The nemesis is a special client, not bound to any particular node, which introduces failure across the cluster. The jepsen.nemesis namespace provides several built-in failure modes.

Like regular clients, the nemesis also draws operations from the generator.

A nemesis generator which depends on the :start and :stop commands to do introduce faults in the system (like a network partition) can look like

(gen/nemesis
  (cycle [(gen/sleep 5)
    {:type :info, :f :start}
    (gen/sleep 5)
    {:type :info, :f :stop}]))

checker

To analyze the history, we specify a :checker for the test, and provide a :model to specify how the system should behave. checker/linearizable uses the Knossos linearizability checker to verify that every operation appears to take place atomically between its invocation and completion. We can use checker/compose to compose multiple checkers together.

Jepsen uses a model to represent the abstract behavior of a system, and a checker to verify whether the history conforms to that model. knossos.model is the commonly used repository of models, jepsen.checker is used as the checker. A model is something that understands the same operations that our client understands (read, write etc). A model data type will take a model state and an operation to apply and return the new model resulting from that operation.

References Official Tutorial

What is a Jepsen test-suite

A test suite is created using functions in the jepsen.cli namespace, mainly single-test-cmd and test-all-cmd. Both functions take a map with :test-fn or :tests-fn and :opt-spec keys and return a map with 2 keys in it :test and :analyze which are treated as subcommands by the cli/run! function.

  • test subcommand has info on how to run a test including a :run key which is a function to run the test. Each test is run by calling (jepsen/run! (test-fn options)) and checking the results→valid? key of the data returned by run!

  • analyze subcommand has info on how to analyze the results of the test. This also has a :run function which runs the jepsen/analyze! function on the test results.

    • This :run function takes the test map from the test-fn function, combines it with the data stored for the latest run of the test. This is stored as file in the store dir.
    • All test results can be obtained by the store/tests function which reads files as Delay objects.

  • test-all-cmd works similarly except that it takes a sequence of test maps and returns only the :test-all subcommand.

    • The test-all-cmd cant be used in isolation without the single-test-cmd but there won’t be an analyze subcommand.

  • cli/run! is the function which runs every subcommand. It takes the map of subcommands to command spec maps, then the command to run and any additional arguments. So when we run lein run test-all , test-all is passed as the second argument to the run! function.

  • Each subcommand map has [opt-spec opt-fn usage run] keys in it.

How is a Jepsen test run

  • Each test within a suite is represented by a subcommand and needs to have a :run function defined. This function generally invokes the jepsen/run! function with the output of the test-fn function.

  • Each test then proceeds as

    • Setup the operating system
    • Try to teardown, then setup the database
      • If the DB supports the jepsen.db/Primary protocol, also perform the Primary setup on the first node.
    • Create the nemesis
    • Fork the client into one client for each node
    • Fork a thread for each client, each of which requests operations from the generator until the generator returns nil
      • Each operation is appended to the operation history
      • The client executes the operation and returns a vector of history elements which are appended to the operation history
    • Capture log files
    • Teardown the database
    • Teardown the operating system
      • When the generator is finished, invoke the checker with the history. This generates the final report

Dataflow in a test

As we saw earlier, a generator is a function which generates a series of operations for the clients.

Each operation is just a map with the following general shape

{:type :invoke/:info/:ok/:fail
 :f <any keyword that your client understands>
 :value <value needed by client to process the function>}

Each test will have one client implementation along with one nemesis implementation. Both have an invoke! function which takes the test info and an op like the one described above.

The client is responsible for interpreting the type, f and value keys and take appropriate actions. The results of the actions are supposed to be assoc’d into the op and returned back.

For example, if a DB client encounters an op like {:type :invoke :f :write :value (rand-int 5)} it could interpret this as a write operation with the value received in the value key.

Or if a nemesis received an op like {:type :info :f :kill :value nil} it could interpret this as a directive to kill the DB instance on each node.

The actual code to invoke the generator starts from the jepsen.core/run-case! function which interprets the generator in the interpreter/run! function.

Once all the ops are generated and passed through the client and nemesis, they are appended to the history for analysis.

Running the Jepsen test suites locally

For official instructions, refer to these documents

In my efforts to understand the Jepsen test suite, I ran the MongoDB tests with a docker setup. Here are the instructions that finally worked for me!

  1. Follow the instructions here to get the docker cluster running
  2. Once you have it running, shut it down and modify the jepsen/docker/docker-compose.yml file to add 2 additional nodes. Running these tests require more than 6 MongodDB nodes to be running. You can add 2 more using code snippet below
services:
  control:
    container_name: jepsen-control
    hostname: control
    depends_on:
      - n1
      - n2
      - n3
      - n4
      - n5
+     - n6
+     - n7

...
...
# Add these lines
  n6:
    << : *default-node
    container_name: jepsen-n6
    hostname: n6
  n7:
    << : *default-node
    container_name: jepsen-n7
    hostname: n7
  1. It also helps to mount the source code at an accessible location from within the control node. For that, do this
services:
  control:
    container_name: jepsen-control
    ...
    ...
    networks:
      - jepsen
+   volumes:
+     - "<path-from-this-dir-to-mongodb-repo>:/usr/share/code:rw"
  1. Start the cluster again.
  2. SSH into the control node and create a nodes file at an accessible location. The home folder is just fine. Add this to the nodes file
n1
n2
n3
n4
n5
n6
n7
  1. Navigate into the mounted location where you have this repository. If you have followed the above instructions it should be /usr/share/code. Run the tests using below command
lein run test-all -w list-append --nodes-file ~/nodes-file -r 1000 --concurrency 3n --time-limit 120 \
--max-writes-per-key 128 --read-concern majority \
--write-concern majority --txn-read-concern snapshot --txn-write-concern majority \
--nemesis-interval 1 --nemesis partition --test-count 1

At the time when I was trying this out, the default mongodb tests from Jepsen actually did not work out of the box on Docker. So I had to make a few changes. Post that, Aphyr has made some updates to the original code and hopefully the tests will work out of the box for you!

Conclusion

Hopefully this blog has given you a basic understanding of what a Jepsen tests entails. In the second part in this series, we will dive slightly deeper into the major components like Generators, Nemesis and Consistency checkers that we have briefly described here.