block_gc

package
v0.52.0 Latest Latest
Warning

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

 Go to latest Published: Jul 2, 2026 License: Apache-2.0 Imports: 20 Imported by: 0

Documentation

Overview

Package block_gc implements garbage collection for Hydra block stores.

The ref graph tracks reference edges using a single gc/ref predicate stored in a KVtx store. Nodes that lose all incoming gc/ref edges are marked unreferenced. The Collector sweeps unreferenced nodes, removing their outgoing edges (which may cascade further orphans), calling the onSwept callback, and physically deleting block-backed nodes via the underlying store.

Content-addressed blocks cannot have reference cycles (hash depends on content which includes refs), so reference counting is sufficient.

Index

Constants

View Source 
const (
	NodeGCRoot       = "gcroot"
	NodeUnreferenced = "unreferenced"
)

Well-known node IRIs (permanent roots).

View Source 
const PredGCRef = "gc/ref"

PredGCRef is the single predicate for all GC reference edges.

Variables

This section is empty.

Functions

func BlockIRI 

func BlockIRI(ref *block.BlockRef) string

BlockIRI returns the IRI for a block reference: "block:{b58hash}".

func BucketFlushTask 

func BucketFlushTask() string

BucketFlushTask returns the runtime trace task name for bucket-level GC flushes.

func BucketIRI 

func BucketIRI(bucketID string) string

BucketIRI returns the IRI for a bucket node: "bucket:{bucketID}".

func IsPermanentRoot 

func IsPermanentRoot(iri string) bool

IsPermanentRoot returns true if the IRI is a well-known permanent root.

func ObjectIRI 

func ObjectIRI(key string) string

ObjectIRI returns "object:{key}" for a world object.

func ParseBlockIRI 

func ParseBlockIRI(iri string) (*block.BlockRef, bool)

ParseBlockIRI parses a "block:{b58}" IRI back to a BlockRef. Returns nil, false if not a valid block IRI.

func ParseBucketIRI 

func ParseBucketIRI(iri string) (string, bool)

ParseBucketIRI parses a "bucket:{id}" IRI back to a bucket ID. Returns the bucket ID and true if valid.

func RegisterEntityChain 

func RegisterEntityChain(ctx context.Context, rg RefGraphOps, nodes ...string) error

RegisterEntityChain registers a chain of gc/ref edges between nodes. Each adjacent pair gets an AddRef call: nodes[0]->nodes[1], nodes[1]->nodes[2], etc. At least 2 nodes required. Idempotent (Cayley ignore_duplicate).

func WorldFlushTask 

func WorldFlushTask() string

WorldFlushTask returns the runtime trace task name for world-local GC flushes.

Types

type Collector 

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

Collector sweeps unreferenced nodes from the ref graph.

Nodes are marked unreferenced by GCStoreOps when they lose all incoming references. Collect iterates unreferenced nodes and deletes them. Deletion cascades: removing a node may orphan its children, which get marked unreferenced for the next iteration.

func NewCollector 

func NewCollector(
	refGraph RefGraphOps,
	store block.StoreOps,
	onSwept func(context.Context, string) error,
) *Collector

NewCollector constructs a new GC collector. The store is the underlying physical store for block deletion. The onSwept callback is optional; if non-nil it is called for each node before physical deletion.

func (*Collector) Collect 

func (c *Collector) Collect(ctx context.Context) (*Stats, error)

Collect sweeps all unreferenced nodes. Loops until no unreferenced nodes remain, since deleting a node may orphan its children.

type CollectorGraph 

type CollectorGraph interface {
	RefGraphOps
	// IterateNodes returns all node IRIs in the node inventory.
	IterateNodes(ctx context.Context) ([]string, error)
	// GetRootNodes returns all node IRIs in the root set.
	GetRootNodes(ctx context.Context) ([]string, error)
	// RemoveRoot removes a node from the root set.
	RemoveRoot(ctx context.Context, iri string) error
	// RemoveNode removes a node from the node inventory.
	RemoveNode(ctx context.Context, iri string) error
}

