Prefer Multithreading to Event-driven in Highly-Concurrent Servers

Introduction

‘서버를 만들 때 Multithreading을 사용해야하는가 아니면 Event-driven (흔히, select/poll/epoll/kqueue 사용한) 방식을 사용해야하는가’라는 질문을 자주 받는다. 대략 내가 처음 job으로서의 프로그래밍을 시작하던 2001년에만 하더라도 리눅스를 포함한 POSIX platform에서의 쓰레드 구현은 형편없었고, select나 kqueue 등을 사용하는 것이 High Performance, High Concurrency를 위한 서버를 만들기 위한, 다시 말해 C10K 문제를 해결하기 위한 거의 유일한 방법이었다. 하지만, 컴퓨팅 환경은 (언제나처럼) 급속도로 발전했고, Multithreading을 사용해 몇몇 프로덕트를 만드는데에 성공하면서, 2004년 말 정도에는 Event-driven보다 Multithreading이 더 나은 해법이 아닌가하는 의심이 들 정도였다. 이러한 의심으로부터 Multithreading이 우월한 해법이라는 것을 확신시켜준 것은 태준옹 와의 대화였고, 이후로는 위와 같은 질문에 대해서는 항상 ‘굉장히 performance-critical한 서버가 아니라면 multithreading을 사용하는 것이 좋다‘라고 답변하고 있다. 그리고, ‘굉장히 performance-critical한 서버가 아니라면’이라는 가정조차도 점점 힘을 잃어가고 있는 추세이다.

그러던 와중에, CN님이 2005년 4월 30일에 쓰신 ‘프로그래머에게 해로운 두가지 1: 쓰래드’라는 글로 Multithreading에 비해 Event-driven을 선호해야한다는 글을 쓰셨는데, 해당 글의 코멘트에서 논쟁을 벌이다가 Multithreading을 방어하기 위한 글을 따로 써야겠다는 마음을 먹었으나, 이를 1년 6개월 만에 실행에 옮기게 된 것이 바로 이 글이다.

Performance

경험 있는 서버 개발자들이 주로 Multithreading에 비해 Event-driven을 선호하는 가장 큰 이유는 performance일 것이다. 실제로 옛날에는 Event-driven 방식을 사용하는 것이 상대적으로 엄청나게 뛰어난 performance를 보여주었다. 하지만, 어디까지나 그건 ‘옛날 이야기’다. 이렇게 된 이유는,

OS의 Multithreading 지원과 이를 통한 더 나은 쓰레드 구현
CPU 속도의 증가 경향
Multiprocessor의 보편화 경향(CPU 수의 증가 경향)과 OS의 지원

정도로 들 수 있을 것 같다.

Multithreading을 사용할 때 performance에 대해 걱정하는 점들은 더이상 문제가 되지 않는다. 하나씩 짚어보면,

쓰레드가 많아지면 schedule하는데 부담이 크지 않을까?
- Linux 2.6 커널은 O(1) 알고리즘의 scheduler를 가지고 있다. (Solaris나 Windows에서도 반영된다고 했으나, 현재 상태는 알 수 없다.) 쓰레드 수가 많다고 해서 scheduling overhead가 증가하는 일은 없는 것이다. 또한, 대화하다보면 sleeping 상태의 쓰레드도 scheduling 오버헤드에 포함될 것이라고 생각하는 사람도 많이 있는 것 같은데, 적어도 Linux에서는 그렇지 않다.
쓰레드가 많아지면 context switching cost가 많이 들지 않을까?
- 현대의 architecture, 적어도 x86은 cpu context가 그다지 크지 않게(몇몇 register를 메모리에 save/restore하는 정도로) 설계되어있다. 실용성은 떨어지지만 32bit x86은 thread에 대한 CPU 레벨의 지원도 포함하고 있을 정도다. (물론, Linux에서는 사용하지 않는다.) 더군다나 CPU 속도가 빨라지면서 context switching의 비용은 점점 중요하지 않게될 것이다. P4 3GHz 머신에서 lmbench의 결과로는 2-3 microseconds 정도의 context switch latency가 있을 뿐이다.

