[RFC] Support pluggable KV and SQL stores

[bri365]

Objectives

This document defines a proposal for updating the SPIRE datastore to a simpler pluggable solution, capable of supporting both SQL and KV backend stores. The primary objectives for this change are to:

1. Satisfy requests for more storage options
2. Simplify installation and operation, especially in container environments
3. Streamline plugin development and support
4. Scale from a few to hundreds of thousands of agents
5. Strengthen SPIRE resiliency solutions
6. Stage SPIRE changes across releases in a way that minimizes impact and risk to running systems

Background

The current datastore design dropped support for plugin extensibility, and only supports sql (SQLite, MySQL, and PostgreSQL), with dependencies on gorm. The rapid evolution of the datastore interface made ongoing plugin support impractical. An investigation last year demonstrated the efficacy of a simpler interface for both SQL and KV stores.

The problems identified last year are still largely relevant:

• Implementation complexity
• Interface churn
• SQL-specific challenges

The SPIRE server datastore is responsible for reliable persistence of agent nodes, selectors, registration entries, bundles, and join tokens. Bundles are associated with multiple registrations, nodes have multiple Selectors, registrations have multiple bundles, DNS names, and selectors.

Datastore operations currently include the following (not all objects support all operations):

• Create, Delete, Update, Append, Prune
• Fetch, Count, List
• Get, Set

Queries across several fields are currently supported for attested nodes and registration entries (see ListAttestedNodesRequest and ListRegistrationEntriesRequest protobuf messages). The proposed solution preserves, and in some cases enhances, flexible query capabilities.

High availability support has been added since the last investigation, adding cross server coherency concerns that must be addressed in proposed solutions.

Proposal

This proposal aims to address the above objectives and problems in a phased approach with the goal of minimal disruption throughout the transition. Key elements include:

1. Leverage the current datastore caching concepts for read requests wherever possible
2. Introduce a simplified backend store plugin interface for item-independent operations
3. Add plugins for KV database(s), starting with etcd
4. Rewrite existing SQL plugin(s)

Leveraging the current datastore cache concept reduces the need for expensive crawling queries of the backend store by serving them from SPIRE server memory while persisting them externally. Most data are safely cacheable; agent authorization caching will be explored at a later time. Change notifications and periodic full refreshes will be employed to ensure server cache consistency and stale data invalidation.

A simplified pluggable store interface will be created, consisting of Put, Get, Count, and Delete operations for one or more entries. The interface will also provide operations to Begin, Commit, and Abort transactions containing multiple primitive operations for cases where read-modify-write operations are required (e.g. prune bundle) or objects reference other objects (e.g. Registration Entries and Selectors or Bundles). The interface may also define a Watch operation to report new or updated items for distributed real-time cache updates.

The initial KV store reference design will support Etcd and serve as the standard for additional KV store plugins. SQL store(s) will be refactored to the new simplified interface.

Phasing

In the interest of minimizing disruption to production customers, offering clear value and migration paths, and keeping changes to manageable sizes, the following phases are considered:

1. Add KV plugin support

• Move current datastore implementation from a plugin to a regular module, retaining the current interface, and SQL backend.
• Create a new “store” plugin with a simplified interface for KV backend(s) only. SQL backends continue to use the existing code in the non-pluggable module. KV backends supported by new code paths in datastore module using the new store interface.
• Create a new etcd KV store plugin with the new store interface.

2. Add SQL plugin support

• Create new SQL plugin(s) with the new store interface
• New SQL plugins exist as alternative to existing non-pluggable SQL store

3. Add Watch support for real-time cache updates
4. Retire legacy SQL support

Store API

The simplest store API passes keys and values rather than entry types and identifiers. This approach is chosen for simplicity of plugin development. Helper functions will be offered as needed to extract entry, ID, and index information from keys.

• Put: add one or more key/value pair(s) to the store
• Get: retrieve one (prefix false) or multiple (prefix true) key/value pair(s) from the store
• Delete: remove one (prefix false) or multiple (prefix true) key/value pair(s) from the store
• Count: return the count of keys with the given prefix
• Begin: initiate a transaction
• Commit: commit a transaction
• Abort: abort a transaction
• Watch: retrieve a stream of updates for one or more key ranges

Objects

KV stores accepts []bytes for keys and values. Building on the prototyping work from last year, two KV object types are required for this design:

Items

• Key - item type ID:item ID
• Value - item gRPC bytes

Question: is it worth the extra few bytes in every record to identify which field is the primary key field in the gRPC bytes? It will be defined as a constant either way.

Indexes

• Key - i:item type ID:item field ID:item field value:item ID
• Value - item type ID:item ID

Question: is it worth the extra bytes in every index record to store "item type ID:item ID" as the value? The data exists in the key and can be reconstructed; is this significantly faster/slower/simpler than iterating over the returned values?

SQL databases prefer integers for primary keys, rather than the []bytes for KV keys. In the interest of keeping the pluggable store interface simple, objects are designed like KV objects. SQL plugins may opt to store them the same way a KV store does or add index columns for ranged operations. Both approaches will be prototyped and evaluated.

