越致力，越侥幸，
本文已珍藏在GitHub中JavaCommunity, 外面有面试分享、源码剖析系列文章，欢送珍藏，点赞
https://github.com/Ccww-lx/Ja...

在理论开发，Redis应用会频繁，那么在应用过程中咱们该如何正确抉择数据类型呢？哪些场景下实用哪些数据类型。而且在面试中也很常会被面试官问到Redis数据结构方面的问题：

  • Redis为什么快呢？
  • 为什么查问操作会变慢了？
  • Redis Hash rehash过程
  • 为什么应用哈希表作为Redis的索引

当咱们剖析了解了Redis数据结构，能够为了咱们在应用Redis的时候，正确抉择数据类型应用，晋升零碎性能。

Redis底层数据结构

Redis 是一个内存键值key-value 数据库，且键值对数据保留在内存中，因而Redis基于内存的数据操作，其效率高，速度快；

其中，Key是String类型，Redis 反对的 value 类型包含了 String、List 、 Hash 、 Set 、 Sorted Set 、BitMap等。Redis 可能之所以可能宽泛地实用泛滥的业务场景，基于其多样化类型的value。

而Redis的Value的数据类型是基于为Redis自定义的对象零碎redisObject实现的，

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

redisObject除了记录理论数据，还须要额定的内存空间记录数据长度、空间应用等元数据信息，其中蕴含了 8 字节的元数据和一个 8 字节指针，指针指向具体数据类型的理论数据所在位置：

其中，指针指向的就是基于Redis的底层数据结构存储数据的地位，Redis的底层数据结构：SDS，双向链表、跳表，哈希表，压缩列表、整数汇合实现的。

那么Redis底层数据结构是怎么实现的呢？

Redis底层数据结构实现

咱们先来看看Redis比较简单的SDS,双向链表，整数汇合。

SDS、双向链表和整数汇合

SDS，应用len字段记录已应用的字节数，将获取字符串长度复杂度升高为O(1)，而且SDS是惰性开释空间的，你free了空间，零碎把数据记录下来下次想用时候可间接应用。不必新申请空间。

整数汇合，在内存中调配一块地址间断的空间，数据元素会挨着寄存，不须要额定指针带来空间开销，其特点为内存紧凑节俭内存空间，查问复杂度为O(1)效率高，其余操作复杂度为O(N)；

双向链表， 在内存上能够为非间断、非程序空间，通过额定的指针开销前驱/后驱指针串联元素之间的程序。

其特点为节插入/更新数据复杂度为O(1)效率高，查问复杂度为O(N)；

Hash哈希表

哈希表，其实相似是一个数组，数组的每个元素称为一个哈希桶，每个哈希桶中保留了键值对数据，且哈希桶中的元素应用dictEntry构造，

因而，哈希桶元素保留的并不是键值对值自身，而是指向具体值的指针，所以在保留每个键值对的时候会额定空间开销，至多有减少24个字节，特地是Value为String的键值对，每一个键值对就须要额定开销24个字节空间。当保留数据小，额定开销比数据还大时，这时为了节俭空间，思考换数据结构。

那来看看全局哈希表全图：

尽管哈希表操作很快，但Redis数据变大后，就会呈现一个潜在的危险：哈希表的抵触问题和 rehash开销问题，这能够解释为什么哈希表操作变慢了？

当往哈希表中写入更多数据时，哈希抵触是不可避免的问题 ， Redis 解决哈希抵触的形式，就是链式哈希，同一个哈希桶中的多个元素用一个链表来保留，它们之间顺次用指针连贯，如图所示：

当哈希抵触也会越来越多，这就会导致某些哈希抵触链过长，进而导致这个链上的元素查找耗时长，效率升高。

为了解决哈希抵触带了的链过长的问题，进行rehash操作，减少现有的哈希桶数量，扩散单桶元素数量。那么rehash过程怎么样执行的呢？

Rehash

为了使rehash 操作更高效，应用两个全局哈希表：哈希表 1 和哈希表 2，具体如下：

  • 将哈希表 2 调配更大的空间，
  • 把哈希表 1 中的数据从新映射并拷贝到哈希表 2 中；
  • 开释哈希表 1 的空间

