# Design and Architecture
## Core Concept: Rotating Buckets
Track event counts with fixed memory using time buckets that rotate as time passes.
### The Bucket Array
Picture tracking the last 7 days with 7 buckets:
```
[0] [1] [2] [3] [4] [5] [6]
Today Yesterday 2 days ago 3 days ago 4 days ago 5 days ago 6 days ago
```
Bucket 0 is always "now". Higher indices are older.
Record an event:
```
Before: [3, 5, 2, 1, 0, 4, 8]
After: [4, 5, 2, 1, 0, 4, 8] // bucket[0]++
```
### Time Advances
When a day passes, the window slides forward:
```
Before: [4, 5, 2, 1, 0, 4, 8]
After: [0, 4, 5, 2, 1, 0, 4] // push 0, drop oldest
```
New bucket at index 0, oldest bucket falls off the end. Data older than 7 days disappears—the trade-off for fixed memory.
### Lazy Rotation
Buckets don't rotate automatically. They rotate when accessed (record or query):
1. Calculate rotations needed: `(now - starting_instant) / bucket_duration`
2. If rotations > 0, push zeros to front and drop oldest buckets
3. Update `starting_instant` to reflect current time
This avoids work when the app isn't running.
### Multi-Granularity
One event updates multiple bucket arrays simultaneously:
```
record("app_launch") updates:
Minutes[0]++ (last 60 minutes)
Hours[0]++ (last 24 hours)
Days[0]++ (last 32 days)
Months[0]++ (last 12 months)
```
Query at any granularity without reprocessing. Total cost: 256 buckets × 4 bytes = 1KB per event.
## Data Structures
Four layers build from bucket arrays to full API.
### IntervalCounter
Tracks one time unit (days, hours, etc):
```rust
pub struct IntervalCounter {
buckets: VecDeque<u32>,
bucket_count: usize,
time_unit: TimeUnit,
}
pub enum TimeUnit {
Minutes,
Hours,
Days,
Weeks,
Months, // 30-day approximation
Years, // 365-day approximation
}
```
Operations:
- `record(count)` - add to bucket[0]
- `rotate(n)` - push n zeros, truncate to bucket_count
- `query(range)` - sum/average/count buckets in range
### SingleEventCounter
Bundles all time units for one event:
```rust
pub struct SingleEventCounter {
starting_instant: DateTime<Utc>,
intervals: HashMap<TimeUnit, IntervalCounter>,
first_seen: Option<DateTime<Utc>>,
pending: u32, // For reservation system
}
```
One `record()` updates all intervals. Query any time unit without duplication.
The `starting_instant` anchors all intervals to the same timeline. All counters align to midnight UTC on January 1st of the current year:
```rust
fn synchronized_start() -> DateTime<Utc> {
Utc::now()
.with_month(1).unwrap()
.with_day(1).unwrap()
.date_naive()
.and_hms_opt(0, 0, 0).unwrap()
.and_utc()
}
```
Why? Different events created seconds apart would rotate at different times without synchronization. Aligned start means all events share time boundaries.
### EventStore
Top-level container:
```rust
pub struct EventStore {
inner: Arc<EventStoreInner>,
}
struct EventStoreInner {
events: DashMap<String, Arc<RwLock<SingleEventCounter>>>,
clock: Arc<dyn Clock>,
storage: Option<Arc<dyn Storage>>,
config: StoreConfig,
}
```
Operations:
- `record(event_id)` - get or create counter, record event
- `query(event_id)` - get counter, build query
- `limit()` - build rate limiting constraints
- `persist()` - save dirty events to storage
Thread-safe with internal locking via `DashMap` and `RwLock`. Multiple threads can record and query concurrently.
### Query
Fluent API for querying:
```rust
pub struct Query {
store: Arc<EventStoreInner>,
event_id: String,
}
impl Query {
pub fn last_days(self, n: usize) -> QueryResult { ... }
pub fn last_hours(self, n: usize) -> QueryResult { ... }
pub fn last_seen(self) -> Option<Duration> { ... }
}
pub struct QueryResult {
buckets: Vec<u32>,
}
impl QueryResult {
pub fn sum(self) -> Option<u32> { ... }
pub fn average(self) -> Option<f64> { ... }
pub fn count_nonzero(self) -> Option<usize> { ... }
}
```
Type-driven API guides users to valid operations.
## Recording and Querying
### Record Flow
```
store.record("event")
↓
Get or create SingleEventCounter
↓
For each IntervalCounter:
advance_if_needed(now) // Lazy rotation
record(1) // Increment bucket[0]
↓
Mark event dirty for persistence
```
### Query Flow
```
store.query("event").last_days(7).sum()
↓
Get SingleEventCounter
↓
Select Days interval
↓
advance_if_needed(now) // Rotate before reading
↓
Sum buckets[0..7]
```
### Recording Past Events
Past events go into older buckets based on how far back they occurred:
```rust
store.record_at("event", timestamp)?
```
Algorithm:
1. `advance_if_needed(now)` - brings counter current
2. Calculate bucket index from timestamp to `starting_instant`
3. Increment that bucket
Bucket selection:
- Future events: error (can't record future)
- Same interval: bucket 0 or 1 (depending on which side of instant)
- Past intervals: bucket 1 + rotations
### Time Estimation from Buckets
Queries like `last_seen()` and `first_seen()` estimate when events occurred by examining bucket data.
#### Interval Coverage
Each interval tracks a fixed window. A 45-minute interval covers the last 45 minutes. Events older than this disappear—the trade-off for fixed memory.
When you configure multiple intervals (minutes + hours), three relationships exist:
**Touching intervals** - Complete coverage, no gaps:
```
60 minutes + 24 hours
Minutes cover: 0-60 minutes ago
Hours cover: 0-24 hours ago
Coverage is complete
```
**Overlapping intervals** - Redundant coverage:
```
120 minutes + 24 hours
Minutes cover: 0-120 minutes ago
Hours cover: 0-24 hours ago
Minutes overlap hours from 60-120 minutes
```
**Disjoint intervals** - Gaps in coverage:
```
45 minutes + 24 hours
Minutes cover: 0-45 minutes ago
Hours cover: 0-24 hours ago
Gap: 45-60 minutes tracked by hours only
```
#### Gaps
A gap is a time period covered by a larger interval but not a smaller one.
Events in gaps appear in the coarse bucket (hours) but not the fine bucket (minutes). You know the event exists but have less precision about when it occurred.
When estimating timestamps for gap events, use the gap midpoint:
```rust
// Gap boundaries
let bucket_far_end = time_unit.bucket_start(now, bucket_idx); // Earliest time in bucket
let coverage_end = prev_config.first_moment_ever(interval_start); // Where smaller interval stops
// Estimate at midpoint
let gap_midpoint = bucket_far_end + ((coverage_end - bucket_far_end) / 2);
```
Example: Event 50 minutes ago with 45-minute + 24-hour intervals:
- Not in minutes (50 > 45)
- In hour bucket 0 (0-60 minutes ago)
- Gap is 45-60 minutes
- Estimate: 52.5 minutes ago (midpoint)
#### last_seen Detection
Searches for most recent event, smallest to largest interval:
Algorithm:
1. Check smallest unit (minutes)
- If found: estimate at bucket midpoint (no gap possible)
2. Check next larger unit (hours)
- If found: check if in gap
- Calculate where smaller unit coverage ends
- Map coverage end to bucket index in current unit
- If event bucket ≤ coverage bucket: gap detected
- Estimate at gap midpoint
3. If not in gap: estimate at bucket midpoint
#### first_seen Detection
Searches for oldest event, largest to smallest interval:
Algorithm:
1. Check largest unit
- If found: calculate expected events from smaller unit
- Count events in larger unit's relevant buckets
- Count events in smaller unit (all buckets)
- If larger count > smaller count: gap events exist
- Estimate at gap midpoint between bucket end and coverage end
2. If no gap: estimate at bucket midpoint
3. Continue to smaller units
#### replay_into Conversion
Converts events between configurations, preserving gap events:
Algorithm:
1. Iterate source intervals (smallest to largest)
2. For each interval with a next (larger) interval:
- Create checksum to track expected events
- Transfer all non-zero buckets to target
- Record each transfer in checksum
- Compare actual vs expected in next interval
- Difference reveals gap events
3. Record gap events at gap midpoint
The checksum detects gap events by tracking what the smaller interval should have recorded. Discrepancies reveal events that only the larger interval saw.
#### Why Midpoint Estimates?
Without additional information, the midpoint is the best unbiased estimate for when an event occurred within a time range. Alternative approaches (earliest time, latest time) introduce systematic bias.
## Rate Limiting
### Limiter API
Fluent builder for constraints:
```rust
pub struct Limiter {
store: Arc<EventStoreInner>,
constraints: Vec<Constraint>,
}
pub enum Constraint {
AtMost { event_id: String, limit: u32, window_count: usize, time_unit: TimeUnit },
AtLeast { event_id: String, count: u32, window_count: usize, time_unit: TimeUnit },
Cooldown { event_id: String, duration: Duration },
Within { prerequisite_event: String, duration: Duration },
During { schedule: Schedule },
OutsideOf { schedule: Schedule },
}
```
Methods add constraints to list:
```rust
store.limit()
.at_most("api", 10, TimeUnit::Minutes)
.at_most("api", 100, TimeUnit::Hours)
.check_and_record("api")?
```
Terminal methods evaluate all constraints. First failure short-circuits with error containing:
- Violated constraint
- Retry-after duration (when known)
### Constraint Evaluation
**AtMost**: Query event count. Fail if >= limit. Retry time is one time unit.
**AtLeast**: Query prerequisite count. Fail if < minimum. No retry time (user-dependent).
**Cooldown**: Query last occurrence. Fail if elapsed < duration. Retry time is remaining cooldown.
**Within**: Query prerequisite last occurrence. Fail if never occurred or elapsed > duration. No retry time.
**During/OutsideOf**: Check current time against schedule. Retry time calculated from schedule boundaries.
### Reservation System
Prevent race conditions in concurrent environments:
```rust
let reservation = store.limit()
.at_most("api", 10, TimeUnit::Hours)
.reserve("api")?;
// Do work
match make_api_call() {
Ok(_) => reservation.commit(), // Count this
Err(_) => reservation.cancel(), // Or auto-cancels on drop
}
```
How it works:
1. `reserve()` increments `pending` counter atomically
2. Constraints check `total + pending` instead of just `total`
3. `commit()` decrements `pending`, increments `buckets[0]`
4. `cancel()` (or drop) decrements `pending` without recording
Multiple threads reserving with limit 10: exactly 10 succeed, rest fail immediately. No TOCTOU race.
## Persistence
### Storage Trait
```rust
pub trait Storage: Send + Sync {
fn save(&mut self, key: &str, data: Vec<u8>) -> Result<()>;
fn load(&self, key: &str) -> Result<Option<Vec<u8>>>;
fn list_keys(&self) -> Result<Vec<String>>;
}
```
Simple interface enables many backends: SQLite, JSON files, PostgreSQL, Redis, S3, etc.
### Serialization
All structures support serde:
```rust
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct SingleEventCounter { ... }
```
Internal persistence uses bincode (compact binary format). Users can export with any serde format:
```rust
let events = store.export_all()?;
let json = serde_json::to_string(&events)?;
let msgpack = rmp_serde::to_vec(&events)?;
```
### Dirty Tracking
Store tracks modified events:
```rust
dirty_events: DashSet<String>
```
Recording marks events dirty. `persist()` writes only dirty events, then clears the set.
Recording 1000 events across 10 event IDs: `persist()` writes 10 entries, not 1000.
### On-Demand Loading
Store starts instantly without loading data:
```rust
let store = EventStore::builder()
.with_storage(storage)
.build()?; // Returns immediately
```
Events load from storage on first access (record or query). Subsequent operations use in-memory data.
If you record before loading:
```rust
store.record("event"); // Creates in-memory counter
// Later query loads from storage and merges
let count = store.query("event").last_days(7).sum()?;
```
Merge works because addition is commutative: `memory[i] + loaded[i] = loaded[i] + memory[i]`.
## Merge and Sync
### Merge Semantics
Merge combines counters by adding bucket values:
```rust
store.merge_event("event", remote_counter)?
```
Algorithm:
1. Align buckets to same `starting_instant` (rotate if needed)
2. Add bucket values: `local[i] += remote[i]`
3. Update `first_seen` to earliest timestamp
4. Mark dirty for persistence
Addition is commutative and associative:
- Order doesn't matter: `A + B = B + A`
- Grouping doesn't matter: `(A + B) + C = A + (B + C)`
This enables conflict-free sync across devices without coordination.
### Multi-Device Pattern
```rust
// Device 1 records events
device1.record_count("event", 5);
let dev1_data = device1.export_dirty()?;
// Device 2 records events
device2.record_count("event", 3);
let dev2_data = device2.export_dirty()?;
// Server merges both
server.merge_all(dev1_data)?;
server.merge_all(dev2_data)?;
// Result: 5 + 3 = 8 events
assert_eq!(server.query("event").ever().sum(), Some(8));
```
Works offline. No timestamps required. No conflict resolution logic.
## Performance
### Memory
Per event: 128 buckets × 8 bytes = 1,024 bytes (default config)
Total: N events × 1KB
Bounded memory. Old data drops automatically.
### Recording
**Current event**: O(I) where I = number of intervals (4 by default)
- Direct increment of bucket[0] in each interval
**Past event**: O(R × I) worst case, O(1) amortized
- R = rotations needed (bounded by bucket_count)
- Usually R = 0 (same interval)
### Querying
O(B) where B = buckets queried
Examples:
- `last_days(7)` = sum 7 buckets
- `last_minutes(60)` = sum 60 buckets
Independent of event count. 1 event or 1 million events, same query time.
### Rotation
Lazy rotation amortizes cost:
- No work when time hasn't advanced
- Bounded by bucket_count (won't rotate more than buffer size)
- Shared across all operations in same interval
## Trade-offs
### Precision vs Memory
Bucket granularity determines precision:
- 1-minute buckets: "10 events this minute" (precise)
- 1-day buckets: "10 events today" (less precise within the day)
More buckets = more precision = more memory.
Default config balances precision and memory: 128 buckets tracks from minutes to months.
### Calendar Accuracy vs Simplicity
Months and years use fixed durations:
- Month = 30 days (not 28-31)
- Year = 365 days (not 365-366)
Trade-off: "Last month" means "previous 30 day interval", not "since the 1st". Simpler code, consistent bucket sizes, but not calendar-aligned.
Future versions might add calendar-aware intervals as an option.
### Lossy History
Data older than tracked window disappears:
- Track 7 days: events from 8+ days ago are gone
- Track 1 year: events from 2+ years ago are gone
Trade-off: Fixed memory requires dropping old data. Choose bucket counts based on how far back you need to query.
### Thread Safety Model
`EventStore` is thread-safe via internal locking (`DashMap` + `RwLock`). Multiple threads can record and query concurrently.
Trade-off: Lock contention under high concurrency. Consider batching records or using per-thread stores that merge periodically.
## Testing Strategies
### Time Control
Use `TestClock` for deterministic tests:
```rust
use tiny_counter::TestClock;
let clock = TestClock::build_for_testing();
let store = EventStore::builder()
.with_clock(Arc::new(clock.clone()))
.build()?;
store.record("event");
clock.advance(Duration::days(1));
// Event now in yesterday's bucket
assert_eq!(store.query("event").last_days(1).sum(), Some(0));
assert_eq!(store.query("event").last_days(2).sum(), Some(1));
```
### Property-Based Tests
Test invariants with randomized inputs:
```rust
#[quickcheck]
fn rotation_preserves_bucket_count(rotations: usize) {
let mut counter = IntervalCounter::new(7, TimeUnit::Days);
counter.rotate(rotations);
assert!(counter.buckets.len() <= 7);
}
#[quickcheck]
fn merge_is_commutative(a_count: u32, b_count: u32) {
let mut store1 = EventStore::new();
store1.record_count("event", a_count);
store1.merge_event("event", make_counter(b_count))?;
let mut store2 = EventStore::new();
store2.record_count("event", b_count);
store2.merge_event("event", make_counter(a_count))?;
assert_eq!(
store1.query("event").ever().sum(),
store2.query("event").ever().sum()
);
}
```
### Concurrent Tests
Verify thread safety:
```rust
#[test]
fn concurrent_reservations() {
let store = Arc::new(EventStore::new());
let handles: Vec<_> = (0..100)
.map(|_| {
let store = store.clone();
thread::spawn(move || {
store.limit()
.at_most("api", 10, TimeUnit::Hours)
.reserve("api")
})
})
.collect();
let results: Vec<_> = handles
.into_iter()
.map(|h| h.join().unwrap())
.collect();
// Exactly 10 succeed
assert_eq!(results.iter().filter(|r| r.is_ok()).count(), 10);
}
```
## Architecture Patterns
### Builder Pattern
Complex construction via builder:
```rust
EventStore::builder()
.with_storage(storage)
.with_clock(clock)
.track_minutes(120)
.track_days(90)
.build()?
```
Self-documenting, order-independent methods. Validates configuration before building.
### Type-Driven API
Type system guides usage:
```rust
store.query("event") // Returns Query
.last_days(7) // Returns QueryResult
.sum() // Returns Option<u32>
```
Each type exposes only valid next operations. Invalid chains don't compile.
### Trait-Based Extension
Storage abstraction enables custom backends:
```rust
struct S3Storage { /* ... */ }
impl Storage for S3Storage {
fn save(&mut self, key: &str, data: Vec<u8>) -> Result<()> {
// Upload to S3
}
fn load(&self, key: &str) -> Result<Option<Vec<u8>>> {
// Download from S3
}
fn list_keys(&self) -> Result<Vec<String>> {
// List S3 keys
}
}
```
Application code stays generic over `Storage`.
## Implementation Notes
### Bucket Rotation Algorithm
```rust
pub fn advance_if_needed(&mut self, now: DateTime<Utc>) {
let rotations = self.time_unit.num_rotations(self.starting_instant, now);
if rotations > 0 {
let to_rotate = rotations.min(self.bucket_count);
self.rotate(to_rotate);
self.starting_instant = self.starting_instant
+ self.time_unit.duration() * rotations;
}
}
```
Key points:
- Capped at `bucket_count` (large time jumps don't explode)
- Updates `starting_instant` by full rotations (not to `now`)
- Preserves alignment to synchronized boundaries
### First Seen Tracking
```rust
pub struct SingleEventCounter {
first_seen: Option<DateTime<Utc>>,
// ...
}
```
Tracks earliest event timestamp. Updated on:
- First record (if None)
- Merge (take minimum)
- Load from storage (preserved)
Used for `query().first_seen()` and cohort analysis.
### Pending Counter for Reservations
```rust
pub struct SingleEventCounter {
pending: u32,
// ...
}
```
Tracks reserved but uncommitted events. Rate limiting checks `total + pending` to prevent race conditions.
Operations:
- `increment_pending()` - reservation reserves slot
- `decrement_pending()` - commit or cancel releases slot
- `total_with_pending()` - query includes pending
## Extension Points
### Custom Time Units
Add new intervals:
```rust
impl TimeUnit {
pub fn custom(duration: Duration) -> Self {
TimeUnit::Custom(duration)
}
}
// Use like built-in units
.track_custom(TimeUnit::custom(Duration::hours(6)), 48) // Last 12 days in 6-hour buckets
```
### Custom Aggregations
Extend `QueryResult`:
```rust
impl QueryResult {
pub fn percentile(&self, p: f64) -> Option<u32> {
// Calculate percentile from bucket distribution
}
pub fn stddev(&self) -> Option<f64> {
// Calculate standard deviation
}
}
```
### Custom Constraints
Extend `Constraint` enum:
```rust
pub enum Constraint {
// ... existing variants
Custom {
predicate: Arc<dyn Fn(&EventStore) -> bool + Send + Sync>,
error_msg: String,
},
}
```
Enables arbitrary rate limiting logic while maintaining fluent API.
## Future Directions
### Sparse Storage
Low-frequency events waste memory on zero buckets. Sparse representation could help:
```rust
struct SparseIntervalCounter {
non_zero_buckets: HashMap<usize, u32>,
bucket_count: usize,
}
```
Trade-off: More complex code, but much less memory for sparse events.
### SIMD Aggregations
Query sums iterate buckets sequentially. SIMD could parallelize:
```rust
fn sum_simd(buckets: &[u32]) -> u32 {
// Use SIMD instructions for 2-8x speedup
}
```
Trade-off: Platform-specific code, but significant speedup for large ranges.
### Calendar-Aware Intervals
Current month approximation (28 days) causes drift. Calendar arithmetic would fix:
```rust
enum TimeUnit {
// ... existing variants
CalendarMonths, // True month boundaries
CalendarWeeks, // Monday-Sunday
}
```
Trade-off: More complex rotation logic, but accurate for business requirements.
## Contributing
Key invariants to preserve:
1. **Bucket count**: `buckets.len() <= bucket_count` always
2. **Time monotonic**: `starting_instant` only moves forward
3. **Non-negative counts**: Buckets are `u32`, never negative (max 4.2 billion per bucket)
4. **Lazy consistency**: Rotation on access, never automatic
5. **Commutative merge**: `A + B = B + A` always
Run full test suite before submitting:
```bash
cargo test --all-features
cargo clippy -- -D warnings
cargo fmt --check
```
Major changes should include:
- Property tests for new invariants
- Concurrent tests for thread-safety
- Documentation with examples
- Benchmark comparisons