rindb

package module
v0.17.0 Latest Latest
Warning

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

 Go to latest Published: Oct 23, 2025 License: MIT Imports: 42 Imported by: 2

README

RinDB

Ask DeepWiki

RinDB is a lightweight, embeddable key-value database inspired by Log-Structured Merge (LSM) trees and LevelDB. It is designed for simplicity, performance, and extensibility, making it suitable for applications requiring fast, persistent storage.

Features

  • LSM Storage Engine: Mutable memtable with leveled SSTables, manifest recovery, and deterministic WAL replay.
  • Crash Safety & Validation: Write-ahead logging, manifest rotation, SQLite oracle fuzzing, and a diff harness with walk mode to enforce correctness.
  • Bidirectional Range Iterators: Unified iterator engine that merges memtable and SSTables with forward/backward scans and reverse range support.
  • Snapshots: Point-in-time reads with automatic retention and cleanup to keep historical versions visible while active.
  • Adaptive Table Cache: Sharded SLRU cache with tombstones, corruption quarantine, and runtime statistics.
  • Observability: OpenTelemetry metrics/tracing plus programmatic stats and CLI reporting.
  • Configurable Runtime: Functional options for directories, memory budgets, cache sizing, telemetry exporters, and logging.
  • Memory-Mapped SSTable Reads: Accelerates SSTable data access on Linux, macOS, and Windows using memory-mapped files, with a fallback to standard file I/O.

Installation

RinDB is written in Go and requires Go 1.25.0 or later. To include it in your project:

go get github.com/metailurini/rindb@latest

Clone the repository for development:

git clone https://github.com/metailurini/rindb.git
cd rindb

Usage

Basic Example
package main

import (
    "context"
    "fmt"

    "github.com/metailurini/rindb"
)

func main() {
    // Initialize RinDB with default configuration
    ctx := context.Background()
    db, err := rindb.InitRinDB(ctx)
    if err != nil {
        fmt.Println("Error initializing RinDB:", err)
        return
    }
    defer db.Close()

    // Put a key-value pair
    err = db.Put(ctx, []byte("key1"), []byte("value1"))
    if err != nil {
        fmt.Println("Error putting key:", err)
        return
    }

    // Get a value by key
    value, err := db.Get(ctx, []byte("key1"))
    if err != nil {
        fmt.Println("Error getting key:", err)
        return
    }
    fmt.Println("Value:", string(value)) // Output: Value: value1

    // Remove a key
    err = db.Remove(ctx, []byte("key1"))
    if err != nil {
        fmt.Println("Error removing key:", err)
        return
    }
}
Snapshot-Based Reads
ctx := context.Background()
db, _ := rindb.InitRinDB(ctx)
defer db.Close()

// Write initial values
_ = db.Put(ctx, []byte("k1"), []byte("v1"))
_ = db.Put(ctx, []byte("k2"), []byte("v2"))

snap, _ := db.NewSnapshot(ctx)
defer snap.Release(ctx)

// Mutations after snapshot do not affect reads through it
_ = db.Put(ctx, []byte("k1"), []byte("v3"))
_ = db.Remove(ctx, []byte("k2"))

val, _ := snap.Get(ctx, []byte("k1"))
fmt.Println(string(val)) // Output: v1

it, _ := snap.IRange(ctx, []byte("k1"), []byte("k3"))
for it.HasNext() {
    rec, _ := it.Next()
    fmt.Printf("%s => %s\n", rec.GetKey(), rec.GetValue())
}
for it.HasPrev() {
    rec, _ := it.Prev()
    fmt.Printf("rev %s => %s\n", rec.GetKey(), rec.GetValue())
}
it.Close()

// Descending scans stream the highest key first.
desc, _ := db.IRange(ctx, []byte("k1"), []byte("k3"), rindb.IRangeOrder(rindb.RangeDesc))
for desc.HasNext() {
    rec, _ := desc.Next()
    fmt.Printf("desc %s => %s\n", rec.GetKey(), rec.GetValue())
}
desc.Close()

Range scans walk keys in ascending order by default. Pass rindb.IRangeOrder(rindb.RangeDesc) (or range <start> <end> desc in the CLI) to stream records from the upper bound down to the start key.

Runtime Statistics
s := db.Stats()
fmt.Println("Active snapshots:", s.ActiveSnapshots)
tc := db.TableCacheStats()
fmt.Println("Cache hits:", tc.Hits)

The Stats method reports metrics such as memtable size, sequence number, active snapshot count, per-level SSTable counts, WAL usage, and operation counters. TableCacheStats exposes cache hit/miss ratios and byte usage.

Custom Configuration
ctx := context.Background()
db, err := rindb.InitRinDB(ctx,
    rindb.WithDatabaseDir("./mydb"),
    rindb.WithMaxMemtableSize(1024*1024), // 1MB
    rindb.WithBloomFalsePositiveRate(0.01),
    rindb.WithCacheBytes(64<<20), // 64MB table cache
    rindb.WithCacheShards(8),
    rindb.WithCacheTombstoneTTL(30 * time.Second),
)
if err != nil {
    fmt.Println("Error:", err)
    return
}
defer db.Close()

