gollowdb

package module
v0.0.0-...-2396a12 Latest Latest
Warning

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

 Go to latest Published: Mar 19, 2023 License: BSD-1-Clause Imports: 23 Imported by: 0

README

Gollowdb

Not maintained

GollowDB is an experimental key-value store inspired by rocksdb and leveldb. The main objective of the project is to learn how a LSM databases works.

📣 Public API

  • get(key): Returns a value from the DB
  • set(key, value): Sets a value to the database
  • delete(key): Deletes a key from the database
  • Tail(key): Iterates through all keys >= key
  • Head(key): Iterates through all keys <= key
  • Sub(start, end): Iterates through all start <= keys <= end
  • FirstRow(): Returns First row
  • LastRow(): Returns last row

Documentation

Overview

* Copyright (c) 2023 * John's Page All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * THIS SOFTWARE IS PROVIDED BY [Name of Organization] “AS IS” AND ANY EXPRESS * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO * EVENT SHALL [Name of Organisation] BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY * OF SUCH DAMAGE.

* Copyright (c) 2023 * John's Page All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * THIS SOFTWARE IS PROVIDED BY [Name of Organization] “AS IS” AND ANY EXPRESS * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO * EVENT SHALL [Name of Organisation] BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY * OF SUCH DAMAGE.

* Copyright (c) 2023 * John's Page All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * THIS SOFTWARE IS PROVIDED BY [Name of Organization] “AS IS” AND ANY EXPRESS * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO * EVENT SHALL [Name of Organisation] BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY * OF SUCH DAMAGE.

* Copyright (c) 2023 * John's Page All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * THIS SOFTWARE IS PROVIDED BY [Name of Organization] “AS IS” AND ANY EXPRESS * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO * EVENT SHALL [Name of Organisation] BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY * OF SUCH DAMAGE.

* Copyright (c) 2023 * John's Page All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * THIS SOFTWARE IS PROVIDED BY [Name of Organization] “AS IS” AND ANY EXPRESS * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO * EVENT SHALL [Name of Organisation] BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY * OF SUCH DAMAGE.

* Copyright (c) 2023 * John's Page All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * THIS SOFTWARE IS PROVIDED BY [Name of Organization] “AS IS” AND ANY EXPRESS * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO * EVENT SHALL [Name of Organisation] BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY * OF SUCH DAMAGE.

* Copyright (c) 2023 * John's Page All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * THIS SOFTWARE IS PROVIDED BY [Name of Organization] “AS IS” AND ANY EXPRESS * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO * EVENT SHALL [Name of Organisation] BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY * OF SUCH DAMAGE.

* Copyright (c) 2023 * John's Page All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * THIS SOFTWARE IS PROVIDED BY [Name of Organization] “AS IS” AND ANY EXPRESS * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO * EVENT SHALL [Name of Organisation] BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY * OF SUCH DAMAGE.

* Copyright (c) 2023 * John's Page All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * THIS SOFTWARE IS PROVIDED BY [Name of Organization] “AS IS” AND ANY EXPRESS * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO * EVENT SHALL [Name of Organisation] BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY * OF SUCH DAMAGE.

* Copyright (c) 2023 * John's Page All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * THIS SOFTWARE IS PROVIDED BY [Name of Organization] “AS IS” AND ANY EXPRESS * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO * EVENT SHALL [Name of Organisation] BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY * OF SUCH DAMAGE.

Index

Constants

View Source 
const (
	ADD    = 0
	REMOVE = 1
)
View Source 
const (
	PUT    int8 = 0
	DELETE int8 = 1
)

Variables

This section is empty.

Functions

func DeleteWAL 

func DeleteWAL(path string, id int)

func SortTableRow 

func SortTableRow(rows *[]*TableRow)

sorts a list od TableRow

func WriteSSTable 

func WriteSSTable(sorted []*TableRow, minBlockCount uint64, maxBlockSize uint64, path string, level uint64, id uint64, compression Compression) error

Types

type AbstractTable 

