고성능 병렬 큐 (High-Performance Parallel Queue)

병렬 큐(Parallel Queue) 설계의 기초 통합 자료입니다. 커널 내부에 국한하지 않고 커널-커널, 커널-사용자, 사용자-사용자, 하드웨어 가속기, 분산 경계까지 아우르는 제출(submit)·완료(completion) 동기화 큐의 설계 공간을 정리합니다. 큐 타입 분류(SPSC/MPSC/SPMC/MPMC), 시나리오별 고려 사항과 대응 방안, 기존 구현 활용 방향과 완전 직접 구현(내재화) 방향을 모두 다루어, 독자가 자신의 요구에 맞는 조합을 선택할 수 있도록 돕는 것이 목적입니다.

개요

고성능 병렬 큐는 "작업을 넘겨주는 쪽(생산자)과 처리하는 쪽(소비자)이 서로 다른 실행 흐름에 있을 때, 최소한의 동기화 비용으로 작업과 결과를 주고받는" 구조입니다. 구체적으로는 다음 두 가지 기능이 항상 함께 필요합니다.

• 제출(submit) 큐 — 생산자가 작업을 소비자에게 전달하는 경로.
• 완료(completion) 큐 — 소비자가 처리 결과를 생산자(또는 완료 회수자)에게 돌려주는 경로.

이 문서에서 다루는 범위는 다음과 같습니다.

• 경계(Boundary) — 커널 내부 스레드(Thread)/인터럽트 간, 커널-사용자 공간, 사용자-사용자 공유 메모리, NIC·ASIC·FPGA·DPU 같은 하드웨어 가속기, RDMA 같은 분산 경계까지를 모두 포함합니다.
• 설계 축 — 큐 타입, 토폴로지, 알림, 흐름 제어, 메모리 모델, 실패 모드, 검증 방법.
• 구현 전략 — 기존 구현을 조합·재사용하는 방향과 라이브러리 없이 직접 구현하는 내재화 방향. 단일 선택지를 강요하지 않고, 시나리오별로 두 방향을 함께 제시합니다.

성능 수치 표기는 이 사이트의 규칙(재현 환경·출처 명시 원칙)을 따르며, 수치가 필요한 부분은 정성적 표현과 조건부 서술을 우선 사용합니다.

병렬 큐의 분류와 용어

병렬 큐는 생산자(Producer)와 소비자(Consumer)의 수 조합으로 분류합니다. S는 Single(단일), M은 Multiple(다중)을 뜻하며, 첫 글자가 생산자, 둘째 글자가 소비자입니다.

• SPSC — 단일 생산자·단일 소비자. 인덱스 충돌이 없어 가장 빠르며, kfifo의 기본 모드가 대표적입니다.
• SPMC — 단일 생산자·다중 소비자. 모든 소비자가 같은 흐름을 구독하는 읽기 전용(Read-Only) 패턴(브로드캐스트)에 적합합니다.
• MPSC — 다중 생산자·단일 소비자. 여러 실행 흐름이 작업을 넣고 한 곳에서 처리합니다. Lock-free 연결 리스트(Linked List, llist)와 완료 큐의 전형입니다.
• MPMC — 다중 생산자·다중 소비자. 누구나 넣고 누구나 뺄 수 있는 범용 큐로, DPDK rte_ring의 MPMC 모드와 Vyukov 큐가 대표적입니다.

인큐(Enqueue)는 큐에 항목을 넣는 연산, 디큐(Dequeue)는 항목을 꺼내는 연산입니다. 이 문서에서는 제출 큐의 인큐를 "제출", 완료 큐의 인큐를 "완료 게시", 완료 큐의 디큐를 "완료 회수"로 표현합니다. 두 큐가 한 쌍으로 동작하는 구조는 제출·완료 구조 절에서 자세히 다룹니다.

링 버퍼: 큐를 배열로 구현하는 원리

병렬 큐의 대부분은 고정 크기 배열을 원형으로 돌려 쓰는 링 버퍼(Ring Buffer)입니다. 배열 앞에서 항목을 꺼낼 때마다 나머지 항목을 앞으로 당기면 항목 수에 비례하는 복사 비용이 들기 때문에, 대신 head(다음에 쓸 위치)와 tail(다음에 읽을 위치) 두 개의 인덱스만 기억해 항목을 전혀 옮기지 않습니다.

• head — 다음에 항목을 쓸 위치. 생산자만 증가시킵니다.
• tail — 다음에 항목을 읽을 위치. 소비자만 증가시킵니다.

핵심은 인덱스를 0부터 다시 시작하지 않고 절대 카운터(Absolute Counter)로 계속 증가시키고, 배열 첨자만 나머지 연산으로 감싸는 것입니다. head와 tail이 "몇 바퀴를 돌았는지"를 함께 운반하므로 head == tail은 빈 상태, head - tail == size는 가득 찬 상태를 정확히 표현합니다. 만약 인덱스를 크기로 나눈 나머지만 저장하면 두 상태를 구분할 수 없어, 슬롯 하나를 항상 비워 두거나 별도의 길이 카운터가 필요해집니다.

배열 크기를 2의 거듭제곱으로 고정하면 나머지 연산이 비트 AND 한 번으로 줄어듭니다. i % size 대신 i & (size - 1)을 쓰는 이유입니다. 리눅스 커널의 kfifo도 이 설계를 그대로 따르며, 아래가 실제 구조(include/linux/kfifo.h, v6.12)입니다.

