深度剖析 Redis 九种数据结构实现原理

一、Redis 介绍

Redis 是一个高性能的键值存储系统，支持多种数据结构。

包含五种基本类型 String（字符串）、Hash（哈希）、List（列表）、Set（集合）、Zset（有序集合），和三种特殊类型 Geo（地理位置）、HyperLogLog（基数统计）、Bitmaps（位图）。

每种数据结构都是为了解决特定问题而设计的，适用不同的场景。想要用好 Redis，必须了解底层实现原理和使用技巧，同时结合具体的业务场景和需求进行选择和使用。无论是工作还是面试中，这些必备的知识。

下面就详细介绍一下每种数据类型的使用方式、实现原理和适用场景。

二、String（字符串）

String（字符串）是 Redis 中最基本的数据结构之一，它可以存储任意类型的数据，包括数字、文本、序列化的对象等。Redis 中的字符串最大可以存储 512MB 的数据。

使用方式

字符串类型的操作是最基本的，包括设置值、获取值、修改值、追加值等。字符串类型支持的操作包括：

应用场景

• 缓存：将计算结果、数据库查询结果或者配置数据存储在 Redis 中，可以提高应用的响应速度和吞吐量。

• 计数器：使用 Redis 的自增和自减操作，实现简单的计数器功能，如网站的访问次数统计

• 限流：使用 Redis 的 incr 和 expire 命令，实现固定窗口算法的流量控制，防止系统过载。

• 分布式锁：使用 SETNX 操作实现分布式锁，保证同一时刻只有一个线程访问临界资源。

• 会话管理：将用户会话信息存储在 Redis 中，可以实现分布式 Session。

内部编码

Redis 字符串的内部编码有三种：

1. int 编码：当字符串长度小于等于 12 字节并且字符串可以表示为整数时，Redis 会使用 int 编码。这样可以节省内存，并且在执行一些命令时可以直接进行数值计算。

2. embstr 编码：当字符串长度小于等于 39 字节时，Redis 会使用 embstr 编码。这种编码方式会将字符串和存储它的结构体一起分配在内存中，这样可以减少内存碎片和结构体的开销。

3. raw 编码：当字符串长度大于 39 字节或者字符串不能表示为整数时，Redis 会使用 raw 编码。这种编码方式直接将字符串存储在一个结构体中，没有进行任何优化。

三、Hash（哈希）

使用方式

哈希类型是一种键值对的集合，其中键值对的值可以是字符串、列表或者其他哈希类型。哈希类型支持的操作包括：

应用场景

• 存储对象：将对象的属性和属性值存储在哈希类型中，可以很方便地进行查询和更新操作，比如常见的用户信息就适合使用哈希类型存储。

内部编码

Redis 哈希类型的内部编码有两种：

1. ziplist（压缩列表）：当 Hash 类型的元素比较少，且元素的大小比较小（小于 64 字节）时，Redis 采用 ziplist 作为 Hash 类型的内部编码。ziplist 是一种紧凑的、压缩的列表结构，可以节省内存空间。但是，ziplist 只能进行线性查找，不支持快速的随机访问。

2. hashtable（字典）：当 Hash 类型的元素比较多，或者元素的大小比较大（大于 64 字节）时，Redis 采用 hashtable 作为 Hash 类型的内部编码。hashtable 是一种基于链表的哈希表结构，可以快速地进行随机访问。但是，hashtable 需要占用更多的内存空间。

四、List（列表）

使用方式

Redis List 类型是一个有序的字符串列表，支持在列表的头部或尾部添加元素，也支持在列表任意位置插入或删除元素。支持的操作包括：

使用场景

Redis List 类型由于支持在列表的头部或尾部添加元素，也支持在列表任意位置插入或删除元素，因此非常适合以下场景：

• 消息队列：Redis List 类型常被用作轻量级的消息队列，生产者将消息插入队列尾部，消费者从队列头部弹出消息进行处理，可以使用 LPUSH、RPUSH、BLPOP、BRPOP 等命令实现。

