큐: FIFO 순서에서 bounded backpressure까지 설계하는 Java 구현

큐는 먼저 도착한 원소를 먼저 꺼내는 FIFO ADT다. 그러나 운영 시스템에서 더 중요한 질문은 “가득 찼을 때 무엇을 할 것인가”다. 무한히 자라는 queue는 overload를 해결하지 않고 heap에 숨긴다.

1. 문제 계약: bounded job queue

예제는 capacity가 고정된 in-memory job queue다. offer는 빈자리가 있으면 tail에 넣고 true, 가득 차면 block하지 않고 false를 반환한다. poll은 head를 제거해 반환하고 비면 null이다. null job은 허용하지 않는다.

이 계약은 producer가 rejection을 보고 retry, drop, upstream throttling 중 하나를 선택하게 한다. add/remove처럼 예외를 쓰는 Queue method와 offer/poll처럼 특수값을 쓰는 method를 의도 없이 섞지 않는다.

2. head/tail 표현 불변식

capacity 2에서 job 1, 2, 3을 넣고 두 번 꺼낸다.

연산	반환	head → tail	설명
`offer(1)`	true	`[1]`	첫 원소가 head/tail
`offer(2)`	true	`[1,2]`	2는 tail
`offer(3)`	false	`[1,2]`	capacity 보존
`poll()`	1	`[2]`	가장 오래된 원소 제거
`poll()`	2	`[]`	FIFO 보존
`poll()`	null	`[]`	empty 계약

표현 불변식: 0 <= size <= capacity이며 iteration 순서는 성공한 offer 중 아직 poll되지 않은 원소의 도착 순서다. 가득 찬 offer를 거절하면 상태가 바뀌지 않는다. poll은 첫 원소만 제거하므로 남은 상대 순서가 보존된다.

처리율 예시로 capacity의 의미를 계산한다

비어 있는 queue에 producer가 초당 120개를 넣고 consumer가 초당 100개를 처리한다고 하자. 평균적으로 backlog는 초당 20개씩 늘어난다. capacity가 1,000이면 약 50초 뒤 가득 찬다. capacity를 10,000으로 키우면 장애가 해결되는 것이 아니라 거절 시점을 약 500초 뒤로 미루고, 오래된 작업의 대기 시간을 키운다.

경과 시간	누적 유입	누적 처리	예상 backlog
10초	1,200	1,000	200
30초	3,600	3,000	600
50초	6,000	5,000	1,000

따라서 bounded queue의 false 반환은 단순 실패값이 아니라 overload 신호다. 호출자는 즉시 drop할지, 제한된 횟수만 retry할지, upstream에 429/503을 돌려보낼지 정해야 한다. retry가 다시 arrival rate를 높이면 queue 앞에서 재시도 폭풍이 생기므로 지수 backoff만 넣고 끝내지 말고 rejection rate와 oldest age를 함께 경보로 묶는다.

실행 재현

아래 코드는 설명용 조각이 아니라 main에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다.

import java.util.ArrayDeque;
import java.util.Deque;

public final class QueueDemo {
    record Job(long id, String payload) {}

    static final class BoundedQueue {
        private final int capacity;
        private final Deque<Job> jobs = new ArrayDeque<>();

        BoundedQueue(int capacity) {
            if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
            this.capacity = capacity;
        }

        boolean offer(Job job) {
            if (job == null) throw new IllegalArgumentException("job must not be null");
            if (jobs.size() == capacity) return false;
            jobs.addLast(job);
            return true;
        }

        Job poll() { return jobs.pollFirst(); }
        int size() { return jobs.size(); }
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        BoundedQueue queue = new BoundedQueue(2);
        check(queue.offer(new Job(1, "A")), "first offer");
        check(queue.offer(new Job(2, "B")), "second offer");
        check(!queue.offer(new Job(3, "C")), "backpressure");
        check(queue.poll().id() == 1, "FIFO first");
        check(queue.poll().id() == 2, "FIFO second");
        check(queue.poll() == null, "empty poll");
        System.out.println("order=1,2; overflow rejected; empty=null");
    }
}

javac --release 21 QueueDemo.java
java QueueDemo

직접 실행한 출력은 다음과 같다.

order=1,2; overflow rejected; empty=null

컴파일러와 런타임은 javac 21.0.11, OpenJDK 21.0.11을 사용했다. assert 옵션에 의존하지 않고 실패 시 AssertionError를 던지므로 위 명령 그대로 검증된다.

3. 왜 배열 deque를 사용하는가

ArrayDeque는 양 끝 삽입·삭제를 대부분 amortized constant time에 제공한다. head에서 제거할 때 나머지를 모두 당기는 ArrayList.remove(0)와 달리 logical head를 이동할 수 있다. LinkedList도 Queue지만 원소별 node와 두 reference를 사용해 allocation/locality 특성이 다르다.

예제 wrapper는 jobs.size()==capacity를 확인한 뒤 addLast한다. 단일 thread 학습용 구현이며 thread-safe하지 않다. 여러 producer/consumer가 접근하면 check와 insert 사이에 race가 생기므로 ArrayBlockingQueue 같은 concurrent bounded queue의 atomic offer/put 계약을 써야 한다.

4. 시간·공간과 resize를 구분한다

wrapper의 offer/poll은 ArrayDeque 양 끝 연산을 사용하므로 amortized $O(1)$ 이다. 저장 원소가 $k$ 개면 보조 저장은 $O(k)$ 이고 bounded 조건에서 $k<=capacity$ 다. JVM에서 Queue object와 backing array, Job record instances는 heap에 있다. local references는 frame에 있지만 job payload가 frame으로 복사되지는 않는다.

generic collection은 reference를 보관한다. primitive job ID만 필요해도 Queue<Long>이면 boxing이 생길 수 있다. 정확한 object byte나 resize 시점은 Java API 보장이 아니므로 OpenJDK source/JOL로 사용하는 runtime을 확인한다.

5. Little's Law로 backlog를 운영 질문으로 바꾼다

안정 상태에서 평균 queue 길이 $L$ , 처리율 $\lambda$ , 평균 대기 시간 $W$ 는 다음 관계를 가진다.

L=\lambda W

알고리즘 복잡도만으로 대기 시간은 결정되지 않는다. arrival rate가 service rate를 넘으면 backlog가 지속적으로 증가한다. capacity는 메모리 한도이자 허용 대기 시간 정책이다. production에서는 queue depth뿐 아니라 oldest message age, enqueue rejection, processing rate, retry rate를 함께 본다.

6. Stack·PriorityQueue·blocking queue와 비교

선택	순서	overload 계약	사용 예
ArrayDeque Queue	FIFO	wrapper가 결정	단일 thread BFS
ArrayBlockingQueue	FIFO	block/timeout/reject	producer-consumer
PriorityQueue	comparator	기본 unbounded	우선순위 scheduler
Stack/Deque push	LIFO	capacity 별도	DFS, undo

긴급 job을 FIFO 앞에 끼워 넣기 시작하면 queue 계약이 바뀐다. priority queue나 별도 lane을 명시적으로 설계하고 starvation metric을 둔다.

7. 실제 도메인 적용

Backend worker: capacity, oldest age, rejection, retry storm, dead-letter count를 본다.
Infrastructure deployment: ready task FIFO가 fairness를 줄 수 있지만 resource priority가 필요하면 scheduler 계약을 분리한다.
BFS: 같은 거리 layer 순서를 보존한다. frontier peak가 graph 폭만큼 커질 수 있으므로 visited 수와 max queue size를 기록한다.
Streaming: event queue만으로 exactly-once가 생기지 않는다. offset commit, idempotency, durability가 별도 계약이다.

8. 이건 피한다

무제한 queue로 spike를 흡수한다. 처리율 부족을 heap 증가와 긴 지연으로 바꾼다. bounded capacity와 rejection/backpressure 정책을 둔다.
ArrayList.remove(0)를 FIFO로 쓴다. 뒤 원소 이동이 반복돼 총비용이 커진다. deque의 head/tail 연산을 쓴다.
size 확인 후 insert를 동시 코드에 쓴다. race로 capacity를 넘거나 상태가 어긋난다. atomic concurrent queue API를 쓴다.
null을 job과 empty sentinel로 동시에 쓴다. 결과를 구분할 수 없다. ArrayDeque처럼 null을 금지하거나 명시적 result type을 쓴다.
queue depth만 감시한다. 낮은 처리율에서 작은 depth도 오래된 job을 숨긴다. oldest age와 처리율을 함께 본다.

Reference

Oracle, Queue — Java SE 21 API
Oracle, Deque — Java SE 21 API
Oracle, ArrayDeque — Java SE 21 API
Oracle, BlockingQueue — Java SE 21 API
John D. C. Little, A Proof for the Queuing Formula: L = λW
Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition — Stacks and Queues