type AbstractTable interface {
	NavigableList[TableRow]

	// Checks if a key is in the tables range
	// minKey <= key <= maxKey
	IsInRange(key any) bool

	// checks if an item is in the table
	// usually uses memtable
	EstimateExistance(key any) bool

	// returns the size of the table
	Size() int
}

All data store manager struct should implement these

type Bloomfilter 

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

A Bloom filter is a space-efficient probabilistic data structure can as "possibly in set" or "definitely not in set" question efficiently

func NewBloomfilter 

func NewBloomfilter(estimatedLength int, hashCount int) *Bloomfilter

creates a new bloomfilter

func (Bloomfilter) Add 

func (x Bloomfilter) Add(value *DataSlice)

adds an item to the filter

func (Bloomfilter) Contains 

func (x Bloomfilter) Contains(value *DataSlice) bool

checks if a DataSlice in the filter

func (Bloomfilter) Size 

func (x Bloomfilter) Size() int

returns the size of the filter

type CompactionStrategy 

type CompactionStrategy interface {
	CalculateScore(lsm []*LSMLevel, level int) float64
	CalculateDelta(lsm []*LSMLevel, level int) int
	PartitionSize(lsm []*LSMLevel, level int) int
}

type Compactor 

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

func NewCompactor 

func NewCompactor(options *DBOption, snapshotsHolds *SortedList[int], lsmUpdateStream *chan bool, sstableManager *SSTableManager, manifest *Manifest, comparator Comparator[*TableRow], wg *sync.WaitGroup, log *log.Logger) *Compactor

func (*Compactor) CalculateScore 

func (i *Compactor) CalculateScore()

func (*Compactor) CreateTaskList 

func (i *Compactor) CreateTaskList() []*LSMLevel

func (*Compactor) RunCompactor 

func (i *Compactor) RunCompactor()

func (*Compactor) RunLevelZeroCompaction 

func (i *Compactor) RunLevelZeroCompaction()

func (*Compactor) SSTableLoader 

func (i *Compactor) SSTableLoader(tables []*SSTableReaderRef) []*TableRow

func (*Compactor) SplitAndSave 

func (i *Compactor) SplitAndSave(sorted []*TableRow, partitionSize int, writeLevel int) []*SSTableReferance

func (*Compactor) Start 

func (i *Compactor) Start()

type Comparator 

type Comparator[V any] func(a V, b V) int

type Compression 

type Compression interface {
	Encode(data []byte) []byte
	Decode(data []byte) ([]byte, error)
}

type CreateIteratorCallback 

type CreateIteratorCallback[V any] func() IteratorBase[V]

type DB 

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

func NewDB 

func NewDB(option *DBOption) *DB

func (*DB) Close 

func (i *DB) Close()

func (*DB) Delete 

func (i *DB) Delete(key any)

func (*DB) FirstRow 

func (i *DB) FirstRow() *TableRow

func (*DB) Get 

func (i *DB) Get(key any) *DataSlice

func (*DB) Head 

func (i *DB) Head(key any) *DBIterator

func (*DB) LastRow 

func (i *DB) LastRow() *TableRow

func (*DB) LockSnapshot 

func (i *DB) LockSnapshot() int

func (*DB) Put 

func (i *DB) Put(key any, value any)

func (*DB) ReleaseSnapshot 

func (i *DB) ReleaseSnapshot(snapshot int)

func (*DB) Sub 

func (i *DB) Sub(key any, endKey any) *DBIterator

func (*DB) Tail 

func (i *DB) Tail(key any) *DBIterator

type DBIterator 

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

func NewDBIterator 

func NewDBIterator(db *DB, startKey *DataSlice, endKey *DataSlice) *DBIterator

func (*DBIterator) Close 

func (i *DBIterator) Close()

func (*DBIterator) GetCurrent 

func (i *DBIterator) GetCurrent() *TableRow

func (*DBIterator) MoveNext 

func (i *DBIterator) MoveNext() bool

type DBOption 

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

func NewDBOption 

func NewDBOption() *DBOption

func (*DBOption) SetComparator 

func (i *DBOption) SetComparator(name string, comparator Comparator[*DataSlice])

func (*DBOption) SetCompression 