但因为表1和表2在从新映射复制时数据大，如果一次性把哈希表 1 中的数据都迁徙完，会造成 Redis 线程阻塞，无奈服务其余申请。

为了防止这个问题，保障Redis能失常解决客户端申请，Redis 采纳了渐进式 rehash。

每解决一个申请时，从哈希表 1 中顺次将索引地位上的所有 entries 拷贝到哈希表 2 中，把一次性大量拷贝的开销，摊派到了屡次解决申请的过程中，防止了耗时操作，保障了数据的快速访问。

在了解完Hash哈希表相干知识点后，看看不常见的压缩列表和跳表。

压缩列表与跳表

压缩列表，在数组根底上，在压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，别离示意列表长度、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，示意列表完结。

长处：内存紧凑节俭内存空间，内存中调配一块地址间断的空间，数据元素会挨着寄存，不须要额定指针带来空间开销；查找定位第一个元素和最初一个元素，能够通过表头三个字段的长度间接定位，复杂度是 O(1)。

跳表 ，在链表的根底上，减少了多级索引，通过索引地位的几个跳转，实现数据的疾速定位，如下图所示：

比方查问33

特点：当数据量很大时，跳表的查找复杂度为O(logN)。

综上所述，能够得悉底层数据结构的工夫复杂度：

数据结构类型工夫复杂度
哈希表O(1)
整数数组O(N)
双向链表O(N)
压缩列表O(N)
跳表O(logN)

Redis自定义的对象零碎类型即为Redis的Value的数据类型，Redis的数据类型是基于底层数据结构实现的，那数据类型有哪些呢？

Redis数据类型

String、List、Hash、Sorted Set、Set比拟常见的类型，其与底层数据结构对应关系如下：

数据类型数据结构
StringSDS(简略动静字符串)
List双向链表
压缩列表
Hash压缩列表<br/>哈希表
Sorted Set压缩列表<br/>跳表
Set哈希表<br/>整数数组

数据类型对应特点跟其实现的底层数据结构差不多，性质也是一样的,且

String，基于SDS实现，实用于简略key-value存储、setnx key value实现分布式锁、计数器(原子性)、分布式全局惟一ID。

List， 依照元素进入List 的程序进行排序的，遵循FIFO(先进先出)规定，个别应用在 排序统计以及简略的音讯队列。

Hash， 是字符串key和字符串value之间的映射，非常适宜用来示意一个对象信息 ，特点增加和删除操作复杂度都是O(1)。

Set，是String 类型元素的无序汇合，汇合成员是惟一的，这就意味着汇合中不能呈现反复的数据。 基于哈希表实现的，所以增加，删除，查找的复杂度都是 O(1)。

Sorted Set， 是Set的类型的降级， 不同的是每个元素都会关联一个 double 类型的分数，通过分数排序，能够范畴查问。

那咱们再来看看这些数据类型，Redis Geo、HyperLogLog、BitMap？

Redis Geo， 将地球看作为近似为球体，基于GeoHash 将二维的经纬度转换成字符串，来实现地位的划分跟指定间隔的查问。特点个别应用在跟地位无关的利用。

HyperLogLog， 是一种概率数据结构，它应用概率算法来统计汇合的近似基数 ， 错误率大略在0.81%。 当汇合元素数量十分多时，它计算基数所需的空间总是固定的，而且还很小，适宜应用做 UV 统计。

BitMap ，用一个比特位来映射某个元素的状态， 只有 0 和 1 两种状态，十分典型的二值状态，且其自身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型 ，劣势大量节俭内存空间，可是应用在二值统计场景。

在了解上述常识后，咱们接下来讨论一下依据哪些策略抉择绝对应的利用场景下的Redis数据类型？

抉择适合的Redis数据类型策略

在理论开发利用中，Redis能够实用于泛滥的业务场景，但咱们须要怎么抉择数据类型存储呢？

次要根据就是工夫/空间复杂度，在理论的开发中能够思考以下几个点：

  • 数据量，数据自身大小
  • 汇合类型统计模式
  • 反对单点查问/范畴查问
  • 非凡应用场景

