힙과 우선순위 큐는 데이터를 완전히 정렬하는 구조가 아니다

vx_developer·2일 전
개발기초데이터알고리즘우선순위 큐자료구조힙

코테보다가

목록 보기
27/29
post-thumbnail

힙을 처음 배우면 부모 노드가 자식 노드보다 크거나 작은 완전 이진 트리라고 설명한다. 우선순위 큐는 우선순위가 가장 높은 데이터를 먼저 꺼내는 자료구조라고 배운다.

priorityQueue.enqueue({
  videoId: "video-101",
  priority: 10
});

const nextJob = priorityQueue.dequeue();

priority가 가장 높은 작업을 먼저 꺼낼 수 있다. 최대 힙에서는 가장 큰 값이 루트에 있고, 최소 힙에서는 가장 작은 값이 루트에 있다는 설명도 입문 단계에서는 힙의 동작을 이해하는 데 유용하다.

하지만 실제 영상 처리 서비스에서는 숫자가 가장 큰 작업을 선택하는 것만으로 충분하지 않다. 유료 사용자의 영상은 일반 사용자보다 먼저 처리해야 할 수 있고, 오랫동안 기다린 작업은 우선순위를 높여야 하며, 장애 복구 작업은 모든 일반 작업보다 먼저 실행해야 할 수도 있다. 여러 작업 서버가 동시에 작업을 가져간다면 같은 작업을 두 번 처리하지 않도록 해야 한다.

우선순위는 누가 결정하는가? 작업의 중요도가 바뀌면 힙에 들어 있는 값도 즉시 수정해야 할까? 높은 우선순위 작업이 계속 들어오면 일반 작업은 언제 처리해야 할까? 우선순위 큐에서 먼저 꺼냈다는 사실만으로 한 작업 서버만 처리한다고 보장할 수 있을까?

실제 서비스에서 힙과 우선순위 큐를 사용한다는 것은 모든 데이터를 순서대로 정리하는 일이 아니라, 계속 변하는 작업 집합에서 지금 처리해야 할 하나를 반복해서 선택하는 비용을 줄이는 것이다.

모든 작업을 정렬해야 다음 작업을 선택할 수 있을까?

영상 변환 서비스에는 다음과 같은 작업이 들어온다고 해보자.

type VideoJob = {
  id: string;
  videoId: string;
  tier: "free" | "pro";
  urgency: "normal" | "incident";
  createdAt: Date;
};

가장 단순한 구현은 새로운 작업이 들어올 때마다 전체 배열을 정렬하는 것이다.

const jobs: VideoJob[] = [];

function addJob(job: VideoJob) {
  jobs.push(job);

  jobs.sort((a, b) => {
    return getPriority(b) - getPriority(a);
  });
}

function takeNextJob() {
  return jobs.shift();
}

이 코드는 동작한다. 작업 전체가 우선순위순으로 정렬되므로 첫 번째 항목을 꺼내면 다음 작업을 얻을 수 있다.

그러나 작업이 하나 추가될 때마다 전체 목록을 다시 정렬한다. 작업이 n개라면 일반적인 정렬 비용은 O(n log n)이다. 영상 작업이 가끔 들어오고 관리 화면에서 전체 순위를 자주 보여줘야 한다면 이 선택도 충분할 수 있다.

반면 서비스가 실제로 반복하는 동작이 다음과 같다면 전체 정렬은 필요한 것보다 많은 일을 한다.

1. 작업 하나가 들어온다.
2. 지금 가장 중요한 작업 하나를 꺼낸다.
3. 새로운 작업이 다시 들어온다.
4. 다시 가장 중요한 작업 하나를 꺼낸다.

두 번째로 중요한 작업과 열 번째로 중요한 작업 사이의 정확한 순서는 당장 필요하지 않다. 지금 처리할 하나만 정확히 찾으면 된다.

힙은 이 요구에 맞춰 전체 순서를 포기한다. 가장 우선순위가 높은 루트만 보장하고 나머지 데이터는 다음 루트를 효율적으로 찾을 수 있는 정도로만 배치한다.

