Redis Hash 结构

最近在学一门新的技艺: GraphViz,总算是找到一个工具来弥补画图这个空缺了. 正好之前看了<Redis设计与实现>,对其中讲的hash结构很是赞服. 大体结构见下图:

image.png

digraph HashTable {
    node [shape=record]
    
    rankdir=LR
    tables [label="<ts>tables |<ri> rehashIndex"]
    TS [label="<t1> t1|<t2> t2"]

    T1 [label="<f0> 0| <f1> 1| <f2> 2| ... | <fn> n", height=2.5]
    N [label="{<i> index | value | next}"]
    N1 [label="{<i> index | value | next}"]
    N2 [label="{<i> index | value | next}"]
    N3 [label="{<i> index | value | next}"]
    N4[label="{<i> index | value | next}"]
    N5 [label="{<i> index | value | next}"]

    N -> N1:i
    N1 -> N2:i
    
    N3 -> N4:i

    tables:ts -> TS:t1
    TS:t1 -> T1:f0
    T1:f0 -> N:i
    T1:f1 -> N3:i
    T1:f2 -> N5:1
}

渐进式rehash

redis的hash设计的精妙处就是这个渐进式rehash过程(PS:至少我没有在其他地方看到有别的优化)

所谓的渐进式rehash是指, 再hash table进行扩容的时候不用一次性把所有的对象都挪移到新的table上, 是先进行一部分的rehash, 再进行剩余的部分...如此

其中的关键便是rehashIndex, 该值代表rehashIndex 的进度, 没有rehash时该值为 -1

rehash过程:

1. 用户执行put()操作, 是否应该rehash, 如果是, 进入过程2(如果用户执行get()操作, 检查rehashIndex是否为-1, 如果不为-1同样进入过程2)

2. 更新rehashIndex值为K(K in [0, table[0].length)), 如果table[1]为空, 则初始化

3. 对[previous_K, K)部分的数据进行rehash

4. 检查rehashIndex值是否大于等于tabole[0].length, 如果是更新rehashIndex为 -1, table[1]赋值给table[0], table[1]设置为空, 一次完整的rehash过程完毕

get()工作逻辑(put()同理)

1. 用户调用get(key)

2. 计算key的hash为 key_hash

3. 此时如果 key_hash % table[0].length < rehashIndex, 则从table[1]中获取, 否则从table[0]中获取

大概逻辑如下:

def get(key):
    hk = hash(key)
    h = hk % len(table[0])
    if h < rehashIndex:
        return get_in_table(table[1], key)
    return get_in_table(table[0], key)

渐进式rehash的利弊

• 这种方式有利于大数据量的hash table进行rehash, 不必一次rehash全部的数据

• 可以get()操作可以介入rehash的过程, 减轻put()的压力

• 代码会相对复杂一些,不过还能理解, 空间占用会有波动, 尤其是在rehash的过程中,需要维护两个table

• 并发环境下做同步是一个挑战(虽然本来同步就很难), 但是对redis来说不存在的