Documentation
¶
Index ¶
- func BuildSortedIndex(ctx context.Context, sourcePaths []string, keyFunc KeyFunc, sidxPath string, ...) error
- func FilterAll(seq iter.Seq2[[]byte, []byte], keep func(line []byte) bool) iter.Seq2[[]byte, []byte]
- type KeyFunc
- type SortedIndex
- func (si *SortedIndex) All() iter.Seq2[[]byte, []byte]
- func (si *SortedIndex) Close() error
- func (si *SortedIndex) Get(key []byte) ([]byte, error)
- func (si *SortedIndex) Has(key []byte) (bool, error)
- func (si *SortedIndex) Len() int64
- func (si *SortedIndex) Prefix(prefix []byte) iter.Seq2[[]byte, []byte]
- func (si *SortedIndex) SourcePaths() []string
- type SortedIndexOptions
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BuildSortedIndex ¶
func BuildSortedIndex(ctx context.Context, sourcePaths []string, keyFunc KeyFunc, sidxPath string, opts SortedIndexOptions) error
BuildSortedIndex scans sourcePaths once each, in order, sequentially (same accept/skip rules as OpenFileIndex's rebuild: keyFunc rejecting a line skips it) and writes a lexicographically sorted directory to sidxPath (plus its sparse/Bloom/sources sidecars) via external merge sort: RAM at any point is bounded by opts.ChunkEntries, never by the combined source line count, so this scales to sources far larger than available RAM.
sourcePaths is precedence order, lowest first: when the same key appears in more than one file (or more than once in the same file), the entry from the latest file wins, and within one file the latest line wins — a later change file always overrides the base, regardless of byte offset. This is the direct multi-file generalization of FileIndex's single-file "last line wins".
No source file is ever rewritten. sidxPath and its sidecars are created fresh (or replaced if present); temporary run files are written alongside sidxPath and removed before return, including on error.
Concurrent BuildSortedIndex calls (or EnsureFresh calls that decide to build) for the same sidxPath, within this process, are serialized — see buildLocks. ctx is checked periodically during the scan and merge passes (every ctxCheckInterval entries); a cancelled build stops promptly, cleans up its temp files the same as any other error, and returns ctx.Err() wrapped.
func FilterAll ¶
func FilterAll(seq iter.Seq2[[]byte, []byte], keep func(line []byte) bool) iter.Seq2[[]byte, []byte]
FilterAll wraps an (key, line) iterator (typically SortedIndex.All or Prefix) with a caller predicate over the raw line bytes — a generic combinator, kept here rather than pushed into app code so every caller gets streaming, RAM-independent filtering for free. Field-specific predicate logic (which JSON fields to check, what values to match) stays the app's concern; only the plumbing lives in the library.
Types ¶
type SortedIndex ¶
type SortedIndex struct {
// contains filtered or unexported fields
}
SortedIndex is a read-only, lexicographically-sorted directory over one or more FileIndex-style source files (see fileindex.go), applied in caller-given precedence order — typically a one-shot base file followed by incremental change files, later file wins on a key conflict, same "last write wins" rule as within a single file. Unlike FileIndex, whose map[string]lineLoc index is fully RAM-resident, SortedIndex keeps the full key set on disk and only a sparse sample of it in RAM, so its memory footprint is independent of key count — built for source data too large to index in RAM (tens of millions of lines and up).
It is built once by BuildSortedIndex (an external merge sort: the combined source data can be far larger than RAM, see sortedindex_build.go) and reopened read-only by OpenSortedIndex, which is self-describing — it reads the source file list back from the .sources sidecar, so callers don't repeat it. There is no Put; a SortedIndex is a point-in-time view over its sources at build time. EnsureFresh (sortedindex_sources.go) is the usual entry point: it rebuilds only when the sources have actually changed (a stat-only check), otherwise just reopens the existing cache — see its doc comment, and SortedIndexManager for pairing that with idle-TTL reaping so a rarely queried dataset costs nothing in RAM between bursts of use.
On-disk layout (all part of one build, sharing sidxPath as a base name):
<sidxPath> (sorted key directory, one entry per source line, ascending key order):
magic "KVSI"(4) | version(4) | count(8)
count * [ keyLen(2) | key | fileIdx(2) | srcOffset(8) | lineLen(4) ]
crc32(4) -- IEEE checksum over every entry byte (not the header)
<sidxPath>.sparse (RAM-loaded directory, every SparseInterval-th key):
magic "KVSP"(4) | version(4) | count(8)
count * [ keyLen(2) | key | sidxOffset(8) ] -- sidxOffset points at
that entry's start within <sidxPath>, header included
crc32(4)
<sidxPath>.bloom (RAM-loaded Get-gating filter; see bloom.go)
<sidxPath>.sources (RAM-loaded freshness record; see
sortedindex_sources.go): the ordered source paths plus the
size/mtime each had at build time, letting EnsureFresh detect
"sources changed" with a stat, not a rebuild.
Get binary-searches the in-RAM sparse directory for the last sampled key <= the target, then does one bounded sequential scan of <sidxPath> from that offset (at most SparseInterval entries) to find the exact entry, then a single pread of the owning source file for the line itself. All files are pread-based (os.File.ReadAt), not mmap'd: unlike the segment reads in segment.go, these are one-shot random reads scattered across a huge file, not hot repeatedly-touched ranges, so there is little to gain from mmap+mincore here and pread keeps the Go scheduler able to park the goroutine during the I/O (see mincore_unix.go's doc comment for why that matters on a single-CPU host).
func EnsureFresh ¶
func EnsureFresh(ctx context.Context, sourcePaths []string, sidxPath string, keyFunc KeyFunc, opts SortedIndexOptions) (*SortedIndex, error)
EnsureFresh returns an open SortedIndex over sourcePaths (ordered lowest-to-highest precedence — later files win on a key conflict, e.g. a one-shot base file followed by incremental change files), updating sidxPath first only if it's missing or its recorded source stats (path/size/mtime) no longer match: a cheap stat-only check on the common path (warm cache, nothing changed), paying real work only when the data actually moved. This is the intended entry point for a rarely-queried, occasionally-changing dataset — see SortedIndexManager for pairing it with idle-TTL reaping.
When something changed, EnsureFresh picks the cheapest safe option:
- if every previously recorded source is unchanged and the only difference is new sources appended after them (incrementalEligible), it folds just the new data into the existing sidx (refreshSortedIndexLocked) — proportional to the new sources' size, not the whole dataset;
- otherwise (a source changed, was removed, or was reordered) it falls back to a full BuildSortedIndex.
The stat check and any resulting build/refresh happen under the same per-path lock BuildSortedIndex uses (see buildLocks): this closes a TOCTOU that would otherwise exist between "checked fresh" and "decided what to do", and means a second concurrent EnsureFresh call for the same sidxPath typically does no redundant work — by the time it gets the lock, the first call has usually already made it fresh. ctx cancels in-progress work the same way BuildSortedIndex's does; it is not consulted once the (fast, read-only) Open step begins.
func OpenSortedIndex ¶
func OpenSortedIndex(sidxPath string, keyFunc KeyFunc) (*SortedIndex, error)
OpenSortedIndex opens a directory previously written by BuildSortedIndex. It is self-describing: the source file list comes from the .sources sidecar (see sortedindex_sources.go), not a caller argument. It loads the (small, RAM-bounded) sparse and Bloom sidecars fully into memory and keeps every source file and the sidx file open for pread-based lookups. It does not load the full sidx or any source file into RAM, but it does do one sequential read over the sidx file's entries region to verify its checksum (see verifySidxChecksum) before trusting it — an O(n) cost on every Open, deliberately: see that function's doc comment for why.
func (*SortedIndex) All ¶
func (si *SortedIndex) All() iter.Seq2[[]byte, []byte]
All returns an iterator over every (key, line) pair in ascending key order: a single sequential scan of the sidx file interleaved with preads of the source files, with no RAM cost beyond one buffered reader regardless of index size.
func (*SortedIndex) Close ¶
func (si *SortedIndex) Close() error
Close closes every underlying source and the sidx file descriptor. A second call, or any Get/Prefix/All call after Close, returns kvtypes.ErrClosed.
func (*SortedIndex) Get ¶
func (si *SortedIndex) Get(key []byte) ([]byte, error)
Get returns the current line for key, or kvtypes.ErrNotFound — same contract as DB.Get and FileIndex.Get. If a Bloom filter sidecar was built, a definite-absent answer from it short-circuits here with zero I/O; otherwise (and on any maybe-present answer) it falls through to reading at most one bounded (<= SparseInterval entries) sequential scan of the sidx file plus one pread of the owning source file — RAM cost is O(1) regardless of index size either way.
func (*SortedIndex) Has ¶
func (si *SortedIndex) Has(key []byte) (bool, error)
Has reports whether key currently has a live entry — same contract as DB.Has and FileIndex.Has. Implemented as Get and discarding the line, since Get is already the cheapest possible existence check here (Bloom gate, then a bounded scan).
func (*SortedIndex) Len ¶
func (si *SortedIndex) Len() int64
Len returns the number of keys in the index.
func (*SortedIndex) Prefix ¶
Prefix returns an iterator over (key, line) pairs whose key has the given prefix, in ascending key order, doing one bounded seek to the start of the range followed by a purely sequential scan — no full-index scan, no RAM proportional to result size or index size.
func (*SortedIndex) SourcePaths ¶
func (si *SortedIndex) SourcePaths() []string
SourcePaths returns the ordered source file list this index was built from (lowest precedence first), as recorded in the .sources sidecar.
type SortedIndexOptions ¶
type SortedIndexOptions struct {
// ChunkEntries bounds how many (key, location) entries are held in RAM
// at once while scanning the source files, before that chunk is sorted
// and spilled to a temporary run file. Defaults to 2,000,000, which
// keeps a single chunk's RAM in the tens-of-MB range for typical key
// sizes while still bounding the number of runs (and therefore the
// merge's open-file-descriptor count) for a 78M-line source to ~40.
ChunkEntries int
// SparseInterval is how many sorted entries separate consecutive
// samples kept in the RAM sparse directory. Larger = less RAM, more
// bytes scanned per Get. Defaults to 4096, which for a 78M-key
// source keeps the sparse directory around ~19k entries (a few
// hundred KB to a few MB depending on key size) while bounding every
// Get's sequential scan to at most 4096 entries (~tens of KB read).
SparseInterval int
// BloomFPR is the target false-positive rate for the Get-gating
// Bloom filter built alongside the index. Defaults to 0.01 (1%), which
// costs ~9.6 bits/key regardless of key length — for 78M keys, ~94MB
// flat, fully RAM-resident like the sparse directory but far cheaper
// per key when keys are long. Set to a negative value to skip building
// a Bloom filter entirely.
BloomFPR float64
}
SortedIndexOptions tunes the RAM/lookup-cost tradeoff of a build.
Source Files