Caching Architecture

This document describes the internal architecture of the hbac-rs caching and evaluation pipeline. For a tutorial introduction, see Caching System.

Overview

The caching system is designed for SSSD-like deployments where HBAC rules are periodically fetched from LDAP and evaluated locally. It provides:

• Pluggable sources for fetching rules from any backend
• Composable filters for host-specific rule selection
• Indexed caches with multi-dimensional lookups
• Disk persistence for offline operation
• Incremental updates for minimal network traffic
• A six-layer optimization stack for sub-microsecond evaluation

Pipeline Architecture

graph TD
    A[RuleSource<br/>LDAP, file, or custom backend] --> B[RuleFilter<br/>Applicability filtering]
    B --> C[IndexedCache<br/>Indexed memory + optional disk]
    C --> D[Optimization Stack<br/>Bloom, decision tree, deny index]
    D --> E[Evaluator<br/>Fast HBAC evaluation]

RulePipeline orchestrates these stages. Build one with RulePipeline::builder():

#![allow(unused)]
fn main() {
use hbac_rs::cache::*;

let pipeline = RulePipeline::builder()
    .with_source(Box::new(ldap_source))
    .with_filter(HostFilter::for_host("web01").with_group("webservers"))
    .with_cache(IndexedCache::new())
    .build();
}

Component Design

RuleSource

#![allow(unused)]
fn main() {
pub trait RuleSource {
    fn fetch_all(&mut self) -> Result<Vec<HbacRule>, RuleSourceError>;
    fn fetch_updated_since(&mut self, timestamp: u64) -> Result<Vec<HbacRule>, RuleSourceError>;
    fn is_available(&self) -> bool;
}
}

fetch_updated_since enables incremental updates: the pipeline tracks the last refresh timestamp and only fetches rules modified after that point.

CompositeSource provides fallback: if the primary source is unavailable (is_available() returns false or fetch_all fails), it tries the next source.

flowchart LR
    CS[CompositeSource] --> S1{Source 1<br/>LDAP}
    S1 -->|available| R1[Return rules]
    S1 -->|unavailable / error| S2{Source 2<br/>File}
    S2 -->|available| R2[Return rules]
    S2 -->|unavailable| ERR[RuleSourceError]

RuleFilter

#![allow(unused)]
fn main() {
pub trait RuleFilter {
    fn should_cache(&self, rule: &HbacRule) -> bool;
    fn filter<'a>(&self, rules: &'a [HbacRule]) -> Vec<&'a HbacRule>;
    fn filter_cloned(&self, rules: &[HbacRule]) -> Vec<HbacRule>;
}
}

filter and filter_cloned have default implementations that delegate to should_cache. Override them for batch optimizations.

HostFilter is the most impactful filter. It caches a rule when any of these conditions holds:

