Redis存储结构设计
Base 2.8.7
Redis是⼀个包含了很多Key-Value对的⼤字典，这个字典⽀持的Value⾮常丰富，可以为 字符串、哈希表、列表、集合和有序集，基于这些类型丰富的value，扩展出了功能强⼤的操作，例如hmset、lpush、sadd等
字典
字典是Redis最基础的数据结构，⼀个字典即⼀个DB，Redis⽀持多DB
Redis字典采⽤Hash表实现，针对碰撞问题，其采⽤的⽅法为“链地址法”，即将多个哈希值相同的节点串连在⼀起， 从⽽解决冲突问题。
“链地址法”的问题在于当碰撞剧烈时，性能退化严重，例如：当有n个数据，m个槽位，如果m=1，则整个Hash表退化为链表，查询复杂度O(n)
为了避免Hash碰撞攻击，Redis随机化了Hash表种⼦
Redis的⽅案是“双buffer”，正常流程使⽤⼀个buffer，当发现碰撞剧烈（判断依据为当前槽位数和Key数的对⽐），分配⼀个更⼤的buffer，然后逐步将数据从⽼的buffer迁移到新的buffer。
Redis字典结构如下：
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2]; //双buffer
int rehashidx;
int iterators;
} dict;
typedef struct dictht {
dictEntry **table; //hash链表
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
//数据节点<K,V>
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
struct dictEntry *next;
} dictEntry;
redisObject是真正存储redis各种类型的结构，其内容如下：
typedef struct redisObject {
unsigned type:4; //逻辑类型
unsigned notused:2;    /* Not used */
unsigned encoding:4; //物理存储类型
unsigned lru:22;        /* lru time (relative to server.lruclock) */
int refcount;
void *ptr;  //具体数据
} robj;
其中type即redis⽀持的逻辑类型，包括：
#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4
enconding为物理存储⽅式，⼀种逻辑类型可以使⽤不同的存储⽅式，包括：
#define REDIS_ENCODING_RAW 0    /* Raw representation */
#define REDIS_ENCODING_INT 1    /* Encoded as integer */
#define REDIS_ENCODING_HT 2      /* Encoded as hash table */
#define REDIS_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define REDIS_ENCODING_INTSET 6  /* Encoded as intset */
#define REDIS_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
字符串
Redis的所有的key都采⽤字符串保存，另外，Redis也⽀持字符串类型的value。
字符串类型即前⽂中看到的REDIS_STRING，其物理实现（enconding）可以为 REDIS_ENCODING_INT或REDIS_ENCODING_RAW  REDIS_ENCODING_INT保存为long型，即redis会尝试将⼀个字符串转化为Long，可以转换的话，即保存为REDIS_ENCODING_INT
否则，Redis会将REDIS_STRING保存为字符串类型，即REDIS_ENCODING_RAW
字符串类型在redis中⽤sds封装，主要为了解决长度计算和追加效率的问题，其定义如下：
typedef char *sds;
struct sdshdr {
int len; // buf 已占⽤长度
int free; // buf 剩余可⽤长度redis五种数据结构
char buf[];// 柔性数组，实际保存字符串数据的地⽅
};
static inline size_t sdslen(const sds s) {
struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
return sh->len;
}
static inline size_t sdsavail(const sds s) {
struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
return sh->free;
}
有时间的同学可以详细看下Sds.h和Sds.c两个⽂件，还是很有意思的。
Hash表
Redis⽀持Value为Hash表，其逻辑类型为REDIS_HASH，REDIS_HASH可以有两种encoding⽅式： REDIS_ENCODING_ZIPLIST 和REDIS_ENCODING_HT
REDIS_ENCODING_HT即前⽂提到的字典的实现
REDIS_ENCODING_ZIPLIST即，是⼀种双端列表，且通过特殊的格式定义，压缩内存适⽤，以时间换空间。ZIPLIST适合⼩数据量的读场景，不适合⼤数据量的多写/删除场景
Hash表默认的编码格式为REDIS_ENCODING_ZIPLIST，在收到来⾃⽤户的插⼊数据的命令时：
1，调⽤hashTypeTryConversion函数检查键/值的长度⼤于 配置的hash_max_ziplist_value（默认64）
2，调⽤hashTypeSet判断节点数量⼤于 配置的hash_max_ziplist_entries （默认512）
以上任意条件满⾜则将Hash表的数据结构从REDIS_ENCODING_ZIPLIST转为REDIS_ENCODING_HT
列表
Redis⽀持Value为⼀个列表，其逻辑类型为REDIS_SET，REDIS_SET有两种encoding⽅式，REDIS_ENCODING_ZIPLIST和
REDIS_ENCODING_LINKEDLIST
REDIS_ENCODING_ZIPLIST同上
REDIS_ENCODING_LINKEDLIST是⽐较正统双端链接表的实现:
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
列表的默认编码格式为REDIS_ENCODING_ZIPLIST，当满⾜以下条件时，编码格式转换为REDIS_ENCODING_LINKEDLIST
1，元素⼤⼩⼤于list-max-ziplist-value（默认64）
2，元素个数⼤于 配置的list-max-ziplist-entries（默认512）
集合
Redis⽀持Value为集合，其逻辑类型为REDIS_SET，REDIS_SET有两种encoding⽅式： REDIS_ENCODING_INTSET 和
REDIS_ENCODING_HT（同上）
集合的元素类型和数量决定了encoding⽅式，默认采⽤REDIS_ENCODING_INTSET ，当满⾜以下条件时，转换为
REDIS_ENCODING_HT：
1. 元素类型不是整数
2. 元素个数超过配置的“set-max-intset-entries”（默认512）
REDIS_ENCODING_INTSET是⼀个有序数组，使⽤的数据结构如下：
typedef struct intset {
uint32_t encoding;  //3种类型：INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64
uint32_t length; //元素个数
int8_t contents[]; //元素实际存放的位置，按序排放
} intset;
Redis会根据整数⼤⼩选择最适合的类型，当发⽣变更时，进⾏调整
有序集
Redis⽀持Value为有序集合，其逻辑类型为REDIS_ZSET，REDIS_ZSET有两种encoding⽅式： REDIS_ENCODING_ZIPLIST（同上）和 REDIS_ENCODING_SKIPLIST
REDIS_ENCODING_SKIPLIST使⽤的数据结构如下，其同事：
typedef struct zset {
dict *dict;  //Hash字典（同前⽂）
zskiplist *zsl; //跳跃表
} zset;
由于有续集每⼀个元素包括：<member，score>两个属性，为了保证对member和score都有很好的查询性
能，REDIS_ENCODING_SKIPLIST同时采⽤字典和有序集两种数据结构来保存数据元素。字典和有序集通过指针指向同⼀个数据节点来避免数据冗余。
字典中使⽤member作为key，score作为value，从⽽保证在O(1)时间对member的查
跳跃表基于score做排序，从⽽保证在 O(logN) 时间内完成通过score对memer的查询
有续集默认也是采⽤REDIS_ENCODING_ZIPLIST的实现，当满⾜以下条件时，转换为REDIS_ENCODING_SKIPLIST
1. 数据元素个数超过配置的zset_max_ziplist_entries 的值（默认值为 128 ）
2. 新添加元素的 member 的长度⼤于配置的 zset_max_ziplist_value 的值（默认值为 64 ）
总结
针对同⼀种数据类型，Redis会根据元素类型/⼤⼩/个数采⽤不同的编码⽅式，不同的编码⽅式在内存使⽤效率/查询效率上差距巨⼤，在遇
到内存问题时，可以尝试下修改相关参数：
hash-max-ziplist-entries 512
hash-max-ziplist-value 64
list-max-ziplist-entries 512
list-max-ziplist-value 64
set-max-intset-entries 512
zset-max-ziplist-entries 128
zset-max-ziplist-value 64

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。