dbengine

package module
v0.0.0-...-461d236 Latest Latest
Warning

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

 Go to latest Published: Dec 28, 2020 License: MIT Imports: 15 Imported by: 0

README

go-db-engine

Writing a log structured database engine from scratch (for learning purpose only)

Documentation

Index

Constants

View Source 
const (
	OP_SSTABLE_READ_FILE      = "OP_SSTABLE_READ_FILE"
	OP_SSTABLE_LOAD_INDEX     = "OP_SSTABLE_LOAD_INDEX"
	OP_SSTABLE_LOAD_DATABLOCK = "OP_SSTABLE_LOAD_DATABLOCK"
	OP_SSTABLE_CREATE_FILE    = "OP_SSTABLE_CREATE_FILE"
	OP_SSTABLE_WRITE_DATA     = "OP_SSTABLE_WRITE_DATA"
	OP_SSTABLE_WRITE_INDEX    = "OP_SSTABLE_WRITE_INDEX"
)
View Source 
const (
	OP_WAL_CREATE_FILE = "OP_WAL_CREATE_FILE"
	OP_WAL_READ_FILE   = "OP_WAL_READ_FILE"
	OP_WAL_APPEND      = "OP_WAL_APPEND"
	OP_WAL_ROLLBACK    = "OP_WAL_ROLLBACK"
	OP_WAL_DELETE      = "OP_WAL_DELETE"
)

Variables

This section is empty.

Functions

func NewWalFile 

func NewWalFile(walDir string, syncOnWrite bool) (*os.File, error)

NewWalFile - creates a new WAL file with name "wal_<unix timestamp>" under `walDir` if `syncOnWrite` is set to true, each write operation will always be flushed to the storage device.

Note that `syncOnWrite` will introduce a performance penalty (4x worse tested with 100k inserts, 4s vs. 15s). It may not be necessary to set `syncOnWrite` on, because for some battery powered hardware even when the OS crashes or machined died (powered-off) the file system cache can still be flushed to the underlying hardware

func ReadDataWithVarintPrefix 

func ReadDataWithVarintPrefix(r VarintSizePrefixDataReader, buf []byte) ([]byte, error)

ReadDataWithVarintPrefix - read a varint prefixed data block into buf. If buf is too small a new allocated slice will be returned. It is also valid to pass `nil` for buf.

func WriteDataWithVarintSizePrefix 

func WriteDataWithVarintSizePrefix(w io.Writer, raw []byte) (written int, err error)

WriteDataWithVarintSizePrefix - writes data to w with a varint size prefix

Types

type BasicSSTable 

type BasicSSTable struct {
	BlockSize uint // BlockSize - controls roughly how big each block should be (in bytes)
	// contains filtered or unexported fields
}

BasicSSTable - a basic implementation of the `SSTableReader` and `SSTableWriter` interface

func (*BasicSSTable) Dump 

func (s *BasicSSTable) Dump(m MemTable) error

Dump - dumps the memtable into the sstable file

func (*BasicSSTable) File 

func (s *BasicSSTable) File() string

File - returns the file path of the sstable file

func (*BasicSSTable) Get 

func (s *BasicSSTable) Get(key string) ([]byte, error)

Get - returns the value of key specified if exist

func (*BasicSSTable) GetRange 

func (s *BasicSSTable) GetRange(start, end string) ([][]byte, error)

GetRange - returns the values of key range specified TODO: (p2) Implement getRange

func (*BasicSSTable) Index 

func (s *BasicSSTable) Index() SSTableIndex

Index - returns the index of the sstable, if there is one

type BasicSSTableIndex 

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

BasicSSTableIndex - a basic implementation of the `SSTableIndex` interface

func NewBasicSSTableIndex 

func NewBasicSSTableIndex() *BasicSSTableIndex

NewBasicSSTableIndex - creates a new basic sstable index

func (*BasicSSTableIndex) GetOffset 

func (idx *BasicSSTableIndex) GetOffset(key string) (offset, size uint64, exist bool)

GetOffset - get start and end offset (in byte) of data block that contains value for key in the sstable file

func (*BasicSSTableIndex) GetOffsetRange 

func (idx *BasicSSTableIndex) GetOffsetRange(start, end string) (startOffset, endOffset uint64, exist bool)

GetOffsetRange - get start, end offsets (in byte) of data blocks in the sstable file for the key range specified TODO: (p2) implement GetOffSetRange

func (*BasicSSTableIndex) Serialize 

