
The technology behind the [eKee consents](https://www.ekee.io/blog/gestion-de-consentements) permits to share a subset of data with an infinit granularity and let the request dictate the final structure. In short, provide a zero config query language.

What this means is that eKee is constantly transpiling a JSON request into a SQL one and then converting back the SQL result to a JSON representation. Issue being that
this operation is done in realtime, making it performance critical.

For a while, we had a naive implementation working just fine. But with the users having more and more data saved, we detected that when the result started to get big (~50MB), the server could take up to 30s to respond.

In this article I'll explain how a new algorithm, building the resulting tree along the stream, permitted to reduce this response time from 30s to 200ms at worst.

## The issue

The goal is to build a JSON object from the results of a SQL request. In our syntax, a JSON object represents an entry in a table and all its fields are the columns of the table plus subobjects if the table have references to other tables.

![The SQL result and its transformation to a JSON object](/assets/blog/posts/sql-to-json/json-sql.jpg)

<center style="margin-top: -12px">
  <i>Fig 1: The SQL result and its transformation to a JSON object</i>
</center>

There is two major issues when transforming SQL results to JSON:

- **Objects unicity**: The result from a SQL request can be seen as a 2D representation. There is no depth. Therefore, we need to remap all the columns in the resulting row to their corresponding object and then be able to understand the relation between each objects before adding the depth dimension (In Fig.1 we would have three kind of objects: _country_, _city_, _street_);
- **Merging identical entries**: As for _country.city_ and _country.city.street_ (Fig.1), when multiple elements are present for a similar relation between two tables **A** and **B** (i.e. one-to-many), a row is returned for each element from **B**. Issue being that each of those rows will have similar columns for the related entry **A**. Even though the resulting object must have only one occurrence of **A** and an array of **B**.

## The naive approach: building and merging trees

A naive approach to the problem would be to handle each issue one after the other. First you build a tree per row and then you merge all those trees together one after the other.

Since each tree have the same structure, the main advantage of this solution is its simplicity. The algorithm takes each tree one after the other and merge it into the result from the previous merge. When comparing, if the nodes are exactly the sames, you keep the current occurrence (_city_ nodes in Fig.1). But if some of their fields missmatch, you create a branching at the level of the missmatching nodes: an array (_street_ nodes in Fig.1).

But this solution is memory expensive. You build tons of intermediate objects which are just going to be released during the merge. In a programming language with a garbage collector such as Go, this impacts the performance _a lot_. You are allocating and releasing quantity of objects, forcing the garbage collector to do frequent and long stops.

Moreover, the number of comparaison to do keeps increasing every time you add a new branching into the resulting tree. Meaning that this solution starts showing its limits
when the resulting JSON object has multiple arrays.

## A more linear approach

The previous algorithm was spending most of its time into the walkthrough and the comparaison of the objects built from the resulting SQL rows. Therefore, the goal of the new approach is to avoid walking through the resulting JSON object and find an efficient way to compare objects.

The new solution consists of building all the objects first before linking them to their parent. No more walking through a tree. But in order to be able to compare the
objects without a walkthrough we need to be able to hash them. This solution is only applicable if the objects to compare have the same structure. That's a piece of luck, in a SQL response each resulting row has the same columns in the same order.

The whole process is carried out in three passes: First, we build the objects and their hash. Then we walk through the hashes to delete the duplicates and register the
different relations between objects. Finally we link the objects between them using the relations found in the latter pass.

### Building the objects and their hash

```go {numberLines}
type Route = string
type RowElement = {
    object: Object
    hash: Hash
    parentRoute: Route
}

objects := map[Route]RowElement

// Format SQL rows into JSON object
for col, value := range SQLrows {
    path := unalias(col)
    // path = "country.city.street.name"
    // Route: "country.city.street"
    // TableName: "street"
    // Column: "name"
    // ParentRoute: "country.city"
    // ParentName: "city"
    route, key := strings.splitLast(path,".")

    // build hash + add RowElement/field if needed
    objects.AddKeyToObject(route, key, val)
}

```

To make the construction of the JSON feasible, all the columns in the SQL query have been previously replaced by a path to the place where the values should be put in the final JSON. It is thus possible to track the position of a field but also that of the object that owns the field, the parent object, etc. However, the number of columns in each object is unknown before the end of the processing. The identifiers of the objects generated for a row can only be used after the processing of all the columns of the row.

![Cutting a line into objects](/assets/blog/posts/sql-to-json/sql-to-object.jpg)

<center style="margin-top: -12px">
  <i>Cutting a line into objects</i>
</center>

The identifier of an object is enriched as columns are added to it. Field names are omitted during the generation of the identifier to limit the size of the data to process. The coupling of the path leading to the object to its values ensures that two objects from different tables cannot be confused. Even if they are made up of the same values.

Since some tables may not have selected columns, calls to _AddKeyToObject_ will ensure that all objects present in the field's route are created. In our example (country.city.street.name), adding the _name_ field will create empty objects for the _country.city_ and _country_ routes in addition to adding a _name_ field to the _country.city.street_ object

### Deleting duplicates and finding the relations between objects

```go {numberLines}
type AllElements = map[TableName]HashList

// Use generated hash to reduce the number of JSON objects
// and link objects
for objRoute, obj := range objects {
    // Append to known json objects
    // permitting to use the same memory
    // for all equal objects (same structure & values)
    jsonObj, has := objectsMap.get(objRoute, obj.hash)
    if !has {
        objectsMap.put(objRoute, obj.hash, obj.object)
    }

    parent := objects[obj.parentRoute]

    // Inserting in the hash list, to remove duplicat objects
    // (Behaves like a hashset)
    // One hashset per table
    objHashList := allElements[objRoute]
    objHashList.Insert(Table{
        parentHash: parent.hash,
        parentTable: obj.parentRoute,
        hash: obj.hash,
    })
}

```

An important point of this second step is how the hash table is handled. The order of arrival of the elements must be preserved so that, if **ORDER BY** is used in the SQL query, the order of the elements in the JSON are well sorted. The objects are grouped according to their _parentHash_ and _parentTable_ and then the arrival order is used. The _hash_ is therefore only used to check the equality between two objects.

### Building the final JSON representation

```go {numberLines}
type ObjectsMap = map[Route][Hash]Object

// Prepare the destination object for all the Table which
// do not have a parent
res = {}
ObjectsMap[""][""] = res

// Link final objects together
for objectRoute, hashList := range allElements {
    hashMap := ObjectsMap[objectRoute]
    for _, el := range hashList {
        currentObj := hashMap[el.hash]
        parent := ObjectsMap[el.parentTable][el.parentHash]
        _, tableName := strings.splitLast(path,".")
        // Insert Or Append field if already present
        parent[tableName] = currentObj
    }
}

// return the only object whose route is ""
for _, res := range ObjectMap[""] {
  return []Object{res}
}

// return an empty array representing nothing found
return []Object{}
```

_ObjectsMap_ contains all the generated JSON objects and _AllElements_ the links between these objects. During this last step, there are no more complex calculations or algorithms to apply. Inserting the new elements is not super interessting but nonetheless verbose, which is why the insertion code is omitted. Arrays should be created if an element is already present in the _tableName_ field.

![Links between end objects](/assets/blog/posts/sql-to-json/object-links.jpg)

<center style="margin-top: -12px">
  <i>Links between end objects</i>
</center>

In the example above, two different objects will be connected to the same parent object using the _street_ field. An array will be used to keep both objects.

## Results

Switching from the first to the second solution allowed us to significantly reduce the execution time of some of our queries. Previously, processing about 50MB of SQL results could take over 30 seconds. Now, this same processing consistently takes less than 200 milliseconds.

However, the implementation presented today remains naive and largely optimizable. Among the most impactful optimizations we can think of:

- Use a more compact representation for the hashes,
- Replace _Map_ by arrays in order to suppress the generation of Go hashes and take advantage of contiguous memory storage,
- Use memory pools when creating objects,
- Implement vectorization during comparisons

But as a wise man once said: _premature optimization is the root of all evil_! Therefore they will only be implemented when the need arises ;)



