Redis中的Hash
Hash基础简介
哈希表是根据键直接访问内存储存位置的数据结构。它通过一个哈希函数,计算键对应的哈希值,然后,将数据存储在对应的区域。加快数据查找。
使用哈希函数计算哈希表地址时,可能会遇到地址冲突。有两种解决方式:开发寻址法,链地址法。开放寻址法就是,取当前冲突的地址的下一个空闲地址作为当前的哈希地址;链地址法是将哈希表每个位置的所有值保存在一个链表中。当遇到冲突时,追加在链表中。
Redis中的Hash
简介
Redis中大量应用哈希结构来存储数据。常见的k-v,hash等,底层存储都是hash字典。暂时抛开Redis而言,如果自己要实现一个hash存储,需要考虑哪些方面呢?
首先,我们需要选择一个hash函数来处理key。此外,需要考虑地址冲突,这个冲突处理决定了我们这个hash的存储结构。这几个方面定好了,大致就可以实现一个基础的hash了。但是不仅仅如此,如果考虑到数据增长的问题,我们不可能一开始就申请一个G的内存来存储数据,最好是根据需要来申请。这就需要考虑一个扩容的处理。此外,当hash表扩容以后,原先拥挤的hash是不是需要重新考虑一下优化呢。就像,原先住在10平米的房子,桌子,柜子上堆满了杂物。现在搬到了一个20平米的房子,有足够的空间了,这时候就需要重新整理房间了。这个过程叫做rehash
。
通过上面一个设想,也就大致说出了Redis中hash的相关知识。Redis使用链地址法来处理地址冲突,它的hash表有n个bucket。每个bucket对应一组数据。在Redis 3.0的版本中,使用的是MurmurHash 2.0
哈希函数来计算索引。Redis的扩容思路是,当,hash表中总的元素数/hash表总的bucket数 > 负载因子,进行扩容操作。扩容大小是找到一个2^n值,刚好大于等于原始bucket的两倍。每次扩容后,会触发rehash
操作。Redis采用渐进式rehash
来优化结构。所谓渐进式就是,每次只调整几个bucket,慢慢的全部调整完。
具体实现
首先是hash相关的结构体定义
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
typedef struct dictType {
...
} dictType;
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; /* number of iterators currently running */
} dict;
这些结构体,用一张图来表示如下
大致过程是,当Redis初始化hash时,先初始化一个dict
结构体。(这里是有误的,初始的Redis hash结构底层并不是字典,而是一个压缩表。只有当大小达到一个范围时,才会采用字典存储hash。但是这里主要学习hash,所以不在意这个逻辑。)
然后,此时执行hset hello world
,Redis会执行dictAddRaw
方法,目的是,往这个哈希表中插入一个元素。插入元素的过程中,会首先计算这个key的hash,找到对应的bucket。如果当前bucket已经有元素了,Redis是将最新的数据插入到链表的开头。简简单单的一个插入,里面还隐藏了一些其他的额外操作,包括扩容等。可以看下面的代码。
插入函数如下
dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;
// 如果当前哈希表在rehash状态,则忙里偷闲的rehash一次
if (dictIsRehashing(d)) _dictRehashStep(d);
// 计算hash,找到对应的bucket。这里面也有其他文章。
if ((index = _dictKeyIndex(d, key)) == -1)
return NULL;
// 如果在rehash状态,则把个元素插入到ht[1]表中,否则插入到ht[0]表中。
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;
dictSetKey(d, entry, key);
return entry;
}
计算key的hash值,找到bucket
static int _dictKeyIndex(dict *d, const void *key)
{
unsigned int h, idx, table;
dictEntry *he;
/**
* 在这里进行hash表的扩容操作!
* 扩容思路就是,如果当前hash表为空,则初始化4个bucket。
* 如果当前bucket不为空,则,根据bucket数和已经存在的元素数来找到一个合适的2^n大小。
*/
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
// 根据murmurhash2算法,计算一个32位的hash值
h = dictHashKey(d, key);
// 这里遍历ht[0]和ht[1]。是因为,rehash操作,会让两个哈希表均有数据存在。所以需要全部查一遍。
for (table = 0; table <= 1; table++) {
/**
* 重要。这里解释了为什么扩容的大小必须是2^n。
* 因为sizemask = size - 1。所以转为二进制,即是全1。这里进行&操作,能保证均匀分布在bucket中。
*/
idx = h & d->ht[table].sizemask;
/* Search if this slot does not already contain the given key */
he = d->ht[table].table[idx];
while(he) {
if (dictCompareKeys(d, key, he->key))
return -1;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return idx;
}
rehash操作
rehash
一般发生在hash扩容后。可以看到前面的Redis字典结构,每个字典都有两个哈希表。即是通过这两个表来进行rehash
操作的。
大致思路是,当发生扩容以后,会标记字典rehashidx
状态值。表明,进入rehash状态。Redis在一些操作里面打了锚点,如果当前处于rehash
状态,则顺手执行一次rehash
。挺好的,均摊一下执行成本。
rehash
执行过程。扩容后,两个hash表的大小是一样的。rehash
就是将ht[0]里面的bucket,重新计算hash,存入到ht[1]中。每次搬完一个bucket,ht[0].used就减一。这样,当归0后,即表示全部迁移完了。然后就是释放ht[0]的内存,将ht[0]和ht[1]互换。
一个感觉,就是有条不紊。hash表大的话,可能几百万个元素,如果阻塞执行,还是挺费时的。
其他
Redis中hash字典还有一个比较重要的应用。我们知道Redis中有数据库的概念。即RedisDb。Redis支持多个数据库,只不过通常都是使用的默认的0数据库。RedisDb底层就是一个dict
结构。也就是说,Redis的所有k-v数据都存在一个hash表中。
接着,思考一个小问题,一个RedisDb一共可以存储多少个k-v数据?
答案是2^32个。为什么呢?因为redis中的hash算法只能生成一个32位hash值。另外,也因为字典中的size和sizemask使用的是unsighed long
类型,这个类型使用4个字节32位,也就是说,sizemask最大是2^32-1。即使一个128位的hash,进行与操作后,最终也只能得到一个2^32范围内的bucket索引,此时hash失效了。不过,实际情况,内存容量也不会支持这么多key。
最后
Redis作为Web开发中的一个基础组件,应用相当广泛。本身使用c语言编写,可读性还是很强的。可以扩宽自己的一些思路。
··· 完 ···
版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0许可协议,转载请注明出处。