로드 밸런서: 알고리즘과 사용 시점

1. 개요

시스템에 백엔드 인스턴스가 여러 개 있을 때 항상 들게 되는 질문은: 새로운 요청은 어느 인스턴스로 보낼까? 이 글에서는 자주 접하는 로드 밸런싱 알고리즘, Java 코드로 시뮬레이션한 동작 방식, 그리고 각 워크로드 유형에 적합한 알고리즘 선택 기준을 설명합니다. 이 글을 다 읽으면, Round Robin만으로 충분한 경우와 Least Connections나 Consistent Hashing이 필요한 경우를 구분할 수 있게 될 겁니다.

2. 로드 밸런서란 무엇인가

로드 밸런서(LB)는 클라이언트와 백엔드 서버 그룹 사이에 위치하는 컴포넌트로, 다음의 역할을 합니다:

• 어떤 서버도 과부하되지 않고 다른 서버가 유휴 상태가 되지 않도록 요청 분산.
• 한 백엔드가 다운되어도 시스템이 계속 동작하도록 페일오버 지원.
• 클라이언트가 모를 사이에 인스턴스를 추가/제거하여 수평 확장 가능.

LB는 소프트웨어(Nginx, HAProxy, Envoy), 하드웨어(F5) 또는 관리형 서비스(AWS ALB/NLB, GCP Load Balancer) 형태입니다. 동작 계층에 따라 두 가지 주요 유형으로 나뉩니다:

• Layer 4(전송 계층): IP/포트 기반 라우팅, HTTP 내용은 읽지 않음. 빠르고 오버헤드 적음.
• Layer 7(응용 계층): HTTP 헤더, 경로, 쿠키 등을 읽으므로 더 지능적인 라우팅 가능(/api/orders 같은 경로별 라우팅). 하지만 CPU를 더 사용함.

주의: 계층을 잘못 선택하는 것은 흔한 설계 실수입니다. URL 경로나 쿠키 기반 sticky session이 필요하면 Layer 4로는 불가능하고, Layer 7을 써야 합니다.

3. 일반적인 로드 밸런싱 알고리즘

3.1. Round Robin

요청이 순서대로 각 서버를 거쳐 가며, 목록의 끝에 도달하면 처음부터 다시 시작합니다.

public class RoundRobinBalancer {

    private final List<String> servers;
    private final AtomicInteger index = new AtomicInteger(0);

    public RoundRobinBalancer(List<String> servers) {
        this.servers = servers;
    }

    public String nextServer() {
        int i = index.getAndIncrement() % servers.size();
        return servers.get(Math.abs(i));
    }
}

getAndIncrement는 여러 스레드 간에 카운터를 안전하게 증가시키고, % servers.size()는 인덱스를 유효한 범위로 가져옵니다. 3개 서버 [A, B, C]의 경우 연속 nextServer() 호출 시:

A, B, C, A, B, C, ...

Round Robin은 단순하고 서버 상태를 알 필요가 없습니다. 단점: 요청 비용이 다른 경우(한 요청은 1ms, 다른 요청은 500ms), 비용이 큰 요청을 처리하는 서버가 시간이 지남에 따라 과부하되기 쉽습니다.

3.2. Weighted Round Robin

각 서버에 “가중치”가 있어서 처리 능력(CPU, RAM)을 반영합니다. 더 강력한 서버가 더 많은 요청을 받습니다.

public class WeightedRoundRobinBalancer {

    private record WeightedServer(String name, int weight) {}

    private final List<WeightedServer> servers;
    private int currentIndex = -1;
    private int currentWeight = 0;

    public WeightedRoundRobinBalancer(Map<String, Integer> weightedServers) {
        this.servers = weightedServers.entrySet().stream()
            .map(e -> new WeightedServer(e.getKey(), e.getValue()))
            .toList();
    }

    public synchronized String nextServer() {
        int maxWeight = servers.stream().mapToInt(WeightedServer::weight).max().orElse(1);
        int gcdWeight = servers.stream().mapToInt(WeightedServer::weight)
            .reduce((a, b) -> java.math.BigInteger.valueOf(a).gcd(java.math.BigInteger.valueOf(b)).intValue())
            .orElse(1);

        while (true) {
            currentIndex = (currentIndex + 1) % servers.size();
            if (currentIndex == 0) {
                currentWeight -= gcdWeight;
                if (currentWeight <= 0) {
                    currentWeight = maxWeight;
                }
            }
            if (servers.get(currentIndex).weight() >= currentWeight) {
                return servers.get(currentIndex).name();
            }
        }
    }
}

이것은 Nginx에서 사용하는 “smooth weighted round robin” 알고리즘입니다: 가중치가 높은 서버가 더 자주 선택되지만 여전히 균등하게 분산되고, 연속으로 같은 서버가 선택되지 않습니다. {A: 5, B: 1, C: 1} 구성의 경우 대략적인 선택 순서는:

A, A, B, A, C, A, A

3.3. Least Connections

현재 처리 중인 연결이 가장 적은 서버를 선택합니다. 요청 처리 시간이 크게 다를 때 적합합니다.

public class LeastConnectionsBalancer {

    private final Map<String, AtomicInteger> activeConnections = new ConcurrentHashMap<>();

    public LeastConnectionsBalancer(List<String> servers) {
        servers.forEach(s -> activeConnections.put(s, new AtomicInteger(0)));
    }

    public String nextServer() {
        return activeConnections.entrySet().stream()
            .min(Comparator.comparingInt(e -> e.getValue().get()))
            .map(Map.Entry::getKey)
            .orElseThrow();
    }

    public void onRequestStart(String server) {
        activeConnections.get(server).incrementAndGet();
    }

    public void onRequestEnd(String server) {
        activeConnections.get(server).decrementAndGet();
    }
}

nextServer()는 맵을 스캔하고 연결 수가 가장 적은 서버를 가져옵니다. onRequestStart/onRequestEnd는 올바르게 쌍을 이루어야 하고(예: try/finally), 통계가 틀어지지 않도록 해야 합니다.

주의: Least Connections은 LB가 상태를 추적해야 하므로(stateful) — 여러 LB 인스턴스가 병렬로 실행 중일 때 상태 동기화 비용이 높아집니다. Round Robin은 완전히 stateless입니다.

3.4. Least Response Time

Least Connections의 변형으로, (연결 수 × 평균 응답 시간)이 가장 낮은 서버를 선택합니다. Least Connections보다 복잡하지만 처리 지연도 고려하므로 실제 부하를 더 정확히 반영합니다.

public record ServerStats(String name, int activeConnections, double avgResponseTimeMs) {
    double score() {
        return activeConnections * avgResponseTimeMs;
    }
}

public String pickFastest(List<ServerStats> stats) {
    return stats.stream()
        .min(Comparator.comparingDouble(ServerStats::score))
        .map(ServerStats::name)
        .orElseThrow();
}

avgResponseTimeMs는 보통 지수 이동 평균으로 계산되며, 매 응답 반환 시마다 업데이트됩니다. 이 알고리즘은 빠른 API(캐시 조회)와 느린 API(보고서, 복잡한 계산)가 섞여 있는 시스템에 좋습니다.

3.5. IP Hash / Consistent Hashing

sticky session이 필요할 때 사용합니다 — 같은 클라이언트는 항상 같은 서버로 라우팅됩니다(예: 서버가 메모리에 세션을 보관하거나 로컬 캐시가 있을 때).

public class ConsistentHashBalancer {

    private final SortedMap<Long, String> ring = new TreeMap<>();
    private static final int VIRTUAL_NODES = 100;

    public ConsistentHashBalancer(List<String> servers) {
        for (String server : servers) {
            for (int i = 0; i < VIRTUAL_NODES; i++) {
                ring.put(hash(server + "#" + i), server);
            }
        }
    }

    public String serverFor(String clientKey) {
        long hash = hash(clientKey);
        SortedMap<Long, String> tail = ring.tailMap(hash);
        Long nodeKey = tail.isEmpty() ? ring.firstKey() : tail.firstKey();
        return ring.get(nodeKey);
    }

    private long hash(String input) {
        return input.hashCode() & 0xFFFFFFFFL;
    }
}

각 서버는 해시 ring(ring) 위에 여러 개의 “virtual node”로 분산되어 더 균등하게 분배됩니다. serverFor는 클라이언트의 키(보통 IP 또는 사용자 ID)에 해당하는 시계 방향 가장 가까운 지점을 찾습니다. 큰 장점: 서버를 추가/제거할 때 일부 키만 재매핑되고, 일반적인 해시처럼 전체가 섞이지 않습니다(hash(key) % n).

같은 키가 항상 같은 서버로 가는지 확인하는 빠른 테스트:

@Test
void sameClientKey_alwaysRoutesToSameServer() {
    ConsistentHashBalancer balancer =
        new ConsistentHashBalancer(List.of("server-1", "server-2", "server-3"));

    String first = balancer.serverFor("user-42");
    String second = balancer.serverFor("user-42");

    assertThat(first).isEqualTo(second);
}

3.6. Random과 Power of Two Choices

Random은 단순히 무작위로 선택합니다 — 많은 요청이 있을 때 Round Robin에 가까운 성능을 보이지만 상태를 유지할 필요가 없습니다. Power of Two Choices(P2C)는 개선 버전입니다: 무작위로 2개 서버를 선택한 후, 그 2개 중 연결이 더 적은 서버를 선택합니다. 이 알고리즘은 Least Connections처럼 전체 클러스터를 추적하지 않으면서도 “tail latency”를 무작위 선택보다 훨씬 줄이는 것으로 증명되었습니다.

