tbtree

package
v1.5.0 Latest Latest
Warning

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

 Go to latest Published: Jun 20, 2023 License: Apache-2.0 Imports: 22 Imported by: 0

Documentation

Overview

Copyright 2022 Codenotary Inc. All rights reserved.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at 

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Index

Constants

View Source 
const (
	InnerNodeType = iota
	LeafNodeType
)
View Source 
const (
	MetaVersion      = "VERSION"
	MetaMaxNodeSize  = "MAX_NODE_SIZE"
	MetaMaxKeySize   = "MAX_KEY_SIZE"
	MetaMaxValueSize = "MAX_VALUE_SIZE"
)
View Source 
const DefaultCacheSize = 100_000
View Source 
const DefaultCleanUpPercentage float32 = 0
View Source 
const DefaultCommitLogMaxOpenedFiles = 1
View Source 
const DefaultCompactionThld = 2
View Source 
const DefaultDelayDuringCompaction = time.Duration(10) * time.Millisecond
View Source 
const DefaultFileMode = os.FileMode(0755)
View Source 
const DefaultFileSize = 1 << 26 // 64Mb
View Source 
const DefaultFlushBufferSize = 4096
View Source 
const DefaultFlushThld = 100_000
View Source 
const DefaultHistoryLogMaxOpenedFiles = 1
View Source 
const DefaultMaxActiveSnapshots = 100
View Source 
const DefaultMaxKeySize = 1024
View Source 
const DefaultMaxNodeSize = 4096
View Source 
const DefaultMaxValueSize = 512
View Source 
const DefaultNodesLogMaxOpenedFiles = 10
View Source 
const DefaultRenewSnapRootAfter = time.Duration(1000) * time.Millisecond
View Source 
const DefaultSyncThld = 1_000_000
View Source 
const MinCacheSize = 1
View Source 
const Version = 3

Variables

View Source 
var ErrAlreadyClosed = errors.New("tbtree: index already closed")
View Source 
var ErrCompactAlreadyInProgress = errors.New("tbtree: compact already in progress")
View Source 
var ErrCompactionThresholdNotReached = errors.New("tbtree: compaction threshold not yet reached")
View Source 
var ErrCorruptedCLog = errors.New("tbtree: commit log is corrupted")
View Source 
var ErrCorruptedFile = errors.New("tbtree: file is corrupted")
View Source 
var ErrIllegalArguments = fmt.Errorf("tbtree: %w", embedded.ErrIllegalArguments)
View Source 
var ErrIllegalState = embedded.ErrIllegalState // TODO: grpc error mapping hardly relies on the actual message, see IllegalStateHandlerInterceptor
View Source 
var ErrIncompatibleDataFormat = errors.New("tbtree: incompatible data format")
View Source 
var ErrInvalidOptions = fmt.Errorf("%w: invalid options", ErrIllegalArguments)
View Source 
var ErrKeyNotFound = fmt.Errorf("tbtree: %w", embedded.ErrKeyNotFound)
View Source 
var ErrNoMoreEntries = fmt.Errorf("tbtree: %w", embedded.ErrNoMoreEntries)
View Source 
var ErrOffsetOutOfRange = fmt.Errorf("tbtree: %w", embedded.ErrOffsetOutOfRange)
View Source 
var ErrReadersNotClosed = errors.New("tbtree: readers not closed")
View Source 
var ErrReadingFileContent = errors.New("tbtree: error reading required file content")
View Source 
var ErrSnapshotsNotClosed = errors.New("tbtree: snapshots not closed")
View Source 
var ErrTargetPathAlreadyExists = errors.New("tbtree: target folder already exists")
View Source 
var ErrorMaxKeySizeExceeded = errors.New("tbtree: max key size exceeded")
View Source 
var ErrorMaxValueSizeExceeded = errors.New("tbtree: max value size exceeded")
View Source 
var ErrorPathIsNotADirectory = errors.New("tbtree: path is not a directory")
View Source 
var ErrorToManyActiveSnapshots = errors.New("tbtree: max active snapshots limit reached")

Functions

This section is empty.

Types

type AppFactoryFunc added in v1.0.5 

