java面试

从数据存储角度分析Redis性能为何如此高

2019-04-08  本文已影响168人  AKyS佐毅

1、Redis性能如此高的原因：

2、在Redis中，常用的 5 种数据结构和应用场景如下：

3、特殊的字符串结构SDS

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

例如：执行命令 set key value，key 和 value 都是一个 SDS 类型的结构存储在内存中。

SDS 与 C 字符串的区别

4、字典

与 Java 中的 HashMap 类似，Redis 中的 Hash 比 Java 中的更高级一些。

Redis 本身就是 KV 服务器，除了 Redis 本身数据库之外，字典也是哈希键的底层实现。

字典的数据结构如下所示：

typedef struct dict{
      dictType *type;
    void *privdata;
    dictht ht[2];
    int trehashidx;
}

typedef struct dictht{
    //哈希表数组
    dectEntrt **table;
    //哈希表大小
    unsigned long size;
    //
    unsigned long sizemask;
    //哈希表已有节点数量
    unsigned long used;
}

重要的两个字段是 dictht 和 trehashidx，这两个字段与 rehash 有关，下面重点介绍 rehash。

Rehash

当然是为了 Rehash，Rehash 的过程如下：

渐进式 Rehash

前一过程如下：

注意，由于维护了两张 Hash 表，所以在 Rehash 的过程中内存会增长。另外，在 Rehash 过程中，字典会同时使用 ht[0] 和 ht[1]。

所以在删除、查找、更新时会在两张表中操作，在查询时会现在第一张表中查询，如果第一张表中没有，则会在第二张表中查询。但新增时一律会在 ht[1] 中进行，确保 ht[0] 中的数据只会减少不会增加。

5、跳跃表 

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;
image

在查询过程中跳跃着前进。由于存在后退指针，如果查询时超出了范围，通过后退指针回退到上一个节点后仍可以继续向前遍历。

6、压缩列表

压缩列表 ziplist 是为 Redis 节约内存而开发的，是列表键和字典键的底层实现之一。

当元素个数较少时，Redis 用 ziplist 来存储数据，当元素个数超过某个值时，链表键中会把 ziplist 转化为 linkedlist，字典键中会把 ziplist 转化为 hashtable。

ziplist 是由一系列特殊编码的连续内存块组成的顺序型的数据结构，ziplist 中可以包含多个 entry 节点，每个节点可以存放整数或者字符串。

由于内存是连续分配的，所以遍历速度很快。

image

7、编码转化

Redis 使用对象（redisObject）来表示数据库中的键值，当我们在 Redis 中创建一个键值对时，至少创建两个对象，一个对象是用做键值对的键对象，另一个是键值对的值对象。

例如我们执行 SET MSG XXX 时，键值对的键是一个包含了字符串“MSG“的对象，键值对的值对象是包含字符串"XXX"的对象。

redisObject 的结构如下：

typedef struct redisObject{
    //类型
   unsigned type:4;
   //编码
   unsigned encoding:4;
   //指向底层数据结构的指针
   void *ptr;
    //...
 }robj;

其中 type 字段记录了对象的类型，包含字符串对象、列表对象、哈希对象、集合对象、有序集合对象。

当我们执行 type key 命令时返回的结果如下：

image

ptr 指针字段指向对象底层实现的数据结构，而这些数据结构是由 encoding 字段决定的，每种对象至少有两种数据编码：

image

可以通过 object encoding key 来查看对象所使用的编码：

image

细心的读者可能注意到，list、hash、zset 三个键使用的是 ziplist 压缩列表编码，这就涉及到了 Redis 底层的编码转换。

上面介绍到，ziplist 是一种结构紧凑的数据结构，当某一键值中所包含的元素较少时，会优先存储在 ziplist 中，当元素个数超过某一值后，才将 ziplist 转化为标准存储结构，而这一值是可配置的。

String 对象的编码转化

String 对象的编码可以是 int 或 raw，对于 String 类型的键值，如果我们存储的是纯数字，Redis 底层采用的是 int 类型的编码，如果其中包括非数字，则会立即转为 raw 编码：

