smol

README

smol

A key-value store written in Go, based on copy-on-write B+ tree.

Status

Under active development. The kv package is ready for use.

kv Package

Disk-based key-value store with:

• Ordered Keys: Lexicographic order via copy-on-write B+ tree
• MVCC: Concurrent reads and writes with snapshot isolation
• Transactions: Read Committed isolation with rollback support
• File Size: 32 KiB minimum, 64 TiB theoretical maximum
• Key/Value Size: No hard limit (recommended: keys < 3258 bytes, values < 13092 bytes)

File format specification is defined in the ksy/ directory, visualizable with Kaitai Struct.

Installation

go get github.com/dacapoday/smol/kv

Get Started

package main

import (
    "fmt"
    "log"

    "github.com/dacapoday/smol/kv"
)

func main() {
    // Open or create database file
    db, err := kv.Open("my-data.kv")
    if err != nil {
        log.Fatal(err)
    }
    defer db.Close()

    // Write
    err = db.Set([]byte("hello"), []byte("world"))
    if err != nil {
        log.Fatal(err)
    }

    // Read
    value, err := db.Get([]byte("hello"))
    if err != nil {
        log.Fatal(err)
    }
    fmt.Printf("hello: %s\n", value)

    // Delete (set value to nil)
    err = db.Set([]byte("hello"), nil)
    if err != nil {
        log.Fatal(err)
    }
}

Transactions

tx := db.Begin()

// Multiple changes
tx.Set([]byte("user:1:name"), []byte("dacapoday"))
tx.Set([]byte("user:1:email"), []byte("dacapoday@gmail.com"))

// Read (sees uncommitted changes)
name, _ := tx.Get([]byte("user:1:name"))
fmt.Printf("Name: %s\n", name)

// Commit atomically
err = tx.Commit()
if err != nil {
    log.Fatal(err)
}

// Or rollback to discard changes

File Format

Database file format visualized with Kaitai Struct IDE:

Documentation

Overview

Package smol defines basic interfaces for building key-value database components.

Index

• Variables
• type Block
• type BlockID
• type Checkpoint
• type File
• type ReadOnly
• type ReadWrite

Variables

var (
	ErrClosed             = errors.New("closed")
	ErrReadOnly           = errors.New("read-only")
	ErrInvalidBlockSize   = errors.New("invalid block size")
	ErrInvalidCipherSuite = errors.New("invalid cipher suite")
	ErrInvalidCipherKey   = errors.New("invalid cipher key")
	ErrBadChecksum        = errors.New("bad checksum")
	ErrBadMeta            = errors.New("bad meta")
	ErrBadEntry           = errors.New("bad entry")
	ErrBadFreelist        = errors.New("bad freelist")
	ErrBadOverflow        = errors.New("bad overflow")
	ErrBadCipherSpec      = errors.New("bad cipher spec")
	ErrUnknownMagicCode   = errors.New("unknown magic code")
	ErrFileEmpty          = errors.New("empty file")
	ErrFileTruncated      = errors.New("file truncated")
	ErrNoSpace            = errors.New("no space")
	ErrUnsupported        = errors.New("unsupported")
	ErrOutOfRange         = errors.New("out of range")
	ErrAllocateFailed     = errors.New("allocate failed")
)

Types

type Block

type Block[C Checkpoint] interface {
	// Close releases the underlying storage and discards uncommitted changes.
	// All Checkpoints must be released before Close.
	Close() error

	// Rollback discards all uncommitted changes.
	Rollback() error

	// Commit atomically persists all changes and returns a Checkpoint.
	// Entry is metadata persisted with the commit.
	//
	// Warning: Entry size must not exceed PageSize().
	Commit(entry []byte) (C, error)

	ReadWrite
}

Block divides storage into fixed-size blocks indexed by BlockID. Requires copy-on-write data structures for Commit and Rollback.

type BlockID

type BlockID = uint32

BlockID identifies a block, starting from 2 (0 and 1 are reserved).

type Checkpoint

type Checkpoint interface {
	// Acquire increments the reference count.
	Acquire()

	// Release decrements the reference count.
	Release()
}

Checkpoint is a reference to a commit snapshot.

type File

type File interface {
	io.ReaderAt
	io.WriterAt
	io.Closer

	// Truncate changes the size of the file.
	Truncate(size int64) error

	// Sync commits file contents to stable storage.
	Sync() error
}

File provides access to a storage backend. *os.File satisfies this interface.

type ReadOnly

type ReadOnly interface {
	// LoadBlock reads a block and returns its content.
	// Returned buffer is read-only. Recycle via RecycleBuffer.
	LoadBlock(blockID BlockID) (buffer []byte, err error)

	// AllocateBuffer allocates a buffer for reading and writing blocks.
	// Recycle via RecycleBuffer when done.
	AllocateBuffer() []byte

	// ReadBlock reads a block using buffer.
	// If reader is provided, access data via reader; otherwise data is copied to buffer.
	//
	// Important: Buffer parameter is required even when reader is provided.
	ReadBlock(blockID BlockID, buffer []byte, reader func(block []byte)) error

	// NeedRecycleBuffer reports whether caller should recycle buffers
	// to relieve memory pressure. holding: buffers held by current session.
	//
	// Returns true when pool resources are strained. Callers may continue
	// allocating but should consider releasing buffers to reduce pressure.
	NeedRecycleBuffer(holding int) bool

	// RecycleBuffer releases a buffer from AllocateBuffer or LoadBlock.
	//
	// Warning: Caller must not use buffer after recycling.
	RecycleBuffer(buffer []byte)
}

ReadOnly is a subset of Block interface for reading blocks.

Important: All buffers from AllocateBuffer or LoadBlock must be recycled via RecycleBuffer.

type ReadWrite

type ReadWrite interface {
	ReadOnly

	// PageSize returns usable bytes within a block.
	PageSize() int

	//
	// Example:
	//   blockID := block.AllocateBlock()
	//   if blockID < 2 {
	//     if err, ok := block.(interface{ Error() error }); ok {
	//       return err.Error()
	//     }
	//     return errors.New("allocation failed")
	//   }
	AllocateBlock() BlockID

	// RecycleBlock marks a BlockID as no longer needed.
	// Recycling the same BlockID multiple times causes undefined behavior.
	RecycleBlock(BlockID)

	// WriteBlock writes buffer to storage at blockID.
	//
	// Warning: Caller must not rely on buffer content after writing as it may be modified.
	WriteBlock(blockID BlockID, buffer []byte) error
}

ReadWrite provides methods for reading and writing blocks. Embeds ReadOnly and extends it with write operations.