• 时间序列：使用 Redis 的 LPUSH 和 RPUSH 命令，将时间序列的数据按照时间顺序添加到列表的头部或尾部，然后使用 LRANGE 命令，查询一段时间范围内的数据，实现时间序列的查询。

• 排行榜：Redis List 类型可以用于实现排行榜功能，将每个用户的得分作为元素值插入到列表中，使用 LINSERT、LREM、LINDEX 等命令进行排名操作，使用 LRANGE 命令查询排名前几的用户，可以使用 LPUSH、LINSERT、LREM、LINDEX、LRANGE 等命令实现。

• 计数器：Redis List 类型可以将每个元素视为计数器的值，可以使用 LPUSH、RPUSH、LINDEX、LREM 等命令实现。

• 最近访问记录：Redis List 类型可以用于记录最近访问的记录，将最新的访问记录插入列表头部，当列表长度超过设定的值时，使用 LTRIM 命令删除最旧的记录，可以使用 LPUSH、LINDEX、LTRIM 等命令实现。

内部编码

Redis List 类型内部编码有两种，分别是 ziplist 和 linkedlist。

• ziplist

ziplist 是一种特殊的编码方式，它可以将小数据量的列表存储在一个连续的内存块中，节省了内存空间，同时还可以提高存取效率。

ziplist 编码的列表最大长度为 2^16-1 个元素，每个元素可以是字符串类型、整数类型或浮点数类型。在 ziplist 中，每个元素都被存储为一个字节数组，并包含一个前缀和一个后缀，用于标识该元素的类型和长度。

• linkedlist

linkedlist 是一种常规的双向链表结构，它可以存储任意长度的列表，并且支持高效的插入和删除操作。在 linkedlist 中，每个节点都包含了一个指向前一个节点和后一个节点的指针，以及一个存储元素数据的指针。

linkedlist 适用于存储大数量的列表，它没有像 ziplist 那样的内存限制，但是会占用更多的内存空间。

五、Set（集合）

使用方式

Redis Set（集合）是一个无序的字符串集合，其中每个元素都是唯一的，不允许重复。Redis Set 类型支持的操作包括：

使用场景

Redis Set 类型的使用场景包括：

• 标签系统：使用 Set 类型存储每个标签对应的对象列表，以便快速查找包含特定标签的对象。可以使用 SADD、SREM、SISMEMBER、SMEMBERS 等命令实现。

• 好友关系：将每个用户的好友列表作为一个集合，可以使用 SADD、SREM、SISMEMBER、SDIFF、SINTER、SUNION 等命令实现。

• 共同好友：使用 SINTER 命令计算出两个用户的共同好友，可以使用 SADD、SINTER、SUNION 等命令实现。

• 排名系统：将每个用户的得分作为元素值插入到集合中，使用 ZADD、ZREM、ZRANK、ZSCORE 等命令进行排名操作，使用 ZREVRANGE 命令查询排名前几的用户，可以使用 ZADD、ZREM、ZRANK、ZSCORE、ZREVRANGE 等命令实现。

• 订阅关系：使用 Set 类型存储用户订阅的内容，以便快速获取用户订阅的内容。

总的来说，Set 类型适用于需要存储一组不重复的数据，并支持集合操作的场景。

内部编码

Redis Set 类型的内部编码有两种：

1. intset（整数集合）：当 Set 类型只包含整数类型的数据，并且元素数量较少（小于 512 个）时，Redis 会使用 intset 作为 Set 类型的内部编码。intset 是一种紧凑的、压缩的整数集合结构，可以节省内存空间，并且支持快速的查找、插入和删除操作。在 intset 中，所有元素都按照从小到大的顺序排列，并且可以使用不同的编码方式（16 位、32 位、64 位）存储不同大小范围内的整数。