数据量，数据自身大小

当数据量比拟大，数据自身比拟小，应用String就会应用额定的空间大大增加，因为应用哈希表保留键值对，应用dictEntry构造保留，会导致保留每个键值对时额定保留dictEntry的三个指针的开销，这样就会导致数据自身小于额定空间开销，最终会导致存储空间数据大小远大于本来数据存储大小。

能够应用基于整数数组和压缩列表实现了 List、Hash 和 Sorted Set ，因为整数数组和压缩列表在内存中都是调配一块地址间断的空间，而后把汇合中的元素一个接一个地放在这块空间内，十分紧凑，不必再通过额定的指针把元素串接起来，这就防止了额定指针带来的空间开销。而且采纳汇合类型时，一个 key 就对应一个汇合的数据，能保留的数据多了很多，但也只用了一个 dictEntry，这样就节俭了内存。

汇合类型统计模式

Redis汇合类型统计模式常见的有：

  • 聚合统计（ 交加、差集、并集统计 ）： 对多个汇合进行聚合计算时，能够抉择Set；
  • 排序统计（要求汇合类型能对元素保序）： Redis中List 和 Sorted Set是有序汇合，List是依照元素进入 List 的程序进行排序的，Sorted Set 能够依据元素的权重来排序；
  • 二值状态统计（ 汇合元素的取值就只有 0 和 1 两种 ）：Bitmap 自身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型 ， Bitmap通过 BITOP 按位 与、或、异或的操作后应用 BITCOUNT 统计 1 的个数。
  • 基数统计（ 统计一个汇合中不反复的元素的个数 ）：HyperLogLog 是一种用于统计基数的数据汇合类型 ，统计后果是有肯定误差的，规范误算率是 0.81% 。须要准确统计后果的话，用 Set 或 Hash 类型。

Set类型，实用统计用户/好友/关注/粉丝/感兴趣的人汇合聚合操作，比方

  • 统计手机APP每天的新增用户数
  • 两个用户的独特好友

Redis中List 和 Sorted Set是有序汇合，应用应答汇合元素排序需要 ，比方

  • 最新评论列表
  • 排行榜

Bitmap二值状态统计，实用数据量大，且能够应用二值状态示意的统计，比方：

  • 签到打卡，当天用户签到数
  • 用户周沉闷
  • 用户在线状态

HyperLogLog 是一种用于统计基数的数据汇合类型， 统计一个汇合中不反复的元素个数 ，比方

  • 统计网页的 UV ， 一个用户一天内的屡次拜访只能算作一次

反对单点查问/范畴查问

Redis中List 和 Sorted Set是有序汇合反对范畴查问，然而Hash是不反对范畴查问的

非凡应用场景

音讯队列，应用Redis作为音讯队列的实现，要音讯的根本要求音讯保序、解决反复的音讯和保障音讯可靠性，计划有如下：

  • 基于 List 的音讯队列解决方案
  • 基于 Streams 的音讯队列解决方案
基于List基于Strems
音讯保序应用LPUSH/RPOP应用XADD/XREAD
阻塞读取应用BRPOP应用XREAD block
反复音讯解决生产者自行实现全局惟一IDStreams主动生成全局惟一ID
音讯可靠性应用BRPOPLPUSH应用PENDING List主动留存音讯
实用场景音讯总量小音讯总量大，须要生产组模式读取数据

基于地位 LBS 服务，应用Redis的特定GEO数据类型实现，GEO 能够记录经纬度模式的地理位置信息，被宽泛地利用在 LBS 服务中。 比方:打车软件是怎么基于地位提供服务的。

总结

Redis之所以那么快，是因为其基于内存的数据操作和应用Hash哈希表作为索引，其效率高，速度快，而且得益于其底层数据多样化使得其能够实用于泛滥场景，不同场景中抉择适合的数据类型能够晋升其查问性能。

谢谢各位点赞，没点赞的点个赞反对反对
最初，微信搜《Ccww技术博客》观看更多文章，也欢送关注一波。