Implementation
To do them justice, each component would need one or more posts on its own. Even if not comprehensive, by going into some implementation details here, I hope to clarify some of the choices and why the high-level overview looks complicated.
In summary, RabbitMQ and block storage used Pattern A, Postgres used Pattern B, and Object Storage Pattern C.
Celonis Key Vault
AWS implements encryption at rest (or at least, the one we use) through KMS. When encrypting some plaintext data, a data store uses a fresh data key, which is itself encrypted by a KMS root key through envelope encryption. The data store stores both the encrypted data and the encrypted data key together. To decrypt the data, it needs to do the opposite. First, it sends the encrypted data key to KMS, which uses the root key to decrypt it, and only then is it able to use it to decrypt the actual data into its plaintext.
This double layer of encryption ensures protection against key wear-out, decouples root key usage from data encryption and also rotation from data re-encryption. When a root key is rotated, all new data keys are encrypted with the new version automatically. When it's revoked, all decrypt operations on data keys start failing (within a few minutes), rendering the data they themselves encrypted inaccessible.
The AWS storage services we rely upon use this mechanism out of the box. S3, for example, uses one data key per object. Besides using these services directly (for Patterns B and C), we also had to encrypt data in proxies for Pattern A. For that, we implemented a simple Celonis Key Vault (CKV) service, which wraps the KMS APIs (or Key Vault in Azure). The service both abstracts away the cloud provider APIs (so that consumers don't need to worry about which cloud they are running in), and also provides a simple API to generate and decrypt data keys based on the current tenant ID. This ensures the correct customer key is used at all times.
The "root key" is what we refer to as the customer-managed key in CMEK: it's the key under their control. Celonis doesn't have access to the key itself and can only "use" it through creating and decrypting data keys through AWS services, or Celonis Key Vault.
When encrypting some data, services like RabbitMQ and the Block Agent request data keys from Celonis Key Vault, which in turn depends on KMS. They follow the same process: encrypt data through fresh data keys, store their encrypted versions, and use CKV to decrypt them. We ensure that revocation and rotation have bounded delays by using new data keys for new data and periodically reloading (every few minutes) and re-encrypting (every day) existing data keys. Given their small size, this is cheap to do and brings us in line with what AWS provides.
RabbitMQ
Backend services make heavy use of RabbitMQ (RMQ) for message passing (1000+ queues, 250 msg/s per instance), and we're self-hosting a few clusters for each Celonis environment. Given that messages contain user data and can stay queued for an unpredictable time, we also had to find a solution for encrypting them at rest.
To solve that, we applied Pattern A cleanly: a transparent AMQP proxy that encrypts the body of messages dynamically before sending them to the existing RMQ clusters. The proxy behaves the same as a regular RMQ instance, as it speaks the same protocol, but only encrypts / decrypts messages on the fly, based on the tenant context (extracted from security context and passed as a message extended header by the client). It delegates all functionality to the actual RMQ instance, which at this point can store the data the way it wants (as it's already encrypted correctly). This required minimal changes to client-side libraries, didn't suffer from any of the problems discussed below and also improved connection counts toward the RMQ cluster.
DAM
To understand which tenants require encryption, and map them to their encryption key, the proxy uses the Orchestration service (described later), and Celonis Key Vault for the data encryption. To reduce latency, data keys are generated every few minutes (still respecting key rotations), instead of for every message. After a key revocation, queues' consumers stop being able to process messages after caches expire.
Before committing to this solution, we also considered "simpler" variations. For example, removing the proxy, and using one vhost per partition, making sure data for each is stored in a separate directory, and each directory encrypted separately with a per-tenant key. For encryption we hoped we could reuse the block storage solution and for routing, pre-existing client-side libraries in backends would have set the appropriate vhost based on the tenant security context.
We discarded this for multiple reasons. The biggest was that not all queue types split storage per vhost. A notable example is quorum queues we heavily depend on, which store a unified write-ahead log (WAL) per node, shared by all queues. This meant we couldn't cleanly separate data per-vhost, and to solve this, we would have had to use classic queues only (unthinkable), or fork RMQ to use split WALs per vhost, which seemed a high risk, high maintenance proposition.
A second issue with the approach is that a listener (the receiving end) is tied to one vhost. The AMQP 0-9-1 protocol picks its vhost once during connection opening, and doesn't allow changing it afterward. Channels and consumers belong to a connection and there's no way to subscribe to a queue "across every vhost". Besides duplicating all queues, exchanges and bindings, this implies that every backend would have to open one connection per queue, per partition, which would have meant a two orders of magnitude increase in connections, which is a critical resource.
An alternative possibility would have been to use Pattern C: split into multiple RMQ clusters and dynamically route messages based on the tenant at the client side. This would have solved the storage problem (each instance would have been single-tenant and used native EBS encryption) and connection multiplicity at the RMQ side, but not at the receiving end. This would also have been complicated to implement (fat client-side library in several different languages) and increased maintenance and costs for RMQ clusters.
Block storage
Even though RabbitMQ didn't end up needing encryption at the block storage level, the general problem was still present. Some backend services did use block storage, mainly for caching or stashing intermediate data, and even though this was a minority, it was an important one. These were the ones handling the biggest data volumes and the most performance-sensitive. Two main examples are Vertica (for data lake) and the "compute service" for serving data model queries.
Our initial thought was to encrypt data from the application side before it hit the disk. This was doable in our libraries, but not everywhere. For example, not for Vertica (which is closed source and cannot use our libraries), nor for the compute service, where it was not considered performant enough. Without getting into too much detail, encrypting from the Java part of the service was deemed too resource intensive, and doing it from the C++ part would not have been reusable across services.
We therefore set out to implement a transparent solution following Pattern A, based on fscrypt, which was both performant and reusable. The main idea was to split the responsibility of "asking for a tenant directory" from "encrypting it". The second part would become a feature of the Kubernetes node a Pod would run in.
DAM
We implemented a DaemonSet (which is a Pod running on every node) called Block Agent. This exposed a local API (REST over a Unix domain socket) to open and close a directory for a tenant. Client libraries would do this automatically before handing over a directory to the application, based on the SecurityContext. The first time a tenant needed storage in a volume, the Block Agent would temporarily mount the volume locally, fetch a data encryption key from Celonis Key Vault, store its encrypted version on the volume, and use it to configure kernel-level encryption for a new directory. The application could then use the directory normally. On backend restarts, all directories in the volume are sealed, and therefore require valid access to the customer keys on KMS. To ensure proper handling of root key rotations and revocations, the agent periodically re-opens directories and re-encrypts their data keys. If the key is no longer available, the directories become unusable (permanently, or temporarily if the customer restores the key).
This setup had several advantages: It was language independent and easy to adopt. It also introduced acceptable overhead (5% - 10% IOPS drop on our workloads), and finally came with built-in compliance. Given that all encryption happened in the kernel, we inherited FIPS compliance from the host images.
For single-tenant backends instead (like Vertica) we provided specific per-partition Storage Classes, configured to use EBS with the customer-provided key. Backends provisioned for a single tenant then had to use the proper pre-configured Storage Class, and everything else would work the same.
Postgres
For efficiency reasons, we use cloud-managed shared Postgres database instances (e.g. one Aurora RDS cluster on AWS), in which each backend service gets a dedicated logical database. This strikes some balance between isolation (each service has its own view) and efficiency (resources are shared by backends).
Multi-tenancy was managed at the row level through a tenant_id tenant-discriminator column per table. Java core libraries propagated the tenant ID from the SecurityContext to queries transparently. This was done through custom @TenantId annotations, equivalent to Hibernate's TenantId, and backed by a Hibernate filter that added a WHERE clause to queries automatically.
We could have encrypted those rows transparently through a Postgres proxy, based on the same discriminator (row-level encryption). Each row with user data would have been encrypted before even reaching the database, similarly to how the RabbitMQ proxy does it. This solution however breaks any query relying on the contents of encrypted columns: sorting, filtering, manipulation, because the execution of the query would still happen at the Postgres cluster, and that would lose visibility into encrypted data.
We couldn't solve this on the proxy, as it would have meant semantically understanding and rewriting queries on the fly (e.g. WHERE x = 'foo' becomes WHERE x = '<encrypted_foo>'), which is a very hard problem to solve. But even if that were doable, among other things, it wouldn't cover approximate queries (e.g. WHERE x LIKE 'foo%'). Because, what do you set foo% to? Encrypted foo is not a prefix of encrypted foobar. This would have meant turning those queries into full scans.
Another possibility would have been to ask backend engineers to avoid forbidden operators, or do more client-side filtering. The magnitude of this change was however large and not transparent, and we had to discard it.
We also considered using Tablespaces and partitioning each table based on the tenant discriminator. Storage would then be naturally separated by tenant and could be encrypted at rest separately, using for example the block storage solution. This would have complicated schema management quite a lot, and also wouldn't solve for the fact that the Postgres Write-Ahead Log (WAL) is unified. The last straw was that this would also have meant moving from cloud-managed to self-managed Postgres clusters, which we were not prepared to do.
What we ended up using was Pattern B. It's no secret that database encryption is best managed by databases themselves. We split the database clusters into several partitions (one per CMEK customer). Each instance was then encrypted at rest with the right customer key at the cloud provider level. To route among those instances, we introduced a proxy (a forked version of pgcat) that speaks the Postgres wire protocol, provides connection pooling and routes according to tenant context.
DAM
Of course then, each database cluster has the same list of logical databases, the same schemas and the same tables. What changes is the rows within each table, as every partition only contains rows belonging to the associated tenants.
DAM
To make routing work transparently, we extended the core libraries so that when a connection is taken from the pool, the library sends a /*ctx:<tenant_id>*/SELECT 1 statement to pgcat. The proxy answers it locally and routes all following queries on that connection to the correct tenant's DB instance. This needed no custom protocol and no full SQL parsing. The proxy only needs to recognize these hints and keep the tenant-to-partition mapping in memory.
This trick solved the vast majority of routing needs we had at the time, but not all. We discovered a long tail of cases where multi-tenant queries were necessary (e.g. old records cleanups, statistics). We initially thought of providing a higher-level library functionality to iterate the same query over all partitions, and rewriting those queries, but we would then also have lost cross-partition atomicity. Automatic retries of failed queries are not safe in general (i.e. idempotency is not always guaranteed), so instead of spending a long time rewriting while taking significant risks, we decided to add a reserved ctx:x-tenant context that routed to all partitions through ShardingSphere (managed automatically through annotations).
Besides routing, multiple instances also brought the challenge of schema management. Whereas before, services could choose to use whatever mechanism they wanted (Flyway, Alembic, custom one-time jobs, SQL scripts at start-up, etc.), we had to become more restrictive, to ensure schemas stayed in sync among all partitions. The good news was that centralizing schema management was a good idea from many angles: no more manual schema migrations, adding linting for common pitfalls and generally preventing many footguns (we've seen some incidents related to bad schema management). This made the transition largely welcomed by engineers, especially because it was automated and driven by us. Onboarding was a GitHub workflow that took schema dumps from the live DBs and rewrote them into a schema.sql suitable for Atlas in a central git repository. Migrations then became new SQL files with changes from previous versions (through PRs). In production, we used a Kubernetes operator that applies those changes to all partitions through Jobs. Applications using our libraries check at startup that the schema version returned by the live database corresponds to the one expected by the running code (a simple version number check).
I'm mentioning only the biggest changes; we had to solve many more sub-problems. For example:
- Tenant-agnostic data (i.e. that didn't belong to any specific tenant) stayed in the shared DB. How do you then join it with tenant data?
- The proxy became the single point of access towards databases. This provided additional benefits, such as better connection pooling, reduced memory usage on DBs, and better failover behavior.
- The proxy also became an enforcement funnel we could use to enforce better service isolation.
- The schema migration automation.
- Postgres "fleet management", or how do you manage, upgrade and scale database servers at scale?
I'm leaving these and other Postgres topics out of this article, but wanted to give you an idea of the complexity behind this apparently simple feature. Postgres was in fact the most complicated storage service to solve CMEK for.
Object Storage
Unlike Postgres, which mainly hosts metadata, Object Storage stores our customers' actual data, which is orders of magnitude larger. Hand-waving and simplifying a lot, Celonis is a data pipeline where data is ingested and processed from and to Object Storage in stages. Adding latency or lowering the reliability of this path has a large impact, because it comes at a cost that is multiplied by the number of steps in this pipeline. Besides the criticality, services were a lot less uniform in the way they used Object Storage than they were with Postgres. Some used our client-side libraries (Java and Python), while others had bespoke libraries or directly used the cloud provider SDKs. Some (e.g. Vertica) we could not really change, as they were highly optimized to use Object Storage directly.
The idea of introducing a transparent proxy was the most appealing initially (either Pattern A or B), as clients would only need to change the configured S3 endpoint, and the proxy would abstract the encryption concern away, similarly to the Postgres solution. We liked it because it allowed the most future flexibility behind a stable API.
Unfortunately, we had to discard Pattern B (proxy to bridge), mainly because of complications in addressing request signing (which prevents the proxy from rewriting the destination bucket without re-signing the request). But more generally, we had to discard proxy-based solutions because of bandwidth concerns (which would have required a large deployment), and more importantly, the fact that Databricks (an alternative to Vertica in our solutions) refused to use custom S3 API endpoints. Similarly, Snowflake and bring-your-own-bucket integrations expect customers to connect to an S3 bucket directly, and asking them to use custom endpoints would have broken them.
We could have asked every client to set client-side encryption correctly per-tenant, but this was error-prone and would have caused a 100x increase in KMS costs, because we couldn't then use bucket keys.
We went instead with a pragmatic client-side library + routing API approach (Pattern C). Backend services using one of the libraries got the change for free, and others could either use the routing API directly to map a tenant to its assigned buckets, or pay at deployment time for dedicated single-tenant instances.
DAM
The core libraries in backends swap the bucket name in every request to S3 with the appropriate one, by using the tenant ID in the SecurityContext. The mapping from tenants to buckets is maintained by the Orchestration service (described below). The library simply fetches, caches, and refreshes it on demand.
Single-tenant backends had to instead provision their service for every tenant and configure each of them to use a different bucket. This is of course sub-optimal, unless the service was already provisioned in this way.
As consequences of this decision:
- We used S3 bucket keys in AWS to save on KMS costs (up to 99%), so we had to split buckets, rather than use client-side or path-based solutions.
- Aggressive caching of the tenant mapping was necessary to trim latency. This applied to libraries and custom implementations as well.
- Evolving the setup in the future didn't become easier, as clients are exposed to the implementation detail of "splitting data into multiple per-customer buckets".
- Cloud-provider details are either exposed to clients or to services directly. There's no abstraction over object storage.
Exposing object storage details to backends was already a reality, because of heavy usage of custom lifecycle policies and presigned URLs, which are inherently cloud-provider specific.
Orchestration and automation
Before this project, we only needed new infrastructure during the spin-up of a new environment, or when we carried out upgrades and improvements. Although painful, these were happening at a pace where human involvement was possible. This feature, however, drastically changed the picture, as we had to start provisioning in response to tenant onboarding, which is automated and happens at a very different scale.
The implication was that we had to be able to hot reload proxy configuration and, more importantly, automate infrastructure provisioning and make it hands-off. The good news was that we could roll out improvements and automation incrementally, as the feature went from a pilot, to a private preview, to becoming generally available.
DAM
We opted for a Kubernetes operator-based solution running on a management cluster already responsible for provisioning some of our cloud infrastructure: the Partition Operator. This new operator is responsible for creating and reconciling resources based on two Kubernetes Custom Resources: a template, defining which resources each partition should have (the Template CR), and a series of Partitions, enumerating which partitions should be instantiated and which key to use for the encryption. This was implemented as a regular Kubernetes operator that manages Crossplane Managed Resources. This way we could easily add business logic and guardrails to the provisioning, while delegating the actual act of provisioning to battle-tested Crossplane providers, which we were already using.
After adding or removing partitions, the operator is then responsible for communicating with the respective Orchestration service, which is responsible for holding the configuration of an environment, providing APIs to query it and coordinating changes to the proxies.
The link between a customer onboarding and a new partition initially required a config change to our GitOps repository by a platform engineer, and is currently being automated further, so that functions other than Engineering could execute it through the default Celonis control plane.
