Caching Architecture Guide for .NET Framework Applications

 

Managing the Contents of a Cache

Summary: This chapter details the various methods available for loading data into a cache and how you should manage the data that is stored in the cache.

So far in this guide, you have seen what data to cache and where to cache it. This chapter describes other issues concerning caching management, including how to load data into a cache and how to manage the data inside the cache.

This chapter contains the following sections:

• "Loading a Cache"
• "Determining a Cache Expiration Policy"
• "Flushing a Cache"
• "Locating Cached Data"

Loading a Cache

Data can be loaded into a cache using various methods. This section covers the different options for populating the cache and how to select a method for loading the data.

When determining the data acquisition method for your cache, consider how much of the data you want to acquire and when you want to load it. For example, you may decide to load data into the cache when the application initializes or to acquire the data only when it is requested. Table 5.1 shows the options available for loading a cache.

Table 5.1: Cache loading options

Loading type	Synchronous methods	Asynchronous methods
Proactive loading	Not recommended	Asynchronous pull loading Notification-based loading
Reactive loading	Synchronous pull loading	Not applicable

Each of these methods has its uses in different application scenarios.

Caching Data Proactively

You can cache data proactively to retrieve all of the required state for an application or a process, usually when the application or process starts, and cache it for the lifetime of the application or process.

Advantages of Proactive Loading

Because you can guarantee that the data has been loaded into the cache, in theory there is no need to check whether the state exists in the cache; however, check whether an item exists in the cache before retrieving it, anyway, because the cache may have been flushed.

Your application performance improves because cache operations are optimized when loading state into the cache proactively, and application response times improve because all of the data is cached.

Disadvantages of Proactive Loading

Proactive loading does not result in the most optimized system because a large amount of the state is cached, even though you may not need it all. For example, an application may contain 100 processes, each of which may require a few items in the cache. If a user launches this application but activates only one process, hundreds of items are needlessly cached.

Proactive caching may result in an implementation more complex than traditional techniques, in which each item is retrieved synchronously in a well-known program flow. Using proactive caching requires working with several threads, so synchronizing them with the application main thread, keeping track of their status, and handling exceptions in an asynchronous programming model can be difficult.

Recommendations for Proactive Loading

If you do not use proactive loading correctly, applications may initialize slowly. When you implement proactive caching, load as much state as possible when the application initializes or when each process initializes. You should use an asynchronous programming model to load the state on a background thread.

Proactive caching is recommended in situations in which:

• You are using static or semistatic state that has known update periods. If you use it in other scenarios, the state might expire before it is used.
• You are using state with a known lifetime.
• You are using state of a known size. If you use proactive cache data loading when you don't know the size of the data, you might exhaust system resources. You must not try to use resources that you do not have.
• You have problematic resources, such as a slow database, a slow network, or unreliable Web services. You can use this technique to retrieve all of the state proactively, cache it, and work against the cache as much as possible.

In these situations, proactive loading can improve application performance.

Using Asynchronous Pull Loading

In asynchronous pull loading, data is loaded into the cache for later use. It is a proactive process, based on expected not actual usage.

When using asynchronous pull loading, none of the requests for data perform worse than any other because the state is retrieved into the cache proactively, not as a response to a specific request. Consider using this technique at startup for applications with problems such as network latencies or service access difficulties.

Service agent caches are usually good candidates for asynchronous pull loading, especially if the data comes from many services and needs to be consolidated for consumption. For example, in a news feed application the data may be consolidated from many news agencies.

Figure 5.1 shows how to implement asynchronous pull loading in service agent elements.

Figure 5.1. Asynchronous pull loading

As Figure 5.1 shows, the steps for asynchronous pull loading are:

1. Based on a schedule or other type of notification, a dispatcher queries application services for their data.
2. Return values from the service agents are placed in the cache, and possibly aggregated with other data.
3. The application queries the cache for subsets of data and uses them.

Asynchronous pull loading ensures that the data is loaded into the cache independently of the application flow and is available for use whenever the application requests it.

Using Notification-Based Loading

In notification-based loading, the application's services notify the application or the cache of state changes. This technique is tightly coupled with the underlying application services.

When using this technique, you have two options for retrieving the state from the application's services into the cache:

• Receiving a notification from the application's services and then pull loading the data to populate the cache
• Receiving the state as part of a notification and populating the cache

Notification-based loading is generally more complex to implement than pull loading; however, it guarantees that new data is loaded only when necessary.

