db

README

Key-Value Database

Databases supporting mappings of arbitrary byte sequences.

Interfaces

The database interface types consist of objects to encapsulate the singular connection to the DB, transactions being made to it, historical version state, and iteration.

DBConnection

This interface represents a connection to a versioned key-value database. All versioning operations are performed using methods on this type.

• The Versions method returns a VersionSet which represents an immutable view of the version history at the current state.
• Version history is modified via the {Save,Delete}Version methods.
• Operations on version history do not modify any database contents.

DBReader, DBWriter, and DBReadWriter

These types represent transactions on the database contents. Their methods provide CRUD operations as well as iteration.

• Writeable transactions call Commit flushes operations to the source DB.
• All open transactions must be closed with Discard or Commit before a new version can be saved on the source DB.
• The maximum number of safely concurrent transactions is dependent on the backend implementation.
• A single transaction object is not safe for concurrent use.
• Write conflicts on concurrent transactions will cause an error at commit time (optimistic concurrency control).

Iterator

• An iterator is invalidated by any writes within its Domain to the source transaction while it is open.
• An iterator must call Close before its source transaction is closed.

VersionSet

This represents a self-contained and immutable view of a database's version history state. It is therefore safe to retain and conccurently access any instance of this object.

Implementations

In-memory DB

The in-memory DB in the db/memdb package cannot be persisted to disk. It is implemented using the Google btree library.

• This currently does not perform write conflict detection, so it only supports a single open write-transaction at a time. Multiple and concurrent read-transactions are supported.

BadgerDB

A BadgerDB-based backend. Internally, this uses BadgerDB's "managed" mode for version management. Note that Badger only recognizes write conflicts for rows that are read after a conflicting transaction was opened. In other words, the following will raise an error:

tx1, tx2 := db.Writer(), db.ReadWriter()
key := []byte("key")
tx2.Get(key)
tx1.Set(key, []byte("a"))
tx2.Set(key, []byte("b"))
tx1.Commit()        // ok
err := tx2.Commit() // err is non-nil

But this will not:

tx1, tx2 := db.Writer(), db.ReadWriter()
key := []byte("key")
tx1.Set(key, []byte("a"))
tx2.Set(key, []byte("b"))
tx1.Commit() // ok
tx2.Commit() // ok

RocksDB

A RocksDB-based backend. Internally this uses OptimisticTransactionDB to allow concurrent transactions with write conflict detection. Historical versioning is internally implemented with Checkpoints.

Documentation

Index

• Variables
• type DBConnection
• type DBReadWriter
  • func ReaderAsReadWriter(r DBReader) DBReadWriter
• type DBReader
• type DBWriter
• type Iterator
• type VersionIterator
• type VersionManager
  • func NewVersionManager(versions []uint64) *VersionManager
  • func (vm *VersionManager) Copy() *VersionManager
  • func (vm *VersionManager) Count() int
  • func (vm *VersionManager) Delete(target uint64)
  • func (vm *VersionManager) Equal(that VersionSet) bool
  • func (vm *VersionManager) Exists(version uint64) bool
  • func (vm *VersionManager) Initial() uint64
  • func (vm *VersionManager) Iterator() VersionIterator
  • func (vm *VersionManager) Last() uint64
  • func (vm *VersionManager) Save(target uint64) (uint64, error)
• type VersionSet

Variables

var (
	// ErrTransactionClosed is returned when a closed or written transaction is used.
	ErrTransactionClosed = errors.New("transaction has been written or closed")

	// ErrKeyEmpty is returned when attempting to use an empty or nil key.
	ErrKeyEmpty = errors.New("key cannot be empty")

	// ErrValueNil is returned when attempting to set a nil value.
	ErrValueNil = errors.New("value cannot be nil")

	// ErrVersionDoesNotExist is returned when a DB version does not exist.
	ErrVersionDoesNotExist = errors.New("version does not exist")

	// ErrOpenTransactions is returned when open transactions exist which must
	// be discarded/committed before an operation can complete.
	ErrOpenTransactions = errors.New("open transactions exist")

	// ErrReadOnly is returned when a write operation is attempted on a read-only transaction.
	ErrReadOnly = errors.New("cannot modify read-only transaction")

	// ErrInvalidVersion is returned when an operation attempts to use an invalid version ID.
	ErrInvalidVersion = errors.New("invalid version")
)

