CAS: Existence Caching in Intermediate Caches (user experience report)

I work for [Cruise](https://getcruise.com). I was talking to our Google Account Manager JP Guerra a while back about this issue and he thought it'd be useful to share our experience with upstream. I liked the idea, so here I am. 😁

We built an in-house RBE service. We diverged from the "ContentAddressableStorage" service API to support existence caching in intermediate caches. I wanted to share what we did and why we did it. We prefer to not diverge from the upstream API but we needed to in this case.

On our internal CAS we register an additional gRPC service called "CruiseContentAddressableStorage". It has a method that is the inverse of the "ContentAddressableStorage" service "FindMissingBlobs" method. Instead of finding blobs which do not exists, the "FindBlobs" method finds blobs which do exist, so that we can return metadata associated with each object. Specifically, we return a timestamp called "expires_at" which is the wall clock time of how long intermediate existence caches may record that an object exists (we never cache non-existence, because that'd cause inconsistency). This enables intermediate CAS (which proxy for another CAS) to cache existence.
```
service CruiseContentAddressableStorage {
rpc FindBlobs(FindBlobsRequest) returns (FindBlobsResponse) {}
}

message FindBlobsRequest {
string instance_name = 1;
repeated Digest blob_digests = 2;
}

message FindBlobsResponse {
repeated FoundBlobMetadata found_digest_metadata = 1;
}

message FoundBlobMetadata {
Digest digest = 1;
google.protobuf.Timestamp expires_at = 2;
}
```

We had thought of using gRPC metadata for the "expire_at" timestamps, but we have batches of around 15,000 digests (each one has its own timestamp) which would have been a challenge to pack into gRPC metadata (due to HTTP2 header size limits). So we registered the additional "CruiseContentAddressableStorage" service, and we dynamically fallback to doing no intermediate existence caching if the server returns the gRPC code "Unimplemented" (meaning the service or method doesn't exist). So we're still compatible with upstream with this fallback.

The underlying reason why we're doing existence caching in intermediate caches is because our underlying database Spanner cannot handle the required read rate, or write rate for updating atime (access time) used for expiration. Our CAS which talks to Spanner has a memory existence cache which also cannot scale high enough so we need to propagate the fact that blobs exist to cache levels that are closer to bazel. We also have to jitter atime to avoid bursts of writes on Spanner which necessitates that our "expire_at" times be different for every object to spread atime update load on Spanner over time.

I think the key idea is that the API is missing information needed to do existence caching in intermediate caches.

Read the existing ContentAddressableStorage API and its FindMissingBlobs method, then compare them with the proposed CruiseContentAddressableStorage and FindBlobs definitions in the report. Clarify whether upstream wants an API change and what compatibility behavior is required; done would require an agreed design or specification, which the issue does not yet define.

Written by the indexing model from the issue text.