실습 코드: https://github.com/DAN-MU-ZI/study/tree/main/03_system/01_url_shortener

도입 및 목표 스펙

『가상 면접 사례로 배우는 대규모 시스템 설계 기초』에 등장하는 URL 단축 서비스를 직접 구현해 보았다. 하루 1억 건의 URL을 단축하는 시스템에서는 단순한 기능 구현보다 부하를 견디는 아키텍처 설계와 병목 추적이 훨씬 중요했다.

이 글은 URL 단축기를 직접 구축하고, 성능의 발목을 잡는 병목 지점들을 하나씩 제거해 최종적으로 목표 처리량(RPS)에 도달하기까지의 과정을 정리한 기록이다.

목표 스펙은 다음과 같이 잡았다.

• 쓰기 연산: 매일 1억 개의 단축 URL 생성
• 초당 쓰기 연산: 1억 / 24시간 / 3600초 ≒ 1,160 RPS
• 읽기 연산: 쓰기 대비 10배 비중으로 가정 = 11,600 RPS
• 목표 RPS: 약 11,000
• (DB 총 용량 계산은 이번 실습 범위에서 제외)

시스템 아키텍처

시스템의 뼈대는 Spring Boot + Redis + MongoDB로 구성했다. 압도적으로 많은 읽기 요청은 Redis를 통해 최대한 흡수하고, URL 데이터의 영구 저장 및 정합성 유지는 MongoDB에 위임하는 구조다.

기본 기능 흐름

API는 아래 두 개로 단순화했다.

1. POST /api/v1/data/shorten

• 입력: { longUrl: longURIstring }
• 출력: 단축 URL

2. GET /api/v1/{shortUrl}

• 출력: 원본 URL로 HTTP 리다이렉트(301/302)

핵심 동작 흐름은 다음과 같다.

1. shorten: ID 생성 -> Base62 인코딩 -> Mongo 저장 -> Redis 캐시 반영
2. redirect: Redis 조회 -> miss 시 Mongo 조회 -> Redis 갱신 -> 리다이렉트 반환

초기 스택과 한계

초기 아키텍처는 보편적인 Spring MVC + PostgreSQL 조합으로 시작했다. 하지만 테스트를 진행할수록 쓰기/조회 경로가 길어지고, 부하가 쌓일수록 응답 지연(Latency)이 빠르게 튀는 현상이 발생했다.

URL 단축 서비스는 복잡한 조인(Join)보다는 단순한 Key-Value 형태의 조회와 저장 비중이 절대적이다. 따라서 Document 기반으로 Upsert 경로가 더 가볍고 유연한 MongoDB가 이 시스템에 훨씬 적합하다고 판단하여 전환을 결정했다.

전환 결과는 아래와 같다.

핵심 문제 해결 과정 (Troubleshooting)

이슈 1. 단축키 충돌과 DB 부하 (ID 생성 전략의 진화)

초기에는 임의의 해시(Hash) 값을 기반으로 단축키를 생성했다. 하지만 이 방식은 필연적으로 '충돌 확인 -> 재시도 로직을 동반했고, 이는 쓰기 경로를 무겁게 만드는 주범이었다.

1. 1차 개선 (Mongo Sequence + Base62): 충돌 검증 로직을 아예 제거하기 위해 MongoDB의 시퀀스를 활용한 고유 ID를 발급받고, 이를 Base62로 인코딩했다. 쓰기 경로는 단순해졌지만, ID 발급을 위해 DB를 2번 왕복해야 하는 2-way 경로(findAndModify -> update) 병목이 새롭게 발생했다.
2. 최종 개선 (Snowflake ID): 데이터베이스에 의존하지 않고 애플리케이션 내부에서 고유 ID를 생성하는 Snowflake ID 방식을 도입하여 DB 왕복 오버헤드를 완전히 제거했다.

이슈 2. 조회 성능 극대화

조회 트래픽 방어를 위해 Look-aside (Cache Aside) 패턴을 적용했다. Redis에 데이터가 있으면 즉시 반환(Hit)하고, 없으면 DB를 조회한 뒤 Redis를 갱신(Miss)한다.

단축 URL은 '생성 직후에 즉시 공유'되는 서비스 특성을 가진다. 이러한 특성 덕분에 생성 시점에 캐시를 미리 밀어 넣는 웜업(Warm-up) 혹은 빠른 캐시 갱신 전략이 적중률을 높이고 데이터베이스 부하를 극적으로 낮추는 데 큰 역할을 했다.

이슈 3. 병목 지점 파악과 리소스 튜닝

Grafana 모니터링을 통해 시스템 지표를 살펴보던 중, 애플리케이션의 메모리 Young 영역이 빠르게 포화되며 Minor GC 지연이 높은 값을 유지하는 패턴을 발견했다.

• 현상: Young 영역 포화 $\rightarrow$ STW(Stop-The-World) 빈도 증가 $\rightarrow$ GC 누적 $\rightarrow$ 처리량 하락 및 Tail Latency(P95) 악화

• 조치:

• CPU 코어 확장: 2 -> 4 RAM 증설: 4GB -> 12GB (Xms, Xmx 옵션 통일)

• 결과: Minor GC 소요 시간이 200ms -> 50ms로 단축되었고, CPU 활용률이 안정화되며 처리량이 눈에 띄게 상승했다.

부하 테스트 및 최종 검증 (k6)

테스트 시나리오 소개

목표 RPS 11,000을 검증하기 위해 k6를 활용해 쓰기 1 : 읽기 10 비율로 시나리오를 구성했다.

export const options = {
  scenarios: {
    load_test: {
      executor: "constant-arrival-rate",
      duration: "30s",
      preAllocatedVUs: 1000,
      rate: 1000,
      timeUnit: "1s",
    },
  },
};

로컬 환경에서의 한계

처음에는 로컬 환경(Windows 10, i7-7700HQ)에서 테스트를 진행했다. 하지만 자원 튜닝을 거쳐도 일정 수준(약 6,000 RPS) 이상 올라가지 않았다. 원인은 애플리케이션의 한계가 아니라, 부하를 생성하는 k6 툴과 서버가 같은 머신 내에서 CPU를 두고 경합(Contention)하고 있었기 때문이다.

EC2 환경 분리 후 최종 결과

정확한 측정을 위해 부하 생성기와 서비스 실행 환경을 물리적으로 분리(Ubuntu 22, EC2 t3.xlarge)한 뒤 10분간 장기 테스트를 수행했다.

마무리 (회고)

이번 대규모 시스템 설계와 부하 테스트를 진행하며 얻은 가장 큰 교훈은 "알고리즘 최적화만으로는 한계가 있으며, 시스템 전반에서 병목이 발생하는 계층을 정확히 짚어내야 한다"는 점이다.

1. 시야의 확장: 코드 레벨을 넘어 시스템 전체로 이전까지는 기능 구현에 주로 집중했기 때문에, 성능 이슈가 발생해도 그 원인을 항상 '코드 레벨'에서만 찾으려 했다. 하지만 트래픽 규모가 커지자 해시 충돌, 2-way ID 생성으로 인한 DB 부하, 그리고 JVM 메모리(GC) 포화 등 전혀 다른 계층의 원인들이 겹치며 단계마다 성능 상한선을 만들고 있었다.

2. 모니터링과 데이터 기반의 문제 해결 비록 초기에는 원인을 찾기 위해 헤매는 시간도 있었지만, 이 과정은 오히려 성장할 수 있었다. Grafana를 구축해 시스템 지표를 직접 모니터링하면서, 감이 아닌 '데이터'를 기반으로 병목 지점을 추적하고 튜닝하는 일련의 노하우를 얻었다. 각 계층의 한계를 하나씩 돌파하며 11,000 RPS라는 목표를 달성해 낸 과정은 무척 뜻깊은 경험이었다.

3. 향후 개선 과제 (Next Step) 이제는 단일 서버에서의 성능 최적화를 넘어, 더 견고한 아키텍처에 대한 고민으로 시야를 넓혀야 한다.

Top-down 최적화: 이번 경험은 문제가 발생한 지점부터 해결해 나가는 Bottom-up 방식으로 접근해나갔다. 다음 설계에서는 3-tier 아키텍처를 순서대로 검증해나가면서, 전체 시스템 관점에서 어디에 부하가 집중되는지 먼저 식별하는 구조적이고 하향식인 접근법을 연습해보고자 한다.

SPOF(단일 장애점) 극복: 현재 아키텍처는 특정 노드에 장애가 발생하면 전체 시스템에 영향을 미칠 수 있다. 이를 Scale-out 이나 다른 방식들을 생각해볼 수 있을것 같다.

고가용성 확보: 이를 해결하기 위해 서버 다중화나 리전 분리 등 고가용성을 보장하는 아키텍처로의 확장을 고민해 볼 계획이다.

비용 효율성: 더불어 무작정 인프라를 늘리는(Scale-out) 것이 아니라, EC2의 비용 효율성을 철저히 따져가며 성능과 유지 유지비용 사이의 '최적의 타협점'을 찾는 것도 훌륭한 다음 과제가 될 것이다.

로스트아크 OpenAPI는 1분당 100회 호출량 제한이 있으며, 이를 고려하지 않는다면 서비스에서 429 에러를 반환할 수 있음. 그래서 전체 API 호출량을 제한해야 한다고 생각함. 이렇게 요청량을 제한하는 기술을 유량제어라고 함. 일반적으로 클라이언트(IP Based) 단위로 유량제어를 구현하는데, 프로젝트 전체 서비스 용량을 기반으로 실습을 설계함. 또한 관심사들을 추가해서 확인해보고자 함.

• OpenAI나 다른 LLM 서비스들이 요청횟수가 아닌 토큰량이라는 개념으로 제어하는 경우도 익혀보고자 요청별 비용을 다르게 설정해보기
• 분산 환경에서도 안전하게 동작하도록 로드밸런서와 여러 서버를 구성하여 실습해보기
• Redis의 싱글 스레드기반 동작 특성을 이용하여 동시성 문제를 해결해보기
• OpenAPI 서버와 시간이 달라 초기화 시점이 불일치하는 문제를 해결하기 위한 슬라이딩 윈도우 방식 적용하기
• 백엔드 프레임워크별 구현해보기(Python(FastAPI), Java(Spring Boot))

실습 링크

GitHub 유량 제어 시스템 실습 레포지토리

핵심 개념

1. 전체 용량 제어 (Global Rate Limiting)

일반적인 IP 기반 제어는 클라이언트가 많아지면 전체 트래픽이 무한정 늘어날 수 있음. 로스트아크 API처럼 프로젝트(API Key) 단위로 총량이 정해져 있는 경우, 모든 서버가 Redis의 global 키 하나를 공유해서 카운팅해야 함.

2. 요청별 비용 차등화 (Weighted Token)

LLM 서비스들이 단순히 "질문 횟수"가 아니라 "토큰 양"으로 과금하는 것과 같은 원리임. 요청별 비용이 다르기 때문에 남은 토큰을 초과한 요청이 들어오면 거절하는 방식으로 구현함.

이렇게 가중치를 두면, 무거운 요청을 많이 보내는 클라이언트를 더 빨리 제한할 수 있어 전체 시스템 안정성을 높일 수 있음.

3. 시간 불일치 해결 (Sliding Window)

OpenAPI 서버와 우리 서버의 시간은 미세하게 다를 수밖에 없음. 만약 Fixed Window(매 분 00초 초기화)를 쓰면, 서로 기준이 달라서 429 에러가 터질 위험이 큼.

Sliding Window는 "현재 시점으로부터 과거 60초"를 매번 계산하기 때문에, 초기화 시점에 얽매이지 않고 훨씬 안전하게 유량을 제어할 수 있음.

현재 요청으로부터 60초전까지의 요청 기록으로부터 남은 토큰을 계산하고, 현재 요청이 요구하는 토큰이 여유가 있다면 요청을 처리하고, 여유가 없다면 거절함.

구현 과정

1. 시스템 아키텍처

로컬 PC에서 Docker Compose로 단일 서버와 다중 서버(Nginx 로드밸런싱) 환경을 각각 구성하여 비교했음.

단일 서버 (Single Server)	다중 서버 (Multi Server)

2. 동작 흐름 (Middleware Logic)

• Client: 요청 전송
• API Server (Middleware): 비즈니스 로직 실행 전, 먼저 Redis와 통신하여 한도 체크
• Redis: Lua Script를 통해 원자적으로 토큰 계산 후 결과 반환
• Logic: 허용된 경우에만 실제 비즈니스 로직(DB 조회 등) 수행

