뒤로가기

[C++] MPSC Queue: Atomic은 MutexLock보다 빠른가

TL;DR — Private Server의 actor mailbox에 사용할 bounded MPSC queue를 구현하면서 Atomic 기반 구현이 MutexLock 기반 구현보다 빠를 것이라고 예상했습니다. 하지만 즉시 재시도하는 CAS 구현은 MutexLock보다 느렸고, CAS 실패 뒤 pause를 적용하자 결과가 다시 역전되었습니다.

Table of contents

Open Table of contents

들어가며

Private Server에서는 여러 IO worker가 만든 event를 하나의 actor owner에게 전달해야 합니다. 이 경계에 여러 producer와 단일 consumer가 사용하는 bounded MPSC queue를 구현했습니다.

처음에는 MutexLock을 제거하고 Atomic 연산만 사용하면 queue가 더 빠를 것이라고 예상했습니다. 그러나 초기 성능 실험에서는 producer가 하나일 때와 여러 개일 때의 결과가 크게 달랐습니다. 이 글에서는 구현 자체보다 예상이 어긋난 이유를 추적하고, 동시성 자료구조를 어떤 기준으로 선택해야 하는지 정리합니다.

이 글에서 다루는 내용:

1. Private Server에 MPSC Queue가 필요한 이유

여러 IO worker는 같은 Runtime Session을 대상으로 event를 만들 수 있지만, session의 mutable state는 한 actor owner만 변경할 수 있게 설계했습니다. 따라서 actor mailbox는 여러 producer가 enqueue하고 단일 drain owner(= actor)가 dequeue하는 MPSC 경계가 됩니다.

bounded capacity(= ring buffer) 를 가진 queue 를 통해 생산되는 event에 따라 동적으로 메모리 할당을 하는 오버헤드를 피하고자 하였고, queue의 사이즈는 producer/consumer가 event 를 생산/소모하는 횟수를 관측하여 조절했습니다.

2. 두 가지 Queue와 처음 세운 가설

비교 대상은 하나의 MutexLock으로 ring buffer의 push와 pop을 보호하는 queue와, producer가 CAS로 위치를 예약하고 slot별 sequence로 message를 공개하는 queue입니다.

처음 세운 가설은 다음과 같습니다.

MutexLock 획득과 대기를 제거하면 Atomic 기반 queue의 처리량이 더 높을 것이다.

MutexLock 구현은 push와 pop의 queue 상태 변경을 같은 std::mutex로 보호합니다. capacity 검사도 lock 안에서 수행해야 여러 producer가 동시에 남은 공간이 있다고 판단하는 경쟁을 막을 수 있습니다.

bool LockedBoundedMpscQueue::TryPush(const Message& value)
{
    std::lock_guard<std::mutex> lock{mutex_};

    if (size_ == capacity_)
        return false;

    storage_[tail_] = value;
    tail_ = (tail_ + 1) % capacity_;
    ++size_;
    return true;
}LockedBoundedMpscQueue.cpp

3. Atomic Queue는 Message를 어떻게 전달하는가

Atomic 기반 queue의 동작은 slot 예약과 message publication으로 나누어 설명합니다.

  1. 여러 producer가 공유 enqueue position을 CAS로 경쟁합니다.
  2. CAS에 성공한 producer가 해당 slot을 독점합니다.
  3. producer가 일반 메모리인 message를 작성합니다.
  4. release store로 slot이 준비되었다는 사실을 공개합니다.
  5. consumer는 acquire load로 준비 상태와 message 작성을 함께 관찰합니다.

핵심 코드는 다음과 같습니다. CAS에 성공한 producer만 slot에 message를 쓰고, 작성이 끝난 뒤 release store로 consumer에게 공개합니다.

if (enqueuePos_.compare_exchange_weak(
        pos,
        pos + 1,
        std::memory_order_relaxed,
        std::memory_order_relaxed))
{
    slot.message = value;

    // slot의 message를 이 thread에서 수정
    // 수정 내용을 release
    slot.seq.store(pos + 1, std::memory_order_release);
    return true;
}

// 초기 구현은 실패 직후 다음 CAS를 시도합니다.
continue;MutexFreeBoundedMpscQueue.cpp

enqueuePos_는 slot의 소유권만 결정하므로 CAS에는 relaxed를 사용합니다. 실제 message publication은 slot별 sequence의 release/acquire 관계가 담당합니다.