127.0.0.1:6379> set str 1
OK
127.0.0.1:6379> object encoding str
"int"
127.0.0.1:6379> set str 1a
OK
127.0.0.1:6379> object encoding str
"raw"
127.0.0.1:6379>

List 对象的编码转化

List 对象的编码可以是 ziplist 或 linkedlist，对于 List 类型的键值，当列表对象同时满足以下两个条件时，采用 ziplist 编码：

列表对象保存的所有字符串元素的长度都小于 64 字节。
列表对象保存的元素个数小于 512 个。
如果不满足这两个条件的任意一个，就会转化为 linkedlist 编码。注意：这两个条件是可以修改的，在 redis.conf 中：

list-max-ziplist-entries 512
list-max-ziplist-value 64

Set 类型的编码转化

Set 对象的编码可以是 intset 或 hashtable，intset 编码的结婚对象使用整数集合作为底层实现，把所有元素都保存在一个整数集合里面。

127.0.0.1:6379> sadd set 1 2 3
(integer) 3
127.0.0.1:6379> object encoding set
"intset"
127.0.0.1:6379>
如果 set 集合中保存了非整数类型的数据时，Redis 会将 intset 转化为 hashtable：

127.0.0.1:6379> sadd set 1 2 3
(integer) 3
127.0.0.1:6379> object encoding set
"intset"
127.0.0.1:6379> sadd set a
(integer) 1
127.0.0.1:6379> object encoding set
"hashtable"
 127.0.0.1:6379>

当 Set 对象同时满足以下两个条件时，对象采用 intset 编码：

不能满足这两个条件的任意一个，Set 都会采用 hashtable 存储。注意：第两个条件是可以修改的，在 redis.conf 中：

set-max-intset-entries 512

Hash 对象的编码转化

Hash 对象的编码可以是 ziplist 或 hashtable，当 Hash 以 ziplist 编码存储的时候，保存同一键值对的两个节点总是紧挨在一起，键节点在前，值节点在后：

当 Hash 对象同时满足以下两个条件时，Hash 对象采用 ziplist 编码：

如果不满足以上条件的任意一个，ziplist 就会转化为 hashtable 编码。注意：这两个条件是可以修改的，在 redis.conf 中：

hash-max-ziplist-entries 512
hash-max-ziplist-value 64

Zset 对象的编码转化

Zset 对象的编码可以是 ziplist 或 zkiplist，当采用 ziplist 编码存储时，每个集合元素使用两个紧挨在一起的压缩列表来存储。

第一个节点存储元素的成员，第二个节点存储元素的分值，并且按分值大小从小到大有序排列。

当 Zset 对象同时满足一下两个条件时，采用 ziplist 编码：

如果不满足以上条件的任意一个，ziplist 就会转化为 zkiplist 编码。注意：这两个条件是可以修改的，在 redis.conf 中：

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

思考：Zset 如何做到 O(1) 复杂度内元素并且快速进行范围操作？Zset 采用 skiplist 编码时使用 zset 结构作为底层实现，该数据结构同时包含了一个跳跃表和一个字典。

其结构如下：

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

Zset 中的 dict 字典为集合创建了一个从成员到分值之间的映射，字典中的键保存了成员，字典中的值保存了成员的分值，这样定位元素时时间复杂度是 O(1)。

Zset 中的 zsl 跳跃表适合范围操作，比如 ZRANK、ZRANGE 等，程序使用 zkiplist。

另外，虽然 Zset 中使用了 dict 和 skiplist 存储数据，但这两种数据结构都会通过指针来共享相同的内存，所以没有必要担心内存的浪费。

8、过期数据的删除对 Redis 性能影响

当我们对某些 key 设置了 expire 时，数据到了时间会自动删除。如果一个键过期了，它会在什么时候删除呢？

下面介绍三种删除策略：

具体的操作如下：

总结

特别感谢:向代码致敬
原文地址：从数据存储角度分析Redis性能为何如此高

详情介绍:

更新主题详情

420天以来，Java架构更新了 888个主题，已经有156+位同学加入。微信扫码关注java架构，获取Java面试题和架构师相关题目和视频。上述相关面试题答案，尽在Java架构中。

上一篇 下一篇

猜你喜欢

热点阅读