2. 동시성 문제 해결 (Race Condition)

단일 서버라면 자원 점유로 인한 Lock 발생하지 않는다. 하지만 서버 3대가 동시에 Redis 값을 읽음(99) → +1 → 저장(100)을 시도하면, 타이밍 문제로 100을 훌쩍 넘겨버릴 수 있음.

Redis는 싱글 스레드 기반이라 한 번에 하나의 명령어만 처리하는데, Lua 스크립트를 통해 하나의 명령어처럼 원자적으로 실행되도록 할 수 있다. 따라서 동시 다발적인 요청이 와도 순차적으로 처리되어 Race Condition이나 초과 요청을 차단할 수 있다.

사용된 Lua 스크립트 핵심 로직:

-- 1. 60초 지난 과거 데이터 청소
redis.call('ZREMRANGEBYSCORE', key, 0, window_start)

-- 2. 현재 남은 토큰 합산 (데이터 포맷: "uuid:cost")
local members = redis.call('ZRANGEBYSCORE', key, window_start, now)
local current_usage = 0
for i, member in ipairs(members) do
    local cost = tonumber(string.match(member, ":(%d+)$"))
    current_usage = current_usage + cost
end

-- 3. 한도 체크 및 저장
if current_usage + request_cost <= limit then
    redis.call('ZADD', key, now, request_id_with_cost)
    return remaining
else
    return -1 -- 거절
end

검증 테스트

제대로 동작하는지 확인하려고 통합 테스트 스크립트(test_rate_limit.ps1)를 만들어서 돌려봤음.

테스트 시나리오

1. GET (1점) × 5번 : 기본 조회 테스트 (누적 5)
2. POST (5점) × 5번 : 쓰기 작업 테스트 (누적 30)
3. SEARCH (3점) × 5번 : 검색 작업 테스트 (누적 45)
4. DELETE (10점) × 5번 : 무거운 작업 테스트 (누적 95)
5. 추가 POST (5점) 1번 : 100 토큰 한도 꽉 채우기
6. 초과 요청 날려보기 : 101번째 토큰 시도시 429 에러 확인

결과 화면 (실제 로그)

[2] GET requests - 1 token each
    GET 1: remaining=99, server: api1 (total: 1)
    ...
    GET 5: remaining=95, server: api2 (total: 5)

[3] POST requests - 5 tokens each (누적 10~30)
    POST 1: remaining=90, server: api3 (total: 10)
    POST 2: remaining=85, server: api1 (total: 15)
    ...

[4] SEARCH requests - 3 tokens each (누적 33~45)
    SEARCH 1: remaining=42, server: api2 (total: 33)
    ...

[5] DELETE requests - 10 tokens each (누적 55~95)
    DELETE 1: remaining=45, server: api1 (total: 55)
    ...
    DELETE 5: remaining=5, server: api3 (total: 95)

[6] Final POST to reach limit (누적 100)
    POST 6: remaining=0, server: api1 (total: 100)

[7] EXCEEDED TEST (차단 확인)
    Response: {"detail":{"error":"Too Many Requests","message":"Token limit exceeded...","limit":100,"window":"60 seconds","server_id":"api2"}}

• 로드밸런싱 확인: server: api1 → api2 → api3 순서로 골고루 찍히는 걸 볼 수 있음.
• 정확한 차단: 100 토큰을 초과한 요청은 429 Too Many Requests 에러를 뱉음.

마무리하며

처음 유량 제어를 공부할때는 모든 요청이 동등한 가치를 전제로 서술되었다. 하지만 최근 LLM API 들은 사용량을 토큰으로 계산하는 구조를 가지고 있다. 이는 요청이 서버 리소스를 점유하는 만큼 가치를 매긴거라고 생각할 수 있다. 그래서 cost-aware rate limiting 개념을 고려하게 되었고 지금처럼 요청별 비용을 도입해보았다. 이외에도 다양한 유량 제어 알고리즘이 존재하지만 현재로썬 지금 방식이 가장 적합하다고 생각했고, 또한 lua 스크립트를 다른 언어환경에서 전달하는 방법을 알게되었다. 서버 유지보수 작업에서 lua 확장자 파일이 간혹 있었는데 이제야 어떻게 사용되는지 알게되었다.

Runpod을 사용할 때 Jupyter Notebook을 에이전트랑 같이 쓰고 싶은데, 단순 Jupyter Lab만 지원되니까 로컬 VSCode단으로 끌어오고 싶었음.

생각했던 건 Colab의 에이전트 느낌이었는데, 이건 고유 환경에서 써야 하니까 구속력이 좀 컸음.

그래서 VSCode에서 작업할 수 있는 환경을 구축했고, 이 방법을 공유하고 싶어서 작성하게 되었음.

방법

1. Runpod에서 Pod 생성하기

Pod를 생성하면 위 사진처럼 Pod가 만들어진다.
빨간색으로 강조된 부분(SSH 명령어)을 복사한다.

2. VSCode에서 Remote-SSH로 Pod 연결하기

사진은 Antigravity라는 다른 IDE인데, VSCode랑 동일한 환경임.

여기서 강조된 부분인 설정 버튼을 클릭한다.

3. SSH Config에 설정하기

방금 복사했던 값을 아래 형식으로 변환한다:

복사한 값:

ssh root@213.173.108.14 -p 11771 -i ~/.ssh/id_ed25519

변환된 값:

Host My-Remote-Server
    HostName 213.173.108.14
    User root
    Port 11771
    IdentityFile ~/.ssh/id_ed25519

이렇게 설정하면 연결 조건이 모두 기록된 상황이다.

4. 접속하기

드롭다운을 누르면 workspace 디렉터리가 나온다.
거기서 화살표 버튼을 누르면 작업 환경으로 접속할 수 있다.

4-1. 뭔가 입력해야 한다면

yes라고 입력하고 엔터를 치면 된다.

별건 아니고 SSH 처음 접속할 때 로컬에서 호스트 키 저장하려고 하는 것이다.
SSH 써본 사람은 아래 메시지를 본 적 있을 것이다:

Are you sure you want to continue connecting (yes/no/[fingerprint])?

이거랑 같은 것이다.

노트북 커널 연결하기

이제 에이전트와 작업할 수 있게 되었고, 이제는 커널을 연결해서 노트북을 써야한다.

1. 커널 상태 확인

노트북 우측 상단에서 커널 연결 상태를 확인할 수 있다.

지금은 커널 연결이 안 되어있는 상태다. Select Kernel 버튼을 클릭한다.

2. 커널 추가 메뉴 진입

클릭하면 아래와 같은 메뉴가 나온다. 여기서 Select Another Kernel...을 선택해서 커널을 추가해야 한다. 여기서 Select Another Kernel...을 선택한다.

3. Jupyter Server 주소 입력

이제 Enter the URL of the running Jupyter Server 메뉴가 나오면, 여기에 직접 URL을 입력해야 한다.

4. Runpod에서 주소 및 토큰 확인

입력할 정보를 얻기 위해 Runpod 대시보드로 이동한다. Runpod에서 'Connect to Jupyter Lab' 버튼에 우클릭 후 링크 주소 복사를 하면 URL과 토큰 정보를 얻을 수 있다.

복사된 정보 예시:

https://r9gxwzt2md23k2-8888.proxy.runpod.net/?token=8aw804df3azxxzmqc05g

여기서 필요한 정보는 다음과 같다:

• URL: https://r9gxwzt2md23k2-8888.proxy.runpod.net
• Password(token): 8aw804df3azxxzmqc05g

5. 연결 완료

VSCode 입력창에 URL을 넣고 엔터를 누른 뒤, 이어서 패스워드(토큰)를 입력하면 커널이 연결된다.

한 번 연결해두면, 이후 다른 노트북 파일을 열 때도 저장된 커널 목록에서 바로 선택하여 편하게 접근할 수 있다.

&nbsp다봉분포로 왜도가 0일 수 있는데, 이는 좌우대칭이라는 뜻이 된다. 이렇게 왜도를 대칭의 정도라고도 해석할 수 있게 되고, 왜도가 0이라고 해서 정규성 변환이 가능하다는 것은 아니다. 이를 확인하기 위해, 단봉분포와 다봉분포를 만들고, Box-Cox 변환을 적용해 봤다.

&nbsp단봉분포는 정규성 변환을 적용하면 어느 정도 보정되는 효과가 나타났지만, 다봉분포는 하나의 봉우리로 합쳐지지 않는 것을 볼 수 있다. 그리고 왜도의 해석 중 하나인 치우쳐진 정도로 중앙값, 평균, 최빈값들에 대한 해석이 불가능해지는 경우가 존재하게 된다. &nbsp그러므로 왜도의 값으로는 데이터의 분포를 정확히 파악하기 어렵다. 데이터 시각화나 추가적인 분석을 통해 데이터의 분포를 파악해야 한다.

위 문제를 여러 알고리즘으로 풀면서 익혀보자.

먼저 떠올린건 크루스칼이었다. 상대적으로 구현이 쉬우므로 먼저 구현했다.

• 크루스칼

    import java.io.*;
    import java.util.*;
  
    public class Main {
        static class Edge implements Comparable<Edge> {
            int src, dst, cost;
  
            public Edge(int _src, int _dst, int _cost) {
                src = _src;
                dst = _dst;
                cost = _cost;
            }
  
            public int compareTo(Edge e) {
                return cost - e.cost;
            }
        }
  
        static class UnionFinder {
            int[] parent;
            int[] rank;
  
            public UnionFinder(int n) {
                parent = new int[n + 1];
                rank = new int[n + 1];
                for (int i = 0; i <= n; i++) {
                    parent[i] = i;
                    rank[i] = 0;
                }
            }
  
            public int find(int x) {
                if (parent[x] != x) {
                    parent[x] = find(parent[x]);
                }
                return parent[x];
            }
  
            public void union(int x, int y) {
                int xroot = find(x);
                int yroot = find(y);
  
                if (xroot == yroot)
                    return;
  
                int cmp = compareRank(xroot, yroot);
                if (cmp < 0) {
                    parent[xroot] = yroot;
                } else if (cmp > 0) {
                    parent[yroot] = xroot;
                } else {
                    parent[yroot] = xroot;
                    rank[xroot]++;
                }
            }
  
            public int compareRank(int x, int y) {
                return rank[x] - rank[y];
            }
        }
  
        public static void main(String[] args) throws Exception {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
            int N = Integer.parseInt(br.readLine());
  
            PriorityQueue<Edge> pq = new PriorityQueue<>();
            for (int i = 0; i < N; i++) {
                int cost = Integer.parseInt(br.readLine());
                pq.add(new Edge(N, i, cost));
            }
  
            for (int i = 0; i < N; i++) {
                String[] tokens = br.readLine().split(" ");
                for (int j = i + 1; j < N; j++) {
                    pq.add(new Edge(i, j, Integer.parseInt(tokens[j])));
                }
            }
  
            int answer = 0;
            UnionFinder uf = new UnionFinder(N);
            while (!pq.isEmpty()) {
                Edge edge = pq.poll();
                int xroot = uf.find(edge.src);
                int yroot = uf.find(edge.dst);
  
                if (xroot != yroot) {
                    answer += edge.cost;
                    uf.union(xroot, yroot);
                }
            }
  
            System.out.println(answer);
        }
    }
  

단순 알고리즘 구현이 아닌, 별도의 루트노트를 가정하여 간선을 추가하는 방식으로 풀 수 있다.

또한 코드에서 간선 중심으로 작성되어있는 것을 볼 수 있다.

다음은 프림으로 풀어보자. 프림은 노드 중심이므로, 별도의 루트를 시작점으로 제시하면 된다.

• 프림

    import java.io.*;
    import java.util.*;
  
    public class Main {
        static class Edge implements Comparable<Edge> {
            int node, cost;
  
            public Edge(int _node, int _cost) {
                node = _node;
                cost = _cost;
            }
  
            public int compareTo(Edge e) {
                return cost - e.cost;
            }
        }
  
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int N = Integer.parseInt(br.readLine());
  
            List<Edge>[] graph = new ArrayList[N + 1];
            for (int i = 0; i <= N; i++) {
                graph[i] = new ArrayList<>();
            }
  
            for (int i = 1; i <= N; i++) {
                int cost = Integer.parseInt(br.readLine());
                graph[0].add(new Edge(i, cost));
                graph[i].add(new Edge(0, cost));
            }
  
            for (int i = 1; i <= N; i++) {
                String[] tokens = br.readLine().split(" ");
                for (int j = 1; j <= N; j++) {
                    int cost = Integer.parseInt(tokens[j - 1]);
                    if (i != j) {
                        graph[i].add(new Edge(j, cost));
                    }
                }
            }
  
            boolean[] visited = new boolean[N + 1];
            PriorityQueue<Edge> pq = new PriorityQueue<>();
            pq.add(new Edge(0, 0));
            int totalCost = 0;
  
            while (!pq.isEmpty()) {
                Edge curr = pq.poll();
                int node = curr.node;
                int cost = curr.cost;
  
                if (visited[node])
                    continue;
                visited[node] = true;
                totalCost += cost;
  
                for (Edge next : graph[node]) {
                    if (!visited[next.node]) {
                        pq.add(new Edge(next.node, next.cost));
                    }
                }
            }
  
            System.out.println(totalCost);
        }
    }

