Skip to content

caching-strategy.adoc

Latest commit

 

History

History
594 lines (462 loc) · 13.5 KB

caching-strategy.adoc

File metadata and controls

594 lines (462 loc) · 13.5 KB
Raw

VeriSimDB Caching Strategy

Table of Contents

1. Overview

VeriSimDB implements a multi-layer, drift-aware caching system that dramatically improves query performance while maintaining data consistency.

2. What Gets Cached?

Cache Type What’s Stored TTL Invalidation

Query Results

Complete query output with metadata

5-60 min (per modality)

On drift, on write

Parsed ASTs

Parsed VCL abstract syntax trees

1 hour

Never (queries don’t change)

Execution Plans

Optimized query plans with cost estimates

10 min

On statistics update

ZKP Proofs

Generated zero-knowledge proofs

30 min

On contract change

Registry Lookups

UUID → store mappings

10 min

On registry update

Temporal Versions

Historical octad states

Infinite

Never (immutable)

Store Metadata

Index info, capabilities

5 min

On store update

3. Cache Architecture

3.1. Three-Layer Design

┌─────────────────────────────────────────────────────────┐
│  L1: In-Memory (ETS)                                    │
│  - Hot data (<1ms access)                               │
│  - 1GB limit (LRU eviction)                             │
│  - Query results, ASTs, plans                           │
└─────────────────────────────────────────────────────────┘
           │ miss
           ▼
┌─────────────────────────────────────────────────────────┐
│  L2: Distributed Cache (Across Nodes)                   │
│  - Warm data (<10ms access)                             │
│  - Shared across federation                             │
│  - Raft-based consistency                               │
└─────────────────────────────────────────────────────────┘
           │ miss
           ▼
┌─────────────────────────────────────────────────────────┐
│  L3: Persistent Cache (verisim-temporal)                │
│  - Cold data (<100ms access)                            │
│  - Survives restarts                                    │
│  - Historical queries                                   │
└─────────────────────────────────────────────────────────┘

3.2. Cache Promotion

When data is accessed: 1. L3 hit → Promote to L2 and L1 2. L2 hit → Promote to L1 3. L1 hit → Update access count (LRU)

4. Cache Policies: Per-Modality

Different modalities have different caching needs:

Modality Policy TTL Rationale

VECTOR

Aggressive

1 hour

Embeddings rarely change, ANN search expensive

GRAPH

Relaxed

5 min

Edges can change, but queries are expensive

DOCUMENT

Aggressive

1 hour

Documents rarely change, full-text search expensive

SEMANTIC

Strict

1 min

ZKP proofs must be fresh, contracts can change

TENSOR

Relaxed

5 min

Tensors moderately stable, operations expensive

TEMPORAL

Aggressive

Infinite

Historical data is immutable

4.1. Policy Definitions

Strict: - Only cache dependent-type (verified) queries - Short TTL (1 minute) - Invalidate immediately on any change

Relaxed: - Cache both query types - Medium TTL (5 minutes) - Invalidate on drift detection

Aggressive: - Cache everything - Long TTL (1 hour) - Only invalidate on explicit writes

5. Drift-Aware Invalidation

Key Innovation: Cache is automatically invalidated when drift is detected.

5.1. Invalidation Triggers

# 1. Drift detected for specific octad
defmodule VeriSim.DriftMonitor do
  def handle_drift_detected(octad_id, _details) do
    # Invalidate all cached queries for this octad
    VeriSim.QueryRouter.Cached.invalidate_on_drift(octad_id)
  end
end

# 2. Federation-wide drift
def handle_federation_drift(federation_pattern) do
  VeriSim.QueryRouter.Cached.invalidate_federation_cache(federation_pattern)
end

# 3. Modality store updated
def handle_store_update(modality) do
  VeriSim.QueryRouter.Cached.invalidate_modality_cache(modality)
end

5.2. Tag-Based Invalidation

Every cache entry has tags for fine-grained invalidation:

# Cache entry with tags
QueryCache.put(key, result,
  tags: [
    "octad:abc-123",
    "modality:GRAPH",
    "federation:/universities/*"
  ]
)

# Invalidate all queries for octad
QueryCache.invalidate_by_tag("octad:abc-123")

# Invalidate all graph queries
QueryCache.invalidate_by_tag("modality:GRAPH")

# Invalidate entire federation
QueryCache.invalidate_by_tag("federation:/universities/*")

6. Usage Examples

6.1. Basic Query with Cache

