[Redis] 레디스 기본타입(Lists)

redis 공식문서를 보고 정리한 글입니다.

 

redis lists는 문자열 값의 linked lists 이며, 주로 아래의 경우 사용됩니다.

- stack, queue 구현

- background worker의 큐 관리

 

리스트라는 개념은 종종 부적절하게 사용되는데, 예를 들어 파이썬의 리스트는 연결 리스트가 아닌 배열이며, Ruby에서는 동일한 데이터 유형이 배열(Array)로 불립니다. 매우 일반적인 관점에서 리스트는 순서가 있는 요소의 sequence 일 뿐입니다. 그러나 배열을 사용하여 구현된 리스트의 특정은 linked list로 구현된 리스트의 특성과 매우 다릅니다.

 

redis lists는  linked list로 구현됩니다. 이는 리스트 안에 수백만 개의 요소가 있더라도, 맨앞/뒤에 새로운 요소를 추가하는 작업이 상수 시간에 수행된다는 것을 의미합니다. 반면에 배열을 사용하여 구현된 리스트에서는 데이터에 대해 인덱스로 접근하기 때문에 매우 빠르지만, linked list로 구현된 리스트에서는 그렇게 빠르지 않습니다.

 

list에 들어갈 수 있는 데이터의 개수는 2^32-1(4,294,967,295)개 입니다.

 

list의 처음/끝에 접근하는 명령어는 시간복잡도가 O(1)이지만, LINDEX, LINSERT, LSET같은 리스트 내부 데이터를 조작하는 명령어는 O(n)시간복잡도를 가집니다.

 

Common use cases for lists

- 소셜 네트워크에서 사용자가 업데이트 한 가장 최신 게시글

- producer - consumer 패턴

 

예를 들어, 사용자들이 게시한 최신 사진을 보여주는 홈페이지가 있고, 이 사진을 빨리 보여주고 싶다고 한다면 가정한다면 아래의 과정을 생각해볼 수 있습니다.

- 유저가 새로운 사진을 올리면, LPUSH 명령어로 redis에 사진의 ID를 삽입한다.

- 사용자들이 홈페이지를 방문하면, LRANCE 0 9 명령어를 사용하여 최신 10개의 사진을 보여준다.

 

Capped lists

많은 사례에서 소셜 네트워크에서 수정된 정보, log, 등등 최신 데이터를 저장하기 위해 사용합니다. redis는 리스트를 capped collection으로 사용할 수 있는 기능을 제공하며, LTRIM 명령어로 몇개의 최신 데이터만 저장하고 오래된 데이터는 삭제하는 기능을 사용할 수 있습니다.

 

LTRIM 명령어는 LRANGE와 명령어와 비슷하지만 특정 범위의 데이터만 보여준다는 점에서 차이가 있으며, 특정 범위 이외의 데이터는 삭제 됩니다. LTRIM arr 0 2명령어를 보면, arr의 0~2번째 인덱스 값만 유지하고 나머지 데이터는 삭제됩니다.

> RPUSH arr 1 2 3 4 5
(integer) 5
> LRANGE arr 0 -1
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
> LTRIM arr 0 2
OK
> LRANGE arr 0 -1
1) "1"
2) "2"
3) "3"

 

 

Blocking operations on lists

list는 큐를 구현하고 일반적으로 프로세스 간 통신 시스템의 구성 요소로 사용하기에 적합하게 만드는 특별한 기능이 있습니다. 예를 들어 하나의 프로세스에서 list에 아이템을 넣고, 다른 프로세스에서 그 아이템을 빼서 사용한다면, 이것은 producer/consumer 구조이며 아래의 방법으로 구현할 수 있습니다.

- list에 아이템 넣기 : LPUSH

- list에서 아이템 뺴기 : RPOP

 

list에 값이 없는 경우 RPOP은 null을 반환하며, 이 경우 consumer는 일정 시간을 대기 후, 다시 RPOP을 하게 되며, 이런 방법을 polling이라고 합니다.  

 

polling 방법은 비효율적이며 대신 redis는 BRPOP, BLPOP이라는 명령어는 제공하며 리스트가 비어있는 경우 대기하다 list에 새로운 데이터가 삽입하면 삽입된 데이터를 반환하며, 사용자가 지정한 시간(0이면 무한)에 도달하면 null을 반환합니다.

---

 

LMOVE

O(1)

LMOVE source destination <LEFT | RIGHT> <LEFT | RIGHT>