실전성을 떨어진다고 하지만, 배운김에 보루프카도 적용해보자.

• 보르푸카

    import java.io.*;
    import java.util.*;
  
    public class Main {
        static class Edge {
            int src, dst, cost;
  
            public Edge(int _src, int _dst, int _cost) {
                src = _src;
                dst = _dst;
                cost = _cost;
            }
        }
  
        static class Boruvka {
            int[] parent;
  
            public Boruvka(int n) {
                parent = new int[n + 1];
                for (int i = 0; i <= n; i++) {
                    parent[i] = i;
                }
            }
  
            public int find(int x) {
                if (parent[x] != x) {
                    parent[x] = find(parent[x]);
                }
                return parent[x];
            }
  
            public boolean union(int x, int y) {
                int xroot = find(x);
                int yroot = find(y);
  
                if (xroot == yroot)
                    return false;
                parent[yroot] = xroot;
                return true;
            }
        }
  
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int N = Integer.parseInt(br.readLine());
  
            List<Edge> edges = new ArrayList();
  
            for (int i = 1; i <= N; i++) {
                int cost = Integer.parseInt(br.readLine());
                edges.add(new Edge(0, i, cost));
            }
  
            for (int i = 1; i <= N; i++) {
                String[] tokens = br.readLine().split(" ");
                for (int j = 1; j <= N; j++) {
                    if (i != j) {
                        int cost = Integer.parseInt(tokens[j - 1]);
                        edges.add(new Edge(i, j, cost));
                    }
                }
            }
  
            int tot = 0;
            Boruvka bv = new Boruvka(N);
            int components = N + 1;
  
            while (components > 1) {
                Edge[] minEdge = new Edge[N + 1];
  
                for (Edge e : edges) {
                    int u = bv.find(e.src);
                    int v = bv.find(e.dst);
  
                    if (u == v)
                        continue;
  
                    if (minEdge[u] == null || minEdge[u].cost > e.cost) {
                        minEdge[u] = e;
                    }
                    if (minEdge[v] == null || minEdge[v].cost > e.cost) {
                        minEdge[v] = e;
                    }
                }
  
                for (int i = 0; i <= N; i++) {
                    Edge e = minEdge[i];
                    if (e != null && bv.union(e.src, e.dst)) {
                        tot += e.cost;
                        components--;
                    }
                }
            }
  
            System.out.println(tot);
        }
    }
  

세 알고리즘의 결과는 위에서 부터 보르푸카, 프림, 크루스칼의 순서로 아래와 같이 나타난다.

보르푸카의 실전성은 떨어지지만 성능적인 면에서 우수한 점이 돋보인다고 할 수 있다.

&nbsp이 개념은 통신망 구축, 도로 건설, 전력망 설계 처럼, 각 지점을 연결하는 비용이나 자원을 최소화하는 문제에 활용된다.

&nbsp문제의 특성에 따라, 크루스칼(Kruskal), 프림(Prim), 보루프카(Borůvka) 등의 알고리즘 등으로 효율적으로 최적화할 수 있다.

&nbsp크루스칼 알고리즘은 모든 간선을 비용 순으로 정렬한 뒤, 가장 작은 비용의 간선부터 하나씩 연결해 나가면서 사이클이 생기지 않을때만 트리에 추가하는 방식이다. 이때 사이클 검사는 유니온 파인드 자료구조를 통해 처리되며, 전체 시간 복잡도는 간선의 정렬에 걸리는 O(E * log E)로 측정된다. 즉, 간선 수가 많지 않은(희소한) 그래프에서 적절하며, 구현기 직관적이고 간결하다는 장점이 있다.

• 코드

    import java.util.*;
  
    class Edge implements Comparable<Edge> {
        int src, dest, weight;
  
        public Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
  
        public int compareTo(Edge other) {
            return this.weight - other.weight;
        }
    }
  
    class Graph {
        int V, E;
        Edge[] edges;
  
        public Graph(int V, int E) {
            this.V = V;
            this.E = E;
            edges = new Edge[E];
        }
    }
  
    class DisjointSet {
        int[] parent;
        int[] rank;
  
        public DisjointSet(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }
  
        public int find(int x) {
            if (parent[x] != x)
                parent[x] = find(parent[x]);
            return parent[x];
        }
  
        // union 메서드: rank 비교를 별도의 compareRank 함수를 사용
        public void union(int x, int y) {
            int xroot = find(x);
            int yroot = find(y);
            if (xroot == yroot) return;
  
            if (compareRank(xroot, yroot) < 0) {
                parent[xroot] = yroot;
            } else if (compareRank(xroot, yroot) > 0) {
                parent[yroot] = xroot;
            } else {
                parent[yroot] = xroot;
                rank[xroot]++;
            }
        }
  
        // 두 집합의 rank를 비교하는 별도의 함수
        public int compareRank(int x, int y) {
            return Integer.compare(rank[x], rank[y]);
        }
    }
  
    public class KruskalMST {
  
        public static List<Edge> kruskalMST(Graph graph) {
            List<Edge> result = new ArrayList<>();
            // 모든 간선을 가중치 순으로 정렬
            Arrays.sort(graph.edges);
  
            DisjointSet ds = new DisjointSet(graph.V);
  
            // 간선 하나씩 선택하며 사이클이 형성되지 않을 경우 MST에 추가
            for (Edge edge : graph.edges) {
                int x = ds.find(edge.src);
                int y = ds.find(edge.dest);
  
                if (x != y) {
                    result.add(edge);
                    ds.union(x, y);
                }
            }
            return result;
        }
  
        public static void main(String[] args) {
            int V = 4, E = 5;
            Graph graph = new Graph(V, E);
  
            // 간선 추가 (예제: 0-1:10, 0-2:6, 0-3:5, 1-3:15, 2-3:4)
            graph.edges[0] = new Edge(0, 1, 10);
            graph.edges[1] = new Edge(0, 2, 6);
            graph.edges[2] = new Edge(0, 3, 5);
            graph.edges[3] = new Edge(1, 3, 15);
            graph.edges[4] = new Edge(2, 3, 4);
  
            List<Edge> mst = kruskalMST(graph);
            System.out.println("Kruskal MST:");
            for (Edge e : mst) {
                System.out.println(e.src + " -- " + e.dest + " == " + e.weight);
            }
        }
    }
  

&nbsp프림 알고리즘은 한 정점에서 출발해 현재 트리에 연결된 정점과 인접한 간선 중 비용이 가장 작은 것을 선택해 확장하는 방식이다. 노드별 우선순위 큐를 사용해 다음 선택 간선을 관리하며, 시간 복잡도는 인접 리스트 기반으로 구현하면 O(E + Vlog V)가 된다. 노드별 간선의 우선도를 기반으로 하기 때문에 간선의 밀도가 높은 그래프에서 더 효율적이다. 알고리즘 특성상 정점을 특정하기 때문에 한 지점에서 최소 연결망을 찾을 때 유리하다.

• 코드

    import java.util.*;
  
    class Pair implements Comparable<Pair> {
        int vertex, key;
  
        public Pair(int vertex, int key) {
            this.vertex = vertex;
            this.key = key;
        }
  
        public int compareTo(Pair other) {
            return this.key - other.key;
        }
    }
  
    public class PrimMST {
  
        public static void primMST(List<List<Pair>> adj, int V) {
            boolean[] inMST = new boolean[V];
            int[] key = new int[V];
            int[] parent = new int[V];
            Arrays.fill(key, Integer.MAX_VALUE);
  
            PriorityQueue<Pair> pq = new PriorityQueue<>();
            key[0] = 0;
            parent[0] = -1;
            pq.add(new Pair(0, key[0]));
  
            while (!pq.isEmpty()) {
                int u = pq.poll().vertex;
                inMST[u] = true;
  
                for (Pair neighbor : adj.get(u)) {
                    int v = neighbor.vertex;
                    int weight = neighbor.key;
                    if (!inMST[v] && weight < key[v]) {
                        key[v] = weight;
                        parent[v] = u;
                        pq.add(new Pair(v, key[v]));
                    }
                }
            }
  
            System.out.println("Prim MST:");
            for (int i = 1; i < V; i++) {
                System.out.println(parent[i] + " - " + i + " : " + key[i]);
            }
        }
  
        // 무방향 그래프의 간선 추가: 양쪽에 추가
        public static void addEdge(List<List<Pair>> adj, int u, int v, int w) {
            adj.get(u).add(new Pair(v, w));
            adj.get(v).add(new Pair(u, w));
        }
  
        public static void main(String[] args) {
            int V = 5;
            List<List<Pair>> adj = new ArrayList<>();
            for (int i = 0; i < V; i++) {
                adj.add(new ArrayList<>());
            }
  
            // 예제 그래프 간선 추가
            addEdge(adj, 0, 1, 2);
            addEdge(adj, 0, 3, 6);
            addEdge(adj, 1, 2, 3);
            addEdge(adj, 1, 3, 8);
            addEdge(adj, 1, 4, 5);
            addEdge(adj, 2, 4, 7);
            addEdge(adj, 3, 4, 9);
  
            primMST(adj, V);
        }
    }
  

&nbsp보루프카 알고리즘은 각 노드(컴포넌트)가 자신과 연결된 가장 낮은 비용 간선을 동시에 선택해 병합하는 과정을 반복한다. 크루스칼과 프림의 방식이 섞여있다고 생각할 수 있다. 각 노드가 동시에 선택하기 때문에, 병렬 처리가 가능하다. 전체 복잡도는 O(E log V)이다. 대규모 분산 시스템이나 외부 메모리 환경에서 활용 가치가 높다. 솔린(Sollin)이라는 사람이 보루프카 이후에 알고리즘을 다시 소개하면서 솔린 알고리즘이라고도 불린다.

• 코드

    import java.util.*;
  
    class BoruvkaEdge {
        int src, dst, weight;
  
        public BoruvkaEdge(int _src, int _dst, int _weight) {
            src = _src;
            dst = _dst;
            weight = _weight;
        }
    }
  
    public class BoruvkaMST {
        static class Subset {
            int parent, rank;
  
            public Subset(int _parent, int _rank) {
                parent = _parent;
                rank = _rank;
            }
        }
  
        public static int boruvkaMST(List<BoruvkaEdge> edges, int V) {
            // 각 정점을 독립적인 컴포넌트로 취급
            Subset[] subsets = new Subset[V];
            for (int i = 0; i < V; i++) {
                subsets[i] = new Subset(i, 0);
            }
  
            int numTrees = V;
            int MSTweight = 0;
            // 각 컴포넌트에서 선택된 최소 간선을 저장할 배열
            BoruvkaEdge[] cheapest = new BoruvkaEdge[V];
  
            while (numTrees > 1) {
                Arrays.fill(cheapest, null);
  
                // 모든 간선을 순회하며 각 컴포넌트별 최소 간선을 갱신
                for (BoruvkaEdge edge : edges) {
                    // 각 컴포넌트의 부모를 찾
                    int set1 = find(subsets, edge.src);
                    int set2 = find(subsets, edge.dst);
  
                    if (set1 == set2)
                        continue;
  
                    if (cheapest[set1] == null || cheapest[set1].weight > edge.weight) {
                        cheapest[set1] = edge;
                    }
                    if (cheapest[set2] == null || cheapest[set2].weight > edge.weight) {
                        cheapest[set2] = edge;
                    }
                }
  
                // 각 컴포넌트의 최소 간선을 MST에 추가
                for (int i = 0; i < V; i++) {
                    if (cheapest[i] != null) {
                        BoruvkaEdge edge = cheapest[i];
                        int set1 = find(subsets, edge.src);
                        int set2 = find(subsets, edge.dst);
  
                        if (set1 == set2)
                            continue;
  
                        MSTweight += edge.weight;
                        union(subsets, set1, set2);
                        System.out.println("Edge " + edge.src + " - " + edge.dst + " added with weight " + edge.weight);
                        numTrees--;
                    }
                }
            }
            System.out.println("Boruvka MST Weight: " + MSTweight);
            return MSTweight;
        }
  
        // 컴포넌트의 부모 찾기 + 경로 압축
        public static int find(Subset[] subsets, int i) {
            if (subsets[i].parent != i) {
                subsets[i].parent = find(subsets, subsets[i].parent);
            }
            return subsets[i].parent;
        }
  
        private static int compareRank(Subset[] subsets, int xRoot, int yRoot) {
            return Integer.compare(subsets[xRoot].rank, subsets[yRoot].rank);
        }
  
        public static void union(Subset[] subsets, int x, int y) {
            int xRoot = find(subsets, x);
            int yRoot = find(subsets, y);
            if (xRoot == yRoot)
                return;
  
            int cmp = compareRank(subsets, xRoot, yRoot);
            if (cmp < 0) {
                subsets[xRoot].parent = yRoot;
            } else if (cmp > 0) {
                subsets[yRoot].parent = xRoot;
            } else {
                subsets[yRoot].parent = xRoot;
                subsets[xRoot].rank++;
            }
        }
  
        public static void main(String[] args) {
            int V = 4;
            List<BoruvkaEdge> edges = new ArrayList<>();
            // 예제 간선 추가 (예: 0-1:10, 0-2:6, 0-3:5, 1-3:15, 2-3:4)
            edges.add(new BoruvkaEdge(0, 1, 10));
            edges.add(new BoruvkaEdge(0, 2, 6));
            edges.add(new BoruvkaEdge(0, 3, 5));
            edges.add(new BoruvkaEdge(1, 3, 15));
            edges.add(new BoruvkaEdge(2, 3, 4));
  
            boruvkaMST(edges, V);
        }
    }
  

