stm

Documentation

Overview

Package stm implements software-transactional memory (STM).

TODO(documentation):

• Overview of STM and MVCC
• Invariants (no mutation, etc.)
• Security model (OCAP and TableRef)

Index

• type Factory
  • func (f *Factory) NewScheduler() (s Scheduler, err error)
  • func (f *Factory) Register(name string, t *memdb.TableSchema) TableRef
• type Scheduler
  • func (s Scheduler) Snapshot() Scheduler
  • func (s Scheduler) Txn(write bool) Txn
• type TableRef
• type Txn
  • func (t Txn) Abort()
  • func (t Txn) Changes() memdb.Changes
  • func (t Txn) Commit()
  • func (t Txn) Defer(fn func())
  • func (t Txn) Delete(table TableRef, v any) error
  • func (t Txn) DeleteAll(table TableRef, index string, args ...any) (int, error)
  • func (t Txn) DeletePrefix(table TableRef, prefix_index string, prefix string) (bool, error)
  • func (t Txn) First(table TableRef, index string, args ...any) (any, error)
  • func (t Txn) FirstWatch(table TableRef, index string, args ...any) (<-chan struct{}, any, error)
  • func (t Txn) Get(table TableRef, index string, args ...any) (memdb.ResultIterator, error)
  • func (t Txn) GetReverse(table TableRef, index string, args ...any) (memdb.ResultIterator, error)
  • func (t Txn) Insert(table TableRef, v any) error
  • func (t Txn) Last(table TableRef, index string, args ...any) (any, error)
  • func (t Txn) LastWatch(table TableRef, index string, args ...any) (<-chan struct{}, any, error)
  • func (t Txn) LongestPrefix(table TableRef, index string, args ...any) (any, error)
  • func (t Txn) LowerBound(table TableRef, index string, args ...any) (memdb.ResultIterator, error)
  • func (t Txn) ReverseLowerBound(table TableRef, index string, args ...any) (memdb.ResultIterator, error)
  • func (t Txn) Snapshot() Txn
  • func (t Txn) TrackChanges()

Types

type Factory

type Factory struct {
	// contains filtered or unexported fields
}

Factory populates a memdb schema and generates secure TableRefs.

func (*Factory) NewScheduler

func (f *Factory) NewScheduler() (s Scheduler, err error)

NewScheduler returns a Scheduler, initialized with the tables that have have been registered to the Factory before the call. Successive calls to NewScheduler produce independent instances of Scheduler that do not share any additional state beyond the underlying schema and TableRefs.

func (*Factory) Register

func (f *Factory) Register(name string, t *memdb.TableSchema) TableRef

Register a table schema for the scheduler. The returned TableRef is required for operations against the table defined by t. If a schema already exists with the supplied name, Register will panic.

type Scheduler

type Scheduler struct {
	// contains filtered or unexported fields
}

Scheduler provides transactions that guarantee the ACID properties of Atomicity, Consistency and Isolation.

Objects managed by the scheduler are updated through MVCC. These objects are not copied, and MUST NOT be modified in-place after they have been inserted. For the avoidance of doubt, said objects MUST NOT be updated after they have been deleted from the scheduler since they may still be present in snapshots held by other goroutines.

func (Scheduler) Snapshot

func (s Scheduler) Snapshot() Scheduler

Snapshot is used to capture a point-in-time snapshot of the database that will not be affected by any write operations to the existing Scheduler.

If the Scheduler is storing reference-based values (pointers, maps, slices, etc.), the Snapshot will not deep copy those values. Therefore, it is still unsafe to modify any inserted values in either DB.

func (Scheduler) Txn

func (s Scheduler) Txn(write bool) Txn

Txn is used to start a new transaction in either read or write mode. There can only be a single concurrent writer, but any number of readers.

type TableRef

type TableRef struct {
	// contains filtered or unexported fields
}

