Documentation
¶
Overview ¶
Package snapshot manages Merkle-based graph snapshots for the knowing knowledge graph.
Each snapshot represents a point-in-time fingerprint of all edges in a repository's graph. The fingerprint is a Merkle root computed by sorting all edge hashes lexicographically and building a binary hash tree. Two snapshots with different roots are guaranteed to have different edge sets, enabling efficient change detection.
Snapshots form a singly-linked chain (each snapshot points to its parent), supporting garbage collection of old snapshots while preserving chain integrity for the most recent N snapshots.
Index ¶
- func DiffMerkle(oldTree, newTree *MerkleTree) (added, removed []types.Hash)
- func SortHashes(hashes []types.Hash)
- type MerkleTree
- type SnapshotManager
- func (sm *SnapshotManager) ComputeSnapshot(ctx context.Context, repoHash types.Hash, commitHash string) (*types.Snapshot, error)
- func (sm *SnapshotManager) Diff(ctx context.Context, oldHash, newHash types.Hash) (*types.DiffResult, error)
- func (sm *SnapshotManager) GarbageCollect(ctx context.Context, repoHash types.Hash, keepCount int) (removed int, err error)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func DiffMerkle ¶
func DiffMerkle(oldTree, newTree *MerkleTree) (added, removed []types.Hash)
DiffMerkle returns the leaf hashes that differ between two Merkle trees. Added are hashes present in newTree but not oldTree. Removed are hashes present in oldTree but not newTree.
func SortHashes ¶
SortHashes sorts a slice of hashes lexicographically using bytes.Compare.
Types ¶
type MerkleTree ¶
type MerkleTree struct {
Root types.Hash // the Merkle root (top of the tree)
Leaves []types.Hash // sorted leaf hashes (the input edge hashes)
}
MerkleTree represents a binary Merkle tree built from sorted hashes. The tree is constructed bottom-up: leaves are sorted edge hashes, and each internal node is SHA-256(left_child || right_child). The root hash uniquely identifies the set of leaves. Comparing two roots in O(1) determines whether the edge sets are identical.
func BuildMerkleTree ¶
func BuildMerkleTree(hashes []types.Hash) *MerkleTree
BuildMerkleTree constructs a binary Merkle tree from a slice of edge hashes. Hashes are sorted lexicographically using bytes.Compare before tree construction. Returns a MerkleTree with the root hash and sorted leaves.
type SnapshotManager ¶
type SnapshotManager struct {
// contains filtered or unexported fields
}
SnapshotManager manages Merkle root computation, snapshot chain maintenance, diff operations, and garbage collection of old snapshots.
func NewSnapshotManager ¶
func NewSnapshotManager(store types.GraphStore) *SnapshotManager
NewSnapshotManager creates a new SnapshotManager backed by the given GraphStore.
func (*SnapshotManager) ComputeSnapshot ¶
func (sm *SnapshotManager) ComputeSnapshot(ctx context.Context, repoHash types.Hash, commitHash string) (*types.Snapshot, error)
ComputeSnapshot computes a new snapshot for a repository by collecting all edge hashes, building a Merkle tree, and storing the resulting snapshot. The snapshot is chained to the latest existing snapshot for the repo.
func (*SnapshotManager) Diff ¶
func (sm *SnapshotManager) Diff(ctx context.Context, oldHash, newHash types.Hash) (*types.DiffResult, error)
Diff returns the structural difference between two snapshots. It delegates to the GraphStore's SnapshotDiff implementation.
func (*SnapshotManager) GarbageCollect ¶
func (sm *SnapshotManager) GarbageCollect(ctx context.Context, repoHash types.Hash, keepCount int) (removed int, err error)
GarbageCollect removes old snapshots for a repo, keeping the most recent keepCount snapshots. It preserves chain integrity by walking the chain from the latest snapshot backwards. Returns the number of removed snapshots.
Source Files