margaret

README

Margaret

Margaret is go-ssb's append-only log* provider, and greatly inspired by flumedb. Compatible with Go 1.13+.

the project name is inspired by Twin Peaks's character Margaret aka the log lady

Margaret has the following facilities:

• an append-only log interface .Append(interface{}), .Get(int64)
• queries .Query(...QuerySpec) for retrieving ranges based on sequence numbers e.g. .Gt(int64), or limiting the amount of data returned .Limit(int64)
• a variety of index mechanisms, both for categorizing log entries into buckets and for creating virtual logs (aka sublogs)

Margaret is one of a few key components that make the go implementation of ssb tick, for example:

• ssb/sbot uses margaret for storing each peer's data

Log storage

Margaret outputs data according to the offset2 format, which is inspired by (but significantly differs from) flumelog-offset.

In brief: margaret stores the data of all logs in the three following files:

• data stores the actual data (with a length-prefix before each entry)
• ofst indexes the starting locations for each data entry in data
• jrnl an integrity checking mechanism for all three files; a checksum of sorts, more details

More details

There are a few concepts that might be tough to digest for newcomers on first approach:

• multilogs, a kind of tree-based index, where each leaf is a margaret.Log
  • in other words: it creates virtual sublogs that map to entries in an offset log (see log storage above)
• margaret/indexes similar to leveldb indexes (arbitrary key-value stores)
• sublogs (and rxLog/receiveLog/offsetLog and its equivalence to offset.log)
• queries
• zeroing out, or replacing, written data

For more on these concepts, visit the dev.scutttlebutt.nz portal for in-depth explanations.

* margaret is technically an append-based log, as there is support for both zeroing out and replacing items in the log after they have been written. Given the relative ubiquity of append-only logs & their uses, it's easier to just say append-only log.

Documentation

Overview

SPDX-FileCopyrightText: 2021 The margaret Authors

SPDX-License-Identifier: MIT Package margaret provides a generic append-only log implementation.

Index

• Constants
• Variables
• func IsErrNulled(err error) bool
• func NewFailedIterator[T Encodeable](err error) iteratorWrapper[T]
• func NewIterWrapper[T Encodeable](yield func(func(int64, T) bool)) iteratorWrapper[T]
• func NewLiveIterWrapper[T Encodeable](yield func(func(int64, T) bool), errFn func() error) iteratorWrapper[T]
• func NewValue[T any]() T
• type Alterable
• type AppendHook
• type BatchAppender
• type Encodeable
• type HookableLog
• type Log
• type NullableLog
• type QueryConfig
  • func ApplyQueryOptions(opts ...QueryOption) (QueryConfig, error)
  • func (cfg QueryConfig) Bounds(logSeq int64) (start, end int64)
• type QueryIterator
• type QueryOption
  • func Gt(n int64) QueryOption
  • func Gte(n int64) QueryOption
  • func Limit(n int) QueryOption
  • func Live(ctx context.Context) QueryOption
  • func Lt(n int64) QueryOption
  • func Lte(n int64) QueryOption
  • func Reverse(yes bool) QueryOption
• type ReplaceableLog
• type SeqWrapper
  • func WrapWithSeq(v interface{}, seq int64) SeqWrapper
• type Seqer

Constants

const (
	// SeqEmpty is the current sequence number of an empty log
	SeqEmpty int64 = -1

	// SeqErrored is returned if an operation (like Append) fails
	SeqErrored int64 = -2

	SeqSublogDeleted int64 = -255
)

Variables

var (
	ErrOutOfBounds = errors.New("margaret: out-of-bounds access")
	ErrNulled      = errors.New("margaret: Entry Nulled")
)

Functions

func IsErrNulled

func IsErrNulled(err error) bool

IsErrNulled returns true if the error indicates a nulled entry.

func NewFailedIterator

func NewFailedIterator[T Encodeable](err error) iteratorWrapper[T]

func NewIterWrapper

func NewIterWrapper[T Encodeable](yield func(func(int64, T) bool)) iteratorWrapper[T]

func NewLiveIterWrapper

func NewLiveIterWrapper[T Encodeable](yield func(func(int64, T) bool), errFn func() error) iteratorWrapper[T]

NewLiveIterWrapper creates an iterator whose error is determined after iteration completes.

func NewValue

func NewValue[T any]() T

NewValue creates a new instance of T, properly handling pointer types. For pointer types like *Foo, it allocates a new Foo and returns *Foo. For value types like Foo, it returns the zero value.

