keyspace

package
v0.1.0 Latest Latest
Warning

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

 Go to latest Published: Jun 23, 2026 License: BSD-3-Clause Imports: 13 Imported by: 0

Documentation

Overview

Package keyspace is aki's logical key dictionary (spec 2064 doc 05). It maps N independent logical databases onto one .aki file. Each database is an ordered map from a binary key to a ValueHeader plus its inline body, stored in a per-DB B-tree keyed by a composite (hash slot, key length, key) tuple. The package tracks a per-DB catalog (root page, key count, expire count, average TTL) on a dedicated catalog page referenced from the meta page, and it applies lazy TTL expiry on read.

This slice is the storage layer the command dispatch layer sits on. It assumes a single writer at a time; the sharded writer model and MVCC snapshot filtering from doc 05 §7 and §12 come in later slices.

Index

Constants

View Source 
const (
	TypeString uint8 = 0 // "string"
	TypeList   uint8 = 1 // "list"
	TypeHash   uint8 = 2 // "hash"
	TypeSet    uint8 = 3 // "set"
	TypeZSet   uint8 = 4 // "zset"
	TypeStream uint8 = 5 // "stream"
)

Type codes for the value stored under a key (doc 05 §3.2). TYPE reports the name in the comment; bitmaps, bitfields and HLL all live under TypeString.

View Source 
const (
	EncInt        uint8 = 0
	EncEmbStr     uint8 = 1
	EncRaw        uint8 = 2
	EncListpack   uint8 = 3
	EncQuicklist  uint8 = 4
	EncHashtable  uint8 = 6
	EncIntset     uint8 = 7
	EncSkiplist   uint8 = 8
	EncStream     uint8 = 9
	EncListpackex uint8 = 11
)

Encoding codes reported by OBJECT ENCODING (doc 05 §3.3). They label the logical Redis structure, not aki's physical paging.

View Source 
const (
	FlagHasTTL     uint8 = 1 << 0
	FlagInlineBody uint8 = 1 << 1
	FlagLFUMode    uint8 = 1 << 2
	FlagNoEvict    uint8 = 1 << 3
	FlagNoTouch    uint8 = 1 << 4
)

Flag bits in ValueHeader.Flags (doc 05 §3.1).

View Source 
const HeaderSize = 40

HeaderSize is the on-disk size of a serialized ValueHeader (doc 05 §3.1).

Variables

View Source 
var ErrDBRange = errors.New("aki/keyspace: database index out of range")

ErrDBRange is returned when a database index is outside [0, DBCount).

Functions

func HashSlot 

func HashSlot(key []byte) uint16

HashSlot returns the cluster hash slot for a key. If the key contains a hash tag {...} with non-empty content, only the content between the first { and the first } after it is hashed, so keys sharing a tag land in the same slot. This matches Redis cluster.c keyHashSlot.

func NowMillis 

func NowMillis() int64

NowMillis returns the keyspace clock in Unix epoch milliseconds. The command layer uses it to turn a relative TTL like EX seconds into the absolute millisecond deadline that Set stores, so both layers read the same clock.

Types

type DB 

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

DB is one logical database: a B-tree of keys plus its catalog counters.

func (*DB) Delete 

func (db *DB) Delete(key []byte) (bool, error)

Delete removes key. It returns whether a key was present.

func (*DB) Exists 

func (db *DB) Exists(key []byte) (bool, error)

Exists reports whether key is present and unexpired without recording an access. An expired key is deleted.

func (*DB) Flush 

func (db *DB) Flush() error

Flush empties the database. It walks the tree once to free every overflow chain and to drop the freed keys from the used-memory estimate, returns the tree's own pages to the freelist, then drops the root and zeroes the counters so the next write starts a fresh tree. Before page reclamation this path orphaned the whole tree, the one place page accounting could not hold; now the pages go back on the freelist like an UNLINK frees its overflow chain.

func (*DB) Freq 

func (db *DB) Freq(key []byte) uint8

Freq returns the decayed LFU counter, the OBJECT FREQ answer. The decay is computed for the read but not stored, since reading frequency is not itself an access.

func (*DB) Get 

func (db *DB) Get(key []byte) (body []byte, hdr ValueHeader, found bool, err error)

Get returns the body and header for key and records an LRU and LFU access. It is the read path data commands use. found is false when the key is absent or has expired; an expired key is deleted as a side effect (lazy expiry).

func (*DB) Idle 

func (db *DB) Idle(key []byte) uint32

Idle returns whole seconds since the key was last accessed, the OBJECT IDLETIME answer. A key with no recorded access yet reports zero.

func (*DB) Index 

func (db *DB) Index() int

Index returns the database's index.

func (*DB) Keys 

func (db *DB) Keys() ([]ScanEntry, error)

Keys returns every live key in the DB with its type, in B-tree order. Expired keys are skipped. The order is the composite-key order from value.go, which is what KEYS and RANDOMKEY treat as unspecified.

