tinykvs

package module
v0.3.0 Latest Latest
Warning

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

 Go to latest Published: Jan 16, 2026 License: MIT Imports: 22 Imported by: 0

README

TinyKVS

CI Coverage Status Go Reference Go Report Card

A low-memory, sorted key-value store for Go built on LSM-tree architecture with zstd compression.

Features

  • Sorted storage - Lexicographic key ordering, efficient range scans
  • Ultra-low memory - Runs 1B+ records on t4g.micro (1GB RAM) with swap
  • Configurable memory - Block cache, memtable size, bloom filters all tunable
  • Concurrent access - Concurrent reads and writes, optimized for read-heavy workloads
  • Durability - Write-ahead log with configurable sync modes
  • Compression - zstd compression with configurable levels
  • Bloom filters - Fast negative lookups (can be disabled to save memory)

Installation

go get github.com/freeeve/tinykvs

Quick Start

package main

import (
    "fmt"
    "log"

    "github.com/freeeve/tinykvs"
)

func main() {
    // Open a store
    store, err := tinykvs.Open("/tmp/mydb", tinykvs.DefaultOptions("/tmp/mydb"))
    if err != nil {
        log.Fatal(err)
    }
    defer store.Close()

    // Write values
    store.PutString([]byte("name"), "Alice")
    store.PutInt64([]byte("age"), 30)
    store.PutFloat64([]byte("score"), 95.5)
    store.PutBool([]byte("active"), true)

    // Read values
    name, _ := store.GetString([]byte("name"))
    age, _ := store.GetInt64([]byte("age"))

    fmt.Printf("Name: %s, Age: %d\n", name, age)

    // Flush to disk
    store.Flush()
}

API

Store Operations
// Open or create a store
func Open(path string, opts Options) (*Store, error)

// Close the store
func (s *Store) Close() error

// Flush all data to disk
func (s *Store) Flush() error
Read/Write
// Generic value operations
func (s *Store) Put(key []byte, value Value) error
func (s *Store) Get(key []byte) (Value, error)
func (s *Store) Delete(key []byte) error

// Typed convenience methods
func (s *Store) PutString(key []byte, value string) error
func (s *Store) PutInt64(key []byte, value int64) error
func (s *Store) PutFloat64(key []byte, value float64) error
func (s *Store) PutBool(key []byte, value bool) error
func (s *Store) PutBytes(key []byte, value []byte) error

func (s *Store) GetString(key []byte) (string, error)
func (s *Store) GetInt64(key []byte) (int64, error)
func (s *Store) GetFloat64(key []byte) (float64, error)
func (s *Store) GetBool(key []byte) (bool, error)
func (s *Store) GetBytes(key []byte) ([]byte, error)
Value Types
type Value struct {
    Type    ValueType
    Int64   int64
    Float64 float64
    Bool    bool
    Bytes   []byte
}

// Value constructors
func Int64Value(v int64) Value
func Float64Value(v float64) Value
func BoolValue(v bool) Value
func StringValue(v string) Value
func BytesValue(v []byte) Value
Configuration
type Options struct {
    Dir              string        // Data directory
    MemtableSize     int64         // Max memtable size before flush (default: 4MB)
    BlockCacheSize   int64         // LRU cache size (default: 64MB, 0 to disable)
    BlockSize        int           // Target block size (default: 4KB)
    CompressionLevel int           // zstd level 1-4 (default: 1 = fastest)
    BloomFPRate      float64       // Bloom filter false positive rate (default: 0.01)
    WALSyncMode      WALSyncMode   // WAL sync behavior
    VerifyChecksums  bool          // Verify on read (default: true)
}

// Preset configurations
func DefaultOptions(dir string) Options          // Balanced defaults
func LowMemoryOptions(dir string) Options        // Minimal memory (1MB memtable, no cache, no bloom)
func HighPerformanceOptions(dir string) Options  // Max throughput

Architecture