CollectorGraph is the interface required by the marker and sweep for graph traversal. It extends RefGraphOps with node inventory, root set, and cleanup operations.

type Color 

type Color int

Color represents the tri-color state of a node during marking. 

const (
	// White is the default state. Nodes still white after marking are
	// unreachable and will be swept.
	White Color = iota
	// Grey means the node is known reachable but its outgoing edges have
	// not been scanned yet.
	Grey
	// Black means the node is reachable and fully scanned.
	Black
)

type GCStoreOps 

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

GCStoreOps wraps a StoreOps with GC ref graph tracking.

PutBlock is called from Transaction.Write's concurrent worker goroutines. Since the RefGraph shares the block cursor's mutex, writing to the RefGraph inside those goroutines would deadlock. Instead, GCStoreOps buffers the operations and they are flushed via FlushPending after Transaction.Write returns.

When parentIRI is set, new blocks are tracked under parentIRI instead of the "unreferenced" staging node. This allows bucket-level ownership of blocks.

func NewGCStoreOps 

func NewGCStoreOps(store block.StoreOps, refGraph RefGraphOps) *GCStoreOps

NewGCStoreOps wraps a StoreOps with GC ref graph tracking. New blocks are added under the "unreferenced" staging node.

func NewGCStoreOpsWithParent 

func NewGCStoreOpsWithParent(store block.StoreOps, refGraph RefGraphOps, parentIRI string) *GCStoreOps

NewGCStoreOpsWithParent wraps a StoreOps with GC ref graph tracking using a specific parent IRI. New blocks are tracked under parentIRI instead of the "unreferenced" staging node.

func NewGCStoreOpsWithParentAndTraceTask 

func NewGCStoreOpsWithParentAndTraceTask(store block.StoreOps, refGraph RefGraphOps, parentIRI, flushTask string) *GCStoreOps

NewGCStoreOpsWithParentAndTraceTask wraps a StoreOps with GC ref graph tracking and a specific runtime trace task name for FlushPending.

func NewGCStoreOpsWithTraceTask 

func NewGCStoreOpsWithTraceTask(store block.StoreOps, refGraph RefGraphOps, flushTask string) *GCStoreOps

NewGCStoreOpsWithTraceTask wraps a StoreOps with GC ref graph tracking and a specific runtime trace task name for FlushPending.

func (*GCStoreOps) AddGCRef 

func (g *GCStoreOps) AddGCRef(ctx context.Context, subject, object string) error

AddGCRef adds a gc/ref edge from subject to object and removes the unreferenced edge from the object (it now has a real reference).

func (*GCStoreOps) BeginDeferFlush 

func (g *GCStoreOps) BeginDeferFlush()

BeginDeferFlush enters a deferred-flush scope. While deferred, FlushPending returns immediately without flushing; pending operations accumulate in the buffer. Supports nesting. Also forwards to the inner store so nested GC layers (e.g. bucket-level gcOps inside bucketHandle) are also deferred.

func (*GCStoreOps) BeginReadOperation added in v0.51.7 

func (g *GCStoreOps) BeginReadOperation(ctx context.Context) (block.StoreOps, func(), error)

BeginReadOperation opens a read scope on the inner store.

func (*GCStoreOps) EndDeferFlush 

func (g *GCStoreOps) EndDeferFlush(ctx context.Context) error

EndDeferFlush exits a deferred-flush scope. When the outermost scope ends, calls FlushPending to flush all accumulated operations in one batch. Also forwards to the inner store.

func (*GCStoreOps) FlushPending 

func (g *GCStoreOps) FlushPending(ctx context.Context) error

FlushPending writes all buffered PutBlock operations to the RefGraph, using batched ref graph updates when the implementation supports them. Must be called after Transaction.Write completes and the cursor mutex is no longer held.

When a deferred-flush scope is active (via BeginDeferFlush), returns nil without flushing. The pending operations accumulate and are flushed when EndDeferFlush closes the outermost scope.

