6편: Spring Boot로 로드밸런서 직접 구현하기 — 나머지 4가지 알고리즘
5편에 이어서 Least Connections, Consistent Hashing, IP Hash, Least Response Time을 구현한다.
5편에서 Round Robin과 Weighted Round Robin을 구현하면서 동시성 제어의 기본기를 익혔다.
이번 편은 좀 더 복잡한 4가지 알고리즘이다. 각각 동시성을 다루는 방식이 다른데, 그 차이에 집중하면서 읽으면 좋다.
3.4 Least Connections
현재 활성 연결이 가장 적은 서버를 선택하는 알고리즘이다. 요청 처리 시간이 들쭉날쭉한 환경에서 Round Robin보다 훨씬 균등하게 부하를 분산한다.
@Override
public Server selectServer(List<Server> servers, String clientInfo) {
if (servers == null || servers.isEmpty()) {
throw new IllegalArgumentException("서버 목록이 비어있습니다.");
}
List<Server> healthyServers = servers.stream()
.filter(Server::isHealthy)
.toList();
if (healthyServers.isEmpty()) {
throw new IllegalStateException("사용 가능한 건강한 서버가 없습니다.");
}
// CAS 루프로 원자적 선택 + 증가
for (int retry = 0; retry < MAX_RETRIES; retry++) {
Server min = healthyServers.stream()
.min(Comparator.comparingInt(Server::getCurrentConnections)
.thenComparing(Server::getId))
.orElse(healthyServers.get(0));
int currentConnections = min.getCurrentConnections();
if (min.tryIncrementConnections(currentConnections)) {
return min;
}
}
// MAX_RETRIES 초과 시 폴백 처리
...
}CAS 루프 도입 — 락 없이 경합하기
Least Connections의 핵심 문제는 "최솟값 찾기"와 "연결 수 증가"가 하나의 원자적 연산이 아니라는 것이다.
순진하게 구현하면 이렇게 된다:
Server min = findMinConnectionsServer(); // 1. 최솟값 찾기
min.incrementConnections(); // 2. 증가문제는 1과 2 사이에 다른 스레드가 끼어들어 min 서버의 연결 수를 올려버릴 수 있다는 점이다. 그러면 "최솟값 서버에 연결"이라는 전제가 깨진다.
CAS(Compare-And-Swap)로 해결한다:
// Server 클래스 내부
public boolean tryIncrementConnections(int expected) {
// "현재 값이 expected와 같으면 +1하고 true 반환, 다르면 false 반환"
return connections.compareAndSet(expected, expected + 1);
}// CAS 루프
for (int retry = 0; retry < MAX_RETRIES; retry++) {
Server min = findMin(healthyServers); // 1. 최솟값 서버 찾기
int current = min.getCurrentConnections(); // 2. 현재 연결 수 기억 (예: 5)
if (min.tryIncrementConnections(current)) { // 3. CAS: "아직 5면 6으로"
return min; // 성공!
}
// 실패 = 다른 스레드가 먼저 바꿈 → 재시도
}동작 흐름을 보면 이렇다:
Thread A Thread B
-------- --------
min = server1 (연결수: 5)
min = server1 (연결수: 5)
CAS(5 → 6) 성공!
CAS(5 → 6) 실패! (이미 6이 됨)
→ 재시도: min = server1 (연결수: 6)
→ 또는 다른 서버가 최솟값이 됨
CAS 재시도 성공💡 팁: CAS는 "락 없이 경합"하는 방식이다.
synchronized처럼 대기하지 않고, 실패하면 그냥 다시 시도한다. 경합이 적을 때 훨씬 빠르다. 반대로 스레드가 매우 많고 경합이 극심하면 재시도가 계속 발생해서 오히려 느려질 수 있다. MAX_RETRIES를 두고 폴백 처리를 하는 이유가 여기에 있다.
3.5 Consistent Hashing
같은 클라이언트는 항상 같은 서버로 보내되, 서버가 추가/제거됐을 때 영향 범위를 최소화하는 알고리즘이다.
기본 필드 구성
private static final int VIRTUAL_NODES = 150;
// MD5 인스턴스를 스레드별로 분리
private static final ThreadLocal<MessageDigest> MD5_HOLDER = ThreadLocal.withInitial(() -> {
try {
return MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException(e);
}
});
// volatile로 원자적 참조 교체 (Copy-on-Write 패턴)
private volatile ConcurrentSkipListMap<Long, Server> hashRing = new ConcurrentSkipListMap<>();
private volatile boolean ringInitialized = false;서버 선택 로직
public Server selectServer(List<Server> servers, String clientInfo) {
// fast-path: 대부분의 요청은 여기서 끝남 (락 없음)
if (!ringInitialized || needsRebuild(servers)) {
rebuildIfNeeded(servers);
}
ConcurrentSkipListMap<Long, Server> currentRing = this.hashRing;
long clientHash = hash(clientInfo);
// 시계방향으로 가장 가까운 서버 찾기
Map.Entry<Long, Server> entry = currentRing.ceilingEntry(clientHash);
if (entry == null) entry = currentRing.firstEntry(); // 링의 끝 → 처음으로
return entry.getValue();
}
private synchronized void rebuildIfNeeded(List<Server> servers) {
// slow-path: 재구성이 필요할 때만 진입
if (!ringInitialized || needsRebuild(servers)) {
buildHashRing(servers);
}
}Virtual Node가 필요한 이유
서버 4개만 해시 링에 배치하면 이런 문제가 생긴다:
해시 링 (0 ~ 2^64)
server1 (hash: 1000)
|
server4 ---+--- server2
(hash:8000) (hash: 3000)
|
server3 (hash: 5000)담당 범위를 보면:
- server1: 8001 ~ 1000 (1000 구간)
- server2: 1001 ~ 3000 (2000 구간)
- server3: 3001 ~ 5000 (2000 구간)
- server4: 5001 ~ 8000 (3000 구간)
서버마다 담당 범위가 전혀 다르다. server4는 server1의 3배 트래픽을 받는다.
가상 노드로 해결한다:
for (int i = 0; i < VIRTUAL_NODES; i++) {
String virtualNodeKey = server.getId() + "#" + i;
long hash = hash(virtualNodeKey);
hashRing.put(hash, server);
}서버 1개당 150개 가상 노드를 링 전체에 뿌린다. 4개 서버 × 150개 = 600개 포인트가 링에 고르게 분산되면, 자연스럽게 각 서버가 25%씩 담당하게 된다.
💡 팁: 가상 노드 수(150)는 많을수록 균등하지만, 해시 링 메모리와 초기화 비용이 늘어난다. 일반적으로 100~200 사이가 균형점이다. 서버 수가 매우 많다면 낮추고, 서버 수가 적다면 높이는 게 낫다.
MD5를 선택한 이유
hashCode()를 쓰면 안 될까?
"server1".hashCode() // 예: 1234567
"server2".hashCode() // 예: 1234568 ← 너무 가까움!비슷한 문자열은 비슷한 해시값을 가져서 링에서 뭉친다. 균등 분산이 깨진다.
MD5는 입력이 조금만 달라도 완전히 다른 결과를 낸다:
MD5("server1#0") → a3f2e8c1...
MD5("server1#1") → 7b9d4e2f... (완전히 다름)
MD5("server2#0") → e1c8a3b9... (완전히 다름)SHA-256도 좋은 분산을 보장하지만 MD5보다 느리다. 로드밸런싱에서 해시의 목적은 보안이 아니라 균등 분산이므로 MD5로 충분하다.
ConcurrentSkipListMap을 선택한 이유
링에서 필요한 핵심 연산은 두 가지다:
// 1. 시계방향으로 가장 가까운 서버 찾기
Map.Entry<Long, Server> entry = hashRing.ceilingEntry(clientHash);
// 2. 링의 끝에서 처음으로 돌아가기
if (entry == null) entry = hashRing.firstEntry();ceilingEntry(key) — "key 이상인 키 중 가장 작은 엔트리 반환". 이게 O(log n)으로 동작하려면 내부가 정렬되어 있어야 한다.
ConcurrentHashMap은 정렬이 없어서 ceilingEntry 지원 자체가 안 된다. 전체 순회(O(n))로 구현해야 한다.
ConcurrentSkipListMap은 내부가 정렬된 동시성 자료구조다:
Level 3: 1 ─────────────────────────────────→ 9
Level 2: 1 ───────────→ 5 ───────────────────→ 9
Level 1: 1 ────→ 3 ────→ 5 ────→ 7 ────────→ 9
Level 0: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9멀티레벨 구조 덕분에 탐색 시 많은 노드를 건너뛸 수 있다. ceilingEntry, firstEntry 모두 O(log n)으로 동작한다.
ThreadLocal로 MD5 인스턴스 분리
MessageDigest는 stateless가 아니다. 내부에 계산 중간 상태를 가지고 있다:
md5.update(...) // 바이트 버퍼에 누적
md5.digest() // 중간값 계산 후 결과 반환여러 스레드가 같은 인스턴스를 공유하면:
Thread A Thread B
-------- --------
md5.reset()
md5.reset()
md5.update("abc")
md5.update("xyz")
md5.digest()
→ "abc"+"xyz" 섞인 이상한 해시값 반환재현하기 어렵고, 동일한 클라이언트가 매번 다른 서버로 보내지는 버그가 생긴다.
volatile이나 synchronized로 해결할 수도 있지만:
volatile: 원자성을 보장하지 않아서 복합 연산에는 부적합synchronized: 모든 요청이 MD5 인스턴스를 순서대로 사용해야 해서 병목
해결책은 공유 자체를 없애는 것이다:
private static final ThreadLocal<MessageDigest> MD5_HOLDER = ThreadLocal.withInitial(() -> {
try {
return MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException(e);
}
});
private long hash(String input) {
MessageDigest md5 = MD5_HOLDER.get(); // 이 스레드 전용 인스턴스
md5.reset();
md5.update(input.getBytes());
byte[] digest = md5.digest();
// ...
}스레드별로 MessageDigest 인스턴스를 따로 가지니 동기화가 필요 없다.
💡 팁: ThreadLocal은 스레드 풀 환경에서 메모리 누수를 일으킬 수 있다. 스레드 풀의 스레드는 재사용되기 때문에, 사용 후
remove()를 명시적으로 호출하지 않으면 이전 요청의 데이터가 다음 요청에 남아있게 된다. 이 구현에서는 매번reset()으로 내부 상태를 초기화하기 때문에 논리적 오염은 방지된다. 하지만 엄밀히 메모리를 돌려주고 싶다면 요청 처리 후MD5_HOLDER.remove()를 호출하는 게 맞다.try { return hash(input); } finally { MD5_HOLDER.remove(); // 엄격하게 관리할 경우 }
Copy-on-Write 패턴으로 링 재구성
링을 재구성할 때 단순하게 구현하면 이런 문제가 생긴다:
private void buildHashRing(List<Server> servers) {
hashRing.clear(); // ← 이 순간 빈 링!
addServer(server1); // ← 일부만 추가된 링
addServer(server2); // ...
}clear() 직후에 다른 스레드가 요청을 처리하면 빈 링에서 NullPointerException이 발생한다. 일부만 추가된 상태에서 접근하면 특정 서버에 트래픽이 몰린다.
Copy-on-Write로 해결한다. 기존 링은 건드리지 않고, 새 링을 완성한 뒤 참조만 교체한다:
Phase 1: 새 링 구성 (기존 링은 그대로 서비스 중)
┌───────────────┐ ┌───────────────┐
│ 기존 hashRing │ │ 새 newRing │
│ (서비스 중!) │ │ (구성 중...) │
│ server1: 100 │ │ server1: 100 │
│ server2: 200 │ │ server1: 150 │
│ server3: 300 │ │ server2: 200 │
└───────────────┘ │ ...구성 중...│
↑ └───────────────┘
Thread B가 여기서
계속 서비스 중
Phase 2: 참조만 교체 (원자적!)
this.hashRing = newRing; ← 한 줄로 완료코드로 보면:
private void buildHashRing(List<Server> servers) {
// 새 링을 별도로 구성 (기존 링은 서비스 중)
ConcurrentSkipListMap<Long, Server> newRing = new ConcurrentSkipListMap<>();
for (Server server : healthyServers) {
for (int i = 0; i < VIRTUAL_NODES; i++) {
String key = server.getId() + "#" + i;
newRing.put(hash(key), server);
}
}
// 원자적 교체
this.hashRing = newRing;
this.ringInitialized = true;
}volatile이 여기서 핵심이다. this.hashRing = newRing 이 한 줄이 다른 스레드에 즉시 보이도록 가시성을 보장한다. 동시에 JVM이 newRing.put() 연산들을 이 라인 뒤로 재정렬하는 것도 막아준다. 즉, hashRing이 새 링을 가리키는 순간 새 링은 반드시 완성된 상태다.
💡 팁: Copy-on-Write가 효과적인 조건은 읽기 >> 쓰기인 경우다. 로드밸런서는 딱 이 경우다. 링 조회(읽기)는 초당 수만 번, 링 재구성(쓰기)은 서버 상태 변경 시에만 발생한다. 변경이 드물면 복사 비용은 무시할 만하고, 대신 읽기에서 락이 전혀 없는 이점이 훨씬 크다.
Volatile + Synchronized 조합 설계
// fast-path: 락 없음 (대부분의 요청)
if (!ringInitialized || needsRebuild(servers)) {
rebuildIfNeeded(servers); // slow-path 진입
}
ConcurrentSkipListMap<Long, Server> currentRing = this.hashRing; // volatile read
long clientHash = hash(clientInfo);
Map.Entry<Long, Server> entry = currentRing.ceilingEntry(clientHash);읽기 경로에 락이 필요한지 생각해보자.
this.hashRing은 volatile이므로, 읽는 순간의 참조를 원자적으로 가져온다. 로컬 변수 currentRing에 저장하면 이 스레드는 이 링을 끝까지 사용한다. 중간에 hashRing이 새 링으로 교체되어도 상관없다. 이전 링이든 새 링이든 둘 다 완성된 상태이기 때문이다.
그래서 읽기에는 락이 불필요하다. rebuildIfNeeded()에만 synchronized를 붙여서 재구성이 한 번만 실행되도록 보장한다.
이 설계의 장점:
- fast-path (대부분의 요청): 락 연산 제로
- slow-path (재구성):
synchronized비용이 들지만 드물게 발생 - 버그 위험 낮음: 단순한 구조라 실수할 여지가 적음
💡 팁: 읽기마다
readLock().lock()을 거는ReadWriteLock방식과 비교해보면, 초당 10,000 요청에서 매번lock()/unlock()20,000번을 실행한다. 성능 차이가 분명히 난다. "락을 잘 쓰는 것"보다 "락이 필요 없는 구조를 만드는 것"이 더 나은 경우가 있다.
3.6 IP Hash
같은 IP에서 오는 요청은 항상 같은 서버로 보내는 알고리즘이다. 세션 데이터가 특정 서버에 저장된 환경에서 세션 일관성을 유지할 수 있다.
// 클라이언트 IP별 서버 매핑 캐시 (세션 지속성)
private final Map<String, String> ipServerMapping = new ConcurrentHashMap<>();
@Override
public Server selectServer(List<Server> servers, String clientInfo) {
// ...생략...
String clientIp = extractIpFromClientInfo(clientInfo);
// compute()로 캐시 확인 + 서버 선택 + 저장을 원자적으로 처리
String selectedServerId = ipServerMapping.compute(clientIp, (ip, cachedServerId) -> {
if (cachedServerId != null) {
boolean serverStillHealthy = healthyServers.stream()
.anyMatch(server -> server.getId().equals(cachedServerId));
if (serverStillHealthy) {
return cachedServerId; // 캐시 히트, 기존 서버 유지
}
// 캐시된 서버가 죽었으면 새로 선택
}
int hash = calculateHash(ip);
int serverIndex = Math.abs(hash) % healthyServers.size();
return healthyServers.get(serverIndex).getId();
});
// compute() 이후 서버 객체 조회 (방어적 처리)
Server selectedServer = healthyServers.stream()
.filter(server -> server.getId().equals(selectedServerId))
.findFirst()
.orElseGet(() -> {
// compute와 이 사이에 서버 상태가 변경된 극히 드문 케이스
ipServerMapping.remove(clientIp);
return healthyServers.get(0);
});
selectedServer.incrementConnections();
return selectedServer;
}compute()로 Check-then-Act 레이스 방지
IP Hash의 핵심 로직은 이렇다:
1. 이 IP에 대한 캐시가 있나?
2. 있으면 그 서버가 아직 살아있나?
3. 살아있으면 그 서버로, 아니면 새로 선택
순진하게 구현하면 레이스 컨디션이 생긴다:
String cached = ipServerMapping.get(ip); // 1. 읽기
if (cached != null) { // 2. 확인
// ...
} else {
ipServerMapping.put(ip, newServer); // 3. 쓰기
}1 → 2 → 3은 각각 thread-safe하지만, 연산 사이에 다른 스레드가 끼어들 수 있다:
Thread A Thread B
-------- --------
get("192.168.1.1") → null
get("192.168.1.1") → null
put("192.168.1.1", "server1")
put("192.168.1.1", "server2") ← 덮어씀!같은 IP인데 A는 server1으로, B는 server2로 보내게 됐다. 세션 일관성이 깨진다.
compute()로 해결한다. 해당 키에 대해 내부적으로 버킷 단위 락을 걸고 람다 전체를 원자적으로 실행한다:
Thread A Thread B
-------- --------
compute("192.168.1.1") 시작
└─ 버킷 락 획득
└─ 람다 실행 중...
compute("192.168.1.1") 시작
└─ 대기 중 (같은 버킷)
└─ server1 반환, 락 해제
└─ 락 획득
└─ cachedServerId = "server1" (A의 결과)
└─ server1 건강함 → server1 유지💡 팁:
compute()의 람다 안에서 무거운 작업을 하면 그 시간 동안 같은 버킷의 다른 키 접근도 블로킹된다. 람다는 가능한 짧고 빠르게 유지하는 게 좋다. 여기서healthyServers.stream().anyMatch()정도는 괜찮지만, DB 조회나 네트워크 호출 같은 건 절대 넣으면 안 된다.
3.7 Least Response Time
평균 응답시간이 가장 빠른 서버를 선택한다. 서버의 현재 상태를 가장 직접적으로 반영하는 알고리즘이다.
private static final double ALPHA = 0.3; // 지수 이동 평균 계수
private static final double INITIAL_RESPONSE_TIME = 1000.0;
private final Map<String, ResponseTimeStats> serverStats = new ConcurrentHashMap<>();
@Override
public Server selectServer(List<Server> servers, String clientInfo) {
// ...생략...
Server selectedServer = healthyServers.stream()
.min(Comparator.comparingDouble(this::getEffectiveResponseTime)
.thenComparing(Server::getId))
.orElseThrow();
selectedServer.incrementConnections();
return selectedServer;
}응답시간 관리 구조
응답시간을 두 곳에서 관리한다:
// 1. Server 객체 내부: 단순 이동 평균 (최근 10개)
server.recordResponseTime(responseTime);
server.getAverageResponseTime();
// 2. Strategy 내부 Map: 지수 이동 평균
Map<String, ResponseTimeStats> serverStats = new ConcurrentHashMap<>();두 방식을 조합해서 getEffectiveResponseTime()을 구성한다. 단순 평균은 슬라이딩 윈도우 안의 값들을 동등하게 취급하고, 지수 이동 평균은 최근 값에 더 높은 가중치를 부여한다.
지수 이동 평균(EMA) 계산:
// ALPHA = 0.3
weightedAverage = ALPHA * newResponseTime + (1 - ALPHA) * weightedAverage;기존 평균: 100ms
새 응답: 200ms
새 평균 = 0.3 × 200 + 0.7 × 100
= 60 + 70
= 130ms단순 평균은 과거 모든 값이 동등하게 영향을 줘서 오래된 데이터가 계속 잔류한다. EMA는 최근 값일수록 더 높은 가중치를 가지므로 서버 상태 변화에 빠르게 반응한다.
💡 팁: ALPHA 값(0.3)은 "반응 속도"를 결정한다. 높을수록(1에 가까울수록) 최근 응답시간에 민감하게 반응하고, 낮을수록(0에 가까울수록) 안정적이지만 변화 감지가 느리다. 서버가 일시적인 GC pause로 한 번 느려졌을 때 바로 트래픽이 몰리는 게 싫다면 낮추고, 빠른 장애 감지가 중요하다면 높이면 된다.
동시성 처리 포인트
ConcurrentHashMap으로 서버 통계 저장
private final Map<String, ResponseTimeStats> serverStats = new ConcurrentHashMap<>();일반 HashMap을 쓰면 여러 스레드가 동시에 접근할 때 내부 배열 구조가 깨져서 무한 루프, NPE, 데이터 손실이 발생할 수 있다.
computeIfAbsent로 원자적 초기화
private void updateWeightedAverage(String serverId, long responseTime) {
serverStats.computeIfAbsent(serverId, k -> new ResponseTimeStats())
.updateWeightedAverage(responseTime, ALPHA);
}get() 후 null 체크하고 put()하는 패턴은 레이스가 있다:
// 이렇게 하면 문제
if (serverStats.get(serverId) == null) { // Thread A: null 확인
serverStats.put(serverId, new Stats()); // Thread A: 저장
} // Thread B: 동시에 같은 작업
// → 두 개 생성, 하나 덮어씀
// computeIfAbsent는 "없으면 만들어서 넣기"가 원자적
serverStats.computeIfAbsent(serverId, k -> new ResponseTimeStats());ResponseTimeStats 내부에 synchronized
public synchronized void updateWeightedAverage(long newResponseTime, double alpha) {
if (!initialized) {
weightedAverage = newResponseTime;
initialized = true;
} else {
weightedAverage = alpha * newResponseTime + (1 - alpha) * weightedAverage;
}
requestCount++;
totalResponseTime += newResponseTime;
}같은 서버에 대한 응답시간 업데이트가 동시에 여러 스레드에서 발생할 수 있다. synchronized 없이는 두 스레드가 동시에 weightedAverage를 읽고, 각자 계산하고, 덮어쓰면 한 쪽 업데이트가 유실된다.
💡 팁: 이
synchronized는 메서드 단위 락이라 해당ResponseTimeStats객체 하나에만 영향을 준다.ConcurrentHashMap에 서버별로 별도 객체가 들어있으므로, server1 통계 업데이트와 server2 통계 업데이트는 서로 블로킹하지 않는다. 락 범위가 좁을수록 병렬성이 높아진다.
마치며
4가지 알고리즘을 구현하면서 쓴 동시성 기법을 정리하면:
| 알고리즘 | 핵심 동시성 기법 | 선택 이유 |
|---|---|---|
| Least Connections | CAS 루프 | 락 없이 원자적 선택+증가 |
| Consistent Hashing | ThreadLocal + Copy-on-Write | 해시 계산 병목 제거, 링 재구성 중 서비스 무중단 |
| IP Hash | compute() | 세션 캐시 접근의 Check-then-Act 레이스 방지 |
| Least Response Time | computeIfAbsent + synchronized | 서버별 독립 락으로 병렬성 확보 |
알고리즘마다 "어떤 레이스를 막을 것인가"가 달랐다. Least Connections은 잘못된 서버 선택을 막아야 했고, Consistent Hashing은 링 재구성 중 불완전한 상태 노출을 막아야 했다. 동시성은 제거 대상이 아니라 어디까지 허용하고 어디서 막을지 설계하는 것이라는 걸 다시 한번 실감했다.
다음 편에서는 K6로 6가지 알고리즘을 한꺼번에 부하 테스트하고 결과를 비교해보겠다.
