대기열을 heap으로 짰다가 느려진 이유

MyRedis 대기열이 느려졌다

공부 삼아 Redis를 직접 만들어보고 있다. MyRedis라고 부르는 자작 인메모리 저장소인데, 여기에 티켓팅 대기열을 얹었다. 유저가 들어오면 sorted set에 넣고(ZADD), "나 지금 몇 번째야?"를 ZRANK로 돌려주고, 앞에서부터 입장시키는(ZPOPMIN) 구조다.

처음엔 잘 돌았다. 문제는 대기 인원이 늘면서였다. 사람이 몇만 명 쌓이자 순번 조회가 눈에 띄게 느려졌다.

요청 분포를 뜯어봤더니 답이 거기 있었다.

• 진입(ZADD)은 유저당 딱 한 번.
• 순번 조회(ZRANK)는 유저당 수십에서 수백 번. 다들 "내 차례 아직 멀었나" 하고 계속 새로고침하니까.
• 입장(ZPOPMIN)은 상대적으로 드물다.

전체 연산의 95% 이상이 ZRANK였다. 그런데 내 MyRedis는 sorted set을 heap으로 구현해 뒀고, 하필 heap에서 ZRANK는 O(N)이다.

느렸던 게 "감"이 아니라 수식으로 나왔다. 제일 자주 부르는 연산이 하필 제일 비싼 연산이었다. 워크로드와 자료구조가 안 맞았다는 뜻이다.

heap은 최솟값 하나만 안다

왜 heap의 ZRANK가 O(N)인지 보려면 heap이 뭘 보장하는지부터 봐야 한다. heap이 지키는 불변식은 딱 하나다. 부모 ≤ 자식(min-heap 기준).

       1
      / \
     3   2
    / \ / \
   7  8 5  9

이 트리가 아는 건 "루트가 최솟값"이라는 것 하나뿐이다. 3과 2 중 누가 큰지 heap은 신경도 안 쓴다. 배열 [1,3,2,7,8,5,9]을 그대로 읽어도 정렬된 순서가 아니다. heap은 최솟값 하나에 전부를 걸고 나머지를 포기한 구조다.

그래서 특정 유저의 순위를 물으면 heap은 막힌다. 우선 그 유저가 배열 어디 있는지부터 모른다. heap엔 값으로 노드를 찾는 능력이 없어서 배열을 처음부터 훑어야 한다. 설령 인덱스를 찾아도 그 인덱스는 순위가 아니다. 형제끼리 순서가 없으니까. 결국 "이 값보다 작은 게 몇 개냐"를 알려면 전부 세는 수밖에 없다. O(N) 확정이다.

이탈 유저를 지우는 ZREM도 같은 병이다. 지우려면 먼저 O(N)으로 찾아야 하니까. heap의 그 유명한 O(1) peek은 최솟값 하나한테만 주어진 특권이고, 나머지 원소들은 heap 입장에선 주소 없는 익명 집합이다.

skip list는 정렬해두고 고속도로를 깐다

Redis는 sorted set을 skip list로 구현한다. 구조가 heap과 정반대다.

바닥층은 그냥 정렬된 연결 리스트다. 전체가 항상 순서대로 누워 있다. 그 위에 확률적으로(보통 네 개 중 하나꼴) 노드를 승격시켜 만든 익스프레스 레인이 여러 층 얹힌다.

L3: 1 ─────────────────────────────▶ 50
L2: 1 ──────────▶ 20 ──────────────▶ 50 ────────▶ 90
L1: 1 ─▶ 7 ─▶ 20 ─▶ 35 ─▶ 50 ─▶ 71 ─▶ 90     (바닥층: 완전 정렬)

탐색은 꼭대기에서 시작해 규칙 하나만 반복한다. 다음 노드가 목표보다 크면 한 층 내려가고, 아니면 오른쪽으로 전진한다. 정렬된 리스트 위에서 이진 탐색을 흉내내는 셈이라 기대 시간복잡도가 O(log N)이다.