func (*GCStoreOps) GetBlock 

func (g *GCStoreOps) GetBlock(ctx context.Context, ref *block.BlockRef) ([]byte, bool, error)

GetBlock gets a block with the given reference.

func (*GCStoreOps) GetBlockExists 

func (g *GCStoreOps) GetBlockExists(ctx context.Context, ref *block.BlockRef) (bool, error)

GetBlockExists checks if a block exists.

func (*GCStoreOps) GetBlockExistsBatch 

func (g *GCStoreOps) GetBlockExistsBatch(ctx context.Context, refs []*block.BlockRef) ([]bool, error)

GetBlockExistsBatch checks whether each block exists.

func (*GCStoreOps) GetHashType 

func (g *GCStoreOps) GetHashType() hash.HashType

GetHashType returns the preferred hash type for the store.

func (*GCStoreOps) GetRefGraph 

func (g *GCStoreOps) GetRefGraph() RefGraphOps

GetRefGraph returns the underlying ref graph.

func (*GCStoreOps) GetStore 

func (g *GCStoreOps) GetStore() block.StoreOps

GetStore returns the underlying store.

func (*GCStoreOps) GetSupportedFeatures 

func (g *GCStoreOps) GetSupportedFeatures() block.StoreFeature

GetSupportedFeatures returns the native feature bitmask for the store.

func (*GCStoreOps) HasWALAppender added in v0.51.7 

func (g *GCStoreOps) HasWALAppender() bool

HasWALAppender returns whether this GC store writes flushes to a WAL.

func (*GCStoreOps) PutBlock 

func (g *GCStoreOps) PutBlock(ctx context.Context, data []byte, opts *block.PutOpts) (*block.BlockRef, bool, error)

PutBlock puts a block into the store and buffers a gc/ref edge for later flush if the block is new. When parentIRI is set, the edge is parentIRI -> block; otherwise unreferenced -> block.

func (*GCStoreOps) PutBlockBatch 

func (g *GCStoreOps) PutBlockBatch(ctx context.Context, entries []*block.PutBatchEntry) error

PutBlockBatch writes a batch of blocks through the inner store and buffers GC ref edges for all new non-tombstone blocks. The inner store decides whether the batch flows through a native path or an internal fallback.

Tombstone entries are handled via GCStoreOps.RmBlock so refgraph cleanup (outgoing edge removal, orphan cascade) is preserved. Non-tombstone entries that already exist in the store are skipped for GC edge buffering to avoid reviving unreferenced edges.

func (*GCStoreOps) RemoveGCRef 

func (g *GCStoreOps) RemoveGCRef(ctx context.Context, subject, object string) error

RemoveGCRef removes a gc/ref edge from subject to object and marks the object as orphaned if it has no remaining incoming references.

func (*GCStoreOps) RmBlock 

func (g *GCStoreOps) RmBlock(ctx context.Context, ref *block.BlockRef) error

RmBlock cleans up the ref graph for a block without performing a physical delete. The Collector handles physical deletion. This removes all outgoing gc/ref edges from the block, removes the parent/unreferenced -> block edge, and cascades orphan detection to any targets that lost their last incoming reference.

When parentIRI is set, the parentIRI -> block edge is buffered as a pending unref removal. When parentIRI is empty, the unreferenced -> block edge is removed directly.

func (*GCStoreOps) SetWALAppender 

func (g *GCStoreOps) SetWALAppender(wal WALAppender)

SetWALAppender sets the WAL appender for deferred ref graph updates. When set, FlushPending writes to the WAL instead of calling ApplyRefBatch on the RefGraph directly.

func (*GCStoreOps) StatBlock 

func (g *GCStoreOps) StatBlock(ctx context.Context, ref *block.BlockRef) (*block.BlockStat, error)

StatBlock returns metadata about a block without reading its data. Returns nil, nil if the block does not exist.

func (*GCStoreOps) Sync added in v0.52.0 

