Redis 基础架构

Redis [3]

RedisObject 和数据结构

Posted by ZYT on November 17, 2018

RedisObject

RedisObject 的结构：

typedef struct redisObject {
    //类型
    unsigned type:4;

    // 编码
    unsigned encoding:4;

    // 指向数据结构的指针
    void *ptr;

    // 高 16 位用来记录访问时间，用于 LRU
    // 低 8 位用来记录访问频率，用于 LFU
    unsigned lru:24;

    // 引用计数
    int refcount;

    // 数据指针
    void *ptr;
    // ...
} robj;

对象的类型

type 属性指定类型：

-------------------------------------------
    类型常量   |  对象的名称  | 调用 type 命令
-------------------------------------------
 REDIS_STRING |  字符串对象  |  "string"
 REDIS_LIST   |  列表对象    |  "list"
 REDIS_HASH   |  哈希对象    |  "hash"
 REDIS_SET    |  集合对象    |  "set"
 REDIS_ZSET   |  有序集合对象 |  "zset"

编码和底层实现

encoding 属性指定编码：

--------------------------------------------------------------------------------------
    类型常量   |             编码常量         |          数据结构        | object encoding
--------------------------------------------------------------------------------------
 REDIS_STRING |  REDIS_ENCODING_INT        |      long 类型的整数      |   "int"
 REDIS_STRING |  REDIS_ENCODING_EMBSTR     | embstr 编码的简单动态字符串 |   "embstr"
 REDIS_STRING |  REDIS_ENCODING_RAW        |       简单动态字符串       |   "raw"

 REDIS_LIST   |  REDIS_ENCODING_ZIPLIST    |          压缩列表         |   "ziplist"   [version 3.2 之前] 
 REDIS_LIST   |  REDIS_ENCODING_LINKEDLIST |          双端列表         |   "linkedlist"[version 3.2 之前] 
 REDIS_LIST   |  REDIS_ENCODING_QUICKLIST  |          快速列表         |   "quicklist" [version 3.2 之后]

 REDIS_HASH   |  REDIS_ENCODING_ZIPLIST    |          压缩列表         |   "ziplist"
 REDIS_HASH   |  REDIS_ENCODING_HT         |            字典          |   "hashtable"

 REDIS_SET    |  REDIS_ENCODING_INTSET     |          整数集合         |   "intset"
 REDIS_SET    |  REDIS_ENCODING_HT         |            字典          |   "hashtable"

 REDIS_ZSET   |  REDIS_ENCODING_ZIPLIST    |          压缩列表         |   "ziplist"
 REDIS_ZSET   |  REDIS_ENCODING_SKIPLIST   |           跳跃表          |   "skiplist"

RedisObject 的优势

  • 在执行命令之前，根据对象的类型即可判断一个对象是否可以执行给定的命令
  • 在不同场景采用不同数据结构实现，优化对象在不同场景下的使用效率
  • 基于引用计数技术的内存回收机制和对象共享机制
  • 记录访问时间，计算键的空转时间，如果服务器打开了 maxmemory 选项，并且服务器用于回收内存的算法为 volatile-lru 或者 allkeys-lru ，那么当服务器占用的内存数超过了 maxmemory 选项所设置的上限值时，空转时长较高的那部分键会优先被服务器释放，从而回收内存

字符串对象

  • int

8 个字节的长整数

  • embstr

<=39 字节的字符串

  • raw

>39 字节的字符串

embstr 与 raw 的区别：

  1. 创建和释放内存时，raw 需要调用两次函数，而 embstr 只需要调用一次函数
  2. embstr 编码的字符串对象的所有数据都保存在一块连续的内存里面，能够更好的利用缓存的优势
  3. 当字符串的长度增加需要重新分配内存时，embstr 整体重新分配空间，所以 embstr 实现为只读

列表对象

  • 压缩列表
    • 列表对象保存的所有字符串元素的长度都小于 64 字节
    • 列表对象保存的元素数量小于 512 个

压缩列表 - Redis 设计与实现

  • 双端列表

不满足条件的列表对象采用双端列表

双端列表 - Redis 设计与实现

        **注意：在 Redis 3.2 之后，列表对象的数据结构采用 quicklist**