source의 head/tail 가져와서 destination의 head/tail에 추가합니다. source의 head/tail 선택은 명령어 옵션의 첫번째 LEFT/RIGHT이며, destination의 head/tail은 명령어 옵션의 두번째 LEFT/RIGHT입니다. 여기서 source에서 가져온 데이터는 source에서 삭제 됩니다. 만약 source가 없으면 nill을 반환하며 명령어가 실행되지 않습니다. 

 

arr1 : [a,b,c]

arr2 : [d,e,f]

LMOVE arr1 arr2 RIGHT RIGHT 명령어는 arr의 가장 오른쪽 값(c)를 가져와서 arr2의 가장 오른쪽에 넣습니다. 이후 데이터는 아래와 같이 형성됩니다.

arr1 : [a,b]

arr2 : [d,e,f,c]

> RPUSH arr1 a b c
(integer) 3
> RPUSH arr2 d e f
(integer) 3
> LRANGE arr1 0 -1
1) "a"
2) "b"
3) "c"
> LRANGE arr1 0 -2
1) "a"
2) "b"
> LMOVE arr1 arr2 RIGHT RIGHT
"c"
> LRANGE arr1 0 -1
1) "a"
2) "b"
> LRANGE arr2 0 -1
1) "d"
2) "e"
3) "f"
4) "c"

 

 

BLMOVE

O(1)

BLMOVE source destination <LEFT | RIGHT> <LEFT | RIGHT> timeout

LMOVE의 blocking 버전 입니다. source에 데이터가 있거나, MULTI/EXEC block 내부에 이 명령어를 사용할 때는 LMOVE와 동일하게 동작합니다. 하지만 만약 source가 비어있을 땐 다른 클라이언트가 source에 데이터를 넣어 주거나, timout에 도달하기 전까지 해당 커넥션이 블락됩니다. timeout이 0이면 시간제한이 없습니다.

 

 

LMPOP

O(N+M), N : keys의 개수, N : 반환되는 데이터 개수

LMPOP numkeys key [key ...] <LEFT | RIGHT> [COUNT count]

key에 입력한 리스트에서 비어있지 않은 리스트를 찾은 후 LEFT/RIGHT에서 count 개수만큼 데이터를 반환합니다. 반환 후, 해당 리스트에서 데이터를 삭제합니다.

 

arr1 : [1,2,3]

arr2 : [4,5,6]

 

LMPOP 2 arr1 arr2 RIGHT count 2

내가 데이터를 가져올 대상 리스트는 2개(arr1, arr2)이다. 순서상 arr1에서 데이터를 먼저 가져오는데, 만약 arr1이 비어있으면 arr2에서 가져온다(pops one or more elements from the first non-empty list).

 

arr1에 데이터가 존재하며, arr1의 가장 오른쪽 에서 2개(count)의 데이터를 가져와서 반환하고, 가져온 데이터는 arr1에서 삭제함. arr1에서 데이터를 2개씩 다 가져오면, 이제 다음 arr2에서 오른쪽 2개씩 데이터를 계속 가져옴.

> RPUSH arr1 1 2 3
(integer) 3
> RPUSH arr2 4 5 6
(integer) 3
> LMPOP 2 arr1 arr2 RIGHT count 2
1) "arr1"
2) 1) "3"
   2) "2"
> LMPOP 2 arr1 arr2 RIGHT count 2
1) "arr1"
2) 1) "1"
> LMPOP 2 arr1 arr2 RIGHT count 2
1) "arr2"
2) 1) "6"
   2) "5"
> LMPOP 2 arr1 arr2 RIGHT count 2
1) "arr2"
2) 1) "4"

 

 

LPOP

O(N)

LPOP key [count]

리스트에서 왼쪽 부터 count 개수만큼 데이터를 가져옵니다. 만약 count가 없으면 한개씩 가져옵니다. 

 

 

RPOP

O(N)

RPOP key [count]

리스트에서 오른쪽 부터 count 개수만큼 데이터를 가져옵니다. 만약 count가 없으면 한개씩 가져옵니다. 

 

 

BLMPOP

O(N+M), N : keys의 개수, N : 반환되는 데이터 개수

BLMPOP timeout numkeys key [key ...] <LEFT | RIGHT> [COUNT count]

LMPOP 명령어의 blocking 버전입니다. 리스트에 데이터가 있거나, MULTI/EXEC block 안에서 명령어가 실행되면 LMPOP와 동일하게 동작합니다. 리스트가 비어 있다면, 리스트에 데이터를 삽입하거나, timout에 도달하기 전까지 blockk 됩니다. 

 

arr1 : [1,2,3]

arr 2 : []

BLMPOP 20 2 arr1 arr2 LEFT count 2

