format

package
v0.2.0 Latest Latest
Warning

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

 Go to latest Published: Jul 2, 2026 License: MIT Imports: 14 Imported by: 0

Documentation

Overview

Package format is the .meguri single-file container: the 64-byte header, the five regions (URL table, host table, schedule index, seen-set filter, string and blob), and the footer written last, bracketed by the magic MEG1 at both ends.

A .meguri file is one partition's entire frontier state. It is at once the durable checkpoint, the redistribution unit when a partition moves or rebalances, and the cold archive (D1, D12). The footer comes last so one read of the file tail learns the whole structure, which is what makes object-store redistribution cheap.

This package owns the bytes. The logical schema it serializes (URLRecord, HostRecord, and the rest) lives in the top-level meguri package, and a checkpoint writes those records straight into columns with no remapping. The writer is deterministic: given the same records and the same creation timestamp it produces byte-identical files, the property every golden-file test and content-addressed redistribution leans on.

M0 lands the container with RAW column encoding plus an optional zstd block codec. The richer tatami encoding cascade (dictionary, delta, frame of reference, FSST) slots in behind the same page and directory structure in later milestones without changing the container.

Index

Constants

View Source 
const (
	VersionMajor uint16 = 1
	VersionMinor uint16 = 0
)

Format version. Major changes break the layout; minor changes are additive.

View Source 
const (
	ChecksumNone   uint8 = 0
	ChecksumCRC32C uint8 = 1
	ChecksumXXH64  uint8 = 2
)

Checksum algorithm selectors, stored in the header's checksum_algo byte.

View Source 
const (
	CodecNone     uint8 = 0
	CodecLZ4      uint8 = 1 // reserved, not wired in M0
	CodecZstd     uint8 = 2
	CodecZstdDict uint8 = 3 // reserved, not wired in M0
)

Block codec ids, stored in the header's default_codec byte and per page. The values match tatami's codec enum so a shared decoder can serve both formats.

View Source 
const (
	EncRaw      uint8 = 0
	EncDict     uint8 = 1
	EncDelta    uint8 = 2
	EncFOR      uint8 = 3
	EncRLE      uint8 = 4
	EncFSST     uint8 = 5
	EncDeltaFOR uint8 = 6
	// EncFrontCode marks a blob page whose payload is front-coded: each string is
	// stored as the shared-prefix length with the previous string in the page plus
	// the literal suffix, the first string of every page a restart (shared 0). It is
	// a meguri extension past tatami's enum (Spec 2074 M1), reversed back to the raw
	// arena bytes on decode so the *Ref offsets are unchanged.
	EncFrontCode uint8 = 7
)

Column encoding ids, stored per page and as the dominant encoding per column. The values match tatami's encoding enum. M0 writes RAW only; the others are decoded-ready placeholders for later milestones.

View Source 
const (
	FlagSorted           uint16 = 1 << 0
	FlagHasSchedule      uint16 = 1 << 1
	FlagHasSeenset       uint16 = 1 << 2
	FlagHasBlob          uint16 = 1 << 3
	FlagSeensetIsRibbon  uint16 = 1 << 4
	FlagHasMPHF          uint16 = 1 << 5
	FlagFooterCompressed uint16 = 1 << 6
	// FlagBlobFrontCoded records that the string blob region's pages are front-coded
	// (EncFrontCode) rather than raw. A reader that does not know the layout rejects
	// the file rather than misresolving a ref against bytes it cannot reverse.
	FlagBlobFrontCoded uint16 = 1 << 7
)

Header flag bits.

View Source 
const (
	RegionURLTable   uint8 = 0
	RegionHostTable  uint8 = 1
	RegionSchedule   uint8 = 2
	RegionSeenset    uint8 = 3
	RegionStringBlob uint8 = 4
)

Region ids, the fixed order regions appear in a .meguri file.

View Source 
const (
	PageData     uint8 = 0
	PageDict     uint8 = 1
	PageIndex    uint8 = 2
	PageBlob     uint8 = 3
	PageFilter   uint8 = 4
	PageSchedule uint8 = 5
)

Page kinds.

View Source 
const (
	ColURLHostKey     = colURLHostKey
	ColURLPathKey     = colURLPathKey
	ColURLStatus      = colURLStatus
	ColURLNextDue     = colURLNextDue
	ColURLHTTPStatus  = colURLHTTPStatus
	ColURLCrawlCount  = colURLCrawlCount
	ColURLLastCrawled = colURLLastCrawled
)

Exported URL column ids, the stable schema positions a projection names. They match the on-disk column directory and never change once shipped (doc 10 section 4, the URL table columns).

View Source 
const HeaderSize = 64

HeaderSize is the fixed size of the .meguri header at offset 0.

View Source 
const PageHeaderSize = 32

PageHeaderSize is the fixed, uncompressed page header size.

View Source 
const RobotsSizeHint = 1 << 20