const jobQueue = new PriorityQueue<VideoJob>({
  compare: (a, b) => compareJobs(a, b)
});

jobQueue.enqueue(job);
const nextJob = jobQueue.dequeue();

힙으로 구현된 우선순위 큐에서는 일반적으로 가장 중요한 작업을 확인하는 데 O(1), 작업을 추가하거나 제거한 뒤 힙의 조건을 복구하는 데 O(log n)이 필요하다.

여기서 중요한 차이는 힙이 더 빠른 정렬 방법이라는 것이 아니다. 힙은 전체 정렬 결과를 만들지 않는다. 서비스가 실제로 요구하는 “다음 작업 하나 선택하기”에 필요한 부분만 유지한다.

우선순위는 하나의 숫자가 아니라 비즈니스 규칙이다

영상 작업의 우선순위를 단순히 클라이언트가 보낸 숫자로 결정할 수 있을까?

// Bad: 사용자가 원하는 우선순위를 직접 결정한다.
await videoQueue.enqueue({
  videoId: input.videoId,
  priority: input.priority
});

외부 입력을 그대로 사용하면 무료 사용자가 매우 큰 우선순위를 보내 자신의 작업을 먼저 처리할 수 있다. 우선순위는 요청 데이터가 아니라 서버의 정책으로 계산해야 한다.

function calculatePriority(
  job: VideoJob,
  now: Date
) {
  const incidentScore =
    job.urgency === "incident" ? 10_000 : 0;

  const tierScore =
    job.tier === "pro" ? 1_000 : 0;

  const waitingMinutes = Math.floor(
    (now.getTime() - job.createdAt.getTime()) / 60_000
  );

  return incidentScore + tierScore + waitingMinutes;
}

장애와 관련된 작업에는 가장 큰 점수를 주고, 유료 사용자의 작업에는 추가 점수를 주며, 오래 기다린 작업에는 대기 시간만큼 점수를 더한다.

하지만 urgency와 tier도 클라이언트가 주장한 값을 그대로 사용해서는 안 된다. 서버는 로그인한 사용자의 구독 상태와 운영자가 등록한 장애 정보를 신뢰할 수 있는 저장소에서 확인해야 한다.

async function createVideoJob(
  userId: string,
  input: CreateVideoJobInput
) {
  const user = await userRepository.findById(userId);
  const video = await videoRepository.findOwnedVideo(
    userId,
    input.videoId
  );

  if (!user || !video) {
    throw new Error("Video not found");
  }

  const job = await videoJobRepository.create({
    videoId: video.id,
    tier: user.subscriptionTier,
    urgency: "normal",
    status: "queued",
    createdAt: new Date()
  });

  await videoQueue.enqueue(job);

  return job;
}

현실의 “중요한 영상 작업”은 코드에서 다음과 같이 변환된다.

입력
사용자 ID와 처리할 영상 ID

상태
검증된 구독 등급, 장애 여부, 생성 시각, 작업 상태

출력
현재 정책에 따라 선택된 다음 처리 작업

우선순위 큐는 이 규칙을 실행하는 도구다. 어떤 사용자를 먼저 처리할지는 자료구조가 결정하지 않는다. 제품 정책과 운영 규칙을 비교 함수와 점수 계산으로 표현해야 한다.

점수가 같을 때도 처리 순서를 정의해야 한다

두 작업의 우선순위 점수가 같다면 어떤 작업을 먼저 처리해야 할까? 비교 함수가 점수만 확인하면 같은 우선순위의 작업 순서는 구현 세부사항에 따라 달라질 수 있다.

function compareJobs(
  a: VideoJob,
  b: VideoJob
) {
  const priorityDifference =
    calculatePriority(a, new Date()) -
    calculatePriority(b, new Date());

  if (priorityDifference !== 0) {
    return priorityDifference;
  }

  return b.createdAt.getTime() - a.createdAt.getTime();
}

점수가 같을 때는 먼저 생성된 작업을 우선하도록 두 번째 기준을 둔다. 생성 시각까지 같을 가능성이 있다면 작업 ID와 같은 안정적인 값을 마지막 기준으로 사용할 수 있다.

