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
- type SecondaryOffset = Word32
-
data
PrimaryIndex
=
MkPrimaryIndex
{
- primaryIndexChunkNo :: ! ChunkNo
- primaryIndexOffsets :: !( Vector SecondaryOffset )
- appendOffsets :: ( Monad m, Foldable f, HasCallStack ) => HasFS m h -> Handle h -> f SecondaryOffset -> m ()
- backfill :: RelativeSlot -> RelativeSlot -> SecondaryOffset -> [ SecondaryOffset ]
- backfillChunk :: ChunkInfo -> ChunkNo -> NextRelativeSlot -> SecondaryOffset -> [ SecondaryOffset ]
- containsSlot :: PrimaryIndex -> RelativeSlot -> Bool
- currentVersionNumber :: Word8
- filledSlots :: ChunkInfo -> PrimaryIndex -> [ RelativeSlot ]
- firstFilledSlot :: ChunkInfo -> PrimaryIndex -> Maybe RelativeSlot
- getLastSlot :: ChunkInfo -> PrimaryIndex -> Maybe RelativeSlot
- isFilledSlot :: HasCallStack => PrimaryIndex -> RelativeSlot -> Bool
- lastFilledSlot :: HasCallStack => ChunkInfo -> PrimaryIndex -> Maybe RelativeSlot
- lastOffset :: PrimaryIndex -> SecondaryOffset
- load :: forall blk m h. ( HasCallStack , MonadThrow m, StandardHash blk, Typeable blk) => Proxy blk -> HasFS m h -> ChunkNo -> m PrimaryIndex
- nextFilledSlot :: ChunkInfo -> PrimaryIndex -> RelativeSlot -> Maybe RelativeSlot
- offsetOfSlot :: HasCallStack => PrimaryIndex -> RelativeSlot -> SecondaryOffset
- open :: ( HasCallStack , MonadCatch m) => HasFS m h -> ChunkNo -> AllowExisting -> m ( Handle h)
- readFirstFilledSlot :: forall blk m h. ( HasCallStack , MonadThrow m, StandardHash blk, Typeable blk) => Proxy blk -> HasFS m h -> ChunkInfo -> ChunkNo -> m ( Maybe RelativeSlot )
- readOffset :: forall blk m h. ( HasCallStack , MonadThrow m, StandardHash blk, Typeable blk) => Proxy blk -> HasFS m h -> ChunkNo -> RelativeSlot -> m ( Maybe SecondaryOffset )
- readOffsets :: 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 ))
- secondaryOffsetSize :: Word64
- sizeOfSlot :: HasCallStack => PrimaryIndex -> RelativeSlot -> Word32
- slots :: PrimaryIndex -> Word64
- truncateToSlot :: ChunkInfo -> RelativeSlot -> PrimaryIndex -> PrimaryIndex
- truncateToSlotFS :: ( HasCallStack , MonadThrow m) => HasFS m h -> ChunkNo -> RelativeSlot -> m ()
- unfinalise :: ( HasCallStack , MonadThrow m, StandardHash blk, Typeable blk) => Proxy blk -> HasFS m h -> ChunkInfo -> ChunkNo -> m ()
- write :: ( HasCallStack , MonadThrow m) => HasFS m h -> ChunkNo -> PrimaryIndex -> m ()
- mk :: ChunkNo -> [ SecondaryOffset ] -> Maybe PrimaryIndex
- toSecondaryOffsets :: PrimaryIndex -> [ SecondaryOffset ]
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
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 ] |
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
).
lastFilledSlot :: HasCallStack => ChunkInfo -> PrimaryIndex -> Maybe RelativeSlot Source #
Return the last filled slot in the primary index.
lastOffset :: PrimaryIndex -> SecondaryOffset Source #
Return the last
SecondaryOffset
in the primary index file.
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.
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.
|
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.
toSecondaryOffsets :: PrimaryIndex -> [ SecondaryOffset ] Source #
Return the
SecondaryOffset
s in the
PrimaryIndex
.