[API Proposal]: Introduce new memory cache library

### Background and motivation

We have two available memory cache libraries in .NET that are popular and well known - `System.Runtime.Caching` and `Microsoft.Extensions.Memory.Cache`. As already described in [this issue](https://github.com/dotnet/runtime/issues/48567) there is a room for improvement in their public APIs. There are also efficiency problems that hit at high scale. Thus, our goal was to implement as efficient memory cache as possible for high concurrency and high traffic servers. During the process we've found a few additional opportunities to do slightly better than existing libraries.

- Our implementation is fully generic for both keys and values, offering greater convenience and potentially improving memory efficiency by avoiding unnecessary boxing and type conversions.
- Our implementation delivers noticeable performance improvements, with reduced latency and greater efficiency across operations.
- Both `System.Runtime.Caching` and `Microsoft.Extensions.Caching.Memory` use mechanisms that may involve background threads or timers for managing expiration. In contrast, our implementation maintains state directly within set and get methods, avoiding thread pool overhead. Since it doesn't implement `IDisposable`, there's also no risk of memory leaks from incorrect disposal, unlike `System.Runtime.Caching`, which allocates timers on construction.
- The API design can lead to inefficiencies by requiring heap-allocated objects, potentially increasing memory pressure at runtime.
- No metrics are emitted by default, which is important for monitoring in distributed systems.

RCache implementation is based on open source library [BitFaster](https://github.com/bitfaster/BitFaster.Caching).

---

Storing pair of (*this is the best situation for RCache since no boxing on key and value*).
The latency includes optional cost of maintaining telemetry state on RCache side.

| Cache library | Remove | TryGetMiss | TryGetHit | GetOrSet | GetOrSet Dynamic TTL | Set | SetDynamicTTL |
|------------------------------------ |--------------:|-----------:|----------:|---------:|---------------------:|----------:|--------------:|
| RCache | 6.5 ns | 10.0 ns | 11.4 ns | 14.7 ns | 15.6 ns | 28.9 ns | 32.2 ns |
| Microsoft.Extensions.Caching.Memory | 59.3 ns | 39.0 ns | 48.4 ns | 52.1 ns | 44.9 ns | 125.5 ns | 130.2 ns |
| System.Runtime.Caching | 59 ns | 54.8 ns | 107.0 ns | 175.8 ns | 239.7 ns | 1192.5 ns | 1216.1 ns |

---

Feature comparison table:

| Feature | RCache | Microsoft.Extensions.Caching.Memory | System.Runtime.Caching |
|--------------------------------|--------|------------------------------------:|-----------------------:|
| Time-based eviction | yes | yes | yes |
| Sliding time to evict | yes | yes | yes |
| Callbacks on eviction | no | yes | yes |
| Metrics | yes | no | no |
| Named caches | yes | no | no |
| Generics support | yes | no | no |
| Priority based eviction | yes** | yes | no |
| Runtime entry size calculation | no | yes | no |
| Dynamic Time To Evict | yes | yes | yes |
| Item update notification | no | yes | no |

** Algorithm we use has a notion of three priorities (hot, warm, cold) and respect them while rotating items. Though, we don't allow to define priorities by customer or have direct control over it.

### API Proposal

```csharp
namespace Microsoft.Extensions.Cache.Memory;

///
/// A synchronous in-memory object cache.
///
/// Type of keys stored in the cache.
/// Type of values stored in the cache.
public abstract class RCache : IEnumerable>
where TKey : notnull
{
///
/// Gets the name of the cache instance.
///
///
/// This name is used to identity this cache when publishing telemetry.
///
public abstract string Name { get; }

///
/// Gets the capacity of the cache, which represents the maximum number of items maintained by the cache at any one time.
///
public abstract int Capacity { get; }

///
/// Tries to get a value from the cache.
///
/// Key identifying the requested value.
/// Value associated with the key or when not found.
///
/// when the value was found, otherwise.
///
public abstract bool TryGet(TKey key, [MaybeNullWhen(false)] out TValue value);

///
/// Sets a value in the cache.
///
///
/// The value's time to expire is set to the global default value defined for this cache instance.
///
/// Key identifying the value.
/// Value to associate with the key.
public abstract void Set(TKey key, TValue value);

///
/// Sets a value in the cache.
///
///
/// After time to expire has passed, a value is not retrievable from the cache.
/// At the same time cache might keep the root for it for some time.
///
/// Key identifying the value.
/// Value to cache on the heap.
/// Amount of time the value is valid, after which it should be removed from the cache.
/// If is less than 1 millisecond.
public abstract void Set(TKey key, TValue value, TimeSpan timeToExpire);

///
/// Gets a value or sets it if doesn't exist.
///
///
/// The value's time to expire is set to the global default value defined for this cache instance.
///
/// Type of the state passed to the function.
/// Key identifying the value.
/// State passed to the factory function.
/// A function used to create a new value if the key is not found in the cache. It returns the value to be cached.
///
/// Data retrieved from the cache or created by the passed factory function.
///
public abstract TValue GetOrSet(TKey key, TState state, Func factory);

///
/// Gets a value or sets it if doesn't exist.
///
///
/// After time to expire has passed, a value is not retrievable from the cache.
/// At the same time cache might keep the root for it for some time.
///
/// The type of the state object passed to the factory function.
/// The key identifying the cached value.
/// An additional state object passed to the factory function.
///
/// A function used to create a new value if the key is not found in the cache. The function returns a tuple where the
/// first item is the value to cache, and the second item is a representing the duration for which
/// the value remains valid in the cache before expiring.
///
///
/// The value associated with the key, either retrieved from the cache or created by the factory function.
///
public abstract TValue GetOrSet(TKey key, TState state,
Func factory);

///
/// Gets a value or sets it if doesn't exist.
///
///
/// The value's time to expire is set to the global default value defined for this cache instance.
///
/// Key identifying the value.
/// A function used to create a new value if the key is not found in the cache. It returns the value to be cached.
///
/// Data retrieved from the cache or created by the passed factory function.
///
public abstract TValue GetOrSet(TKey key, Func factory);

///
/// Gets a value or sets it if doesn't exist.
///
///
/// After time to expire has passed, a value is not retrievable from the cache.
/// At the same time cache might keep the root for it for some time.
///
/// Key identifying the value.
///
/// A function used to create a new value if the key is not found in the cache. The function returns a tuple where the
/// first item is the value to cache, and the second item is a representing the duration for which
/// the value remains valid in the cache before expiring.
///
///
/// Data retrieved from the cache or created by the passed factory function.
///
public abstract TValue GetOrSet(TKey key, Func factory);

///
/// Gets the current number of items in the cache.
///
///
/// This method is inherently imprecise as threads may be asynchronously adding
/// or removing items. In addition, this method may be relatively costly, so avoid
/// calling it in hot paths.
///
public abstract int GetCount();

///
/// Attempts to remove the value that has the specified key.
///
/// Key identifying the value to remove.
///
/// if the value was removed, and if the key was not found.
///
public abstract bool Remove(TKey key);

///
/// Attempts to remove the specified key-value pair from the cache.
///
/// Key identifying the value to remove.
/// The value associated with the key to remove.
///
/// if the specified key-value pair was found and removed;
/// otherwise, .
///
///
/// This method checks both the key and the associated value for a match before removal.
/// If the specified key exists but is associated with a different value, the cache remains unchanged.
///
public abstract bool Remove(TKey key, TValue value);

///
/// Removes all expired entries from the cache.
///
///
/// Some implementations perform lazy cleanup of cache resources. This call is a hint to
/// ask the cache to try and synchronously do some cleanup.
///
public abstract void RemoveExpiredEntries();

///
/// Returns an enumerator that iterates through the items in the cache.
///
///
/// An enumerator for the cache.
///
///
/// This can be a slow API and is intended for use in debugging and diagnostics, avoid using in production scenarios.
///
/// The enumerator returned from the cache is safe to use concurrently with
/// reads and writes, however it does not represent a moment-in-time snapshot.
/// The contents exposed through the enumerator may contain modifications
/// made after was called.
///
public abstract IEnumerator> GetEnumerator();

///
/// Returns an enumerator that iterates through the items in the cache.
///
///
/// An enumerator for the cache.
///
///
/// This can be a slow API and is intended for use in debugging and diagnostics, avoid using in production scenarios.
///
/// The enumerator returned from the cache is safe to use concurrently with
/// reads and writes, however it does not represent a moment-in-time snapshot.
/// The contents exposed through the enumerator may contain modifications
/// made after was called.
///
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

///
/// Options for LRU (Least Recently Used) implementations of .
///
/// Type of keys stored in the cache.
public class RCacheLruOptions
where TKey : notnull
{
///
/// Gets or sets the maximum number of items that can be stored in the cache.
///
///
/// Defaults to 1024.
///
[Range(3, int.MaxValue - 1)]
public int Capacity { get; set; } = 1024;

///
/// Gets or sets the default time to evict individual items from the cache.
///
///
/// This value is used by methods which do not accept an explicit time to evict parameter.
/// If you don't want your items to be ever evicted due to time, set this value to .
///
///
/// Defaults to 5 minutes.
///
[TimeSpan(minMs: 1)]
public TimeSpan DefaultTimeToEvict { get; set; } = TimeSpan.FromMinutes(5);

///
/// Gets or sets the amount of time by which an items's eviction time is extended upon a cache hit.
///
///
/// This value is ignored when is .
///
///
/// Defaults to 5 minutes.
///
[TimeSpan(minMs: 1)]
public TimeSpan ExtendedTimeToEvictAfterHit { get; set; } = TimeSpan.FromMinutes(5);

///
/// Gets or sets a value indicating whether an item's time to evict should be extended upon a cache hit.
///
///
/// Defaults to .
///
public bool ExtendTimeToEvictAfterHit { get; set; }

///
/// Gets or sets the cache's level of concurrency.
///
///
/// Increase this value if you observe lock contention.
///
///
/// Defaults to .
///
[Range(1, int.MaxValue)]
public int ConcurrencyLevel { get; set; } = Environment.ProcessorCount;

///
/// Gets or sets the custom time provider used for timestamp generation in the cache.
///
///
/// If this value is , the cache will default to using
/// for timestamp generation to optimize performance. If a is set,
/// the cache will call the method.
/// The should primarily be used for testing purposes, where custom time manipulation is required.
///
///
/// Defaults to .
///
public TimeProvider? TimeProvider { get; set; }

///
/// Gets or sets the comparer used to evaluate keys.
///
///
/// Defaults to ,
/// except for string keys where the default is .
///
public IEqualityComparer KeyComparer { get; set; }
= typeof(TKey) == typeof(string) ? (IEqualityComparer)StringComparer.Ordinal : EqualityComparer.Default;

///
/// Gets or sets a value indicating how often cache metrics are refreshed.
///
///
/// Setting this value too low can lead to poor performance due to the overhead involved in
/// collecting and publish metrics.
///
///
/// Defaults to 30 seconds.
///
[TimeSpan(min: "00:00:05")]
public TimeSpan MetricPublicationInterval { get; set; } = TimeSpan.FromSeconds(30);

///
/// Gets or sets a value indicating whether metrics are published or not.
///
///
/// Defaults to .
///
public bool PublishMetrics { get; set; } = true;
}

///
/// Builder for creating instances.
///
/// Type of keys stored in the cache.
/// Type of values stored in the cache.
public class RCacheLruBuilder
where TKey : notnull
{
///
/// Initializes a new instance of the class.
///
/// Name of the cache, used in telemetry.
/// Thrown when the is null.
public RCacheLruBuilder(string name);

///
/// Sets the options for the cache.
///
/// Cache options.
/// The current instance of the .
/// Thrown when the is null.
public RCacheLruBuilder WithOptions(RCacheLruOptions options);

///
/// Sets the meter factory for the cache.
///
/// Meter factory for telemetry.
/// The current instance of the .
public RCacheLruBuilder WithMeterFactory(IMeterFactory? meterFactory);

///
/// Builds the instance with the specified configurations.
///
/// A ready-to-use instance.
/// Thrown when the validation of options fails.
/// Thrown when the meter factory is null but metrics publishing is enabled.
public RCache Build();
}

///
/// Extension methods for caching.
///
public static class RCacheExtensions
{
///
/// Adds an LRU (Least Recently Used) cache to the dependency injection container.
///
/// Type of keys stored in the cache.
/// Type of values stored in the cache.
/// Dependency injection container to add the cache to.
/// The value of.
/// When passed are .
public static IServiceCollection AddRCacheLru(this IServiceCollection services)
where TKey : notnull;

///
/// Adds a named LRU (Least Recently Used) cache to the dependency injection container.
///
/// Type of keys stored in the cache.
/// Type of values stored in the cache.
/// Dependency injection container to add the cache to.
/// Name of the cache, used in telemetry.
/// The value of.
/// When passed are .
/// When passed is or empty.
public static IServiceCollection AddRCacheLru(this IServiceCollection services, string name)
where TKey : notnull;

///
/// Adds an LRU (Least Recently Used) cache to the dependency injection container.
///
/// Type of keys stored in the cache.
/// Type of values stored in the cache.
/// Dependency injection container to add the cache to.
/// A function used to configure cache options.
/// The value of.
/// When passed or are .
public static IServiceCollection AddRCacheLru(this IServiceCollection services, Action> configure)
where TKey : notnull;

///
/// Adds an LRU (Least Recently Used) cache to the dependency injection container.
///
/// Type of keys stored in the cache.
/// Type of values stored in the cache.
/// Dependency injection container to add the cache to.
/// Configuration part that defines cache options.
/// The value of.
/// When passed or are .
public static IServiceCollection AddRCacheLru(this IServiceCollection services, IConfigurationSection section)
where TKey : notnull;

///
/// Adds a named LRU (Least Recently Used) cache to the dependency injection container.
///
/// Type of keys stored in the cache.
/// Type of values stored in the cache.
/// Dependency injection container to add the cache to.
/// Name of the cache, used in telemetry.
/// Configuration part that defines cache options.
/// The value of.
/// When passed or are .
/// When passed is or empty.
public static IServiceCollection AddRCacheLru(this IServiceCollection services, string name,
IConfigurationSection section)
where TKey : notnull;

///
/// Adds a named LRU (Least Recently Used) cache to the dependency injection container.
///
/// Type of keys stored in the cache.
/// Type of values stored in the cache.
/// Dependency injection container to add the cache to.
/// Name of the cache, used in telemetry.
/// A function used to configure cache options.
/// The value of.
/// When passed or are .
/// When passed is or empty.
public static IServiceCollection AddRCacheLru(this IServiceCollection services, string name,
Action> configure)
where TKey : notnull;
}

///
/// Metrics published by .
///
public static class RCacheMetrics
{
///
/// Name of the to listen to is the name of the cache.
///
///
/// RCache with name "test" will publish metrics with tag "cache-name" equal to "test".
///
public const string LruCacheMeterName = "Microsoft.Extensions.Cache.Memory";

///
/// Gets the total number of cache queries that were successful.
///
///
/// Metric is exposed as with value being .
///
public const string Hits = "rcache.hits";

///
/// Gets the total number of unsuccessful cache queries.
///
///
/// Metric is exposed as with value being .
///
public const string Misses = "rcache.misses";

///
/// Gets the total number of expired values.
///
///
/// Metric is exposed as with value being .
/// Expired values are one removed from cache because they were too old.
///
public const string Expirations = "rcache.expirations";

///
/// Gets the total number of values added to cache.
///
///
/// This value refers to total calls to set method, and does not include updates.
/// Metric is exposed as with value being .
///
public const string Adds = "rcache.adds";

///
/// Gets the total number of cache removals.
///
///
/// This value refers to total calls to remove method, and does not include evictions.
/// If you are interested in metric of total values being removed from the cache, add and .
/// Metric is exposed as with value being .
///
public const string Removals = "rcache.removals";

///
/// Gets the total number of evicted values.
///
///
/// Metric is exposed as with value being .
/// Evicted values are those removed based on the implementation's eviction policy and not time expiration or intentional removal.
///
public const string Evictions = "rcache.evictions";

///
/// Gets the total number of updated values.
///
///
/// Metric is exposed as with value being .
///
public const string Updates = "rcache.updates";

///
/// Gets the total number of values in the cache over time.
///
///
/// Metric is exposed as with value being .
///
public const string Count = "rcache.entries";

///
/// Gets the gauge of elements compacted in the cache.
///
///
/// Metric is exposed as with value being .
///
public const string Compacted = "rcache.compacted_entries";
}
```

### API Usage

**Add default cache to DI.**

```csharp
IServiceCollection services;

services.AddRCacheLru();

services.AddRCacheLru("different", options => options.PublishMetrics = false);
```

**Get default cache from DI.**

```csharp
namespace Example;

using Microsoft.Extensions.Cache;

public class UserService
{
private readonly RCache _users;

public UserService(RCache users)
{ ^^^^^^^^^^^^^^^^^^^^^^^^
_users = users
}
}
```

**Create cache using builder.**

```csharp
namespace Example;

using System.Diagnostics.Metrics;
using Microsoft.Extensions.Cache;

public class UserService
{
private readonly RCache _users;

public UserService(IMeterFactory meterFactory)
{
_users = new RCacheLruBuilder("my-cache-name")
.WithMeterFactory(meterFactory)
.Build();
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
}
}
```

### Alternative Designs

**Callbacks and notifications**
We could introduce a feature from `Microsoft.Extensions.Caching.Memory` that allows to track if value was changed or implement eviction callbacks. Instead of storing a callback with each entry or some change tokens we could use System.Threading.Channels library. Through exposed ChannelReader, consumer could react on events like eviction, mutation and so on. I expect this design to be more memory/cpu efficient than existing one.

**Size check**
We could implement item size limit through interface implemented on stored type by library client.

```csharp
public interface ISizer
{
int GetSizeInBytes();
}
```

This design would allow us to implement size check without boxing TValue or introducing CPU branches on hot-path.

**Asynchronous interface**

We wanted to be explicit that everything in RCache should be sync. This approach allows us not to go into distributed systems problems, since async caches requires much richer semantics. __We are going to propose another interface in the future that covers asynchronous caches scenarios and more.__

### Risks

**Another cache**
This is yet another memory cache implementation which may confuse .NET community. We should be clear in framing the purpose of this interface, and make sure design is extendable enough so we don't need to repeat the same process in the future.

**Layering**
Is dotnet/extensions the right place for this code? For me it looks like a general purpose data structure that should be available for the whole stack. Should we introduce it to runtime repository?

**Deferred removal**
Cache item removal is deferred which can keep alive objects for longer than they need to be.