┌─────────────────────────────────────────────────────────┐
│                        Store                            │
├─────────────────────────────────────────────────────────┤
│  Write Path                    Read Path                │
│  ┌─────────┐                   ┌─────────────────────┐  │
│  │   WAL   │                   │ Memtable (newest)   │  │
│  └────┬────┘                   ├─────────────────────┤  │
│       │                        │ Immutable Memtables │  │
│       v                        ├─────────────────────┤  │
│  ┌─────────┐                   │ L0 SSTables         │  │
│  │Memtable │                   ├─────────────────────┤  │
│  └────┬────┘                   │ L1+ SSTables        │  │
│       │ flush                  └─────────┬───────────┘  │
│       v                                  │              │
│  ┌─────────┐    ┌───────────┐            │              │
│  │ SSTable │◄───│ LRU Cache │◄───────────┘              │
│  └─────────┘    └───────────┘                           │
│       │                                                 │
│       v compaction                                      │
│  ┌─────────────────────────────────────────────────┐    │
│  │ L0 → L1 → L2 → ... → L6 (leveled compaction)    │    │
│  └─────────────────────────────────────────────────┘    │
└─────────────────────────────────────────────────────────┘
Key Design Decisions
Component Choice Rationale
Compression zstd Fast, configurable ratio
I/O Explicit syscalls Control over caching
Index Sparse (per block) Low memory footprint
Compaction Leveled Read-optimized
Concurrency RWMutex Simple, read-optimized
SSTable Format
┌────────────────────────────────────┐
│ Data Block 0 (zstd compressed)     │
│ Data Block 1                       │
│ ...                                │
│ Data Block N                       │
├────────────────────────────────────┤
│ Bloom Filter                       │
├────────────────────────────────────┤
│ Index Block (sparse)               │
├────────────────────────────────────┤
│ Metadata Block                     │
├────────────────────────────────────┤
│ Footer (64 bytes)                  │
└────────────────────────────────────┘

Memory Usage

Component Memory
Block cache Configurable (default 64MB)
Memtable Configurable (default 4MB)
Bloom filters ~1.2MB per 1M keys
Sparse index ~5KB per 1M keys

For minimal memory (billions of records), use LowMemoryOptions():

  • 1MB memtable
  • No block cache
  • No bloom filters
  • Total: ~2MB overhead regardless of dataset size

Performance

Apple M3 Max
Operation Latency Throughput
Random read (64MB cache) 1.3 µs 800K ops/sec
Sequential read 684 ns 1.5M ops/sec
Sequential write 5.7 µs 175K ops/sec
Mixed (80% read) 1.7 µs 600K ops/sec

Block cache impact (random reads, 100K keys):

Cache Latency Hit Rate
0 MB 42 µs 0%
64 MB 1.3 µs 99.9%
AWS t4g.micro (1GB RAM, ARM64)

Ultra-low memory configuration with GOMEMLIMIT=600MiB:

Metric Value
Write throughput ~150K ops/sec
Memory (heap) 30-90 MB
Memory (sys) ~130 MB
WAL size ~3-4 MB (bounded)

This configuration can sustain 1 billion sequential writes while staying within memory limits. The benchmark uses:

  • 1MB memtable
  • No block cache
  • No bloom filters
  • WAL sync disabled (for throughput)

See BENCHMARKS.md for detailed results.

Complexity

  • Writes: O(log n) memtable insert, sequential I/O for WAL
  • Reads: O(log n) per level, bloom filter avoids unnecessary reads
  • Space: ~1.1x raw data size (compression + overhead)

Examples

Persistence and Recovery
// Data persists across restarts
store, _ := tinykvs.Open("/tmp/mydb", tinykvs.DefaultOptions("/tmp/mydb"))
store.PutString([]byte("key"), "value")
store.Flush() // Ensure durability
store.Close()

// Reopen - data is still there
store, _ = tinykvs.Open("/tmp/mydb", tinykvs.DefaultOptions("/tmp/mydb"))
val, _ := store.GetString([]byte("key"))
fmt.Println(val) // "value"
Low Memory Configuration
opts := tinykvs.LowMemoryOptions("/tmp/mydb")
opts.MemtableSize = 512 * 1024 // 512KB
store, _ := tinykvs.Open("/tmp/mydb", opts)
Low Memory (Billions of Records)

For running on memory-constrained systems like t4g.micro (1GB RAM) with billions of records:

// Use LowMemoryOptions: 1MB memtable, no cache, no bloom filters
opts := tinykvs.LowMemoryOptions("/data/mydb")
store, _ := tinykvs.Open("/data/mydb", opts)

// Combined with GOMEMLIMIT for Go runtime memory control:
// GOMEMLIMIT=600MiB ./myapp

This configuration can handle 1B+ records while staying within tight memory limits.

Statistics
stats := store.Stats()
fmt.Printf("Memtable: %d bytes, %d keys\n", stats.MemtableSize, stats.MemtableCount)
fmt.Printf("Cache hit rate: %.1f%%\n", stats.CacheStats.HitRate())
for _, level := range stats.Levels {
    fmt.Printf("L%d: %d tables, %d keys\n", level.Level, level.NumTables, level.NumKeys)
}
Storing Structs

TinyKVS stores primitive types and byte slices natively. For structs, serialize to bytes using your preferred encoding. Here are common patterns:

JSON (simple, human-readable)
import "encoding/json"

