Left-Right 并发模式

Left Right Concurrency

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

个人笔记

题目详情

在高频交易中，以读为主的配置数据（如风控限额或标的映射）必须被关键路径线程无阻塞访问。Left-Right 并发模式通过维护两份数据实例实现 wait-free 读取：读者无障碍地进行，写者在后台协调更新。

任务：实现 Left-Right 并发模式的模拟器。LeftRight class 维护两个数据实例（left 和 right），读者线程始终从"当前活跃"实例无等待读取，写者线程更新"非活跃"实例后切换活跃指针。

英文原题

In high-frequency trading, read-dominated configuration data such as risk limits or symbol mappings must be accessed by critical-path threads without blocking. The Left-Right concurrency pattern achieves this wait-free read access by maintaining two data instances, allowing readers to proceed unhindered while a writer coordinates updates in the background.
Task
Implement a simulator for the Left-Right concurrency pattern that calculates the exact completion time of each write operation.
You are

解析

问题分析

Left-Right 模式是读优化并发控制的经典技术。维护两份数据副本（left 和 right），写入者更新非活跃副本后切换指针，读者始终无锁读取活跃副本。适合读比例极高（>99%）的场景。

实现

template<typename T>
class LeftRight {
    T left_, right_;
    std::atomic<T*> active_{&left_};
    std::atomic<int> readers_{0};
    std::mutex write_mtx_;
public:
    T read() {
        readers_.fetch_add(1, std::memory_order_acquire);
        T* ptr = active_.load(std::memory_order_acquire);
        T copy = *ptr;
        readers_.fetch_sub(1, std::memory_order_release);
        return copy;
    }
    void write(const T& val) {
        std::lock_guard lk(write_mtx_);
        T* inactive = (active_.load() == &left_) ? &right_ : &left_;
        *inactive = val;
        active_.store(inactive, std::memory_order_release);
        while (readers_.load() > 0) std::this_thread::yield(); // 等待旧读者
    }
};

复杂度与边界

时间复杂度：read O(1) 无锁，write O(等待读者数)
空间复杂度：2 * O(sizeof(T))
边界条件：(1) 连续两次 write 之间必须有读者退出 (2) 仅适合单写入者 (3) 内存开销为双倍

英文解析

Analysis

The Left-Right pattern is a classic read-optimized concurrency control technique. It maintains two data copies (left and right), where the writer updates the inactive copy then swaps the pointer, and readers always read the active copy without locking. This suits scenarios with extremely high read ratios (>99%).

Solution

template<typename T>
class LeftRight {
    T left_, right_;
    std::atomic<T*> active_{&left_};
    std::atomic<int> readers_{0};
    std::mutex write_mtx_;
public:
    T read() {
        readers_.fetch_add(1, std::memory_order_acquire);
        T* ptr = active_.load(std::memory_order_acquire);
        T copy = *ptr;
        readers_.fetch_sub(1, std::memory_order_release);
        return copy;
    }
    void write(const T& val) {
        std::lock_guard lk(write_mtx_);
        T* inactive = (active_.load() == &left_) ? &right_ : &left_;
        *inactive = val;
        active_.store(inactive, std::memory_order_release);
        while (readers_.load() > 0) std::this_thread::yield();
    }
};

Complexity & Edge Cases

Time complexity: read O(1) lock-free, write O(wait for existing readers)
Space complexity: 2 x O(sizeof(T))
Edge cases: (1) Two consecutive writes must allow existing readers to exit (2) Only suits single-writer (3) Memory overhead is doubled

Verification

Concurrent readers verify they always get a consistent snapshot. Writer verifies no reader accesses freed data during swap. Test high-read ratio (>99%) scenarios for performance.

Key Considerations

The Left-Right pattern is superior to read-write locks when the read ratio exceeds 99%, because reads never acquire any lock. In order book snapshot dissemination, thousands of strategy threads read the book while only the matching engine writes - Left-Right eliminates read-side contention entirely.