The sample CLI accepts --cache-bytes and --cache-shards flags to tune the cache.

Logging

RinDB does not emit logs unless a logger is provided. Inject a custom logger and set the desired verbosity:

logger := rindb.NewStdLogger(log.New(os.Stdout, "", log.LstdFlags))
db, _ := rindb.InitRinDB(ctx,
    rindb.WithLogger(logger),
    rindb.WithLogLevel(rindb.LogLevelDebug),
)

Omitting WithLogger keeps the database silent. To log only warnings and errors:

db, _ := rindb.InitRinDB(ctx,
    rindb.WithLogger(logger),
    rindb.WithLogLevel(rindb.LogLevelWarn),
)

OpenTelemetry telemetry options operate independently of the logger.

Table Cache

RinDB keeps recently used SSTables open in a sharded SLRU cache. The cache size and number of shards are controlled via WithCacheBytes and WithCacheShards. Deleted tables leave temporary tombstones, blocking re-admission until the WithCacheTombstoneTTL duration elapses (default 5m). You can inspect runtime metrics to observe hit/miss ratios and byte usage:

stats := db.TableCacheStats()
fmt.Printf("cache hits=%d misses=%d\n", stats.Hits, stats.Misses)

Files that fail verification are quarantined automatically, and the cache evicts least-recently-used entries while respecting internally pinned tables during compaction.

CLI

The interactive CLI under cmd/main.go exposes put, get, remove, range, stats, and exit commands. Optional flags such as --cache-bytes and --cache-shards allow quick cache tuning while experimenting locally:

go build -o rindb cmd/main.go
./rindb --cache-bytes=67108864 --cache-shards=8

Building and Testing

Run formatting, vet (including the custom span-name analyzer), and static analysis:

make check

Run tests:

make test

Run tests with coverage:

make test-coverage

Run smoke integration tests:

make test-integration-smoke

Run full integration tests:

make test-integration-full

Build the CLI:

go build -o rindb cmd/main.go

Contributing

Contributions are welcome!

License

RinDB is licensed under the MIT License.

Documentation

Overview

Package rindb is key-value database

Index

Constants

View Source 
const (
	CurrentFile         = "CURRENT"
	CurrentTmp          = "CURRENT.tmp"
	DefaultManifestFile = "MANIFEST-000001"
)

Variables

View Source 
var (
	ErrKeyNotFound      = errors.New("key not found")
	ErrTombstoneFound   = errors.New("tombstone found")
	ErrMalFormedSSTable = errors.New("malformed sstable")
)
View Source 
var (
	ErrClosed     = errors.New("cache closed")
	ErrObsolete   = errors.New("cache entry obsolete")
	ErrCorruption = errors.New("corruption verified")
)
View Source 
var EOI = errors.New("EOI")

EOI is end of iteration

View Source 
var ErrChecksumMismatch = errors.New("checksum mismatch")
View Source 
var ErrDatabaseClosed = errors.New("database is closed")

ErrDatabaseClosed is returned when an operation is attempted on a closed database.

View Source 
var (
	ErrFileNotOpened = errors.New("file is not opened")
)
View Source 
var (
	// ErrMalformedList is returned when a SkipList has not been initialized
	// properly. It is exported so callers interacting with SkipList can
	// detect improper initialization.
	ErrMalformedList = errors.New("the list was not init-ed properly")
)
View Source 
var ErrSSTableAlreadyBuilt = errors.New("SSTable already built")
View Source 
var ErrUnsupportedType = errors.New("unsupported type: type does not implement CmpType interface")

ErrUnsupportedType is returned when a value does not implement the CmpType interface and therefore cannot be compared with Compare.

Functions

func CalOnDiskSize 

func CalOnDiskSize(r Record) int

func DecodeInternalKey added in v0.5.0 

func DecodeInternalKey(ikey Bytes) (Bytes, uint64, RecordType, error)

func DefaultNewWALFunc added in v0.3.0 

func DefaultNewWALFunc(ctx context.Context, cfg Config) (*wal, error)

DefaultNewWALFunc provides the default WAL initialization logic.

func EncodeInternalKey added in v0.5.0 

func EncodeInternalKey(key Bytes, seq uint64, typ RecordType) []byte

func InitMemtable 

func InitMemtable(config Config) memtable

InitMemtable initializes a new Memtable with the given configuration.

func InitSSTableManager 

func InitSSTableManager(ctx context.Context, config Config, vs *versionSet, mw manifestWriter) (*ssTableManager, error)

func NewWAL 

func NewWAL(config Config, fs *FileSystem) *wal

func OtelInit added in v0.3.0 

func OtelInit(ctx context.Context, enable bool, endpoint string, insecure bool, samplingRate float64, logger Logger, level LogLevel) (func(context.Context) error, error)

OtelInit initializes OpenTelemetry providers when enabled. The returned shutdown function should be called to flush data. If insecure is true, transport security is disabled for the OTLP exporters.

func ValidateCmpType 

func ValidateCmpType[T Comparable](a T) error

ValidateCmpType verifies that the provided value is a supported Comparable type. It returns ErrUnsupportedType if the value cannot be compared.

Types

type Bitset 

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