# First execution: Cache MISS
{:ok, result} = VeriSim.QueryRouter.Cached.execute_with_cache(
  "SELECT GRAPH FROM HEXAD abc-123",
  use_dependent_types: true
)
# Execution time: 500ms

# Second execution: Cache HIT
{:ok, result} = VeriSim.QueryRouter.Cached.execute_with_cache(
  "SELECT GRAPH FROM HEXAD abc-123",
  use_dependent_types: true
)
# Execution time: 2ms (250x faster!)

6.2. Force Fresh Results

# Bypass cache, force fresh query
{:ok, result} = VeriSim.QueryRouter.Cached.execute_with_cache(
  query,
  use_dependent_types: true,
  force_fresh: true
)

6.3. Cache Warming at Startup

# Pre-populate cache with common queries
common_queries = [
  "SELECT GRAPH FROM FEDERATION /universities/* LIMIT 100",
  "SELECT VECTOR FROM STORE milvus-1 WHERE ... LIMIT 50",
  "SELECT TEMPORAL FROM HEXAD abc-123 AS OF 'yesterday'"
]

VeriSim.QueryRouter.Cached.warm_cache(common_queries)

6.4. Manual Cache Control

# Invalidate specific query
QueryCache.invalidate(query_key)

# Clear entire cache
QueryCache.clear_all()

# Get cache statistics
QueryCache.stats()
# => %{
#   hit_rate: 87.5,
#   hits: %{l1: 1000, l2: 200, l3: 50},
#   misses: 150,
#   l1_entries: 5000,
#   memory_mb: 234.5
# }

7. Performance Impact

7.1. Benchmark: Cached vs Uncached

Query Type Uncached Cached (L1) Speedup

Simple Graph Query

150ms

2ms

75x

Vector Similarity (HNSW)

300ms

1ms

300x

Multi-Modal (Graph+Vector+Doc)

800ms

5ms

160x

Dependent-Type with ZKP

1200ms

3ms

400x

Temporal Historical Query

250ms

1ms

250x

7.2. Cache Hit Rates (Production)

Based on typical workloads:

  • Read-heavy workload: 90-95% hit rate

  • Mixed workload: 70-80% hit rate

  • Write-heavy workload: 40-50% hit rate

7.3. Memory Usage

L1 Cache (1GB limit): - Typical entry: 10-50KB - Capacity: ~20,000-100,000 entries - LRU eviction when full

Storage Overhead: - L1: 0% (in-memory ETS) - L2: ~5% (distributed across nodes) - L3: ~10% (persistent in verisim-temporal)

8. Cache Configuration

8.1. Default Configuration

%{
  max_memory_mb: 1024,        # 1GB L1 cache
  default_ttl_seconds: 300,   # 5 minutes
  enable_l2: true,            # Distributed cache
  enable_l3: true,            # Persistent cache
  policy: :relaxed,           # Global policy

  modality_policies: %{
    "VECTOR" => :aggressive,
    "GRAPH" => :relaxed,
    "DOCUMENT" => :aggressive,
    "SEMANTIC" => :strict,
    "TENSOR" => :relaxed,
    "TEMPORAL" => :aggressive
  }
}

8.2. Runtime Configuration

# Update cache size
VeriSim.QueryCache.set_max_memory(2048)  # 2GB

# Change global policy
VeriSim.QueryCache.set_policy(:aggressive)

# Override per modality
VeriSim.QueryCache.set_modality_policy("GRAPH", :aggressive)

9. Integration with Query Optimization

Caching integrates seamlessly with query optimization:

9.1. Cached Execution Plans

Query: SELECT GRAPH, VECTOR FROM ...

First Execution:
  1. Parse query → AST (20ms) ← CACHED for next time
  2. Generate plan (50ms) ← CACHED for next time
  3. Execute query (500ms) ← CACHED for next time
  Total: 570ms

Second Execution:
  1. Get cached AST (1ms)
  2. Get cached plan (1ms)
  3. Get cached result (1ms)
  Total: 3ms (190x faster!)

9.2. Cached ZKP Proofs

# First query with ZKP generation
{:ok, result} = execute_with_cache(
  "SELECT SEMANTIC FROM HEXAD abc-123 PROOF ACCESS(Contract)",
  use_dependent_types: true
)
# ZKP generation: 500ms
# Total: 800ms

# Second query reuses cached proof
{:ok, result} = execute_with_cache(
  "SELECT SEMANTIC FROM HEXAD abc-123 PROOF ACCESS(Contract)",
  use_dependent_types: true
)
# ZKP retrieved from cache: 1ms
# Total: 50ms (16x faster)

