1 //------------------------------------------------------------------------------ 2 // <copyright file="QueryCacheManager.cs" company="Microsoft"> 3 // Copyright (c) Microsoft Corporation. All rights reserved. 4 // </copyright> 5 // 6 // @owner Microsoft 7 // @backupOwner Microsoft 8 //------------------------------------------------------------------------------ 9 10 namespace System.Data.Common.QueryCache 11 { 12 using System; 13 using System.Collections.Generic; 14 using System.Data.EntityClient; 15 using System.Data.Metadata.Edm; 16 using System.Data.Objects.Internal; 17 using System.Diagnostics; 18 using System.Threading; 19 using System.Data.Common.Internal.Materialization; 20 using System.Data.Entity.Util; 21 22 /// <summary> 23 /// Provides Query Execution Plan Caching Service 24 /// </summary> 25 /// <remarks> 26 /// Thread safe. 27 /// Dispose <b>must</b> be called as there is no finalizer for this class 28 /// </remarks> 29 internal class QueryCacheManager : IDisposable 30 { 31 #region Constants/Default values for configuration parameters 32 33 /// <summary> 34 /// Default high mark for starting sweeping process 35 /// default value: 80% of MaxNumberOfEntries 36 /// </summary> 37 const float DefaultHighMarkPercentageFactor = 0.8f; // 80% of MaxLimit 38 39 /// <summary> 40 /// Recycler timer period 41 /// </summary> 42 const int DefaultRecyclerPeriodInMilliseconds = 60 * 1000; 43 44 #endregion 45 46 #region Fields 47 48 /// <summary> 49 /// cache lock object 50 /// </summary> 51 private readonly object _cacheDataLock = new object(); 52 53 /// <summary> 54 /// cache data 55 /// </summary> 56 private readonly Dictionary<QueryCacheKey, QueryCacheEntry> _cacheData = new Dictionary<QueryCacheKey, QueryCacheEntry>(32); 57 58 /// <summary> 59 /// soft maximum number of entries in the cache 60 /// </summary> 61 private readonly int _maxNumberOfEntries; 62 63 /// <summary> 64 /// high mark of the number of entries to trigger the sweeping process 65 /// </summary> 66 private readonly int _sweepingTriggerHighMark; 67 68 /// <summary> 69 /// Eviction timer 70 /// </summary> 71 private readonly EvictionTimer _evictionTimer; 72 73 #endregion 74 75 #region Construction and Initialization 76 77 /// <summary> 78 /// Constructs a new Query Cache Manager instance, with default values for all 'configurable' parameters. 79 /// </summary> 80 /// <returns>A new instance of <see cref="QueryCacheManager"/> configured with default entry count, load factor and recycle period</returns> Create()81 internal static QueryCacheManager Create() 82 { 83 return new QueryCacheManager(AppSettings.QueryCacheSize, DefaultHighMarkPercentageFactor, DefaultRecyclerPeriodInMilliseconds); 84 } 85 86 /// <summary> 87 /// Cache Constructor 88 /// </summary> 89 /// <param name="maximumSize"> 90 /// Maximum number of entries that the cache should contain. 91 /// </param> 92 /// <param name="loadFactor"> 93 /// The number of entries that must be present, as a percentage, before entries should be removed 94 /// according to the eviction policy. 95 /// Must be greater than 0 and less than or equal to 1.0 96 /// </param> 97 /// <param name="recycleMillis"> 98 /// The interval, in milliseconds, at which the number of entries will be compared to the load factor 99 /// and eviction carried out if necessary. 100 /// </param> QueryCacheManager(int maximumSize, float loadFactor, int recycleMillis)101 private QueryCacheManager(int maximumSize, float loadFactor, int recycleMillis) 102 { 103 Debug.Assert(maximumSize > 0, "Maximum size must be greater than zero"); 104 Debug.Assert(loadFactor > 0 && loadFactor <= 1, "Load factor must be greater than 0.0 and less than or equal to 1.0"); 105 Debug.Assert(recycleMillis >= 0, "Recycle period in milliseconds must not be negative"); 106 107 // 108 // Load hardcoded defaults 109 // 110 this._maxNumberOfEntries = maximumSize; 111 112 // 113 // set sweeping high mark trigger value 114 // 115 this._sweepingTriggerHighMark = (int)(_maxNumberOfEntries * loadFactor); 116 117 // 118 // Initialize Recycler 119 // 120 this._evictionTimer = new EvictionTimer(this, recycleMillis); 121 } 122 123 #endregion 124 125 #region 'External' interface 126 /// <summary> 127 /// Adds new entry to the cache using "abstract" cache context and 128 /// value; returns an existing entry if the key is already in the 129 /// dictionary. 130 /// </summary> 131 /// <param name="inQueryCacheEntry"></param> 132 /// <param name="outQueryCacheEntry"> 133 /// The existing entry in the dicitionary if already there; 134 /// inQueryCacheEntry if none was found and inQueryCacheEntry 135 /// was added instead. 136 /// </param> 137 /// <returns>true if the output entry was already found; false if it had to be added.</returns> TryLookupAndAdd(QueryCacheEntry inQueryCacheEntry, out QueryCacheEntry outQueryCacheEntry)138 internal bool TryLookupAndAdd(QueryCacheEntry inQueryCacheEntry, out QueryCacheEntry outQueryCacheEntry) 139 { 140 Debug.Assert(null != inQueryCacheEntry, "qEntry must not be null"); 141 142 outQueryCacheEntry = null; 143 144 lock (_cacheDataLock) 145 { 146 if (!_cacheData.TryGetValue(inQueryCacheEntry.QueryCacheKey, out outQueryCacheEntry)) 147 { 148 // 149 // add entry to cache data 150 // 151 _cacheData.Add(inQueryCacheEntry.QueryCacheKey, inQueryCacheEntry); 152 if (_cacheData.Count > _sweepingTriggerHighMark) 153 { 154 _evictionTimer.Start(); 155 } 156 157 return false; 158 } 159 else 160 { 161 outQueryCacheEntry.QueryCacheKey.UpdateHit(); 162 163 return true; 164 } 165 } 166 } 167 168 /// <summary> 169 /// Lookup service for a cached value. 170 /// </summary> 171 internal bool TryCacheLookup<TK, TE>(TK key, out TE value) 172 where TK : QueryCacheKey 173 { 174 Debug.Assert(null != key, "key must not be null"); 175 176 value = default(TE); 177 178 // 179 // invoke internal lookup 180 // 181 QueryCacheEntry qEntry = null; 182 bool bHit = TryInternalCacheLookup(key, out qEntry); 183 184 // 185 // if it is a hit, 'extract' the entry strong type cache value 186 // 187 if (bHit) 188 { 189 value = (TE)qEntry.GetTarget(); 190 } 191 192 return bHit; 193 } 194 195 /// <summary> 196 /// Clears the Cache 197 /// </summary> Clear()198 internal void Clear() 199 { 200 lock (_cacheDataLock) 201 { 202 _cacheData.Clear(); 203 } 204 } 205 #endregion 206 207 #region Private Members 208 209 /// <summary> 210 /// lookup service 211 /// </summary> 212 /// <param name="queryCacheKey"></param> 213 /// <param name="queryCacheEntry"></param> 214 /// <returns>true if cache hit, false if cache miss</returns> TryInternalCacheLookup( QueryCacheKey queryCacheKey, out QueryCacheEntry queryCacheEntry )215 private bool TryInternalCacheLookup( QueryCacheKey queryCacheKey, out QueryCacheEntry queryCacheEntry ) 216 { 217 Debug.Assert(null != queryCacheKey, "queryCacheKey must not be null"); 218 219 queryCacheEntry = null; 220 221 bool bHit = false; 222 223 // 224 // lock the cache for the minimal possible period 225 // 226 lock (_cacheDataLock) 227 { 228 bHit = _cacheData.TryGetValue(queryCacheKey, out queryCacheEntry); 229 } 230 231 // 232 // if cache hit 233 // 234 if (bHit) 235 { 236 // 237 // update hit mark in cache key 238 // 239 queryCacheEntry.QueryCacheKey.UpdateHit(); 240 } 241 242 return bHit; 243 } 244 245 246 /// <summary> 247 /// Recycler handler. This method is called directly by the eviction timer. 248 /// It should take no action beyond invoking the <see cref="SweepCache"/> method on the 249 /// cache manager instance passed as <paramref name="state"/>. 250 /// </summary> 251 /// <param name="state">The cache manager instance on which the 'recycle' handler should be invoked</param> CacheRecyclerHandler(object state)252 private static void CacheRecyclerHandler(object state) 253 { 254 ((QueryCacheManager)state).SweepCache(); 255 } 256 257 /// <summary> 258 /// Aging factor 259 /// </summary> 260 private static readonly int[] _agingFactor = {1,1,2,4,8,16}; 261 private static readonly int AgingMaxIndex = _agingFactor.Length - 1; 262 263 /// <summary> 264 /// Sweeps the cache removing old unused entries. 265 /// This method implements the query cache eviction policy. 266 /// </summary> SweepCache()267 private void SweepCache() 268 { 269 if (!this._evictionTimer.Suspend()) 270 { 271 // Return of false from .Suspend means that the manager and timer have been disposed. 272 return; 273 } 274 275 bool disabledEviction = false; 276 lock (_cacheDataLock) 277 { 278 // 279 // recycle only if entries exceeds the high mark factor 280 // 281 if (_cacheData.Count > _sweepingTriggerHighMark) 282 { 283 // 284 // sweep the cache 285 // 286 uint evictedEntriesCount = 0; 287 List<QueryCacheKey> cacheKeys = new List<QueryCacheKey>(_cacheData.Count); 288 cacheKeys.AddRange(_cacheData.Keys); 289 for (int i = 0; i < cacheKeys.Count; i++) 290 { 291 // 292 // if entry was not used in the last time window, then evict the entry 293 // 294 if (0 == cacheKeys[i].HitCount) 295 { 296 _cacheData.Remove(cacheKeys[i]); 297 evictedEntriesCount++; 298 } 299 // 300 // otherwise, age the entry in a progressive scheme 301 // 302 else 303 { 304 int agingIndex = unchecked(cacheKeys[i].AgingIndex + 1); 305 if (agingIndex > AgingMaxIndex) 306 { 307 agingIndex = AgingMaxIndex; 308 } 309 cacheKeys[i].AgingIndex = agingIndex; 310 cacheKeys[i].HitCount = cacheKeys[i].HitCount >> _agingFactor[agingIndex]; 311 } 312 } 313 } 314 else 315 { 316 _evictionTimer.Stop(); 317 disabledEviction = true; 318 } 319 } 320 321 if (!disabledEviction) 322 { 323 this._evictionTimer.Resume(); 324 } 325 } 326 327 #endregion 328 329 #region IDisposable Members 330 331 /// <summary> 332 /// Dispose instance 333 /// </summary> 334 /// <remarks>Dispose <b>must</b> be called as there are no finalizers for this class</remarks> Dispose()335 public void Dispose() 336 { 337 // Technically, calling GC.SuppressFinalize is not required because the class does not 338 // have a finalizer, but it does no harm, protects against the case where a finalizer is added 339 // in the future, and prevents an FxCop warning. 340 GC.SuppressFinalize(this); 341 if (this._evictionTimer.Stop()) 342 { 343 this.Clear(); 344 } 345 } 346 347 #endregion 348 349 /// <summary> 350 /// Periodically invokes cache cleanup logic on a specified <see cref="QueryCacheManager"/> instance, 351 /// and allows this periodic callback to be suspended, resumed or stopped in a thread-safe way. 352 /// </summary> 353 private sealed class EvictionTimer 354 { 355 /// <summary>Used to control multi-threaded accesses to this instance</summary> 356 private readonly object _sync = new object(); 357 358 /// <summary>The required interval between invocations of the cache cleanup logic</summary> 359 private readonly int _period; 360 361 /// <summary>The underlying QueryCacheManger that the callback will act on</summary> 362 private readonly QueryCacheManager _cacheManager; 363 364 /// <summary>The underlying <see cref="Timer"/> that implements the periodic callback</summary> 365 private Timer _timer; 366 EvictionTimer(QueryCacheManager cacheManager, int recyclePeriod)367 internal EvictionTimer(QueryCacheManager cacheManager, int recyclePeriod) 368 { 369 this._cacheManager = cacheManager; 370 this._period = recyclePeriod; 371 } 372 Start()373 internal void Start() 374 { 375 lock (_sync) 376 { 377 if (_timer == null) 378 { 379 this._timer = new Timer(QueryCacheManager.CacheRecyclerHandler, _cacheManager, _period, _period); 380 } 381 } 382 } 383 384 /// <summary> 385 /// Permanently stops the eviction timer. 386 /// It will no longer generate periodic callbacks and further calls to <see cref="Suspend"/>, <see cref="Resume"/>, or <see cref="Stop"/>, 387 /// though thread-safe, will have no effect. 388 /// </summary> 389 /// <returns> 390 /// If this eviction timer has already been stopped (using the <see cref="Stop"/> method), returns <c>false</c>; 391 /// otherwise, returns <c>true</c> to indicate that the call successfully stopped and cleaned up the underlying timer instance. 392 /// </returns> 393 /// <remarks> 394 /// Thread safe. May be called regardless of the current state of the eviction timer. 395 /// Once stopped, an eviction timer cannot be restarted with the <see cref="Resume"/> method. 396 /// </remarks> Stop()397 internal bool Stop() 398 { 399 lock (_sync) 400 { 401 if (this._timer != null) 402 { 403 this._timer.Dispose(); 404 this._timer = null; 405 return true; 406 } 407 else 408 { 409 return false; 410 } 411 } 412 } 413 414 /// <summary> 415 /// Pauses the operation of the eviction timer. 416 /// </summary> 417 /// <returns> 418 /// If this eviction timer has already been stopped (using the <see cref="Stop"/> method), returns <c>false</c>; 419 /// otherwise, returns <c>true</c> to indicate that the call successfully suspended the inderlying <see cref="Timer"/> 420 /// and no further periodic callbacks will be generated until the <see cref="Resume"/> method is called. 421 /// </returns> 422 /// <remarks> 423 /// Thread-safe. May be called regardless of the current state of the eviction timer. 424 /// Once suspended, an eviction timer may be resumed or stopped. 425 /// </remarks> Suspend()426 internal bool Suspend() 427 { 428 lock (_sync) 429 { 430 if (this._timer != null) 431 { 432 this._timer.Change(Timeout.Infinite, Timeout.Infinite); 433 return true; 434 } 435 else 436 { 437 return false; 438 } 439 } 440 } 441 442 /// <summary> 443 /// Causes this eviction timer to generate periodic callbacks, provided it has not been permanently stopped (using the <see cref="Stop"/> method). 444 /// </summary> 445 /// <remarks> 446 /// Thread-safe. May be called regardless of the current state of the eviction timer. 447 /// </remarks> Resume()448 internal void Resume() 449 { 450 lock (_sync) 451 { 452 if (this._timer != null) 453 { 454 this._timer.Change(this._period, this._period); 455 } 456 } 457 } 458 } 459 } 460 } 461