# Command Cache

The command cache is used for de-duplicating both idempotent and non-idempotent requests, e.g., when broker replays requests because client disconnected. This is necessary when methods are not idempotent, or else the same method would be invoked twice, which is incorrect.

Command cache is also useful for reusing a previously computed cacheable response when invoking equivalent idempotent methods, where it is unnecessary to invoke the same method twice if the response is fresh.

> A response for an idempotent command is cached for de-duplication and _can_ be cached for reuse. A response for a non-idempotent command is cached only for de-duplication.

## Assumptions

1. Methods are attributed with idempotency when established into a RPC service. Idempotency should be an immutable property of a method.
1. Responses of idempotent methods have a time-To-Live (TTL) which is indicated by the server when producing a response for a request. TTL may or may not be a DTDL property, and may or may not be immutable.

> [!NOTE]
> Considerations on a method idempotency and TTL related to DTDL modeling are irrelevant for this discussion and will be addressed in a separate doc_.

### _Duplicate_ request and _equivalent_ request

The command service tracks requests by a Correlation ID which is a part of the request's metadata. Correlation ID MUST be generated by RPC stack and SHOULD NOT be under user control.

Two requests should be considered **_duplicate_** when the requests have identical correlation ID. If two requests have the same correlation ID, then the topic and the payload of the requests MUST match, or else the request should be treated as a protocol error. Identifying such error is not necessarily relevant for this discussion. For asserting protocol correctness we only need to track Correlation ID of requests. 

- A request may be **_repeated_** by the broker, e.g., when the server MQTT client disconnects and re-connects. The broker will send the same PUBLISH (identical PACKET ID) with a DUP flag set to true. The PUBLISH ID and the DUP flag are MQTT constructs, and will not be observed by the RPC stack. The RPC stack works only with the Correlation ID. The RPC protocol on executor side should treat a **_repeated_** request as a **_duplicate_** request. In this case the executor MUST use the cache to de-duplicate a non-idempotent request. In case of an idempotent request the executor SHOULD use the cache, but it is not required for correctness.

- An invoker may also **_repeat_** a request, e.g. when the MQTT client of an invoker disconnects before receiving a PUBACK for a request, and then reconnects. In this case the executor will observe a **_repeated_** request, i.e., the **_duplicate_** request twice or more times. The broker will send distinct PUBLISHes (different PACKET ID) for the **_duplicate_** requests, however, they will have the *same* Correlation ID. The RPC stack works only with the Correlation ID.

Also, one or more invokers may invoke the same method with same parameters and same topic multiple times. In both cases, the invoker clients will send a different PUBLISH (different PACKET ID) and the RPC stack will observe a different Correlation ID for each request. The executor will observe an **_equivalent_** request, i.e., a request for the same method with same topic and parameters, but different correlation ID. The executor should treat an **_equivalent_** request as a **_different_** request for the same method with same parameters. In this case the executor SHOULD use the cache for efficiency, but not for de-duplication, and only if the request is idempotent. If the request is non-idempotent then the cache should not prevent the new request from executing.

In summary, when the broker repeats a request, that request will be _same_ as a request the executor may have observed already. When an invoker repeats a request, that request will be either _repeated_ or just _equivalent_ to a previous request, and the executor should use the Correlation ID of the request to track the difference. 

> NOTE: when an invoker repeats a request because because it never got a PUBACK for the first request, the broker will PUBLISH both (or multiple) MQTT PUBLISH packets that it received from the invoker. The executor will observe _repeated requests_ in this case. From an RPC layer's perspective, this case is equivalent to the case where executor disconnects and re-connects before sending PUBACK for a request it already received. In both cases the _same_ or _repeated_ requests received have the same correlation ID.

De-duplicating via cache cannot safeguard against executing the same method twice if a server restarts after executing a method but before signaling completion to the broker. Only QoS2 can cover for that case.

