(CS Study) Redis List 정복 : 내부 구조부터 Queue / Stack으로의 활용까지

👀 들어가기 전에

Redis를 어느정도 사용하다보면 자연스럽게 Redis에서 사용하는 자료구조들에 관심이가고, 

이 중 List를 어떻게 써야 할지 고민하는 시점이 오게 됩니다.

특히 

• 이벤트 처리
• 비동기 작업 큐
• 최근 기록 관리
• Producer / Consumer 구조 (물론, Redis에서 제공해주는 pub/sub 라이브러리가 존재하기는 한다.)

에서 Redis List를 쓰면 좋겠다라는 생각이 드는데,

 

막상 내부 구조나 성능 특성을 제대로 모르고 사용하면

잘못쓰게 되고 결국 성능 병목으로 이어질 수 밖에 없습니다.

 

그래서 이번 글에서는 Redis List의 내부 구조 + 시간 복잡도 + 실전 활용 패턴까지 정리해보도록 하겠습니다.

---

👀 본론

1. Redis List란?

답부터 이야기하면, 문자열 값(String)들의 연결리스트(LinkedLIst)입니다.

Redis의 List는 LinkedList로 구현되어 있습니다. 

 

그렇기에 일반적인 배열과는 다르게, 헤드와 테일 양쪽 끝에서 요소를 삽입 삭제하는 과정은 O(1)정도의 시간복잡도를 갖습니다.

(왜인지는 LinkedList의 내부구조를 알 수 있는 글 참조 : https://xeulbn-dev.tistory.com/18 )

(물론, 자바에서의 LinkedList이나 구조는 유사하게 생각하면 됩니다.)

 

그렇기에 몇 개의 요소가 들어있든 상관없이 동일한 속도로 처리가 가능합니다.

---

왜 동일한 속도로 처리가 가능할까?

 

맨 앞이나 맨 뒤에 추가하거나 삭제할때는 포인터만 변경하게 되는 LinkedList의 특징 때문이 가장 큽니다.

LinkedList는 각 노드들이 포인터로 연결되어있고, 맨 앞, 맨 뒤에 추가하거나 삭제하게 되면, 포인터의 위치만 바꿔주기에

데이터의 개수와 무관하게 작업의 속도가 O(1)안에 끝날 수 있는 부분인 것입니다.

---

2. 내부 인코딩

내부 인코딩은 Redis 7.0 버전 이전과 이후로 나눌 수 있을 것 같습니다.

7.0버전 이전에는 2가지의 인코딩 방식이 존재했습니다.

1. 요소가 작은 경우 → ziplist
2. 요소가 많거나 크기 자체가 클 때 → LinkedList

허나 7.0 이후에는 quicklist라는 하이브리드된 구조를 사용합니다.

Redis quicklist 구조

 

전체적인 list를 여러 개의 작은 블록으로 나누고 각 블록을 ziplist로 압축해서 저장합니다.

그리고 그 블록간 연결을 Linkedlist로 연결하는 것입니다.

→ 이로 인해 블록사이 빠른 삭제삽입을 사용할 수 있습니다.

 

이렇게 둘을 혼용하게 되면서, 전체적인 메모리 효율성과 성능을 동시에 잡게 된 것입니다.

---

몇 개까지 저장될까?

 

Redis의 list는 최대 2^{32}​ -1 정도의 요소가 저장 가능합니다.

약 42억개의 요소를 저장할 수 있는 것입니다.

 

하지만, 현실적으로 생각해야합니다.

 

Redis는 메모리 위에 저장합니다. 결국 가용 메모리가 제한 요소가 될 것입니다.

각 요소 하나를 100 byte라고 할 때, 1,000,000개면 약 100MB가 됩니다.

결국 메모리적 요소를 고려해야하는 것입니다.

---

3. 기본 특징 및 기본 명령어

리스트는 중복을 허용합니다. 즉, 동일한 요소를 저장할 수 있는 것입니다.

그렇다는 것은 인덱스에 따른 접근도 가능한 것입니다.

list에 대한 기본적인 명령어를 살펴보겠습니다.

 

1) LPUSH (왼쪽 삽입) / RPUSH (오른쪽 삽입)

//LPUSH 명령어
LPUSH key value
LPUSH key v1 v2 v3

//RPUSH 명령어
RPUSH key value
RPUSH key v1 v2 v3

 

LPUSH와 RPUSH 모두 1개 이상의 요소를 저장할 때 사용합니다.

LPUSH는 Head에(Left에) 1개 이상의 요소를 저장할 때, RPUSH는 Tail에(Right에) 1개 이상의 요소를 저장할 때 사용됩니다.

 

동작을 살펴보겠습니다.

LPUSH mylist A B C

→ C B A

 

Head에 삽입하기에, 왼쪽부터 삽입이 되어가는 것을 확인할 수 있습니다.

 

