octez-proto-libs 20.1 · OCaml Package

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.

type 'value t

Abstract type for a cache parameterized by the value type.

Cache layout

A layout determines the number of sub-caches as well as the size limit of those sub-caches. No assumption is made on the unit of each of those sub-cache sizes. All we use is the natural ordering of int. In particular, the size units for different sub-caches need not be the same.

There are only two constructors for a cache:

uninitialised which returns an uninitialised cache ;

from_layout which initialises a cache with a layout.

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.

type size = int

Size of sub-caches or values.

type index = int

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.

type key

Abstract type for a cache key.

type identifier = string

Identifier of a key.

val key_of_identifier : cache_index:index -> identifier -> 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.

val identifier_of_key : key -> identifier

identifier_of_key key returns the identifier associated to the key.

type value_metadata = {

size : int;
(*
size must be strictly positive. This attribute is used to computed the cache size. The unit of the size is not specified at this stage. It is up to the economic protocol to give a measure of it.
*)
birth : int64;
(*
birth must be greater than 1. This number corresponds to the number of entries inserted in the cache after the insertion of this entry. The birth is used to determine which entry is the oldest one. The risk of overflow is minor.
*)
cache_nonce : Tezos_base.TzPervasives.Bytes.t;
(*
cache_nonce identifies the block that introduced this cache entry. The nonce must uniquely identify the block which modifies this value. It cannot be the block hash for circularity reasons: The value of the nonce is stored onto the context and consequently influences the context hash of the very same block. Such nonce cannot be determined by the shell and its computation is delegated to the economic protocol.
cache_nonces are used by the shell to properly relate the cached entries with the current block and its predecessors. In particular in case of reorganizations, that is a context which is not on the same branch as the current branch, cache_nonces are used to filter out entries that do not exist in the target branch.
*)

}

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.

val lookup : 'value t -> key -> ('value * value_metadata) option

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 requested 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.

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.

type domain

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 domain_encoding : domain Tezos_base.TzPervasives.Data_encoding.t

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) result Lwt.t) ->
  ('value t, 'trace) 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:Tezos_base.TzPervasives.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 : Format.formatter -> 'value t -> unit

pp fmt cache is a pretty printer for a cache.

package octez-proto-libs

An LRU inter-blocks cache for the economic protocol

Cache layout

Keys

Cache Getters/Setters

Cache synchronisation