2026-05-13
개요
카테고리 검수 작업을 여러 검수자(Inspector)에게 자동으로 할당해야 하는 요구사항이 있었습니다.
처음에는 단순 Round Robin(RR)을 고려했지만, 검수자별 처리 capacity가 다르다는 점에서 적합하지 않았습니다. 가중치를 반영하는 Weighted Round Robin(WRR)으로 넘어가면 capacity 문제는 해결됩니다. 다만 단순 WRR은 weight 비율을 맞추기 위해 같은 노드를 weight만큼 연속으로 뽑은 뒤 다음 노드로 넘어가는 방식이라, weight 5:1인 두 검수자가 있다면 A, A, A, A, A, B처럼 같은 사람에게 작업이 몰리는 burst 현상이 발생합니다. weight=5는 '5배 자주 처리한다'는 의미일 뿐 '5개를 동시에 처리한다'는 뜻이 아니므로, A의 큐에는 작업이 5개 쌓이는 동안 B는 놀고 있게 됩니다. 그 결과 결제 이벤트별로 검수 완료까지 걸리는 시간이 크게 벌어지고(즉시 처리 vs 앞 작업 대기), 검수자 각자의 부하도 고르게 퍼지지 않습니다.
결국 weight 비례 선택과 균등 분산 두 가지를 모두 만족하는 Smooth Weighted Round Robin(SWRR) 알고리즘을 도입했습니다. 이 글에서는 SWRR의 동작 원리, Kotlin 구현, 그리고 운영 환경에서 마주친 고민들을 정리합니다.
본문
RR vs WRR vs SWRR 비교
세 가지 라운드 로빈 알고리즘의 차이를 정리하면 다음과 같습니다.
알고리즘 | weight 반영 | 분산 품질 | 선택 패턴 (A:2, B:1) |
Round Robin (RR) |  | 균등 | A, B, A, B, A, B |
Weighted Round Robin (WRR) | | 편중 (burst) | A, A, B, A, A, B |
Smooth Weighted Round Robin (SWRR) | | 균등 (smooth) | A, B, A, A, B, A |
WRR의 핵심 문제는 weight만큼 같은 노드를 연속해서 선택한다는 점입니다. weight가 작으면 티가 안 나지만, weight=10인 검수자가 있다면 10번 연속으로 같은 사람에게만 작업이 가는 burst가 발생합니다.
SWRR은 매 라운드마다 weight를 누적시켜 가장 높은 누적값을 가진 노드를 선택하므로, 결과적으로 weight 비율은 동일하게 유지되면서도 선택은 시간축으로 고르게 분산됩니다.
SWRR 알고리즘 동작 방식
SWRR은 "포인트 적립/사용" 비유로 이해하면 직관적입니다.
각 Inspector는 currentWeight(현재 포인트)를 가지며, 매 선택마다 다음 3단계를 수행합니다.
•
적립: 모든 Inspector의 currentWeight에 자신의 weight만큼 더한다
•
선택: currentWeight가 가장 높은 Inspector를 선택한다
•
차감: 선택된 Inspector의 currentWeight에서 totalWeight(모든 weight의 합)를 뺀다
이 단순한 규칙만으로 weight 비율 보장과 균등 분산이 동시에 이루어집니다. Inspector 3명 (철수 weight=5, 영희 weight=3, 민수 weight=1, totalWeight=9)으로 9라운드 시뮬레이션을 돌려보면 다음과 같습니다.
라운드 | 적립 후 currentWeight | 선택 | 차감 후 currentWeight |
1 | 철수=5, 영희=3, 민수=1 | 철수 | 철수=-4, 영희=3, 민수=1 |
2 | 철수=1, 영희=6, 민수=2 | 영희 | 철수=1, 영희=-3, 민수=2 |
3 | 철수=6, 영희=0, 민수=3 | 철수 | 철수=-3, 영희=0, 민수=3 |
4 | 철수=2, 영희=3, 민수=4 | 민수 | 철수=2, 영희=3, 민수=-5 |
5 | 철수=7, 영희=6, 민수=-4 | 철수 | 철수=-2, 영희=6, 민수=-4 |
6 | 철수=3, 영희=9, 민수=-3 | 영희 | 철수=3, 영희=0, 민수=-3 |
7 | 철수=8, 영희=3, 민수=-2 | 철수 | 철수=-1, 영희=3, 민수=-2 |
8 | 철수=4, 영희=6, 민수=-1 | 영희 | 철수=4, 영희=-3, 민수=-1 |
9 | 철수=9, 영희=0, 민수=0 | 철수 | 철수=0, 영희=0, 민수=0 |
9라운드의 결과는 철수 5번, 영희 3번, 민수 1번으로 정확히 weight 비율과 일치합니다. 동시에 같은 Inspector가 연속으로 선택되는 경우가 거의 없고, 9라운드 후에는 모든 currentWeight가 0으로 돌아와 다음 사이클을 깔끔하게 시작합니다.
Kotlin으로 구현하기
3단계 규칙이 코드에 거의 그대로 매핑됩니다.
@Service
class SelectInspectorSWRRService(
private val inspectorQueryOutputPort: InspectorOutputPort,
) : SelectInspectorUseCase {
private val lock = ReentrantReadWriteLock()
private var inspectorStates: MutableList<InspectorState> = mutableListOf()
private var totalWeight: Int = 0
private var lastRefreshTime: Instant = Instant.MIN
companion object {
private const val CACHE_TTL_SECONDS = 60L
}
override fun selectNext(): String {
return lock.write {
ensureCacheValid()
if (inspectorStates.isEmpty()) {
throw NoActiveInspectorException()
}
// 1. 적립: 모든 Inspector의 currentWeight += weight
inspectorStates.forEach { it.currentWeight += it.weight }
// 2. 선택: 가장 높은 currentWeight를 가진 Inspector
val selected = inspectorStates.maxBy { it.currentWeight }
// 3. 차감: currentWeight -= totalWeight
selected.currentWeight -= totalWeight
selected.inspectorId
}
}
private data class InspectorState(
val inspectorId: String,
val weight: Int,
var currentWeight: Int,
)
}
Kotlin
복사
상태는 InspectorState data class로 캡슐화했고, 동시 접근 보호를 위해 ReentrantReadWriteLock으로 감쌌습니다. 알고리즘 코어는 단 3줄(forEach, maxBy, -=)이라 의도가 한눈에 읽힙니다.
운영 환경에서의 고민
알고리즘 자체는 단순하지만, 실제 운영에 올리면 몇 가지 고민거리가 생깁니다.
•
Pod별 독립 동작 (eventual consistency): Redis 같은 외부 저장소를 두지 않고 각 Pod가 자체 in-memory 상태를 유지합니다. 인프라가 단순해지는 대신, 짧은 윈도우에서는 Pod별로 약간씩 다른 선택이 일어날 수 있습니다. 검수 작업 분배는 일정 시간만 지나면 통계적으로 수렴하므로 이 정도 trade-off는 허용 가능했습니다.
•
Thread Safety: 여러 스레드가 동시에 selectNext()를 호출해도 일관된 상태를 유지하도록 ReentrantReadWriteLock으로 보호했습니다.
•
60초 TTL 캐시: Inspector 목록을 매번 DB에서 조회하면 비용이 큽니다. 60초 TTL로 캐시하고 만료 시에만 재조회하며, 즉시 반영이 필요한 경우 refreshInspectors()를 수동 호출합니다.
가장 까다로웠던 건 Pod 재시작 시 편중 문제였습니다. SWRR은 초기 currentWeight가 모두 0이라서, 첫 라운드는 weight가 가장 높은 Inspector가 항상 선택됩니다. Pod가 자주 재시작되거나 캐시가 갱신될 때마다 가장 weight 높은 Inspector에게 작업이 쏠리게 되죠.
이를 해결하기 위해 Warm-Up 단계를 추가했습니다.
private fun warmUp() {
if (inspectorStates.isEmpty()) return
val skipCount = Random.nextInt(inspectorStates.size)
repeat(skipCount) {
inspectorStates.forEach { it.currentWeight += it.weight }
val selected = inspectorStates.maxBy { it.currentWeight }
selected.currentWeight -= totalWeight
}
}
Kotlin
복사
loadInspectors() 직후 Random.nextInt(inspectorStates.size)만큼 SWRR을 공회전시켜 시작 위치를 무작위화합니다. SWRR은 이미 균등 분산되어 있으므로 별도의 수렴 시간 없이 즉시 효과가 적용됩니다.
Warm-Up이 가능한 이유는 SWRR의 상태가 결정적(deterministic) 이기 때문입니다. 같은 weight 집합에서 N번 호출 후의 상태는 항상 동일하므로, "랜덤하게 N번 미리 돌려두는" 것만으로 시작 위치를 효과적으로 분산할 수 있습니다.
테스트로 검증한 것들
SWRR은 결정적이라 테스트하기 좋습니다. 다음 4가지 시나리오를 단위 테스트로 검증했습니다.
•
weight 비례 선택: weight 5:1 Inspector를 6번 호출하면 정확히 5:1로 분배
•
균등 weight 균등 분산: weight 1:1:1을 9번 호출하면 각 3번씩
•
smooth 분산 검증: weight 2:1에서 12회 호출 시 연속 선택 횟수가 2를 넘지 않음
•
동시성: 멀티스레드 환경에서 동시 호출해도 weight 비율이 유지됨
weight 비례와 smooth 분산은 SWRR의 두 가지 핵심 보장이므로, 두 속성을 모두 테스트로 가두는 게 중요했습니다.
사용 시 주의사항
•
weight = 0인 Inspector는 선택 대상에서 제외됩니다. 일시 휴직 처리하고 싶다면 weight를 0으로 두면 됩니다.
•
Inspector 변경 즉시 반영이 필요하다면 refreshInspectors()를 수동 호출해야 합니다. 그렇지 않으면 최대 60초 동안 예전 목록으로 동작합니다.
•
Pod 재시작 직후 짧은 윈도우에서는 통계적 편차가 발생할 수 있습니다. Warm-Up으로 완화되지만 완전 제거는 불가능합니다. 분배 정확도가 더 중요하다면 Redis 기반 공유 상태로 이전을 검토할 수 있습니다.
SWRR은 상태 기반 알고리즘이라 Inspector를 추가/제거할 때 기존 상태를 보존할지 초기화할지 결정해야 합니다. 현재 구현은 refreshInspectors() 호출 시 currentWeight를 모두 0으로 초기화하고 Warm-Up으로 시작 위치만 분산시킵니다.