Building app infrastructure in Elixir: Time-traveling state

In the previous post, I discussed making crush into a more-viable data store for mahou. Since then, I’ve implemented forking and joining of key-value pairs in crush, and this post will be discussing the implementation thereof.

Fork-join of keys is conceptually fairly simple. A key stores its current fork, and the list of its ancestors, forks that were merged into it. To make ancestor tracking easier, the revision that said key was at during the join (or merge) is stored as part of the ancestor data:

typedstruct module: Ancestor do
  field :fork, String.t()
  field :rev, non_neg_integer()
end

Note: Example code is using typed_struct.

Once we can store the ancestors in the value’s state, we have everything that we need to make fork-join work!

At this point, our value state struct looks like this:

typedstruct module: Item do
  field :value, binary()
  field :patches, [any()]
  field :fork, String.t(), default: "default"
  field :ancestors, [Ancestor.t()], default: []
  field :rev, non_neg_integer(), default: 0
end

The easiest thing to do is implementing forking. That’s just copy the value struct, change its fork, and prepend the latest ancestor. This is very easy to do:

@spec fork(String.t(), String.t(), __MODULE__.Item.t()) :: :ok
def fork(key, target, %Item{fork: fork, ancestors: ancestors, rev: rev} = item) do
  new_item = %{item | fork: target, ancestors: [%Ancestor{fork: fork, rev: rev} | ancestors]}
  Cluster.write to_key(target, key), new_item
end

to_key/2 is simply a function that maps a fork name and a key name into a composite key that can be stored in a DeltaCRDT AWLWWMap trivially:

defp to_key(fork, key), do: fork <> ":" <> key

Simple enough, right?

Merging keys is a bit harder. Not only do we have to get ancestry right, we also have to make sure that the patch history makes sense, revision count gets incremented, and that the correct value is set. This is slightly-ugly code, but it’s easy-enough to grok, I think:

@spec merge(String.t(), String.t(), String.t()) :: :ok
def merge(key, source_fork, target_fork) do
  %Item{
    value: source_value,
    fork: source_fork,
    rev: source_rev,
  } = get source_fork, key, :all, false

  %Item{
    value: target_value,
    fork: ^target_fork,
    patches: patches,
    ancestors: ancestors,
    rev: target_rev,
  } = target = get target_fork, key, :all, false

  next_patch = Differ.diff source_value, target_value
  merged_item = %{
    target
    | value: source_value,
      patches: [next_patch | patches],
      ancestors: [%Ancestor{fork: source_fork, rev: source_rev} | ancestors],
      rev: target_rev + 1,
  }

  Cluster.write to_key(target_fork, key), merged_item
end

What this does is:

1. Read the source (to-merge) and (merge) target values.
2. Merge them together.
3. Write it into the cluster’s state.

Easy, right?

Okay, I say that, but I know it’s actually significantly more effort than that to implement it right. Lots and lots of testing. But hey, that’s software development for you.

This does, of course, necessitate even MORE API routes to make it all work. If we check our mix phx.routes:

git:(master) | ▶  mix phx.routes
 api_path  GET     /:key                      CrushWeb.ApiController :get
 api_path  PUT     /:key                      CrushWeb.ApiController :set
 api_path  DELETE  /:key                      CrushWeb.ApiController :del
 api_path  GET     /:key/:fork                CrushWeb.ApiController :get
 api_path  PUT     /:key/:fork                CrushWeb.ApiController :set
 api_path  DELETE  /:key/:fork                CrushWeb.ApiController :del
 api_path  GET     /:key/info                 CrushWeb.ApiController :key_info
 api_path  GET     /:key/:fork/info           CrushWeb.ApiController :key_info
 api_path  POST    /:key/:fork/fork/:target   CrushWeb.ApiController :fork
 api_path  POST    /:key/:fork/merge/:target  CrushWeb.ApiController :merge

git:(master) | ▶  

Wow, that’s a lot! But it makes perfect sense. It’s our get/set/delete routes, exactly the same, just with forking and merging added. Beyond that, there’s also the basic routes to make forking and merging work. Not too complicated, though.

Pretty short this time, but hey, it wasn’t too difficult to make it work. Next time is gonna be about mahou cluster state management and making sure app deployments work right.