_To illustrate this article, you can find the github repository
[Dot-H/simple-staging-env-ex](https://github.com/Dot-H/simple-staging-env-ex)_

At eKee, when the team and the number of users started growing, we had an issue.
We wanted to test things out and propose different versions of the product to
the users. Issue being we were a startup and duplicating the environment was way
to expensive.

In this article, I'll shortly explain our backend architecture, the solution I
went to and the tools used to develop it.

## The backend environment

At eKee we had an **hybrid architecture**. Without the fancy words, it just means
that our stateful services (_databases_, _knowledge base software_, _gitlab_...)
were running on on-premise servers while the stateless services
(_engine_, _api_, _websites_...) were running in a cloud infrastructure using
kubernetes.

Everything was deployed using a gitops approach, taging a new version of a service
would trigger a new deployment. In order to do so, we were using
[**ansible**](https://docs.ansible.com/ansible/latest/index.html) for on-premise
services and [**helm**](https://helm.sh/) coupled with
[**argocd**](https://argo-cd.readthedocs.io/en/stable/) for the in-cloud services.

## The specification

Based on this environment, here is what I wanted to develop:

- Expose a `staging.[service]` subdomain for each service which would resolve to
  a specific version of this service;
- The version of a service could be any of its branch on git. If I want to test
  _feature-A_ on the _ekee-api_ service I would deploy the latest commit on branch
  _feature-A_;
- Each service in the staging environment can use a different branch. They can be
  deployed independantly;
- The staging environment relies as much as it can on the prod one, no extra
  deployment needed;
- Deployments must be **simple**. If the developers needs to do more than two
  operations, they won't use it (we all know we are lazy kind of people).

Following this specification, here is the developer experience I wanted:

1. **Developer A** develops a new interface to share documents. The branch
   _doc-sharing-v2_ is created in the repository _ekee-dashboard_,
1. After commiting some beautiful engineering, **Developer A** opens a pull
   request and labels it _staging_,
1. Once the CI returns no error, **Developer A** clicks _deploy_ in _argocd_,
1. When the PR is closed and/or the label **staging** is removed, the resources
   used by in the staging environment are released.

## The implementation

### Adding the workflow around the _staging_ label in github

To trigger special workflows upon specific events, github exposes a wonderful
set of tools through what they call [github actions](https://docs.github.com/en/actions).

Here is the action we need to tag the latest PR's commit when the _staging_ label
is present and untag it when the PR is closed or unlabeled:

```yaml
name: Release staging version
on:
  pull_request:
    types: [opened, synchronize, reopened, labeled]
jobs:
  tag:
    if: ${{ !contains(github.event.pull_request.labels.*.name, 'no-ci') }}
    name: Release staging
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v2
        with:
          fetch-depth: 1
      # Retrieve the branch name when there is a `staging` label
      - name: Extract branch name
        shell: bash
        run: echo "branch=${GITHUB_HEAD_REF}" >> $GITHUB_OUTPUT
        id: extract_branch
      # Tag the current commit with `staging-BRANCH_NAME` when there is a `staging` label
      - name: "Tag staging"
        uses: eKee-io/git-tag-action@fix-not-a-git-dir
        if:
          ${{ !contains(fromJson('["unlabeled", "closed"]'), github.event.action)
          && contains(github.event.pull_request.labels.*.name, 'staging') }}
        env:
          TAG: staging-${{ steps.extract_branch.outputs.branch }}
          GITHUB_TOKEN: ${{ secrets.GITHUB_TOKEN }}
          BRANCH: ${{ steps.extract_branch.outputs.branch }}
```

### Building the staging image to deploy

Nothing fancy here! What we deploy is a docker image so the strategy is pretty simple:

1. Put a Dockerfile in the root directory of the services,
1. Add an action triggered on tagging events building the docker image,
1. Tag the docker image with the same tag as git,
1. Push this image to your registry in order for it to be accessible by
   your cloud resources.

To illustrate this, I used the github container registry in
[Dot-H/simple-staging-env-ex](https://github.com/Dot-H/simple-staging-env-ex).

With the github workflows I had an issue I didn't have with gitlab: a workflow inside a
branch does not seem to be able to trigger an other one without the explicit
[workflow_run](https://docs.github.com/en/actions/using-workflows/events-that-trigger-workflows#workflow_run)
action..

So no fancy linking through the tag event possible. We need to use this action in the
[build_image.yaml](https://github.com/Dot-H/simple-staging-env-ex):

```yaml
name: Build docker image
on:
  workflow_run:
    workflows: ["Release staging version"]
    types:
      - completed
env:
  REGISTRY: ghcr.io
  IMAGE_NAME: ${{ github.repository }}
jobs:
  deploy:
    name: Build the docker image
    runs-on: ubuntu-latest
    permissions:
      contents: read
      packages: write
    steps:
      - name: Checkout repository
        uses: actions/checkout@v3
        # The workflow runs on the main branch, we need to checkout to the
        # commit which triggered the `workflow_run` action
        with:
          ref: ${{ github.event.workflow_run.head_sha }}
      - name: Log in to the Container registry
        uses: docker/login-action@v2
        with:
          registry: ${{ env.REGISTRY }} # Login to ghcr.io
          username: ${{ github.actor }}
          password: ${{ secrets.GITHUB_TOKEN }}
      # Nicely format the tags & labels. This maybe useful if, as for me,
      # your actor name contains uppercase letters
      - name: Extract metadata (tags, labels) for Docker
        id: meta
        uses: docker/metadata-action@v4
        with:
          images: ${{ env.REGISTRY }}/${{ env.IMAGE_NAME }}
          tags: |
            type=raw,value=staging-${{ github.event.workflow_run.head_branch }}
      - name: Build and push Docker image
        uses: docker/build-push-action@v3
        with:
          context: .
          push: true
          tags: ${{ steps.meta.outputs.tags }}
          labels: ${{ steps.meta.outputs.labels }}
```

### Deploying the resources in k8s

Once the staging image is built and present on your container registry, it
should be available to your infrastructure.

In order for the infrastructure to handle the deployment of the staging
version, what we need is add a staging version for the [_deployment_](https://kubernetes.io/docs/concepts/workloads/controllers/deployment/)
, the [_service_](https://kubernetes.io/docs/concepts/services-networking/service/)
and potentially exposing through an [_ingress_](https://kubernetes.io/docs/concepts/services-networking/service/).

To do so without having to rewrite everything, I use [helm](https://helm.sh/)
and its templates. I won't explain the helm chart I developed for the example
in details here but rather the small helm tricks I used. Take a glance [here](https://github.com/Dot-H/simple-staging-env-ex/tree/main/k8s/staging-env)
to illustrate what I'm saying.

#### Staging specific values

The helm staging values are defined in the [`values-staging.yaml`](https://github.com/Dot-H/simple-staging-env-ex/blob/main/k8s/staging-env/values-staging.yaml)
and by default extend [`values.yaml`](https://github.com/Dot-H/simple-staging-env-ex/blob/main/k8s/staging-env/values.yaml).

The staging value file is composed as follow:

```yaml
nameOverride: "NAME"
image:
  pullPolicy: Always
staging:
  tag: staging-BRANCH_NAME
  enabled:
    echo-server: true
```

The `staging.enabled` controls which services compose the staging deployment
by using the `staging.tag`. When used, the tag is expected to be available
on the cloud repository.

The `nameOverride` permits to give a name to the created resources in the
staging environment. This avoids them to conflict with the production ones.
You may wonder why we don't rely on namespaces here. The main reason is that
it makes sharing resources between the staging environment and the production
one harder and the configuration less clear. With this approach, having staging
versions using only a subset of the real environment is way simpler.

The `image.pullPolicy: Always` causes the staging pods to always pull their
images. This is important because our building process does not change the tag
when a new version is deployed, it just publishes a new image. Therefore we
want the pods to always pull to make sure they always have the latest version.

#### Make staging elements use production resources

To permit one template file to be used by both the production & staging
deployments, their name are computed using the [`staging-env.name` template](https://github.com/Dot-H/simple-staging-env-ex/blob/main/k8s/staging-env/templates/_helpers.tpl#L4).
Nevertheless, some resources like secrets aren't meant for staging. For that
purpose, the [`staging-env.strictName`](https://github.com/Dot-H/simple-staging-env-ex/blob/main/k8s/staging-env/templates/_helpers.tpl#L12)
template permits to keep a fixed name which can then be used in staging
deployments:

```yaml
# deployment.yaml
#....
- name: ECHO_SERVER_USERNAME
valueFrom:
	secretKeyRef:
	name: {{ include "staging-env.strictName" . }}-secret
	key: username
```

#### Ignored resources

To avoid resources to be present in the staging deployments, they are wrapped
in a conditional clause at the beginning of the file to ignore:

```yaml
# secret.yaml
{{- if not .Values.staging.tag }} # Not in staging mode
apiVersion: v1
kind: Secret
metadata:
  name: {{ include "staging-env.strictName" . }}-secret
type: Opaque
data:
  username: YWRtaW4=
  password: MWYyZDFlMmU2N2Rm
{{- end }} # Not in staging mode
```

#### Deploy a staging environment

Finally, thanks to all those tricks, deploying a staging environment is as
simple as deploying a production one. All we need to do is:

- Give it a name;
- Specify the tag to use for the docker images;
- Inform which services are enabled.

```bash
helm install staging-echo-server . \
	--values values-staging.yaml \
	--set nameOverride=staging-echo-server \
	--set staging.tag=staging-update-echo \
	--set staging.enabled.echoServer=true
```

And that's it! The host `echo.staging-echo-server.alx-b.com` will be available
and route to the `staging-update-echo` version of the echo server.

To uninstall the staging env and free all the resources allocated
we just need to run:

```bash
helm delete staging-echo-server
```

## Conclusion

In this article we've seen how combining the github workflow, docker and helm
permitted us to setup a whole staging environment just from adding the label
_staging_ to a pull request.

With this base, you can build more complex and complete environment. At eKee
we used this in an architecture with 8 services connected with each others and
despite multiple staging environments running at once, the extra cost stood low.
Nevertheless, I recommand you to have a mirrored database for your staging
environments. A mistake happens quickly when you deploy the latest commits of
unmerged PRs 👀

I did not take the time to show you how you could connect the deployment to
github. Personnaly I like to use [**argocd**](https://argo-cd.readthedocs.io/en/stable/)
to manage deployments. It handles everything from the deployments to the rollbacks
and has a nice interface for my engineers to manage their staging environment without
having to type commands. Personnaly I felt like this section was making the
article way too big but if you feel like it's needed, don't hesitate to send me
a message on [Linkedin](https://www.linkedin.com/in/alexandre-bernard-ek/).


Zero configuration query language

More to come soon...

Other posts might interest you

Efficiently converting SQL results to JSON

Setting up a startup's staging environment