Advantages of Notification-Based Loading

A primary reason to use notification-based loading is that it results in minimal state staleness, so it makes it much easier for you to cache state and items that do not tolerate state becoming stale.

Because the application services handle the notifications, you do not need to implement a refresh mechanism in the application. This helps reduce the management overhead of the application.

You can use notification-based loading in Web farm scenarios, in which more than one cache needs to be notified of changes. Notification-based loading can ensure that multiple caches remain synchronized.

Disadvantages of Notification-Based Loading

The major disadvantage of this technique is that many services do not implement notification mechanisms. For example, Web services and legacy systems do not support notifications.

The application services layer may need more maintenance than when using other loading mechanisms. For example, triggers in SQL Server used for notifications need to be maintained.

Implementing notification-based loading can be more complex than using pull loading techniques.

Recommendations for Notification-Based Loading

Implementing notification-based loading usually involves the publish-subscribe (pub-sub) design pattern. In pub-sub applications, data published by a publisher entity is sent to all subscriber entities that subscribe to that data. Use the pub-sub pattern to receive notifications of state changes. For more information about using notifications, see "Using Expiration Policies" later in this chapter.

Using SQL Server 2000 Notification Services

Microsoft SQL Server 2000 Notification Services is a powerful notification application platform. It helps developers build centralized pub-sub applications and deploy them on a large scale. These applications are often used to send notification messages to end users and applications.

You can use this technology to monitor services, including Web services and legacy systems, for changes to data, and then to notify applications of the changes. The information updates can be delivered to various devices, including mobile devices such as cellular phones and Pocket PCs.

For more information about Notification Services, see the SQL Server 2000 Notification Services Web site.

Figure 5.2 shows one way to use Notification Services in your caching systems.

Figure 5.2. Implementing a pub-sub system

For a sample application design that demonstrates how to use Notification Services as a push mechanism for cached items, see Chapter 7, "Appendix."

Caching Data Reactively

You can cache data reactively to retrieve data as it is requested by the application and cache it for future requests.

Advantages of Reactive Loading

Because you are not loading large amounts of data when the application initializes, your system resources are not misused.

This method results in an optimized caching system because you are storing only requested items.

Disadvantages of Reactive Loading

Performance might decrease when any piece of data is requested the first time because it must be loaded from the source not retrieved from the cache.

You need to check whether an item exists in the cache before you can use it. Implementing this checking in every service agent can result in excessive conditional logic in your code.

Recommendations for Reactive Loading

When you implement reactive caching, load the state only when it is requested using a synchronous programming model. For more information about using a synchronous programming model, see the next section, "Using Synchronous Pull Loading."

Reactive caching is recommended in situations in which:

• You are using large amounts of state and do not have adequate resources to cache all of the state for the entire application.
• You are using reliable and responsive resources, such as a database, network, or Web service that will not impede application stability and performance.

In these situations, reactive loading can improve performance.

Using Synchronous Pull Loading

In synchronous pull loading, the data is loaded into the cache when the application requires the data. As such, it is a reactive loading method.

When using synchronous pull loading, the first request for the data decreases performance because the data has to be retrieved from the application service. Therefore, synchronous pull loading is best used when you need to get a specific piece of state rather than when you want to cache all of the state for the entire application or process.

You may want to use synchronous pull loading only when your system is running in a steady state, so that, for example, your application won't suffer from unexpected network latencies.

Advantages of Synchronous Pull Loading

It is relatively easy to implement synchronous pull loading because all of the loading code is written within the application and none is needed in the underlying application services. For example, you do not need to create or maintain SQL Server triggers or Windows Management Instrumentation (WMI) event listeners.

The synchronous pull loading implementation is independent of the underlying services. Synchronous pull loading does not rely on a specific application services technology, so it can be used to retrieve data from services such as Web services and legacy systems.

Disadvantages of Synchronous Pull Loading

The major problem that occurs when using pull loading is state staleness. Because no mechanism exists to notify the cache of data changes in the underlying application services, data changes in the application services might not be reflected in the cached data. For example, you may be caching flight departure information in your application. If a flight departure time changes and that change is not reflected in the cache, you may miss your flight.

Recommendations for Synchronous Pull Loading

Use synchronous pull loading for populating the cache when:

• The state retrieved from the different application services can have known and acceptable degrees of staleness.
• The state can be refreshed at known intervals. For example, cached stock quotes in a delayed stock ticker application can be refreshed once every 20 minutes.
• Working with third-party services, such as Web services or legacy systems, or while using services that don't implement notification mechanisms.

