redis中没有直接使用C语言的字符串,而是自定义了一种名为简单动态字符串的抽象类型——SDS。我们下载redis源码,可以在src目录下找到一个sds.h
的文件,打开这个文件查看它的部分代码:
typedef char *sds;
/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
根据代码注释我们知道:
因此sds示意图就是这样的:
那么redis为什么要这么设计呢,出于以下几点考虑:
在redis 源码中链表的定义可以通过adlist.h
查看:
/* Node, List, and Iterator are the only data structures used currently. */
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
typedef struct listIter {
listNode *next;
int direction;
} listIter;
typedef struct list {
listNode *head;
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned long len;
} list;
从源码我们可以看出链表由三个结构体来维护,list
\ listNode
\ listIter
。list结构为链表提供了表头指针 head,表尾指针 tail,链表长度 len。redis 链表有以下特点:
字典即map,redis字典使用哈希表作为底层的实现,每个哈希表节点中保存字典中的一个键值对。在redis的源码中可以通过dict.h
查看字典的定义:
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
typedef struct dictType {
uint64_t (*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;
/* 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;
unsigned long used;
} dictht;
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
/* If safe is set to 1 this is a safe iterator, that means, you can call
* dictAdd, dictFind, and other functions against the dictionary even while
* iterating. Otherwise it is a non safe iterator, and only dictNext()
* should be called while iterating. */
typedef struct dictIterator {
dict *d;
long index;
int table, safe;
dictEntry *entry, *nextEntry;
/* unsafe iterator fingerprint for misuse detection. */
long long fingerprint;
} dictIterator;
我们看到源码中有dictType
,dictEntry
,dict
,dictIterator
,dictht
这几个结构体来维护字典结构,(7.0以后版本无dictht)。其中dictIterator
为字典的迭代器,dictEntry
结构保存着一个键值对,dictEntry
属性说明:
结构体dictType
定义了一堆用于处理键值的函数,我们可以不去关心。
dictht
是一个哈希表结构,它通过将哈希值相同的元素放到一个链表中来解决冲突问题,属性说明:
结构体dict
包含的属性有:
dictType
结构的指针;dictht
哈希表;redis的hash算法使用的是MurmurHash2
,具体算法细节不做介绍。随着对hash的操作其中的键值对会发生改变,这个时候为了更合理的分配空间就需要进行hash重算(rehash)。在dict中ht属性是一个长度为2的dictht
数组,当进行hash重算的时候会将ht[0]的键值对rehash到ht[1]里面。rehash这个过程不是一次性完成的,是多次渐进式地去完成的。
rehash过程:
这种方式主要是为了避免集中的rehash所带来的庞大计算量。因为渐进式rehash会同时使用ht[0]和ht[1],所以在rehash期间redis对这个字典的更新查找等操作会同时在这两个ht中进行。
跳跃表是一种有序数据结构,它通过在每个节点中维持多个指针指向其他节点从而实现跳跃访问其他节点,zset的底层便是跳跃表。在redis源码中server.h
定义了跳跃表的结构:
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
我们看到zset 是由 dict
(集合)和zskiplist
(跳表)组成,zskiplist又包含了如下属性:
其中 header 和 tail 是结构体zskiplistNode
的指针,这个结构体便是跳表的节点,它有如下属性:
跳表的层可以包含多个元素,每个元素都包含指向一个节点的指针用于快速访问其他节点,比如程序访问节点1,节点的层包含了节点4的层,那么就可以跳跃到节点四,而不是一直遍历到节点4。
redis 使用对象来表示数据库中的键值,当我们在redis数据库中创建一个键值对时,至少会生成两个对象,用于表示key和value。redis对象源码:
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount;
void *ptr;
} robj;
属性说明:
redis 命令的多态,内存回收,内存共享,内存淘汰策略等特性都涉及到 redisObject,下一章节将单独讲解相关特性,感谢阅读。