Documentation
¶
Index ¶
- Constants
- Variables
- func BranchSnapshotName(childTableID uint64) string
- func BuildBranchSnapshotDeleteSQL(snames []string) string
- func ComputeBranchReclaimDropList(dag BranchReclaimDag, deadTIDs []uint64) []string
- func ReclaimBranchSnapshotsCore(deadTIDs []uint64, loadDAG func() (BranchReclaimDag, error), ...) error
- type BranchChangeHandle
- type BranchHashmap
- type BranchHashmapOption
- func WithBranchHashmapAllocator(allocator malloc.Allocator) BranchHashmapOption
- func WithBranchHashmapShardCount(shards int) BranchHashmapOption
- func WithBranchHashmapSpillBucketCount(bucketCount int) BranchHashmapOption
- func WithBranchHashmapSpillRoot(root string) BranchHashmapOption
- func WithBranchHashmapSpillSegmentMaxBytes(maxBytes uint64) BranchHashmapOption
- type BranchReclaimDag
- type BranchReclaimNode
- type DataBranchDAG
- func (d *DataBranchDAG) Exists(tableID uint64) bool
- func (d *DataBranchDAG) FindLCA(tableID1, tableID2 uint64) (lcaTableID uint64, childTableID1 uint64, childTableID2 uint64, ok bool)
- func (d *DataBranchDAG) GetCloneTS(tableID uint64) (int64, bool)
- func (d *DataBranchDAG) HasParent(tableID uint64) bool
- func (d *DataBranchDAG) PathFromAncestor(descendantID, ancestorID uint64) (tableIDs []uint64, cloneTSes []int64, ok bool)
- type DataBranchMetadata
- type GetResult
- type ShardCursor
Constants ¶
const BranchSnapshotKind = "branch"
BranchSnapshotKind is the value stored in mo_snapshots.kind for rows that are managed by the data-branch protect-snapshot mechanism. The `kind` column is the single source of truth for "is this snapshot managed by branch".
const BranchSnapshotSnamePrefix = "__mo_branch_"
BranchSnapshotSnamePrefix is the sname prefix used by branch-owned snapshot rows. The suffix is the decimal child table id. Keep this in sync with the design doc §4.3.
Variables ¶
var CollectChanges = func( ctx context.Context, rel engine.Relation, from types.TS, end types.TS, mp *mpool.MPool, ) (engine.ChangesHandle, error) { if end.GE(&from) { handle := &BranchChangeHandle{ snapshotReadPolicy: engine.SnapshotReadPolicyVisibleState, retainRowID: true, } ctx = engine.WithSnapshotReadPolicy(ctx, engine.SnapshotReadPolicyVisibleState) ctx = engine.WithRetainRowID(ctx, true) var err error if handle.handle, err = rel.CollectChanges( ctx, from, end, false, mp, ); err != nil { return nil, err } return handle, nil } return nil, nil }
var CollectChangesWithPKFilter = func( ctx context.Context, rel engine.Relation, from types.TS, end types.TS, mp *mpool.MPool, pkFilter *engine.PKFilter, ) (engine.ChangesHandle, error) { if end.GE(&from) { handle := &BranchChangeHandle{ snapshotReadPolicy: engine.SnapshotReadPolicyVisibleState, retainRowID: true, pkFilter: pkFilter, } ctx = engine.WithSnapshotReadPolicy(ctx, engine.SnapshotReadPolicyVisibleState) ctx = engine.WithRetainRowID(ctx, true) if pkFilter != nil && pkFilter.Valid() { ctx = engine.WithPKFilter(ctx, pkFilter) } var err error if handle.handle, err = rel.CollectChanges( ctx, from, end, false, mp, ); err != nil { return nil, err } return handle, nil } return nil, nil }
CollectChangesWithPKFilter is the same as CollectChanges but additionally attaches a PK filter to the context so that CollectChanges can prune objects and blocks via ZoneMap that do not match the requested PK values. Only DATA BRANCH PICK uses this; other callers use the plain CollectChanges. Row-level PK filtering is handled downstream by the data branch hashmap.
Functions ¶
func BranchSnapshotName ¶
BranchSnapshotName returns the sname used in mo_snapshots for the branch protect snapshot of a child table. Child table ids are cluster-unique, so the name is globally unique without any additional qualifier.
func BuildBranchSnapshotDeleteSQL ¶
BuildBranchSnapshotDeleteSQL returns the DELETE statement that reclaims the given snames from mo_snapshots, or the empty string if there is nothing to drop. The caller is responsible for executing it as sys.
Branch snames are synthesised internally as `__mo_branch_<decimal>` so they cannot contain quote characters in practice. The only "foreign" value in this SQL is thus a known-safe synthesised identifier.
func ComputeBranchReclaimDropList ¶
func ComputeBranchReclaimDropList(dag BranchReclaimDag, deadTIDs []uint64) []string
ComputeBranchReclaimDropList walks the DAG starting from `deadTIDs`, climbing to every ancestor and re-checking subtree-all-deleted. The return value is the (sorted, deduplicated) list of snames that must be removed from mo_snapshots to release protection (§5.3).
Both the ancestor walk (this function) and the subtree check (SubtreeAllDeleted) are cycle-safe — a corrupt `mo_branch_metadata` row that produces a parent-cycle must never hang the drop path.
func ReclaimBranchSnapshotsCore ¶
func ReclaimBranchSnapshotsCore( deadTIDs []uint64, loadDAG func() (BranchReclaimDag, error), execDelete func(snames []string) error, ) error
ReclaimBranchSnapshotsCore runs the shared reclaim algorithm. It is the single source of truth for the "flip table_deleted → compute drop list → delete mo_snapshots rows" pipeline. Both the frontend path (data branch delete) and the compile path (plain DROP TABLE) route through it via the wrapper in their respective packages. Test code can drive it directly by passing mock closures, which is what UT-U5/UT-U6/UT-U7 rely on.
Types ¶
type BranchChangeHandle ¶
type BranchChangeHandle struct {
// contains filtered or unexported fields
}
func (*BranchChangeHandle) Close ¶
func (b *BranchChangeHandle) Close() error
type BranchHashmap ¶
type BranchHashmap interface {
// PutByVectors stores the provided vectors. Each row across the vectors is
// treated as a single record and the columns referenced by keyCols build the key.
PutByVectors(vecs []*vector.Vector, keyCols []int) error
// GetByVectors probes the map using the supplied key vectors and returns one
// GetResult per probed row, preserving the order of the original vectors. The
// returned rows reference the internal storage and must be treated as read-only.
GetByVectors(keyVecs []*vector.Vector) ([]GetResult, error)
// GetByEncodedKey retrieves rows using a pre-encoded key such as one obtained
// from ForEachShardParallel. Returned rows reference internal storage and must
// be treated as read-only.
GetByEncodedKey(encodedKey []byte) (GetResult, error)
// PopByVectors behaves like GetByVectors but removes matching rows from the
// hashmap. When removeAll is true, all rows associated with a key are removed.
// When removeAll is false, only a single row is removed. Returned rows are
// detached copies because the underlying entries have been removed.
PopByVectors(keyVecs []*vector.Vector, removeAll bool) ([]GetResult, error)
// PopByVectorsStream removes rows like PopByVectors but streams each matched
// row to the callback. The callback receives the original key row index plus
// the encoded key/value; the slices are detached copies and safe to keep.
// The returned integer counts removed rows.
PopByVectorsStream(keyVecs []*vector.Vector, removeAll bool, fn func(idx int, key []byte, row []byte) error) (int, error)
// PopByEncodedKey removes rows using a pre-encoded key such as one obtained
// from ForEachShardParallel. It mirrors PopByVectors semantics.
PopByEncodedKey(encodedKey []byte, removeAll bool) (GetResult, error)
// PopByEncodedKeyValue removes rows matching both the encoded key and encoded
// value. When removeAll is true it removes all matching rows, otherwise it
// removes a single row. It returns the number of rows removed.
PopByEncodedKeyValue(encodedKey []byte, encodedValue []byte, removeAll bool) (int, error)
// PopByEncodedFullValue PopByEncodedFullValues removes rows by reconstructing the key from a full
// encoded row payload. The full row must match the value encoding used by
// PutByVectors. It mirrors PopByEncodedKey semantics.
PopByEncodedFullValue(encodedValue []byte, removeAll bool) (GetResult, error)
// PopByEncodedFullValueExact removes rows by matching the full encoded row
// payload, including the value bytes. It mirrors PopByEncodedKeyValue semantics.
PopByEncodedFullValueExact(encodedValue []byte, removeAll bool) (int, error)
// ForEachShardParallel provides exclusive access to each shard. The callback
// receives a cursor offering read-only iteration plus mutation helpers that
// avoid blocking other shards. parallelism <= 0 selects the default value:
// min(runtime.NumCPU(), shardCount), clamped to [1, shardCount].
ForEachShardParallel(fn func(cursor ShardCursor) error, parallelism int) error
// Project rebuilds a new hashmap using the provided keyCols from the current
// rows. parallelism controls shard-level fan-out; see ForEachShardParallel
// for the clamping rules. The returned hashmap owns its own storage and is
// independent from the source.
Project(keyCols []int, parallelism int) (BranchHashmap, error)
// Migrate rebuilds a new hashmap using the provided keyCols while freeing
// rows from the current map during the process. This reduces peak memory
// when Project would duplicate data. parallelism follows ForEachShardParallel
// semantics.
Migrate(keyCols []int, parallelism int) (BranchHashmap, error)
// ItemCount reports the number of rows currently stored in the hashmap.
ItemCount() int64
// ShardCount reports the number of shards in the hashmap.
ShardCount() int
// DecodeRow turns the encoded row emitted by Put/Get/Pop/ForEach back into a
// tuple of column values in the same order that was originally supplied.
DecodeRow(data []byte) (types.Tuple, []types.Type, error)
Close() error
}
BranchHashmap exposes the operations supported by the adaptive hashmap.
func NewBranchHashmap ¶
func NewBranchHashmap(opts ...BranchHashmapOption) (BranchHashmap, error)
NewBranchHashmap constructs a new branchHashmap.
type BranchHashmapOption ¶
type BranchHashmapOption func(*branchHashmap)
BranchHashmapOption configures a branchHashmap instance.
func WithBranchHashmapAllocator ¶
func WithBranchHashmapAllocator(allocator malloc.Allocator) BranchHashmapOption
WithBranchHashmapAllocator overrides the allocator used by branchHashmap.
func WithBranchHashmapShardCount ¶
func WithBranchHashmapShardCount(shards int) BranchHashmapOption
WithBranchHashmapShardCount sets the shard count. Values outside [4, 64] are clamped.
func WithBranchHashmapSpillBucketCount ¶
func WithBranchHashmapSpillBucketCount(bucketCount int) BranchHashmapOption
WithBranchHashmapSpillBucketCount sets the number of spill buckets per shard. The value is rounded up to the next power of two.
func WithBranchHashmapSpillRoot ¶
func WithBranchHashmapSpillRoot(root string) BranchHashmapOption
WithBranchHashmapSpillRoot sets the root directory where spill files will be created.
func WithBranchHashmapSpillSegmentMaxBytes ¶
func WithBranchHashmapSpillSegmentMaxBytes(maxBytes uint64) BranchHashmapOption
WithBranchHashmapSpillSegmentMaxBytes caps the size of each spill file segment.
type BranchReclaimDag ¶
type BranchReclaimDag struct {
Children map[uint64][]uint64
Info map[uint64]BranchReclaimNode
}
BranchReclaimDag is an in-memory picture of mo_branch_metadata suitable for running the reclaim DAG walk. `Children` is an adjacency list keyed on parent table id; `Info` maps every known table id to its metadata row.
It is a distinct, slimmer structure from the LCA-oriented DataBranchDAG defined in branch_dag.go: the reclaim walk only cares about (parent, deleted) and would waste work computing depths or LCA pointers.
func NewBranchReclaimDag ¶
func NewBranchReclaimDag(rows []DataBranchMetadata) BranchReclaimDag
NewBranchReclaimDag builds the reclaim DAG from a flat list of metadata rows (shape shared with NewDAG).
func (BranchReclaimDag) SubtreeAllDeleted ¶
func (d BranchReclaimDag) SubtreeAllDeleted(root uint64) bool
SubtreeAllDeleted returns true iff `root` and every descendant reachable through the DAG have `Deleted == true`. A root that is not in `Info` is treated as "deleted" (i.e. already reclaimable), which matches the dangling-metadata case in the design doc (§9.3.1 UT-U7).
Implementation notes:
- The walk is cycle-safe: a `visited` set prevents infinite recursion if `mo_branch_metadata` is corrupted into a cycle (e.g. A.parent=B, B.parent=A). A revisited node is treated as "still deleted" so the cycle does not starve an otherwise-reclaimable subtree.
- A per-invocation `memo` cache turns the amortised cost from O(N²) to O(N) when the same subtree is evaluated for multiple candidates, which is the common case during cascaded drops.
type BranchReclaimNode ¶
BranchReclaimNode is the per-tid metadata needed by the reclaim walk.
type DataBranchDAG ¶
type DataBranchDAG struct {
// contains filtered or unexported fields
}
func NewDAG ¶
func NewDAG(rows []DataBranchMetadata) *DataBranchDAG
func (*DataBranchDAG) Exists ¶
func (d *DataBranchDAG) Exists(tableID uint64) bool
func (*DataBranchDAG) FindLCA ¶
func (d *DataBranchDAG) FindLCA(tableID1, tableID2 uint64) (lcaTableID uint64, childTableID1 uint64, childTableID2 uint64, ok bool)
FindLCA finds the Lowest Common Ancestor (LCA) for two given table IDs. It returns: 1. lcaTableID: The table_id of the common ancestor. 2. childTableID1: The direct child table of the LCA that is on the path to tableID1. 3. childTableID2: The direct child table of the LCA that is on the path to tableID2. 4. ok: A boolean indicating if a common ancestor was found.
func (*DataBranchDAG) GetCloneTS ¶
func (d *DataBranchDAG) GetCloneTS(tableID uint64) (int64, bool)
func (*DataBranchDAG) HasParent ¶
func (d *DataBranchDAG) HasParent(tableID uint64) bool
func (*DataBranchDAG) PathFromAncestor ¶
func (d *DataBranchDAG) PathFromAncestor(descendantID, ancestorID uint64) ( tableIDs []uint64, cloneTSes []int64, ok bool, )
PathFromAncestor returns the table IDs and clone timestamps along the chain from ancestorID (inclusive) down to descendantID (inclusive). Entries are ordered top-down: result[0] is ancestorID, result[len-1] is descendantID. Returns ok=false if descendantID is not a (possibly transitive) descendant of ancestorID, or if the walk exceeds maxBranchDAGDepth (a defense-in-depth guard against a corrupted DAG with a cycle in Parent pointers).
cloneTSes[0] is ancestorID's own CloneTS (or 0 if ancestorID is a root); cloneTSes[i] for i>0 is the CloneTS of result[i] (i.e. the moment result[i] was forked off result[i-1]).
Used by `data branch diff` to walk every ancestor between the LCA and each endpoint — supporting arbitrary tree depths uniformly.
Example. With the tree
t0
/ | \
t1 t2 t3
| |
t4 t6
/
t9
PathFromAncestor(t9, t0) = ([t0, t1, t4, t9], [<cts>, <cts>, <cts>, <cts>], true) PathFromAncestor(t6, t0) = ([t0, t2, t6], ..., true) PathFromAncestor(t9, t1) = ([t1, t4, t9], ..., true) PathFromAncestor(t9, t6) = (nil, nil, false) // not on the chain
type DataBranchMetadata ¶
type GetResult ¶
type GetResult struct {
// Exists reports whether at least one row matched the probed key.
Exists bool
// Rows contains the encoded payloads for every row that matched the key.
// When obtained via GetByVectors the slices alias the internal storage and
// must be treated as read-only views. Results returned by Pop* are copies.
Rows [][]byte
}
GetResult bundles the original rows associated with a probed key.
type ShardCursor ¶
type ShardCursor interface {
// ShardID returns the zero-based shard identifier.
ShardID() int
// ForEach visits every encoded key stored inside the shard, including rows
// that have spilled to disk. The callback is invoked per entry with a single
// payload row. The provided slices reference internal buffers (or scratch
// copies for spilled data) and are only valid inside the callback.
ForEach(fn func(key []byte, row []byte) error) error
// GetByEncodedKey retrieves rows using a pre-encoded key while the caller
// still owns the iteration lock.
GetByEncodedKey(encodedKey []byte) (GetResult, error)
// PopByEncodedKey removes entries from the shard while the caller still owns
// the iteration lock, ensuring In-shard mutations stay non-blocking.
PopByEncodedKey(encodedKey []byte, removeAll bool) (GetResult, error)
// PopByEncodedKeyValue removes entries matching both key and value while the
// caller still owns the iteration lock.
PopByEncodedKeyValue(encodedKey []byte, encodedValue []byte, removeAll bool) (int, error)
}
ShardCursor exposes shard-scoped helpers when iterating via ForEachShardParallel.