Redis가 싱글 스레드 모델임에도 높은 성능을 보장하는 이유 (I/O Multiplexing)

오진서·2024년 1월 12일

틀린 내용이 있을 수 있어 피드백 해주시면 감사하겠습니다 😀

들어가며

Redis는 Remote Dictionary Server이며, Dictionary, Set 등과 같은 메모리 내 자료구조를 제공하는 TCP 서버이다. Redis는 캐싱, 세션 저장소, 실시간 데이터 저장소, 스트리밍 엔진 등 다양한 용도로 사용된다. Redis가 high-throughput-low-latency (HTLL)을 가지는 주된 이유는 다음과 같다.

1. 메모리 기반 데이터 저장
Redis는 모든 데이터를 메인 메모리에 저장하고 주기적으로 스냅샷을 디스크에 저장한다.

2. 싱글 스레드 및 이벤트 루프 시스템
Redis는 Node.js와 같이 이벤트 루프와 I/O Multiplexing을 통해 싱글 스레드 모델임에도 높은 동시성을 보장한다.

3. 효율적인 데이터 구조
Redis는 skip-lists, 간단한 동적 문자열 등과 같이 효율적인 데이터 구조를 사용하여 빠른 연산을 지원한다.

Background

동시 클라이언트를 처리할 수 있는 웹 서버를 설계한다고 가정해보자. 첫 번째 가능한 해결책은 클라이언트가 TCP 프로토콜을 이용해 서버의 소켓에 연결을 생성하고, 서버가 이 연결을 수락하여 처리하는 것이다. 동시성을 제공하기 위해, 각 연결마다 새로운 스레드를 생성하여 연결을 관리하는 멀티 스레드 모델을 구현할 수 있다. 최적화를 위해 스레드 풀을 사용하여 연결을 할당할 수도 있다.

하지만 멀티스레드 환경에서는 CPU가 다수의 스레드를 관리해야 한다. 즉, CPU는 대부분의 시간을 컨텍스트 스위칭, 스케줄링, 스레드 수명주기 등 스레드 관리에 소비하게되며 이는 시스템 성능 저하로 이어질 수 있다. 또한, 스레드는 자신만의 스택 메모리를 가지게되는데 많은 수의 스레드가 생성될수록, 사용되는 총 메모리 양도 증가하게 된다.

1. Blocking I/O

I/O 블로킹이란 I/O 작업이 완료될 때까지 해당 작업을 요청한 프로세스 또는 스레드의 실행을 중지시키는 작업 방식을 말한다. 여러 스레드가 동시에 I/O 작업으로 인해 블로킹되면, CPU는 작업을 처리하는 데 사용되기보다는 대부분의 시간을 컨텍스트 스위칭이나 I/O를 기다리는 데 소비하게 된다. 이로인해 전체 시스템의 처리량이 크게 저하될 수 있다.

I/O 블로킹 모델에서는 클라이언트가 서버에 연결 요청을 할 때 그 연결을 처리하는 서버의 소켓과 스레드는 데이터를 읽을 수 있을 때까지 작업이 중단된다. 이는 아래 그림과 같이 시스템 콜을 호출한 후에, I/O 작업이 완료되기 전에는 제어권을 커널이 갖고 있기 때문이다. 즉, 데이터가 네트워크 버퍼에 모두 도착하고 처리 준비가 될 때까지 서버는 기다리는 것 외에는 아무것도 할 수 없다.

정리하면 I/O 블로킹 모델은 동시에 많은 클라이언트 연결(thread per connection)을 효율적으로 처리하기 어렵다. 각 연결마다 별도의 스레드를 할당하고, 각 스레드가 I/O 작업에 대해 블로킹되면, 컨텍스트 스위칭으로 인한 오버헤드가 증가될 수 있어 서버의 응답성이 저하되는 결과로 이어질 수 있다.

2. Non-Blocking I/O

이제 접근 방식을 바꿔서 단일 스레드 환경에서의 논블로킹 I/O 방식을 알아보자. 논 블로킹 I/O는 프로세스 또는 스레드가 I/O 작업을 수행하는 동안 대기 상태에 빠지지 않고, 다른 작업을 계속 진행할 수 있도록 하는 모델이다. 기본적으로 소켓 연산(accept(), read(), write())은 블로킹 모드로 동작한다. 반면, 논블로킹에서는 소켓 연산이 즉시 리턴되어, 데이터가 준비되지 않았을 때 스레드가 다른 작업을 계속할 수 있도록 해준다.

