본문으로 건너뛰기
Folly Code Review · 47/89

folly::UnboundedQueue — 동적 크기 lock-free

· Hawk · 6분 읽기
cpp folly queue unbounded lock-free

#한 줄 요약

folly::UnboundedQueue<T, ...>는 고정 크기가 없는 lock-free MPMC 큐다. 내부적으로 고정 크기 segment를 linked list로 연결하고, 한 segment가 가득 차면 새 segment를 alloc해서 이어붙인다. 동시성 모드(SPSC/MPSC/SPMC/MPMC)를 템플릿 인자로 선택할 수 있다.

#동기 — bounded의 한계

MPMCQueue는 빠르지만 capacity를 미리 정해야 한다. capacity가 작으면 backpressure, 크면 메모리 낭비. workload가 burst-y하면 어느 값을 잡아도 어색하다.

UnboundedQueue는 “평소엔 작게, 필요할 때만 크게”의 정신이다.

  • 평소엔 segment 한두 개로 운영.
  • burst가 오면 segment가 자동 추가되어 producer가 막히지 않음.
  • consumer가 따라잡으면 빈 segment는 자동 회수.

대가는 segment 경계에서 한 번의 atomic CAS와, 동적 할당 비용이다. 그러나 segment 크기가 충분하면 amortized 비용이 매우 낮다.

#unbounded variant도 같은 모델

unbounded라고 해서 모델이 바뀌는 건 아니다. capacity 제약을 느슨하게 했을 뿐 producer/consumer 구도는 동일하다.

Producer / consumer queue

차이는 backpressure 정책뿐 — bounded는 가득 차면 producer가 block, unbounded는 segment를 늘려 producer를 절대 막지 않는다. 단, 시스템 전체에서는 producer가 무한정 빨라지면 memory pressure로 다른 곳이 막힌다. backpressure를 미는 게 아니라 옮긴 것이다.

#API

#include <folly/concurrency/UnboundedQueue.h>


// 템플릿 파라미터: T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize
folly::UMPMCQueue<Task, true /*MayBlock*/> q;       // MPMC + blocking 지원
folly::USPSCQueue<Task, false> q_spsc;              // SPSC, non-blocking


// Producer
q.enqueue(task);


// Consumer
auto t = q.dequeue();         // blocking
auto t = q.try_dequeue();     // non-blocking, returns Optional
auto t = q.try_dequeue_for(std::chrono::milliseconds(100));

별칭이 많다.

aliasmode
USPSCQueuesingle producer, single consumer
UMPSCQueuemulti producer, single consumer
USPMCQueuesingle producer, multi consumer
UMPMCQueuemulti producer, multi consumer

mode가 더 제한적일수록 내부 path가 더 단순해진다. SPSC mode는 CAS 거의 없이 동작한다.

#내부 구현 — segment chain

struct Segment {
  std::array<Slot, kSegmentSize> slots;
  std::atomic<Segment*> next;
  uint64_t baseTicket;
};


alignas(cacheline) std::atomic<Segment*> head_;  // consumer 측
alignas(cacheline) std::atomic<Segment*> tail_;  // producer 측
alignas(cacheline) std::atomic<uint64_t> producerTicket_;
alignas(cacheline) std::atomic<uint64_t> consumerTicket_;

큐 전체는 MPMCQueue처럼 ticket으로 슬롯을 받는다. ticket의 상위 bit가 segment index, 하위 bit가 segment 내부 슬롯.

#enqueue

void enqueue(T&& v) {
  auto ticket = producerTicket_.fetch_add(1);
  auto segIdx = ticket / kSegmentSize;
  auto slotIdx = ticket % kSegmentSize;


  Segment* seg = findOrAllocSegment(segIdx); // tail_을 따라가며 필요시 alloc
  seg->slots[slotIdx].store(std::move(v));
}

findOrAllocSegment가 핵심이다. tail_이 가리키는 segment를 따라가서, 필요하면 새 segment를 alloc해 next에 CAS로 연결한다. CAS 한 번이 segment 경계에서만 발생하므로 segment_size가 1024라면 1024 enqueue당 한 번꼴.

#dequeue

T dequeue() {
  auto ticket = consumerTicket_.fetch_add(1);
  auto segIdx = ticket / kSegmentSize;
  auto slotIdx = ticket % kSegmentSize;


  Segment* seg = waitForSegment(segIdx); // head_부터 따라감
  return seg->slots[slotIdx].load();
}

consumer는 head_부터 segment chain을 따라가며 자기 segment를 찾는다. 이전 segment가 완전히 비면 GC 후보가 된다.

#Hazard pointer로 GC

segment 회수는 까다롭다. 어떤 consumer가 아직 segment를 참조 중일 수 있기 때문에 free하면 use-after-free. Folly는 folly::hazptr로 이를 처리한다. consumer가 segment를 참조하는 동안 hazard pointer에 등록하고, 모든 hazard에서 빠진 segment만 GC.

#std / abseil 비교

큐동시성 모드bounded비고
std::queue + mutexMPMCunboundedmutex 단일 hotspot
folly::MPMCQueueMPMC만bounded가장 빠름, capacity 고정
folly::UnboundedQueue4가지unboundedsegment chain
concurrentqueue (moodycamel)MPMCunbounded비슷한 설계, 외부 lib

Meta 내부에선 burst workload(예: log ingestion)는 UnboundedQueue, 안정 load(예: RPC dispatch)는 MPMCQueue로 나눠 쓴다.

#코드 리뷰 포인트

#1. 적절한 동시성 mode 선택

// 회피 — MPMC가 default라 안전해 보이지만 SPSC보다 5-10배 느림
folly::UMPMCQueue<int> q;


// Good — 알고 있다면 정확히 명시
folly::USPSCQueue<int> q;

mode가 더 제한적일수록 내부 atomic 연산이 줄어든다. “혹시나”라며 MPMC를 고르면 그만큼 비용을 낸다.

#2. segment size 선택

LgSegmentSize 템플릿 파라미터(log2)가 segment 크기를 결정한다. default는 보통 8(=256슬롯)이나 9(=512).

  • segment가 작으면: 새 segment alloc/free가 잦아진다 → CAS 비용 증가.
  • segment가 크면: 메모리 fragmentation 줄어들지만, 마지막 segment가 partial 사용일 때 낭비.

burst 크기와 메모리 budget에 맞춰 조정.

#3. MayBlock 의미

folly::UMPMCQueue<T, true /*MayBlock*/> q;

MayBlock=true면 dequeue가 비어 있을 때 Baton으로 park한다. false면 try만 가능. blocking semantics이 필요 없으면 false가 더 가벼움.

#4. 메모리 사용량 추정

// 가득 찼을 때 메모리
peak_memory = peak_segment_count * (segment_size * sizeof(T) + overhead)

burst가 끝나도 segment는 GC가 들어와야 회수된다. metric으로 peak segment 수를 모니터링.

#안티패턴

#1. SPSC가 명확한데 UMPMCQueue를 default로

// 회피
folly::UMPMCQueue<Frame> frameQ; // network thread → render thread

mode를 정확히 지정하면 thread 수만큼 throughput이 늘어난다.

#2. unbounded라고 backpressure 없이 마구 enqueue

// 회피
for (;;) {
  q.enqueue(make_log()); // consumer가 못 따라가면 메모리 폭주
}

unbounded는 OOM의 ticking bomb이다. queue size를 metric으로 보내고, threshold 넘으면 drop 또는 source throttle.

#3. T가 큰 객체

// 회피
folly::UMPMCQueue<LargeStruct> q; // 매 dequeue가 큰 복사

segment에 직접 저장되므로 큰 T는 segment alloc 비용을 키운다. unique_ptr<LargeStruct>로 감싸 포인터만 큐에 둔다.