type User struct {
    Name  string `json:"name"`
    Email string `json:"email"`
    Age   int    `json:"age"`
}

// Write
user := User{Name: "Alice", Email: "alice@example.com", Age: 30}
data, _ := json.Marshal(user)
store.PutBytes([]byte("user:1"), data)

// Read
data, _ := store.GetBytes([]byte("user:1"))
var user User
json.Unmarshal(data, &user)
Gob (Go-native, efficient for Go-to-Go)
import (
    "bytes"
    "encoding/gob"
)

// Write
var buf bytes.Buffer
gob.NewEncoder(&buf).Encode(user)
store.PutBytes([]byte("user:1"), buf.Bytes())

// Read
data, _ := store.GetBytes([]byte("user:1"))
var user User
gob.NewDecoder(bytes.NewReader(data)).Decode(&user)
MessagePack (compact, fast)
import "github.com/vmihailenco/msgpack/v5"

// Write
data, _ := msgpack.Marshal(user)
store.PutBytes([]byte("user:1"), data)

// Read
data, _ := store.GetBytes([]byte("user:1"))
var user User
msgpack.Unmarshal(data, &user)
Protocol Buffers (schema-defined, cross-language)
import "google.golang.org/protobuf/proto"

// Assuming User is a generated protobuf message
// Write
data, _ := proto.Marshal(user)
store.PutBytes([]byte("user:1"), data)

// Read
data, _ := store.GetBytes([]byte("user:1"))
user := &pb.User{}
proto.Unmarshal(data, user)
Comparison
Format Size Speed Cross-language Schema
JSON Largest Slow Yes No
Gob Medium Fast Go only No
MessagePack Small Fast Yes No
Protobuf Smallest Fastest Yes Required

For most Go applications, MessagePack offers a good balance. Use Protobuf for cross-language systems or when schema evolution matters.

License

MIT

Documentation

Index

Constants

View Source 
const (
	BlockTypeData  uint8 = 1
	BlockTypeIndex uint8 = 2
	BlockTypeBloom uint8 = 3
	BlockTypeMeta  uint8 = 4
)

Block types

View Source 
const (
	SSTableMagic   uint64 = 0x544B5653_00000001 // "TKVS" + version 1
	SSTableVersion uint32 = 1
)

SSTable magic number and version

View Source 
const (
	OpPut    uint8 = 1
	OpDelete uint8 = 2
)

WAL operation types

View Source 
const BlockFooterSize = 12 // checksum(4) + uncompressed_size(4) + compressed_size(4)

BlockFooterSize is the size of the block footer in bytes.

View Source 
const DataPointerSize = 14 // 4 + 4 + 2 + 4

DataPointerSize is the serialized size of a DataPointer.

View Source 
const InlineThreshold = 64

InlineThreshold determines when to store data inline vs pointer. Values smaller than this are stored directly in the record.

View Source 
const MaxImmutableMemtables = 2

MaxImmutableMemtables is the max number of memtables waiting to be flushed. When this limit is reached, writes will block until a flush completes.

View Source 
const SSTableFooterSize = 64

SSTableFooterSize is the fixed size of the footer in bytes.

Variables

View Source 
var (
	ErrKeyNotFound      = errors.New("key not found")
	ErrInvalidValue     = errors.New("invalid value encoding")
	ErrCorruptedData    = errors.New("corrupted data")
	ErrChecksumMismatch = errors.New("checksum mismatch")
)

Common errors

View Source 
var (
	ErrInvalidSSTable = errors.New("invalid sstable format")
)

Errors

View Source 
var (
	ErrStoreClosed = errors.New("store is closed")
)

Errors

Functions

func AppendEncodedValue 

func AppendEncodedValue(dst []byte, v Value) []byte

AppendEncodedValue appends the encoded value to dst and returns the result. This avoids allocation when dst has sufficient capacity.

func CompareKeys 

func CompareKeys(a, b []byte) int

CompareKeys performs lexicographic comparison of two keys. Returns -1 if a < b, 0 if a == b, 1 if a > b. Uses bytes.Compare which is assembly-optimized on most platforms.

func EncodeEntry 

func EncodeEntry(e Entry) []byte

EncodeEntry serializes an entry (key + value + sequence) to bytes.

func EncodeValue 

func EncodeValue(v Value) []byte

EncodeValue serializes a value to bytes.

func SearchBlock 

func SearchBlock(block *Block, key []byte) int

SearchBlock performs binary search within a block for a key. Returns the index of the matching entry, or -1 if not found.

Types

type Block 

type Block struct {
	Type    uint8
	Entries []BlockEntry
}

Block represents a decompressed data block.

func DecodeBlock 

func DecodeBlock(data []byte, verifyChecksum bool) (*Block, error)