이는 소켓의 파일 디스크립터(fd)에 O_NONBLOCK 플래그를 설정함으로써, 해당 소켓에서 I/O작업을 비동기 방식으로 처리할 수 있다. 이제 accept() 같은 시스템 콜을 호출했을 때 데이터가 준비되지 않으면 즉시 에러 EAGAIN 또는 EWOULBLOCK을 응답한다. 이는 커널이 시스템 콜을 받자마자 제어권을 다시 유저 프로세스에게 넘겨 준다는 것이기에, 유저 프로세스는 I/O가 완료 되기 전에도 다른 작업을 할 수 있는 것이다.

에러 코드를 받으면, 스레드는 데이터가 준비될 때까지 지속적으로 폴링(busy-wait)방식으로 I/O가 완료되었는지 확인한다. 데이터가 준비되면, accept()는 새로운 클라이언트 연결에 대한 cfd를 반환하여 스레드는 클라이언트와의 통신을 수행한다.

하지만, 논블로킹 모델에서 폴링 방식은 스레드가 계속해서 에러 코드를 확인하기 위해 fd를 검사해야하기 때문에 CPU 시간이 많이 걸리고 사이클이 낭비된다. 즉, 논블로킹은 비동기적인 작업이지만 동기적으로 폴링해야 된다는 문제가 있다.

3. I/O Multiplexing

I/O 멀티플렉싱은 단일 프로세스 또는 스레드가 여러 I/O 작업을 동시에 모니터링할 수 있도록 해주는 기술이다. 이 방법을 사용하면, 여러 파일 디스크립터(fd)의 I/O 상태를 하나의 호출로 확인할 수 있어, 논블로킹 모델의 단점을 극복할 수 있다.

멀티플렉싱 모델에서는 select, poll, epoll 등의 시스템 콜을 호출해서 여러 소켓을 동시에 모니터링할 수 있게 해준다. select의 결과로 read 함수를 호출할 수 있는 소켓의 목록이 반환되면, 해당 소켓들에 대해 read 함수를 호출한다. 하지만 select 호출은 fd 상태를 주기적으로 확인하여 준비된 O(N)의 시간 복잡도로 fd가 있는지를 검사하므로 busy-wait 문제가 존재한다. 즉, 비동기적으로 여러 fd를 동시에 모니터링할 수 있지만 select 호출 자체는 블로킹(동기식) 특성을 띈다.

poll은 select과 거의 동일하며, select은 관리할 수 있는 fd 수가 제한이 있지만 poll은 이러한 제한 없이 무한 개의 fd를 관리할 수 있다는 차이가 있다. fd 집합을 모니터링 할 때, 매번 최대 fd까지 loop를 도는 select과 달리 poll은 실제 fd 개수 만큼만 loop만 돌게끔 구현할 수 있어 select 보다 시스템 콜 호출이 적다고 한다. 하지만 poll 역시 O(N)으로 각 fd를 순회하는 busy-wait 문제가 존재한다.

epoll은 select과 poll의 문제를 근본적으로 해결한다. epoll은 fd를 검사하기 위해 loop를 돌 필요 없이 fd 상태를 커널에서 직접 관리하여, I/O 이벤트가 발생할 때만 애플리케이션에 통지함으로써 busy-wait 문제를 해결한다.

아래는 fd 수에 따라 select, poll, epoll의 시간 소모를 비교한 모습이다.

정리하면 select나 poll은 스레드가 fd를 순회하면서 준비되었는지 주기적으로 검사하므로 busy-wait 상황을 초래할 수 있으며, 시스템 콜 호출 자체는 동기적인 블로킹 모델로 볼 수 있다. 반면 epoll은 커널이 직접 fd 상태를 관리해 상태가 바뀐 것을 통지하여 그에 대한 작업을 즉시 수행할 수 있게 해주므로 비동기적인 논블로킹 모델로 볼 수 있다.

📌 Redis Event-Loop

Redis는 Node.js와 유사한 단일 스레드 이벤트 루프(Event-Loop) 방식을 사용한다. 이벤트 루프는 I/O 처리에 있어서 이벤트 기반의 비동기 작업을 가능하게 하여 서버가 동시에 많은 작업을 처리할 수 있게 한다. Redis는 비동기 방식으로 TCP 연결을 수락한 다음, 이벤트 루프 내에서 각 연결에 대한 명령을 처리한다. 이벤트 루프의 주요 기능은 다음과 같다.

