starshard

Changelog

All notable changes to this project will be documented in this file.

[Unreleased]

[2.4.0] - 2026-10-02

Upgrade notes

• Existing CRUD signatures and ReplicaError variants are retained. Review the 2.3.x upgrade guide for corrected snapshot-version semantics, stricter replication validation, and snapshot locking tradeoffs.
• Release evidence includes deterministic concurrency, allocation, hashing, and metadata-publication checks. General throughput, p99, cross-platform runtime behavior, and real replica failures must be validated for the deployment workload.

Fixed

• Pin shard routing for each operation so resize cannot invalidate in-flight indices, and serialize migration publication while keeping source entries reachable until commit.
• Make conditional initialization, CAS, transactions, snapshots, retain, and drain include both migration generations without duplicate length accounting or resurrecting old values.
• Preserve committed length and snapshot epochs across async cancellation and retain-predicate panics; prepare migration replacements before user Hash/Clone/Eq can interrupt publication.
• Consume caller-provided batch iterators before locking to preserve reentrant lazy producers.
• Label versioned snapshots with their committed data epoch; repeated snapshots without writes retain the same version and stale version queries return None.

Added

• Add shared_snapshot() for immutable shared snapshot handles and get_borrowed, contains_borrowed, remove_borrowed, and read_with without changing existing CRUD signatures.

Changed

• Aggregate stable-layout batch length and write-epoch publication once per touched shard. A scoped mutation guard publishes committed changes before unlocking, including Hash/Eq or key/value destructor unwinding; versions remain change tokens, not operation counters.
• Rebuild snapshots behind a dedicated builder gate using shared routing, retained directory reads, and ordered shard read guards. This preserves coherent cuts and coalesces cache misses while permitting ordinary reads subject to lock fairness; writers and topology changes still wait.
• Preallocate snapshot output from frozen shard lengths, remove async migration deduplication hashing, and flatten synchronous Rayon scans without a temporary Vec per shard.
• Serve valid Cached/Cow snapshots without acquiring routing, validating the immutable data and write epoch together. Sync handle capture uses a short cache critical section to avoid shared-reader/refcount contention.
• Clone owned cached iteration results and destroy retired cached values after releasing routing. Reject obsolete snapshot versions without rebuilding, while retaining Tokio cooperative scheduling for cache hits and early version misses.
• Build Cached/Cow snapshots lazily instead of cloning entire shards on each write. Cache misses hold shard read locks to build a consistent view; both modes currently use a whole-map cache.
• Use read access for initialized shard directories, avoid allocating shards for read misses, clone async snapshot entries once, and collect keys/values without copying the unused counterpart.
• Return no lock profiling samples until actual instrumentation exists, rather than fabricated zero measurements.

Tests

• Cover reader progress during rebuild, cold-slot stability, coalesced builds, builder cancellation/panic recovery, migration transaction cuts, and projection clone/hash counts.
• Cover batch Hash/Eq/Drop unwinding, cancellation between committed shard buckets, duplicate keys, empty/miss-only cache reuse, and different-shard length accumulation.
• Cover cached reads during exclusive topology changes, invalidated-cache waits, coherent transaction snapshots, writer progress during value cloning/destruction outside routing, and current-thread Tokio scheduling fairness.
• Add sync/async regressions for migration interleavings, shrinking, atomic initialization, CAS/transactions, cancellation, panic recovery, lazy producer reentry, snapshot versions, and clone counts.

Replication

• Count the primary toward write quorum and validate replica counts, quorum values, duplicate handles, and nonzero deadlines.
• Add try_with_replication; invalid configuration uses the existing ReplicaError::Rejected variant. with_replication now panics for invalid topology instead of silently accepting it.
• Enforce one deadline across queueing, local application, and remote fanout. Acknowledge quorum early while tracking bounded remaining work in order across map clones; dropping the last map cancels that work.
• Document primary-first local application: failure/cancellation does not roll back writes, ordinary local operations are outside replica ordering, and quorum reads/consensus are not implemented.
• Implement Display and Error for ReplicaError without adding enum variants; enable Tokio time only when async and advanced features are combined.
• Add quorum, cancellation, clone lifetime, timeout cleanup, queued timeout, replica panic, and ordering regression tests.

Iteration utilities

• Honor IterBuilder::parallel for large filtered inputs with Rayon while preserving input order, filter-before-limit behavior, and sequential callbacks; retain a sequential fallback without Rayon.
• Correct DrainIterator::size_hint() to match its exact remaining length.
• Add parallel-filter, callback, ordering, and drain-size regression tests.

