关注互联网应用及运维技术的个人博客

REDIS-Hash存储原理

存储(实现)原理

Redis 的 Hash 本身也是一个 KV 的结构,类似于 Java 中的 HashMap

外层的哈希(Redis KV 的实现)只用到了 hashtable。当存储 hash 数据类型时,叫做内层的哈希,内层的哈希底层可以使用两种数据结构实现

ziplist:压缩列表,hashtable:哈希表

ziplist 压缩列表

ziplist 是一个经过特殊编码的双向链表,它不存储指向上一个链表节点和指向下一个链表节点的指针,而是存储上一个节点长度和当前节点长度,通过牺牲部分读写性能,来换取高效的内存空间利用率,是一种时间换空间的思想

ziplist 的内部结构

typedef struct zlentry {
unsigned int prevrawlensize;
unsigned int prevrawlen;
unsigned int lensize; 
unsigned int len; 
unsigned int headersize;
// encoding的长度
// #define ZIP_STR_06B (0 << 6) 长度小于等于 63 字节
// #define ZIP_STR_14B (1 << 6) 长度小于等于 16383 字节
// #define ZIP_STR_32B (2 << 6) 长度小于等于 4294967295 字节 
unsigned char encoding; 
unsigned char *p;
} zlentry;

当 hash 对象同时满足以下两个条件的时候,使用 ziplist 编码

所有的键值对的健和值的字符串长度都小于等于 64byte 哈希对象保存的键值对数量小于 512 个 一个哈希对象超过配置的阈值(键和值的长度有>64byte,键值对个数>512 个)时,会转换成哈希表(hashtable)

hashtable

在Redis中,hashtable被称为字典(dictionary),是一个数组+链表的结构

typedef struct dictEntry {
void *key; 
union {
void *val; uint64_t u64; 
int64_t s64; double d;
} v;
struct dictEntry *next; /* 指向下一个节点 */
} dictEntry;
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
dictEntry **table; /* 哈希表数组 */
unsigned long size; /* 哈希表大小 */
unsigned long sizemask; /* 掩码大小,用于计算索引值。总是等于 size-1 */
unsigned long used; /* 已有节点数 */
} dictht;
typedef struct dict {
dictType *type; /* 字典类型 */
void *privdata; /* 私有数据 */
dictht ht[2]; /* 一个字典有两个哈希表 */
long rehashidx; /* rehash 索引 */
unsigned long iterators; /* 当前正在使用的迭代器数量 */
} dict;

dictEntry放到了dictht中,dictht放到了dict中

赞(0)
未经允许不得转载:飞天狒狒 » REDIS-Hash存储原理

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址