2. hashtable（字典）：当 Set 类型包含字符串类型或者元素数量较多时，Redis 会使用 hashtable 作为 Set 类型的内部编码。hashtable 是一种基于链表的哈希表结构，可以快速地进行随机访问、插入和删除操作。在 hashtable 中，每个元素都被存储为一个字符串，并且使用哈希函数将字符串映射到一个桶中，然后在桶中进行查找、插入和删除操作。

在实际使用中，当 Set 类型的元素全部为整数类型时，建议使用 intset 编码；而当 Set 类型的元素包含非整数类型时，才使用 hashtable 编码。

六、Zset（有序集合）

使用方式

Redis 中的 Zset（有序集合）是一个键值对集合，其中每个元素都关联一个分值（score），通过分值进行排序，可以看作是一个字典（dict）和一个跳跃列表（skip list）的混合体，它可以存储多个相同的元素，但每个元素必须有一个唯一的 score 值。

支持的操作包括：

使用场景

Redis Zset 是一种有序集合，其使用场景主要包括以下几个方面：

• 排行榜：使用 Zset 类型可以实现排行榜功能，将每个用户的得分作为元素值插入到集合中，使用 ZADD、ZINCRBY、ZREM 等命令进行排名操作，使用 ZRANGE、ZREVRANGE 命令查询排名前几的用户。

• 最近访问记录：使用 Zset 类型可以用于记录最近访问的记录，将最新的访问记录插入集合中，使用 ZREMRANGEBYRANK 命令删除最旧的记录，使用 ZRANGE 命令查询最近访问的记录。

• 计数器：Redis Zset 可以用于实现计数器功能，比如统计某个页面的访问次数、统计某个广告的点击量等。将页面 ID 或广告 ID 作为成员(member)存储在 Zset 中，以访问次数或点击量作为分数(score)存储。

• 好友关系：Redis Zset 可以用于存储用户之间的关注关系以及用户之间的互动，比如点赞、评论等。可以将用户 ID 作为成员(member)存储在 Zset 中，将时间戳或者其他标识作为分数(score)存储，以此记录用户之间的互动情况。

内部编码

Redis Zset 的内部编码有两种：

1. ziplist 编码：当 Zset 中元素个数小于 128 个，并且所有元素的长度都小于 64 字节时，Redis 会使用 ziplist 编码存储 Zset。这种编码方式可以节省内存空间，并且可以提高存取效率，但是不支持随机访问和范围查询。

2. skiplist 编码：当 Zset 中元素个数大于等于 128 个，或者有一个元素的长度大于 64 字节时，Redis 会使用 skiplist 编码存储 Zset。这种编码方式支持高效的随机访问和范围查询，但是需要占用更多的内存空间。

七、Geo（地理位置）

使用方式

Redis Geo（地理位置）是一个键值对集合，其中每个元素都包含一个经度和纬度，可以用于存储地理位置信息并支持基于位置的搜索。Redis Geo 支持的操作包括：

Redis Geo 类型适用于需要存储地理位置信息并支持基于位置的搜索的场景，比如附近的人、附近的商家等。

使用场景

Redis Geo 类型的使用场景如下：

1. 位置服务：用于存储地理位置信息，如餐厅、商店、机场、医院等的经纬度信息，可以通过 Geo 库提供的命令查询指定范围内的所有商家信息。

2. 车辆监控：用于车辆位置跟踪和监控，可以将车辆的经纬度信息存储在 Redis 中，并通过 Geo 库提供的命令查询车辆的位置，以及在指定半径内的其他车辆信息。

3. 物流配送：用于存储配送员的位置信息，以及需要配送的订单信息的经纬度信息，可以通过 Geo 库提供的命令查询配送员在指定范围内的订单信息，以提高配送效率。

4. 电商推荐：用于存储用户的位置信息，以及商家和商品的经纬度信息，可以通过 Geo 库提供的命令查询指定范围内的商家和商品信息，以提供更加精准的推荐服务。