func (idx *BasicSSTableIndex) Serialize() ([]byte, error)

Serialize - turn the index data structure into bytes that can be stored on disk

type BasicWal 

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

BasicWal - implements the `Wal` interface

func NewBasicWal 

func NewBasicWal(walDir string, syncOnWrite bool) (*BasicWal, error)

NewBasicWal - creates a new WAL instance and an underlying WAL file if `syncOnWrite` is set to true, each write operation will always be flushed to the storage device. errors out if file with same name already exists (no WAL file reuse between `BasicWal` instances)

func (*BasicWal) Append 

func (wal *BasicWal) Append(log []byte) error

Append - append an operation log to the WAL file

func (*BasicWal) Delete 

func (wal *BasicWal) Delete() error

Delete - delete the WAL file

func (*BasicWal) File 

func (wal *BasicWal) File() WalFile

File -- returns the underlying WAL file

type BasicWalLog 

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

BasicWalLog - represents a WAL log record

func (*BasicWalLog) Serialize 

func (l *BasicWalLog) Serialize() ([]byte, error)

Serialize - turn the WAL log into bytes

type DBConfig 

type DBConfig func(*DBSetting)

DBConfig - configuration function for db setting

func ConfigDBDir 

func ConfigDBDir(dir string) DBConfig

ConfigDBDir - configures the DB directory location

func ConfigLogLevel 

func ConfigLogLevel(level log.Level) DBConfig

ConfigLogLevel - configures the log level of the database, default to WARN

func ConfigMemtableSizeByte 

func ConfigMemtableSizeByte(size uint) DBConfig

ConfigMemtableSizeByte - configures roughly how much data (in bytes) should be saved into the storage in memroy before it gets flushed into disk. Tuning this paramter could demonstrate different performance depending on the worklaod.

func ConfigSStableDatablockSizeByte 

func ConfigSStableDatablockSizeByte(size uint) DBConfig

ConfigSStableDatablockSizeByte - configures how much data (in bytes) should be stored for each data block in the underlying sstable file. Tuning this paramter could demonstrate different performance depending on the worklaod.

func ConfigWalStrictMode 

func ConfigWalStrictMode(isOn bool) DBConfig