func (g *GCStoreOps) Sync(ctx context.Context) (bool, error)

Sync forwards the durability barrier to the inner store. Applying buffered ref-graph edges stays an explicit FlushPending call, not a Sync side effect, because FlushPending must run with the cursor mutex released.

type Manager 

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

Manager owns the GC graph store and sweep executor lifecycle. It runs startup WAL replay and periodic sweep cycles.

func NewManager 

func NewManager(cfg ManagerConfig) *Manager

NewManager creates a GC manager with the given configuration.

func (*Manager) Run 

func (m *Manager) Run(ctx context.Context) error

Run starts the GC manager lifecycle: startup WAL replay followed by periodic sweep cycles. Blocks until the context is canceled.

type ManagerConfig 

type ManagerConfig struct {
	SweepConfig
	// SweepInterval is the periodic sweep interval. Default 30s.
	SweepInterval time.Duration
	// Maintenance runs after a successful sweep cycle, inside the same
	// maintenance lifecycle.
	Maintenance func(context.Context) error
}

ManagerConfig holds the configuration for a GC manager.

type ManagerHooks 

type ManagerHooks struct {
	Graph       CollectorGraph
	ReplayWAL   WALReplayFunc
	AcquireSTW  STWLockFunc
	Maintenance func(context.Context) error
}

ManagerHooks are the GC manager dependencies supplied by a storage backend. The controller/runtime provides the sweep target and interval.

type Marker 

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

Marker performs an in-memory tri-color mark traversal over a CollectorGraph.

func NewMarker 

func NewMarker(graph CollectorGraph) *Marker

NewMarker creates a Marker for the given graph backend.

func (*Marker) Mark 

func (m *Marker) Mark(ctx context.Context) (sweepCandidates []string, colors map[string]Color, err error)

Mark runs the tri-color mark phase and returns the set of white (unreachable) nodes as sweep candidates. The colors map contains the final state of all nodes for inspection.

type RefEdge 

type RefEdge struct {
	Subject, Object string
}

RefEdge is a subject -> object edge in the GC ref graph.

type RefGraph 

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

RefGraph is a unified reference graph for garbage collection backed by Cayley.

func NewRefGraph 

func NewRefGraph(ctx context.Context, store kvtx.Store, prefix []byte) (*RefGraph, error)

NewRefGraph constructs a RefGraph backed by the given kvtx store. prefix is prepended to all keys (e.g., "gc/" for space context).

func (*RefGraph) AddBlockRef 

func (rg *RefGraph) AddBlockRef(ctx context.Context, source, target *block.BlockRef) error

AddBlockRef adds gc/ref from source block to target block.

func (*RefGraph) AddObjectRoot 

func (rg *RefGraph) AddObjectRoot(ctx context.Context, objectKey string, ref *block.BlockRef) error

AddObjectRoot adds gc/ref from object:{key} to block.

func (*RefGraph) AddRef 

func (rg *RefGraph) AddRef(ctx context.Context, subject, object string) error

AddRef adds a gc/ref edge from subject to object. Idempotent.

func (*RefGraph) ApplyRefBatch 

func (rg *RefGraph) ApplyRefBatch(ctx context.Context, adds, removes []RefEdge) error

ApplyRefBatch applies a batch of ref graph edge additions and removals in a single Cayley transaction.

func (*RefGraph) CloneIRIRefKeys 

func (rg *RefGraph) CloneIRIRefKeys() map[string]any

CloneIRIRefKeys returns a snapshot of the positive IRI ref-key cache.

func (*RefGraph) Close 

func (rg *RefGraph) Close() error

Close closes the underlying graph handle.

func (*RefGraph) GetIncomingRefs 

func (rg *RefGraph) GetIncomingRefs(ctx context.Context, node string) ([]string, error)

GetIncomingRefs returns all sources that have gc/ref edges pointing to the given node.

func (*RefGraph) GetOutgoingRefs 

func (rg *RefGraph) GetOutgoingRefs(ctx context.Context, node string) ([]string, error)