func (*DB) Len 

func (db *DB) Len() uint64

Len returns the number of live keys, the value DBSIZE reports.

func (*DB) Peek 

func (db *DB) Peek(key []byte) (body []byte, hdr ValueHeader, found bool, err error)

Peek is Get without recording an access, the read path introspection commands use so OBJECT, EXISTS and friends do not reset a key's idle time or bump its frequency.

func (*DB) Scan 

func (db *DB) Scan(cursor uint64, count int) (uint64, []ScanEntry, error)

Scan returns up to count live keys at or above the cursor in hash order, plus the cursor to resume from. A cursor of 0 starts a new scan and a returned cursor of 0 means the keyspace is exhausted.

The cursor is the FNV-1a hash of a key's composite B-tree key truncated to 48 bits. Emitting keys in hash order keeps the scan stateless and complete: a key present for the whole scan has a fixed hash, so it is returned in exactly the one call whose hash window covers it, and a key deleted mid-scan only drops itself rather than cutting the scan short. Each call walks the whole tree, so this is O(n log n) per call; a later milestone replaces it with an incremental B-tree cursor.

func (*DB) Set 

func (db *DB) Set(key, body []byte, typ, enc uint8, ttlMs int64) error

Set writes key with the given body, type, encoding and TTL. A ttlMs of -1 means no expiry; a positive ttlMs is an absolute Unix epoch in milliseconds. A key whose absolute TTL is already in the past is not written and any existing key under that name is removed, matching Redis's write-time expiry.

func (*DB) SetFreq 

func (db *DB) SetFreq(key []byte, freq uint8)

SetFreq seeds a key's LFU counter, which is how RESTORE FREQ reconstructs the frequency of a dumped key.

func (*DB) SetIdle 

func (db *DB) SetIdle(key []byte, idle uint32)

SetIdle seeds a key's last-access time to idle seconds in the past, which is how RESTORE IDLETIME reconstructs the LRU clock of a dumped key.

type DBCheck 

type DBCheck struct {
	Index       int
	Entries     int // total tree entries walked
	Live        int // entries that are not expired
	Expires     int // entries carrying a TTL
	StaleTTL    int // entries whose TTL is already in the past
	FutureTTL   int // entries with an impossibly far-future TTL
	BadHeaders  int // entries whose value header failed to parse
	OrderErrors int // entries out of composite-key order
	// StructErr is set when the B-tree itself is malformed (bad child counts,
	// keys outside their range, a broken leaf chain). It is independent of the
	// per-entry counts above, which assume a walkable tree.
	StructErr error
}

DBCheck is the integrity result for one database. The counts come from a single in-order walk of the B-tree.

type EvictionCandidate 

type EvictionCandidate struct {
	DB     int
	Key    []byte
	TTLms  int64
	HasTTL bool
	Atime  uint32 // unix seconds of last access; smaller is older, evicted first by LRU
	Freq   uint8  // decayed LFU counter; smaller is colder, evicted first by LFU
}

EvictionCandidate is a key the eviction loop may remove, carrying the fields the policies sort on: the expiry for volatile-ttl, the last-access time for the lru policies, and the decayed frequency for the lfu policies.

type ExpiredKey 

type ExpiredKey struct {
	DB  int
	Key []byte
}

ExpiredKey names a key that lazy expiry removed, tagged with the database it lived in. The command layer drains these after a keyspace access to fire the "expired" notification, which the keyspace layer cannot fire on its own.

type Keyspace 

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

Keyspace owns every logical database in one .aki file.

func Open 

func Open(pgr *pager.Pager) (*Keyspace, error)

Open binds a Keyspace to a pager and loads the catalog. The number of databases comes from the file header; a fresh file with no catalog page yields empty databases that materialize their B-trees on first write.

func (*Keyspace) ActiveExpireCycle 

func (ks *Keyspace) ActiveExpireCycle() (int, error)

ActiveExpireCycle walks every database for volatile keys whose TTL has passed, deletes them, and records each in the expired log so the command layer can fire the "expired" event. It returns the number of keys removed. A database with no volatile keys is skipped on the cheap expireCount guard.

func (*Keyspace) Check 

func (ks *Keyspace) Check() ([]DBCheck, error)

Check walks every database B-tree in order and reports the per-database integrity counts. A traversal error (an unreadable page) is returned so the caller can treat it as structural corruption.

func (*Keyspace) CheckPageAccounting 

func (ks *Keyspace) CheckPageAccounting() error

