zip list

Redis는 모든 데이터를 메모리(RAM)에 저장한다. 메모리는 디스크에 비해 비싼 자원이기 때문에 메모리를 절약하기 위해 zip list라는 메모리 효율적인 데이터 구조를 사용하며, 이는 작은 크기의 문자열들을 저장하는데 최적화되어 있다.

주로 Redis의 List, Hash, ZSet(Sorted Set) 등의 내부 구현에서 사용된다.

배열과 연결 리스트

배열은 크기가 고정되어 있고 동적 할당이 어렵다. 또한 중간에 삽입/삭제 시 모든 요소의 이동이 필요하게 되는데 이는 O(N) 시간 복잡도를 갖게 된다.

연결 리스트는 각 노드를 연결하는 주소값을 저장하는 next/prev 포인터가 필요하다. 이는 메모리 오버헤드를 증가시키고, 각 노드들은 메모리상 흩어져 있기 때문에 캐시 효율이 떨어진다.

zip list는 작은 데이터를 저장할 때 배열의 확장성과 연결 리스트에 삽입/삭제 용이성의 장점을 가지면서 메모리 효율성까지 갖춘 자료구조이다.

그 이유는 동적으로 크기를 조절할 수 있고, 포인터 대신 이전 엔트리의 길이만 저장하여 메모리를 절약한다.

zip list 자료구조

zip list는 연속된 메모리 블록을 사용하여 데이터를 저장한다.

구조를 봤을 때 동적으로 메모리 할당이 가능하고 메모리를 연속적으로 할당한다고 해서 정확히 어떤 자료구조로 이루어졌는지 궁금증이 생겼다.

조사한 바로는, 실제 순수 배열 혹은 연결 리스트가 아닌, 두 가지의 장점을 결합한 특별한 자료구조라고 한다.

• 연속된 블록을 사용하지만 배열처럼 고정 크기로 미리 할당하지 않고 필요한 경우 동적으로 할당

• 각 노드는 이전/다음 엔트리의 거리를 포함하고 있어서 양방향 탐색이 가능

// 일반적인 연결 리스트의 경우
[노드1] -> [노드2] -> [노드3]   // 메모리 상 흩어져 있음
주소:  1000     2500     1750    // 불연속적인 메모리 주소

// zip list
[노드1][노드2][노드3]  // 붙어있는 메모리 블록
주소: 1000  1016  1032 // 연속적인 메모리 주소

이렇게 연속된 메모리를 사용하여 단편화를 감소하고 캐시 지역성의 이점을 얻을 수 있다고 한다.

연속된 각 블록은 헤더(zlbytes, zltail, zllen)와 엔트리들, 끝을 나타내는 zlend로 구성된다.

헤더

• zlbytes: zip list 총 바이트 수

• ztail: 마지막 엔트리 시작 지점(offset)

• zllen: zip list의 총 엔트리 수

• zlend: zip list의 끝을 나타내는 바이트

엔트리 구조

1. prelen(previous_entry_length)

이전 엔트리 길이를 저장하고 있다. 이전 엔트리를 찾을 때, 현재 위치의 prelen 값을 읽고 그 크기만큼 뒤로 이동하면서 이전 엔트리의 시작 점에 도달한다.

1. itself len(encoding + length):

엔트리 자신의 값(value)의 길이를 나타내고 순방향 탐색과 값 조회용으로 사용된다. 현재 엔트리의 타입과 길이 정보를 저장하는데, 정수값의 경우에는 특별한 인코딩을 사용하여 저장한다고 한다.

1. value(actual data):

실제로 저장되는 데이터 값이 저장된다. 문자열 또는 정수 타입으로 저장한다.

만약 실수의 경우 숫자를 직접 저장하지 않는다. 그 이유는 double형으로 바꾸는 것이 메모리를 더 많이 사용할 경우가 많으므로 문자열 그대로를 저장한다.

Summary

일반적인 연결 리스트라면, 각 노드마다 next/prev 포인터가 필요하지만 zip list에서는 이전 엔트리의 길이만 저장한다. 이처럼 연속된 메모리 블록을 사용하여 포인터가 필요 없으므로 메모리 공간 절약에 효율적이다.

Reference

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

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