새로운 클라이언트 연결 수락
기존 연결로부터의 명령에 응답

이벤트 루프의 알고리즘은 다음과 같이 동작한다.

1. 네트워크 소켓 연결 유형 초기화 및 등록

server.c의 main 함수에서 connTypeInitialize()를 호출한다. 이 함수는 내부적으로 connTypeRegister(&CT_Socket)을 호출하여 CT_Socket을 등록한다. CT_Socket 유형은 ConnectionType 중 하나로, 네트워크 이벤트 처리, 연결 생성 및 종료, 데이터 입출력과 관련된 함수 포인터들의 집합이다. (connection.h)

/* server.c */
int main() {
  ...
  
  connTypeInitialize()
  ...
}


/* connection.c */
int connTypeRegister(ConnectionType *ct) {
    ...
    ConnectionType *tmpct;
    int type;

    /* find an empty slot to store the new connection type */
    for (type = 0; type < CONN_TYPE_MAX; type++) {
        tmpct = connTypes[type];
        if (!tmpct)
            break;
        ...
    }

    connTypes[type] = ct;
    ...
    return C_OK;
}

2. Redis 서버의 이벤트 루프 초기화

Redis 이벤트 루프는 Redis 서버 구조체 변수 내의 aeEventLoop *el 변수에 의해 정의된다. 이벤트 루프를 초기화하기 위해, main() 함수에서 initServer()함수를 호출하여 server.el을 초기화(aeCreateEventLoop함수 호출)시킨다.

/* server.c */ 
void  initServer ( void ) { 
  ... 

   server.el = aeCreateEventLoop(server.maxclients+CONFIG_FDSET_INCR); 

  ... 

}

aeEventLoop 구조체는 ae.h 파일에 정의되어 있으며, 이벤트 루프의 핵심 요소들을 담고있다.

typedef struct aeEventLoop
{
    int maxfd;                         /* 최대 파일 디스크립터 수 */
    long long timeEventNextId;         /* 다음 타임 이벤트 ID */
    aeFileEvent events[AE_SETSIZE];    /* 등록된 이벤트들 */
    aeFiredEvent fired[AE_SETSIZE];    /* 발생한 이벤트들 */
    aeTimeEvent *timeEventHead;        /* 타임 이벤트 리스트의 헤드 */
    int stop;                          /* 이벤트 루프 종료 여부 */
    void *apidata;                     /* 특정 폴링 API 데이터 */
    aeBeforeSleepProc *beforesleep;    /* 이벤트 루프의 슬립 전 실행 함수 */
} aeEventLoop;

aeCreateEventLoop함수는 이벤트 루프(server.el)을 초기화하는 역할만 수행하고, 특정 이벤트를 기다리거나 준비된 이벤트를 처리할 이벤트 핸들러를 등록하지는 않는다.

3. 이벤트 루프에 이벤트 등록

Redis에는 비동기적 작업을 처리하는 두 가지 유형의 이벤트가 있는데 fileEvents와 timedEvents이다. fileEvents는 네트워크 소켓 또는 fd에서 발생하는 I/O이벤트를, timedEvents는 시간 기반의 이벤트를 처리하는 데 사용된다.

fileEvents에는 1)AE_READABLE과 2)AE_WRITABLE이 존재하는데,
1)AE_READABLE 플래그는 fd가 읽기 작업을 위해 준비되었음을 나타내는 이벤트이다. 클라이언트로부터 데이터가 서버의 소켓에 도착하면, 해당 소켓은 AE_READABLE이벤트가 발생하여 등록한 읽기 핸들러를 호출시킨다.
2)AE_WRITABLE 플래그는 fd가 쓰기 작업을 위해 준비되었음을 나타내는 이벤트이다. 서버 소켓이 클라이언트에게 데이터를 전송하고자 할 때, AE_WRITABLE이벤트가 발생하여 등록된 쓰기 핸들러를 호출시켜 데이터를 클라이언트에게 전송시킨다.

이벤트 등록은 ae.c 파일에 있는 aeCreateFileEvent함수를 통해 수행된다.

