Redis 는 해시 테이블을 키울 때 왜 멈추지 않나요: 점진적 리해시와 면접 답

딥다이브 스터디 노트

목록 보기

3/3

면접관이 질문을 던집니다. 「해시 테이블에 원소가 가득 차면 크기를 두 배로 늘려야 합니다. 1억 개의 키가 들어 있는 해시 테이블을 두 배로 늘리려면 모든 키를 다시 해시해야 해서 수백 밀리초 동안 멈추게 됩니다. 그런데 싱글 스레드로 동작하는 Redis 는 어떻게 멈추지 않고 키를 늘릴까요?」 질문을 받고 머릿속으로 'Redis 는 메모리 DB 라서 빠르다'라는 답변을 떠올렸다면 면접관의 의도와 멀어진 것입니다.

이 글은 해시 테이블이 거대해질 때 발생하는 정지 현상을 Redis 가 어떻게 해결했는지 기술적으로 풀어냅니다. 그릿 딥다이브 Vol.1 · Redis 2주차 「깊이」에서 다룬 내용을 바탕으로 작성했습니다.

표준 해시 테이블은 리해시할 때 왜 멈추나요?

표준 해시 테이블(Hash Table)은 배열을 기본 구조로 사용합니다. 키의 해시값을 배열 크기로 나눈 나머지를 인덱스로 삼아 데이터를 저장합니다. 키의 개수가 늘어나 배열 크기에 가까워지면 충돌이 잦아집니다. 이를 나타내는 지표가 부하 인자(load factor, 원소 수를 배열 크기로 나눈 비율)입니다.

부하 인자가 임계치(보통 0.75 또는 1.0)를 넘으면 해시 테이블은 배열 크기를 두 배로 늘립니다. 새 배열을 할당한 뒤 기존의 모든 원소를 다시 해시하여 새 배열로 옮겨 담습니다. 이 과정을 리해시(rehash)라고 부릅니다.

1억 개의 키를 가진 해시 테이블을 리해시하려면 1억 번의 해시 재계산과 메모리 쓰기가 발생합니다. 단일 CPU 기준으로 약 100ms 이상의 시간이 소요됩니다. 표준 해시 테이블 구현(예: Java의 HashMap)은 이 작업을 단 한 번의 연산 안에서 통째로 처리합니다. 리해시가 일어나는 그 한 번의 연산 동안 해당 해시 테이블에 접근하려는 모든 작업은 멈추게 됩니다.

교과서에서는 이를 분할 상환 O(1)(amortized O(1)) 분석으로 설명합니다. 1억 번의 빠른 O(1) 삽입 연산 끝에 한 번의 100ms 정지가 오더라도, 전체 비용을 1억 번으로 나누면 평균 비용은 여전히 O(1)이라는 뜻입니다. 하지만 싱글 스레드로 작동하는 Redis 에서 100ms 정지는 모든 클라이언트의 요청이 멈추는 심각한 장애로 이어집니다.

Redis 는 1억 개 키를 늘릴 때 왜 멈추지 않나요?

Redis 는 전체 리해시 작업을 한 번에 실행하지 않습니다. 작업 자체를 잘게 쪼개어 명령어 하나가 들어올 때마다 조금씩 진행합니다. 이 방식을 점진적 리해시(incremental rehash)라고 부릅니다.

차근차근 진행한다는 뜻의 incremental 이 붙은 점진적 리해시는 전체 옮김 작업을 한 번에 끝내지 않고, 명령어 한 번에 버킷 한 칸씩 나누어 마무리하는 방식입니다.

Redis 는 이를 위해 내부 자료구조인 dict 안에 해시 테이블을 두 개 유지합니다. 평소에는 ht[0] 만 사용하다가, 리해시가 시작되면 ht[1] 에 두 배 크기의 새 해시 테이블을 할당합니다.

점진적 리해시가 시작되면 Redis 는 다음과 같이 동작합니다.