Types

type DBConnection

type DBConnection interface {
	// Reader opens a read-only transaction at the current working version.
	Reader() DBReader

	// ReaderAt opens a read-only transaction at a specified version.
	// Returns ErrVersionDoesNotExist for invalid versions.
	ReaderAt(uint64) (DBReader, error)

	// ReadWriter opens a read-write transaction at the current version.
	ReadWriter() DBReadWriter

	// Writer opens a write-only transaction at the current version.
	Writer() DBWriter

	// Versions returns all saved versions as an immutable set which is safe for concurrent access.
	Versions() (VersionSet, error)

	// SaveNextVersion saves the current contents of the database and returns the next version ID,
	// which will be `Versions().Last()+1`.
	// Returns an error if any open DBWriter transactions exist.
	// TODO: rename to something more descriptive?
	SaveNextVersion() (uint64, error)

	// SaveVersion attempts to save database at a specific version ID, which must be greater than or
	// equal to what would be returned by `SaveNextVersion`.
	// Returns an error if any open DBWriter transactions exist.
	SaveVersion(uint64) error

	// DeleteVersion deletes a saved version. Returns ErrVersionDoesNotExist for invalid versions.
	DeleteVersion(uint64) error

	// Revert reverts the DB state to the last saved version; if none exist, this clears the DB.
	// Returns an error if any open DBWriter transactions exist.
	Revert() error

	// Close closes the database connection.
	Close() error
}

DBConnection represents a connection to a versioned database. Records are accessed via transaction objects, and must be safe for concurrent creation and read and write access. Past versions are only accessible read-only.

type DBReadWriter

type DBReadWriter interface {
	DBReader
	DBWriter
}

DBReadWriter is a transaction interface that allows both reading and writing.

func ReaderAsReadWriter

func ReaderAsReadWriter(r DBReader) DBReadWriter

ReaderAsReadWriter returns a ReadWriter that forwards to a reader and errors if writes are attempted. Can be used to pass a Reader when a ReadWriter is expected but no writes will actually occur.

type DBReader

type DBReader interface {
	// Get fetches the value of the given key, or nil if it does not exist.
	// CONTRACT: key, value readonly []byte
	Get([]byte) ([]byte, error)

	// Has checks if a key exists.
	// CONTRACT: key, value readonly []byte
	Has(key []byte) (bool, error)

	// Iterator returns an iterator over a domain of keys, in ascending order. The caller must call
	// Close when done. End is exclusive, and start must be less than end. A nil start iterates
	// from the first key, and a nil end iterates to the last key (inclusive). Empty keys are not
	// valid.
	// CONTRACT: No writes may happen within a domain while an iterator exists over it.
	// CONTRACT: start, end readonly []byte
	Iterator(start, end []byte) (Iterator, error)

	// ReverseIterator returns an iterator over a domain of keys, in descending order. The caller
	// must call Close when done. End is exclusive, and start must be less than end. A nil end
	// iterates from the last key (inclusive), and a nil start iterates to the first key (inclusive).
	// Empty keys are not valid.
	// CONTRACT: No writes may happen within a domain while an iterator exists over it.
	// CONTRACT: start, end readonly []byte
	// TODO: replace with an extra argument to Iterator()?
	ReverseIterator(start, end []byte) (Iterator, error)

	// Discard discards the transaction, invalidating any future operations on it.
	Discard() error
}

DBReader is a read-only transaction interface. It is safe for concurrent access. Callers must call Discard when done with the transaction.

Keys cannot be nil or empty, while values cannot be nil. Keys and values should be considered read-only, both when returned and when given, and must be copied before they are modified.

type DBWriter