TableRef is a token that allows the holder to designate a table in the Scheduler. It is effectively an object capability that confers access to a given table. The table's name is kept in a private field to prevent unauthorized code from designating the table (i.e. unauthorized users have no way to pass in a table).

type Txn

type Txn struct {
	// contains filtered or unexported fields
}

Txn is a transaction against a Scheduler instance. This can be a read or write transaction.

func (Txn) Abort

func (t Txn) Abort()

Abort is used to cancel this transaction. This is a noop for read transactions, already aborted or committed transactions.

func (Txn) Changes

func (t Txn) Changes() memdb.Changes

Changes returns the set of object changes that have been made in the transaction so far. If change tracking is not enabled it wil always return nil. It can be called before or after Commit. If it is before Commit it will return all changes made so far which may not be the same as the final Changes. After abort it will always return nil. As with other Txn methods it's not safe to call this from a different goroutine than the one making mutations or committing the transaction. Mutations will appear in the order they were performed in the transaction but multiple operations to the same object will be collapsed so only the effective overall change to that object is present. If transaction operations are dependent (e.g. copy object X to Y then delete X) this might mean the set of mutations is incomplete to verify history, but it is complete in that the net effect is preserved (Y got a new value, X got removed).

func (Txn) Commit

func (t Txn) Commit()

Commit is used to finalize this transaction. This is a noop for read transactions, already aborted or committed transactions.

func (Txn) Defer

func (t Txn) Defer(fn func())

Defer is used to push a new arbitrary function onto a stack which gets called when a transaction is committed and finished. Deferred functions are called in LIFO order, and only invoked at the end of write transactions.

func (Txn) Delete

func (t Txn) Delete(table TableRef, v any) error

Delete is used to delete a single object from the given table. This object must already exist in the table.

func (Txn) DeleteAll

func (t Txn) DeleteAll(table TableRef, index string, args ...any) (int, error)

DeleteAll is used to delete all the objects in a given table matching the constraints on the index

func (Txn) DeletePrefix

func (t Txn) DeletePrefix(table TableRef, prefix_index string, prefix string) (bool, error)

DeletePrefix is used to delete an entire subtree based on a prefix. The given index must be a prefix index, and will be used to perform a scan and enumerate the set of objects to delete. These will be removed from all other indexes, and then a special prefix operation will delete the objects from the given index in an efficient subtree delete operation.

This is useful when you have a very large number of objects indexed by the given index, along with a much smaller number of entries in the other indexes for those objects.

func (Txn) First

func (t Txn) First(table TableRef, index string, args ...any) (any, error)

First is used to return the first matching object for the given constraints on the index.

Note that all values read in the transaction form a consistent snapshot from the time when the transaction was created.

func (Txn) FirstWatch

func (t Txn) FirstWatch(table TableRef, index string, args ...any) (<-chan struct{}, any, error)

FirstWatch is used to return the first matching object for the given constraints on the index along with the watch channel.

Note that all values read in the transaction form a consistent snapshot from the time when the transaction was created.

The watch channel is closed when a subsequent write transaction has updated the result of the query. Since each read transaction operates on an isolated snapshot, a new read transaction must be started to observe the changes that have been made.

If the value of index ends with "_prefix", FirstWatch will perform a prefix match instead of full match on the index. The registered indexer must implement PrefixIndexer, otherwise an error is returned.

func (Txn) Get

func (t Txn) Get(table TableRef, index string, args ...any) (memdb.ResultIterator, error)

Get is used to construct a ResultIterator over all the rows that match the given constraints of an index. The index values must match exactly (this is not a range-based or prefix-based lookup) by default.

Prefix lookups: if the named index implements PrefixIndexer, you may perform prefix-based lookups by appending "_prefix" to the index name. In this scenario, the index values given in args are treated as prefix lookups. For example, a StringFieldIndex will match any string with the given value as a prefix: "mem" matches "memdb".

See the documentation for ResultIterator to understand the behaviour of the returned ResultIterator.

