Redis深入理解(一)源码索引以及数据结构

原创
07/08 09:13
阅读数 0

    Redis存储对象类型共有5种:string(字符串),set(集合),zset(有序集合),list(列表),hash(哈希)。存储对象5种,但是底层实现的数据结构却比较灵活。底层数据结构有:SDS(simple dynamic string)简单动态字符串、链表、字典、跳跃表、整数集合、压缩列表。

源码索引:

附录:各个源码文件的作用简介
------------------------------

+-------------------------------------------------------------------+-------------------------------------------------------------------+
| 文件                                                              | 作用                                                              |
+===================================================================+===================================================================+
| ``adlist.c`` 、 ``adlist.h``                                      | 双端链表数据结构的实现。                                          |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``ae.c`` 、 ``ae.h`` 、 ``ae_epoll.c`` 、 ``ae_evport.c`` 、      | 事件处理器,以及各个具体实现。                                    |
| ``ae_kqueue.c`` 、 ``ae_select.c``                                |                                                                   |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``anet.c`` 、 ``anet.h``                                          | Redis 的异步网络框架,内容主要为对 socket 库的包装。              |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``aof.c``                                                         | AOF 功能的实现。                                                  |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``asciilogo.h``                                                   | 保存了 Redis 的 ASCII LOGO 。                                     |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``bio.c`` 、 ``bio.h``                                            | Redis 的后台 I/O 程序,用于将 I/O 操作放到子线程里面执行,        |
|                                                                   | 减少 I/O 操作对主线程的阻塞。                                     |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``bitops.c``                                                      | 二进制位操作命令的实现文件。                                      |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``blocked.c``                                                     | 用于实现 BLPOP 命令和 WAIT 命令的阻塞效果。                       |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``cluster.c`` 、 ``cluster.h``                                    | Redis 的集群实现。                                                |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``config.c`` 、 ``config.h``                                      | Redis 的配置管理实现,负责读取并分析配置文件,                    |
|                                                                   | 然后根据这些配置修改 Redis 服务器的各个选项。                     |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``crc16.c`` 、 ``crc64.c`` 、 ``crc64.h``                         | 计算 CRC 校验和。                                                 |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``db.c``                                                          | 数据库实现。                                                      |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``debug.c``                                                       | 调试实现。                                                        |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``dict.c`` 、 ``dict.h``                                          | 字典数据结构的实现。                                              |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``endianconv.c`` 、 ``endianconv.h``                              | 二进制的大端、小端转换函数。                                      |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``fmacros.h``                                                     | 一些移植性方面的宏。                                              |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``help.h``                                                        | ``utils/generate-command-help.rb`` 程序自动生成的命令帮助信息。   |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``hyperloglog.c``                                                 | HyperLogLog 数据结构的实现。                                      |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``intset.c`` 、 ``intset.h``                                      | 整数集合数据结构的实现,用于优化 SET 类型。                       |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``lzf_c.c`` 、 ``lzf_d.c`` 、 ``lzf.h`` 、 ``lzfP.h``             | Redis 对字符串和 RDB 文件进行压缩时使用的 LZF 压缩算法的实现。    |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``Makefile`` 、 ``Makefile.dep``                                  | 构建文件。                                                        |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``memtest.c``                                                     | 内存测试。                                                        |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``mkreleasehdr.sh``                                               | 用于生成释出信息的脚本。                                          |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``multi.c``                                                       | Redis 的事务实现。                                                |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``networking.c``                                                  | Redis 的客户端网络操作库,                                        |
|                                                                   | 用于实现命令请求接收、发送命令回复等工作,                        |
|                                                                   | 文件中的函数大多为 write 、 read 、 close 等函数的包装,          |
|                                                                   | 以及各种协议的分析和构建函数。                                    |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``notify.c``                                                      | Redis 的数据库通知实现。                                          |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``object.c``                                                      | Redis 的对象系统实现。                                            |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``pqsort.c`` 、 ``pqsort.h``                                      | 快速排序(QuickSort)算法的实现。                                 |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``pubsub.c``                                                      | 发布与订阅功能的实现。                                            |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``rand.c`` 、 ``rand.h``                                          | 伪随机数生成器。                                                  |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``rdb.c`` 、 ``rdb.h``                                            | RDB 持久化功能的实现。                                            |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``redisassert.h``                                                 | Redis 自建的断言系统。                                            |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``redis-benchmark.c``                                             | Redis 的性能测试程序。                                            |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``redis.c``                                                       | 负责服务器的启动、维护和关闭等事项。                              |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``redis-check-aof.c`` 、 ``redis-check-dump.c``                   | RDB 文件和 AOF 文件的合法性检查程序。                             |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``redis-cli.c``                                                   | Redis 客户端的实现。                                              |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``redis.h``                                                       | Redis 的主要头文件,记录了 Redis 中的大部分数据结构,             |
|                                                                   | 包括服务器状态和客户端状态。                                      |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``redis-trib.rb``                                                 | Redis 集群的管理程序。                                            |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``release.c`` 、 ``release.h``                                    | 记录和生成 Redis 的释出版本信息。                                 |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``replication.c``                                                 | 复制功能的实现。                                                  |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``rio.c`` 、 ``rio.h``                                            | Redis 对文件 I/O 函数的包装,                                     |
|                                                                   | 在普通 I/O 函数的基础上增加了显式缓存、以及计算校验和等功能。     |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``scripting.c``                                                   | 脚本功能的实现。                                                  |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``sds.c`` 、 ``sds.h``                                            | SDS 数据结构的实现,SDS 为 Redis 的默认字符串表示。               |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``sentinel.c``                                                    | Redis Sentinel 的实现。                                           |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``setproctitle.c``                                                | 进程环境设置函数。                                                |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``sha1.c`` 、 ``sha1.h``                                          | SHA1 校验和计算函数。                                             |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``slowlog.c`` 、 ``slowlog.h``                                    | 慢查询功能的实现。                                                |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``solarisfixes.h``                                                | 针对 Solaris 系统的补丁。                                         |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``sort.c``                                                        | SORT 命令的实现。                                                 |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``syncio.c``                                                      | 同步 I/O 操作。                                                   |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``testhelp.h``                                                    | 测试辅助宏。                                                      |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``t_hash.c`` 、 ``t_list.c`` 、 ``t_set.c`` 、 ``t_string.c`` 、  | 定义了 Redis 的各种数据类型,以及这些数据类型的命令。             |
| ``t_zset.c``                                                      |                                                                   |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``util.c`` 、 ``util.h``                                          | 各种辅助函数。                                                    |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``valgrind.sup``                                                  | valgrind 的suppression文件。                                      |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``version.h``                                                     | 记录了 Redis 的版本号。                                           |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``ziplist.c`` 、 ``ziplist.h``                                    | ZIPLIST 数据结构的实现,用于优化 LIST 类型。                      |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``zipmap.c`` 、 ``zipmap.h``                                      | ZIPMAP 数据结构的实现,在 Redis 2.6 以前用与优化 HASH 类型,      |
|                                                                   | Redis 2.6 开始已经废弃。                                          |
+-------------------------------------------------------------------+-------------------------------------------------------------------+
| ``zmalloc.c`` 、 ``zmalloc.h``                                    | 内存管理程序。                                                    |
+-------------------------------------------------------------------+-------------------------------------------------------------------+