Bitset is a compact bit array used by BloomFilter and other components. It is exported for advanced users who need a lightweight bitset implementation.

func NewBitset 

func NewBitset(size uint32) Bitset

NewBitset creates and returns a new bitset with enough capacity to hold size bits.

func (Bitset) Set 

func (b Bitset) Set(index uint32)

Set sets the bit at the specified index to 1.

func (Bitset) Test 

func (b Bitset) Test(index uint32) bool

Test checks whether the bit at the specified index is set or not.

type BloomFilter 

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

BloomFilter represents a probabilistic data structure used for efficient membership testing. It is exposed to allow advanced users to leverage the filter independently from the rest of the database.

func NewBloomFilter 

func NewBloomFilter(options ...BloomFilterOpt) *BloomFilter

NewBloomFilter creates a new BloomFilter with the specified options. n, p, m and k are mandatory params.

func (*BloomFilter) FalsePositive 

func (b *BloomFilter) FalsePositive() float64

FalsePositive calculates the probability of a false positive in the current Bloom filter.

func (*BloomFilter) Insert 

func (b *BloomFilter) Insert(str Bytes)

Insert adds a string to the BloomFilter.

func (*BloomFilter) Lookup 

func (b *BloomFilter) Lookup(str Bytes) bool

Lookup checks if a given string is likely to be in the Bloom filter.

type BloomFilterOpt 

type BloomFilterOpt func(cfg *bloomFilterConfig)

BloomFilterOpt is a functional option type for configuring a Bloom filter.

func SetK 

func SetK(k uint32) BloomFilterOpt

SetK sets the optimal number of hash functions for the Bloom filter.

func SetM 

func SetM(m uint32) BloomFilterOpt

SetM sets the number of bits for the Bloom filter.

func SetN 

func SetN(n uint64) BloomFilterOpt

SetN sets the number of inserted elements for the Bloom filter.

func SetP 

func SetP(p float64) BloomFilterOpt

SetP sets the probability of a false positive for the Bloom filter.

func WithCalculatedK 

func WithCalculatedK() BloomFilterOpt

WithCalculatedK sets the optimal number of hash functions for the Bloom filter. To use this option, m and n must be set first

func WithCalculatedM 

func WithCalculatedM() BloomFilterOpt

WithCalculatedM sets the number of bits for the Bloom filter. To use this option, n and p must be set first

type Bytes 

type Bytes []byte

Bytes is a convenience wrapper around a byte slice that implements the CmpType interface. It is exported so callers can use it with generic collections like SkipList.

func (Bytes) Clone added in v0.5.0 

func (b Bytes) Clone() Bytes

Clone returns a deep copy of the Bytes slice.

func (Bytes) Compare 

func (b Bytes) Compare(other any) int

type CmpType 

type CmpType interface {
	Compare(other any) int
}

CmpType must be implemented by types that provide their own comparison logic through the Compare function.

type Comparable 

type Comparable interface {
	cmp.Ordered | *CmpType | any
}

Comparable is a union constraint that lists all types which can be compared using the generic Compare function. It is exported so applications can define their own comparable types.

type CompareResult 

type CompareResult = int

CompareResult represents the outcome of a comparison between two values. It follows the semantics of cmp.Compare. 

const (
	UnsupportedTypeCode CompareResult = -2

	// CmpLess if x is less than y,
	CmpLess CompareResult = -1
	//	CmpEqual if x equals y,
	CmpEqual CompareResult = 0
	// CmpGreater if x is greater than y.
	CmpGreater CompareResult = 1
)

func Compare 

func Compare[T Comparable](a, b T) CompareResult

Compare returns the ordering between a and b. It supports builtin ordered types and any custom type that implements CmpType. Unsupported types return UnsupportedTypeCode.

type Config 

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

func DefaultConfig 

func DefaultConfig() Config

DefaultConfig returns a Config with default values.

func NewConfig 

func NewConfig(opts ...Option) Config

NewConfig creates a new Config with default values and applies the provided options.

func (Config) Validate added in v0.3.0 

func (c Config) Validate()

Validate checks if the Config has valid values.

type Direction added in v0.16.4 

type Direction int
const (
	DirForward Direction = iota
	DirReverse
)

type FDLimiter added in v0.8.0 

type FDLimiter interface {
	Acquire(ctx context.Context) error
	Release()
}

FDLimiter is a minimal semaphore interface (Acquire before Open, Release after Close).

type FileSystem 

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

func NewFS 

func NewFS(file *os.File) *FileSystem

func OpenExistingFS added in v0.7.0 

func OpenExistingFS(ctx context.Context, filePath string) (*FileSystem, error)

OpenExistingFS opens a file system for an existing file without creating it if missing.

func OpenFS 

func OpenFS(ctx context.Context, filePath string) (*FileSystem, error)

func (*FileSystem) Clean 

func (fs *FileSystem) Clean() error

func (*FileSystem) Close 

func (fs *FileSystem) Close() error

func (*FileSystem) CursorPos 

func (fs *FileSystem) CursorPos() (int64, error)

CursorPos get current cursor position in file system

func (*FileSystem) IsOpened 

func (fs *FileSystem) IsOpened() bool

func (*FileSystem) Open 