/* include/linux/kfifo.h (v6.12) — kfifo의 핵심 구조 */
struct __kfifo {
    unsigned int in;      /* 게시(put)된 항목 수 — 절대 카운터 */
    unsigned int out;     /* 소비(get)된 항목 수 — 절대 카운터 */
    unsigned int mask;    /* 크기 - 1 (크기는 반드시 2의 거듭제곱) */
    unsigned int esize;   /* 요소 하나의 바이트 크기 */
    void        *data;   /* 버퍼 시작 주소 */
};

/* 실제 매크로는 문장 표현식(statement expression) 형태지만 의미는 아래와 같습니다 */
#define kfifo_is_empty(fifo) ((fifo)->kfifo.in == (fifo)->kfifo.out)
#define kfifo_is_full(fifo)  ((fifo)->kfifo.in - (fifo)->kfifo.out > (fifo)->kfifo.mask)

왜 잠금으로는 부족한가: lock-free의 개념

이 절은 Lock-free 자료구조와 메모리 배리어 / 메모리 모델 문서의 핵심을, 큐 설계에 필요한 만큼만 다시 정리한 것입니다.

큐 연산(인큐·디큐) 전체를 잠금(Lock)으로 감싸면 정확성은 쉽게 얻을 수 있습니다. 문제는 성능입니다. 잠금을 쓰면 잠금 변수를 둘러싼 캐시라인(Cache Line)의 소유권(Ownership)이 CPU 사이를 옮겨 다니며, 잠금을 잡지 못한 CPU는 홀더가 해제할 때까지 멈춰 있어야 합니다. 코어 수가 늘수록 이 대기 시간(Latency)이 누적되어, 오히려 처리량이 줄어드는 구간이 생깁니다.

lock-free는 "잠금을 아예 쓰지 않고, 원자적 연산(Atomic Operation)으로 공유 상태를 한 번에 갱신"하는 방식입니다. 대표적인 원자적 연산이 CAS(Compare-and-Swap)입니다. CAS는 "메모리 값이 내가 기대한 값과 같으면 새 값으로 교체하고 성공을, 다르면 아무것도 바꾸지 않고 실패를 돌려주는" 단일 연산입니다.

/* CAS(Compare-and-Swap) — 읽고-비교하고-쓰는 동작을 하나의 원자적 연산으로 */
int old = atomic_read(&x);            /* 기대값 읽기 */
int cur = atomic_cmpxchg(&x, old, old + 1);  /* x == old 이면 old+1 로 교체 */
if (cur == old) {
    /* 성공 — x를 갱신한 유일한 실행 흐름 */
} else {
    old = cur;   /* 실패 — 누군가 먼저 갱신함. 최신 값으로 즉시 재시도 */
}

CAS가 성공하는 실행 흐름은 순간에 하나뿐이지만, 실패한 쪽은 "되어 있는 값"을 읽고 즉시 재시도하면 되므로 잠금처럼 남의 해제를 기다리지 않습니다. 이 성질 덕분에 잠들 수 없고 선점(Preemption)될 수도 없는 콘텍스트(예: 인터럽트, NMI)에서도 사용할 수 있습니다. 커널에서 lock-free는 흔히 시스템 전체의 진행을 의미합니다. 즉 어떤 실행 흐름이 중간에 죽거나 멈춰도 나머지 흐름은 반드시 진행할 수 있어야 합니다(더 강한 보장인 wait-free는 각 흐름이 유한한 단계 안에 끝납니다). 이 기준에서 보면 Vyukov 큐는 "모든 흐름의 무한 진행"을 보장하지 않으므로 완전한 lock-free가 아닌데, 이 점은 뒤의 직접 구현(내재화) 방향 절에서 다시 짚습니다.

이 그림에서 보듯 어느 쪽이든 공유되는 캐시라인 자체는 존재하므로, 경합(Contention)을 줄이는 것은 큐 토폴로지(공유 vs 분할)의 몫입니다. 이 점은 설계 고려 축 절에서 다룹니다.

제출·완료 구조와 방향 비대칭

요구 사항이 "1 생산자 : N 소비자"라면, 완료 방향을 함께 설계해야 합니다. N개의 소비자가 각자의 처리를 마치고 결과를 게시하므로 완료 큐는 항상 MPSC 이상이 됩니다. 완료 회수자(Reaper)가 생산자 1명이면 MPSC, 완료 회수자도 여러 명이면 MPMC입니다. 따라서 일반적인 구성은 다음과 같습니다.

• 제출 경로 — 생산자 1명이 N개의 per-consumer SPSC 링에 작업을 분산(팬아웃).
• 완료 경로 — N명의 소비자가 결과를 집계하는 MPSC(또는 MPMC) 링에 게시하고, 완료 회수자가 읽습니다.

이 구조의 변형으로는 완료 회수자 다중화(Multiplexing)(MPMC 완료 링 + 복수 회수자), 완료 곧바로 재제출(완료 항목이 다음 파이프라인(Pipeline) 단계의 제출 링으로 재인큐되는 형태), 완료 통합·간소화(오류가 있는 항목만 별도 큐로 보내는 형태)가 있습니다. 어떤 변형을 쓰든, 제출과 완료의 큐 타입을 "각각 독립적으로" 결정해야 합니다.

설계 고려 축과 대응 방안

어떤 큐를 만들든 다음 여덟 가지 축을 빠짐없이 점검해야 합니다. 각 축은 서로 독립적이지 않으며, 특히 순서·알림·백프레셔는 토폴로지 선택과 강하게 결합됩니다.

