redis 자료구조 - LISTS

LISTS

Lists는 key와 value가 일 대 다 관계입니다.
value는 입력된 순서대로 저장됩니다.
Lists는 주로 큐 와 스택으로 사용됩니다.
큐는 들어오는 데이터를 순서대로 처리할때 사용
스택은 웹브라우져의 뒤로가기처럼 되돌아 갈때 사용

키의 생성과 삭제

value가 저장되면 리스트가 생성되고 키에 value가 하나도 없으면 키는 삭제됩니다. 즉 키의 생성과 삭제를 위한 별도의 작업은 필요없습니다.

명령어 요약

SET (PUSH): LPUSH, RPUSH, LPUSHX, RPUSHX, LSET, LINSERT, RPOPLPUSH
GET: LRANGE, LINDEX, LLEN
POP: LPOP, RPOP, BLPOP, BRPOP
REM: LREM, LTRIM
BLOCK: BLPOP, BRPOP, BRPOPLPUSH
Enterprise: LREVRANGE, LPUSHS, RPUSHS (subquery)

위 명령어에 대한 docs

http://redisgate.kr/redis/command/lists.php

list 내부 데이터 구조

Linked list : 리스트의 메인 데이터 구조

흔히 아는 양방향 리크드 리스트 구조,

redis.conf에 있는 관련 파라미터

• list-max-ziplist-entries 512 : 엔트리 수가 512 이하면 짚 리스트, 512보다 많으면 링크드 리스트
• list-max-ziplist-value 64 : 값의 크기(바이트)가 64 이하면 짚 리스트, 64보다 크면 링크드 리스트
  위 두 조건은 OR 조건이다. 어느 것 하나라도 만족하면 링크드 리스트로 변경된다.
  단, 증가할 때만 해당되고, 줄어든다고 다시 짚 리스트로 바꾸지 않는다.이유는 512 엔트리에서 push와 pop이 반복되어 엔트리 수가 512와 513을 왔다 갔다 하면 데이터 타입 변경이 계속 발생한다.데이터 타입 변경은 push 나 pop 처리 시간보다 수백 배 더 걸리므로 성능에 매우 악 영향을 미친다. 따라서 한번 링크드 리스트로 바뀌면 다시는 데이터 타입 변환이 발생하지 않는다.

zip list : 메모리 절약형 자료구조

레디스는 모든 데이터를 메모리(RAM)에 저장합니다. 업무에 따라서 수십 기가 또는 수백 기가 메모리를 가진 시스템들을 사용하지만, 메모리는 디스크에 비해 여전히 비싼 자원입니다. 그리고 레디스 서버는 데이터 타입에 따라 다르기는 합니다만, 실 데이터가 아주 작은 경우 메모리 오버헤드가 8 ~ 10 배에 이르는 경우도 있습니다.

• 메모리를 절약하기 위해서 redis가 선택한방법

메모리를 절약하기위한 데이터 구조

1. 데이터는 특수문자를 포함할 수 있다.
2. 순방향 또는 역방향 탐색을 할 수 있어야한다.

zip list 데이터 구조

prevlen + itself len + value

• prevlen : 이전 엔트리의 길이, 역방향 탐색용 1, 5 byte 두종류가 있다.
  • 이전 엔트리의 길이가 zip_biglen 254 보다 적으면 1바이트를 할당해서 길이를 저장하고 그 이상이라면 5바이트를 할당해서 첫 바이트에 254를 넣고 이후 4바이트에 길이를 저장한다.
• itself len : 엔트리 자신의 값의 길이, 순방향 탐색과 값 조회용 문자는 1,2,5 byte의 세종류가 있고 수자는 1byte 한 종류가 있다.
• value : 값은 문자와 정수로 구분해서 저장한다. 실수는 문자로 구분(메모리 효율 때문), 문자는 문자 그대로저장

• itself len은 값이 문자열일 때는 1,2,5 바이트로 구분해서 길이를 저장하고, 숫자(정수) 일 때는 1 바이트만 사용한다.
• prevlen은 이전 엔트리의 길이를 저장하는 것이므로 문자, 숫자 구분 없이 1,5 바이트 두 종류를 사용한다.
• 값(value)은 문자열일 때는 그대로 저장하고, 숫자(정수) 일 때는 4,8,16,24,32,64 비트로 구분해서 저장한다.
• 값(value)이 실수일 때는 문자열로 취급한다.
• 레디스에서는 이렇게 데이터의 형태, 길이에 맞게 최대한 메모리를 절약할 수 있는 구조로 짚 리스트를 설계해서 사용하고 있다.

prevlen은 왜 두종류 일까?

itself len처럼 세종류를 사용하면 메모리를 더 절약할수 있을텐데 두종류일까?
엔트리를 삽입할때 삽입되는 엔트리의 길이를 다음 엔트리의 prevlen필드에 update할 필요가 있다. 이 과정에서 비효율적인 prevlen의 사이즈를 규칙에 따라 늘리고 줄이고 하는데 이 과정이 생기지않도록 한번 늘린것은 줄이지 않는 규칙이 있다고 한다.