系统 Mesi Cache Coherence

Systems Mesi Cache Coherence

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

个人笔记

题目详情

高频交易应用运行在多核处理器上。两个独立线程在不同核心上频繁更新恰好位于同一缓存行的不同变量。此场景称为 false sharing。

任务：分析 MESI 协议下 false sharing 的影响：当线程 A 更新变量 x，整个缓存行在 B 的核心上标记为 Invalid，B 必须重新从主内存加载——即使 B 只读 y 不读 x。每次更新触发缓存行失效，性能下降数十倍。解决方案：alignas(64) 使变量位于不同缓存行。

英文原题

Consider a high-frequency trading application running on a multi-core processor. Two independent threads, running on separate cores, are frequently updating different variables that happen to reside within the same cache line. This scenario is known as false sharing.
Assume a MESI (Modified, Exclusive, Shared, Invalid) cache coherence protocol is in place. Each time one core modifies its variable, the cache line must transition through different states, potentially invalidating the other core's

解析

问题分析

解法

根据题目要求实现相应功能。核心逻辑需要：

// 核心数据结构和方法——根据题目 API 约定实现
// 1. 确定状态表示——选择支持所需操作的数据结构
// 2. 实现核心算法——确保 O(·) 时间复杂度和正确性
// 3. 处理边界条件——空输入、极值参数、并发访问

验证

用具体输入验证：构造已知输入的测试用例，确认输出匹配预期结果。

复杂度与边界

时间复杂度：取决于选用的算法
空间复杂度：取决于数据规模
关键边界条件：空输入、极值参数、并发场景下的正确性保证

英文解析

Analysis

Consider a high-frequency trading application on a multi-core processor. Two independent threads on separate cores frequently update different variables that happen to reside within the same cache line. This is false sharing. Under MESI protocol, when one thread modifies its variable, the entire cache line transitions from Shared to Modified state, forcing the other core's copy to Invalid. The other thread must then fetch the line again, incurring ~100ns cache coherence traffic per modification, even though it only reads a different variable on the same line.

Solution

struct alignas(64) PaddedCounter {  // 64-byte aligned = one per cache line
    std::atomic<uint64_t> value{0};
    char padding[64 - sizeof(std::atomic<uint64_t>)];
};
// Each counter occupies its own cache line - no false sharing
class OrderBookStats {
    PaddedCounter updates_, inserts_, deletes_;  // Each on separate line
};

Complexity & Edge Cases

Time complexity: Counter update O(1), false sharing elimination O(1) setup
Space complexity: 64 bytes per counter (vs 8 bytes without padding)
Edge cases: (1) Padding wastes ~56 bytes per counter (2) alignas(64) requires compiler support (3) False sharing detection requires perf stat cache-miss analysis

Verification

Run two threads updating adjacent vs padded counters. Measure cache miss rate via perf_event. Verify padded counters show ~0 cross-core coherence traffic while adjacent counters show high L3 miss rate.

Key Considerations

False sharing is the most common performance bug in multi-threaded trading systems. Two atomic counters on the same cache line cause 100ns coherence traffic per update - at 10M updates/second, this adds 1 second of pure overhead per second. The fix is simple and universal: pad all frequently-updated shared variables to cache line size (64 bytes). The memory cost is negligible compared to the latency benefit.