Revision ef8cda843ec243983b64de277678108f37087be3 authored by Alain Mebsout on 31 January 2024, 08:46:55 UTC, committed by Marge Bot on 05 February 2024, 14:08:44 UTC
1 parent 05eb698
block_store.mli
(*****************************************************************************)
(* *)
(* Open Source License *)
(* Copyright (c) 2020-2021 Nomadic Labs, <contact@nomadic-labs.com> *)
(* *)
(* Permission is hereby granted, free of charge, to any person obtaining a *)
(* copy of this software and associated documentation files (the "Software"),*)
(* to deal in the Software without restriction, including without limitation *)
(* the rights to use, copy, modify, merge, publish, distribute, sublicense, *)
(* and/or sell copies of the Software, and to permit persons to whom the *)
(* Software is furnished to do so, subject to the following conditions: *)
(* *)
(* The above copyright notice and this permission notice shall be included *)
(* in all copies or substantial portions of the Software. *)
(* *)
(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*)
(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, *)
(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL *)
(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*)
(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING *)
(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER *)
(* DEALINGS IN THE SOFTWARE. *)
(* *)
(*****************************************************************************)
(** Persistent and cached generic block store
The store instantiate a cemented block store and multiple floating
block stores. The floating stores serve as buffers until enough
blocks have arrived. Then it performs a "cementing" (also
called a "merge"). Under normal circumstances, there are two
different kinds ({!Floating_block_store.floating_kind}) of
floating stores instances: a [RO](read-only) and a
[RW](read-write). Newly arrived blocks are {b always} pushed in
the [RW] instance. The block lookup is first tried in [RW], then
[RO] and finally in the cement blocks.
This store also instantiates a LRU block cache to reduce the number
of I/O operations. This cache is updated whenever a block is read
or stored.
When a merge occurs, the [RW] instance is promoted as another
[RO'] and a new [RW'] instance replaces it. This allows retrieving
the new cycle to be cemented from [RO] and [RO'] (former [RW]) {b
asynchronously} and thus allowing new blocks to be stored in the
newly instantiated [RW] store without pausing. This asynchronous
merging thread, while retrieving the cycle to cement, also
combines [RO] and [RO'] into a {b new} [RO''] without the cemented
cycle. When the merging thread is done, the former [RO] and [RO']
instances are deleted from the disk and the new [RO''] replaces
them. A merging thread has to wait for the previous one to finish.
Retrieving the new cycle from [RO] and [RO'] from blocks [B_start]
and [B_end] means that we must retrieve the set of blocks between
them but also trim potential branches that have roots in this set.
To achieve that, we iterate over [RO] and [RO'] {b linearly}. This
means that {b every block's predecessor in floating stores must be
previously known}. Either we previously encountered it in the same
floating store file, either in [RO] if the block is in [RO'] or in
the cemented store (see invariants below). This invariant is
required to ensure minimal memory usage. The iterations done to
retrieve the cycle and merge the floating stores works similarly
to a {i stop and copy} GC algorithm. It works as follows:
- We retrieve the blocks from [B_end] to [B_start] by sequentially
reading predecessors.
- We instantiate a set of encountered block hashes with [B_end]'s
hash as initial value.
- We iterate sequentially over [RO] and [RO'] blocks and copy them
only if their predecessors is present in the visited set, adding
their hash in the process.
The result is a correct, in order and trimmed new [RO] floating
store. A visual example of merging is given below.
The merging thread will also trigger a garbage-collection of the
cemented block store w.r.t. the given history mode.
{1 Invariants}
This store is expected to respect the following invariants:
- If no merging thread is pending, two floating stores are
present: a [RO] and a [RW].
- If a merging thread is pending, there are three floating stores
present: a [RO], a [RO'] and a [RW].
- Blocks may be stored twice in {b floating stores} but only when
a merging occurs (as [RO''] is a subset of [RO]+[RO']). However,
blocks can be present in both the cemented and the floating
store (after importing a storage snapshot as the floating block
store consist in a checkpoint associated with its `max_op_ttl`
blocks which were already cemented).
- For every stored block in floating stores, its predecessor is
either already stored in the same floating store file, in a
previous floating store file or in the cemented store.
- A merging thread does not start until the previous one has
completed.
*)
(** {1 Merging example}
{v
RO RW
| C' - D' - E' G'
/ | /
A - B - | C - D - E - F - G
| \
| D'' - E''
| \
| E'''
v}
For instance, a merging from [A] to [C] will first retrieve blocks
[C], [B] and [A]. Then, iterate over all the blocks in both the
[RO] and [RW] files: reading first in [RO], then in [RW]. By
construction, blocks are stored after their predecessors. For
example, \[ A ; B ; C ; C'; D'' ; D'; D ; E ; E'' ; F ; E''' ; G'
; G \] is a valid storing sequence.
The algorithm starts iterating over this sequence and will only
copy blocks for which predecessors are present in the set S of
hash (initially S = \{ hash([C]) \}). Thus, for the given sequence,
[D''] will first be considered, S will be updated to \{ hash([C]),
hash([D]) \} and so on, until [RO] and [RW] are fully read.
The new RO will then be:
{v
G'
/
- D - E - F - G
- D'' - E''
\
E'''
v}
where its storing order will be correct with regards to the
invariant.
*)
(** The type of the block store *)
type block_store
type t = block_store
(** The type of the block's key to be accessed: a hash and an offset.
- Block (h, 0) represents the block h itself ;
- Block (h, n) represents the block's [n]th predecessor.
A block key may represent an invalid block (wrong hash and/or
offset) as it is not ensured to be valid by construction.*)
type key = Block of (Block_hash.t * int)
(** The status of the merging thread *)
type merge_status = Not_running | Running | Merge_failed of tztrace
(** [floating_block_stores block_store] returns all running floating
block store instances for [block_store]. It will always return two
or three ordered floating stores:
- [ [RO] ; [RW] ] if a merge is not occurring;
- [ [RO] ; [RO'] ; [RW] ] if a merge is occurring.
{b Warning} These stores should only be accessed when the store is
not active. *)
val genesis_block : block_store -> Block_repr.t
(** [mem block_store key] tests the existence of the block [key] in
[block_store]. *)
val mem : block_store -> key -> bool tzresult Lwt.t
(** [get_hash block_store key] retrieves the hash corresponding to the
given [key] in [block_store]. Return [None] if the block is
unknown. *)
val get_hash : block_store -> key -> Block_hash.t option tzresult Lwt.t
(** [resulting_context_hash block_store ~expect_predecessor_context key]
retrieves the resulting context hash from the block application,
corresponding to the given [key]. *)
val resulting_context_hash :
block_store ->
expect_predecessor_context:bool ->
key ->
Context_hash.t option tzresult Lwt.t
(** [read_block ~read_metadata block_store key] reads the block [key]
in [block_store] if present. Return [None] if the block is
unknown. If [read_metadata] is set to [true] it tries to retreive
the metadata but do not fail if it is not available. *)
val read_block :
read_metadata:bool -> block_store -> key -> Block_repr.t option tzresult Lwt.t
(** [read_block_metadata block_store key] reads the metadata for the
block [key] in [block_store] if present. Return [None] if the block
is unknown or if the metadata are not present. *)
val read_block_metadata :
block_store -> key -> Block_repr.metadata option tzresult Lwt.t
(** [store_block block_store block resulting_context_hash] stores the
[block] in the current [RW] floating store with its associated
[resulting_context_hash]. *)
val store_block :
block_store -> Block_repr.t -> Context_hash.t -> unit tzresult Lwt.t
(** In this faked implementation, the caboose is always equal to the genesis block. *)
val caboose : block_store -> Store_types.block_descriptor Lwt.t
(** [create ?block_cache_limit ~chain_dir ~genesis_block] instantiates
a fresh [block_store] in directory [chain_dir] and stores the
[genesis_block] in it. It fails if the given [chain_dir] is already
populated. Setting the [block_cache_limit] allows to override the
default block cache size. *)
val create :
?block_cache_limit:int ->
[`Chain_dir] Naming.directory ->
genesis_block:Block_repr.t ->
block_store tzresult Lwt.t
(** [close block_store] closes the [block_store] and every underlying
opened stores.
{b Warning} If a merging thread is occurring, it will wait up to
5s for its termination before effectively closing the store. *)
val close : block_store -> unit Lwt.t
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...