internal

package
v0.2.3-0...-31b6e5e Latest Latest
Warning

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

Go to latest
Published: Feb 11, 2021 License: BSL-1.0 Imports: 14 Imported by: 0

Documentation

Index

Constants

View Source
const (
	// Bucket header
	BucketHeaderSize = SizeUint16 +
		SizeUint48 // Spill

	// Bucket item
	BucketEntrySize = SizeUint48 +
		SizeUint48 +
		SizeUint64 // Hash
)
View Source
const (
	MaxUint16 = math.MaxUint16
	MaxUint24 = 0xffffff
	MaxUint32 = math.MaxUint32
	MaxUint48 = 0x0000ffffffffffff
	MaxUint64 = math.MaxUint64

	MaxInt16 = math.MaxInt16

	MaxBlockSize = MaxUint16 // maximum length of a keyfile block in bytes (must not be larger than MaxKeySize due to on-disk representation)
	MaxKeySize   = MaxUint16 // maximum length of a data record's key in bytes
	MaxDataSize  = MaxUint48 // maximum length of a data record's value in bytes
)
View Source
const (
	SizeUint16 = 2
	SizeUint24 = 3
	SizeUint32 = 4
	SizeUint48 = 6
	SizeUint64 = 8
)
View Source
const (
	DatFileHeaderSize = SizeUint64 +
		SizeUint16 +
		SizeUint64 +
		SizeUint64 +
		SizeUint16 +
		64 // (Reserved)

	KeyFileHeaderSize = 8 +
		SizeUint16 +
		SizeUint64 +
		SizeUint64 +
		SizeUint16 +
		SizeUint64 +
		SizeUint64 +
		SizeUint16 +
		SizeUint16 +
		56 // (Reserved)

	LogFileHeaderSize = 8 +
		SizeUint16 +
		SizeUint64 +
		SizeUint64 +
		SizeUint16 +
		SizeUint64 +
		SizeUint64 +
		SizeUint16 +
		SizeUint64 +
		SizeUint64 // DataFileSize

	SpillHeaderSize = SizeUint48 +
		SizeUint16 // size
)

Variables

View Source
var (
	ErrAppNumMismatch     = errors.New("appnum mismatch")
	ErrDataMissing        = errors.New("data missing")
	ErrDataTooLarge       = errors.New("data too large")
	ErrDifferentVersion   = errors.New("different version")
	ErrHashMismatch       = errors.New("hash mismatch")
	ErrInvalidBlockSize   = errors.New("invalid block size")
	ErrInvalidBucketCount = errors.New("invalid bucket count")
	ErrInvalidCapacity    = errors.New("invalid capacity")
	ErrInvalidDataRecord  = errors.New("not a data record: contains spill marker")
	ErrInvalidKeySize     = errors.New("invalid key size")
	ErrInvalidLoadFactor  = errors.New("invalid load factor")
	ErrInvalidRecordSize  = errors.New("invalid record size")
	ErrInvalidSpill       = errors.New("not a spill record: missing spill marker")
	ErrKeyExists          = errors.New("key exists")
	ErrKeyMismatch        = errors.New("key mismatch")
	ErrKeyMissing         = errors.New("key missing")
	ErrKeyNotFound        = errors.New("key not found")
	ErrKeySizeMismatch    = errors.New("key size mismatch")
	ErrKeyTooLarge        = errors.New("key too large")
	ErrKeyWrongSize       = errors.New("key wrong size") // deprecated: use ErrKeyMissing and ErrKeyTooLarge instead
	ErrNotDataFile        = errors.New("not a data file")
	ErrNotKeyFile         = errors.New("not a key file")
	ErrNotLogFile         = errors.New("not a log file")
	ErrShortKeyFile       = errors.New("short key file")
	ErrUIDMismatch        = errors.New("uid mismatch")
)
View Source
var (
	DatFileHeaderType = []byte("gonudbdt")
	KeyFileHeaderType = []byte("gonudbky")
	LogFileHeaderType = []byte("gonudblg")
)
View Source
var GitVersion string = "unknown"

Functions

func BucketCapacity

func BucketCapacity(blockSize int) int

