redis高性能分析

发表于 2020-05-28 更新于 2023-02-05 分类于 redis 阅读次数： Waline：本文字数： 6.2k 阅读时长 ≈ 6 分钟

redis高性能分析

内存
高效的数据结构时间复杂度O(1)
IO模型

数据类型

redis为了达到高性能，对数据类型做了调整，更好的适用于高并发

redis的源码相关文件如下：
t_hash.c, t_list.c, t_set.c, t_string.c, t_zset.c and t_stream.c contains the implementation of the Redis data types. They implement both an API to access a given data type, and the client commands implementations for these data types.

sds.c is the Redis string library, check http://github.com/antirez/sds for more information.

dict.c is an implementation of a non-blocking hash table which rehashes incrementally.

SDS

SDS使用C语言编写。C语言的字符串是用一个以\0结尾的char[]表示。
但是为什么不直接使用C语言字符串。
C语言字符串的缺点：

获取字符串长度每次需要遍历char[]数组，时间复杂度O(n)
修改字符串忘记分配内存容易造成缓冲区溢出 (buffer overflow) 。
修改字符串需要重新分配内存，设计系统调用。

SDS优点

获取字符串长度时间复杂度O(1) 。
通过封装，避免了直接操作C语言字符串忘记分配内存导致的内存泄露。
减少修改字符串时内存分配次数。

空间预分配惰性空间释放

二进制安全
SDS的buf保存的是二进制数组

struct sdshdr {
    int len;
    int free;
    char buf[];
};

redis里的key是保存了字符串的SDS
redis里的value

SDS实现

代码引用自 sds

sds.h redis/src/sds.h

#ifndef __SDS_H
#define __SDS_H

#define SDS_MAX_PREALLOC (1024*1024)
extern const char *SDS_NOINIT;

#include <sys/types.h>
#include <stdarg.h>
#include <stdint.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[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

可以看到 sds 有 sdshdr5 sdshdr8 sdshdr16 sdshdr32 sdshdr64， sdshdr5 is never used

链表

链表的优点是在任意位置增加、修改、删除节点只有O(1)的时间复杂度。而且不需要连续的内存。
缺点是不支持根据下标随机访问，需要遍历链表，所以访问指定元素时时间复杂度是O(N)

链表提供了高效的重排能力，以及顺序节点的访问。

redis 链表键、发布与订阅、慢查询、监视器也用到了链表。

adlist.h redis/src/adlist.h

/* adlist.h - A generic doubly linked list implementation
 */
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 int len;
} list;

每个链表节点由一个listNode结构表示，保存了指向前置节点、后置节点的指针。
每个链表由一个list结构表示，保存了头结点、尾节点、链表的长度等参数
链表的头结点的前置节点、尾节点的后置节点都指向NULL，所以redis链表是无环链表。
list结构里使用void*指针保存节点值，所以链表支持多种数据类型

字典

redis数据库底层就是用字典实现的。
hash结构底层也是用字典实现的。

redis字典底层使用哈希表实现。

字典实现

dict.h::dictht redis/src/dict.h

/* Hash Tables Implementation.
 *
 * This file implements in memory hash tables with insert/del/replace/find/
 * get-random-element operations. Hash tables will auto resize if needed
 * tables of power of two in size are used, collisions are handled by
 * chaining. See the source code for more information... :)
 */

#ifndef __DICT_H
#define __DICT_H

#define DICT_OK 0
#define DICT_ERR 1

/* Unused arguments generate annoying warnings... */
#define DICT_NOTUSED(V) ((void) V)

typedef struct dictEntry {
    void *key;
    void *val;
    struct dictEntry *next;
} dictEntry;

typedef struct dictType {
    unsigned int (*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];
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

/* If safe is set to 1 this is a safe iteartor, 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;
    int table, index, safe;
    dictEntry *entry, *nextEntry;
} dictIterator;

/* This is the initial size of every hash table */
#define DICT_HT_INITIAL_SIZE     4

可以看到

哈希表结构

/* 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;

table 代表哈希表数组
size 代表哈希表大小
sizemask 代表哈希表大小掩码，用于计算索引值
used 代表该哈希表已有的元素个数

哈希表节点，用来存储每个key和value

typedef struct dictEntry {
    void *key;
    void *val;
    struct dictEntry *next;
} dictEntry;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

根据源码可以看到redis自定义了hash函数，
哈希冲突时使用链地址法，
扩容时新建一个哈希表
在对哈希表进行扩容或缩容操作时，会把哈希表的键值对rehash到新哈希表里，这个rehash过程是渐进式完成的。

跳跃表

对象 redisObject

使用redisObject对象的好处

可以根据不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。
在回收内存时，直接使用对象
通过引用

可以在执行命令前根据对象的类型判断一个对象是否可以执行给定的命令

/*-----------------------------------------------------------------------------
 * Data types
 *----------------------------------------------------------------------------*/

/* A redis object, that is a type able to hold a string / list / set */

/* The actual Redis Object */
#define REDIS_LRU_CLOCK_MAX ((1<<21)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 10 /* LRU clock resolution in seconds */
typedef struct redisObject {
    unsigned type:4;
    unsigned storage:2;     /* REDIS_VM_MEMORY or REDIS_VM_SWAPPING */
    unsigned encoding:4;
    unsigned lru:22;        /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
    /* VM fields are only allocated if VM is active, otherwise the
     * object allocation function will just allocate
     * sizeof(redisObjct) minus sizeof(redisObjectVM), so using
     * Redis without VM active will not have any overhead. */
} robj;

References

[1] redis.io/documentation
[1] redis.io/topics/data-types
[2] redis.io/topics/data-types-intr
[3] redis-doc
[4] 10万+QPS 真的只是因为单线程和基于内存？
[5] 《Redis设计与实现》黄健宏
[6] redis.io/topics/internals-sds
[7] [github.com/antirez/sds github.com/antirez/sds )