README

github.com/cznic/kv has moved to modernc.org/kv (vcs).

Please update your import paths to modernc.org/kv.

This repo is now archived.

Expand ▾ Collapse ▴

Documentation

Overview

Package kv implements a simple and easy to use persistent key/value (KV) store.

Changelog

2016-07-11: KV now uses the stable version of lldb. (github.com/cznic/lldb).

The stored KV pairs are sorted in the key collation order defined by an user supplied 'compare' function (passed as a field in Options).

Keys and Values Limits

Keys, as well as the values associated with them, are opaque []bytes. Maximum size of a "native" key or value is 65787 bytes. Larger keys or values have to be composed of the "native" ones in client code.

Database limits

The maximum DB size kv can handle is 2^60 bytes (1 exabyte). See also [4]: "Block handles".

ACID and transactional properties

Transactions are resource limited. All changes made by a transaction are held in memory until the top level transaction is committed. ACID[1] implementation notes/details follows.

Atomicity

A successfully committed transaction appears (by its effects on the database) to be indivisible ("atomic") iff the transaction is performed in isolation. An aborted (via RollBack) transaction appears like it never happened under the same limitation.

Atomic updates to the DB, via functions like Set, Inc, etc., are performed in their own automatic transaction. If the partial progress of any such function fails at any point, the automatic transaction is canceled via Rollback before returning from the function. A non nil error is returned in that case.

Consistency

All reads, including those made from any other concurrent non isolated transaction(s), performed during a not yet committed transaction, are dirty reads, i.e. the data returned are consistent with the in-progress state of the open transaction, or all of the open transactions. Obviously, conflicts, data races and inconsistent states can happen, but iff non isolated transactions are performed.

Performing a Rollback at a nested transaction level properly returns the transaction state (and data read from the DB) to what it was before the respective BeginTransaction.

Isolation

Transactions of the atomic updating functions (Set, Put, Delete ...) are always isolated. Transactions controlled by BeginTransaction/Commit/RollBack, are isolated iff their execution is serialized.

Durability

Transactions are committed using the two phase commit protocol(2PC)[2] and a write ahead log(WAL)[3]. DB recovery after a crash is performed automatically using data from the WAL. Last transaction data, either of an in progress transaction or a transaction being committed at the moment of the crash, can get lost.