위 축 중에서도 토폴로지(공유 vs 분할)는 가장 큰 분기점입니다. 공유 MPMC 링 하나는 구현이 단순하고 순서 보장이 쉽지만, 원자적 연산이 머리·꼬리 인덱스에 집중되어 코어 수가 늘어나면 Lock-free 자료구조 문서의 캐시라인(Cache Line)·거짓 공유(False Sharing) 분석에서 설명하는 확장성 한계에 부딪힙니다. 분할 SPSC 팬아웃은 경합이 없어 대규모 코어에서 유리하지만, 부하 불균형과 순서 약화를 감수해야 합니다.

시나리오: 커널 ↔ 커널

커널 내부에서 커널 스레드(Kernel Thread), 인터럽트(Interrupt) 처리기, softirq, 작업 큐(Workqueue) 워커 사이에 작업을 전달하는 경로입니다. 가장 일반적인 형태는 "하드웨어 인터럽트가 패킷(Packet)·이벤트를 받아서 작업 큐에 밀어넣고, 워커 스레드가 배치로 처리하는" 구조입니다.

고려 사항

• 컨텍스트 안전성 — 인터럽트 처리기(Interrupt Handler)에서는 절전(sleep) 불가, 스핀락(Spinlock)만 사용 가능합니다. 큐 연산이 인터럽트 처리기에서 호출되면 lock-free여야 합니다.
• NMI-safe — NMI 처리기에서도 안전해야 하면 objpool처럼 per-CPU 슬롯 분리, 사전 할당(런타임 메모리 할당 없음), raw_local_irq_save + try_cmpxchg만 사용하는 설계를 검토합니다. llist 계열을 NMI에서 쓸 때는 CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG가 필요합니다.
• 스케줄러(Scheduler) 상호작용 — 워커가 큐를 폴링할 때 CPU를 태우는 폴링 루프가 되지 않도록 웨이크업 경로가 필요합니다.
• 배치 처리 — 항목 하나마다 웨이크업하면 스래싱(Thrashing)이 발생하므로, 일정 개수·시간 단위 배치를 권장합니다.

기존 구현 활용

• 작업 큐(CMWQ) — "단일 인터럽트 처리기 → 여러 per-CPU 워커"가 사실상 1P:N 제출의 표준입니다. 자체 큐를 만들기 전에 가장 먼저 검토할 대상입니다. 다만 웨이크업과 동적 워커 관리 오버헤드가 있어 극단적 저지연 경로에는 부적합할 수 있습니다.
• llist(Lock-free Linked List) — MPSC 연결 리스트로, softirq→커널 스레드 같은 다중 생산자·단일 소비자 경로에 적합합니다. 생산은 llist_add를 잠금 없이 쓰고, 소비는 단일 소비자면 llist_del_first, 다중 소비자면 llist_del_all로 나눠 갖습니다(del_all 결과는 역순이라 llist_reverse_order로 뒤집습니다).
• kfifo — SPSC(또는 잠금(Lock)을 얹은 MPSC) 원형 버퍼(Buffer)로, 드라이버에서 수신 버퍼 용도로 사용합니다.
• Ptr Ring(struct ptr_ring) — 유계 FIFO 포인터 링으로, 한쪽 CPU 생산 + 한쪽 CPU 소비가 최적이며 생산·소비 스핀락으로 다중 CPU도 허용합니다(ptr_ring_consume_batched로 배치 소비 가능). 네트워크 코어 경로에서 사용합니다.
• 완료 신호 — 작업 결과가 "값"이 아니라 "끝났다"는 신호만 필요하면 완료 변수(Completion)를 사용합니다. Completion의 complete_all()은 N명 대기자를 한 번에 깨우는 완료 회수 브로드캐스트로 쓸 수 있습니다.

직접 구현 방향

• 인터럽트 처리기에서 잠금 없이 항목을 넣고, 워커는 직접 구현 절의 SPSC·배치 디큐로 처리하는 형태를 권장합니다.
• 인터럽트 처리기에서 큐가 가득 찼을 때의 동작(드롭 카운터 증가, 재시도, NAPI 식 예산)을 미리 정의합니다.
• KCSAN으로 경쟁 조건(Race Condition)을, LKMM/litmus로 순서를 검증합니다.

시나리오: 커널 ↔ 사용자

커널과 사용자 공간(User Space) 사이의 제출·완료 큐입니다. 이 경계에서는 시스템 콜(System Call) 오버헤드와 데이터 복사 비용이 지배적이며, 이를 제거하기 위해 메모리 맵(Memory Map) 공유 링을 사용합니다.

고려 사항

• 시스템 콜 제거 — 제출마다 write() 같은 시스템 콜을 하면 모드 전환·검증 오버헤드(Overhead)가 요청마다 누적되어 처리량이 크게 제한됩니다. 공유 메모리 링 + 폴링(SQPOLL)으로 시스템 콜 없이 제출·완료를 교환합니다.
• 페이지(Page) 수명 — 사용자 페이지를 고정(pin)하거나, 링 메모리를 커널이 할당해 mmap으로 노출해야 안전합니다. hugetlb 사용도 고려합니다.
• 알림 — 사용자가 블로킹 대기해야 하면 eventfd(또는 futex)로 완료를 알리고, 폴링을 원하면 CQ를 직접 폴링하게 합니다.
• 보안 — 사용자가 제공하는 포인터·길이는 반드시 검증해야 합니다. io_uring은 이 때문에 엄격한 검증과 restrictions 기능을 둡니다.

기존 구현 활용