DecodeBlock decompresses and parses a block. The returned Block's entries reference the internal decompressed buffer, so the Block should not be modified and is only valid while cached.

type BlockBuilder 

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

BlockBuilder builds blocks from entries.

func NewBlockBuilder 

func NewBlockBuilder(blockSize int) *BlockBuilder

NewBlockBuilder creates a new block builder.

func (*BlockBuilder) Add 

func (b *BlockBuilder) Add(key, value []byte) bool

Add adds an entry to the block. Returns true if the entry was added, false if the block is full.

func (*BlockBuilder) Build 

func (b *BlockBuilder) Build(blockType uint8, compressionLevel int) ([]byte, error)

Build serializes and compresses the block.

func (*BlockBuilder) Count 

func (b *BlockBuilder) Count() int

Count returns the number of entries in the block.

func (*BlockBuilder) Entries 

func (b *BlockBuilder) Entries() []BlockEntry

Entries returns the entries in the block.

func (*BlockBuilder) FirstKey 

func (b *BlockBuilder) FirstKey() []byte

FirstKey returns the first key in the block, or nil if empty.

func (*BlockBuilder) Reset 

func (b *BlockBuilder) Reset()

Reset clears the builder for reuse.

func (*BlockBuilder) Size 

func (b *BlockBuilder) Size() int

Size returns the current uncompressed block size.

type BlockEntry 

type BlockEntry struct {
	Key   []byte
	Value []byte // Encoded value bytes
}

BlockEntry represents a key-value pair within a block.

type BloomFilter 

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

BloomFilter wraps a bloom filter with serialization.

func DeserializeBloomFilter 

func DeserializeBloomFilter(data []byte) (*BloomFilter, error)

DeserializeBloomFilter recreates a bloom filter from bytes.

func NewBloomFilter 

func NewBloomFilter(numKeys uint, fpRate float64) *BloomFilter

NewBloomFilter creates a bloom filter for the expected number of keys.

func (*BloomFilter) Add 

func (bf *BloomFilter) Add(key []byte)

Add adds a key to the bloom filter.

func (*BloomFilter) MayContain 

func (bf *BloomFilter) MayContain(key []byte) bool

MayContain returns true if the key might be in the set. False positives are possible, but false negatives are not.

func (*BloomFilter) Serialize 

func (bf *BloomFilter) Serialize() ([]byte, error)

Serialize encodes the bloom filter for storage.

type CacheKey 

type CacheKey struct {
	FileID      uint32
	BlockOffset uint64
}

CacheKey uniquely identifies a cached block.

type CacheStats 

type CacheStats struct {
	Hits     uint64
	Misses   uint64
	Size     int64
	Capacity int64
	Entries  int
}

CacheStats contains cache statistics.

func (CacheStats) HitRate 

func (s CacheStats) HitRate() float64

HitRate returns the cache hit rate as a percentage.

type CompactionStyle 

type CompactionStyle int

CompactionStyle determines the compaction strategy. 

const (
	// CompactionStyleLeveled uses leveled compaction (read-optimized).
	CompactionStyleLeveled CompactionStyle = iota
	// CompactionStyleSizeTiered uses size-tiered compaction (write-optimized).
	CompactionStyleSizeTiered
)

type DataPointer 

type DataPointer struct {
	FileID      uint32 // SSTable file identifier
	BlockOffset uint32 // Offset to the data block within file
	DataOffset  uint16 // Offset within the decompressed block
	Length      uint32 // Total length of the data
}

DataPointer references variable-length data stored in data blocks. Used for strings/bytes larger than InlineThreshold.

type Entry 

type Entry struct {
	Key      []byte
	Value    Value
	Sequence uint64 // Monotonic sequence number for ordering
}

Entry represents a key-value pair with metadata.

func DecodeEntry 

func DecodeEntry(data []byte) (Entry, int, error)

DecodeEntry deserializes an entry from bytes.

type Index 

type Index struct {
	Entries []IndexEntry
	MinKey  []byte
	MaxKey  []byte
	NumKeys uint64
}

Index provides efficient key lookup within an SSTable.

func DeserializeIndex 

func DeserializeIndex(data []byte) (*Index, error)

DeserializeIndex recreates an index from bytes.

func (*Index) Search 

func (idx *Index) Search(key []byte) int

Search finds the block that may contain the key. Returns the index of the block, or -1 if key is out of range.

func (*Index) Serialize 

func (idx *Index) Serialize() []byte

Serialize encodes the index for storage.

type IndexBuilder 

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

IndexBuilder builds the sparse index during SSTable creation.

func NewIndexBuilder 

func NewIndexBuilder() *IndexBuilder