BucketCapacity returns the number of entries that fit in a bucket

func BucketIndex

func BucketIndex(h uint64, buckets int, modulus uint64) int

func BucketSize

func BucketSize(capacity int) int

BucketSize returns the actual size of a bucket. This can be smaller than the block size.

func CreateDataFile

func CreateDataFile(path string, appnum, uid uint64) error

func CreateKeyFile

func CreateKeyFile(path string, uid uint64, appnum uint64, salt uint64, blockSize int, loadFactor float64) error

func CreateStore

func CreateStore(datPath, keyPath, logPath string, appnum, uid, salt uint64, blockSize int, loadFactor float64) error

func DecodeUint16

func DecodeUint16(b []byte) uint16

func DecodeUint24

func DecodeUint24(b []byte) uint32

func DecodeUint32

func DecodeUint32(b []byte) uint32

func DecodeUint48

func DecodeUint48(b []byte) uint64

func DecodeUint64

func DecodeUint64(b []byte) uint64

func EncodeUint16

func EncodeUint16(b []byte, v uint16)

func EncodeUint24

func EncodeUint24(b []byte, v uint32)

func EncodeUint32

func EncodeUint32(b []byte, v uint32)

func EncodeUint48

func EncodeUint48(b []byte, v uint64)

func EncodeUint64

func EncodeUint64(b []byte, v uint64)

func NewSalt

func NewSalt() uint64

NewSalt returns a random salt or panics if the system source of entropy cannot be read

func NewUID

func NewUID() uint64

NewUID returns a random identifier or panics if the system source of entropy cannot be read

func Version

func Version() string

String formats the version in semver format, see semver.org

Types

type Bucket

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

TODO: evaluate tradeoffs of using a slice of Entry instead of blob

func NewBucket

func NewBucket(blockSize int, blob []byte) *Bucket

bucket takes ownership of blob

func (*Bucket) ActualSize

func (b *Bucket) ActualSize() int

ActualSize returns the serialized bucket size, excluding empty space

func (*Bucket) BlockSize

func (b *Bucket) BlockSize() int

func (*Bucket) Capacity

func (b *Bucket) Capacity() int

func (*Bucket) CopyInto

func (b *Bucket) CopyInto(b2 *Bucket)

func (*Bucket) Count

func (b *Bucket) Count() int

Count returns the number of entries in the bucket

func (*Bucket) Entry

func (b *Bucket) Entry(idx int) Entry

Returns the record for a key entry without bounds checking.

func (*Bucket) Has

func (b *Bucket) Has(h uint64) bool

func (*Bucket) HighestHash

func (b *Bucket) HighestHash() uint64

func (*Bucket) IsEmpty

func (b *Bucket) IsEmpty() bool

func (*Bucket) IsFull

func (b *Bucket) IsFull() bool

func (*Bucket) LoadFrom

func (b *Bucket) LoadFrom(spill int64, s Spiller) error

LoadFrom reads data containing entries from r, padding the rest of the bucket with zero bytes.

func (*Bucket) Lock

func (b *Bucket) Lock()

func (*Bucket) LowestHash

func (b *Bucket) LowestHash() uint64

func (*Bucket) SetSpill

func (b *Bucket) SetSpill(v int64)

SetSpill sets the offset of next spill record

func (*Bucket) Spill

func (b *Bucket) Spill() int64

Spill returns offset of next spill record or 0

func (*Bucket) Unlock

func (b *Bucket) Unlock()

func (*Bucket) WriteTo

func (b *Bucket) WriteTo(w io.Writer) (int64, error)

WriteTo writes data to w until all entries in the bucket are written or an error occurs.

type BucketCache

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

func (*BucketCache) BucketCount

func (c *BucketCache) BucketCount() int

BucketCount returns the number of buckets in the cache

func (*BucketCache) EntryCount

func (c *BucketCache) EntryCount() int

EntryCount returns the number of entries in the cache

func (*BucketCache) Exists

func (c *BucketCache) Exists(hash uint64, key string, df *DataFile) (bool, error)

Exists reports whether a record with the given hash and key exists in the data file

func (*BucketCache) Fetch