Benchmarks and documentation

• Add sync/async stable and migrating snapshot-rebuild benchmarks plus batch insertion/removal workloads, with setup, invalidation, input generation, and output destruction outside timing.
• Add persistent-worker comparisons of ordinary reads, projected reads, initialization hits, and fixed-batch cached-snapshot/read mixtures; document cache-hit versus rebuild locking boundaries.
• Pre-generate benchmark keys and reuse worker threads; cover thread counts, skewed key distributions, value sizes, write ratios, owned snapshots, and shared cache hits.
• Strengthen the locked feature matrix with isolated lifecycle, advanced, async, and async-combination lanes.
• Update English/Chinese usage guidance and document migration pauses, lazy snapshot tradeoffs, pessimistic transaction semantics, and unimplemented TTL/metrics/profiling scheduling capabilities.
• Performance evidence is workload-specific: clone-count regressions verify zero full-shard clones on Cow writes and one value clone per async Clone snapshot entry. No general throughput, p99, or memory guarantee is implied.

[2.3.0] - 2026-08-25

Added

• Added Entry-style APIs for sync and async maps:
  • ShardedHashMap::entry(...) -> Entry
  • AsyncShardedHashMap::entry(...).await -> AsyncEntry
  • Entry::{or_insert, or_insert_with, and_modify, insert, remove}
  • OccupiedEntry / VacantEntry and async equivalents
• Added atomic get-or-create helpers for sync and async maps:
  • ShardedHashMap::get_or_insert_with(...)
  • AsyncShardedHashMap::get_or_insert_with(...).await

Changed

• Unified compute_if_absent, get_or_insert_with, and Entry insertion paths through a shared internal hot path to avoid patch-on-patch public API forwarding.
• Preserved online-rebalance fallback semantics for get-or-create operations, including active-first + previous-shard fallback lookup.
• Pinned dependency version requirements and refreshed the lockfile for the release.
• Included examples and integration tests in the packaged crate so declared targets resolve cleanly during packaging.

Tests

• Added sync and async coverage for Entry operations, atomic get-or-insert behavior, concurrent single-initializer execution, COW snapshot updates, and online rebalance fallback behavior.

[2.2.2] - 2026-07-16

Changed

• Simplified the optional Tokio dependency used by the async feature to rt + sync, so downstream users are no longer forced onto Tokio’s multi-thread runtime.
• Made the dev Tokio dependency explicit with default-features = false while keeping macros, rt-multi-thread, and sync for tests and examples.
• Refreshed dependency lock state for the release.

[2.2.1] - 2026-06-14

Changed

• Refactored lib.rs into focused modules: types.rs, error.rs, rebalance.rs.
• Extracted tests into tests/ module with sync.rs, async_tests.rs, batch.rs, snapshot.rs.
• lib.rs reduced from 1349 to 290 lines (-78.5%).

Documentation

