kolo docsbeta

kolo-kv

Un almacén clave-valor ordenado con un solo escritor, guardado en un log firmado de Kolo.

En esta página

kolo-kv es un almacén clave-valor ordenado que se guarda en un log firmado de kolo-log. Cada Put y cada Delete es una entrada de ese log, guardado con kolo-store. El estado actual es un índice que se reconstruye a partir de ese log al abrirlo y se comprueba frente al head firmado del log: una réplica solo confía en las entradas que cubre un head verificado, como lo hace un monitor de Certificate Transparency (RFC 9162, sección 8.2). Un peer que tiene una réplica del log, mantenida al día por kolo-sync o por cualquier otra cosa que llame a Replica.Update, la abre en solo lectura y obtiene el mismo estado, sin ningún protocolo adicional. No hay transacciones, ni índices secundarios, ni compactación.

Instalación

go get github.com/ciranda-dev/kolo-kv

Pebble, que usa kolo-store, enlaza la biblioteca C de zstd cuando cgo está activado. Compila con CGO_ENABLED=0 para obtener un binario solo en Go.

Inicio rápido

Escribe unas cuantas claves en un directorio temporal, cierra el almacén y después vuelve a abrirlo y lista las claves.

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)
	}
}

Imprime user/ana = admin, user/bo = editor y entries: 5: cuatro puts y un delete. Para volver a abrir el almacén en una ejecución posterior, conserva me con Save y Load de kolo-id y guarda el ID del log.

Referencia de la API

La referencia de la API se genera a partir del código Go y está en inglés.

Paquete 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.

Constantes

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")
)

Tipos

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.

Conviene saber

Open recibe tu propio Log de kolo-store, y OpenReader una Replica del log de otra persona. El DB se queda con el handle: Close lo cierra, y en el escritor todas las escrituras tienen que pasar por el DB. El log tiene que usar la codificación de valores kololog.Bytes. Si Open falla, el handle sigue abierto.

Un lector reproduce el prefijo más largo de su réplica que puede reproducir con exactitud, hasta el último head verificado y completo de la réplica, así que su estado siempre es el del escritor en alguna longitud, y Len dice en cuál. Se detiene en la primera entrada que tiene sin su clave, y antes de una entrada destruida cuya entrada de borrado aún no tiene. Solo cambia de estado con Refresh, salvo los valores destruidos, que desaparecen enseguida, y puede volver a una longitud anterior antes que mostrar un estado que el escritor nunca tuvo.

Un DB y un Snapshot son seguros para uso concurrente, y las escrituras se serializan. Un Iterator es para una sola goroutine. Ninguna llamada espera a la red, así que ninguna recibe un context.Context.

Límites

  • MaxKeySize: 32 KiB. Una clave más larga devuelve ErrKeyTooLarge. La clave vacía es una clave válida.
  • MaxValueSize: 1 MiB. Un valor más grande devuelve ErrValueTooLarge.
  • Cuando una clave tiene 65.536 valores desde su último borrado, el siguiente Put los borra primero, como hace Delete. Así, una entrada de borrado lista como mucho 65.536 entradas.
  • El índice (cada clave viva y el número de su entrada) está en memoria. Los valores se quedan en el log y se leen del almacenamiento cuando se piden, así que la memoria crece con el número de claves y de entradas, no con el tamaño de los valores.

Seguridad

  • Open verifica el head con kololog.VerifyHead frente a la clave del propietario del log. kolo-store ya ha comprobado frente a ella cada entrada, cada registro, cada marca de borrado y la raíz de Merkle.
  • Las lecturas descifran la entrada a través de kolo-log, así que un valor destruido nunca se guarda en otro sitio. Una instantánea o un iterador creados antes de un Delete ya no devuelven el valor destruido: el borrado gana a las vistas más antiguas.
  • La entrada de borrado y la destrucción son dos escrituras. Si una caída o una escritura fallida ocurren entre ellas, la entrada de borrado ya está en el log, así que la clave sigue borrada, y sus valores se pueden seguir leyendo en el disco hasta que el siguiente Open los destruye. Cuando el borrado automático de un Put falla así, Put devuelve el error sin asignar la clave.
  • Después de Open, Get, Snapshot.Get e Iterator leen cada valor del almacenamiento. Una entrada que ya no coincide con su registro verificado (kololog.ErrStorageMismatch) es ErrCorrupt, igual que en Open.
  • El escritor reproduce todas las entradas que cubre su head. Una entrada destruida que no aparece en ninguna lista, una clave de entrada que falta, una lista que nombra una entrada equivocada o una entrada que no se decodifica son ErrCorrupt.
  • Cada op empieza con la etiqueta kolo-kv/op/v0. Otra etiqueta u otro tipo, una clave, un valor o una lista más largos, una lista que se desborda, varints no mínimos o bytes sobrantes son ErrCorrupt.

Límites conocidos

  • Experimental. La API puede cambiar antes de v1.0.0.
  • Un solo escritor. Put y Delete sobre un almacén abierto con OpenReader devuelven ErrReadOnly.
  • No hay transacciones, ni índices secundarios, ni compactación.
  • Un lector solo muestra las entradas nuevas después de Refresh, que es una pasada por el log. Len puede bajar después de un Refresh.
  • El formato de las ops no tiene forma JSON.

Errores

ErrorMensaje
ErrClosedkolokv: closed
ErrCorruptkolokv: corrupt log
ErrKeyTooLargekolokv: key too large
ErrNotFoundkolokv: not found
ErrReadOnlykolokv: read-only store
ErrValueTooLargekolokv: value too large

Comprueba los errores con errors.Is. Los errores de kolo-store y de kolo-log que vienen del log o de la réplica se transmiten envueltos, como kolostore.ErrClosed o un error del almacenamiento, y un ErrCorrupt por un head que no se verifica o por una entrada que ya no coincide con su registro también envuelve el error de kolo-log.

Referencias

  • RFC 9162, Certificate Transparency Version 2.0 (Experimental, December 2021).
    • Toma: la sección 8.2, el monitor que conserva todas las entradas: la réplica solo confía en las entradas que cubre un head verificado.
    • No implementa: no se deja nada fuera.