Considerations

Data Size

A million agents and/or registration entries at a (hopefully) generous 4KB each would require 4GB of memory - very reasonable for a deployment of that size. This is half the recommended max Etcd data max and well within SQL database limits.

Performance

API authorization requests for a million agents checking in every five seconds would result in 200,000 authorization queries per second. This would strain a database and should be handled primarily from memory if possible. 100,000 agents would require around 20,000 queries per second, well within Etcd and SQL database limits.

Database Availability and Concurrency

Data store availability in the face of backend failures may be mitigated through a number of store specific alternatives. MySQL offers group replication for multi-master database availability. Percona offers resiliency solutions for MySQL, PostgreSQL, and MongoDB. Etcd enforces strict serializability and linearizability by default for parallel multi-node availability.

Concurrency in distributed systems is critical for data consistency and correctness. SQL transactions and locking provide this for SPIRE today. Etcd has documented notes for distributed coordination, which will be used to ensure transactional integrity.

Database Migration

SQL database migrations are unaffected in the first phase, as we would leave the existing structures in place.

A migration tool will be required to convert the existing tables to the new store tables in the second phase.

Security

The Watch operation allows SPIRE servers to listen for updates to the database, allowing for real-time updates to cache to maintain coherence in multiple server HA deployments for datastore plugins capable of supporting this. This also addresses scenarios where network connection between SPIRE servers is not available.

SPIRE servers also perform full cache reloads on configurable intervals to protect against cache drift. This operation will alert any discovered differences for analysis and potential debug. Over time, the default refresh interval should increase if no drift is detected.

An updated security review should be conducted with/after this refactor.

Failure Scenarios

How does the new system handle:

1. failure or unavailability of one or more backend store nodes
2. failure or unavailability of one or more HA SPIRE servers
3. network segmentation of SPIRE servers and/or store servers
4. (more scenarios needed)

[azdagron]

Thanks for putting this together @bri365. I'm still digesting but a few things that surfaced as I read this over:

1. Are objects stored under a single key (by primary index)? Are there key/value size limitations that we may run across? Would core need to adopt constraints on object size? Would a SQL implementation need to use a large column type to meet the theoretical maximum value size? How would that impact performance?
2. It isn't clear to me, reading the proposal, what fields for each object are being considered for indexing. Are we indexing every column? What is our plan for index migration when we want to change what fields are indexed? How does this jive with HA? How does this impact future changes in the types of queries we execute?
3. How are indices updated when an object is updated?
4. Does this proposal assume the same breakdown of models that we have today? Has there been any thought into what improvements, if any, could be made to the existing models?

[elinesterov]

This is definitely something we are looking forward to at ByteDance :) happy to collaborate on this. We've done some tests with 100k agents with recent caching changes enabled which shows around 15k QPS. It will be interesting to take it x5 or x10 from here 😬 .
In our current deployment model, we have DB per DC which adds a certain overhead, especially for JWT-SVID. Having one global DB spread across multiple regional DC will be great but might be challenging because of performance and specific failure scenarios.

[bri365]

Great questions @azdagron - keep them coming

1. gRPC limits messages to 4MB (I've also heard 1MB internally), which sets what I believe to be a rather high practical limit for our objects. MySQL has a 64KB row limit; large text and blobs are stored separately. Performance testing is definitely a critical part of this effort.
2. The goal in simplifying the store interface is to allow SPIRE to index any fields it desires, with or without backend store knowledge. KV indexing keys can be created as needed by SPIRE, and a simplified SQL backend can use this approach as well. More complicated SQL store plugins may have the option of "unpacking" the data to create indexes columns. This will be decided after performance analysis.
3. I expect indices and objects to be updated as a single backend transaction for KV and simplified SQL.
4. This proposal presumes the same fields as currently used, but as of now makes no assumptions about relationality or nesting. This is definitely an opportunity to review these.

[bri365]

Thanks, @elinesterov! Architecturally, I am aiming for one million agents. Can you elaborate on the idea of a global DB versus nested or federated in your use cases?

[azdagron]

My question on adding/removing indices is mostly around how that is managed in an HA deployment. For example:

1. In the presence of multiple servers, who builds the new index?
2. How are we going to ensure the completed index is consistent (e.g. are objects allowed to be mutated while the index is being built, and if not, how do we block those ops).
3. Do index changes need to be managed over multiple releases? I presume so) considering our upgrade policy (version N and N-1 should be able to coexist).

Right now much of the complexity above is handled by the SQL databases. Our solution is now operating at the level previously handled by SQL, so we'll need to handle this ourselves.

Also, is there a need to build multi column indices? For example, our current entry listing semantics involve queries filtered by multiple columns (e.g. parent + spiffe id + selector)

[bri365]

The server updating the object is responsible for updating the indices as well. In the simplified KV format the indices are just more objects with different keys, and those will be performed in a single transaction, with a distributed lock. There will be no "rebuilding indices" per se. If we add an index checker utility (probably a good idea), it will add indices the same way.