Figure 5.3 shows how you can implement synchronous pull loading in a service agent element.

Figure 5.3. Synchronous pull loading

As Figure 5.3 shows, the steps for synchronous pull loading are:

1. The application business logic calls the service agent and requests the data.
2. The service agent checks whether a suitable response is available in the cache—that is, it looks for the item in the cache and the expiration policies of any relevant items in it.
3. If the data is available in the cache, it is used. If not, the application service is called to return the data, and the service agent places the returned data in the cache.

Note   It is recommended that you separate service agents that use caching from those that do not. Doing so avoids having excess conditional logic in the service agent code.

In addition to reloading cache items to keep them valid, you may also want to implement an expiration policy to invalidate cached items.

Determining a Cache Expiration Policy

Preceding sections describe how to keep cache items valid by reloading the cache items using pull or push loading techniques. In this section, you learn about the different ways to maintain the validity of the data and items in the cache by using time-based or notification-based expiration.

Using Expiration Policies

There are two categories of expiration policy:

• Time-based expirations—Invalidate data based on either relative or absolute time periods
• Notification-based expirations—Invalidate data based on instructions from an internal or external source

Figure 5.4 shows the different dependencies that can be used to define the validity of cached items by using expiration policies.

Figure 5.4. Policy dependencies

Each type of expiration policy has its advantages and disadvantages.

Using Time-Based Expirations

You should use time-based expiration when volatile cache items—such as those that have regular data refreshes or those that are valid for only a set amount of time—are stored in a cache. Time-based expiration enables you to set policies that keep items in the cache only as long as their data remains current. For example, if you are writing an application that tracks currency exchange rates by obtaining the data from a frequently updated Web site, you can cache the currency rates for the time that those rates remain constant on the source Web site. In this situation, you would set an expiration policy that is based on the frequency of the Web site updates—for example, once a day or every 20 minutes.

There are two categories of time-based expiration policies, absolute and sliding:

• Absolute—Absolute expiration policies allow you to define the lifetime of an item by specifying the absolute time for an item to expire. There are two types:

  • Simple—You define the lifetime of an item by setting a specific date and time for the item to expire.
  • Extended—You define the lifetime of an item by specifying expressions such as every minute, every Sunday, expire at 5:15 AM on the 15th of every month, and so on.

  The following example shows how you can implement absolute time expiration.

  internal bool CheckSimpleAbsoluteExpiration(DateTime nowDateTime, 
                                        DateTime absoluteExpiration)
  {
  bool hasExpired = false;
  
  //Check expiration.
  if(nowDateTime.Ticks > absoluteExpiration.Ticks)
  {
      hasExpired = true;
  }
  else
  {
      hasExpired = false;
  }
  return hasExpired;
  }
  
  

• Sliding—Sliding expiration policies allow you to define the lifetime of an item by specifying the interval between the item being accessed and the policy defining it as expired.

  The following example shows how you can implement sliding time expiration.

  internal bool CheckSlidingExpiration(DateTime nowDateTime,
                                       DateTime lastUsed, 
                                       TimeSpan slidingExpiration)
  {
    bool hasExpired = false;
  
    //Check expiration.
    if(nowDateTime.Ticks > (lastUsed.Ticks + slidingExpiration.Ticks))
    {
      hasExpired = true;
    }
    else
    {
      hasExpired = false;
    }
    return hasExpired;
  }
  
  

For more information about implementing extended-format time expirations, see Chapter 7, "Appendix."

Using Notification-Based Expirations

You can use notification-based expiration to define the validity of a cached item based on the properties of an application resource, such as a file, a folder, or any other type of data source. If a dependency changes, the cached item is invalidated and removed from the cache.

Common sources of dependencies include:

• File changes
• WMI events
• Business logic operations

You can implement file dependencies by using the FileSystemWatcher class, in the System.IO namespace. The following code demonstrates how to create a file dependency class for invalidating cached items.

namespace Microsoft.Samples.Caching.Cs
{
   public class FileDependency
   {
      private System.IO.FileSystemWatcher m_fileSystemWatcher;

      public delegate void FileChange(object sender, 
                                      System.IO.FileSystemEventArgs e);
      //The OnFileChange event is fired when the file changes.
      public event FileChange OnFileChange;