&nbsp각 알고리즘은 탐색 기준, 자료 구조, 복잡도, 그래프 밀도 등에 따라 아래와 같이 정리할 수 있다.

&nbsp자 그럼, 상황마다 최적의 알고리즘을 알게되었다. 크루스칼은 간선이 적을때 유리하고, 프림은 간선 밀도가 높을때 유리하고, 보루프카는 병렬 작업에 유리하다. 이를 검증하기 위한 테스트 파일을 작성하고 결과를 비교해보자. 실행 시간 평균과 표준편차, 힙 메모리 사용량을 측정할 것이다. 실험 환경은 노드 수, 간선 수, 직/병렬 여부에 따라 측정되었다. 프림의 경우 노드관점 탐색이므로 병렬 측정은 제외했다. 다용도 환경에서 작성되었으므로 측정이 불안정할 수 있다.

• 코드(GPT로 작성되어 잘못된 정보가 있을 수 있음)

    import java.util.*;
    import java.util.concurrent.atomic.*;
  
    public class MSTBenchmark {
  
        // JVM 실행 시 아래 옵션을 사용하세요.
        // java -Xms4g -Xmx4g -XX:+UseG1GC MSTBenchmarkOptimized
  
        static class Edge implements Comparable<Edge> {
            int u, v, w;
            Edge(int u, int v, int w) { 
                this.u = u; 
                this.v = v; 
                this.w = w; 
            }
            public int compareTo(Edge o) { 
                return this.w - o.w; 
            }
        }
  
        static class UnionFind {
            int[] parent, rank;
            UnionFind(int n) {
                parent = new int[n];
                rank = new int[n];
                for (int i = 0; i < n; i++) 
                    parent[i] = i;
            }
            int find(int x) { 
                return parent[x] == x ? x : (parent[x] = find(parent[x])); 
            }
            void union(int a, int b) {
                a = find(a); 
                b = find(b);
                if (a == b) return;
                if (rank[a] < rank[b]) 
                    parent[a] = b;
                else if (rank[a] > rank[b]) 
                    parent[b] = a;
                else {
                    parent[b] = a; 
                    rank[a]++;
                }
            }
        }
  
        // 간선 리스트를 만들 때, 초기 용량을 E로 설정하여 내부 배열 재할당을 피함.
        static List<Edge> genEdges(int V, int E) {
            Random rnd = new Random(0);
            List<Edge> edges = new ArrayList<>(E);
            for (int i = 0; i < E; i++) {
                int u = rnd.nextInt(V), v = rnd.nextInt(V), w = rnd.nextInt(1000) + 1;
                if (u != v)
                    edges.add(new Edge(u, v, w));
            }
            return edges;
        }
  
        static long kruskalSingle(List<Edge> edges, int V) {
            Collections.sort(edges);
            UnionFind uf = new UnionFind(V);
            for (Edge e : edges)
                if (uf.find(e.u) != uf.find(e.v))
                    uf.union(e.u, e.v);
            return 0;
        }
  
        static long kruskalParallel(List<Edge> edges, int V) {
            Edge[] arr = edges.toArray(new Edge[0]);
            Arrays.parallelSort(arr);
            UnionFind uf = new UnionFind(V);
            for (Edge e : arr)
                if (uf.find(e.u) != uf.find(e.v))
                    uf.union(e.u, e.v);
            return 0;
        }
  
        // Prim: 각 정점의 인접 간선 리스트를 만들 때, 예상 간선 수 = (E * 2)/V 로 초기 용량 설정
        static long prim(List<Edge> edges, int V, int E) {
            int expectedEdgeCount = Math.max(4, (E * 2) / V);
            List<List<int[]>> adj = new ArrayList<>(V);
            for (int i = 0; i < V; i++)
                adj.add(new ArrayList<>(expectedEdgeCount));
            for (Edge e : edges) {
                adj.get(e.u).add(new int[]{e.v, e.w});
                adj.get(e.v).add(new int[]{e.u, e.w});
            }
            boolean[] used = new boolean[V];
            int[] dist = new int[V];
            Arrays.fill(dist, Integer.MAX_VALUE);
            dist[0] = 0;
            // PriorityQueue의 초기 용량을 V로 설정
            PriorityQueue<int[]> pq = new PriorityQueue<>(V, Comparator.comparingInt(a -> a[1]));
            pq.add(new int[]{0, 0});
            while (!pq.isEmpty()) {
                int u = pq.poll()[0];
                if (used[u]) continue;
                used[u] = true;
                for (int[] nei : adj.get(u)) {
                    if (!used[nei[0]] && nei[1] < dist[nei[0]]) {
                        dist[nei[0]] = nei[1];
                        pq.add(new int[]{nei[0], nei[1]});
                    }
                }
            }
            return 0;
        }
  
        static long boruvkaSingle(List<Edge> edges, int V) {
            UnionFind uf = new UnionFind(V);
            int components = V;
            while (components > 1) {
                Edge[] cheapest = new Edge[V];
                for (Edge e : edges) {
                    int u = uf.find(e.u), v = uf.find(e.v);
                    if (u != v) {
                        if (cheapest[u] == null || e.w < cheapest[u].w)
                            cheapest[u] = e;
                        if (cheapest[v] == null || e.w < cheapest[v].w)
                            cheapest[v] = e;
                    }
                }
                for (Edge e : cheapest) {
                    if (e != null) {
                        int u = uf.find(e.u), v = uf.find(e.v);
                        if (u != v) { uf.union(u, v); components--; }
                    }
                }
            }
            return 0;
        }
  
        static long boruvkaParallel(List<Edge> edges, int V) {
            UnionFind uf = new UnionFind(V);
            int components = V;
            while (components > 1) {
                @SuppressWarnings("unchecked")
                AtomicReference<Edge>[] cheapest = new AtomicReference[V];
                for (int i = 0; i < V; i++) 
                    cheapest[i] = new AtomicReference<>();
                edges.parallelStream().forEach(e -> {
                    int u = uf.find(e.u), v = uf.find(e.v);
                    if (u != v) {
                        cheapest[u].updateAndGet(cur -> cur == null || e.w < cur.w ? e : cur);
                        cheapest[v].updateAndGet(cur -> cur == null || e.w < cur.w ? e : cur);
                    }
                });
                for (AtomicReference<Edge> ref : cheapest) {
                    Edge e = ref.get();
                    if (e != null) {
                        int u = uf.find(e.u), v = uf.find(e.v);
                        if (u != v) { uf.union(u, v); components--; }
                    }
                }
            }
            return 0;
        }
  
        // 메모리 사용량과 실행 시간을 측정하는 메서드
        static void runAndRecord(String name, Runnable task, List<Long> times, List<Double> mems) {
            System.gc();
            // 현재 힙 사용량 (바이트 단위)
            long beforeMem = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
            long start = System.nanoTime();
            task.run();
            long elapsed = (System.nanoTime() - start) / 1_000_000; // ms 단위
            long afterMem = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
            times.add(elapsed);
            mems.add((afterMem - beforeMem) / (1024.0 * 1024.0)); // MB 단위
        }
  
        static void benchmark(int V, int E, int runs) {
            // 간선 리스트를 생성할 때 예상 용량을 지정
            List<Edge> base = genEdges(V, E);
            Map<String, List<Long>> times = new LinkedHashMap<>();
            Map<String, List<Double>> mems = new LinkedHashMap<>();
            String[] algos = { "Kruskal(single)", "Kruskal(parallel)", "Prim(single)" };
            for (String a : algos) {
                times.put(a, new ArrayList<>());
                mems.put(a, new ArrayList<>());
            }
            if (E <= 200_000) {
                times.put("Boruvka(single)", new ArrayList<>());
                mems.put("Boruvka(single)", new ArrayList<>());
                times.put("Boruvka(parallel)", new ArrayList<>());
                mems.put("Boruvka(parallel)", new ArrayList<>());
            }
  
            for (int i = 0; i < runs; i++) {
                // 매 실행마다 동일한 간선 리스트의 복사본 사용
                List<Edge> copy = new ArrayList<>(base);
                runAndRecord("Kruskal(single)", () -> kruskalSingle(new ArrayList<>(copy), V), times.get("Kruskal(single)"), mems.get("Kruskal(single)"));
                runAndRecord("Kruskal(parallel)", () -> kruskalParallel(new ArrayList<>(copy), V), times.get("Kruskal(parallel)"), mems.get("Kruskal(parallel)"));
                runAndRecord("Prim(single)", () -> prim(new ArrayList<>(copy), V, E), times.get("Prim(single)"), mems.get("Prim(single)"));
                if (E <= 200_000) {
                    runAndRecord("Boruvka(single)", () -> boruvkaSingle(new ArrayList<>(copy), V), times.get("Boruvka(single)"), mems.get("Boruvka(single)"));
                    runAndRecord("Boruvka(parallel)", () -> boruvkaParallel(new ArrayList<>(copy), V), times.get("Boruvka(parallel)"), mems.get("Boruvka(parallel)"));
                }
            }
  
            System.out.printf("Config: V=%d, E=%d, Runs=%d%n", V, E, runs);
            times.keySet().forEach(name -> {
                double avgTime = times.get(name).stream().mapToLong(x -> x).average().orElse(0);
                double stdTime = Math.sqrt(times.get(name).stream().mapToDouble(x -> Math.pow(x - avgTime, 2)).sum() / runs);
                double avgMem = mems.get(name).stream().mapToDouble(x -> x).average().orElse(0);
                double stdMem = Math.sqrt(mems.get(name).stream().mapToDouble(x -> Math.pow(x - avgMem, 2)).sum() / runs);
                System.out.printf("%-20s: time=%.2f±%.2f ms, mem=%.2f±%.2f MB%n", name, avgTime, stdTime, avgMem, stdMem);
            });
            System.out.println();
        }
  
        public static void main(String[] args) {
            int V = 2000, runs = 5;
            int[][] configs = { { V, 5 * V }, { V, 20 * V }, { V, 100 * V } };
            for (int[] cfg : configs) {
                benchmark(cfg[0], cfg[1], runs);
            }
        }
    }
  

MST 알고리즘 벤치마크 결과 (V=2000, Runs=5)

&nbsp단일 버전 크루스칼은 메모리 사용이 일관되게 낮지만 조밀해질수록 시간 증가폭이 커져 대규모 그래프에서 느린 편이다. 병렬 버전은 고밀도에서 평균 실행시간이 개선되나 표준편차가 매우 커 안정성이 떨어지며 메모리 소비도 크게 늘어난다.

&nbsp프림은 모든 밀도에서 실행시간이 안정적이고 빠르며, 특히 중간 밀도에서 최저 시간을 기록했다. 하지만 높은 밀도에서 메모리 사용량이 크게 증가해 메모리 예산이 고려된다.