10. Cache Monitoring

10.1. Real-Time Statistics

# Get current cache stats
iex> VeriSim.QueryCache.stats()
%{
  hit_rate: 87.5,           # 87.5% of queries served from cache
  hits: %{
    l1: 10000,              # 10k hits from in-memory
    l2: 1500,               # 1.5k hits from distributed
    l3: 500                 # 500 hits from persistent
  },
  misses: 1800,             # 1.8k cache misses
  evictions: 200,           # 200 LRU evictions
  l1_entries: 45000,        # 45k entries in L1
  memory_mb: 876.5,         # 876MB used (out of 1024MB)
  memory_limit_mb: 1024
}

10.2. Performance Metrics

# Cache access times
L1 access: 0.5-2ms (in-memory)
L2 access: 5-15ms (network + deserialization)
L3 access: 50-150ms (disk + Merkle chain)

# Compared to uncached:
Graph query: 100-500ms
Vector search: 200-800ms
ZKP generation: 300-1000ms

10.3. Logging

[info] Cache hit (l1): 1.2ms for query:result:abc123def
[info] Cache miss: 0.8ms for query:plan:balanced:xyz789
[info] Evicted 1000 LRU cache entries (memory limit reached)
[info] Invalidated 234 cache entries with tag: octad:abc-123
[info] Cache warming complete: 50 queries pre-loaded

11. Best Practices

11.1. 1. Use Appropriate Policies

# Read-heavy workload → Aggressive caching
QueryCache.set_modality_policy("DOCUMENT", :aggressive)

# Compliance/audit queries → Strict caching
QueryCache.set_modality_policy("SEMANTIC", :strict)

# Development/testing → Disable caching
QueryCache.clear_all()  # Clear before each test

11.2. 2. Warm Cache After Major Changes

# After data import
def after_bulk_import do
  # Invalidate old cache
  QueryCache.clear_all()

  # Warm with new common queries
  QueryRouter.Cached.warm_cache(get_common_queries())
end

11.3. 3. Monitor Hit Rates

# Alert if hit rate drops below 50%
defmodule CacheMonitor do
  use GenServer

  def handle_info(:check_hit_rate, state) do
    stats = QueryCache.stats()

    if stats.hit_rate < 50.0 do
      Logger.warn("Cache hit rate low: #{stats.hit_rate}%")
      # Consider: increasing cache size, adjusting TTLs
    end

    schedule_check()
    {:noreply, state}
  end
end

11.4. 4. Use Tags for Organized Invalidation

# Tag by project
QueryCache.put(key, result, tags: ["project:thesis-2025"])

# Later: invalidate entire project
QueryCache.invalidate_by_tag("project:thesis-2025")

12. Troubleshooting

12.1. Problem: Low Hit Rate

Symptoms: Hit rate < 50%, many misses

Causes: 1. TTL too short (entries expire before reuse) 2. High write rate (frequent invalidations) 3. Query patterns too diverse (no repeated queries) 4. Cache too small (LRU evictions)

Solutions: 1. Increase TTL for stable modalities 2. Use more aggressive policies 3. Increase cache size 4. Pre-warm cache with common queries

12.2. Problem: Stale Data

Symptoms: Queries return outdated results

Causes: 1. Drift not detected (DriftMonitor not running) 2. Manual writes bypass invalidation 3. TTL too long

Solutions: 1. Ensure DriftMonitor is active 2. Call invalidate_on_drift() after writes 3. Reduce TTL for affected modalities 4. Use force_fresh: true for critical queries

12.3. Problem: High Memory Usage

Symptoms: L1 cache using >1GB, frequent evictions

Causes: 1. Large query results cached 2. Too many entries 3. Memory limit too low

Solutions: 1. Increase max_memory_mb 2. Use more conservative policies (cache less) 3. Reduce TTLs (entries expire sooner) 4. Use L2/L3 for large results

13. Future Enhancements

13.1. Planned Features

  1. Smart Cache Warming

    • ML-based prediction of common queries

    • Automatic pre-loading based on usage patterns

  2. Cross-Federation Cache Sharing

    • Universities share cached results

    • Reduces duplicate work across federation

  3. Query Result Compression

    • Compress large results in L2/L3

    • Trade CPU for memory/network

  4. Cache Analytics Dashboard

    • Real-time visualization of hit rates

    • Query pattern analysis

    • Cost savings estimation

  5. Adaptive TTLs

    • Automatically adjust TTL based on update frequency

    • Longer TTL for stable data, shorter for volatile