skip list

skip list

skip list는 확률적 자료구조라고 부르며, 검색이나 삽입 시 O(logN)의 속도를 보장한다. 리스트와 유사하지만, 리스트는 검색이 O(N)이다.

skip list는 보통 아래와 같은 형태를 갖는다.

그림처럼 멀티 헤더를 갖고 있으며, 높이가 여러 개다.

여기서 말하는 높이란, 하나의 노드는 값(value)을 가지고 있는데 노드의 레벨(높이)마다 같은 값을 가진다.

• 값은 같지만, 헤더에서 가리키는 포인터가 다르다.

이 높이는 랜덤 확률로 결정되는데 보통은 한 개씩은 기본적으로 생긴다.

왜 확률적 자료구조 인가?

노드의 높이. 즉, 노드의 레벨은 확률로 결정된다. 레벨이 확률적으로 계산되는 것을 제외하면 링크드 리스트랑 유사하다고 한다.

/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. 
 */
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

// 출처: https://github.com/zpoint/Redis-Internals/blob/5.0/Object/zset/zset.md

zslRandomLevel 함수는 redis의 skip list 구현에서 새로운 노드의 레벨을 결정하는 함수이다.

깊게 분석하지 않았지만, 이 함수는 랜덤한 값을 생성하여, 그 값이 특정 임계값보다 작을 때마다 레벨을 증가시키는 방식으로 작동한며 최대 레벨은 초과하지 않도록 보장된다.

결과적으로, 이 함수는 1레벨에서 시작하여 다음 레벨로 올라갈 확률이 1/4로 설계되어 있으며, 최대 레벨은 32이다.

저장 예시

예를 들어, score가 10, 20, 30인 세 개의 member가 존재한다고 하면 skip list는 다음과 같이 구성된다.

Level 2:  Head -> [30] -> NULL
Level 1:  Head -> [10] -> [20] -> [30] -> NULL
Level 0:  Head -> [10] -> [20] -> [30] -> NULL

O(logN)으로 탐색이 가능한 이유

skip list는 여러 레벨의 연결 리스트로 구성된다. Level 1에서의 탐색으로 본다면, 링크드 리스트와 유사하게 O(N)의 속도가 나온다. 하지만 탐색 효율성은 Tree와 유사하다.

• 가장 아래 레벨은 모든 요소(실제 값)을 포함하고, 상위 레벨로 갈수록 요소 수가 줄어든다.

각 노드가 상위 레벨에 포함될 확률은 50%이다. 이로 인해 레벨 K에는 평균적으로 N / 2^K 개의 노드가 포함된다.

탐색 과정:

1. 최상위 레벨에서 시작하여, 각 레벨에서 오른쪽으로 이동하며 탐색한다.

2. 더 이상 이동할 수 없으면 한 단계 아래 레벨로 내려간다.

3. 이 과정을 반복하여 원하는 요소에 도달한다.

ex) 7을 찾는 과정

Level 3 |    1 ------------------------> 9
Level 2 |    1 --------> 5 ------------> 9
Level 1 |    1 ----> 3 -> 5 ----> 7 ---> 9
Level 0 |    1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 9

검색 값: 7

1. Level 3에서 시작: 1 → 9 (9가 더 크므로 내려감)

2. Level 2로 내려감: 1 → 5 → 9 (9가 더 크므로 내려감)

3. Level 1로 내려감: 5 → 7 → 9 (7을 찾음)

이 과정에서 몇 개의 노드만 확인하고도 빠르게 7을 찾을 수 있다.

과정을 보면, Level1 에서는 1번, 3번 노드의 탐색을 건너 뛰는 것을 볼 수 있다.

일반 연결 리스트였다면 1~7까지 모든 노드를 확인해야 한다.

각 레벨에서 확인하는 노드 수가 제한적이고, 레벨 수가 logN에 비례하기 때문에 전체 탐색 시간이 O(logN)이 된다.

skip list 구조

skip list는 quad node 형태로 구현된다. 따라서 한 레이어 안에서 링크드 리스트의 양방향 탐색 뿐만아니라 위아래로도 링크를 가지고 있어서 삭제, 검색, 업데이트에도 용이하다.

노드 구조

• backward: 이전 노드를 가르키는 포인터

• level[]: 각 레벨별 다음 노드 정보 (포인터와 span)

• score: 정렬 기준이 되는 점수 (삽입으로 들어오는 점수)

• ele: 실제 저장되는 member 데이터 (삽입으로 들어오는 member 값이 들어옴)

skip list에서는 span을 통해 각 레벨에서 노드가 얼마나 많은 노드를 건너뛰는지를 기록하여, 특정 key의 순위를 쉽게 계산할 수 있고 이를 통해 검색 시 몇 개의 노드를 건너뛰어야 하는지를 빠르게 알 수 있어서 탐색 속도를 향상시킨다고 한다.

예를 들어, span=5인 경우, 현재 노드 다음에 5개의 노드가 있다는 것을 의미한다.

Redis에서 skip list 적용

Redis는 Sorted Set을 내부적으로 ZSet이라고 한다. Sorted Set은 내부적으로 두 가지 데이터 구조로 저장된다. Redis가 데이터 구조를 선택하는 데, 두 가지 조건이 있다.

1. member 수가 128개 까지는 zip list 자료구조에 저장된다.

   • 다른 하나의 값(value)의 길이가 64byte까지는 zip list에 저장된다.

2. 129개부터는 자료구조를 변환해서 skip list에 저장된다.

   • 65 byte 부터는 skip list에 저장된다.

   • 여러 멤버 중 하나라도 값이 65 byte 이상이면 변환된다.

   • 이 두가지는 OR 조건이기 때문에 하나라도 조건에 충족하면 레디스 서버가 자동으로 자료구조를 변환해서 저장한다.

이렇게 하는 이유는 member 수가 적을 때는 zip list가 연속된 메모리 공간을 사용하여 메모리 오버헤드를 줄이고, 빠른 성능을 제공한다고 한다. 만약 member가 많아지면 O(logN)의 검색, 삽입, 삭제를 보장하는 skip list가 더 적합하다고 한다.

이 설정은 redis.conf의 ADVANCDE CONFIG의 값으로 조정할 수 있다.

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

• zset-max-ziplist-entries는 Sorted Set에서 zip list로 저장할 수 있는 최대 엔트리(member) 수를 설정하는 파라미터이다. 0으로 설정하면 처음부터 스킵 리스트에 저장되어 테스트 시 성능을 좀 더 정확하게 파악할 수 있다.

• zset-max-ziplist-value는 zip list로 저장할 수 있는 값(value)의 최대 길이이다.