여기에 Multiprocessor 문제가 추가되면 더더욱 Multithreading의 손을 들어줄 수 밖에 없다. Consumer PC에서도 Multiprocessor가 일반화되어가는 추세라는 것은 대부분의 사람들이 이제는 동의할 것이다. 프로그래머가 user-level에서 어떤 Multiprocessor를 사용할 것인가, 또는 각 processor에 연결된 메모리를 어떻게 효율적으로 사용할 수 있는가(NUMA )와 같은 문제까지 신경쓸 수는 없다. 결국, Multiprocessor를 효율적으로 사용하기 위해서는 processor 자원의 분배를 OS에 의존하는 Multithreading이 가장 좋은 방법이 되었다. 최근 수년간 (특히, Linux/FreeBSD에서는) Multiprocessor를 지원하기 위해 OS 디자인에서도 변화가 생기는 등 여러가지 노력들이 보이고 있다.

Event-driven 방식은 원래 하나의 쓰레드에서 event dispatcher와 handler가 함께 동작하는 방식이었으나, Multiprocessor를 활용하기 위해서는 event dispatcher를 processor 수에 따라 나누던가, handler가 쓰레드 풀 상에서 동작하도록 하는 방식을 채용하는 수 밖에 없다. 이렇게 되면, Event-driven 방식을 주장하는 사람들이 좋아하지 않는 쓰레드의 온갖 단점들이 Event-driven 방식에도 도입되게 된다. 그럼에도 불구하고 Multithreading이 Event-driven에 비해 state의 효율적인 관리가 불가능(이를테면, idle connection을 handle하기 위한 thread의 불필요한 stack 차지)하다는 주장을 할 수 있으나, 이 문제는 다음 섹션을 보도록 하자.

State Management

최근에 이루어진 컴퓨팅 환경의 변화 중 또다른 하나의 커다란 축은 바로 64bit 주소 공간의 도입일 것이다. 일단 주소 공간이 충분히 넓어졌기 때문에 쓰레드 수에 따른 주소 공간의 낭비는 크게 의미가 없게 되었다. Linux와 같은 현대의 OS는 스택에서도 페이지 폴트가 발생할 때 물리 메모리를 할당하는 방식을 취하므로 물리 메모리의 낭비 또한 거의 없다. 설령 32bit 머신을 사용하고 있어서 주소 공간이 부족하다고 하더라도, Linux의 쓰레드 구현인 NPTL은 쓰레드별로 스택 크기를 조정할 수 있으며, 최악의 경우에는 Event-driven과 같이 대부분의 state를 heap에 두면 대부분의 문제를 해결할 수 있다.

Synchronization

대부분의 서버의 경우 connection 단위의 세션들이 서로 공유해야하는 것이 별로 없는 경우가 많기 때문에 Synchronization 이슈가 생각만큼 크지는 않다. 하지만, 분명히 복잡한 logic을 가지고 synchronization을 많이 사용해야하는 경우도 존재할 것이다.

Event-driven 방식에서는 Synchronization의 문제가 자동적으로(for free) 해결된다고 하지만, 이는 Uniprocessor라는 가정하에서 뿐이다. Multiprocessor가 보편화된 환경을 고려하자면 Event-driven 방식이라고 해서 Synchronization 문제를 해결하지 않는 것은 어리석은 일이다. 더구나 Event-driven 방식에서 Synchronization을 하기 위해서는 state가 적어도 하나 더 추가되어야 한다. 아래에서도 설명하겠지만, Event-driven 방식에서 state 하나가 추가되는 것은 state 수 이상의 복잡도를 발생시킨다. 결국은 Synchronization을 하지 않는 디자인을 하는 수 밖에 없고, 이것은 말그대로 Synchronization을 하지 않는 것 뿐이고, 이러한 디자인 하에서는 Multithreading 방식으로 구현하더라도 Synchronization이 필요 없음을 의미할 뿐이다.