5. 游戏地图：用于存储游戏地图的位置信息和玩家的位置信息，可以通过 Geo 库提供的命令查询玩家在游戏地图上的位置，以及在指定半径内的其他玩家信息，以提供更加丰富的游戏体验。

6. 社交应用：用于存储用户的位置信息，以及附近的其他用户的位置信息，可以通过 Geo 库提供的命令查询指定范围内的用户信息，以提供更加精准的社交服务。

内部编码

Redis Geo 类型内部使用 zset 来存储地理位置信息，其中元素的 score 值为经度，member 值为经纬度组合的字符串。在使用 GEORADIUS 和 GEORADIUSBYMEMBER 命令搜索元素时，Redis 会构建一个跳跃表，以实现高效的搜索。

八、HyperLogLog（基数统计）

使用方式

Redis HyperLogLog（基数统计）是一种基于概率统计的数据结构，用于估计大型数据集合的基数（不重复元素的数量），以及对多个集合进行并、交运算等。HyperLogLog 的优点是可以使用极少的内存空间，同时可以保证较高的准确性。

每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基数。

使用场景

HyperLogLog 的使用场景主要包括以下几个方面：

• 用户去重：使用 HyperLogLog 可以对海量的用户数据进行去重，快速地统计出不重复的用户数量。

• 网站 UV 统计：使用 HyperLogLog 可以对网站的访问日志进行分析，统计出每天、每周、每月的独立访客数量。

• 广告点击统计：使用 HyperLogLog 可以对广告的点击数据进行分析，统计出独立点击用户的数量，以及对多个广告进行并、交运算等。

• 数据库查询优化：使用 HyperLogLog 可以对数据库中的数据进行去重，减少查询的数据量，提高查询效率。

• 分布式计算：使用 HyperLogLog 可以在分布式系统中对数据进行去重、并、交等操作，以支持分布式计算。

使用 HyperLogLog 可以大大减少内存占用和计算时间，是处理大数据量去重计数的有效工具。

内部编码

Redis HyperLogLog 类型的内部编码使用的"稀疏矩阵"和”稠密矩阵“。

当计数较少时，采用”稀疏矩阵“，其中绝大部分元素都是 0。计数增多后，超过阈值后，会转换成”稠密矩阵“。

九、Bitmaps（位图）

使用方式

Redis Bitmaps（位图）是一种紧凑的数据结构，可以用于表示一个只有 0 和 1 的数组。位图可以用于高效地存储大规模的布尔值，以及进行位运算、位图图形化等操作。Redis Bitmaps 支持的操作包括：

使用场景

Redis Bitmaps 适用于需要高效地存储大规模的布尔值，并进行位运算、统计等操作的场景。比如：

• 统计在线用户数：使用 Bitmaps 类型来表示用户的在线状态，例如一个 bit 位表示一个用户，当用户登录时将对应的 bit 位置为 1，当用户退出时将其位置为 0。这样可以非常方便地进行在线用户的统计。

• 黑白名单统计：在网络安全中，可以使用位图记录 IP 地址的访问情况、黑白名单等信息。

• 统计用户访问行为：例如将每个页面或功能点表示为一个 bit 位，用户访问时将对应的 bit 位置为 1，未访问则为 0。这样就可以方便地统计用户的访问习惯，了解用户对产品的喜好和热点等信息。

• 布隆过滤器：这是最常用的场景，布隆过滤器是一种用于快速判断某个元素是否在集合中的算法，在大数据量场景下其效率非常高。Redis 的 Bitmaps 类型可以用来实现布隆过滤器，节约存储空间，并提高查询效率。

内部编码

Redis Bitmaps 类型的内部编码使用了一种称为“压缩位图”的数据结构。它通过使用两个数组来存储位图数据：一个存储实际位的值，另一个存储每个字节中 1 的个数。这种编码方式可以大大压缩位图数据的大小。

作者：一灯架构

链接：https://juejin.cn/post/7220607468699451449

来源：稀土掘金