NewIndexBuilder creates an index builder.

func (*IndexBuilder) Add 

func (ib *IndexBuilder) Add(firstKey []byte, lastKey []byte, offset uint64, size uint32, keysInBlock int)

Add adds a block reference to the index.

func (*IndexBuilder) Build 

func (ib *IndexBuilder) Build() *Index

Build creates the final index.

type IndexEntry 

type IndexEntry struct {
	Key         []byte // First key in the block (separator key)
	BlockOffset uint64 // File offset to the block
	BlockSize   uint32 // Size of the compressed block
}

IndexEntry represents a sparse index entry pointing to a data block.

type LRUCache 

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

LRUCache is a thread-safe LRU block cache.

func NewLRUCache 

func NewLRUCache(capacity int64) *LRUCache

NewLRUCache creates a new LRU cache with the given capacity in bytes. If capacity is 0, the cache is disabled.

func (*LRUCache) Clear 

func (c *LRUCache) Clear()

Clear removes all entries from the cache.

func (*LRUCache) Get 

func (c *LRUCache) Get(key CacheKey) (*Block, bool)

Get retrieves a block from the cache. Returns the block and true if found, nil and false otherwise.

func (*LRUCache) Put 

func (c *LRUCache) Put(key CacheKey, block *Block)

Put adds a block to the cache.

func (*LRUCache) Remove 

func (c *LRUCache) Remove(key CacheKey)

Remove removes a specific key from the cache.

func (*LRUCache) RemoveByFileID 

func (c *LRUCache) RemoveByFileID(fileID uint32)

RemoveByFileID removes all entries for a given file ID. Useful when an SSTable is deleted during compaction.

func (*LRUCache) Stats 

func (c *LRUCache) Stats() CacheStats

Stats returns cache statistics.

type LevelStats 

type LevelStats struct {
	Level     int
	NumTables int
	Size      int64
	NumKeys   uint64
}

LevelStats contains statistics for a single level.

type Memtable 

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

Memtable is an in-memory sorted buffer using a skiplist. It is safe for concurrent reads but requires external synchronization for writes.

func NewMemtable 

func NewMemtable() *Memtable

NewMemtable creates a new empty memtable.

func (*Memtable) Count 

func (m *Memtable) Count() int64

Count returns the number of entries.

func (*Memtable) Get 

func (m *Memtable) Get(key []byte) (Entry, bool)

Get retrieves an entry by key. Returns the entry and true if found, or an empty entry and false if not found.

func (*Memtable) Iterator 

func (m *Memtable) Iterator() *MemtableIterator

Iterator returns an iterator over all entries in sorted order. The caller must call Close() when done.

func (*Memtable) MinSequence 

func (m *Memtable) MinSequence() uint64

MinSequence returns the minimum sequence number in this memtable.

func (*Memtable) Put 

func (m *Memtable) Put(key []byte, value Value, seq uint64)

Put inserts or updates a key-value pair.

func (*Memtable) Size 

func (m *Memtable) Size() int64

Size returns approximate memory usage in bytes.

type MemtableIterator 

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

MemtableIterator iterates over memtable entries in sorted order.

func (*MemtableIterator) Close 

func (it *MemtableIterator) Close()

Close releases resources held by the iterator.

func (*MemtableIterator) Entry 

func (it *MemtableIterator) Entry() Entry

Entry returns the current entry. Only valid after a successful call to Next().

func (*MemtableIterator) Key 

func (it *MemtableIterator) Key() []byte

Key returns the current key.

func (*MemtableIterator) Next 

func (it *MemtableIterator) Next() bool

Next advances to the next entry. Returns true if there is a next entry, false if iteration is complete.

func (*MemtableIterator) Seek 

func (it *MemtableIterator) Seek(target []byte) bool

Seek positions the iterator at the first entry with key >= target.

func (*MemtableIterator) Valid 

func (it *MemtableIterator) Valid() bool

Valid returns true if the iterator is positioned at a valid entry.

func (*MemtableIterator) Value 

func (it *MemtableIterator) Value() Value

Value returns the current value.

type Options 

