ouroboros-consensus-0.1.0.2: Consensus layer for the Ouroboros blockchain protocol

Ouroboros.Consensus.Storage.ImmutableDB.Impl.Index.Primary

Description

Primary Index

Intended for qualified import > import qualified Ouroboros.Consensus.Storage.ImmutableDB.Impl.Index.Primary as PrimaryIndex

Synopsis

# SecondaryOffset

An offset in the secondary index file.

We need 4 bytes (Word32) because the secondary index file can grow to +1MiB.

# PrimaryIndex

In-memory representation of the primary index file.

The primary index maps relative slots to offsets in the secondary index file. The first offset is always 0, as the first entry in the secondary index file will always start at offset 0. The second offset will be equal to the size of a secondary index entry, unless the slot is empty, in which case it will be 0. In general, an offset will either be a repetition of the offset before it, to indicate the slot is empty, or the offset before it + the fixed size of a secondary index entry, in case the slot is filled.

The size of a secondary index entry can be computed by subtracting the offset corresponding to the respective slot from the offset corresponding to the slot after it.

For example, if slots 0, 1 and 4 are filled, we'd have the following offsets in the primary index file:

slot:       0   1   2   3   4
┌───┬───┬───┬───┬───┬───┐
offset: │ 0 │ x │ y │ y │ y │ z │
└───┴───┴───┴───┴───┴───┘

We use x, y, z in the example above, but in practice these will be multiples of the (fixed) size of an entry in secondary index.

TODO As all entries have the same size, we could use a bitvector instead, see #1234.

The serialisation of a primary index file starts with currentVersionNumber followed by all its offset.

Constructors

 MkPrimaryIndex FieldsprimaryIndexChunkNo ∷ !ChunkNoThe ChunkNo of the chunk this index is associated withprimaryIndexOffsets ∷ !(Vector SecondaryOffset)The entries in the index proper

#### Instances

Instances details
 Source # Instance details Methods Source # Instance details Methods Source # Instance details Associated Types Methods Source # Instance details MethodsnoThunks ∷ Context → PrimaryIndex → IO (Maybe ThunkInfo) #wNoThunks ∷ Context → PrimaryIndex → IO (Maybe ThunkInfo) # type Rep PrimaryIndex Source # Instance details type Rep PrimaryIndex = D1 ('MetaData "PrimaryIndex" "Ouroboros.Consensus.Storage.ImmutableDB.Impl.Index.Primary" "ouroboros-consensus-0.1.0.2-inplace" 'False) (C1 ('MetaCons "MkPrimaryIndex" 'PrefixI 'True) (S1 ('MetaSel ('Just "primaryIndexChunkNo") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 ChunkNo) :*: S1 ('MetaSel ('Just "primaryIndexOffsets") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (Vector SecondaryOffset))))

appendOffsets ∷ (Monad m, Foldable f, HasCallStack) ⇒ HasFS m h → Handle h → f SecondaryOffset → m () Source #

Append the given SecondaryOffset to the end of the file (passed as a handle).

Arguments

 ∷ RelativeSlot The slot to write to (>= next expected slot) → RelativeSlot The next expected slot to write to → SecondaryOffset The last SecondaryOffset written to → [SecondaryOffset]

Return the slots to backfill the primary index file with.

A situation may arise in which we "skip" some relative slots, and we write into the DB, for example, every other relative slot. In this case, we need to backfill the primary index file with offsets for the skipped relative slots. Similarly, before we start a new chunk, we must backfill the primary index file of the current chunk to indicate that the remaining slots in the chunk are empty.

For example, say we have written to relative slots 0 and 1. We have the following primary index file:

slot:       0   1
┌───┬───┬───┐
offset: │ 0 │ x │ y │
└───┴───┴───┘

Now we want to write to relative slot 4, skipping 2 and 3. We first have to backfill the primary index by repeating the last offset for the two missing slots:

slot:       0   1   2   3
┌───┬───┬───┬───┬───┐
offset: │ 0 │ x │ y │ y │ y │
└───┴───┴───┴───┴───┘

After backfilling (writing the offset y twice), we can write the next offset:

slot:       0   1   2   3   4
┌───┬───┬───┬───┬───┬───┐
offset: │ 0 │ x │ y │ y │ y │ z │
└───┴───┴───┴───┴───┴───┘

For the example above, the output of this function would thus be: [y, y].

We use x, y, z in the examples above, but in practice these will be multiples of the (fixed) size of an entry in secondary index.

Return the slots to backfill the primary index file with when padding it to the chunk size.

See backfill for more details.