      public FileDependency(string fullFileName)
      {
      //Validate file.
         System.IO.FileInfo fileInfo = new 
               System.IO.FileInfo(fullFileName);
         if (!fileInfo.Exists)
            throw new System.IO.FileNotFoundException();

        //Get path from full file name.
        string path = System.IO.Path.GetDirectoryName(fullFileName);
        //Get file name from full file name.
        string fileName = System.IO.Path.GetFileName(fullFileName);
        //Initialize new FileSystemWatcher.
        m_fileSystemWatcher = new System.IO.FileSystemWatcher();

        m_fileSystemWatcher.Path = path;
        m_fileSystemWatcher.Filter = fileName;
        m_fileSystemWatcher.EnableRaisingEvents = true;
        this.m_fileSystemWatcher.Changed += new 
      System.IO.FileSystemEventHandler(this.fileSystemWatcher_Changed);
      }

      private void fileSystemWatcher_Changed(object sender, 
                                       System.IO.FileSystemEventArgs e)
      {
         OnFileChange(sender, e);
      }
   } 
}
  

Whenever the specified file (or folder) changes, the OnFileChange event executes, and your custom code can be used to invalidate a cached item.

Using External Notifications

In some situations, external sources used in your application provide notifications of state changes. You can handle those notifications in two ways:

• Create a dependency directly from the cache to the service.
• Create an internal pub-sub to obtain external notification of changes and notify the internal subscribers for this event.

Figure 5.5 illustrates how to create a dependency directly from the cache to the service.

Figure 5.5. Creating a dependency for external service notification

Figure 5.6 shows how to create an internal pub-sub to obtain external notification of changes and notify the internal subscribers for this event.

Figure 5.6. Using internal pub-sub for external notifications

When you build applications with a large number of event subscribers, you should handle external notifications in a pub-sub way to improve scalability and availability.

If your application's data is stored in a SQL Server database, you can use triggers to implement a simple notification mechanism for your application's cache. The main advantage of using triggers is that your application is immediately notified of database changes.

One disadvantage of using this technique is that it is not optimized for many subscribers or for many events, which can lead to a decrease in database performance and can create scalability issues. Another disadvantage is that triggers are not easy to implement. In the database, you must write stored procedures containing the code to run when the trigger executes and write custom listeners in the application to receive the notifications.

For more information and sample code showing how to implement dependencies using SQL Server triggers, see Rob Howard's team page.

Expirations work well for removing invalid items from a cache; however, this may not always be enough to ensure an efficiently managed cache.

Flushing a Cache

Flushing allows you to manage cached items to ensure that storage, memory, and other resources are used efficiently. Flushing is different from expiration in that you may decide in some cases to flush valid cache items to make space for more frequently used items, whereas expiration policies are used to remove invalid items.

There are two categories of flushing techniques: explicit flushing and scavenging. Scavenging can be implemented to flush items based on when they were last used, how often they have been used, or using priorities that you assign in your application.

Figure 5.7 shows the two categories of flushing techniques.

Figure 5.7. Flushing techniques

Explicit flushing requires that you write the code to determine when the item should be flushed and the code to flush it. With scavenging, you write an algorithm for the cache to use to determine what items can be flushed.

Using Explicit Flushing

Different scenarios require that cache stores be explicitly flushed by instructing the cache to clear its content. You can implement explicit flushing either manually or programmatically. For example, if cached data becomes obsolete or damaged, there may be an immediate need to clear the contents of the cache. In this situation, a system administrator must be able to explicitly flush the cache.

None of the custom stores—for example, SQL Server and static variables—support scavenging, so you must explicitly implement any flushing techniques that you require.

Implementing Scavenging

You can use a scavenging algorithm to automatically remove seldom used or unimportant items from the cache when system memory or some other resource becomes scarce.

Typically, scavenging is activated when storage resources become scarce, but it can also be activated to save computing resources—for example, to reduce the time and CPU cycles required to look up specific cached items.

The following code shows how to initiate a process based on the amount of memory available.

using System;
using System.Management;

namespace Microsoft.Samples.Caching.Cs.WMIDependency
{
   public delegate void WmiMonitoringEventHandler(object sender, object newValue);
   public class WMIMemoryDependency : IDisposable
   {
       string path = @"\\" + "localhost" + @"\root\cimv2";
       private int m_MemoryLimit = 0;
       private ManagementEventWatcher memoryEventWatcher;
       public event WmiMonitoringEventHandler MemoryLimitReached;
    