type Options struct {
	// Dir is the base directory for all data files.
	Dir string

	// MemtableSize is the max memtable size in bytes before flush.
	// Default: 4MB
	MemtableSize int64

	// BlockCacheSize is the LRU cache size in bytes.
	// Set to 0 for minimal memory usage (no caching).
	// Default: 64MB
	BlockCacheSize int64

	// BlockSize is the target block size before compression.
	// Default: 4KB
	BlockSize int

	// CompressionLevel is the zstd compression level.
	// 1 = fastest, 3 = default, higher = better compression.
	// Default: 1 (fastest)
	CompressionLevel int

	// BloomFPRate is the target false positive rate for bloom filters.
	// Default: 0.01 (1%)
	BloomFPRate float64

	// CompactionStyle determines the compaction strategy.
	// Default: CompactionStyleLeveled
	CompactionStyle CompactionStyle

	// L0CompactionTrigger is the number of L0 files that triggers compaction.
	// Default: 4
	L0CompactionTrigger int

	// MaxLevels is the maximum number of LSM levels.
	// Default: 7
	MaxLevels int

	// LevelSizeMultiplier is the size ratio between adjacent levels.
	// Default: 10
	LevelSizeMultiplier int

	// WALSyncMode determines when WAL is synced to disk.
	// Default: WALSyncPerBatch
	WALSyncMode WALSyncMode

	// FlushInterval is the automatic flush interval.
	// Default: 30s
	FlushInterval time.Duration

	// CompactionInterval is how often to check for compaction.
	// Default: 1s
	CompactionInterval time.Duration

	// VerifyChecksums enables checksum verification on reads.
	// Default: true
	VerifyChecksums bool

	// DisableBloomFilter disables bloom filters for minimal memory.
	// Default: false
	DisableBloomFilter bool
}

Options configures the Store behavior.

func DefaultOptions 

func DefaultOptions(dir string) Options

DefaultOptions returns production-ready defaults for the given directory.

func HighPerformanceOptions 

func HighPerformanceOptions(dir string) Options

HighPerformanceOptions returns options optimized for performance.

func LowMemoryOptions 

func LowMemoryOptions(dir string) Options

LowMemoryOptions returns options for memory-constrained environments. Suitable for running billions of records on systems with <1GB RAM.

type Reader 

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

Reader coordinates lookups across memtable and SSTables.

func NewReader 

func NewReader(memtable *Memtable, levels [][]*SSTable, cache *LRUCache, opts Options) *Reader

NewReader creates a new reader.

func (*Reader) AddImmutable 

func (r *Reader) AddImmutable(mt *Memtable)

AddImmutable adds an immutable memtable.

func (*Reader) AddSSTable 

func (r *Reader) AddSSTable(level int, sst *SSTable)

AddSSTable adds an SSTable to a level.

func (*Reader) Get 

func (r *Reader) Get(key []byte) (Value, error)

Get looks up a key, checking memtable first, then SSTables.

func (*Reader) GetLevels 

func (r *Reader) GetLevels() [][]*SSTable

GetLevels returns a copy of the current levels.

func (*Reader) RemoveImmutable 

func (r *Reader) RemoveImmutable(mt *Memtable)

RemoveImmutable removes an immutable memtable after it's been flushed.

func (*Reader) ScanPrefix 

func (r *Reader) ScanPrefix(prefix []byte, fn func(key []byte, value Value) bool) error

ScanPrefix iterates over all keys with the given prefix in sorted order. Keys are deduplicated (newest version wins) and tombstones are skipped. Return false from the callback to stop iteration early.

func (*Reader) SetLevels 

func (r *Reader) SetLevels(levels [][]*SSTable)

SetLevels updates the SSTable levels.

func (*Reader) SetMemtable 

func (r *Reader) SetMemtable(mt *Memtable)

SetMemtable updates the active memtable.

type SSTable 

type SSTable struct {
	ID          uint32
	Path        string
	Level       int
	Footer      SSTableFooter
	Meta        SSTableMeta
	Index       *Index
	BloomFilter *BloomFilter
	// contains filtered or unexported fields
}

SSTable represents an on-disk sorted string table.

func OpenSSTable 

func OpenSSTable(id uint32, path string) (*SSTable, error)

OpenSSTable opens an existing SSTable file.

func (*SSTable) Close 

func (sst *SSTable) Close() error

Close closes the SSTable file.

func (*SSTable) Get 

func (sst *SSTable) Get(key []byte, cache *LRUCache, verifyChecksum bool) (Entry, bool, error)

Get retrieves a value from the SSTable. Returns the entry, whether it was found, and any error.

func (*SSTable) MaxKey 

func (sst *SSTable) MaxKey() []byte

MaxKey returns the maximum key in this SSTable.

func (*SSTable) MinKey 

func (sst *SSTable) MinKey() []byte

MinKey returns the minimum key in this SSTable.

func (*SSTable) Size 

func (sst *SSTable) Size() int64

Size returns the file size in bytes.

type SSTableFooter 