func (c *BucketCache) Fetch(hash uint64, key string, df *DataFile) (io.Reader, error)

Fetch returns a reader that can be used to read the data record associated with the key

func (*BucketCache) FetchHeader

func (c *BucketCache) FetchHeader(hash uint64, key string, df *DataFile) (*DataRecordHeader, error)

FetchHeader returns a record header for the data record associated with the key

func (*BucketCache) Get

func (c *BucketCache) Get(idx int) *Bucket

Get retrieves a copy of the bucket at index idx

func (*BucketCache) Has

func (c *BucketCache) Has(hash uint64, sp Spiller) (bool, error)

func (*BucketCache) Insert

func (c *BucketCache) Insert(offset int64, size int64, hash uint64, df Spiller) error

func (*BucketCache) WriteDirty

func (c *BucketCache) WriteDirty(lf *LogFile, kf *KeyFile) (int64, error)

type BucketRecord

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

type BucketScanner

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

BucketScanner implements a sequential scan through a key file. Successive calls to the Next method will step through the buckets in the file, including spilled buckets in the data file.

func (*BucketScanner) Bucket

func (b *BucketScanner) Bucket() *Bucket

Bucket returns the current bucket. Should not be called until Next has been called. The bucket is backed by data that may be overwritten with a call to Next so should not be retained.

func (*BucketScanner) Close

func (b *BucketScanner) Close() error

func (*BucketScanner) Err

func (b *BucketScanner) Err() error

Err returns the first non-EOF error that was encountered by the BucketScanner.

func (*BucketScanner) Index

func (b *BucketScanner) Index() int

Index returns the index of the current bucket. Should not be called until Next has been called. Spill buckets share an index with their parent.

func (*BucketScanner) IsSpill

func (b *BucketScanner) IsSpill() bool

IsSpill reports whether the current bucket was read from a data store spill.

func (*BucketScanner) Next

func (b *BucketScanner) Next() bool

Next reads the next bucket in sequence, including spills to the data store. It returns false if it encounters an error or there are no more buckets to read.

type Cache

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

Cache is an in memory buffer of buckets. It is not safe for concurrent use.

func NewCache

func NewCache(keySize int, blockSize int, sizeHint int) *Cache

func (*Cache) Clear

func (c *Cache) Clear()

func (*Cache) Count

func (c *Cache) Count() int

func (*Cache) Find

func (c *Cache) Find(n int) (*Bucket, bool)

func (*Cache) Has

func (c *Cache) Has(n int) bool

func (*Cache) Insert

func (c *Cache) Insert(idx int, b *Bucket)

func (*Cache) TakeData

func (c *Cache) TakeData() *CacheData

TakeData takes ownership of the Cache's data. The Cache is cleared after.

func (*Cache) WithBuckets

func (c *Cache) WithBuckets(fn func(bs []BucketRecord) error) error

type CacheData

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

CacheData is a read only view of a bucket cache. It is safe for concurrent use.

func (*CacheData) Count

func (c *CacheData) Count() int

func (*CacheData) Find

func (c *CacheData) Find(n int) (*Bucket, bool)

func (*CacheData) Has

func (c *CacheData) Has(n int) bool

func (*CacheData) WithBuckets

func (c *CacheData) WithBuckets(fn func(bs []BucketRecord) error) error

type CountWriter

type CountWriter interface {
	WriterFlusher

	// Offset returns the position in the file at which the next write will be made
	Offset() int64

	// Count returns the number of bytes written
	Count() int64
}

type DatFileHeader

type DatFileHeader struct {
	Type    [8]byte
	Version uint16
	UID     uint64
	AppNum  uint64
}

func (*DatFileHeader) DecodeFrom

func (d *DatFileHeader) DecodeFrom(r io.Reader) error

DecodeFrom reads d from a reader

func (*DatFileHeader) EncodeTo

func (d *DatFileHeader) EncodeTo(w io.Writer) error

EncodeTo writes d to a writer

func (*DatFileHeader) Size

func (*DatFileHeader) Size() int

func (*DatFileHeader) Verify

func (d *DatFileHeader) Verify() error

