| | | 1 | | using System; |
| | | 2 | | using System.Collections.Concurrent; |
| | | 3 | | using System.Collections.Generic; |
| | | 4 | | using System.Threading; |
| | | 5 | | using System.Threading.Tasks; |
| | | 6 | | |
| | | 7 | | namespace AmbientServices; |
| | | 8 | | |
| | | 9 | | /// <summary> |
| | | 10 | | /// Default in-process implementation of <see cref="IAmbientAtomicCache"/> using concurrent dictionaries and optimistic |
| | | 11 | | /// </summary> |
| | | 12 | | /// <remarks> |
| | | 13 | | /// <pitch>The zero-configuration atomic cache used unless overridden: a single-process realization (<see cref="IsShared |
| | | 14 | | /// <pledge><see cref="IAmbientAtomicCache"/></pledge> |
| | | 15 | | /// <pledge>Optimistic add/update retries are capped at thirty seconds of <see cref="AmbientClock"/> time, shortened fur |
| | | 16 | | /// <pledge>Because <see cref="IsShared"/> is false, disposable values are permitted, and dispose responsibility is infe |
| | | 17 | | /// <plan> |
| | | 18 | | /// One <see cref="ConcurrentDictionary{TKey,TValue}"/> holds both operation families, with single-character storage-key |
| | | 19 | | /// Installs are compare-and-swap loops over TryAdd/TryUpdate: factories run outside any lock, losers are disposed via a |
| | | 20 | | /// Disposal is driven off a type test taken when the entry is built, so the cache disposes a losing factory result, a r |
| | | 21 | | /// A displaced versioned entry is disposed once, awaited, outside the dictionary rather than inside an update delegate, |
| | | 22 | | /// Caller timeouts are realized by linking the caller's token to an <see cref="AmbientCancellationTokenSource"/> (an al |
| | | 23 | | /// Size is bounded by the same timed/untimed queue bookkeeping, cadence-driven ejection, and bounded <see cref="Clear"/ |
| | | 24 | | /// Trade-offs: no cross-process sharing or durability, approximate size bounds, and duplicate factory work under conten |
| | | 25 | | /// </plan> |
| | | 26 | | /// <priority> |
| | | 27 | | /// <see cref="IAmbientAtomicCache"/> |
| | | 28 | | /// 1. Sharing the local cache's bookkeeping over tuning its own: size bounding reuses <see cref="BasicAmbientLocalCache |
| | | 29 | | /// </priority> |
| | | 30 | | /// <para>Bounded size is enforced by ejecting timed and untimed bookkeeping rows on a configurable cadence. Settings u |
| | | 31 | | /// <para>Expiration comparisons and optimistic retry deadlines use <see cref="AmbientClock"/> so tests can pause or ski |
| | | 32 | | /// <para><see cref="Clear"/> snapshots the cache and ejects each entry in a bounded number of passes. Concurrent insta |
| | | 33 | | /// </remarks> |
| | | 34 | | [DefaultAmbientService] |
| | | 35 | | internal class BasicAmbientAtomicCache : IAmbientAtomicCache |
| | | 36 | | { |
| | | 37 | | /// <summary>Distinct one-char prefix so unversioned and versioned logical keys never share one dictionary slot.</su |
| | | 38 | | private const string UnversionedStorageKeyPrefix = "N"; |
| | | 39 | | |
| | | 40 | | /// <summary>Distinct one-char prefix so unversioned and versioned logical keys never share one dictionary slot.</su |
| | | 41 | | private const string VersionedStorageKeyPrefix = "V"; |
| | | 42 | | |
| | | 43 | | /// <summary>Wall-clock budget for optimistic <see cref="GetOrAdd{T}"/> / <see cref="AddOrUpdate{T}"/> CAS-style ret |
| | | 44 | | private static readonly TimeSpan MaxOptimisticRetryDuration = TimeSpan.FromSeconds(30); |
| | | 45 | | |
| | | 46 | | private const string OptimisticRetryBudgetExceededMessage = "The atomic cache optimistic retry budget was exceeded." |
| | | 47 | | |
| | | 48 | | /// <summary>Caps stale-queue draining per eject call so a pathological queue cannot spin unbounded in one async con |
| | | 49 | | private const int MaxEjectQueueDrainSteps = 65536; |
| | | 50 | | |
| | | 51 | | /// <summary>Maximum snapshot-and-eject passes in <see cref="Clear"/> before giving up on reaching an empty cache.</ |
| | | 52 | | private const int MaxClearPasses = 8; |
| | | 53 | | |
| | | 54 | | private static readonly AmbientService<IAmbientSettingsSet> _Settings = Ambient.GetService<IAmbientSettingsSet>(); |
| | | 55 | | |
| | | 56 | | private readonly IAmbientSetting<int> _callFrequencyToEject; |
| | | 57 | | private readonly IAmbientSetting<int> _countToEject; |
| | | 58 | | private readonly IAmbientSetting<int> _minCacheEntries; |
| | | 59 | | private int _expireCount; |
| | | 60 | | private ConcurrentQueue<TimedQueueEntry> _timedQueue = new(); // interlocked (make readonly when we no longer supp |
| | | 61 | | private ConcurrentQueue<string> _untimedQueue = new(); // interlocked (make readonly when we no longer supp |
| | | 62 | | private readonly ConcurrentDictionary<string, CacheEntry> _cache = new(); |
| | | 63 | | private readonly ConcurrentDictionary<string, VersionCounter> _versionCounters = new(); |
| | | 64 | | |
| | | 65 | | private sealed class VersionCounter |
| | | 66 | | { |
| | | 67 | | internal long Last; |
| | | 68 | | } |
| | | 69 | | |
| | | 70 | | public BasicAmbientAtomicCache() |
| | | 71 | | : this(_Settings.Local) |
| | | 72 | | { |
| | | 73 | | } |
| | | 74 | | |
| | | 75 | | public BasicAmbientAtomicCache(IAmbientSettingsSet? settings) |
| | | 76 | | { |
| | | 77 | | _callFrequencyToEject = AmbientSettings.GetSetting<int>(settings, nameof(BasicAmbientAtomicCache) + "-EjectFrequ |
| | | 78 | | _countToEject = AmbientSettings.GetSetting<int>(settings, nameof(BasicAmbientAtomicCache) + "-MaximumItemCount", |
| | | 79 | | _minCacheEntries = AmbientSettings.GetSetting<int>(settings, nameof(BasicAmbientAtomicCache) + "-MinimumItemCoun |
| | | 80 | | } |
| | | 81 | | |
| | | 82 | | private static string GetUnversionedStorageKey(string itemKey) => UnversionedStorageKeyPrefix + itemKey; |
| | | 83 | | |
| | | 84 | | private static string GetVersionedStorageKey(string itemKey) => VersionedStorageKeyPrefix + itemKey; |
| | | 85 | | |
| | | 86 | | private struct TimedQueueEntry |
| | | 87 | | { |
| | | 88 | | public string Key; |
| | | 89 | | public DateTime Expiration; |
| | | 90 | | } |
| | | 91 | | |
| | | 92 | | private static bool ShouldDisposeWhenDiscarding(object entry) |
| | | 93 | | { |
| | | 94 | | return entry is IAsyncDisposable || entry is IDisposable; |
| | | 95 | | } |
| | | 96 | | |
| | | 97 | | private readonly struct TimeoutCancellationRegistration : IDisposable |
| | | 98 | | { |
| | | 99 | | public CancellationToken Token { get; } |
| | | 100 | | private readonly IDisposable? _cleanup; |
| | | 101 | | |
| | | 102 | | public static TimeoutCancellationRegistration Create(TimeSpan? timeout, CancellationToken cancel) |
| | | 103 | | { |
| | | 104 | | if (timeout is not TimeSpan to) |
| | | 105 | | { |
| | | 106 | | return new TimeoutCancellationRegistration(null, cancel); |
| | | 107 | | } |
| | | 108 | | |
| | | 109 | | // System.Timers.Timer rejects non-positive intervals; use an already-cancelled CTS for "elapsed now" budget |
| | | 110 | | if (to <= TimeSpan.Zero) |
| | | 111 | | { |
| | | 112 | | #pragma warning disable CA2000 // dispose ownership transferred to TimeoutCancellationRegistration or linked CTS |
| | | 113 | | CancellationTokenSource immediateTimeout = new(); |
| | | 114 | | #pragma warning restore CA2000 |
| | | 115 | | immediateTimeout.Cancel(); |
| | | 116 | | if (!cancel.CanBeCanceled) |
| | | 117 | | { |
| | | 118 | | return new TimeoutCancellationRegistration(immediateTimeout, immediateTimeout.Token); |
| | | 119 | | } |
| | | 120 | | |
| | | 121 | | CancellationTokenSource linkedImmediateTimeout = CancellationTokenSource.CreateLinkedTokenSource(cancel, |
| | | 122 | | return new TimeoutCancellationRegistration(linkedImmediateTimeout, linkedImmediateTimeout.Token); |
| | | 123 | | } |
| | | 124 | | |
| | | 125 | | AmbientCancellationTokenSource ambientTimeout = new(to); |
| | | 126 | | if (!cancel.CanBeCanceled) |
| | | 127 | | { |
| | | 128 | | return new TimeoutCancellationRegistration(ambientTimeout, ambientTimeout.Token); |
| | | 129 | | } |
| | | 130 | | |
| | | 131 | | CancellationTokenSource linkedAmbientTimeout = CancellationTokenSource.CreateLinkedTokenSource(cancel, ambie |
| | | 132 | | return new TimeoutCancellationRegistration(new TimeoutCleanup(linkedAmbientTimeout, ambientTimeout), linkedA |
| | | 133 | | } |
| | | 134 | | |
| | | 135 | | private TimeoutCancellationRegistration(IDisposable? cleanup, CancellationToken token) |
| | | 136 | | { |
| | | 137 | | Token = token; |
| | | 138 | | _cleanup = cleanup; |
| | | 139 | | } |
| | | 140 | | |
| | | 141 | | public void Dispose() => _cleanup?.Dispose(); |
| | | 142 | | } |
| | | 143 | | |
| | | 144 | | private sealed class TimeoutCleanup : IDisposable |
| | | 145 | | { |
| | | 146 | | private readonly CancellationTokenSource _linked; |
| | | 147 | | private readonly AmbientCancellationTokenSource _ambient; |
| | | 148 | | |
| | 2 | 149 | | public TimeoutCleanup(CancellationTokenSource linked, AmbientCancellationTokenSource ambient) |
| | | 150 | | { |
| | 2 | 151 | | _linked = linked; |
| | 2 | 152 | | _ambient = ambient; |
| | 2 | 153 | | } |
| | | 154 | | |
| | | 155 | | public void Dispose() |
| | | 156 | | { |
| | 2 | 157 | | _linked.Dispose(); |
| | 2 | 158 | | _ambient.Dispose(); |
| | 2 | 159 | | } |
| | | 160 | | } |
| | | 161 | | |
| | | 162 | | private class CacheEntry |
| | | 163 | | { |
| | | 164 | | public bool DisposeWhenDiscarding { get; private set; } |
| | | 165 | | public string Key; |
| | | 166 | | public DateTime? Expiration; |
| | | 167 | | public object Entry; |
| | | 168 | | /// <summary>Monotonic revision for versioned storage keys; 0 for non-versioned atomic entries.</summary> |
| | | 169 | | public long MonotonicRevision; |
| | | 170 | | |
| | | 171 | | public CacheEntry(string key, DateTime? expiration, object entry, bool disposeWhenDiscarding, long monotonicRevi |
| | | 172 | | { |
| | | 173 | | DisposeWhenDiscarding = disposeWhenDiscarding; |
| | | 174 | | Key = key; |
| | | 175 | | Expiration = expiration; |
| | | 176 | | Entry = entry; |
| | | 177 | | MonotonicRevision = monotonicRevision; |
| | | 178 | | } |
| | | 179 | | public async ValueTask Dispose() |
| | | 180 | | { |
| | | 181 | | // if the entry is disposable, dispose it after removing it |
| | | 182 | | if (DisposeWhenDiscarding) await DisposeDiscardedValue(Entry); |
| | | 183 | | } |
| | | 184 | | } |
| | | 185 | | |
| | | 186 | | private static DateTime? NormalizeExpiresInstant(DateTime? expires) |
| | | 187 | | { |
| | | 188 | | if (expires == null) return null; |
| | | 189 | | DateTime e = expires.Value; |
| | | 190 | | if (e.Kind == DateTimeKind.Local) return e.ToUniversalTime(); |
| | | 191 | | if (e.Kind == DateTimeKind.Unspecified) return DateTime.SpecifyKind(e, DateTimeKind.Utc); |
| | | 192 | | return e; |
| | | 193 | | } |
| | | 194 | | |
| | | 195 | | private static bool IsExpired(CacheEntry entry, DateTime nowUtc) => entry.Expiration < nowUtc; |
| | | 196 | | |
| | | 197 | | private static DateTime? ComputeActualExpiration(TimeSpan? maxCacheDuration, DateTime? expiration, DateTime utcNow) |
| | | 198 | | { |
| | | 199 | | if (maxCacheDuration < TimeSpan.FromTicks(0)) return null; |
| | | 200 | | DateTime? actualExpiration = null; |
| | | 201 | | if (maxCacheDuration != null) actualExpiration = utcNow.Add(maxCacheDuration.Value); |
| | | 202 | | if (expiration != null) |
| | | 203 | | { |
| | | 204 | | DateTime exp = expiration.Value; |
| | | 205 | | if (exp.Kind == DateTimeKind.Local) exp = exp.ToUniversalTime(); |
| | | 206 | | else if (exp.Kind == DateTimeKind.Unspecified) exp = DateTime.SpecifyKind(exp, DateTimeKind.Utc); |
| | | 207 | | if (actualExpiration == null || exp < actualExpiration) actualExpiration = exp; |
| | | 208 | | } |
| | | 209 | | return actualExpiration; |
| | | 210 | | } |
| | | 211 | | |
| | | 212 | | private static DateTime ComputeOptimisticRetryDeadlineUtc(TimeSpan? operationTimeout) |
| | | 213 | | { |
| | | 214 | | DateTime utcNow = AmbientClock.UtcNow; |
| | | 215 | | DateTime deadline = utcNow.Add(MaxOptimisticRetryDuration); |
| | | 216 | | if (operationTimeout is TimeSpan to) |
| | | 217 | | { |
| | | 218 | | DateTime byCallerTimeout = utcNow.Add(to); |
| | | 219 | | if (byCallerTimeout < deadline) |
| | | 220 | | { |
| | | 221 | | deadline = byCallerTimeout; |
| | | 222 | | } |
| | | 223 | | } |
| | | 224 | | |
| | | 225 | | return deadline; |
| | | 226 | | } |
| | | 227 | | |
| | | 228 | | private static void ThrowIfOptimisticRetryDeadlineExceeded(DateTime deadlineUtc) |
| | | 229 | | { |
| | | 230 | | if (AmbientClock.UtcNow >= deadlineUtc) |
| | | 231 | | throw new InvalidOperationException(OptimisticRetryBudgetExceededMessage); |
| | | 232 | | } |
| | | 233 | | |
| | | 234 | | /// <summary> |
| | | 235 | | /// If the token is already canceled only because the optimistic-retry window elapsed (ambient clock), |
| | | 236 | | /// throw <see cref="InvalidOperationException"/> instead of <see cref="OperationCanceledException"/> so callers |
| | | 237 | | /// do not treat policy timeout as cooperative cancellation. |
| | | 238 | | /// </summary> |
| | | 239 | | private static void ThrowIfCancellationUnlessRetryDeadlineExceeded(DateTime optimisticRetryDeadlineUtc, Cancellation |
| | | 240 | | { |
| | | 241 | | if (!effectiveCancel.IsCancellationRequested) return; |
| | | 242 | | ThrowIfOptimisticRetryDeadlineExceeded(optimisticRetryDeadlineUtc); |
| | | 243 | | effectiveCancel.ThrowIfCancellationRequested(); |
| | | 244 | | } |
| | | 245 | | |
| | | 246 | | private void EnqueueExpiration(string storageKey, DateTime? actualExpiration) |
| | | 247 | | { |
| | | 248 | | if (actualExpiration == null) |
| | | 249 | | { |
| | | 250 | | _untimedQueue.Enqueue(storageKey); |
| | | 251 | | } |
| | | 252 | | else |
| | | 253 | | { |
| | | 254 | | _timedQueue.Enqueue(new TimedQueueEntry { Key = storageKey, Expiration = actualExpiration.Value }); |
| | | 255 | | } |
| | | 256 | | } |
| | | 257 | | |
| | | 258 | | /// <summary> |
| | | 259 | | /// Disposes a value the cache is discarding, preferring asynchronous disposal when the value implements both interf |
| | | 260 | | /// </summary> |
| | | 261 | | private static async ValueTask DisposeDiscardedValue(object value) |
| | | 262 | | { |
| | | 263 | | if (value is IAsyncDisposable asyncDisposable) await asyncDisposable.DisposeAsync(); |
| | | 264 | | else if (value is IDisposable disposable) disposable.Dispose(); |
| | | 265 | | } |
| | | 266 | | |
| | | 267 | | /// <inheritdoc/> |
| | | 268 | | public bool IsShared => false; |
| | | 269 | | |
| | | 270 | | /// <inheritdoc/> |
| | | 271 | | public async ValueTask<T> GetOrAdd<T>(string itemKey, Func<ValueTask<(T Item, DateTime? Expires)>> create, TimeSpan? |
| | | 272 | | { |
| | | 273 | | using TimeoutCancellationRegistration timeoutRegistration = TimeoutCancellationRegistration.Create(timeout, canc |
| | | 274 | | CancellationToken effectiveCancel = timeoutRegistration.Token; |
| | | 275 | | string storageKey = GetUnversionedStorageKey(itemKey); |
| | | 276 | | DateTime optimisticRetryDeadlineUtc = ComputeOptimisticRetryDeadlineUtc(timeout); |
| | | 277 | | while (AmbientClock.UtcNow < optimisticRetryDeadlineUtc) |
| | | 278 | | { |
| | | 279 | | ThrowIfOptimisticRetryDeadlineExceeded(optimisticRetryDeadlineUtc); |
| | | 280 | | ThrowIfCancellationUnlessRetryDeadlineExceeded(optimisticRetryDeadlineUtc, effectiveCancel); |
| | | 281 | | DateTime now = AmbientClock.UtcNow; |
| | | 282 | | if (_cache.TryGetValue(storageKey, out CacheEntry? entry)) |
| | | 283 | | { |
| | | 284 | | if (!IsExpired(entry, now)) |
| | | 285 | | { |
| | | 286 | | if (refresh != null) |
| | | 287 | | { |
| | | 288 | | DateTime newExpiration = now.Add(refresh.Value); |
| | | 289 | | entry.Expiration = newExpiration; |
| | | 290 | | _timedQueue.Enqueue(new TimedQueueEntry { Key = storageKey, Expiration = newExpiration }); |
| | | 291 | | } |
| | | 292 | | await EjectIfNeeded(); |
| | | 293 | | return (T)entry.Entry; |
| | | 294 | | } |
| | | 295 | | await EjectEntry(entry); |
| | | 296 | | ThrowIfOptimisticRetryDeadlineExceeded(optimisticRetryDeadlineUtc); |
| | | 297 | | } |
| | | 298 | | else |
| | | 299 | | { |
| | | 300 | | await EjectIfNeeded(); |
| | | 301 | | ThrowIfOptimisticRetryDeadlineExceeded(optimisticRetryDeadlineUtc); |
| | | 302 | | } |
| | | 303 | | |
| | | 304 | | (T created, DateTime? expires) = await create(); |
| | | 305 | | ThrowIfOptimisticRetryDeadlineExceeded(optimisticRetryDeadlineUtc); |
| | | 306 | | DateTime? actualExpiration = NormalizeExpiresInstant(expires); |
| | | 307 | | DateTime nowAfterCreate = AmbientClock.UtcNow; |
| | | 308 | | if (actualExpiration < nowAfterCreate) |
| | | 309 | | { |
| | | 310 | | await DisposeDiscardedValue(created); |
| | | 311 | | ThrowIfOptimisticRetryDeadlineExceeded(optimisticRetryDeadlineUtc); |
| | | 312 | | ThrowIfCancellationUnlessRetryDeadlineExceeded(optimisticRetryDeadlineUtc, effectiveCancel); |
| | | 313 | | continue; |
| | | 314 | | } |
| | | 315 | | |
| | | 316 | | CacheEntry newEntry = new(storageKey, actualExpiration, created, ShouldDisposeWhenDiscarding(created)); |
| | | 317 | | if (_cache.TryAdd(storageKey, newEntry)) |
| | | 318 | | { |
| | | 319 | | EnqueueExpiration(storageKey, actualExpiration); |
| | | 320 | | await EjectIfNeeded(); |
| | | 321 | | return created; |
| | | 322 | | } |
| | | 323 | | |
| | | 324 | | await DisposeDiscardedValue(created); |
| | | 325 | | } |
| | | 326 | | |
| | | 327 | | throw new InvalidOperationException(OptimisticRetryBudgetExceededMessage); |
| | | 328 | | } |
| | | 329 | | |
| | | 330 | | /// <inheritdoc/> |
| | | 331 | | public async ValueTask<T> AddOrUpdate<T>(string itemKey, Func<ValueTask<(T Item, DateTime? Expires)>> create, Func<T |
| | | 332 | | { |
| | | 333 | | using TimeoutCancellationRegistration timeoutRegistration = TimeoutCancellationRegistration.Create(timeout, canc |
| | | 334 | | CancellationToken effectiveCancel = timeoutRegistration.Token; |
| | | 335 | | string storageKey = GetUnversionedStorageKey(itemKey); |
| | | 336 | | DateTime optimisticRetryDeadlineUtc = ComputeOptimisticRetryDeadlineUtc(timeout); |
| | | 337 | | while (AmbientClock.UtcNow < optimisticRetryDeadlineUtc) |
| | | 338 | | { |
| | | 339 | | ThrowIfOptimisticRetryDeadlineExceeded(optimisticRetryDeadlineUtc); |
| | | 340 | | ThrowIfCancellationUnlessRetryDeadlineExceeded(optimisticRetryDeadlineUtc, effectiveCancel); |
| | | 341 | | DateTime now = AmbientClock.UtcNow; |
| | | 342 | | if (_cache.TryGetValue(storageKey, out CacheEntry? existing)) |
| | | 343 | | { |
| | | 344 | | if (IsExpired(existing, now)) |
| | | 345 | | { |
| | | 346 | | await EjectEntry(existing); |
| | | 347 | | ThrowIfOptimisticRetryDeadlineExceeded(optimisticRetryDeadlineUtc); |
| | | 348 | | } |
| | | 349 | | else |
| | | 350 | | { |
| | | 351 | | T current = (T)existing.Entry; |
| | | 352 | | (T updatedItem, DateTime? expires) = await update(current); |
| | | 353 | | ThrowIfOptimisticRetryDeadlineExceeded(optimisticRetryDeadlineUtc); |
| | | 354 | | DateTime? actualExpiration = NormalizeExpiresInstant(expires); |
| | | 355 | | DateTime nowAfterUpdate = AmbientClock.UtcNow; |
| | | 356 | | if (actualExpiration < nowAfterUpdate) |
| | | 357 | | { |
| | | 358 | | await DisposeDiscardedValue(updatedItem); |
| | | 359 | | await EjectEntry(existing); |
| | | 360 | | ThrowIfOptimisticRetryDeadlineExceeded(optimisticRetryDeadlineUtc); |
| | | 361 | | ThrowIfCancellationUnlessRetryDeadlineExceeded(optimisticRetryDeadlineUtc, effectiveCancel); |
| | | 362 | | continue; |
| | | 363 | | } |
| | | 364 | | |
| | | 365 | | CacheEntry replacement = new(storageKey, actualExpiration, updatedItem, ShouldDisposeWhenDiscarding( |
| | | 366 | | if (_cache.TryUpdate(storageKey, replacement, existing)) |
| | | 367 | | { |
| | | 368 | | EnqueueExpiration(storageKey, actualExpiration); |
| | | 369 | | await EjectIfNeeded(); |
| | | 370 | | return updatedItem; |
| | | 371 | | } |
| | | 372 | | await DisposeDiscardedValue(updatedItem); |
| | | 373 | | continue; |
| | | 374 | | } |
| | | 375 | | } |
| | | 376 | | |
| | | 377 | | (T created, DateTime? createExpires) = await create(); |
| | | 378 | | ThrowIfOptimisticRetryDeadlineExceeded(optimisticRetryDeadlineUtc); |
| | | 379 | | DateTime? createActualExpiration = NormalizeExpiresInstant(createExpires); |
| | | 380 | | DateTime nowAfterCreate = AmbientClock.UtcNow; |
| | | 381 | | if (createActualExpiration < nowAfterCreate) |
| | | 382 | | { |
| | | 383 | | await DisposeDiscardedValue(created); |
| | | 384 | | ThrowIfOptimisticRetryDeadlineExceeded(optimisticRetryDeadlineUtc); |
| | | 385 | | ThrowIfCancellationUnlessRetryDeadlineExceeded(optimisticRetryDeadlineUtc, effectiveCancel); |
| | | 386 | | continue; |
| | | 387 | | } |
| | | 388 | | |
| | | 389 | | CacheEntry newEntry = new(storageKey, createActualExpiration, created, ShouldDisposeWhenDiscarding(created)) |
| | | 390 | | if (_cache.TryAdd(storageKey, newEntry)) |
| | | 391 | | { |
| | | 392 | | EnqueueExpiration(storageKey, createActualExpiration); |
| | | 393 | | await EjectIfNeeded(); |
| | | 394 | | return created; |
| | | 395 | | } |
| | | 396 | | |
| | | 397 | | await DisposeDiscardedValue(created); |
| | | 398 | | } |
| | | 399 | | |
| | | 400 | | throw new InvalidOperationException(OptimisticRetryBudgetExceededMessage); |
| | | 401 | | } |
| | | 402 | | |
| | | 403 | | /// <inheritdoc/> |
| | | 404 | | public async ValueTask Remove<T>(string itemKey, CancellationToken cancel = default) |
| | | 405 | | { |
| | | 406 | | if (_cache.TryRemove(GetUnversionedStorageKey(itemKey), out CacheEntry? disposeEntry)) |
| | | 407 | | { |
| | | 408 | | await disposeEntry!.Dispose(); |
| | | 409 | | } |
| | | 410 | | } |
| | | 411 | | |
| | | 412 | | /// <inheritdoc/> |
| | | 413 | | public async ValueTask VersionedRemove<T>(string itemKey, CancellationToken cancel = default) |
| | | 414 | | { |
| | | 415 | | if (_cache.TryRemove(GetVersionedStorageKey(itemKey), out CacheEntry? disposeEntry)) |
| | | 416 | | { |
| | | 417 | | await disposeEntry!.Dispose(); |
| | | 418 | | } |
| | | 419 | | } |
| | | 420 | | |
| | | 421 | | /// <inheritdoc/> |
| | | 422 | | public async ValueTask<(T? Value, long Version)> VersionedGet<T>(string itemKey, long minVersion = -1, TimeSpan? ref |
| | | 423 | | { |
| | | 424 | | string storageKey = GetVersionedStorageKey(itemKey); |
| | | 425 | | using TimeoutCancellationRegistration timeoutRegistration = TimeoutCancellationRegistration.Create(timeout, canc |
| | | 426 | | CancellationToken effectiveCancel = timeoutRegistration.Token; |
| | | 427 | | if (!_cache.TryGetValue(storageKey, out CacheEntry? entry)) |
| | | 428 | | { |
| | | 429 | | return (default, 0); |
| | | 430 | | } |
| | | 431 | | |
| | | 432 | | effectiveCancel.ThrowIfCancellationRequested(); |
| | | 433 | | DateTime now = AmbientClock.UtcNow; |
| | | 434 | | if (IsExpired(entry, now)) |
| | | 435 | | { |
| | | 436 | | await EjectEntry(entry); |
| | | 437 | | return (default, 0); |
| | | 438 | | } |
| | | 439 | | |
| | | 440 | | if (entry.MonotonicRevision < minVersion) |
| | | 441 | | { |
| | | 442 | | return (default, entry.MonotonicRevision); |
| | | 443 | | } |
| | | 444 | | |
| | | 445 | | if (refresh != null) |
| | | 446 | | { |
| | | 447 | | DateTime newExpiration = now.Add(refresh.Value); |
| | | 448 | | entry.Expiration = newExpiration; |
| | | 449 | | _timedQueue.Enqueue(new TimedQueueEntry { Key = storageKey, Expiration = newExpiration }); |
| | | 450 | | } |
| | | 451 | | await EjectIfNeeded(); |
| | | 452 | | return ((T)entry.Entry, entry.MonotonicRevision); |
| | | 453 | | } |
| | | 454 | | |
| | | 455 | | /// <inheritdoc/> |
| | | 456 | | public async ValueTask<long> VersionedPut<T>(string itemKey, T value, TimeSpan? maxCacheDuration = null, DateTime? e |
| | | 457 | | { |
| | | 458 | | if (maxCacheDuration < TimeSpan.FromTicks(0)) |
| | | 459 | | { |
| | | 460 | | await DisposeDiscardedValue(value); |
| | | 461 | | return 0; |
| | | 462 | | } |
| | | 463 | | |
| | | 464 | | string storageKey = GetVersionedStorageKey(itemKey); |
| | | 465 | | using TimeoutCancellationRegistration timeoutRegistration = TimeoutCancellationRegistration.Create(timeout, canc |
| | | 466 | | CancellationToken effectiveCancel = timeoutRegistration.Token; |
| | | 467 | | DateTime utcNow = AmbientClock.UtcNow; |
| | | 468 | | DateTime? actualExpiration = ComputeActualExpiration(maxCacheDuration, expiration, utcNow); |
| | | 469 | | if (actualExpiration < utcNow) |
| | | 470 | | { |
| | | 471 | | await DisposeDiscardedValue(value); |
| | | 472 | | return 0; |
| | | 473 | | } |
| | | 474 | | |
| | | 475 | | effectiveCancel.ThrowIfCancellationRequested(); |
| | | 476 | | |
| | | 477 | | VersionCounter vc = _versionCounters.GetOrAdd(itemKey, _ => new VersionCounter()); |
| | | 478 | | long revision = Interlocked.Increment(ref vc.Last); |
| | | 479 | | CacheEntry newEntry = new(storageKey, actualExpiration, value, ShouldDisposeWhenDiscarding(value), revision); |
| | | 480 | | // ConcurrentDictionary has no async update delegate, and its update delegate may run more than |
| | | 481 | | // once under contention — so a disposing side effect there can double-dispose. Do the compare-and-swap |
| | | 482 | | // ourselves: this displaces exactly one entry, which we then dispose once, awaited, outside the dictionary. |
| | | 483 | | CacheEntry? displaced = null; |
| | | 484 | | while (true) |
| | | 485 | | { |
| | | 486 | | if (_cache.TryGetValue(storageKey, out CacheEntry? old)) |
| | | 487 | | { |
| | | 488 | | if (_cache.TryUpdate(storageKey, newEntry, old)) |
| | | 489 | | { |
| | | 490 | | displaced = old; |
| | | 491 | | break; |
| | | 492 | | } |
| | | 493 | | } |
| | | 494 | | else if (_cache.TryAdd(storageKey, newEntry)) |
| | | 495 | | { |
| | | 496 | | break; |
| | | 497 | | } |
| | | 498 | | // another writer changed the slot first; re-read and retry |
| | | 499 | | } |
| | | 500 | | if (displaced != null) await displaced.Dispose(); |
| | | 501 | | EnqueueExpiration(storageKey, actualExpiration); |
| | | 502 | | await EjectIfNeeded(); |
| | | 503 | | return revision; |
| | | 504 | | } |
| | | 505 | | |
| | | 506 | | private async ValueTask EjectIfNeeded() |
| | | 507 | | { |
| | | 508 | | int callFrequencyToEject = _callFrequencyToEject.Value; |
| | | 509 | | if (callFrequencyToEject <= 0) |
| | | 510 | | callFrequencyToEject = 1; |
| | | 511 | | |
| | | 512 | | int countToEject = _countToEject.Value; |
| | | 513 | | // One increment per cache operation (not per inner eject round): the previous loop incremented on every |
| | | 514 | | // pressure-driven iteration which inflated the cadence counter and could spin unbounded under concurrency |
| | | 515 | | // when queue bookkeeping lagged cache entries (ConcurrentQueue.Count is approximate) or ejection could not |
| | | 516 | | // shrink the queues in one pass. |
| | | 517 | | int opSerial = Interlocked.Increment(ref _expireCount); |
| | | 518 | | bool onCadence = (opSerial % callFrequencyToEject) == 0; |
| | | 519 | | int queueSum = _untimedQueue.Count + _timedQueue.Count; |
| | | 520 | | bool overCapacity = queueSum > countToEject; |
| | | 521 | | if (!onCadence && !overCapacity) |
| | | 522 | | return; |
| | | 523 | | |
| | | 524 | | int maxRounds = Math.Max(32, Math.Min(131072, 4 + 2 * Math.Max(queueSum, countToEject + 1))); |
| | | 525 | | for (int round = 0; round < maxRounds; round++) |
| | | 526 | | { |
| | | 527 | | await EjectOneTimed(); |
| | | 528 | | await EjectOneUntimed(); |
| | | 529 | | |
| | | 530 | | queueSum = _untimedQueue.Count + _timedQueue.Count; |
| | | 531 | | if (queueSum <= countToEject) |
| | | 532 | | break; |
| | | 533 | | } |
| | | 534 | | } |
| | | 535 | | |
| | | 536 | | private async ValueTask EjectOneTimed() |
| | | 537 | | { |
| | | 538 | | // have we hit the minimum number of items? |
| | | 539 | | if (_timedQueue.Count <= _minCacheEntries.Value) return; |
| | | 540 | | // removing at least one timed item (as well as any expired items we come across) |
| | | 541 | | bool unexpiredItemEjected = false; |
| | | 542 | | int steps = 0; |
| | | 543 | | while (steps++ < MaxEjectQueueDrainSteps && _timedQueue.TryDequeue(out TimedQueueEntry qEntry)) |
| | | 544 | | { |
| | | 545 | | // Eject only when the cache still has this key with the same expiration as when the row was enqueued (other |
| | | 546 | | if (_cache.TryGetValue(qEntry.Key, out CacheEntry? entry) && qEntry.Expiration == entry.Expiration) |
| | | 547 | | { |
| | | 548 | | // remove it from the cache, even though it may not have expired yet because it's time to eject somethin |
| | | 549 | | await EjectEntry(entry); |
| | | 550 | | // fall through and check to see if the next item is already expired |
| | | 551 | | unexpiredItemEjected = true; |
| | | 552 | | } |
| | | 553 | | // stale queue row or missing cache entry: if we have already ejected an unexpired item, check for another e |
| | | 554 | | else if (!unexpiredItemEjected) |
| | | 555 | | { |
| | | 556 | | continue; |
| | | 557 | | } |
| | | 558 | | // peek at the next entry |
| | | 559 | | if (_timedQueue.TryPeek(out qEntry)) |
| | | 560 | | { |
| | | 561 | | // has this entry expired? continue looping so that we remove this one too, even though we didn't *have* |
| | | 562 | | if (qEntry.Expiration < AmbientClock.UtcNow) continue; |
| | | 563 | | // else the entry hasn't expired and we either removed an entry above or skipped this code, so we can ju |
| | | 564 | | } |
| | | 565 | | // if we get here, there is no reason to look at another timed entry |
| | | 566 | | break; |
| | | 567 | | } |
| | | 568 | | } |
| | | 569 | | |
| | | 570 | | private async ValueTask EjectOneUntimed() |
| | | 571 | | { |
| | | 572 | | // have we hit the minimum number of items? |
| | | 573 | | if (_untimedQueue.Count <= _minCacheEntries.Value) return; |
| | | 574 | | // remove one untimed entry |
| | | 575 | | int steps = 0; |
| | | 576 | | while (steps++ < MaxEjectQueueDrainSteps && _untimedQueue.TryDequeue(out string? key)) |
| | | 577 | | { |
| | | 578 | | // can we find this item in the cache? |
| | | 579 | | if (_cache.TryGetValue(key, out CacheEntry? entry)) |
| | | 580 | | { |
| | | 581 | | // is the expiration still the same (ie. untimed)? |
| | | 582 | | if (entry.Expiration == null) |
| | | 583 | | { |
| | | 584 | | // remove it from the cache |
| | | 585 | | await EjectEntry(entry); |
| | | 586 | | // fall through and stop looping |
| | | 587 | | } |
| | | 588 | | else // else the item was refreshed, so we should ignore this entry and go around again to remove anothe |
| | | 589 | | { |
| | | 590 | | continue; |
| | | 591 | | } |
| | | 592 | | } |
| | | 593 | | // else we couldn't find the entry in the cache, so just move to the next entry |
| | | 594 | | else |
| | | 595 | | { |
| | | 596 | | continue; |
| | | 597 | | } |
| | | 598 | | // if we get here, there is no reason to look at another untimed entry |
| | | 599 | | break; |
| | | 600 | | } |
| | | 601 | | } |
| | | 602 | | |
| | | 603 | | private async ValueTask EjectEntry(CacheEntry entry) |
| | | 604 | | { |
| | | 605 | | // race to remove the item from the cache--did we win the race? |
| | | 606 | | if (_cache.TryRemove(entry.Key, out CacheEntry? disposeEntry)) |
| | | 607 | | { |
| | | 608 | | await disposeEntry.Dispose(); |
| | | 609 | | } |
| | | 610 | | } |
| | | 611 | | |
| | | 612 | | /// <inheritdoc/> |
| | | 613 | | public async ValueTask Clear(CancellationToken cancel = default) |
| | | 614 | | { |
| | | 615 | | Interlocked.Exchange(ref _untimedQueue, new ConcurrentQueue<string>()); |
| | | 616 | | Interlocked.Exchange(ref _timedQueue, new ConcurrentQueue<TimedQueueEntry>()); |
| | | 617 | | _versionCounters.Clear(); |
| | | 618 | | |
| | | 619 | | for (int pass = 0; pass < MaxClearPasses; pass++) |
| | | 620 | | { |
| | | 621 | | KeyValuePair<string, CacheEntry>[] snapshot = _cache.ToArray(); |
| | | 622 | | if (snapshot.Length == 0) |
| | | 623 | | break; |
| | | 624 | | |
| | | 625 | | foreach (KeyValuePair<string, CacheEntry> kv in snapshot) |
| | | 626 | | { |
| | | 627 | | cancel.ThrowIfCancellationRequested(); |
| | | 628 | | await EjectEntry(kv.Value); |
| | | 629 | | } |
| | | 630 | | |
| | | 631 | | if (_cache.IsEmpty) |
| | | 632 | | break; |
| | | 633 | | } |
| | | 634 | | } |
| | | 635 | | } |