An LRU inter-blocks cache for the economic protocol
This is for use *within* the Environment_context
only.
Frequently used data should be kept in memory and persist along a chain of blocks. The caching mechanism allows the economic protocol to declare such data and to rely on an Least Recently Used strategy to keep the cache size under a fixed limit.
One important difficulty is to correctly maintain this in-memory cache. There are three issues related to this mechanism from the shell perspective:
1. The in-memory cache must take chain reorganization into account. (Chain reorganizations occur when the node's preferred chain is not the one that has been chosen by the consensus algorithm.)
2. The in-memory cache must be completely determined by the storage.
3. The loading of the cache should introduce minimal latency during node reboots, RPC processing, or other operations. The cache should also have similar reactivity time on every node, independently of the fact that the node has just been rebooted or not.
This module implements the core logic of the cache mechanism (not the storage) part. The implementation provided to the protocol is implemented in Environment_context.Cache
.
The type of a cache is parameterized by the type of the values stored.
When a value is cached, we also stored metadata about the status of this value in the cache. The value's key and its metadata are the only data stored in the context. The set of all the keys and metadatas of the cache is called the *domain*.
The actual cached values are introduced at runtime during cache lifetime. When the node needs to load a cache in memory for a specific context, it uses a *builder*, i.e., a function which reconstructs a cached value from a key. We can reconstruct all the values in a cache given its domain. In practice, such builder is provided by the cache mechanism client, i.e., the economic protocol.
Finally, notice that the cache is divided into sub-caches which have their own size limit. Each sub-cache is referenced by an index (as a positive integer). This layout is defined by the economic protocol.
Abstract type for a cache parameterized by the value type.
Cache layout
A layout determines the number of sub-caches as well as the limit of those sub-caches. No assumption is made on the unit of each of those size. All we use is the natural ordering of int
.
There are only two constructors for a cache:
Moreover, the layout of the cache cannot be resized. This way, the cache's layout is determined uniquely by the one given to from_layout
.
The only way to change the layout
of a cache is to create a new cache and explicitly copy all the values from the previous cache to the new one. Such constraint may be relaxed in the future if necessary.
Size of sub-caches or values.
Index of the subcache in the cache. Values of this type should stay between 0
and 16383
.
val uninitialised : 'value t
uninitialised
is a special value which identify cache without a layout. Most functions of this interface will raise Invalid_argument
is they are called on this value.
val from_layout : size list -> 'value t
from_layout layout
initializes a cache with the layout
. Such function is intended to be called by the init
function of the economic protocol. In particular, this means that the cache's values will be reset after stitching of context.
val compatible_layout : 'value t -> size list -> bool
compatible_layout cache layout
returns true
if the layout is compatible with the one cache
was initialised with, false
otherwise. By compatible, we mean that the layouts are actually precisely the same.
val clear : 'value t -> 'value t
clear cache
resets the cache
except the layout. It is equivalent to from_layout layout
where layout
was the layout
provided to initialise the cache.
Keys
A key is built from an identifier and an index of the corresponding cache.
Abstract type for a cache key.
key_of_identifier ~cache_index identifier
builds a key from the cache_index
and the identifier
.
No checks are made to ensure the validity of the index.
identifier_of_key key
returns the identifier associated to the key
.
Metadata associated to a value in the cache.
Cache Getters/Setters
val find : 'value t -> key -> 'value option
find cache key
is Some v
if key
has an associated cached value v
in cache
, or None
otherwise.
lookup cache key
is Some (v, m)
where v
is the value associated to key
and m
is the corresponding metadata. This function returns None
if key
is not in the cache domain.
val update : 'value t -> key -> ('value * size) option -> 'value t
update cache key request
returns a new version of cache
where a request
ed change has been applied to the key
.
More specifically:
update cache key None
removes key
from the cache
.
update cache key (Some (value, size))
is cache
where key
is now associated to value
.
The metadata of the key
is also updated in the returned cache:
- the
size
field is modified in the metadata ; - the
birth
is the higher birth, so that the key is the most recently used key.
The cache_nonce
of the entry is preserved.
If the cache is full, the insertion of a new entry provokes the removal of the least recently used entries.
update_cache_key caches key value meta
updates the cache to associate key
to the value
with some meta
data.
val future_cache_expectation : 'value t -> time_in_blocks:int -> 'value t
future_cache_expectation cache ~time_in_blocks
returns a predicted cache that tries to anticipate the state of cache
in time_in_blocks
. This function is using an heuristic.
Cache synchronisation
Synchronisation of a cache aims to be done once all the accesses to the caches have been done by the economic protocol.
For each value added or updated since the last synchronisation, they are updated with the nonce
provided by the economic protocol.
The domain is the on-disk representation of the cache. Notice that in-memory values must be constructed from a domain to get a cache.
val empty_domain : domain -> bool
empty_domain d
returns true
iff d
is the domain of an uninitialized cache.
val from_cache :
'value t ->
domain ->
value_of_key:(key -> ('value, 'trace) Stdlib.result Lwt.t) ->
('value t, 'trace) Stdlib.result Lwt.t
from_cache initial domain ~value_of_key
initializes a cache with the given domain
by reusing values from initial
if nonces match, or by calling value_of_key
otherwise.
domain
and initial
must share the same layout.
This function is typically used when the cache is loaded from the context. See Environment_context
.
val sync : 'value t -> cache_nonce:Stdlib.Bytes.t -> 'value t * domain
sync cache ~cache_nonce
computes a new cache with a new domain.
Various functions used to introspect the content of the cache.
val number_of_caches : 'value t -> int
number_of_caches cache
returns the number of sub-caches in the cache.
val cache_size : 'value t -> cache_index:int -> size option
cache_size cache ~cache_index
returns an overapproximation of the size of the cache. Returns None
if cache_index
is an invalid index.
val cache_size_limit : 'value t -> cache_index:int -> size option
cache_size_limit cache ~cache_index
returns the maximal size of the cache indexed by cache_index
. Returns None
if cache_index
is an invalid index.
val list_keys : 'value t -> cache_index:index -> (key * size) list option
list_keys cache ~cache_index
returns the list of keys along with their size recorded into the subcache with index cache_index
.
val key_rank : 'value t -> key -> int option
key_rank cache key
returns the rank of the value associated to the given key
. The rank is defined as the number of values older than the current one. Returns None
if the key
is not in the cache.
val pp : Stdlib.Format.formatter -> 'value t -> unit
pp fmt cache
is a pretty printter for a cache
.