RPUSH key v1 v2 v3

→ v1 v2 v3

 

Tail에 삽입하기에 오른쪽부터 삽입 되어가는 것을 확인할 수 있습니다.

 

⇒ Head와 Tail에 한개씩 추가하는 애들이기 때문에 시간복잡도는 O(1)입니다.

List자체에 몇개의 요소가 있든 상관없이 시간복잡도 O(1)이 됩니다.

다만, 여러개 요소 추가되면 시간복잡도는 O(N)이 됩니다.

 

(중요) LPUSH , RPUSH 명령어의 반환값은 이후 List의 전체 길이입니다.

---

기존에 있는 값이라면 들어가는데,
값이 없으면 어떻게 될까요?

 

Key가 존재하지 않는다면 빈리스트를 생성하고 원하는 요소를 추가합니다.

따로 내가 굳이 생성할 필요는 없습니다.

키가 존재하는데 list 타입이 아니고, String이나 Set타입이라면 어떻게 될까요? → 에러가 반환됩니다.

---

2) LPOP (왼쪽 제거) / RPOP (오른쪽 제거)

 

LPOP key는 값을 빼는(왼쪽에서 = Head에서) 명령어입니다.

RPOP key는 값을 빼는(오른쪽에서 = Tail에서) 명령어입니다. 

 

Redis 6.2버전 이후부터는 count값 주기가 가능해졌습니다.

LPOP key count => count만큼 여러개 요소 제거 

RPOP key count => count만큼 여러개 요소 제거

 

그렇다면, List에 2개만있는데 count가 5면 어떻게 될까요?

 

나머지 요소를 반환하고, list는 빈 상태가 됩니다.

성능 자체도 빼는 행위 그냥 빼면 되니 O(1)의 시간복잡도로 갖게 됩니다.

Redis는 메모리를 효율적으로 관리하기 위해 빈 리스트는 자동으로 삭제합니다.

리스트가 비면 키 자체가 삭제가 되고 이는 EXIST 명령어에서는 문제가 될 수 있습니다.

---

3) LRANGE (조회)

LRANGE key start stop

 

 

⇒ List에서 지정한 범위(start<= 범위 <= stop)의 요소들 조회

 

 

여기서 주의해야할 점은 범위에 start와 stop 즉, 인덱스 요소까지 포함이 된다는 것입니다.

인덱스는 0부터 시작되며, 음수도 지원 가능합니다.

아래와 같은 코드가 있다고 생각해보겠습니다.

LRANGE mylist 0 -1

 

위 코드는 전체 리스트 조회 시 사용하는 코드입니다.

여기서 0의 의미는, 시작 인덱스이고, -1은 끝까지를 의미합니다.

여기서 눈치채시는 분들도 있겠지만, -1은 음수 인덱스로 뒤에서부터 세는 인덱스를 의미합니다.

음수 인덱스 = 마지막 요소 부터 거꾸로 돌아가는(?) 인덱스인 것입니다.

 

그렇다면, 만약 start와 stop이 리스트의 실제 크기를 벗어나게 되면 어떻게 될까요?

 

실제 크기를 벗어나게 된다고 하더라도 에러를 반환하지 않으며 자동으로 범위를 조절합니다.

이는 내부 동작원리를 생각해보면 편합니다.

⇒ Redis의 List는 LinkedList로 구성되어 있습니다.

 

즉, 탐색할 때, O(s+n)의 시간복잡도를 갖고 있습니다.

여기서 

• s = start 인덱스 까지의 이동비용
• n= 반환할 요소의 개수

입니다.

 

애초에 탐색을 할 때, 포인터로 직접 돌기 때문에 이런 결과가 가능한 것입니다.

그리고 이러한 LinkedList의 특성으로 인해 Head나 Tail에 가까운 요소 반환은 매우 빠릅니다.

반면, 중간요소를 반환하게 된다면 성능적인 이슈가 발생할 수 있습니다.

 

따라서, LRANGE는 전체 리스트 조회, 혹은 양끝 작은 범위 조회시 사용하는 것이 적합한 선택인 것입니다.

만약, 너무나도 크기가 큰 리스트의 중간범위를 조회하게 될 것 같다고 하면, 다른 자료구조형을 고려하는 것이 좋아보입니다.

---

4) List 정보 조회 (LLEN / LINDEX)

 

List의 정보를 조회하는 명령어 중 LLEN 과 LINDEX를 알아보도록 하겠습니다.

LLEN key

 

LLEN은 리스트 길이(포함된 요소 길이 반환)를 조회하는 명령어입니다. 

시간복잡도가 어떻게 될까요?

LinkedList로 전체 탐색하니 O(s+n)일까요? O(N)일까요? O(1)일까요?

⇒ LLEN 자체는 시간복잡도 O(1)입니다.

Redis QuickList구조

 