• io_uring — 이 경계의 사실상 표준입니다. SQE(제출 큐 엔트리) 링과 CQE(완료 큐 엔트리) 링을 mmap으로 공유하고, IORING_SETUP_SQPOLL로 커널 스레드가 제출을 폴링하게 만들어 제출 시스템 콜을 없앱니다. 완료 알림은 IORING_REGISTER_EVENTFD(eventfd)로, 버퍼는 제공 버퍼 링(IORING_REGISTER_PBUF_RING)과 multishot 수신으로, 링 간 메시지는 IORING_OP_MSG_RING으로 처리합니다. io_uring (Async I/O) 문서의 링 버퍼 동작 원리, 메모리 배리어, eventfd, multi-ring 절이 설계 참고가 됩니다. 직접 만든 큐를 쓰기 전에 io_uring의 기능이 요구를 충족하는지 먼저 확인하는 것이 안전합니다.
• AF_XDP — 패킷 경로에 특화된 4-링 모델(RX/TX/FILL/COMP)입니다. FILL(사용자가 버퍼를 커널에 반환)과 COMP(커널이 버퍼 사용 완료를 통지)가 제출·완료 큐 쌍의 전형입니다. AF_XDP (XDP Sockets) 문서의 큐 구조와 zero-copy 모드가 참고가 됩니다.
• perf/relay 링 버퍼 — 커널 → 사용자 단방향 SPSC 스트림으로, 추적 데이터 전달에 사용합니다(Lock-free 자료구조의 SPSC 절 참조).

직접 구현 방향

• 커널이 링 메모리를 kzalloc으로 만들고 mmap으로 노출하는 형태로 시작합니다. head/tail 인덱스는 메모리 배리어 / 메모리 모델에 따라 release/acquire로 교환합니다.
• 제출 알림이 필요하면 eventfd를 링과 함께 노출하고, 커널이 CQE 게시 후 eventfd_signal()을 호출합니다.
• 사용자가 준 버퍼를 참조하는 방식은 피하고, "커널 소유 메모리 + 사용자 작업 기술자(Descriptor)" 모델을 기본으로 합니다.

시나리오: 사용자 ↔ 사용자

같은 호스트에서 서로 다른 프로세스 사이에 공유 메모리로 큐를 만드는 경로입니다. 커널을 거치지 않는 데이터 경로가 목표이므로, 순수 데이터 전송은 lock-free 공유 링 + 알림만 커널(futex)을 사용합니다.

고려 사항

• 공유 메모리 생성 — memfd 또는 hugetlb 파일을 mmap으로 여러 프로세스에 매핑(Mapping)합니다. 로컬 파일시스템(Filesystem)이므로 파편화와 페이지 폴트(Page Fault) 비용을 고려해 크기를 잡습니다.
• 블로킹 대기 — 링이 비어 있거나 가득 찼을 때 스핀하지 않고 대기하려면 futex를 큐 인덱스와 연동합니다(시퀀스 기반 futex 웨이크).
• 프로세스 크래시 — 소비자가 죽으면 생산자가 영원히 블록할 수 있습니다. 하트비트·타임아웃·에포크(epoch) 검증으로 좀비 상태를 감지합니다.
• 격리(Isolation) — 공유 메모리에 포인터를 그대로 저장하면 다른 프로세스 주소 공간(Address Space)에서 유효하지 않으므로, 오프셋(Offset)·인덱스·시퀀스 번호로 참조를 표현합니다.

기존 구현 활용

• DPDK rte_ring — SPSC/MPSC/SPMC/MPMC 네 모드를 메모리 풀과 함께 제공합니다. 공유 메모리 위에서 동작하므로 U2U의 기본 선택지입니다. DPDK 문서의 Ring 절이 참고가 됩니다.
• vhost-user — virtqueue 프로토콜을 사용자 공간에서 구현한 것으로, "게스트 드라이버 → 사용자 데이터플레인 프로세스"의 제출·완료 경로를 그대로 재현합니다(virtio / vhost 참조).
• futex — 대기·깨우기(Wakeup) 전용 프리미티브로 큐와 조합합니다(Futex (Fast Userspace Mutex)).

직접 구현 방향

• Vyukov 큐(시퀀스 번호 + CAS)를 공유 메모리에 배치하는 것이 표준 내재화 경로입니다. 크래시 복구를 위해 링 메타데이터(머리·꼬리, 에포크)를 별도 캐시라인에 두고 주기적으로 검증합니다.
• 생산자·소비자가 각 CPU에 고정(pinning)되면 SPSC로 충분하며, 이 경우 futex 대기조차 줄일 수 있습니다.

시나리오: 하드웨어 가속기(ASIC·NIC·FPGA·DPU)

NIC, SmartNIC, FPGA 가속기, 보안 처리 ASIC 등 하드웨어와 호스트 CPU 사이의 제출·완료 큐입니다. 하드웨어 큐는 아래 세 가지가 소프트웨어 큐와 근본적으로 다릅니다.

• 게시 = 도어벨(Doorbell) — 인덱스 갱신을 MMIO 쓰기로 하드웨어에 알립니다. 소프트웨어의 "시스템 콜" 대신 MMIO 쓰기 비용이 듭니다.
• 완료 = 인터럽트 또는 폴링 — 하드웨어가 완료 큐에 항목을 쓰고 MSI-X 인터럽트를 발생시키거나, 호스트가 완료 링을 폴링합니다.
• 메모리 = DMA 일관성 — 링 메모리는 장치가 접근하므로 일관성(Coherency)과 배리어가 장치 규격(PCIe 메모리 모델)에 따라 결정됩니다. 디스크립터 필드 작성 후 dma_wmb(), 소유권 비트 확인 후 dma_rmb()로 장치가 보는 순서를 보장합니다(상세는 네트워크 드라이버 구현 가이드의 DMA 배리어 절 참조).

