Variance Saturation-Governed Cache Eviction: UID Density Replacing Static TTL

Mechanism

The cache holds entries keyed by content identifier. Each entry carries, in addition to its content, a set of lineage edges pointing to the entries from which it was derived and a set of inverse edges pointing to entries that have been derived from it. When a candidate entry is selected for eviction by the cache's replacement policy, the eviction routine does not remove the candidate immediately. Instead, it traverses the inverse edges to enumerate every derivative that depends on the candidate, marks each derivative for invalidation, removes the candidate, and removes the marked derivatives in the same eviction transaction. The transaction is recorded in the eviction audit log with the candidate's identifier, the list of invalidated derivatives, the reason the candidate was selected, and the timestamp.

Lineage edges are established at the moment a derivative is admitted to the cache. The admission routine consults the derivative's manifest, extracts the identifiers of its parents, and writes a forward edge from the derivative to each parent and an inverse edge from each parent to the derivative. The edges are stored in the cache's index alongside the entries themselves, so that the eviction traversal is local to the cache and does not require an external lineage service.

The mechanism produces a deterministic invalidation set. Given the same cache state and the same candidate, every node hosting a replica of the cache will invalidate the same set of derivatives. Determinism is required so that downstream consumers, observing that a derivative is no longer served by one cache, can predict that the same derivative is or will be invalid in every other cache that held the same parent.

Cycles in the lineage graph are precluded by the manifest's content-addressed identifiers: a derivative's identifier is a hash of its content and its parent identifiers, so a derivative cannot list itself or any of its descendants as a parent without producing a hash collision. The eviction traversal therefore terminates after a finite number of steps bounded by the depth of the lineage subtree rooted at the candidate. When the cache holds derivatives whose parents are absent, those derivatives are nonetheless tracked by their forward edges and are correctly invalidated if the parent is later admitted and subsequently evicted, because the inverse-edge construction is symmetric with respect to admission order.

Operating Parameters

The eviction routine is parameterized by the replacement policy that selects candidates, by the maximum cascade depth, and by the audit retention window. The replacement policy may be least-recently-used, least-frequently-used, variance-saturation-governed, or any policy that produces a candidate; the cascade is invariant across choices of policy. The maximum cascade depth bounds the number of derivative generations the eviction traversal will follow; deeper cascades are split into multiple eviction transactions to bound the latency of any single eviction. The audit retention window is bounded below by the longest dispute window for any data class held in the cache.

The audit log is parameterized by visibility and by integrity. Visibility controls which principals may read the log; the default permits any principal who could have read the evicted entry to read its eviction record, ensuring that a consumer who finds a derivative missing can determine whether it was evicted as a cascade from a parent eviction or as a primary candidate. Integrity is enforced by chaining each log entry's hash into the next, so that no eviction record can be removed or altered without invalidating subsequent records.

Performance parameters include the maximum eviction transaction size, the maximum eviction latency budget, and the rate at which evictions may be initiated. Transaction size is bounded so that a single eviction does not stall the cache for an unbounded interval; when a candidate's cascade exceeds the transaction size, the eviction is split, and intermediate states in which some derivatives are invalidated but the parent has not yet been removed are not exposed to readers.

Alternative Embodiments

The eviction mechanism has been reduced to practice in several embodiments. In the synchronous embodiment, the eviction transaction blocks new admissions until it completes; this configuration is suitable for small caches with shallow lineage and produces the strongest consistency guarantee. In the staged embodiment, the eviction marks all candidates and derivatives as invalid in a first pass and removes them in a second pass; the marking is visible to readers immediately, but the storage reclamation is amortized.

A further embodiment uses a write-ahead eviction log: the eviction routine appends the planned transaction to a durable log before performing any in-memory removal, so that a crash during eviction can be recovered to a state in which the transaction either fully completed or did not start. The audit log and the write-ahead log are the same log in this embodiment, with the consequence that successful evictions are auditable without an additional write.

In an embodiment optimized for distributed caches, the eviction is initiated by the node that holds the candidate but the invalidation of derivatives is broadcast to every node that holds any of them. Each receiving node performs the local invalidation and appends to its local audit log; the logs are reconciled by lineage matching rather than by global timestamp, because the lineage edges are content-addressed and therefore identical across nodes.