4. 예상과 달랐던 초기 실험

MutexLock baseline의 capacity 검사를 lock 안으로 옮긴 뒤 Windows Release x64 환경에서 다시 측정했습니다. workload는 다음과 같습니다.

전체 테스트 흐름은 다음과 같습니다.

queue를 생성한다

consumer 1개를 시작한다
    시작 barrier에서 대기한다
    총 8,000,000개를 소비할 때까지 TryPop을 반복한다

producer 8개를 시작한다
    시작 barrier에서 대기한다
    각 producer가 1,000,000개 message를 생성한다
    queue가 full이면 yield 후 같은 message를 다시 시도한다

모든 thread가 barrier에 도착하면 시간을 측정한다
producer와 consumer가 끝날 때까지 기다린다
elapsed time과 throughput을 계산한다

조건별로 10회 반복하고 median과 min/max를 기록한다

첫 baseline에서는 pause 없이 즉시 재시도하는 CAS queue와 MutexLock queue를 각각 10회 측정했습니다.

구현Min/Max elapsedThroughput
MutexLock495.376 / 1,497.160 ms12.499 Mmsg/s
CAS866.816 / 1,726.800 ms5.015 Mmsg/s

처리량은 총 8,000,000개 message를 median elapsed로 나누어 환산했습니다. 이번 workload에서 MutexLock queue의 처리량은 CAS queue의 약 2.49배였습니다. Atomic 연산만 사용하면 MutexLock보다 빠를 것이라는 처음 가설과 반대되는 결과였습니다.

4-1. Producer가 늘어나면 무엇을 경쟁하는가

producer가 늘어나면 모든 producer가 같은 Atomic 위치를 수정하려고 시도하고, CAS 실패와 재시도가 증가합니다.

때문에 producer가 하나인 상태에서 비교를 해보면 enqueue position에 대한 CAS 경합이 줄기 때문에 더 좋은 결과를 얻을 수 있었습니다.

4-2. False Sharing과 True Sharing 구분하기

서로 다른 스레드가 서로 다른 변수를 수정하지만 두 변수가 같은 cache line에 배치된 경우를 false sharing으로 구분합니다. enqueue position과 dequeue position을 서로 다른 cache line에 배치했습니다.

반면 여러 producer가 동일한 enqueue position을 CAS하는 것은 실제로 같은 값을 공유하는 true sharing입니다.

5. std::mutex는 경합을 어떻게 처리하는가

왜 초기 예상과 다른 결과가 발생했는지 확인하기 위해서는 std::mutex가 어떤 방식으로 작동하는지 확인이 필요합니다.

MSVC 환경에서의 std::mutex는 실제로 다음과 같은 코드를 내부적으로 호출하고 있습니다.

std::lock_guard<std::mutex>
  -> std::mutex::lock()
  -> _Mtx_lock()
  -> AcquireSRWLockExclusive()

std::mutex::unlock()
  -> _Mtx_unlock()
  -> ReleaseSRWLockExclusive()

내부 동작 흐름에서 SRWLOCK 를 호출하고 있는 것을 확인할 수 있습니다. SRWLOCK은 다음과 같은 특징을 가지고 있는 경량 lock 입니다.

exclusive lock을 즉시 얻지 못한 thread는 소유권을 받을 때까지 기다립니다. 대기하던 thread가 다시 실행되는 과정에서는 scheduler에 의한 context switch 비용이 발생할 수 있습니다. 대신 기다리는 producer가 공유 cache line에 CAS를 계속 요청하지 않으므로 runnable contender와 cache coherence traffic을 줄일 수 있습니다.

CAS queue는 반대 특성을 보입니다. 모든 producer가 계속 runnable한 상태에서 같은 enqueuePos_에 CAS를 반복하므로 wait와 wake-up 비용은 피하지만, 실패한 CAS와 cache line ownership 경쟁에 CPU 시간을 사용할 수 있습니다.

따라서 최초 결과는 다음 가설로 이어졌습니다.

현재처럼 producer가 많고 각 queue operation이 짧은 workload에서는, SRWLOCK의 대기·재실행 비용보다 CAS의 과도한 재시도 비용이 더 클 수 있다. 그러므로 CAS 경합 비용을 줄여보자.

