Help us shape the future of Go! Take the 2026 Go Developer Survey

sorted

package
v0.0.0-...-74c3634 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 3, 2026 License: Apache-2.0 Imports: 9 Imported by: 23

Documentation

Overview

Package sorted provides a KeyValue interface and constructor registry.

Index

Constants

View Source
const (
	MaxKeySize   = 767   // Maximum size, in bytes, for a key in any store implementing KeyValue.
	MaxValueSize = 63000 // Maximum size, in bytes, for a value in any store implementing KeyValue. MaxKeySize and MaxValueSize values originate from InnoDB and MySQL limitations.
)
View Source
const DefaultKVFileType = "leveldb"

DefaultKVFileType is the sorted type for file-backed stores that don't need a particular implementation. Import perkeep.org/pkg/sorted/defaultkv to register it.

Variables

View Source
var (
	ErrNotFound      = errors.New("sorted: key not found")
	ErrKeyTooLarge   = fmt.Errorf("sorted: key size is over %v", MaxKeySize)
	ErrValueTooLarge = fmt.Errorf("sorted: value size is over %v", MaxValueSize)
)

Functions

func CheckSizes

func CheckSizes(key, value string) error

CheckSizes returns ErrKeyTooLarge if key does not respect KeyMaxSize or ErrValueTooLarge if value does not respect ValueMaxSize

func Foreach

func Foreach(kv KeyValue, fn func(key, value string) error) error

Foreach runs fn for each key/value pair in kv. If fn returns an error, that same error is returned from Foreach and iteration stops.

func ForeachInRange

func ForeachInRange(kv KeyValue, start, end string, fn func(key, value string) error) error

ForeachInRange runs fn for each key/value pair in kv in the range of start and end, which behave the same as kv.Find. If fn returns an error, that same error is returned from Foreach and iteration stops. fn runs with the iterator open. Use ScanPaged if fn accesses kv or blocks on consumers that do.

func RegisterKeyValue

func RegisterKeyValue(typ string, fn func(jsonconfig.Obj) (KeyValue, error))

func ScanPaged

func ScanPaged(kv KeyValue, start, end string) iter.Seq[result.Of[Entry]]

ScanPaged returns a sequence of key/value pairs in kv in key order in the range specified by start and end, which behave the same as kv.Find. The sequence opens iterators lazily and can be iterated more than once; each iteration starts a new scan from start.

It buffers at most 1000 entries at a time and closes each iterator before yielding, so the loop body can safely read from or write to kv, even when an open iterator would otherwise block those operations. Subsequent pages resume at the last key and skip keys less than or equal to it, without extending the key or constructing a backend-specific bound. A page iterator may therefore read 1001 pairs, including the skipped key.

Unlike ForeachInRange, it uses a new iterator for each page and does not provide a snapshot across pages. Changes to later pages may be observed, while changes to already buffered pairs are not. Keys inserted at or before the last key of an already buffered page will not be visited.

Results contain successful entries, followed by at most one terminal error. If an iterator reports an error when closed, the entries successfully read from that page are yielded before the error. If iteration stops early, no more results (including a pending error) are yielded and no more iterators are opened.

Types

type BatchMutation

type BatchMutation interface {
	Set(key, value string)
	Delete(key string)
}

func NewBatchMutation

func NewBatchMutation() BatchMutation

type Entry

type Entry struct {
	Key, Value string
}

Entry is a key/value pair in a KeyValue.

type Iterator

type Iterator interface {
	// Next moves the iterator to the next key/value pair.
	// It returns false when the iterator is exhausted.
	Next() bool

	// Key returns the key of the current key/value pair.
	// Only valid after a call to Next returns true.
	Key() string

	// KeyBytes returns the key as bytes. The returned bytes
	// should not be written and are invalid after the next call
	// to Next or Close.
	// TODO(bradfitz): rename this and change it to return a
	// mem.RO instead?
	KeyBytes() []byte

	// Value returns the value of the current key/value pair.
	// Only valid after a call to Next returns true.
	Value() string

	// ValueBytes returns the value as bytes. The returned bytes
	// should not be written and are invalid after the next call
	// to Next or Close.
	// TODO(bradfitz): rename this and change it to return a
	// mem.RO instead?
	ValueBytes() []byte

	// Close closes the iterator and returns any accumulated error. Exhausting
	// all the key/value pairs in a table is not considered to be an error.
	// It is valid to call Close multiple times. Other methods should not be
	// called after the iterator has been closed.
	Close() error
}

