C++20으로 M:N 스케줄러를 밑바닥부터 구현한 교육용 프로젝트 (EBR, Work-Stealing)

C++20으로 M:N 스케줄러를 밑바닥부터 구현한 교육용 프로젝트

C++20 코루틴을 활용해 M:N 비동기 런타임을 처음부터 직접 만들어본 교육용 프로젝트 tiny_coro가 공개됨. Seastar나 Folly 같은 산업용 라이브러리의 복잡한 래퍼를 걷어내고, 고성능 동시성 런타임의 핵심 개념만 약 1,000줄의 코드로 보여주는 것이 목표임.

핵심 컴포넌트 구성

• M:N 스레딩 모델: M개의 코루틴을 N개의 커널 스레드에 매핑해 멀티코어 성능을 최대한 활용함
• Work-Stealing 스케줄링: Chase-Lev Lock-Free Deque 기반으로, 유휴 스레드가 바쁜 스레드의 큐 꼬리에서 태스크를 훔쳐오는 방식으로 부하를 분산함
• EBR (Epoch-Based Reclamation): Lock-Free 프로그래밍에서의 ABA 문제를 해결하고, 큐 확장이나 노드 삭제 시 Use-After-Free를 방지하는 메모리 안전 회수 메커니즘
• AsyncMutex: Baton Passing 기술 기반으로, 깨울 때 락 소유권을 직접 전달해 thundering herd 문제를 회피함
• Channel: CSP(Communicating Sequential Processes) 모델 구현, 버퍼 모드와 언버퍼 모드 모두 지원

EBR이 왜 필요한가

Lock-Free 큐(StealQueue)에서 한 스레드가 노드 A를 읽고 있을 때, 다른 스레드가 A를 삭제하고 메모리를 해제할 수 있음. 시스템이 이 메모리를 즉시 재사용하면 읽는 쪽 스레드가 크래시하거나 더티 데이터를 읽게 됨. tiny_coro의 EBR 방식은 다음과 같음:

• 각 스레드가 로컬 Epoch을 유지함
• 모든 활성 스레드가 따라잡은 후에만 글로벌 Epoch이 전진함
• 글로벌 Epoch이 2세대(G-2) 이상 앞서간 경우에만 메모리를 실제로 삭제함

Lock-Free 큐의 최적화 디테일

• alignas(64): top과 bottom 포인터가 같은 캐시 라인에 놓이는 것을 방지해 False Sharing을 차단함
• seq_cst 배리어: pop 연산에서 Dekker 알고리즘 원리를 따라, 큐에 원소가 하나만 남았을 때의 데이터 레이스를 방지함
• await_suspend가 bool을 반환하는 기능을 활용해 Fast Path 최적화 구현. 락 획득이나 버퍼 읽기/쓰기 성공 시 코루틴이 서스펜드 없이 바로 계속 실행되므로, 기존의 "서스펜드 -> 큐 삽입 -> 스케줄러 웨이크업" 경로 대비 훨씬 빠름

아키텍처 흐름

전체 구조는 다음과 같이 동작함:

• Scheduler -> Worker 스레드 풀 시작 + 글로벌 큐 관리
• Worker: 각각 시스템 스레드에 바인딩되어 run_once() 루프 실행. 우선순위는 로컬 큐 -> 글로벌 큐 -> 다른 Worker에서 훔치기 -> Sleep(Park)
• EBR Manager: 글로벌 Epoch을 모니터링해 Lock-Free 큐 확장 시 모든 스레드가 크리티컬 섹션을 빠져나간 후에만 메모리를 해제함
• Parker: Atomic Wait(Futex) 기반으로 Lost Wakeup 문제를 해결하는 효율적 슬립 메커니즘

네트워크 I/O

• Reactor 패턴: epoll(Linux) / kqueue(macOS) 캡슐화
• Zero-Copy HTTP 파서: std::string_view로 수신 버퍼에서 직접 동작해 메모리 할당을 회피함
• 스트림 처리: 코루틴 기반 파일 업로드/다운로드를 8KB 상수 메모리로 처리함

성능 결과

MacBook M1 Air 로컬 루프백 wrk 테스트 기준:

• tiny_coro 기반 간단한 HTTP 서버: 186,045 QPS
• 동일 로직의 Go 구현: 193,587 QPS
• ASAN, TSAN 테스트 모두 통과함

Go가 Google의 깊은 최적화와 OS 통합의 이점을 가진 점을 감안하면, 교육용 프로젝트로서 매우 인상적인 수치임.

학습 가이드

이 프로젝트는 프로덕션용이 아니라 순수 교육 목적임. 버그가 존재하지만 코드의 최소한의 가독성을 유지하기 위해 의도적으로 수정하지 않은 상태임. 대신 자체 개발한 coroTracer 도구로 버그의 근본 원인을 분석한 기록이 포함되어 있음.

• 입문자: how_to_make_your_MN_scheduler.md 문서를 따라 순서대로 학습할 수 있음. 기본 C++ 문법만 알면 충분함
• 코루틴에 익숙한 개발자: docs 폴더에서 모듈별로 독립적으로 참고 가능함
• 전체 코드가 약 1,000줄 수준이라 통독하기에도 부담이 적음

참고 및 영감

• Tokio(Rust): Work-Stealing과 Reactor 설계의 영감 소스
• Go Runtime: M:N 모델과 Channel 설계 참고
• picohttpparser: HTTP 파싱용 (코루틴 스케줄러 자체는 외부 의존성 없음)

C++20 코루틴의 내부 동작 원리를 "직접 만들어보면서" 이해하고 싶은 개발자에게 매우 좋은 학습 자료가 될 것으로 보임.