When there is only one instance of an executor, the cache will be effective in de-duplicating messages as long as the process does not terminate before the delayed ACK that completes the transaction is received by the broker. If the executor process terminates before then, then the request will be executed again upon the broker re-delivering the message. This case is equivalent to the case when the server terminates after executing the method but before signaling completion to the broker, and therefore cannot be fully prevented without QoS2.

The immediate goal is to serve the single executor case with an in-process cache and take the necessary precautions to isolate execution failures for the server and the executor as much as possible, e.g., via proper failure and exception handling.

## Cache behavior for RPC correctness
Caching in the context of RPC is done for 2 reasons: 

### 1.	Caching for de-duplication of requests with same CorrelationID, i.e. _**duplicate**_ request

1. Invokers should never send 2 requests with the same CorrelationID
1. 2 requests with same CorrelationID will happen only in the case of invoker or executor MQTT connection drops, causing duplicates because of MQTT QoS1 (at-least-once) semantics. 
1. In this case, we should always de-dup from the cache, irrespective of whether the method is idempotent or not. 
    - Note that in case of pure idempotent methods, it is okay to not de-dup, but there is no reason to not de-dup either. The response for an idempotent request may be removed from the cache earlier if the cost-weighted benefit is too low and the cache is under size pressure. 
    - So we will always de-dup these requests from the cache on the Executor side. 
    - On the invoker side as well, there will be de-duping based on correlation ID (the 1st response will be sent to the app, the 2nd response will be dropped, as its Correlation ID has already been handled). 
1. The cache duration here is >= invocation timeout duration.
1. The cache key is CorrelationID + InvokerClientID. This usage of the cache is necessary for the correctness of the RPC protocol. So this should be considered a P0. 

### 2.	Caching for reuse of response with same request with different CorrelationID, i.e. _**equivalent**_ request
1. If there are 2 identical invocation requests, then we can avoid unnecessary executions by caching the response and returning it. BUT, this has 2 complications – (1) how to identify identical invocations and (2) behavior may be different based on whether the method is idempotent or not. 
2. Identical invocations could be identified by comparing the invoked method and request payload. An idempotent method with identical input parameters should be considered an identical invocation. (details of how, are implementation specific) 
3. For idempotent methods: we can cache, for a configurable period of time and return the response of an equivalent request from the cache. The response is cached until the response ttl defined by the server.
4. For non-idempotent methods: theoretically we cannot cache, as each execution can result in a different outcome. 
    - Note: It is possible that caching can be used in some scenarios for “debouncing” (say the same client calls “ExecuteSqlScript” 100 times in 1 sec, then the app can choose to execute only once). Of course, these parameters need to be set by the application, as the cache or RPC layer cannot decide how to handle this. However, this should be considered an advanced use-case which we will re-visit at a later time. 
5.	For non-idempotent methods: the handling in multiple executors becomes interesting – the requests to the executor need to be serialized. So we need to do consistent sharding, either driven by the broker via shared subs, or driven by the executor via specific topics. That way the same executor will handle execution for the “same” shard of request. 
6.	Here the cache key is the request itself, and cache duration is configured by the App. 
This usage of caching is good-to-have for improved behavior of the executor, though not strictly required for the correctness of the RPC layer. So this can be considered a P1. 

## Cache behavior for non-idempotent methods

Non-idempotent methods cannot be called more than once for _same_ request. De-duplication of _same_ request or _repeated_ request (same Correlation ID) must happen via cache.

Non-idempotent methods MUST not have responses with a TTL, because non-idempotent commands are not cached for reuse. De-duplication of a _duplicate_ request (same Correlation ID) MUST happen until the request times out.

If an executor gets two _same_ requests for the method, then it should always answer with the _same_ response, and MUST do so for each request. The cache MUST start tracking the response from the time the first request is received, and at least up until when the request timeout elapses. When a response is delivered, the cache SHOULD still track the response up until the original request timeout , because more _duplicated_ requests may still be in flight, e.g., if the invoker produced multiple requests because it did not receive a PUBACK.
After the timeout of the request elapses, the cache MAY no longer track the response, because the need for de-duplication of the request is fulfilled when the timeout of the request elapses. An unacknowledged PUBLISH packet expiring at the broker is dropped by the broker. An unacknowledged PUBLISH expiring at the RPC layer returns a "timeout" error response code.