heap과의 차이를 한 줄로 줄이면 이렇다. heap은 최솟값 하나만 최적화하고 정렬을 포기했고, skip list는 전 구간을 정렬해두고 그 위를 빠르게 건너뛴다. 대기열이 제일 많이 쓰는 "중간 순위 조회"는 정확히 skip list가 최적화한 지점이고, heap이 포기한 지점이다.

연산별로 보면 승부가 분명하다.

heap이 이기는 칸이 한 칸도 없다. 제일 잘하는 ZPOPMIN조차 비긴다. 그리고 대기열의 킬러 연산인 ZRANK와 ZREM에서 O(N)으로 무너진다.

순위는 어떻게 O(log N)에 나오나: span

여기서 한 가지 짚고 가야 한다. 교과서적인 순수 skip list도 사실 순위는 못 구한다. 탐색 경로만으로는 "내가 바닥층 기준 몇 번째 노드인지"를 알 방법이 없다.

Redis가 쓰는 건 각 forward 포인터에 span을 얹은 변형이다. span은 그 점프가 바닥층 기준 몇 칸을 건너뛰는지를 저장한 숫자다.

50을 찾아가면서 지나온 span을 더하기만 하면 된다. 탐색 경로가 그대로 순위 계산이 된다. 순위를 얻는 데 드는 추가 비용이 0이다. 이게 span의 핵심이다. ZRANGE도 같은 원리로, span을 누적해 시작 위치까지 O(log N)에 점프한 다음 바닥층을 따라 k개를 줍는다. 그래서 O(log N + k)다.

물론 공짜는 아니다. 삽입하고 삭제할 때마다 지나온 각 층의 span을 갱신해줘야 한다. 새 노드가 들어가면 승격된 층에서는 직전 노드의 span이 "내 앞까지 / 내 뒤부터"로 쪼개지고, 승격 안 된 상위 층에서는 그 구간 아래에 노드가 하나 늘었으니 span이 1 커진다. 삭제는 반대로 앞뒤 span을 합친다. skip list 구현에서 버그가 제일 많이 나는 지점이 정확히 여기다.

그래서 나는 MyRedis에 불변식 하나를 assert로 박아뒀다. "어느 층에서든 그 층 노드들의 span 합은 바닥층 노드 수와 같아야 한다." 각 층은 결국 바닥층 전체를 몇 칸씩 건너뛰며 빠짐없이 덮는 파티션이라, 이게 깨지면 span 갱신 어딘가가 틀린 거다. 삽입과 삭제 직후에 이 검사만 돌려도 대부분의 span 버그가 조기에 잡힌다.

for (int level = 0; level < maxLevel; level++) {
    long sum = 0;
    for (Node n = head; n.forward[level] != null; n = n.forward[level])
        sum += n.span[level];
    assert sum == bottomLevelCount : "span 불변식 깨짐 @ level " + level;
}

skip list 혼자가 아니다: dict와 짝

Redis zset을 한 꺼풀 더 벗기면 skip list 단독이 아니다. dict(member → score)와 skip list의 쌍이다.

이유는 진입점 때문이다. ZSCORE(내 점수)는 dict에서 O(1)로 끝난다. 더 중요한 건 ZADD로 기존 유저의 점수를 바꿀 때다. 옛 점수를 알아야 skip list에서 그 노드를 찾아 지우고 새 점수로 다시 넣는데, 그 옛 점수를 skip list에서 member로 찾으려면 O(N)이다. dict가 그 옛 점수를 O(1)로 쥐여준다. dict는 모든 연산의 시작점을 상수 시간으로 만들어주는 장치다.

대가는 메모리다. 같은 member와 score를 양쪽에 들고 있으니 대략 두 배를 쓴다. 대신 모든 연산의 진입이 O(1)이 된다. MyRedis도 이 쌍을 그대로 따라가야 한다.

그럼 균형 트리는 왜 아닌가

