redis sorted set

[skarltjr]

1. 개요

지속적인 데이터 정렬을 위한 저장소 선정과정에서 redis sorted set을 고려하려고한다.
그러기 위해서 이것이 어떻게 동작하는지 이해가 선행되어야한다고 생각.

2. 개념

Redis의 sorted set은 개별적인 각 멤버(data)라는 collection을 저장하며,
각 멤버는 score라는 구성요소를 포함한다.
각 데이터는 이 score에 의해 정렬된다.

3. 기본적인 동작 방식

1. sorted set의 각 멤버(데이터)는 유니크하다. 즉 같은 이름의 데이터는 존재할 수 없다

2. 모든 멤버는 스코어에 해당하는 데이터를 갖고 있다.
이 스코어에 의해 정렬된다.

3. 각 멤버는 레디스의 자료구조인 skiplist로 저장되는데 
이 자료구조는 검색과 insert에 최적화되어있다.

4. skiplist는 연결리스트로 구성되는데, 각 노드는 score value를 가지며 다음 노드에 연결되어있다.
첫번쨰 노드는 가장 작은 score를 가지며 마지막 노드가 가장 큰 score를 가진다.

5. 그래서 새로운 멤버를 insert하면 score value에 따라 연결리스트를 타고타고
삽입 위치를 결정하여 삽입한다.

6. 이러한 연결리스트를 바탕으로 상위 n개 등 조회 가능

• 참고로 정렬은 매 insert 시점에 일어난다.
• 그러니까 비교적 read-heavy workloads를 갖는다면 삽입 시점에만 정렬을하는 레디스가 유리할 수 있다.

참고 : http://redisgate.kr/redis/configuration/internal_skiplist.php

[skarltjr]

Skiplist 좀 더 알아보기

들어가기 앞서 사실 sorted set은 크게 두 자료구조를 활용한다
zip-list , skip-list
멤버수가 128개보다 작을때 zip-list를 사용하는데 아무래도 사실상
거의다 128개를 넘어가지않을까싶다.

다만 알아야할것은 왜 이렇게 분리했을까?
메모리 절약을 위해서.

skiplist 이해하기

1. skiplist는 정렬된 상태를 유지하면서 데이터 삽입,삭제 및 탐색을 할 수 있는 구조체

• 기본적으로 연결리스트 형태를 사용한다.

2. 연결리스트의 단점 개선하기

2-1. 기본 연결리스트

• 

보이는것처럼 만약 80을 찾는경우가 발생( 예를들어, 80을 새로 삽입하거나 그냥 조회를 하거나...)
그런데 연결리스트라면 80전까지 최대. n번의 비교가 필요. 즉 매번 최대 n개 데이터 순회가 필요할 수 있다는 문제점

2-2. 레벨 도입

그럼 우리는 이런 비교 횟수자체를 줄인다면 성능 개선을 할 수 있을것이다.
따라서 skiplist는 레벨이라는 개념을 갖는다.
레벨이란 홀수 노드는 포인터를 1개만 / 짝수 노드는 포인터를 2개 갖는것으로
즉 짝수 노드는 다음 노드를 향하는 포인터 + 다음 다음 노드를 향하는 포인터 총 2개를 갖는다..

• 

2-3. n개의 레벨

• 

3. 레벨의 문제

여기까진 탐색시에는 굉장히 효과적이다
그런데 만약 삽입, 삭제가 발생하면? 
- 모든 레벨이 수정되어야한다. 그리고 이는 곧 삽입/삭제 시간이 굉장히 오래걸리게될것

[skarltjr]

새로운 레벨 선정 방법

앞선 방법은 탐색에 효과적이지만 삽입/삭제에 대처가 제대로 안된다.
그래서 이들은 새로운 방법을 생각했고 핵심포인트는

"각 노드의 레벨은 독립적으로 정해져야한다."
즉 skiplist의 총 노드수, 순서등에 관계없이 한 번 정해지면 바뀌지 않아야한다.
그럼 새로운 삽입/ 삭제에 각 노드의 레벨이 영향을 받지 않고 유지할 수 있다.

• 

확률을 통해 레벨을 갖는다.

일단 각 노드가 개별적인 레벨을 갖기 때문에 삽입/삭제에 영향을 받지 않는다.

추가로 인상깊은점은 레벨 10처럼 높은 레벨이 거의 나올일이 없어진다는건데
이게 메모리와 연관있다는것이다.

앞에서 레벨이 3정도만 되어도 한 노드가 갖는 포인터가 3개가된다.
즉 레벨이 10이면 한 노드가 10개 포인터까지 갖게되어 메모리를 많이 차지한다. 이런 부분을 개선한거같다.

여전히 남은 문제점

여전히 남은 문제점은 확률로 레벨을 정하다보니 
레벨을 통해 정렬된 상태는 유지되지만 이게 몇번째인지 알 수 없다.


노드 1  노드 2  노드 3  노드 4
레벨 1  레벨 1  레벨 2  레벨 3

이라고 했을때 노드1, 노드2는 개별 레벨을 갖고. 레벨순으로 정렬되어 있지만
이게 노드 2 노드 1 순일수도있고 반대일수도있고

순서를 위한 span field

• 

이를위해 레디스는 레벨에 포인터와 순서를 가지는 필드를 만들어 정하고 이를 span이라고한다.

여기서 보면 

span
[n][pointer]로 이루어진다.
여기서 n은 현재 위치로부터 n칸 떨어진곳

그럼 우리가 20을 찾는다고 가정해보자.
레벨 0 사용하면 한칸 이동했을때 나오는 13
레벨 1사용하면 3칸 이동했을때 나오는 18
레벨 2 사용하면 5칸 이동했을때 나오는 25

우리가 찾는건 20이니까 레벨1을 사용
18로 이동해왔다. 

다시 18에서 레벨 0부터.. 

[skarltjr]

마지막 span의 경우
완벽 이해는 어렵다. 머리로 아직 제대로 못따라가겠다.

하지만 redis의 sorted set 레벨의 활용을 통해 탐색의 속도를 개선하며
무엇보다 삽입시점마다 재정렬이 일어나지 않고, score에 기반하여 자신의 자리를 찾아가기때문에
굉장히 효과적이라고 생각할 수 있었다.