func (fs *FileSystem) Open(ctx context.Context) error

func (*FileSystem) OpenExisting added in v0.7.0 

func (fs *FileSystem) OpenExisting(ctx context.Context) error

OpenExisting opens the file system assuming the file already exists. It returns an error if the file does not exist.

func (*FileSystem) Path 

func (fs *FileSystem) Path() string

func (*FileSystem) Read 

func (fs *FileSystem) Read(p []byte) (int, error)

func (*FileSystem) ReadAt added in v0.5.0 

func (fs *FileSystem) ReadAt(p []byte, off int64) (int, error)

func (*FileSystem) Rename added in v0.7.0 

func (fs *FileSystem) Rename(newPath string) error

Rename moves the underlying file to newPath. It closes the file if it's open and updates the internal path.

func (*FileSystem) Seek added in v0.5.0 

func (fs *FileSystem) Seek(offset int64, whence int) (int64, error)

func (*FileSystem) Sync 

func (fs *FileSystem) Sync() error

func (*FileSystem) Write 

func (fs *FileSystem) Write(p []byte) (int, error)

func (*FileSystem) WriteAt added in v0.5.0 

func (fs *FileSystem) WriteAt(p []byte, off int64) (int, error)

type InternalKey added in v0.5.0 

type InternalKey struct {
	UserKey Bytes
	Seq     uint64
	Type    RecordType
}

InternalKey represents a user key combined with sequence number and type.

func (InternalKey) Compare added in v0.5.0 

func (k InternalKey) Compare(other any) int

Compare implements CmpType for InternalKey. Order is by user key ascending, sequence descending, type ascending.

type Iterator 

type Iterator[T any] interface {
	// HasNext reports whether calling Next will succeed.
	HasNext() bool
	// Next advances to the next element and returns it. It returns EOI
	// when the iteration is exhausted.
	Next() (T, error)
	// HasPrev reports whether calling Prev will succeed.
	HasPrev() bool
	// Prev returns the current element and moves the iterator one step
	// backward. It returns EOI when no more elements remain.
	Prev() (T, error)
	// Last positions the iterator at the final element and returns it. The
	// subsequent Prev call should yield the element that precedes the value
	// returned by Last, mirroring how Next leaves the cursor after the
	// current record.
	Last() (T, error)
}

Iterator defines the iteration contract. Implementations may support moving both forward and backward. Iterators start positioned before the first element. Next advances to the next element and returns it. Prev returns the current element and moves the iterator one step backward; as a consequence, a Prev call immediately after a successful Next returns the same element again. It is exported so callers can provide their own iterator implementations that work with Rindb primitives.

type KeyOffset 

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

type LogLevel added in v0.14.0 

type LogLevel int

LogLevel represents the minimum severity threshold for emitted logs. Messages with a lower severity are discarded. 

const (
	LogLevelDebug LogLevel = iota
	LogLevelInfo
	LogLevelWarn
	LogLevelError
)

type Logger added in v0.14.0 

type Logger interface {
	Debug(ctx context.Context, msg string, args ...any)
	Info(ctx context.Context, msg string, args ...any)
	Warn(ctx context.Context, msg string, args ...any)
	Error(ctx context.Context, msg string, args ...any)
}

Logger defines logging methods used by RinDB. Implementations may incorporate structured logging and should be safe for concurrent use. The context may carry tracing information which is appended to messages.

func NewStdLogger added in v0.14.0 

func NewStdLogger(l *log.Logger) Logger

NewStdLogger wraps a standard library logger to satisfy Logger. A nil *log.Logger results in a logger that discards all output.

type MergingIterator added in v0.5.0 

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

MergingIterator merges multiple iterators without deduplication. It yields records ordered by key and sequence number (descending) and supports bidirectional traversal.

func NewMergingIterator added in v0.5.0 

func NewMergingIterator(iterators []Iterator[Record], cleanup func(), order RangeOrder) (*MergingIterator, error)

NewMergingIterator constructs a MergingIterator over provided iterators. The optional cleanup function is called when Close is invoked.

func (*MergingIterator) Close added in v0.5.0 

func (m *MergingIterator) Close() error

Close releases any resources held by the iterator. It is safe to call multiple times.

func (*MergingIterator) HasNext added in v0.5.0 

func (m *MergingIterator) HasNext() bool

HasNext implements Iterator[Record].

func (*MergingIterator) HasPrev added in v0.13.0 

func (m *MergingIterator) HasPrev() bool

HasPrev implements Iterator[Record].

func (*MergingIterator) Last added in v0.15.0 

func (m *MergingIterator) Last() (Record, error)

Last implements Iterator[Record].

func (*MergingIterator) Next added in v0.5.0 

func (m *MergingIterator) Next() (Record, error)

Next implements Iterator[Record].

func (*MergingIterator) Prev added in v0.13.0 

func (m *MergingIterator) Prev() (Record, error)

Prev implements Iterator[Record].

type NewSSTableManagerFunc added in v0.3.0 

type NewSSTableManagerFunc func(ctx context.Context, cfg Config, vs *versionSet, mw manifestWriter) (*ssTableManager, error)

NewSSTableManagerFunc defines the signature for a function that creates an SSTableManager instance.

