SFQ, Shuffle Sharding, Best-of-2: 분산 시스템의 공정성 확보 전략
SFQ(Stochastic Fairness Queuing)는 분산 시스템에서 노이즈 이웃(Noisy Neighbors) 문제를 완화하는 알고리즘임
O(1) 큐(Queues)와 O(1) 시간 복잡도(Time Complexity)를 통해 효율적인 자원 할당을 가능하게 함
Shuffle Sharding과 Best-of-2를 결합하여 노이즈 이웃으로부터의 격리(Isolation)를 강화함
댓글에서는 SFQ의 한계와 대안 제시, 특히 O(n) 메모리 사용량(Memory Usage) 문제를 지적함
SFQ(Stochastic Fairness Queuing)의 기본 원리
SFQ는 각 고객(Customer)의 워크로드를 확률적으로 격리하여 노이즈 이웃(Noisy Neighbors)의 영향을 줄이는 알고리즘이다. O(1) 큐(Queues)를 사용하며, 해시 함수(Hash Function)를 통해 고객을 고정된 큐 집합에 할당한다. 주기적으로 해시 함수를 변경하여 충돌(Collision)을 방지하고, 특정 고객이 과도하게 자원을 점유하는 것을 막는다. 이러한 방식은 네트워크 장비(Network Equipment)에서 트래픽 제어(Traffic Control)에 활용된다.
Shuffle Sharding 및 Best-of-2의 결합
SFQ는 Shuffle Sharding과 Best-of-2를 결합하여 노이즈 이웃 격리를 더욱 강화한다. 각 고객을 큐의 부분 집합에 매핑하고, 요청을 해당 부분 집합 내에서 가장 짧은 큐에 배치한다. 주기적인 부분 집합 변경을 통해 장기적인 불운(Long-term Bad Luck)을 방지한다. 이 접근 방식은 O(1) 큐, O(1) 인큐(Enqueue) 및 디큐(Dequeue) 작업을 보장하며, 노이즈 이웃으로부터의 강력한 격리를 제공한다.
SFQ의 한계와 대안
댓글에서는 SFQ가 네트워크 장비(Network Equipment)에는 적합하지만, 애플리케이션 개발자에게는 적합하지 않을 수 있다고 지적한다. 특히, 공정성을 유지하기 위해 필요한 큐의 수가 고객 수에 비례하여 O(n) 메모리(Memory)를 사용해야 하는 문제가 있다. 대안으로, 각 고객에 대한 토큰 버킷(Token Bucket) 기반의 속도 제한(Rate Limit)을 샘플링 제거 캐시(Sampling Eviction Cache)에 저장하는 방식이 제시되었다. 이 방식은 공정성을 유지하면서도 자동 스케일링(Automatic Scaling)을 가능하게 한다.
샘플링 제거 캐시(Sampling Eviction Cache) 기반의 속도 제한
샘플링 제거 캐시는 각 고객의 속도 제한을 관리하기 위한 효율적인 방법으로 제시되었다. 이 캐시는 사용자 정의 함수를 사용하여 항목의 유효성을 검사하며, 각 항목 추가 시 무작위로 선택된 키에 대해 소수의 제거 시도를 수행한다. 유효하지 않은 항목은 토큰이 가득 찬 속도 제한과 같이, 활성 요청에 의해 공유 잠금이 유지되지 않는 속도 제한이다. 이 방식을 통해 메모리 오버헤드(Memory Overhead)를 최소화하면서 캐시 내 유효한 요소의 높은 비율을 유지할 수 있다.