내가 선택할 대상 리스트는 2개(arr1, arr2)입니다. 이 두개 중에서 데이터가 있는 리스트를 먼저 선택 후, 리스트의 왼쪽(처음)부터 2개씩 가져온다(가져온 후 해당 리스트에서 삭제함). 계속 가져오다가, 만약 arr1에 데이터가 모두 없게 되면, arr2가 비었는지 검사하고, 만약 arr2까지 비어있다면 block됩니다. 20초까지 기다리다가 다른 클라이언트에서 arr1, arr2에 데이터를 안넣어주면 nill을 반환합니다. 하지만 20초 전에 다른 클라이언트가 arr1 또는 arr2에 데이터를 넣어주면 해당 리스트의 왼쪽에서 2개를 반환합니다.

> RPUSH arr1 1 2 3
(integer) 3
> BLMPOP 20 2 arr1 arr2 LEFT count 2
1) "arr1"
2) 1) "1"
   2) "2"
> BLMPOP 20 2 arr1 arr2 LEFT count 2
1) "arr1"
2) 1) "3"
> BLMPOP 20 2 arr1 arr2 LEFT count 2
1) "arr2"
2) 1) "4"
   2) "5"
(10.70s)
> BLMPOP 20 2 arr1 arr2 LEFT count 2
1) "arr2"
2) 1) "6"

 

 

BLPOP

O(N) : N은 입력받은 key의 개수

BLPOP key [key ...] timeout

LPOP의 block 버전입니다.. 입력한 키 순서대로 검사하다, 비어있지 않은 리스트를 발견하면 해당 리스트에서 왼쪽 첫번째 값을 반환합니다. 만약 키의 모든 리스트가 비어있다면 timout 만큼 대기하다, 그 사이에 key의 리스트에 데이터가 삽입되지 않으면 nil을 반환합니다.

 

만약 다음과 같은 경우는 어떨까요.

client A : BLPOP foo 0
client B : LPUSH foo a b c

B가 push 하자마자, 즉 a를 넣자마자 A가 바로 a를 pop할까요? 아니면 B가 a b c를 모두 넣은 후, A는 pop할까요 ?

redis 2.6버전 또는 그 이후부터는 B가 데이터를 모두 넣은 후 A가 pop해 가기 때문에 c가 조회되지만, 2.4버전에서는 B가 a 를 넣자마자 바로 A가 pop하기 때문에 a가 조회됩니다.

 

 

BRPOP

O(N) : N은 입력받은 key의 개수

BRPOP key [key ...] timeout

바로 위 BLPOP의 명령어와 같으며 오른쪽에서부터 데이터를 pop한다는 점만 다릅니다.

 

 

LINDEX

O(N) : 해당 index까지 찾아 가는데 거친 데이터 수, 리스트의 첫/끝 구성요소에 접근한다면 O(1)

LINDEX key index

index 위치에 있는 데이터를 반환합니다. -1은 가장 마지막 값을 반환하며, -2는 가장 마지막에서 2번째 값을 반환합니다. key가 없다면 에러를 반환합니다.

 

 

LINSERT

O(N) : pivot까지 찾아 가는데 거친 데이터의 수, 처음/끝에 삽입하는 경우 O(1)

LINSERT key <BEFORE | AFTER> pivot element

리스트의 pivot위치 전/후에 데이터를 삽입합니다.

 

 

LLEN

O(1)

LLEN key

리스트의 길이를 반환합니다.

 

 

LPOS

O(N) : 평균적으로 리스트의 데이터 수인 O(N)이지만, 목록의 처음/끝 근처거나 MAXLEN 옵션이 제공된 경우 상수 시간을 가집니다.

LPOS key element [RANK rank] [COUNT num-matches] [MAXLEN len]

elemet에 매칭되는 데이터의 index의 값을 반환합니다. 옵션이 주어지지 않으면 리스트의 처음-끝까지 스캔합니다.

 

RANK 2는 처음부터 끝까지 탐색하다 element를 2번째로 찾았을 때의 index 값을 반환합니다.

RANK -2는 끝부터 처음까지 탐색하다 element를 2번째로(뒤에서 기준) 찾았을 때의 index 값을 반환합니다.

> RPUSH arr 1 1 2 3 1 4 5 1 6 1
(integer) 10
> LPOS arr 1 RANK 2
(integer) 1
> LPOS arr 1 RANK -2
(integer) 7

 

COUNT 2는 1이 존재하는 index를 2개 찾아서 반환합니다.

RANK와 조합해서 사용할 수도 있는데, RANK -1 COUNT 2는 리스트의 끝부터 시작해서 1이 존재하는 index를 2개 찾아서 반환합니다.

> LPOS arr 1 COUNT 2
1) (integer) 0
2) (integer) 1


