Mar 15, 2022 (last updated: Mar 16, 2022)

Zanzibar Goes Elixir, Pt. 1: Setup and Relation Tuples

Zanzibar is a unified, planet-scale authorization system used by Google. While none of my side projects are quite at planet scale yet, the idea of a general purpose authorization engine is intriguing. In this article series, I’ll attempt to write a naive implementation of the system using Elixir and PostgreSQL.

Project initialization

To save us some time around configuration and test setups, we’ll generate a new project with Phoenix.

We’ll call this project Xalapa, because Zanzibar is a place on earth, Elixir has an X in it, and Xalapa has both of these properties.

mix phx.new xalapa --binary-id --no-mailer --no-gettext --no-html --no-live
cd xalapa

We’ll also add a docker compose config to run PostgreSQL. Save this as docker-compose.yml:

version: "3.1"

services:
  postgres:
    image: postgres:14.1-alpine3.15
    environment:
      POSTGRES_PASSWORD: postgres
    ports:
      - 5432:5432

And run it:

docker compose up

Get the dependencies and create the database with:

mix setup

Let’s also disable the automatic creation of primary key columns when creating tables in Ecto migrations by adding this to config/config.exs:

config :xalapa, Xalapa.Repo, migration_primary_key: false

Relation tuples

Zanzibar revolves around relations of users or usersets to objects within namespaces. The notation as defined in the paper is:

⟨tuple⟩ ::= ⟨object⟩‘#’⟨relation⟩‘@’⟨user⟩
⟨object⟩ ::= ⟨namespace⟩‘:’⟨object id⟩
⟨user⟩ ::= ⟨user id⟩ | ⟨userset⟩
⟨userset⟩ ::= ⟨object⟩‘#’⟨relation⟩

Some examples:

image:beach#owner@1 - user 1 is the owner of the image beach
image:beach#viewer@2 - user 2 is a viewer of the image beach
group:friends#owner@1 - user 1 is the owner of the group friends
group:friends#member@3 - user 3 is a member of the group friends
image:beach#viewer@group:friends#member - members of the group friends are viewers of the image beach

As you can see, it is possible to define hierarchical relationships of any depths this way.

The namespaces and their possible relations need to be configured before they can be used. We’ll skip over that part for now and start with only defining the database schema for relation tuples. Zanzibar stores the relation tuples of each namespace in a separate database, but we will keep it simple and use a single database here.

Schema

In order to allow us to support different persistence layers, we are going to implement an adapter system. The data validation will be the responsibility of the business layer, while the adapter will only be responsible for writing and retrieving data from storage.

The paper tells us that the primary keys for relation tuples are shard ID, object ID, relation, user, and commit timestamp. Since we don’t care about sharding within the scope of these articles, and since we store all relation tuples in a single database, we’ll use namespace, object ID, relation, user or userset, and the commit timestamp.

Add the file lib/xalapa/relation_tuple.ex:

defmodule Xalapa.RelationTuple do
  use Ecto.Schema

  import Ecto.Changeset

  alias Ecto.Changeset

  @type t :: %__MODULE__{
          namespace: String.t(),
          object_id: Ecto.UUID.t(),
          relation: String.t(),
          user_id: Ecto.UUID.t(),
          userset_namespace: String.t(),
          userset_object_id: Ecto.UUID.t(),
          userset_relation: String.t(),
          commit_timestamp: DateTime.t()
        }

  @primary_key false

  embedded_schema do
    field :namespace, :string
    field :object_id, Ecto.UUID
    field :relation, :string
    field :user_id, Ecto.UUID
    field :userset_namespace, :string
    field :userset_object_id, Ecto.UUID
    field :userset_relation, :string
    field :commit_timestamp, :utc_datetime_usec
  end
end

This schema is an embedded schema that will only be used for data casting and validation. The struct defined by this schema will be passed to the actual adapter modules.

The paper states that the user IDs are integers, but we are going to use UUIDs for both objects and users.

We will also define a changeset to validate incoming parameters. Add this changeset function to the same module:

def changeset(relation_tuple, attrs) do
  relation_tuple
  |> cast(attrs, [
    :namespace,
    :object_id,
    :relation,
    :user_id,
    :userset_namespace,
    :userset_object_id,
    :userset_relation
  ])
  |> validate_required([:namespace, :object_id, :relation])
  |> validate_length(:namespace, max: 100)
  |> validate_length(:relation, max: 100)
  |> validate_length(:userset_namespace, max: 100)
  |> validate_length(:userset_relation, max: 100)
  |> validate_user_or_userset()
end

defp validate_user_or_userset(%Changeset{} = changeset) do
  user_not_nil? = !is_nil(get_field(changeset, :user_id))

  userset_not_nil? =
    Enum.any?(
      [:userset_namespace, :userset_object_id, :userset_relation],
      fn field -> !is_nil(get_field(changeset, field)) end
    )

  cond do
    user_not_nil? && userset_not_nil? ->
      add_error(changeset, :user_id, "either user or userset is required")

    !user_not_nil? && !userset_not_nil? ->
      add_error(changeset, :user_id, "either user or userset is required")

    userset_not_nil? ->
      validate_required(changeset, [
        :userset_namespace,
        :userset_object_id,
        :userset_relation
      ])

    true ->
      changeset
  end
end

Here we cast all fields, add length validation to all string fields, and ensure that either a user is referenced, or a userset, but not both.

Write API

The Zanzibar API has five parts: read, write, watch, check and expand. We are going to start with the write API.

Adapter

Let’s define an adapter behaviour first. We want to support creating and deleting relation tuples. Create a file called lib/xalapa/adapter.ex:

defmodule Xalapa.Adapter do
  alias Xalapa.RelationTuple

  @callback create_relation_tuple(map) ::
              {:ok, RelationTuple.t()} | {:error, any}

  @callback delete_relation_tuple(map) :: :ok | {:error, any}
end

This defines one callback for persisting a relation tuple and one for deletion. Note that the adapter is required to accept and return the relation tuple struct defined by the embedded schema.

Our first adapter will be an Ecto adapter.

Migration

Generate a new migration:

mix ecto.gen.migration create_relation_tuples

Paste this into the migration file generated in the priv/repo/migrations folder:

defmodule Xalapa.Repo.Migrations.CreateRelationTuples do
  use Ecto.Migration

  def change do
    create table(:relation_tuples) do
      add :namespace, :string, null: false
      add :object_id, :binary_id, null: false
      add :relation, :string, null: false
      add :user_id, :binary_id
      add :userset_namespace, :string
      add :userset_object_id, :binary_id
      add :userset_relation, :string

      add :commit_timestamp, :utc_datetime_usec,
        null: false,
        default: fragment("now()")
    end

    create unique_index(
             :relation_tuples,
             [
               :namespace,
               :object_id,
               :relation,
               :user_id
             ],
             where: "user_id IS NOT NULL"
           )

    create unique_index(
             :relation_tuples,
             [
               :namespace,
               :object_id,
               :relation,
               :userset_namespace,
               :userset_object_id,
               :userset_relation
             ],
             where: "user_id IS NULL"
           )

    create constraint("relation_tuples", :either_user_or_userset,
             check: """
             (
              user_id IS NOT NULL
              AND userset_namespace IS NULL
              AND userset_object_id IS NULL
              AND userset_relation IS NULL
             ) OR
             (
              user_id IS NULL
              AND userset_namespace IS NOT NULL
              AND userset_object_id IS NOT NULL
              AND userset_relation IS NOT NULL
             )
             """
           )
  end
end

This creates a new table for the relation tuples, two partial indexes (one for tuples relating to users and one for tuples relating to usersets), and a constraint that ensures that either a user or a userset is set.

Schema

Since the Ecto schema we defined above is an embedded schema only used for validation before the data is passed to the adapters, we need a second schema for the Ecto adapter that is backed by the database table.

Save this module as lib/xalapa/adapter/ecto/relation_tuple.ex:

defmodule Xalapa.Adapter.Ecto.RelationTuple do
  use Ecto.Schema

  @primary_key false

  schema "relation_tuples" do
    field :namespace, :string
    field :object_id, Ecto.UUID
    field :relation, :string
    field :user_id, Ecto.UUID
    field :userset_namespace, :string
    field :userset_object_id, Ecto.UUID
    field :userset_relation, :string
    field :commit_timestamp, :utc_datetime_usec
  end