Verify contents of data file header

func (*DatFileHeader) VerifyMatchingKey

func (d *DatFileHeader) VerifyMatchingKey(k *KeyFileHeader) error

VerifyMatchingKey makes sure key file and data file headers match

type DataFile

type DataFile struct {
	Path   string
	Header DatFileHeader
	// contains filtered or unexported fields
}

DataFile assumes it has exclusive write access to the file

func OpenDataFile

func OpenDataFile(path string) (*DataFile, error)

OpenDataFile opens a data file for appending and random reads

func (*DataFile) AppendBucketSpill

func (d *DataFile) AppendBucketSpill(blob []byte) (int64, error)

func (*DataFile) AppendRecord

func (d *DataFile) AppendRecord(dr *DataRecord) (int64, error)

AppendRecord writes a record to the data file. It returns the position at which the record was written.

func (*DataFile) Close

func (d *DataFile) Close() error

func (*DataFile) Flush

func (d *DataFile) Flush() error

func (*DataFile) LoadBucketSpill

func (d *DataFile) LoadBucketSpill(offset int64, blob []byte) error

func (*DataFile) LoadRecordHeader

func (d *DataFile) LoadRecordHeader(offset int64) (*DataRecordHeader, error)

func (*DataFile) Offset

func (d *DataFile) Offset() int64

func (*DataFile) RecordDataReader

func (d *DataFile) RecordDataReader(offset int64, key string) (io.Reader, error)

func (*DataFile) RecordScanner

func (d *DataFile) RecordScanner() *RecordScanner

RecordScanner returns a RecordScanner that may be used to iterate over the records in the data file.

func (*DataFile) Size

func (d *DataFile) Size() (int64, error)

func (*DataFile) Sync

func (d *DataFile) Sync() error

type DataRecord

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

type DataRecordHeader

type DataRecordHeader struct {
	DataSize int64
	KeySize  uint16
	Key      []byte
}

DataRecordHeader is prepended to each record written to the data file. Layout is:

6 bytes  DataSize
2 bytes  KeySize
n bytes  Key

func (*DataRecordHeader) IsData

func (d *DataRecordHeader) IsData() bool

IsData reports whether the data record contains data

func (*DataRecordHeader) IsSpill

func (d *DataRecordHeader) IsSpill() bool

IsSpill reports whether the data record is a bucket spill

func (*DataRecordHeader) Size

func (d *DataRecordHeader) Size() int64

Size returns the size of the header in bytes

type Entry

type Entry struct {
	Offset int64 // 48 bits
	Size   int64 // 48 bits
	Hash   uint64
}

type Hasher

type Hasher uint64

func (Hasher) Hash

func (h Hasher) Hash(data []byte) uint64

func (Hasher) HashString

func (h Hasher) HashString(data string) uint64

type KeyFile

type KeyFile struct {
	Path   string
	Header KeyFileHeader
	// contains filtered or unexported fields
}

KeyFile assumes it has exclusive write access to the file

func OpenKeyFile

func OpenKeyFile(path string) (*KeyFile, error)

OpenKeyFile opens a key file for random reads and writes

func (*KeyFile) BlockSize

func (k *KeyFile) BlockSize() uint16

func (*KeyFile) BucketScanner

func (k *KeyFile) BucketScanner(df *DataFile) *BucketScanner

BucketScanner returns a BucketScanner that may be used to iterate over the buckets in the key file.

func (*KeyFile) Close

func (k *KeyFile) Close() error

func (*KeyFile) Hash

func (k *KeyFile) Hash(key []byte) uint64

func (*KeyFile) HashString

func (k *KeyFile) HashString(key string) uint64

func (*KeyFile) LoadBucket

func (k *KeyFile) LoadBucket(idx int) (*Bucket, error)

func (*KeyFile) PutBucket

func (k *KeyFile) PutBucket(idx int, b *Bucket) error

expects to have exclusive access to b

func (*KeyFile) Size

func (k *KeyFile) Size() (int64, error)

func (*KeyFile) Sync

func (k *KeyFile) Sync() error

type KeyFileHeader

