[SOSP '23] Achieving Microsecond-Scale Tail Latency Efficiently with Approximate Optimal Scheduling

 
Title : Achieving Microsecond-Scale Tail Latency Efficiently with Approximate Optimal Scheduling
Author: Rishabh Iyer, Musa Unal, Marios Kogias, George Candea
Published: SOSP 2023
[ paper | github ]
 

---

Abstract

- 데이터센터 application은 workload 수요가 많아짐에 따라 microsecond-scale service times와 tightly bound tail latency를 원하지만 최신 실행시간은 이론적으로 최적의 스케줄링 정책(single queue & strict preemption)을 따르고 있어서 challenge가 존재한다.

- 논문에서 제안하는 Concord는 기존의 디자인 변경과 그 디자인을 밀접하게 근사화함으로써 성능을 향상하면서 중요한 SLO 목표를 충족시키는 런타임 시스템이다.
 
- Concord는 tail latency SLO를 만족시키면서 microbenchmarks에서 처리량을 최대 52% 향상하고 Google's LevelDB KVS에서 최대 83% 향상한다. 
 
- Concord는 비표준적인 하드웨어 환경에 의존하지 않고, 바로 공용 클라우드에 배포할 수 있다.
 

Introduction

엄격한 tail-latency SLO는 시간이 지남에 따라 더 엄격해질 것이다. (by 미세한 마이크로서비스 모듈화 & 특수 하드웨어에 오프로드된 통신스택) 
 
✔️ 문제 : 최첨단 microsecond-scale scheduler는 2가지 조건을 지원해야 한다. (tail-optimized microsecond-scale systems)
(1) heavy-tailed workload에 대한 PS(Processor Sharing)를 구현하기 위한 preemptive scheduling
(2) a single queue 
 
→ 위 조건을 만족하려면 처리량을 희생해야한다.(preemptive scheduling은 처리량 penalty가 발생하고, single queue는 tail latency가 증가한다.)
 
→ 위 조건은 deployability와 generic 지원을 희생해야 한다.
(위 조건에 해당하는 Shinjuku [36]는 조건에 만족하는 대신 public cloud에 deploy가 불가능하다. Persephone [19]는 서비스 시간 분포에 대한 사전 지식이 필요하며, 이는 사전에 알려진 서비스 시간 분포가 서로 겹치치 않는 요청 클래스를 필요로 한다. 하지만 이는 사전 지식 없이 일반적인 정책이 필요한 데이터센터에는 불필요하다.)
 
✔️ 해결 : Concord

Figure 4. The Concord architecture. Concord의 강제적인 컴파일러 협동은 dedicated cache line을 통해서 dispatcher와 worker thread 간 통신하도록 한다. JBSQ는 Bounded loacal queue에서 일관성 지연을 제거하고 dispatcher는 부하가 높을 때 work를 global single queue로부터 훔쳐와서 throughput 향상에 기여한다.

 
(1) a schediling runtime for microsecond-scale application
(2) improved trade-off between tail latency and throughput without sacrificing deployability or generality
 
key insight : "careful approximation"
새로운 microsecond mechanisms을 가능하게 하는 최적의 스케줄링 policies →  상당한 처리량을 제공하면서 tail-latency cost는 무시할 정도이다. (기존의 policy를 변경시키고 새로운 mechanism을 도입하여 기존의 policy(조건 2가지)와 근사화한다.)
 

Three mechanism (Design)

효율적으로 최적의 정책을 근사화하기 위해서 세 가지 mechanism을 도입한다.

1. compiler-enforced cooperation

요약 : Dispatcher와 worker threads 간에 비동기 통신을 사용하여 정확한 preemption을 근사화한다. 비동기 통신은 약간 부정확한 scheduling quanta가 있지만 이 문제는 tail latency에 상당한 영향을 미치지 않는다. 부정확한 scheduling quanta가 있음에도 불구하고 비동기 통신은 런타임 오버헤드는 낮추고 선점 알림 오버헤드는 최소화함으로써 preemption overhead를 4배 감소가 가능하다.
 

- 비동기 통신은 여러 작업이 동시에 실행되고 서로 간섭하지 않기 때문에 작업 간의 context switch가 최소화된다. 또한 작업이 독립적으로 실행될 수 있게 하여, 다른 작업을 기다리는 시간을 줄일 수 있다.

 

- scheduling quanta : 다른 프로세스가 실행될 수 있도록 선점되거나 중단되기 전에 프로세스가 CPU에서 실행되도록 허용되는 고정된 시간을 나타낸다. 즉, 선점되지 않고 실행될 수 있는 프로세스에 할당된 시간.

 
Concord의 compiler-enforced cooperative scheduling은 IPI에 대한 낮은 오버헤드 대안을 제공한다. IPI는 Inter-processor interrupt로, Concord는 dispatcher와 worker thread 간의 통신에 인터럽트를 사용하지 않고 전용 캐시 라인을 활용하여 오버헤드를 최소화하고 효율성을 향상시킨다.
 
what?
(1) microscalesecond-scale taks를 위해 낮은 오버헤드에서 preemption이 가능해야 함
(2) 비표준 하드웨어가 아닌 public cloud에서 배치가 되어야 함
(3) 쉽게 application을 port 하고 안전하게 선점할 수 있어야 함
 
How?
- 자동화된 컴파일러 장비로 dispatcher와 worker thread 간의 통신을 보장한다. (poll-mode CPU drivers)
- concord's compiler instrumentation : 컴파일러를 사용하여 컴파일된 프로그램에 추가 코드를 자동으로 삽입하는 기술
- dispatcher는 작업 실행 시간을 모니터 하고 qunata의 끝을 나타내기 위해 cache line에 write를 수행한다. worker thread는 주기적으로 cache line에서 preemtion 신호를 확인하는데, 신호를 받으면 worker thread는 양보하고 현재 context를 저장 후 기본 context로 전환한다. dispatcher는 preemption 된 작업을 다시 main queue에 넣는다.
 
why?
preemption notification 비용은 코어 간의 빠른 통신을 활용하여 최소화한다. 캐신 라인을 확인할 때 측정 표준인 rdtsc 호출과 달리 지연이 증가하지 않는다. 또한 선점은 즉각적으로 이루어지지 않으며 퀀텀이 작은 간격 내에서 이루어지기만 한다면 tail latency에 영향을 상당히 미치지 않는다.
 

2. Stall-Free Workers

요약 : JBSQ scheduling은 single queue를 근사화하기 위해서 bounded code local queue를 추가한다. Concord는 cnext를 거의 제거하여 worker thread의 cache-coherence stall을 9-13배 줄입니다. cnext는 다음 요청이 기다리는 동안 발생하는 cost이다. (모든 프로세스가 일관된 메모리 뷰를 볼 수 있도록 일관되게 하기 위한 작업의 시간을 줄이는 것이다. 즉, 공유 데이터에 대한 액세스 충돌을 해결하기 위해서 캐시 일관성 프로토콜을 기다려야 하기 때문에 지연이 발생하는데 이 시간을 줄이도록 하는 것이다.)
 
why JBSQ(K)?
- worker thread가 idle 상태에 따른 오버헤드를 없애기 위해서 최적의 singlq queue policy를 포기하고 JBSQ(k) 사용.
 
what is the JBSQ(k)?
- 하나의 central queue와 각각이 최대 k개의 메시지로 제한된 짧고 유한한 worker별 queue를 결합하여 이상적인 work-conversing을 근사화한다.
- JBSQ(1) == single queue
 
How?
- main queue에 대기 중인 요청이 있고 하나 이상의 worker별 queue에 빈 슬롯이 있을 때 dispatcher는 요청을 가장 짧은 worker별 queue로 푸시한다.
- 이렇게 하면 worker thread는 요청을 처리한 후 즉시 local queue에서 새로운 요청을 처리할 수 있으니까 idle 시간이 제거된다.
- k는 충분히 큰 값이어야 하는데, 그 이유는 디스패서-워커 스레드 통신 중에 워커가 idle 상태가 되지 않도록 위해서이다.
- k=2가 충분하다. 무시할 만한 tail-latency penalty를 가지기 때문이다. (single queue와 비교했을 때)
 

3. Work-Conserving Dispatcher

요약 : 사용 가능한 리소스를 적극적으로 작동시켜 idle 시간을 최소화하기 위해서 dispatcher가 work-conserving 하고, 모든 worker thread가 바쁠 때 global single queue로부터 work를 미리 가져와서 worker thread에게 preemption notification을 보낸다.
 
dispatcher는 rdtsc() -based code instrumentation을 활용한다. 이는 외부 에이전트가 dispatcher에 preemption 신호를 보낼 수 없기 때문에 필요하며, 이에 따라 self-preemption 할 수 있어야 한다.
 
- 두 가지 instrumented version of the application code
1) rdtsc() -based instrumentation : only used for the dispatcher thread
2) the cache-line polling : used on the worker thread
 