public String pickWithPowerOfTwo(List<String> servers, Map<String, Integer> loadMap, Random random) {
    String candidate1 = servers.get(random.nextInt(servers.size()));
    String candidate2 = servers.get(random.nextInt(servers.size()));
    return loadMap.get(candidate1) <= loadMap.get(candidate2) ? candidate1 : candidate2;
}

4. 헬스 체크와 페일오버

서버 선택 알고리즘은 LB가 어느 서버가 “살아있는지” 알 때만 의미가 있습니다. 헬스 체크는 보통 두 가지 방식입니다:

• Active check: LB가 정기적으로 /health 같은 엔드포인트에 요청을 보냅니다.
• Passive check: LB가 실제 요청에서 오류/타임아웃을 받으면 서버를 “다운”으로 표시합니다.

Nginx에서 active health check 구성 예:

upstream backend_pool {
  server 10.0.0.1:8080 max_fails=3 fail_timeout=30s;
  server 10.0.0.2:8080 max_fails=3 fail_timeout=30s;
}

max_fails=3은 연속 3회 실패 후 서버를 fail_timeout 초 동안 풀에서 제외한 후 다시 시도한다는 뜻입니다. 헬스 체크가 없으면 LB는 죽은 서버로 계속 요청을 보내 클라이언트 타임아웃까지 기다립니다 — 매우 나쁜 사용자 경험입니다.

5. 비교표: 각 알고리즘을 언제 사용할 것인가

알고리즘	적합한 경우	피해야 할 경우
Round Robin	서버가 동일하고 요청 복잡도가 비슷한 경우(간단한 REST API)	서버 사양이 다르거나 요청 복잡도가 다른 경우
Weighted Round Robin	클러스터의 서버 사양이 다른 경우(새 인스턴스로 단계적 마이그레이션)	실시간 부하에 따라 반응할 필요가 있는 경우
Least Connections	요청 처리 시간이 크게 다른 경우(파일 업로드, long-polling)	여러 LB 인스턴스가 있을 때 상태 동기화 비용이 높은 경우
Least Response Time	빠른/느린 API가 섞여 있고 전체 latency를 최적화할 필요가 있는 경우	시스템이 작거나 안정적인 응답 시간 데이터가 부족한 경우
IP Hash / Consistent Hashing	Sticky session, 캐시 지역성, 클라이언트별 샤딩이 필요한 경우	서버가 빠르게 스케일 업/다운될 때(재매핑 오버헤드가 줄어들긴 했지만 여전히 있음)
Random / P2C	매우 큰 시스템이고 집중식 상태 추적 오버헤드를 피하고 싶은 경우	짧은 시간 동안 절대적으로 균등한 분배를 보장해야 하는 경우

6. 로드 밸런싱 설계 시 흔한 실수

• 동일하지 않은 워크로드에 Round Robin 사용: 일부 서버가 비용이 큰 요청을 받으면서 다른 서버는 유휴 상태가 되어 부하가 비대칭이 되고, 평균 모니터링으로는 발견 어려움(평균 CPU는 여전히 “정상”).
• NAT/프록시 뒤의 클라이언트에 IP Hash로 sticky session 구성: 여러 실제 클라이언트가 하나의 IP로 그룹화되어 한 서버가 비정상적인 부하를 받음. Layer 7의 쿠키 기반 sticky session을 대신 사용해야 합니다.
• 헬스 체크가 없거나 잘못됨: /health가 200 OK를 반환하지만 데이터베이스 연결은 확인하지 않아 서버가 LB 관점에서는 “살아있지만” 실제로는 요청을 처리할 수 없음.
• 스케일 인 시 connection draining 무시: 서버를 즉시 종료하면 처리 중인 요청이 손실됨. 기존 연결이 완료된 후(graceful shutdown) 풀에서 제거해야 합니다.
• LB 자체가 단일 장애점: 하나의 LB 인스턴스만 있으면 그것이 전체 시스템의 장애점이 됨. DNS 페일오버 또는 가상 IP(keepalived)를 사용하여 최소 2개의 LB 인스턴스가 필요합니다.

7. 결론

로드 밸런서는 단순히 “요청을 균등하게 나누는 것”이 아닙니다 — 올바른 알고리즘 선택은 워크로드의 특성에 따라 달라집니다: 서버가 동일한지, sticky session이 필요한지, 시스템이 집중식 상태 추적을 할 수 있는지 등. Round Robin과 Weighted Round Robin은 대부분의 간단한 경우에 적합하고, Least Connections과 Least Response Time은 동적 워크로드를 잘 처리하고, Consistent Hashing은 클러스터 변화 시에도 안정적으로 sticky session과 샤딩을 해결합니다. 알고리즘보다 더 중요한 것은 올바른 헬스 체크와 페일오버 구현이 실제 시스템 신뢰성을 결정한다는 점입니다.