The versionSet parameter provides metadata about existing SSTables. Callers should pass the same instance used elsewhere in the database so the manager can operate on consistent state.

type NewWALFunc added in v0.3.0 

type NewWALFunc func(ctx context.Context, cfg Config) (*wal, error)

NewWALFunc defines the signature for a function that creates a WAL instance.

type Option 

type Option func(*Config)

Option defines a functional option type for Config.

func WithBaseCompactionSizeMB 

func WithBaseCompactionSizeMB(size int) Option

WithBaseCompactionSizeMB sets the base size in MB for level 1 compaction.

func WithBloomFalsePositiveRate 

func WithBloomFalsePositiveRate(rate float64) Option

WithBloomFalsePositiveRate configures the Bloom filter false positive probability.

func WithCacheBytes added in v0.8.0 

func WithCacheBytes(v int64) Option

WithCacheBytes sets the total byte budget for the table cache.

func WithCacheCorruptTTL added in v0.8.0 

func WithCacheCorruptTTL(d time.Duration) Option

WithCacheCorruptTTL sets the corruption quarantine duration for the table cache.

func WithCacheProbationFraction added in v0.8.0 

func WithCacheProbationFraction(v float64) Option

WithCacheProbationFraction sets the probation segment fraction for the table cache.

func WithCacheShards added in v0.8.0 

func WithCacheShards(v int) Option

WithCacheShards sets the number of shards for the table cache.

func WithCacheTombstoneTTL added in v0.8.0 

func WithCacheTombstoneTTL(d time.Duration) Option

WithCacheTombstoneTTL sets the tombstone duration for the table cache.

func WithConfig added in v0.3.0 

func WithConfig(cfg Config) Option

func WithDatabaseDir 

func WithDatabaseDir(dir string) Option

Option functions

func WithDisableProcessLock added in v0.17.0 

func WithDisableProcessLock() Option

WithDisableProcessLock disables inter-process locking for InitRinDB.

This is primarily intended for advanced testing scenarios that require multiple processes to open the same database directory concurrently.

func WithEnableTelemetry added in v0.3.0 

func WithEnableTelemetry(enable bool) Option

WithEnableTelemetry toggles OpenTelemetry metrics and traces.

func WithExporterEndpoint added in v0.3.0 

func WithExporterEndpoint(endpoint string) Option

WithExporterEndpoint sets the OTLP gRPC endpoint for telemetry export.

func WithExporterInsecure added in v0.3.0 

func WithExporterInsecure(insecure bool) Option

WithExporterInsecure disables TLS for the OTLP exporter.

func WithFDLimiter added in v0.8.0 

func WithFDLimiter(l FDLimiter) Option

WithFDLimiter sets the file descriptor limiter used by the table cache. The provided limiter must not be nil. Omit this option to use the default unlimited implementation.

func WithIOLoadMax added in v0.3.0 

func WithIOLoadMax(max float64) Option

WithIOLoadMax limits the allowed disk utilization fraction for dynamic compaction triggers.

func WithLevel0CompactionThreshold 

func WithLevel0CompactionThreshold(threshold int) Option

WithLevel0CompactionThreshold configures how many level 0 files trigger a compaction.

func WithLevelSizeMultiplier 

func WithLevelSizeMultiplier(multiplier int) Option

WithLevelSizeMultiplier specifies the multiplier for computing higher level sizes.

func WithLogLevel added in v0.14.0 

func WithLogLevel(level LogLevel) Option

WithLogLevel sets the minimum log level emitted through the logger.

func WithLogger added in v0.14.0 

func WithLogger(l Logger) Option

WithLogger sets the logger used by RinDB. A nil logger results in a no-op logger.

func WithManifestSizeThreshold added in v0.7.0 

func WithManifestSizeThreshold(threshold int64) Option

WithManifestSizeThreshold defines the manifest size in bytes that triggers rotation.

func WithMaxMemtableSize 

func WithMaxMemtableSize(size uint) Option

WithMaxMemtableSize sets the maximum number of entries allowed in the memtable before flushing.

func WithNewSSTableManagerFunc added in v0.3.0 

func WithNewSSTableManagerFunc(f NewSSTableManagerFunc) Option

WithNewSSTableManagerFunc overrides the default SSTableManager constructor.

func WithNewWALFunc added in v0.3.0 

func WithNewWALFunc(f NewWALFunc) Option

WithNewWALFunc overrides the default WAL constructor.

func WithRepairMode added in v0.7.0 

func WithRepairMode(v bool) Option

WithRepairMode enables repair mode which scans SSTables from disk on startup.

func WithSSTableMmap added in v0.16.0 

func WithSSTableMmap(enabled bool) Option

WithSSTableMmap toggles mmap-backed SSTable reads.

func WithSkipListDefaultLevel 

func WithSkipListDefaultLevel(level uint) Option

WithSkipListDefaultLevel sets the initial height of the skip list.

func WithSkipListMaxLevel 

func WithSkipListMaxLevel(maxLevel uint) Option

WithSkipListMaxLevel sets the maximum height of the skip list.

func WithSkipListP 

func WithSkipListP(p float64) Option

WithSkipListP sets the probability for skip list level promotion.