type AppFactoryFunc func(
	rootPath string,
	subPath string,
	opts *multiapp.Options,
) (appendable.Appendable, error)

type HistoryReader added in v0.9.1 

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

func (*HistoryReader) Close added in v0.9.1 

func (r *HistoryReader) Close() error

func (*HistoryReader) Read added in v0.9.1 

func (r *HistoryReader) Read() (tss []uint64, err error)

type HistoryReaderSpec added in v0.9.1 

type HistoryReaderSpec struct {
	Key       []byte
	Offset    uint64
	DescOrder bool
	ReadLimit int
}

type KVT added in v1.5.0 

type KVT struct {
	K []byte
	V []byte
	T uint64
}

type Options 

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

func DefaultOptions 

func DefaultOptions() *Options

func (*Options) Validate added in v1.2.4 

func (opts *Options) Validate() error

func (*Options) WithAppFactory added in v1.0.5 

func (opts *Options) WithAppFactory(appFactory AppFactoryFunc) *Options

func (*Options) WithCacheSize 

func (opts *Options) WithCacheSize(cacheSize int) *Options

func (*Options) WithCleanupPercentage added in v1.2.3 

func (opts *Options) WithCleanupPercentage(cleanupPercentage float32) *Options

func (*Options) WithCommitLogMaxOpenedFiles added in v1.2.3 

func (opts *Options) WithCommitLogMaxOpenedFiles(commitLogMaxOpenedFiles int) *Options

func (*Options) WithCompactionThld added in v0.9.2 

func (opts *Options) WithCompactionThld(compactionThld int) *Options

func (*Options) WithDelayDuringCompaction added in v0.9.2 

func (opts *Options) WithDelayDuringCompaction(delay time.Duration) *Options

func (*Options) WithFileMode 

func (opts *Options) WithFileMode(fileMode os.FileMode) *Options

func (*Options) WithFileSize 

func (opts *Options) WithFileSize(fileSize int) *Options

func (*Options) WithFlushBufferSize added in v1.2.3 

func (opts *Options) WithFlushBufferSize(size int) *Options

func (*Options) WithFlushThld 

func (opts *Options) WithFlushThld(flushThld int) *Options

func (*Options) WithHistoryLogMaxOpenedFiles added in v1.2.3 

func (opts *Options) WithHistoryLogMaxOpenedFiles(historyLogMaxOpenedFiles int) *Options

func (*Options) WithLogger added in v1.2.4 

func (opts *Options) WithLogger(logger logger.Logger) *Options

func (*Options) WithMaxActiveSnapshots 

func (opts *Options) WithMaxActiveSnapshots(maxActiveSnapshots int) *Options

func (*Options) WithMaxKeySize added in v1.2.4 

func (opts *Options) WithMaxKeySize(maxKeySize int) *Options

func (*Options) WithMaxNodeSize 

func (opts *Options) WithMaxNodeSize(maxNodeSize int) *Options

func (*Options) WithMaxValueSize added in v1.2.4 

func (opts *Options) WithMaxValueSize(maxValueSize int) *Options

func (*Options) WithNodesLogMaxOpenedFiles added in v1.2.3 

func (opts *Options) WithNodesLogMaxOpenedFiles(nodesLogMaxOpenedFiles int) *Options

func (*Options) WithReadOnly 

func (opts *Options) WithReadOnly(readOnly bool) *Options

func (*Options) WithRenewSnapRootAfter 

func (opts *Options) WithRenewSnapRootAfter(renewSnapRootAfter time.Duration) *Options

func (*Options) WithSyncThld added in v1.2.3 

func (opts *Options) WithSyncThld(syncThld int) *Options

type Reader 

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

func (*Reader) Close 

func (r *Reader) Close() error

func (*Reader) Read 

func (r *Reader) Read() (key []byte, value []byte, ts, hc uint64, err error)

func (*Reader) ReadBetween added in v1.3.0 

func (r *Reader) ReadBetween(initialTs, finalTs uint64) (key []byte, ts, hc uint64, err error)

func (*Reader) Reset added in v1.0.0 

func (r *Reader) Reset() error

