资讯详情

Redis 九种数据结构及其底层实现 持久化 缓存机制 过期键与内存淘汰 集群等相关知识

参考内容:

Redis笔记

1 Redis基础介绍

  • redis启动

    • 前台启动 ---->redis-server
    • 后台启动
      • 修改配置文件,将/opt/reids/redis.conf文件中的daemonize 的no值修改为yes,即支持后台启动
      • redis-server /opt/redis/redis.conf可以在后台启动(也可以启动)redis.conf复制到其他目录,启动时使用此路径)
  • 访问redis客户端

    • redis-cli
  • redis的关闭

    • 进入客户端后使用命令shutdown

    • 找到redis-server直接杀死线程号的线程号

  • 相关知识

  • image-20220711194531978

    • 单线程和多路IO复用
    • 支持持久化
    • 支持多种数据类型
    • 非关系数据库
  • redis相关命令

    • 键相关命令

      命令 作用
      **keys ***

2 Redis数据类型

2.0 Redis底层数据结构

2.0.1 redisObject类型

typedef struct redisObject {     unsigned type:4;  //对象数据类型     unsigned encoding:4; //对象的编码格式     unsigned lru:LRU_BITS; /* lru time (relative to server.lruclock) */     int refcount;     void *ptr; //指向真实数据 } robj; 
  • type的五种取值
    • OBJ_STRING, OBJ_LIST, OBJ_SET, OBJ_ZSET, OBJ_HASH
  • encoding的取值
    • OBJ_ENCODING_RAW: 最原生的表达方式。其实只有string使用这种类型encoding值(表示成sds)。
    • OBJ_ENCODING_INT: 表示成数字long表示。
    • OBJ_ENCODING_HT: 表示成dict。
    • OBJ_ENCODING_ZIPMAP: 这是一种旧的表达方式,不再使用。Redis 2.只有6个版本。
    • OBJ_ENCODING_LINKEDLIST: 这也是一种旧的表达方式,不再使用。
    • OBJ_ENCODING_ZIPLIST: 表示成ziplist。
    • OBJ_ENCODING_INTSET: 表示成intset。用于set数据结构。
    • OBJ_ENCODING_SKIPLIST: 表示成skiplist。用于sorted set数据结构。
    • OBJ_ENCODING_EMBSTR: 表示为特殊的嵌入式sds。
    • OBJ_ENCODING_QUICKLIST: 表示成quicklist。用于list数据结构。
  • 作用
    • 为多种数据类型提供统一表示方式。
    • 允许同一类型的数据采用不同的内部表示,从而在某些情况下尽量节省内存。
    • 支持对象共享和引用计数。当对象被共享的时候,只占用一份内存拷贝,进一步节省内存。

2.0.2 SDS(Simple Dynamic String)

  1. sds特点
    • 可以动态扩展内存
    • 采用预分配空间的方式减少内存的频繁分配
    • 二进制安全
  2. 不同的编码实现
    • type = OBJ_STRING
      • encoding = OBJ_ENCODING_RAW: string采用原生的表示方式,即用sds来表示
      • encoding = OBJ_ENCODING_EMBSTR: string采用一种特殊的嵌入式的sds来表示
      • encoding = OBJ_ENCODING_INT: string采用数字的表示方式,实际上是一个long型。
  3. 完整结构由如下两个在内存地址上前后相连的两部分组成
    • header
      • 字符串的长度(len) 表示字符串的真正长度,不包含NULL结束符
      • 最大容量(alloc) 表示字符串的最大容量,不包含最后多余的一个字节
      • flags 表示Header的类型,一共五种,固定用一个字节的第三位表示
    • 字符数组
      • 数组的长度等于最大容量+1,为了当字符串的实际长度等于最大容量时,末尾仍可以由一个字节存放NULL结束符
      • 真正的字符串数据后还有一个NULL结束符,为了和C语言中的字符串兼容

2.0.3 dict

typedef struct dictEntry { 
        
    void *key;
    union { 
        
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictType { 
        
    unsigned int (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

/* This is our hash table structure. Every dictionary has two of this as we * implement incremental rehashing, for the old to the new table. */
typedef struct dictht { 
        
    dictEntry **table;
    unsigned long size;//总是2的指数
    unsigned long sizemask;//size-1 用于将key的hash映射到对应的bucket
    unsigned long used;//已有的数据个数
} dictht;
//字典数据结构,包含两个hashtable
typedef struct dict { 
        
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;
  • 包含两个哈希表,当发生重哈希时,数据从第一个哈希表向第二个哈希表迁移

2.0.4 ziplist

  • ziplist使用一块连续的内存空间来存储数据,并采用可变长的编码方式,支持不同类型和大小的数据的存储,比较节省内存。而且数据存储在一片连续的内存空间,读取的效率也非常高。

2.0.5 quicklist

  • quicklist是一个双向链表,而且是一个基于ziplist的双向链表,quicklist的每个节点都是一个ziplist

  • ziplist长度的确定

    • 参数值大于0表示ziplist中的元素个数

    • 参数值小于0表示ziplist的内存大小

    • 通过如下的参数确定

      list-max-ziplist-size -2

2.0.6 intset

  • intset是一个由整数组成的有序集合,从而便于进行二分查找,用于快速地判断一个元素是否属于这个集合。它在内存分配上与ziplist有些类似,是连续的一整块内存空间,而且对于大整数和小整数(按绝对值)采取了不同的编码,尽量对内存的使用进行了优化

2.0.7 skiplist

  • 跳表是一种可以进行二分查找的有序链表,采用空间换时间的设计思路,跳表在原有的有序链表上面增加了多级索引(例如每两个节点就提取一个节点到上一级),通过索引来实现快速查找。跳表是一种动态数据结构,支持快速的插入、删除、查找操作,时间复杂度都为O(logn),空间复杂度为 O(n)。跳表非常灵活,可以通过改变索引构建策略,有效平衡执行效率和内存消耗。

  • 跳跃表的每个节点都生成随机的层数,插入操作只用修改系欸但前后的指针,不需要对多个节点都进行调整

  • skiplist与hashtable,AVL的比较

    • skiplist和各种平衡树(如AVL、红黑树等)的元素是有序排列的,而哈希表不是有序的。因此,在哈希表上只能做单个key的查找,不适宜做范围查找。所谓范围查找,指的是查找那些大小在指定的两个值之间的所有节点。
    • 在做范围查找的时候,平衡树比skiplist操作要复杂。在平衡树上,我们找到指定范围的小值之后,还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造,这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单,只需要在找到小值之后,对第1层链表进行若干步的遍历就可以实现。
    • 平衡树的插入和删除操作可能引发子树的调整,逻辑复杂,而skiplist的插入和删除只需要修改相邻节点的指针,操作简单又快速。
    • 从内存占用上来说,skiplist比平衡树更灵活一些。一般来说,平衡树每个节点包含2个指针(分别指向左右子树),而skiplist每个节点包含的指针数目平均为1/(1-p),具体取决于参数p的大小。如果像Redis里的实现一样,取p=1/4,那么平均每个节点包含1.33个指针,比平衡树更有优势。
    • 查找单个key,skiplist和平衡树的时间复杂度都为O(log n),大体相当;而哈希表在保持较低的哈希值冲突概率的前提下,查找时间复杂度接近O(1),性能更高一些。所以我们平常使用的各种Map或dictionary结构,大都是基于哈希表实现的。
    • 从算法实现难度上来比较,skiplist比平衡树要简单得多。
  • Redis中的跳跃表

    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
    
  • 初始化跳跃表

2.1 字符串类型(String)

2.1.1 相关命令

2.1.2 数据结构

  • type = OBJ_STRING

    • encoding = OBJ_ENCODING_RAW: string采用原生的表示方式,即用sds来表示

    • encoding = OBJ_ENCODING_EMBSTR: string采用一种特殊的嵌入式的sds来表示(专门用于短字符串,字符串长度小于等于44字节)
      • redisObject和sds的内存是连续的,只用分配一次内存,提升性能。
      • embstr编码的字符串对象是只读的,在对该类型的字符串进行修改时会改变其编码格式。
    • encoding = OBJ_ENCODING_INT: string采用数字的表示方式,实际上是一个long型。

  • String类型是二进制安全的,意味着redis的String可以包含任何类型的数据
  • 简单动态字符串(Simple Dynamical String),需要时才扩容,类似于Java中的ArrayList,1M以下增加1倍,1M以上一次增加1M,最大512M。
  • SDS保存了字符串的长度
  • SDS可以预分配空间,修改SDS时先检查SDS空间是否足够,不够会先扩展SDS的空间,防止缓存溢出。

2.1.3 应用场景

  • 缓存对象
  • 常规计数
  • 分布式锁
  • 共享session信息

2.2 列表(List)

2.2.1 相关命令

命令 作用

2.2.2 数据结构

  • 压缩链表 ziplist ,列表的元素个数小于512个,列表的每个元素的值都小于64字节,redis使用压缩列表作为List类型的底层数据结构

  • 快速链表 quicklist(宏观上是双向链表)

    • 数据少时是ziplist,元素挨着存储,分配的内存空间是连续的
      • 由表头和N个entry节点和压缩列表尾部标识符zlend组成的一个连续的内存块。然后通过一系列的编码规则,提高内存的利用率,主要用于存储整数和比较短的字符串。可以看出在插入和删除元素的时候,都需要对内存进行一次扩展或缩减,还要进行部分数据的移动操作,这样会造成更新效率低下的情况
    • 数据量较多时改为quicklist,多个ziplist使用双向指针穿起来

2.2.3 应用场景

  • 不完善的消息队列
    • 保序性:LPUSH+RPOP
    • 阻塞读取: BRPOP
    • 重复消息处理: 生产者自行实现全局唯一ID
    • 消息的可靠性:使用BRPOPLPUSH, 读取消息的同时把这条消息插入到另一个备份list中

2.3 Set

2.3.1 常用命令

2.3.2 数据结构

  • intset:集合中都是整数,且数据量不超过512个,使用intset(有序且不重复的连续空间)
  • String类型的set集合,底层是value为null的hash表,dict的结构

2.3.3 应用场景

  • 点赞
  • 共同关注
  • 抽奖活动

2.4 Hash

2.4.1 常用命令

2.4.2 数据结构

  • field : value(类似HashMap<String,Object>)
  • set数据较少:ziplist
    • 键的个数小于512,值的大小不超过64字节
  • 数据较多: hashtable

2.4.3 应用场景

  • 缓存对象
  • 购物车

2.5 有序集合Zset(sorted set)

2.5.1 常用命令

2.5.2 数据结构

  • 有序的set集合,每个元素关联一个评分(score),元素唯一,但是不同元素的score可以重复
  • ziplist
    • 键值对个数小于128,ziplist数据项小于256
    • 集合中每个数据的大小都要小于64字节
  • skiplist

2.5.3 应用场景

  • 排行榜
  • 电话,姓名排序

2.6 Bitmaps

2.6.1 相关命令

常用命令 作用
SETBIT key offset value 向指定位置存入0或者1
GETBIT key offset 获取指定位置的bit
BITCOUNT key [start end] 获取指定范围内1的个数
BITFIELD key [GET type offset] [SET type offset value] [INCRBY type offset increment] 操作指定位置的bit type指定符号数(u为无符号,i为有符号)
BITPOS key bit [start] [end] 获取指定范围内第一个出现的1

2.6.2 数据结构

  • 基于String类型作为底层数据结构实现的一种统计二值状态的数据类型,可以看作是一个bit数组

2.6.3 应用场景

  • 签到统计
  • 判断用户的登录状态
  • 连续签到的用户总数

2.7 HyperLogLog(基数计算)

  • **:U**nique isitor,也叫独立访客量,是指通过互联网访问、浏览这个网页的自然人。1天内同一个用户多次访问该网站,只记录1次。

  • **:P**age iew,也叫页面访问量或点击量,用户每访问网站的一个页面,记录1次PV,用户多次打开页面,则记录多次PV。往往用来衡量网站的流量。

  • HyperLogLog通常用于基数统计。使用少量固定大小的内存,来统计集合中唯一元素的数量。统计结果不是精确值,而是一个带有0.81%标准差(standard error)的近似值。所以,HyperLogLog适用于一些对于统计结果精确度要求不是特别高的场景,例如网站的UV统计。

常用命令 作用
PFADD key element… 添加数据到HyperLogLog
PFCOUNT key 统计HyperLogLog中的个数,有一定的误差
PFMERGE destkey sourcekey… 将多个HyperLogLog合并为一个

2.9 Geospatial(地理信息,经纬度)

常用命令 作用
GEOADD key longitude latitude member 添加一个或者多个位置的经纬度信息到某个集合
GEODIST key member1 member2 [m|km] 返回集合中两个位置的距离
GEOHASH key member … 返回某个位置的hash
GEOPOS key member … 返回某个位置的经纬度信息
GEOSERACH key [FROMMEMBER member] [FROMLONLAT longitude latitude] [BYRADIUS radius m|km] [ASC|DESC] [COUNT count [ANY]] [WITHCOORD] [WITHDIST] [WITHHASH] 在指定范围内搜索member,并按照与指定点之间的距离排序后返回。范围可以是圆形或矩形

2.10 Stream

  • 基于Stream可以实现一个相对完善的消息队列

  • 常用命令

    • 发送消息

    • 读取消息

  • 消费者组:将多个消费者放到一个组里,监控同一个队列

    • :队列中的消息会分流给组内的不同消费者,而不是重复消费,从而加快消息处理的速度
    • :消费者组会维护一个标示,记录最后一个被处理的消息,哪怕消费者宕机重启,还会从标示之后读取消息。确保每一个消息都会被消费
    • :消费者获取消息后,消息处于pending状态,并存入一个pending-list。当处理完成后需要通过XACK来确认消息,标记消息为已处理,才会从pending-list移除。
    消费者组命令 作用
    XGROUP CREATE key groupname ID|$ [MKSTREAM] 创建消费者组
    ID指定队列中消息位置,0表示第一个,$表示最后一个
    XGROUP DESTORY key groupName 删除指定的消费者组
    XGROUP CREATECONSUMER key groupname consumername 给指定的消费者组添加消费者
    XGROUP DELCONSUMER key groupname consumername 删除消费者组中的指定消费者
  • 读取队列中的消息

    • group:消费组名称

    • consumer:消费者名称,如果消费者不存在,会自动创建一个消费者

    • count:本次查询的最大数量

    • BLOCK milliseconds:当没有消息时最长等待时间

    • NOACK:无需手动ACK,获取到消息后自动确认

    • STREAMS key:指定队列名称

    • ID:获取消息的起始ID:

      • “>”:从下一个未消费的消息开始

      • 其它:根据指定id从pending-list中获取已消费但未确认的消息,例如0,是从pending-list中的第一个消息开始

  • 确认已经处理过的消息

3 Redis客户端

3.1 Jedis

package com.lzx;

import redis.clients.jedis.Jedis;

public class JedisTest { 
        
    public static void main(String[] args) { 
        
        Jedis jedis = new Jedis("192.168.248.131", 6379);
        String result = jedis.ping();
        System.out.println(result);
        jedis.close();
    }
}

3.2 Spring Data Redis

锐单商城 - 一站式电子元器件采购平台