&nbsp단일 버전 보르푸카는 실행 시간과 메모리 모두 일관되게 낮아 가장 안정적이면서 빠른 성능을 나타낸다. 병렬 버전은 오버헤드로 희소 구간에서는 성능저하가 나탄나지만, 중-고밀도 구간에서 단일 버전 대비 약간의 시간 이득을 보지만 메모리 사용량이 급증하는 부하가 있다.

&nbsp정리하자면, 조밀한 그래프에서는 프림이 최고이며, 전체적으로 일관된 성능은 단일 보르푸카를 선택하는 것이 좋다. 병렬 크루스칼은 고밀도 작업에서는 고려할 수 있겠지만, 변동성이 크므로 조심해서 써야 한다.

&nbsp최근 삼성 B형 테스트를 준비하면서 레퍼런스를 찾고 있다. 매우 유익한 자료들이 많았지만 C++로 되어있어 일부 내용은 그대로 적용할 수 없었다. 그 중 하나가 디버깅 이었고, 이를 Java 만의 방식으로 바꿔보도록 하자.

C++ 레퍼런스 : 링크

1. 테스트 케이스 오류 원인 점검

테스트 케이스의 일부만 통과한다면, 대부분 변수나 배열의 초기화 문제다.

Java는 배열은 기본값으로 초기화되지만, 로컬 변수는 명시적 초기화가 필요하다.

사용하는 모든 변수와 배열을 꼼꼼히 초기화하는지 확인해보자.

int pool;
Node[] nodes = new Node[MAX_NODES]; // 테스트끼리 공유됨

void init() {
    pool = 0; // 하나의 클래스에서 여러번 사용될 경우 초기화 필요

    for (int i = 0; i < MAX_NODES; i++) {
        // 각 node의 초기화가 필요할 수도 있음
    }
}

2. 출력 결과 파일로 리다이렉션해 디버깅하기

테스트 케이스가 많거나 콘솔 출력이 과도할 때, 출력 내용을 파일에 저장하면 문제 파악이 쉬워진다.

Java에서는 System.setOut()을 활용해 출력 스트림을 파일로 전환할 수 있다.

구현한 코드의 답을 출력하면 비교할 때 편하다.

try {
    // 출력 스트림을 output.txt 파일로 설정
    PrintStream fileOut = new PrintStream(new FileOutputStream("res/output.txt"));
    System.setOut(fileOut);
} catch (FileNotFoundException e) {
    e.printStackTrace();
}

3. 프로그램 강제 종료로 중간 상태 확인하기

복잡한 구현 중 특정 부분까지만 실행하고 상태를 확인하고 싶을때, 프로그램 자체를 종료해보자.

Java에서는 System.exit(0)를 사용해 프로그램을 강제로 종료할 수 있다.

public static void function() {
  System.out.println("여기까지 실행됨. 프로그램 종료.");
  System.exit(0);
  // 아래 코드는 실행되지 않음
}

4. 추가 테스트 케이스로 성능과 안정성 확인하기

기존 테스트 케이스 외에도, 데이터를 직접 생성해 시간과 메모리 초과를 점검해볼 수 있다.

1. System.out.println의 동작 구조

System.out.println("hello world");

위 코드는 단순한 출력 코드이지만, 내부 동작을 깊이 파고들어 보자.

// PrintStream.java
public void println(String x) {  
    if (getClass() == PrintStream.class) {  
        writeln(String.valueOf(x));  
    } else {  
        synchronized (this) {  
            print(x);  
            newLine();  
        }  
    }  
}

System.out.println()은 PrintStream의 println() 메서드를 통해 출력된다. 상속 여부를 체크한 후, 내부적으로 writeln()을 호출한다.

// PrintStream.java
private void writeln(String s) {  
    try {  
        synchronized (this) {  
            ensureOpen();  
            textOut.write(s);  
            textOut.newLine();  
            textOut.flushBuffer();  // 즉시 플러시 발생
            charOut.flushBuffer();  
            if (autoFlush)  
                out.flush();  
        }  
    } catch (IOException x) {  
        trouble = true;  
    }  
}

System.out.print는 즉시 출력이 이루어지도록 flushBuffer()를 호출하여 I/O 호출이 자주 발생하게 된다.

2. BufferedWriter의 동작 방식

// BufferedWriter.java
public void write(char cbuf[], int off, int len) throws IOException {  
    synchronized (lock) {  
        ensureOpen();  
        if (len >= nChars) {  
            flushBuffer();  
            out.write(cbuf, off, len);  
            return;  
        }  
        int b = off, t = off + len;  
        while (b < t) {  
            int d = Math.min(nChars - nextChar, t - b);  
            System.arraycopy(cbuf, b, cb, nextChar, d);  
            b += d;  
            nextChar += d;  
            if (nextChar >= nChars)  
                flushBuffer();  
        }  
    }  
}

BufferedWriter는 버퍼(기본 8192바이트)를 사용하여 일정 크기 이상이 되면 한 번에 출력하기 때문에 I/O 호출 횟수가 줄어들어 성능이 향상된다.

3. 성능 비교 실험

import java.io.*;

public class PrintVsBufferedWriter {
    public static void main(String[] args) throws IOException {
        int N = 8192 * 10; // 출력 횟수  

        // System.out.print 사용  
        long start1 = System.currentTimeMillis();  
        for (int i = 0; i < N; i++) {  
            System.out.print(i + " ");  // 즉시 출력됨  
        }  
        long end1 = System.currentTimeMillis();  
        long printTime = end1 - start1;  // 실행 시간 저장  

        // BufferedWriter 사용  
        long start2 = System.currentTimeMillis();  
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));  
        for (int i = 0; i < N; i++) {  
            bw.write(i + " ");  // 버퍼에 저장됨  
        }  
        bw.flush();  // 최종 출력  
        long end2 = System.currentTimeMillis();  
        long bufferedTime = end2 - start2;  // 실행 시간 저장  

        // 최종 결과 비교 출력  
        System.out.println("\n===== 성능 비교 결과 =====");  
        System.out.println("System.out.print 실행 시간: " + printTime + "ms");  
        System.out.println("BufferedWriter 실행 시간: " + bufferedTime + "ms");  
        System.out.println("=========================");  

        bw.close();  
    }
}

** 실행 결과 (환경에 따라 다를 수 있음)**

===== 성능 비교 결과 =====
System.out.print 실행 시간: 325ms
BufferedWriter 실행 시간: 22ms
=========================

4. 결론

결론

• System.out.print는 즉시 플러시(flush)되므로, 한 글자라도 출력할 때마다 OS에 요청을 보냄 → 성능 저하.
• BufferedWriter는 버퍼를 사용하여 일정 크기 이상이 될 때만 출력 → I/O 요청 횟수가 줄어들어 성능이 크게 향상됨.
• 코딩 테스트에서 대량의 출력을 처리할 때는 반드시 **BufferedWriter를 사용해야 함.**

1. 익명 클래스(Anonymous Class)로 정의하기

Java 8 이전 버전에서 주로 사용되던 방식이다. 익명 클래스를 통해 Comparator를 정의한다.

숫자형

Comparator<Integer> comparator = new Comparator<Integer>() {
    @Override
    public int compare(Integer key1, Integer key2) {
        // 오름차순
        return key1 - key2;

        // 내림차순
        // return key2 - key1;
    }

문자열

Comparator<String> stringComparator = new Comparator<String>() {
    @Override
    public int compare(String str1, String str2) {
        // 알파벳 순서 (오름차순)
        return str1.compareto(str2);

        // 알파벳 역순 (내림차순)
        //return str2.compareTo(str1);
    }
}

2. 람다 표현식(Lambda Expression)으로 정의하기

Java 8 이상에서는 람다 표현식을 활용하여 정의할 수 있다.

수치형

// 내림차순 정렬
TreeMap<Integer, String> treeMapDesc = new TreeMap<>((key1, key2) -> key2 - key1);
// 오름차순 정렬
TreeMap<Integer, String> treeMapAsc = new TreeMap<>((key1, key2) -> key1 - key2);

문자열

// 알파벳 역순 정렬
TreeMap<String, Integer> stringTreeMapDesc new TreeMap((str1, str) -> str2.compareTo(str1));
// 알파벳 순서 정렬
TreeMap<String, Integer> stringTreeMapAsc new TreeMap((str1, str) -> str1.compareTo(str2));

3. 직접 Comparator 클래스 정의하기

Comparator는 인터페이스다. 그러므로 직접 구현해서 정의하는 방식이 있다.

숫자형

class DescendingComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer key1, Integer key2) {
        // 오름차순
        // return key1 - key2;

        // 내림차순
        return key2 - key1;
    }

문자열

class StringDescendingComparator implements Comparator<String> {
    @Override
    public int compare(String str1, String str2) {
        // 알파벳 역순 정렬
        return str2.compareTo(str1);
    }
}

개발 공부를 하면서 오픈소스에 대해서 호기심이 생겼다. 오픈소스에 기여하는 게 어떻게 하는 건지 궁금했고, 이리저리 찾아봤다. 컨트리뷰트 유형들이 존재했었는데, 요약하면 프로젝트가 발전할 수 있게 하는 모든 활동을 컨트리뷰션이라고 하는 것 같다.

솔직히 개발 공부하면서 문서 수정을 가볍게 보는 것은 아니지만, 코딩을 통해 기여하는 것이 더 와닿았다. 내가 기여하고 또 기여할 수 있는 프로젝트는 다음 조건으로 결정했다.

1. 나의 스택과 관련 있는가(Java, Python, 백엔드 등)
2. 프로젝트에 대한 지식이 부족해도 충분히 기여할 수 있는가

깃헙에서 good-first-issue라는 태그로 검색하면 기여할 만한 프로젝트들을 찾을 수 있었다. 그런데 대부분 자기들끼리만 통하는 얘기를 하는 것 같다. 프로젝트 도메인 지식이 부족하다면 기여하기 어려운 것들이 대부분이었다.

그러던 중 두 가지 이슈를 찾을 수 있었다.

첫 번째 이슈

JUnit4에서 JUnit5로 미그레이션하는 이슈이다.

이슈의 특징

1. 메인테이너(프로젝트 주도자)가 제기한 이슈
2. 나의 스택에 도움이 됨
3. 심지어 테스트 커버리지가 넓음
4. Assigner가 테스트 몇 개 깔짝거리고 더 작업한 게 없음
5. 신뢰감 느껴지는 인도 출신 구글 개발자의 프로젝트임
6. Star 수가 많다.

하지만 패스한 이유

1. 코멘트 남기니 작업 중이라고 다른 이슈로 넘김
2. 의료 데이터 웨어하우스 관련 주제인데 위키에서도 환경설정 가이드라인이 부족했음
3. 리눅스 + Maven 환경이라 IntelliJ에서 동작시키기 어려웠음

두 번째 이슈

이미지 파일의 메타데이터를 추출하는 과정에서 에러 핸들링 이슈이다.

이슈의 특징

1. 메인테이너가 이슈를 확인함
2. 프로젝트가 친절하게 알려줌
3. 생각보다 개선점이 많아 보임(내가 기여할 수 있는 파이가 있음)
4. MS 개발자임
5. Star 수가 훨씬 많다.

작업하기로 결정한 이유

이런 이유들로 작업하기로 결정했고, 코멘트를 남기기 위해 이슈를 조사했다.

작업 과정

1. 문제 상황 재현

   • 프로젝트를 fork해서 문제 상황을 재현해서 같은 에러가 발생하는 것을 확인했다.

2. 왜 문제인가

   • 실제로 HxD를 통해 바이너리 까서 확인함
   • 이미지 파일의 일부 정보가 깨져서 발생했음.
   • 예를 들면, 설명 태그를 파싱하는 부분이 0xFF로 도배되었음.
   • 그런데 해당 에러를 핸들링하지 않아서 원래 의도(넘기기)를 벗어남
   • 찾아보니 해당 부분에서 적절한 throw가 이루어지지 않았음

case ICC_TAG_TYPE_DESC:
    int stringLength = reader.getInt32(8);
    return new String(bytes, 12, stringLength - 1);

• String 객체에서 parsing 하는 과정에서 발생한 에러는 별도로 의도되지 않았고, 별도의 처리가 없었던 거임

3. 그럼 어쩌지?
   • 일단 물어보자.

요약하면 별도로 throw하지 않아서 발생한 것이다. 그래서 문제 상황을 공유했고, 답변은 BufferBoundsException를 발생시키라는 것이었다.

작업 후 피드백 반영 및 PR