여기서 자연스러운 질문. 순위가 필요하면 RB 트리에 서브트리 크기를 달아도 O(log N)이 나온다(order-statistics tree). 성능만 보면 skip list와 대등하다. 그런데 Redis를 만든 antirez는 skip list를 골랐다. 이유가 재밌다.

우선 구현이 압도적으로 단순하다. RB 트리의 회전과 리컬러링 지옥에 비하면 skip list는 "레벨을 코인 던지기로 정한다"가 전부다. 디버깅 난이도가 다르다. 범위 순회도 자연스럽다. ZRANGE는 바닥층 리스트를 그냥 따라가면 되는데, 트리는 in-order 순회 상태를 들고 다녀야 한다. 그리고 Redis는 단일 스레드라 락 경합이 없으니, skip list의 확률적 균형("최악의 경우 O(N)"이지만 그 확률이 사실상 0으로 수렴)을 감수할 여유가 있다.

성능이 대등할 때 자료구조를 가른 건 결국 구현과 유지보수의 단순함이었다. antirez의 실용주의다.

heap이 나쁜 게 아니다

그래서 heap을 못난 자료구조라고 버렸느냐. 아니다. heap이 압승하는 워크로드는 분명히 있다. 최솟값만 계속 꺼내고 중간 조회가 없는 경우가 그렇다. Kafka의 지연 메시지 타이머, OS 스케줄러의 ready 큐, 다익스트라 최단 경로. 여기선 heap이 정답이다. 배열 기반이라 CPU 캐시에 친화적이고 포인터 오버헤드도 없어서, 같은 O(log N)이라도 상수가 더 작다.

큐를 자료구조부터 정리한 글에서 "우선순위 큐는 내부적으로 heap"이라고 적었는데, 이 글은 같은 heap이 오답이 되는 경우다. 내 대기열이 느렸던 건 heap이 못나서가 아니라, 대기열이 "우선순위 큐"가 아니라 "순위 조회 시스템"이었기 때문이다. 최솟값을 꺼내는 일보다 "내가 몇 번째냐"를 묻는 일이 압도적으로 많은 시스템에, 최솟값 하나에만 최적화된 자료구조를 갖다 쓴 거다.

아직 숫자는 안 재봤다

여기까지는 복잡도로 설명한 이야기다. "몇 배 빨라진다"는 실제 숫자는 아직 안 재봤다. 이론이 맞는지 벤치마크로 확인하는 게 다음 숙제고, 어떻게 잴지는 정해뒀다.

메인 샷은 N 스케일링이다. 1만, 10만, 100만 명을 채워두고 ZRANK를 각각 10만 번 돌려 평균과 p99를 비교한다. 예상대로면 heap은 N에 선형으로 악화되고 skip list는 거의 평평할 거다. 그래프에서 직선과 수평선으로 갈리는 그림을 기대하고 있다.

거기에 두 가지를 더 붙일 생각이다. 하나는 실제 대기열 비율(ZADD 5% + ZRANK 90% + ZPOPMIN 5%)로 섞은 혼합 워크로드의 전체 처리량이다. 이론이 아니라 진짜 대기열에서 몇 배인지가 나온다. 다른 하나는 ZPOPMIN만 단독으로 재는 대조군이다. 여기선 heap도 안 밀린다는 걸 보여줘야 "무조건 skip list"가 아니라 "워크로드가 도구를 정한다"는 이야기가 완성된다. 반례를 포함한 주장이 더 세다.

재는 도구는 JMH를 쓸 거다. 손으로 System.nanoTime()을 재면 JIT 워밍업 때문에 숫자가 거짓말을 한다. 숫자가 채워지면 이 글에 이어 붙이겠다.

마치며

이번 일로 남은 건 "skip list가 빠르더라"가 아니다. 대기열을 짜기 전에 제일 자주 부르는 연산이 뭔지부터 봤어야 했다는 거다. 그걸 봤으면 순위 조회가 95%인 시스템에 heap을 고르지는 않았을 테니까. 자료구조를 먼저 정하고 워크로드를 끼운 게 문제였지, heap 자체가 문제였던 적은 없었다.