[API Proposal]: Introduce new memory cache library

[rafal-mz]

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 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.

---

Storing pair of <int, int> (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

namespace Microsoft.Extensions.Cache.Memory;

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

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

    /// <summary>
    /// Tries to get a value from the cache.
    /// </summary>
    /// <param name="key">Key identifying the requested value.</param>
    /// <param name="value">Value associated with the key or <see langword="null"/> when not found.</param>
    /// <returns>
    /// <see langword="true"/> when the value was found, <see langword="false"/> otherwise.
    /// </returns>
    public abstract bool TryGet(TKey key, [MaybeNullWhen(false)] out TValue value);

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

    /// <summary>
    /// Sets a value in the cache.
    /// </summary>
    /// <remarks>
    /// 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.
    /// </remarks>
    /// <param name="key">Key identifying the value.</param>
    /// <param name="value">Value to cache on the heap.</param>
    /// <param name="timeToExpire">Amount of time the value is valid, after which it should be removed from the cache.</param>
    /// <exception cref="ArgumentOutOfRangeException">If <paramref name="timeToExpire"/> is less than 1 millisecond.</exception>
    public abstract void Set(TKey key, TValue value, TimeSpan timeToExpire);

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

    /// <summary>
    /// Gets a value or sets it if doesn't exist.
    /// </summary>
    /// <remarks>
    /// 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.
    /// </remarks>
    /// <typeparam name="TState">The type of the state object passed to the factory function.</typeparam>
    /// <param name="key">The key identifying the cached value.</param>
    /// <param name="state">An additional state object passed to the factory function.</param>
    /// <param name="factory">
    /// 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 <see cref="TimeSpan"/> representing the duration for which 
    /// the value remains valid in the cache before expiring.    
    /// </param>
    /// <returns>
    /// The value associated with the key, either retrieved from the cache or created by the factory function.
    /// </returns>
    public abstract TValue GetOrSet<TState>(TKey key, TState state,
        Func<TKey, TState, (TValue value, TimeSpan timeToExpire)> factory);

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

    /// <summary>
    /// Gets a value or sets it if doesn't exist.
    /// </summary>
    /// <remarks>
    /// 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.
    /// </remarks>
    /// <param name="key">Key identifying the value.</param>
    /// <param name="factory">
    /// 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 <see cref="TimeSpan"/> representing the duration for which 
    /// the value remains valid in the cache before expiring.
    /// </param>
    /// <returns>
    /// Data retrieved from the cache or created by the passed factory function.
    /// </returns>
    public abstract TValue GetOrSet(TKey key, Func<TKey, (TValue value, TimeSpan timeToExpire)> factory);

    /// <summary>
    /// Gets the current number of items in the cache.
    /// </summary>
    /// <returns>
    /// 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.
    /// </returns>
    public abstract int GetCount();

    /// <summary>
    /// Attempts to remove the value that has the specified key.
    /// </summary>
    /// <param name="key">Key identifying the value to remove.</param>
    /// <returns>
    /// <see langword="true"/> if the value was removed, and <see langword="false"/> if the key was not found.
    /// </returns>
    public abstract bool Remove(TKey key);

    /// <summary>
    /// Attempts to remove the specified key-value pair from the cache.
    /// </summary>
    /// <param name="key">Key identifying the value to remove.</param>
    /// <param name="value">The value associated with the key to remove.</param>
    /// <returns>
    /// <see langword="true"/> if the specified key-value pair was found and removed; 
    /// otherwise, <see langword="false"/>.
    /// </returns>
    /// <remarks>
    /// 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.
    /// </remarks>
    public abstract bool Remove(TKey key, TValue value);

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

    /// <summary>
    /// Returns an enumerator that iterates through the items in the cache.
    /// </summary>
    /// <returns>
    /// An enumerator for the cache.
    /// </returns>
    /// <remarks>
    /// 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 <see cref="GetEnumerator"/> was called.
    /// </remarks>
    public abstract IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator();

    /// <summary>
    /// Returns an enumerator that iterates through the items in the cache.
    /// </summary>
    /// <returns>
    /// An enumerator for the cache.
    /// </returns>
    /// <remarks>
    /// 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 <see cref="GetEnumerator"/> was called.
    /// </remarks>
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

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

    /// <summary>
    /// Gets or sets the default time to evict individual items from the cache.
    /// </summary>
    /// <remarks>
    /// 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 <see cref="TimeSpan.MaxValue"/>.
    /// </remarks>
    /// <value>
    /// Defaults to 5 minutes.
    /// </value>
    [TimeSpan(minMs: 1)]
    public TimeSpan DefaultTimeToEvict { get; set; } = TimeSpan.FromMinutes(5);

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

    /// <summary>
    /// Gets or sets a value indicating whether an item's time to evict should be extended upon a cache hit.
    /// </summary>
    /// <value>
    /// Defaults to <see langword="false"/>.
    /// </value>
    public bool ExtendTimeToEvictAfterHit { get; set; }

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

    /// <summary>
    /// Gets or sets the custom time provider used for timestamp generation in the cache.
    /// </summary>
    /// <remarks>
    /// If this value is <see langword="null"/>, the cache will default to using <see cref="Environment.TickCount64"/>
    /// for timestamp generation to optimize performance. If a <see cref="TimeProvider"/> is set, 
    /// the cache will call the <see cref="TimeProvider.GetTimestamp"/> method.
    /// The <see cref="TimeProvider"/> should primarily be used for testing purposes, where custom time manipulation is required.
    /// </remarks>
    /// <value>
    /// Defaults to <see langword="null"/>.
    /// </value>
    public TimeProvider? TimeProvider { get; set; }

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

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

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

/// <summary>
/// Builder for creating <see cref="RCache{TKey, TValue}"/> instances.
/// </summary>
/// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
/// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
public class RCacheLruBuilder<TKey, TValue>
    where TKey : notnull
{
    /// <summary>
    /// Initializes a new instance of the <see cref="RCacheLruBuilder{TKey,TValue}"/> class.
    /// </summary>
    /// <param name="name">Name of the cache, used in telemetry.</param>
    /// <exception cref="ArgumentNullException">Thrown when the <paramref name="name"/> is null.</exception>
    public RCacheLruBuilder(string name);

    /// <summary>
    /// Sets the options for the cache.
    /// </summary>
    /// <param name="options">Cache options.</param>
    /// <returns>The current instance of the <see cref="RCacheLruBuilder{TKey,TValue}"/>.</returns>
    /// <exception cref="ArgumentNullException">Thrown when the <paramref name="options"/> is null.</exception>
    public RCacheLruBuilder<TKey, TValue> WithOptions(RCacheLruOptions<TKey> options);

    /// <summary>
    /// Sets the meter factory for the cache.
    /// </summary>
    /// <param name="meterFactory">Meter factory for telemetry.</param>
    /// <returns>The current instance of the <see cref="RCacheLruBuilder{TKey,TValue}"/>.</returns>
    public RCacheLruBuilder<TKey, TValue> WithMeterFactory(IMeterFactory? meterFactory);

    /// <summary>
    /// Builds the <see cref="RCache{TKey, TValue}"/> instance with the specified configurations.
    /// </summary>
    /// <returns>A ready-to-use <see cref="RCache{TKey, TValue}"/> instance.</returns>
    /// <exception cref="OptionsValidationException">Thrown when the validation of options fails.</exception>
    /// <exception cref="InvalidOperationException">Thrown when the meter factory is null but metrics publishing is enabled.</exception>
    public RCache<TKey, TValue> Build();
}

/// <summary>
/// Extension methods for caching.
/// </summary>
public static class RCacheExtensions
{
    /// <summary>
    /// Adds an LRU (Least Recently Used) cache to the dependency injection container.
    /// </summary>
    /// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
    /// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
    /// <param name="services">Dependency injection container to add the cache to.</param>
    /// <returns>The value of<paramref name="services"/>.</returns>
    /// <exception cref="ArgumentNullException">When passed <paramref name="services"/> are <see langword="null"/>.</exception>
    public static IServiceCollection AddRCacheLru<TKey, TValue>(this IServiceCollection services)
        where TKey : notnull;

    /// <summary>
    /// Adds a named LRU (Least Recently Used) cache to the dependency injection container.
    /// </summary>
    /// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
    /// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
    /// <param name="services">Dependency injection container to add the cache to.</param>
    /// <param name="name">Name of the cache, used in telemetry.</param>
    /// <returns>The value of<paramref name="services"/>.</returns>
    /// <exception cref="ArgumentNullException">When passed <paramref name="services"/> are <see langword="null"/>.</exception>
    /// <exception cref="ArgumentException">When passed <paramref name="name"/> is <see langword="null"/> or empty.</exception>
    public static IServiceCollection AddRCacheLru<TKey, TValue>(this IServiceCollection services, string name)
        where TKey : notnull;

    /// <summary>
    /// Adds an LRU (Least Recently Used) cache to the dependency injection container.
    /// </summary>
    /// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
    /// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
    /// <param name="services">Dependency injection container to add the cache to.</param>
    /// <param name="configure">A function used to configure cache options.</param>
    /// <returns>The value of<paramref name="services"/>.</returns>
    /// <exception cref="ArgumentNullException">When passed <paramref name="services"/> or <paramref name="configure"/> are <see langword="null"/>.</exception>
    public static IServiceCollection AddRCacheLru<TKey, TValue>(this IServiceCollection services, Action<RCacheLruOptions<TKey>> configure)
        where TKey : notnull;

    /// <summary>
    /// Adds an LRU (Least Recently Used) cache to the dependency injection container.
    /// </summary>
    /// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
    /// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
    /// <param name="services">Dependency injection container to add the cache to.</param>
    /// <param name="section">Configuration part that defines cache options.</param>
    /// <returns>The value of<paramref name="services"/>.</returns>
    /// <exception cref="ArgumentNullException">When passed <paramref name="services"/> or <paramref name="section"/> are <see langword="null"/>.</exception>
    public static IServiceCollection AddRCacheLru<TKey, TValue>(this IServiceCollection services, IConfigurationSection section)
        where TKey : notnull;

    /// <summary>
    /// Adds a named LRU (Least Recently Used) cache to the dependency injection container.
    /// </summary>
    /// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
    /// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
    /// <param name="services">Dependency injection container to add the cache to.</param>
    /// <param name="name">Name of the cache, used in telemetry.</param>
    /// <param name="section">Configuration part that defines cache options.</param>
    /// <returns>The value of<paramref name="services"/>.</returns>
    /// <exception cref="ArgumentNullException">When passed <paramref name="services"/> or <paramref name="section"/> are <see langword="null"/>.</exception>
    /// <exception cref="ArgumentException">When passed <paramref name="name"/> is <see langword="null"/> or empty.</exception>
    public static IServiceCollection AddRCacheLru<TKey, TValue>(this IServiceCollection services, string name,
        IConfigurationSection section)
        where TKey : notnull;

    /// <summary>
    /// Adds a named LRU (Least Recently Used) cache to the dependency injection container.
    /// </summary>
    /// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
    /// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
    /// <param name="services">Dependency injection container to add the cache to.</param>
    /// <param name="name">Name of the cache, used in telemetry.</param>
    /// <param name="configure">A function used to configure cache options.</param>
    /// <returns>The value of<paramref name="services"/>.</returns>
    /// <exception cref="ArgumentNullException">When passed <paramref name="services"/> or <paramref name="configure"/> are <see langword="null"/>.</exception>
    /// <exception cref="ArgumentException">When passed <paramref name="name"/> is <see langword="null"/> or empty.</exception>
    public static IServiceCollection AddRCacheLru<TKey, TValue>(this IServiceCollection services, string name,
        Action<RCacheLruOptions<TKey>> configure)
        where TKey : notnull;
}

/// <summary>
/// Metrics published by <see cref="RCache{TKey, TValue}"/>.
/// </summary>
public static class RCacheMetrics
{
    /// <summary>
    /// Name of the <see cref="Meter"/> to listen to is the name of the cache.
    /// </summary>
    /// <example>
    /// RCache with name "test" will publish metrics with tag "cache-name" equal to "test".
    /// </example>
    public const string LruCacheMeterName = "Microsoft.Extensions.Cache.Memory";

    /// <summary>
    /// Gets the total number of cache queries that were successful.
    /// </summary>
    /// <remarks>
    /// Metric is exposed as <see cref="ObservableCounter{T}"/> with value being <see cref="long"/>.
    /// </remarks>
    public const string Hits = "rcache.hits";

    /// <summary>
    /// Gets the total number of unsuccessful cache queries.
    /// </summary>
    /// <remarks>
    /// Metric is exposed as <see cref="ObservableCounter{T}"/> with value being <see cref="long"/>.
    /// </remarks>
    public const string Misses = "rcache.misses";

    /// <summary>
    /// Gets the total number of expired values.
    /// </summary>
    /// <remarks>
    /// Metric is exposed as <see cref="ObservableCounter{T}"/> with value being <see cref="long"/>.
    /// Expired values are one removed from cache because they were too old.
    /// </remarks>
    public const string Expirations = "rcache.expirations";

    /// <summary>
    /// Gets the total number of values added to cache.
    /// </summary>
    /// <remarks>
    /// This value refers to total calls to set method, and does not include updates.
    /// Metric is exposed as <see cref="ObservableCounter{T}"/> with value being <see cref="long"/>.
    /// </remarks>
    public const string Adds = "rcache.adds";

    /// <summary>
    /// Gets the total number of cache removals.
    /// </summary>
    /// <remarks>
    /// 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 <see cref="Evictions"/> and <see cref="Expirations"/>.
    /// Metric is exposed as <see cref="ObservableCounter{T}"/> with value being <see cref="long"/>.
    /// </remarks>
    public const string Removals = "rcache.removals";

    /// <summary>
    /// Gets the total number of evicted values.
    /// </summary>
    /// <remarks>
    /// Metric is exposed as <see cref="ObservableCounter{T}"/> with value being <see cref="long"/>.
    /// Evicted values are those removed based on the implementation's eviction policy and not time expiration or intentional removal.
    /// </remarks>
    public const string Evictions = "rcache.evictions";

    /// <summary>
    /// Gets the total number of updated values.
    /// </summary>
    /// <remarks>
    /// Metric is exposed as <see cref="ObservableCounter{T}"/> with value being <see cref="long"/>.
    /// </remarks>
    public const string Updates = "rcache.updates";

    /// <summary>
    /// Gets the total number of values in the cache over time.
    /// </summary>
    /// <remarks>
    /// Metric is exposed as <see cref="ObservableGauge{T}"/> with value being <see cref="long"/>.
    /// </remarks>
    public const string Count = "rcache.entries";

    /// <summary>
    /// Gets the gauge of elements compacted in the cache.
    /// </summary>
    /// <remarks>
    /// Metric is exposed as <see cref="Histogram{T}"/> with value being <see cref="long"/>.
    /// </remarks>
    public const string Compacted = "rcache.compacted_entries";
}

API Usage

Add default cache to DI.

IServiceCollection services;

services.AddRCacheLru<Guid, User>();

services.AddRCacheLru<Guid, User>("different", options => options.PublishMetrics = false);

Get default cache from DI.

namespace Example;

using Microsoft.Extensions.Cache;

public class UserService
{
    private readonly RCache<Guid, User> _users;

    public UserService(RCache<Guid, User> users)
    {                  ^^^^^^^^^^^^^^^^^^^^^^^^
        _users = users
    }
}

Create cache using builder.

namespace Example;

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

public class UserService
{
    private readonly RCache<Guid, User> _users;

    public UserService(IMeterFactory meterFactory)
    {
        _users = new RCacheLruBuilder<Guid, User>("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.

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.

[KalleOlaviNiemitalo]

Does it interoperate with TimeProvider?

[rafal-mz]

No, it doesn't. The whole purpose of this library is to speed up things. We would need to introduce time provider in the hot-path, which adds a virtual dispatch overhead. We can add 'FakeLruRCache' which would be no different from original implementation beside using TimeProvider. That would allow to test algorithm alone.

update

Actually, we could add TimeProvider in options as well, and until it would be overriden manually we could ignore it. I think it would solve the perf concern.

[amoerie]

What is the thread safety model here of the valueFactory? I typically wrap MemoryCache to ensure that the value factory is only called once in case of a cache miss. This always seemed self evident to me, since you wouldn't be caching in the first place if the valueFactory was cheap.

And if there is a locking mechanism, is it global or is it dependent on the key, like in ConcurrentDictionary?

[rafal-mz]

What is the thread safety model here of the valueFactory?

We are not preventing stampedes atm, so there is a chance that factory is called more than once.
Our model is basically the same what concurrent dictionary GetOrSet is doing. The solutions I see:

• Lazy{T},
• Using accepting TState GetOrSet overload and implement locking in there
• Add one more overload for RCache like GetOrSetLazy (?) that encapsulates Lazy approache in the cache itself.
• Extension method over RCache that is doing one of the mentioned above and comes from library.
• Explicitly add different cache implementation like 'LruAtomicWrites'.

If there is something I am missing let me know.

And if there is a locking mechanism, is it global or is it dependent on the key, like in ConcurrentDictionary?

RCache is wrapping over concurrent dictionary and it has no global locks.

[Richard004]

Nice. I like it. If the Lazy usecase for expensive valueFactories is nicely documented and tested (single execution guraranteed), then it does not need extra API support I believe.

What I do VERY often is Lazy<Task<TValue>>. So that concurrent requests await the same long running task. Please take this into account in examples, tests and documentation. 🙏

[Richard004]

Please consider support for "keyed service dependency injection".
[FromKeyedServices("usersCache")]
[FromKeyedServices("projectsCache")]
Typically I would configure expiration times on the level of the keyed instance of cache for all items in the once cache.
But maybe your idea about naming these and obtaining from factory is a better consideration.

[rafal-mz]

The library was originally developed before key service support was released, so it comes with:

public interface IRCacheProvider
{
  public RCache<TKey, TValue> Get<TKey, TValue>(string name);
}

and getting it by name from DI:

namespace Example;

using Microsoft.Extensions.Cache;

public class UserService
{
    private readonly RCache<Guid, User> _users;

    public UserService(IRCacheProvider caches)
    {
        _users = caches.Get<Guid, User>("my-cache-name");
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    }
}

I didn't include it in the proposal because it will be changed towards keyd services.

[to11mtm]

@rafal-mz Is RCache in a repo somewhere to peek at? I've used and even customized Bitfaster in the past so curious to see what changes were made in this case.

[rafal-mz]

RCache is not yet public. I will create a PR and link here as soon as it is possible.

[alastairtree]

Interesting proposal. Thanks for asking the community for feedback. I am sure lots of us value effort being put into the caching bits of the framework.

For me the Lazy ("cache stampede") factory evaluation requirement is pretty fundamental. Personally I struggle to find use cases that warrant a cache without lazy factory. Either not needing a lazy factory shows you don't actually need a cache at all (aka premature optimisation), or you need a cache such that it must have a lazy factory to not overwhelm your system. My experience says it should be lazy factory by default, and lazy factory is what people expect when using a cache for the first time. But I totally accept I'm biased as the author of a library that does just that!
I would like to hear from use cases that need a cache without lazy factory behaviour.

And a couple of questions:

• Can you explain the name RCache? What does it stand for? Doesn't seem intuitive to me.
• I understand the need to add a new cache API for higher performance caching but why not just fix/expand the existing Microsoft libraries? I'm sure there is good reason but it needs setting out in writing because a framework with 3 official cache libraries is not a great experience either.
• What is the difference between the proposal and the existing open source Bitfaster library? Could that be improved instead? Why not just support and direct people to existing existing open source community work if they need the highest performance cache?

[rafal-mz]

Thanks for your feedback. I really appreciate it.

Either not needing a lazy factory shows you don't actually need a cache at all (aka premature optimisation).

I would not go that far. Cache can be used as general purpose data structure that keep memory constrained through eviction policy and capacity limit. I've seen (written few myself :-)) far too many concurrent dictionaries called 'cache' that were accumulating memory to an infinite. RCache is just a concurrent dictionary wrapper that adds efficient eviction policy, so I would not limit the use cases to 'costly to create'. Sometimes it may be 'costly to keep forever'. Generally, the cost of creation matter less the longer entry TTL.

So far I've had an opinion that fast and simple is better than safe and slow. Now I am not sure. Need to think it through.

Can you explain the name RCache? What does it stand for? Doesn't seem intuitive to me.

We just had to have a different name than existing MemoryCache. RCache was developed in a project that has a name starting with 'R'.

I understand the need to add a new cache API for higher performance caching but why not just fix/expand the existing Microsoft libraries?

.NET team has long lasting culture of keeping strict backward compatibility guarantees. That's why expanding is hard when original implementations are not abstract classes. Microsoft.Extensions.Caching.Memory is getting better with every version but if the interface is locked it is only so much you can do.

Hopefully the interface we propose now can be extendable enough that in the future we can still improve the library and not introduce yet another API.

I'm sure there is good reason but it needs setting out in writing because a framework with 3 official cache libraries is not a great experience either.

We are aware of this problem that's why we call it out in risks. As mentioned above we cannot remove we can just add.

What is the difference between the proposal and the existing open source Bitfaster library? Could that be improved instead? Why not just support and direct people to existing existing open source community work if they need the highest performance cache?

RCache so far implements one algorithm out of many that are available in BitFaster. Some technical details in RCache are different compared to original. Author of BitFaster is a Microsoft employee and he was involved in the process.

Its worth to mention that there is also a layering problem. For instance, for a library to be used in runtime repo, it needs to be pulled there. This is also something we call out in risks.

[to11mtm]

Interesting proposal. Thanks for asking the community for feedback. I am sure lots of us value effort being put into the caching bits of the framework.

For me the Lazy ("cache stampede") factory evaluation requirement is pretty fundamental. Personally I struggle to find use cases that warrant a cache without lazy factory. Either not needing a lazy factory shows you don't actually need a cache at all (aka premature optimisation), or you need a cache such that it must have a lazy factory to not overwhelm your system. My experience says it should be lazy factory by default, and lazy factory is what people expect when using a cache for the first time. But I totally accept I'm biased as the author of a library that does just that! I would like to hear from use cases that need a cache without lazy factory behaviour.

This does bring up the point that, If there is a good way to add some additional abstractions to make Lazy evaluation simple and efficient, that would be great.

At the same time, I know of at least two larger OSS libs that may be able to benefit from a more raw base abstraction. (in one case I saw equivalent performance with lower memory usage compared to a very nice, hand crafted robin hood hash)

And a couple of questions:

* What is the difference between the proposal and the existing open source Bitfaster library? Could that be improved instead? Why not just support and direct people to existing existing open source community work if they need the highest performance cache?

If I had to guess, From my own experience hacking at it, Bitfaster is a very good caching library, however if you need a portion of the functionality it is better to specialize the implementation you can get even more from it. Kinda per above, on the average it's really good, but a purpose trimmed and tuned 'general but fixed use case' version is competitive with a 'hand chosen and written algo' cache.

[danmoseley]

From my own experience hacking at it, Bitfaster is a very good caching library, however if you need a portion of the functionality it is better to specialize the implementation you can get even more from it.

I am not familiar with it but was contributing to "Bitfaster" considered as an alternative? (Can we cc their owners here?)

[geeknoid]

@alastairtree I believe the value of a Lazy model is for a small cache with a high likelihood of concurrent accesses to the same state. But in a high traffic service which may have millions of entries in cache, the risk of wasted work due to concurrent evaluation of the factory method is low enough to simply not be a concern.

However, if it is a concern, then the cache can simply be configured to hold Lazy and then it will work as needed and prevent redundant calls to the factory method. I think that seems like a good place to be.

Now even if your cache sometimes experiences collisions and does redundant work as a result, it doesn't mean use of Lazy is warranted. It depends on the observed rate of collisions. Using a Lazy imparts a definite measurable cost to every use of the cache, whereas collisions only cost you when they occur. Thus a low collision rate may be cheaper than using Lazy.

[RobDeVoer]

I am excited about the introduction of a new memory cache and will follow its final specification if it proceeds. My experience with caching is not detailed enough to properly take part in the current level of conversation but I am happy to provide input and feedback as the design and first iteration progresses. Picking Bitfaster and extending/improving it sounds like the right plan. The current proposal appears to nearly match the existing Bitfaster or am I missing some key items?

[geeknoid]

@RobDeVoer It's very similar on the inside, but the API surface has been considerably simplified by hiding all the complications around how monomorphisation is achieved. And we have some ideas in the pipeline which may deliver additional raw performance to the code as well, but those are still experimental in nature.

[jodydonetti]

Hi all, here's my thoughts on this effort: I tried to condense all of them into a single answer, therefore sorry for it being quite long.

First of all, as others already said, thanks for discussing this in public to gather the community's opinions, including the ones by OSS maintainers like me, @alastairtree , @Turnerj and others. Really appreciated!

The most important thing I'd like to highlight is that when this will be finalized and released (I suppose in the .NET 9 timeframe), it will be important to clearly explain the positioning of it.
As already discussed on the previous issue caching is a tough beast with quite different use cases, the 2 primary ones being:

• low-level caching: basically a dictionary + some form of expiration, where the data is typically homogeneous (of the same type), typically privately owned by a single piece of code (eg: internally by libraries like EF), where the data is not shared app-wide, the type of the cache key should be anything (so no boxing, etc) and with a limited feature set. Also typically there will be a lot of different instances of it
• app-level caching: is still caching, but more "high level", where the data may be heterogeneous (of different types), the data is (or may be) shared between different pieces of code, the type of the key is typically string to allow for some higher level features like prefix/suffix addition for automatic scoping/less collisions and with a generally richer feature set, with typically few instances of it

Following this distinction I see this new RCache as part of the 1st category, and in this sense it feels good to me: the scope is quite narrow, no extra high-level features and the attention to micro-benchmarking is quite high. FWIW, good 👍

RCache

As pointed out by others the name is quite strange: I feel you in wanting to avoid some other uber general/all encompassing name and to avoid confusion with the other 2 existing _memory cache_s, so that this also feels "smaller/specialized/optimized" (again, 1st category from above). Having said that, naming it RCache just because the project where it originated started with an "R"... I don't know. Maybe something that communicate the low-level/no-frills nature of it like RawCache or similar?
Mind you, it's probably a minor thing, but still wanted to point that out.

• Both caches implementations are using background threads / timers. Our implementation maintains its state on set method, thus sparing some threadpool overhead over existing libraries. Our implementation is also friendlier to use, since it won't create a memory leak when not disposed (compared to System.Runtime.Caching which allocates timers on ctor).

Understood, but to do this it seems you are not cleaning up automatically: not having the code to look at I'm wondering if a SET call of key "foo" will also cleanup the expired entry for cache key "bar". If this is not the case you may run into memory remaining allocated by cache entries that ended up not being touched for a long time, so this is something to look out for.
A different approach may be to include timed background cleanup but as optional, with something like a bool flag in the general options or a TimeSpan? (null being the default, so no auto-cleanup). This way by default no leaks will be guaranteed but, if wanted, the ease of it can be obtained. I think the related code should not be that much.

** RCache is disposing entries on eviction and it can be used as eviction callback.

The feature is nice, but watch out for this (been there): I would enable automatic Dispose calls on eviction only as an opt-in feature (like bool EnableAutoDisposeOnEvict), since sometimes I saw usages in the wild where something is get from the cache and kept used only to become randomly disposed while still being used, for this exact behavior.

API Proposal
...

In general it looks quite good to me: I like that it is an abstract class with different factory methods so that currently there's only the LRU special case but I can imagine in the future there may be others (LFU, TLRU, PLRU, MRU, RR, FIFO, etc).

A couple of notes though:

• factory methods: why 2 of them instead of only one with name + options and options being nullable? If tomorrow a new param param3 would arrive, that may generate new permutations (name + param3, name + options + param3, etc). Nothing major, just wondering
• named caches: thinking about the DI support, I assume calling CreateLru<TKey, TValue>("foo") multiple times will return the same instance right? What about calling it twice with the same name but different options? Or with the same name but with different types? Is the name unique per-types-combination or global?
• options: RCacheLruOptions<TKey, TValue> why the generic typing here? Currently there does not seem to be nothing justying that, and as it is it would avoid sharing the same options with different instances. Maybe is it to make it future proof? Admittedly the cost here is nothing, so again just wondering
• ExtendedTimeToEvictAfterHit vs ExtendTimeToEvictAfterHit: I suggest to use a Is/Enable/etc prefix for bool options. In this case specifically the 2 options looks quite identical, so by using something like EnableExtendedTimeToEvictAfterHit it would make it clearer which one is which
• methods overloads: I see different overloads with/without optional params (like 4 different GetOrSets). I understand the need but down the line it may be quite daunting to maintain/evolve with this approach
• factory signature: you are using the specific params currently used, I can imagine to avoid bloat. While I feel that, I also can see a problem in the future when new factory params/return values may be needed, and then you would need to add more overloads and handle them all and the permutations will become quite a lot (been there...)
• the bool TryGet(out ...) signature will not be usable in case one day you'd like to add async support, so you'll eventually end up with 2 different methods with 2 very different signatures for the sync and async versions. I'd suggest to start immediately with a signature that will be able to support async. In my project I have used a simple MaybeValue<T> struct, kinda like a Nullable<T> but for both ref/value type (like a maybe/option monad). It works well, is not heavy on resources and is easily evolvable into the async territory

Another thing is that, as already said by others, the lack of cache stampede prevention is quite a big thing.
I can feel not wanting to go there, but at the same time it's something quite important and expected, and something that is already missing in the current MemoryCache (with the added "bonus" there that people usually think the GetOrCreate ext method will protect them, when instead it will not).

Because of this, if you decide not to implement it, I think it should be very clear to consumers that there's no protection there.

Also, now that I'm thinking about it: if no stampede prevention is provided, and no async support is provided (see later), why having a GetOrSet at all?

By not having it:

• it would make it clear that there's no stampede prevention
• it would avoid having to support its different overloads (including the TState support)

I mean, I understand it's an attractive method to have, but it may be counterproductive.

Alternative Designs

Callbacks and notifications [...] Instead of storing a callback with each entry or some change tokens we could use System.Threading.Channels [...] I expect this design to be more memory/cpu efficient than existing one

Oh yes please: if you decide to go with the callbacks route, a single stream of events would definitely be better then a ton of specific callbacks stored inside each cache entry.

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

public interface ISizer
{
   int GetSizeInBytes();
}

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

This may be a nice idea: in case it will go forward I think it should be explained more and experimented with, including some practical examples on how to implement it.

Asynchronous interface

We wanted to be explicit that everything in RCache should be sync.

Understood, but as said by providing a GetOrSet method with a factory passed to it, I think users will expect both of these:

• stampede is take care of
• both sync/async are supported

Anyway fingers crossed for you: I hope it will be enough for the community... but I'm not that sure.

This approach allows us not to go into distributed systems problems, since async caches requires much richer semantics.

Eh, definitely, I feel that 😅

We are happy though to add 'TryAdd' to our proposal, to avoid stampedes for async factories.

How would a TryAdd method solve the stampede for async operations? If there's stampede prevention, it should be in the normal GetOrSet method(s) available, maybe optionally (like the new output cache in aspnet).

We are going to propose another interface in the future that covers asynchronous caches scenarios and more.

I'm interested in this, will follow!

Enumeration
We decided not to implement enumeration on RCache:

Good call!

A couple of final things.

This looks good for caches of homogeneous values, but for heterogeneous values? Would we just use RCache<TKey, object> and then cast the result or is there something else to look out for?

Capacity: what happens when the Capacity is reached? I think I've missed the explanation.

Regarding logging: is there a plan to support logging or is it way too overkill at such a low level? I can imagine the latter, but just asking.

Ok, I think it's all.

Thanks again for sharing this with us!

[rafal-mz]

Thanks for your feedback. :-)

when this will be finalized and released (I suppose in the .NET 9 timeframe)

If this is going to end up in dotnet/extensions then we have 1 month release cadence for this repository.

Following this distinction I see this new RCache as part of the 1st category, and in this sense it feels good to me: the scope is quite narrow, no extra high-level features and the attention to micro-benchmarking is quite high. FWIW, good 👍

I agree with this classification and how you position RCache there. Application level cache IMHO must have much richer semantics to support all those features and it affects overall performance. Lower level cache can be also used as a building block for creating app level caches.

Maybe something that communicate the low-level/no-frills nature of it like RawCache or similar?

I am not very opinionated on the name. I like RCache since it is short and quite unique. If it will lay in appropriate namespace and will be well documented I don't see an object name to be point of confusion. Probably whatever name we choose there will be somebody that don't like it, so I will leave this decision to you.

Understood, but to do this it seems you are not cleaning up automatically: not having the code to look at I'm wondering if a SET call of key "foo" will also cleanup the expired entry for cache key "bar". If this is not the case you may run into memory remaining allocated by cache entries that ended up not being touched for a long time, so this is something to look out for.
A different approach may be to include timed background cleanup but as optional, with something like a bool flag in the general options or a TimeSpan? (null being the default, so no auto-cleanup). This way by default no leaks will be guaranteed but, if wanted, the ease of it can be obtained. I think the related code should not be that much.

You are correct with the first three sentences. We may leave uncleared memory when cache is long untouched. This is the reason our interface has RemoveExpiredEntries method, so that if you know this might be your case you can implement automatic clearup easily. We can also create some helpers that do it for you. LRU implementation that we have now is not using background threads but the LFU implementation that we will come up with next will do. One of the core ideas of this proposal is - this is not just one implementation. This is the first one.

The feature is nice, but watch out for this (been there): I would enable automatic Dispose calls on eviction only as an opt-in feature (like bool EnableAutoDisposeOnEvict), since sometimes I saw usages in the wild where something is get from the cache and kept used only to become randomly disposed while still being used, for this exact behavior.

Thats great experience. I will add this to proposal. Thanks a lot!

factory methods: why 2 of them instead of only one with name + options and options being nullable? If tomorrow a new param param3 would arrive, that may generate new permutations (name + param3, name + options + param3, etc). Nothing major, just wondering

I expect 'Options' parameter to absorb new features instead of adding new permutations to factory method. This is just a preference decision, since nullable is semantically equivalent to what we have now. I think that interfaces that require passing null explicitly are just longer to write and not always clear to interpret.

named caches: thinking about the DI support, I assume calling CreateLru<TKey, TValue>("foo") multiple times will return the same instance right? What about calling it twice with the same name but different options? Or with the same name but with different types? Is the name unique per-types-combination or global?

• RCache factory is a factory, so creating the cache with the same name twice will return different instance. (Not using DI)
• Using `AddLruRCache' in ServiceCollection with the same name multiple times will configure one instance of RCache that is unique in DI per name and types. We are following .NET options pattern, so each configuration will apply in sequnce.
• As stated above, name + types is a differentiatior. Cache with the same name and different types will have its own instance.

So to summary, DI is global per name and key value combination. Creating 'RCache' by hand gives you no protection.

options: RCacheLruOptions<TKey, TValue> why the generic typing here? Currently there does not seem to be nothing justying that, and as it is it would avoid sharing the same options with different instances. Maybe is it to make it future proof? Admittedly the cost here is nothing, so again just wondering

• By having RCacheLruOptions follow the same generic parameters as RCache itself, you can have shorter signature for creating a cache using factory since types will be inferred.
• This is future proof if we want any TValue specific option in options we don't need to do a breaking change. (Examples: calculating TValue size func in options)

ExtendedTimeToEvictAfterHit vs ExtendTimeToEvictAfterHit: I suggest to use a Is/Enable/etc prefix for bool options. In this case specifically the 2 options looks quite identical, so by using something like EnableExtendedTimeToEvictAfterHit it would make it clearer which one is which

Noted, will think about clearer naming.

methods overloads: I see different overloads with/without optional params (like 4 different GetOrSets). I understand the need but down the line it may be quite daunting to maintain/evolve with this approach

Could you give an example when maintaing/evolving it is daunting?

factory signature: you are using the specific params currently used, I can imagine to avoid bloat. While I feel that, I also can see a problem in the future when new factory params/return values may be needed, and then you would need to add more overloads and handle them all and the permutations will become quite a lot (been there...)

If I understand correctly you think that the RCache factory may be returning some wrap over TValue and TTL and accept different parameters than TKey and TState?

I think that having TState allow you to pass any parameter type, and returning TValue to return any type of value. Could you share your experience with the issues you had with permutations?

the bool TryGet(out ...) signature will not be usable in case one day you'd like to add async support, so you'll eventually end up with 2 different methods with 2 very different signatures for the sync and async versions. I'd suggest to start immediately with a signature that will be able to support async. In my project I have used a simple MaybeValue struct, kinda like a Nullable but for both ref/value type (like a maybe/option monad). It works well, is not heavy on resources and is easily evolvable into the async territory

RCache will never have async support. This is explicit design decision and proposal is not supposed to evolve in this direction.

Also, now that I'm thinking about it: if no stampede prevention is provided, and no async support is provided (see later), why having a GetOrSet at all?

As explained above by Martin, stampade can be easily fixed by returning Lazy from a cache. For big services collision rate is small, so even when cost of creation is high you don't need this protection.

Understood, but as said by providing a GetOrSet method with a factory passed to it, I think users will expect both of these:

Concurrent dictionary does not support async and does not prevent stampedes but still supports GetOrSet. Why users would expect different behavior from RCache than ConcurrentDictionary?

How would a TryAdd method solve the stampede for async operations?

I've made a mistake, it won't. I've removed this part from proposal.

This looks good for caches of homogeneous values, but for heterogeneous values? Would we just use RCache<TKey, object> and then cast the result or is there something else to look out for?

This is one possible solution.

Capacity: what happens when the Capacity is reached? I think I've missed the explanation.

When capacity reaches nothing happens. When an item is added to a cache with full capacity, cache will evict one entry in approx Lru order.

Regarding logging: is there a plan to support logging or is it way too overkill at such a low level? I can imagine the latter, but just asking.

I think it would be an overkill but we can add optional logging for diagnostic purposes that would be turned off by default. The question is what the log lines would be about? If the case is to log TKey and TValue there comes a problem of not capturing any sensitive data.

[Richard004]

Small remark.
I realize that we aim primarily for the highly perf, low allocation scenarios (like ConcurrentDictionary). That is a good call. I might use it for many of my ConcurrentDictionaries.

I am a big fan of the TValue GetOrSet<TState>(TKey key, TState state, Func<TKey, TState, TValue> factory); overload, which allows to save allocation of TState closure for the factory that might need it.

I just hope that it will not be implemented as is in the BitFaster caching repo like this
V GetOrAdd<TArg>(K key, Func<K, TArg, V> valueFactory, TArg factoryArgument) => this.GetOrAdd(key, k => valueFactory(k, factoryArgument));

Where this line indeed creates a closure of the valueFactory and factoryArgument.
Sorry if that is obvious, just wanted to make sure.

[rafal-mz]

No, its not implemented like that. This overload was specifically added to avoid closure allocation.

[jodydonetti]

If this is going to end up in dotnet/extensions then we have 1 month release cadence for this repository.

Ah, probably even better.

I agree with this classification and how you position RCache there. Application level cache IMHO must have much richer semantics to support all those features and it affects overall performance. Lower level cache can be also used as a building block for creating app level caches.

Exactly, that's the idea!

Probably whatever name we choose there will be somebody that don't like it

Yep, most definitely 🤷

so I will leave this decision to you.

Ahah thanks, but part I'm not a Microsoft employee :-)

Anyway, another idea that just came up: MemoryCacheSlim.
It's a known and common naming pattern in .NET and already have ManualResetEvent and ManualResetEventSlim, Semaphore and SemaphoreSlim, etc and each "slim" variant is kinda known to be the "lightweight version with somewhat less features" of the "full" version.
On the other hand maybe in this case the 2 designs (MemoryCache and this new one) would be quite different so this convention may not apply.
I don't know, just spitballing here at the moment for everybody to think about it.

You are correct with the first three sentences. We may leave uncleared memory when cache is long untouched. This is the reason our interface has RemoveExpiredEntries method, so that if you know this might be your case you can implement automatic clearup easily. We can also create some helpers that do it for you. LRU implementation that we have now is not using background threads but the LFU implementation that we will come up with next will do.

Understood, and I like having the ability to not having stuff running in the background and being able to fully control manual calls to RemoveExpiredEntries manually. Having said that, I still think the support to do it automatically in an opt-in way with the implementation already provided would be something people would like, and the code may be small in theory. But of course I may be wrong here, and without looking at the code I'll wait and see.

Btw I later noticed that the abstract class already implements IDisposable, so I was wondering the rationale here: without a timer there would not be a potential timer leak, got it, but what is IDisposable here for then? There mey still be leaks of something else?

One of the core ideas of this proposal is - this is not just one implementation. This is the first one.

Totally got it, and I really like it!

Thats great experience. I will add this to proposal. Thanks a lot!

You're welcome!

I expect 'Options' parameter to absorb new features instead of adding new permutations to factory method.

Makes sense. I still have a doubt about what can actually go into options, when we also consider the IOptions<T> pattern and the way it can naturally be configured via the general config system (so JSON deserialization and stuff), and I have the same concern in FusionCache, too.
Some time ago I was wondering about this with both Davids (Fowler and Pine) in an email thread: should sub-components like an ITimeProvider or similar (so not just plain values) be put directly into an options object or on separate ctor params, but I never got to a definitive answer about it.
Do you see an hypothetical ITimeProvider or others non-plain-values into the options class itself?

This is just a preference decision, since nullable is semantically equivalent to what we have now. I think that interfaces that require passing null explicitly are just longer to write and not always clear to interpret.

Agree, but I usually also declare the nullable params with a default value of null, to get the best of both worlds. Anyway it's more of a stylistic preference probably, so I get the different vibes.

• RCache factory is a factory, so creating the cache with the same name twice will return different instance. (Not using DI)
• Using `AddLruRCache' in ServiceCollection with the same name multiple times will configure one instance of RCache that is unique in DI per name and types. We are following .NET options pattern, so each configuration will apply in sequnce.
• As stated above, name + types is a differentiatior. Cache with the same name and different types will have its own instance.

Yeah sorry, after posting my comment I got to it, sorry for the time wasted.

So to summary, DI is global per name and key value combination. Creating 'RCache' by hand gives you no protection.

Makes sense, thanks.

• This is future proof if we want any TValue specific option in options we don't need to do a breaking change. (Examples: calculating TValue size func in options)

Right, makes sense.

Could you give an example when maintaing/evolving it is daunting?

Eh, (un)luckily yes 😅: see here, here and here. They are the same class (splitted in 3 partial files for organization purposes), and they represent the permutation of all the optional params and signatures. I started with some, and then added support for more params, so I had to add all the possible combinations of params to keep the thing aligned with the general approach.
Maybe this will not apply here, and maybe it's not so bad (I had to do it once), but I preferred to warn you guys about this, maybe you can take some inspiration on what to potentially avoid.

If I understand correctly you think that the RCache factory may be returning some wrap over TValue and TTL and accept different parameters than TKey and TState?
I think that having TState allow you to pass any parameter type, and returning TValue to return any type of value. Could you share your experience with the issues you had with permutations?

For the return types of the factory lambda, adding new overloads with new lambda signatures is a pita, whereas adding a new prop to an existing return type is much easier and will not explode into a lot of variations.
On the other hand I can understand the potential extra allocations even when not needed, but still is something to look out for.

As an exercise I suggest to try to keep the current design, and see what would needs to change in the future by adding an extra return type, not just TValue or (TValue, TimeSpan), but also the Hotness thing you mentioned, let's say to let consumers configure how important something is (it's just an example).
How would that work down the line?

RCache will never have async support. This is explicit design decision and proposal is not supposed to evolve in this direction.

Ok, I was referring to this passage "We are going to propose another interface in the future that covers asynchronous caches scenarios and more" and thinking about consistency overall.

As explained above by Martin, stampade can be easily fixed by returning Lazy from a cache.

Yes, as in ConcurrentDictionary, but then on the consumer side I saw a lot of people wanting to avoid always having to do dict[key].Value etc and ending up creating their own LazyConcurrentDictioanry or whatever to shield them from having to directly work with Lazy<T> every time. Also, they need to understand the LazyThreadSafetyMode.
Just my two cents.

For big services collision rate is small, so even when cost of creation is high you don't need this protection.
Mmmh, this sounds strange: I had members of the FusionCache community telling me that just by swapping MemoryCache with FusionCache they saw somewhere around 50% less calls to the database. Of course this wholly depends on the access patterns involved, so it may very well depends on a lot of factors.
And anyway you surely have way more field data than me 😅 so I trust you guys here.

Concurrent dictionary does not support async and does not prevent stampedes but still supports GetOrSet. Why users would expect different behavior from RCache than ConcurrentDictionary?

I'm going out on a limb here maybe, but 2 things come to mind:

1. it's not that they expect have different expectations, it's that in my experience most of the times they expect protection in the dictionary too, and are biten by it down the line when they discover that they are not. Of course there's the whole RTFM and stuff, but I'm just pointing this out after having seen it multiple times
2. the thing is called cache stampede, and this is a cache, so expectations may differ

This is one possible solution.

Got it, thanks!

When capacity reaches nothing happens. When an item is added to a cache with full capacity, cache will evict one entry in approx Lru order.

Got it.

I think it would be an overkill but we can add optional logging for diagnostic purposes that would be turned off by default.

As it is today, logging is probably overkill, I agree. I was just thinking in perspective.
Anyway if it may be useful to you and the team, have a read here as I've been there in the past, maybe it can be of help with public expectations.
In the end the standard way of having to configure the min log level (via namespace prefix etc) ended up being the right call, imho, but I'm still wondering if a global (meaning per-instance) bool flag would be a nice addition, to avoid inadvertently enabling logging for the cache, and for every cache instance. Since here we are driving for max perf, a nice little bool flag (default to false) to explicitly enable it may be a nice addition, on top of receiving an ILogger instance whichwould happen automatically via DI.

If the case is to log TKey and TValue there comes a problem of not capturing any sensitive data.

Good call, haven't thought about it.

The question is what the log lines would be about?

In FusionCache there can be a lot of stuff going on: async calls, automatic background factory completion, distribuetd cache + backplane communications, eager refresh and so on so logging becomes quite fundamental for when my users go into detective mode (and for my own sanity too, when developing new features 🤣). But here, in such a low-level + hi-perf case, probably it's not worth it, you're right.

Anyway... woah, what a good discussion to have, thanks again, I really appreciate it!

[rafal-mz]

Ahah thanks, but part I'm not a Microsoft employee :-)

I've meant to leave this decision to the community, reviewers. For me its just a name.

Btw I later noticed that the abstract class already implements IDisposable, so I was wondering the rationale here: without a timer there would not be a potential timer leak, got it, but what is IDisposable here for then? There mey still be leaks of something else?

If the cache holds TValues implementing IDisposable, it will dispose each of those at its own disposal. The class is also holding System.Diagnostics.Metrics.Meter, which is IDisposable.

As an exercise I suggest to try to keep the current design, and see what would needs to change in the future by adding an extra return type, not just TValue or (TValue, TimeSpan), but also the Hotness thing you mentioned, let's say to let consumers configure how important something is (it's just an example).
How would that work down the line?

The presented model is general and cannot have any assumptions about underlying algorithm. If we would return 'hotness' or 'priority' it would mean that all of the implementations must have a notion of prioritization. IMHO to specify such details in a correct way one needs to have deep understanding of the implementation details, algorithm used, data access patterns and excesssive measurements. So, I would call it a leaky abstraction.

There are some algorithm details which may be useful for tuning the cache for high performance. Such details (if exposed) will be part of the options object for specific implementation. In this case it would be RCacheLruOptions<TK, TV>

Do you see an hypothetical ITimeProvider or others non-plain-values into the options class itself?

I believe that anything like ILogger, TimeProvider should go into ctor and be taken from DI. First, it allows to configure cross cutting concerns once and the whole system 'pick them up' automatically. Second, it makes the contract implicit, so that it is less work for library developer to maintain the interface. Third (this is just my impression not backed by data), I think that configuration model is not that well understood in the community and folks often build service provider multiple times to pass some class instance to options.

Funny enough, I think in case of time provider and RCache it will be taken from options as instance. The reason for that is we have public factory that don't know about DI container.

I saw a lot of people wanting to avoid always having to do dict[key].Value etc and ending up creating their own LazyConcurrentDictioanry or whatever to shield them from having to directly work with Lazy every time. Also, they need to understand the LazyThreadSafetyMode.

I think (again as Martin already mentioned) we want people to pay for what they use. I don't like the idea of slowing down everybody by default to shield less experienced folks from shooting their foot. I would love to do both at the same time. :-)

the thing is called cache stampede, and this is a cache, so expectations may differ

Thats fair. I will think about it.

[mobratil]

@ReubenBond
Thank you for the feedback, @jamesqquick. I'm glad to hear that you are excited about the progress.

Regarding your suggestion to include a bool Remove(KeyValuePair<TKey, TValue> entry) API, I agree that this addition would be valuable.

I will review how challenging it would be to integrate this into our internal prototype.

[mobratil]

@ReubenBond I tried to adopt bool Remove(KeyValuePair<TKey, TValue> entry)
However, I think I found an issue in the code which I don't know how to fix: bitfaster/BitFaster.Caching#615

I'm waiting for the reply from @bitfaster to confirm.

[joperezr]

This proposal has been updated. @ReubenBond @mgravell would you mind taking one last look before we mark it ready for review?

[verdie-g]

Small comments about the metrics naming:

• The meters for the runtime metrics is System.Diagnostics.Runtime (Metrics for System.Runtime runtime#85372) so we might want to use the namespace here instead
• process.* are reserved for process metrics such as CPU, memory, etc. (https://opentelemetry.io/docs/specs/semconv/system/process-metrics)
• cache prefix could conflict with other libraries
• *.count seems to be for up/down counters (https://opentelemetry.io/docs/specs/semconv/general/metrics/#use-count-instead-of-pluralization-for-updowncounters)

What do you think about these names:

• rcache.hits
• rcache.misses
• rcache.expirations
• rcache.adds
• rcache.removals
• rcache.evictions
• rcache.items.usage
• rcache.items.limit

[KalleOlaviNiemitalo]

    /// <summary>
    /// Adds an LRU (Least Recently Used) cache to the dependency injection container.
    /// </summary>
    /// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
    /// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
    /// <param name="services">Dependency injection container to add the cache to.</param>
    /// <returns>The value of<paramref name="services"/>.</returns>
    /// <exception cref="ArgumentNullException">When passed <paramref name="services"/> are <see langword="null"/>.</exception>
    public static IServiceCollection AddLruRCache<TKey, TValue>(this IServiceCollection services)
        where TKey : notnull;

Does this add the cache both as a keyed service (with a name derived from TKey and Value, as noted in #4766 (comment)) and as an unkeyed service (so that the application can resolve the service before it has an RCache<TKey, TValue> reference from which it could read the string Name property)?

If it adds the cache as an unkeyed service only, then the following remarks are not quite right:

    /// <summary>
    /// Gets the name of the cache instance.
    /// </summary>
    /// <remarks>
    /// This name is used to identity this cache when publishing telemetry. It's also the name used if query for the cache via
    /// dependency injection.
    /// </remarks>
    public abstract string Name { get; }

[jodydonetti]

This proposal has been updated. @ReubenBond @mgravell would you mind taking one last look before we mark it ready for review?

I'm no @ReubenBond nor @mgravell , but I hope my 2 cents may be helpful.

Overall it looks good, I just have a couple of notes.

Builder

I see you've revamped the builder part, which in theory is great for extensibility and 3rd party implementations (see: OSS people), but to me it looks like the new builder API is too tied to a specific LRU implementation, mainly because the class is not abstract and because of this:

public RCacheBuilder<TKey, TValue> WithOptions(RCacheLruOptions<TKey> options);

Wouldn't it be better to make the RCacheBuilder class abstract and let subclasses be specific about which type of RCache they are for? Otherwise how would someone create a builder for a different one?

I'll keep using the Belady cache I've used previously as an example: should I then create an RCacheBeladyBuilder that derives from RCacheBuilder, and that would have a WithOptions method accepting an RCacheLruOptions? That would be strange... both for implementers and users.

Instead I would propose something like this:

public abstract class RCacheBuilder<TKey, TValue>
    where TKey : notnull
{
    public abstract RCacheBuilder(string name);
    public abstract RCacheBuilder<TKey, TValue> WithMeterFactory(IMeterFactory? meterFactory);
    public abstract RCache<TKey, TValue> Build();
}

// LRU
public class RCacheLruBuilder<TKey, TValue>
    : RCacheBuilder<TKey, TValue>
    where TKey : notnull
{
    public RCacheLruBuilder(string name);
    public RCacheLruBuilder<TKey, TValue> WithOptions(RCacheLruOptions<TKey> options);
}

// BELADY
public class RCacheBeladyBuilder<TKey, TValue>
    : RCacheBuilder<TKey, TValue>
    where TKey : notnull
{
    public RCacheBeladyBuilder(string name);
    public RCacheBeladyBuilder<TKey, TValue> WithOptions(RCacheBeladyOptions<TKey> options);
}

And they would be used like this:

var _cacheLru = new RCacheLruBuilder<Guid, User>("my-cache-name")
    .WithMeterFactory(meterFactory)
    .Build();

var _cacheBelady = new RCacheBeladyBuilder<Guid, User>("my-cache-name")
    .WithMeterFactory(meterFactory)
    .Build();

UPDATE 2024-08-23: thinking about it, maybe it was not your intention to for the builder part to be shared between different implementations (using the same RCache class as a base gives a lot of value, maybe less so for the builder part). If that is the case, another option would be to simply change the name from RCacheBuilder to RCacheLruBuilder and call it a day.

DI

The DI registration part seems good 👍 , except for one thing about naming (naming is hard etc).
I see 2 different naming use:

• RCacheLru (mostly everywhere)
• LruRCache (only in the DI part)

I think consistency and uniformity is highly desirable.

Enumerable

Something else not technically "wrong" but just... I don't know, feels "risky": is it the best thing for RCache to directly implement IEnumerable<KeyValuePair<TKey, TValue>> instead of exposing something like IEnumerable<KeyValuePair<TKey, TValue>> Entries? I know we are used to just foreach over a dictionary, but doing that over a cache... I don't know.
But again, nothing wrong per se, I just wanted to shared how it feels.

Other than this it LGTM!

Release Channel

One final question, maybe it has been already said: is this an out of band thing or part of .NET?
And what would be the supported TFMs?
I think the .NET 9 train is already gone (preview 7 is the last chance for public API changes if I'm not wrong), so what is the idea?

I'm really interesting in this, not just to use it per-se but also as a potential new L1 in FusionCache.

Hope this helps.

[mgravell]

Thought on expiration: what is providing time? Is this TimeProvider ? ISystemClock? or flat time? Supporting time abstraction might significantly improve testability.

[RussKie]

Release Channel

One final question, maybe it has been already said: is this an out of band thing or part of .NET? And what would be the supported TFMs? I think the .NET 9 train is already gone (preview 7 is the last chance for public API changes if I'm not wrong), so what is the idea?

Yes, dotnet/extensions don't exactly follow the .NET release cycle, nor follow the semver convention. This repo is on a monthly release cadence and each "point" release can bring new API and a possibility of breaking changes (though it's something we, generally, avoid as much as we can).

Our build artifacts multi-target, and 8.x train supports net462, net6.0 and net8.0. The 9.x train supports net462, net8.0 and net9.0.

[mobratil]

@jodydonetti

Builder

Thank you for your suggestion regarding the builder. The builder was indeed not intended to be shared among various implementations, but rather focused solely on the LRU implementation.
I like your suggestion to rename it from RCacheBuilder to RCacheLruBuilder.

DI

Thanks for finding the naming inconsistency.
I will update the DI registration to use RCacheLru consistently throughout the API.

IEnumerable

I understand your reservations about directly implementing IEnumerable<KeyValuePair<TKey, TValue>> for the cache.
The decision to go with direct implementation was influenced by the BitFaster implementation, which we found to be practical and convenient, especially since these caches function as keyed collections with eviction policies.

Regarding your suggestion to expose it via an Entries property, while this would add an additional call, it doesn’t necessarily provide a significant benefit over the direct implementation.
However, I’m open to revisiting this if there’s strong feedback from the community or additional use cases that justify the property-based approach.

[mobratil]

    /// <summary>
    /// Adds an LRU (Least Recently Used) cache to the dependency injection container.
    /// </summary>
    /// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
    /// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
    /// <param name="services">Dependency injection container to add the cache to.</param>
    /// <returns>The value of<paramref name="services"/>.</returns>
    /// <exception cref="ArgumentNullException">When passed <paramref name="services"/> are <see langword="null"/>.</exception>
    public static IServiceCollection AddLruRCache<TKey, TValue>(this IServiceCollection services)
        where TKey : notnull;

Does this add the cache both as a keyed service (with a name derived from TKey and Value, as noted in #4766 (comment)) and as an unkeyed service (so that the application can resolve the service before it has an RCache<TKey, TValue> reference from which it could read the string Name property)?

If it adds the cache as an unkeyed service only, then the following remarks are not quite right:

    /// <summary>
    /// Gets the name of the cache instance.
    /// </summary>
    /// <remarks>
    /// This name is used to identity this cache when publishing telemetry. It's also the name used if query for the cache via
    /// dependency injection.
    /// </remarks>
    public abstract string Name { get; }

Thank you for identifying this issue.

You are correct—the public static IServiceCollection AddLruRCache<TKey, TValue>(this IServiceCollection services) method adds the cache as an unkeyed service only.
I will update the XML documentation.

[mobratil]

Thought on expiration: what is providing time? Is this TimeProvider ? ISystemClock? or flat time? Supporting time abstraction might significantly improve testability.

@mgravell, thank you for the insightful suggestion. Currently, we use Environment.TickCount64 primarily due to the micro-optimization benefits, as it avoids the overhead that might come with using TimeProvider.

That said, I see the value in supporting a TimeProvider option. We could introduce this as an optional parameter: if a TimeProvider is not explicitly provided, the implementation would default to the current approach.
I plan to run benchmarks to assess the performance impact of this change before proceeding.

[jodydonetti]

@mobratil thanks for your answer, appreciate it.

And yes the IEnumerable thing is not 100% right/wrong, so I'm totally ok with any outcome.

Thanks!

[mgravell]

@mobratil as a minor note: when we wrote the kinda-similar-to-this cache at StackOverflow, we found (during measuring) that the simple act of fetching the current time via tick-count (or similar) was our bottleneck; we fixed this by adding a "now-ish" concept that was a snapshot of time that was incremented separately by a timer at a reasonable frequency, so the bulk of the "has this expired" checks were just a volatile read. I'm not saying you'll have the same experience, but it might at least be worth considering / measuring.

[jodydonetti]

If I remember correctly, even @davidfowl and the gang used a "less precise" clock measurement technique in Kestrel (but I'm not sure/don't remember the details).

It may be worth exploring if it's worth it or not: if it is, since that may change the actual expiration (even if by a microscopic amount) allow users to enable it via a bool EnableLessPreciseTime option or something like that (naming is hard etc, as always).

[khellang]

If I remember correctly, even @davidfowl and the gang used a "less precise" clock measurement technique in Kestrel (but I'm not sure/don't remember the details).

Yeah, that's exactly what the DateHeaderValueManager in Kestrel does 😄

[mobratil]

@mobratil as a minor note: when we wrote the kinda-similar-to-this cache at StackOverflow, we found (during measuring) that the simple act of fetching the current time via tick-count (or similar) was our bottleneck; we fixed this by adding a "now-ish" concept that was a snapshot of time that was incremented separately by a timer at a reasonable frequency, so the bulk of the "has this expired" checks were just a volatile read. I'm not saying you'll have the same experience, but it might at least be worth considering / measuring.

I did some measurements based on your suggestion, and you're right. The raw measurements show the following differences for the Get operation:

• Environment.TickCount64: 3.7 ns
• Timer updating ticks value: 3.2 ns

However, incorporating a timer to periodically update the ticks value would conflict with our design philosophy of avoiding background threads. I believe it’s best to stick with our current approach for now. That said, we can definitely revisit this idea in the future. I’m also open to any further suggestions on how we can optimize within these constraints.

[mobratil]

Small comments about the metrics naming:

• The meters for the runtime metrics is System.Diagnostics.Runtime (Metrics for System.Runtime runtime#85372) so we might want to use the namespace here instead
• process.* are reserved for process metrics such as CPU, memory, etc. (https://opentelemetry.io/docs/specs/semconv/system/process-metrics)
• cache prefix could conflict with other libraries
• *.count seems to be for up/down counters (https://opentelemetry.io/docs/specs/semconv/general/metrics/#use-count-instead-of-pluralization-for-updowncounters)

What do you think about these names:

• rcache.hits
• rcache.misses
• rcache.expirations
• rcache.adds
• rcache.removals
• rcache.evictions
• rcache.items.usage
• rcache.items.limit

Thanks @verdie-g, for the suggestions. I agree with your points. I've updated the proposal accordingly, incorporating your suggested names for consistency and clarity. Please take a look and let me know if it makes more sense.

[jodydonetti]

Hi @joperezr

[...] would you mind taking one last look before we mark it ready for review?

Will the review be on YT or in private?
If on YT, can we know the date upfront? I'd like to follow along, thanks.

[joperezr]

I'll find more details about the schedule and then will report back here with dates and links in case it will be hosted.

[ReubenBond]

@mobratil one more thing comes to mind as I consider how we would leverage this in dotnet/orleans: the new GetAlternateLookup API would be very useful to have, particularly for serialization/deserialization. @neuecc wrote a blog entry on how MessagePack-CSharp leverages a similar technique here (and how they could leverage the new functionality): https://neuecc.medium.com/fast-dictionary-lookup-of-utf-8-string-in-the-c-13-with-net-9-alternatelookup-43798aef022d. We take a similar approach in Orleans to avoid allocating objects during [de]serialization if they are already cached.

[mgravell]

Microsoft.Extensions.Memory.Cache - is that a tyop [sic] to Microsoft.Extensions.Caching.Memory ?

[mobratil]

@mobratil one more thing comes to mind as I consider how we would leverage this in dotnet/orleans: the new GetAlternateLookup API would be very useful to have, particularly for serialization/deserialization. @neuecc wrote a blog entry on how MessagePack-CSharp leverages a similar technique here (and how they could leverage the new functionality): https://neuecc.medium.com/fast-dictionary-lookup-of-utf-8-string-in-the-c-13-with-net-9-alternatelookup-43798aef022d. We take a similar approach in Orleans to avoid allocating objects during [de]serialization if they are already cached.

I think the GetAlternateLookup feature would be really useful. Adding alternate lookup support, like what we see in ConcurrentDictionary. It's not something we’ve included in the current design, but it’s definitely something we could look at adding in future updates.

[jodydonetti]

Builder

Thank you for your suggestion regarding the builder. The builder was indeed not intended to be shared among various implementations, but rather focused solely on the LRU implementation.

I like your suggestion to rename it from RCacheBuilder to RCacheLruBuilder.

Just to avoid an involuntary oversight before passing the pearly gates of an official approval, in the current proposal the name is still the old one.

[joperezr]

Hi @joperezr

[...] would you mind taking one last look before we mark it ready for review?

Will the review be on YT or in private? If on YT, can we know the date upfront? I'd like to follow along, thanks.

FYI, the current plan is to Review this tomorrow 9/10 in our design review at 11:00 PST and I do believe that we plan on streaming it here: https://www.youtube.com/@NETFoundation/streams

[bartonjs]

• Name: "RCache" is not descriptive. Come up with a descriptive name (that helps explain why you want this one vs some other one)
• Namespace: Microsoft.Extensions.Cache.Memory would be bad "we'd have both Caching and Cache". Probably meant Microsoft.Extensions.Caching.Memory
• Most of the public abstract methods should be non-virtual and use the template method pattern
• The overloads of GetOrSet do not have a least common denominator (other than pre-invoking the callback) that a new overload could be added with a new factory shape without requiring all derived types to override it.
• Why is there a boolean ExtendTimeToEvictAfterHit instead of allowing ExtendedTimeToEvictAfterHit to be 0, or be nullable?
• "Lru" may be a contentious name, though it'll probably work as the industry standard term.

namespace Microsoft.Extensions.Caching.Memory;

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

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

    /// <summary>
    /// Tries to get a value from the cache.
    /// </summary>
    /// <param name="key">Key identifying the requested value.</param>
    /// <param name="value">Value associated with the key or <see langword="null"/> when not found.</param>
    /// <returns>
    /// <see langword="true"/> when the value was found, <see langword="false"/> otherwise.
    /// </returns>
    public abstract bool TryGet(TKey key, [MaybeNullWhen(false)] out TValue value);

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

    /// <summary>
    /// Sets a value in the cache.
    /// </summary>
    /// <remarks>
    /// 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.
    /// </remarks>
    /// <param name="key">Key identifying the value.</param>
    /// <param name="value">Value to cache on the heap.</param>
    /// <param name="timeToExpire">Amount of time the value is valid, after which it should be removed from the cache.</param>
    /// <exception cref="ArgumentOutOfRangeException">If <paramref name="timeToExpire"/> is less than 1 millisecond.</exception>
    public abstract void Set(TKey key, TValue value, TimeSpan timeToExpire);

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

    /// <summary>
    /// Gets a value or sets it if doesn't exist.
    /// </summary>
    /// <remarks>
    /// 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.
    /// </remarks>
    /// <typeparam name="TState">The type of the state object passed to the factory function.</typeparam>
    /// <param name="key">The key identifying the cached value.</param>
    /// <param name="state">An additional state object passed to the factory function.</param>
    /// <param name="factory">
    /// 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 <see cref="TimeSpan"/> representing the duration for which 
    /// the value remains valid in the cache before expiring.    
    /// </param>
    /// <returns>
    /// The value associated with the key, either retrieved from the cache or created by the factory function.
    /// </returns>
    public abstract TValue GetOrSet<TState>(TKey key, TState state,
        Func<TKey, TState, (TValue value, TimeSpan timeToExpire)> factory);

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

    /// <summary>
    /// Gets a value or sets it if doesn't exist.
    /// </summary>
    /// <remarks>
    /// 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.
    /// </remarks>
    /// <param name="key">Key identifying the value.</param>
    /// <param name="factory">
    /// 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 <see cref="TimeSpan"/> representing the duration for which 
    /// the value remains valid in the cache before expiring.
    /// </param>
    /// <returns>
    /// Data retrieved from the cache or created by the passed factory function.
    /// </returns>
    public abstract TValue GetOrSet(TKey key, Func<TKey, (TValue value, TimeSpan timeToExpire)> factory);

    /// <summary>
    /// Gets the current number of items in the cache.
    /// </summary>
    /// <returns>
    /// 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.
    /// </returns>
    public abstract int GetCount();

    /// <summary>
    /// Attempts to remove the value that has the specified key.
    /// </summary>
    /// <param name="key">Key identifying the value to remove.</param>
    /// <returns>
    /// <see langword="true"/> if the value was removed, and <see langword="false"/> if the key was not found.
    /// </returns>
    public abstract bool Remove(TKey key);

    /// <summary>
    /// Attempts to remove the specified key-value pair from the cache.
    /// </summary>
    /// <param name="key">Key identifying the value to remove.</param>
    /// <param name="value">The value associated with the key to remove.</param>
    /// <returns>
    /// <see langword="true"/> if the specified key-value pair was found and removed; 
    /// otherwise, <see langword="false"/>.
    /// </returns>
    /// <remarks>
    /// 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.
    /// </remarks>
    public abstract bool Remove(TKey key, TValue value);

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

    /// <summary>
    /// Returns an enumerator that iterates through the items in the cache.
    /// </summary>
    /// <returns>
    /// An enumerator for the cache.
    /// </returns>
    /// <remarks>
    /// 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 <see cref="GetEnumerator"/> was called.
    /// </remarks>
    public abstract IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator();

    /// <summary>
    /// Returns an enumerator that iterates through the items in the cache.
    /// </summary>
    /// <returns>
    /// An enumerator for the cache.
    /// </returns>
    /// <remarks>
    /// 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 <see cref="GetEnumerator"/> was called.
    /// </remarks>
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

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

    /// <summary>
    /// Gets or sets the default time to evict individual items from the cache.
    /// </summary>
    /// <remarks>
    /// 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 <see cref="TimeSpan.MaxValue"/>.
    /// </remarks>
    /// <value>
    /// Defaults to 5 minutes.
    /// </value>
    [TimeSpan(minMs: 1)]
    public TimeSpan DefaultTimeToEvict { get; set; } = TimeSpan.FromMinutes(5);

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

    /// <summary>
    /// Gets or sets a value indicating whether an item's time to evict should be extended upon a cache hit.
    /// </summary>
    /// <value>
    /// Defaults to <see langword="false"/>.
    /// </value>
    public bool ExtendTimeToEvictAfterHit { get; set; }

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

    /// <summary>
    /// Gets or sets the custom time provider used for timestamp generation in the cache.
    /// </summary>
    /// <remarks>
    /// If this value is <see langword="null"/>, the cache will default to using <see cref="Environment.TickCount64"/>
    /// for timestamp generation to optimize performance. If a <see cref="TimeProvider"/> is set, 
    /// the cache will call the <see cref="TimeProvider.GetTimestamp"/> method.
    /// The <see cref="TimeProvider"/> should primarily be used for testing purposes, where custom time manipulation is required.
    /// </remarks>
    /// <value>
    /// Defaults to <see langword="null"/>.
    /// </value>
    public TimeProvider? TimeProvider { get; set; }

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

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

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

/// <summary>
/// Builder for creating <see cref="RCache{TKey, TValue}"/> instances.
/// </summary>
/// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
/// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
public class RCacheLruBuilder<TKey, TValue>
    where TKey : notnull
{
    /// <summary>
    /// Initializes a new instance of the <see cref="RCacheLruBuilder{TKey,TValue}"/> class.
    /// </summary>
    /// <param name="name">Name of the cache, used in telemetry.</param>
    /// <exception cref="ArgumentNullException">Thrown when the <paramref name="name"/> is null.</exception>
    public RCacheLruBuilder(string name);

    /// <summary>
    /// Sets the options for the cache.
    /// </summary>
    /// <param name="options">Cache options.</param>
    /// <returns>The current instance of the <see cref="RCacheLruBuilder{TKey,TValue}"/>.</returns>
    /// <exception cref="ArgumentNullException">Thrown when the <paramref name="options"/> is null.</exception>
    public RCacheLruBuilder<TKey, TValue> WithOptions(RCacheLruOptions<TKey> options);

    /// <summary>
    /// Sets the meter factory for the cache.
    /// </summary>
    /// <param name="meterFactory">Meter factory for telemetry.</param>
    /// <returns>The current instance of the <see cref="RCacheLruBuilder{TKey,TValue}"/>.</returns>
    public RCacheLruBuilder<TKey, TValue> WithMeterFactory(IMeterFactory? meterFactory);

    /// <summary>
    /// Builds the <see cref="RCache{TKey, TValue}"/> instance with the specified configurations.
    /// </summary>
    /// <returns>A ready-to-use <see cref="RCache{TKey, TValue}"/> instance.</returns>
    /// <exception cref="OptionsValidationException">Thrown when the validation of options fails.</exception>
    /// <exception cref="InvalidOperationException">Thrown when the meter factory is null but metrics publishing is enabled.</exception>
    public RCache<TKey, TValue> Build();
}

/// <summary>
/// Extension methods for caching.
/// </summary>
public static class RCacheExtensions
{
    /// <summary>
    /// Adds an LRU (Least Recently Used) cache to the dependency injection container.
    /// </summary>
    /// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
    /// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
    /// <param name="services">Dependency injection container to add the cache to.</param>
    /// <returns>The value of<paramref name="services"/>.</returns>
    /// <exception cref="ArgumentNullException">When passed <paramref name="services"/> are <see langword="null"/>.</exception>
    public static IServiceCollection AddRCacheLru<TKey, TValue>(this IServiceCollection services)
        where TKey : notnull;

    /// <summary>
    /// Adds a named LRU (Least Recently Used) cache to the dependency injection container.
    /// </summary>
    /// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
    /// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
    /// <param name="services">Dependency injection container to add the cache to.</param>
    /// <param name="name">Name of the cache, used in telemetry.</param>
    /// <returns>The value of<paramref name="services"/>.</returns>
    /// <exception cref="ArgumentNullException">When passed <paramref name="services"/> are <see langword="null"/>.</exception>
    /// <exception cref="ArgumentException">When passed <paramref name="name"/> is <see langword="null"/> or empty.</exception>
    public static IServiceCollection AddRCacheLru<TKey, TValue>(this IServiceCollection services, string name)
        where TKey : notnull;

    /// <summary>
    /// Adds an LRU (Least Recently Used) cache to the dependency injection container.
    /// </summary>
    /// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
    /// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
    /// <param name="services">Dependency injection container to add the cache to.</param>
    /// <param name="configure">A function used to configure cache options.</param>
    /// <returns>The value of<paramref name="services"/>.</returns>
    /// <exception cref="ArgumentNullException">When passed <paramref name="services"/> or <paramref name="configure"/> are <see langword="null"/>.</exception>
    public static IServiceCollection AddRCacheLru<TKey, TValue>(this IServiceCollection services, Action<RCacheLruOptions<TKey>> configure)
        where TKey : notnull;

    /// <summary>
    /// Adds an LRU (Least Recently Used) cache to the dependency injection container.
    /// </summary>
    /// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
    /// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
    /// <param name="services">Dependency injection container to add the cache to.</param>
    /// <param name="section">Configuration part that defines cache options.</param>
    /// <returns>The value of<paramref name="services"/>.</returns>
    /// <exception cref="ArgumentNullException">When passed <paramref name="services"/> or <paramref name="section"/> are <see langword="null"/>.</exception>
    public static IServiceCollection AddRCacheLru<TKey, TValue>(this IServiceCollection services, IConfigurationSection section)
        where TKey : notnull;

    /// <summary>
    /// Adds a named LRU (Least Recently Used) cache to the dependency injection container.
    /// </summary>
    /// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
    /// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
    /// <param name="services">Dependency injection container to add the cache to.</param>
    /// <param name="name">Name of the cache, used in telemetry.</param>
    /// <param name="section">Configuration part that defines cache options.</param>
    /// <returns>The value of<paramref name="services"/>.</returns>
    /// <exception cref="ArgumentNullException">When passed <paramref name="services"/> or <paramref name="section"/> are <see langword="null"/>.</exception>
    /// <exception cref="ArgumentException">When passed <paramref name="name"/> is <see langword="null"/> or empty.</exception>
    public static IServiceCollection AddRCacheLru<TKey, TValue>(this IServiceCollection services, string name,
        IConfigurationSection section)
        where TKey : notnull;

    /// <summary>
    /// Adds a named LRU (Least Recently Used) cache to the dependency injection container.
    /// </summary>
    /// <typeparam name="TKey">Type of keys stored in the cache.</typeparam>
    /// <typeparam name="TValue">Type of values stored in the cache.</typeparam>
    /// <param name="services">Dependency injection container to add the cache to.</param>
    /// <param name="name">Name of the cache, used in telemetry.</param>
    /// <param name="configure">A function used to configure cache options.</param>
    /// <returns>The value of<paramref name="services"/>.</returns>
    /// <exception cref="ArgumentNullException">When passed <paramref name="services"/> or <paramref name="configure"/> are <see langword="null"/>.</exception>
    /// <exception cref="ArgumentException">When passed <paramref name="name"/> is <see langword="null"/> or empty.</exception>
    public static IServiceCollection AddRCacheLru<TKey, TValue>(this IServiceCollection services, string name,
        Action<RCacheLruOptions<TKey>> configure)
        where TKey : notnull;
}

/// <summary>
/// Metrics published by <see cref="RCache{TKey, TValue}"/>.
/// </summary>
public static class RCacheMetrics
{
    /// <summary>
    /// Name of the <see cref="Meter"/> to listen to is the name of the cache.
    /// </summary>
    /// <example>
    /// RCache with name "test" will publish metrics with tag "cache-name" equal to "test".
    /// </example>
    public const string LruCacheMeterName = "Microsoft.Extensions.Cache.Memory";

    /// <summary>
    /// Gets the total number of cache queries that were successful.
    /// </summary>
    /// <remarks>
    /// Metric is exposed as <see cref="ObservableCounter{T}"/> with value being <see cref="long"/>.
    /// </remarks>
    public const string Hits = "rcache.hits";

    /// <summary>
    /// Gets the total number of unsuccessful cache queries.
    /// </summary>
    /// <remarks>
    /// Metric is exposed as <see cref="ObservableCounter{T}"/> with value being <see cref="long"/>.
    /// </remarks>
    public const string Misses = "rcache.misses";

    /// <summary>
    /// Gets the total number of expired values.
    /// </summary>
    /// <remarks>
    /// Metric is exposed as <see cref="ObservableCounter{T}"/> with value being <see cref="long"/>.
    /// Expired values are one removed from cache because they were too old.
    /// </remarks>
    public const string Expirations = "rcache.expirations";

    /// <summary>
    /// Gets the total number of values added to cache.
    /// </summary>
    /// <remarks>
    /// This value refers to total calls to set method, and does not include updates.
    /// Metric is exposed as <see cref="ObservableCounter{T}"/> with value being <see cref="long"/>.
    /// </remarks>
    public const string Adds = "rcache.adds";

    /// <summary>
    /// Gets the total number of cache removals.
    /// </summary>
    /// <remarks>
    /// 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 <see cref="Evictions"/> and <see cref="Expirations"/>.
    /// Metric is exposed as <see cref="ObservableCounter{T}"/> with value being <see cref="long"/>.
    /// </remarks>
    public const string Removals = "rcache.removals";

    /// <summary>
    /// Gets the total number of evicted values.
    /// </summary>
    /// <remarks>
    /// Metric is exposed as <see cref="ObservableCounter{T}"/> with value being <see cref="long"/>.
    /// Evicted values are those removed based on the implementation's eviction policy and not time expiration or intentional removal.
    /// </remarks>
    public const string Evictions = "rcache.evictions";

    /// <summary>
    /// Gets the total number of updated values.
    /// </summary>
    /// <remarks>
    /// Metric is exposed as <see cref="ObservableCounter{T}"/> with value being <see cref="long"/>.
    /// </remarks>
    public const string Updates = "rcache.updates";

    /// <summary>
    /// Gets the total number of values in the cache over time.
    /// </summary>
    /// <remarks>
    /// Metric is exposed as <see cref="ObservableGauge{T}"/> with value being <see cref="long"/>.
    /// </remarks>
    public const string Count = "rcache.entries";

    /// <summary>
    /// Gets the gauge of elements compacted in the cache.
    /// </summary>
    /// <remarks>
    /// Metric is exposed as <see cref="Histogram{T}"/> with value being <see cref="long"/>.
    /// </remarks>
    public const string Compacted = "rcache.compacted_entries";
}

[RussKie]

API Review recording: https://youtu.be/H5srJ2tz1vM?t=64