cdb

package module
v0.0.0-...-455a96b Latest Latest
Warning

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

Go to latest
Published: Feb 18, 2023 License: ISC Imports: 9 Imported by: 0

README

cdb

This is a "pure Go" implementation of "Constant Database" as described by D. J. Bernstein under http://cr.yp.to/cdb.html.

This is a read-only, disk-based, key-value store. The implementation embedded in the program. There is no need to have a client/server architecture.

The advantages are described D. J. Bernstein. But what people care the most are fast-look up (at most two disk accesses per lookup) and low overhead (2kib of metadata per database + 24b per records).

One of the limitation of cdb database is their 4GiB limit, since they store 32 bits positions pointers. This can be consider an advantage for SoC and embedded devices development.

The database is create with initial data once, and read-only. Some use cases include blazing fast static HTTP.

This is an alternative implementation to github.com/jbarham/cdb. For the following reason:

  • J. Barham's Go CDB implementation heavily uses panic() and recover() which is officially an "approved" method to handle errors, however it makes, IMHO, the code hard to follow.

  • J. Barham's Go CDB implementation copy the original cdb, especially for Dump. This tools offers more generic interfaces/methods.

Documentation

Index

Examples

Constants

This section is empty.

Variables

View Source
var (
	ErrOverflow       = errors.New("overflow error")
	ErrOverflowUint32 = fmt.Errorf("%w: over 4GiB which fits in a 32bit unsigned integer", ErrOverflow)
)
View Source
var DefaultCreateOptions = &CreateOptions{

	HeadroomPerMille: 250,
}
View Source
var NotFound = errors.New("not found")

Functions

func ContentToMapString

func ContentToMapString(content Content) (map[string]string, error)

func Create

func Create(writer io.WriterAt, content Content, opts *CreateOptions) error

Create creates a constant database with the given content.

The data is never kept entirely in memory. However a few 32bits integer are kept in memory for each key/value pair, in order to write the hash tables at the end.

If opts are nil, the DefaultCreateOptions are used.

func CreateFile

func CreateFile(fname string, content Content, opts *CreateOptions) error

CreateFile creates a constant database with the given content into the file.

func CreateInto

func CreateInto(writer io.Writer, content Content, opts *CreateOptions) error

CreateInto creates a constant database with the given content into a Writer.

Because of the nature of how constant database are created, this method buffers the entire data in memory.

Types

type Content

type Content interface {
	Next() bool
	KeyValue() *KeyValue
	Err() error
}

Content represent a list of KeyValue.

Content is not goroutine safe, and MUST NOT be used in mutiple goroutine at the same time.

Example
/* Copyright 2023, Antoine Catton
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
 * FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
 * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 */

package main

import (
	"fmt"
	"io"
)

func getContent() Content {
	return &KeyValueMapString{
		Map: map[string]string{"foo": "bar"},
	}
}

func main() {
	var content Content = getContent()
	for content.Next() {
		kv := content.KeyValue()
		key, err := io.ReadAll(kv.Key)
		if err != nil {
			fmt.Printf("ERROR: while reading key: %v\n", err)
		}
		value, err := io.ReadAll(kv.Value)
		if err != nil {
			fmt.Printf("ERROR: while reading value: %v\n", err)
		}
		fmt.Printf("%q=%q\n", key, value)
	}
	if err := content.Err(); err != nil {
		fmt.Printf("ERROR: while scanning content: %v\n", err)
	}
}
Output:

"foo"="bar"

type CreateOptions

type CreateOptions struct {
	// Headroom in ‰ (= tenth of a percent). This is the headroom left after
	// the hash table is full. This number should be between 0 and 999.
	// Here are a few rules:
	//   * 1000‰ headroom would lead to a division by zero.
	//   * 0 means the hashtable is fully populated.
	//   * if the hash table has 1000 entries, 1‰ means it will contain 1001
	//     slots after creation.
	HeadroomPerMille int
}

type Database

type Database struct {
	// contains filtered or unexported fields
}

Database represents a read-only database.

It can be created with NewDatabase or with Open. Its goroutine safety depends on the underlying ReaderAt being used. It does not guard reads with a mutex. For files (= using Open()) or mmaps (= using golang.org/x/exp/mmap), it is goroutine safe. For other ReaderAt, please consult the documentations for these.

func NewDatabase

func NewDatabase(r io.ReaderAt) (*Database, error)

NewDatabase instantiate a new database from a ReaderAt

This allows to instantiate a database from an mmap file, using golang.org/x/exp/mmap for example.

func Open

func Open(fname string) (*Database, func() error, error)

Open opens a CDB file as a database.

The resulting database is thread safe. For better performance, it might advisable to pass the result of a mmap.Open() call to NewDatabase() by using golang.org/x/exp/mmap. This is not provided by default as an API in order to prevent dependency-creep.

Open also returns the function to close the file.

func (*Database) Get

func (db *Database) Get(key []byte) ([]byte, error)

Get fetches the value as a slice of bytes.

If the key is not found it will return (nil, NotFound).

func (*Database) GetAsReader

func (db *Database) GetAsReader(key []byte) (io.Reader, error)

GetAsReader gets the value as a reader.

The returned reader is not goroutine specific, and MUST NOT be shared across goroutine.

If the key is not found it will return (nil, NotFound).

func (*Database) GetString

func (db *Database) GetString(key string) (string, error)

Get fetches the value as string for a string key.

If the key is not found it will return ("", NotFound).

func (*Database) GetStringAsReader

func (db *Database) GetStringAsReader(key string) (io.Reader, error)

GetStringAsReader is the exact same as GetAsReader, but it takes a string.

func (*Database) Has

func (db *Database) Has(key []byte) (bool, error)

Has checks if a key exists.

func (*Database) HasString

func (db *Database) HasString(key string) (bool, error)

Has checks if a key string exists.

type KeyValue

type KeyValue struct {
	KeyLen   int32
	Key      io.Reader
	ValueLen int32
	Value    io.Reader
}

KeyValue represent a stream Key and Value pair.

Key MUST be fully read before reading the Value reader. If not, behavior are undefined.

KeyValue is not goroutine safe, and MUST NOT be used in multiple goroutine at the same time.

type KeyValueMapString

type KeyValueMapString struct {
	Map map[string]string
	// contains filtered or unexported fields
}

KeyValueMapString is a simple wrapper for a map[string]string, in order to provide a content interface.

KeyValueMapString MUST NOT be shared across goroutines, as it is not goroutine safe.

func (*KeyValueMapString) Err

func (kv *KeyValueMapString) Err() error

func (*KeyValueMapString) KeyValue

func (kv *KeyValueMapString) KeyValue() *KeyValue

func (*KeyValueMapString) Next

func (kv *KeyValueMapString) Next() bool

Directories

Path Synopsis
cmd

Jump to

Keyboard shortcuts

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