type ReaderSpec 

type ReaderSpec struct {
	SeekKey       []byte
	EndKey        []byte
	Prefix        []byte
	InclusiveSeek bool
	InclusiveEnd  bool
	DescOrder     bool
	Offset        uint64
}

type Snapshot 

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

Snapshot implements a snapshot on top of a B-tree data structure. It provides methods for storing and retrieving key-value pairs. The snapshot maintains a consistent view of the underlying data structure. It uses a lock to ensure concurrent access safety. Snapshot represents a consistent view of a B-tree data structure.

func (*Snapshot) Close 

func (s *Snapshot) Close() error

Close closes the snapshot and releases any associated resources. It locks the snapshot for writing, checks if there are any active readers, and marks the snapshot as closed. The method returns an error if there are active readers. Example usage: 

err := snapshot.Close()

func (*Snapshot) Get 

func (s *Snapshot) Get(key []byte) (value []byte, ts uint64, hc uint64, err error)

Get retrieves the value associated with the given key from the snapshot. It locks the snapshot for reading, and delegates the retrieval to the root node. The method returns the value, timestamp, hash count, and an error. Example usage: 

value, timestamp, hashCount, err := snapshot.Get([]byte("key"))

func (*Snapshot) GetWithPrefix added in v1.5.0 

func (s *Snapshot) GetWithPrefix(prefix []byte, neq []byte) (key []byte, value []byte, ts uint64, hc uint64, err error)

GetWithPrefix retrieves the key-value pair with a specific prefix from the snapshot. It locks the snapshot for reading, and delegates the retrieval to the root node. The method returns the key, value, timestamp, hash count, and an error. Example usage: 

key, value, timestamp, hashCount, err := snapshot.GetWithPrefix([]byte("prefix"), []byte("neq"))

func (*Snapshot) History added in v0.9.1 

func (s *Snapshot) History(key []byte, offset uint64, descOrder bool, limit int) (tss []uint64, hCount uint64, err error)

History retrieves the history of a key in the snapshot. It locks the snapshot for reading, and delegates the history retrieval to the root node. The method returns an array of timestamps, the hash count, and an error. Example usage: 

timestamps, hashCount, err := snapshot.History([]byte("key"), 0, true, 10)

func (*Snapshot) NewHistoryReader added in v0.9.1 

func (s *Snapshot) NewHistoryReader(spec *HistoryReaderSpec) (*HistoryReader, error)

NewHistoryReader creates a new history reader for the snapshot. It locks the snapshot for reading and creates a new history reader based on the given specification. The method returns the history reader and an error if the creation fails. Example usage: 

reader, err := snapshot.NewHistoryReader(&HistoryReaderSpec{Key: []byte("key"), Limit: 10})

func (*Snapshot) NewReader added in v0.9.1 

func (s *Snapshot) NewReader(spec ReaderSpec) (r *Reader, err error)

NewReader creates a new reader for the snapshot. It locks the snapshot for writing and creates a new reader based on the given specification. The method returns the reader and an error if the creation fails. Example usage: 

reader, err := snapshot.NewReader(ReaderSpec{Prefix: []byte("prefix"), DescOrder: true})

func (*Snapshot) Set added in v1.2.0 

func (s *Snapshot) Set(key, value []byte) error

Set inserts a key-value pair into the snapshot. It locks the snapshot, performs the insertion, and updates the root node if necessary. The method handles splitting of nodes to maintain the B-tree structure. It returns an error if the insertion fails. Example usage: 

err := snapshot.Set([]byte("key"), []byte("value"))

func (*Snapshot) Ts 

func (s *Snapshot) Ts() uint64

Ts returns the timestamp associated with the root node of the snapshot. It locks the snapshot for reading and returns the timestamp. Example usage: 

timestamp := snapshot.Ts()

func (*Snapshot) WriteTo 

func (s *Snapshot) WriteTo(nw, hw io.Writer, writeOpts *WriteOpts) (rootOffset, minOffset int64, wN, wH int64, err error)

WriteTo writes the snapshot to the specified writers. It locks the snapshot for writing, performs the write operation on the root node, and returns the root offset, minimum offset, number of bytes written to nw and hw, and an error if any.