고려 사항

• 링 메모리 배치 — head/tail과 슬롯을 장치가 요구하는 정렬로 배치하고, 캐시라인(Cache Line) 단위로 분리합니다.
• 배치 게시 — 도어벨은 비싸므로 여러 항목을 쌓아 한 번에 게시합니다.
• 인터럽트 폭풍 — 완료 인터럽트를 항목 1개마다 발생시키면 CPU가 인터럽트에 잠식됩니다. 코얼레싱(Coalescing)으로 인터럽트를 모아 발생시킵니다.
• 가상화(Virtualization) 경계 — 게스트가 하드웨어를 직접 제어하지 못하는 경우 virtio/vDPA가 중계합니다.

기존 구현 활용

• virtio/vDPA — virtqueue는 분할(split) 형식(디스크립터 테이블 desc + avail 링 + used 링)과 압축(packed) 형식(단일 디스크립터 링 + 이벤트 억제)을 정의합니다. used 링 항목이 id/len으로 완료를 돌려주고 VRING_DESC_F_NEXT/WRITE/INDIRECT 플래그가 제출·완료 시맨틱을 규정합니다. 소프트웨어 구현(vhost-user)과 하드웨어 오프로드(vDPA)가 같은 API로 묶여 "호스트 소프트웨어 큐 → 실리콘 큐" 전환의 표준 참고입니다.
• NVMe·NIC 멀티큐 — per-CPU 제출 큐 + 공유 완료 큐 형태로, 분할 제출·집계 완료의 산업 표준입니다. io_uring은 이 링에 직접 붙습니다.
• AF_XDP zero-copy — 드라이버가 RX/TX 링을 직접 채우는 경로로, 하드웨어 링과 사용자 링 사이의 연결 예시입니다.

직접 구현 방향

• 장치별로 MMIO 도어벨, 완료 인터럽트, DMA 링 규격이 다르므로, "공통 큐 코어(소프트웨어 링 로직)"와 "장치 어댑터(도어벨·인터럽트)"를 분리해 추상화합니다.
• 보안 처리 ASIC처럼 "기능별 병렬 프로세서" 구조(예: 네트워크 처리·패턴 매칭·암호화(Encryption)를 각각 담당하는 프로세서)에 붙인다면, 입력단에서 해시(Hash)로 per-processor SPSC 링에 팬아웃하고 완료는 MPSC로 재집계하는 토폴로지가 단일 파이프라인 처리(패킷당 1회 패스)와 잘 맞습니다.
• 하드웨어 큐에서는 순서 보장(Ordering)이 장치 규격에 종속되므로, 순서가 필요한 요청은 별도 시퀀스 번호를 부여해 소프트웨어에서 재정렬하는 설계를 준비합니다.

시나리오: 분산·네트워크 경계

RDMA(InfiniBand, RoCE)처럼 네트워크를 가로지르는 제출·완료 큐입니다. 큐 쌍(Queue Pair, QP)은 전송 큐(Send Queue, SQ)와 수신 큐(Receive Queue, RQ)로 구성되며, 완료 큐(Completion Queue, CQ)는 가장 오래된 "하드웨어 제출·완료" 설계 중 하나입니다.

• 제출 — post_send/post_recv로 작업 요청(Work Request, WR)을 큐에 넣습니다. Send·Recv 외에 RDMA Write/Read, Atomic(CAS/FAA) 같은 원격 메모리 직접 접근 동작이 있으며, 여러 WR을 한 번에 게시(batch post)하고 도어벨을 한 번 울리는 배치 제출이 일반적입니다. 각 WR은 하나 이상의 산포·수집 요소(SGE, Scatter/Gather Element)로 데이터 버퍼를 지정합니다.
• 완료 — 장치가 완료 큐 엔트리(CQE)를 쓰고, 호스트는 poll_cq로 폴링하거나 완료 채널(Completion Channel) 이벤트로 대기합니다. 완료 항목(Work Completion, WC)에는 wr_id, 성공/실패 상태, 전송 바이트 수가 포함되며, 여러 QP가 하나의 CQ를 공유할 수 있습니다.
• 메모리 등록 — 데이터 버퍼는 HCA에 등록한 메모리 영역(Memory Region, MR)으로 참조되며, 원격 접근은 rkey 권한에 의존합니다. 큐 항목에는 실제 데이터가 아니라 "기술자(Descriptor) + 키"만 들어갑니다.
• 시맨틱 차이 — 로컬 lock-free 큐는 "메모리 순서만" 보장하면 되지만, 분산 큐는 전송 자체가 무순서(비순차 도착)일 수 있어 완료 순서와 재전송(Retransmission)·누락 처리·원격 접근 권한이 추가로 필요합니다. 완료 도착 시점은 요청 게시 순서와 어긋날 수 있으므로, 순서가 중요한 요청은 시퀀스 번호를 함께 보내 소비자 측에서 재정렬합니다.

분산 경계에서 큐를 직접 구현하려면 네트워크 전송 계층까지 책임져야 하므로, 일반적으로 RDMA Verbs 또는 메시지 전달 라이브러리를 재사용하고, 자체 큐는 "로컬 송수신 측의 배치 버퍼"로만 관여하는 것이 현실적입니다. 이 문서에서는 InfiniBand / RDMA 문서를 참고 자료로 연결합니다.