각 리스트의 길이를 별도의 메타데이터로 저장하고 있기 때문입니다.

(앞에서 LPUSH, RPUSH를 하게될 경우 List의 전체 길이를 반환한다는 것을 기억하고 계신다면 쉽게 이해하실 수 있을 것 같습니다.)

 

LINDEX는 특정 인덱스에 있는 요소의 값을 반환합니다.

LINDEX key index

 

index가 음수일 경우 음수 인덱스가 적용되어 뒤에서부터 세게 됩니다.

인덱스 범위 벗어나면 nil값을 반환합니다.

 

인덱스가 0이나 -1처럼 끝요소는 빠르지만, 중간위치는 느릴 수 있습니다.

그렇기에 Redis에서 List는 웬만하면 양 끝값 써먹을 때 활용하면 좋다.

---

4. 그렇다면 이 Redis List는 어떤 상황에서 쓸까요?

List는 특정 구현체를 기준으로 활용하게 됩니다.

즉, Redis의 List를 사용하지만, List로 queue나 stack을 구현해서 사용하는 것입니다.

1. Queue
   ⇒ FIFO구조입니다.
   Redis의 List로 Queue를 구현하는 경우가 있습니다. (장점 : 시간복잡도 무조건 O(1)만 걸립니다!)
   Queue를 구현하는 방법은 아래와 같이 2가지 방법이 있습니다.
   
   1) RPUSH + LPOP ⇒ FIFO
       ⇒ 주로 Producer / Consumer 용도로 사용합니다. 
       (물론, Redis에서 제공하는 Producer / Consumer가 있기는 하지만, 커스텀하여 사용하기 위해 많이 사용합니다.)
   2) LPUSH + RPOP ⇒ FIFO
   
   
2. Stack
   ⇒ LIFO 구조입니다.
   Redis의 List로 Stack을 구현하는 경우 아래의 2가지 방법이 있습니다.
   
   1) LPUSH + LPOP ⇒ LIFO
       ⇒ 최근 이력 관리에서 주로 사용됩니다.
   2) RPUSH + RPOP ⇒ LIFO

이런 구조를 통해 서비스간의 결합도를 줄이고, 이벤트처럼 동작하도록 만들 수 있기 때문에 다양한 분산환경에서 Queue나 Stack을 Redis로 구현하고 쓸 수 있는 것입니다.

 

커스텀하게 순서를 잡고 사용할 수 있기에 활용도가 높다고 생각하시면 될 것 같습니다.

 

그리고 이렇게 사용하게 될 때, Blocking 환경을 생각해야 합니다.

이와 어울리는 명령어로 BLPOP / BRPOP 가 있습니다.

---

(중요) BLPOP/ BRPOP (Blocking Queue)

 

List가 비어있을 때, 즉시 Nil을 반환하는 것이 아니라 대신 요소가 추가될 때까지 대기하는 것입니다.

BLPOP key timeout
BRPOP key timeout

ex. BLPOP queue 0 (0이면 무한 대기)
    BLPOP queue 5 (5s 대기)

 

위와 같이 명령어를 작성하게 됩니다. Timeout 설정까지 커스텀 가능합니다.

0이면 무한대기를 하며, 5로 설정하게 되면 5초를 대기하게 됩니다.

 

이것으로 Producer, Consumer 패턴 구현 시 활용 가능합니다.

Consumer가 작업이 없을 때 CPU를 낭비하지 않고 효율적으로 대기합니다.

이는 이벤트처럼 동작하기에 Polling 방식보다 더 효율적인 방식입니다. 

 

그리고 당연하게도 여러 개를 동시에 모니터링하는 것 또한 가능합니다.

아래 명령어로 예시를 들어보겠습니다.

BLOPOP queue1 queue2 0

 

 

위와 같이 실행하면 두개의 큐 중에 하나라도 요소가 추가되면 값을 즉시 반환하게 됩니다.
여러 큐 중에는 가장 왼쪽에 있는게 우선순위가 높을 것이고 말입니다. 우선순위 큐를 이런형태라고 가정하시면 될 것 같습니다.

---

👀 마무리하며...

역시 새로운 기술을 받아들이고 공부해보는 것은 언제나 재밌는 것 같습니답!..

내부 구조를 공부해보면서, 이 소스에서는 어떻게 효율적으로 돌아가도록 만들었는지, 어떻게 동시성을 관리했는지 등을

보게 되는 이 공부가 정말 즐거운 것 같습니다.

그리고...신기술 접하는 것은 언제나 재밌네요 정말...

 

(추가)

Redis 깃허브를 찾아보다가 아래와 같은 이슈를 발견했습니다.

https://github.com/redis/redis/issues/8702

[NEW] listpack migration - replace all usage of ziplist with listpack · Issue #8702 · redis/redis

 

현재는 Redis에서 ziplist사용을 모두 listpack으로 대체한 것으로 보입니다!!