int aeCreateFileEvent(aeEventLoop *eventLoop, int fd, int mask,
        aeFileProc *proc, void *clientData)
{
    if (fd >= eventLoop->setsize) {
        errno = ERANGE;
        return AE_ERR;
    }
    aeFileEvent *fe = &eventLoop->events[fd];

    if (aeApiAddEvent(eventLoop, fd, mask) == -1)
        return AE_ERR;
    fe->mask |= mask;
    if (mask & AE_READABLE) fe->rfileProc = proc;
    if (mask & AE_WRITABLE) fe->wfileProc = proc;
    fe->clientData = clientData;
    if (fd > eventLoop->maxfd)
        eventLoop->maxfd = fd;
    return AE_OK;
}

aeCreateFileEvent()는 fd에 대한 이벤트를 등록하는 데 사용되며, 특정 fd에 대해 이벤트가 발생했을 때 호출될 콜백 함수(proc)를 설정할 수 있다. 이 함수에서는 fd에 대한 이벤트 정보를 저장할 aeFileEvent 구조체를 eventLoop->events 배열에서 찾는다. 이후, 지정된 이벤트 마스크(mask)를 해당 fd에 epoll 등록하기 위해 aeApiAddEvent를 호출한다.

4. 포트 및 주소 바인딩 및 소켓 리스너 초기화

Redis 서버에서 새로운 연결을 수락하기 위해 3단계의 리스너 초기화 과정이 필요하다.

1단계) 서버는 먼저 네트워크 인터페이스와 포트에 소켓을 바인딩하고, 해당 소켓에서 들어오는 연결 요청을 리스너하기 시작한다. 또한 서버는 각 연결 유형(TCP/TLS/UNIX 소켓)별로 하나 이상의 리스너를 초기화한다.

2단계) 각 리스너는 새 연결을 수락하기 위한 핸들러(accept handlers)를 등록한다. 이 핸들러는 들어오는 연결 요청을 식별하고, 이를 수락하여 클라이언트와의 통신을 가능하게 한다. 또한 수락된 연결을 서버의 이벤트 루프에 등록하여, 이벤트 기반 처리가 가능하도록 한다.

3단계) 연결이 성공적으로 수락되면, 서버는 핸들러(read handler)를 이벤트 루프에 등록한다. 이 핸들러를 사용하여 클라이언트로부터의 데이터 수신(레디스 명령어)을 처리한다.

5. 이벤트 루프에서 준비된 이벤트 순회하며 등록된 핸들러에 의한 이벤트 처리

리스너가 초기화되고 핸들러가 등록된 후, main() 함수는 aeMain()을 호출하여 이벤트 루프의 실행을 시작한다.

void aeMain(aeEventLoop *eventLoop) {
    eventLoop->stop = 0;
    while (!eventLoop->stop) {
        aeProcessEvents(eventLoop, AE_ALL_EVENTS|
                                   AE_CALL_BEFORE_SLEEP|
                                   AE_CALL_AFTER_SLEEP);
    }
}

aeMain()은 while 루프 안에서 eventLoop->stop 값이 0이 아닐 때까지 계속해서 모든 이벤트를 처리한다. aeProcessEvents함수를 호출해서 실제 이벤트 처리를 수행하게 된다.

int aeProcessEvents(aeEventLoop *eventLoop, int flags)
{
    int processed = 0, numevents;
              ...

        /* Call the multiplexing API, will return only on timeout or when
         * some event fires. */
        numevents = aeApiPoll(eventLoop, tvp);

        for (j = 0; j < numevents; j++) {
            int fd = eventLoop->fired[j].fd;
            aeFileEvent *fe = &eventLoop->events[fd];
            ...
            int fired = 0; /* Number of events fired for current fd. */

            if (!invert && fe->mask & mask & AE_READABLE) {
                fe->rfileProc(eventLoop,fd,fe->clientData,mask);
                fired++;
                fe = &eventLoop->events[fd]; /* Refresh in case of resize. */
            }

            /* Fire the writable event. */
            if (fe->mask & mask & AE_WRITABLE) {
                if (!fired || fe->wfileProc != fe->rfileProc) {
                    fe->wfileProc(eventLoop,fd,fe->clientData,mask);
                    fired++;
                }
            }

             ...
            processed++;
        }
    }

    return processed; /* return the number of processed file/time events */
}

