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
- user1
is the owner of the imagebeach
image:beach#viewer@2
- user2
is a viewer of the imagebeach
group:friends#owner@1
- user1
is the owner of the groupfriends
group:friends#member@3
- user3
is a member of the groupfriends
image:beach#viewer@group:friends#member
- members of the groupfriends
are viewers of the imagebeach
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.