func (i *DBOption) SetCompression(compression Compression)

func (*DBOption) SetLSMOptions 

func (i *DBOption) SetLSMOptions(options LSMOptions)

func (*DBOption) SetMaxInmemoryWriteBuffer 

func (i *DBOption) SetMaxInmemoryWriteBuffer(newSize int)

func (*DBOption) SetPath 

func (i *DBOption) SetPath(newPath string)

func (*DBOption) SetShouldCreateIfNotExists 

func (i *DBOption) SetShouldCreateIfNotExists()

func (*DBOption) SetShouldNotCreateIfNotExists 

func (i *DBOption) SetShouldNotCreateIfNotExists()

type DataSlice 

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

Container that holds the data

func NewDataSlice 

func NewDataSlice(value any) *DataSlice

Creates a new DataSlice

func (DataSlice) GetByte 

func (dataSlice DataSlice) GetByte() []byte

returns the binary array of the data inside

func (DataSlice) GetSize 

func (dataSlice DataSlice) GetSize() int

get the size of the object

func (DataSlice) String 

func (dataSlice DataSlice) String() string

to string

type EnhancedIterator 

type EnhancedIterator[V any] struct {
	// contains filtered or unexported fields
}

func (EnhancedIterator[V]) ToList 

func (v EnhancedIterator[V]) ToList() []V

func (EnhancedIterator[V]) Where 

func (v EnhancedIterator[V]) Where(filter FilterCallback[V]) Iterable[V]

type FilterCallback 

type FilterCallback[V any] func(a V) bool

type FilterIterator 

type FilterIterator[V any] struct {
	// contains filtered or unexported fields
}

func (*FilterIterator[V]) GetCurrent 

func (i *FilterIterator[V]) GetCurrent() V

func (*FilterIterator[V]) MoveNext 

func (i *FilterIterator[V]) MoveNext() bool

type FirstNodeWhenCallback 

type FirstNodeWhenCallback[V any] func(a *V, b *V) bool

type IndexRow 

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

type Iterable 

type Iterable[V any] struct {
	EnhancedIterator[V]
	// contains filtered or unexported fields
}

func (Iterable[V]) GetIterator 

func (i Iterable[V]) GetIterator() IteratorBase[V]

type IterableInterface 

type IterableInterface[V any] interface {
	GetIterator() IteratorBase[V]
}

type IteratorBase 

type IteratorBase[V any] interface {
	MoveNext() bool
	GetCurrent() V
}

type LSMLevel 

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

type LSMOptions 

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

func NewLSMOptions 

func NewLSMOptions(maxBaseLevelSize int, levelFactor int, maxLevelZeroFileCount int, sstableFileSize int) LSMOptions

func (*LSMOptions) GetLevelFactor 

func (i *LSMOptions) GetLevelFactor(levelFactor int) int

func (*LSMOptions) GetMaxBaseLevelSize 

func (i *LSMOptions) GetMaxBaseLevelSize(maxBaseLevelSize int) int

func (*LSMOptions) GetMaxLevelZeroFileCount 

func (i *LSMOptions) GetMaxLevelZeroFileCount(maxLevelZeroFileCount int) int

func (*LSMOptions) GetSSTableFileSize 

func (i *LSMOptions) GetSSTableFileSize(sstableFileSize int) int

func (*LSMOptions) SetLevelFactor 

func (i *LSMOptions) SetLevelFactor(levelFactor int)

func (*LSMOptions) SetMaxBaseLevelSize 

func (i *LSMOptions) SetMaxBaseLevelSize(maxBaseLevelSize int)

func (*LSMOptions) SetMaxLevelZeroFileCount 

func (i *LSMOptions) SetMaxLevelZeroFileCount(maxLevelZeroFileCount int)

func (*LSMOptions) SetSSTableFileSize 

func (i *LSMOptions) SetSSTableFileSize(sstableFileSize int)

type LZ4Compression 

type LZ4Compression struct{}

func NewLZ4Compression 

func NewLZ4Compression() *LZ4Compression

func (*LZ4Compression) Decode 

func (c *LZ4Compression) Decode(data []byte) ([]byte, error)