Please note that when an invoker invokes a method with a request timeout T, then the deadline to track the request is strictly equal to the current time when the request is observed on the executor side plus T. Though, because of the network travel time of messages, the executor should track the request for a longer interval to account for network delays. Network delays are typically << 1 sec.

With non-idempotent methods, the cache MUST never expire entries for one specific request before the timeout of the request elapses.

Non-idempotent methods that receive an _equivalent_ request (different correlation ID) must be executed as separate requests and MUST not be returned from the cache.

Non-idempotent methods are cached only for de-duplication, never for reuse.

## Cache behavior for idempotent methods

Idempotent methods are safe to invoke multiple times even for the _same_ or _equivalent_ request, although it is inefficient.

Idempotent methods invoked with same parameters can simply be treated as non-idempotent methods, with a TTL set to infinite, unless otherwise indicated by a server.

Idempotent methods SHALL have responses with a TTL. De-duplication of _duplicate_ request may happen until the maximum(request timeout, TTL of the response). Reuse of response from the cache for an _equivalent_ request may happen only until the TTL of the response elapses.

With idempotent methods, the cache can expire entries at any time and the only penalty would be efficiency, because the server method could invoked more than once for no gain.

Idempotent methods are cached for both de-duplication and reuse.

## In summary:

1. Caching for de-duplication - for _**duplicated**_ idempotent and non-idempotent requests.
    1. Idempotent requests MAY be cached until max (request timeout, response ttl). _May be removed earlier if the cost-weighted benefit is too low and the cache is under size pressure._
    1. Non-idempotent requests MUST be cached until request timeout.
1. Caching for reuse - for _**equivalent**_ idempotent requests.
    1. Idempotent requests MAY be cached until response ttl. _May be removed earlier if the cost-weighted benefit is too low and the cache is under size pressure._
    1. Non-idempotent requests MUST never be cached.

### For RPC correctness:
- A non-duplicated, non-equivalent request **MUST** not be retrieved from  cache.
- An equivalent request for a non-cacheable command **MUST** not be retrieved from cache. This covers both of the below cases:
    - A non-idempotent command
    - An idempotent command with cacheable duration set to 0.
- An equivalent request for a cacheable (idempotent) command whose response TTL has elapsed **MUST** not be retrieved from cache.
- A duplicate request for a non-cacheable (non-idempotent) command within the request expiration time **MUST** be retrieved from the cache.

### Additionally:
- An equivalent request for a cacheable (idempotent) command whose response TTL has not elapsed **MAY** be retrieved from the cache. _The entry may be removed from the cache earlier if the cost-weighted benefit is too low and the cache is under size pressure._
- A duplicate request for a cacheable (idempotent) command whose response TTL has not elapsed or it is within the request expiration time **MAY** be retrieved from the cache. _The entry may be removed from the cache earlier if the cost-weighted benefit is too low and the cache is under size pressure._
- A duplicate request for an idempotent command or non-idempotent command outside the request expiration **MAY** be retrieved from the cache. Ideally, the expired request would either get dropped by the broker, or it would return a "timeout" error response code. However, for the purpose of discussion about the cache, the cache can be used for de-duplication.

## Cache behavior for multiple invokers and multiple executors

Multiple invokers may invoke the same method. When cache is populated as a result of an invocation by one specific invoker, another invoker can use the same response if the request is a cacheable request, i.e. it is idempotent and the response TTL did not elapse and original invoker did not invoke one specific executor, but rather addressed the service.

If an invoker invokes one specific executor rather than the service, then the cache entry should be specific to the original invoker/executor pair only to avoid leaking potentially private data.

There could be multiple executors behind one RPC service. If they are hosted in different processes, then the cache will be common only if the cache is distributed across different processes. This is possible using a distributed cache or using DSS to back the cache implementation. One simpler implementation would avoid using a distributed cache. Implementation would still be correct as far as de-duplication is concerned because it is the responsibility of the broker to re-play the same request to the same invoker (broker accomplish this using stable hashing on shared subscriptions, and therefore the RPC stack would not have to deal with this concern).