RobotsSizeHint bounds an unpacked robots blob. A robots.txt that matters for crawl scheduling is small; a blob claiming to inflate past this is treated as corrupt rather than allocated.

Variables

View Source 
var (
	ErrBadMagic    = errors.New("meguri/format: bad magic")
	ErrShortFile   = errors.New("meguri/format: file too short")
	ErrCorrupt     = errors.New("meguri/format: corrupt file")
	ErrChecksum    = errors.New("meguri/format: checksum mismatch")
	ErrUnsupported = errors.New("meguri/format: unsupported version")
	ErrNotSorted   = errors.New("meguri/format: url records not sorted by urlkey")
)

Sentinel errors a caller can match with errors.Is.

View Source 
var ErrArenaBackward = errors.New("format: arena ref moved backward")

ErrArenaBackward is returned by ArenaSeqReader.At when a ref moves backward, which breaks the ascending-access contract the sequential reader relies on.

View Source 
var Magic = [4]byte{'M', 'E', 'G', '1'}

Magic brackets a .meguri file at both ends.

View Source 
var ManifestMagic = [4]byte{'M', 'G', 'M', '1'}

ManifestMagic brackets a serialized manifest. It is distinct from the file magic so a manifest is never mistaken for a partition file.

Functions

func Encode 

func Encode(p *Partition) ([]byte, error)

Encode serializes a Partition into a complete .meguri file. The output is deterministic: the same Partition value always produces the same bytes, which is what makes a checkpoint diffable and the round-trip gate meaningful. Encode does not sort; it returns ErrNotSorted if the caller's rows are out of order.

func EncodeManifest 

func EncodeManifest(m *Manifest) []byte

EncodeManifest serializes a manifest deterministically: the magic, the entry count, then each entry, then the trailing CRC and magic, mirroring the file's commit discipline so a torn manifest is detectable.

func EncodeToFile added in v0.2.0 

func EncodeToFile(path string, p *Partition) (err error)

EncodeToFile writes a Partition's complete .meguri file to path, producing the exact bytes Encode produces but streaming one region at a time so the whole image is never held in memory at once. Encode accumulates every region and then a second full-image copy in its output slice; at 100M URLs that doubled image is several GB of avoidable checkpoint transient on top of the record materialization the snapshot already pays (scale doc 12, F4). This builds each region, writes it through a buffered writer, and drops it before building the next, so the resident cost is the largest single region (the URL table or the string blob), not their sum plus a copy. The header's FooterOffset is known only after the body is sized, so a zero placeholder goes down first and the real header is written last with WriteAt at offset 0; everything between is written front to back.

The output is byte-for-byte identical to Encode(p): the same regions in the same order, the same footer, trailer, and header. TestEncodeToFileMatchesEncode pins the equality on the real corpus, so the streaming path can never drift from the in-memory one without the gate catching it.

func PackRobots 

func PackRobots(blob []byte, codec uint8) []byte

PackRobots wraps a robots blob in the smallest of the three modes: the allow-all sentinel for an empty blob, then whichever of raw or codec-compressed is shorter. The first byte is always the mode, so UnpackRobots needs nothing else to reverse it. An empty blob packs to a single sentinel byte.

func StreamEncodeToFile added in v0.2.0 

func StreamEncodeToFile(path string, src URLRecordSource, maxRows int, p *Partition, tmpDir string) (err error)

StreamEncodeToFile writes a complete .meguri file to path, streaming the URL table from src one record at a time instead of taking a materialized p.URLs. It is the bounded-memory checkpoint encoder (spec 2072 D9, 2071 implementation doc 51): the largest region, the URL table, never exists as a record slice or a column-major copy in memory; it is built page by page by StreamURLRegion and spilled to temp files. The host table, string blob, and optional seen-set are small and stay materialized in p, as in EncodeToFile. The output is a valid, byte-stable .meguri file identical to EncodeToFile fed the same records with the same MaxPageRows; the schedule region is not supported here because a checkpoint snapshot never builds one (p.BuildSchedule must be false).