func WithTelemetrySamplingRate added in v0.3.0 

func WithTelemetrySamplingRate(rate float64) Option

WithTelemetrySamplingRate configures the trace sampling rate (0.0-1.0).

func WithWriteRateTrigger added in v0.3.0 

func WithWriteRateTrigger(trigger float64) Option

WithWriteRateTrigger sets the write throughput threshold to attempt background compaction.

type PriorityQueue added in v0.3.0 

type PriorityQueue[T any] struct {
	// contains filtered or unexported fields
}

PriorityQueue is a generic min-heap based priority queue. It is exported so advanced users can leverage the implementation when building their own schedulers or data-structure helpers.

func NewPriorityQueue added in v0.3.0 

func NewPriorityQueue[T any](less func(a, b T) bool) *PriorityQueue[T]

NewPriorityQueue creates a new priority queue with the given less function.

func (PriorityQueue[T]) Len added in v0.3.0 

func (pq PriorityQueue[T]) Len() int

Len implements heap.Interface.

func (PriorityQueue[T]) Less added in v0.3.0 

func (pq PriorityQueue[T]) Less(i, j int) bool

Less implements heap.Interface.

func (PriorityQueue[T]) PeekItem added in v0.13.0 

func (pq PriorityQueue[T]) PeekItem() T

PeekItem returns, but does not remove, the highest priority item from the queue.

func (*PriorityQueue[T]) Pop added in v0.3.0 

func (pq *PriorityQueue[T]) Pop() any

Pop implements heap.Interface.

func (*PriorityQueue[T]) PopItem added in v0.3.0 

func (pq *PriorityQueue[T]) PopItem() T

PopItem pops the highest priority item from the queue.

func (*PriorityQueue[T]) Push added in v0.3.0 

func (pq *PriorityQueue[T]) Push(x any)

Push implements heap.Interface.

func (*PriorityQueue[T]) PushItem added in v0.3.0 

func (pq *PriorityQueue[T]) PushItem(item T)

PushItem pushes an item onto the priority queue.

func (PriorityQueue[T]) Swap added in v0.3.0 

func (pq PriorityQueue[T]) Swap(i, j int)

Swap implements heap.Interface.

type RangeIterator added in v0.3.0 

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

RangeIterator is a user-facing iterator that hides tombstones and duplicates. It wraps a MergingIterator which provides all records in key and sequence order.

func NewRangeIterator added in v0.5.0 

func NewRangeIterator(mi *MergingIterator, order RangeOrder) *RangeIterator

NewRangeIterator creates a new RangeIterator from a MergingIterator.

func (*RangeIterator) Close added in v0.3.0 

func (r *RangeIterator) Close() error

Close releases any resources held by the iterator.

func (*RangeIterator) HasNext added in v0.3.0 

func (r *RangeIterator) HasNext() bool

HasNext implements Iterator[Record].

func (*RangeIterator) HasPrev added in v0.13.0 

func (r *RangeIterator) HasPrev() bool

HasPrev implements Iterator[Record].

func (*RangeIterator) Last added in v0.15.0 

func (r *RangeIterator) Last() (Record, error)

Last implements Iterator[Record].

func (*RangeIterator) Next added in v0.3.0 

func (r *RangeIterator) Next() (Record, error)

Next implements Iterator[Record].

func (*RangeIterator) Prev added in v0.13.0 

func (r *RangeIterator) Prev() (Record, error)

Prev implements Iterator[Record].

type RangeOption added in v0.15.0 

type RangeOption func(*rangeConfig)

RangeOption configures IRange behaviour.

func IRangeOrder added in v0.15.0 

func IRangeOrder(order RangeOrder) RangeOption

IRangeOrder sets the initial iteration order for IRange.

func IRangeSnapshot added in v0.15.0 

func IRangeSnapshot(seq uint64) RangeOption

IRangeSnapshot restricts IRange to records visible at or below seq.

type RangeOrder added in v0.15.0 

type RangeOrder int

RangeOrder represents the initial traversal direction for range iterators. 

const (
	// RangeAsc streams keys from smallest to largest.
	RangeAsc RangeOrder = iota
	// RangeDesc streams keys from largest to smallest.
	RangeDesc
)

type Record 

type Record interface {
	GetKey() Bytes
	GetValue() Bytes
	GetSequenceNumber() uint64
	GetType() RecordType
}

type RecordImpl 

type RecordImpl struct {
	Key, Value     Bytes
	SequenceNumber uint64
	Type           RecordType
}

func (RecordImpl) GetKey 

func (r RecordImpl) GetKey() Bytes

GetKey implements Record.

func (RecordImpl) GetSequenceNumber added in v0.3.0 

func (r RecordImpl) GetSequenceNumber() uint64

GetSequenceNumber implements Record.

func (RecordImpl) GetType added in v0.5.0 

func (r RecordImpl) GetType() RecordType

GetType implements Record.

func (RecordImpl) GetValue 

func (r RecordImpl) GetValue() Bytes

GetValue implements Record.

type RecordType added in v0.5.0 

type RecordType uint8
const (
	TypeValue RecordType = iota
	TypeDeletion
	TypeMerge
)

