The postgres data driver currently keeps the full history of all relationships written and deleted. It should allow for the specification of a garbage collection policy, indicating the point after which deleted relationship rows should be removed

This requires a few steps:

• Converting our existing ad-hoc process for performance testing into a GitHub Action
• Connecting GitHub Actions to dedicated hardware that can measure performance without noisy-neighbor issues
• Formalizing the output of performance tests
• Determining how and when these tests run
• Determining how to produce action items from tests that are ran

Now that all of SpiceDB is open source, there's no purpose to the test-server being built as its a separate binary.
Instead it could easily be migrated into subcommand of the main binary.

Right now, the time field in the pgx logs as output is repeated:

{"level":"info","module":"pgx","args":[],"commandTag":"...","sql":"begin read only","time":2.258174,"time":"2021-09-02T16:31:54Z","message":"Exec"}

Note that the produced JSON, when piped through tooling, loses one of the values

The authzed.api.v0.DeveloperService, which is used to power the Authzed Playground and any schema language tooling, supports formatting and compilation errors, but it does not include any linting or warning information that can be used to optionally improve the designs of schemas.

SpiceDB uses the gRPC authentication middleware to protect its services. The reflection service should be exposed without requiring authn. A mixin from grpcutil is used to carve out other exceptions to the authn middleware.

Related: grpc-ecosystem/go-grpc-middleware#244

There are a variety of command-line flags that are shared across Authzed projects that do the same thing, but are named differently.

This issue should track documenting those shared flags and updating them so that everything is consistent.
Where it makes sense, flags can be upstreamed into cobrautil, like the zerolog flags already are.

There is no validation that deduplicates or asserts that every Tuple provided to authzed.api.v0.ACLService.Write() must be unique. Because of this, it is up to the data store to determine whether or not this will manifest itself as an error.

There are two immediately obvious solutions:

• Validate that every Tuple is unique and return an error
• Deduplicate Tuples before attempting to persist Tuples into the data store

The arrow operator can only be used once in an expression (e.g. org->admin), but should be able to support traversing an arbitrary number of relations (e.g. namespace->org->admin, tenant->namespace->org->admin->member).

This would allow for nested arrows in schema

A CLI command that runs a demo of SpiceDB with a schema and data already that generates load would be useful for both load testing and showing users what using the database is like.

This is inspired by the same functionality in CockroachDB.

The Zanzibar paper devotes a lot of time to the leopard cache, which caches member to group and group to group relationships:

Recursive pointer chasing during check evaluation has difficulty maintaining low latency with groups that are deeply nested or have a large number of child groups. For selected namespaces that exhibit such structure, Zanzibar handles checks using Leopard, a specialized index that supports efficient set computation.

The Leopard system consists of three discrete parts: a serving system capable of consistent and low-latency operations across sets; an offline, periodic index building system; and an online real-time layer capable of continuously updating the serving system as tuple changes occur.

Distributed dispatching currently reuses the existing gRPC API and uses headers to propagate context.
It might make sense to design an API dedicated for dispatching that encapsulates this context and is agnostic to the API with which the end-user made a request.

The Homebrew formula generated by go-releaser should also install shell completion.

It should use filters to build the base query.

One of the major benefits of using CockroachDB is that it can optimize performance for multi-region deployments.

Here are a few unexplored ideas for ways that this could be handled in SpiceDB:

• Document configuring CockroachDB out of band
• SpiceDB creates database indexes based on CLI flags

Add support for pagination into the Expand API

Should ideally make use of a generic pagination system over the dispatcher that can be shared with Lookup

In https://github.com/authzed/spicedb/blob/main/internal/graph/check.go#L61, we perform a lookup of all relationships under a relation, and then search for the goal subject, as well as kicking off the recursive checks if a non-terminal subject is found.

We should consider making the following optimizations:

• Check for the goal subject directly in a single query, without a loop, and only if that subject relation is possible on the relation (via type information, if present)
• Lookup only the non-terminal ONRs in its own query and use those results to issue recursive checks

We're manually calling protobufMessage.Validate() first thing in many of the API handlers. We can replace all of that by adding the gRPC community validation middleware to the constructors of the gRPC Server.

This issue is meant to track design requirements for the v1 API.

• Support for schema language instead of namespace configs
• All API calls are consistent by default
• Zookies optionally can be provided to safely allow flexibility in consistency
• Subject References should treat a lack of relation as "ellipsis"

See: cockroachlabs.com/docs/v21.1/transactions#client-side-intervention

Here's an example of spicedb logs when a retry isn't handled:

5:04PM ERR Exec args=[] err="ERROR: restart transaction: TransactionRetryWithProtoRefreshError: TransactionRetryError: retry txn (RETRY_SERIALIZABLE - failed preemptive refresh): \"sql txn\" meta={id=caf1be11 key=/Table/54/2/\"QRdiUVdMQmkyjQjX\"/\"user\"/\"...\"/\"resource\"/\"direct\"/\"thegoods\"/0 pri=0.04592771 epo=0 ts=1631394282.849166225,2 min=1631394148.811930011,0 seq=6} lock=true stat=PENDING rts=1631394148.811930011,0 wto=false gul=1631394149.311930011,0 (SQLSTATE 40001)" module=pgx sql=commit
5:04PM ERR finished server unary call error="unable to write tuples: ERROR: restart transaction: TransactionRetryWithProtoRefreshError: TransactionRetryError: retry txn (RETRY_SERIALIZABLE - failed preemptive refresh): \"sql txn\" meta={id=caf1be11 key=/Table/54/2/\"QRdiUVdMQmkyjQjX\"/\"user\"/\"...\"/\"resource\"/\"direct\"/\"thegoods\"/0 pri=0.04592771 epo=0 ts=1631394282.849166225,2 min=1631394148.811930011,0 seq=6} lock=true stat=PENDING rts=1631394148.811930011,0 wto=false gul=1631394149.311930011,0 (SQLSTATE 40001)" grpc.code=Unknown grpc.method=Write grpc.method_type=unary grpc.service=authzed.api.v0.ACLService grpc.start_time=2021-09-11T17:02:29-04:00 grpc.time_ms=3712.738 kind=server system=grpc

Without exposing a better API that can enable calls to span across the same transaction, API handlers cannot make perfect guarantees about the consistency of the data they are saving.

A strawman API would look something like this, using a closure to get any data in and out:

// within an API handler
err := datastore.Transact(func(ctx context.Context, tx datastore.Tx) error {
    query := tx.QueryTuples(...)
    // do stuff with query
    tx.DeleteRelationships(...)
})

authzed.api.v0.ACLService.Read() cannot support reading queries with large result sets.

This will have to be added as some form of pagination in order to remain backwards compatible.

A future API could use gRPC streams instead of pagination.

There needs to be a document that expands on the structure of the repository and the design of the project.

The document should:

• Reiterate Zanzibar basics
• Explain differences between SpiceDB & Zanzibar
• Describe the end-to-end lifetime of a check request

The gRPC recovery middleware can be added catch any panics and convert them into an gRPC internal error.

This requires a careful review to ensure that no resources are leaked as a result of continuing the program after a panic occurs.

Everything is instrumented using OpenTelemetry, but Jaeger is the only format exposed by command-line flags.
If it can be made generic enough, this could be upstreamed into cobrautil.

The CRDB datastore works around the assumption that the hybrid logical can be used for ordering all transactions, when this is might not be a safe assumption.

If we assume the "overlapping transactions" are the only things guaranteed to be linearizable the following can occur:
You could issue a ContentChangeCheck, get a Zookie, then immediately do a Check which then had a "non-overlapping transitive relationship change" included in the evaluation of that Check (e.g. a group relationship that was deleted).