6. CAS 재시도에 Exponential Pause를 적용

가설에 따라 CAS 실패 직후 모든 producer 가 다시 CAS를 수행하면서 경합을 하는 횟수를 줄이기 위한 방법을 찾아보았습니다.

Win32 API 에서는 YieldProcessor라는 매크로를 제공하고 있습니다. x64 기반의 환경에서는 _mm_pause를 호출하게 되어 있는데, 이는 다음과 같은 동작을 가능하게 합니다.

따라서 SRWLOCK에서 발생하는 경합 과정 중의 wait 후 context 복구 과정 비용이 CAS 경합으로 인해 발생하는 비용보다 크다고 하면, pause를 통해 비용을 줄일 수 있다고 생각해볼 수 있겠습니다.

if (!enqueuePos_.compare_exchange_weak(
        pos,
        pos + 1,
        std::memory_order_relaxed,
        std::memory_order_relaxed))
{
    for (std::size_t count = 0; count < pauseCount; ++count)
        YieldProcessor(); // Windows x64에서는 _mm_pause

    pauseCount *= 2;
    if (pauseCount > 1024)
        pauseCount = 1024;

    continue;
}MutexFreeBoundedMpscQueue.cpp

processor에 spin-wait 중임을 알리고 다음 CAS까지의 active spin을 완화합니다. queue가 full일 때 호출하는 std::this_thread::yield()와도 역할이 다릅니다.

같은 Windows 환경과 workload에서 MutexLock을 먼저, CAS+Pause를 두 번째로 실행하는 묶음을 10회 반복했습니다.

구현Min/Max elapsedThroughput
MutexLock539.096 / 1,084.180 ms10.894 Mmsg/s
CAS + exponential pause159.037 / 235.814 ms41.857 Mmsg/s

이번 묶음에서는 CAS+Pause가 10회 모두 MutexLock보다 짧았고, 처리량은 약 3.84배였습니다. 이전 별도 세션의 CAS 처리량은 5.015 Mmsg/s였으므로 exponential pause가 현재 high-contention workload를 크게 개선했을 가능성을 확인했습니다.

7. Atomic을 사용하면 진짜 Lock-Free인가

Atomic 연산만 사용하고 MutexLock이 없다는 사실만으로 자료구조 전체가 lock-free가 되지는 않습니다.

현재 구조에서는 한 producer가 enqueue position을 예약한 뒤 message를 공개하기 전에 멈추면, consumer가 해당 slot을 지나갈 수 없습니다. 뒤의 producer가 다음 slot 작성을 끝내더라도 앞 slot이 준비되지 않았다면 FIFO 진행이 막힙니다.

이 실행 순서를 통해 다음 용어를 구분합니다.

따라서 최종 글에서는 현재 구현을 공식적인 의미의 lock-free queue로 단정하지 않고, Vyukov bounded queue 계열의 mutex-free bounded MPSC 변형으로 설명합니다.

8. 고성능 Queue는 무엇이 다른가

하나의 공유 cursor가 병목이라면 memory order나 padding만 조정하는 것으로는 확장성에 한계가 있습니다. 더 높은 처리량을 목표로 하는 queue는 공유 지점과 동기화 횟수 자체를 줄이는 방향을 사용합니다.

후보 구조는 다음과 같습니다.

각 구조는 ordering, memory usage, bounded capacity, NUMA locality와 구현 복잡도에서 서로 다른 계약을 가집니다. 따라서 “가장 빠른 MPMC queue”를 찾기보다 실제 producer/consumer 수와 필요한 ordering을 먼저 정해야 합니다.

참고할 고성능 MPSC Queue 구현

이 구현들은 현재 queue를 바로 교체하기 위한 정답 목록이 아닙니다. 공유 cursor, batch 처리, ordering과 bounded capacity 중 어떤 계약을 바꾸어 처리량을 얻는지 비교하기 위한 참고 자료입니다.

핵심 요약:

참고 자료

이 게시물은 학습한 내용을 바탕으로 초안을 작성한 뒤, LLM의 도움을 받아 내용을 검수하고 다듬어 완성되었습니다.

공유하기:
Share this post on XShare this post via email
이전 글
[C++] IOCP 2: NrRuntime의 Winsock I/O Pipeline과 Lifetime
다음 글
[C++] IOCP 1: OVERLAPPED I/O와 Completion Port