redis高性能（1）数据结构

redis高性能的原因是什么，好记性不如烂笔头，写个系列把以往笔记写下来，这是开篇。讲之前先把redis为什么是单线程解释一下

redis是单线程吗

我们经常能听到别人说：redis是单线程，其实这里主要是指Redis的网络IO（redis 6.0版本支持多线程处理网络I O）和键值对读写（也就是执行命令）是由一个线程来完成的，这也是redis对外提供键值存储服务的主要流程。但redis的其他功能，比如持久化、异步删除、集群数据同步等，其实是由额外的线程执行的。

所以，严格来说，redis并不是单线程。

为什么执行命令使用单线程

使用多线程，可以增加系统吞吐率，或是可以增加系统扩展性。那为什么redis在执行命令时要采用单线程的方式呢？一个关键的瓶颈在于，系统中通常会存在被多线程同时访问的共享资源，比如一个共享的数据结构。当有多个线程要修改这个共享资源时，为了保证共享资源的正确性，就需要有额外的机制进行保证，而这个额外的机制，就会带来额外的开销。

拿redis举例。redis有List的数据类型，并提供出队（LPOP）和入队（LPUSH）操作。假设Redis采用多线程设计，线程A对一个List做LPUSH操作，并对队列长度加1。同时，线程B对该List执行LPOP操作，并对队列长度减1。为了保证队列长度的正确性，Redis需要让线程A和B的LPUSH和LPOP串行执行，这样一来，Redis可以无误地记录它们对List长度的修改。否则，可能会得到错误的长度结果。这就是多线程编程模式面临的共享资源的并发访问控制问题。并发访问控制一直是多线程开发中的一个难点问题，如果没有精细的设计，比如说，只是简单地采用一个粗粒度互斥锁，就会出现不理想的结果：即使增加了线程，大部分线程也在等待获取访问共享资源的互斥锁，并行变串行，系统吞吐率并没有随着线程的增加而增加。

而且，采用多线程开发一般会引入同步原语来保护共享资源的并发访问，这也会降低系统代码的易调试性和可维护性。为了避免这些问题，Redis直接采用了单线程模式。

为什么单线程redis可以那么快

那么回到主题，redis能使用单线程模型达到每秒数十万级别的处理能力，为什么？

一方面，Redis的大部分操作在内存上完成，再加上它采用了高效的数据结构，例如哈希表和跳表，这是它实现高性能的一个重要原因。另一方面，就是redis采用了I/O多路复用机制，使其在网络IO操作中能并发处理大量的客户端请求，实现高吞吐率。

1.大部分操作在内存

2.高效的数据结构

3.I/O多路复用

我们先来看第二点，高效的数据结构

redis数据结构

redis有String，Set，Sorted Set，Hash，List 5种数据类型

有简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组6种数据结构

对应关系如下图：

String类型的底层实现只有一种数据结构，也就是简单动态字符串。而List、Hash、Set和Sorted Set这四种数据类型，都有两种底层实现结构。通常情况下，我们会把这四种类型称为集合类型，它们的特点是一个键对应了一个集合的数据。

想一下这几个问题

• 这些数据结构中键和值本身之间用什么结构组织？
• 为什么集合类型有那么多的底层结构，它们都是怎么组织数据的，都很快吗？
• 什么是简单动态字符串，和常用的字符串是一回事吗？

键和值用什么结构组织？

为了实现从键到值的快速访问，Redis使用了一个哈希表来保存所有键值对。

一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。所以，我们常说，一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据。

看到这里，你可能会问了：“如果值是集合类型的话，作为数组元素的哈希桶怎么来保存呢？”其实，哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。这也就是说，不管值是String，还是集合类型，哈希桶中的元素都是指向它们的指针。

在下图中，可以看到，哈希桶中的entry元素中保存了*key和*value指针，分别指向了实际的键和值，这样一来，即使值是一个集合，也可以通过*value指针被查找到。

因为这个哈希表保存了所有的键值对，所以，把它称为全局哈希表。哈希表的最大好处很明显，就是让我们可以用O(1)的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值，就可以知道它所对应的哈希桶位置，然后就可以访问相应的entry元素。

