Overview
In production caches, keys are rarely independent. A user profile depends on preferences, which depend on feature flags. When a feature flag changes, every downstream key must be invalidated — or you serve stale data. The Causal Dependency Graph tracks these relationships as a DAG (directed acyclic graph) and provides automatic cascade invalidation with a single command.
The graph is stored entirely in-process using two DashMap structures: a forward map (key → dependencies) and a reverse map (key → dependents). All mutations are lock-free at the shard level. Cycle detection runs inline on every add_dependency call via BFS, rejecting edges that would create a cycle before they enter the graph.
Use dependency graphs when your cache keys have causal relationships — when changing key A means key B is now stale. Common patterns: config → computed values, user → session → permissions, product → price → cart totals.
Data Structure
The dependency graph is maintained by two concurrent hash maps that provide O(1) lookups for both forward and reverse traversal.
Both maps are updated atomically on every DEPENDS_ON command. The reverse map enables O(1) lookup of "which keys depend on this key?" — the critical question during cascade invalidation.
DEPENDS_ON Command
Declare that one key depends on another. Cachee validates the edge will not create a cycle before inserting it.
Cycle Detection
Every add_dependency(child, parent) call runs a BFS from child through the forward map to determine whether parent is reachable from child. If reachable, adding the edge parent → child would form a cycle, so the operation is rejected with an error.
Complexity: O(V+E) where V is the number of keys reachable from child and E is the number of edges. In practice, dependency chains are shallow (3–5 levels), so this completes in single-digit microseconds.
Cycle detection runs synchronously on the calling thread. If your graph has thousands of transitive dependencies per key, the BFS adds measurable latency to DEPENDS_ON. For most workloads (<100 transitive deps), this is sub-microsecond.
Cascade Invalidation
When a key is invalidated, invalidate_cascade performs a BFS over the reverse map to find all transitive dependents, then invalidates each one in the underlying cache engine.
get_cascade
Returns the full set of keys that transitively depend on a given key, without invalidating them. Useful for dry-run analysis.
Cascade traversal is O(V+E) over the reverse subgraph. Each invalidated key is deleted from the cache engine via the standard DEL path. The dependency edges themselves are not removed — only the cached values are cleared. This means dependents will be re-populated on the next access and their dependency relationships are preserved.
Configuration
| Parameter | Default | Description |
|---|---|---|
deps.enabled |
false | Enable the dependency graph subsystem. When disabled, DEPENDS_ON commands return an error. |
deps.max_depth |
32 | Maximum allowed depth of dependency chains. BFS stops at this depth during cycle detection and cascade traversal. |
deps.max_dependents |
10000 | Maximum number of reverse dependents per key. Prevents a single key from becoming an invalidation bottleneck. |
deps.cascade_on_expire |
true | When a key expires via TTL, automatically cascade-invalidate its dependents. |
Memory Overhead
The dependency graph maintains two DashMaps. Each edge consumes space in both the forward and reverse maps.
| Keys | Avg Edges/Key | Total Edges | Memory Overhead |
|---|---|---|---|
| 100K | 3 | 300K | ~38 MB |
| 1M | 3 | 3M | ~380 MB |
| 10M | 3 | 30M | ~3.8 GB |
Per-edge overhead is approximately 64 bytes (two String references in HashSets across both maps, plus HashSet bucket overhead). For most workloads, the graph adds less than 5% to total cache memory.
Performance
| Operation | Complexity | Typical Latency |
|---|---|---|
| DEPENDS_ON (with cycle check) | O(V+E) | <5 µs (shallow graphs) |
| GET_CASCADE | O(V+E) | <10 µs (100 dependents) |
| INVALIDATE_CASCADE | O(V+E) + O(V) DELs | ~15 µs (100 dependents) |
| Edge insertion (no cycle) | O(1) amortized | <1 µs |
Without the dependency graph, applications must maintain their own invalidation lists and issue individual DEL commands for each dependent key. This is error-prone (missed dependents = stale data) and slower (N round-trips vs. one INVALIDATE_CASCADE command). The graph trades ~64 bytes per edge for automatic, correct, transitive invalidation.