Iterator iterates over an index KeyValue's key/value pairs in key order.

An iterator must be closed after use, but it is not necessary to read an iterator until exhaustion.

An iterator is not necessarily goroutine-safe, but it is safe to use multiple iterators concurrently, with each in a dedicated goroutine.

type KeyValue

type KeyValue interface {
	// Get gets the value for the given key. It returns ErrNotFound if the DB
	// does not contain the key.
	Get(key string) (string, error)

	Set(key, value string) error

	// Delete deletes keys. Deleting a non-existent key does not return an error.
	Delete(key string) error

	BeginBatch() BatchMutation
	CommitBatch(b BatchMutation) error

	// Find returns an iterator positioned before the first key/value pair
	// whose key is 'greater than or equal to' the given key. There may be no
	// such pair, in which case the iterator will return false on Next.
	//
	// The optional end value specifies the exclusive upper
	// bound. If the empty string, the iterator returns keys
	// where "key >= start".
	// If non-empty, the iterator returns keys where
	// "key >= start && key < endHint".
	//
	// Any error encountered will be implicitly returned via the iterator. An
	// error-iterator will yield no key/value pairs and closing that iterator
	// will return that error.
	//
	// An iterator may or may not observe writes made after Find returns;
	// implementations differ. Callers needing a consistent view across
	// several reads should use TransactionalReader, if implemented.
	Find(start, end string) Iterator

	// Close is a polite way for the server to shut down the storage.
	// Implementations should never lose data after a Set, Delete,
	// or CommmitBatch, though.
	Close() error
}

KeyValue is a sorted, enumerable key-value interface supporting batch mutations.

func NewKeyValue

func NewKeyValue(cfg jsonconfig.Obj) (KeyValue, error)

NewKeyValue returns a KeyValue as defined by cfg. It returns an error of type NeedWipeError when the returned KeyValue should be fixed with Wipe.

func NewKeyValueMaybeWipe

func NewKeyValueMaybeWipe(cfg jsonconfig.Obj) (KeyValue, error)

NewKeyValueMaybeWipe calls NewKeyValue and wipes the KeyValue if, and only if, NewKeyValue has returned a NeedWipeError.

func NewMemoryKeyValue

func NewMemoryKeyValue() KeyValue

NewMemoryKeyValue returns a KeyValue implementation that's backed only by memory. It's mostly useful for tests and development.

func WithPrefix

func WithPrefix(kv KeyValue, prefix string) KeyValue

WithPrefix returns a view of kv whose keys have prefix prepended in the backing store and removed when iterating. An empty prefix views the entire store. Prefixes are used verbatim, so one view's prefix must not be a prefix of another's if the views need disjoint namespaces.

Key size limits include the prefix. Invalid mutations return size errors; for batches, these errors are deferred until CommitBatch, which writes nothing if any mutation is invalid. A batch belongs to the view that created it, even if another view uses the same prefix.

Closing the view does not close kv. The view exposes no optional backend interfaces except TransactionalReader, when supported by kv. Closing a read transaction releases that transaction, not kv.

type Mutation

type Mutation interface {
	Key() string
	Value() string
	IsDelete() bool
}

type NeedWipeError

type NeedWipeError struct {
	Msg string
}

NeedWipeError is returned by NewKeyValue when the returned KeyValue is not usable until Wipe has been called on it.

func (NeedWipeError) Error

func (e NeedWipeError) Error() string

type ReadTransaction

