HotOS IX 에 발표된 ‘Why Events Are A Bad Idea‘는 이벤트 기반 프로그래밍(event-based programming)에 비해 쓰레드 프로그래밍(thread programming)을 옹호하는 입장을 취하고 있는 논문 중의 하나다. 이 문서는 위 논문의 한글 요약이다.
1 Introduction
Highly concurrent application에 있어서 그동안 쓰레드를 사용한 시도들이 실패해왔기 때문에, 연구자들 사이에 이벤트 기반 프로그래밍이 쓰레드 프로그래밍에 비해 더 나은 선택이라고 결론 내려지고 있는데, 그 이유를 다음과 같이 요약하고 있다.
- cooperative multitasking으로 인해 synchronization cost가 저렴하다.
- state를 관리하기 위한 오버헤드가 낮다. (스택이 없음)
- appplication 수준의 정보를 이용하여 보다 나은 스케줄링과 locality를 얻을 수 있다.
- 보다 유연한 control flow.
이 논문의 기본적인 생각은
- 쓰레드가 Highly concurrent application에 대해 좀 더 자연스러운 abstraction을 제공하며,
- 컴파일러와 쓰레드 시스템 (패키지)의 약간의 개선을 통해서 쓰레드에 비해 이벤트를 사용해야만 했던 이유 (주로, 성능)가 없다는 것
을 지적하며, 쓰레드 프로그래밍이 이벤트 기반 프로그래밍에 비해 더 선호되어야 한다고 주장하고 있다.
2 Threads vs. Events
2.1 Duality Revisited
Lauer와 Needham은 ‘On the duality of operation system structures‘에서 쓰레드(threaded) 방식과 메시지 전달(message-passing, i.e., event-based) 방식은 대등하고 동등한 성능(equivalent performance)을 가지고 있기 때문에, 대상 애플리케이션에 더 자연스러운 방식을 선택해야한다고 주장한다. 이 논문의 저자는 (대상 애플리케이션이) high-concurrency server의 경우에는 쓰레드에 기반한 접근이 더 낫다고 생각한다.
저자는 Lauer와 Needham의 메시지 전달 시스템이 다음과 같은 점들에서 현재의 이벤트 시스템(modern event systems)과 정확하게 대응하지는 않는다고 얘기하고 있다.
- 이벤트가 synchronization을 위해 사용하는 cooperative scheduling을 무시하고 있다.
- 대부분의 이벤트 시스템들은 shared memory와 global data structure를 사용하고 있으나, Lauer와 Needham은 이것이 전형적이지 않은 (atypical) 것으로 표현하고 있다.
- Lauer와 Needham이 주장한 동등한 성능(performance equivalence)은 제대로 된(equally good) 구현을 필요로 한다. 저자는 very high concurency에 적합한 쓰레드 구현이 존재하지 않다고 생각한다.
동등한 성능을 주장함에 있어서 Lauer와 Needham은 blocking/yielding point가 node이고 그러한 point들 사이에서 실행되는 code가 edge인 그래프를 사용하고 있는데, 두 방식은 본질적으로 같은 그래프를 가지고 있다고 얘기하고 있다. 저자는 이러한 사실이 쓰레드의 성능과 사용성에 대한 비판이 특정한 쓰레드 구현의 문제에서 나온 것이지 일반적인 쓰레드에서 발생한 것이 아니라고 보고 있다.
2.2 “Problems” with Threads
이 섹션에서 저자들은 쓰레드에 관련된 비판을 하나씩 반박하고 있다.
Performance
Criticism: Many attempts to use threads for high concurrency have not performed well.
저자들은 좋지 않은 쓰레드 구현 때문이라고 주장한다. 특히 현재의 쓰레드 구현들은 high concurrency나 blocking operation를 위해 설계되지 않았다고 지적하고 있다.
쓰레드 구현에서의 오버헤드의 원인은
- 쓰레드의 수에 따른 O(n) operation의 존재와
- 이벤트에 비해 상대적으로 높은 context switch 오버헤드 (preemtion을 위한 context 저장 오버헤드와 커널 쓰레드의 커널 진입에 의한 오버헤드)
라고 한다.
저자들은 이러한 단점들은 역시 쓰레드의 기본적인 특성은 아니라고 얘기하고 있다. 저자들이, O(n) operation들을 대부분 제거한 GNU Pth user-level 쓰레드 구현을 사용한 SEDA 쓰레드 서버 벤치마크를 반복해본 결과, 10만개의 쓰레드에 대해서도 충분히 scale하며, 성능도 이벤트 기반 서버와 거의 동등하다고 한다.
Control Flow
Criticism: Threads have restrictive control flow.
쓰레드를 사용하는 프로그래머는 control flow에 대해 너무 linear하게 생각하므로 효율적인 control flow 패턴을 사용하지 못한다는 주장에 대해, 저자들은 복잡한 control flow 패턴은 실제로는 드물다고 얘기하고 있다. 저자들이 실제 애플리케이션들의 코드 구조를 분석한 결과 control flow 패턴은 call/return, parallel calls, pipelines의 세가지로 떨어진다고 한다. 그리고 이 패턴들은 쓰레드로 보다 자연스럽게 표현할 수 있다.
저자들은 이보다 복잡한 패턴들은 제대로 사용하기가 어렵기 때문에 사용되지 않는다고 주장한다. 이벤트 시스템에서 자주 일어나는 비본질적인 비선형성은 애초에 이해하기 힘들며, 미묘한 에러가 발생하기 쉽게 만든다고 한다. 의도적인 복잡한 control flow도 마찬가지라고 한다.
multicast나 publish/subscribe 애플리케이션에서 사용되는 dynamic fan-in/fan-out 패턴은 쓰레드보다는 이벤트 시스템과 더 잘 어울리는데, 조사한 high concurrency 서버들에서는 어떤 서버도 이 패턴을 사용하지 않았다고 한다.
Synchronization
Criticism: Thread synchronization mechanisms are too heavyweight.
이벤트 시스템은 cooperative multitasking으로 인해서 synchronization을 위한 mutex 등의 오버헤드가 없다고 여겨지나, Adya 등은 Cooperative task management without manual stack management에서 이러한 장점은 이벤트 자체에서 얻어지는 것이 아니라 cooperative multitasking에 있다고 한다. 따라서, cooperative 쓰레드 시스템에서도 같은 이득을 볼 수 있다. 하지만, 이러한 이득은 단일 프로세서에서만 얻어지는 것이고 일반적으로 high concurrency 서버들이 실행되는 다중 프로세서에서는 얻을 수 없는 것이다.
State Management
Criticism: Thread stacks are an ineffective way to manage live state.
쓰레드 시스템은 stack overflow와 virtual address space 사이의 tradeoff 문제를 가지고 있다. 저자들은 dynamic stack growth를 사용해서 이 문제를 해결할 것을 제안한다. 이벤트 시스템의 경우 쓰레드를 거의 사용하지 않으므로 이러한 문제가 없지만, live state의 관리를 프로그래머가 모두 직접해주어야 한다. 반면, 쓰레드 시스템은 stack을 통한 자동적인 관리가 이루어진다.
Scheduling
Criticism: The virtual processor model provided by threads forces the runtime to be too generic and prevents it from making optimal scheduling decisons.
이벤트 시스템은 애플리케이션 레벨에서 이벤트를 스케줄링할 수 있으므로 몇가지 최적화가 가능할 것이다. 또한, Larus와 Parkes에 의하면, Using cohort sched
uling to enhance server perf
ormance에서는 같은 종류의 이벤트를 한번에 처리함으로써 code locality를 개선함으로써 얻는 이익도 있을 수 있다고 한다. 하지만, 이러한 모든 이점들은 cooperatively scheduled threads를 사용함으로써 똑같이 얻을 수 있는 것들이다.
2.3 Summary
쓰레드도 high concurrency에 대해 적어도 이벤트 만큼 성능을 낼 수 있으며 이벤트에 중요한 질적인 이점은 없다. 이벤트 스타일을 많이 추구하게 된 것은 쓰레드의 기본적인 특성이라기보다는 scalable한 user-level 쓰레드가 없었기 때문이다.
3 The Case for Threads
다음의 두가지 이유에 기반하여 쓰레드가 high-concurrency 서버에 보다 적합한 abstraction이라고 얘기하고 있다.
- 동시에 발생하는 request는 거의 독립적이다.
- 각각의 request를 다루는 코드는 보통 순차적이다.
Control Flow
High-concurrency 시스템들에서 이벤트 기반 프로그래밍은 애플리케이션의 control flow을 이해하기 힘들게 만든다. 이벤트 시스템에서는 이벤트를 다른 모듈에 보냄으로써 어떤 메서드를 “call”하고, 그 메서드에서의 “return”을 기대한다. 프로그래머는 마음속으로 이러한 call/return pair를 파악하고 있어야한다. 더구나 프로그래머는 call/return pair를 위해 live state를 저장하고 복구해주어야 한다. Adya는 이를 “stack ripping”이라고 부르는데, 이벤트 시스템을 사용하려는 프로그래머의 가장 큰 부담이라고 얘기한다.
쓰레드 시스템에서는 control flow나 state를 좀 더 자연스러운 방식으로 표현할 수 있다. call과 return은 문법적으로 grouping이 되므로 1:1의 인과 관계를 이해하기 쉽고, call stack이 모든 live state를 encapsulate한다.
Exception Handling and State Lifetime
예외 상황 또는 정상적인 종료 이후, task의 state를 clean up하는 것은 쓰레드 시스템에서 더욱 간단하다. 이벤트 시스템에서는 task state가 일반적으로 heap에 할당되어 있기 때문에, control flow가 분기를 통해 복잡해지면, 적절한 시점에 이를 지우는 것은 매우 힘들다. Ninja난 SEDA와 같은 이벤트 시스템에서는 이 문제를 해결하기 위해 garbage collection을 사용하지만, Java의 general-purpose garbage collection 메커니즘은 high-performance 시스템에 부적합하다고 한다. Inktomi의 Traffic Server는 reference counting을 사용하고 있지만 정확한 counting은 어렵다고 한다.
Existing Systems
저자들이 만든 Ninja 시스템은 recovery와 같은 복잡한 부분에서 이벤트를 사용해 정확한 동작을 얻기가 거의 불가능했기 때문에, 결국 쓰레드를 사용했다고 한다. 이 외에도 high concurrency를 필요로 하지 않는 애플리케이션은 항상 쓰레드를 사용하고 있다.
Just Fix Events?
쓰레드를 사용하는 대신 이벤트 시스템의 문제를 해결하는 도구와 언어를 만들어야한다는 주장은 결국 쓰레드의 문법과 run-time behavior를 복제할 뿐이다. Adya가 기술한 cooperative task management 기술은 이벤트 시스템의 사용자로 하여금 쓰레드와 같은 코드를 쓰게 하고, 이것이 blocking call들 사이의 continuation으로 변환되도록 한다. 결국 대부분의 경우 이벤트의 문제를 수정하는 것은 쓰레드로 전환하는 것과 같다.
4 Compiler Support for Threads
4.1 Dynamic Stack Growth
run time에 stack의 크기가 조정될 수 있도록 하는 메커니즘을 통해 고정된 크기의 스택 때문에 stack overflow와 address space의 낭비 사이에서의 tradeoff 문제를 제거할 수 있다. compiler의 분석을 통해서 각각의 function을 호출할 때 필요한 stack 크기에 대한 upper bound를 알 수 있으므로 호출하는 곳에서 stack growth가 필요한가도 판단할 수 있다. recursive function이나 function pointer가 추가적인 문제를 던져주지만 이것도 추가적인 분석을 통해 해결할 수 있다.
4.2 Live State Management
function 호출을 하기전에 컴파일러가 불필요한 state를 쉽게 제거할 수 있다. (e.g. tail call optimization) 하나의 blocking call에 많은 양의 state가 걸려있다면 컴파일러가 프로그래머에게 경고해줄 수 있다.
4.3 Synchronization
컴파일 시간의 분석을 통해 프로그래머에게 race condition을 경고해줌으로써 버그를 줄일 수 있다. TinyOS에 기반한 networked sensor를 위한 언어인 nesC는 atomic section에 대해 지원하고 concurrency model에 대해서 이해한다. atomic section이 동시에 수행되어도 안전한지를 결정하는데 도움을 줄 수도 있다. 다중 프로세서에 대해서도 마찬가지고 libasync에서 직접 코딩한 graph coloring 기술을 자동화하는 것이다.
5 Evaluation
<생략>
6 Relative Work
<생략>
7 Conclusions
이벤트 시스템이 high concurrent 시스템에서 좋은 성능을 얻는데 사용되어왔지만, 쓰레드를 사용해서 비슷하거나 더 나은 성능을 얻을 수 있다. 간단한 프로그래밍 모델과 더 나은 컴파일러 분석이 가능하다는 점은 쓰레드에 중요한 이점을 제공한다. 저자들은 컴파일러와 쓰레드 시스템의 결합을 통해서 더욱 뛰어난 성능을 얻는 동시에 깔끔하고 간단한 인터페이스를 가진 프로그래밍 모델을 프로그래머에게 제공해줄 수 있을 것이라고 주장한다.