Types

type Alterable

type Alterable[T Encodeable] interface {
	NullableLog[T]
	ReplaceableLog[T]
}

Alterable combines nullable and replaceable capabilities.

type AppendHook

type AppendHook[T Encodeable] func(seq int64, value T)

AppendHook is called after a successful append. Useful for building live subscriptions on top.

type BatchAppender

type BatchAppender[T Encodeable] interface {
	// AppendBatch appends multiple values atomically.
	// Returns the sequence number of each appended entry.
	// If any write fails mid-batch, the log is rolled back to its
	// pre-batch state and an error is returned.
	// An empty batch (len(values) == 0) returns nil, nil.
	AppendBatch(values []T) ([]int64, error)
}

BatchAppender extends a log with atomic multi-entry append. Implementations write all entries under a single lock and fsync once.

type Encodeable

type Encodeable interface {
	encoding.BinaryMarshaler
	encoding.BinaryUnmarshaler
}

type HookableLog

type HookableLog[T Encodeable] interface {
	Log[T]
	// OnAppend registers a hook called after each append.
	// Returns a function to unregister the hook.
	OnAppend(AppendHook[T]) (unregister func())
}

HookableLog supports registering append hooks.

type Log

type Log[T Encodeable] interface {
	// Seq returns the current sequence number (latest entry index).
	// Returns SeqEmpty (-1) if the log is empty.
	Seq() int64

	// Append adds a value to the log and returns its sequence number.
	Append(T) (int64, error)

	// Get retrieves the value at the given sequence number.
	Get(seq int64) (T, error)

	// Query returns an iterator over log entries matching the query options.
	Query(...QueryOption) QueryIterator[T]

	io.Closer
}

Log is a generic append-only log.

type NullableLog

type NullableLog[T Encodeable] interface {
	Log[T]
	// Null zeroes out the entry at seq. The entry still exists but contains no data.
	Null(seq int64) error
}

NullableLog extends Log with the ability to null (zero out) entries.

type QueryConfig

type QueryConfig struct {
	Gt      *int64 // Greater than
	Gte     *int64 // Greater than or equal
	Lt      *int64 // Less than
	Lte     *int64 // Less than or equal
	Limit   int    // Max entries (0 = unlimited)
	Reverse bool   // Iterate in reverse order
	Live    bool   // Follow new entries as they are appended
	Ctx     context.Context
}

QueryConfig holds query parameters.

func ApplyQueryOptions

func ApplyQueryOptions(opts ...QueryOption) (QueryConfig, error)

ApplyQueryOptions builds a QueryConfig from options.

func (QueryConfig) Bounds

func (cfg QueryConfig) Bounds(logSeq int64) (start, end int64)

Bounds calculates the effective start/end sequence from config and log length.

type QueryIterator

type QueryIterator[T any] interface {
	Iter() iter.Seq2[int64, T]

	// Err should be checked after draining the iterator
	Err() error
}

type QueryOption

type QueryOption func(*QueryConfig) error

QueryOption configures a query.

func Gt

func Gt(n int64) QueryOption

Gt returns only entries with seq > n.

func Gte

func Gte(n int64) QueryOption

Gte returns only entries with seq >= n.

func Limit

func Limit(n int) QueryOption

Limit returns at most n entries.

func Live

func Live(ctx context.Context) QueryOption

Live follows new entries as they are appended. The iterator blocks waiting for new entries until ctx is cancelled. Lt and Lte are ignored in live mode (there is no upper bound).

func Lt

func Lt(n int64) QueryOption

Lt returns only entries with seq < n.

func Lte

func Lte(n int64) QueryOption

Lte returns only entries with seq <= n.

func Reverse

func Reverse(yes bool) QueryOption

Reverse iterates from newest to oldest.

type ReplaceableLog

type ReplaceableLog[T Encodeable] interface {
	Log[T]
	// Replace overwrites the entry at seq. New data must fit in existing space.
	Replace(seq int64, data []byte) error
}

ReplaceableLog extends Log with the ability to replace entries.

type SeqWrapper

type SeqWrapper interface {
	Seqer

	// Value returns the item itself.
	Value() interface{}
}

SeqWrapper wraps a value to attach a sequence number to it.

func WrapWithSeq

func WrapWithSeq(v interface{}, seq int64) SeqWrapper

WrapWithSeq wraps the value v to attach a sequence number to it.

type Seqer

type Seqer interface {
	Seq() int64
}

Seqer returns the current sequence of a log