[redis] list

redis를 캐싱 툴로만 활용할 경우, 대부분의 상황은 string만으로도 해결 가능한 경우가 많다.

그러나 애플리케이션 요구사항상 string 이외의 자료구조가 필요한 경우도 존재한다.
따라서 Redis의 여러 자료구조를 학습하는 것을 목표로 한다.

Redis List

Redis List는 연결 리스트의 형태이다.
이 말은 즉, head와 tail에서 삽입과 삭제 연산이 가능하다는 뜻이다.

이것이 가능한 이유는 각 노드가 자신의 저장 데이터뿐만 아니라 다음 노드의 주소를 저장하고 있기 때문이다.
따라서 포인터를 두 개 변경하는 방식으로 어떤 원소를 추가하거나 삭제하는 연산이 쉽다.

예를 들어 a -> b 구조에서 c를 추가할 경우,
a -> c, c -> b 와 같이 연결을 변경해 구현할 수 있다.

과거 Redis List의 인코딩 방식

과거 Redis List의 인코딩 방식은 요소의 양과 크기에 따라 나뉘었다.

첫 번째는 요소의 양이 적고, 요소의 크기도 작은 경우이다.
이 경우는 ziplist 형태로 압축해 저장했다.
이를 통해 연속된 메모리 공간에 데이터를 저장할 수 있었다.

• 메모리 효율을 위해 최대한 붙여 데이터를 저장하므로 “압축 리스트”라고 부른다.

두 번째는 요소의 양이 많고, 요소의 크기도 큰 경우이다.
이 경우는 linked list를 활용하며, 각 요소가 포인터로 연결되어 삽입과 삭제가 빠르다.

Redis 7.0 이후의 quicklist

Redis 7.0 이후부터는 quicklist라는 형태로 List를 제공하고 있다.
이는 하이브리드 리스트로, ziplist와 linked list를 여러 개 합쳐 활용하는 구조이다.

전체 리스트를 여러 블록으로 나누고, 각 블록은 ziplist 형태로 압축해 저장한다.
그리고 그 블록들을 다시 연결 리스트로 연결하는 형태이다.

이를 통해 성능과 메모리 효율을 모두 어느 정도 확보할 수 있다.

• 성능: 연결 리스트처럼 양끝 삽입/삭제에 유리
• 효율: 각 블록 내부는 압축 리스트이므로 메모리 낭비를 줄일 수 있음

Redis List의 특징

Redis List는 일반적인 list의 특징도 함께 가진다.

• index를 통해 접근 가능
• 동일 요소 저장 가능(중복 허용)

또한 List에는 2^32 - 1 개의 요소를 저장할 수 있다.
이는 약 42억 개의 요소를 저장할 수 있다는 의미이다.

다만 실제로 그 정도 크기의 리스트를 운영하는 경우, Redis 서버의 메모리가 제약이 될 수 있다.
예를 들어 각 요소가 평균 100byte라고 하면, 100만 개의 요소만으로도 약 100MB가 필요하기 때문이다.

Redis List 명령어

List 자료구조를 다루기 위한 주요 명령어는 다음과 같다.

• push
• pop
• lrange
• llen
• lindex

push

• LPUSH
• RPUSH

각각 왼쪽, 오른쪽으로 요소를 추가한다.

예를 들어,

LPUSH mylist v1 v2

의 경우 v1을 먼저 추가한 뒤, v2를 다시 왼쪽에 추가하므로 최종 순서는 다음과 같다.

v2 v1

추가 후에는 List의 길이를 반환한다.

예외 상황

• key가 존재하지만 list가 아닌 경우
  → error 반환

• key에 대해 value가 없는 경우
  → Redis가 자동으로 리스트를 생성하고 원하는 원소를 추가

추가 연산의 시간 복잡도

O(1)

이유는 head 또는 tail에서의 추가는 포인터 방향만 수정하면 되기 때문이다.

다만, 요소를 “찾는” 경우는 다르다.
원하는 위치까지 직접 노드들을 따라가야 하므로, 최악의 경우 n개의 원소에 대해 n번의 연산이 발생할 수 있다.

즉, LPUSH와 RPUSH가 O(1)이라고 하는 것은
원소를 추가하는 명령 자체의 비용을 말하는 것이다.

따라서 맨 앞, 맨 뒤로 추가하는 경우의 비용은 순수하게 O(1)일 것이다
그러나 실제로 중간 요소를 찾아 삽입하는 경우
찾는 연산에 추가적으로 O(n)이 발생하게 된다

pop

• LPOP
• RPOP

각각 왼쪽, 오른쪽에서 요소를 제거할 수 있다.

pop 연산의 시간 복잡도는 push와 동일하다.

빈 리스트의 경우

마지막 요소가 제거되면 빈 리스트가 유지되는 것이 아니라,
key 자체가 자동으로 삭제될 수 있다.

따라서 EXISTS 같은 명령어로 확인할 경우 주의가 필요하다.