src must yield records in ascending URLKey order (the store's k-way shard merge does); the meter verifies it and the call fails with ErrNotSorted otherwise. maxRows should be > 0 so the per-column page buffers stay bounded; a zero keeps the single-page layout and reintroduces the O(rows) buffer the streaming exists to avoid.

func StreamURLRegion added in v0.2.0 

func StreamURLRegion(w io.Writer, src URLRecordSource, regionStart uint64, maxRows int, codec uint8, tmpDir string) ([]columnDir, uint64, uint32, error)

StreamURLRegion encodes the URL column region by pulling records from src one at a time, spilling each column's pages to a temp file under tmpDir, then concatenating the temp files in column order to w. It produces byte-identical output to encodeColumnRegion(urlColumns(allRecords, codec), regionStart, maxRows): same page boundaries, same per-page buildColumnPage decisions, same directory. The win is residency. It holds at most one page per column (about maxRows*width bytes each) plus one record, never the O(rows) partition slice or the column-major copy that the materializing checkpoint builds (spec 2072 D9, 2071 implementation doc 51). regionStart is the region's absolute file offset so the directory's firstPageOffset is absolute, matching encodeColumnRegion.

maxRows must be > 0 for the residency win: with maxRows <= 0 the format keeps a single page per column and a single page is the whole column, so the last page buffer holds every row. The function stays byte-identical in that case but is no longer bounded; the checkpoint caller passes a bounded maxRows. The fourth return is the CRC32C over the entire region's bytes, which the footer's region descriptor records exactly as Encode/EncodeToFile do for the materialized region.

func UnpackRobots 

func UnpackRobots(packed []byte, codec uint8, sizeHint int) ([]byte, bool)

UnpackRobots reverses PackRobots, returning the original blob and whether the bytes were a well-formed packed blob. A compressed body is bounded by sizeHint so a corrupt length cannot drive an unbounded allocation; pass the codec the blob was packed with. Empty input or an unknown mode reports not-ok.

Types

type ArenaRandReader added in v0.2.0 

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

ArenaRandReader resolves arena refs in any order. It decodes the whole string arena once, so its resident cost is the arena size, not one page, and it is the tool for a file whose arena is not key-ordered: an engine checkpoint interns strings in the insertion order URLs were discovered, so a walk in URLKey order hits refs that jump backward, which ArenaSeqReader rejects by contract. A key-ordered, front-coded file (BulkLoad or a compaction wrote it) should use ArenaSeqReader instead, whose transient is one page and so scales to a 100M arena; this reader is for the general unordered file where correctness beats the page bound.

func (*ArenaRandReader) At added in v0.2.0 

func (a *ArenaRandReader) At(ref uint64) ([]byte, error)

At returns the string interned at ref, or nil for the zero sentinel or an out-of-range ref. The slice aliases the decoded arena and stays valid for the reader's life, unlike ArenaSeqReader.At whose result the next call overwrites. The error is always nil; it matches ArenaSeqReader.At's signature so an export can hold either behind one interface.

type ArenaSeqReader added in v0.2.0 

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

ArenaSeqReader resolves string-arena refs in ascending order without holding the whole (possibly multi-gigabyte) arena resident. It is the read side of Stage 2 compaction (spec 2073 doc 08): the compactor walks the base URL table in URLKey order to source each unchanged record's URL string, and BulkLoad interns URL strings in that same key order, so a record's URLRef only ever increases as the cursor advances. This reader decodes the blob region's pages in order and keeps a sliding window of decoded bytes starting at the last resolved ref, so its transient is about one blob page plus the current span, not the arena. The whole-arena decodeBlobRegion is the wrong tool at 100M scale; this is the bounded one.

Host strings live at the low end of the arena (BulkLoad interns hosts before URLs), so a compactor resolves the host table's refs through one reader first, then opens a second reader for the ascending URL walk. Two forward passes, never a random seek.

func (*ArenaSeqReader) At added in v0.2.0 

func (a *ArenaSeqReader) At(ref uint64) ([]byte, error)

At returns the string interned at ref, valid until the next At call. ref must be at or after the previous call's ref (ascending access); a zero ref is the absent sentinel and returns nil. A backward ref returns ErrArenaBackward; a ref or span past the arena returns ErrCorrupt.

type DueCursor added in v0.2.0 

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

DueCursor streams the URL rows due at or before a wall-clock hour off the file in bounded batches, so a scheduler pulls the next work without decoding the whole next_due column or materializing every due key at once. It walks the next_due, hostkey, and pathkey columns page by page, uses each next_due page's zone map to skip a page whose soonest due time is still in the future, and emits due keys up to a caller batch cap, remembering its position across calls. The transient is a few decoded pages plus the batch, not the column: at 100M, where DueKeys' whole-column projection plus its every-due-key slice would hold gigabytes, this is the scale-appropriate scheduler read.

func (*DueCursor) NextBatch added in v0.2.0 

func (c *DueCursor) NextBatch(limit int) ([]m.URLKey, error)

NextBatch returns up to limit URLKeys due at or before the cursor's now, in stored (host-key ascending) order, decoding only as many pages as it takes to fill the batch. It returns nil when the scan is exhausted, so a scheduler loops on NextBatch until it gets nil or has dispatched enough. A due row has a nonzero next_due at or before now; a zero next_due is unscheduled and never returned.

type FSSTArena 

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

FSSTArena is a per-ref string arena: a shared symbol table and a span region where each string is stored as its own FSST code stream behind a uvarint length. A ref is a byte offset into the spans, and Read decodes just that string from the shared table, the random access the whole-arena zstd blob cannot give. It is the doc 10 section 7 layout: the columns keep byte-offset refs, but a resolve touches one span, not the whole region.

func BuildFSSTArena 

func BuildFSSTArena(strs [][]byte) (*FSSTArena, []uint64)

BuildFSSTArena trains a table over the strings and lays each one out as an independently-decodable span, returning the arena and the per-string offsets in input order. Offset 0 is the none sentinel (a single zero byte), so a zero ref reads back empty, matching the verbatim arena's convention.

func LoadFSSTArena 

func LoadFSSTArena(table, spans []byte) *FSSTArena

LoadFSSTArena reconstructs an arena from its serialized table and span region, the read side a file uses after decoding the two regions off disk.

func (*FSSTArena) Bytes 

func (a *FSSTArena) Bytes() (table, spans []byte)

Bytes returns the arena's two regions, the shared table and the span region, the sizes a measurement sums and the file would frame as its string region.

func (*FSSTArena) Read 

func (a *FSSTArena) Read(off uint64) []byte

Read decodes the string at a span offset, reading only that span and the shared table. A zero or out-of-range offset reads back nil, the none sentinel. 

type Header struct {
	VersionMajor uint16
	VersionMinor uint16
	PartitionID  uint32
	Flags        uint16
	ChecksumAlgo uint8
	DefaultCodec uint8
	HostKeyLo    uint64
	HostKeyHi    uint64
	URLCount     uint64
	HostCount    uint64
	FooterOffset uint64
	CreatedHours uint32
}

Header is the fixed 64-byte file header. It lets a reader sanity-check the file and learn the global facts (the partition's HostKey range, the region offsets, the row counts) without parsing the footer, and it carries the two things a frontier partition file needs that a document shard does not: the partition id and the HostKey range the partition owns.

func DecodeHeader 

func DecodeHeader(b []byte) (*Header, error)

DecodeHeader parses and verifies a 64-byte header.

func (*Header) Encode 

func (h *Header) Encode() []byte

Encode writes the header into a fresh 64-byte slice, stamping the CRC32C over the first 60 bytes into the last 4. The magic is written first.

type Inspect 

type Inspect struct {
	PartitionID  uint32
	VersionMajor uint16
	VersionMinor uint16
	Flags        uint16
	ChecksumAlgo uint8
	DefaultCodec uint8
	CreatedHours uint32
	HostKeyLo    uint64
	HostKeyHi    uint64
	URLCount     uint64
	HostCount    uint64
	FileSize     uint64

	Regions     []RegionInfo
	URLColumns  int
	HostColumns int
	Encodings   map[string]int // encoding name -> column count, the cascade made visible
	Stats       Stats
	Meta        map[string]string
}

Inspect is the cheap structural summary of a .meguri file: everything the header and footer carry, with no column data decoded. It is what the inspect subcommand prints and what a tool reaches for to decide whether a file is worth loading. It is read from the tail, so it costs a header read plus a footer read regardless of file size.

func InspectBytes 

func InspectBytes(b []byte) (*Inspect, error)

InspectBytes builds an Inspect from a whole file in memory. It verifies the header and footer checksums but does not touch the column pages.

func (*Inspect) String 

func (ins *Inspect) String() string

String renders the inspect summary as a stable, human-readable block.

type Manifest 

type Manifest struct {
	Entries []ManifestEntry
}

Manifest is the parsed catalog: the partition entries sorted by HostKeyLo so a route is a binary search.

func BuildManifest 

func BuildManifest(entries []ManifestEntry) *Manifest

BuildManifest assembles a manifest from entries, sorting by HostKeyLo so the route lookup is a binary search and the ranges read in order.

func DecodeManifest 

func DecodeManifest(b []byte) (*Manifest, error)

DecodeManifest parses what EncodeManifest wrote, verifying the magic at both ends and the body CRC. The entries are returned in their written (sorted) order, so Route works without a re-sort.

func (*Manifest) CoverageGap 

func (m *Manifest) CoverageGap(epoch uint32) (lo, hi uint64, ok bool)

CoverageGap returns the first HostKey range gap or overlap in the manifest within one epoch, or ok=false when the entries tile [0, 2^64) cleanly. The ranges must partition the space with no gap and no overlap (doc 10 section 11, D14), and this is the check a control plane runs before trusting the map.

func (*Manifest) DueParts 

func (m *Manifest) DueParts(now uint32) []ManifestEntry

DueParts returns the partitions with due work at or before now: those whose DueMin is nonzero and not in the future. This is the fleet-level pushdown of doc 10 section 9 lifted to partitions, reading only the manifest.

func (*Manifest) Route 

func (m *Manifest) Route(hk uint64) (ManifestEntry, bool)

Route returns the partition entry whose [HostKeyLo, HostKeyHi] contains hk, found by binary search over the sorted ranges. ok is false when no partition owns hk, which a caller treats as a gap in the range coverage.

type ManifestEntry 

type ManifestEntry struct {
	PartitionID  uint32
	FileRef      string // path or object-store key of the .meguri file
	HostKeyLo    uint64
	HostKeyHi    uint64
	URLCount     uint64
	HostCount    uint64
	DueMin       uint32
	BytesPerURL  float32
	FileCRC32C   uint32 // a CRC over the file's footer, a cheap identity check
	CreatedHours uint32
	Epoch        uint32
}

ManifestEntry is one partition's row in the catalog, the durable record of its range, size, and soonest due time pulled from the file's STATS.

func ManifestEntryFor 

func ManifestEntryFor(fileBytes []byte, fileRef string, epoch uint32) (ManifestEntry, error)

ManifestEntryFor builds a manifest entry from a freshly written file's bytes and its storage ref, reading the header and footer once. The epoch tags which partition-map generation the entry belongs to (doc 10 section 11, D14).

type Partition 

type Partition struct {
	ID           uint32
	HostKeyLo    uint64
	HostKeyHi    uint64
	CreatedHours uint32
	DefaultCodec uint8 // CodecNone or CodecZstd; M0 writes RAW pages either way

	URLs    []m.URLRecord
	Hosts   []m.HostRecord
	Strings []byte // arena the URLRef/ETagRef/HostRef/RegistrableRef offsets index

	// StringsAt and StringsSize are the streaming alternative to Strings for the
	// bounded-memory checkpoint (StreamEncodeToFile). When StringsAt is non-nil the
	// encoder reads the [0, StringsSize) string arena from it through a bounded
	// chunk buffer and writes the blob region page by page, so a 100M checkpoint
	// never materializes the whole multi-gigabyte arena in RAM. The streamed pages
	// decode to the same bytes Strings would have framed as one page, so the *Ref
	// offsets are identical. A non-nil StringsAt takes precedence over Strings.
	StringsAt   io.ReaderAt
	StringsSize int64

	// SeenFilter is the optional serialized resident seen-set filter (doc 10
	// section 6, the seen-set filter region). It is the approximate dedup tier
	// (dedup.SeenSet.MarshalFilter) carried across a checkpoint so a reload does
	// not re-add every key; empty means the region is omitted and the filter is
	// rebuilt from the urlkey column on load. The bytes are opaque to the format:
	// the dedup package owns their layout, the format frames them with a CRC.
	SeenFilter []byte

	// BuildSchedule asks Encode to derive and write the schedule index region (doc
	// 10 section 7, the bucketed timing wheel) from the URL rows' next_due. It is
	// off by default so a partition that does not want the wheel stays byte-for-byte
	// the same; a checkpoint that wants a scheduler to find due work without
	// scanning the next_due column sets it. The region is omitted anyway when no row
	// is scheduled.
	BuildSchedule bool

	// MaxPageRows caps how many rows one column page holds. Zero (the default) keeps
	// the M0 behavior of one page per column, so a partition that does not opt in
	// stays byte-for-byte the same and the pinned size baselines do not move. A
	// positive value spills a column past that many rows into successive pages and
	// builds a per-page skip list (doc 10 section 4, the page_index_offset and inline
	// page min/max): each page carries its own zone min/max so a reader prunes at the
	// page level, decompressing only the pages whose range overlaps a predicate
	// rather than the whole column. doc 14 sets the production page size; this is the
	// mechanism it turns on.
	MaxPageRows int

	// BlobFrontCode asks the encoder to front-code the string blob region (Spec 2074
	// M1): each string stored as the shared-prefix length with the previous string
	// in its page plus the literal suffix, ahead of the block codec. Off by default
	// so a partition that does not opt in stays byte-for-byte the same and the pinned
	// size baselines do not move; the live engine's writers set it. The transform is
	// reversed to the exact raw arena on decode, so the *Ref offsets are unchanged.
	BlobFrontCode bool

	Meta map[string]string // optional string metadata, keys sorted on write
}

Partition is the in-memory image of one .meguri file: the URL and host tables plus the shared string arena their *Ref fields point into. It is the unit a checkpoint writes and a load reads. The engine builds one from its live state and hands it to Encode; Decode hands one back on recovery or redistribution.

The caller owns ordering: URLs must be sorted by URLKey big-endian and hosts by HostKey ascending. Encode verifies this rather than sorting, so a buggy caller is caught instead of silently reordering rows the column zone maps and the seen-set assume are sorted.

func Compact 

func Compact(p *Partition) *Partition

Compact rewrites a partition dropping the URL rows whose status is Gone (the crawl has confirmed they no longer exist, doc 03) and reclaiming the string arena to only the spans the surviving rows still reference. A partition that has accumulated Gone rows and orphaned strings shrinks to exactly its live footprint, which is the garbage collection D11's checkpoint rotation leans on. The result is a fresh Partition; the input is untouched.

func Decode 

func Decode(b []byte) (*Partition, error)

Decode parses a complete .meguri file back into a Partition, verifying the header, footer, region, page, and column checksums along the way.

func Extract 

func Extract(p *Partition, moving map[uint64]bool) (out, rest *Partition)

Extract splits a partition by host membership: out holds exactly the rows of the hosts whose HostKey is in moving, rest holds every other host. Both keep the input's sorted order and each gets its own re-based string arena holding only the spans its rows reference.

This is the rebalance primitive the distribution layer calls with a jump-hash moving set (doc 12, section 3). Unlike Split, which cuts at one HostKey boundary, the moving set is a set of non-contiguous HostKeys, because jump hashing spreads the hosts that remap onto a new partition across the whole key space. Each host's rows are still a contiguous run in the source (the table is sorted by URLKey, so by HostKey first), so the selection is a single pass that copies whole hosts to one side or the other, never splitting a host.

The two results carry the input's id, creation time, and codec; the caller assigns each its destination id and HostKey range as the rebalance needs.

func Merge 

func Merge(a, b *Partition) (*Partition, error)

Merge combines two partitions with disjoint HostKey ranges into one, keeping both tables sorted and the string arena shared. It is the inverse of Split, the rebalance step that folds two small partitions back together. Merge returns ErrNotSorted if the merged URL rows would not be sorted, which catches overlapping or mis-ordered inputs rather than producing a file a reader would reject. The lower-keyed partition's identity and creation time win.

func Pack 

func Pack(id uint32, hostKeyLo, hostKeyHi uint64, createdHours uint32, codec uint8, urls []m.URLRecord, hosts []m.HostRecord, strings []byte) *Partition

Pack builds a Partition from already-sorted records and the shared string arena. It is the in-memory step before Encode: a caller that has live URL and host records hands them here, sets the partition identity, and gets a value ready to serialize. Pack does not sort; it trusts the caller, the same contract Encode keeps, so an unsorted input is caught at Encode.

func Split 

func Split(p *Partition, atHostKey uint64) (lo, hi *Partition)

Split divides a partition into a low half owning HostKeys < atHostKey and a high half owning HostKeys >= atHostKey. Because the URL rows are sorted by URLKey (HostKey high half first) and a host's rows are contiguous, the cut is one boundary in each table, so neither half ever holds part of a host. Each half gets its own re-based string arena holding only the spans its rows reference. The two halves carry the same partition id and creation time as the input; a caller assigns new identities and ranges as the rebalance needs.

type Reader 

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

Reader is a projection-and-pushdown view over a .meguri file. Where Decode materializes every column of every row into full records, a Reader parses the header and footer once and then decodes only the columns a caller asks for, and lets a caller skip the file entirely when the footer's zone maps prove no row can match a predicate (doc 10 section 9, predicate pushdown and projection discipline). This is what keeps a scheduler scan, a dedup rebuild, and a host range read from paying for the 21 columns they do not read.

A Reader holds the file bytes; it does not copy them. The decoded columns it returns are fresh slices.

func NewReader 

func NewReader(b []byte) (*Reader, error)

NewReader parses a .meguri file's header and footer, verifying their checksums, without decoding any column body. It is the cheap open a pushdown query starts from: the zone maps and stats it needs to decide whether to read further all live in the footer.

func (*Reader) ArenaRandReader added in v0.2.0 

func (r *Reader) ArenaRandReader() (*ArenaRandReader, error)

ArenaRandReader opens a random-access reader over the file's string blob, decoding the whole arena up front. A file with no blob region yields a reader that resolves every ref to nil.

func (*Reader) ArenaSeqReader added in v0.2.0 

func (r *Reader) ArenaSeqReader() *ArenaSeqReader

ArenaSeqReader opens a sequential reader over the file's string-blob region. A file with no blob region yields a reader that resolves every ref to nil, matching an empty arena.

func (*Reader) ContainsURL added in v0.2.0 

func (r *Reader) ContainsURL(key m.URLKey) (bool, error)

ContainsURL reports whether key is stored in the partition, the dedup-confirm primitive the file-backed engine runs when its resident filter says "maybe" (spec 2073 doc 08). It is LookupURL stripped to a presence test: it decodes only the two key columns, not the full thirteen-column record, so a confirmation costs a key-column page decode rather than a whole-row projection. The header host range rejects an out-of-partition key in O(1); a multi-page table prunes to the pages whose hostkey zone covers the key and binary-searches each by URLKey; a single-page table decodes its key columns once and binary-searches the set.

func (*Reader) DueByWheel 

func (r *Reader) DueByWheel(now uint32) ([]m.URLKey, error)

DueByWheel returns the URLKeys of every row due at or before now, using the schedule wheel to prune the scan: it reads the wheel's due buckets, then projects the urlkey and next_due columns only for those candidate rows and confirms each against next_due. It falls back to the column-scan DueKeys when the file carries no wheel. This is the schedule-index read path of doc 10 section 7.

func (*Reader) DueCursor added in v0.2.0 

func (r *Reader) DueCursor(now uint32) (*DueCursor, error)

DueCursor opens a bounded due-dispatch scan for the rows due at or before now. When the file's footer proves nothing is due it returns a cursor that yields no batches, the same file-level pushdown DueKeys uses, so a partition with no due work costs no column decode. The next_due, hostkey, and pathkey columns must split on the same page boundaries (they always do, since the encoder pages the URL table uniformly), so a page index lines up across the three.

func (*Reader) DueKeys 

func (r *Reader) DueKeys(now uint32) ([]m.URLKey, error)

DueKeys returns the URLKeys of every row due at or before now, combining the file-level pushdown with a two-column projection: when the footer proves nothing is due it returns nil without decoding a body, otherwise it reads only the urlkey and next_due columns. A due row has a nonzero next_due at or before now (a zero next_due is unscheduled). This is the scheduler's read path made cheap, the worked example of doc 10 section 9.

func (*Reader) DueRange 

func (r *Reader) DueRange() (min, max uint32)

DueRange returns the smallest and largest nonzero next_due across the URL rows, as the footer stats recorded them. A dueMin of 0 means no row is scheduled.

func (*Reader) EnableKeyCache added in v0.2.0 

func (r *Reader) EnableKeyCache(capPages int)

EnableKeyCache installs a decoded key-page cache of capPages pages on the reader, so repeated presence checks into the same pages amortize the decode. capPages <= 0 disables it. It is opt-in because a one-shot scan gains nothing from it and a cache holds decoded pages resident; the live engine turns it on for the probe-stream read path.

func (*Reader) HasSchedule 

func (r *Reader) HasSchedule() bool

HasSchedule reports whether the file carries a schedule index region, the durable timing wheel a scheduler can read instead of scanning the next_due column.

func (*Reader) Header added in v0.2.0 

func (r *Reader) Header() Header

Header returns the file's decoded header: partition id, build time, codec, key range, and row counts. It is the cheap metadata a recovering store reads to rebuild its shell without decoding a single body column.

func (*Reader) HostCount 

func (r *Reader) HostCount() int

func (*Reader) HostKeyRange 

func (r *Reader) HostKeyRange() (lo, hi uint64)

HostKeyRange returns the partition's HostKey bounds from the header, the range a router uses to decide whether this file could own a host at all.

func (*Reader) HostRangePageScan 

func (r *Reader) HostRangePageScan(lo, hi uint64) (scanned, total int)

HostRangePageScan reports how many of the hostkey column's pages a host-range read for [lo, hi] would decode versus the column's total page count, the observable proof that the per-page skip list pruned pages. total is 0 for a single-page column, which carries no skip list to prune.

func (*Reader) HostRangeURLKeys 

func (r *Reader) HostRangeURLKeys(lo, hi uint64) ([]m.URLKey, error)

HostRangeURLKeys returns the URLKeys of every row whose host key falls in [lo, hi], the host range read of doc 10 section 9 sharpened to the page level. When the hostkey column is split across pages (Partition.MaxPageRows opted in), it consults the per-page skip list and decodes only the pages whose zone overlaps [lo, hi], pruning the rest without decompressing them; the pathkey column splits on the same boundaries, so the same page indices line up. A single-page column falls back to a whole-column projection and filter, and a range disjoint from the partition's header bounds returns nil without touching the body. The rows stay in stored order, which is host-key ascending.

func (*Reader) Hosts added in v0.2.0 

func (r *Reader) Hosts() ([]m.HostRecord, error)

Hosts decodes the whole host table into records. The host table is the small region of the file, one row per host rather than per URL, so it is materialized whole where the URL table streams. A recovering engine reads it to rebuild the resident host map from the mapped file without decoding the URL body.

func (*Reader) LookupURL added in v0.2.0 

func (r *Reader) LookupURL(key m.URLKey) (m.URLRecord, bool, error)

LookupURL returns the URL record stored under key, or ok=false when the partition does not hold it. It is the point read the live store needs once the .meguri file is the body store rather than the append log (doc 03 change 3): a GetURL that misses the in-memory tail resolves the base record here by key, with no log byte offset to chase. The lookup is a zone-pruned page search. The header HostKey range rejects an out-of-partition key in O(1). For a multi-page table the hostkey column's per-page skip list narrows the scan to the pages whose zone covers the key's host, and a binary search inside each candidate page finds the row by full URLKey, the rows being stored in URLKey order (the streamed repository's order). A single-page table decodes its columns once and binary-searches the whole set.

func (*Reader) MaybeDueAt 

func (r *Reader) MaybeDueAt(now uint32) bool

MaybeDueAt reports whether any URL could be due at or before now, the file-level pushdown a scheduler uses to skip a partition with no due work without decoding a single column: false means the soonest due time is in the future (or nothing is scheduled), true means the next_due column must be read.

func (*Reader) MaybeOwnsHost 

func (r *Reader) MaybeOwnsHost(hostKey uint64) bool

MaybeOwnsHost reports whether the host could live in this partition, a O(1) pushdown from the header's HostKey range: a false is authoritative (the host is outside the partition's range), a true means the file must be read to confirm. This is the host range read of doc 10 section 9.

func (*Reader) NextDue 

func (r *Reader) NextDue() ([]uint32, error)

NextDue decodes only the next_due column, the next_due-only scan of doc 10 section 9: a scheduler reads the due times without materializing records.

func (*Reader) Schedule 

func (r *Reader) Schedule() (*ScheduleIndex, error)

Schedule decodes the schedule index region into a wheel a scheduler queries with DueBuckets, or returns nil when the file carries no schedule region. It verifies the page CRC. This is the pushdown read for due work: the wheel narrows the scan to the buckets whose window has opened, the next_due column confirms the survivors.

func (*Reader) SeenFilter added in v0.2.0 

func (r *Reader) SeenFilter() ([]byte, error)

SeenFilter returns the serialized resident seen-set filter from the file's seen-set region, or nil if the file has none. It is the bytes dedup.LoadFilter restores, so a recovering engine reloads the approximate dedup tier from the mapped file without re-adding every key (spec 2073 doc 08, the recovery path).

func (*Reader) URLCount 

func (r *Reader) URLCount() int

URLCount and HostCount report the row counts from the header.

func (*Reader) URLKeys 

func (r *Reader) URLKeys() ([]m.URLKey, error)

URLKeys decodes only the two key columns and reconstructs the partition's URLKeys, the urlkey-only dedup projection of doc 10 section 9: a seen-set rebuild reads the keys without paying for status, timestamps, or fingerprints.

func (*Reader) URLRows added in v0.2.0 

func (r *Reader) URLRows() (*URLRowCursor, error)

URLRows opens a sequential row cursor over the file's URL table. A single-page table decodes its columns once on the first Next; a multi-page table decodes a page at a time, so the resident cost is one page regardless of the table size.

func (*Reader) URLZone 

func (r *Reader) URLZone(col int) (min, max uint64, ok bool)

URLZone returns a URL column's zone min/max from the footer directory, the per-column pushdown bound. ok is false for a column with no zone map (a float or opaque-byte column). The column id is one of the ColURL* constants.

type RegionInfo 

type RegionInfo struct {
	ID     uint8
	Name   string
	Offset uint64
	Length uint64
}

RegionInfo is one row of the inspect region table.

type ScheduleIndex 

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

ScheduleIndex is the read view over a schedule region: the wheel base and the row indices grouped by bucket. A scheduler asks it which rows could be due at a given time and confirms the candidates against the next_due column.

func (*ScheduleIndex) Base 

func (s *ScheduleIndex) Base() uint32

Base returns the wheel's base time, the file's earliest nonzero next_due that all bucket windows are measured from.

func (*ScheduleIndex) Covered 

func (s *ScheduleIndex) Covered() uint32

Covered returns the total URL row count the wheel was built over, the denominator for the fraction of rows a due query selects.

func (*ScheduleIndex) DueBuckets 

func (s *ScheduleIndex) DueBuckets(now uint32) []uint32

DueBuckets returns the row indices of every bucket whose window starts at or before now, the wheel's pushdown answer to "what could be due at now". It is a superset of the truly-due rows: a row in the boundary bucket (the one now falls inside) may have a next_due just past now, so a caller confirms each candidate against the next_due column. A now before the base yields nothing, the cheap skip for a file whose soonest work is still in the future.

type Stats 

type Stats struct {
	ScheduledCount    uint64
	DueMin            uint32
	DueMax            uint32
	TotalCompressed   uint64
	TotalUncompressed uint64
	BytesPerURL       float32
}

Stats is the inspect-visible copy of the footer stats block.

type URLRecordSource added in v0.2.0 

type URLRecordSource interface {
	Next() (m.URLRecord, bool)
}

URLRecordSource yields URL records in ascending URLKey order for streaming region encoding. Next returns false once the records are exhausted. The source is pulled one record at a time, so a caller can k-way-merge the store's sorted shards (spec 2072 D9) without ever materializing the whole partition.

type URLRowCursor added in v0.2.0 

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

URLRowCursor streams the URL table of a .meguri file row by row in stored order (URLKey ascending), decoding one page of all columns at a time and yielding its rows before moving to the next page. It is the sequential read the checkpoint needs to source base-record bodies from the prior snapshot: a checkpoint that re-folds the live frontier reads every unchanged record straight off the file in key order, merge-joined against the log tail, instead of a per-key page decode or a random-read gather over the body log (doc 14, the body-ordered store). The transient is one page of records, not the table.

func (*URLRowCursor) Next added in v0.2.0 

func (c *URLRowCursor) Next() (m.URLRecord, bool, error)

Next returns the next URL record in stored order. ok is false at the end of the table.

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.