[redis] 레디스 내부 동작 이해 : sorted set

오늘은 레디스의 sorted set 의 내부 작동원리에 대해 이해한것을 정리해보려 한다. 아래 내용이 포함된다.

1. sorted set 지원 기능 정리

2. sorted set 내부 동작원리

3. skip list 자료구조의 주요 기능(탐색, 삽입, 삭제..)들이 왜 O(log N)인지에 대한 수학적 분석

4. sorted set은 왜 내부적으로 BST를 쓰지 않았을까?(이건 TMI지만 개인적인 호기심ㅎ)

5. hash table 자료구조 동작원리

 

Overview

sorted set은 고유한 요소(멤버)와 실수형 점수를 쌍으로 저장하며, 점수를 기준으로 항상 정렬된 상태를 유지하는 데이터 구조이다. 시간복잡도 측면에서 당연하겠지만 모든기능은 O(log N)이다(시간복잡도란 해당기능이 수행되는데 걸리는 시간을 데이터의 크기(N)과 관련지어 설명하는 수학적인 방식)

 

핵심 기능들을 정리해보면 아래와 같다.

1. ZADD: 요소 추가

ZADD 명령은 Sorted Set에 새로운 요소를 추가하거나, 기존 요소의 점수를 업데이트한다. 점수를 기준으로 요소가 자동으로 정렬되며, 삽입할 때마다 정렬 상태가 유지된다.

2. ZSCORE: 점수 조회

ZSCORE는 특정 요소의 점수를 조회한다. 해당 요소가 Sorted Set에 존재하는 경우, 그에 대응하는 점수를 반환한다.

3. ZRANK / ZREVRANK: 순위 조회

ZRANK는 특정 요소가 Sorted Set에서 몇 번째 순위에 있는지 조회한다. 점수가 작은 순서대로 정렬된 상태에서의 순위를 반환하며, ZREVRANK는 반대로 점수가 큰 순서대로 순위를 반환한다.

4. ZRANGE / ZREVRANGE: 범위 내 요소 조회

ZRANGE는 점수가 작은 순서대로 지정된 인덱스 범위에 해당하는 요소들을 반환한다. ZREVRANGE는 점수가 큰 순서대로 반환한다. 이 명령을 통해 Sorted Set의 특정 구간에 있는 요소들을 조회할 수 있다.

5. ZREM: 요소 삭제

ZREM은 Sorted Set에서 특정 요소를 삭제한다. 해당 요소는 Sorted Set에서 제거되며, 더 이상 점수와 함께 저장되지 않는다.

6. ZCOUNT: 점수 범위 내 요소 개수 조회

ZCOUNT는 지정된 점수 범위 내에 속하는 요소들의 개수를 반환한다. 특정 점수 구간에 해당하는 데이터의 크기를 파악하는 데 유용하다.

7. ZRANGEBYSCORE / ZREVRANGEBYSCORE: 점수 범위 내 요소 조회

ZRANGEBYSCORE는 지정된 점수 범위 내에 있는 요소들을 반환한다. 점수가 작은 순서대로 정렬된 결과를 제공하며, ZREVRANGEBYSCORE는 점수가 큰 순서대로 반환한다.

8. ZREM / ZREMRANGEBYRANK / ZREMRANGEBYSCORE: 요소 삭제

ZREM은 특정 요소를 삭제하고, ZREMRANGEBYRANK는 지정된 순위 범위 내의 요소들을, ZREMRANGEBYSCORE는 지정된 점수 범위 내의 요소들을 삭제한다.

 

Sorted Set 내부 구현

내부에 skip list 와 hash table 을 결합한 특이한 형태의 자료구조를 사용하고 있다. hash table은 멤버를 통해 점수를 조회하는 기능을 O(1)에 근접하게 처리하기 위해, 또한 멤버를 유니크하게 관리하기 위한 목적등으로 사용하는 것으로 보인다.

 

Skip List는 점수를 항상 정렬된 형태로 관리하는 리스트형 자료구조인데 BST형 자료구조와 마찬가지로 특정요소 추가/삭제/수정 기능 모두 O(log N)을 지원하기 위해 사용하는 것으로 보인다. redis는 Skip List의 노드에 점수와 함께 멤버의 포인터를 함께 저장하므로 점수범위나 등수범위로 요소들을 조회하는것을 빠르게 지원할 수 있다.

 

조금 디테일한 내용이기는 하지만 redis는 Sorted Set 이 만들어진 처음부터 바로 skip list를 사용하지는 않는다. 요소의 갯수가 특정설정값 이하 일때는 zip list라는 데이터구조를 사용하고 이게 넘어가면 sorted set을 사용하게 되는구조이다. 주된 이유는 메모리의 효율적인 사용이다.

 

