icarus.models.cache package¶
Submodules¶
icarus.models.cache.policies module¶
Cache replacement policies implementations
This module contains the implementations of all the cache replacement policies provided by Icarus.
-
class
LinkedSet(iterable=[])[source]¶ Bases:
objectA doubly-linked set, i.e., a set whose entries are ordered and stored as a doubly-linked list.
This data structure is designed to efficiently implement a number of cache replacement policies such as LRU and derivatives such as Segmented LRU.
It provides O(1) time complexity for the following operations: searching, remove from any position, move to top, move to bottom, insert after or before a given item.
Attributes: Methods
append_bottom(k)Append an item at the bottom of the set append_top(k)Append an item at the top of the set clear()Empty the set index(k)Return index of a given element. insert_above(i, k)Insert an item one position above a given item already in the set insert_below(i, k)Insert an item one position below a given item already in the set move_down(k)Move a specified item one position down in the set move_to_bottom(k)Move a specified item to the bottom of the set move_to_top(k)Move a specified item to the top of the set move_up(k)Move a specified item one position up in the set pop_bottom()Pop the item at the bottom of the set pop_top()Pop the item at the top of the set remove(k)Remove an item from the set -
append_bottom(k)[source]¶ Append an item at the bottom of the set
Parameters: - k : any hashable type
The item to append
-
append_top(k)[source]¶ Append an item at the top of the set
Parameters: - k : any hashable type
The item to append
-
bottom¶ Return the item at the bottom of the set
Returns: - bottom : any hashable type
The item at the bottom or None if the set is empty
-
index(k)[source]¶ Return index of a given element.
This operation has a O(n) time complexity, with n being the size of the set.
Parameters: - k : any hashable type
The item whose index is queried
Returns: - index : int
The index of the item
-
insert_above(i, k)[source]¶ Insert an item one position above a given item already in the set
Parameters: - i : any hashable type
The item of the set above which the new item is inserted
- k : any hashable type
The item to insert
-
insert_below(i, k)[source]¶ Insert an item one position below a given item already in the set
Parameters: - i : any hashable type
The item of the set below which the new item is inserted
- k : any hashable type
The item to insert
-
move_down(k)[source]¶ Move a specified item one position down in the set
Parameters: - k : any hashable type
The item to move down
-
move_to_bottom(k)[source]¶ Move a specified item to the bottom of the set
Parameters: - k : any hashable type
The item to move to the bottom
-
move_to_top(k)[source]¶ Move a specified item to the top of the set
Parameters: - k : any hashable type
The item to move to the top
-
move_up(k)[source]¶ Move a specified item one position up in the set
Parameters: - k : any hashable type
The item to move up
-
pop_bottom()[source]¶ Pop the item at the bottom of the set
Returns: - bottom : any hashable type
The item at the bottom or None if the set is empty
-
pop_top()[source]¶ Pop the item at the top of the set
Returns: - top : any hashable type
The item at the top or None if the set is empty
-
top¶ Return the item at the top of the set
Returns: - top : any hashable type
The item at the top or None if the set is empty
-
-
class
Cache(maxlen, *args, **kwargs)[source]¶ Bases:
objectBase implementation of a cache object
Attributes: maxlenReturn the maximum number of items the cache can store
Methods
clear()Empty the cache do(op, k, *args, **kwargs)Utility method that performs a specified operation on a given item. dump()Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy. get(k, *args, **kwargs)Retrieves an item from the cache. has(k, *args, **kwargs)Check if an item is in the cache without changing the internal state of the caching object. put(k, *args, **kwargs)Insert an item in the cache if not already inserted. remove(k, *args, **kwargs)Remove an item from the cache, if present. -
do(op, k, *args, **kwargs)[source]¶ Utility method that performs a specified operation on a given item.
This method allows to perform one of the different operations on an item:
- GET: Retrieve an item
- PUT: Insert an item
- UPDATE: Update the value associated to an item
- DELETE: Remove an item
Parameters: - op : string
The operation to execute: GET | PUT | UPDATE | DELETE
- k : any hashable type
The item looked up in the cache
Returns: - res : bool
Boolean value being True if the operation succeeded or False otherwise.
-
dump()[source]¶ Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy.
Returns: - cache_dump : list
The list of all items currently stored in the cache
-
get(k, *args, **kwargs)[source]¶ Retrieves an item from the cache.
Differently from has(k), calling this method may change the internal state of the caching object depending on the specific cache implementation.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
has(k, *args, **kwargs)[source]¶ Check if an item is in the cache without changing the internal state of the caching object.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
maxlen¶ Return the maximum number of items the cache can store
-
put(k, *args, **kwargs)[source]¶ Insert an item in the cache if not already inserted.
If the element is already present in the cache, it will not be inserted again but the internal state of the cache object may change.
Parameters: - k : any hashable type
The item to be inserted
Returns: - evicted : any hashable type
The evicted object or None if no contents were evicted.
-
class
NullCache(maxlen=0, *args, **kwargs)[source]¶ Bases:
icarus.models.cache.policies.CacheImplementation of a null cache.
This is a dummy cache which never stores anything. It is functionally identical to a cache with max size equal to 0.
Attributes: maxlenReturn the maximum number of items the cache can store.
Methods
clear()Empty the cache do(op, k, *args, **kwargs)Utility method that performs a specified operation on a given item. dump()Return a list of all the elements currently in the cache. get(k, *args, **kwargs)Retrieves an item from the cache. has(k, *args, **kwargs)Check if an item is in the cache without changing the internal state of the caching object. put(k, *args, **kwargs)Insert an item in the cache if not already inserted. remove(k, *args, **kwargs)Remove a specified item from the cache. -
dump()[source]¶ Return a list of all the elements currently in the cache.
In this case it is always an empty list.
Returns: - cache_dump : list
An empty list.
-
get(k, *args, **kwargs)[source]¶ Retrieves an item from the cache.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise. It always returns False
-
has(k, *args, **kwargs)[source]¶ Check if an item is in the cache without changing the internal state of the caching object.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise. It always returns False
-
maxlen¶ Return the maximum number of items the cache can store.
Since this is a dummy cache implementation, this value is 0.
Returns: - maxlen : int
The maximum number of items the cache can store. It is always 0
-
name= 'NULL'¶
-
put(k, *args, **kwargs)[source]¶ Insert an item in the cache if not already inserted.
Parameters: - k : any hashable type
The item to be inserted
Returns: - evicted : any hashable type
The evicted object or None if no contents were evicted.
-
remove(k, *args, **kwargs)[source]¶ Remove a specified item from the cache.
If the element is not present in the cache, no action is taken.
Parameters: - k : any hashable type
The item to be inserted
Returns: - removed : bool
True if the content was in the cache, False if it was not. It always return False
-
class
BeladyMinCache(maxlen, trace, **kwargs)[source]¶ Bases:
icarus.models.cache.policies.CacheBelady’s MIN cache replacement policy
The Belady’s MIN policy is the provably optimal cache replacement policy under arbitrary workload. Each time an item is inserted into a full cache, it evicts the item that will be requested next the latest.
This policy is not implementable in practice because it requires knowledge of future requests, however it is very useful as a theoretical performance upper bound.
Attributes: maxlenReturn the maximum number of items the cache can store
Methods
clear()Empty the cache do(op, k, *args, **kwargs)Utility method that performs a specified operation on a given item. dump()Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy. get(k, *args, **kwargs)Retrieves an item from the cache. has(k, *args, **kwargs)Check if an item is in the cache without changing the internal state of the caching object. remove(k, *args, **kwargs)Remove an item from the cache, if present. put -
dump()[source]¶ Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy.
Returns: - cache_dump : list
The list of all items currently stored in the cache
-
get(k, *args, **kwargs)[source]¶ Retrieves an item from the cache.
Differently from has(k), calling this method may change the internal state of the caching object depending on the specific cache implementation.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
has(k, *args, **kwargs)[source]¶ Check if an item is in the cache without changing the internal state of the caching object.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
maxlen¶ Return the maximum number of items the cache can store
-
name= 'MIN'¶
-
put(k, *args, **kwargs)[source]¶ Insert an item in the cache if not already inserted.
If the element is already present in the cache, it will not be inserted again but the internal state of the cache object may change.
Parameters: - k : any hashable type
The item to be inserted
Returns: - evicted : any hashable type
The evicted object or None if no contents were evicted.
-
class
LruCache(maxlen, **kwargs)[source]¶ Bases:
icarus.models.cache.policies.CacheLeast Recently Used (LRU) cache eviction policy.
According to this policy, When a new item needs to inserted into the cache, it evicts the least recently requested one. This eviction policy is efficient for line speed operations because both search and replacement tasks can be performed in constant time (O(1)).
This policy has been shown to perform well in the presence of temporal locality in the request pattern. However, its performance drops under the Independent Reference Model (IRM) assumption (i.e. the probability that an item is requested is not dependent on previous requests).
Attributes: maxlenReturn the maximum number of items the cache can store
Methods
clear()Empty the cache do(op, k, *args, **kwargs)Utility method that performs a specified operation on a given item. dump()Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy. get(k, *args, **kwargs)Retrieves an item from the cache. has(k, *args, **kwargs)Check if an item is in the cache without changing the internal state of the caching object. position(k, *args, **kwargs)Return the current position of an item in the cache. put(k, *args, **kwargs)Insert an item in the cache if not already inserted. remove(k, *args, **kwargs)Remove an item from the cache, if present. -
dump()[source]¶ Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy.
Returns: - cache_dump : list
The list of all items currently stored in the cache
-
get(k, *args, **kwargs)[source]¶ Retrieves an item from the cache.
Differently from has(k), calling this method may change the internal state of the caching object depending on the specific cache implementation.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
has(k, *args, **kwargs)[source]¶ Check if an item is in the cache without changing the internal state of the caching object.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
maxlen¶ Return the maximum number of items the cache can store
-
name= 'LRU'¶
-
position(k, *args, **kwargs)[source]¶ Return the current position of an item in the cache. Position 0 refers to the head of cache (i.e. most recently used item), while position maxlen - 1 refers to the tail of the cache (i.e. the least recently used item).
This method does not change the internal state of the cache.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - position : int
The current position of the item in the cache
-
put(k, *args, **kwargs)[source]¶ Insert an item in the cache if not already inserted.
If the element is already present in the cache, it will pushed to the top of the cache.
Parameters: - k : any hashable type
The item to be inserted
Returns: - evicted : any hashable type
The evicted object or None if no contents were evicted.
-
class
SegmentedLruCache(maxlen, segments=2, alloc=None, *args, **kwargs)[source]¶ Bases:
icarus.models.cache.policies.CacheSegmented Least Recently Used (LRU) cache eviction policy.
This policy divides the cache space into a number of segments of equal size each operating according to an LRU policy. When a new item is inserted to the cache, it is placed on the top entry of the bottom segment. Each subsequent hit promotes the item to the top entry of the segment above. When an item is evicted from a segment, it is demoted to the top entry of the segment immediately below. An item is evicted from the cache when it is evicted from the bottom segment.
This policy can be viewed as a sort of combination between an LRU and LFU replacement policies as it makes eviction decisions based both frequency and recency of item reference.
Attributes: maxlenReturn the maximum number of items the cache can store
Methods
clear()Empty the cache do(op, k, *args, **kwargs)Utility method that performs a specified operation on a given item. dump([serialized])Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy. get(k, *args, **kwargs)Retrieves an item from the cache. has(k, *args, **kwargs)Check if an item is in the cache without changing the internal state of the caching object. position(k, *args, **kwargs)Return the current position of an item in the cache. put(k, *args, **kwargs)Insert an item in the cache if not already inserted. remove(k, *args, **kwargs)Remove an item from the cache, if present. -
dump(serialized=True)[source]¶ Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy.
Returns: - cache_dump : list
The list of all items currently stored in the cache
-
get(k, *args, **kwargs)[source]¶ Retrieves an item from the cache.
Differently from has(k), calling this method may change the internal state of the caching object depending on the specific cache implementation.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
has(k, *args, **kwargs)[source]¶ Check if an item is in the cache without changing the internal state of the caching object.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
maxlen¶ Return the maximum number of items the cache can store
-
name= 'SLRU'¶
-
position(k, *args, **kwargs)[source]¶ Return the current position of an item in the cache. Position 0 refers to the head of cache (i.e. most recently used item), while position maxlen - 1 refers to the tail of the cache (i.e. the least recently used item).
This method does not change the internal state of the cache.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - position : int
The current position of the item in the cache
-
put(k, *args, **kwargs)[source]¶ Insert an item in the cache if not already inserted.
If the element is already present in the cache, it will pushed to the top of the cache.
Parameters: - k : any hashable type
The item to be inserted
Returns: - evicted : any hashable type
The evicted object or None if no contents were evicted.
-
class
InCacheLfuCache(maxlen, *args, **kwargs)[source]¶ Bases:
icarus.models.cache.policies.CacheIn-cache Least Frequently Used (LFU) cache implementation
The LFU replacement policy keeps a counter associated each item. Such counters are increased when the associated item is requested. Upon insertion of a new item, the cache evicts the one which was requested the least times in the past, i.e. the one whose associated value has the smallest value.
This is an implementation of an In-Cache-LFU, i.e. a cache that keeps counters for items only as long as they are in cache and resets the counter of an item when it is evicted. This is different from a Perfect-LFU policy in which a counter is maintained also when the content is evicted.
In-cache LFU performs better than LRU under IRM demands. However, its implementation is computationally expensive since it cannot be implemented in such a way that both search and replacement tasks can be executed in constant time. This makes it particularly unfit for large caches and line speed operations.
Attributes: maxlenReturn the maximum number of items the cache can store
Methods
clear()Empty the cache do(op, k, *args, **kwargs)Utility method that performs a specified operation on a given item. dump()Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy. get(k, *args, **kwargs)Retrieves an item from the cache. has(k, *args, **kwargs)Check if an item is in the cache without changing the internal state of the caching object. put(k, *args, **kwargs)Insert an item in the cache if not already inserted. remove(k, *args, **kwargs)Remove an item from the cache, if present. -
dump()[source]¶ Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy.
Returns: - cache_dump : list
The list of all items currently stored in the cache
-
get(k, *args, **kwargs)[source]¶ Retrieves an item from the cache.
Differently from has(k), calling this method may change the internal state of the caching object depending on the specific cache implementation.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
has(k, *args, **kwargs)[source]¶ Check if an item is in the cache without changing the internal state of the caching object.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
maxlen¶ Return the maximum number of items the cache can store
-
name= 'IN_CACHE_LFU'¶
-
put(k, *args, **kwargs)[source]¶ Insert an item in the cache if not already inserted.
If the element is already present in the cache, it will not be inserted again but the internal state of the cache object may change.
Parameters: - k : any hashable type
The item to be inserted
Returns: - evicted : any hashable type
The evicted object or None if no contents were evicted.
-
class
PerfectLfuCache(maxlen, *args, **kwargs)[source]¶ Bases:
icarus.models.cache.policies.CachePerfect Least Frequently Used (LFU) cache implementation
The LFU replacement policy keeps a counter associated each item. Such counters are increased when the associated item is requested. Upon insertion of a new item, the cache evicts the one which was requested the least times in the past, i.e. the one whose associated value has the smallest value.
This is an implementation of a Perfect-LFU, i.e. a cache that keeps counters for every item, even for those not in the cache.
In contrast to LRU, Perfect-LFU has been shown to perform optimally under IRM demands. However, its implementation is computationally expensive since it cannot be implemented in such a way that both search and replacement tasks can be executed in constant time. This makes it particularly unfit for large caches and line speed operations.
Attributes: maxlenReturn the maximum number of items the cache can store
Methods
clear()Empty the cache do(op, k, *args, **kwargs)Utility method that performs a specified operation on a given item. dump()Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy. get(k, *args, **kwargs)Retrieves an item from the cache. has(k, *args, **kwargs)Check if an item is in the cache without changing the internal state of the caching object. put(k, *args, **kwargs)Insert an item in the cache if not already inserted. remove(k, *args, **kwargs)Remove an item from the cache, if present. -
dump()[source]¶ Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy.
Returns: - cache_dump : list
The list of all items currently stored in the cache
-
get(k, *args, **kwargs)[source]¶ Retrieves an item from the cache.
Differently from has(k), calling this method may change the internal state of the caching object depending on the specific cache implementation.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
has(k, *args, **kwargs)[source]¶ Check if an item is in the cache without changing the internal state of the caching object.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
maxlen¶ Return the maximum number of items the cache can store
-
name= 'PERFECT_LFU'¶
-
put(k, *args, **kwargs)[source]¶ Insert an item in the cache if not already inserted.
If the element is already present in the cache, it will not be inserted again but the internal state of the cache object may change.
Parameters: - k : any hashable type
The item to be inserted
Returns: - evicted : any hashable type
The evicted object or None if no contents were evicted.
-
class
FifoCache(maxlen, *args, **kwargs)[source]¶ Bases:
icarus.models.cache.policies.CacheFirst In First Out (FIFO) cache implementation.
According to the FIFO policy, when a new item is inserted, the evicted item is the first one inserted in the cache. The behavior of this policy differs from LRU only when an item already present in the cache is requested. In fact, while in LRU this item would be pushed to the top of the cache, in FIFO no movement is performed. The FIFO policy has a slightly simpler implementation in comparison to the LRU policy but yields worse performance.
Attributes: maxlenReturn the maximum number of items the cache can store
Methods
clear()Empty the cache do(op, k, *args, **kwargs)Utility method that performs a specified operation on a given item. dump()Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy. get(k, *args, **kwargs)Retrieves an item from the cache. has(k, *args, **kwargs)Check if an item is in the cache without changing the internal state of the caching object. position(k, *args, **kwargs)Return the current position of an item in the cache. put(k, *args, **kwargs)Insert an item in the cache if not already inserted. remove(k, *args, **kwargs)Remove an item from the cache, if present. -
dump()[source]¶ Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy.
Returns: - cache_dump : list
The list of all items currently stored in the cache
-
get(k, *args, **kwargs)[source]¶ Retrieves an item from the cache.
Differently from has(k), calling this method may change the internal state of the caching object depending on the specific cache implementation.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
has(k, *args, **kwargs)[source]¶ Check if an item is in the cache without changing the internal state of the caching object.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
maxlen¶ Return the maximum number of items the cache can store
-
name= 'FIFO'¶
-
position(k, *args, **kwargs)[source]¶ Return the current position of an item in the cache. Position 0 refers to the head of cache (i.e. most recently inserted item), while position maxlen - 1 refers to the tail of the cache (i.e. the least recently inserted item).
This method does not change the internal state of the cache.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - position : int
The current position of the item in the cache
-
put(k, *args, **kwargs)[source]¶ Insert an item in the cache if not already inserted.
If the element is already present in the cache, it will not be inserted again but the internal state of the cache object may change.
Parameters: - k : any hashable type
The item to be inserted
Returns: - evicted : any hashable type
The evicted object or None if no contents were evicted.
-
class
ClimbCache(maxlen, *args, **kwargs)[source]¶ Bases:
icarus.models.cache.policies.CacheCLIMB cache implementation
According to this policy, items are organized in a list. When an item in the cache is requested it is moved one position up the list; if already on top, nothing is done. When a new item is inserted, it replaces the one at the bottom of the list.
Attributes: maxlenReturn the maximum number of items the cache can store
Methods
clear()Empty the cache do(op, k, *args, **kwargs)Utility method that performs a specified operation on a given item. dump()Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy. get(k, *args, **kwargs)Retrieves an item from the cache. has(k, *args, **kwargs)Check if an item is in the cache without changing the internal state of the caching object. position(k, *args, **kwargs)Return the current position of an item in the cache. put(k, *args, **kwargs)Insert an item in the cache if not already inserted. remove(k, *args, **kwargs)Remove an item from the cache, if present. -
dump()[source]¶ Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy.
Returns: - cache_dump : list
The list of all items currently stored in the cache
-
get(k, *args, **kwargs)[source]¶ Retrieves an item from the cache.
Differently from has(k), calling this method may change the internal state of the caching object depending on the specific cache implementation.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
has(k, *args, **kwargs)[source]¶ Check if an item is in the cache without changing the internal state of the caching object.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
maxlen¶ Return the maximum number of items the cache can store
-
name= 'CLIMB'¶
-
position(k, *args, **kwargs)[source]¶ Return the current position of an item in the cache. Position 0 refers to the head of cache, while position maxlen - 1 refers to the tail of the cache.
This method does not change the internal state of the cache.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - position : int
The current position of the item in the cache
-
put(k, *args, **kwargs)[source]¶ Insert an item in the cache if not already inserted.
If the element is already present in the cache, it will pushed one position up.
Parameters: - k : any hashable type
The item to be inserted
Returns: - evicted : any hashable type
The evicted object or None if no contents were evicted.
-
class
RandEvictionCache(maxlen, *args, **kwargs)[source]¶ Bases:
icarus.models.cache.policies.CacheRandom eviction cache implementation.
This class implements a cache replacement policies which randomly select an item to evict when the cache is full. It generally yields poor performance in terms of cache hits, especially with non-stationary workloads but is sometimes used as baseline and for this reason it has been implemented here.
In case of stationary IRM workloads, the RAND eviction policy provably achieves the same cache hit ratio of the FIFO replacement policy.
Attributes: - maxlen
Methods
clear()Empty the cache do(op, k, *args, **kwargs)Utility method that performs a specified operation on a given item. dump()Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy. get(k, *args, **kwargs)Retrieves an item from the cache. has(k, *args, **kwargs)Check if an item is in the cache without changing the internal state of the caching object. put(k, *args, **kwargs)Insert an item in the cache if not already inserted. remove(k, *args, **kwargs)Remove an item from the cache, if present. -
dump()[source]¶ Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy.
Returns: - cache_dump : list
The list of all items currently stored in the cache
-
get(k, *args, **kwargs)[source]¶ Retrieves an item from the cache.
Differently from has(k), calling this method may change the internal state of the caching object depending on the specific cache implementation.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
has(k, *args, **kwargs)[source]¶ Check if an item is in the cache without changing the internal state of the caching object.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
maxlen¶
-
name= 'RAND'¶
-
put(k, *args, **kwargs)[source]¶ Insert an item in the cache if not already inserted.
If the element is already present in the cache, it will not be inserted again but the internal state of the cache object may change.
Parameters: - k : any hashable type
The item to be inserted
Returns: - evicted : any hashable type
The evicted object or None if no contents were evicted.
-
insert_after_k_hits_cache(cache, k=2, memory=None)[source]¶ Return a cache inserting items only after k requests.
This methods allows to implement a variant of k-LRU and k-RANDOM policies, which insert items in the main cache only at the k-th request. However, proper k-LRU and k-RANDOM policies, keep a separate queue of fixed size for items being hit the same number of times. For example, let’s say k=3, then there is a fixed size queue storing all items being hit 1 time and another queue for items being hit 2 times. In this implementation there is a unique FIFO queue keeping all items being hit < k times. The size of this queue is equal to the value of memory parameter. If memory is None, then this queue is infinite.
In the most common case of k=2, this difference of implementation does not matter.
Parameters: - cache : Cache
The instance of a cache to be applied random insertion
- k : int, optional
The number of hits after which the item is inserted
- memory : int, optional
The size of the metacache just storing the reference to the item and the number of hits, without storing the item itself.
Returns: - cache : Cache
The modified cache instance
-
rand_insert_cache(cache, p, seed=None)[source]¶ Return a random insertion cache
It modifies the instance of a cache object such that items are inserted randomly instead of deterministically.
This function modifies the behavior of the put method of a given cache instance such that it inserts contents randomly with a given probability
Parameters: - cache : Cache
The instance of a cache to be applied random insertion
- p : float
the insert probability
- seed : any hashable type, optional
The seed of the random number generator
Returns: - cache : Cache
The modified cache instance
-
keyval_cache(cache)[source]¶ It modifies the instance of a cache object such that items are saved together with a value instead of just a key.
This modifies the signature and/or return types of methods get, put and dump. The new format is documented in the docstrings of the modified methods of the cache instance.
This function modifies the contract of methods of Cache objects, which is admittedly a bad software engineering practice . It may also lead to bugs in a key-value cache implementation if the base key-only cache implementation from which it derives has methods calling other methods of the same instance.
Parameters: - cache : Cache
The instance of a cache to be changed to a key-value cache
Returns: - cache : Cache
The modified cache instance
-
ttl_cache(cache, f_time)[source]¶ Return a TTL cache.
This function takes as a input a cache policy and returns a new policy where items, when inserted, are (optionally) labelled with their expiration time and are automatically evicted when their validity expires.
The time validity is verified against the return value of the callable argument f_time, which is called whenever a purging is executed.
This implementation can be used with both real time and simulated time.
Parameters: - cache : Cache
The instance of a cache to be changed to a TTL cache
- f_time : callable
A function that returns the current time (simulated or real). The return type must be a numerical value, e.g. float
Returns: - cache : Cache
The modified cache instance
Notes
The returned TTL cache performs purging operations only when has, get, put and dump operations are performed. This ensures correctness when normal caches are used with common routing and caching strategies. However, if other operations like position or len are executed, results may take into account also expired items. In such cases, it is then advisable to execute a purge first.
icarus.models.cache.systems module¶
Simple networks of caches modeled as single caches.
-
class
PathCache(caches, **kwargs)[source]¶ Bases:
objectPath of caches
This is not a single-node cache implementation but rather it implements a path of caching nodes in which requests are fed to the first node of the path and, in case of a miss, are propagated down to the remaining nodes of the path. A miss occurs if none of the nodes on the path has the requested content.
Attributes: - maxlen
Methods
put(k)Insert an item in the cache if not already inserted. clear dump get has position remove -
maxlen¶
-
name= 'PATH'¶
-
put(k)[source]¶ Insert an item in the cache if not already inserted.
If the element is already present in the cache, it will pushed to the top of the cache.
Parameters: - k : any hashable type
The item to be inserted
Returns: - evicted : any hashable type
The evicted object or None if no contents were evicted.
-
class
TreeCache(leaf_caches, root_cache, **kwargs)[source]¶ Bases:
objectPath of caches
This is not a single-node cache implementation but rather it implements a tree of caching nodes in which requests are fed to a random leaf node and, in case of a miss, are propagated down to the remaining nodes of the path. A miss occurs if none of the nodes on the path has the requested content.
Notes
This cache can only be operated in a read-through manner and not in write through or read/write aside. In other words, before issuing a put, you must issue a get for the same item. The reason for this limitation is to ensure that matching get/put requests go through the same randomly selected node.
Attributes: - maxlen
Methods
put(k)Insert an item in the cache if not already inserted. clear dump get has position remove -
maxlen¶
-
name= 'TREE'¶
-
put(k)[source]¶ Insert an item in the cache if not already inserted.
If the element is already present in the cache, it will pushed to the top of the cache.
Parameters: - k : any hashable type
The item to be inserted
Returns: - evicted : any hashable type
The evicted object or None if no contents were evicted.
-
class
ArrayCache(caches, weights=None, **kwargs)[source]¶ Bases:
objectArray of caches
This is not a single-node cache implementation but rather it implements an array of caching nodes in which requests are fed to a random node of a set.
Notes
This cache can only be operated in a read-through manner and not in write through or read/write aside. In other words, before issuing a put, you must issue a get for the same item. The reason for this limitation is to ensure that matching get/put requests go through the same randomly selected node.
Attributes: - maxlen
Methods
put(k)Insert an item in the cache if not already inserted. clear dump get has position remove -
maxlen¶
-
name= 'ARRAY'¶
-
put(k)[source]¶ Insert an item in the cache if not already inserted.
If the element is already present in the cache, it will pushed to the top of the cache.
Parameters: - k : any hashable type
The item to be inserted
Returns: - evicted : any hashable type
The evicted object or None if no contents were evicted.
-
class
ShardedCache(maxlen, policy='LRU', nodes=4, f_map=None, policy_attr={}, **kwargs)[source]¶ Bases:
icarus.models.cache.policies.CacheSet of sharded caches.
Set of caches coordinately storing items. When a request reaches the caches, the request is forwarded to the specific cache (shard) based on the outcome of a hash function. So, an item can be stored only by a single node of the system.
Attributes: - maxlen
Methods
clear()Empty the cache do(op, k, *args, **kwargs)Utility method that performs a specified operation on a given item. dump([serialized])Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy. get(k)Retrieves an item from the cache. has(k)Check if an item is in the cache without changing the internal state of the caching object. put(k)Insert an item in the cache if not already inserted. remove(k)Remove an item from the cache, if present. -
dump(serialized=True)[source]¶ Return a dump of all the elements currently in the cache possibly sorted according to the eviction policy.
Returns: - cache_dump : list
The list of all items currently stored in the cache
-
get(k)[source]¶ Retrieves an item from the cache.
Differently from has(k), calling this method may change the internal state of the caching object depending on the specific cache implementation.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
has(k)[source]¶ Check if an item is in the cache without changing the internal state of the caching object.
Parameters: - k : any hashable type
The item looked up in the cache
Returns: - v : bool
Boolean value being True if the requested item is in the cache or False otherwise
-
maxlen¶
-
name= 'SHARD'¶
-
put(k)[source]¶ Insert an item in the cache if not already inserted.
If the element is already present in the cache, it will not be inserted again but the internal state of the cache object may change.
Parameters: - k : any hashable type
The item to be inserted
Returns: - evicted : any hashable type
The evicted object or None if no contents were evicted.