type KeyFileHeader struct {
	Type    [8]byte
	Version uint16
	UID     uint64
	AppNum  uint64

	Salt       uint64
	Pepper     uint64
	BlockSize  uint16
	LoadFactor uint16

	// Computed values
	Capacity int    // Entries per bucket
	Buckets  int    // Number of buckets
	Modulus  uint64 // pow(2,ceil(log2(buckets)))
}

func (*KeyFileHeader) DecodeFrom

func (k *KeyFileHeader) DecodeFrom(r io.Reader, fileSize int64) error

func (*KeyFileHeader) EncodeTo

func (k *KeyFileHeader) EncodeTo(w io.Writer) error

func (*KeyFileHeader) Size

func (k *KeyFileHeader) Size() int

func (*KeyFileHeader) Verify

func (k *KeyFileHeader) Verify() error

Verify contents of key file header

type LogFile

type LogFile struct {
	Path   string
	Header LogFileHeader
	// contains filtered or unexported fields
}

func OpenLogFile

func OpenLogFile(path string) (*LogFile, error)

OpenLogFile opens a log file for appending, creating it if necessary.

func (*LogFile) AppendBucket

func (l *LogFile) AppendBucket(idx int, b *Bucket) (int64, error)

func (*LogFile) Close

func (l *LogFile) Close() error

func (*LogFile) Flush

func (l *LogFile) Flush() error

func (*LogFile) Prepare

func (l *LogFile) Prepare(df *DataFile, kf *KeyFile) error

func (*LogFile) Sync

func (l *LogFile) Sync() error

func (*LogFile) Truncate

func (l *LogFile) Truncate() error

type LogFileHeader

type LogFileHeader struct {
	Type        [8]byte
	Version     uint16
	UID         uint64
	AppNum      uint64
	Salt        uint64
	Pepper      uint64
	BlockSize   uint16
	KeyFileSize int64
	DatFileSize int64
}

func (*LogFileHeader) DecodeFrom

func (l *LogFileHeader) DecodeFrom(r io.Reader) error

func (*LogFileHeader) EncodeTo

func (l *LogFileHeader) EncodeTo(w io.Writer) error

func (*LogFileHeader) Size

func (l *LogFileHeader) Size() int

type Pool

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

Buffers data records in a map

func NewPool

func NewPool(sizeHint int) *Pool

func (*Pool) Clear

func (p *Pool) Clear()

func (*Pool) Count

func (p *Pool) Count() int

Count returns the number of data records in the pool

func (*Pool) DataSize

func (p *Pool) DataSize() int

DataSize returns the sum of data sizes in the pool

func (*Pool) Find

func (p *Pool) Find(key string) ([]byte, bool)

func (*Pool) Has

func (p *Pool) Has(key string) bool

func (*Pool) Insert

func (p *Pool) Insert(hash uint64, key string, value []byte)

func (*Pool) IsEmpty

func (p *Pool) IsEmpty() bool

func (*Pool) WithRecords

func (p *Pool) WithRecords(fn func([]DataRecord) error) error

func (*Pool) WriteRecords

func (p *Pool) WriteRecords(df *DataFile) (int64, error)

type RecordScanner

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

RecordScanner implements a sequential scan through a data file. Successive calls to the Next method will step through the records in the file.

func (*RecordScanner) Close

func (s *RecordScanner) Close() error

func (*RecordScanner) Err

func (s *RecordScanner) Err() error

Err returns the first non-EOF error that was encountered by the RecordScanner.

func (*RecordScanner) IsData

func (s *RecordScanner) IsData() bool

IsData reports whether the current record is a data record

func (*RecordScanner) IsSpill

func (s *RecordScanner) IsSpill() bool

IsSpill reports whether the current record is a bucket spill

func (*RecordScanner) Key

func (s *RecordScanner) Key() string

Key returns the key of the current record

func (*RecordScanner) Next

func (s *RecordScanner) Next() bool

Next reads the next bucket in sequence, including spills to the data store. It returns false if it encounters an error or there are no more buckets to read.

func (*RecordScanner) Reader

func (s *RecordScanner) Reader() io.Reader