function compareJobs(
  a: RankedVideoJob,
  b: RankedVideoJob
) {
  if (a.priority !== b.priority) {
    return a.priority - b.priority;
  }

  if (a.createdAt.getTime() !== b.createdAt.getTime()) {
    return b.createdAt.getTime() - a.createdAt.getTime();
  }

  return b.id.localeCompare(a.id);
}

이처럼 비교 규칙은 하나의 숫자보다 구체적이어야 한다. 장애 여부, 구독 등급, 대기 시간과 생성 순서가 어떤 순서로 적용되는지 명확해야 같은 입력에서 일관된 결과를 얻을 수 있다.

오래 기다릴수록 우선순위가 높아진다면 무엇이 달라질까?

앞의 calculatePriority()는 현재 시각을 사용한다. 작업이 큐에 들어간 뒤 시간이 지나면 대기 점수가 올라간다.

하지만 힙은 내부 데이터의 값이 저절로 변했다는 사실을 알지 못한다.

const queuedJob = {
  ...job,
  priority: calculatePriority(job, new Date())
};

videoQueue.enqueue(queuedJob);

작업을 넣을 때 계산한 점수만 저장하면 한 시간 뒤에도 같은 점수가 남는다. 반대로 작업을 꺼낼 때마다 모든 항목의 점수를 다시 계산하고 힙을 만들면 최신 결과를 얻을 수 있지만, 반복 비용이 커진다.

이 문제에는 하나의 정답만 있는 것이 아니다. 서비스 요구사항에 따라 다음과 같은 선택을 할 수 있다.

  • 대기 시간 점수를 분 단위가 아니라 넓은 구간으로 계산한다.
  • 일정 시간 이상 기다린 작업을 별도의 우선순위 큐로 이동한다.
  • 주기적으로 일부 작업의 우선순위를 다시 계산한다.
  • 무료 작업과 유료 작업에 별도 큐를 두고 정해진 비율로 번갈아 가져간다.
  • 작업을 꺼낼 때 저장소의 현재 상태를 확인하고 오래된 항목이면 다시 등록한다.

중요한 것은 “우선순위가 동적이다”라는 규칙을 단순한 정적 숫자로 축소하지 않는 것이다. 우선순위가 언제 계산되고 언제 다시 평가되는지까지 정의해야 한다.

높은 우선순위 작업만 계속 처리해도 될까?

유료 사용자의 작업이 계속 들어오면 무료 사용자의 영상은 영원히 처리되지 않을 수 있다. 이를 기아 상태라고 한다. 실행 가능한 작업이 큐에 있지만 다른 작업에 계속 밀려 실행 기회를 얻지 못하는 상황이다.

다음 정책은 유료 작업을 항상 무료 작업보다 먼저 처리한다.

function getPriority(job: VideoJob) {
  return job.tier === "pro" ? 100 : 10;
}

유료 작업의 유입량이 작업 서버의 처리량보다 많다면 무료 작업은 큐에서 빠져나올 수 없다. 비즈니스가 유료 사용자에게 더 빠른 처리를 약속했더라도 무료 사용자의 작업을 무기한 방치하겠다는 의미는 아닐 수 있다.

대기 시간을 우선순위에 반영하는 에이징 정책을 적용할 수 있다.

function getPriority(
  job: VideoJob,
  now: Date
) {
  const tierScore =
    job.tier === "pro" ? 100 : 10;

  const waitingHours = Math.floor(
    (now.getTime() - job.createdAt.getTime()) /
      3_600_000
  );

  return tierScore + waitingHours * 10;
}

무료 작업도 오래 기다리면 점수가 올라가 언젠가는 처리될 수 있다.

또 다른 방법은 큐를 분리하고 작업 서버가 가져가는 비율을 정하는 것이다.

async function takeNextJob() {
  if (processedProJobs < 4) {
    const proJob = await proQueue.dequeue();

    if (proJob) {
      processedProJobs += 1;
      return proJob;
    }
  }

  processedProJobs = 0;

  return (
    await freeQueue.dequeue()
  ) ?? proQueue.dequeue();
}

