kolo-kv is an ordered key-value store kept in a signed
kolo-log log. Every Put and Delete is one entry
in that log, stored with kolo-store. The current
state is an index rebuilt from that log when it opens and checked against the
log's signed head: a replica trusts only entries that a verified head covers,
as a Certificate Transparency monitor (RFC 9162, section 8.2) does. A peer that holds a replica of the log, kept up to date by
kolo-sync or anything else that calls
Replica.Update, opens it read-only and gets the same state, with no extra
protocol. There are no transactions, no secondary indexes and no compaction.
Install
go get github.com/ciranda-dev/kolo-kvPebble, used by kolo-store, links the C zstd library when cgo is enabled.
Build with CGO_ENABLED=0 for a pure Go binary.
Quick start
Write a few keys in a temp directory, close the store, then open it again and list the keys.
package main
import (
"fmt"
"log"
"os"
"path/filepath"
koloid "github.com/ciranda-dev/kolo-id"
kolokv "github.com/ciranda-dev/kolo-kv"
kolostore "github.com/ciranda-dev/kolo-store"
)
func main() {
dir, err := os.MkdirTemp("", "kolo-kv-quickstart")
check(err)
defer os.RemoveAll(dir)
me, err := koloid.Generate()
check(err)
b, err := kolostore.OpenPebble(filepath.Join(dir, "db"))
check(err)
s := kolostore.New(b)
defer s.Close()
l, err := s.Create(me)
check(err)
db, err := kolokv.Open(l)
check(err)
check(db.Put([]byte("user/ana"), []byte("admin")))
check(db.Put([]byte("user/bo"), []byte("guest")))
check(db.Put([]byte("user/bo"), []byte("editor")))
check(db.Put([]byte("user/cy"), []byte("guest")))
check(db.Delete([]byte("user/cy")))
logID := l.ID()
check(db.Close())
// The state is rebuilt from the log and checked against its signed head.
l, err = s.Open(me, logID)
check(err)
db, err = kolokv.Open(l)
check(err)
defer db.Close()
it := db.Prefix([]byte("user/"))
for it.Next() {
fmt.Printf("%s = %s\n", it.Key(), it.Value())
}
check(it.Close())
fmt.Println("entries:", db.Len())
}
func check(err error) {
if err != nil {
log.Fatal(err)
}
}It prints user/ana = admin, user/bo = editor and entries: 5: four puts
and one delete. To open the store again in a later run, keep me with
kolo-id Save and Load and keep the log ID.
API reference
The API reference is generated from the Go source and is in English.
Package kolokv is a single-writer ordered key-value store on top of a kolo-log log.
Every Put and Delete is one log entry, so the store is signed, verifiable and replicates like any kolo-log log. Open rebuilds the state from the log of a kolo-store Log; OpenReader does the same, read-only, from a kolo-store Replica. Delete destroys the entry keys of every value of the key, so on peers that follow the protocol the old values are gone; a peer that already read them can keep them.
Experimental: the API may change before v1.0.0.
Constants
const (
// MaxKeySize is the largest key in bytes. Empty keys are allowed.
MaxKeySize = 32 << 10
// MaxValueSize is the largest value in bytes.
MaxValueSize = 1 << 20
)Variables
var (
// ErrNotFound is returned for a key that is not in the store.
ErrNotFound = errors.New("kolokv: not found")
// ErrReadOnly is returned by Put and Delete on a store from OpenReader.
ErrReadOnly = errors.New("kolokv: read-only store")
// ErrClosed is returned after Close.
ErrClosed = errors.New("kolokv: closed")
// ErrKeyTooLarge is returned for a key over MaxKeySize.
ErrKeyTooLarge = errors.New("kolokv: key too large")
// ErrValueTooLarge is returned for a value over MaxValueSize.
ErrValueTooLarge = errors.New("kolokv: value too large")
// ErrCorrupt is returned when the log is not a valid kolokv log or does not match its signed head,
// and by reads when a stored entry no longer matches its record.
ErrCorrupt = errors.New("kolokv: corrupt log")
)Types
type DB
type DB struct {
// contains filtered or unexported fields
}DB is a key-value store kept in a kolo-log log. It is safe for concurrent use.
func Open
func Open(l *kolostore.Log) (*DB, error)Open rebuilds the store from l, your own log, and takes it over: write to l only through the DB, which closes it. The log must use the kololog.Bytes value encoding. If Open fails, l stays open.
func OpenReader
func OpenReader(r *kolostore.Replica) (*DB, error)OpenReader rebuilds a read-only store from r, a replica of someone's log, and takes it over: DB.Close closes it. Keep growing r with Update, AddKey and ApplyDelete, then call Refresh.
func (DB) Close
func (db *DB) Close() errorClose closes the store and its log or replica. Closing twice is not an error.
func (DB) Delete
func (db *DB) Delete(key []byte) errorDelete removes key with a delete entry that lists every value of key since its last delete, then destroys their entry keys in one write. A missing key is not an error. If Delete fails after its delete entry was written, the key is gone but its old entries are not destroyed yet; open the log again to destroy them.
func (DB) Get
func (db *DB) Get(key []byte) ([]byte, error)Get returns a copy of the value of key, or ErrNotFound.
func (DB) Len
func (db *DB) Len() uint64Len returns the number of log entries the state is built from. On a reader it is at most the size of the replica's last complete verified head, and less while an entry key or a delete entry is missing.
func (DB) Prefix
func (db *DB) Prefix(prefix []byte) *IteratorPrefix returns an iterator over the keys that start with prefix in byte order, as of now.
func (DB) Put
func (db *DB) Put(key, value []byte) errorPut sets key to value. Both are copied. Put does not destroy the older value of key; Delete does. Once key holds 65536 values since its last delete, the next Put first deletes them; if that delete fails after its delete entry was written, Put returns the error without setting key, and key is already deleted.
func (DB) Range
func (db *DB) Range(start, end []byte) *IteratorRange returns an iterator over the keys in [start, end) in byte order, as of now; a nil end has no upper bound.
func (DB) Refresh
func (db *DB) Refresh() errorRefresh rebuilds a reader's state from the longest prefix of its replica it can replay exactly; on the writer it does nothing. On an error the state stays as it was.
func (DB) Snapshot
func (db *DB) Snapshot() (*Snapshot, error)Snapshot returns a read view of the store at its current log length.
type Iterator
type Iterator struct {
// contains filtered or unexported fields
}Iterator walks keys in byte order, as of when it was made, like database/sql Rows. Call Next before each Key and Value, then Err; Close is idempotent. An Iterator is for one goroutine.
func (Iterator) Close
func (it *Iterator) Close() errorClose stops the iteration and returns Err.
func (Iterator) Err
func (it *Iterator) Err() errorErr returns the error that stopped the iteration, if any; reaching the end is not an error.
func (Iterator) Key
func (it *Iterator) Key() []byteKey returns the current key; the caller may keep it.
func (Iterator) Next
func (it *Iterator) Next() boolNext moves to the next key and reports whether there is one; it is false at the end, on an error and after Close. A value destroyed by Delete after the iterator was made is skipped.
func (Iterator) Value
func (it *Iterator) Value() []byteValue returns the current value; the caller may keep it.
type Snapshot
type Snapshot struct {
// contains filtered or unexported fields
}Snapshot is a read view of a store at one log length. It is safe for concurrent use and holds no resources. A value destroyed by Delete after the snapshot was made reads as ErrNotFound.
func (Snapshot) Get
func (s *Snapshot) Get(key []byte) ([]byte, error)Get returns a copy of the value key had at the snapshot, or ErrNotFound.
func (Snapshot) Len
func (s *Snapshot) Len() uint64Len returns the log length the snapshot was made at.
func (Snapshot) Prefix
func (s *Snapshot) Prefix(prefix []byte) *IteratorPrefix returns an iterator over the snapshot's keys that start with prefix.
func (Snapshot) Range
func (s *Snapshot) Range(start, end []byte) *IteratorRange returns an iterator over the snapshot's keys in [start, end); a nil end has no upper bound.
Good to know
Open takes your own kolo-store Log, and OpenReader a Replica of
someone else's log. The DB takes the handle over: Close closes it, and on
the writer every write must go through the DB. The log must use the
kololog.Bytes value encoding. If Open fails, the handle stays open.
A reader replays the longest prefix of its replica it can replay exactly, up
to the replica's last complete verified head, so its state is always the
writer's state at some length, and Len says which. It stops at the first
entry it holds without its key, and before a destroyed entry whose delete
entry it does not hold yet. It changes state only on Refresh, apart from
destroyed values, which disappear at once, and it can move back to an
earlier length rather than show a state the writer never had.
A DB and a Snapshot are safe for concurrent use, and writes are
serialized. An Iterator is for one goroutine. No call waits on the network,
so none takes a context.Context.
Limits
MaxKeySize: 32 KiB. A longer key returnsErrKeyTooLarge. The empty key is a valid key.MaxValueSize: 1 MiB. A larger value returnsErrValueTooLarge.- Once a key holds 65536 values since its last delete, the next
Putfirst deletes them, asDeletedoes. So a delete entry lists at most 65536 entries. - The index (each live key and the number of its entry) is in memory. Values stay in the log and are read from storage when asked for, so memory grows with the number of keys and entries, not with the size of the values.
Security
Openverifies the head withkololog.VerifyHeadunder the log's owner key. kolo-store has already checked every entry, record, delete marker and the Merkle root against it.- Reads decrypt the entry through kolo-log, so a destroyed value is never
kept elsewhere. A snapshot or iterator made before a
Deleteno longer returns the destroyed value: deletion wins over older views. - The delete entry and the destroy are two writes. If a crash or a failed
write comes between them, the delete entry is already in the log, so the
key stays deleted, and its values stay readable on disk until the next
Opendestroys them. When the automatic delete of aPutfails this way,Putreturns the error without setting the key. - After
Open,Get,Snapshot.GetandIteratorread each value from storage. An entry that no longer matches its verified record (kololog.ErrStorageMismatch) isErrCorrupt, as inOpen. - The writer replays every entry its head covers. An unlisted destroyed
entry, a missing entry key, a list that names a wrong entry or an entry
that does not decode is
ErrCorrupt. - Every op starts with the tag
kolo-kv/op/v0. Another tag or kind, a longer key, value or list, a list that overflows, non-minimal varints or trailing bytes areErrCorrupt.
Known limits
- Experimental. The API may change before v1.0.0.
- One writer.
PutandDeleteon a store fromOpenReaderreturnErrReadOnly. - No transactions, no secondary indexes and no compaction.
- A reader shows new entries only after
Refresh, which is one pass over the log.Lencan go down after aRefresh. - There is no JSON form of the op format.
Errors
| Error | Message |
|---|---|
ErrClosed | kolokv: closed |
ErrCorrupt | kolokv: corrupt log |
ErrKeyTooLarge | kolokv: key too large |
ErrNotFound | kolokv: not found |
ErrReadOnly | kolokv: read-only store |
ErrValueTooLarge | kolokv: value too large |
Test errors with errors.Is. kolo-store and kolo-log errors from the log or
replica pass through wrapped, such as kolostore.ErrClosed or a storage
error, and an ErrCorrupt for a head that does not verify or an entry that
no longer matches its record wraps the kolo-log error too.
References
- RFC 9162, Certificate Transparency Version 2.0 (Experimental, December 2021).
- Takes: section 8.2, the monitor that keeps every entry: the replica only trusts entries a verified head covers.
- Not implemented: nothing left out.