#정리

  • UnboundedQueue는 segment chain 기반 lock-free 동적 큐다.
  • 동시성 mode(SPSC/MPSC/SPMC/MPMC)를 템플릿 인자로 선택해 내부 path를 최적화.
  • segment 경계에서만 CAS가 발생하므로 amortized 비용 낮음.
  • hazard pointer로 segment GC 처리.
  • burst 워크로드에 적합. 안정 load는 MPMCQueue가 더 빠르다.
  • unbounded는 backpressure 정책이 외부에 있어야 한다.

#다음 편

Part 10-04 fibers::Channel — fiber 간 채널. Go의 channel과 비교하며 본다.

#관련 항목

Folly Code Review · 48 of 89

  1. 1 Folly Code Review — Meta의 production-grade C++ 라이브러리 코드 분석
  2. 2 Folly 개요 — Meta가 production에서 검증한 utility 모음 분석
  3. 3 Folly vs Abseil 철학 비교 — performance-first vs std-compatible
  4. 4 Folly 빌드와 fbcode 환경 — monorepo의 그림자
  5. 5 Folly API stability 정책 — 어떤 보장도 없다는 솔직함
  6. 6 Folly production validation 문화 — peta-scale에서 단련된 코드
  7. 7 folly::Future 분석 — std::future의 한계를 넘는 composable async
  8. 8 folly::Promise·makeFuture — Future를 만드는 두 길
  9. 9 folly::SemiFuture vs Future — executor binding의 명시화
  10. 10 folly::Future thenValue·thenError·thenTry — continuation 체인 분석
  11. 11 folly::collect·collectAll·collectAny — fan-in 패턴 분석
  12. 12 folly::Future retry·window·via — 제어 흐름 조합자
  13. 13 folly::fibers 분석 — M:N stackful coroutine
  14. 14 folly::InlineExecutor — 호출자 thread에서 즉시 실행
  15. 15 folly::CPUThreadPoolExecutor — CPU-bound 작업의 표준 thread pool
  16. 16 folly::IOThreadPoolExecutor — libevent 기반 I/O pool
  17. 17 folly::ManualExecutor — 결정적 테스트를 위한 수동 진행
  18. 18 folly::EventBase 분석 — libevent 이벤트 루프의 핵심
  19. 19 folly::IOBuf 분석 — zero-copy buffer chain의 기본 단위
  20. 20 folly::IOBufQueue — chain의 push/pull 추상화
  21. 21 folly::io::Cursor·RWCursor — chain 위의 stream
  22. 22 folly Zero-copy 패턴 — IOBuf로 ScatterGather I/O 표현
  23. 23 folly::IOBuf shared semantics — clone·unshare·takeOwnership
  24. 24 folly::FBString 분석 — SSO + COW 구현
  25. 25 folly의 fmt::format 통합 — 모던 포맷팅 채택
  26. 26 folly::StringPiece — string_view 호환 분석
  27. 27 folly Join·Split utilities — 문자열 분해와 결합
  28. 28 folly::to·tryTo — text↔num 변환 분석
  29. 29 folly Conv Customization — 사용자 타입 지원
  30. 30 folly Conv 성능 비교 — sprintf·stringstream 대비
  31. 31 folly::F14ValueMap vs std::unordered_map
  32. 32 folly::F14NodeMap — stable pointer가 필요할 때
  33. 33 folly::F14VectorMap — cache-friendly iteration
  34. 34 folly::F14FastMap — auto-select 동작
  35. 35 folly F14 internals — SIMD probing 메커니즘
  36. 36 folly::small_vector — inline storage 분석
  37. 37 folly::FixedString — compile-time string
  38. 38 folly::AtomicHashMap — lock-free read 분석
  39. 39 folly::ConcurrentHashMap — sharded 동시 해시 맵
  40. 40 folly::EvictingCacheMap — LRU 구현 분석
  41. 41 folly::Synchronized — lock wrapper 패턴
  42. 42 folly::SharedMutex 분석
  43. 43 folly::Baton — one-shot wait 동기화
  44. 44 folly::RWSpinLock 분석
  45. 45 folly::PicoSpinLock — 1-byte spinlock
  46. 46 folly::ProducerConsumerQueue — SPSC 큐 분석
  47. 47 folly::MPMCQueue — multi-producer multi-consumer
  48. 48 folly::UnboundedQueue — 동적 크기 lock-free
  49. 49 folly::fibers::Channel — Go-like channel
  50. 50 folly::dynamic — JSON-like dynamic type 분석
  51. 51 folly JSON conversion — toJson·parseJson
  52. 52 folly dynamic ↔ struct — manual marshaling
  53. 53 folly dynamic Visitor pattern — type별 분기
  54. 54 folly::Singleton vs Meyers/static — 왜 Folly의 Singleton인가
  55. 55 folly::SingletonVault 분석 — 등록·소멸·의존성
  56. 56 folly::Singleton try_get·try_get_fast — TLS-cached 접근
  57. 57 folly::ExceptionWrapper — type-erased exception holder
  58. 58 folly::ScopeGuard·SCOPE_EXIT — RAII cleanup
  59. 59 folly::Optional vs std::optional
  60. 60 folly::Function vs std::function
  61. 61 folly::Lazy — 지연 초기화 wrapper
  62. 62 folly Meta 스타일 code review 패턴
  63. 63 folly anti-patterns — 잘못 쓰면 std보다 느림
  64. 64 folly vs std 선택 기준 분석
  65. 65 folly::coro 개요 — production C++20 코루틴 어댑터
  66. 66 folly::coro::Task — lazy single-shot 코루틴
  67. 67 folly::coro::AsyncGenerator — 비동기 스트림
  68. 68 folly coro blockingWait·collectAll — 동기 경계와 fan-in
  69. 69 folly::coro::Baton·Mutex — 코루틴-aware 동기화
  70. 70 folly::Expected — 결과 또는 오류
  71. 71 folly::Try — Future 결과 wrapper
  72. 72 folly::Try vs Expected 선택 기준
  73. 73 folly::Range — 일반 iterator pair
  74. 74 folly::Uri — URL 파서
  75. 75 folly Fingerprint64·128 — 분산 hash
  76. 76 folly SpookyHashV2 — fast non-crypto hash
  77. 77 folly::Init — main() 부트스트랩
  78. 78 folly::Indestructible — global lifetime 패턴
  79. 79 folly::MicroLock — 1-byte 락
  80. 80 folly::MicroSpinLock — 가장 좁은 spin lock
  81. 81 folly::format — legacy formatter 분석
  82. 82 folly::demangle — typeid 디망글링
  83. 83 folly::DynamicConverter — dynamic ↔ struct
  84. 84 folly::RecordIO — append-only 로그 파일 포맷
  85. 85 folly::io::Compression — zstd·lz4·snappy wrapper
  86. 86 folly::AsyncIO — io_uring·Linux AIO
  87. 87 folly::CancellationToken — 코루틴·Future 취소 전파
  88. 88 folly::observer — hot config의 atomic refresh
  89. 89 fbcode 패턴 모음 — folly 사용의 실전

관련 글

folly::MPMCQueue — multi-producer multi-consumer

Part 10-02: MPMCQueue — ticket 기반 lock-free 큐. CAS 없이 여러 producer/consumer를 안전하게 처리한다.

· cpp

같은 시리즈에서 이어 읽기

folly::ProducerConsumerQueue — SPSC 큐 분석

Part 10-01: ProducerConsumerQueue — SPSC lock-free ring buffer. cache line padding, acquire/release만으로 RTT을 줄이는 패턴.

· cpp

같은 시리즈에서 이어 읽기

folly::AtomicHashMap — lock-free read 분석

AtomicHashMap — lock-free read, append-only insert, 큰 read-heavy 워크로드용 hash map.

· cpp

같은 시리즈에서 이어 읽기

이 글을 참조하는 글 (1)