List

Redis에서 사용하는 기본 List구조는 우리가 아는 Doubly Linked List입니다. (adlist.c)

그런데 List의 구조체가 아래와 같이 생겨먹었습니다.

value 3을 저장하게되면 기본으로 value의 크기 + sizeof(list) 만큼의 메모리가 사용되게 됩니다.
이를 아깝게 생각한 두 Redis 커미터는 메모리를 아끼는방법이 없을까.....생각합니다.
그게 ziplist와 zipmap입니다. 여기서는 ziplist에 대해서만 알아보겠습니다.
ziplist에 대한 발표자료 4~11 쪽입니다.

ziplist의 구조는 다음과 같습니다.
<zlbytes><zltail><zllen><entry><entry><zlend>

zlbyte는 ziplist의 전체 크기로 byte단위이며, 자료형은 unsigned integer입니다.
zltail은 tail Entry가 시작 offset을 가집니다. 이것도 unsigned integer
zllength는 16 byte이고, ziplist entry의 갯수입니다.  zlend는 1 byte이고, 255인 경우 ziplist의 끝을 뜻합니다.

여기서 모든 숫자는 little-endian order 을 사용합니다.
little-endian의 장점은 낮은주소에 하위 byte를 저장하기 때문에 byte씩 읽어들이면서 필드 구분을 바로 바로 할수있습니다.  (반면에 big-endian은 첫 byte로 음수인지 아닌지 판단이 가능하겠죠.)
<little-endian   and big-endian>   , 바이트 순서



entry에는 실제 데이타와 두개의 header로 구성되어 있습니다.
첫번째 header는 이전 entry의 크기 
두번째 header는 현재 entry의 크기를 나타냅니다.

첫번째 header의 규칙은 다음과 같습니다.
이전 entry의 크기가 (두개의 header 크기 + value의 크기)가 254보다 작으면 1 byte만 사용
254보다 크거나 같으면 1byte에는 254를 기록하고, 뒤에 4 bytes에 이전 entry크기를 저장합니다

두번째 header는 1 byte 읽어서, 

1 byte가 00xxxxxx 이면, value type은 String이고 63보다 같거나 작은 경우
2 bytes가 01xxxxxx xxxxxxxx 이면, value는 String이고 16383보다 같거나 작은 경우

5 bytes가 10______ xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx이면, value는 String이고 16384보다 큰 경우

1 byte가 11000000 이면, value는 int16_t    value 2bytes

1 byte가 11010000 이면, value는 int32_t    value 4bytes

1 byte가 11100000 이면, value는 int64_t    value 8bytes

1 byte가 11110000 이면, value는 int24_t    value 3bytes

1 byte가 11111110 이면, value는 8bit signed integer  value 1 byte

1 byte가 1111xxxx 이면, value는 4bit integer(0000~1111사용가능하지만,    
11110000은 int24_t에서 사용, 11111111은 ziplist end를 나타낼때 사용하므로 0001~1101를 사용가능,

실제 숫자는 0~12를 표현하므로 ziplist에 저장된 value에 -1을 한값이 실제 값이 된다.

1 byte가 11111111  이면 ziplist의 끝

(next도 있는데 그려보니 지저분해서....귀찮아서 화살표 저런거 아니에요 ㅋㅋㅋ)

prev, next pointer를 value의 길이, datatype에 따라 최대한 메모리를 아껴 list와 동일한 기능을 하도록 구현됩니다.
첫번째 header를 통해 이전 entry의 시작점을 알수있고, 두번째 header를 통해 다음 entry의 시작점을 알수있습니다.
물론 pointer는 그냥 쓰면 되지만 위에처럼 하게되면 encoding, decoding하는 과정이 필요합니다.

__ziplistInsert, __ziplistCascadeUpdate 에 대해 설명하려고 합니다. 

먼저 __ziplistInsert에 대해 알아보겠습니다.

===================================================================================================

삽입되는 위치가 tail이 아닌경우의 사진에서 2번을 보면 reqlen + nextdiff만큼 메모리를 재할당 했습니다.
이유는 그 차이만큼의 header 크기가 필요하기때문이다.
1번사진의 두번째 entry의 크기가 nextdiff 만큼 커졌다고 보면 됩니다.

__ziplistCascadeUpdate를 살펴보겠습니다.

tail에 있는 entry를 삭제하거나 추가하면 아무 문제 없지만,
header나 중간위치에 insert/delete 연산이 들어가게되면 위에서 본것처럼 header의 크기가 달라집니다.

header의 크기가 달라지면 결국엔 그 entry의 크기가 달라진것이고,
그렇다는건 결국 다음 entry의 prev header가 변경되어야 한다는 말이 됩니다.
그 작업을 __ziplistCascadeUpdate 수행합니다.
insert/delete된 위치에서부터 entry하나씩 하나씩 살펴보면서 header를 수정합니다.

아래는 언제까지 header update를 수행하는지 주석으로 적어보았습니다.

https://github.com/antirez/redis/issues/627    에서 nextdiff에 대한 issue가 나왔습니다. 

(우왁~!! 나는 백날 봐도 이해하기 바쁜데.....ㅠ,.ㅠ)

first 는 지우려는 entry의 첫 entry, p는 마지막으로 지워지는 entry에 다음 entry

testcase 만드는거 배울만 하네요. ; ), 영어도......;;

마지막으로 두개의 list를 관리해주는게 t_list.c입니다.

이놈이 list관련 명령어가 올때 ziplist로 할지 doubly linked list로 할지 정해줍니다.

그 역할을 하는 함수가 listTypeTryConversion입니다. redis.conf의 두개의 설정값에 따라서 그 이하인 경우엔 ziplist, 아니면 doubly linked list를 사용합니다.
512개 entry, value최대길이 64, 더 크게하지 왜 저렇게 했을까요?
pdf 발표자료에 벤치마크결과가 있는데 간단히 말하면
아까도 언급한것처럼 encoding/decoding과정이 있기때문에 entry가 많아지면 성능이 저하가 나온다고 하네요.
조금씩 늘려봐서 자신의 서비스에 맞게 조정하는것도 좋을것 같습니다.

redis.conf에 입니다.

# Similarly to hashes, small lists are also encoded in a special way in order
# to save a lot of space. The special representation is only used when
# you are under the following limits:
list-max-ziplist-entries 512
list-max-ziplist-value 64

마지막으로 listTypePush 함수를 보면 ziplist의 경우 decrRefCount, linked list의 경우는 incrRefCount 입니다.
이유는 간단합니다. redis의 모든 값들은 object로 다루게되는데,
ziplist의 경우는 object가 아니라, ziplist에 직접 value를 기록하기때문에 decrRefCount가 하게되고,
linked list의 경우는 listNode *node; node->value = value라 object로 관리가 되서, refcount++을 하게 됩니다.

이상 List를 마치고, Set을 알아보아요~

ps. linked list, ziplist 테스트