func (*LZ4Compression) Encode 

func (c *LZ4Compression) Encode(data []byte) []byte

type LeveledCompaction 

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

func (*LeveledCompaction) CalculateDelta 

func (i *LeveledCompaction) CalculateDelta(lsm []*LSMLevel, level int) int

func (*LeveledCompaction) CalculateLevelTargetSize 

func (i *LeveledCompaction) CalculateLevelTargetSize(level int) int

func (*LeveledCompaction) CalculateScore 

func (i *LeveledCompaction) CalculateScore(lsm []*LSMLevel, level int) float64

func (*LeveledCompaction) PartitionSize 

func (i *LeveledCompaction) PartitionSize(lsm []*LSMLevel, level int) int

type Manifest 

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

func OpenManifest 

func OpenManifest(path string, id string) *Manifest

func (*Manifest) AddTable 

func (m *Manifest) AddTable(table *SSTableReferance)

func (*Manifest) AddTables 

func (m *Manifest) AddTables(tables []*SSTableReferance)

func (*Manifest) AddWalId 

func (m *Manifest) AddWalId(id int)

func (*Manifest) AddWalIds 

func (m *Manifest) AddWalIds(ids []int)

func (*Manifest) Commit 

func (m *Manifest) Commit()

func (*Manifest) GetAllTables 

func (m *Manifest) GetAllTables() []*SSTableReferance

func (*Manifest) GetAllWALIds 

func (m *Manifest) GetAllWALIds() []int

func (*Manifest) GetDBid 

func (m *Manifest) GetDBid() string

getter for id

func (*Manifest) GetLastSnapshot 

func (m *Manifest) GetLastSnapshot() int

func (*Manifest) GetNextSSTableID 

func (m *Manifest) GetNextSSTableID() int64

func (*Manifest) GetNextWALID 

func (m *Manifest) GetNextWALID() int64

func (*Manifest) GetVersion 

func (m *Manifest) GetVersion() int64

getter for iterationId

func (*Manifest) PackSSTableMetadata 

func (i *Manifest) PackSSTableMetadata(writer io.Writer)

func (*Manifest) RemoveTable 

func (m *Manifest) RemoveTable(table SSTableReferance)

func (*Manifest) RemoveTables 

func (m *Manifest) RemoveTables(tables []*SSTableReferance)

func (*Manifest) RemoveWALId 

func (m *Manifest) RemoveWALId(id int)

func (*Manifest) RemoveWALIds 

func (m *Manifest) RemoveWALIds(ids []int)

func (*Manifest) SetLastSnapshot 

func (m *Manifest) SetLastSnapshot(snapshot int64)

func (*Manifest) String 

func (m *Manifest) String() string

type Memtable 

type Memtable interface {
	AbstractTable

	// Deletes an item from the table
	Delete(key any)

	// updates/adds something to the table
	Put(key any, value any)
}

In memory memtable/buffer 

type NavigableList[V any] interface {
	// Returns as a list
	ToList() []V

	// Returns the first value
	First() *V

	// Returns the last value
	Last() *V

	// Returns a key-value mapping associated with the least key greater
	// than or equal to the given key, or null if there is no such key.
	Ceiling(k V) *V

	// Returns a key-value mapping associated with the least key
	// strictly greater than the given key, or null if there is
	// no such key.
	Higher(k V) *V

	// Returns a key-value mapping associated with the greatest key less
	// than or equal to the given key, or null if there is no such key.
	Floor(k V) *V

	// Returns a key-value mapping associated with the greatest key
	// strictly less than the given key, or null if there is no such
	// key.
	Lower(k V) *V

	// Returns a view of the portion of this map whose keys are
	// strictly less than toKey.
	Tail(fromKey V, inclusive bool) Iterable[V]

	// Returns a view of the portion of this map whose keys are
	// greater than or equal to fromKey.
	Head(toKey V, inclusive bool) Iterable[V]

	// Returns a view of the portion of this map whose keys range
	// from fromKey, inclusive, to toKey, exclusive.
	Sub(fromKey V, toKey V, fromInclusive bool, toInclusive bool) Iterable[V]

	// Returns all the entry matching the value
	Get(value V) Iterable[V]

	// iterates through all the items
	GetIterator() IteratorBase[V]
}