As a result, different requests, e.g., _equivalent_ requests, may not enjoy the benefit of caching even when responses have a TTL > 0 in implementation when there are multiple executors and cache is not distributed. This is a fine way to start and we will re-consider at later time.

## Example: _EchoWithTag_

Given the following server method:

```csharp
// EchoWithTag produces a string that is the same string passed 
// in input with an appended tag in the for of ":tag". 
// The tag is the stringification o a monotonic integer 
// starting at 1, and the integer is increased at each invocation.
String EchoWithTag( String input );```
```

Let's assume this is the implementation:

```csharp
public class EchoWithTagServer
{
    private int _tag;
    public EchoWithTagServer() { _tag = 0; }
    public String EchoWithTag(String input)
    {

        return input + ":" + Interlocked.Increment(ref _tag).ToString();
    }
}
```

Invoking this method with:
```csharp 
...
var server = new EchoWithTagServer();
var answer = server.EchoWithTag("Hello!");
var answer2 = server.EchoWithTag("Hello!");
...
```

will yield ```"Hello!:1"``` and ```"Hello!:2"``` as responses. Please note that this requests are at least _equivalent_ : same method, same parameters. Also this method is not idempotent, but its answer may have a TTL. We will use this method for all subsequent examples ignoring the fact that we should not really look into parameters to assert requests are _same_...

### Invoke _EchoWithTag_ as a non-idempotent method

Let's assume an executor sets up the ```EchoWithTag``` method above as non-idempotent, with a **TTL of 0** for its responses, and invoker invokes methods with a **timeout of 5 seconds**. Let's also assume that we always use the input
`"Hello!"`.

Here below are the most important cases to handle correctly:

1. If an invoker invokes the method once, it will receive a response ```"Hello!:1"```, whether the invocation was for one specific executor or for the service in general. The server method will be executed once.
1. If an invoker invokes the method once but it is disconnected before receiving the PUBACK for the request and subsequently re-connects, then the MQTT client in the invoker will re-send the request. The executor SHOULD populate the cache upon receiving the first request with a placeholder for the response. When the executor receives both requests, if **the second request arrives within the timeout window of the first (5 secs)**, the executor SHOULD NOT call the server again but rather observe that the request is already in process. Executor MUST send PUBACK for requests in order and send two responses, one for each request. Both responses MUST be ```"Hello!:1"``` and server method MUST be invoked once only. Responses SHOULD be sent only if request completes within the timeout indicated by the invoker. Cache entry should be discarded after timeout indicated by invoker elapses, as all subsequent _duplicate_ requests will be dead on arrival.
1. If an invoker invokes the method once but it is disconnected before receiving the PUBACK for the request and subsequently re-connects, then the MQTT client in the invoker will re-send the request. The executor SHOULD populate the cache upon receiving the first request with a placeholder for the response. If the executor receives both requests, but **the second request arrives when the timeout window of the first request (5 secs) elapsed already**, then the executor SHOULD discard the second request. Executor MUST send PUBACK for requests in order and send only one response for the first request, if it completes within the timeout indicated by the invoker. Response MUST be ```"Hello!:1"``` and second request must timeout on the invoker side. Cache entry should be discarded after timeout indicated by invoker elapses, as all subsequent _duplicate_ requests will be dead on arrival.
1. If an invoker invokes the method once and then again with a different request (different CorrelationID) the executor SHOULD always invoke server method again. Responses should be ```"Hello!:1"``` and ```"Hello!:2"```.

### Invoke _EchoWithTag_ as an idempotent method

Let's assume an executor sets up the ```EchoWithTag``` method above as idempotent, with a **TTL of 1 hour** for its responses, and invoker invokes methods with a **timeout of 5 seconds**.

1. If an invoker invokes the method once it will receive a response ```"Hello!:1"```, whether the invocation was for one specific executor or for the service in general. the server method will be executed once.
1. If an invoker invokes the method once but it is disconnected before receiving the PUBACK for the request and subsequently re-connects, then the MQTT client in the invoker will re-send the request. The executor SHOULD populate the cache upon receiving the first request with a placeholder for the response. If the executor receives both requests, and **the second request arrives within the timeout window of the first (5 secs)**, the executor SHOULD NOT call the server again but rather observe that the request is already in process and it is a _duplicate_ request. Executor MUST send PUBACK for requests in order and send two responses, one for each request. Both responses MUST be ```"Hello!:1"``` and server method MUST be invoked once only. Responses SHOULD be sent only if request completes within the timeout indicated by the invoker. Cache entry SHOULD NOT be discarded after timeout indicated by invoker elapses, as the response is valid for 1 hour. Though, any _duplicate_ requests arriving after timeout expired should be treated as dead on arrival and should be discarded after sending PUBACK to broker, with invoker timing out by itself.
1. If an invoker invokes the method once but it is disconnected before receiving the PUBACK for the request and subsequently re-connects, then the MQTT client in the invoker will re-send the request. The executor SHOULD populate the cache upon receiving the first request with a placeholder for the response. If the executor receives both requests, but the **second request arrives when the timeout window of the first request (5 secs) elapsed already**, then the executor SHOULD discard the second request. Executor MUST send PUBACK for requests in order and send only one response for the first request, if it completes within the timeout indicated by the invoker. Response MUST be ```"Hello!:1"``` and second request must timeout on the invoker side. Cache entry SHOULD NOT be discarded after timeout indicated by invoker elapses, as the response is valid for 1 hour, with any _duplicate_ request treated as dead on arrival thereafter.
1. If an invoker invokes the method once and then again with a different request (different Correlation ID) immediately after the first request the executor SHOULD NOT invoke server method again if response TTL did not elapse. Responses should both be ```"Hello!:1"```.
1. If an invoker invokes the method once and then again with a different request (different Correlation ID) after the first request the executor SHOULD  invoke server method again if response TTL elapsed. Responses should both be ```"Hello!:1"``` and ```"Hello!:2"```.

## Summary of examples

Here are a few salient points:

1. Executors should always expect duplicate requests and use correlation ID to de-duplicate.
1. Executor should always send PUBACK for requests, even when request is not actionable.
1. Requests should be tracked by Correlation ID.
1. Requests for specific executors should be tracked for original invoker/executor pair.
1. Requests for non-idempotent methods must be tracked for de-duplication purposes.
1. Requests for idempotent methods must be tracked for de-duplication purposes and reused for efficiency.
1. If the target of a request is one specific executor, then the response must be cached only for that specific invoker/executor pair (or not cached at all, other than for de-duplication purpose, which must always happen).
1. If the target of the request is any executor, then the response should be cache for any other invoker that targets any executor (and for de-duplication purposes as well).

## Practical cache implementation considerations

Since cache is used for de-duplication, requests should be tracked even before a response is available.
Cache implementation can use a placeholder to assert that a request is in process, so that two _same_ request can use the same response.

Tracking requests should happen by correlation ID, which we assume to be universally unique, but that is practical for de-duplication purposes only, since lifetime of cache entries for de-duplication is confined to request timeout, plus a reasonable delta. De-duplication can guarantee a once-only delivery only if every Correlation ID is tracked forever, which is obviously impractical.
Therefore, it is reasonable to assume that duplicate _same_ requests outside of the original timeout of the first request would be treated as separate requests. This requires that a Correlation ID become inactive as a cache key without necessarily expiring the cache entry.

After a Correlation ID is considered expired, the cache entry should still survive for the TTL indicated by the server. This is required for efficiency for idempotent methods only. Response for non-idempotent methods should be cached only for de-duplication purposes for obvious reasons. After completing tracking a correlation ID for de-duplication purposes for a idempotent method, still it is required to compare parameters of method invocation to use cached entry, and keep track of TTL.

We also have a duty of tracking invokers/executor pairs where an invoker uses a specific executor (this is because of privacy reasons).