type DBWriter interface {
	// Set sets the value for the given key, replacing it if it already exists.
	// CONTRACT: key, value readonly []byte
	Set([]byte, []byte) error

	// Delete deletes the key, or does nothing if the key does not exist.
	// CONTRACT: key readonly []byte
	Delete([]byte) error

	// Commit flushes pending writes and discards the transaction.
	Commit() error

	// Discard discards the transaction, invalidating any future operations on it.
	Discard() error
}

DBWriter is a write-only transaction interface. It is safe for concurrent writes, following an optimistic (OCC) strategy, detecting any write conflicts and returning an error on commit, rather than locking the DB. Callers must call Commit or Discard when done with the transaction.

This can be used to wrap a write-optimized batch object if provided by the backend implementation.

type Iterator

type Iterator interface {
	// Domain returns the start (inclusive) and end (exclusive) limits of the iterator.
	// CONTRACT: start, end readonly []byte
	Domain() (start []byte, end []byte)

	// Next moves the iterator to the next key in the database, as defined by order of iteration;
	// returns whether the iterator is valid.
	// Once this function returns false, the iterator remains invalid forever.
	Next() bool

	// Key returns the key at the current position. Panics if the iterator is invalid.
	// CONTRACT: key readonly []byte
	Key() (key []byte)

	// Value returns the value at the current position. Panics if the iterator is invalid.
	// CONTRACT: value readonly []byte
	Value() (value []byte)

	// Error returns the last error encountered by the iterator, if any.
	Error() error

	// Close closes the iterator, relasing any allocated resources.
	Close() error
}

Iterator represents an iterator over a domain of keys. Callers must call Close when done. No writes can happen to a domain while there exists an iterator over it, some backends may take out database locks to ensure this will not happen.

Callers must make sure the iterator is valid before calling any methods on it, otherwise these methods will panic. This is in part caused by most backend databases using this convention. Note that the iterator is invalid on contruction: Next() must be called to initialize it to its starting position.

As with DBReader, keys and values should be considered read-only, and must be copied before they are modified.

Typical usage:

var itr Iterator = ...
defer itr.Close()

for itr.Next() {
  k, v := itr.Key(); itr.Value()
  ...
}
if err := itr.Error(); err != nil {
  ...
}

type VersionIterator

type VersionIterator interface {
	// Next advances the iterator to the next element.
	// Returns whether the iterator is valid; once invalid, it remains invalid forever.
	Next() bool
	// Value returns the version ID at the current position.
	Value() uint64
}

type VersionManager

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

VersionManager encapsulates the current valid versions of a DB and computes the next version.

func NewVersionManager

func NewVersionManager(versions []uint64) *VersionManager

NewVersionManager creates a VersionManager from a slice of version ids.

func (*VersionManager) Copy

func (vm *VersionManager) Copy() *VersionManager

func (*VersionManager) Count

func (vm *VersionManager) Count() int

Count implements VersionSet.

func (*VersionManager) Delete

func (vm *VersionManager) Delete(target uint64)

func (*VersionManager) Equal

func (vm *VersionManager) Equal(that VersionSet) bool

Equal implements VersionSet.

func (*VersionManager) Exists

func (vm *VersionManager) Exists(version uint64) bool

Exists implements VersionSet.

func (*VersionManager) Initial

func (vm *VersionManager) Initial() uint64

func (*VersionManager) Iterator

func (vm *VersionManager) Iterator() VersionIterator

Iterator implements VersionSet.

func (*VersionManager) Last

func (vm *VersionManager) Last() uint64

Last implements VersionSet.

func (*VersionManager) Save

func (vm *VersionManager) Save(target uint64) (uint64, error)

type VersionSet

type VersionSet interface {
	// Last returns the most recent saved version, or 0 if none.
	Last() uint64
	// Count returns the number of saved versions.
	Count() int
	// Iterator returns an iterator over all saved versions.
	Iterator() VersionIterator
	// Equal returns true iff this set is identical to another.
	Equal(VersionSet) bool
	// Exists returns true if a saved version exists.
	Exists(uint64) bool
}

VersionSet specifies a set of existing versions