기존 구현 활용 방향

기존 구현을 조합해 요구를 충족하는 것이 항상 첫 번째 후보입니다. 자체 구현은 검증·유지보수 비용이 크므로, 아래 표를 기준으로 "왜 기존 구현으로 안 되는지"를 먼저 명확히 하고 넘어가는 것이 원칙입니다.

활용 전략의 핵심은 계층 조합입니다. 예를 들어 "커널 인터럽트 → 작업 큐 분산 → 사용자 io_uring 완료 통지"처럼, 각 경계에서 가장 검증된 구현을 골라 잇는 것이 단일 구현을 확장하는 것보다 안전합니다. 기존 구현으로 안 되는 대표적인 경우는 다음과 같습니다.

• 요구 큐 타입이 특정 구현의 고정 타입과 다른 경우(예: io_uring CQ가 가지는 고정 시맨틱과 다른 완료 순서가 필요한 경우).
• 하드웨어 규격(도어벨 오프셋, 링 정렬, 인터럽트 방식)이 기존 추상화로 표현되지 않는 경우.
• 순서·알림·우선순위의 조합이 기존 구현의 옵션으로 조합되지 않는 경우.

메모리 순서: 왜 release/acquire가 필요한가

lock-free 큐는 "항목 쓰기 → 인덱스 게시"라는 두 단계로 동작한다고 했습니다. 그런데 컴파일러와 CPU는 서로 관련이 없어 보이는 메모리 접근의 순서를 바꿀 수 있습니다. 이를 순서 재배열(Reordering)이라고 합니다. 다음 코드를 보겠습니다.

/* 잘못된 예 — 순서 보장이 없으면 소비자가 미완성 항목을 볼 수 있음 */
WRITE_ONCE(r->slots[i], item);   /* ① 항목 쓰기 */
WRITE_ONCE(r->head, i + 1);   /* ② 인덱스 게시 */

소비자는 head가 i+1이 된 것을 확인한 뒤에야 슬롯을 읽습니다. 그런데 CPU가 ②를 먼저 실행하거나(원인 중 하나는 CPU 내부의 쓰기 버퍼(Store Buffer)입니다), 소비자 CPU가 ②의 새 값을 먼저 보게 되면? 소비자는 아직 ①의 쓰기가 끝나지 않은 슬롯을 읽게 됩니다. 정확한 큐라면 절대 있어서는 안 되는 동작입니다.

이것을 막는 것이 release/acquire 한 쌍입니다. release 쓰기는 "이 쓰기보다 앞선 모든 메모리 쓰기가, 이 값을 읽는 쪽에는 반드시 먼저 보이도록" 보장하고, acquire 읽기는 "이 읽기가 관측한 값 이후의 모든 메모리 읽기가, 그 값이 게시한 상태를 반드시 보도록" 보장합니다. 정리하면 다음과 같습니다.

/* 올바른 예 — 항목 쓰기(일반 쓰기) 다음에 release로 게시 */
WRITE_ONCE(r->slots[i], item);          /* ① 항목 쓰기 */
smp_store_release(&r->head, i + 1);    /* ② release 게시 */

/* 소비자: acquire로 head를 읽으면, 그 뒤의 슬롯 읽기는 게시된 항목을 반드시 봄 */
u32 head = smp_load_acquire(&r->head);   /* ③ acquire 확인 */

여기서 WRITE_ONCE/READ_ONCE는 "한 번의 메모리 접근으로 읽고 쓴다"는 보장으로, 중간 값을 쪼개서 보는 일을 막습니다. 이 보장만으로는 순서가 잡히지 않으므로 release/acquire와 함께 써야 합니다. 구체적인 게시·확인 순서와 다이어그램은 아래 직접 구현(내재화) 방향 절의 SPSC 예제에서 다룹니다. 재배열이 왜 일어나는지(스토어 버퍼, 파이프라인)와 더 많은 사례는 메모리 배리어 / 메모리 모델 문서를 참조합니다.

직접 구현(내재화) 방향

직접 구현을 선택했다면, 이 절의 알고리즘 카탈로그에서 시작합니다. 모든 직접 구현은 다음 원칙을 따른 것입니다: 데이터 경로에 잠금을 두지 않고, 원자적 연산과 메모리 배리어(Memory Barrier)로 순서를 보장합니다.

SPSC 링(가장 기본)

head/tail 인덱스를 각각 생산자·소비자가 독점해서 갱신하면 원자적 연산이 거의 필요 없습니다. 항목 게시는 smp_store_release, 게시 확인은 smp_load_acquire로 합니다.

/* 단일 생산자·단일 소비자(SPSC) 링 — 인덱스만 순서 보장하면 됩니다 */
struct spsc_ring {
    u32 size;              /* 2의 거듭제곱 크기 */
    u32 mask;
    u32 head;             /* 생산자 전용 기록 지점 */
    u32 tail;             /* 소비자 전용 기록 지점 */
    void *slots[];        /* 항목 배열 */
};

bool spsc_push(struct spsc_ring *r, void *item)
{
    u32 head = READ_ONCE(r->head);
    u32 tail = READ_ONCE(r->tail);

    if ((head - tail) >= r->size)
        return false;          /* 가득 참 — 백프레셔 */
    WRITE_ONCE(r->slots[head & r->mask], item);
    smp_store_release(&r->head, head + 1);  /* 항목 게시 */
    return true;
}

