README
¶
kv
Package kv implements a simple and easy to use persistent key/value (KV) store.
Installation
$ go get github.com/cznic/kv
Documentation: godoc.org/github.com/cznic/kv
Documentation
¶
Overview ¶
Package kv implements a simple and easy to use persistent key/value (KV) store.
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 ¶
- type DB
- func (db *DB) BeginTransaction() (err error)
- func (db *DB) Close() (err error)
- func (db *DB) Commit() (err error)
- func (db *DB) Delete(key []byte) (err error)
- func (db *DB) Extract(buf, key []byte) (value []byte, err error)
- func (db *DB) First() (key, value []byte, err error)
- func (db *DB) Get(buf, key []byte) (value []byte, err error)
- func (db *DB) Inc(key []byte, delta int64) (val int64, err error)
- func (db *DB) Last() (key, value []byte, err error)
- func (db *DB) Name() string
- func (db *DB) Put(buf, key []byte, upd func(key, old []byte) (new []byte, write bool, err error)) (old []byte, written bool, err error)
- func (db *DB) Rollback() (err error)
- func (db *DB) Seek(key []byte) (enum *Enumerator, hit bool, err error)
- func (db *DB) SeekFirst() (enum *Enumerator, err error)
- func (db *DB) SeekLast() (enum *Enumerator, err error)
- func (db *DB) Set(key, value []byte) (err error)
- func (db *DB) Size() (sz int64, err error)
- func (db *DB) Verify(log func(error) bool, stats *lldb.AllocStats) (err error)
- func (db *DB) WALName() string
- type Enumerator
- type Options
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 ¶
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 CreateMem ¶
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 ¶
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 ¶
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 (*DB) BeginTransaction ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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) 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 ¶
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 ¶
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) Verify ¶
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.
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)
// 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.
Source Files