type Rindb 

type Rindb struct {
	WAL            *wal
	Memtable       memtable
	SSTableManager *ssTableManager
	// contains filtered or unexported fields
}

Rindb is the main database structure

func InitRinDB 

func InitRinDB(ctx context.Context, opts ...Option) (_ *Rindb, err error)

InitRinDB initializes a new RinDB instance with provided configuration options. Parameters: 

opts... - Configuration options to customize database behavior

Returns: 

*Rindb - Initialized database instance
error  - Any initialization error encountered

Errors:

  • Filesystem errors during directory creation
  • WAL initialization failures
  • SSTable manager startup failures

Initialization sequence: 1. Create database directory structure 2. Initialize Write-Ahead Log (WAL) 3. Load existing memtable from WAL 4. Initialize SSTable storage manager

func (*Rindb) Close 

func (r *Rindb) Close() error

Close gracefully shuts down the database instance with proper resource cleanup. Sequence: 1. Prevent new operations by marking as closed 2. Wait for background compaction to complete 3. Close WAL and SSTableManager resources 4. Log final shutdown status Safety: Idempotent - multiple calls will return ErrDatabaseClosed

func (*Rindb) Get 

func (r *Rindb) Get(ctx context.Context, key Bytes, seq ...uint64) (Bytes, error)

Get retrieves the value associated with the given key from the database. It first checks the memtable and then the SSTables if the key is not found in the memtable. Parameters: 

key - The key to search for.

Returns: 

Bytes - The value associated with the key, or nil if the key is not found.
error - An error if the database is closed, or if an error occurs during lookup in memtable or SSTables.

func (*Rindb) IRange added in v0.3.0 

func (r *Rindb) IRange(ctx context.Context, start, end Bytes, opts ...RangeOption) (*RangeIterator, error)

IRange returns an iterator over records with keys in [start, end], merged across the memtable and relevant SSTables.

The returned iterator must be closed when no longer needed to release any associated resources.

func (*Rindb) NewSnapshot added in v0.5.0 

func (r *Rindb) NewSnapshot(ctx context.Context) (*Snapshot, error)

NewSnapshot captures the current sequence number and tracks it in the list of active snapshots.

func (*Rindb) Put 

func (r *Rindb) Put(ctx context.Context, key, value Bytes) error

Put inserts or updates a key-value pair in the database. The operation is first written to the Write-Ahead Log (WAL) and then applied to the memtable. If the memtable size exceeds the configured threshold, it triggers a flush to an SSTable and WAL cleaning. Parameters: 

key - The key to insert or update.
value - The value to associate with the key.

Returns: 

error - An error if the database is closed, or if an error occurs during WAL append, memtable update,
        flushing, SSTable registration, or WAL cleaning.

func (*Rindb) Remove 

func (r *Rindb) Remove(ctx context.Context, key Bytes) error

Remove deletes a key-value pair from the database by writing a tombstone record. The deletion is first written to the Write-Ahead Log (WAL) and then applied to the memtable. Parameters: 

key - The key to remove.

Returns: 

error - An error if the database is closed, or if an error occurs during WAL append or memtable update.

func (*Rindb) Stats added in v0.3.0 

func (r *Rindb) Stats() Stats

Stats returns current statistics of the database.

func (*Rindb) TableCacheStats added in v0.8.0 

func (r *Rindb) TableCacheStats() tableCacheStats

type SLNode 

type SLNode[K Comparable, V any] struct {
	Key   K
	Value V
	// contains filtered or unexported fields
}

SLNode represents a single node within a SkipList. It is exported to allow advanced users to inspect or traverse the list directly.

func (*SLNode[K, V]) Next 

func (n *SLNode[K, V]) Next() *SLNode[K, V]

Next returns the node's immediate successor on the lowest level.

type SSTableBuilder added in v0.6.0 

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

func NewSSTableBuilder added in v0.6.0 

func NewSSTableBuilder(ctx context.Context, cfg Config, fs *FileSystem, expected int) (*SSTableBuilder, error)

func (*SSTableBuilder) Add added in v0.6.0 

func (b *SSTableBuilder) Add(rec Record) error

func (*SSTableBuilder) Build added in v0.6.0 

func (b *SSTableBuilder) Build(ctx context.Context) (sst SStable, meta fileMeta, written int64, err error)

func (*SSTableBuilder) Close added in v0.6.0 

func (b *SSTableBuilder) Close(ctx context.Context) error

type SStable 

type SStable struct {
	*FileSystem
	SparseIndex SparseIndex
	Bloom       *BloomFilter
	// contains filtered or unexported fields
}

func NewSSTable 

func NewSSTable(ctx context.Context, config Config, fs *FileSystem) (SStable, error)

func (SStable) GetKeyRange 

func (s SStable) GetKeyRange() (Bytes, Bytes)

GetKeyRange returns the minimum and maximum keys in the SStable.

func (SStable) GetValue 

func (s SStable) GetValue(ctx context.Context, key Bytes, seq ...uint64) (Bytes, error)

func (SStable) IRange added in v0.3.0 

func (s SStable) IRange(start, end Bytes, order RangeOrder, seq ...uint64) (Iterator[Record], error)

