redis1111

SDS

把SDS单独提一下，所有的用户数据在Redis中都是使用SDS进行存储的，之前内存模型中有详细说明过

String

string是Redis中最简单的键值对存储方式，使用字典进行实现，基于Hash表，当往Redis中添加一个键值对的时候，通过key计算出的hash值被映射到一个Hash表上（Hash居然是一个单向链表），由于是Hash值做的映射，会发生冲突，冲突的时候通过链表把数据（key）依次进行存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct dict {
    dictType *type;		// 记录类型，用于创建多类型的字典，不清楚具体作用

    dictEntry **ht_table[2];	// Hash表，这里有两个Hash表，正常只使用第一个，当第一个需要重做Hash时临时使用第二个
    unsigned long ht_used[2];		// 之前版本有个独立的dictht结构体用来存储Hash表的统计信息，估计现在存在这个地方了

    long rehashidx; /* rehashing not in progress if rehashidx == -1 用于保存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]; /* exponent of size. (size = 1<<exp) */
};

typedef 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. */
    void *metadata[];           /* An arbitrary number of bytes (starting at a
                                 * pointer-aligned address) of size as returned
                                 * by dictType's dictEntryMetadataBytes(). */
} dictEntry;

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(dict *d, const void *key);
    void *(*valDup)(dict *d, const void *obj);
    int (*keyCompare)(dict *d, const void *key1, const void *key2);
    void (*keyDestructor)(dict *d, void *key);
    void (*valDestructor)(dict *d, void *obj);
    int (*expandAllowed)(size_t moreMem, double usedRatio);
    /* Allow a dictEntry to carry extra caller-defined metadata.  The
     * extra memory is initialized to 0 when a dictEntry is allocated. */
    size_t (*dictEntryMetadataBytes)(dict *d);
} dictType;

比对从网上找到的Redis 3.x版本源码，结构做了调整，下图为3.x版本结构图：

3.x版本结构图

列表

列表的底层实现是链表

1
2
3
4
5
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

c中没有链表的实现，Redis自己实现了一个双向链表，这里的value应该是对应SDS的内存指针

1
2
3
4
5
6
7
8
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;

2023-05-10list

zset

zset在数据少的时候使用的压缩表，在数据多的时候使用跳跃表（SkipList）

跳跃表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

2023-05-12skiplist

  • 上面是查找元素的过程，类似于二叉查找树，时间复杂度为logn，但是相对二叉查找树它维持平衡的成本更低，是以空间换时间的思路
  • 数据删除，即是把元素在各个层的指针都断开，链接相邻节点指针
  • 添加元素，先把元素添加到最底层的有序链表中，再通过完全随机的抛硬币（50%）几率决定是否要将元素上浮，直到停下