Mingyu Kim

Sorted Set - ZipList

Linked List가 데이터 하나를 저장할 때마다 앞뒤를 가리키는 포인터(주소값)를 저장하여 메모리를 낭비하는 문제를 해결하기 위한 구조

포인터를 버리고, 모든 데이터를 하나의 연속된 바이트 덩어리(Byte Array)에 때려 넣는다.

1. ZipList의 내부 메모리 구조

메모리상에서 끊김 없이 쭉 이어진 형태를 가진다. 각 엔트리(데이터)는 자신이 얼마나 큰지, 이전 데이터가 어디서 끝나는지를 기록하여 포인터 없이도 다음 데이터로 이동할 수 있다.

• zlbytes (4바이트): ZipList 전체가 차지하는 총 바이트 수
• zltail (4바이트): 마지막 엔트리까지의 오프셋(거리). 덕분에 맨 뒤에 데이터를 추가하거나 뒤에서부터 읽는 게 빠름
• zllen (2바이트): 전체 엔트리의 개수
• Entry: 실제 데이터가 담긴 곳
• zlend (1바이트): ZipList의 끝을 알리는 특수 마커(0xFF)

2. Entry(데이터)의 세부 구성

각 엔트리는 앞뒤를 탐색하기 위한 정보를 ‘가변 길이’를 가진다.

• prevlen (Previous Entry Length): 바로 이전 엔트리의 길이를 저장(덕분에 포인터가 없어도 역방향 탐색 가능)
• encoding: 데이터가 문자열인지 숫자 인지, 몇 바이트인지 정보를 저장
• entry-data: 실제 저장된 값

3. 치명적인 단점: “연쇄 업데이트”

만약 이전 데이터가 갑자기 커져서 prevlen 자체의 기록 공간(1바이트 -> 5바이트)이 늘어나야 한다면?

• 그 뒤에 있는 모든 엔트리들의 시작 위치가 밀리면서, 줄줄이 prevlen 값을 수정해야 하는 상황이 발생
• 이로 인해 최악의 경우 $O(N^2)$의 비용이 발생할 수 있음

이 문제를 해결하기 위해 최신 레디스(7.0+)에서는 ZipList를 폐기하고, 더 안전하고 효율적인 Listpack으로 대체했다.

4. 왜 O(N)인데 쓰는 걸까?

• CPU 캐시 효율: 데이터가 메모리에 다닥다닥 붙어 있어서 한 번 읽을 때 CPU 캐시에 몽땅 올라온다.
• 포인터 오버헤드 제거: 64비트 시스템에서 포인터 하나는 8바이트입니다. 데이터가 1바이트인데 포인터가 8바이트면 배보다 배꼽이 더 크다. ZipList는 이 낭비를 완벽히 제거한다.