Testing a Basic Concurrent Cache: Writing Tests

With the cache complete, we can write tests for it that will show whether it works correctly. As we’ve seen earlier, stateful properties are executed in two big phases:

1. Symbolic phase to generate the command set.
2. Real to run the commands against the real system for validation purposes.

We’re going to follow the same pattern here, and we’ll start with a focus on the symbolic execution by setting up the model before adding validation rules and then running the property to see if it’s sound.

Building the model

The first step in coming up with a good stateful model is to think like an operator, meaning someone in charge of running or debugging our code in production. If people are to operate and run our code, they have to be able to understand what to expect out of it. Whatever expectations they form as operators are often mental models meaning that they think through the operations in their heads and make guesses as to what data or behavior they’ll get back out of the system. Whenever their mental model is wrong (“The system doesn’t do what we think it should”), we’ll get a bug report or a production incident.

If we’ve managed to explain how the system works to an operator in a way that is both realistic and simple, we’ve given them a reliable mental model to work with. That mental model is something we can try to encode as a property.

Interestingly, if a good way to come up with a model is to figure out how we’d explain our component to a human operator having to run it in production, the opposite is true as well. If we have to explain our system to someone, the model we used in our tests could be a good starting point. If our tests are complex, convoluted, and hard to explain, then the testing experience is likely to match their operational experience.

The model

Since our cache works a bit like a big array where old entries are evicted to make place for new ones, we can use any data structure or implementation with first-in-first-out (FIFO) semantics as a model. This should be relatively accurate. We’ll use all of the callbacks of proper_statem’ to write our simpler FIFO structure to show whether the real cache works or not. Let’s set this up.

defmodule CacheTest do
  use ExUnit.Case
  use PropCheck
  use PropCheck.StateM
  doctest Cache
  @moduletag timeout: :infinity

  @cache_size 10

  property "stateful property", [:verbose] do
    forall cmds <- commands(__MODULE__) do
      Cache.start_link(@cache_size)
      {history, state, result} = run_commands(__MODULE__, cmds)
      Cache.stop()

      (result == :ok)
      |> aggregate(command_names(cmds))
      |> when_fail(
        IO.puts("""
        History: #{inspect(history}
        State: #{inspect(state)}
        Result: #{inspect(result)}
        """)
      )
    end
  end
end

We’ve used an arbitrary ?CACHE_SIZE value for the sake of simplicity. We could have used a generator for more thorough testing, but we’ll get the basics of stateful testing without that. Important to note is that the setup and teardown functions (cache:start_link/1 and cache:stop/0) always run as part of the property. Had we used the ?SETUP macro instead, we’d have needed to only call cache:flush() after every run to ensure it’s always empty. The current form is just a bit longer, and it provides enough setup and teardown requirements that it’ll do fine for our example.

Model state

For our model’s state, we’ll try to use as little data as possible, carrying only what’s strictly necessary to validate everything.

defmodule State do
  @cache_size 10
  defstruct max: @cache_size, count: 0, entries: []
end

def initial_state(), do: %State{}

The commands and preconditions

We’ll use a list to contain the model’s data, along with a count of how many entries were seen. The list will contain {Key, Value} pairs, and the counter will know when to drop pairs from the list, keeping the list as simple as possible.

The command generation is straightforward as well. We put emphasis on writes for the tests by using the frequency/1 generator.

We can then use the precondition to add constraints, like preventing calls to empty the cache when it’s already empty.

def command(_state) do 
  frequency([
    {1, {:call, Cache, :find, [key()]}},
    {3, {:call, Cache, :cache, [key(), val()]}}, 
    {1, {:call, Cache, :flush, []}}
  ])
end


def precondition(%State{count: 0}, {:call, Cache, :flush, []}) do 
  false
end

def precondition(%State{}, {:call, _mod, _fun, _args}) do 
  true
end

def key() do
  oneof([range(1, @cache_size), integer()])
end

def val() do 
  integer()
end

The generator for keys is designed to allow some keys to be repeated multiple times. By using a restricted set of keys (with the range/2 generator) along with an unrestricted integer(), we can ensure that some keys will be reused. This forces our property to exercise any code related to key reuse or matching, without losing the ability to fuzz the system with occasionally unexpected new keys.

The next_state

The next_state callback completes command generation by allowing the model to stay up-to-date with what the system state should be.