IRange returns an iterator over records with keys in [start, end] and sequence numbers less than or equal to seq.

func (SStable) Iterator 

func (s SStable) Iterator() (Iterator[Record], error)

func (SStable) MaxSequenceNumber added in v0.3.0 

func (s SStable) MaxSequenceNumber() (uint64, error)

type SemaphoreFDLimiter added in v0.8.0 

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

SemaphoreFDLimiter limits concurrent file descriptor usage using a semaphore. It implements the FDLimiter interface for table cache operations.

func NewSemaphoreFDLimiter added in v0.8.0 

func NewSemaphoreFDLimiter(n int) *SemaphoreFDLimiter

NewSemaphoreFDLimiter creates a limiter that permits up to n concurrent acquisitions. n must be >0.

func (*SemaphoreFDLimiter) Acquire added in v0.8.0 

func (l *SemaphoreFDLimiter) Acquire(ctx context.Context) error

Acquire blocks until a slot is available or the context is done.

func (*SemaphoreFDLimiter) Release added in v0.8.0 

func (l *SemaphoreFDLimiter) Release()

Release frees a slot previously acquired.

type SkipList 

type SkipList[K Comparable, V any] struct {
	// contains filtered or unexported fields
}

SkipList is a generic ordered map implemented with a probabilistic skip list. It is exported for users who need a stand‑alone sorted in-memory index structure.

func InitSkipList 

func InitSkipList[K Comparable, V any](config Config) (*SkipList[K, V], error)

InitSkipList creates a new empty SkipList using the provided configuration. The key type must satisfy Comparable; otherwise ErrUnsupportedType is returned.

func (*SkipList[K, V]) Clear 

func (list *SkipList[K, V]) Clear()

Clear removes all entries from the list, resetting it to its initial state.

func (*SkipList[K, V]) FindGreaterOrEqual added in v0.5.0 

func (list *SkipList[K, V]) FindGreaterOrEqual(searchKey K) (*SLNode[K, V], error)

FindGreaterOrEqual returns the first node with key >= searchKey.

func (*SkipList[K, V]) Get 

func (list *SkipList[K, V]) Get(searchKey K) (V, error)

Get retrieves the value associated with searchKey. If the key does not exist ErrKeyNotFound is returned.

func (*SkipList[K, V]) Head 

func (list *SkipList[K, V]) Head() *SLNode[K, V]

Head returns the head sentinel node of the list.

func (*SkipList[K, V]) IRange added in v0.3.0 

func (list *SkipList[K, V]) IRange(start, end K, order RangeOrder) Iterator[V]

IRange returns an iterator over records with keys in [start, end].

func (*SkipList[K, V]) Iterator added in v0.3.0 

func (list *SkipList[K, V]) Iterator() Iterator[V]

Iterator returns a bidirectional iterator over the list's values.

func (*SkipList[K, V]) Len 

func (list *SkipList[K, V]) Len() uint

Len returns the number of elements currently stored in the list.

func (*SkipList[K, V]) Put 

func (list *SkipList[K, V]) Put(searchKey K, newValue V)

Put inserts or replaces the value associated with searchKey.

func (*SkipList[K, V]) Remove 

func (list *SkipList[K, V]) Remove(searchKey K) error

Remove deletes the node with the given key. It returns ErrKeyNotFound if the key is absent.

type Snapshot added in v0.5.0 

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

Snapshot represents a point-in-time view of the database.

It captures the sequence number at the time of creation and a reference to the parent database, allowing callers to perform read operations (e.g., Get, IRange) against a consistent view of the data as it existed when the snapshot was taken.

func (*Snapshot) Get added in v0.5.0 

func (s *Snapshot) Get(ctx context.Context, key Bytes) (Bytes, error)

Get returns the value associated with the key as of the snapshot's sequence.

func (*Snapshot) IRange added in v0.5.0 

func (s *Snapshot) IRange(ctx context.Context, start, end Bytes, opts ...RangeOption) (*RangeIterator, error)

IRange returns an iterator over records with keys in [start, end] as of the snapshot's sequence.

func (*Snapshot) Release added in v0.5.0 

func (s *Snapshot) Release(ctx context.Context) error

Release removes the snapshot from the list of active snapshots.

func (*Snapshot) Sequence added in v0.5.0 

func (s *Snapshot) Sequence() uint64

Sequence returns the captured sequence number for this snapshot.

type SparseIndex 

type SparseIndex []KeyOffset

func (SparseIndex) GetOffset 

func (s SparseIndex) GetOffset(key Bytes) (int64, error)

type Stats added in v0.3.0 

type Stats struct {
	MemtableBytes    int
	SequenceNumber   uint64
	ActiveSnapshots  int
	SSTablesPerLevel []int
	WALBytes         uint64
	WALRecords       uint64
	GetCalls         uint64
	PutCalls         uint64
	RemoveCalls      uint64
	IRangeCalls      uint64
	Flushes          uint64
}

Stats represents runtime statistics of the database.

It includes information about memtable size, sequence number, active snapshot count, per-level SSTable counts, WAL usage and operation counters.

Source Files

View all Source files

Directories

Path Synopsis
diffharness module
tool
spanname command
testname 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.