클라이언트가 GET 이나 SET 같은 명령어를 보냅니다.
Redis 는 해당 명령어를 처리하는 과정에서 ht[0] 의 버킷 하나(연결 리스트 하나)에 들어 있는 키들을 ht[1] 로 옮깁니다.
옮김 위치는 rehashidx 라는 인덱스 변수로 기록합니다.
리해시가 진행되는 동안 검색은 ht[0] 을 먼저 보고, 없으면 ht[1] 을 봅니다.
새 키 삽입은 무조건 ht[1] 에만 수행하여 ht[0] 이 더 이상 자라지 않게 막습니다.

초당 10만 번의 요청이 들어오는 시스템이라면 초당 10만 개의 버킷이 자연스럽게 이동합니다. 클라이언트는 자신이 보낸 명령어에 몇 마이크로초의 리해시 비용만 얹어서 지불하므로, 서버 전체가 100ms 동안 멈추는 지연 튀어오름(latency spike)이 발생하지 않습니다.

이런 CS 질문 하나를 아침마다 같이 풀어 보는 오픈채팅방이 있습니다. 개발자: 데일리 CS 역량 강화 챌린지 들어가 보기 →

함께 보면 좋은 글: Redis 백업 중 메모리가 두 배로 찍혔다: 서버를 늘리기 전에, 면접에서 답하기 전에 볼 세 가지

점진적 리해시는 코드에서 어떻게 작동하나요?

redis/src/dict.c 파일의 dictRehash 함수에 핵심 로직이 들어 있습니다. 이 함수는 옮길 버킷 수 n 을 매개변수로 받습니다.

/* redis/src/dict.c 의 dictRehash 일부 */
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* 빈 버킷을 너무 많이 만나면 멈춤 */
    if (!dictIsRehashing(d)) return 0;

    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];
        while(de) {
            uint64_t h;
            nextde = de->next;
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }
    return 1;
}

이 코드는 두 가지 안전장치를 두고 있습니다. 첫째, 빈 버킷이 길게 이어질 때 CPU 를 계속 쓰지 않도록 empty_visits 한도를 설정합니다. 둘째, 한 버킷 안에 매달린 연결 리스트 전체를 옮긴 뒤 rehashidx 인덱스를 1 늘립니다.

이 함수는 두 곳에서 호출됩니다.

첫째는 명령어가 들어올 때 실행되는 _dictRehashStep 함수입니다.

/* redis/src/dict.c 의 _dictRehashStep */
static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}

dictAdd, dictFind, dictGenericDelete 등 모든 dict 접근 연산의 입구에서 _dictRehashStep 이 호출되어 딱 1 버킷(n=1)을 옮깁니다.

둘째는 클라이언트 요청이 없는 한가한 시간(idle time)입니다. 이벤트 루프(Event Loop)가 쉴 때 dictRehashMilliseconds 함수를 호출하여 1ms 예산 동안 리해시를 최대한 가속합니다.

/* redis/src/dict.c 의 dictRehashMilliseconds */
int dictRehashMilliseconds(dict *d, int ms) {
    long long start = timeInMilliseconds();
    int rehashes = 0;
    while(dictRehash(d,100)) {
        rehashes += 100;
        if (timeInMilliseconds()-start > ms) break;
    }
    return rehashes;
}

명령어가 들어올 때 1 버킷씩 옮기는 처리와 쉬는 시간에 1ms 씩 옮기는 처리가 협력하여 1억 개 키의 리해시를 멈춤 없이 안전하게 마칩니다.

왜 amortized O(1) 대신 worst-case O(1) 을 선택했나요?

학술적으로는 표준 해시 테이블의 분할 상환 O(1) 분석도 정직한 분석입니다. 하지만 분석 모델이 전제하는 환경과 실제 운영 환경 사이에 간극이 있습니다.

분할 상환 분석은 연산의 비용이 수많은 연산 전체에 균등하게 분산될 수 있다고 가정합니다. 멀티스레드 애플리케이션이나 개별 객체 수준에서는 한 스레드가 리해시 비용을 떠안더라도 다른 스레드가 영향을 받지 않거나, 전체 수명주기 안에서 평균을 낼 수 있습니다.