Parameters: - nw: The writer to write the snapshot's nodes. - hw: The writer to write the snapshot's history. - writeOpts: The options for the write operation.

Returns: - rootOffset: The offset of the root node in the written data. - minOffset: The minimum offset of all written nodes. - wN: The number of bytes written to nw. - wH: The number of bytes written to hw. - err: An error if the write operation fails or the arguments are invalid.

Example usage: 

rootOffset, minOffset, wN, wH, err := snapshot.WriteTo(nw, hw, &WriteOpts{})

type TBtree 

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

TBTree implements a timed-btree

func Open 

func Open(path string, opts *Options) (*TBtree, error)

func OpenWith 

func OpenWith(path string, nLog, hLog, cLog appendable.Appendable, opts *Options) (*TBtree, error)

func (*TBtree) BulkInsert 

func (t *TBtree) BulkInsert(kvts []*KVT) error

BulkInsert inserts multiple entries atomically. It is possible to specify a logical timestamp for each entry. Timestamps with zero will be associated with the current time plus one. The specified timestamp must be greater than the root's current timestamp. Timestamps must be increased by one for each additional entry for a key.

func (*TBtree) Close 

func (t *TBtree) Close() error

func (*TBtree) Compact added in v1.0.5 

func (t *TBtree) Compact() (uint64, error)

func (*TBtree) Flush 

func (t *TBtree) Flush() (wN, wH int64, err error)

func (*TBtree) FlushWith added in v1.2.3 

func (t *TBtree) FlushWith(cleanupPercentage float32, synced bool) (wN, wH int64, err error)

func (*TBtree) Get added in v0.9.0 

func (t *TBtree) Get(key []byte) (value []byte, ts uint64, hc uint64, err error)

func (*TBtree) GetOptions added in v0.9.1 

func (t *TBtree) GetOptions() *Options

func (*TBtree) GetWithPrefix added in v1.5.0 

func (t *TBtree) GetWithPrefix(prefix []byte, neq []byte) (key []byte, value []byte, ts uint64, hc uint64, err error)

func (*TBtree) History added in v0.9.1 

func (t *TBtree) History(key []byte, offset uint64, descOrder bool, limit int) (tss []uint64, hCount uint64, err error)

func (*TBtree) IncreaseTs added in v1.2.3 

func (t *TBtree) IncreaseTs(ts uint64) error

func (*TBtree) Insert 

func (t *TBtree) Insert(key []byte, value []byte) error

func (*TBtree) Snapshot 

func (t *TBtree) Snapshot() (*Snapshot, error)

func (*TBtree) SnapshotCount added in v1.0.5 

func (t *TBtree) SnapshotCount() (uint64, error)

SnapshotCount returns the number of stored snapshots Note: snapshotCount(compact(t)) = 1

func (*TBtree) SnapshotMustIncludeTs added in v1.5.0 

func (t *TBtree) SnapshotMustIncludeTs(ts uint64) (*Snapshot, error)

func (*TBtree) SnapshotMustIncludeTsWithRenewalPeriod added in v1.5.0 

func (t *TBtree) SnapshotMustIncludeTsWithRenewalPeriod(ts uint64, renewalPeriod time.Duration) (*Snapshot, error)

SnapshotMustIncludeTsWithRenewalPeriod returns a new snapshot based on an existent dumped root (snapshot reuse). Current root may be dumped if there are no previous root already stored on disk or if the dumped one was old enough. If ts is 0, any snapshot not older than renewalPeriod may be used. If renewalPeriod is 0, renewal period is not taken into consideration

func (*TBtree) Sync 

func (t *TBtree) Sync() error

func (*TBtree) SyncSnapshot added in v1.5.0 

func (t *TBtree) SyncSnapshot() (*Snapshot, error)

func (*TBtree) Ts 

func (t *TBtree) Ts() uint64

type WriteOpts 

type WriteOpts struct {
	OnlyMutated    bool
	BaseNLogOffset int64
	BaseHLogOffset int64

	MinOffset int64
	// contains filtered or unexported fields
}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.