이 함수에서는 aeApiPoll()을 호출하여 준비된 이벤트의 수(numevents)를 받아온다. aeApiPoll에서는 epoll_wait를 호출하여 등록된 소켓들의 이벤트를 대기하고 감지한다. epoll_wait()는 지정된 시간(tvp)동안 이벤트가 발생할 때까지 대기하며, 이벤트가 발생하면 감지된 이벤트 수를 반환한다. 이벤트 수만큼 반복하면서 이벤트가 발생한 fd를 찾고, 해당 fd와 연관된 aeFileEvent 구조체를 참조해서 읽기 및 쓰기 이벤트 핸드러를 호출하여 실제 I/O작업을 수행시킨다.

이벤트 루프에서의 처리 과정을 다시 정리해보면,

1) 이벤트 루프 시작
이벤트 루프는 aeMain()의 무한 루프에서 시작되며, aeMain()에서는 이벤트 루프 객체 eventLoop를 인자로 받아, eventLoop->stop 플래그가 설정될 때까지 무한히 실행된다.

2) 이벤트 폴링
aeProcessEvents()는 현재 발생할 수 있는 모든 이벤트(Time Events, File Events)를 처리하기 위해 호출된다. aeProcessEvents 함수는 aeApiPoll 함수를 호출하여 이벤트 폴링(epoll_wait[linux])을 수행하여 이벤트를 기다린다.

3) 이벤트 발생
aeApiPoll()에서 이벤트가 감지되면, 해당 이벤트에 연결된 fd와 이벤트 유형(AE_READABLE, AE_WRITABLE)가 eventLoop->fired 배열에 저장된다.

4) 이벤트 처리
그런 다음, aeProcessEvents()는 fired 배열을 순회하며 각 이벤트를 처리한다. 만약 발생한 이벤트가 AE_READABLE(클라이언트로부터 데이터가 도착)이라면 fe->rfileProc() 읽기 핸들러를 호출시켜 데이터를 읽고, AE_WRITABLE(데이터를 클라이언트에게 전송할 준비)이라면, fe->wfileProc() 쓰기 핸들러를 호출시켜 데이터를 클라이언트에게 전송한다.

결론

정리해보니 결국, 아래 aeApiPoll()에서 호출하는 epoll() (I/O Multiplexing 기술) 시스템 콜 덕분에, 싱글 스레드임에도 불구하고, 다수의 연결과 요청을 비동기적으로 처리할 수 있다는 것을 알 수 있었다.

static int aeApiPoll(aeEventLoop *eventLoop, struct timeval *tvp) {
    aeApiState *state = eventLoop->apidata;
    int retval, numevents = 0;

    retval = epoll_wait(state->epfd,state->events,eventLoop->setsize,
            tvp ? (tvp->tv_sec*1000 + (tvp->tv_usec + 999)/1000) : -1);
    if (retval > 0) {
        int j;

        numevents = retval;
        for (j = 0; j < numevents; j++) {
            int mask = 0;
            struct epoll_event *e = state->events+j;

            if (e->events & EPOLLIN) mask |= AE_READABLE;
            if (e->events & EPOLLOUT) mask |= AE_WRITABLE;
            if (e->events & EPOLLERR) mask |= AE_WRITABLE|AE_READABLE;
            if (e->events & EPOLLHUP) mask |= AE_WRITABLE|AE_READABLE;
            eventLoop->fired[j].fd = e->data.fd;
            eventLoop->fired[j].mask = mask;
        }
    } else if (retval == -1 && errno != EINTR) {
        panic("aeApiPoll: epoll_wait, %s", strerror(errno));
    }

    return numevents;
}

epoll()을 사용하면, 소켓 연결의 상태 변화를 논블로킹 방식으로 감지할 수 있다. 코드 레벨에서 살펴보았듯이, aeApiPoll()에서 epoll_wait()는 한번의 호출로 여러 이벤트를 반환할 수 있으며, 이는 동시성을 크게 향상시킨다. 즉, epoll_wait()를 호출하여 fd에 대한 이벤트를 대기하고, 이벤트가 발생되면 epoll_wait()에서 반환되어 aeApiPoll()에 의해 핸들러(콜백 함수)를 호출하여 처리된다.

이러한 epoll()의 비동기적 이벤트 처리 방식을 통해 Redis가 싱글 스레드에서도 높은 동시성과 성능을 보장할 수 있었다.