redis旧版小hash使用的数据结构,紧密数组存储结构 用1字节存储总节点数(如果1字节满了,代表需要遍历到底才知道有多少节点) 每个节点存储自己占用的内存空间,修改删除后,标记为闲置空间,闲置空间不压缩不回收,留用节点扩展或者插入节点 这也代表插入没有足够闲置时要O(n)移动后续内存 数据也是占用zipmap内存,所以查找是O(n)(利用len做快表跳跃)
<zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"<ZIPMAP_END>
新版小hash使用的数据结构,紧密数组存储结构 用1字节存储总节点数(如果1字节满了,代表需要遍历到底才知道有多少节点) 每个节点存储自己占用的内存空间和前一节点占用内存空间 修改删除后,实时压缩内存(o(N)移动后续节点前移) 数据不占用ziplist内存,ziplist里保存一个entry,entry存储指针指向值对象的动态内存 好处是节点大小固定(sizeof(entry)),随机下标访问可以基于下标直接算内存地址访问
<zlbytes><zltail><zllen><entry><entry><zlend>
环形双端链表,没啥好说的
这里比较特别的是一个字典里会有最多两个hash表同时存在,目的是rehash的时候可以做渐进式hash table的结构是个数组,每个元素是一条链表,redis最小rehash单位为链表,所以为了避免rehash的时候元素过多需要卡住服务器很久,采取部分rehash,然后用一个标记维护处于rehash中未完成(rehashidx),新增操作和修改操作发现有该标记,新的插入会插入到新hash表,然后在每次查询、修改处,执行单步rehash(单条链表) 也就是把rehash的时间消耗分摊下去,不要一下子卡住服务很久 因为新数据都会到新hash,所以几次下来旧hash就空了,旧hash空了以后就把新hash作为主hash,释放旧hash表了
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点,形成链表
struct dictEntry *next;
} dictEntry;
typedef struct dictht {
// 哈希表
dictEntry **table;// (dictEntry * ) table[]
// 哈希表大小
unsigned long size;
// 哈希表大小掩码,用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
typedef struct dict {
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时,值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
redis的全遍历(scan)是按照bucket的顺序遍历(单个bucket同步,多个也是分摊异步) 采用了一些算法保证中间过程触发一次rehash不影响,具体: 从小往大顺序异步遍历,则在缩容时可能导致没有遍历过的大编号bucket被rehash到已经遍历过的小编号bucket,导致遍历遗漏 (扩容不影响) 解决的方法就是在同步遍历某个bucket时,把缩容一次后会聚拢到该bucket的bucket也遍历了,也就是idx与(idx + size/2) % size 比如size是8,缩容后就是4,所以对size为8的遍历就是
0->4
1->5
2->6
3->7
基于idx与idx + size/2这个公式得到的bucket 源码里把这用一个数学公式体现(反序+1后再反序)
//每次从高位进1
000 0 -》 100 4
001 1 -》 101 5
010 2 -》 110 6
011 3- 》 111 7