Sorted list/map that can be navigated easily

type NoCompression 

type NoCompression struct{}

func NewNoCompression 

func NewNoCompression() *NoCompression

func (*NoCompression) Decode 

func (c *NoCompression) Decode(data []byte) ([]byte, error)

func (*NoCompression) Encode 

func (c *NoCompression) Encode(data []byte) []byte

type SSTableIterator 

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

Iterator for a sstable

func (*SSTableIterator) GetCurrent 

func (i *SSTableIterator) GetCurrent() *TableRow

func (*SSTableIterator) MoveNext 

func (i *SSTableIterator) MoveNext() bool

type SSTableManager 

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

func NewSSTableManager 

func NewSSTableManager(options *DBOption, snapshotsHolds *SortedList[int], manifest *Manifest, rowComparator Comparator[*TableRow], wg *sync.WaitGroup, log *log.Logger) *SSTableManager

func (*SSTableManager) AddAllSSTables 

func (i *SSTableManager) AddAllSSTables(refs []*SSTableReferance)

func (*SSTableManager) DeleteSSTablesByIds 

func (i *SSTableManager) DeleteSSTablesByIds(ids []*SSTableReferance)

func (*SSTableManager) FilesInRangeInLayer 

func (i *SSTableManager) FilesInRangeInLayer(start *DataSlice, end *DataSlice, ln int) []*SSTableReader

func (*SSTableManager) GetFileCount 

func (i *SSTableManager) GetFileCount() int

func (*SSTableManager) GetFilesFromLayer 

func (i *SSTableManager) GetFilesFromLayer(ln int) []*SSTableReaderRef

func (*SSTableManager) LayerCount 

func (i *SSTableManager) LayerCount() int

func (*SSTableManager) PlanSSTableQueryStrategy 

func (i *SSTableManager) PlanSSTableQueryStrategy(key *DataSlice, ln int, across int) []*SSTableReader

func (*SSTableManager) RemoveAllSSTable 

func (i *SSTableManager) RemoveAllSSTable(refs []*SSTableReferance)

func (*SSTableManager) Updater 

func (i *SSTableManager) Updater(val []SSTableUpdate)

type SSTableMetadata 

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

func (SSTableMetadata) PackSSTableMetadata 

func (i SSTableMetadata) PackSSTableMetadata(writer io.Writer)

type SSTableReader 

type SSTableReader struct {
	EnhancedIterator[*TableRow]
	// contains filtered or unexported fields
}

func NewSSTableReader 

func NewSSTableReader(path string, level uint64, id uint64, compression Compression, comparator Comparator[*DataSlice]) (SSTableReader, error)

func (*SSTableReader) Ceiling 

func (i *SSTableReader) Ceiling(k TableRow) *TableRow

Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.

func (*SSTableReader) Close 

func (i *SSTableReader) Close() error

Close

func (*SSTableReader) EstimateExistance 

func (i *SSTableReader) EstimateExistance(key any) bool

func (*SSTableReader) First 

func (i *SSTableReader) First() **TableRow

Returns the first value

func (*SSTableReader) Floor 

func (i *SSTableReader) Floor(k TableRow) *TableRow

Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.

func (*SSTableReader) Get 

func (i *SSTableReader) Get(value *TableRow) Iterable[*TableRow]

Returns all the entry matching the value

func (*SSTableReader) GetBlock 

func (i *SSTableReader) GetBlock(idx int) (*SortedList[*TableRow], error)

func (*SSTableReader) GetBlocksForRange 

func (i *SSTableReader) GetBlocksForRange(a *DataSlice, b *DataSlice) []int

func (*SSTableReader) GetID 

func (i *SSTableReader) GetID() uint64

func (*SSTableReader) GetIterator 

func (i *SSTableReader) GetIterator() IteratorBase[*TableRow]

iterates through all the items

func (*SSTableReader) GetLevel 

func (i *SSTableReader) GetLevel() uint64

func (*SSTableReader) GetMetadata 

