之前就说了要来西索Redis，现在来辣！
本文的部分内容参考自《小林Coding》，部分地方根据源代码进行剖析。
Redis源码地址：https://github.com/redis/redis.git
阅读本文之前建议先阅读我的上一篇文章：神奇，Redis存储原理竟然是这样！ – Karos (wzl.fyi)
Hash
建议先阅读：神奇，Redis存储原理竟然是这样！ – Karos (wzl.fyi)，或者本页面的第一章
观其面
哈希结构大家也不陌生了，kv嘛，redis不就是kv模型嘛，那么Redis里面hash又是啥？
这里给大家说一下，就是套娃，用伪代码表示就是这样
HashMap<String,HashMap<String,String>>
当然，实际的类型是泛型。
和String相比具体的区别就是这样
如果你用mysql数据库来表示的话
hash其实是field,value
然后每个hash对应一个表
如果放在Redis的话就是一个key里面放了很多个field,value
可以这样理解：
key field value
其实神简单，说多了还容易绕
应用场景
购物车实现
key：uid
field：商品id
value: 数量
- 添加商品：
HSET cart:{用户id} {商品id} 1 - 添加数量：
HINCRBY cart:{用户id} {商品id} 1 - 商品总数：
HLEN cart:{用户id} - 删除商品：
HDEL cart:{用户id} {商品id} - 获取购物车所有商品：
HGETALL cart:{用户id}
获取商品信息还得进数据库回表一次，拿到完整的商品信息
分布式锁实现
Redis分布式锁深入分析 – Karos (wzl1.top)
之前我讲过，这里再简单说一下把
key为锁名，field是线程ID（加上服务的UUID），然后value是进入锁的次数
看一个加锁的Lua脚本吧，为什么用Lua脚本？我们后面细说。
-- 如果Lock存在
if redis.call("exists",KEYS[1]) ~= 0 then
-- 如果不是自己的锁
if redis.call("exists",KEYS[1],ARGS[1]) == 0 then
-- 不是自己的锁，返回剩余时间
return redis.call("pttl",KEYS[1]);
end
-- 如果是自己的锁就记录次数
redis.call("hincrby",KEYS[1],ARGS[1],1);
-- 延期
redis.call("pexpire",KEYS[1],ARGS[2]);
else
-- 如果Lock不存在，那么就直接加上就可以了，hhh
redis.call("hset",KEYS[1],ARGS[1],1);
-- 设置默认延期
redis.call("pexpire",KEYS[1],ARGS[2]);
end
return nil;
究其身
当数据量少的时候使用压缩链表（早期，Redis7.0以后完成的对ZipList的全部替代，都用LIstPack来实现了）
- 如果哈希类型元素个数小于
512个（默认值，可由hash-max-ziplist-entries和hash-max-listpack-entries配置），所有值小于64字节（默认值，可由hash-max-ziplist-value配置）的话，Redis 会使用压缩列表/ListPack作为 Hash 类型的底层数据结构； - 如果哈希类型元素不满足上面条件，Redis 会使用哈希表作为 Hash 类型的 底层数据结构。
哈希结构客户端哈希设计（基于Redis 7.0解释）
在之前我们讲过dict，dict是用于存储key和value的，但是这里我们客户端hash是将dictEntry的集合放入value，显然不能够用原来服务器的value来存储一个新的dict，你不知道客户端输入的是什么属性
呃呃呃，这上面几句话说的可能有点绕，看代码吧。
其实Redis的开发者确实考虑到了这一点，所以做了个区分，两个虽然都叫做dict，但是所属dir不一样
// /deps/hiredis/dict.h 客户端源码
typedef struct dict {
dictEntry **table;
dictType *type;
// 哈希表大小，桶的数量
unsigned long size;
// 哈希表大小掩码，用于计算索引值
unsigned long sizemask;
// 已有哈希节点数量
unsigned long used;
void *privdata;
} dict;
typedef struct dictEntry {
void *key;
void *val;
struct dictEntry *next;
} dictEntry;
typedef struct dictType {
unsigned int (*hashFunction)(const void *key);
void *(*keyDup)(void *privdata, const void *key);
void *(*valDup)(void *privdata, const void *obj);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
void (*keyDestructor)(void *privdata, void *key); // 析构
void (*valDestructor)(void *privdata, void *obj); // 析构
} dictType;
先说一下新增元素，RedisHash采用的是头插法
/* Add an element to the target hash table */
static int dictAdd(dict *ht, void *key, void *val) {
int index;
dictEntry *entry;
/* Get the index of the new element, or -1 if
* the element already exists. */
if ((index = _dictKeyIndex(ht, key)) == -1)
return DICT_ERR;
/* Allocates the memory and stores key */
entry = hi_malloc(sizeof(*entry));
if (entry == NULL)
return DICT_ERR;
// 执行头茬
entry->next = ht->table[index];
ht->table[index] = entry;
/* Set the hash entry fields. */
dictSetHashKey(ht, entry, key);
dictSetHashVal(ht, entry, val);
ht->used++;
return DICT_OK;
}
对于Hash结构来说，有个扩容操作，同时会伴随rehash，我们来看看
/* Expand or create the hashtable */
static int dictExpand(dict *ht, unsigned long size) {
dict n; /* the new hashtable */
unsigned long realsize = _dictNextPower(size), i; // 通过该方法获取真实内存，扩大为比size大的第一个2^n
/* the size is invalid if it is smaller than the number of
* elements already inside the hashtable */
if (ht->used > size) // size不合法，如果哈希总节点数大于了size
return DICT_ERR;
// 对新的hash进行初始化
_dictInit(&n, ht->type, ht->privdata);
n.size = realsize;
n.sizemask = realsize-1;
n.table = hi_calloc(realsize,sizeof(dictEntry*));
if (n.table == NULL)
return DICT_ERR;
/* Copy all the elements from the old to the new table: 把旧数据复制到新的哈希表中
* note that if the old hash table is empty ht->size is zero,
* so dictExpand just creates an hash table. */
n.used = ht->used;
for (i = 0; i < ht->size && ht->used > 0; i++) {
dictEntry *he, *nextHe;
if (ht->table[i] == NULL) continue;
/* For each hash entry on this slot... */
he = ht->table[i];
while(he) {
unsigned int h;
nextHe = he->next; // 先获取下一次循环需要的entry
/* Get the new element index */ // 通过计算哈希值获取新的下标（索引计算），其实相当于对长度取余
h = dictHashKey(ht, he->key) & n.sizemask;
// 头插
he->next = n.table[h];
n.table[h] = he;
ht->used--; // ht被使用的节点减少
/* Pass to the next element */
he = nextHe; // 移步到下一个
}
}
assert(ht->used == 0);
hi_free(ht->table);
/* Remap the new hashtable in the old */
*ht = n;
return DICT_OK;
}
为什么扩容是2^n
其实这里哈希表扩容和Java中HashMap扩容原理一样，我们来回忆一下
HashMap是如何扩容的
HashMap扩容依靠的是resize()方法，根据负载因子来计算临界值，达到临界值进行扩容。
而resize()方法也是通过一个newTable进行操作的
Rehash如何确定新元素的位置
通过将hashcode()%length，当leng为$2^n$时，刚好等于hashcode()&(length-1)
但是对于Redis对象存储来说，具体的rehash的方法是拉链法，和JavaSE HashMap类似，同样使用，这样做只是为了加快计算（直接对内存庶几乎进行操作）
Redis服务端存储原理-Hash解析
ReHash
在之前，其实讲到了，Redis的存储原理，其中使用的dict中，直接便是dictEntry
dictEntry **ht_table[2]; // 第二个表用来进行rehash
/**
* dictEntry **ht_table[2]; <==>
* typedef struct dictht{
* dictEntry **table;
* }dictht;
* ditcht ht[2];
**/
之前我们说到第二个ht_table用来做rehash，是这样的，原理其实和上面也类似。
不过为了内存切换方便，每次rehash的时候，只需要将ht_table[0]和ht_table[1]进行交换即可，扩容完毕后直接使用，不用再换回去（类比JVM中幸存区From和幸存区To的交换）。
那么为什么服务端存储kv的哈希靠复制交换，而客户端确是直接新建一个dict Ｎ呢？
其实原因可想而知。
- 服务器的ht数量是固定的，而hash的数据是由客户端操作，数量不定，如果采取复制的话浪费空间，要扩容的时候new一个就行，这一个其实不太重要，重要的在后面
- 最重要的其实时，服务端一定会保证长连接状态，当数据量很大的时候，我们不可能花较长时间来进行rehash，所以我们采用两个哈希表进行渐进式rehash
渐进式ReHash
为了避免 rehash 在数据迁移过程中，因拷贝数据的耗时，影响 Redis 性能的情况，所以 Redis 采用了渐进式 rehash，也就是将数据的迁移的工作不再是一次性迁移完成，而是分多次迁移。
渐进式 rehash 步骤如下：
- 给「哈希表 2」 分配空间；
- 在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上；
- 随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点会把「哈希表 1 」的所有 key-value 迁移到「哈希表 2」，从而完成 rehash 操作。
这样就巧妙地把一次性大量数据迁移工作的开销，分摊到了多次处理请求的过程中，避免了一次性 rehash 的耗时操作。
在进行渐进式 rehash 的过程中，会有两个哈希表，所以在渐进式 rehash 进行期间，哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。
比如，查找一个 key 的值的话，先会在「哈希表 1」 里面进行查找，如果没找到，就会继续到哈希表 2 里面进行找到。
另外，在渐进式 rehash 进行期间，新增一个 key-value 时，会被保存到「哈希表 2 」里面，而「哈希表 1」 则不再进行任何添加操作，这样保证了「哈希表 1 」的 key-value 数量只会减少，随着 rehash 操作的完成，最终「哈希表 1 」就会变成空表。
ReHash触发条件
介绍了 rehash 那么多，还没说什么时情况下会触发 rehash 操作呢？
rehash 的触发条件跟负载因子（load factor）有关系。
负载因子可以通过下面这个公式计算：
触发 rehash 操作的条件，主要有两个：
- 当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作。
- 当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作。
服务端哈希扩容
在讲扩容源码之前，我们先来回顾之前讲的内容
// dictEntry的实现很简单，就是个链表
struct dictEntry {
void *key;
union {
void *val; // 其他
uint64_t u64; // 整数
int64_t s64; // 整数
double d; // 双精度数值
} v;
struct dictEntry *next; /* Next entry in the same hash bucket. 指向下一个hash值相同的entry*/
void *metadata[]; /* An arbitrary number of bytes (starting at a
* pointer-aligned address) of size as returned
* by dictType's dictEntryMetadataBytes(). */
};
struct dict {
dictType *type;
dictEntry **ht_table[2]; // 第二个表用来进行rehash
/**
* dictEntry **ht_table[2]; <==>
* typedef struct dictht{
* dictEntry **table;
* }dictht;
* ditcht ht[2];
**/
unsigned long ht_used[2];
// 用于保证rehash安全，如果值为-1，那么不能执行rehash
long rehashidx;
// redis6之后新加入，如果值>0则暂停rehash，保证rehash安全
/* Keep small vars at end for optimal (minimal) struct padding */
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
// 哈希的内存指数
signed char ht_size_exp[2];
// 由dictType的dictEntryBytes定义的大小的任意字节数(从指针对齐的地址开始)。
void *metadata[];
};
说到这里，我们来看看扩容的源码，先来个宏定义
#define dictIsRehashing(d) ((d)->rehashidx != -1)
再来一个获取新内存大小的源码
static signed char _dictNextExp(unsigned long size)
{
unsigned char e = DICT_HT_INITIAL_EXP;
if (size >= LONG_MAX) return (8*sizeof(long)-1);
// 这里采用的是用移位来计算，保证效率
while(1) {
if (((unsigned long)1<<e) >= size)
return e;
e++;
}
}
一个判断是否运行扩容的"私有"函数
/* ------------------------- private functions ------------------------------ */
/* Because we may need to allocate huge memory chunk at once when dict
* expands, we will check this allocation is allowed or not if the dict
* type has expandAllowed member function. */
static int dictTypeExpandAllowed(dict *d) {
// 不允许返回1
if (d->type->expandAllowed == NULL) return 1;
// 这里的计算我们后面讲
return d->type->expandAllowed(
DICTHT_SIZE(_dictNextExp(d->ht_used[0] + 1)) * sizeof(dictEntry*),
(double)d->ht_used[0] / DICTHT_SIZE(d->ht_size_exp[0]));
}
下面是扩容源码
/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
/* Incremental rehashing already in progress. Return. */
// 如果正在rehash，那么直接返回Ok
if (dictIsRehashing(d)) return DICT_OK;
/* If the hash table is empty expand it to the initial size. */
// 如果哈希表是空的，那么就创建
if (DICTHT_SIZE(d->ht_size_exp[0]) == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
/* If we reached the 1:1 ratio, and we are allowed to resize the hash
* table (global setting) or we should avoid it but the ratio between
* elements/buckets is over the "safe" threshold, we resize doubling
* the number of buckets. */
// 如果不被允许扩展就返回ok
if (!dictTypeExpandAllowed(d))
return DICT_OK;
if ((dict_can_resize == DICT_RESIZE_ENABLE &&
d->ht_used[0] >= DICTHT_SIZE(d->ht_size_exp[0])) ||
(dict_can_resize != DICT_RESIZE_FORBID &&
d->ht_used[0] / DICTHT_SIZE(d->ht_size_exp[0]) > dict_force_resize_ratio))
{
return dictExpand(d, d->ht_used[0] + 1); // +1是为了避免和当前分配相同的内存
}
// 分配成功
return DICT_OK;
}
/* Expand or create the hash table,
* when malloc_failed is non-NULL, it'll avoid panic if malloc fails (in which case it'll be set to 1).
* Returns DICT_OK if expand was performed, and DICT_ERR if skipped. */
int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
{
if (malloc_failed) *malloc_failed = 0;
/* the size is invalid if it is smaller than the number of
* elements already inside the hash table */
if (dictIsRehashing(d) || d->ht_used[0] > size) // 判断是否能够哈希，并且传入的size合法
return DICT_ERR;
/* the new hash table */
dictEntry **new_ht_table; // 创建一个新的哈希表
unsigned long new_ht_used;
signed char new_ht_size_exp = _dictNextExp(size); // 计算log(新哈希表的长度)
/* Detect overflows */
size_t newsize = 1ul<<new_ht_size_exp; // 计算长度
if (newsize < size || newsize * sizeof(dictEntry*) < newsize) // 如果比原来的还小
return DICT_ERR;
/* Rehashing to the same table size is not useful. */
if (new_ht_size_exp == d->ht_size_exp[0]) return DICT_ERR; // 如果和原来相同，没用
/* Allocate the new hash table and initialize all pointers to NULL */ // 分配内存，并且memset all为NULL
if (malloc_failed) {
new_ht_table = ztrycalloc(newsize*sizeof(dictEntry*));
*malloc_failed = new_ht_table == NULL; // 判断是否分配成功
if (*malloc_failed)
return DICT_ERR;
} else
new_ht_table = zcalloc(newsize*sizeof(dictEntry*));
new_ht_used = 0; // 新的表还没有使用过
/* Is this the first initialization? If so it's not really a rehashing
* we just set the first hash table so that it can accept keys. */
if (d->ht_table[0] == NULL) {
// 如果是第一次次创建，使用第一张表为哈希表
d->ht_size_exp[0] = new_ht_size_exp;
d->ht_used[0] = new_ht_used;
d->ht_table[0] = new_ht_table;
return DICT_OK;
}
/* Prepare a second hash table for incremental rehashing */
// 使用第二张表进行rehash
d->ht_size_exp[1] = new_ht_size_exp;
d->ht_used[1] = new_ht_used;
d->ht_table[1] = new_ht_table;
// 表示当前表正在进行哈希中，后续不可以进行rehash，具体的判断在前面的宏定义内
d->rehashidx = 0;
return DICT_OK;
}
