README
¶
Engine package
LSM-style key-value store: write-ahead log (WAL), in-memory sorted MemTable, and immutable SSTables. Focuses on durability guarantees and checksummed records.
Import path: github.com/Milkhaa/SimpleDB/engine
Package layout
| File | Purpose |
|---|---|
store.go |
KV type, Open/Close, Get/Set/Del, compaction |
merge.go |
SortedKV abstraction and merge iterator over levels |
sorted_array.go |
In-memory sorted table (MemTable) |
sorted_file.go |
On-disk SSTable format and iteration |
wal.go |
Write-ahead log (append-only, fsynced) |
record.go |
WAL record binary format |
metadata.go |
Persisted metadata (SSTable list, version) |
config.go |
Config and defaults |
errors.go |
Package errors |
Usage
import "github.com/Milkhaa/SimpleDB/engine"
kv, err := engine.Open(engine.Config{Path: "./data"})
if err != nil {
log.Fatal(err)
}
defer kv.Close()
kv.Set([]byte("foo"), []byte("bar"))
val, ok, _ := kv.Get([]byte("foo"))
kv.Del([]byte("foo"))
Config.Path is a directory; the WAL and SSTable files live under it.
Configuration
- Config.Path — Database directory. Default:
.simpledb. - Config.LogThreshold — Max keys in the MemTable before flushing to an SSTable. Default:
1000. - Config.GrowthFactor — Merge adjacent SSTables when
cur*GrowthFactor >= cur+next. Default:2.0.
For design background (serialization, durability, fsync, atomicity, LSM), see docs/database_internals.md.
Documentation
¶
Overview ¶
Package engine provides a durable key-value store with an LSM-style layout.
Use Open to create or open a store, then call Get, Set, and Del. All data is persisted: writes go to a write-ahead log (WAL) and an in-memory sorted table; reads merge the in-memory table with immutable on-disk SSTables. Compaction flushes the in-memory table to new SSTables and merges existing SSTables when configured.
For design details (durability, formats, compaction), see the engine README.
Package layout (for readers):
- store.go — KV type, Open/Close, Get/Set/Del, compaction
- merge.go — SortedKV abstraction and merge iterator over levels
- sorted_array.go — In-memory sorted table (MemTable)
- sorted_file.go — On-disk SSTable format and iteration
- wal.go — Write-ahead log (append-only, fsynced)
- record.go — WAL record binary format
- metadata.go — Persisted metadata (SSTable list, version)
- config.go — Config and defaults
- errors.go — Package errors
Index ¶
- Constants
- Variables
- type Config
- type KV
- func (kv *KV) Close() error
- func (kv *KV) Compact() error
- func (kv *KV) Del(key []byte) (updated bool, err error)
- func (kv *KV) Get(key []byte) (value []byte, ok bool, err error)
- func (kv *KV) NewTX() *KVTX
- func (kv *KV) Seek(key []byte) (SortedKVIter, error)
- func (kv *KV) Set(key, value []byte) (updated bool, err error)
- type KVMetaData
- type KVMetaStore
- type KVTX
- type MergedSortedKV
- type MergedSortedKVIter
- type NoDeletedIter
- type NoDeletedSortedKV
- type RecordOp
- type SortedArray
- func (a *SortedArray) Clear()
- func (a *SortedArray) Del(key []byte) (deleted bool, err error)
- func (a *SortedArray) EstimatedSize() int
- func (a *SortedArray) Iter() (SortedKVIter, error)
- func (a *SortedArray) Key(i int) []byte
- func (a *SortedArray) Seek(key []byte) (SortedKVIter, error)
- func (a *SortedArray) Set(key, val []byte) (updated bool, err error)
- func (a *SortedArray) Size() int
- type SortedFile
- type SortedKV
- type SortedKVIter
Constants ¶
const ( DefaultPath = ".simpledb" DefaultLogThreshold = 1000 DefaultGrowthFactor = 2.0 )
Default configuration values when fields are zero or invalid.
Variables ¶
var ErrBadChecksum = errors.New("engine: bad checksum")
ErrBadChecksum indicates a WAL record failed checksum validation (e.g. incomplete or corrupted write).
var ErrCorruptSSTable = errors.New("engine: corrupt sstable")
ErrCorruptSSTable indicates an SSTable file has invalid header or entry (e.g. count or length out of bounds).
var ErrKeyOrValueTooLarge = errors.New("engine: key or value length exceeds maximum")
ErrKeyOrValueTooLarge indicates a key or value length exceeds the maximum storable in the SSTable header (uint32).
var ErrTxClosed = errors.New("engine: transaction is closed")
ErrTxClosed indicates a transaction was aborted/committed and is no longer usable.
Functions ¶
This section is empty.
Types ¶
type Config ¶
type Config struct {
// Path is the database directory (WAL and SSTables live under it).
// If empty, DefaultPath is used.
Path string
// LogThreshold is the max keys in the MemTable before flushing to an SSTable.
// If <= 0, DefaultLogThreshold is used.
LogThreshold int
// GrowthFactor controls when adjacent SSTables are merged: merge main[i] and main[i+1]
// when cur*GrowthFactor >= cur+next. If < 2.0, DefaultGrowthFactor is used.
GrowthFactor float32
}
Config holds options for opening the key-value store.
type KV ¶
type KV struct {
// contains filtered or unexported fields
}
KV is a durable key-value store using an LSM-style layout.
Data flow: Writes go to the WAL (for durability) and the in-memory sorted table (mem). Reads merge mem with on-disk SSTables (sstables) via the SortedKV abstraction; newest level wins for duplicate keys. Compaction flushes mem to a new SSTable when it exceeds logThreshold, and merges adjacent SSTables when growthFactor says so.
func Open ¶
Open opens or creates the database. Path is always a directory; WAL and SSTables live under it. Zero or invalid Config fields are replaced with defaults (see config.go).
func (*KV) Compact ¶
Compact flushes the MemTable if it exceeds logThreshold, then merges adjacent SSTables when shouldMerge(i) is true (cur*growthFactor >= cur+next).
func (*KV) Del ¶
Del removes key. It returns updated=true if the key existed. Implemented as a single-operation transaction; commits only when the key existed.
func (*KV) Get ¶
Get returns the value for key. ok is false if the key is missing or was deleted. Implemented as a single-operation transaction that aborts without committing.
func (*KV) NewTX ¶
NewTX starts a new transaction. All reads and writes use the transaction until Commit or Abort.
type KVMetaData ¶
type KVMetaData struct {
Version uint64
// SSTableFiles are filenames (not full paths) under the DB directory.
// Order is newest-first (same order as the in-memory `KV.sstables` slice).
SSTableFiles []string
}
KVMetaData holds LSM metadata: a version and the list of SSTable filenames.
type KVMetaStore ¶
type KVMetaStore struct {
// contains filtered or unexported fields
}
KVMetaStore persists metadata with double-buffering: two files (meta0, meta1), alternate writes so we always have one valid copy; Get returns the slot with the higher version. Cached after Open and Set so we do not read from disk on Get.
func (*KVMetaStore) Close ¶
func (m *KVMetaStore) Close() error
func (*KVMetaStore) Get ¶
func (m *KVMetaStore) Get() KVMetaData
Get returns the metadata from the slot with the higher version (uses cached data).
func (*KVMetaStore) Open ¶
func (m *KVMetaStore) Open(dir string) error
func (*KVMetaStore) Set ¶
func (m *KVMetaStore) Set(d KVMetaData) error
Set writes to the alternate slot and updates the cache.
type KVTX ¶
type KVTX struct {
// contains filtered or unexported fields
}
KVTX is a transaction over KV. Updates are buffered in updates and applied on Commit. Reads see tx.updates merged with the target's mem and sstables (tx.levels).
func (*KVTX) Commit ¶
Commit applies the transaction to the target KV (write log, update mem) and ends the transaction.
func (*KVTX) Del ¶
Del removes key in the transaction. It returns updated=true if the key existed. The delete is buffered until Commit.
type MergedSortedKV ¶
type MergedSortedKV []SortedKV
MergedSortedKV merges multiple SortedKV levels; for duplicate keys the earliest level wins.
func (MergedSortedKV) EstimatedSize ¶
func (m MergedSortedKV) EstimatedSize() (total int)
func (MergedSortedKV) Iter ¶
func (m MergedSortedKV) Iter() (SortedKVIter, error)
func (MergedSortedKV) Seek ¶
func (m MergedSortedKV) Seek(key []byte) (SortedKVIter, error)
type MergedSortedKVIter ¶
type MergedSortedKVIter struct {
// contains filtered or unexported fields
}
MergedSortedKVIter merges multiple level iterators; which is the index of the current key.
func (*MergedSortedKVIter) Deleted ¶
func (iter *MergedSortedKVIter) Deleted() bool
func (*MergedSortedKVIter) Key ¶
func (iter *MergedSortedKVIter) Key() []byte
func (*MergedSortedKVIter) Next ¶
func (iter *MergedSortedKVIter) Next() error
func (*MergedSortedKVIter) Prev ¶
func (iter *MergedSortedKVIter) Prev() error
func (*MergedSortedKVIter) Val ¶
func (iter *MergedSortedKVIter) Val() []byte
func (*MergedSortedKVIter) Valid ¶
func (iter *MergedSortedKVIter) Valid() bool
type NoDeletedIter ¶
type NoDeletedIter struct {
// contains filtered or unexported fields
}
NoDeletedIter wraps a SortedKVIter and skips deleted entries in Next/Prev.
func (*NoDeletedIter) Deleted ¶
func (iter *NoDeletedIter) Deleted() bool
func (*NoDeletedIter) Key ¶
func (iter *NoDeletedIter) Key() []byte
func (*NoDeletedIter) Next ¶
func (iter *NoDeletedIter) Next() error
func (*NoDeletedIter) Prev ¶
func (iter *NoDeletedIter) Prev() error
func (*NoDeletedIter) Val ¶
func (iter *NoDeletedIter) Val() []byte
func (*NoDeletedIter) Valid ¶
func (iter *NoDeletedIter) Valid() bool
type NoDeletedSortedKV ¶
type NoDeletedSortedKV struct {
SortedKV
}
NoDeletedSortedKV wraps a SortedKV and skips deleted entries when iterating. Used when writing the first SSTable or the result of merging the last two levels so that the on-disk file contains no tombstones.
func (NoDeletedSortedKV) Iter ¶
func (n NoDeletedSortedKV) Iter() (SortedKVIter, error)
func (NoDeletedSortedKV) Seek ¶
func (n NoDeletedSortedKV) Seek(key []byte) (SortedKVIter, error)
type SortedArray ¶
type SortedArray struct {
// contains filtered or unexported fields
}
SortedArray is the in-memory sorted table (MemTable): keys, values, and a deleted flag per entry (tombstones). Used for WAL replay and live writes.
func (*SortedArray) Clear ¶
func (a *SortedArray) Clear()
Clear removes all entries. Used after flushing the MemTable to an SSTable.
func (*SortedArray) Del ¶
func (a *SortedArray) Del(key []byte) (deleted bool, err error)
Del marks key as deleted or inserts a tombstone. Returns deleted=true if the key existed and was not already deleted.
func (*SortedArray) EstimatedSize ¶
func (a *SortedArray) EstimatedSize() int
func (*SortedArray) Iter ¶
func (a *SortedArray) Iter() (SortedKVIter, error)
func (*SortedArray) Key ¶
func (a *SortedArray) Key(i int) []byte
func (*SortedArray) Seek ¶
func (a *SortedArray) Seek(key []byte) (SortedKVIter, error)
func (*SortedArray) Set ¶
func (a *SortedArray) Set(key, val []byte) (updated bool, err error)
Set inserts or updates key to val. Returns updated=true if the key was new, was deleted, or value changed.
func (*SortedArray) Size ¶
func (a *SortedArray) Size() int
type SortedFile ¶
type SortedFile struct {
FileName string
// contains filtered or unexported fields
}
SortedFile is an immutable on-disk sorted key-value file (SSTable).
func (*SortedFile) Close ¶
func (f *SortedFile) Close() error
Close closes the file. Safe to call multiple times.
func (*SortedFile) CreateFromSorted ¶
func (f *SortedFile) CreateFromSorted(kv SortedKV) error
CreateFromSorted writes a SortedKV to a new file.
func (*SortedFile) EstimatedSize ¶
func (f *SortedFile) EstimatedSize() int
func (*SortedFile) Iter ¶
func (f *SortedFile) Iter() (SortedKVIter, error)
func (*SortedFile) Open ¶
func (f *SortedFile) Open() error
Open opens the file for reading and loads the index (key count and offsets).
func (*SortedFile) Seek ¶
func (f *SortedFile) Seek(key []byte) (SortedKVIter, error)
type SortedKV ¶
type SortedKV interface {
EstimatedSize() int
Iter() (SortedKVIter, error)
Seek(key []byte) (SortedKVIter, error)
}
SortedKV is the common abstraction for the in-memory table (SortedArray) and on-disk SSTables (SortedFile). Level 0 is the newest; for duplicate keys the earliest level wins. MergedSortedKV merges multiple levels for reads.
Source Files