ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • QuickList
    개발하면서/코드보면서 2015.02.04 22:53

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

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

    TAG

    댓글 0

Designed by Tistory.