CheckPageAccounting proves every page in the file is accounted for exactly once: either live (reachable from the catalog, a database B-tree, or a value's overflow chain) or free (on the freelist), never both and never neither. It is the page-level form of doc 23 section 9.3, run on demand by the integrity checker and after every commit in debug builds.

The three faults it catches are a page that is reachable and also on the freelist (a use-after-free waiting to happen), a page that two structures both claim as live (a double reference), and a page that is neither reachable nor free (a leak). The freelist's own no-duplicate rule is checked here too.

func (*Keyspace) Commit 

func (ks *Keyspace) Commit() error

Commit persists the catalog and every DB root, then commits the pager. The catalog page is allocated on first commit that has data to record.

func (*Keyspace) DB 

func (ks *Keyspace) DB(index int) (*DB, error)

DB returns the database at index, or an error if the index is out of range.

func (*Keyspace) DBCount 

func (ks *Keyspace) DBCount() int

DBCount returns the number of logical databases.

func (*Keyspace) FixFutureTTLs 

func (ks *Keyspace) FixFutureTTLs() (int, error)

FixFutureTTLs clears TTLs that are impossibly far in the future, rewriting those keys with no expiry, and commits. It returns the number of keys fixed. This is the only repair the checker performs on the keyspace; structural corruption is left to a dump and reimport.

func (*Keyspace) PagerName 

func (k *Keyspace) PagerName() string

PagerName returns the file path the underlying pager was opened with, empty for an in-memory backing.

func (*Keyspace) PagerStats 

func (k *Keyspace) PagerStats() pager.Stats

PagerStats returns the underlying pager's counters for the file-growth INFO fields. It is a passthrough so the command layer does not reach into the pager.

func (*Keyspace) SampleForEviction 

func (ks *Keyspace) SampleForEviction(n int, volatileOnly bool) []EvictionCandidate

SampleForEviction reservoir-samples up to n eviction candidates across every database. When volatileOnly is set it considers only keys that carry a TTL, which is what the volatile-* policies evict from.

func (*Keyspace) SetLFUParams 

func (k *Keyspace) SetLFUParams(logFactor, decayTime int)

SetLFUParams sets the LFU counter tuning the eviction sampler uses, from the lfu-log-factor and lfu-decay-time config knobs. A log factor below zero clamps to zero, which makes the counter climb on every access. A decay time of zero or below disables decay, so a counter never falls on its own.

func (*Keyspace) Swap 

func (ks *Keyspace) Swap(i, j int) error

Swap exchanges the contents of two databases in place, leaving their indexes fixed, so a client on index i sees what was in index j afterward. Swapping a database with itself does nothing.

func (*Keyspace) SystemDelete 

func (ks *Keyspace) SystemDelete(name string) (bool, error)

SystemDelete removes name and reports whether it existed.

func (*Keyspace) SystemGet 

func (ks *Keyspace) SystemGet(name string) ([]byte, bool, error)

SystemGet returns the blob stored under name. The second result is false when no entry exists. The returned slice is a copy the caller may keep.

func (*Keyspace) SystemList 

func (ks *Keyspace) SystemList(prefix string) ([]string, error)

SystemList returns every entry name that starts with prefix, in sorted order. An empty prefix lists every entry.

func (*Keyspace) SystemPut 

func (ks *Keyspace) SystemPut(name string, val []byte) error

SystemPut stores val under name, replacing any current value. The change becomes durable on the next Commit. A value too large for one leaf returns the B-tree's ErrCellTooLarge.

func (*Keyspace) TakeExpired 

func (ks *Keyspace) TakeExpired() []ExpiredKey

TakeExpired returns the keys lazily expired since the last call and clears the log. The command engine calls it under its own lock so there is no concurrent appender.

func (*Keyspace) UsedMemory 

func (ks *Keyspace) UsedMemory() int64

UsedMemory returns the live-data estimate in bytes, the value compared against maxmemory. It is the sum of key name, body and per-key overhead across every live key, which shrinks as keys are deleted or evicted.

type ScanEntry 

type ScanEntry struct {
	Key  []byte
	Type uint8
}

ScanEntry is one live key visited by Keys or Scan, paired with its value type so a caller can apply a TYPE filter without a second lookup.

type ValueHeader 

type ValueHeader struct {
	Type     uint8
	Encoding uint8
	Flags    uint8
	TTLms    int64  // absolute Unix epoch ms; -1 means no expiry
	Version  uint64 // monotonic write version
	LRULFU   uint32 // LRU clock or LFU counter
	BodyRef  uint64 // sub-tree root page when not inline; 0 when inline
	BodyLen  uint32 // serialized body size
	RefCount uint32 // always 1 for now
}

ValueHeader is the envelope written as the value side of every key in the keyspace B-tree. It carries type and encoding metadata, the absolute TTL, the write version used by WATCH and MVCC, and a reference to the value body. In this slice the body is always stored inline right after the header in the same B-tree leaf cell, so BodyRef is zero and FlagInlineBody is set.

func (ValueHeader) AppendTo 

func (h ValueHeader) AppendTo(dst []byte) []byte

AppendTo appends the 40-byte little-endian encoding of h to dst.

func (ValueHeader) HasTTL 

func (h ValueHeader) HasTTL() bool

HasTTL reports whether the header carries an expiry.

Source Files

View all Source files

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.