type ReadTransaction interface {
	Get(key string) (string, error)
	Find(start, end string) Iterator

	// End the transaction.
	Close() error
}

ReadTransaction is a read-only transaction on a KeyValue. It admits the same read operations as the KeyValue itself, but writes that occur after the transaction is created are not observed.

Users should close the transaction as soon as it as no longer needed, as failing to do so can tie up resources.

type ReindexSession

type ReindexSession interface {
	KeyValue

	// Finish(true) durably commits all remaining writes and marks the index
	// complete, returning any previously encountered storage error as well.
	// Finish(false), or Close, aborts the pending group and leaves the index
	// marked incomplete; earlier committed groups may remain. In either
	// case Finish releases the session's resources, not the underlying KV.
	// A failed build's Index and caches must be discarded, not reused.
	Finish(success bool) error
}

ReindexSession is a private, concurrent-safe view of a rebuilding index. Unlike an ordinary KeyValue, individual successful mutations may not yet be durable. Reads see those mutations, including complete logical batches. The view must not be published to readers or used for live upload acks.

type Reindexer

type Reindexer interface {
	KeyValue

	// BeginReindex atomically discards the old rows and durably marks the
	// index incomplete. No other access to this storage is allowed until
	// the returned session is finished. An interrupted build must not be
	// accepted on an ordinary reopen; it requires another reindex or Wipe.
	BeginReindex() (ReindexSession, error)
}

Reindexer optionally supports batching writes to a disposable index. Only offline reindexing may use this interface; ordinary KeyValue mutations retain their normal durability guarantees.

type TransactionalReader

type TransactionalReader interface {
	KeyValue

	// BeginReadTx begins a read-only transaction.
	BeginReadTx() ReadTransaction
}

TransactionalReader is an optional interface that may be implemented by storage implementations. It may be implemented when a storage backend supports multiple atomic reads.

type Wiper

type Wiper interface {
	KeyValue

	// Wipe removes all key/value pairs, and resets the storage to a blank state.
	// For a given storage, when NewKeyValue returns a NeedWipeError, Wipe
	// should be implemented so that it fixes the returned KeyValue.
	Wipe() error
}

Wiper is an optional interface that may be implemented by storage implementations.

Directories

Path Synopsis
Package defaultkv registers the sorted.KeyValue implementation named by sorted.DefaultKVFileType.
Package defaultkv registers the sorted.KeyValue implementation named by sorted.DefaultKVFileType.
Package jsonfile registers the "jsonfile" sorted.KeyValue type, which keeps its rows in memory and in a JSON file, an object of string keys to string values, that it rewrites after each change.
Package jsonfile registers the "jsonfile" sorted.KeyValue type, which keeps its rows in memory and in a JSON file, an object of string keys to string values, that it rewrites after each change.
Package kvfile provides an implementation of sorted.KeyValue on top of a single mutable database file on disk using modernc.org/kv.
Package kvfile provides an implementation of sorted.KeyValue on top of a single mutable database file on disk using modernc.org/kv.
Package kvtest tests sorted.KeyValue implementations.
Package kvtest tests sorted.KeyValue implementations.
Package leveldb provides an implementation of sorted.KeyValue on top of a single mutable database file on disk using github.com/syndtr/goleveldb.
Package leveldb provides an implementation of sorted.KeyValue on top of a single mutable database file on disk using github.com/syndtr/goleveldb.
Package mysql provides an implementation of sorted.KeyValue on top of MySQL.
Package mysql provides an implementation of sorted.KeyValue on top of MySQL.
Package postgres provides an implementation of sorted.KeyValue on top of PostgreSQL.
Package postgres provides an implementation of sorted.KeyValue on top of PostgreSQL.
Package sqlite provides an implementation of sorted.KeyValue using an SQLite database file.
Package sqlite provides an implementation of sorted.KeyValue using an SQLite database file.
Package sqlkv implements the sorted.KeyValue interface using an *sql.DB.
Package sqlkv implements the sorted.KeyValue interface using an *sql.DB.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL