우선순위 큐 설계: 힙 구현부터 동시성 처리까지

먼저 처리할 작업을 고르는 자료구조

운영체제 스케줄링, 경로 탐색, 실시간 작업 분배에서는 모든 작업을 도착 순서대로 처리할 수 없다. 우선순위 큐는 각 원소에 우선순위를 두고, 가장 높은 우선순위의 원소를 먼저 조회하거나 제거하는 추상 자료구조다. 일반적으로 힙을 기반으로 구현한다.

최솟값을 먼저 꺼내는 최소 힙과 최댓값을 먼저 꺼내는 최대 힙이 대표적이다. 같은 우선순위의 항목도 입력 순서대로 처리해야 한다면 보조 키나 시퀀스 번호를 둬 안정성을 보장해야 한다.

주요 연산은 삽입(push/insert), 최상위 항목 조회(peek/find-min/max), 추출(pop/extract), 키 감소(decrease-key)다. 대부분의 구현에서 삽입과 추출은 O(log n), 조회는 O(1) 특성을 가진다.

구현 방식은 우선순위 분포와 갱신 빈도로 결정된다

배열 기반 이진 힙은 메모리 레이아웃이 캐시 친화적이고 구현이 단순하다. 삽입과 추출은 O(log n)이며, 감소키를 지원하려면 보조 인덱싱이 필요하다.

피보나치 힙과 페어링 힙은 감소키에 유리하다. 피보나치 힙은 이론상 감소키의 암시적 상수 비용이 낮지만, 구현 복잡성과 상수 요인이 커진다. 실무에서는 페어링 힙이 타협점이 될 수 있다.

우선순위가 소수의 정수 범위에 한정되는 경우에는 버킷 큐를 고려할 수 있다. 평균 O(1) 삽입과 삭제가 가능하며, 네트워크 QoS나 레디 큐처럼 우선순위 구간이 제한된 환경에서 유효하다.

힙은 배열 기반이라 메모리 오버헤드가 낮다. 다만 감소키나 삭제에 무효화 패턴을 사용하면 엔트리 맵(entry-finder)을 위한 추가 메모리가 필요하다.

비교 규칙과 안정성을 먼저 정한다

큐에 넣기 전에는 Comparator 기반의 총순서를 정해야 한다. 동일 우선순위에서 순서를 보장하려면 (priority, sequence, payload) 튜플을 사용하는 방식이 적합하다.

부동소수점 우선순위에는 NaN, +0.0/-0.0, 정밀도 문제가 얽힌다. 정수 우선순위나 정규화된 스코어를 사용하는 편이 안전하다.

단일 락에서 시작해 경합에 맞춰 확장한다

단일 락으로 임계구역을 보호하면 선형화가 단순하다. 경합이 커지면 queue-per-class 형태의 샤딩, 멀티큐와 워크 스틸링 전략을 적용할 수 있다.

ABA 문제와 무효화된 엔트리를 어떤 규칙으로 처리할지도 정해야 한다. 트랜잭션 성질이 필요하다면 삽입과 추출의 원자성을 확보하고, 타임아웃과 취소 토큰을 지원하는 방식이 권장된다.

메모리를 넘는 워크로드는 레벨드 세그먼트 파일과 메모리 힙을 결합한 외부 메모리 구조로 다룰 수 있다. 내구성이 필요하면 Write-Ahead Log(WAL)에 삽입을 기록하고 재시작 시 큐를 재구성한다. 지연된 삭제에 대한 가비지 컬렉션 정책도 함께 설계해야 한다.

스케줄링부터 그래프 탐색까지

우선순위 큐는 OS 레디 큐, 배치 잡 스케줄링, 마이크로서비스 작업 우선순위 처리에 쓰인다. Dijkstra, A*, Prim 같은 그래프 알고리즘에서는 최단거리나 휴리스틱을 기준으로 다음 대상을 선택한다.

네트워킹과 메시징에서는 QoS 큐잉, 레이트 리미팅, 백프레셔 우선 처리에 적용할 수 있다. 제한된 정수 우선순위 환경에서는 버킷 큐가 효율적이다. 주문처리와 거래 시스템에서는 SLA를, 알림과 티켓 시스템에서는 긴급도를 반영하는 데 활용된다.

임계 요청의 우선순위가 적중하고 큐 길이가 적절히 관리되면 p95 지연을 2060% 줄일 수 있다. 같은 자원에서의 효과적 스케줄링으로 처리량은 1030% 개선을 기대할 수 있으며, 긴급 트래픽을 먼저 처리해 오류 전파와 타임아웃을 줄이는 효과도 있다.