func (i *SSTableReader) GetMetadata() SSTableMetadata

func (*SSTableReader) GetPath 

func (i *SSTableReader) GetPath() string

func (*SSTableReader) Head 

func (i *SSTableReader) Head(fromKey TableRow, inclusive bool) Iterable[*TableRow]

Returns a view of the portion of this map whose keys are strictly less than fromKey. O(log n)

func (*SSTableReader) Higher 

func (i *SSTableReader) Higher(k TableRow) *TableRow

Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.

func (*SSTableReader) IsInRange 

func (i *SSTableReader) IsInRange(key any) bool

Checks if a key is in the tables range minKey <= key <= maxKey

func (*SSTableReader) Last 

func (i *SSTableReader) Last() **TableRow

Returns the last value

func (*SSTableReader) Lower 

func (i *SSTableReader) Lower(k TableRow) *TableRow

Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.

func (*SSTableReader) Print 

func (i *SSTableReader) Print()

print the index and all of the blocks

func (*SSTableReader) Size 

func (i *SSTableReader) Size() int

EstimateExistance(key any)

func (*SSTableReader) Sub 

func (i *SSTableReader) Sub(fromKey *TableRow, toKey *TableRow, fromInclusive bool, toInclusive bool) Iterable[*TableRow]

Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.

func (*SSTableReader) Tail 

func (i *SSTableReader) Tail(fromKey TableRow, inclusive bool) Iterable[*TableRow]

Returns a view of the portion of this map whose keys are greater than or equal to fromKey.

type SSTableReaderRef 

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

type SSTableReferance 

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

func NewSSTableRef 

func NewSSTableRef(level int, id int) *SSTableReferance

func (*SSTableReferance) GetId 

func (i *SSTableReferance) GetId() int

func (*SSTableReferance) GetLevel 

func (i *SSTableReferance) GetLevel() int

type SSTableUpdate 

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

type SkipListIterator 

type SkipListIterator[V any] struct {
	// contains filtered or unexported fields
}

func (*SkipListIterator[V]) GetCurrent 

func (i *SkipListIterator[V]) GetCurrent() V

func (*SkipListIterator[V]) MoveNext 

func (i *SkipListIterator[V]) MoveNext() bool

type SkipListMemtable 

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

func NewSkipListMemtable 

func NewSkipListMemtable(path string, id int64, comparator Comparator[*DataSlice]) *SkipListMemtable

func (*SkipListMemtable) Delete 

func (i *SkipListMemtable) Delete(key any)

func (*SkipListMemtable) EstimateExistance 

func (i *SkipListMemtable) EstimateExistance(key any) bool

func (*SkipListMemtable) Get 

func (i *SkipListMemtable) Get(key any) Iterable[*TableRow]

func (*SkipListMemtable) GetSize 

func (i *SkipListMemtable) GetSize() int

func (*SkipListMemtable) IsInRange 

func (i *SkipListMemtable) IsInRange(key any) bool

func (*SkipListMemtable) Put 

func (i *SkipListMemtable) Put(key any, value any)

func (*SkipListMemtable) ToList 

func (i *SkipListMemtable) ToList() []*TableRow

type Skiplist 

type Skiplist[V any] struct {
	EnhancedIterator[V]
	// contains filtered or unexported fields
}

func CreateSkiplist 

func CreateSkiplist[V any](estimateSize int, comparator Comparator[V]) *Skiplist[V]

func (*Skiplist[V]) Add 

func (v *Skiplist[V]) Add(value V)

Adds item to a skiplist. O(log n)

func (*Skiplist[V]) Ceiling 

func (v *Skiplist[V]) Ceiling(k V) *V

Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key. O(log n)

func (*Skiplist[V]) First 

func (v *Skiplist[V]) First() *V

Returns the first value. O(1)

func (*Skiplist[V]) FirstNodeWhen 

func (v *Skiplist[V]) FirstNodeWhen(key *V, callback FirstNodeWhenCallback[V]) *skiplistNode[V]

func (*Skiplist[V]) Floor 

func (v *Skiplist[V]) Floor(k V) *V

Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key. O(log n)