• Added module-level doc comments (//!) to all source modules (types, error, rebalance, core, serde).
• Added doc comments to all complex private functions in core/sync_impl.rs and core/async_impl.rs.
• Added doc comments to core/helpers.rs utility functions (std_read_guard, std_write_guard, normalized_shard_count, strict_shard_count, capped_shard_count).
• Added doc comments to RebalanceTracker internals in rebalance.rs.
• Added inline comments explaining COW merge algorithm (3-phase), iteration branching (epoch cache / COW / standard / rayon), and batch operation migration fallback.

[2.2.0] - 2026-05-15

Added

• Snapshot mode APIs (sync + async):
  • Added SnapshotMode::{Clone, Cached, Cow}.
  • Added constructors:
    • with_snapshot_mode(...)
    • with_shards_and_hasher_and_snapshot_mode(...)
    • with_shards_and_hasher_capped_and_snapshot_mode(...)
  • Added write epoch + snapshot cache flow for repeated snapshot reads.
  • Added COW snapshot shard path for snapshot-heavy workloads.
  • Added snapshot mode benchmark groups in benches/bench_main.rs.
  • Added snapshot mode examples:
    • snapshot_mode_clone_demo
    • snapshot_mode_cached_demo
    • snapshot_mode_cow_demo
    • mixed_workload_snapshot_tradeoff_demo

Changed

• Snapshot concurrency hardening:
  • Eliminated snapshot cache race windows in sync/async paths.
  • Strengthened COW snapshot + rebalance interaction consistency under concurrent writes.
  • Refined snapshot/rebalance internal flow to reduce patch-on-patch branching in hot paths.

Documentation

• Updated release documentation and roadmap status to v2.2.0.
• Refreshed snapshot mode guidance and runnable examples in README.md and README_CN.md.

[2.1.0] - 2026-05-15

Added

• Adaptive rebalance APIs (sync + async):
  • Added stop-the-world rebalance:
    • ShardedHashMap::rebalance_to(...)
    • AsyncShardedHashMap::rebalance_to(...).await
  • Added online incremental rebalance lifecycle:
    • start_rebalance_online(...)
    • advance_rebalance(...)
  • Added status snapshot API:
    • rebalance_status() -> RebalanceStatus
  • Added data models:
    • RebalanceOptions
    • RebalanceReport
    • RebalanceStatus

Changed

• Routing internals for shard expansion:
  • Reworked internal shard-count storage to allow safe runtime shard-count transitions.
  • Added previous-epoch shard storage for online migration fallback reads.
  • Updated read/write paths so online migration follows active-first, previous-fallback semantics.

Tests

• Added rebalance test coverage for:
  • stop-the-world sync/async migration correctness
  • status lifecycle correctness
  • online incremental sync/async migration path

[2.0.0] - 2026-05-15

Changed

• Version bump:
  • Crate version updated from 1.2.0 to 2.0.0.
• Shard safety hardening (public API + behavior update):
  • Added MAX_SHARDS default hard cap to guard infallible constructors against oversized allocations.
  • Added ShardCountError and strict constructors: try_with_shards_and_hasher(...) and try_with_shards_and_hasher_capped(...) for both sync and async maps.
  • Added capped constructors: with_shards_and_hasher_capped(...) for both sync and async maps.
  • Updated constructor behavior so oversized requests are clamped (infallible constructors) or rejected (strict constructors) instead of allocating unbounded shard vectors.
• Internal architecture refactor:
  • Split core sync implementation out of src/lib.rs into src/core/sync_impl.rs.
  • Split core async implementation out of src/lib.rs into src/core/async_impl.rs.
  • Extracted serde implementation into src/serde/sync_serde.rs and src/serde/async_snapshot.rs.
  • Added core internal split files: src/core/types.rs and src/core/helpers.rs.
  • Reduced lib.rs complexity by moving implementation details into focused modules.
• Batch-path performance optimization:
  • Reworked sync/async batch_insert, batch_remove, and batch_get grouping to sparse per-touched-shard buckets.
  • Eliminated shard-count-sized per-call bucket preallocation in batch grouping paths.
  • Improved async compute_if_present to evaluate closure before removal, aligning sync/async behavior and avoiding unnecessary remove+reinsert work.

Added

• Refactor guardrails and verification scripts:
  • Added scripts/export_api_surface.sh for API-surface snapshot/export.
  • Added scripts/verify_feature_matrix.sh for repeatable feature-matrix validation.
• CI hardening:
  • Added dedicated feature matrix job in GitHub Actions.
  • Added dedicated doctest job in GitHub Actions.

Documentation

• Updated README.md and README_CN.md for 2.0.0 version references.
• Synced feature matrix and performance notes with current v2.0 implementation status.

[1.2.0] - 2026-05-15

Added

• Lifecycle API completion:
  • Added memory_stats() for ShardedHashMap and AsyncShardedHashMap under lifecycle.
  • Added drain() for ShardedHashMap and AsyncShardedHashMap under lifecycle.
  • Added async per_shard_load() for AsyncShardedHashMap under lifecycle.
• Tests:
  • Added regression tests for shard empty-count accounting.
  • Added lifecycle tests for memory stats and drain behavior (sync + async).

Fixed

• Shard statistics correctness:
  • Fixed ShardStats.empty calculation in both sync and async shard_stats() implementations.

Documentation

• Updated README.md lifecycle section to match current implementation and added examples for:
  • per_shard_load() (sync + async)
  • memory_stats() (sync + async)
  • drain() (sync + async)

[1.1.0] - 2026-02-03

Added

• Shard Introspection:
  • per_shard_load(): Returns detailed load statistics (PerShardLoad) for each initialized shard, including entry count and capacity. Available for both ShardedHashMap and AsyncShardedHashMap when the lifecycle feature is enabled.
• Logging:
  • Added #[tracing::instrument] to public APIs and core helpers across sync/async maps and lifecycle/advanced modules.

Changed

• Robust Error Handling:
  • Replaced unwrap() in shard initialization and transaction shard lookup with logged fallbacks; transactions abort safely on missing shard indices.
• Refactoring:
  • Introduced shared std RwLock guard helpers to reduce repetitive poisoned-lock handling.

[1.0.1] - 2026-02-02

Changed

• Feature Consolidation:
  • Merged ttl, metrics, and advanced-iter features into a single lifecycle feature.
  • Merged transactions, cas, cow-snapshot, replication, and diagnostics features into a single advanced feature.
  • Promoted batch operations to core functionality (removed batch feature flag).
  • Updated full feature to include async, rayon, serde, lifecycle, and advanced.

Optimized

• Batch Operations:
  • Optimized batch_insert and batch_remove to acquire the shard lock only once per shard group, significantly reducing lock contention.

[1.0.0] - 2026-01-31

Added

Advanced Concurrency & Distributed Features

• Atomic Transactions (MVCC-based):
  • Transaction<K, V>: Multi-key atomic operations with read/write/remove support
  • execute_transaction(): Sync and async transaction execution with deadlock prevention
  • TransactionResult<T>: Result enum (Committed, Aborted, Conflict)
  • Shard-level locking with sorted indices to prevent deadlocks
• Compare-And-Swap (CAS) Operations:
  • compare_and_swap(key, expected, new): Atomic value replacement
  • compare_and_remove(key, expected): Conditional removal
  • CasResult<V>: Success/Failure result with current value
  • Full support for both sync and async variants
• Copy-On-Write Snapshots:
  • cow_snapshot(): Zero-allocation snapshot for read-heavy workloads
  • CowSnapshot<K, V>: Immutable snapshot with version tracking
  • Minimal lock contention during snapshot creation
  • Iterator support with snapshot isolation guarantees
• Snapshot Isolation & Versioning:
  • versioned_snapshot(): Create timestamped snapshots for time-travel queries
  • snapshot_at_version(version): Retrieve snapshot at specific version
  • IsolatedSnapshot<K, V>: Version-tagged snapshot with age tracking
  • Monotonic version counter for consistency
• Lock Profiling & Diagnostics:
  • lock_profiles(): Per-shard lock contention statistics
  • enable_profiling(bool): Toggle profiling with minimal overhead
  • LockProfile: Metrics including reads, writes, contention count, wait times
  • Runtime-configurable profiling for production diagnostics
• Distributed Replication Framework (async only):
  • Replica<K, V> trait: Interface for custom replica implementations
  • with_replication(): Configure map with replica set and quorum
  • insert_replicated() / remove_replicated(): Quorum-based operations
  • ReplicationOp<K, V>: Serializable operation types (Insert, Remove, Clear)
  • QuorumConfig: Majority and strict quorum configurations
  • Parallel async replication with configurable timeouts
  • ReplicaError: Comprehensive error handling for replication failures

Implementation Details

• Type Safety: All generic types use 'static bounds for async compatibility
• Zero External Dependencies: No dashmap or parking_lot - uses only hashbrown and std library
• Type Aliases: ReplicaList<K, V> to reduce type complexity (clippy-clean)
• Version Tracking: Arc<AtomicUsize> for lock-free version increments
• Feature Flags: All functionality behind advanced feature flag

Testing

• 40+ Test Cases: Comprehensive coverage for all features
  • Transaction tests (5): basic commit, multi-shard, read ops, empty, async
  • CAS tests (11): success/failure scenarios, multi-threaded, async variants
  • CoW snapshot tests (6): creation, isolation, iteration, race conditions
  • Versioned snapshot tests (8): ordering, version queries, time-travel
  • Lock profiling tests (3): enable/disable, structure validation
  • Replication tests (4): quorum configs, insert/remove operations
  • Integration tests (3): cross-feature interactions

Fixed

• Type complexity warning (clippy): Added ReplicaList<K, V> type alias
• Lifetime errors: Added 'static bounds to K and V types for async compatibility
• Test race conditions: Used Barrier for proper synchronization
• Quorum validation: Corrected replica count matching in tests

Documentation

• 14 detailed documentation files covering implementation and fixes
• API documentation with examples for all public methods
• Comprehensive test suite serving as usage examples
• Full async/await pattern documentation

[0.9.0] - 2026-01-31

Added

Production Features (v0.9.0)

• TTL & Eviction System:
  • EvictionPolicy enum: LRU, LFU, TimeToLive, Custom predicates
  • EvictionConfig: Configurable policy, max_entries, check intervals
  • Background eviction task with atomic control
  • Per-shard eviction statistics tracking
• Metrics Collection:
  • MetricsStats: Comprehensive operation counters
  • AtomicMetrics: Lock-free metrics aggregation
  • MemoryStats: Memory utilization tracking
  • Hit rate calculation and snapshot functionality
  • reset_metrics(): Clear accumulated statistics
• Advanced Iteration Builders:
  • IterBuilder<K, V>: Fluent API for complex iteration patterns
  • Filter, limit, and parallel control
  • collect(), for_each() execution methods
• Drain Operation:
  • DrainIterator<K, V>: Efficient bulk removal
  • Lock-per-shard acquisition
  • ExactSizeIterator implementation
  • Zero intermediate allocation
• Extended Introspection:
  • memory_stats(): Shard allocation and load factor
  • per_shard_load(): Per-shard entry counts
  • Detailed shard distribution metrics

Infrastructure (v0.9.0)

• New feature flags: ttl, metrics, advanced-iter
• Type aliases for reduced complexity
• Comprehensive test suite (30+ tests)
• Performance benchmarking infrastructure
• Documentation examples for each feature

Configuration Changes

Cargo.toml:

• Added optional dependencies: parking_lot
• New feature flags for modular enablement
• Updated full feature set

v0.8.0 & v1.0.0 Modules (Specification)

• eviction.rs: TTL, eviction policies, metrics, advanced iteration framework
• advanced.rs: Transactions, CAS, CoW snapshots, replication, diagnostics framework

[0.8.0] - 2026-01-30

Added

Core Features (v0.8.0)

• Conditional Update Operations: Efficient in-place updates with single shard lock
  • compute_if_present(): Update value only if key exists; remove if closure returns None
  • compute_if_absent(): Insert only if key is absent; return final value
  • Single lock acquisition per operation (no extra contention)
  • Ideal for check-then-update patterns common in concurrent scenarios
• Batch Operations: Amortized lock acquisition for multiple keys
  • batch_insert(): Insert multiple key-value pairs in grouped shard batches
  • batch_remove(): Remove multiple keys with efficient per-shard grouping
  • batch_get(): Fetch multiple keys in one call, preserving order
• Filtering & Retention:
  • retain(): Remove entries where predicate returns false (per-shard locking)
• Collection Views:
  • keys(): Iterate over all keys (snapshot-based)
  • values(): Iterate over all values (snapshot-based)
  • iter(): Full key-value pair iteration with optional rayon parallelism
• Shard Introspection:
  • shard_stats(): Returns ShardStats with detailed shard distribution metrics
  • shard_utilization(): Percentage of initialized shards for capacity planning
  • Per-shard load tracking and distribution analysis
• Async Equivalents: All v0.8.0 methods available on AsyncShardedHashMap

Infrastructure

• New feature flags: batch (Entry API provided as methods, not as traditional enum)
• Conditional operations available on both ShardedHashMap and AsyncShardedHashMap
• Comprehensive test suite (50+ new unit tests for conditional operations, batch ops, filtering)
• Example programs: v080_entry_api.rs (conditional operations & views), v080_async_batch.rs (async variants)
• ROADMAP.md: Multi-version development plan (v0.8, v0.9, v1.0)
• IMPLEMENTATION_SUMMARY.md: Design decisions, architecture, performance characteristics

[0.7.0] - 2026-01-30

• add cross-platform test
• chore(deps): bump tokio from 1.48.0 to 1.49.0 and serde_json from 1.0.145 to 1.0.149

[0.6.0] - 2025-11-23

• set starshard version 0.6.0
• upgrade actions/checkout from v5 to v6
• upgrade crates version
• chore(deps): bump github/codeql-action from 3 to 4 (#1)

[0.5.0] - 2025-09-29

• Replace fxhash with rustc-hash for improved hashing performance and compatibility

[0.4.0] - 2025-09-26

• improve for README
• feat(serde): finalize serde support, add async snapshot serialization, doc updates

[0.3.0] - 2025-09-26

• improve for v0.3.0

[0.2.0] - 2025-09-25

• rename async func
• fmt MIT License
• chore(init): bootstrap starshard crate (sync/async sharded HashMap)

This site is open source. Improve this page.