Why Events Are A Bad Idea에서 지적되었던 것처럼 Event-driven 방식 자체가 Synchronization 이슈를 해결하는 것이 아니라는 점을 되새길 필요가 있다. Multithreading에서 복잡한 Synchronization이 필요하다면 Event-driven 방식에서도 마찬가지다.

Complexity

Event-driven 방식 사용을 자제해야하는 가장 커다란 이유는 Complexity에 있다. Multithreading에 반대하는 많은 사람들이 Synchronization의 복잡도 때문에 Event-driven 방식을 사용해야한다고 주장하지만, Event-driven 방식을 제대로 경험해보지 못한 사람의 생각이라고 얘기하고 싶다.

2001년에 나는 당시로서는 서버 프로그래밍 방법 중 최고의 성능을 보여준다고 하는 kqueue()를 사용해서 Web Cache내의 Event-driven 방식 서버 엔진을 만든 경험을 가지고 있다. Web Cache는 단순한 서버가 아니라 서버와 클라이언트를 모두 포함하고 있기 때문에, 비교적 복잡한 Network I/O 패턴을 가지고 있다. 여기에 ICP(Internet Cache Protocol)나 DNS resolving과 같은 또다른 Network I/O나 cache 페이지를 접근하기 위해 Disk I/O가 더해지면 state 수가 불어나면서 엄청난 복잡도를 가지고 온다. Dispatcher와 State/Session 관리 부분을 모두 프레임웍화 한다고 하더라도 Event-driven 방식 자체에 내재한 복잡도는 state가 하나씩 추가될 때마다 state의 수 이상으로 증가한다. 다행히, 프로덕트는 나왔고, 외국의 벤치마크에서 좋은 평가를 받고, 상용화도 되었고, 어느 정도 팔렸으나, 차후에 자체적으로 개발한 쓰레드 패키지를 이용한 쓰레드 방식으로 재개발 되었다. 그 정도로 Event-driven 방식으로 만들어진 코드의 관리는 지속 불가능했다는 것이다.

이 후에, 다른 회사로 옮겨간 이후에도 서버 프로그래밍을 계속 해오면서 느낀 점 중 하나는, 많은 프로그래머들은 Event-driven 방식을 이해하기 힘들어 한다는 것이었다. 이것이 Event-driven 방식에 대한 회의를 느끼게 된 커다란 이유 중의 하나가 되었다. 나름대로 내린 결론은 기본적으로는 Why Events Are A Bad Idea에서도 지적되었던대로 Non-linearity다. 클라이언트-서버 패턴에서 서버는 클라이언트로부터의 요청을 처리해서 답변을 되돌려준다는 linear한 개념을 기반으로 하기 때문에, Event-driven이 서버에 도입하는 non-linearity는 클라이언트-서버 패턴을 구현하는데 중대한 장벽이 된다.

