Atomic Fetch Add 统计

Atomic Fetch Add Stats

专题: Systems & Architecture / 系统与架构
难度: L2
来源: MyntBit

个人笔记

题目详情

在高频交易系统中，跨多线程维护交易计数和成交量等实时统计数据对风控和信号生成至关重要。使用锁进行这些更新会引入不可接受的延迟和竞争，因此带宽松内存序的无锁原子操作成为标准方案。

任务：实现线程安全的 TradeStats 类，跟踪交易计数、累计成交量和成交金额。所有更新使用 atomic fetch_add 操作，读取使用原子 load，内存序使用 relaxed 以最小化开销。

英文原题

In high-frequency trading systems, maintaining real-time statistics like trade counts and volumes across multiple threads is critical for risk management and signal generation. Using locks for these updates introduces unacceptable latency and contention, making lock-free atomic operations with relaxed memory ordering the standard approach.
Task
Implement a thread-safe TradeStats class that tracks the total number of trades and the total traded volume for a fixed number of symbols. You must use

解析

问题分析

std::atomic 的 fetch_add 可以用来实现无锁的统计计数器。在交易系统中，多个线程需要累积订单数、成交量等统计信息，使用原子变量避免互斥锁开销。

实现

struct TradeStats {
    std::atomic<uint64_t> order_count{0}, fill_count{0};
    std::atomic<double> total_volume{0.0};  // 注意：浮点 fetch_add 需 CAS 循环
    void recordFill(double vol) {
        fill_count.fetch_add(1, std::memory_order_relaxed);
        double expected = total_volume.load(std::memory_order_relaxed);
        while (!total_volume.compare_exchange_weak(expected, expected + vol,
                   std::memory_order_release, std::memory_order_relaxed));
    }
    TradeStats snapshot() const {
        return {order_count.load(), fill_count.load(), total_volume.load()};
    }
};

复杂度与边界

时间复杂度：recordFill O(1)（整数）或均摊 O(1)（浮点 CAS 循环）
空间复杂度：O(1)
边界条件：(1) 浮点原子操作必须用 CAS 循环（无 hardware fetch_add） (2) 高竞争下 CAS 可能多次重试 (3) 快照是非原子的——各字段独立读取

英文解析

Analysis

`std::atomic` fetch_add enables lock-free statistical counters. In trading systems, multiple threads accumulate order counts, fill volumes, etc. Atomic variables avoid mutex overhead for simple aggregations.

Solution

struct TradeStats {
    std::atomic<uint64_t> order_count{0}, fill_count{0};
    std::atomic<double> total_volume{0.0};  // note: float fetch_add requires CAS loop
    void recordFill(double vol) {
        fill_count.fetch_add(1, std::memory_order_relaxed);
        double expected = total_volume.load(std::memory_order_relaxed);
        while (!total_volume.compare_exchange_weak(expected, expected + vol,
                   std::memory_order_release, std::memory_order_relaxed));
    }
    TradeStats snapshot() const {
        return {order_count.load(), fill_count.load(), total_volume.load()};
    }
};

Complexity & Edge Cases

Time complexity: recordFill O(1) (integer) or amortized O(1) (float CAS loop)
Space complexity: O(1)
Edge cases: (1) CAS loop for float may retry under high contention (2) Snapshot not atomic across all fields — use separate snapshots for consistency (3) Overflow for uint64 requires periodic reset

Key Considerations

Statistical accuracy: Atomic fetch_add provides exact counts but no ordering guarantees between different counters; two counters updated in same operation may reflect inconsistent order
Overflow handling: 64-bit counters rarely overflow in practice; 32-bit counters overflow after ~4 billion operations — use uint64_t for production counters
Memory ordering: relaxed ordering sufficient for counters (no dependency on other atomic operations); acquire/release ordering wastes CPU cycles on unnecessary synchronization
Reporting vs counting: Counter reads should be infrequent (e.g., once per second); frequent reads add atomic load overhead and may interfere with cache line layout