Reader returns an io.Reader that may be used to read the data from the record. Should not be called until Next has been called. The Reader is only valid for use until the next call to Next().

func (*RecordScanner) RecordSize

func (s *RecordScanner) RecordSize() int64

RecordSize returns the number of bytes occupied by the current record including its header

func (*RecordScanner) Size

func (s *RecordScanner) Size() int64

Size returns the size of the current record's data in bytes

type SectionWriter

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

SectionWriter implements Write on a section of an underlying WriterAt

func NewSectionWriter

func NewSectionWriter(w io.WriterAt, offset int64, size int64) *SectionWriter

func (*SectionWriter) Write

func (s *SectionWriter) Write(v []byte) (int, error)

type Spiller

type Spiller interface {
	LoadBucketSpill(int64, []byte) error
	AppendBucketSpill([]byte) (int64, error)
	Flush() error
}

type Store

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

func OpenStore

func OpenStore(datPath, keyPath, logPath string, syncInterval time.Duration, elogger logr.Logger, dlogger logr.Logger, tlogger logr.Logger) (*Store, error)

func (*Store) Close

func (s *Store) Close() error

func (*Store) DataFile

func (s *Store) DataFile() *DataFile

func (*Store) DataSize

func (s *Store) DataSize(key string) (int64, error)

func (*Store) Err

func (s *Store) Err() error

Err returns an error if the store is in an error state, nil otherwise

func (*Store) Exists

func (s *Store) Exists(key string) (bool, error)

func (*Store) FetchReader

func (s *Store) FetchReader(key string) (io.Reader, error)

func (*Store) Flush

func (s *Store) Flush()

func (*Store) Insert

func (s *Store) Insert(key string, data []byte) error

func (*Store) KeyFile

func (s *Store) KeyFile() *KeyFile

func (*Store) LogFile

func (s *Store) LogFile() *LogFile

func (*Store) Rate

func (s *Store) Rate() float64

func (*Store) RecordCount

func (s *Store) RecordCount() int

type VerifyResult

type VerifyResult struct {
	DatPath    string  // The path to the data file
	KeyPath    string  // The path to the key file
	Version    uint16  // The API version used to create the database
	UID        uint64  // The unique identifier
	AppNum     uint64  // The application-defined constant
	Salt       uint64  // The salt used in the key file
	Pepper     uint64  // The salt fingerprint
	BlockSize  uint16  // The block size used in the key file
	LoadFactor float64 // The target load factor used in the key file

	KeyFileSize int64 // The size of the key file in bytes
	DatFileSize int64 // The size of the data file in bytes
	Capacity    int   // The maximum number of keys each bucket can hold
	Buckets     int   // The number of buckets in the key file
	BucketSize  int64 // The size of a bucket in bytes
	Modulus     uint64

	KeyCount         int64   // The number of keys found
	ValueCountInUse  int64   // The number of values found that are referenced by a key
	ValueCountTotal  int64   // The number of values found
	ValueBytesInUse  int64   // The total number of bytes occupied by values that are referenced by a key
	ValueBytesTotal  int64   // The total number of bytes occupied by values
	RecordBytesInUse int64   // The total number of bytes occupied by records (header + value) that are referenced by a key
	RecordBytesTotal int64   // The total number of bytes occupied by records (header + value)
	SpillCountInUse  int64   // The number of spill records in use
	SpillCountTotal  int64   // The total number of spill records
	SpillBytesInUse  int64   // The number of bytes occupied by spill records in use
	SpillBytesTotal  int64   // The number of bytes occupied by all spill records
	AverageFetch     float64 // Average number of key file reads per fetch
	Waste            float64 // The fraction of the data file that is wasted
	Overhead         float64 // The data amplification ratio (size of data files compared to the size of the underlying data and keys)
	ActualLoad       float64 // The measured bucket load fraction (number of keys as a fraction of the total capacity)
}

func VerifyStore

func VerifyStore(datPath, keyPath string, logger logr.Logger) (*VerifyResult, error)

VerifyStore verifies consistency of the data and key files.

type WriterFlusher

type WriterFlusher interface {
	io.Writer
	Flush() error
}

Jump to

Keyboard shortcuts

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