Any index added or removed in a new release will need to be created across all entries as part of the upgrade path (see "checker" utility above), with code supporting N-1, N, (and maybe N+1 if we choose to background create new indices prior to using them).

Considering multi-field indices, they should be no different than regular indices - created transactionally on object creation or update. Examples of multi-field indices should be added to the document.

[bri365]

It may also be worth reiterating that this solution builds on the current caching model, so we envision these multi-column queries to be handled from server memory rather than from the backing store.

[azdagron]

In the simplified KV format the indices are just more objects with different keys, and those will be performed in a single transaction, with a distributed lock

I don't think leveraging a distributed lock is going to cut it. SPIRE allows for N and N-1 versions of the server to coexist. If version N introduces a new index on a field, even if it takes a lock to build the new index, operations by N-1 will not take the index into account, meaning that object deletions will leave dangling index keys, object additions will have index key gaps, etc. We don't have this kind of problem today because the DBS manages the indices, not SPIRE. Even if the index is not actively used until N+1, there is going to have to be a step to fix up the index at some point.

It may also be worth reiterating that this solution builds on the current caching model, so we envision these multi-column queries to be handled from server memory rather than from the backing store.

Yes, if the original thesis is sound (we can fit all this stuff into memory), that will probably work as long as we don't have queries that have strong consistency guarantees that span multiple indices. I think that is probably true given the current data set, but it could impact future query flexibility, so it is a restriction we'd have to be comfortable with.

[bri365]

I don't think leveraging a distributed lock is going to cut it. SPIRE allows for N and N-1 versions of the server to coexist. If version N introduces a new index on a field, even if it takes a lock to build the new index, operations by N-1 will not take the index into account

Isn't this one of the reasons why we introduce new dependencies at least one version before using them?

[bri365]

As discussed, I'm moving the documentation effort to a Google doc

We can keep questions flowing here as well - they will be captured in the document.

[bri365]

I believe do we want to keep Create and Update operations separate at the store layer to enforce unique identifiers at that layer (e.g. prevent two servers simultaneously creating the same bundle, RE, etc.)? Does anyone disagree?

[azdagron]

Isn't this one of the reasons why we introduce new dependencies at least one version before using them?

Yes. The dependencies have thus far been schema changes and DBS managed indices, not data migrations. We haven't yet tackled data migrations, which are essentially what the proposed KV indices are, at least from the storage backend perspective. Our current migration strategy is sufficient for schema changes and DBS managed indices, because operations by the N-1 servers aren't impacting the integrity of the new changes. They are oblivious to their existence, but otherwise don't need to care about them. That isn't the case with these K/V indices. Operations by the N-1 servers WILL impact the integrity of the indices, so we need clean plan of execution into how indices are added, deleted, etc.

[elinesterov]

@bri365

I am aiming for one million agents. Can you elaborate on the idea of a global DB versus nested or federated in your use cases?

When you use nested SPIRE topology you still need to have multiple clusters. Let's say you want to have a million agents and one cluster for 100k agents. In that case, you end up with 10 clusters and one for top-level to support your nested architecture. That is fine but each cluster needs to have its own datastore. When each cluster has its own datastore you get an issue you need to resolve - how to prevent agents to connect to a different cluster? (Because when it connect to a different cluster that cluster doesn't know anything about the agent's identity) You can partially solve this by having registration entries for all agents in all clusters and re-starting the agent when it connects to a different cluster.

Another solution would be to have agents connecting to specific clusters that could be done via configuration but that would depend on your agent deployment model. If your agent deployment model allows you to specify which cluster it should connect to then I would definitely use the nested spire model. This is not something that works for us so we have to rely at this point on one global spire server address which is resolved to different clusters in different DC.

When you have a "global" data store that could be shared across different clusters you don't have all the issues above because the agent can connect to any cluster that uses the same datastore. However, datastore performance could be an issue in this case especially with a growing number of agents and servers in different spire clusters.

[rturner3]

Hi @bri365, thanks for putting so much effort into this. Solving some of these datastore pluggability and performance problems once and for all would be an incredible win for the project.

I gave your current proposal a once over and left you a few initial questions in the linked Google Doc. I probably need a little more time to fully wrap my head around this, but I'm interested in seeing this through.

[evan2645]

I stumbled across some relevant issues/chatter in Smallstep's project today that I thought I'd share here. There are some community requests for issuance auditing that is not CT [1] [2], and the current k/v storage backing is cited as the primary blocker in implementing it. Apparently, the project is planning to move away from k/v in favor of an SQL backend in order to better support this class of use case [3].

As we look towards similar audit functionality in SPIRE, I think the lesson here is that we'll need to offer a pretty high degree of flexibility. We'll probably need either an API with a (very) rich set of filters, or an SQL-based storage option that is directly consumable (i.e. not k/v data stored in an RDBMS). I am not totally sure on the implications of the former in the context of this issue (indexing? issuance data size? synchronization? something something :) ), but it definitely feels like an experience that we can learn from.

[1] https://gitter.im/smallstep/community?at=5fc10266ed05c659158ceff6
[2] smallstep/certificates#239
[3] smallstep/certificates#282