[C 기술면접] Queue 설계 — 크기 산정과 가득 찼을 때 처리
NOTE
질문 5: Queue를 만든다면 크기를 어떻게 정하고, 최대(가득 참)에 도달하면 어떻게 처리할 것인가? 핵심은 두 가지다. ① 크기는 “도착 속도 − 처리 속도”가 만드는 순간적 쌓임(burst)을 흡수할 만큼, 그리고 허용 지연·메모리 한도 안에서 정한다(무한정 키우지 않는다). ② 가득 찼을 때의 정책(블로킹 / 거절 / 폐기 / 덮어쓰기)을 업무 특성에 맞게 미리 정하고, 지표·알람으로 관측한다.
1. Queue는 왜 쓰는가
- 생산자와 소비자의 속도 차이를 흡수(버퍼링) 하고, 서로를 분리(decoupling) 한다.
- 순간적 폭주(burst)를 평탄화한다. 단, 지속적으로 도착 속도 > 처리 속도면 어떤 크기의 큐도 결국 가득 찬다. 큐는 문제를 해결하는 게 아니라 시간을 번다.
2. 큐 크기를 어떻게 정하는가
기준 1) 도착/처리 속도와 burst
필요한 최소 크기 ≈ (피크 도착 속도 − 소비 속도) × 지속 시간(burst 길이 또는 소비자 정지 시간)
- 예: 피크 5,000건/초, 소비 3,000건/초, 피크가 2초 지속 → (5000−3000)×2 = 4,000건 이상 필요.
- 소비자가 GC/DB 지연/네트워크 재접속으로 잠시 멈추는 시간(stall)도 포함한다. 평균이 아니라 피크와 최악 지연으로 계산한다.
기준 2) 허용 지연(Latency)
큐에서의 최대 대기 시간 ≈ 큐 크기 / 소비 속도 (Little의 법칙: L = λ × W)
- 큐가 크면 오래된 요청이 오래 기다린다. 타임아웃이 1초인데 큐 대기만 5초면 처리해도 이미 쓸모없는 일(클라이언트는 포기)이다.
- 따라서 큐 크기 ≤ 소비 속도 × 허용 대기 시간. 지연 민감 서비스는 큐를 작게 두고 빨리 실패시키는 편이 낫다(“큐를 크게 잡는다고 안전해지지 않는다”: bufferbloat).
기준 3) 메모리 한도
총 메모리 = 큐 크기 × 요소 크기 (+ 요소가 가리키는 힙 메모리)
- 요소가 포인터면 가리키는 객체까지 계산한다. 큐 수(스레드 수만큼 있을 수 있음)를 곱한다.
- 메모리 상한을 넘지 않도록 상한을 설정값으로 둔다.
기준 4) 구현 편의와 성능
- 링 버퍼는 크기를 2의 거듭제곱으로 두면
idx & (size-1)로 모듈로 연산을 비트 연산으로 대체할 수 있다. - 캐시 라인(64B) 단위 정렬, 생산자/소비자 인덱스를 다른 캐시 라인에 분리(false sharing 방지).
기준 5) 측정으로 보정
- 운영 지표(큐 길이 최대치, 평균, 가득 참 횟수, 폐기 건수, 대기 시간 분포)를 보고 조정한다.
- 크기를 설정 파일 값으로 빼고, 기본/최소/최대 범위를 검증한다. 재컴파일 없이 튜닝할 수 있게 한다.
한 줄 결론
“평균이 아니라 피크와 정지 시간으로 계산하고, 허용 지연과 메모리 상한으로 위아래를 제한하며, 측정해서 조정한다. 무한 큐는 지양한다.”
3. 가득 찼을 때(Full / Max) 처리 정책
| 정책 | 동작 | 장점 | 단점 / 적합한 상황 |
|---|---|---|---|
| 블로킹 (백프레셔) | 생산자를 not_full 조건변수로 대기시킴 (타임아웃 옵션) | 데이터 유실 없음, 생산자가 자연스럽게 느려짐 | 생산자 스레드가 막힘 → 연쇄 정체/데드락 위험. 내부 파이프라인, 유실 불가 데이터 |
| 즉시 실패(거절) | 실패 코드 반환(-1/EAGAIN), 호출자가 재시도·거절 응답 | 지연 예측 가능, 과부하 신호를 상류에 전달 | 호출자가 처리 필요. 외부 요청(예: HTTP 503 + Retry-After) |
| 최신 폐기 (Drop newest / tail drop) | 새로 온 것을 버림 | 구현 단순, 기존 요청 보호 | 최신 데이터가 더 중요하면 부적합 |
| 오래된 것 폐기 / 덮어쓰기 (Drop oldest / overwrite) | 가장 오래된 항목을 밀어내고 새 항목 저장 | 항상 최신 상태 유지 | 오래된 데이터 유실. 센서/모니터링/최신값만 의미 있는 경우 |
| 우선순위 기반 폐기 | 중요도 낮은 것부터 폐기, 중요 메시지는 예약 공간 | 핵심 트래픽 보호 | 구현 복잡. 제어 메시지 vs 일반 데이터 구분 |
| 동적 확장 (grow) | 크기를 늘림(realloc) | 순간 폭주 흡수 | 상한 필수. 상한 없으면 OOM. 확장 중 복사 비용·지연 |
| 디스크/외부 큐로 스필(spill) | 넘치면 파일·MQ에 보관 | 유실 방지 | 복잡도·지연·운영 부담 |
| 샤딩/큐 분리 | 키별·우선순위별로 큐를 나눔 | 한 종류의 폭주가 전체를 막지 않음 | 순서 보장 범위가 샤드 단위로 한정 |
정책 선택 기준
데이터 유실이 절대 안 됨(결제, 주문) → 블로킹 또는 거절 + 상류 재시도 / 영속 큐 스필
지연이 중요하고 과부하 시 빨리 실패해야 함 → 즉시 거절(503) + 알람
최신 값만 의미 있음(센서, 상태 모니터링) → 오래된 것 덮어쓰기
제어/하트비트가 데이터 폭주에 묻히면 안 됨 → 우선순위 큐 또는 별도 큐
- 과부하 보호(Load Shedding): 큐가 임계치(예: 80%)를 넘으면 일찍 신규 요청을 거절한다. 100%에 닿은 뒤에 거절하면 이미 지연이 크다.
- 히스테리시스: 알람/거절 해제 임계치를 진입 임계치보다 낮게(예: 80%에서 시작, 50%에서 해제) 두어 경계에서 깜빡이는 것을 막는다.
반드시 같이 설계할 것
- 관측성: 현재 길이, 최대 길이(high watermark), 폐기/거절 건수, 대기 시간을 지표·로그로 남긴다. “가득 참”은 로그 한 줄이 아니라 알람 대상이다.
- 종료(shutdown) 처리: 종료 시 남은 항목을 비울지(drain) 버릴지, 대기 중인 생산자/소비자를 깨워서 빠져나오게 한다(
broadcast). - 소유권: 큐에 넣은 포인터를 누가 해제하는지. 폐기할 때 해제하지 않으면 누수.
- 타임아웃: 블로킹 정책에서는 무기한 대기 대신
pthread_cond_timedwait로 시간 제한.
4. 구현 예시 — 고정 크기 링 버퍼 + 뮤텍스/조건변수
가득 참/비어 있음 구분
링 버퍼에서 head == tail만으로는 가득 참과 비어 있음을 구분할 수 없다. 해결책:
count필드를 따로 둔다(가장 단순) — 아래 예시- 한 칸을 비워 둔다(
(tail+1)%N == head면 가득 참) - 인덱스를
2N범위로 증가시켜 차이로 판단(SPSC 락프리에 흔함)
typedef struct {
void **buf;
size_t cap, head, tail, count;
int closed;
unsigned long dropped; /* 폐기 건수 지표 */
pthread_mutex_t lock;
pthread_cond_t not_full, not_empty;
} queue_t;
/* 블로킹 push (타임아웃 지원). 성공 0, 가득참(타임아웃) -1, 종료됨 -2 */
int queue_push(queue_t *q, void *item, const struct timespec *abs_deadline)
{
pthread_mutex_lock(&q->lock);
while (q->count == q->cap && !q->closed) {
if (abs_deadline == NULL) {
pthread_cond_wait(&q->not_full, &q->lock);
} else if (pthread_cond_timedwait(&q->not_full, &q->lock, abs_deadline) == ETIMEDOUT) {
q->dropped++; /* 정책: 시간 내 못 넣으면 거절 */
pthread_mutex_unlock(&q->lock);
return -1;
}
}
if (q->closed) { pthread_mutex_unlock(&q->lock); return -2; }
q->buf[q->tail] = item;
q->tail = (q->tail + 1) % q->cap;
q->count++;
pthread_cond_signal(&q->not_empty);
pthread_mutex_unlock(&q->lock);
return 0;
}
/* 논블로킹 push: 가득 차면 즉시 실패 (거절 정책) */
int queue_try_push(queue_t *q, void *item)
{
pthread_mutex_lock(&q->lock);
if (q->count == q->cap) { q->dropped++; pthread_mutex_unlock(&q->lock); return -1; }
q->buf[q->tail] = item; q->tail = (q->tail + 1) % q->cap; q->count++;
pthread_cond_signal(&q->not_empty);
pthread_mutex_unlock(&q->lock);
return 0;
}
/* 덮어쓰기 정책: 가득 차면 가장 오래된 항목을 버리고 저장 (버리는 항목의 해제는 호출자 정책에 맞게) */
void queue_push_overwrite(queue_t *q, void *item, void **evicted)
{
pthread_mutex_lock(&q->lock);
*evicted = NULL;
if (q->count == q->cap) {
*evicted = q->buf[q->head];
q->head = (q->head + 1) % q->cap;
q->count--; q->dropped++;
}
q->buf[q->tail] = item; q->tail = (q->tail + 1) % q->cap; q->count++;
pthread_cond_signal(&q->not_empty);
pthread_mutex_unlock(&q->lock);
}- 조건 대기는 항상
while로 재검사한다(spurious wakeup). pop은 대칭: 비면not_empty에서 대기, 꺼낸 뒤not_full에signal.- 종료 시
closed = 1후pthread_cond_broadcast로 양쪽 대기자를 모두 깨운다.
락 경합이 문제라면
| 방법 | 설명 |
|---|---|
| SPSC 락프리 링 버퍼 | 생산자 1, 소비자 1이면 head/tail을 각자만 쓰므로 atomic(acquire/release)만으로 구현 가능 |
| 스레드별 전용 큐 + 해시 샤딩 | 키 해시로 워커를 고정해 락 자체를 제거. 같은 키의 순서도 보장 |
| MPMC 락프리 큐 | 구현·검증이 어려워 검증된 라이브러리를 쓰는 편이 안전 |
→ 참고: 배열 기반 원형 큐(Ring Buffer), 스레드별 전용 큐와 해시 샤딩, 락 없는 카운터
5. 꼬리 질문
| 질문 | 답변 요지 |
|---|---|
| 큐를 무한으로 만들면 안 되나? | 소비자가 느려지면 메모리가 계속 늘어 OOM, 대기 시간이 무한히 늘어 의미 없는 처리가 된다. 반드시 상한을 두고 가득 참 정책을 정의한다. |
| 큐가 항상 가득 차 있다면? | 용량 문제가 아니라 처리량 문제다. 소비자 수/속도 증가, 병목(DB, 락) 제거, 상류 속도 제한, 수평 확장이 필요하다. 큐를 키우면 지연만 늘어난다. |
| 백프레셔(Backpressure)란? | 소비자의 처리 한계를 생산자에게 전달해 생산 속도를 늦추는 것. 블로킹, 거절 응답, 크레딧 기반 흐름 제어(예: TCP 윈도우, HTTP/2 flow control). |
| 링 버퍼를 쓰는 이유? | 고정 메모리, 할당/해제 없이 O(1) push/pop, 캐시 친화적. 연결 리스트 큐는 노드마다 할당 비용과 단편화가 있다. |
| 큐 크기를 2의 거듭제곱으로 하는 이유? | % cap 대신 & (cap-1)로 계산해 나눗셈을 피하고, 인덱스 오버플로우 시에도 wrap이 자연스럽다. |
| 우선순위가 다른 메시지는? | 큐를 분리하거나 우선순위 큐(힙)를 쓰되, 낮은 우선순위의 기아(starvation)를 막는 에이징을 고려한다. |
| 메시지 유실이 절대 안 되면? | 인메모리 큐만으로는 장애 시 유실된다. 영속 큐(디스크 로그, Kafka/RabbitMQ), ACK/재전송, 멱등 처리와 함께 설계한다. |
| 소비자 스레드는 몇 개가 적당한가? | CPU 바운드면 코어 수 근처, I/O 바운드면 대기 비율을 고려해 늘린다. 부하 테스트로 결정하며 설정값으로 뺀다. |
| 가득 찼을 때 로그를 매번 찍으면? | 폭주 상황에서 로그 자체가 부하를 키운다. 레이트 리밋(초당 1회 등)과 카운터 집계로 대체한다. |
한 줄 요약
- 크기:
(피크 도착 − 소비) × 지속시간으로 시작, 허용 지연(크기 ≤ 소비속도 × 허용대기) 과 메모리 상한으로 제한, 지표로 보정. - 가득 참: 블로킹/거절/폐기/덮어쓰기 중 업무 특성(유실 허용 여부, 최신성, 지연 민감도)으로 선택하고, 임계치에서 미리 부하를 줄이며(Load Shedding) 관측·알람을 남긴다.