삽입과 추출에서 지켜야 할 일관성

⤢✕

put과 pop은 단일 락 기준의 임계구역에서 힙 연산을 수행하고, 무효화된 엔트리는 건너뛴다. 성공하면 아이템이나 상태를 반환하며, 비어 있는 큐에서의 pop은 None 또는 예외로 처리한다. 잘못된 우선순위, 취소, 타임아웃도 에러 처리 범위에 포함된다.

각 연산은 선형화(linearizability)를 보장하며, 삽입과 삭제가 원자적 단위라면 실패 시 별도의 롤백은 필요하지 않다.

구현별 선택 기준

구현	성능(삽입/추출/감소키)	확장성	일관성	안정성	운영 편의
배열 기반 이진 힙	O(log n)/O(log n)/O(log n)	단일 락에서 중간, 샤딩으로 개선	선형화 용이	기본 비안정, 시퀀스로 보완	구현·디버깅 용이
페어링 힙	평균 빠름, 감소키 유리	스레드 안전 구현 난도 ↑	구조 복잡	비안정, 보완 필요	라이브러리 의존 권장
피보나치 힙	이론적 최적, 감소키 암시적 상수 ↓	실무 상수 비용 큼	복잡도 ↑	비안정	운영 복잡
스킵리스트 기반	O(log n)	락 분할 유리	비교적 단순	안정성 보완 필요	정렬 순회 유리
버킷 큐(정수)	평균 O(1)	우선순위 범위 의존	단순	범위 내 안정 보완	QoS에 최적

Python에서 lazy deletion을 적용한 예제

Python 3.10+와 표준 라이브러리 heapq를 사용하는 단일 스레드 예제다. 동일 우선순위의 안정성을 위해 시퀀스 번호를 사용하고, decrease-key는 무효화 패턴으로 처리한다.

import heapq
import itertools

class PriorityQueue:
    def __init__(self):
        self._heap = []
        self._entry_finder = {}  # item -> [priority, seq, item]
        self._REMOVED = object()
        self._seq = itertools.count()

    def put(self, item, priority):
        if item in self._entry_finder:
            self.remove(item)
        entry = [priority, next(self._seq), item]
        self._entry_finder[item] = entry
        heapq.heappush(self._heap, entry)

    def remove(self, item):
        entry = self._entry_finder.pop(item)
        entry[2] = self._REMOVED  # lazy deletion

    def decrease_key(self, item, new_priority):
        # new_priority가 더 작을 때만 갱신
        if item in self._entry_finder and new_priority < self._entry_finder[item][0]:
            self.put(item, new_priority)

    def pop(self):
        while self._heap:
            priority, _, item = heapq.heappop(self._heap)
            if item is not self._REMOVED:
                del self._entry_finder[item]
                return item, priority
        raise KeyError("pop from an empty priority queue")

    def peek(self):
        while self._heap:
            priority, _, item = self._heap[0]
            if item is self._REMOVED:
                heapq.heappop(self._heap)  # clean up
                continue
            return item, priority
        return None

    def empty(self):
        return not any(e[2] is not self._REMOVED for e in self._heap)

# 사용 예
if __name__ == "__main__":
    pq = PriorityQueue()
    pq.put("low", 5)
    pq.put("high", 1)
    pq.put("medium", 3)
    pq.decrease_key("medium", 0)
    print(pq.pop())  # ('medium', 0)
    print(pq.pop())  # ('high', 1)
    print(pq.pop())  # ('low', 5)

동일 우선순위 항목의 순서는 seq 카운터로 안정화한다. 제거와 감소키는 lazy deletion으로 처리해 힙 재구성 비용을 줄이지만, 주기적인 청소가 필요하다. 멀티스레드 환경에서는 외부에서 락으로 put과 pop의 임계구역을 보호하고, 경합이 높으면 샤딩을 고려한다.

제한된 자원에서 중요한 작업을 앞세우려면 배열 기반 이진 힙, 시퀀스 기반 안정화, lazy deletion을 조합할 수 있다. 동시성 요구에는 샤딩과 워크 스틸링을, 외부 메모리와 내구성 요구에는 WAL과 재구성 전략을 더한다. 구현 선택은 우선순위 분포, 감소키 빈도, 동시성 요구 수준을 기준으로 결정한다.