# Graph API design

## Abstract

Kubernetes objects can reference each other.
References can be one to one or one to many (e.g. via label selectors).
These relationships can be represented in a graph.
We need an API that allows to load and query the graph.
Our first use case is a [dashboard](https://gitlab.com/groups/gitlab-org/-/epics/13963).

## Requirements

Functional:

- Load the graph of objects.
- Watch the graph for changes in real time. We want a dashboard that is updated as the changes happen in the cluster.
- Support both namespace-scoped and cluster-scoped objects.
- Support known (e.g. built-in and Flux) and unknown objects (e.g. defined via CRDs or future built-in).
- Support various ways for objects to refer to each other:
  - Field with referred object name. E.g. a `Deployment` referring to a `ConfigMap`.
  - Label selector. In practice label selectors are often used together with controller
    [owner references](https://kubernetes.io/docs/concepts/overview/working-with-objects/owners-dependents/)
    to resolve situations where multiple objects use overlapping selectors.
  - Owner references. Apart from the above, owner references can be used for
    [deletion ordering](https://kubernetes.io/docs/concepts/architecture/garbage-collection/#foreground-deletion).
    They have extra flags: `controller` and `blockOwnerDeletion`
  - List references. Some objects (e.g. Flux `Kustomization` or `HelmRelease`'s `Secret`) store the list of
    managed objects in their `data` or `status` fields.

Non-functional:

- Watch implementation should be in agentk.
  We'll use Kubernetes watch API to watch objects in the cluster to deliver real time updates to the graph.
  A robust way to use the watch API is via informers.
  Informers can consume a lot of RAM since they load all objects in a namespace or even globally (can filter with label selectors).
  Because of that, we cannot implement this in kas as the API will need to handle an unknown and potentially large
  number of objects.
  An extra benefit of implementing the functionality in agentk is that it can filter objects out relatively cheaply,
  without sending anything to kas.
- Minimize RAM usage. For the same reasons as above, the implementation should minimize RAM usage.
  We don't know how much RAM agentk has available, and we want to minimize the chance of running out of RAM.
- Flexible API.
  It's impractical to make significant changes to an implementation in agentk since users don't update very often.
  Hence, since a considerable chunk of functionality will be in agentk,
  it should be made more flexible from the get-go so that it's somewhat future-proof.
- Kubernetes is an eventually consistent system. It's possible for an object to refer to a
  non-existent object. It may have been deleted or never existed in the first place.
  This graph API will expose the information as-is. API clients need to handle this gracefully, including situations
  where the referred object didn't exist but was created later (or the opposite - existed and then was deleted).
- Due to security consideration, contents of the `Secret` objects is never returned.
- The solution should scale to 5,000 resources in a tree. Customers shared concerns that the tree might fail
  to render for their clusters given the size of it.

## Background information

### Groups, versions, resources

From [Kubernetes API terminology](https://kubernetes.io/docs/reference/using-api/api-concepts/#standard-api-terminology)
note `resource` and `kind`.
From [Resource URIs](https://kubernetes.io/docs/reference/using-api/api-concepts/#resource-uris)
note `group` and `version`.
We don't care about other things in this document.

In Kubernetes all resources are part of the following hierarchy.
Root of the hierarchy is an array of groups.
Each group has one or more versions.
This document refers to a particular version of a group as "group+version".
Each group+version contains an array of resources.
Note that in this structure it is possible that a resource may exist in group+version `v1` but be absent
in group+version `v2` (or vice versa).

```yaml
- mygroup1
  - v1
    - foos
    - abcs
  - v2beta1
    - bars
    - abcs
- mygroup2.mydomain.com
  - v2
    - foos
    - abcs
```

The `foos` resource exists in `mygroup1/v1` but does not in `mygroup2.mydomain.com/v2`.
`bars` is the other way around.

The `foos` resources from `mygroup2.mydomain.com/v2` is not the same thing as the `foos` from `mygroup1/v1`.
They are completely separate resources.
Hence, the full "identifier" of a resource is group+version+resource (otherwise there is ambiguity).

There is a concept of co-habitation that is apparently not documented anywhere.
It's a way to move a resource to another group without breaking existing consumers.
Here is the
[list of co-habitating resources](https://github.com/kubernetes/kubernetes/blob/v1.30.3/pkg/kubeapiserver/default_storage_factory_builder.go#L129-L136)
in Kubernetes v1.30.3, for example.
This information is not exposed via discovery, so we need to be careful not to expose the same thing multiple times
to avoid any user confusion.
In practice this mechanism was used to get rid of the `extensions` and `events` groups.
We can avoid any problems if we always exclude these two groups.

### Selectors

[Label selectors](https://kubernetes.io/docs/concepts/overview/working-with-objects/labels/#label-selectors).

[Field selectors](https://kubernetes.io/docs/concepts/overview/working-with-objects/field-selectors/).

[JSONPath Support](https://kubernetes.io/docs/reference/kubectl/jsonpath/).

## Proposal

Expose a new WebSocket API that allows to configure which objects (group+version+resource) to watch, how to filter them and what information to return.
Information about resources (graph vertices) and references among them (graph arcs aka directed edges) is returned as a stream of
WebSocket messages.

Note that the resources graph is a directed graph.
Vertices are connected by arcs.
A graph may have cycles and loops (an arc that connects a vertex to itself).
Two vertices may be connected by more than one arc (directly or indirectly), but in that case arcs will be of different types.
If a resource has multiple references of the same type to another resource, they are considered a single arc.

Types of arcs:

- Owner reference (`t=or`). E.g. `Pod` has an owner reference to a `ReplicaSet`.
- Label selector (`t=ls`). E.g. `ReplicaSet` has a label selector that matches some `Pod`s.
- Reference (`t=r`). E.g. a `Deployment` may mount a `ConfigMap`.
- Transitive reference (`t=t`). E.g. Helm stores information about a release in a `Secret`.
  Hence, resources, referenced via that `Secret`, have a transitive arc from the corresponding `HelmRelease` object.
- "Transitive via" reference (`t=via`). E.g. `HelmRelease` object has an arc of this type to the release storage `Secret` object.

A vertex may have multiple arcs of the same type, but they will be connected to distinct vertices.

Having loops is a pathological case but Kubernetes API allows for that.
For example, an owner reference to itself.

### Client request

API path is `/graph` on the Kubernetes API proxy endpoint.
It accepts a WebSocket upgrade request on this path.
WebSocket subprotocol `gitlab-agent-graph-api` is accepted here.

First WebSocket message the client sends configures what information is requested.
No more messages are expected.
Server closes the connection if another message is received.
The message is a text message with JSON payload:

```json
{
  "namespaces": ["myns"],
  "roots": {
    "individual": [
      {
        "group": "apps",
        "resource": "deployments",
        "ns": "myns",
        "name": "mydeployment"
      }
    ],
    "selectors": [
      {
        "group": "",
        "resource": "services",
        "labelSelector": "",
        "fieldSelector": ""
      }
    ]
  },
  "rules": [
    {
      "includeGroup": {
        "group": "apps",
        "labelSelector": "",
        "fieldSelector": "",
        "jsonPath": ""
      }
    },
    {
      "includeGroupVersion": {
        "group": "apps",
        "version": "v1",
        "labelSelector": "",
        "fieldSelector": "",
        "jsonPath": ""
      }
    },
    {
      "includeGroupVersionResource": {
        "group": "apps",
        "version": "v1",
        "resource": "deployments",
        "labelSelector": "",
        "fieldSelector": "",
        "jsonPath": ""
      }
    },
    {
      "excludeGroup": {
        "group": "apps"
      }
    },
    {
      "excludeGroupVersion": {
        "group": "apps",
        "version": "v1beta1"
      }
    },
    {
      "excludeGroupVersionResource": {
        "group": "discovery.k8s.io",
        "version": "v1",
        "resource": "endpointslices"
      }
    },
    {
      "includeAll": {
        "labelSelector": "",
        "fieldSelector": "",
        "jsonPath": ""
      }
    },
    {
      "excludeAll": {}
    }
  ]
}
```

`namespaces` is the list of namespaces to watch.
Optional field.
All namespaces are watched by default.

`roots` allows to select a subgraph of resources that are connected to the provided roots.
Optional field.
Root selection is additive.
If no roots are specified, no root-based filtering is performed.

`roots.individual` allows to provide individual resources to use as roots.
Only group+resource is specified because the version of the matched and included resource will be used (see `rules` and below).
Root is ignored if no version of this group+resource is included by `rules`.
`ns` is the namespace.
Must be provided if resource is a namespaced resource.
If it's a cluster-scoped resource, then it's an error to provide `ns`.

`roots.selectors` allows to select root(s) based on label and/or field selectors.
Roots are a mechanism to filter out parts of the graph that are not interesting to the client.
Only group+resource is specified because the version of the matched and included resource will be used (see `rules` and below).
Root selector is ignored if no version of this group+resource is included by `rules`.
For namespace-scoped resources, namespaces specified in the `namespaces` field are used.

`rules` is a set of matching rules to select which groups+versions+resources to watch.
Required field, must have at least one element in the array.
Agentk gets the list of all groups and resources Kubernetes supports via the discovery API.
It then evaluates each one using the matching rules.
Rules are evaluated in the provided order, from the first to last one in the array.
First one that matches is selected for a particular group+version+resource.
Subresources (e.g. `deployments/scale`) are never evaluated.

Possible matching rules and their effect:

- `includeGroup` matches and includes all resources in that group. Version selection is described below.
- `includeGroupVersion` matches and includes all resources of a particular version in that group.
- `includeGroupVersionResource` matches and includes a particular group+version+resource.
- `excludeGroup` matches all excludes all resources of all versions in that group.
- `excludeGroupVersion` matches and excludes all resources of a particular version in that group.
- `excludeGroupVersionResource` matches and excludes a particular group+version+resource.
- `includeAll` matches and includes everything.
- `excludeAll` matches and excludes everything. This rule is implicitly added as the last rule.

`includeGroup`, `includeGroupVersion`, and `includeAll` are provided so that the API supports retrieving unknown
resources and/or retrieving resources without having to explicitly list them one by one.

#### Version selection

Version is called "stable" if it matches the `^v\d+$` regex e.g. `v1`. Otherwise, it's called "unstable".

At most one version of a group+resource is ever selected to be watched.
Discovery returns groups+versions in some implementation-dependent order so there needs to be an ordering
mechanism in this API to avoid any non-determinism.
Hence, versions within a group are sorted in ascending natural order.
This is only necessary to resolve non-determinism if the matching rules match multiple versions of the same
group+resource in a sticky mode (see below).

All resources in all versions in all groups are visited in a depth first traversal: group -> version -> resource.
Each group+version+resource is matched against the matching rules.
If a rule, that matches first, includes the group+version+resource, then it's selected to be watched.

Sticky version selection:

`includeGroupVersion` and `includeGroupVersionResource` version selections are sticky - once a version for a
group+resource is matched, that version will be used.
Other versions of the same group+resource are not evaluated against rules.

Non-sticky version selection:

If a group+version+resource is matched with `includeGroup` or `includeAll`, the version that is currently
being evaluated is selected.
This selection is not sticky.
If later the same group+resource of a different version is evaluated and matches for inclusion,
the version may be upgraded.

Non-sticky version may be upgraded if:

- Currently selected version is stable and new version is newer and is stable too.
  This rule ensures that out of matched versions, the most recent stable version is selected.
  E.g. `v1` -> `v2`.
- Currently selected version is unstable and new version is newer (stable or unstable).
  This rule ensures that out of matched versions, a newer version is selected.
  E.g. `v1beta1` -> `v1` or `v1beta1` -> `v1beta2`.
- Currently selected version is unstable and new version is stable (newer or older).
  This rule ensures that out of matched versions, stable versions are preferred to unstable ones.
  E.g. `v1beta1` -> `v1` or `v2beta1` -> `v1`.

### Response to client

Server will send WebSocket text messages with JSON of the following format:

```json
{
  "actions": [],
  "errors": []
}
```

`actions` may contain zero or more actions to alter the graph.
Actions must be carried out in the order they appear in the array.
There may be lots and lots of actions, so short field names are used to save bandwidth and reduce loading times.
Possible actions are listed below.

`errors` may contain zero or more error objects.
This field contains non-terminal errors.

#### Errors

An error object has these fields:

- `type`. One of the predefined types of errors. This can be used to programmatically understand what happened.
- `message`. A free-form message to show to the human user.
- `attributes`. A `type`-specific set of attributes to programmatically understand what happened.

Known error `type` constants:

- `INFORMER_SYNC_FAILED`. Happens when an informer fails to sync withing a timeout.

Attributes for `INFORMER_SYNC_FAILED`:

- `g` is the group.
- `v` is the version.
- `r` is the resource.
- `ns` is the namespace. Omitted when empty i.e. for cluster-scoped resources.

Example:

```json
{
  "type": "INFORMER_SYNC_FAILED",
  "message": "Failed to sync informer for apps/v1/deployments in myns in 30 seconds. Check agent's log, agent's permissions",
  "attributes": {
    "g": "apps",
    "v": "v1",
    "r": "deployments",
    "ns": "myns"
  }
}
```

#### Set a vertex in the graph

This action is used to add or update a vertex in the graph.

- `svx` stands for "set vertex".
- `g` is the group.
- `v` is the version.
- `r` is the resource.
- `ns` is the namespace. Omitted when empty i.e. for cluster-scoped resources.
- `n` is the name.
- `o` is the contents of the resource.
  Only set if `j` is not set.
- `j` is the contents of the resource filtered by JSON path.
  `j` is an array because JSON path may select multiple nodes from the resource's JSON representation.
  May be an empty array if JSON path didn't select anything.
  Only set if `jsonPath` was provided in the matched rule that included the resource.

At most one of `o` or `j` is set, never both.
None is set if both are empty (empty object/array).
`Secret` objects always have `o`/`j` set to an empty object/array.

```json
{
  "svx": {
    "g": "apps",
    "v": "v1",
    "r": "deployments",
    "ns": "myns",
    "n": "my_deployment",
    "o": {},
    "j": []
  }
}
```

#### Remove a vertex from the graph

- `rvx` stands for "remove vertex".
- `g` is the group.
- `v` is the version.
- `r` is the resource.
- `ns` is the namespace. Omitted when empty i.e. for cluster-scoped resources.
- `n` is the name.

```json
{
  "rvx": {
    "g": "apps",
    "v": "v1",
    "r": "deployments",
    "ns": "myns",
    "n": "my_deployment"
  }
}
```

#### Set an arc in the graph

This action is used to add or update an arc in the graph.

- `sarc` stands for "set arc".
- `s` is object defining the "source" vertex.
  - `g` is the group.
  - `v` is the version.
  - `r` is the resource.
  - `ns` is the namespace. Omitted when empty i.e. for cluster-scoped resources.
  - `n` is the name.
- `d` is the object defining the "destination" vertex.
  - `g` is the group.
  - `v` is the version.
  - `r` is the resource.
  - `ns` is the namespace. Omitted when empty i.e. for cluster-scoped resources.
  - `n` is the name.
- `t` is the type of the arc. See the section "types of arcs" above.
- `a` is the attributes object. Keys are attribute names and values are attribute values. Omitted when empty.

Known attributes:

- For owner reference arcs (i.e. `t=or`):
  - `c` marks an owner reference as a controller reference. It's only set when it's `true`.

Label selector arc example:

```json
{
  "sarc": {
    "s": {
      "g": "apps",
      "v": "v1",
      "r": "deployments",
      "ns": "myns",
      "n": "my_deployment"
    },
    "d": {
      "g": "",
      "v": "v1",
      "r": "pods",
      "ns": "myns",
      "n": "pod1"
    },
    "t": "ls"
  }
}
```

Owner reference arc example:

```json
{
  "sarc": {
    "s": {
      "g": "",
      "v": "v1",
      "r": "pods",
      "ns": "myns",
      "n": "pod1"
    },
    "d": {
      "g": "apps",
      "v": "v1",
      "r": "deployments",
      "ns": "myns",
      "n": "my_deployment"
    },
    "t": "or",
    "a": {
      "c": true
    }
  }
}
```

#### Remove an arc from the graph

- `rarc` stands for "remove arc".
- `s` is the object defining the "source" vertex.
  - `g` is the group.
  - `v` is the version.
  - `r` is the resource.
  - `ns` is the namespace. Omitted when empty i.e. for cluster-scoped resources.
  - `n` is the name.
- `d` is the object defining the "destination" vertex.
  - `g` is the group.
  - `v` is the version.
  - `r` is the resource.
  - `ns` is the namespace. Omitted when empty i.e. for cluster-scoped resources.
  - `n` is the name.
- `t` is the type of the arc. See the section "types of arcs" above.

```json
{
  "rarc": {
    "s": {
      "g": "",
      "v": "v1",
      "r": "pods",
      "ns": "myns",
      "n": "pod1"
    },
    "d": {
      "g": "apps",
      "v": "v1",
      "r": "deployments",
      "ns": "myns",
      "n": "my_deployment"
    },
    "t": "or"
  }
}
```

### Error responses to client

kas returns an error if it cannot find an agent supporting the new functionality.
UI can then show a messages, asking to update the agent.

agentk returns an error if it cannot get an informer to sync within a time interval (e.g. 30 seconds).
kas propagates that error to the caller.

### kas to agentk API

The new functionality will need a new RPC exposed by agentk.

```protobuf
syntax = "proto3";

package gitlab.agent.kubernetes_api.rpc;

message Action {
  // Graph actions.
}

message Error {
  // Details.
}

message StreamGraphRequest {
  // The parsed request that comes from the client.
}

message StreamGraphResponse {
  repeated Action actions = 1;
  repeated Error errors = 2;
}

service KubernetesApi {
  rpc StreamGraph (StreamGraphRequest) returns (stream StreamGraphResponse) {
  }
}
```
