Hasty Briefsbeta

Go rate limiter that writes 95%-99% less I/O

a day ago
https://github.com/etalazz/vsa
Copy Link
  • #data-structures
  • #high-performance
  • #transaction-processing
  • The VSA (Volatile State Accumulator) is a high-performance, in-memory data structure designed to track the state of volatile resources by filtering I/O overhead from self-canceling transactions.
  • It provides guaranteed O(1) lookups and an O(1) memory footprint for resource counters, minimizing expensive disk/network I/O operations in high-throughput systems.
  • The VSA addresses 'transactional noise'—frequent updates that are quickly reversed (e.g., buy/sell shares, reserve/cancel tickets).
  • Traditional data structures (atomic counters, write buffers, caches) inefficiently handle transactional noise, leading to latency and high infrastructure costs.
  • The VSA is inspired by scalar electromagnetics, using a stable Scalar (S) for committed resource counts and a volatile Vector (A_net) for uncommitted changes.
  • Updates are applied only to A_net, allowing opposing actions to cancel each other out algebraically, reducing unnecessary writes to S.
  • Available resources are calculated in real-time as S - |A_net|, ensuring O(1) performance.
  • Disk writes to S occur only when |A_net| exceeds a predefined threshold, reducing I/O.
  • The VSA outperforms traditional solutions in time and space complexity, especially in high-volume, volatile conditions.
  • Applications include high-frequency trading, cloud resource management, e-commerce inventory, online gaming, social media engagement, IoT data aggregation, and logistics.
  • The VSA is unsuitable for non-commutative operations, systems requiring full audit trails, or where data loss is unacceptable.
  • Key trade-offs include durability risks and the need to carefully tune the commit threshold.
  • The VSA should be used as a front-end filter, not a system of record, and can be combined with durable logs (e.g., Kafka) for robustness.
  • Scaling the VSA involves using it as a value in a hash map (HashMap<ResourceID, VSA>) for O(1) performance across millions of resources.
  • A demo implementation includes a high-throughput API rate-limiting service, showcasing the VSA's real-world benefits.
AboutLogin