Caching.ExpiringCacheMap.OrdECM

A cache that holds values for a length of time that uses Ord keys with Data.Map.Strict.

An example of creating a cache for accessing files:

{-# LANGUAGE OverloadedStrings #-}

import Caching.ExpiringCacheMap.OrdECM (newECMIO, lookupECM, CacheSettings(..), consistentDuration)

import qualified Data.Time.Clock.POSIX as POSIX (POSIXTime, getPOSIXTime)
import qualified Data.ByteString.Char8 as BS
import System.IO (withFile, IOMode(ReadMode))

example = do
  filecache <- newECMIO
        (consistentDuration 100 -- Duration between access and expiry time of each item
          (\state id -> do BS.putStrLn "Reading a file again..."
                           withFile (case id :: BS.ByteString of
                                       "file1" -> "file1.txt"
                                       "file2" -> "file2.txt")
                              ReadMode $
                              \fh -> do content <- BS.hGetContents fh
                                        return $! (state, content)))
        (do time <- POSIX.getPOSIXTime
            return (round (time * 100)))
        1 -- Time check frequency: (accumulator `mod` this_number) == 0.
        (CacheWithLRUList
          6     -- Expected size of key-value map when removing elements.
          6     -- Size of map when to remove items from key-value map.
          12    -- Size of list when to compact
          )
  
  -- Use lookupECM whenever the contents of "file1" is needed.
  b <- lookupECM filecache "file1"
  BS.putStrLn b
  return ()

Create cache

newECMIO :: Ord k => (Maybe s -> k -> IO (TimeUnits, (Maybe s, v))) -> IO TimeUnits -> ECMIncr -> CacheSettings -> IO (ECM IO MVar s Map k v)

Create a new expiring cache for retrieving uncached values via IO interaction (such as in the case of reading a file from disk), with a shared state lock via an MVar to manage cache state.

Value request and time check request functions are provided as arguments.

The time check frequency value has to be 1 or higher, with higher values postponing time checks for longer periods of time.

A cache setting specifies how the cache should remove entries when the cache becomes a certain size. The only constructor for this is CacheWithLRUList.

newECMForM :: (Monad m1, Monad m2) => Ord k => (Maybe s -> k -> m1 (TimeUnits, (Maybe s, v))) -> m1 TimeUnits -> ECMIncr -> CacheSettings -> ECMNewState m2 mv s Map k v -> ECMEnterState m1 mv s Map k v -> ECMReadState m1 mv s Map k v -> m2 (ECM m1 mv s Map k v)

Create a new expiring cache along arbitrary monads with provided functions to create cache state in Monad m2, and modify and read cache state in Monad m1.

newECMIO is just a wrapper to this function with MVar functions:

 newECMIO retr gettime timecheckmodulo cachesettings =
   newECMForM retr gettime timecheckmodulo cachesettings
     newMVar modifyMVar readMVar

Value request and time check request functions are provided as arguments.

The time check frequency value has to be 1 or higher, with higher values postponing time checks for longer periods of time.

A cache setting specifies how the cache should remove entries when the cache becomes a certain size. The only constructor for this is CacheWithLRUList.

consistentDuration :: (Monad m, Ord k) => TimeUnits -> (Maybe s -> k -> m (Maybe s, v)) -> Maybe s -> k -> m (TimeUnits, (Maybe s, v))

Used with newECMIO or newECMForM to provide a consistent duration for requested values.

Request value from cache

lookupECM :: (Monad m, Ord k) => ECM m mv s Map k v -> k -> m v

Request a value associated with a key from the cache.

• If the value is not in the cache, it will be requested through the function defined through newECM, its computation returned and the value stored in the cache state map.
• If the value is in the cache and has not expired, it will be returned.
• If the value is in the cache and a new time is computed in the same lookup, and the value has been determined to have since expired, it will be discarded and a new value will be requested for this computation.

Every lookupECM computation increments an accumulator in the cache state which is used to keep track of the succession of key accesses. Based on the parameters provided with the CacheWithLRUList constructor, this history of key accesses is then used to remove entries from the cache back down to a minimum size. Also, when the modulo of the accumulator and the modulo value computes to 0, the time request function is invoked. In some cases the accumulator may get incremented more than once in a lookupECM computation.

As the accumulator is a bound unsigned integer, when the accumulator increments back to 0, the cache state is completely cleared.

The time request function is invoked in one of two different conditions

• When a new key-value entry is requested, the current time is also requested during the same lookup, as a recent time determination is needed for a new entry in the key-value cache.
• When the modulo of the accumulator and a specified value equals to 0.

When the current time is determined during a lookup, access times of the entries in the key-value cache are compared with the new time to filter out expired entries from the key-value map.

Value request function state

getValReqState :: (Monad m, Ord k) => ECM m mv s Map k v -> k -> m (Maybe s)

Invalidate cache

invalidate :: (Monad m, Ord k) => ECM m mv s Map k v -> k -> m (Maybe v)

Invalidates a key from the cache and returns its value if any. Note that this is a sequential composition of a read and modify of the mutable cache container (e.g. readMVar followed by modifyMVar with newECMIO instances).

invalidateCache :: (Monad m, Ord k) => ECM m mv s Map k v -> m (Maybe (k, v))

Invalidates the entire cache and returns the last key and value if any. Note that this is a sequential composition of a read and modify of the mutable cache container (e.g. readMVar followed by modifyMVar with newECMIO instances).

List keys

keysCached :: (Monad m, Ord k) => ECM m mv s Map k v -> m [k]

List of keys in the cache map without performing a time check, returning both stored keys that are expired and keys that are not expired. keys are in an unspecified order.

keysNotExpired :: (Monad m, Ord k) => ECM m mv s Map k v -> m [k]

List of keys in the cache map that are not expired values. A time check is always performed to compare with the elapsed time left with each key. The cache state is not modified and the time check is not performed from within a modifying state context, e.g. not within modifyMVar with a newECMIO instance. Keys are in an unspecified order.

Type

data ECM a b s m k v

The type that encapsulates a cache map.

data CacheSettings

Constructors

CacheWithLRUList

A cache that maintains a key access history list to perform removals of least recently used entries. Once the key-value map reaches removalsize keys, then a list of keys to keep in the map is determined which is no larger than mapsize size. Entries are removed only on insertion of a new entry in the key-value map.

Key access history entries are prepended to the head of the LRU list, if an existing entry for the key appears close to the head of the list it is moved to the head of the list, instead of growing the list. When the LRU list reaches compactlistsize items, it is compacted by removing duplicate keys, by keeping only the most recent accumulator value for that key.

Fields

• mapsize :: ECMMapSize
• removalsize :: ECMMapSize
• compactlistsize :: ECMULength