ouroboros-consensus-0.1.0.1: Consensus layer for the Ouroboros blockchain protocol
Safe Haskell None
Language Haskell2010

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

type SecondaryOffset = Word32 Source #

An offset in the secondary index file.

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

PrimaryIndex

data PrimaryIndex Source #

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

Fields

Instances

Instances details
Eq PrimaryIndex Source #
Instance details

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

Show PrimaryIndex Source #
Instance details

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

Generic PrimaryIndex Source #
Instance details

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

NoThunks PrimaryIndex Source #
Instance details

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

type Rep PrimaryIndex Source #
Instance details

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

type Rep PrimaryIndex = D1 (' MetaData "PrimaryIndex" "Ouroboros.Consensus.Storage.ImmutableDB.Impl.Index.Primary" "ouroboros-consensus-0.1.0.1-DT4Cvwf63DZKctsEvaJqCU" ' 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).

backfill Source #

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.

backfillChunk :: ChunkInfo -> ChunkNo -> NextRelativeSlot -> SecondaryOffset -> [ SecondaryOffset ] Source #

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

See backfill for more details.

containsSlot :: PrimaryIndex -> RelativeSlot -> Bool Source #

Check whether the given slot is within the primary index.

currentVersionNumber :: Word8 Source #

Version number of the index format

filledSlots :: ChunkInfo -> PrimaryIndex -> [ RelativeSlot ] Source #

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

firstFilledSlot :: ChunkInfo -> PrimaryIndex -> Maybe RelativeSlot Source #

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.

getLastSlot :: ChunkInfo -> PrimaryIndex -> Maybe RelativeSlot Source #

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

Returns Nothing if the index is empty.

isFilledSlot :: HasCallStack => PrimaryIndex -> RelativeSlot -> Bool Source #

Return True when the given slot is filled.

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

load :: forall 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.

nextFilledSlot :: ChunkInfo -> PrimaryIndex -> RelativeSlot -> Maybe RelativeSlot Source #

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.

offsetOfSlot :: HasCallStack => PrimaryIndex -> RelativeSlot -> SecondaryOffset Source #

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 -> ChunkNo -> AllowExisting -> 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 :: forall blk m h. ( HasCallStack , MonadThrow m, StandardHash blk, Typeable blk) => Proxy blk -> HasFS m h -> ChunkInfo -> ChunkNo -> 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 :: forall blk m h. ( HasCallStack , MonadThrow m, StandardHash blk, Typeable blk) => Proxy blk -> HasFS m h -> ChunkNo -> RelativeSlot -> m ( Maybe SecondaryOffset ) Source #

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

readOffsets Source #

Arguments

:: forall 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.

secondaryOffsetSize :: Word64 Source #

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

sizeOfSlot :: HasCallStack => PrimaryIndex -> RelativeSlot -> Word32 Source #

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

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

slots :: PrimaryIndex -> Word64 Source #

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

truncateToSlot :: ChunkInfo -> RelativeSlot -> PrimaryIndex -> PrimaryIndex Source #

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 -> ChunkNo -> RelativeSlot -> 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 -> ChunkInfo -> ChunkNo -> 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 -> ChunkNo -> PrimaryIndex -> 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

mk :: ChunkNo -> [ SecondaryOffset ] -> Maybe PrimaryIndex Source #

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