func (Txn) GetReverse

func (t Txn) GetReverse(table TableRef, index string, args ...any) (memdb.ResultIterator, error)

GetReverse is used to construct a Reverse ResultIterator over all the rows that match the given constraints of an index. The returned ResultIterator's Next() will return the next Previous value.

See the documentation on Get for details on arguments.

See the documentation for ResultIterator to understand the behaviour of the returned ResultIterator.

func (Txn) Insert

func (t Txn) Insert(table TableRef, v any) error

Insert is used to add or update an object into the given table.

When updating an object, the obj provided should be a copy rather than a value updated in-place. Modifying values in-place that are already inserted into MemDB is not supported behavior.

func (Txn) Last

func (t Txn) Last(table TableRef, index string, args ...any) (any, error)

Last is used to return the last matching object for the given constraints on the index.

Note that all values read in the transaction form a consistent snapshot from the time when the transaction was created.

func (Txn) LastWatch

func (t Txn) LastWatch(table TableRef, index string, args ...any) (<-chan struct{}, any, error)

LastWatch is used to return the last matching object for the given constraints on the index along with the watch channel.

Note that all values read in the transaction form a consistent snapshot from the time when the transaction was created.

The watch channel is closed when a subsequent write transaction has updated the result of the query. Since each read transaction operates on an isolated snapshot, a new read transaction must be started to observe the changes that have been made.

If the value of index ends with "_prefix", LastWatch will perform a prefix match instead of full match on the index. The registered indexer must implement PrefixIndexer, otherwise an error is returned.

func (Txn) LongestPrefix

func (t Txn) LongestPrefix(table TableRef, index string, args ...any) (any, error)

LongestPrefix is used to fetch the longest prefix match for the given constraints on the index. Note that this will not work with the memdb StringFieldIndex because it adds null terminators which prevent the algorithm from correctly finding a match (it will get to right before the null and fail to find a leaf node). This should only be used where the prefix given is capable of matching indexed entries directly, which typically only applies to a custom indexer. See the unit test for an example.

Note that all values read in the transaction form a consistent snapshot from the time when the transaction was created.

func (Txn) LowerBound

func (t Txn) LowerBound(table TableRef, index string, args ...any) (memdb.ResultIterator, error)

LowerBound is used to construct a ResultIterator over all the the range of rows that have an index value greater than or equal to the provide args. Calling this then iterating until the rows are larger than required allows range scans within an index. It is not possible to watch the resulting iterator since the radix tree doesn't efficiently allow watching on lower bound changes. The WatchCh returned will be nill and so will block forever.

If the value of index ends with "_prefix", LowerBound will perform a prefix match instead of a full match on the index. The registered index must implement PrefixIndexer, otherwise an error is returned.

See the documentation for ResultIterator to understand the behaviour of the returned ResultIterator.

func (Txn) ReverseLowerBound

func (t Txn) ReverseLowerBound(table TableRef, index string, args ...any) (memdb.ResultIterator, error)

ReverseLowerBound is used to construct a Reverse ResultIterator over all the the range of rows that have an index value less than or equal to the provide args. Calling this then iterating until the rows are lower than required allows range scans within an index. It is not possible to watch the resulting iterator since the radix tree doesn't efficiently allow watching on lower bound changes. The WatchCh returned will be nill and so will block forever.

See the documentation for ResultIterator to understand the behaviour of the returned ResultIterator.

func (Txn) Snapshot

func (t Txn) Snapshot() Txn

Snapshot creates a snapshot of the current state of the transaction. Returns a new read-only transaction or nil if the transaction is already aborted or committed.

func (Txn) TrackChanges

func (t Txn) TrackChanges()

TrackChanges enables change tracking for the transaction. If called at any point before commit, subsequent mutations will be recorded and can be retrieved using ChangeSet. Once this has been called on a transaction it can't be unset. As with other Txn methods it's not safe to call this from a different goroutine than the one making mutations or committing the transaction.