Redis는 I/O 이벤트 통지 메커니즘, epoll에 대해 알아보자

개요

 Redis는 메모리 기반의 키-값 저장소로 유명하며, 뛰어난 성능을 자랑한다. 이러한 높은 성능의 비결 중 하나는 I/O 멀티플렉싱(IO Multiplexing)을 활용한 싱글 스레드 이벤트 루프 구조에 있다. 특히 리눅스에서 Redis는 epoll이라는 고성능 I/O 이벤트 통지 메커니즘을 사용해 수많은 클라이언트 연결을 효율적으로 다룬다. epoll은 기존의 select(2)나 poll(2) 호출과 달리 커널 내부에서 관심있는 파일 디스크립터들을 관리하며, 이를 위해 레드-블랙 트리(Red-Black Tree) 기반의 자료 구조를 활용한다. 본 글에서는 커널 레벨에서 epoll이 어떻게 동작하고 select/poll 대비 무엇이 다른지, epoll 구현에 쓰이는 레드-블랙 트리가 I/O 성능에 어떤 영향을 주는지 살펴본다. 또한 Redis 내부에서 이벤트 루프가 어떤 방식으로 동작하는지, 싱글 스레드 기반으로 non-blocking I/O와 I/O 멀티플렉싱을 통해 여러 클라이언트를 처리하는 구조를 설명하고, Redis가 빠른 이유를 epoll과 레드-블랙 트리 관점에서 정리한다.

 

epoll vs select/poll – 커널 I/O 이벤트 통지와 레드-블랙 트리

 서버 프로그래밍에서 동시에 여러 소켓이나 파일에 대해 I/O 이벤트를 처리하려면 I/O 다중화가 필요하다. 과거에는 POSIX 표준인 select와 poll 시스템 호출이 주로 사용되었다. 하지만 이들 방식에는 성능과 확장성에 한계가 있다. select()는 내부적으로 고정 크기의 비트마스크(fd_set)를 사용하기 때문에 감시할 수 있는 파일 디스크립터 수에 제한이 있는데, 일반적으로 FD_SETSIZE로 정의된 1024개 정도가 기본 상한이다​.

[사진 1] POSIX 표준 시스템 호출

 또한 select/poll의 가장 큰 문제는 호출 때마다 전체 디스크립터 집합을 선형 탐색해야 한다는 점이다. 즉, 매번 커널에 모니터링을 의뢰한 모든 소켓을 일일이 검사하여 어떤 것이 준비되었는지 확인하므로 O(n) 시간 복잡도를 갖는다​. poll()은 select의 FD 개수 제한은 없앴지만 마찬가지로 매 호출마다 전달된 목록을 처음부터 끝까지 스캔해야 하므로 근본적인 선형 복잡도 문제는 동일하다​.

 

 이 때문에 연결 수가 많은 고성능 서버에서는 select/poll 방식이 비효율적이다. 이에 비해 리눅스의 epoll은 대량의 파일 디스크립터를 효율적으로 처리하기 위해 설계된 I/O 이벤트 통지 매커니즘이다​

[사진 2] select와 poll이 커널에 FD를 저장하는 방식

 

 epoll 인터페이스는 세 가지 주요 호출로 이루어진다: epoll_create()로 epoll 인스턴스를 생성하고, epoll_ctl()로 관심있는 파일 디스크립터(event)를 등록/수정/삭제하며, epoll_wait()으로 이벤트 발생을 대기한다. 핵심 차이점은 커널이 관심 목록을 기억한다는 것이다. 한 번 epoll_ctl로 등록된 디스크립터들은 커널 내부의 관심 리스트에 보관되며, 이후 매번 epoll_wait를 호출할 때 사용자가 모든 디스크립터를 다시 전달하지 않아도 된다​.

 

커널은 이전에 등록된 목록을 알고 있으므로, select/poll처럼 “매번 처음부터 전체를 훑는” 작업이 필요 없다. 이로 인해 이벤트 대기 자체의 비용은 관찰 대상의 수와 무관하게 상수 시간에 수행될 수 있다​. 요약하면, select/poll는 매 이벤트 대기 호출이 O(n)이지만, epoll은 등록된 소켓의 수에 상관없이 이벤트 통지에서 선형 탐색을 피하여 높은 규모에서도 성능이 떨어지지 않는 I/O 처리가 가능하다​

 

[사진 3] epoll이 커널에 FD를 저장하는 방식

 

 epoll이 이러한 효율을 달성하는 데에는 커널 내부 구현이 중요하다. 리눅스 커널은 epoll의 관심 목록(감시 중인 파일 디스크립터 집합)을 관리하기 위해 레드-블랙 트리 자료 구조를 사용한다​. 새로운 소켓을 epoll에 추가하거나(epoll_ctl_add), 제거하거나 수정할 때 커널은 이 레드-블랙 트리에 해당 디스크립터를 삽입/삭제/찾기 하게 된다. 레드-블랙 트리는 자기 균형 이진 탐색 트리이므로 최악의 경우에도 연산이 O(log n)에 수행되어, 수많은 디스크립터를 관리할 때도 일정한 성능을 보장한다​.

 

 epoll_wait로 이벤트를 받을 때는 이 트리를 매번 탐색하지 않아도 되는데, 그 이유는 커널이 각 디스크립터의 상태 변화를 콜백 형태로 처리하여 별도의 준비 완료 리스트를 관리하기 때문이다​. 즉, 관심 리스트는 레드-블랙 트리로 관리하되, 이벤트가 발생하면 해당 디스크립터를 별도의 대기열에 넣어두고 epoll_wait 호출 시 바로 준비된 이벤트들을 반환하는 방식이다. 이를 통해 이벤트 통지 자체는 연결 수 n에 대해 O(1)의 비용만 들고, 실제 비용은 발생한 이벤트 개수에 비례하게 된다​.

 

정리하면, select/poll vs epoll의 차이는 다음과 같다

• FD 관리 방식: select는 고정 크기 비트셋을 사용하여 FD를 관리(기본 1024 한계)하고, poll은 가변 길이 배열을 사용하지만 둘 다 사용자 공간에서 매 호출마다 관심 FD 목록을 전달한다​. 반면 epoll은 커널 내부에 관심 FD 목록을 유지한다​
• 이벤트 대기 성능: select/poll는 매 호출 시 선형 탐색을 하므로, 감시 중인 FD가 많을수록 CPU 사용량이 증가한다​. epoll은 준비된 이벤트만 통지하므로 대기 호출은 활성 이벤트 수에 비례한 비용만 발생하고, 대기 중인 수천 개의 FD가 있어도 추가 부담이 크지 않다​
  
• FD 등록/해제 비용: select/poll는 별도의 등록 단계가 없지만 매번 전체 목록을 넘겨야 하고, epoll은 초기 등록에 O(log n) 비용이 들지만 이후 이벤트 대기는 효율적이다​. 일반적으로 연결이 빈번하게 추가/제거되지 않고 유지되는 장기 연결이 많은 서버라면, epoll의 등록 비용은 무시할 만하고 이익이 훨씬 크다.
• 수용 가능한 연결 규모: select는 1024 FD 제한(혹은 그 이상 상수 조정 가능)이 있으므로 매우 많은 연결을 처리하기 어렵다. poll은 제한은 없지만 성능 문제가 있고, epoll은 수만 개 이상의 소켓도 실용적으로 처리 가능하도록 설계되어 있다​.

참고 자료

What is a POSIX File System? - Quobyte

 

Understanding Advanced I/O Event Handling: Multiplexing, Signal-Driven, and Epoll

What is epoll?