No protection from non readable files, files corrupted by other processes or by memory faults or other HW problems, is provided. Always properly backup your DB data file(s).

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type DB

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

    DB represents the database (the KV store).

    func Create

    func Create(name string, opts *Options) (db *DB, err error)

      Create creates the named DB file mode 0666 (before umask). The file must not already exist. If successful, methods on the returned DB can be used for I/O; the associated file descriptor has mode os.O_RDWR. If there is an error, it will be of type *os.PathError.

      For the meaning of opts please see documentation of Options.

      func CreateFromFiler

      func CreateFromFiler(filer lldb.Filer, opts *Options) (db *DB, err error)

        CreateFromFiler is like Create but accepts an arbitrary backing storage provided by filer.

        For the meaning of opts please see documentation of Options.

        func CreateMem

        func CreateMem(opts *Options) (db *DB, err error)

          CreateMem creates a new instance of an in-memory DB not backed by a disk file. Memory DBs are resource limited as they are completely held in memory and are not automatically persisted.

          For the meaning of opts please see documentation of Options.

          func CreateTemp

          func CreateTemp(dir, prefix, suffix string, opts *Options) (db *DB, err error)

            CreateTemp creates a new temporary DB in the directory dir with a basename beginning with prefix and name ending in suffix. If dir is the empty string, CreateTemp uses the default directory for temporary files (see os.TempDir). Multiple programs calling CreateTemp simultaneously will not choose the same file name for the DB. The caller can use Name() to find the pathname of the DB file. It is the caller's responsibility to remove the file when no longer needed.

            For the meaning of opts please see documentation of Options.

            func Open

            func Open(name string, opts *Options) (db *DB, err error)

              Open opens the named DB file for reading/writing. If successful, methods on the returned DB can be used for I/O; the associated file descriptor has mode os.O_RDWR. If there is an error, it will be of type *os.PathError.

              Note: While a DB is opened, it is locked and cannot be simultaneously opened again.

              For the meaning of opts please see documentation of Options.

              func OpenFromFiler

              func OpenFromFiler(filer lldb.Filer, opts *Options) (db *DB, err error)

                OpenFromFiler is like Open but it accepts an arbitrary backing storage provided by filer.

                func (*DB) BeginTransaction

                func (db *DB) BeginTransaction() (err error)

                  BeginTransaction starts a new transaction. Every call to BeginTransaction must be eventually "balanced" by exactly one call to Commit or Rollback (but not both). Calls to BeginTransaction may nest.

                  BeginTransaction is atomic and it is safe for concurrent use by multiple goroutines (if/when that makes sense).

                  func (*DB) Close

                  func (db *DB) Close() (err error)

                    Close closes the DB, rendering it unusable for I/O. It returns an error, if any. Failing to call Close before exiting a program can lose the last open or being committed transaction.

                    Successful Close is idempotent.

                    func (*DB) Commit

                    func (db *DB) Commit() (err error)

                      Commit commits the current transaction. If the transaction is the top level one, then all of the changes made within the transaction are atomically made persistent in the DB. Invocation of an unbalanced Commit is an error.

                      Commit is atomic and it is safe for concurrent use by multiple goroutines (if/when that makes sense).

                      func (*DB) Delete

                      func (db *DB) Delete(key []byte) (err error)

                        Delete deletes key and its associated value from the DB.

                        Delete is atomic and it is safe for concurrent use by multiple goroutines.

                        func (*DB) Extract

                        func (db *DB) Extract(buf, key []byte) (value []byte, err error)

                          Extract is a combination of Get and Delete. If the key exists in the DB, it is returned (like Get) and also deleted from the DB in a more efficient way which doesn't search for the key twice. The returned slice may be a sub-slice of buf if buf was large enough to hold the entire content. Otherwise, a newly allocated slice will be returned. It is valid to pass a nil buf.

                          Extract is atomic and it is safe for concurrent use by multiple goroutines.

                          func (*DB) First

                          func (db *DB) First() (key, value []byte, err error)

                            First returns the first KV pair in the DB, if it exists. Otherwise key == nil and value == nil.

                            First is atomic and it is safe for concurrent use by multiple goroutines.

                            func (*DB) Get

                            func (db *DB) Get(buf, key []byte) (value []byte, err error)

                              Get returns the value associated with key, or nil if no such value exists. The returned slice may be a sub-slice of buf if buf was large enough to hold the entire content. Otherwise, a newly allocated slice will be returned. It is valid to pass a nil buf.

                              Get is atomic and it is safe for concurrent use by multiple goroutines.

                              func (*DB) Inc

                              func (db *DB) Inc(key []byte, delta int64) (val int64, err error)

                                Inc atomically increments the value associated with key by delta and returns the new value. If the value doesn't exists before calling Inc or if the value is not an [8]byte, the value is considered to be zero before peforming Inc.

                                Inc is atomic and it is safe for concurrent use by multiple goroutines.

                                func (*DB) Last

                                func (db *DB) Last() (key, value []byte, err error)

                                  Last returns the last KV pair of the DB, if it exists. Otherwise key == nil and value == nil.

                                  Last is atomic and it is safe for concurrent use by multiple goroutines.

                                  func (*DB) Name

                                  func (db *DB) Name() string

                                    Name returns the name of the DB file.

                                    func (*DB) Put

                                    func (db *DB) Put(buf, key []byte, upd func(key, old []byte) (new []byte, write bool, err error)) (old []byte, written bool, err error)

                                      Put combines Get and Set in a more efficient way where the DB is searched for the key only once. The upd(ater) receives the current (key, old-value), if that exists or (key, nil) otherwise. It can then return a (new-value, true, nil) to create or overwrite the existing value in the KV pair, or (whatever, false, nil) if it decides not to create or not to update the value of the KV pair.

                                      db.Set(k, v)
                                      

                                      conceptually equals

                                      db.Put(k, func(k, v []byte){ return v, true }([]byte, bool))
                                      

                                      modulo the differing return values.

                                      The returned slice may be a sub-slice of buf if buf was large enough to hold the entire content. Otherwise, a newly allocated slice will be returned. It is valid to pass a nil buf.

                                      Put is atomic and it is safe for concurrent use by multiple goroutines.

                                      func (*DB) Rollback

                                      func (db *DB) Rollback() (err error)

                                        Rollback cancels and undoes the innermost transaction level. If the transaction is the top level one, then no of the changes made within the transactions are persisted. Invocation of an unbalanced Rollback is an error.

                                        Rollback is atomic and it is safe for concurrent use by multiple goroutines (if/when that makes sense).

                                        func (*DB) Seek

                                        func (db *DB) Seek(key []byte) (enum *Enumerator, hit bool, err error)

                                          Seek returns an enumerator positioned on the first key/value pair whose key is 'greater than or equal to' the given key. There may be no such pair, in which case the Next,Prev methods of the returned enumerator will always return io.EOF.

                                          Seek is atomic and it is safe for concurrent use by multiple goroutines.

                                          func (*DB) SeekFirst

                                          func (db *DB) SeekFirst() (enum *Enumerator, err error)

                                            SeekFirst returns an enumerator positioned on the first KV pair in the DB, if any. For an empty DB, err == io.EOF is returned.

                                            SeekFirst is atomic and it is safe for concurrent use by multiple goroutines.

                                            func (*DB) SeekLast

                                            func (db *DB) SeekLast() (enum *Enumerator, err error)

                                              SeekLast returns an enumerator positioned on the last KV pair in the DB, if any. For an empty DB, err == io.EOF is returned.

                                              SeekLast is atomic and it is safe for concurrent use by multiple goroutines.

                                              func (*DB) Set

                                              func (db *DB) Set(key, value []byte) (err error)

                                                Set sets the value associated with key. Any previous value, if existed, is overwritten by the new one.

                                                Set is atomic and it is safe for concurrent use by multiple goroutines.

                                                func (*DB) Size

                                                func (db *DB) Size() (sz int64, err error)

                                                  Size returns the size of the DB file.

                                                  func (*DB) Verify

                                                  func (db *DB) Verify(log func(error) bool, stats *lldb.AllocStats) (err error)

                                                    Verify attempts to find any structural errors in DB wrt the organization of it as defined by lldb.Allocator. Any problems found are reported to 'log' except non verify related errors like disk read fails etc. If 'log' returns false or the error doesn't allow to (reliably) continue, the verification process is stopped and an error is returned from the Verify function. Passing a nil log works like providing a log function always returning false. Any non-structural errors, like for instance Filer read errors, are NOT reported to 'log', but returned as the Verify's return value, because Verify cannot proceed in such cases. Verify returns nil only if it fully completed verifying DB without detecting any error.

                                                    It is recommended to limit the number reported problems by returning false from 'log' after reaching some limit. Huge and corrupted DB can produce an overwhelming error report dataset.

                                                    The verifying process will scan the whole DB at least 3 times (a trade between processing space and time consumed). It doesn't read the content of free blocks above the head/tail info bytes. If the 3rd phase detects lost free space, then a 4th scan (a faster one) is performed to precisely report all of them.

                                                    Statistics are returned via 'stats' if non nil. The statistics are valid only if Verify succeeded, ie. it didn't reported anything to log and it returned a nil error.

                                                    func (*DB) WALName

                                                    func (db *DB) WALName() string

                                                      WALName returns the name of the WAL file in use or an empty string for memory or closed databases.

                                                      type Enumerator

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

                                                        Enumerator captures the state of enumerating a DB. It is returned from the Seek* methods. Multiple enumerations may be in progress simultaneously. The enumerator is aware of any mutations made to the tree in the process of enumerating it and automatically resumes the enumeration.

                                                        Multiple concurrently executing enumerations may be in progress.

                                                        func (*Enumerator) Next

                                                        func (e *Enumerator) Next() (key, value []byte, err error)

                                                          Next returns the currently enumerated KV pair, if it exists and moves to the next KV in the key collation order. If there is no KV pair to return, err == io.EOF is returned.

                                                          Next is atomic and it is safe for concurrent use by multiple goroutines.

                                                          func (*Enumerator) Prev

                                                          func (e *Enumerator) Prev() (key, value []byte, err error)

                                                            Prev returns the currently enumerated KV pair, if it exists and moves to the previous KV in the key collation order. If there is no KV pair to return, err == io.EOF is returned.

                                                            Prev is atomic and it is safe for concurrent use by multiple goroutines.

                                                            type Options

                                                            type Options struct {
                                                            	// Compare compares x and y. Compare may be nil, then bytes.Compare is
                                                            	// used instead.
                                                            	//
                                                            	// Compare returns:
                                                            	//
                                                            	//	-1 if x <  y
                                                            	//	 0 if x == y
                                                            	//	+1 if x >  y
                                                            	Compare func(x, y []byte) int
                                                            
                                                            	// Locker specifies a function to lock a named file.
                                                            	// On success it returns an io.Closer to release the lock.
                                                            	// If nil, a default implementation is used.
                                                            	Locker func(name string) (io.Closer, error)
                                                            
                                                            	// The write ahead log pathname. Applicable iff ACID == ACIDFull. May
                                                            	// be left empty in which case an unspecified pathname will be chosen,
                                                            	// which is computed from the DB name and which will be in the same
                                                            	// directory as the DB. Moving or renaming the DB while it is shut down
                                                            	// will break it's connection to the automatically computed name.
                                                            	// Moving both the files (the DB and the WAL) into another directory
                                                            	// with no renaming is safe.
                                                            	//
                                                            	// On creating a new DB the WAL file must not exist or it must be
                                                            	// empty. It's not safe to write to a non empty WAL file as it may
                                                            	// contain unprocessed DB recovery data.
                                                            	WAL string
                                                            
                                                            	// VerifyDbBeforeOpen turns on structural verification of the DB before
                                                            	// it is opened. This verification may legitimately fail if the DB
                                                            	// crashed and a yet-to-be-processed non empty WAL file exists.
                                                            	VerifyDbBeforeOpen bool
                                                            
                                                            	// VerifyDbAfterOpen turns on structural verification of the DB after
                                                            	// it is opened and possibly recovered from WAL.
                                                            	VerifyDbAfterOpen bool
                                                            
                                                            	// VerifyDbBeforeClose turns on structural verification of the DB
                                                            	// before it is closed.
                                                            	VerifyDbBeforeClose bool
                                                            
                                                            	// VerifyDbAfterClose turns on structural verification of the DB after
                                                            	// it is closed.
                                                            	VerifyDbAfterClose bool
                                                            	// contains filtered or unexported fields
                                                            }

                                                              Options are passed to the DB create/open functions to amend the behavior of those functions. The compatibility promise is the same as of struct types in the Go standard library - introducing changes can be made only by adding new exported fields, which is backward compatible as long as client code uses field names to assign values of imported struct types literals.

                                                              Directories

                                                              Path Synopsis
                                                              Command kvaudit verifies kv databases.
                                                              Command kvaudit verifies kv databases.