> LPOS arr 1 RANK -1 COUNT 2
1) (integer) 9
2) (integer) 7

 

 

MAXLEN은 탐색하는 리스트의 최대 길이를 제한합니다.

COUNT 2 MAX LEN7은 arr의 길이가 10이지만, 7번째 까지만 탐색하여 그 중에 1인 데이터의 인덱스를 2개까지만 반환합니다.

> LPOS arr 1 COUNT 2 MAXLEN 7
1) (integer) 0
2) (integer) 1

 

 

LPUSH

각 데이터를 삽입할 때 O(1)이므로, 데이터가 여러개 일땐 O(N)이 소요됩니다.

LPUSH key element [element ...]

리스트의 왼쪽부터 한개 또는, 여러개의 데이터를 삽입하며 키가 없는 경우 리스트를 만들어 삽입합니다. LPUSH arr a b c의 경우 c부터 리스트의 왼쪽에 삽입됩니다.

 

 

LPUSHX

각 데이터를 삽입할 때 O(1)이므로, 데이터가 여러개 일땐 O(N)이 소요됩니다.

LPUSHX key element [element ...]

key가 존재하면 LPUSH와 동일하게 동작하지만 key가 없다면 명령어가 실행되지 않습니다.

 

 

LRANGE

O(S+N) : S는 리스트의 시작부터 start까지 거리, N은 범위에 속한 데이터의 개수

LRANGE key start stop

리스트에서 start ~ stop 사이의 데이터를 반환합니다. -1은 리스트의 마지막 데이터, -2은 마지막 두번째 데이터 입니다.

 

조회되는 데이터는 start와 stop 위치를 포함하고 있으며, [1, 2, 3, 4, 5, 6, 7]에서 LRANGE arr 0 5 [1, 2, 3, 4, 5, 6]를 반환합니다. 또한 start가 리스트의 길이보자 크면 빈 배열을 반환하며, stop이 리스트의 최대값보다 크면 stop을 리스트의 최대값으로 다룹니다.

 

 

LREM

O(N+M) : N은 리스트의 길이, M은 제거하려는 데이터의 개수

LREM key count element

리스트에 존재하는 element를 count개 만큼 제거합니다.  count에 따라 시작점을 어디서부터 할 지 결정합니다.

- count > 0 : 리스트의 처음부터 끝까지 진행하면서 제거

- count < 0 : 리스트의 끝에서 처음으로 진행하면서 제거

- count = 0 : 리스트의 모든 element를 제거

 

 

LSET

0(N) : N은 리스트의 길이, 첫/끝 데이터를 수정하는 경우 O(1)

LSET key index element

리스트의 index에 위치하는 값을 element로 변경 하며 index의 값이 리스트의 크기를 벗어나면 에러를 반환합니다.

 

 

LTRIM

O(N) : N은 제거해야 할 데이터의 개수

LTRIM key start stop

리스트에서 start ~ stop 영역의 데이터만 남기고 제거합니다. start가 리스트의 길이보다 크거나, start > stop인 경우 해당 키가 삭제됩니다. stop이 리스트의 길이보다 큰 경우, 리스트의 길이로 설정됩니다.

 

LTRIM와 LPUSH/RPUSH 명령어를 같이 사용하면 리스트에 데이터를 삽입하는 경우 리스트가 100개의 데이터를 넘지 못하게 강제할 수 있습니다. 이는 레디스를 log 저장 용도로 사용하는데 좋습니다. 이 방법을 사용하는 경우 LTRIM은 평균적으로 리스트의 끝에서 데이터 하나만 제거하면 되기 때문에 O(1)의 복잡도를 가집니다. 

LPUSH mylist someelement
LTRIM mylist 0 99

 

 

RPOP

O(N) : N은 pop하려는 데이터의 개수

RPOP key [count]

리스트의 끝에서 count 만큼 데이터를 제거하여 반환합니다. count가 없으면 하나만 pop 하면 반환합니다.

 

 

RPUSH

각각의 데이터를 삽입하는데는 O(1), 여러 데이터를 삽입하는데에는 O(N)

RPUSH key element [element ...]

여러개의 값은 리스트에 삽입하며, 만약 리스트가 없다면 생성 후 명령어를 실행합니다. RPUSH arr a b c명령어를 하게되면, 리스트에 a 부터 차례대로 삽입됩니다.

 

RPUSHX

각각의 데이터를 삽입하는데는 O(1), 여러 데이터를 삽입하는데에는 O(N)

RPUSHX key element [element ...]

key가 존재하는 경우 RPUSH와 동일하지만, key가 없다면 명령어를 실행하지 않습니다.