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-kvO 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.
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.
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() 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.
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 retornaErrKeyTooLarge. A chave vazia é uma chave válida.MaxValueSize: 1 MiB. Um valor maior retornaErrValueTooLarge.- Quando uma chave guarda 65.536 valores desde a sua última exclusão, o
próximo
Putprimeiro os exclui, comoDeletefaz. 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
Openverifica o head comkololog.VerifyHeadsob 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
Deletenã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
Opendestruí-los. Quando a exclusão automática de umPutfalha assim,Putretorna o erro sem definir a chave. - Depois de
Open,Get,Snapshot.GeteIteratorleem cada valor do armazenamento. Uma entrada que não bate mais com o seu registro verificado (kololog.ErrStorageMismatch) éErrCorrupt, como emOpen. - 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ãoErrCorrupt.
Limites conhecidos
- Experimental. A API pode mudar antes da v1.0.0.
- Um único escritor.
PuteDeleteem um store aberto comOpenReaderretornamErrReadOnly. - 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.Lenpode diminuir depois de umRefresh. - Não existe forma JSON do formato das operações.
Erros
| Erro | Mensagem |
|---|---|
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 |
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.