• 이렇게 하면 되냐고 예시를 작성해서 물어봤고, 답변으로는 BufferBoundsException를 활용하고, 길이가 0인 경우도 정상으로 처리하라는 피드백을 받았다.
• 확인해보니까 대체할 수 있는 메서드가 있어서 다시 수정했다.
• 마지막 답변으로는 작성한 거 PR해보라는 답변을 받았고, 바로 작성했다.

결과

다행히 merge되었다.

소감

이 프로젝트가 초보자가 하기에 정말 좋은 것 같은데, 영향력이 있어서 가성비 넘치는 기여라고 생각된다. 또한 도메인 지식도 개발자라면 충분히 해결할 수 있는 범위이고, 문제 해결을 위한 레퍼런스를 찾는 과정과 소통하는 과정을 경험할 수 있어서 매우 좋았다.

처음 하기 좋은 이슈라는 태그에 충분히 걸맞았다. 이번 이슈에서 끝나지 않고 새로 생긴 이슈에도 메인테이너 대신 피드백을 줄 수 있었다.

이걸 하고 나니 문제를 해결하기 위한 접근법이 발전되는 게 느껴졌다. 좋은 동기부여가 되었고, 지속적으로 이 프로젝트에 기여할 것이다.

문제 링크

문제 요약

수열에서 두 개의 수를 골라 N회 변경해서 최대값을 만들자.

문제 풀이

DFS로 모든 경우를 시도한다. 이미 시도한 경우를 저장해서 중복된 접근을 생략한다.

DFS(N^2)

def swap(a, b):
    return b, a


def arr_to_int(arr):
    return int("".join(arr))


def dfs(arr, remain):
    global answer
    if remain == 0:
        num = arr_to_int(arr)
        answer = max(answer, num)
        return

    for i in range(len(arr) - 1):
        for j in range(i + 1, len(arr)):
            arr[i], arr[j] = swap(arr[i], arr[j])

            num = arr_to_int(arr)
            if num not in save[remain]:
                dfs(arr, remain - 1)
                save[remain].add(num)

            arr[i], arr[j] = swap(arr[i], arr[j])


T = int(input())
for test_case in range(1, T + 1):
    global answer
    answer = 0
    arr, count = input().split()
    arr = list(arr)
    count = int(count)
    save = {k: set() for k in range(count+1)}

    dfs(arr, count)
    print(f"#{test_case} {answer}")

문제 링크

문제 요약

최빈수 찾기

해시맵(1)

T = int(input())
for test_case in range(1, T + 1):
    num = input()
    arr = list(map(int, input().split()))

    counter = [0] * 101

    for i in arr:
        counter[i]+=1

    highest_idx = 0
    for i in range(1, 101):
        if counter[highest_idx] <= counter[i]:
            highest_idx = i

    print(f'#{test_case} {highest_idx}')

문제 링크

문제 링크

문제 요약

배열을 순회하면서 합을 구하기

슬라이딩 윈도우(T*N)

for test_case in range(1, 10 + 1):
    answer = 0
    N = int(input())
    arr = list(map(int, input().split()))

    left = 2
    right = N-2
    for i in range(left, right):
        highest = max(arr[i-2], arr[i-1], arr[i+1], arr[i+2])
        if arr[i] > highest:
            answer += arr[i] - highest

    print(f'#{test_case} {answer}')

문제 링크

문제 링크

문제 요약

주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 반환하라.

이분 탐색(nlogn)

import sys

input = sys.stdin.readline

N = int(input())

A = list(map(int, input().split()))

arr = []

for i in range(N):
    node = A[i]

    left = 0
    right = len(arr) - 1
    pos = -1
    while left <= right:
        mid = (left + right) // 2

        if node > arr[mid]:
            left = mid + 1
        else:
            right = mid - 1
            pos = mid

    if pos == -1:
        arr.append(node)
    else:
        arr[pos] = node


print(len(arr))

문제 링크

문제 링크

문제 요약

오름차순으로 구성된 배열에서 두 특성값의 합이 0에 최대한 가까운 조합을 찾아야 한다. 풀이법은 투 포인터와 이분 탐색이 있고, 각각 N과 Nlogn 의 시간 복잡도를 가진다.

투 포인터(N)

import sys

input = sys.stdin.readline

N = int(input())
M = list(map(int, input().split()))


def solution(N, M):
    start, end = 0, N - 1
    best = abs(M[start] + M[end])
    prev_start, prev_end = start, end
    while start < end:
        cur = M[start] + M[end]
        if best > abs(cur):
            best = abs(cur)
            prev_start, prev_end = start, end

        if cur < 0:
            start += 1
        elif cur == 0:
            break
        else:
            end -= 1

    print(M[prev_start], M[prev_end])


solution(N, M)

이분 탐색(NlogN)

import sys

input = sys.stdin.readline

N = int(input())
M = list(map(int, input().split()))


def solution(N, M):
    best = sys.maxsize
    best_start = 0
    best_end = N - 1
    for i in range(N - 1):
        val, end = bisect(i + 1, N - 1, i, best, M)
        if best > val:
            best = val
            best_start = i
            best_end = end

    print(M[best_start], M[best_end])


def bisect(left, right, cur, best, M):
    best_end = right
    while left <= right:
        mid = (left + right) // 2
        total = M[mid] + M[cur]

        if best > abs(total):
            best = abs(total)
            best_end = mid

        if total < 0:
            left = mid + 1
        else:
            right = mid - 1
    return best, best_end


solution(N, M)

N+1 문제란?

특정 엔티티를 조회할 때, 연관된 엔티티를 개별적으로 가져오기 위해 추가적인 쿼리가 발생하는 문제이다. 예를 들어, Memeber 엔티티와 연관된 Item 엔티티가 N개 있을때, Member를 조회하면 Item을 가져오기 위해 추가로 N개의 SELECT 쿼리가 실행된다. 결과적으로 총 N+1개의 쿼리가 발생한다.

왜 N+1 문제가 발생하지?

지연 로딩에 의해 발생한다. 기본적으로 @ManyToOne 이나 OneToMany와 같은 연관 관계에서, JPA는 연관된 엔티티를 나중에 필요한 시점에 로드하려고 한다. 그래서 초기 조회 쿼리 이후에 연관 엔티티를 조회하기 위한 추가적인 쿼리가 발생하게 된다.

이게 왜 문제지?

1. 성능 저하: 쿼리의 수가 많아짐에 따라 데이터베이스와의 통신 횟수가 증가한다. 이는 데이터베이스의 응답 시간을 증가시킨다.

2. 리소스 낭비: 여러 번의 쿼리 호출로 인해 네트워크 트래픽이 증가하고, 서버 부하가 커진다.

3. 대용량 데이터: 연관된 데이터가 많은 경우 병목 현상을 일으킬 수 있다.

   재현

   아래는 Member와 Item 엔티티가 N:1 관계를 가지도록 작성되어있다.

   @Getter  
   @Setter  
   @Entity  
   public class Member {  
    @Id  
    @GeneratedValue(strategy = GenerationType.IDENTITY)  
    private Long id;  
   
    private String name;  
   
    @OneToMany(mappedBy = "owner")  
    private List<Item> itemList;  
   }
   

@Getter
@Setter
@Entity
public class Item {
@Id
@GeneratedValue(strategy = GenerationType.IDENTITY)
private Long id;

private String name;  

@ManyToOne  
private Member owner;  

}