There is only a small window where this could actually occur in practice, but that window depends on clock skew.
A simple proposal could be simply waiting a configurable duration until returning a Zookie.

Here are some resources that are fuel for discussion:

• CRDB Consistency Model docs

• Fun fact: early CockroachDB had a hidden --linearizable switch that would do essentially the above, so theoretically, if you did have some atomic clocks lying around (or generally an acceptable maximum clock offset), you’d get Spanner-like behavior out of the box. We’ve since removed it given how under-tested it was, but perhaps it would make sense to resurrect it as cloud providers trend towards exposing TrueTime-like APIs. Chip-scale atomic clocks are a reality; putting one on server motherboards would beat the pants off a quartz crystal oscillator.

• Usenix Exploiting a Natural Network Effect for Scalable, Fine-grained Clock Synchronization
• https://clockwork.io
• https://github.com/rubrikinc/kronos

https://github.com/reviewdog/reviewdog

The Zanzibar implementation at Google uses a special-case userset to represent the set of all users "aka public".

As per one of their public presentations:

Because SpiceDB's schema language is more expressive, we have some better options than introducing this concept as a special-cased tuple:

• A keyword could be used to embellish relations/permissions that are public.
• We could introduce a type to represent public, but it might be surprising if a user unintentionally unions a relation/permission with public by accident.

reproducer: https://play.authzed.com/s/zT3GO2ufKQf_A/relationships

In the case of bad network performance, cache misses, or a variety of invalid assumptions that could cause latency, the distributed dispatcher should also dispatch to another instance as a "hedged bet" to guarantee a response with the least amount of latency as possible.

The Write API should coalesce multiple deletes into 1 delete, so that a rogue client can't keep us busy for a long time.

From the Zanzibar paper:

When a zookie is not provided, the server uses a default staleness chosen to ensure that all transactions are evaluated at a timestamp that is as recent as possible without impacting latency.
On each read request it makes to Spanner, Zanzibar receives a hint about whether or not the data at that timestamp
required an out-of-zone read and thus incurred additional latency.
Each server tracks the frequency of such out-of-zone reads for data at a default staleness as well as for fresher and staler data, and uses these frequencies to compute a binomial proportion confidence interval of the probability that any given piece of data is available locally at each staleness.
Upon collecting enough data, the server checks to see if each staleness value has a sufficiently low probability of incurring an out-of-zone read, and thus will be low-latency.
If so, it updates the default staleness bound to the lowest “safe” value. If no known staleness values are safe, we use a twoproportion z-test to see if increasing the default will be a statistically significant amount safer. In that case, we increase
the default value in the hopes of improving latency. This default staleness mechanism is purely a performance optimization. It does not violate consistency semantics because Zanzibar always respects zookies when provided.

CockroachDB supports regions and zones. There isn't a way (that I can see) to get statistics on zone information during a single read, but locality data can be fetched within the same transaction with a show range for row query.

A sufficient document on Zookie would cover the following subjects:

• How they are different from a typical read snapshot token
• How they are used in Zanzibar
• How they are used in v0 API
• How they are used in v1 API
• How they are represented internally within SpiceDB

Currently they silently return no results.

Add support for pagination into the Lookup API

Should ideally make use of a generic pagination system over the dispatcher that can be shared with Expand

See #42 for Expand

The native CockroachDB schema guarantees uniqueness of Tuples, while the Postgres datastore does not. Theoretically, it's possible for SpiceDB to create duplicate living Tuples if there is a bug. By creating a unique constraint, we can enforce only a single living Tuple for a relationship at the database level.

Callers of authzed.api.v0.Expand often only care about a subset of the users present in the results. Expand could provide a means of filtering users, which could potentially improve performance for those requests.

Tuple Query iterators load the full set of tuples from the database before passing the iterator to the various callers.

Not all APIs make full use of the result set, so having a streaming iterator could provide some efficiencies when the limit in a lookup is reached.

