QuickList

2015년 1월 초에 unstable에 merge된 QuickList에 알아본다.

https://matt.sh/redis-quicklist 에서 나온 얘기를 조금 하고 코드를 보자

Redis에 List 자료구조는 일반적인 Linked list와 메모리를 절약을 위한 Ziplist두개가 있다.

포인터를 이용하여 리스트 구현한것과 배열을 이용하여 리스트를 구현한것이라고 생각하면 쉽다.

list-max-ziplist-entries 512
list-max-ziplist-value 64

(노드 갯수가 512개 이상 || 저장하려는 값의 길이가 64 byte 초과)면 Linked list로 저장이 되고

(노드 갯수가 512개 미만 && 저장하려는 값의 길이가 64 byte 이하)면 ziplist로 저장이 된다.

재미진건 ziplist -> Linked list변환은 되는데 Linked list -> ziplist 변환은 안된다.
(하긴 511개 노드였을때 넣다뺐다 하면 변환하다가 끝나겠네...그리고 추가전에만 타입 변환 검사 한다.삭제할때는
검사 안함)

http://dol9.tistory.com/187

Linked list의 장점은 추가/삭제가 쉽다는 점이고, 단점으로는 작은 값(예:4 byte)을 추가하는데 실제 값보다
더 많은 메타데이타?(예: prev, next 포인터, 8 byte)를 사용한다.

Ziplist의 장점은 내부적으로 포인터를 안써서 메모리 절약이 된다는 점이고, 단점으로는 리스트 중간에 노드를
추가/삭제를 하게되면 메모리 재할당, 복사/이동이 일어난다.

2014년 2월 3일에 봤을때 Redis에 리스트 자료구조는 QuickList만 사용한다.

https://github.com/antirez/redis/pull/2143 QuickList에 대해 정말 활발한 리뷰 오고가는걸 볼 수있다.
(재밌겠다~~~~~!!!!)

각 노드를 ziplist로 구성하고 적정 크기로 유지하면서 각각의 노드는 포인터로 연결하는 자료구조 그게 QuickList이다.

[ziplist 0] <-> [ziplist 1] <-> ... <-> [ziplist N]

데이타를 ziplist에 추가하다 조건이 충족되면 노드를 하나 더 생성해서 새로운 노드에 데이타를 저장하거나 노드를
split한후 데이타를 저장하고 Merge하는 작업을 한다.

재미진건 ziplist에서 더 아끼기위해 압축을 한다.

QuickList에 대해 대략 알아봤으니 궁금한 부분을 나열하고 그에 대해 알아보자

. 데이타 traverse

. 데이타 추가할때 동작

. Compression의 동작과 발생 조건

. Decompression의 동작과 발생 조건

. 노드 Merge 동작과 발생 조건

. 노드 Split 동작과 발생 조건

로 나눠서 하면 좀 간단하지 않을까 했지만 결국엔 주저리 떠드는걸로 됐음

. 데이타 traverse

pop이나 push명령이 아닌 중간에 있는 노드에 작업을 해야할때가 있다.

기존 ziplist, Linked list는 하나하나씩 노드 곱씹어가며 index 도달할때까지 이동하는데

QuickList는 quicklistNode->count에 ziplist의 데이타 갯수가 저장되있어서 마치 skiplist처럼 탐색을 한다.

. 데이타 추가할때 동작을 보기전에 관련 설정값을 알아보도록 하자

list-max-ziplist-size는 한 노드의 ziplist 최대 크기또는 최대 갯수를 정한다. -5~-1은 최대 크기(byte),
양수는 최대 갯수를 의미한다. 1로 해놓으면 성능 더 안 좋은 Linked list라고 보면 된다.

list-compress-depth는 head, tail부터 안쪽으로 이동하면서 압축 하지 않을 노드의 깊이를 정한것이다. 
compress에서 다시 보자.

# For a fixed maximum size, use -5 through -1, meaning:

# -5: max size: 64 Kb  <-- not recommended for normal workloads

# -4: max size: 32 Kb  <-- not recommended

# -3: max size: 16 Kb  <-- probably not recommended

# -2: max size: 8 Kb   <-- good

# -1: max size: 4 Kb   <-- good

list-max-ziplist-size -2

# Lists may also be compressed.

# Compress depth is the number of quicklist ziplist nodes from *each* side of

# the list to *exclude* from compression.  The head and tail of the list

# are always uncompressed for fast push/pop operations.  Settings are:

# 0: disable all list compression

# 1: depth 1 means "don't start compressing until after 1 node into the list,

#    going from either the head or tail"

#    So: [head]->node->node->...->node->[tail]

