• Chen Tianjie's avatar
    Replace slots_to_channels radix tree with slot specific dictionaries for shard channels. (#12804) · 85279595
    Chen Tianjie authored
    
    
    We have achieved replacing `slots_to_keys` radix tree with key->slot
    linked list (#9356), and then replacing the list with slot specific
    dictionaries for keys (#11695).
    
    Shard channels behave just like keys in many ways, and we also need a
    slots->channels mapping. Currently this is still done by using a radix
    tree. So we should split `server.pubsubshard_channels` into 16384 dicts
    and drop the radix tree, just like what we did to DBs.
    
    Some benefits (basically the benefits of what we've done to DBs):
    1. Optimize counting channels in a slot. This is currently used only in
    removing channels in a slot. But this is potentially more useful:
    sometimes we need to know how many channels there are in a specific slot
    when doing slot migration. Counting is now implemented by traversing the
    radix tree, and with this PR it will be as simple as calling `dictSize`,
    from O(n) to O(1).
    2. The radix tree in the cluster has been removed. The shard channel
    names no longer require additional storage, which can save memory.
    3. Potentially useful in slot migration, as shard channels are logically
    split by slots, thus making it easier to migrate, remove or add as a
    whole.
    4. Avoid rehashing a big dict when there is a large number of channels.
    
    Drawbacks:
    1. Takes more memory than using radix tree when there are relatively few
    shard channels.
    
    What this PR does:
    1. in cluster mode, split `server.pubsubshard_channels` into 16384
    dicts, in standalone mode, still use only one dict.
    2. drop the `slots_to_channels` radix tree.
    3. to save memory (to solve the drawback above), all 16384 dicts are
    created lazily, which means only when a channel is about to be inserted
    to the dict will the dict be initialized, and when all channels are
    deleted, the dict would delete itself.
    5. use `server.shard_channel_count` to keep track of the number of all
    shard channels.
    
    ---------
    Co-authored-by: default avatarViktor Söderqvist <viktor.soderqvist@est.tech>
    85279595
acl.c 126 KB