GetOutgoingRefs returns all targets of gc/ref edges from the given node.

func (*RefGraph) GetUnreferencedNodes 

func (rg *RefGraph) GetUnreferencedNodes(ctx context.Context) ([]string, error)

GetUnreferencedNodes returns all nodes that have a gc/ref from "unreferenced".

func (*RefGraph) HasIncomingRefs 

func (rg *RefGraph) HasIncomingRefs(ctx context.Context, node string) (bool, error)

HasIncomingRefs checks if a node has any incoming gc/ref edges. Excludes edges from "unreferenced" (those don't count as real refs).

func (*RefGraph) HasIncomingRefsExcluding 

func (rg *RefGraph) HasIncomingRefsExcluding(
	ctx context.Context,
	node string,
	excluded ...string,
) (bool, error)

HasIncomingRefsExcluding checks if a node has any incoming gc/ref edges. Excludes edges from "unreferenced" and the specified source nodes.

func (*RefGraph) ImportIRIRefKeys 

func (rg *RefGraph) ImportIRIRefKeys(keys map[string]any)

ImportIRIRefKeys seeds the positive IRI ref-key cache.

func (*RefGraph) RemoveNodeRefs 

func (rg *RefGraph) RemoveNodeRefs(ctx context.Context, node string, markOrphaned bool) ([]string, error)

RemoveNodeRefs removes ALL outgoing gc/ref edges for a node. Returns the list of target IRIs that lost an incoming edge. If markOrphaned is true, targets that have no remaining incoming refs (excluding from "unreferenced") get an unreferenced edge.

func (*RefGraph) RemoveObjectRoot 

func (rg *RefGraph) RemoveObjectRoot(ctx context.Context, objectKey string, ref *block.BlockRef) error

RemoveObjectRoot removes gc/ref from object:{key} to block.

func (*RefGraph) RemoveRef 

func (rg *RefGraph) RemoveRef(ctx context.Context, subject, object string) error

RemoveRef removes a single gc/ref edge from subject to object. Removing a non-existent edge is a no-op.

type RefGraphOps 

type RefGraphOps interface {
	// AddRef adds a gc/ref edge from subject to object. Idempotent.
	AddRef(ctx context.Context, subject, object string) error
	// RemoveRef removes a single gc/ref edge from subject to object.
	RemoveRef(ctx context.Context, subject, object string) error
	// ApplyRefBatch applies ref graph edge additions followed by removals.
	// Implementations should batch these operations when possible.
	ApplyRefBatch(ctx context.Context, adds, removes []RefEdge) error
	// RemoveNodeRefs removes all outgoing gc/ref edges for a node.
	// Returns the list of target IRIs that lost an incoming edge.
	// If markOrphaned is true, targets with no remaining incoming
	// refs get an unreferenced edge.
	RemoveNodeRefs(ctx context.Context, node string, markOrphaned bool) ([]string, error)
	// HasIncomingRefs checks if a node has any incoming gc/ref edges.
	// Excludes edges from "unreferenced".
	HasIncomingRefs(ctx context.Context, node string) (bool, error)
	// HasIncomingRefsExcluding checks if a node has any incoming gc/ref edges
	// excluding edges from "unreferenced" and the specified source nodes.
	HasIncomingRefsExcluding(ctx context.Context, node string, excluded ...string) (bool, error)
	// GetOutgoingRefs returns all targets of gc/ref edges from a node.
	GetOutgoingRefs(ctx context.Context, node string) ([]string, error)
	// GetIncomingRefs returns all sources with gc/ref edges to a node.
	GetIncomingRefs(ctx context.Context, node string) ([]string, error)
	// GetUnreferencedNodes returns all nodes linked from "unreferenced".
	GetUnreferencedNodes(ctx context.Context) ([]string, error)
	// AddBlockRef adds gc/ref from source block to target block.
	AddBlockRef(ctx context.Context, source, target *block.BlockRef) error
	// AddObjectRoot adds gc/ref from object:{key} to block.
	AddObjectRoot(ctx context.Context, objectKey string, ref *block.BlockRef) error
	// RemoveObjectRoot removes gc/ref from object:{key} to block.
	RemoveObjectRoot(ctx context.Context, objectKey string, ref *block.BlockRef) error
	// Close closes the ref graph.
	Close() error
}

RefGraphOps is the interface for GC reference graph operations.

type STWLockFunc 

type STWLockFunc func() (release func(), err error)

STWLockFunc acquires the STW lock in exclusive mode and returns a release function.

type Stats 

type Stats struct {
	// NodesSwept is the number of nodes swept.
	NodesSwept int
	// UnreferencedNodeCount is the number of unreferenced node entries read.
	UnreferencedNodeCount int
	// RemoveNodeRefsCount is the number of nodes whose outgoing refs were removed.
	RemoveNodeRefsCount int
	// RemoveUnreferencedEdgeCount is the number of unreferenced marker edges removed.
	RemoveUnreferencedEdgeCount int
	// OnSweptCount is the number of onSwept callbacks run.
	OnSweptCount int
	// RemoveBlockCount is the number of physical block deletes attempted.
	RemoveBlockCount int
	// Duration is how long the GC cycle took.
	Duration time.Duration
	// UnreferencedScanDuration is time spent listing unreferenced nodes.
	UnreferencedScanDuration time.Duration
	// RemoveNodeRefsDuration is time spent removing outgoing node refs.
	RemoveNodeRefsDuration time.Duration
	// RemoveUnreferencedEdgeDuration is time spent removing unreferenced markers.
	RemoveUnreferencedEdgeDuration time.Duration
	// OnSweptDuration is time spent in onSwept callbacks.
	OnSweptDuration time.Duration
	// RemoveBlockDuration is time spent physically deleting block-backed nodes.
	RemoveBlockDuration time.Duration
}

Stats holds GC cycle statistics.

type SweepConfig 

type SweepConfig struct {
	Graph      CollectorGraph
	Target     SweepTarget
	ReplayWAL  WALReplayFunc
	AcquireSTW STWLockFunc
}

SweepConfig holds the dependencies for a sweep cycle.

type SweepResult 

type SweepResult struct {
	WALEntriesPhase1 int
	WALEntriesPhase2 int
	SweepCandidates  int
	Rescued          int
	Swept            int
}

SweepResult holds statistics from a completed sweep cycle.

func SweepCycle 

func SweepCycle(ctx context.Context, cfg SweepConfig) (*SweepResult, error)

SweepCycle runs the full two-phase GC sweep protocol.

Phase 1 (no lock): replay WAL entries into the graph, then run the tri-color marker to get sweep candidates.

Phase 2 (exclusive STW lock): process remaining WAL entries with transitive rescue, then delete sweep candidates from the backend.

type SweepTarget 

type SweepTarget interface {
	// DeleteBlock deletes a block from the block store by its IRI.
	DeleteBlock(ctx context.Context, iri string) error
	// DeleteObject deletes an object key from the object store by its IRI.
	DeleteObject(ctx context.Context, iri string) error
}

SweepTarget provides backend-specific deletion for swept nodes.

type WALAppender 

type WALAppender interface {
	Append(ctx context.Context, adds, removes []RefEdge) error
}

WALAppender appends batched ref graph edge operations to a write-ahead log. When set on GCStoreOps, FlushPending writes to the WAL instead of calling ApplyRefBatch on the RefGraph directly.

type WALReplayFunc 

type WALReplayFunc func(ctx context.Context, graph CollectorGraph) (int, error)

WALReplayFunc reads and applies WAL entries to the graph, returning the count of entries processed. Entries should be deleted eagerly after apply.

Source Files

View all Source files

Directories

Path Synopsis
Package gcgraph implements the GC reference graph on OPFS.
 Package gcgraph implements the GC reference graph on OPFS.
rpc
client
server

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.