end

Tests

Now we can implement the behaviour with the Ecto adapter. Let’s write a test first. We will use ex_machina to define a test factory. Add ex_machina to your dependencies in mix.exs:

defp deps do
  [
    # ...
    {:ex_machina, "~> 2.7.0", only: :test},
  ]
end

Create the file test/support/factory.ex and insert:

defmodule Xalapa.Factory do
  use ExMachina.Ecto, repo: Xalapa.Repo

  alias Ecto.UUID
  alias Xalapa.RelationTuple

  @namespaces ["article", "document", "group", "image", "receipt"]
  @relations ["owner", "editor", "member", "viewer"]

  def relation_tuple_for_user_factory do
    %RelationTuple{
      namespace: sequence(:namespace, @namespaces),
      object_id: UUID.generate(),
      relation: sequence(:relation, @relations),
      user_id: UUID.generate(),
      commit_timestamp: random_datetime()
    }
  end

  def relation_tuple_for_userset_factory do
    build(:relation_tuple_for_user,
      user_id: nil,
      userset_namespace: "document",
      userset_object_id: UUID.generate(),
      userset_relation: "member"
    )
  end

  def random_datetime do
    DateTime.add(DateTime.utc_now(), Enum.random(-1_000_000..0))
  end
end

The tests for the Ecto adapter are defined at test/xalapa/adapter/ecto_test.exs:

defmodule Xalapa.Adapter.EctoTest do
  use Xalapa.DataCase, async: true

  import Xalapa.Factory

  alias Xalapa.Adapter
  alias Xalapa.RelationTuple
  alias Xalapa.Repo

  describe "create_relation_tuple/1" do
    test "inserts a relation tuple" do
      relation_tuple = build(:relation_tuple_for_user, commit_timestamp: nil)

      assert {:ok, %RelationTuple{} = returned_tuple} =
               Adapter.Ecto.create_relation_tuple(relation_tuple)

      [inserted_tuple] = Repo.all(Adapter.Ecto.RelationTuple)

      assert %DateTime{} = inserted_tuple.commit_timestamp

      inserted_tuple_map =
        inserted_tuple |> Map.from_struct() |> Map.delete(:__meta__)

      returned_tuple_map = Map.from_struct(returned_tuple)

      assert inserted_tuple_map == returned_tuple_map

      assert Map.put(returned_tuple_map, :commit_timestamp, nil) ==
               Map.from_struct(relation_tuple)
    end
  end

  describe "delete_relation_tuple/1" do
    test "deletes a user relation tuple" do
      relation_tuple = build(:relation_tuple_for_user)
      assert {:ok, _} = Adapter.Ecto.create_relation_tuple(relation_tuple)

      # repeated deletes of the same tuple don't return error
      assert Adapter.Ecto.delete_relation_tuple(relation_tuple) == :ok
      assert Adapter.Ecto.delete_relation_tuple(relation_tuple) == :ok

      assert Repo.all(Adapter.Ecto.RelationTuple) == []
    end

    test "deletes a userset relation tuple" do
      relation_tuple = build(:relation_tuple_for_userset)
      assert {:ok, _} = Adapter.Ecto.create_relation_tuple(relation_tuple)

      # repeated deletes of the same tuple don't return error
      assert Adapter.Ecto.delete_relation_tuple(relation_tuple) == :ok
      assert Adapter.Ecto.delete_relation_tuple(relation_tuple) == :ok

      assert Repo.all(Adapter.Ecto.RelationTuple) == []
    end
  end
end

The first test asserts that a given relation tuple struct is persisted to the database and that the returned struct is the correct struct including the commit_timestamp. The structs are converted to maps for comparison because of the two different structs we set up. After that, we test whether user relation tuples and userset relation tuples can be deleted.

Implementation

Now we can add the actual implementation. Save this to lib/adapter/ecto.ex:

defmodule Xalapa.Adapter.Ecto do
  @behaviour Xalapa.Adapter

  import Ecto.Query

  alias Ecto.Changeset
  alias Xalapa.Adapter
  alias Xalapa.RelationTuple
  alias Xalapa.Repo

  @impl Xalapa.Adapter
  def create_relation_tuple(%RelationTuple{} = relation_tuple) do
    map = Map.from_struct(relation_tuple)

    result =
      %Adapter.Ecto.RelationTuple{}
      |> Changeset.change(map)
      |> Repo.insert(returning: [:commit_timestamp])

    case result do
      {:ok, %Adapter.Ecto.RelationTuple{} = relation_tuple} ->
        {:ok, convert_tuple(relation_tuple)}

      {:error, %Changeset{} = changeset} ->
        {:error, changeset}
    end
  end

  @impl Xalapa.Adapter
  def delete_relation_tuple(%RelationTuple{} = relation_tuple) do
    Adapter.Ecto.RelationTuple
    |> find_tuple(relation_tuple)
    |> Repo.delete_all()

    :ok
  end

  defp find_tuple(q, %RelationTuple{user_id: user_id} = relation_tuple)
       when is_binary(user_id) do
    where(q,
      namespace: ^relation_tuple.namespace,
      object_id: ^relation_tuple.object_id,
      relation: ^relation_tuple.relation,
      user_id: ^relation_tuple.user_id
    )
  end

  defp find_tuple(q, %RelationTuple{user_id: nil} = relation_tuple) do
    where(q,
      namespace: ^relation_tuple.namespace,
      object_id: ^relation_tuple.object_id,
      relation: ^relation_tuple.relation,
      userset_namespace: ^relation_tuple.userset_namespace,
      userset_object_id: ^relation_tuple.userset_object_id,
      userset_relation: ^relation_tuple.userset_relation
    )
  end

  defp convert_tuple(%Adapter.Ecto.RelationTuple{
         namespace: namespace,
         object_id: object_id,
         relation: relation,
         user_id: user_id,
         userset_namespace: userset_namespace,
         userset_object_id: userset_object_id,
         userset_relation: userset_relation,
         commit_timestamp: commit_timestamp
       }) do
    %RelationTuple{
      namespace: namespace,
      object_id: object_id,
      relation: relation,
      user_id: user_id,
      userset_namespace: userset_namespace,
      userset_object_id: userset_object_id,
      userset_relation: userset_relation,
      commit_timestamp: commit_timestamp
    }
  end
end

Since the validation will be handled outside of the adapter, we can insert the data optimistically. Note that we need to convert between the relation tuple struct of the Ecto adapter and the global embedded struct here.

We are using the global Repo module that was generated by the Phoenix generator. In a published application or library, we would make the repo configurable for the adapter, but that is out of scope.

Boundary

Finally, we can add the entry function for the create operation. Add the file test/xalapa/xalapa_test.exs and insert:

defmodule XalapaTest do
  use Xalapa.DataCase, async: true

  import Xalapa.Factory

  alias Ecto.Changeset
  alias Ecto.UUID
  alias Xalapa.RelationTuple

  describe "create_relation_tuple/1" do
    test "inserts a relation tuple for user with Ecto adapter" do
      params = params_for(:relation_tuple_for_user, commit_timestamp: nil)

      assert {:ok, %RelationTuple{} = relation_tuple} =
               Xalapa.create_relation_tuple(params)

      assert %DateTime{} = relation_tuple.commit_timestamp

      map = relation_tuple |> Map.from_struct() |> Map.delete(:__meta__)

      assert Map.drop(map, [
               :commit_timestamp,
               :userset_namespace,
               :userset_object_id,
               :userset_relation
             ]) == params
    end

    test "inserts a relation tuple for userset with Ecto adapter" do
      params = params_for(:relation_tuple_for_userset, commit_timestamp: nil)

      assert {:ok, %RelationTuple{} = relation_tuple} =
               Xalapa.create_relation_tuple(params)

      assert %DateTime{} = relation_tuple.commit_timestamp

      map = relation_tuple |> Map.from_struct() |> Map.delete(:__meta__)

      assert Map.drop(map, [
               :commit_timestamp,
               :user_id
             ]) == params
    end

    test "returns error if given data is invalid" do
      params = params_for(:relation_tuple_for_user, namespace: nil)

      assert {:error, %Changeset{} = changeset} =
               Xalapa.create_relation_tuple(params)

      assert %{namespace: ["can't be blank"]} = errors_on(changeset)
    end

    test "returns error if both user and userset are passed" do
      params =
        params_for(:relation_tuple_for_user,
          userset_namespace: "document",
          userset_object_id: UUID.generate(),
          userset_relation: "member"
        )

      assert {:error, %Changeset{} = changeset} =
               Xalapa.create_relation_tuple(params)

      assert %{user_id: ["either user or userset is required"]} =
               errors_on(changeset)
    end

    test "returns error if neither user nor userset is passed" do
      params = params_for(:relation_tuple_for_user, user_id: nil)

      assert {:error, %Changeset{} = changeset} =
               Xalapa.create_relation_tuple(params)

      assert %{user_id: ["either user or userset is required"]} =
               errors_on(changeset)
    end

    test "returns error if userset is missing field" do
      params = params_for(:relation_tuple_for_userset, userset_relation: nil)

      assert {:error, %Changeset{} = changeset} =
               Xalapa.create_relation_tuple(params)

      assert %{userset_relation: ["can't be blank"]} = errors_on(changeset)
    end
  end

  describe "delete_relation_tuple/1" do
    test "deletes a relation tuple for user with Ecto adapter" do
      params = params_for(:relation_tuple_for_user, commit_timestamp: nil)

      assert {:ok, %RelationTuple{}} = Xalapa.create_relation_tuple(params)
      assert Xalapa.delete_relation_tuple(params) == :ok
    end

    test "deletes a relation tuple for userset with Ecto adapter" do
      params = params_for(:relation_tuple_for_userset, commit_timestamp: nil)

      assert {:ok, %RelationTuple{}} = Xalapa.create_relation_tuple(params)
      assert Xalapa.delete_relation_tuple(params) == :ok
    end
  end
end

This defines a couple of tests for validating, creating and deleting relation tuples. To make these tests pass, paste this into lib/xalapa.ex:

defmodule Xalapa do
  alias Ecto.Changeset
  alias Xalapa.Adapter
  alias Xalapa.RelationTuple

  @spec create_relation_tuple(map, keyword) ::
          {:ok, RelationTuple.t()} | {:error, any}
  def create_relation_tuple(%{} = params, opts \\ []) do
    with {:ok, opts} <- Keyword.validate(opts, adapter: Adapter.Ecto),
         {:ok, relation_tuple} <- validate_params(params) do
      adapter = Keyword.fetch!(opts, :adapter)
      adapter.create_relation_tuple(relation_tuple)
    end
  end

  @spec delete_relation_tuple(map, keyword) ::
          {:ok, RelationTuple.t()} | {:error, any}
  def delete_relation_tuple(%{} = params, opts \\ []) do
    with {:ok, opts} <- Keyword.validate(opts, adapter: Adapter.Ecto),
         {:ok, relation_tuple} <- validate_params(params) do
      adapter = Keyword.fetch!(opts, :adapter)
      adapter.delete_relation_tuple(relation_tuple)
    end
  end

  defp validate_params(%{} = params) do
    %RelationTuple{}
    |> RelationTuple.changeset(params)
    |> Changeset.apply_action(:validate)
  end
end

The create_relation_tuple function validates the given options and parameters, and then uses the given adapter (defaulting to the Ecto adapter) to insert the data.

The original Zanzibar write API also supports modifying all relation tuples for an object, but we will skip this for now. The paper also mentions that “multiple tuple versions are stored on different rows, so that we can evaluate checks and reads at any timestamp within the garbage collection window.” We’ll ignore that as well. In the next article, we will add a basic read and check API.

Feel free to get in contact and bother me to continue.

References

Zanzibar: Google’s Consistent, Global Authorization System

Mathias Polligkeit

Zanzibar Goes Elixir, Pt. 1: Setup and Relation Tuples

Project initialization

Relation tuples

Schema

Write API

Adapter

Migration

Schema

Tests

Implementation

Boundary

References

See Also