Check whether the given slot is within the primary index.

Version number of the index format

Return a list of all the filled (length > zero) slots in the primary index.

Find the first filled (length > zero) slot in the primary index. If there is none, return Nothing.

Example: given the primary index below:

slot:       0   1
┌───┬───┬───┐
offset: │ 0 │ 0 │ x │
└───┴───┴───┘

Return slot 1.

Return the last slot of the primary index (empty or not).

Returns Nothing if the index is empty.

Return True when the given slot is filled.

Precondition: the given slot must be within the primary index (containsSlot).

Return the last filled slot in the primary index.

Return the last SecondaryOffset in the primary index file.

load ∷ ∀ blk m h. (HasCallStack, MonadThrow m, StandardHash blk, Typeable blk) ⇒ Proxy blk → HasFS m h → ChunkNo → m PrimaryIndex Source #

Load a primary index file in memory.

Find the next filled (length > zero) slot after the given slot in the primary index. If there is none, return Nothing.

Precondition: the given slot must be within the primary index (containsSlot).

Example: given the primary index below and slot 1:

slot:       0   1   2   3   4
┌───┬───┬───┬───┬───┬───┐
offset: │ 0 │ x │ y │ y │ y │ z │
└───┴───┴───┴───┴───┴───┘

Return slot 4.

Return the offset for the given slot.

Precondition: the given slot must be within the primary index (containsSlot).

open ∷ (HasCallStack, MonadCatch m) ⇒ HasFS m h → ChunkNoAllowExisting → m (Handle h) Source #

Open a primary index file for the given chunk and return a handle to it.

The file is opened with the given AllowExisting value. When given MustBeNew, the version number is written to the file.

readFirstFilledSlot ∷ ∀ blk m h. (HasCallStack, MonadThrow m, StandardHash blk, Typeable blk) ⇒ Proxy blk → HasFS m h → ChunkInfoChunkNo → m (Maybe RelativeSlot) Source #

Return the first filled slot in the primary index file, or Nothing in case there are no filled slots.

PRECONDITION: the index file must exist and contain at least the version number and offset 0.

May throw InvalidPrimaryIndexException.

readOffset ∷ ∀ blk m h. (HasCallStack, MonadThrow m, StandardHash blk, Typeable blk) ⇒ Proxy blk → HasFS m h → ChunkNoRelativeSlot → m (Maybe SecondaryOffset) Source #

Read the SecondaryOffset corresponding to the given relative slot in the primary index. Return Nothing when the slot is empty.

Arguments

 ∷ ∀ blk m h t. (HasCallStack, MonadThrow m, Traversable t, StandardHash blk, Typeable blk) ⇒ Proxy blk → HasFS m h → ChunkNo → t RelativeSlot → m (t (Maybe SecondaryOffset)) The offset in the secondary index file corresponding to the given slot. Nothing when the slot is empty.

Same as readOffset, but for multiple offsets.

NOTE: only use this for a few offsets, as we will seek (pread) for each offset. Use load if you want to read the whole primary index.

The size of each entry in the primary index file, i.e., the size of a SecondaryOffset.

Return the size of the given slot according to the primary index.

Precondition: the given slot must be within the primary index (containsSlot).

Count the number of (filled or unfilled) slots currently in the index

Truncate the primary index so that the given RelativeSlot will be the last slot (filled or not) in the primary index, unless the primary index didn't contain the RelativeSlot in the first place.

truncateToSlotFS ∷ (HasCallStack, MonadThrow m) ⇒ HasFS m h → ChunkNoRelativeSlot → m () Source #

On-disk variant of truncateToSlot. The truncation is done without reading the primary index from disk.

unfinalise ∷ (HasCallStack, MonadThrow m, StandardHash blk, Typeable blk) ⇒ Proxy blk → HasFS m h → ChunkInfoChunkNo → m () Source #

Remove all trailing empty slots that were added during the finalisation/backfilling of the primary index.

POSTCONDITION: the last slot of the primary index file will be filled, unless the index itself is empty.

write ∷ (HasCallStack, MonadThrow m) ⇒ HasFS m h → ChunkNoPrimaryIndex → m () Source #

Write a primary index to a file.

Property: for hasFS, err, chunk

'write' hasFS chunk primaryIndex
primaryIndex' <- 'load' hasFS err chunk

Then it must be that:

primaryIndex === primaryIndex'

# Exported for testing purposes

Smart constructor: checks that the offsets are non-decreasing, there is at least one offset, and that the first offset is 0.

Return the SecondaryOffsets in the PrimaryIndex.