kolo docsbeta

kolo-kv

Um armazenamento chave-valor ordenado com um único escritor, guardado em um log assinado do Kolo.

Nesta página

A kolo-kv é um armazenamento chave-valor ordenado, mantido em um log assinado da kolo-log. Cada Put e cada Delete é uma entrada desse log, guardado com a kolo-store. O estado atual é um índice reconstruído a partir desse log quando ele abre, e verificado contra o head assinado do log: uma réplica só confia nas entradas que um head verificado cobre, como faz um monitor de Certificate Transparency (RFC 9162, seção 8.2). Um peer que tem uma réplica do log, mantida atualizada pela kolo-sync ou por qualquer outra coisa que chame Replica.Update, abre essa réplica em modo somente leitura e obtém o mesmo estado, sem nenhum protocolo extra. Não há transações, índices secundários nem compactação.

Instalação

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

O Pebble, usado pela kolo-store, faz link com a biblioteca C zstd quando o cgo está ativado. Compile com CGO_ENABLED=0 para ter um binário em Go puro.

Início rápido

Grave algumas chaves em um diretório temporário, feche o store, abra de novo e liste as chaves.

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

O programa imprime user/ana = admin, user/bo = editor e entries: 5: quatro puts e um delete. Para abrir o store de novo em uma execução posterior, guarde me com Save e Load da kolo-id e guarde o ID do log.

Referência da API

A referência da API é gerada a partir do código Go e está em inglês.

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

Variáveis

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.

Bom saber

Open recebe o seu próprio Log da kolo-store, e OpenReader uma Replica do log de outra pessoa. O DB assume o handle: Close o fecha, e no escritor toda gravação precisa passar pelo DB. O log precisa usar a codificação de valor kololog.Bytes. Se Open falhar, o handle continua aberto.

Um leitor reproduz o maior prefixo da sua réplica que ele consegue reproduzir exatamente, até o último head verificado completo da réplica. Assim o seu estado é sempre o estado do escritor em algum tamanho, e Len diz qual. Ele para na primeira entrada que tem sem a sua chave, e antes de uma entrada destruída cuja entrada de exclusão ele ainda não tem. Ele só muda de estado em Refresh, a não ser pelos valores destruídos, que somem na hora, e pode voltar para um tamanho anterior em vez de mostrar um estado que o escritor nunca teve.

Um DB e um Snapshot são seguros para uso concorrente, e as gravações são serializadas. Um Iterator é para uma única goroutine. Nenhuma chamada espera pela rede, então nenhuma recebe um context.Context.

Limites

  • MaxKeySize: 32 KiB. Uma chave mais longa retorna ErrKeyTooLarge. A chave vazia é uma chave válida.
  • MaxValueSize: 1 MiB. Um valor maior retorna ErrValueTooLarge.
  • Quando uma chave guarda 65.536 valores desde a sua última exclusão, o próximo Put primeiro os exclui, como Delete faz. Assim, uma entrada de exclusão lista no máximo 65.536 entradas.
  • O índice (cada chave viva e o número da sua entrada) fica na memória. Os valores ficam no log e são lidos do armazenamento quando pedidos, então a memória cresce com o número de chaves e de entradas, não com o tamanho dos valores.

Segurança

  • Open verifica o head com kololog.VerifyHead sob a chave do dono do log. A kolo-store já verificou contra ele cada entrada, registro, marcador de exclusão e a raiz Merkle.
  • As leituras descriptografam a entrada por meio da kolo-log, então um valor destruído nunca fica guardado em outro lugar. Um snapshot ou iterador criado antes de um Delete não retorna mais o valor destruído: a exclusão vence as visões mais antigas.
  • A entrada de exclusão e a destruição são duas gravações. Se uma falha ou uma gravação malsucedida acontecer entre elas, a entrada de exclusão já está no log, então a chave continua excluída, e os seus valores continuam legíveis no disco até o próximo Open destruí-los. Quando a exclusão automática de um Put falha assim, Put retorna o erro sem definir a chave.
  • Depois de Open, Get, Snapshot.Get e Iterator leem cada valor do armazenamento. Uma entrada que não bate mais com o seu registro verificado (kololog.ErrStorageMismatch) é ErrCorrupt, como em Open.
  • O escritor reproduz cada entrada que o seu head cobre. Uma entrada destruída que não está em nenhuma lista, uma chave de entrada ausente, uma lista que aponta para a entrada errada ou uma entrada que não decodifica é ErrCorrupt.
  • Toda operação começa com a tag kolo-kv/op/v0. Outra tag ou outro tipo, uma chave, um valor ou uma lista mais longos, uma lista que estoura, varints não mínimos ou bytes sobrando são ErrCorrupt.

Limites conhecidos

  • Experimental. A API pode mudar antes da v1.0.0.
  • Um único escritor. Put e Delete em um store aberto com OpenReader retornam ErrReadOnly.
  • Sem transações, sem índices secundários e sem compactação.
  • Um leitor só mostra novas entradas depois de Refresh, que é uma passada pelo log. Len pode diminuir depois de um Refresh.
  • Não existe forma JSON do formato das operações.

Erros

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

Teste os erros com errors.Is. Os erros da kolo-store e da kolo-log vindos do log ou da réplica passam adiante envolvidos, como kolostore.ErrClosed ou um erro do armazenamento, e um ErrCorrupt para um head que não passa na verificação ou para uma entrada que não bate mais com o seu registro também envolve o erro da kolo-log.

Referências

  • RFC 9162, Certificate Transparency Version 2.0 (Experimental, December 2021).
    • Usa: a seção 8.2, o monitor que guarda todas as entradas: a réplica só confia nas entradas que um head verificado cobre.
    • Não implementa: nada ficou de fora.