ConfigWalStrictMode - configures if strict mode should be turned on or not for the wal (write-ahead-log). Strict mode means that every write to the wal file will be flushed to the storage device (instead of being buffered in the kernel's page cache, similar to calling `fsync` after every `write` syscall). It's advised that this setting only be turned on for mission critical application where no writes should be lost upon system failure.Enabling this comes with a signficant performance penalty for writing data.

type DBSetting 

type DBSetting struct {
	DBDir                    string
	WalStrictModeOn          bool
	MemtableSizeByte         uint
	SStableDatablockSizeByte uint
	LogLevel                 log.Level
}

DBSetting - sepcifies the various configurations of the database that are customizable

type Database 

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

Database - something that you can write data to and read data from

func NewDatabase 

func NewDatabase(configs ...DBConfig) (*Database, error)

NewDatabase - creates a new database instance

func (*Database) Delete 

func (db *Database) Delete(key string) error

Delete - delete a key from the database TODO: (p1) make the deletion behavior correct across from memtable and sstable

func (*Database) Get 

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

Get - read value for key from the database

func (*Database) Write 

func (db *Database) Write(key string, value []byte) error

Write - write value into the database

type MemTable 

type MemTable interface {
	// Get - retrieves the value saved with key
	Get(key string) []byte

	// GetRange - retrieves all values from specified key range
	GetRange(start, end string) [][]byte

	// Write - write key with value into memtable
	Write(key string, value []byte) error

	// Delete - delete a record with key
	Delete(key string) error

	// Wal - returns the write-ahead-log instance for write ops recording
	Wal() Wal

	// GetAll - returns all records stored in the memtable
	GetAll() []*MemtableRecord

	// SizeBytes - returns the total size of data stored in this memtable
	SizeBytes() uint32
}

MemTable - A memtable handles the in-memory operatoins of the DB on data that has not been persisted into the file system

func NewBasicMemTable 

func NewBasicMemTable(walDir string, walStrictModeOn bool) MemTable

NewBasicMemTable - create a new memtable instance TODO: (p3) make the memtable implementaion thread-safe

type MemtableRecord 

type MemtableRecord struct {
	Key   string
	Value []byte
}

MemtableRecord - represents a single inserted record

type SSTableError 

type SSTableError struct {
	Op  string
	Err error
}

SSTableError - includes error for specifc sstable operation

func (*SSTableError) Error 

func (stErr *SSTableError) Error() string

func (*SSTableError) Unwrap 

func (stErr *SSTableError) Unwrap() error

type SSTableFileMetadata 

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

SSTableFileMetadata - metadata about sstable file

type SSTableIndex 

type SSTableIndex interface {
	// GetOffset - get starting offset (in byte) of the block that contians the value for key
	GetOffset(key string) (offset, size uint64, exist bool)

	// GetOffsetRange - get start, end (non-inclusive) offsets (in byte) of blocks for key range specified
	GetOffsetRange(start, end string) (startOffset, endOffset uint64, exist bool)

	// Serialize - turn the index data structure into bytes that can be stored on disk
	Serialize() ([]byte, error)
}

SSTableIndex - represents an index for a SSTable file

type SSTableReader 

type SSTableReader interface {
	// Index - returns the index of the sstable, if there is one
	Index() SSTableIndex

	// File - returns the file path of the sstable file
	File() string

	// Get - returns the value of key specified
	Get(key string) ([]byte, error)

	// GetRange - returns the values of key range specified
	GetRange(start, end string) ([][]byte, error)
}

SSTableReader - represents a reader that reads data from a sstable file

func NewBasicSSTableReader 

func NewBasicSSTableReader(sstableFile string) (SSTableReader, error)

NewBasicSSTableReader - creates a new `SSTableReader` instance that handles reading data from sstable file

type SSTableWriter 

type SSTableWriter interface {
	// File - returns the file path of the sstable file
	File() string

	// Dump - dumps the memtable into the sstable file
	Dump(MemTable) error
}

SSTableWriter - represents a writer that dump content into a sstable file

func NewBasicSSTableWriter 

func NewBasicSSTableWriter(sstableDir string, blockSize uint) (SSTableWriter, error)

NewBasicSSTableWriter - creates a new `SSTableWriter` instance along with newly created sstable file

type SkipListMemTable 

type SkipListMemTable struct {
	TotalSizeBytes uint32 // total size of key, value data stored
	// contains filtered or unexported fields
}

SkipListMemTable - A memtable implementation using the skip list data structure

func (*SkipListMemTable) Delete 

func (m *SkipListMemTable) Delete(key string) error

Delete - delete a record with key

func (*SkipListMemTable) Get 

func (m *SkipListMemTable) Get(key string) []byte

Get - retrieves the value saved with key

func (*SkipListMemTable) GetAll 

func (m *SkipListMemTable) GetAll() []*MemtableRecord

GetAll - returns all records stored in the memtable

func (*SkipListMemTable) GetRange 

func (m *SkipListMemTable) GetRange(start, end string) [][]byte

GetRange - retrieves all values from specified key range TODO: (p2) implement GetRange

func (*SkipListMemTable) SizeBytes 

func (m *SkipListMemTable) SizeBytes() uint32

SizeBytes - returns the total size of data stored in this memtable

func (*SkipListMemTable) Wal 

func (m *SkipListMemTable) Wal() Wal

Wal - returns the write-ahead-log instance for write ops recording

func (*SkipListMemTable) Write 

func (m *SkipListMemTable) Write(key string, value []byte) error

Write - write key with value into memtable

type VarintSizePrefixDataReader 

type VarintSizePrefixDataReader interface {
	io.Reader
	io.ByteReader
}

VarintSizePrefixDataReader - a reader interface for varint prefixed data

type Wal 

type Wal interface {
	// Append - append an operation log to the WAL file
	Append([]byte) error

	// Delete - delete the WAL file
	Delete() error

	// File -- returns the underlying WAL file
	File() WalFile
}

Wal - represents a write-ahead-log

type WalError 

type WalError struct {
	Op            string
	BeforeLastSeq uint32
	Err           error
}

WalError - wraps errors with WAL operation and basic information before the error happens

func (*WalError) Error 

func (walErr *WalError) Error() string

func (*WalError) Unwrap 

func (walErr *WalError) Unwrap() error

type WalFile 

type WalFile interface {
	io.Writer
	io.Reader

	Truncate(int64) error
	Stat() (os.FileInfo, error)
	Name() string
}

WalFile - file interface that defines basic methods needed for WAL operations the interface can be satisfied by `os.File`

Source Files

View all Source files

Directories

Path Synopsis

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.