예를 들어 유료 작업 네 개를 처리한 뒤 무료 작업 하나를 처리하도록 정할 수 있다. 이 방식은 하나의 점수로 모든 정책을 표현하지 않고 처리 비율을 명시한다.

어떤 방식이 더 적합한지는 서비스가 약속한 처리 시간과 작업량에 따라 달라진다. 우선순위는 기술적인 정렬 기준이 아니라 어떤 사용자의 기다림을 얼마나 허용할지 결정하는 제품 정책이다.

큐에서 꺼낸 작업이 실제로 처리 가능한지는 다시 확인해야 한다

영상 작업이 우선순위 큐에서 기다리는 동안 사용자가 영상을 삭제하거나 구독을 취소할 수 있다. 운영자가 작업을 중단시켰을 수도 있다.

큐에 들어 있는 데이터가 생성 당시에는 정확했더라도 실행 시점에는 오래된 상태가 될 수 있다.

async function processNextJob() {
  const queuedJob = videoQueue.dequeue();

  if (!queuedJob) {
    return;
  }

  await transcodeVideo(queuedJob.videoId);
}

이 코드는 큐의 항목을 현재 상태의 원본으로 사용한다. 삭제된 영상이나 이미 취소된 작업도 처리할 수 있다.

큐에는 작업을 찾기 위한 최소한의 정보와 정렬에 필요한 정보를 넣고, 실행 전 데이터베이스에서 현재 상태를 다시 확인하는 편이 안전하다.

type QueuedJob = {
  jobId: string;
  priority: number;
  version: number;
};

async function processNextJob() {
  const queuedJob = videoQueue.dequeue();

  if (!queuedJob) {
    return;
  }

  const job = await videoJobRepository.findById(
    queuedJob.jobId
  );

  if (
    !job ||
    job.status !== "queued" ||
    job.version !== queuedJob.version
  ) {
    return;
  }

  const claimed =
    await videoJobRepository.claimIfQueued(job.id);

  if (!claimed) {
    return;
  }

  await transcodeVideo(claimed.videoId);
}

데이터베이스의 작업 레코드가 상태의 Source of Truth가 되고, 힙에 저장된 항목은 다음 후보를 빠르게 찾기 위한 계산 데이터가 된다.

version이 다르다면 작업의 우선순위나 상태가 큐에 들어간 뒤 변경되었다는 뜻이다. 오래된 항목은 무시하고 최신 버전의 항목을 따로 처리할 수 있다.

claimIfQueued()는 작업 상태가 queued일 때만 processing으로 변경해야 한다. 여러 작업 서버가 비슷한 시점에 같은 작업을 선택하더라도 상태 변경에 성공한 하나의 서버만 실제 처리를 시작한다.

힙은 가장 중요한 후보를 선택할 수 있지만, 동시 실행 제어까지 해결하지는 않는다. 작업 소유권은 데이터베이스의 조건부 업데이트나 트랜잭션처럼 여러 서버가 공유하는 저장소에서 보장해야 한다.

우선순위 큐가 필요하지 않은 경우도 있다

작업이 열 개뿐이고 우선순위가 자주 바뀌며 관리 화면에서 전체 순서를 항상 보여줘야 한다면 배열을 정렬하는 구현이 더 단순할 수 있다.

작업이 데이터베이스에 저장되어 있고 여러 서버가 함께 처리한다면 애플리케이션 메모리의 힙보다 데이터베이스 조회가 더 적합할 수도 있다.

SELECT id
FROM video_jobs
WHERE status = 'queued'
ORDER BY priority DESC, created_at ASC
LIMIT 1
FOR UPDATE SKIP LOCKED;

이 쿼리는 처리 가능한 작업 중 우선순위가 가장 높은 하나를 선택하면서 다른 작업 서버가 잠근 행은 건너뛴다. 작업 수와 조회 빈도에 맞는 인덱스가 필요하지만, 여러 서버가 공유하는 작업 상태를 한곳에서 관리할 수 있다.