sorted set은 자료구조 특성상 연산속도를 빠르게 하기위해 여러 메타데이터가 추가되기에 메모리 오버헤드가 있는편이다. 요소갯수가 적을때는 전체 처리량이 적기 때문에 연산량의 비효율을 감안하고라도 메모리를 최대한 적게 쓰는 방향을 의도했는데, zip list는 이러한 의도에 딱 맞는, 메모리를 최대한 컴팩트하게 줄이는데 목적을 둔 list이다. zip list 는 여기, redis official 잘 설명되어 있다.

 

skip list

1. 기본 구성

Skip List는 기본적으로 여러 레벨의 연결 리스트로 이루어진다. 가장 아래 레벨(Level 1)은 모든 요소를 포함하고, 상위 레벨로 갈수록 요소 수는 점차 줄어든다. 최상위 레벨은 최소한의 요소만 포함하여 탐색할 수 있게 한다.

2. 노드 구성

각 노드는 여러 레벨의 포인터를 가진다. 예를 들어, 노드 A가 Level 3까지 연결된 경우, A는 자신 다음에 오는 노드에 대해 1레벨씩 건너뛰어 접근할 수 있다. 이 덕분에 노드 A는 Level 1, 2, 3에서 각각 다른 범위의 요소들과 연결된다.

3. 탐색 방식

탐색은 최상위 레벨(Level k)에서 시작한다. 먼저 상위 레벨에서 다음 노드로 이동할 수 있는지 확인하고, 이동할 수 없다면 한 단계 아래 레벨로 내려가며 탐색을 계속한다. 최종적으로 Level 1에 도달할 때까지 이 과정을 반복하며, O(log N) 시간에 원하는 요소에 도달한다.

 

logN을 더 잘 이해하기위해 부가적으로 설명해 보자면.. Skip List의 레벨 1에는 모든노드가 포함되고, Level 2에는 그 절반의 노드가 포함된다. 왜냐하면 각 노드가 상위 레벨을 갖을 확률은 항상 50%이기 때문이다. 레벨 3에도 그와 마찬가지로 1/4 노드가 포함된다. 따라서, 레벨 K에는 N / 2^K 개의 노드가 포함되게 된다. 이런식으로 생각했을때 최상위 레벨은 평균적으로 1개의 노드가 있게 되고, 그 높이는 근사적으로 Log_2_N이 된다. 탐색은 최상위 레벨에서 시작하여 각 레벨마다 오른쪽으로 이동하고 더 이상 이동할 수 없으면 하위 레벨로 내려가는 방식이다. 각 레벨에서 오른쪽으로 이동하는 횟수는 상수시간으로, 약 2번정도 이동하면 탐색경로가 결정된다(이 부분은 노드가 상위레벨로 올라갈 확률이 50% 이므로, 오른쪽으로 이동할 수 있는 평균 횟수는 매우 적다는 점에서 나온다). 그로므로, 탐색이 각 레벨에서 상수 시간에 이루어지고, 레벨의 수는 log_2_N 이므로 탐색의 총 시간은 O(log N) 이다.

4. 삽입

새로운 요소를 삽입할 때는 먼저 적절한 위치를 찾기 위해 탐색 과정을 수행한다. 삽입 위치가 결정되면, 새 노드가 몇 개의 레벨에 걸쳐 연결될지를 랜덤하게 결정한다. 이때 각 레벨마다 상위 레벨에 올라갈 확률은 보통 50%로 설정된다. 삽입이 완료되면, 새 노드는 해당하는 모든 레벨에서 기존 노드들과 연결된다.

5. 삭제

삭제 연산도 삽입과 유사하게 진행된다. 먼저 삭제할 요소를 찾고, 해당 요소가 포함된 모든 레벨에서 노드를 제거한다. 각 레벨에서 제거 작업이 이루어진 후, 노드 간의 연결 관계를 다시 맞춰준다. 삽입의 과정과 매우 유사하다고 볼 수 있는데, 해당 노드를 탐색하면서 각 레벨에서 해당 노드를 모두 지워주는 과정을 하면서 탐색한다고 보면 된다.

6. 레벨확률에 따른 탐색시간, 메모리사용 변화

해당 skip list 논문 저자인 Pugh 는 탐색시간과 포인터갯수(메모리사용)를 고려하여 p를 1/4로 사용하는것을 권장했다고 한다.

 

 

왜 sorted set은 BST를 사용하지 않고 skip list를 사용했을까?