type SSTableFooter struct {
	BloomOffset   uint64 // Offset to bloom filter block
	BloomSize     uint32 // Size of bloom filter block
	IndexOffset   uint64 // Offset to index block
	IndexSize     uint32 // Size of index block
	MetaOffset    uint64 // Offset to metadata block
	MetaSize      uint32 // Size of metadata block
	NumDataBlocks uint32 // Number of data blocks
	NumKeys       uint64 // Total number of keys
	FileSize      uint64 // Total file size for validation
	Magic         uint64 // Magic number for validation
}

SSTableFooter is the fixed-size footer at the end of each SSTable.

type SSTableMeta 

type SSTableMeta struct {
	Level         int
	MinSequence   uint64
	MaxSequence   uint64
	NumTombstones uint64
	CreatedAt     int64
}

SSTableMeta contains metadata about the SSTable.

type SSTableWriter 

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

SSTableWriter builds an SSTable file.

func NewSSTableWriter 

func NewSSTableWriter(id uint32, path string, numKeys uint, opts Options) (*SSTableWriter, error)

NewSSTableWriter creates a new SSTable writer.

func (*SSTableWriter) Abort 

func (w *SSTableWriter) Abort() error

Abort closes and removes the incomplete SSTable file.

func (*SSTableWriter) Add 

func (w *SSTableWriter) Add(entry Entry) error

Add adds an entry to the SSTable.

func (*SSTableWriter) Close 

func (w *SSTableWriter) Close() error

Close closes the writer without finishing.

func (*SSTableWriter) Finish 

func (w *SSTableWriter) Finish(level int) error

Finish completes the SSTable and writes the footer.

func (*SSTableWriter) ID 

func (w *SSTableWriter) ID() uint32

ID returns the SSTable ID.

func (*SSTableWriter) Path 

func (w *SSTableWriter) Path() string

Path returns the SSTable file path.

type Store 

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

Store is the main key-value store.

func Open 

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

Open opens or creates a store at the given path.

func (*Store) Close 

func (s *Store) Close() error

Close closes the store.

func (*Store) Compact 

func (s *Store) Compact() error

Compact forces compaction of all L0 tables to L1. This makes reads faster by converting overlapping L0 tables to disjoint L1 tables.

func (*Store) Delete 

func (s *Store) Delete(key []byte) error

Delete removes a key.

func (*Store) Flush 

func (s *Store) Flush() error

Flush forces all data to disk.

func (*Store) Get 

func (s *Store) Get(key []byte) (Value, error)

Get retrieves a value by key.

func (*Store) GetBool 

func (s *Store) GetBool(key []byte) (bool, error)

GetBool retrieves a bool value by key.

func (*Store) GetBytes 

func (s *Store) GetBytes(key []byte) ([]byte, error)

GetBytes retrieves a byte slice value by key.

func (*Store) GetFloat64 

func (s *Store) GetFloat64(key []byte) (float64, error)

GetFloat64 retrieves a float64 value by key.

func (*Store) GetInt64 

func (s *Store) GetInt64(key []byte) (int64, error)

GetInt64 retrieves an int64 value by key.

func (*Store) GetString 

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

GetString retrieves a string value by key.

func (*Store) Put 

func (s *Store) Put(key []byte, value Value) error

Put stores a key-value pair.

func (*Store) PutBool 

func (s *Store) PutBool(key []byte, value bool) error

PutBool stores a bool value.

func (*Store) PutBytes 

func (s *Store) PutBytes(key []byte, value []byte) error

PutBytes stores a byte slice value.

func (*Store) PutFloat64 

func (s *Store) PutFloat64(key []byte, value float64) error

PutFloat64 stores a float64 value.

func (*Store) PutInt64 

func (s *Store) PutInt64(key []byte, value int64) error

PutInt64 stores an int64 value.

func (*Store) PutString 

func (s *Store) PutString(key []byte, value string) error

PutString stores a string value.

func (*Store) ScanPrefix 

func (s *Store) ScanPrefix(prefix []byte, fn func(key []byte, value Value) bool) error

ScanPrefix iterates over all keys with the given prefix in sorted order. The callback receives the key and value bytes directly (zero-copy). Return false from the callback to stop iteration. Keys are deduplicated (newest version wins) and tombstones are skipped.

func (*Store) Stats 

func (s *Store) Stats() StoreStats

Stats returns store statistics.

type StoreStats 

type StoreStats struct {
	MemtableSize  int64
	MemtableCount int64
	CacheStats    CacheStats
	Levels        []LevelStats
}

StoreStats contains store statistics.

type Value 

type Value struct {
	Type ValueType

	// Inline storage for primitives
	Int64   int64
	Float64 float64
	Bool    bool

	// For strings/bytes - either inline data or pointer to block
	Bytes   []byte       // Used for inline storage (small values)
	Pointer *DataPointer // Used for large values stored in data blocks
}

Value represents a typed value in the store.