#    [head], [tail] will always be uncompressed; inner nodes will compress.

# 2: [head]->[next]->node->node->...->node->[prev]->[tail]

#    2 here means: don't compress head or head->next or tail->prev or tail,

#    but compress all nodes between them.

# 3: [head]->[next]->[next]->node->node->...->node->[prev]->[prev]->[tail]

# etc.

list-compress-depth 0

데이타 추가전에, _quicklistNodeAllowInsert 함수로 해당 노드가 가득찬 상태인지 아닌지 판단한다. 

그리고 추가되는 위치가 ziplist의 처음이면서 정방향인지, ziplist의 마지막이면서 역방향인지도 판단한다. 

총 6개로 구분해서 추가 로직을 구현했는데 간단하게 알아보자

대부분의 분기문에서 해당 노드를 decompress하고 데이타 추가 작업후 compress를 한다. 

얼마나 안타까운 현실인가 LINSERT 명령어는 자제 해야겠다.
비즈니스상 꼭 필요한 거라면 list-compress-depth를 0으로 사용해서 압축을 안하던가...

. 노드 Merge 동작과 발생 조건

. 노드 Split 동작과 발생 조건

발생조건은 데이타 추가에서 알아본 6개의 분기문중 마지막 분기문에서 split과 Merge가 발생한다.

노드 Merge할지 말지 결정할때 사이즈를 구하는데 11을 빼는이유는 ziplist Header사이즈 제거
(두 노드중 한 노드는 header 필요없음)

[A]<->[B]<->[C]<->[D]<->[E]

Merge 는 기준이 되는 노드를 인자로 받아 A/B Merge , D/E Merge , B/C Merge , C/D Merge 가 발생한다.(쉽게 설명한 감이 있음, 사실 앞에서 Merge 가 발생되면 달라짐)

Split 은 동작이 단순 무식하다. split할 노드와 동일한 노드를 새로 만들어서, 

한 노드는 (offset+1)~끝까지 지우고 다른 하나는 0~offset까지 지운다.

. Compression의 동작과 발생 조건

ㄴ 노드 생성하고 기존 노드에 포인터 연결후 기존 노드 compress

ㄴ LSET 명령으로 값 수정 후 해당 노드 compress

ㄴ 노드 merge 할때 count가 큰 노드 compress (ziplist 합치는 작업시 작은 ziplist가 큰 ziplist에 merge된다.)

ㄴ iter 사용후 release할때 iter에서 가리키고 있는 노드 compress

ㄴ A <-> B 노드가 있고 iter가 A의 ziplist 마지막으로 가리키고 있을때 Next 실행 시 A 노드 compress
(iter가 B의 ziplist 처음을 가리키고 있고 Prev 실행시 B 노드 compress)

compress는 두가지 방법으로 한다. 하나는 인자로 들어온 노드만 compress하는 방법이 있고,

다른 하나는 list-compress-depth 변수를 이용하는 방법이 있는데 다음과 같다.

list-compress-depth=2, 인자로 들어온 노드=[E] 

[A]<->[B]<->[C]<->[D]<->[E]<->[F]<->[G]

바깥쪽에서 안쪽으로 list-compress-depth만큼은 compress 안하겠다는 말인데,[A], [B], [F], [G] 노드를 decompress하고 [E]를 compress한다
아...이건 설명하기 참 거시기 하다. compress 방식을 두개로 나눈 이유는 decompress 에서 알아본다.

. decompress의 동작과 발생 조건

ㄴ 노드 compress 작업할때 decompress

ㄴ 두 노드 Merge 할때 두 노드 decompress

ㄹ 데이타 삽입시 노드 decompress

ㄹ 데이타 삭제시 노드 decompress

ㄹ로 되어있는 발생조건이 ㄴ과 다른건 recompress값을 1로 대입하는것 말고는 없다.
차이는 해당 노드만 compress할것이냐, 아니면 compress 두번째 설명한 방식대로 할것이냐 차이다.
ㄹ조건을 보면 데이타 추가/수정/삭제인 경우이다. matt의 섬세함이 느껴졌다.
한번 decompress/compress 한 노드이니까 굳이 할 필요가 없는거지...

따라가기도 버거운걸 코드로 표현한 matt...참 대단하다 난 QuickList 자료구조만 알아본건데
aof, rdb등 전체적인 구조 다 수정 했을텐데...무서운사람....덜덜

antirez가 활발하게 커뮤니케이션 하는거 처음봤다. 부러움이 넘쳤다, 재밌겠다 ㅜ,ㅜ.
영어로 내 의견 쓸 정도는 되야하는데...

기승전 자기반성 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