개인적으로는.. BST의 경우 노드가 매우 많을경우 노드 삭제나 추가시 균형을 맞추기위한 작업이 비대한 경우들이 있어 일관된 성능보장이 힘들어서가 아닐까 싶었다. 아래는 antirez 가 밝힌 내용이다.

https://stackoverflow.com/questions/45115047/why-redis-sortedset-uses-skip-list-instead-of-balanced-tree

There are a few reasons:
They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.

A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.

They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

About the Append Only durability & speed, I don't think it is a good idea to optimize Redis at cost of more code and more complexity for a use case that IMHO should be rare for the Redis target (fsync() at every command). Almost no one is using this feature even with ACID SQL databases, as the performance hint is big anyway.

About threads: our experience shows that Redis is mostly I/O bound. I'm using threads to serve things from Virtual Memory. The long term solution to exploit all the cores, assuming your link is so fast that you can saturate a single core, is running multiple instances of Redis (no locks, almost fully scalable linearly with number of cores), and using the "Redis Cluster" solution that I plan to develop in the future.

 

sorted set 내부 hash table

해시테이블은 어떤 데이터든 O(1)에 근접하게 접근할 수 있는 자료구조로 해시함수를 사용하여 데이터를 배열에 저장하는 방식이 기본구현으로 사용된다. sorted set 에서는 hash table 로 중복되지 않은 멤버가 저장되도록 관리하고, 멤버로 스코어를 조회시 O(1)에 조회할 수 있도록 값을 저장하기위해 사용한다.

 

아래는 Hash Table의 핵심 개념들을 정리한 내용이다.

1. 해시 함수

Hash Table은 데이터를 저장할 때 해시 함수(hash function)를 사용하여 키를 해시값으로 변환한다. 해시 함수는 입력된 키를 특정 정수 값(해시값)으로 변환하며, 이 해시값을 배열의 인덱스로 사용한다. 이 과정을 통해 데이터의 저장 위치를 빠르게 찾을 수 있다.

예를 들어, hash(key) % table_size 방식으로 배열 내 인덱스를 결정한다.

2. 배열 기반 저장

Hash Table은 내부적으로 고정 크기의 배열을 사용해 데이터를 저장한다. 해시 함수로부터 얻은 해시값을 배열의 인덱스로 사용하여 데이터를 저장하거나 조회한다. 만약 배열의 크기를 초과하는 해시값이 발생하면, 모듈러 연산(%)을 통해 배열 크기에 맞는 인덱스를 계산한다.

3. 리사이징(Resizing)

Hash Table은 배열의 크기가 꽉 차거나 충돌이 빈번해지면 리사이징을 통해 배열의 크기를 증가시키는데, 리사이징이 발생하면, 기존 데이터를 새로운 크기의 배열에 다시 해시해서 재배치해야 한다. 이 과정은 O(N) 시간이 소요되지만, 리사이징을 통해 해시 테이블의 성능을 유지한다.

4. 충돌 처리

해시 함수는 서로 다른 키에 대해 같은 해시값을 반환할 수도 있는데, 이를 충돌이라고 한다. 충돌이 발생하면 이를 해결하는 방식은 두 가지 가 있는데, 체이닝과 오픈어드레싱 방식이다. 레디스에서는 체이닝방식을 사용하는것으로 보인다.

• 체이닝(Chaining): 충돌이 발생한 경우, 해당 인덱스에서 연결 리스트를 사용하여 동일한 인덱스에 저장된 여러 데이터를 관리한다. 즉, 동일한 해시값을 가진 데이터를 연결 리스트로 이어 저장하며, 새로운 데이터가 들어오면 리스트의 끝에 추가한다.
• 오픈 어드레싱(Open Addressing): 충돌이 발생하면 다른 빈 슬롯을 찾아 데이터를 저장한다. 이 방식은 여러 가지 탐색 전략이 있는데, 그중 가장 일반적인 방법은 선형 탐사(Linear Probing)이다. 충돌이 발생하면 다음 인덱스를 순차적으로 탐색해 빈 공간을 찾아 데이터를 저장하는 방식이다.

 

 

 

참고

redis zip list 

http://redisgate.kr/redis/configuration/internal_ziplist.php

redis zip list(official)

https://redis.io/glossary/redis-ziplist/

skip list(cmu cs)

https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/skiplists.pdf

hash table(cmu cs)

https://www.cs.cmu.edu/~mrmiller/15-121/Slides/25-HashTables.pdf

Pugh, W. (1990). Skip Lists: A Probabilistic Alternative to Balanced Trees(skip list 논문 링크)

https://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
https://epaperpress.com/sortsearch/download/skiplist.pdf
[Redis] ZSet의 내부 구조: skip 리스트

https://bugoverdose.github.io/posts/86/