动态字符串实现:

struct sdshdr {
    // buf 中已占用空间的长度
    int len;
    // buf 中剩余可用空间的长度
    int free;
    // 数据空间
    char buf[];
};

链表:

typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

字典:

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时,值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */
} dict;

跳跃表:

typedef struct zskiplistNode {
    // 成员对象
    robj *obj;
    // 分值
    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 intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组,内部可以是int8,int16,int32,int64
    int8_t contents[];

} intset;

压缩列表:直接看源码吧

对象实现:

typedef struct redisObject {
    // 类型
    unsigned type:4;
    // 编码
    unsigned encoding:4;
    // 对象最后一次被访问的时间
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    // 引用计数
    int refcount;
    // 指向实际值的指针
    void *ptr;
} robj;

encoding用来指定底层数据结构使用哪一种。refcount是引用计数,针对Integer类型数据的value,如果有一样的,则直接用一份数据就好,不用开辟内存。refcount++.达到数据共享的效果。

    判定数据是否可以共享,需要进行数据校验,目前Redis只对包含整数的字符串对象进行 共享,原因是因为校验时间复杂度是O(1). 如果是字符串值的字符串对象,时间复杂度为O(N).如果对象包含多个值,或对象的对象,或者列表对象,或者哈希对象,那么验证操作的复杂度将会是O(N^2).

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部