→ 두 가지 다른 버전의 코드를 사용하기 때문에 single queue에 약간의 수정이 필요하다. dispatcher와 worker thread는 각자의 요청만 처리할 수 있다. (dispatcher에 의해 처리된 요청은 worker에 의해 처리될 수 없다. 반대도)
→  dispatcher는 전형적인 worker보다 효과적이지 않으며 요청이 평소의 서비스 시간보다 2.5배 더 걸린다. 하지만 이는 요청이 대기하지 않도록 하고 worker 간에 이동을 방지하여 전체 시스템 대기 시간을 줄이는 데 도움이 되기 때문에 중요한 역할을 한다.
→ 이는 기존에 전형적인 tail slowdown의 목표가 서비스 시간의 20배~50배임을 생각하면 2.5배의 추가 처리 시간이 발생하더라도 더 나은 성능을 제공함을 알 수 있다.
 

Conclusion

논문에서는 approximating tail-optimal scheduling polices가 µs-scale applications에서 상당한 처리량을 이끌어냄을 입증하였다. 또한 오버헤드를 줄이기 위한 세 가지 메커니즘을 제공하였다.
 

Referances

[19] Demoulin, H. M., Fried, J., Pedisich, I., Kogias, M., Loo, B. T., Phan, L. T. X., and Zhang, I. When Idling is Ideal: Optimizing Tail-Latency for Heavy-Tailed Datacenter Workloads with Perséphone. In Symposium on Operating Systems Principles (2021).
[36] Kaffes, K., Chong, T., Humphries, J. T., Belay, A., Mazières, D., and Kozyrakis, C. Shinjuku: Preemptive Scheduling for 𝜇second-scale Tail Latency. In Symposium on Networked Systems Design and Implementation (2019).