void *spsc_pop(struct spsc_ring *r)
{
    void *item;
    u32 tail = READ_ONCE(r->tail);
    u32 head = smp_load_acquire(&r->head);

    if (tail == head)
        return NULL;           /* 비어 있음 */
    item = READ_ONCE(r->slots[tail & r->mask]);
    WRITE_ONCE(r->tail, tail + 1);     /* 슬롯 반환 */
    return item;
}

MPMC 링(Vyukov 큐 코어)

생산자·소비자가 여럿이면 머리·꼬리 인덱스를 CAS로 독점하고, 슬롯마다 시퀀스 번호를 두어 "쓰기 완료"와 "해제 완료"를 구분합니다. 아래 코드는 개념 설명용 축약이며, 실제 구현에서는 게시·해제 순서에 release/acquire 의미론(atomic_set_release 등)을 정확히 적용해야 합니다.

/* 다중 생산자·다중 소비자(MPMC) 링 — Vyukov 큐의 핵심 구조 */
#define MPMC_SIZE 1024              /* 2의 거듭제곱 */

struct mpmc_slot {
    atomic_t seq;              /* 슬롯 시퀀스 번호 */
    void *item;                 /* 항목 포인터 */
};

struct mpmc_queue {
    struct mpmc_slot slots[MPMC_SIZE];
    atomic_t head;            /* 다음 인큐 위치 */
    atomic_t tail;            /* 다음 디큐 위치 */
};

void mpmc_init(struct mpmc_queue *q)
{
    int i;
    for (i = 0; i < MPMC_SIZE; i++)
        atomic_set(&q->slots[i].seq, i);
    atomic_set(&q->head, 0);
    atomic_set(&q->tail, 0);
}

bool mpmc_push(struct mpmc_queue *q, void *item)
{
    for (;;) {
        struct mpmc_slot *s;
        u32 head = atomic_read(&q->head);
        s = &q->slots[head & (MPMC_SIZE - 1)];
        if (atomic_read(&s->seq) != head)
            return false;        /* 아직 비워지지 않음 — 가득 참 */
        if (atomic_cmpxchg(&q->head, head, head + 1) == head) {
            WRITE_ONCE(s->item, item);
            atomic_set(&s->seq, head + 1);   /* 게시: 소비자가 읽을 수 있는 상태 */
            return true;
        }
    }
}

void *mpmc_pop(struct mpmc_queue *q)
{
    for (;;) {
        struct mpmc_slot *s;
        void *item;
        u32 tail = atomic_read(&q->tail);
        s = &q->slots[tail & (MPMC_SIZE - 1)];
        if (atomic_read(&s->seq) != tail + 1)
            return NULL;         /* 아직 게시 전 — 비어 있음 */
        item = READ_ONCE(s->item);
        if (atomic_cmpxchg(&q->tail, tail, tail + 1) == tail) {
            atomic_set(&s->seq, tail + MPMC_SIZE);  /* 슬롯 해제 */
            return item;
        }
    }
}

위 예제는 가득 참·비어 있음 시 false/NULL을 반환하는 비블로킹 변형입니다. Dmitry Vyukov의 원본 bounded MPMC 큐(1024cores)는 가득 참·비어 있음 시 스핀으로 대기하는 블로킹 변형이며, "모든 스레드의 무한 진행을 보장하는 공식 의미의 lock-free"는 아닙니다. 원본은 enqueue_pos/dequeue_pos를 서로 다른 캐시라인(Cache Line)에 두고 각 슬롯도 캐시라인 단위 패딩으로 분리해 거짓 공유(False Sharing)를 방지합니다. 위 예제는 원본의 핵심 구조(슬롯 시퀀스 번호, 머리·꼬리 1회 CAS)를 따르되, 실제 구현에는 캐시라인 배치와 release/acquire 의미론(atomic_set_release 등)을 반드시 추가해야 합니다.

MPSC 링(llist 기반)

완료 큐의 전형인 MPSC는 커널의 llist(Lock-free Linked List)가 사실상 표준입니다. llist는 단일 연결 리스트의 머리(head) 갱신을 원자적 교환 하나로 처리하므로, 생산자는 노드를 항목에 내장해 llist_add()만 호출하면 됩니다. 아래가 실제 구조(include/linux/llist.h, v6.12)입니다.

/* include/linux/llist.h (v6.12) — 머리만 있는 lock-free 단일 연결 리스트 */
struct llist_head {
    struct llist_node *first;   /* 원자적으로 교체되는 머리(xchg/CAS) */
};

struct llist_node {
    struct llist_node *next;    /* 생산자가 쓰는 동안 아무도 읽지 않음 */
};

/* 생산자(다중): 머리를 CAS로 교체 — 잠금 없음 */
static inline bool llist_add(struct llist_node *new,
                          struct llist_head *head)
{
    return llist_add_batch(new, new, head);  /* lib/llist.c: cmpxchg 기반 */
}

/* 소비자(단일): 전체를 한 번에 꺼냄 */
static inline struct llist_node *llist_del_all(struct llist_head *head)
{
    return xchg(&head->first, NULL);
}

사용 패턴은 아래와 같습니다. 항목 구조체(Struct)에 llist_node를 내장하고, 소비자는 덩어리째 꺼낸 뒤 순서를 되돌려 처리합니다.

/* MPSC 사용 패턴 — 항목에 llist_node를 내장하고 머리만 공유 */
struct work_item {
    struct llist_node node;   /* 반드시 첫 필드일 필요는 없음 */
    u32 kind;
};

