kolo docsbeta

kolo-kv

An ordered key-value store with one writer, kept in a signed Kolo log.

On this page

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-kv

Pebble, 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.

main.go
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 · github.com/ciranda-dev/kolo-kv · v0.1.0

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() error

Close closes the store and its log or replica. Closing twice is not an error.

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

Delete 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() uint64

Len 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) *Iterator

Prefix 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) error

Put 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) *Iterator

Range 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() error

Refresh 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() error

Close stops the iteration and returns Err.

func (Iterator) Err
func (it *Iterator) Err() error

Err returns the error that stopped the iteration, if any; reaching the end is not an error.

func (Iterator) Key
func (it *Iterator) Key() []byte

Key returns the current key; the caller may keep it.

func (Iterator) Next
func (it *Iterator) Next() bool

Next 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() []byte

Value 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() uint64

Len returns the log length the snapshot was made at.

func (Snapshot) Prefix
func (s *Snapshot) Prefix(prefix []byte) *Iterator

Prefix returns an iterator over the snapshot's keys that start with prefix.

func (Snapshot) Range
func (s *Snapshot) Range(start, end []byte) *Iterator

Range 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 returns ErrKeyTooLarge. The empty key is a valid key.
  • MaxValueSize: 1 MiB. A larger value returns ErrValueTooLarge.
  • Once a key holds 65536 values since its last delete, the next Put first deletes them, as Delete does. 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

  • Open verifies the head with kololog.VerifyHead under 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 Delete no 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 Open destroys them. When the automatic delete of a Put fails this way, Put returns the error without setting the key.
  • After Open, Get, Snapshot.Get and Iterator read each value from storage. An entry that no longer matches its verified record (kololog.ErrStorageMismatch) is ErrCorrupt, as in Open.
  • 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 are ErrCorrupt.

Known limits

  • Experimental. The API may change before v1.0.0.
  • One writer. Put and Delete on a store from OpenReader return ErrReadOnly.
  • No transactions, no secondary indexes and no compaction.
  • A reader shows new entries only after Refresh, which is one pass over the log. Len can go down after a Refresh.
  • There is no JSON form of the op format.

Errors

ErrorMessage
ErrClosedkolokv: closed
ErrCorruptkolokv: corrupt log
ErrKeyTooLargekolokv: key too large
ErrNotFoundkolokv: not found
ErrReadOnlykolokv: read-only store
ErrValueTooLargekolokv: 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