func (*Skiplist[V]) Get 

func (v *Skiplist[V]) Get(value V) Iterable[V]

Returns all the entry matching the value. O(log n)

func (*Skiplist[V]) GetIterator 

func (v *Skiplist[V]) GetIterator() IteratorBase[V]

func (*Skiplist[V]) Head 

func (v *Skiplist[V]) Head(toKey V, inclusive bool) Iterable[V]

Returns a view of the portion of this map whose keys are greater than or equal to fromKey. O(log n)

func (*Skiplist[V]) Higher 

func (v *Skiplist[V]) Higher(k V) *V

Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key. O(log n)

func (*Skiplist[V]) Last 

func (v *Skiplist[V]) Last() *V

Returns the first value. O(log n)

func (*Skiplist[V]) Lower 

func (v *Skiplist[V]) Lower(k V) *V

Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key. O(log n)

func (*Skiplist[V]) Sub 

func (v *Skiplist[V]) Sub(fromKey V, toKey V, fromInclusive bool, toInclusive bool) Iterable[V]

Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive. O(log n)

func (*Skiplist[V]) Tail 

func (v *Skiplist[V]) Tail(fromKey V, inclusive bool) Iterable[V]

Returns a view of the portion of this map whose keys are strictly less than toKey. O(log n)

type SnappyCompression 

type SnappyCompression struct{}

func NewSnappyCompression 

func NewSnappyCompression() *SnappyCompression

func (*SnappyCompression) Decode 

func (c *SnappyCompression) Decode(data []byte) ([]byte, error)

func (*SnappyCompression) Encode 

func (c *SnappyCompression) Encode(data []byte) []byte

type SortedList 

type SortedList[V any] struct {
	EnhancedIterator[V]
	// contains filtered or unexported fields
}

func NewSortedList 

func NewSortedList[V any](list []V, comparator Comparator[V]) *SortedList[V]

func (*SortedList[V]) Add 

func (v *SortedList[V]) Add(value V)

Add adds a value to the list efficiently

func (*SortedList[V]) AddAll 

func (v *SortedList[V]) AddAll(values []V)

Add all values to the list efficiently

func (*SortedList[V]) Ceiling 

func (v *SortedList[V]) Ceiling(k V) *V

Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.

func (*SortedList[V]) Clear 

func (v *SortedList[V]) Clear()

func (*SortedList[V]) First 

func (v *SortedList[V]) First() *V

Returns the first value. O(1)

func (*SortedList[V]) Floor 

func (v *SortedList[V]) Floor(k V) *V

Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key. O(log n)

func (*SortedList[V]) Get 

func (v *SortedList[V]) Get(value V) Iterable[V]

Returns all the entry matching the value. O(log n)

func (*SortedList[V]) GetIterator 

func (v *SortedList[V]) GetIterator() IteratorBase[V]

returns sortedlist iterator

func (*SortedList[V]) GetSize 

func (v *SortedList[V]) GetSize() int

func (*SortedList[V]) Head 

func (v *SortedList[V]) Head(toKey V, inclusive bool) Iterable[V]

Returns a view of the portion of this map whose keys are greater than or equal to toKey.

func (*SortedList[V]) Higher 

func (v *SortedList[V]) Higher(k V) *V

Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.

func (*SortedList[V]) Last 

func (v *SortedList[V]) Last() *V

Returns the last value. O(1)

func (*SortedList[V]) Lower 

func (v *SortedList[V]) Lower(k V) *V

Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.

func (*SortedList[V]) Merge 

func (v *SortedList[V]) Merge(other []V)

func (*SortedList[V]) Remove 

func (v *SortedList[V]) Remove(value V) *V

Remove removes a value from the list efficiently

func (*SortedList[V]) RemoveWhere 

func (v *SortedList[V]) RemoveWhere(predicate func(V) bool) []V

Remove removes a value from the list efficiently

func (*SortedList[V]) Sub 

func (v *SortedList[V]) Sub(fromKey V, toKey V, fromInclusive bool, toInclusive bool) Iterable[V]

Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.

func (*SortedList[V]) Tail 

