双缓冲交换
Double Buffer Swap
题目详情
在高频交易系统中，订单簿快照被多个策略线程频繁读取，由单个行情线程更新。为最小化延迟和避免锁开销，常使用双缓冲方案：写者准备新数据在后台缓冲区完成后原子切换指针。
任务：实现 DoubleBuffer 类，维护两个缓冲区（active 和 standby）。写者更新 standby 缓冲区，完成后 swap() 原子切换指针使 standby 变为 active。读者始终从 active 缓冲区无锁读取。
英文原题
In high-frequency trading systems, order book snapshots are frequently read by multiple strategy threads and updated by a single market data thread. To minimize latency and avoid locking, a double-buffering scheme is often used. The writer prepares data in a background buffer and atomically swaps a pointer to make it active, while readers track their access using reference counts.
Task
Implement a simulated DoubleBuffer class that manages an order book snapshot (best bid and best ask) using two
解析
问题分析
双缓冲技术维护两份数据副本（active 和 standby）。写入者更新 standby 副本后原子切换指针，读者始终读取 active 副本无需加锁。适合配置热加载、行情快照更新等读多写一场景。
实现
template<typename T>
class DoubleBuffer {
T buffers_[2];
std::atomic<int> active_{0};
std::mutex write_mtx_;
public:
T read() const { return buffers_[active_.load(std::memory_order_acquire)]; }
void write(const T& val) {
std::lock_guard lk(write_mtx_);
int standby = 1 - active_.load(std::memory_order_relaxed);
buffers_[standby] = val;
active_.store(standby, std::memory_order_release);
}
};复杂度与边界
- 时间复杂度：read O(1) 无锁，write O(sizeof(T)) 拷贝
- 空间复杂度：2 * O(sizeof(T))
- 边界条件：(1) 连续两次 write 之间读者可能仍持有旧版本指针——需延迟回收 (2) 仅适合单写者 (3) 大对象拷贝开销显著
英文解析
Analysis
Double buffering maintains two data copies (active and standby). The writer updates the standby copy then atomically swaps the pointer, while readers always read the active copy without locking. This pattern suits configuration hot-reload, market snapshot updates, and other read-heavy single-writer scenarios.
Solution
template<typename T>
class DoubleBuffer {
T buffers_[2];
std::atomic<int> active_{0};
std::mutex write_mtx_;
public:
T read() const { return buffers_[active_.load(std::memory_order_acquire)]; }
void write(const T& val) {
std::lock_guard lk(write_mtx_);
int standby = 1 - active_.load(std::memory_order_relaxed);
buffers_[standby] = val;
active_.store(standby, std::memory_order_release);
}
};Complexity & Edge Cases
- Time complexity: read O(1) lock-free, write O(sizeof(T)) copy
- Space complexity: 2 x O(sizeof(T))
- Edge cases: (1) Between two consecutive writes, readers may still hold a pointer to the old version - delayed reclamation needed (2) Only suits single-writer scenario (3) Large object copy overhead is significant
Verification
Test with concurrent read/write: writer updates a snapshot value, readers verify they always get a consistent (though possibly stale) copy. Confirm atomicity of pointer swap under concurrent reads.
Key Considerations
Double buffering trades memory for read-side lock freedom. In trading systems, this is ideal for market data snapshots where readers (strategy threads) far outnumber writers (data feed handler). The stale-read tolerance is acceptable since market data is inherently point-in-time.