A tiered embodiment positions a fast cache in front of a slower governed store: evictions from the fast cache do not necessarily invalidate derivatives, because the parent may still be retrievable from the slower store; only when the parent is evicted from the slower store does the cascade propagate to derivatives in the fast cache. The lineage edges are maintained at both tiers, and the audit log records the tier from which the eviction originated, so that consumers can distinguish capacity-driven evictions in the fast tier from authoritative removals in the slower tier. This embodiment supports deployments in which working-set pressure on the fast tier is high but lineage invariants must be preserved across the system as a whole.

Composition

The eviction mechanism composes with the broader content anchoring system by consuming the lineage manifests that the anchoring system attaches to each content unit. The cache does not need to compute lineage; it inherits the lineage from the manifest at admission time and uses it at eviction time. The mechanism composes with the cryptographic governance framework by recording eviction events in an audit log that is itself a governed resource: writes to the log are subject to the framework's admission gates, and the log's contents are visible to governance consumers under the same predicates that govern the cache's underlying content.

Composition with the memory-native protocol is direct. A carrier delivering a derivative to a remote cache carries the derivative's manifest, including its parent identifiers, in its governance section; the receiving cache extracts the parent identifiers and establishes lineage edges before admitting the derivative. When the remote cache later receives an invalidation broadcast for one of those parents, it cascades to the derivative without needing additional information from the sender.

Composition with downstream consumers is enforced by the audit log. A consumer that observes a missing derivative can consult the eviction audit log to determine whether the derivative was evicted, whether the eviction was a cascade, and which parent's eviction caused it. The consumer can then decide whether to request regeneration of the derivative from a still-present ancestor or to treat the absence as authoritative.

Prior Art

Conventional cache replacement policies, including least-recently-used, least-frequently-used, and adaptive replacement, select candidates for eviction based on access patterns but operate on individual entries without regard to lineage. They do not invalidate derivatives when a parent is removed, with the consequence that a cache may continue to serve a derivative whose source is no longer present and cannot be reconstructed. Time-to-live policies expire entries on a fixed schedule but do not propagate expirations along lineage edges; an expired parent does not cause derivatives to expire.

Database invalidation systems propagate updates along foreign-key relationships, but they operate within a transactional engine and depend on the engine's catalog rather than on a content-addressed manifest. They do not produce an audit log that is independently verifiable across substrates, and they do not extend to caches that hold content from multiple producers.

Content delivery network purge mechanisms allow operators to invalidate cached content by URL or by tag, but the tag space is operator-defined rather than content-derived, and the propagation of invalidation is not constrained by a verifiable lineage. The mechanism described here differs by deriving lineage from the content's own manifest and by recording each cascade in an audit log whose entries are chained for tamper-evidence.

Materialized-view maintenance in database systems propagates invalidations from base tables to dependent views, but the dependency graph is fixed by the schema rather than carried with the data, and the invalidation events are not durable across the lifetime of the view; a dropped view leaves no record of which base-table changes had been propagated to it. The eviction mechanism disclosed here keeps the dependency graph in the cache index and records every invalidation in a durable audit log that outlives the entries it concerns, so that downstream consumers can reason about the historical state of the cache long after the entries themselves have been removed.

Reference-counted memory systems remove an object when its count reaches zero but do not propagate removal to objects that were derived from it; a derivative holds its own data and its own count, and the disappearance of its source is not signalled. Garbage-collected systems traverse from roots to live objects but do not produce an audit record of which objects became unreachable as a consequence of which root retraction. The mechanism here is distinct in propagating eviction along derivation edges, in producing a tamper-evident record of each propagation, and in making the propagation visible to consumers outside the cache process.

Disclosure Scope

The disclosure applies to any cache whose entries carry lineage manifests and whose eviction routine traverses lineage edges to invalidate derivatives. The disclosure is not limited to a particular replacement policy, a particular hash function, or a particular storage backend. It specifies that derivatives are invalidated when their parents are evicted, that the cascade is deterministic given the cache state, and that each cascade is recorded in an audit log accessible to consumers; any concrete instantiation of those properties is within scope.

The disclosure further extends to embodiments in which the cache is distributed, in which the cache is layered with other caches under the same lineage protocol, and in which the cache participates in a broader content anchoring system whose anchors are the same hashes used as cache keys. The disclosure covers both the eviction mechanism and the methods by which lineage is established at admission, traversed at eviction, recorded for audit, and reconciled across replicas.