Metadata-Version: 2.4
Name: rottl
Version: 0.0.4
Summary: A high-performance Python library providing bucket-based rotating data structures with approximate TTL eviction and strict memory constraints.
Project-URL: Homepage, https://github.com/sharvul/rottl
Project-URL: Issues, https://github.com/sharvul/rottl/issues
License-Expression: MIT
License-File: LICENSE
Keywords: bloom,bloom-filter,cache,data-structures,rotating,ttl
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Requires-Python: >=3.9
Requires-Dist: rbloom==1.5.4
Description-Content-Type: text/markdown

# RoTTL — Rotating TTL Data Structures
 
RoTTL provides memory-efficient rotating sets, dicts, and Bloom filters with approximate TTL-based eviction.
 
Rather than maintaining per-item expiry timestamps, the TTL window is divided into a fixed number of rotating buckets — expired buckets are evicted as a whole, trading per-item precision for significantly lower memory usage and faster writes, at the cost of sequential bucket scans.
 
The library exposes three structures:
 
- **`RotatingTTLSet`** — a rotating, TTL-based set backed by native Python `set` buckets.
- **`RotatingTTLDict`** — a rotating, TTL-based dict backed by native Python `dict` buckets.
- **`RotatingTTLBloom`** — a rotating, TTL-based Bloom filter backed by [`rbloom`](https://github.com/KenanHanke/rbloom).
 
All three structures rotate automatically based on time and capacity, though capacity tracking differs between implementations:
 
* **`RotatingTTLSet` and `RotatingTTLDict`**: Capacity is checked inline on every insertion via an $O(1)$ `len()` call.
* **`RotatingTTLBloom`**: Estimating the number of unique inserted items requires inspecting filter occupancy by counting set bits — an $O(M)$ operation. To keep the hot path $O(1)$ for the vast majority of insertions, capacity is managed via an **amortized countdown** that defers the check.
 
`RotatingTTLSet` and `RotatingTTLDict` support an optional **history fast-reject** mode, which maintains an auxiliary Bloom filter over all non-expired historical buckets. This allows most negative lookups to be rejected without scanning the full bucket deque, at the cost of filter rebuild on each rotation.
 
---
 
## When to use RoTTL
 
- **Approximate TTL is acceptable.** Expiry happens at bucket boundaries, not per item. Under normal load (no capacity-based eviction), items live between `ttl - (ttl / num_buckets)` and `ttl` seconds. Capacity pressure can cause earlier eviction.
- **Memory-constrained environments.** RoTTL's bucket-level eviction avoids per-item bookkeeping, keeping structure overhead proportional to bucket count rather than item count.
  - `RotatingTTLDict` uses roughly 3–4× less memory than `cachetools.TTLCache`.
- **Write-heavy workloads.** RoTTL's write path is lightweight — no per-item expiry metadata is maintained on insertion.
  - `RotatingTTLDict` is 6–15× faster than `cachetools.TTLCache` on insertions (varies by fast-reject usage and rotation pressure).
- **Lookup performance scales with configuration.** Lookups scan up to `num_buckets` buckets, so with a small bucket count the overhead is negligible. With a large bucket count, hit cost depends on which bucket the item is found in, and miss cost grows linearly. `RotatingTTLSet` and `RotatingTTLDict`'s history fast-reject option makes most miss latency independent of `num_buckets`, at the cost of slower rotations.
 