즉,

• “원래 있었지만 비어 있는 리스트”
• “애초에 존재하지 않았던 key”

를 Redis에서는 동일하게 볼 수 있다.

LRANGE

리스트에서 지정한 범위의 요소를 조회하는 용도이다.

예시:

LRANGE mylist 0 -1
→ 음수 인덱스를 지원하므로 0부터 리스트의 끝까지 조회

LRANGE mylist 0 100
→ 리스트 크기가 5라면 100까지 지정하더라도 실제 존재하는 5개까지만 출력

형태는 다음과 같다.

LRANGE key start stop

이때 stop 인덱스의 요소도 포함한다.
예를 들어 stop = 3이면 3번 인덱스까지 조회한다.

연산 비용

O(s + n)

• s: start index까지 이동하는 비용
• n: 반환할 요소 개수

연결 리스트 기반이기 때문에 head와 tail에 대한 연산은 빠르지만,
중간 요소를 조회해야 하는 경우에는 직접 그 위치까지 이동해야 하므로 성능 이슈가 발생할 수 있다.

따라서 LRANGE는 다음과 같은 경우에 적합하다.

• 양끝의 작은 범위 조회
• 전체 리스트 조회

LLEN

List의 길이, 즉 요소의 개수를 반환한다.

연산 비용

O(1)

이는 요소를 모두 조회해서 길이를 계산하는 것이 아니라,
길이를 메타데이터로 따로 저장하고 있기 때문이다.

예를 들어 작업 큐에 대기 중인 작업 수를 확인할 때 유용하다.

예시:

LLEN mylist

이는 push, pop 시 length 를 반환할 때도 동일하게 쓰인다

LINDEX

특징은 다음과 같다.

• 0부터 지원
• 인덱스 범위를 벗어나면 nil 반환
• 음수 인덱스 지원(끝에서부터 셈)

연산 비용

O(n)

여기서 n은 접근하려는 원소의 위치이다.
직접 포인터를 그만큼 이동해야 하기 때문이다.

양끝의 원소는 상대적으로 빠르지만,
중간 원소는 느리다는 점도 이 때문이다.

List는 언제 사용하는가?

Redis List는 주로 큐(queue), 스택(stack)과 같은 구조를 구현할 때 사용한다.

queue: FIFO

먼저 들어온 데이터가 먼저 나가야 하므로 다음과 같은 조합으로 구현할 수 있다.

• RPUSH + LPOP
• LPUSH + RPOP

stack: LIFO

마지막에 들어온 데이터가 먼저 나가야 하므로 다음과 같은 조합으로 구현할 수 있다.

• LPUSH + LPOP
• RPUSH + RPOP

blocking

이러한 자료구조를 활용하면 서비스 간 결합을 줄이면서,
이벤트처럼 동작하는 구조를 만들 수 있다.

다양한 분산 환경에서 큐나 스택을 Redis로 구현하고,
이 자료구조를 통해 이벤트를 전달받는 형태로 사용할 수 있는 것이다.

이와 같은 점에서 활용도가 높다.

예를 들어 blocking 버전의 pop을 사용하면,
list가 비어 있을 때 즉시 nil을 반환하는 것이 아니라
요소가 추가될 때까지 대기하도록 만들 수 있다.

예시:

BLPOP queue 0

여기서 0은 무한 대기를 의미한다.

즉, block 계열 명령이므로

• 큐에 요소가 있다면 즉시 반환
• 비어 있다면 요소가 들어올 때까지 대기

또한 다음과 같이 여러 큐를 동시에 모니터링할 수도 있다.

BLPOP queue1 queue2 0

이를 통해 consumer / producer 구조를 구현하기에 적합하다.

polling보다 효율적인 이유

이 방식은 polling보다 효율적이며 event처럼 동작한다.

• polling: 계속해서 상태를 확인
• event 기반: 실제 이벤트가 발생했을 때만 동작

즉, polling은 변화가 없어도 계속 확인 비용이 발생하지만,
event 기반은 변화가 생겼을 때만 처리하므로 자원을 절약할 수 있다.

또한 애플리케이션이 직접 while 문으로 계속 확인하지 않더라도,
운영체제는 자원 요청을 인터럽트 기반으로 받아 처리할 수 있다.

따라서 애플리케이션 레벨에서는 polling 없이도 event처럼 동작하는 구조를 만들 수 있다.

다만 이를 “OS가 계속 폴링한다”고 단순화하면 부정확하다.

핵심은 다음 두 가지를 구분하는 것이다.

• 애플리케이션 레벨의 바쁜 폴링(busy polling)
• OS 레벨의 인터럽트 + 대기 큐 기반 처리

즉, 이벤트 기반 구조에서는
애플리케이션이 계속 확인하는 것이 아니라,
OS나 런타임이 대기하고 있다가 조건이 충족되면 깨워주는 방식에 가깝다.