flowchart TD
    RULE[Rule] --> C1{host dimension<br/>category=all?}
    C1 -->|yes| CACHE[Cache rule]
    C1 -->|no| C2{host name<br/>in rule's names?}
    C2 -->|yes| CACHE
    C2 -->|no| C3{any host group<br/>overlaps rule's groups?}
    C3 -->|yes| CACHE
    C3 -->|no| SKIP[Skip rule]

This typically reduces the working set by 95-99% in large deployments.

AndFilter and OrFilter compose filters: AndFilter requires all children to accept; OrFilter accepts if any child accepts.

RuleCache and IndexedCache

#![allow(unused)]
fn main() {
pub trait RuleCache {
    fn store(&mut self, rules: Vec<HbacRule>);
    fn get(&self, name: &str) -> Option<&HbacRule>;
    fn get_all(&self) -> Vec<&HbacRule>;
    fn len(&self) -> usize;
    fn clear(&mut self);
    fn stats(&self) -> CacheStats;
}
}

IndexedCache implements RuleCache with multi-dimensional indexes:

flowchart TD
    IC[IndexedCache] --> NM[Name Map<br/>AHashMap name → rule]
    IC --> UI[UserIndex<br/>user/group → rule names]
    IC --> HI[HostIndex<br/>host/group → rule names]
    IC --> CI[CompositeIndex<br/>user+host → rule names]

    Q[find_by_user_and_host] --> UI
    Q --> HI
    UI --> INT[Intersect<br/>candidate sets]
    HI --> INT
    INT --> RS[Small candidate set]

The find_by_user_and_host method intersects user and host candidates to produce a small set of rules that could possibly match, avoiding full scans.

DiskCache (requires the serde feature) wraps a file path and provides flush() to persist rules as JSON. On construction, it loads existing rules from disk if the file exists.

RuleIndex

#![allow(unused)]
fn main() {
pub trait RuleIndex {
    fn index(&mut self, rules: &[HbacRule]);
    fn find_by_user(&self, user_id: &str, user_groups: &[String]) -> Vec<usize>;
    fn find_by_host(&self, host: &str, host_groups: &[String]) -> Vec<usize>;
    fn find_by_service(&self, service: &str, service_groups: &[String]) -> Vec<usize>;
    fn clear(&mut self);
}
}

Each index maps entity names and group names to sets of rule indices. Rules with category=all in the indexed dimension match every query. The index returns rule indices (not rules themselves) – the caller resolves them through the canonical rule slice. Internal maps use AHashMap<Arc<str>, Vec<usize>> for fast non-cryptographic hashing.

Optimization Stack

Evaluations pass through six layers in order. Each layer is skipped if a previous layer already produced a result.

flowchart TD
    REQ[Incoming Request] --> L0{Layer 0<br/>Constant Result?}
    L0 -->|yes| R0[Return stored result]
    L0 -->|no| L1{Layer 1<br/>LRU Cache Hit?}
    L1 -->|hit| R1[Return cached result]
    L1 -->|miss| L2{Layer 2<br/>Bloom Filter}
    L2 -->|definite no-match| R2[Return Deny]
    L2 -->|maybe match| L3{Layer 3<br/>Decision Tree}
    L3 -->|resolved| R3[Return result]
    L3 -->|not available| L4{Layer 4<br/>Deny-Rule Index}
    L4 -->|deny found| R4[Return Deny]
    L4 -->|no deny| L5[Layer 5<br/>Composite Index]
    L5 --> R5[Return result]

    L3 -..->|optional| L6[Layer 6: JIT]

    style L6 stroke-dasharray: 5 5

Layer 0: Constant-Result Fast Path

When the decision tree collapses to a single outcome (e.g., a universal deny rule exists, or a universal allow with no deny rules), the result is stored at build time and returned immediately. Bypasses all other layers.

Layer 1: LRU Memoization Cache

1,024-entry cache keyed by a u64 hash of (user, host, service, groups). Group hashing uses order-independent wrapping addition so that the same set of groups produces the same hash regardless of iteration order. Zero heap allocations per lookup.

Layer 2: Bloom Filter Pre-screening

Fast negative check before full evaluation. Configured for a 1% false positive rate. Effective for non-matching requests when no category=all rules exist. In SSSD deployments where category=all is common, the Bloom filter rarely rejects – but the cost of the check is negligible.

Layer 3: Decision Tree

Rules are compiled into a DecisionNode tree at load time. The tree structure depends on the rule set:

• When a universal allow exists alongside specific deny rules, the tree stores only the deny rules, reducing evaluation from O(n) to O(d) where d is the deny rule count.
• Otherwise, the tree checks dimensions in sequence: user, then host, then service.

Layer 4: Deny-Rule Index

Indexes deny rules by user, host, and service dimensions using AHashMap<Arc<str>, Vec<BitPos>> per dimension. Each deny rule is assigned a BitPos (word index + u64 bitmask). On evaluation, per-dimension inverted indexes produce bitmasks that are ANDed together; any surviving bit indicates a deny match.

flowchart LR
    U[User Candidates<br/>bitmask] --> INT[Bitmask<br/>Intersection]
    H[Host Candidates<br/>bitmask] --> INT
    INT --> SVC{Service<br/>Match?}
    SVC -->|match| DENY[Deny]
    SVC -->|no match| PASS[Pass to next layer]

This narrows the candidate set from potentially hundreds of deny rules to 2-3.

Layer 5: Composite Indexing (Fallback)

When the decision tree is not available (e.g., the rule set does not fit a tree pattern), the evaluator falls back to CompositeIndex for candidate selection. O(1) for category=all dimensions, O(g) for specific entities where g is the group count.

Layer 6: JIT Compilation (optional)

Requires the jit feature flag. Compiles per-rule matching logic to native code. Provides throughput improvement on uncached workloads; no benefit on cached workloads where the LRU already dominates.

See Performance Results for measured impact of each layer.

SSSD Integration Pattern

The SSSD lifecycle has three phases: initialize from the fastest available source, refresh periodically in the background, and evaluate requests on the hot path.

flowchart TD
    subgraph Init["Initialization"]
        START[Start] --> DISK{Disk cache<br/>available?}
        DISK -->|yes| LOAD[Load from disk]
        DISK -->|no| LDAP[Full LDAP sync]
        LOAD --> READY[Pipeline ready]
        LDAP --> READY
    end

    subgraph Refresh["Background Refresh (every 5 min)"]
        TIMER[Timer fires] --> INC[incremental_update]
        INC -->|Ok| LOG[Log updated count]
        INC -->|Err| WARN[Log warning<br/>keep cached rules]
    end

    subgraph Eval["Evaluation (hot path)"]
        REQ[PAM request] --> BUILD[Build HbacRequest]
        BUILD --> PIPE[pipeline.evaluate]
        PIPE --> RESULT[Allow / Deny]
    end

    READY --> TIMER
    READY --> REQ

Initialization

#![allow(unused)]
fn main() {
use hbac_rs::cache::*;

let hostname = get_hostname();
let host_groups = get_host_groups();

let mut pipeline = RulePipeline::builder()
    .with_source(Box::new(ldap_source))
    .with_filter(
        HostFilter::for_host(&hostname)
            .with_groups(host_groups)
    )
    .with_cache(IndexedCache::new())
    .build();

// Try disk cache first, then full LDAP sync
let disk_cache = DiskCache::new("/var/cache/sssd/hbac")?;
let cached_rules: Vec<HbacRule> = disk_cache.get_all().into_iter().cloned().collect();

if !cached_rules.is_empty() {
    pipeline.load(cached_rules);
} else {
    pipeline.refresh()?;
}
}

Periodic Refresh

#![allow(unused)]
fn main() {
use std::time::Duration;

loop {
    std::thread::sleep(Duration::from_secs(300));

    match pipeline.incremental_update() {
        Ok(count) => {
            log::debug!("Updated {} rules", count);
        }
        Err(e) => {
            log::warn!("Incremental update failed: {}", e);
        }
    }
}
}

Evaluation

#![allow(unused)]
fn main() {
use hbac_rs::prelude::*;

let mut subject = Subject::new(username);
subject.roles.extend(groups.iter().cloned());

let request = HbacRequest::new(subject, hostname, service);
let allowed = pipeline.evaluate(&request).is_allowed();
}

Memory Optimization

Host Filtering Impact

Only caching rules applicable to the local host dramatically reduces memory:

Index Overhead

Optimization structures add less than 1% overhead on top of rule storage:

• LRU cache: 1,024 entries at ~64 bytes each
• Bloom filters: ~1 KB per 1,000 rules
• Decision trees: ~0.05 KB per deny rule
• Deny-rule index: ~1 KB per deny rule (bitmap indexes over user/host/service dimensions)

Trade-offs

See Performance Results for measured memory usage, build times, and evaluation latency at each scale.

Monitoring

#![allow(unused)]
fn main() {
let stats = pipeline.stats();

// Expose as metrics
metrics.gauge("hbac.rules.count", stats.rule_count);
metrics.gauge("hbac.cache.memory_bytes", stats.memory_bytes);
metrics.gauge("hbac.cache.hit_rate", stats.hit_rate());

// Log periodic summaries
log::info!(
    "HBAC cache: {} rules, {} bytes, {:.1}% hit rate",
    stats.rule_count,
    stats.memory_bytes,
    stats.hit_rate() * 100.0,
);
}

A sustained low hit rate may indicate excessive request diversity or a misconfigured host filter. A sudden drop in rule_count may signal a broken LDAP connection.

Cache Invalidation

Three approaches, used alone or in combination:

#![allow(unused)]
fn main() {
// Explicit: full reload from source
pipeline.refresh()?;

// Time-based: check staleness
if pipeline.last_update_timestamp() + max_cache_age < current_timestamp_millis() {
    pipeline.refresh()?;
}

// Incremental: fetch only changed rules
pipeline.incremental_update()?;
}

See Also

• Caching System – tutorial introduction
• SSSD Integration – deployment patterns
• Performance Results – benchmark data
• API Reference – complete type listings