Documentation
¶
Overview ¶
Package csrfile defines the on-disk binary format used by GoGraph's Tier 2 (out-of-core, mmap-backed) CSR storage.
The format is stable and versioned; the full specification lives at docs/csrfile-v1.md alongside this repository. Tier 2 readers mmap the file and reinterpret the aligned sections as typed []uint64 slices without parsing.
Example ¶
Example writes a CSR snapshot to an on-disk Tier 2 file and reads it back through the mmap-backed Reader, inspecting the header and the stored edge weights without re-parsing the body.
package main
import (
"fmt"
"os"
"path/filepath"
"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
"github.com/FlavioCFOliveira/GoGraph/graph/csr"
"github.com/FlavioCFOliveira/GoGraph/store/csrfile"
)
func main() {
dir, err := os.MkdirTemp("", "csrfile-example")
if err != nil {
panic(err)
}
defer func() { _ = os.RemoveAll(dir) }()
// Build a small weighted directed graph and freeze it into an
// immutable CSR snapshot.
a := adjlist.New[string, int64](adjlist.Config{Directed: true})
for _, e := range []struct {
src, dst string
w int64
}{
{"a", "b", 10},
{"a", "c", 20},
{"b", "c", 30},
} {
if err := a.AddEdge(e.src, e.dst, e.w); err != nil {
panic(err)
}
}
c := csr.BuildFromAdjList(a)
// Write the CSR to disk; publication is atomic (write .tmp, fsync,
// rename).
path := filepath.Join(dir, "graph.csr")
if _, err := csrfile.WriteToFile(path, c); err != nil {
panic(err)
}
// Open mmaps the file read-only and verifies the header and tail
// CRC. The returned slices alias the mapped region and stay valid
// until Close.
r, err := csrfile.Open(path)
if err != nil {
panic(err)
}
defer func() { _ = r.Close() }()
// NEdges is the live edge count. NVertices is the length of the
// dense vertex-offset (row-pointer) array, which is sized by the
// largest interned NodeID rather than by the number of distinct
// keys, so it is not asserted here; csr.CSR.Order reports the live
// vertex count when that is what you need.
h := r.Header()
fmt.Printf("edges=%d\n", h.NEdges)
weights, ok := r.WeightsUint64()
fmt.Printf("weights present=%t count=%d\n", ok, len(weights))
// The mmapped edge slice has one entry per stored edge.
fmt.Printf("edge slice len=%d\n", len(r.Edges()))
}
Output: edges=3 weights present=true count=3 edge slice len=3
Index ¶
- Constants
- Variables
- func AlignUp(n, alignment uint64) uint64
- func BuildFixture(spec FixtureSpec) (*csr.CSR[struct{}], error)
- func EncodeHeader(h Header) []byte
- func Reinterpret[T any](data []byte, n int) []T
- type AccessPattern
- type File
- type FixtureSpec
- type Header
- type Reader
- func (r *Reader) Close() error
- func (r *Reader) Edges() []graph.NodeID
- func (r *Reader) Header() Header
- func (r *Reader) Read(fn func(vertices []uint64, edges []graph.NodeID, weights []byte) error) error
- func (r *Reader) SetHint(pattern AccessPattern) error
- func (r *Reader) Vertices() []uint64
- func (r *Reader) WeightsFloat64() ([]float64, bool)
- func (r *Reader) WeightsRaw() []byte
- func (r *Reader) WeightsUint64() ([]uint64, bool)
- type WeightKind
Examples ¶
Constants ¶
const Alignment = 64
Alignment is the section alignment in bytes; every typed section starts at an offset that is a multiple of this value.
const CurrentVersion uint16 = 1
CurrentVersion is the format version emitted by this build.
const HeaderSize = 64
HeaderSize is the fixed byte length of the file header.
Variables ¶
var ( // ErrBadMagic indicates the first four bytes are not Magic. ErrBadMagic = errors.New("csrfile: bad magic") // ErrUnsupportedVersion indicates a newer-than-build version. ErrUnsupportedVersion = errors.New("csrfile: unsupported version") // ErrUnsupportedByteOrder indicates a non-little-endian file. ErrUnsupportedByteOrder = errors.New("csrfile: unsupported byte order") // ErrUnknownWeightKind indicates an out-of-range WeightKind. ErrUnknownWeightKind = errors.New("csrfile: unknown weight kind") // ErrFileCorrupted indicates the tail CRC32C check failed. ErrFileCorrupted = errors.New("csrfile: file corrupted") // ErrHeaderTooShort indicates a short read while parsing the header. ErrHeaderTooShort = errors.New("csrfile: header too short") // ErrReaderClosed indicates an operation was attempted on a Reader // whose mmap has already been released by [Reader.Close]. ErrReaderClosed = errors.New("csrfile: reader closed") // ErrHeaderInconsistent indicates the decoded header's counts and // offsets do not match the single canonical on-disk layout for // those counts (a malformed, hostile, or overflowing header). It // wraps [ErrFileCorrupted]: errors.Is(err, ErrFileCorrupted) is // true for any structural rejection, so callers that already test // for ErrFileCorrupted keep working. ErrHeaderInconsistent = fmt.Errorf("%w: header layout inconsistent", ErrFileCorrupted) // ErrNotRepresentable indicates an in-memory CSR whose section counts // have no representation in the on-disk format, so [WriteToFile] refuses // it rather than emitting a file it could never read back. // // It is the WRITE-side answer to the condition [Header.validate] answers // with [ErrHeaderInconsistent] on the read side: [Layout] returning a zero // totalBytes. The two are deliberately distinct errors because the two // inputs are — a file that may be corrupt or hostile on one side, the // caller's own oversized CSR on the other, which is not corruption and // must not be reported as it. What the two sides agree on is the VERDICT // (rmp #2744). ErrNotRepresentable = errors.New("csrfile: layout not representable on disk") )
Errors surfaced by the format helpers.
var ErrInvalidFixtureSpec = errors.New("csrfile: invalid fixture spec")
ErrInvalidFixtureSpec reports a FixtureSpec that BuildFixture cannot satisfy. Test for it with errors.Is; the wrapped message names the offending field and its value.
It exists because the specs it now covers used to be answered with a runtime panic and with an interning loop that exhausts memory, under a godoc that told the caller the function could not fail (rmp #2744, found under #2708). BuildFixture is exported, so an embedder reaches both.
var ErrPublishedNotDurable = errors.New("csrfile: published but durability unproven")
ErrPublishedNotDurable reports that the publish RENAME already succeeded — the new generation is visible and the previous one is gone — but the parent directory fsync that makes that rename survive a crash did not.
It exists because the two failure modes were indistinguishable from the caller's side (rmp #2580's sibling, rmp #2581). Every earlier step's failure leaves the previous generation intact and the temp file removed, so an error from WriteToFile read naturally as "not published". A parent-fsync failure returned an error over a state where publication HAD occurred, and a caller that reacted by assuming the old file survived would be wrong.
Wrap-and-return is the deliberate choice among the two shapes prior art takes: RocksDB returns the survivable error (file/filename.cc, v9.7.3), while PostgreSQL escalates a failed fsync to PANIC rather than let a caller carry on (src/backend/storage/file/fd.c, REL_17_STABLE), on the reasoning that a LATER fsync may falsely report success once the kernel has dropped the dirty page. GoGraph is an embedded library and cannot take the process down on its embedder's behalf, so it returns — but it returns something the embedder can TELL APART, and documents that retrying the fsync, or failing the process, are the two sound responses. Treating it as "not published" is not one of them.
Test for it with errors.Is; the underlying filesystem error is wrapped and remains reachable.
var Magic = [4]byte{'G', 'G', 'C', 'S'}
Magic is the 4-byte file identifier: ASCII "GGCS".
Functions ¶
func BuildFixture ¶
func BuildFixture(spec FixtureSpec) (*csr.CSR[struct{}], error)
BuildFixture deterministically builds a CSR snapshot meeting spec. The graph is directed and uses uint32 vertex identifiers; weights are absent (struct{}). Suitable for Tier 2 benchmarks and the crash-recovery harness, where reproducibility matters more than realism.
Failure modes ¶
BuildFixture returns an error wrapping ErrInvalidFixtureSpec, before doing any work, for the two specs it cannot satisfy:
- Edges > 0 while Vertices == 0. There is no vertex an edge can attach to. This case PANICKED with "runtime error: integer divide by zero" until rmp #2744, on the modulo that reduces the generator's output into the vertex range; the godoc that stood here promised the only failure mode was adjlist.ErrShardFull "which cannot be reached", so a caller had no reason to write a recover.
- Vertices > math.MaxUint32. Vertex identifiers are uint32, so a larger vertex set is not representable and the conversion would truncate: at exactly 2^32 the range collapses to zero and divides by zero as above, and just past it the edges would be drawn over a tiny prefix of a vertex set the caller asked to be enormous. Refusing up front also replaces an interning loop that ends in memory exhaustion: interning was measured at ~270 bytes per node at V=4e6, so 2^32 vertices needs on the order of 1.1 TB of heap and cannot complete on any machine GoGraph targets. It was also measured at 232.7 ns per node, but that timing was taken on a host running other work and is indicative only; the memory figure is what makes the case.
Nothing else the type admits is refused. In particular Edges is NOT bounded: a large value is satisfied correctly, merely slowly.
No error can reach the caller from the underlying adjlist.AdjList on the default uncapped configuration: adjlist.AdjList.AddNode never fails, and adjlist.ErrShardFull requires an adjlist.Config.MaxShardCapacity that BuildFixture does not set. Both call sites are checked and wrapped even so, so an adjlist that grows a new failure mode is surfaced rather than dropped.
func EncodeHeader ¶
EncodeHeader writes h into a fresh HeaderSize-byte slice.
func Reinterpret ¶
Reinterpret returns a typed slice of length n that aliases the memory backing data. T must be a fixed-size primitive (or a named alias of one) — int8/int16/int32/int64/uint*/float32/float64 or a type whose layout is identical to one of those. The function panics when data is too short to hold n elements of T or when its alignment is incompatible with T.
Precondition on n: the byte requirement size(T)*n must be representable; n is treated as untrusted. When size(T)*n overflows (or exceeds what a Go slice length can address), the requirement can never be satisfied by any real buffer, so Reinterpret takes the same "data too short" panic path rather than computing a wrapped product and slicing out of bounds. Callers that derive n from a wire- or file-encoded value therefore get a deterministic, guarded failure instead of an out-of-bounds read.
Because the returned slice aliases data's memory, callers must preserve the data buffer's lifetime for the duration they hold the returned slice, and must not mutate it through the returned slice in ways that would surprise other readers. Typical use: re-typing the body of a memory-mapped region as a []uint64 view.
This helper is unsafe in the Go-language sense (it uses unsafe.Pointer and unsafe.Slice); the project policy for unsafe usage is documented in CONTRIBUTING.md.
Types ¶
type AccessPattern ¶
type AccessPattern uint8
AccessPattern is the advisory hint given to the OS about the expected memory-access pattern of a mapped section. It is an immutable scalar with no methods, taken by value by Reader.SetHint, so it is safe for concurrent use.
const ( AccessDefault AccessPattern = iota AccessSequential AccessRandom AccessWillNeed AccessDontNeed )
Supported access patterns.
type File ¶ added in v0.6.0
type File interface {
io.Writer
// Truncate resizes the open file to size bytes.
//
// It is on the HANDLE rather than on the path (where csrfile called
// os.Truncate until rmp #2580) because a path-based resize moments after the
// create is a TOCTOU window on a name an attacker controls: the temp name is
// OutputPath + ".tmp" and therefore fully predictable. Operating on the
// descriptor the create returned removes the second name resolution, so
// nothing can be swapped in between the two calls.
Truncate(size int64) error
Sync() error
Close() error
}
File is the minimal open-file handle the csrfile writer needs. *os.File satisfies it directly, and the in-memory DST backend supplies an equivalent handle, so the same write path serves both without a branch.
It is exported so an external filesystem backend (the deterministic- simulation harness) can name it as the return type of its Create method and thereby satisfy the unexported [fs] interface; production code never references it directly.
Concurrency: a File is used by a single writer goroutine for the duration of one WriteToFile call and is not safe for concurrent use; the concurrency guarantees of any implementation are the implementation's own.
type FixtureSpec ¶
type FixtureSpec struct {
// Vertices is the number of pre-interned vertex IDs. Identifiers are
// uint32, so Vertices must not exceed [math.MaxUint32]; a larger value is
// refused with [ErrInvalidFixtureSpec] rather than silently truncated.
Vertices uint64
// Edges is the number of edges to add (uniformly random
// (src, dst) over [0, Vertices)). Edges must be zero when Vertices is
// zero — there is no endpoint to draw — and is otherwise unbounded.
Edges uint64
// Seed is the PCG seed (any uint64).
Seed uint64
// Multigraph allows parallel edges; without it duplicates are
// silently collapsed.
Multigraph bool
}
FixtureSpec parameterises BuildFixture. The same seed produces the same graph every time, making the harness deterministic.
FixtureSpec holds only scalars and is taken by value; BuildFixture seeds a fresh generator per call from Seed and shares no state between calls, so one spec may drive any number of concurrent builds and each independently produces the same graph.
type Header ¶
type Header struct {
Version uint16
Alignment uint8
// NVertices is the number of uint64 entries in the vertices section — the
// CSR offsets array — which under that convention is MaxNodeID+1.
//
// It is NOT a count of distinct vertices, and the difference is large rather
// than off-by-one: measured on a graph with 4 distinct vertices and 4 edges,
// NVertices is 257, because [graph.Mapper] spreads keys across 256 shards and
// the offsets array spans the whole NodeID space including the gaps.
//
// A consumer that wants the NodeID space — the length of any per-vertex array
// indexed by NodeID, such as the slice [search/extern.PageRank] returns — must
// use NVertices-1. Trusting the field name instead is what made
// TestPageRank_LDBCSf10_Soak permanently red from Sprint 65 until rmp #2256.
// The name is kept because it is published API; the contract is stated here.
NVertices uint64
NEdges uint64
Weight WeightKind
VerticesOffset uint64
EdgesOffset uint64
WeightsOffset uint64
TailCRCOffset uint64
}
Header is the in-memory representation of the 64-byte file preamble.
A Header is a plain value, copied by value and immutable once returned by Reader.Header or WriteToFile, so it is safe for concurrent reads by any number of goroutines. It holds no pointers or slices, so there is nothing a reader can alias or mutate.
func DecodeHeader ¶
DecodeHeader parses the first HeaderSize bytes into a Header.
func Layout ¶
func Layout(nVertices, nEdges uint64, weight WeightKind) (header Header, totalBytes uint64)
Layout computes the on-disk byte offsets and total size for a header populated with NVertices, NEdges, and Weight. It returns the header with offsets filled and the total file size including the trailing CRC32C uint32.
All arithmetic is overflow-safe: when NVertices, NEdges, or the derived section sizes would overflow a uint64 (as a hostile or corrupted header can request), Layout returns the zero Header and a zero totalBytes. Callers — both the writer and [Header.validate] — must treat a zero totalBytes as "this header is not representable on disk" and reject it rather than proceeding with bogus offsets.
func WriteToFile ¶
WriteToFile serialises c into the path atomically and durably: data lands in path + ".tmp" first, the temp file's contents are fsync'd, the file is renamed onto path, and finally the PARENT directory is fsync'd so the rename's directory entry survives a crash. Concurrent readers see either the previous file or the new file, never a partial write.
On return with a NIL error the published file's CONTENTS are durable everywhere — the temp file is fsync'd before the rename — and on linux/darwin/freebsd/netbsd/openbsd the rename's DIRECTORY ENTRY is durable too, so the publication survives process crash, host crash and kill -9.
The platform scope of that sentence (rmp #2582) ¶
Outside that build set [parentDirFsync] is an unconditional no-op, so this function performs no barrier after the rename and the durability of the directory ENTRY is not established by anything GoGraph does. What happens to it is then a property of the filesystem, and this godoc deliberately makes no claim either way: the audit that raised this had inferred a Windows answer from the absent barrier rather than measuring one, and found no normative documentation on NTFS journal-commit ordering with respect to MoveFileEx. Stating where the barrier IS is a fact; stating what other platforms do without one would be a guess.
Process crash and kill -9 are unaffected by the platform: the rename is a single kernel operation and survives the death of the process that issued it everywhere.
On return with a NON-NIL error, which of the two states holds depends on the error, and the caller must not guess:
- errors.Is(err, ErrPublishedNotDurable) — the rename SUCCEEDED. The new generation is visible and the previous one is gone; only the parent directory fsync failed, so the rename may not survive a crash. Retry the fsync or fail the process; do NOT assume the previous file survived.
- any other error — nothing was published. The previous generation is intact and the temp file has been removed.
This guarantee matters because WriteToFile is the bulk loader's sole durability mechanism — the bulk path bypasses the WAL, so there is no replay and no later checkpoint of this artefact to recover a lost rename. Without the parent-directory fsync, a crash within the kernel's writeback window after a successful return could lose the rename's directory entry and with it the entire bulk load. The parent fsync is a no-op on platforms without a directory-fsync primitive (Windows); see [parentDirFsync].
W must be one of the supported weight kinds, which are the same set store/snapshot persists so a weight type accepted by one durable path is accepted by the other (rmp #2529):
struct{} unweighted, 0 bytes
int8, uint8, bool 1 byte
int16, uint16 2 bytes
int32, uint32, float32 4 bytes
int, uint, uintptr 8 bytes — see the note below
int64, uint64, float64 8 bytes
Any other type produces an error wrapping ErrUnknownWeightKind and NAMING the type, so the limit is discoverable without reading this list.
A CSR whose section counts have no on-disk representation produces an error wrapping ErrNotRepresentable, and nothing is written. This is unreachable for any CSR that fits in memory — it needs section counts on the order of 2^61 — but it is checked rather than assumed, because Layout requires every caller to check and proceeding would panic rather than write a bad file (rmp #2744); see [layoutForWrite].
int, uint and uintptr are PLATFORM-DEPENDENT widths, persisted at 8 bytes deliberately. They are 8 bytes on every platform GoGraph builds for today and store/snapshot already made this choice, so the two formats agree. The cost is stated rather than hidden: such a file, written on a 64-bit build, would be misread by a 32-bit one. Use an explicitly-sized weight type for a file that must cross word sizes.
func WriteToFileWith ¶ added in v0.6.0
WriteToFileWith is WriteToFile over a caller-supplied filesystem backend. It exists for the deterministic-simulation harness (internal/sim), which passes an in-memory backend so it can crash between any two of the write/fsync/rename/parent-fsync steps and replay the result. The backend parameter type is unexported (mirroring github.com/FlavioCFOliveira/GoGraph/store/wal.OpenWith); production code calls WriteToFile, which supplies the OS backend. Passing the OS backend here is byte-for-byte equivalent to WriteToFile.
type Reader ¶
type Reader struct {
// contains filtered or unexported fields
}
Reader is a read-only, mmap-backed view of a csrfile.
All slices returned by Reader.Vertices / Reader.Edges / Reader.WeightsRaw alias the underlying mmap region — they must not be mutated and remain valid only for as long as the mapping is live. Reader.Close unmaps the region, after which any retained slice is a dangling view into freed memory; reading it is a use-after-unmap fault, not a recoverable Go panic.
Concurrency. A Reader is safe for concurrent use, but a long-lived reader that binds the slices once and iterates them MUST do so inside Reader.Read: Read holds an internal read lock for the whole duration of the callback, and Close blocks until every in-flight Read has returned before it unmaps. Calling the bare accessors (Reader.Vertices etc.) and then iterating outside Read races a concurrent Close and may fault the process; the accessors are retained only for short, non-concurrent inspection.
func Open ¶
Open mmaps path read-only, verifies the header and the tail CRC, and returns a Reader pointing into the mapped region.
func OpenWith ¶ added in v0.6.0
OpenWith opens a csrfile through a caller-supplied filesystem backend. For the production OS backend it is byte-for-byte equivalent to Open (it mmaps the file). For an alternate (in-memory) backend — supplied by the deterministic-simulation harness (internal/sim) — it reads the whole file into an 8-byte-aligned buffer and binds the typed slices off it, because there is no real file to mmap. The backend parameter type is unexported, mirroring github.com/FlavioCFOliveira/GoGraph/store/wal.OpenWith; production code calls Open.
func (*Reader) Close ¶
Close releases the mmap and underlying file. Any slice returned by the Reader becomes invalid.
Close acquires the Reader's write lock, so it blocks until every in-flight Reader.Read has returned before unmapping — no reader can be iterating the mapping at the moment it is released. Close is idempotent: the second and later calls observe the already-released mapping and return nil without unmapping twice. Close is safe to call concurrently from multiple goroutines.
func (*Reader) Edges ¶
Edges returns the edges slice. The returned slice aliases the mmap region and is valid only until Reader.Close; long-lived or concurrent iteration MUST use Reader.Read.
func (*Reader) Read ¶ added in v0.2.0
Read invokes fn with the mmap-aliased vertices, edges and raw weights slices while holding an internal read lock for the whole duration of the call. The lock keeps the mapping live across the entire callback, so fn may safely bind the slices once and iterate them: a concurrent Reader.Close blocks until fn returns before it unmaps, closing the use-after-unmap window that bare accessors plus an external iteration would leave open.
The slices passed to fn alias the read-only mmap region; fn must not mutate them and must not retain them beyond its own return — they are invalid once Read returns. weights is nil when the file is unweighted.
Read returns ErrReaderClosed if the Reader has already been closed; otherwise it returns whatever fn returns. The read lock is released even if fn panics. Read is safe for concurrent use; any number of Read calls run in parallel.
func (*Reader) SetHint ¶
func (r *Reader) SetHint(pattern AccessPattern) error
SetHint applies an OS-level advisory hint to the mapped region describing the expected access pattern. On Linux it issues madvise; on other platforms the call returns nil and is a no-op at the OS level (Go's mmap-go does not expose madvise on every platform).
SetHint holds the read lock across the OS call, so it cannot race a concurrent Reader.Close (which would otherwise unmap the region the madvise syscall is about to touch). It returns ErrReaderClosed if the Reader is already closed. Safe for concurrent use.
func (*Reader) Vertices ¶
Vertices returns the offsets slice. Each entry is the start index in Reader.Edges of that vertex's out-neighbours.
The returned slice aliases the mmap region and is valid only until Reader.Close. A consumer that iterates it concurrently with a possible Close MUST use Reader.Read instead; see the Reader type documentation.
func (*Reader) WeightsFloat64 ¶
WeightsFloat64 returns the weights section as a []float64 when possible.
func (*Reader) WeightsRaw ¶
WeightsRaw returns the raw bytes of the weights section. Use Reader.WeightsUint64 / Reader.WeightsFloat64 for typed views. Returns nil when the file is unweighted. The returned slice aliases the mmap region and is valid only until Reader.Close; long-lived or concurrent iteration MUST use Reader.Read.
func (*Reader) WeightsUint64 ¶
WeightsUint64 returns the weights section as a []uint64 when possible. Returns nil, false when the weight kind is not 8-byte integer.
type WeightKind ¶
type WeightKind uint8
WeightKind tags the on-disk type of the weights section. It is an immutable scalar and its only method, WeightKind.Size, reads nothing but the receiver, so it is safe for concurrent use.
const ( WeightAbsent WeightKind = 0 WeightUint32 WeightKind = 1 WeightUint64 WeightKind = 2 WeightFloat32 WeightKind = 3 WeightFloat64 WeightKind = 4 // WeightUint8 is the 1-byte kind, carrying int8, uint8 and bool. WeightUint8 WeightKind = 5 // WeightUint16 is the 2-byte kind, carrying int16 and uint16. WeightUint16 WeightKind = 6 )
Supported weight kinds.
The wire values are stable and additive: 0-4 are the original set and 5-6 were added by rmp #2529 to reconcile csrfile with the snapshot writer, which already persisted the narrower widths. A file written by an older build therefore reads unchanged, and a file carrying a new kind is refused by an older reader with ErrUnknownWeightKind rather than misread.
func (WeightKind) Size ¶
func (k WeightKind) Size() int
Size returns the byte size of one weight value for k.
Source Files