You are tasked with designing and implementing an in-memory,...

Prompt

You are tasked with designing and implementing an in-memory, lock-free (or fine-grained concurrent) LFU (Least Frequently Used) cache with TTL (Time-To-Live) expiration in Rust (using only the standard library). Your response MUST strictly follow these four sections and constraints: 1. ARCHITECTURAL SPECIFICATION (Exactly 3 paragraphs): Explain the data structures used to achieve O(1) time complexity for `get`, `put`, and frequency eviction, and how TTL expiration is handled lazily and/or actively without global locks. Constraint: Do not use the letter "z" (case-insensitive) anywhere in this section. 2. FORMAL INVARIANTS (JSON format): Output a valid, parseable JSON array containing exactly 4 objects. Each object must have the keys: `"invariant_id"`, `"description"`, `"failure_mode"`, and `"time_complexity"`. 3. COMPLETE IMPLEMENTATION (Rust): Write the complete, compilable Rust code for `ConcurrentTtlLfuCache<K, V>`. - Must support `new(capacity: usize)`, `get(&self, key: &K) -> Option<V>`, and `put(&self, key: K, value: V, ttl_ms: u64)`. - When capacity is reached, evict expired items first; if none are expired, evict the least frequently used item (breaking ties by least recently used). - Include zero placeholders, `todo!()`, or unimplemented methods. 4. EDGE CASE TRACE & VERIFICATION (Markdown Table): Trace a sequence of 8 operations on a cache of capacity 2, demonstrating a tie-breaker eviction and a TTL expiration eviction. Columns must be: `Step`, `Operation`, `Timestamp (ms)`, `Cache State (Key: [Val, Freq, Expiry])`, and `Evicted Key`.