static LLIST_HEAD(work_head);   /* 전역 머리 */

/* 인터럽트 처리기 등 여러 실행 흐름에서 호출 가능 */
static void submit_work(struct work_item *w)
{
    llist_add(&w->node, &work_head);
}

/* 단일 소비자(커널 스레드) — 한 번에 모두 꺼내 역순 복원 후 처리 */
static void drain_work(void)
{
    struct llist_node *n = llist_del_all(&work_head);
    struct work_item *w;

    n = llist_reverse_order(n);   /* 최신→최고 순서를 최고→최신으로 */
    while (n) {
        w = llist_entry(n, struct work_item, node);
        n = n->next;
        process_one(w);
    }
}

llist의 두 가지 주의점을 기억합니다. 첫째, llist_del_all()이 돌려주는 연결은 "가장 최근에 넣은 것부터"이므로 순서 복원에 llist_reverse_order()가 필요합니다. 즉 llist로는 전역 FIFO 순서를 보장할 수 없습니다 — 순서가 필수라면 링 버퍼 계열을 검토합니다. 둘째, 소비자가 여러 명이면 llist_del_first()를 동시에 쓸 수 없습니다(헤더 주석의 표: del_first는 다른 소비자의 del_first/del_all과 잠금이 필요). 다중 소비자는 llist_del_all()로 덩어리째 가져가 나누는 방식이 안전합니다. NMI 처리기에서 쓸 때는 CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG가 필요하며, 이 점은 커널 ↔ 커널 시나리오에서도 언급했습니다.

알고리즘 카탈로그

검증 절차

• LKMM/litmus — 커널 메모리 모델로 배리어 배치가 순서를 보장하는지 검증합니다(Lock-free 자료구조의 검증 절 참조).
• KCSAN — 런타임 데이터 경쟁 검출기로 실제 실행에서 경쟁 조건(Race Condition)을 찾습니다.
• 스트레스 테스트 — 생산자·소비자 수, 배치 크기, 링 크기를 바꿔가며 정확성(누락·중복 없음)을 확인합니다.

SPSC 링의 "항목 쓰기 → head 게시 → acquire 확인 → 슬롯 읽기" 순서는 커널 메모리 모델의 공식 litmus 테스트 MP+pooncerelease+poacquireonce(tools/memory-model/litmus-tests/, v6.12)와 같은 패턴이며, 이 테스트의 결과는 Never입니다(잘못된 결과 exists (1:r0=1 /\ 1:r1=0)가 발생하지 않음).

/* C MP+pooncerelease+poacquireonce — 커널 공식 litmus 테스트(v6.12) */
/* smp_store_release()/smp_load_acquire()가 메시지 전달(message-passing) 순서를 보장하는지 검증 */

P0(int *buf, int *flag)   /* 생산자(Producer) */
{
    WRITE_ONCE(*buf, 1);
    smp_store_release(flag, 1);
}

P1(int *buf, int *flag)   /* 소비자(Consumer) */
{
    int r0;
    int r1;

    r0 = smp_load_acquire(flag);
    r1 = READ_ONCE(*buf);
}

exists (1:r0=1 /\ 1:r1=0)   /* 나쁜 결과(Bad outcome) — 허용되면 안 됨. 이 테스트의 결과는 Never */

선택 가이드(의사결정 절차)

아래 질문을 순서대로 따라가면 대부분의 요구에서 초안 설계가 나옵니다. 각 질문의 답은 다음 질문의 입력이 됩니다.

실제 사례로 "패킷 수신 → 보안 검사 3단계 파이프라인 → 완료 통지"를 생각하면, 단계 1에서 1P:N 및 완료 회수 1명이므로 제출 = SPSC 팬아웃, 완료 = MPSC가 나오고, 단계 4에서 데이터 경로는 폴링(CPU 고정), 단계 5에서 큐 가득 참은 드롭 + 카운터, 단계 6에서 기존의 작업 큐+NAPI 흐름으로 충분하면 재사용, 부족하면 자체 링으로 진행하는 결론이 나옵니다.

실패 모드와 대응 방안

병렬 큐의 버그는 대부분 미세한 타이밍 문제로 나타나므로, 아래 실패 모드를 설계 단계에서부터 점검합니다.

성능 평가와 운영 검증

병렬 큐는 구현 정확성과 성능을 분리해서 검증해야 합니다. 정확성은 위 검증 절차로, 성능은 아래 원칙으로 측정합니다.

• 재현 환경 명시 — CPU 모델, 코어 수, 커널 버전, 큐 크기, 생산자·소비자 수, 워크로드를 보고해야 합니다. 이 사이트의 성능 최적화 문서와 동일한 표기 규칙(측정 환경·출처 명시)을 따릅니다.
• 프로파일링(Profiling) — perf(CPU 사이클, 캐시 미스, 원자적 연산), ftrace(경로 지연), /proc/interrupts(완료 인터럽트 분포)로 병목을 확인합니다.
• 경합 측정 — 생산자·소비자 수를 바꿔가며 처리량·지연을 기록하고, 공유 큐 대비 분할 큐의 경합 차이를 확인합니다.
• 부하 변동 — 짧은 시간에 몰리는 연속 입력(burst), 큐 가득 참 상황, 소비자 지연(스케줄 지연) 상황을 포함해 백프레셔 동작을 관찰합니다.

수치를 문서화할 때는 단일 숫자 대신 범위와 조건을 함께 표기하고, 근거 없는 구체 수치는 넣지 않습니다.