이 문제를 좀 더 자세히 들여다보면, decomposition 문제로 치환해서 생각해볼 수도 있다. 일반적으로 좋은 프로그램들은 logical한 단위의 decomposition을 사용한다. 그것이 structured이든 object-oriented이든 말이다. Event-driven 방식은 이벤트의 발생이 decomposition의 단위가 된다. 이벤트가 특정 애플리케이션에서 중요한 의미를 가지고 있다면 별다른 문제가 되지 않는다. 하지만, 적어도 서버에서는 일반적으로 이러한 이벤트의 발생이 자연스러운 기준이 되기는 힘들다. Event-driven 방식의 프로그래밍을 직접 해보면 깨닫게 되지만, 뭔가를 기다려야하는 operation, 즉 blocking operation이 도입될 때마다, 기다리는 상태와 깨어난 상태를 나타내는 두개의 state와 기다리는 상태에서 벗어나기 위한 이벤트가 하나씩 추가되어야 한다. 서버에서 이러한 blocking operation의 전형적이고 가장 자주 나타나는 예는 모든 종류의 I/O (Network I/O, Disk I/O, …)라고 볼 수 있다. 여기서 질문을 하나 던진다면, I/O 이벤트가 과연 좋은 decomposition 단위일까? 서버에서 I/O가 얼마나 높은 수준의 의미를 가질까? 이러한 blocking operation에 I/O만 존재한다면 그나마 행복한 편이다. Timeout을 상상해보라. Lock, Condition variable과 같은 Synchronization을 Event-driven 방식에서 구현한다고 상상해보라. (위에서 언급했듯이 Event-driven이라고 하더라도 Multiprocessor에서는 Synchronization이 필요하다.) I/O할 곳이 추가될 때마다, Synchronization이 추가될 때마다 서버의 복잡도는 지수적으로 증가할 것이다. 얼마지나지 않아 그 서버는 본인도 알아보기 힘들고, 아무도 건드리려하지 않는 괴물이 될 뿐이다. Web Cache를 만들던 시절에는 이러한 단점을 보완하기 위해서 I/O를 동반하지 않은 state를 만들거나 substate를 만들기도 했으나, 이러한 시도는 Why Events Are A Bad Idea에 언급되었던 ‘Just Fixing Events’에 지나지 않는다.

물론, Event-driven 방식이 완전히 쓸모없는 decomposition 방식인 것은 아니다. 애플리케이션 특성 상, 이벤트가 높은 수준의 abstraction을 가지는 경우, 특히 GUI 애플리케이션과 같이 어떤 이벤트가 일어났을 때 어떤 작업을 해야하는가를 생각하는 것이 자연스러운 경우가 분명히 존재한다.

Idle Connection Management

Introduction에서 했던 답변에 항상 덧붙여서 하는 얘기 중 하나는 바로 idle connection의 관리에 관한 얘기다. 서버를 Multithreading으로 구현한다고 하더라도 idle connection과 같이 하나의 thread를 할당하기가 불필요한 정도는 Event-driven 방식으로 따로 관리해서 thread의 낭비를 막는 방법 정도는 사용해볼만 할 것이다. Multithreading을 선호하라고 해서, 무조건 Event-driven 방식을 쓰지말라는 얘기는 아니라는 얘기다.

Cooperative Threads

Why Events Are A Bad Idea에서는 Synchronization이나 Scheduling에서의 오버헤드를 방지하기 위해서 User-level의 Cooperative Threads 구현을 사용해서 해결책을 내놓고 있지만, 위에서 기술한대로 Kernel-level 쓰레드 구현을 사용하더라도 크게 문제가 없거나 오히려 더 나은 해결책이 될 수 있다.

Standard Thread API

Linux에서도 기존의 구현 (linuxthreads)은 signal과 관련된 동작들이 제대로 정의된 최근의 POSIX 표준을 따르지 않았기 때문에 여러가지 문제들이 많았다. 특히, 커널의 지원이 미비한 상황에서 구현의 한계상 signal과 관련한 표준들이 제대로 지켜지기 힘들었다. 하지만, Linux 2.6에서 지원되는 NPTL은 구현시부터 POSIX compliance가 상당히 중요한 목표로 책정되어 개발되었다.

Conclusions

기존에는 Event-driven방식이 Highly-Concurrent 서버를 개발하기 위한 최적의 방법이라고 생각되었으나, 이제는 Multiprocessor의 보편화, 저가의 메모리, 64bit 메모리 스페이스, OS와 쓰레드 구현의 진화 등 컴퓨팅 환경의 변화로 인해서 Event-driven방식 보다는 Multithreading 방식을 선호하는 것이 타당하다고 생각된다.