각 Memeber마다 2개의 Item을 가지도록 데이터를 준비했다.
```java
@BeforeEach  
public void beforeEach() {  
    List<Member> memberList = new ArrayList<>();  
    for (int i = 0; i < 10; i++) {  
       Member member = new Member();  
       member.setName("member: " + i);  
       memberList.add(member);  
    }  
    memberRepository.saveAllAndFlush(memberList);  

    List<Item> itemList = new ArrayList<>();  
    for (int i = 0; i < 10; i++) {  
       for (int j = 0; j < 2; j++) {  
          Item item = new Item();  
          item.setOwner(memberList.get(i));  
          item.setName("item: " + i + '-' + j);  
          itemList.add(item);  
       }  
    }  
    itemRepository.saveAllAndFlush(itemList);  

    em.clear();  
}

아래의 코드는 모든 Item을 불러오는 테스트이다. 모든 Item을 조회하는 하나의 쿼리문과 각 Item의 Member를 불러오는 10개의 추가 쿼리가 나올 것으로 기대된다.

@Test  
public void givenMemberAndItem_whenFindAll_thenNPlusOneOccurs() {  
    List<Item> itemList = itemRepository.findAll();  
    itemList.forEach(item -> assertNotNull(item.getOwner().getName()));  
}

실행 결과 Item에 대한 조회 한 건과 Member에 대한 조회 10건이 발생했다. 이를 통해 N+1 문제가 발생하는 것을 확인할 수 있다.

insert 
into
    item
    (name, owner_id, id) 
values
    (?, ?, default)

select
    m1_0.id,
    m1_0.name 
from
    member m1_0 
where
    m1_0.id=?

어떻게 해결할 수 있지?

Fetch join

JPQL에서 fetch join을 사용해서 연관된 엔티티를 한 번의 쿼리로 가져온다.

테스트 코드:

@Query("select i from Item i left join fetch i.owner")  
List<Item> findAllWithOwner();

@Test  
public void whenFetchJoinUsed_thenNoNPlus1Problem() {  
    List<Item> items = itemRepository.findAllWithOwner();  
    assertEquals(2, items.size());  
}

실행되는 쿼리:

select
    i1_0.id,
    i1_0.name,
    o1_0.id,
    o1_0.name 
from
    item i1_0 
left join
    member o1_0 
        on o1_0.id=i1_0.owner_id

join을 사용하여 Item과 Member를 조인하여 한 번의 쿼리로 데이터를 로드한다. N+1 문제를 방지하면서도 Item과 Member를 한 번에 가져온다. 하지만 페이징이 필요한 상황에서 LIMIT 사용은 어렵다.

EntityGraph

JPA에서 제공하며, 연관된 엔티티를 동적으로 로딩할 수 있다.

테스트 코드:

@EntityGraph(attributePaths = {"owner"})  
@Query("select i from Item i")  
List<Item> findAllWithOwnerEntityGraph();

@Test  
public void whenEntityGraphUsed_thenNoNPlus1Problem() {  
    List<Item> items = itemRepository.findAllWithOwnerEntityGraph();  
    assertEquals(20, items.size());  
}

실행되는 쿼리:

select
    i1_0.id,
    i1_0.name,
    o1_0.id,
    o1_0.name 
from
    item i1_0 
left join
    member o1_0 
        on o1_0.id=i1_0.owner_id

EntityGraph를 사용해 owner를 함께 로드하여 N+1 문제를 해결한다. JOIN을 통해 기존 fetch join 과 같은 한 번의 쿼리를 전송한다. 또한 페이징에 대해서 문제가 있고, 설정이 NamedEntityGraph, SubGraph 등의 설정이 복잡할 수 있다.

@BatchSize 사용

지연 로딩 시 여러 엔티티를 설정한 만큼 로드하여 완화하는 방식이다.

테스트 코드:

@Test  
public void whenBatchSizeUsed_thenReducedQueries() {  
    List<Member> memberList = memberRepository.findAll();  
    assertEquals(10, memberList.size());  
    memberList.forEach(member -> assertEquals(2, member.getItemList().size()));  
}

엔티티 설정(Member):

@OneToMany(mappedBy = "owner")  
@BatchSize(size = 5)  
private List<Item> itemList;

실행되는 쿼리

select
    m1_0.id,
    m1_0.name 
from
    member m1_0

select
    il1_0.owner_id,
    il1_0.id,
    il1_0.name 
from
    item il1_0 
where
    il1_0.owner_id in (?, ?, ?, ?, ?)

select
    il1_0.owner_id,
    il1_0.id,
    il1_0.name 
from
    item il1_0 
where
    il1_0.owner_id in (?, ?, ?, ?, ?)

첫 SELCT 문 이후 Member 기준으로 Item을 가져오는 쿼리가 두 번 실행된다. 배치 사이즈만큼의 Member 엔티티를 로드한다. 기존 N+1보다 쿼리 수를 줄일 수 있다. 이전의 방식과 다르게 IN 절을 사용하기 때문에 쿼리가 복잡해질 수 있다.

FetchMode.SUBSELECT

초기화되지 않은 컬렉션을 로드할 때 서브쿼리를 사용해 문제를 해결한다.

테스트 코드:

@Test  
public void whenSubSelectUsed_thenNoNPlus1Problem() {  
    List<Member> memberList = memberRepository.findAll();  
    assertEquals(10, memberList.size());  
    memberList.forEach(member -> assertEquals(2, member.getItemList().size()));  
}

엔티티 설정(Member):

@OneToMany(mappedBy = "owner")  
@Fetch(FetchMode.SUBSELECT)  
private List<Item> itemList;

실행되는 쿼리

select
    m1_0.id,
    m1_0.name 
from
    member m1_0

select
    il1_0.owner_id,
    il1_0.id,
    il1_0.name 
from
    item il1_0 
where
    il1_0.owner_id in (select
        m1_0.id 
    from
        member m1_0)

서브쿼리를 사용해서 연관된 컬렉션을 한 번에 로드한다. 기존 N+1은 하나의 엔티티에 대해 연관된 엔티티를 하나씩 조회하지만, 이 방식은 연관된 엔티티 전체에서 한 번에 가져온다. BatchSize 방식처럼 IN 절에 대한 문제를 가지고 있다.

DTO 프로젝션 사용

필요한 필드만 선택적으로 가져와 메모리 사용량을 줄이고 성능을 최적화한다.

테스트 코드:

@Query("select "  
    + "m.id as id, "  
    + "m.name as memberName, "  
    + "i.name as itemName "    + "from Member m "  
    + "left join m.itemList i")  
List<MemberProjection> findAllMemberProjections();

@Test  
public void whenDTOProjectionUsed_thenNoNPlus1Problem() {  
    List<MemberProjection> projections = memberRepository.findAllMemberProjections();  
    assertEquals(20, projections.size());  
}

실행되는 쿼리:

select
    m1_0.id,
    m1_0.name,
    il1_0.name 
from
    member m1_0 
left join
    item il1_0 
        on m1_0.id=il1_0.owner_id

하나의 Member당 2개의 Item이 있으므로 20개의 행이 만들어진다. 필요한 필드만을 요청하므로 네트워크 트래픽을 절약할 수 있다. DTO 에 대한 정의와 유지 관리가 번거로울 수 있다.

QueryDSL 사용

Inetger와 Long 을 헷갈리는 문제를 해결할 수 있도록, 타입 안전한 방식으로 쿼리를 작성해준다. fetchJoin()을 사용해 N+1 문제를 해결한다.

빌드 추가:

implementation 'com.querydsl:querydsl-jpa:5.0.0:jakarta'  
annotationProcessor "com.querydsl:querydsl-apt:5.0.0:jakarta"  
annotationProcessor "jakarta.annotation:jakarta.annotation-api"  
annotationProcessor "jakarta.persistence:jakarta.persistence-api"

테스트 코드(N+1):

@Test  
public void whenQueryDSLUsed_thenNoNPlus1Problem() {  
    List<Item> items = new JPAQueryFactory(em)  
       .selectFrom(QItem.item)  
       .leftJoin(QItem.item.owner, QMember.member)  
       .fetchJoin()  
       .fetch();  
    assertEquals(20, items.size());  
}

실행되는 쿼리:

select
    i1_0.id,
    i1_0.name,
    o1_0.id,
    o1_0.name 
from
    item i1_0 
left join
    member o1_0 
        on o1_0.id=i1_0.owner_id

일반 fetch 조인과 같이 동작하므로 N+1 문제를 방지한다. 또한 검색과 같은 동적 쿼리 작성과 페이징 처리에 용이하다.

아래는 페이징 처리를 하는 두 가지 방법이다.

테스트 코드(페이징)

@Test  
public void whenQueryDSLWithPagination_thenCorrectPageResults() {  
    int pageNumber = 0;  
    int pageSize = 5;  

    List<Member> memberList = new JPAQueryFactory(em)  
       .selectFrom(QMember.member)  
       .leftJoin(QMember.member.itemList, QItem.item)  
       .fetchJoin()  
       .offset(pageNumber * pageSize)  
       .limit(pageSize)  
       .fetch();  

    assertEquals(pageSize, memberList.size());  
    for (int i = 0; i < pageSize; i++) {  
       Member member = memberList.get(i);  
       assertEquals(member.getId(), i + 1);  

       List<Item> itemList = member.getItemList();  
       assertEquals(itemList.size(), 2);  
       for (int j = 0; j < 2; j++) {  
          assertEquals(itemList.get(j).getId(), i * 2 + j + 1);  
       }  
    }  
}

실행되는 쿼리:

select
    m1_0.id,
    il1_0.owner_id,
    il1_0.id,
    il1_0.name,
    m1_0.name 
from
    member m1_0 
left join
    item il1_0 
        on m1_0.id=il1_0.owner_id

기존 fetch join 과 같은 동작을 하지만 LIMIT 절이 동작하지 않는다. 데이터베이스 레벨에서는 일반 fetch join 과 같이 동작한다.

대신 메모리 레벨에서 페이징 동작이 발생한다. 그래서 아래와 같은 경고문이 발생한다.

HHH90003004: firstResult/maxResults specified with collection fetch; applying in memory

이는 메모리 사용량이 N * M 을 가지게 되므로 매우 부담일 수 있다.

이를 해결하기 위해서는 FetchMode.SUBSELECT 처럼 쿼리를 나눠서 전송해야 한다. 테스트 코드(분할 쿼리)

@Test  
public void whenQueryDSLWithSeperatedPagination_thenCorrectPageResults() {  
    int pageNumber = 0;  
    int pageSize = 5;  

    List<Member> memberList = new JPAQueryFactory(em)  
       .selectFrom(QMember.member)  
       .offset(pageNumber * pageSize)  
       .limit(pageSize)  
       .fetch();  

    List<Long> memberIds = memberList.stream()  
       .map(Member::getId)  
       .toList();  

    Map<Long, List<Item>> itemsByMemberId = new JPAQueryFactory(em)  
       .selectFrom(QItem.item)  
       .where(QItem.item.owner.id.in(memberIds))  
       .fetch().stream()  
       .collect(Collectors.groupingBy(item -> item.getOwner().getId()));  

    memberList.forEach(member -> {  
       List<Item> itemList = itemsByMemberId.getOrDefault(member.getId(), Collections.emptyList());  
       member.setItemList(itemList);  
    });  

    assertEquals(pageSize, memberList.size());  
    for (int i = 0; i < pageSize; i++) {  
       Member member = memberList.get(i);  
       assertEquals(member.getId(), i + 1);  

       List<Item> itemList = member.getItemList();  
       assertEquals(itemList.size(), 2);  
       for (int j = 0; j < 2; j++) {  
          assertEquals(itemList.get(j).getId(), i * 2 + j + 1);  
       }  
    }  
}

실행되는 쿼리

select
    m1_0.id,
    m1_0.name 
from
    member m1_0 
offset
    ? rows 
fetch
    first ? rows only

select
    i1_0.id,
    i1_0.name,
    i1_0.owner_id 
from
    item i1_0 
where
    i1_0.owner_id in (?, ?, ?, ?, ?)

기준 엔티티는 페이징을 적용하고, 연관된 엔티티는 별도로 조회하여 매핑한다. 현재 코드는 setter를 이용하지만 유지보수를 위해서는 별도의 처리가 필요하다. N+1의 문제를 해결하면서 EntityGraph의 복잡성을 해소할 수 있다.

해결 방법 정리

결론

N+1 문제는 JPA 에서 성능 저하의 주요 원인 중 하나다. 이를 해결하기 위한 방법들을 찾아보았고, 각자 장단점이 있다는 것을 확인했다. 단순한 쿼리는 fetch join을, 복잡한 조건에서는 QueryDSL을 고려할 수 있다. 또한 대용량 데이터로 실험하지 않았기에 정확한 성능을 비교해볼 필요가 있다. DTO의 경우 최적화를 적용할 수 있으며, 다른 기술에 적용가능한 유연성을 지니고 있다.

Docker 의 멀티 스테이지 빌드가 이미지 경량화의 효과가 있었다. 그리고 예전에 팀 프로젝트 했을때 테스크 코드 때문에 빌드 속도가 매우 느렸다. 그래서 이번 기회에 Spring Boot 프로젝트의 도커 이미지 빌드 과정을 개선해보려고 한다.

계획

Spring Boot 프로젝트를 실행하는 과정은 다음과 같다.

1. Gradle 기반 빌드
2. JDK 기반 실행

# step 1: Build Stage  
FROM gradle:jdk17-alpine AS build  
WORKDIR /home/app  
COPY ./ ./  
RUN ./gradlew bootJar  

# step 2: Run Stage  
FROM openjdk:17-alpine AS run  
WORKDIR /home/app  
COPY --from=build /home/app/build/libs/*.jar app.jar  
ENTRYPOINT ["java", "-jar", "app.jar"]

docker build -t spring-boot-app-multi-stage .

처음에는 build 를 쓸까 고민했지만 빌드 과정은 test 과정을 내포하고 있어 시간이 많이 걸린다. 그리고 실제 배포 이전에 test 과정을 거친결과만 올리게 될 것이므로 빠르게 배포하려고 한다.

gradle 에서 build 과정은 아래와 같다.

:compileJava SKIPPED
:processResources SKIPPED
:classes SKIPPED
:resolveMainClassName SKIPPED
:bootJar SKIPPED
:jar SKIPPED
:assemble SKIPPED
:compileTestJava SKIPPED
:processTestResources SKIPPED
:testClasses SKIPPED
:test SKIPPED
:check SKIPPED
:build SKIPPED

bootJar 은 test 이전까지의 과정만 거치기 때문에 빠른 빌드가 가능하다.

:compileJava SKIPPED
:processResources SKIPPED
:classes SKIPPED
:resolveMainClassName SKIPPED
:bootJar SKIPPED

싱글 스테이지 빌드와 비교

이전에는 Java 기반 이미지에서 효능감을 확인하려고 한다.

# step 1: Single Stagae Build  
FROM openjdk:17-alpine  
WORKDIR /home/app  
COPY ./ ./  
RUN ./gradlew bootJar  
COPY *.jar app.jar  
ENTRYPOINT ["java", "-jar", "app.jar"]

docker build -t spring-boot-app-single-stage .

실행 결과

싱글 스테이지 빌드와 멀티 스테이지 빌드의 용량 차이가 2배 가까이 나는 것을 확인할 수 있다. 빌드 시간은 각각 약 60초와 77초로 멀티 스테이지 빌드에서 시간이 더 걸린다.

멀티 스테이지 빌드란?

멀티 스테이지 빌드는 Dockerfile 을 최적화하면서도 읽고 유지 관리하기 쉽도록 하는 데 어려움을 겪는 모든 사람에게 유용하다.

멀티 스테이지 빌드 사용법

멀티 스테이지 빌드를 사용하면 Dockerfile 에서 여러 개의 FROM 문을 사용할 수 있다. 각 FROM 문은 서로 다른 베이스를 사용할 수 있으며, 각 명령어는 빌드의 새로운 단계를 시작한다. 한 단계에서 다른 단계로 아티팩트를 선택적으로 복사할 수 있으며 최종 이미지에 필요한 것만 남길 수 있다.

다음 Dockerfile 은 두 개의 분리된 단계를 포함하고 있다. 하나는 바이너리를 빌드하는 단계이고, 다른 하나는 첫 번재 단계에서 바이너리를 복사하는 단계입니다.

# syntax=docker/dockerfile:1
FROM golang:1.23
WORKDIR /src
COPY <<EOF ./main.go
package main

import "fmt"

func main() {
  fmt.Println("hello, world")
}
EOF
# RUN go build -o /bin/hello ./main.go
RUN go build -o /bin/hello ./main.go && rm -rf /usr/local/go/pkg/* /src/*


FROM scratch
COPY --from=0 /bin/hello /bin/hello
CMD ["/bin/hello"]

Dockerfile 하나만 필요하며 별도의 빌드 스크림트가 필요하지 않습니다. 그냥 docker build 명령어를 실행하면 됩니다.

docker build -t hello .

결과적으로 최종 이미지에는 빌드된 바이너리만 들어있는 작은 프로덕션 이미지가 생성됩니다. 애플리케이션을 빌드하는 데 필요한 도구들은 최종 이미지에 포함되지 않습니다.

검증

멀티 스테이징 빌드가 필요한 것만 남길 수 있다면 싱글 스테이지 빌드보다 경량화 된 모습이 확인되어야 합니다. 싱글 스테이지 빌드 환경을 구성해서 비교해봅시다.

# syntax=docker/dockerfile:1
FROM golang:1.23

WORKDIR /src

COPY <<EOF ./main.go
package main

import "fmt"

func main() {
  fmt.Println("hello, world")
}
EOF

# 애플리케이션 빌드
RUN go build -o /bin/hello ./main.go

# 컨테이너 실행 시 명령어
CMD ["/bin/hello"]

docker build -t hello2 .

위 사진과 같이 멀티 스테이지 빌드는 2.13MB 를 차지하고, 싱글 스테이지 빌드는 869MB 를 차지하는 것을 볼 수 있다.

어떻게 작동하는가?

두 번째 FROM 지시문은 scratch 이미지를 베이스로 새로운 빌드 스테이지를 시작합니다. COPY --from=0 은 이전 스테이지에서 빌드된 아티팩트만 현재 스테이지로 복사합니다. Go SDK 와 중간 아티팩트들은 최종 이미지에 저장되지 않고 남겨집니다.

빌드 스테이지에 이름 지정하기

기본적으로 스테이지는 이름이 없으며, 첫 번째 FROM 지시문을 0부터 시작하는 정수로 참조합니다. 그러나 FROM 지시문에 AS <NAME> 을 추가하여 스테이지에 이름을 지정할 수 있습니다. 다음 예제는 이전 예제를 개선하여 스테이지에 이름을 지정하고, COPY 지시문에서 이름을 사용합니다. 이렇게 하면 Dockerfile 의 지시문 순서가 나중에 변경되더라도 COPY 는 문제없이 작동합니다.

# syntax=docker/dockerfile:1
# 빌드 스테이지 네이밍 -> AS build
FROM golang:1.23 AS build
WORKDIR /src
COPY <<EOF /src/main.go
package main

import "fmt"

func main() {
  fmt.Println("hello, world")
}
EOF
RUN go build -o /bin/hello ./main.go

FROM scratch
# 빌드 스테이지 이름 참고 -> --from=build
COPY --from=build /bin/hello /bin/hello
CMD ["/bin/hello"]

특정 빌드 스테이지에서 중지하기

이미지를 빌드할 때, 반드시 Dockerfile 의 모든 스테이지를 빌드할 필요는 없습니다. 목표 빌드 스테이지를 지정할 수 있습니다. 다음 명령은 이전 Dockerfile 을 사용하면서 build 로 이름 지정된 스테이지에서 멈춥니다.

docker build --target build -t hello .

이 기능이 유용한 몇 가지 시나리오:

• 특정 빌드 스테이지를 디버깅할 때
• 모든 디버그 심볼 또는 도구를 활성화한 디버그 스테이지와, 간소화된 프로덕션 스테이지를 사용할 때
• 테스트 데이터를 채워 넣는 테스트 스테이지를 사용하면서, 실제 데이터를 사용하는 프로덕션 스테이지를 사용해 빌드할 때

  외부 이미지를 스테이지로 사용하기

  멀티 스테이지 빌드를 사용할 때, Dockerfile 에서 생성한 스테이지에만 국한되지 않습니다. COPY --from 지시문을 사용하여 별도의 이미지에서 복사할 수 있습니다. 로컬 이미지 이름, 로컬 또는 Docker 레지스트리에서 사용할 수 있는 태그 또는 태그 ID 를 사용할 수 있습니다. 필요한 경우 Docker 클라이언트는 이미지를 가져와 그곳에서 아티팩트를 복사합니다. 구문은 다음과 같습니다.

COPY --from=nginx:latest /etc/nginx/nginx.conf /nginx.conf

첫 예제에서도 Go SDK 를 외부 이미지로 사용하는 모습을 볼 수 있습니다.

FROM golang:1.23

이전 스테이지를 새 스테이지로 사용하기

FROM 지시문을 사용할 때 이전 스테이지가 중단된 곳에서 다시 시작할 수 있습니다. 예를 들어

# syntax=docker/dockerfile:1

FROM alpine:latest AS builder
RUN apk --no-cache add build-base

FROM builder AS build1
COPY source1.cpp source.cpp
RUN g++ -o /binary source.cpp

FROM builder AS build2
COPY source2.cpp source.cpp
RUN g++ -o /binary source.cpp

이렇게하면 builder 를 기준으로 build1 과 build2 가 각각 빌드할 수 있게 됩니다.

레거시 빌더와 BuildKit 의 차이점

레거시 Docker 엔진 빌더는 선택한 --target 에 이르는 모든 스테이지를 처리합니다. 이는 선택한 대상이 해당 스테이지에 의존하지 않아도 스테이지를 빌드하는다는 의미입니다.

BuildKit 은 대상 스테이지에 의존하는 스테이지만 빌드합니다.

다음 Dockerfile 을 예로 들어 보겠습니다.

# syntax=docker/dockerfile:1
FROM ubuntu AS base
RUN echo "base"

FROM base AS stage1
RUN echo "stage1"

FROM base AS stage2
RUN echo "stage2"

BuildKit 이 활성화된 경우, 이 Dockerfile 에서 stage2 대상 빌드 시 base 와 stage2 만 처리됩니다. stage1 에 대한 의존성이 없으므로 생략됩니다.

DOCKER_BUILDKIT=1 docker build --no-cache -f Dockerfile --target stage2 .

$ DOCKER_BUILDKIT=1 docker build --no-cache -f Dockerfile --target stage2 .
#0 building with "default" instance using docker driver

#1 [internal] load build definition from Dockerfile
#1 transferring dockerfile: 189B done
#1 DONE 0.0s

#2 resolve image config for docker-image://docker.io/docker/dockerfile:1
#2 DONE 1.6s

#3 docker-image://docker.io/docker/dockerfile:1@sha256:865e5dd094beca432e8c0a1d5e1c465db5f998dca4e439981029b3b81fb39ed5
#3 CACHED

#4 [internal] load metadata for docker.io/library/ubuntu:latest
#4 DONE 0.0s

#5 [internal] load .dockerignore
#5 transferring context:
#5 transferring context: 2B done
#5 DONE 0.0s

#6 [base 1/2] FROM docker.io/library/ubuntu:latest
#6 DONE 0.0s

#7 [base 2/2] RUN echo "base"
#7 0.323 base
#7 DONE 0.4s

#8 [stage2 1/1] RUN echo "stage2"
#8 0.267 stage2
#8 DONE 0.3s

#9 exporting to image
#9 exporting layers 0.1s done
#9 writing image sha256:bf74e2e21b477d89652cb54a01ac0d110dcf66984d28a7935c1388975d6fdb3c done
#9 DONE 0.1s

View build details: docker-desktop://dashboard/build/default/default/leeq2808la11op7rrkphw6q2t

What's Next?
  View a summary of image vulnerabilities and recommendations → docker scout quickview

반면, BuildKit 없이 동일한 대상을 빌드하면 모든 스테이지가 처리됩니다. 그리고 레거시 빌더가 deprecated 되었다는 알림을 볼 수 있습니다.

DOCKER_BUILDKIT=0 docker build --no-cache -f Dockerfile --target stage2 .

$ DOCKER_BUILDKIT=0 docker build --no-cache -f Dockerfile --target stage2 .
DEPRECATED: The legacy builder is deprecated and will be removed in a future release.
            BuildKit is currently disabled; enable it by removing the DOCKER_BUILDKIT=0
            environment-variable.

Sending build context to Docker daemon  2.048kB
Step 1/6 : FROM ubuntu AS base
 ---> edbfe74c41f8
Step 2/6 : RUN echo "base"
 ---> Running in 65b6aa46a6b6
base
 ---> Removed intermediate container 65b6aa46a6b6
 ---> 6de405e6b173
Step 3/6 : FROM base AS stage1
 ---> 6de405e6b173
Step 4/6 : RUN echo "stage1"
 ---> Running in 8a05cb170ab1
stage1
 ---> Removed intermediate container 8a05cb170ab1
 ---> 07b3d9163bb5
Step 5/6 : FROM base AS stage2
 ---> 6de405e6b173
Step 6/6 : RUN echo "stage2"
 ---> Running in 51544f6ad948
stage2
 ---> Removed intermediate container 51544f6ad948
 ---> b8a5a5355925
Successfully built b8a5a5355925
SECURITY WARNING: You are building a Docker image from Windows against a non-Windows Docker host. All files and directories added to build context will have '-rwxr-xr-x' permissions. It is recommended to double check and reset permissions for sensitive files and directories.

What's Next?
  View a summary of image vulnerabilities and recommendations → docker scout quickview

레거시 빌더는 stage1 의 빌드를 거치고 stage2 에 진입하는 차이가 있습니다.

그렇다면 기본 빌드는 BuildKit 으로 빌드하고 있을까요?

docker build --no-cache -f Dockerfile --target stage2 .

아래 처럼 stage1 이 동작하지 않는 점과 BuildKit 을 명시한 경우와 동일한 결과라는 점을 통해 BuildKit 으로 동작함을 확인할 수 있습니다.

$ docker build --no-cache -f Dockerfile --target stage2 .
#0 building with "default" instance using docker driver

#1 [internal] load build definition from Dockerfile
#1 transferring dockerfile: 189B done
#1 DONE 0.0s

#2 resolve image config for docker-image://docker.io/docker/dockerfile:1
#2 DONE 1.6s

#3 docker-image://docker.io/docker/dockerfile:1@sha256:865e5dd094beca432e8c0a1d5e1c465db5f998dca4e439981029b3b81fb39ed5
#3 CACHED

#4 [internal] load metadata for docker.io/library/ubuntu:latest
#4 DONE 0.0s

#5 [internal] load .dockerignore
#5 transferring context:
#5 transferring context: 2B done
#5 DONE 0.0s

#6 [base 1/2] FROM docker.io/library/ubuntu:latest
#6 CACHED

#7 [base 2/2] RUN echo "base"
#7 0.278 base
#7 DONE 0.3s

#8 [stage2 1/1] RUN echo "stage2"
#8 0.272 stage2
#8 DONE 0.3s

#9 exporting to image
#9 exporting layers 0.0s done
#9 writing image sha256:5fe18f4ced90a7932db7b35bcb350710174d5c6bd39f73397e89a47ba6f6f486 done
#9 DONE 0.1s

View build details: docker-desktop://dashboard/build/default/default/vw8lnc0g1wez01bwkanyy582s

What's Next?
  View a summary of image vulnerabilities and recommendations → docker scout quickview

@GetMapping("/update/{id}")
public String updatePost(CreatePostRequest request, @PathVariable("id") Long id) {
    Post post = postService.findById(id);

    request = new CreatePostRequest(post.getTitle(), post.getContent());

    return "post_update";
}

request 를 새로운 record 로 대체하면 페이지에서 값이 입력되지 않았다. 그래서 class 타입으로 선언해야했다.

웹 폼 제출 후 새로고침이나 뒤로 가기로 인해 데이터가 중복으로 제출되는 문제를 방지하는 방법이다. 폼 제출 후 서버에서 결과 페이지가 아닌 다른 페이지로 리다이렉트 시키고 결과를 보여준다.

동작

1. POST : 사용자가 폼을 제출하면, 서버에서 폼 데이터를 처리한다.
2. Redirect : 폼 데이터가 성공적으로 처리되면 다른 페이지로 Redirect 한다. 이로 인해 브라운저는 새로운 GET 요청을 수행한다.
3. GET : 사용자는 새로운 GET 요청에 의한 새로운 페이지를 보게 된다.

   특징

• 이중 제출 방지 : 사용자가 페이지를 새로고침이나 뒤로 가기 버튼으로 폼을 다시 제출하지 않도록 할 수 있다. 이는 브라우저의 동작을 알아볼 필요가 있다.
• 무결성 검증 : 제출한 폼에서 잘못된 데이터에 대한 처리를 할 수 있다.
• 사용자 경험 개선 : 화면이 바뀜으로서 폼 제출이 성공적으로 처리됨을 인지할 수 있다.

이 패턴을 사용하게 된 배경

점프 투 스프링 부트 3 을 공부하면서 특정 패턴이 보여서 찾아보았다. POST 동작을 하게되는 페이지에서 입력값을 검증하는데 사용되는데 GET 과 함께 사용되고 있는 것이다.

@GetMapping  
public String createPost(CreatePostRequest request) {  
    return "post_new";  
}  

@PostMapping  
public String createPost(@Valid CreatePostRequest request, BindingResult bindingResult) {  
    if (bindingResult.hasErrors()) {  //  무결성 위반시 반환
       return "post_new";  
    }  
    postService.savePost(request);  
    return "redirect:/";  // 성공시 리다이렉트
}

이 코드에서는 폼을 전송했을 때 에러가 발생하면 다시 원래 폼으로 돌려주는 방식이다. 성공적으로 제출했을 경우 리다이렉트로 이중 제출을 방지할 수 있다. 이렇게 폼 제출 후에 발생하는 문제들을 해결하는데 사용하는 패턴이 PRG 패턴이라고 한다.