• sundb's avatar
    Add listpack encoding for list (#11303) · 2168ccc6
    sundb authored
    Improve memory efficiency of list keys
    
    ## Description of the feature
    The new listpack encoding uses the old `list-max-listpack-size` config
    to perform the conversion, which we can think it of as a node inside a
    quicklist, but without 80 bytes overhead (internal fragmentation included)
    of quicklist and quicklistNode structs.
    For example, a list key with 5 items of 10 chars each, now takes 128 bytes
    instead of 208 it used to take.
    
    ## Conversion rules
    * Convert listpack to quicklist
      When the listpack length or size reaches the `list-max-listpack-size` limit,
      it will be converted to a quicklist.
    * Convert quicklist to listpack
      When a quicklist has only one node, and its length or size is reduced to half
      of the `list-max-listpack-size` limit, it will be converted to a listpack.
      This is done to avoid frequent conversions when we add or remove at the bounding size or length.
        
    ## Interface changes
    1. add list entry param to listTypeSetIteratorDirection
        When list encoding is listpack, `listTypeIterator->lpi` points to the next entry of current entry,
        so when changing the direction, we need to use the current node (listTypeEntry->p) to 
        update `listTypeIterator->lpi` to the next node in the reverse direction.
    
    ## Benchmark
    ### Listpack VS Quicklist with one node
    * LPUSH - roughly 0.3% improvement
    * LRANGE - roughly 13% improvement
    
    ### Both are quicklist
    * LRANGE - roughly 3% improvement
    * LRANGE without pipeline - roughly 3% improvement
    
    From the benchmark, as we can see from the results
    1. When list is quicklist encoding, LRANGE improves performance by <5%.
    2. When list is listpack encoding, LRANGE improves performance by ~13%,
       the main enhancement is brought by `addListListpackRangeReply()`.
    
    ## Memory usage
    1M lists(key:0~key:1000000) with 5 items of 10 chars ("hellohello") each.
    shows memory usage down by 35.49%, from 214MB to 138MB.
    
    ## Note
    1. Add conversion callback to support doing some work before conversion
        Since the quicklist iterator decompresses the current node when it is released, we can 
        no longer decompress the quicklist after we convert the list.
    2168ccc6
defrag.c 45.4 KB