ext_authz cache

[naoitoi-v]

Commit Message: This is a draft PR to discuss the design of the response cache in the ext_authz filter.

We are seeking feedback on the design to make sure this is headed to the right direction.

Similar requests were discussed in #37449 and #3023

Additional Description:

Purpose:
We would like to cache the response from an external authorization server in the ext_authz filter for scalability. Depending on the use case, if you do not have to check the authentication token on every request, you can reduce the number of calls to the server by caching the response from it.

Functionality:
To use this functionality, you need to configure the name(s) of the header(s) in which the auth token is carried, e.g., "Authorization" or "x-auth-token." You can also configure the max cache size and TTL. When this is configured, ext_authz will cache the response from the external authorization server.

Implementation:
We implemented a simple cache. Responses are stored in a simple unordered_map. We implemented a simple FIFO eviction policy over the LRU policy to make the cache size small. In our benchmark, for each cache key (35 bytes), we need ~100 bytes of memory.

We store a response in the cache in the onComplete() method.
We read a cached response in the decoderHeaders() method.

Next Steps:

• Write tests.
• Make sure the code complies with the coding style.
• Do pre-commit checks.
• May add an option to NOT cache 4xx errors to avoid cache poisoning.
• May add an option to inject randomness in TTL to avoid synchronization.

Risk Level: Low. This functionality would be turned off by default.

Testing: TBD
Docs Changes:
Release Notes:
Platform Specific Features:
[Optional Runtime guard:]
[Optional Fixes #Issue]
[Optional Fixes commit #PR or SHA]
[Optional Deprecated:]
[Optional API Considerations:]

[repokitteh-read-only]

Hi @naoitoi-v, welcome and thank you for your contribution.

We will try to review your Pull Request as quickly as possible.

In the meantime, please take a look at the contribution guidelines if you have not done so already.

🐱

Caused by: #37953 was opened by naoitoi-v.

see: more, trace.

[repokitteh-read-only]

As a reminder, PRs marked as draft will not be automatically assigned reviewers,
or be handled by maintainer-oncall triage.

Please mark your PR as ready when you want it to be reviewed!

🐱

Caused by: #37953 was opened by naoitoi-v.

see: more, trace.

[repokitteh-read-only]

CC @envoyproxy/api-shepherds: Your approval is needed for changes made to (api/envoy/|docs/root/api-docs/).
envoyproxy/api-shepherds assignee is @markdroth
CC @envoyproxy/api-watchers: FYI only for changes made to (api/envoy/|docs/root/api-docs/).

🐱

Caused by: #37953 was opened by naoitoi-v.

see: more, trace.

[ggreenway]

Some early feedback:

• This doesn't do FIFO eviction. I think the evicted element is the one with the lowest hash value. You'll need additional bookkeeping to know the order the elements were inserted.
• The semantics of having multiple possible headers that contain the cache key are confusing, and possibly insecure.
• You'll need to refactor all of this to conform to Envoy style and norms

[adisuissa]

A drive-by suggestion: it may be beneficial to generalize the caching for both ext_authz and ext_proc.
I suggest creating the cache configuration (an implementation) separate, and use it only for ext_authz in the first step.

[ggreenway]

Related to what Adi said, I think you need to cache the response message and replay it on each request. It may add or remove headers, etc. Just looking at the status code is insufficient.

[naoitoi-v]

Thank you for your early and insightful feedback, @ggreenway, @adisuissa.

1. This cache eviction implementation is not FIFO.

Great point!

In our (Verkada's) use case, it's important to keep the memory footprint as small as possible. We expect few evictions. We'll change this implementation to random eviction.

In the future, there may be users who want more sophisficated eviction policies (e.g., LRU, random sampling-based LRU). We'll restructure the code so that one can provide different cache implementation.

2. Looking for auth tokens in multiple headers

Good point. For now we'll make it to look at only one header.

Our use case may require it to look at multiple headers for leagacy reasons. If we have to go that route, we'll use header + auth token as a cache key, so we wouldn't mix auth tokens from multiple headers.

3. Compliance to Envoy coding style

Yes, we started this effort. Fixing things pointed out by //tools/code_format:check_format and //tools/code:check .

4. Making cache config and code one detached from ext_authz so that it can be reused in ext_proc

This makes sense. We'll try it.

5. Storing response message and headers

This makes sense.

In our use case, we'd only need the status code. It's important to minimize the memory footprint.

We'll write the code to store and replay the response messages and all the headers. We'll make this configurable so that the user can decide to store response & headers, or not.

**

Thanks for the great discussion, again. We'll keep you updated on the progress.

Nao

[naoitoi-v]

I took care of (3) coding style.