func (v *SortedList[V]) Tail(fromKey V, inclusive bool) Iterable[V]

Returns a view of the portion of this map whose keys are strictly less than toKey.

func (*SortedList[V]) ToList 

func (v *SortedList[V]) ToList() []V

type SortedListIterator 

type SortedListIterator[V any] struct {
	// contains filtered or unexported fields
}

Iterator for a sortedlist

func (*SortedListIterator[V]) GetCurrent 

func (i *SortedListIterator[V]) GetCurrent() V

get current for SortedListIterator

func (*SortedListIterator[V]) MoveNext 

func (i *SortedListIterator[V]) MoveNext() bool

move next for SortedListIterator

type StopCallback 

type StopCallback[V any] func(a *V) bool

type TableRow 

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

This represents a row in the table

func Merge 

func Merge(a []*TableRow, b []*TableRow, comparator Comparator[*TableRow]) []*TableRow

func MergeRows 

func MergeRows(rows []*TableRow, snapshot *SortedList[int]) []*TableRow

func NewTableRow 

func NewTableRow(key *DataSlice, value *DataSlice, timestamp uint64, snapshotId uint64, rowType int8) *TableRow

creates a new TableRow struct

func NewTableRowFrom 

func NewTableRowFrom(reader io.Reader) (*TableRow, error)

parses a row from an io writer

func NewTableRowFromKey 

func NewTableRowFromKey(key any) *TableRow

func (*TableRow) GetKey 

func (i *TableRow) GetKey() *DataSlice

getter for key

func (*TableRow) GetRowType 

func (i *TableRow) GetRowType() int

func (*TableRow) GetSnapshotId 

func (i *TableRow) GetSnapshotId() uint64

getter for snapshotId

func (*TableRow) GetTimestamp 

func (i *TableRow) GetTimestamp() uint64

getter for timestamp

func (*TableRow) GetValue 

func (i *TableRow) GetValue() *DataSlice

getter for value

func (*TableRow) PackRow 

func (i *TableRow) PackRow(writer io.Writer)

stores the row to [writer]

func (*TableRow) String 

func (i *TableRow) String() string

type TableRowSortBy 

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

struct that helps in sorting TableRows implements Sort Interface

func NewTableRowSortBy 

func NewTableRowSortBy(list []*TableRow, comparator Comparator[*DataSlice]) TableRowSortBy

func (*TableRowSortBy) Len 

func (a *TableRowSortBy) Len() int

func (*TableRowSortBy) Less 

func (a *TableRowSortBy) Less(i, j int) bool

func (*TableRowSortBy) Swap 

func (a *TableRowSortBy) Swap(i, j int)

type WALReader 

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

Reads a Write Ahead Log from disk

func NewWALReader 

func NewWALReader(path string, id int) WALReader

Creates a WALReader struct to read

func (WALReader) ReadAllRows 

func (v WALReader) ReadAllRows() []*TableRow

read all entries in the log as an array of TableRow

type WALReference 

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

func (*WALReference) GetId 

func (i *WALReference) GetId() int

type WALWriter 

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

Write Ahead Log is used to store the mutations to memtable

func NewWALWriter 

func NewWALWriter(path string, id int64) WALWriter

Creates a new log at path with [id]

func (WALWriter) AddTableRow 

func (v WALWriter) AddTableRow(row *TableRow)

Add an entry to the log

func (WALWriter) Close 

func (v WALWriter) Close()

closes the log

type ZlibCompression 

type ZlibCompression struct{}

func NewZlibCompression 

func NewZlibCompression() *ZlibCompression

func (*ZlibCompression) Decode 

func (c *ZlibCompression) Decode(data []byte) ([]byte, error)

func (*ZlibCompression) Encode 

func (c *ZlibCompression) Encode(data []byte) []byte

type ZstdCompression 

type ZstdCompression struct{}

func NewZstdCompression 

func NewZstdCompression() *ZstdCompression

func (*ZstdCompression) Decode 

func (c *ZstdCompression) Decode(data []byte) ([]byte, error)

func (*ZstdCompression) Encode 

func (c *ZstdCompression) Encode(data []byte) []byte

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.