Such a document should include the pros & cons to each datastore and when to use them

Datstores:

• In-memory
• Postgres
• Postgres (Cockroach)
• Cockroach
• Read-only
• Mapping Proxy

From the Zanzibar paper:

Zanzibar’s distributed processing requires measures to accommodate slow tasks. For calls to Spanner and to the Leopard index we rely on request hedging (i.e. we send the same request to multiple servers, use whichever response comes back first, and cancel the other requests). To reduce round-trip times, we try to place at least two replicas of these backend services in every geographical region where we have Zanzibar servers. To avoid unnecessarily multiplying load, we first send one request and defer sending hedged requests until the initial request is known to be slow.
To determine the appropriate hedging delay threshold, each server maintains a delay estimator that dynamically computes an Nth percentile latency based on recent measurements. This mechanism allows us to limit the additional traffic incurred by hedging to a small fraction of total traffic.
Effective hedging requires the requests to have similar costs. In the case of Zanzibar’s authorization checks, some checks are inherently more time-consuming than others because they require more work. Hedging check requests would result in duplicating the most expensive workloads and, ironically, worsening latency. Therefore we do not hedge requests between Zanzibar servers, but rely on the previously discussed sharding among multiple replicas and on monitoring mechanisms to detect and avoid slow servers

When the same read-only requests occur within a configurable window of time, a single dispatch can be performed to fetch their results.

A useful library for implementing this is the golang.org/x/sync/singleflight.

Distributed dispatching currently relies on a single implementation of peer discovery that uses Servok.
Because there are various ways to discover peers, this should likely be placed behind an interface so that more implementations can arise over time.

There are various registries with different retention policies for container images.
It is probably worth setting up redundant repositories to hedge against losing any images.

Potential registries:

• Quay (already being used)
• Docker Hub
• GitHub

There are functions in the tuple package that panic when the invalid input is provided.
These functions should be renamed to have the prefix Must in front of them in order to follow the Go convention.

revive is being ran in GitHub Actions, but it is not failing the build if there are any linting errors.

Lots of docstrings need to be added among any other changes and then the step in GHA needs to be updated to fail the build if a new linting error is introduced.

Right now, the transaction used in the CRDB driver to set the query to use the proper time is rolled back synchronously via a defer tx.Rollback(ctx) call in the query code: https://github.com/authzed/spicedb/blob/main/internal/datastore/common/sql.go#L248

During performance testing it was noticed that this rollback can take anywhere from 0.5ms to 3ms, so it might be possible to get a small win if we can run the rollback asynchronously while the queried data is returned to the caller. This may not be possible given the connection pool in use; we'd need to investigate if this would cause any secondary effects.

We currently use validation files for testing and importing/exporting databases from the playground.

The UX for running an instance of SpiceDB would be improved if there was a command-line flag (--bootstrap-file) that took a path to a validation file and loaded it on start-up. An additional --bootstrap-overwrite flag would force the validation to run regardless of whether or not the data store was empty at startup.

From the Zanzibar paper:

Because changes to namespace configs can change the results of ACL evaluations, and therefore their correctness, Zanzibar chooses a single snapshot timestamp for config metadata when evaluating each client request. All aclservers in a cluster use that same timestamp for the same request, including for any subrequests that fan out from the original client request.
Each server independently loads namespace configs from storage continuously as they change (§3.1.3). Therefore, each server in a cluster may have access to a different range of config timestamps due to restarts or network latency. Zanzibar must pick a timestamp that is available across all of them. To facilitate this, a monitoring job tracks the timestamp range available to every server and aggregates them, reporting a globally available range to every other server.
On each incoming request the server picks a time from this range, ensuring that all servers can continue serving even if they are no longer able to read from the config storage.

SpiceDB currently caches namespace configs but does not enforce their evaluation at a particular snapshot. Without this in place, changes to namespace configuration needs to be carefully planned.