Redis 存储结构分析,及哈希相关

Redis 是支持多 key-value 数据库 ( 表 ) 的 , 并用 RedisDb 来表示一个 key-value 数据库 ( 表 ). redisServer 中有一个 redisDb *db; 成员变量 , RedisServer 在初始化时 , 会根据配置文件的 db 数量来创建一个 redisDb 数组 . 客户端在连接后 , 通过 SELECT 指令来选择一个 reidsDb, 如果不指定 , 则缺省是 redisDb 数组的第 1 个 ( 即下标是 0)redisDb. 一个客户端在选择 redisDb 后 , 其后续操作都是在此 redisDb 上进行的 .

 

dictType 中定义的为各种函数 : 哈希函数 ,key 比较函数 ,key/value 复制函数等 .

dict 是主要是由 struct dictht 的哈希表构成的 , 之所以定义成长度为 2 的 (dictht ht[2]) 哈希表数组 , 是因为 redis 采用增量的 rehash. 这种渐进的 rehash 需要一个额外的 struct dictht 结构来保存 .

dictht 中的 table 是一个数组 + 指针形式的 hash 表， size 表 hash 数组 ( 桶 ) 的大小， used 表示 hash 表的元素个数，这两个值与 rehash 、 resize 过程密切相关。 sizemask 等于 size-1 ，这是为了方便将 hash 值映射到数组中。

iterators 记录当前 dict 中的迭代器数，主要是为了避免在有迭代器时 rehash ，在有迭代器时 rehash 可能会造成值的丢失或重复 .

rehashidx 表示上次 rehash 时在 ht[0] 的下标位置 .

 

关于 rehash:

1)原因:
redis使用的为动态大小的哈希表,当哈希表的大小不能满足需求,元素的hash碰撞比较多时进行扩容. 由于在数据结构中定义使用两个哈希表,当第一个表ht中的元素大于桶的个数时,进行扩容(dictAdd->_dictKeyIndex->_dictExpandIfNeeded->dictExpand),每次扩容大小为((d->ht[0].size > d->ht[0].used) ? d->ht[0].size : d->ht[0].used)*2,初始值为DICT_HT_INITIAL_SIZE = 4.扩容后开始将第一个表ht中的元素进行增量rehash到第二个表中,当rehash完成时,将第二个表赋给第一个表,并将原表内存释放.

/* Check if we already rehashed the whole table... */
if (d->ht[0].used == 0) {
  zfree(d->ht[0].table);
  d->ht[0] = d->ht[1];
  _dictReset(&d->ht[1]);
  d->rehashidx = -1;
  return 0;
}

 

2)原则: 增量更新与分批更新同时进行,不阻塞请求. 将操作平摊到每次操作,以及充分利用server idle时的CPU资源,以减少突然的rehash行为造成服务器性能的瞬间下降.
3)模式:
lazy rehashing：在每次对dict进行操作的时候执行一个slot的rehash
_dictRehashStep中，也会调用dictRehash，而_dictRehashStep每次仅会rehash一个值从ht[0]到ht[1]，但由于_dictRehashStep是被dictGetRandomKey、 dictFind、 dictGenericDelete、dictAdd调用的，因此在每次dict增删查改时都会被调用，这无疑就加快rehash了 过程。
active rehashing：每100ms里面使用1ms时间进行rehash。
serverCron中，当没有后台子线程时，会调用incrementallyRehash，最终调用dictRehashMilliseconds。 incrementallyRehash的时间较长，rehash的个数也比较多。这里每次执行 1 millisecond rehash 操作；如果未完成 rehash，会在下一个loop里面继续执行。
4)方法:
active rehashing: serverCron->incrementallyRehash->dictRehashMilliseconds->dictRehash(100)
lazy rehashing: dictAdd/dictGenericDelete/dictFind/dictGetRandomKey->_dictRehashStep-> dictRehash(1)