quicklist 是一个节点为压缩列表的双端列表，设计的原因：

  • 双端列表的优缺点

优点：操作方便

缺点：存储前后指针，内存开销较大，且地址不联系，容易产生碎片

  • 压缩列表的优缺点：

优点：整块连续内存，存储效率高

缺点：操作不方便，每次数据变动都会引发内存的分配和数据拷贝

结合双端列表和压缩列表的 quicklist 就产生了，随之也引发了新问题：

压缩列表的长度

长度过短，退化为双端列表
长度过长，退化为压缩列表

redis 提供了可进行配置的参数：

# Lists are also encoded in a special way to save a lot of space.
# The number of entries allowed per internal list node can be specified
# as a fixed maximum size or a maximum number of elements.
# For a fixed maximum size, use -5 through -1, meaning:
# -5: max size: 64 Kb  <-- not recommended for normal workloads
# -4: max size: 32 Kb  <-- not recommended
# -3: max size: 16 Kb  <-- probably not recommended
# -2: max size: 8 Kb   <-- good
# -1: max size: 4 Kb   <-- good
# Positive numbers mean store up to _exactly_ that number of elements
# per list node.
# The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size),
# but if your use case is unique, adjust the settings as necessary.
list-max-ziplist-size -2

当列表很长，两端的数据被高频访问，中间的数据被低频访问的场景

redis 提供了可进行配置的参数，可以将中间的数据进行压缩：

# Lists may also be compressed.
# Compress depth is the number of quicklist ziplist nodes from *each* side of
# the list to *exclude* from compression.  The head and tail of the list
# are always uncompressed for fast push/pop operations.  Settings are:
# 0: disable all list compression
# 1: depth 1 means "don't start compressing until after 1 node into the list,
#    going from either the head or tail"
#    So: [head]->node->node->...->node->[tail]
#    [head], [tail] will always be uncompressed; inner nodes will compress.
# 2: [head]->[next]->node->node->...->node->[prev]->[tail]
#    2 here means: don't compress head or head->next or tail->prev or tail,
#    but compress all nodes between them.
# 3: [head]->[next]->[next]->node->node->...->node->[prev]->[prev]->[tail]
# etc.
list-compress-depth 0

哈希对象

  • 压缩列表
    • 哈希对象保存的所有字符串元素的长度都小于 64 字节
    • 哈希对象保存的元素数量小于 512 个

这两个上限值可进行修改：

# Hashes are encoded using a memory efficient data structure when they have a
# small number of entries, and the biggest entry does not exceed a given
# threshold. These thresholds can be configured using the following directives.
hash-max-ziplist-entries 512
hash-max-ziplist-value 64
  • 字典

不满足条件的哈希对象采用字典

Redis 使用 MurmurHash2 这种运行速度快、随机性好的哈希算法作为哈希函数，对于哈希冲突问题，Redis 采用链表法来解决。

字典 - Redis 设计与实现

集合对象

  • 整数集合
    • 集合对象保存的所有元素都是整数值
    • 集合对象保存的元素数量小于 512 个

第二个条件的上限值可进行修改：

# Sets have a special encoding in just one case: when a set is composed
# of just strings that happen to be integers in radix 10 in the range
# of 64 bit signed integers.
# The following configuration setting sets the limit in the size of the
# set in order to use this special memory saving encoding.
set-max-intset-entries 512

整数集合 - Redis 设计与实现

  • 字典

不满足条件的集合对象采用字典

有序集合对象

  • 压缩列表
    • 有序集合对象保存的所有字符串元素的长度都小于 64 字节
    • 有序集合对象保存的元素数量小于 128 个

这两个上限值可进行修改：

# Similarly to hashes and lists, sorted sets are also specially encoded in
# order to save a lot of space. This encoding is only used when the length and
# elements of a sorted set are below the following limits:
zset-max-ziplist-entries 128
zset-max-ziplist-value 64
  • skiplist

不满足条件的有序集合对象采用 skiplist 编码，其底层使用 zset，其中同时包含一个字典和跳跃表

跳跃表 - Redis 设计与实现

目录
    标签云
    Redis 基础架构 Docker Python 编程语言 Airflow Code & Life Message Queue Kubernetes Nginx Flutter Liunx Flask