func BoolValue 

func BoolValue(v bool) Value

BoolValue creates a Value containing a bool.

func BytesValue 

func BytesValue(v []byte) Value

BytesValue creates a Value containing bytes.

func DecodeValue 

func DecodeValue(data []byte) (Value, int, error)

DecodeValue deserializes a value from bytes. Returns the value and number of bytes consumed.

func DecodeValueZeroCopy 

func DecodeValueZeroCopy(data []byte) (Value, int, error)

DecodeValueZeroCopy deserializes a value without copying byte data. The returned Value's Bytes field points into the input data slice. Caller must ensure data outlives the returned Value. This is faster but the Value is only valid while data is valid.

func Float64Value 

func Float64Value(v float64) Value

Float64Value creates a Value containing a float64.

func Int64Value 

func Int64Value(v int64) Value

Int64Value creates a Value containing an int64.

func StringValue 

func StringValue(v string) Value

StringValue creates a Value containing a string.

func TombstoneValue 

func TombstoneValue() Value

TombstoneValue creates a tombstone Value for deletions.

func (*Value) EncodedSize 

func (v *Value) EncodedSize() int

EncodedSize returns the serialized size of a value.

func (Value) GetBytes 

func (v Value) GetBytes() []byte

GetBytes returns the byte slice for string/bytes values.

func (Value) IsTombstone 

func (v Value) IsTombstone() bool

IsTombstone returns true if this value represents a deletion.

func (Value) String 

func (v Value) String() string

String returns the string representation for string values.

type ValueType 

type ValueType uint8

ValueType represents the type of stored value. 

const (
	ValueTypeInt64 ValueType = iota + 1
	ValueTypeFloat64
	ValueTypeBool
	ValueTypeString
	ValueTypeBytes
	ValueTypeTombstone // Special type for deletions
)

type WAL 

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

WAL implements write-ahead logging for durability.

func OpenWAL 

func OpenWAL(path string, syncMode WALSyncMode) (*WAL, error)

OpenWAL opens or creates a WAL file.

func (*WAL) Append 

func (w *WAL) Append(entry WALEntry) error

Append writes an entry to the WAL.

func (*WAL) Close 

func (w *WAL) Close() error

Close closes the WAL file.

func (*WAL) Recover 

func (w *WAL) Recover() ([]WALEntry, error)

Recover reads all entries from the WAL for crash recovery.

func (*WAL) Sync 

func (w *WAL) Sync() error

Sync forces WAL data to disk.

func (*WAL) Truncate 

func (w *WAL) Truncate() error

Truncate clears the WAL after a successful flush.

func (*WAL) TruncateBefore 

func (w *WAL) TruncateBefore(minSeq uint64) error

TruncateBefore removes WAL entries with sequence < minSeq. This is used for partial WAL cleanup when some memtables are still pending flush.

type WALEntry 

type WALEntry struct {
	Operation uint8
	Key       []byte
	Value     Value // Empty for delete
	Sequence  uint64
}

WALEntry represents a logged operation.

type WALSyncMode 

type WALSyncMode int

WALSyncMode determines when WAL is synced to disk. 

const (
	// WALSyncNone never syncs. Fastest but may lose data on crash.
	WALSyncNone WALSyncMode = iota
	// WALSyncPerBatch syncs after each batch of writes. Good balance.
	WALSyncPerBatch
	// WALSyncPerWrite syncs after each write. Slowest but safest.
	WALSyncPerWrite
)

type Writer 

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

Writer handles all write operations including flushes and compaction.

func NewWriter 

func NewWriter(store *Store, memtable *Memtable, wal *WAL, reader *Reader) *Writer

NewWriter creates a new writer.

func (*Writer) Delete 

func (w *Writer) Delete(key []byte) error

Delete marks a key as deleted.

func (*Writer) Flush 

func (w *Writer) Flush() error

Flush forces a synchronous flush of all data to disk.

func (*Writer) ForceCompact 

func (w *Writer) ForceCompact() error

ForceCompact forces compaction of all L0 tables to L1.

func (*Writer) Memtable 

func (w *Writer) Memtable() *Memtable

Memtable accessor

func (*Writer) Put 

func (w *Writer) Put(key []byte, value Value) error

Put writes a key-value pair.

func (*Writer) SetSequence 

func (w *Writer) SetSequence(seq uint64)

SetSequence sets the sequence number (for recovery).

func (*Writer) Start 

func (w *Writer) Start()

Start starts background goroutines for flush and compaction.

func (*Writer) Stop 

func (w *Writer) Stop()

Stop stops background goroutines.

Source Files

View all Source files

Directories

Path Synopsis
cmd
tinykvs-bench command

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.