每次创建一个 key-value 键值对，Redis 都会创建两个对象，一个是键对象，一个是值对象。而且需要注意的是在 Redis 中，值对象并不是直接存储，而是被包装成 redisObject 对象，并同时将键对象和值对象通过 dictEntry 对象进行封装，如下就是一个 dictEntry 对象：

typedef struct dictEntry {
    void *key;//指向key，即sds
    union {
        void *val;//指向value
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;//指向下一个key-value键值对(哈希值相同的键值对会形成一个链表，从而解决哈希冲突问题)
} dictEntry;

redisObject 对象的定义为：

typedef struct redisObject {
    unsigned type:4;//对象类型（4位=0.5字节）
    unsigned encoding:4;//编码（4位=0.5字节）
    unsigned lru:LRU_BITS;//记录对象最后一次被应用程序访问的时间（24位=3字节）
    int refcount;//引用计数。等于0时表示可以被垃圾回收（32位=4字节）
    void *ptr;//指向底层实际的数据存储结构，如：sds等(8字节)
} robj;

当我们在 Redis 客户端中执行命令 set name lonely_wolf ，就会得到下图所示的一个结构（省略了部分属性）：

查找过程主要依赖于哈希计算，和数据量的多少并没有直接关系。也就是说，不管哈希表里有10万个键还是100万个键，我们只需要一次计算就能找到相应的键。

但是，如果你只是了解了哈希表的O(1)复杂度和快速查找特性，那么，当你往Redis中写入大量数据后，就可能发现操作有时候会突然变慢了。这其实是因为你忽略了一个潜在的风险点，那就是哈希表的冲突问题和rehash可能带来的操作阻塞。

数据结构优化实践

举个例子。之前我做的一个业务场景是这样子的：将跑步路线ID和路线详情ID做一一对应的关联。当时我第一想法就是用redis String，因为都是单对单。但后面评审的时候，组内有同事指出：假设有一亿个跑步路线，就需要用到6GB的内存，大内存的redis实例在生成RDB时响应会变慢，可想而知这不是一个好的设计方案。先来说下为什么String类型内存开销大。

redis 的数据类型有很多，而且，不同数据类型都有些相同的元数据要记录（比如最后一次访问的时间、被引用的次数等），所以，redis 会用一个 RedisObject 结构体来统一记录这些元数据，同时指向实际数据。

一个 RedisObject 包含了 8 字节的元数据和一个 8 字节指针，这个指针再进一步指向具体数据类型的实际数据所在，例如指向 String 类型的 SDS 结构所在的内存地址，可以看一下下面的示意图。

我们前面说过，redis 会使用一个全局哈希表保存所有键值对，哈希表的每一项是一个 dictEntry 的结构体，用来指向一个键值对。也就是说，每一个key，都会有一个dictEntry的内存开销。

那么用什么数据结构可以节省内存呢？Redis 基于压缩列表实现了 List、Hash 和 Sorted Set 这样的集合类型，这样做的最大好处就是节省了 dictEntry 的开销。当你用 String 类型时，一个键值对就有一个 dictEntry，要用 32 字节空间。但采用集合类型时，一个 key 就对应一个集合的数据，能保存的数据多了很多，但也只用了一个 dictEntry，这样就节省了内存。

在用集合类型保存键值对时，一个键对应了一个集合的数据，但是在我的这个业务场景中，一个路线 ID 只对应一个路线详情 ID，该怎么用集合类型呢？

在保存单值的键值对时，可以采用基于 Hash 类型的二级编码方法。这里说的二级编码，就是把一个单值的数据拆分成两部分，前一部分作为 Hash 集合的 key，后一部分作为 Hash 集合的 value，这样一来，就可以把单值数据保存到 Hash 集合中了。

以路线 ID 1101000060 和图片存储对象 ID 3302000080 为例，可以把图片 ID 的前 7 位（1101000）作为 Hash 类型的键，把图片 ID 的最后 3 位（060）和图片存储对象 ID 分别作为 Hash 类型值中的 key 和 value。