하지만 싱글 스레드로 작동하는 Redis 는 모든 클라이언트 요청을 단 하나의 스레드가 순차적으로 처리합니다. 리해시 연산이 일어나는 순간 그 단일 스레드가 멈추면, 뒤이어 들어오는 모든 클라이언트의 요청이 큐에 쌓이고 타임아웃이 발생합니다. 분할 상환 분석의 평균값은 의미를 잃고 p99 지연 시간(p99 latency)이 심각하게 상해버립니다.

Redis 는 최악의 상황에서도 O(1) 시간 복잡도를 보장하는 최악 시간 O(1)(worst-case O(1)) 구조를 선택했습니다. 각 명령어마다 1 버킷을 옮기는 약간의 고정 비용을 추가하는 대신, 최악의 순간에 100ms 가 멈추는 위험을 완벽하게 제거한 것입니다. 평균 지연 시간을 아주 미세하게 올리는 대가로 최악 지연 시간을 확실하게 통제하는 설계입니다.

면접에서 이 질문을 받는다면

「Redis 는 해시 테이블을 키울 때 왜 멈추지 않나요?」라는 질문을 받는다면 다음과 같이 답변할 수 있습니다.

Redis 는 전체 리해시를 한 번에 실행하지 않고 잘게 쪼개어 처리하는 점진적 리해시(incremental rehash) 방식을 사용합니다. 내부 자료구조 안에 두 개의 해시 테이블(ht[0], ht[1])을 두고, 평소에는 하나만 쓰다가 리해시가 시작되면 두 배 크기의 새 테이블을 할당합니다. 이후 클라이언트의 요청 명령어가 들어올 때마다 기존 테이블의 버킷을 1개씩 새 테이블로 옮깁니다. 이와 함께 이벤트 루프가 쉬는 한가한 시간에 1ms 단위로 리해시를 추가 진행합니다. 이렇게 최악 연산 비용을 시간에 분산시킴으로써 싱글 스레드 환경에서도 지연 시간이 튀어오르는 현상을 막습니다.

꼬리 질문으로 「리해시 진행 중에 데이터 조회가 들어오면 어떻게 처리하나요?」라고 물어볼 수 있습니다.

rehashidx 변수를 통해 현재 리해시 진행 상태인지 확인합니다. 리해시 중이라면 먼저 기존 테이블인 ht[0] 에서 키를 찾고, 없으면 새 테이블인 ht[1] 을 추가로 조회합니다. 반면 새로운 키를 삽입하는 작업은 무조건 새 테이블인 ht[1] 에만 기록하여 기존 테이블이 더 이상 자라지 않도록 조율합니다.

개발자: 데일리 익명 면접 챌린지 들어가 보기 →

하나 더: 왜 해시 테이블을 굳이 두 개나 둘까요?

한 개의 배열 안에서 인덱스 경계선을 두고 옮긴 영역과 안 옮긴 영역을 구분하는 구현도 떠올릴 수 있습니다. 메모리를 절약할 수 있어 보이지만 Redis 는 해시 테이블 두 개(ht[0], ht[1])를 들고 있는 방식을 선택했습니다.

이유는 코드의 단순성과 명확성 때문입니다. 테이블 두 개를 분리하면 읽기는 ht[0] 과 ht[1] 순차 조회, 리해시 중 새 키 삽입은 ht[1] 단독 쓰기, 갱신 및 삭제는 두 테이블 검색 후 처리라는 단순한 조건문 몇 줄로 구현됩니다. 한 개 배열 안에서 비트 플래그를 관리하며 옮김 여부를 판단하면 복잡한 분기 조건이 늘어나 버그가 생기기 쉽습니다. Redis 는 리해시 동안 메모리를 2배로 사용하는 임시 비용을 지불하는 대신, 버그를 줄이고 유지보수성을 극대화하는 단순성(Simplicity)을 선택했습니다.