       public WMIMemoryDependency(int memoryLimit)
  {
          m_MemoryLimit = memoryLimit;
       StartEvent();
  }
       private void StartEvent()
  {            
          ManagementScope scope = new ManagementScope(path);
          scope.Options.EnablePrivileges = true;
          WqlEventQuery eventQuery = new WqlEventQuery();  
    
          eventQuery.QueryString = "SELECT * FROM __InstanceOperationEvent " 
+ 
               "WITHIN 30 WHERE TargetInstance ISA " + 
               "'Win32_PerfRawData_PerfOS_Memory'";  
          memoryEventWatcher = new ManagementEventWatcher(scope, 
                                                           eventQuery);
          memoryEventWatcher.EventArrived += new 
              EventArrivedEventHandler(MemoryEventArrived);
          memoryEventWatcher.Start();
  }

  private void MemoryEventArrived(object o,EventArrivedEventArgs e)
  {
     try
     {
       ManagementBaseObject eventArg = null;
        
       eventArg = (ManagementBaseObject)(e.NewEvent["TargetInstance"]);  
       string memory = 
           eventArg.Properties["AvailableKBytes"].Value.ToString();
       Int64 freeMemory = Convert.ToInt64(memory);
       if (freeMemory <= m_MemoryLimit)
        {
          if(MemoryLimitReached != null)
              MemoryLimitReached(this, freeMemory);
        }
     }
     catch(Exception ex) {throw(ex);}
  }

    void IDisposable.Dispose()
    {
       if(memoryEventWatcher != null)
           memoryEventWatcher.Stop();
    }
   }
}
  

Flushing items from memory can be initiated using one of three common algorithms:

• Least Recently Used algorithm—The Least Recently Used (LRU) algorithm flushes the items that have not been used for the longest period of time.

  The following pseudocode shows how the LRU algorithm works.

  Sort_cache_items_by_last_used_datetime;
  While (%cache_size_from_available_memory > 
  max_cache_size%_from_available_memory) 
  {
     item = peek_first_item;
     Remove_item_from_cache( item );
  }
  
  

• Least Frequently Used algorithm—The Least Frequently Used (LFU) algorithm flushes the items that have been used least frequently since they were loaded. The main disadvantage of this algorithm is that it may keep obsolete items infinitely in the cache.

  The following pseudocode shows how the LFU algorithm works.

  Sort_cache_items_by_usage_count;
  While (%cache_size_from_available_memory > 
  max_cache_size%_from_available_memory) 
  {
     item = peek_first_item;
     Remove_item_from_cache( item );
  }
  
  

• Priority algorithm—The priority algorithm instructs the cache to assign certain items priority over other items when it scavenges. Unlike in the other algorithms, the application code rather than the cache engine assigns priorities.

You have seen how to load a cache and how to remove items from a cache for different reasons. The last main planning task is to determine how to access the information stored in the cache.

Locating Cached Data

In many cases, a cache exposes an API to enable you to load and retrieve items based on some kind of identifier—for example, a key, a tag, or an index. If you want your cache to be generic, it must support storage of many types of items; therefore, it must expose an API that allows applications to access any of the items it stores.

When you are caching many different types of items, create multiple caches, one for each type of item. This increases the efficiency of data searching because it reduces the number of items in each cache. Furthermore, in rare cases, you may not know exactly what cached items your application will retrieve. For example, you may have an asynchronously pull loaded cache that obtains news feeds from many news agencies and places them in a SQL Server database. When the application retrieves cached data, it may simply request news items related to Microsoft. In this scenario, you must implement some identification method based on the cached data attributes, such as keywords, which allows this type of search to be used.

Figure 5.8 shows how data is commonly requested, using either a known key or a set of attributes.

Figure 5.8. Locating cached data

Whether you are implementing a known key or a data attribute-based cache searching mechanism, use the following guidelines for locating an item:

• If there is only one primary key or identifier, use key-value pair collections such as hash table or hybrid dictionary.

• If there are multiple potential keys, create one hash table for each identifier, as Figure 5.9 shows. However, doing so can make it harder to remove items from the cache because you need information from all of the hash tables that refer to the cache item.

  

  Figure 5.9. Using multiple hash tables

Be careful not to over-engineer your indexing strategy. If you require complex indexing, aggregation, or querying language capabilities, use a relational database management system as your caching mechanism.

Summary

This chapter explains the options for loading data into a cache and managing the data after it is in the cache. However, you must consider other issues when planning and designing a cache, including security, monitoring, and synchronizing caches in server farms.