반대로 한 프로세스 안에서 수많은 후보가 계속 들어오고 가장 중요한 항목을 반복해서 꺼내야 한다면 메모리 힙이 잘 맞는다. 영구 보관이 필요한 작업은 데이터베이스에 저장하고, 빠른 선택을 위한 인덱스 구조만 메모리에 유지하는 조합도 가능하다.

자료구조를 선택할 때는 O(log n)만 비교해서는 안 된다. 작업이 어디에 저장되는지, 프로세스가 재시작돼도 남아야 하는지, 여러 서버가 같은 큐를 공유하는지까지 함께 판단해야 한다.

우선순위 작업 처리를 설계하기 전에 확인할 질문

  1. 서비스가 전체 작업 순서를 필요로 하는가, 지금 처리할 하나만 필요로 하는가?
  2. 우선순위를 결정하는 비즈니스 규칙은 무엇이며 어떤 기준이 먼저 적용되는가?
  3. 클라이언트가 보낸 우선순위가 아니라 서버가 검증한 상태로 점수를 계산하는가?
  4. 우선순위가 같은 작업의 처리 순서를 안정적으로 결정했는가?
  5. 대기 시간이나 상태 변화에 따라 우선순위를 다시 계산해야 하는가?
  6. 높은 우선순위 작업이 계속 들어올 때 낮은 우선순위 작업이 영원히 기다리지 않는가?
  7. 큐에 저장된 항목과 데이터베이스의 현재 상태 중 무엇이 Source of Truth인가?
  8. 취소되거나 변경된 작업을 실행 직전에 다시 검증하는가?
  9. 여러 작업 서버가 같은 작업을 동시에 처리하지 않도록 소유권을 획득하는 과정이 있는가?
  10. 프로세스가 종료되었을 때 메모리의 우선순위 큐를 복구할 수 있는가?
  11. 작업 전체를 자주 조회해야 한다면 정렬된 배열이나 데이터베이스 조회가 더 단순하지 않은가?
  12. 대기 작업 수, 우선순위별 대기 시간과 기아 상태를 관찰할 수 있는가?

힙은 전체 순서 대신 다음 선택에 집중한다

힙은 모든 데이터를 완전히 정렬하지 않는다. 가장 우선순위가 높은 항목을 빠르게 확인하고, 작업이 추가되거나 제거될 때 다음 선택에 필요한 조건만 복구한다. 따라서 수많은 작업 중 지금 처리할 하나를 반복해서 선택하는 서비스에 잘 맞는다.

하지만 힙을 도입한다고 우선순위 정책까지 자동으로 만들어지는 것은 아니다. 영상 처리 서비스에서는 장애 여부, 구독 등급, 대기 시간과 생성 순서가 어떤 관계를 가지는지 먼저 정의해야 한다. 높은 우선순위 작업 때문에 다른 작업이 영원히 밀리지 않도록 처리 규칙도 설계해야 한다.

또한 메모리의 우선순위 큐는 다음 후보를 고르는 계산 구조일 뿐이다. 작업의 현재 상태와 실행 소유권은 여러 서버가 공유할 수 있는 저장소에서 관리해야 한다. 실행 직전에는 작업이 여전히 유효한지 확인하고, 하나의 작업 서버만 상태 변경에 성공하도록 해야 한다.

결국 힙과 우선순위 큐를 선택한다는 것은 데이터를 모두 정렬하겠다는 뜻이 아니다. 서비스가 반복해서 내려야 하는 “지금 무엇을 먼저 처리할 것인가”라는 결정을 효율적으로 유지하겠다는 설계 판단이다.

다음 글에서는 트리가 단순히 부모와 자식의 관계를 저장하는 구조를 넘어, 계층을 표현하고 탐색 범위를 단계적으로 줄이는 데 어떻게 사용되는지 살펴본다.

profile
vx_developer
Vision eXperience Developer
이전 포스트

큐는 먼저 들어온 데이터를 먼저 처리하는 구조가 아니다

다음 포스트

트리는 부모와 자식으로 데이터를 연결하는 구조가 아니다

0개의 댓글