Redis Sorted Set은 왜 Skip List를 선택 했을까?

 

Skip List

스킵리스트는 여러 레벨의 연결 리스트를 확률적으로 구성해 평균 O(log N)에 탐색·삽입·삭제를 지원하는 자료구조

 

장점

• 스킵 리스트는 다중 레벨로 구성된 연결 리스트 구조를 가지므로, 일반 연결 리스트의 탐색·삽입·삭제가 O(N)인 것에 비해 평균 O(log N)에 수행된다.
• 범위 탐색이 효율적이다. O(log N + M)
• B-트리와 달리, 스킵 리스트는 별도의 리밸런싱 과정 없이 노드 간 포인터만 조작하여 삽입과 삭제가 가능하다.

단점

• 각 노드가 여러 레벨의 포인터를 갖기 때문에 연결 리스트에 비해 메모리 사용량이 많다.
• 확률적 구조 특성상 최악의 경우에는 일반 연결 리스트와 동일한 O(N)의 시간 복잡도를 가질 수 있다.

---

 

Redis Sorted Set은 왜 Skip List를 선택 했을까?

 

antirez
1) 메모리를 많이 차지하지 않습니다. 기본적으로 사용자에게 달려 있습니다. 노드가 주어진 수의 레벨을 가질 확률에 대한 매개변수를 변경하면 btrees보다 메모리 사용량이 줄어듭니다.
2) 정렬된 집합은 종종 링크된 목록으로 스킵 목록을 트래버스하는 ZRANGE 또는 ZREVRANGE 연산의 대상이 됩니다. 이 연산을 사용하면 스킵 리스트의 캐시 위치가 적어도 다른 종류의 균형 트리만큼 우수합니다.
3) 구현, 디버그 등이 더 간단합니다. 예를 들어 건너뛰기 목록의 단순성 덕분에 저는 O(log(N))에서 ZRANK를 구현하는 증강 건너뛰기 목록이 포함된 패치(이미 Redis 마스터에 있음)를 받았습니다. 코드 변경은 거의 필요하지 않았습니다.

 

처음에는 B+트리 구조가 쓰기 작업이 많을 때 잦은 리밸런싱으로 인해 추가적인 디스크 I/O가 발생해 비효율적일 것이라 생각했다.
하지만 Redis는 모든 데이터를 메모리에서 처리하므로, B+트리의 모든 노드가 메모리 상에만 존재한다면 디스크 I/O가 발생하지 않아 성능 차이가 크지 않을 것 같다.

결국 Skip List를 선택한 이유는 구현과 디버깅이 상대적으로 쉽고, 매개변수를 조정해 메모리 사용량을 유연하게 관리할 수 있기 때문이다.

 

 

---

https://news.ycombinator.com/item?id=1171423