锐单电子商城 , 一站式电子元器件采购平台!
  • 电话:400-990-0325

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

时间:2023-07-03 04:07:00 ht2088变送器

参考内容:

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 *** 查看当前数据库中的所有键
      set key value 添加键值
      exists key 判断某个key是否存在
      type key 查看key的类型
      del key 删除指定的key数据
      unlink key 根据value选择非阻塞删除
      expire key seconds 给指定的Key设置过期时间
      ttl key 查看当前key还有多少秒过期,-1表示永远不会过期,-2表示已经过期
      select nums 切换数据库,redis默认有16个数据库,默认使用0号数据库
      dbsize 查看当前数据库key的数量
      flushdb 清空当前库
      flushall 清空所有库

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 相关命令

命令 作用
set key value 添加键值对
get key 查询对应键的值
append key value 将给定的value追加到原value的末尾
strlen key 获取当前键的值的长度
setnx key value 当key不存在时,设置key的值
incr key 将键值增加1,只能对数字值进行操作,若当前key不存在则将Key的值设为1
decr key 将键值减少1,只能对数字值进行操作,若当前key不存在则将Key的值设为-1
incrby / decrby key step 与incr和decr一致,可以自定义步长 step
mset key1 value1 key2 value2 … 同时设置一个或者多个键值对
mget key1 key2… 同时获取多个value
msetnx key1 value1 key2 value2… 同时设置一个或者多个键值对,当且仅当所有的Key都不存在时才会设置
getrange key start end 获取值的范围,与java中的substring类似,前后都是闭包
setrange key start value 用value的值覆盖从start开始的值,有几位覆盖几位
setex key seconds value 设置键值的同时设置过期时间
getset key value 得到旧的值,同时用value替换原有的值

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 相关命令

命令 作用
lpush/rpush key1 value1 key2 value2 从左边/右边插入一个或者多个值
lpop/rpop key 从左边或者右边弹出一个值,值在键在,值光键亡
lrange key start stop 按照索引下标获得元素,从左到右,0表示左边第一个,-1表示右边第一个
lindex key index 根据index的值获取元素(从左到右)
llen key 获取链表的长度
linsert key before/after value newvalue 在value的前面或者后面插入newvalue
lrem key n value 从左边删除n个指定的value
lset key index value 将index处的值替换为value

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 常用命令

命令 作用
SADD key member 向set中添加一个或多个元素
SISMEMBER key member 判断一个元素是否存在于set中
SREM key member 移除set中的指定元素
SCARD key 返回set中元素的个数
SMEMBERS 获取set中的所有元素
SINTER key1 key2 求key1与key2的交集
SDIFF key1 key2 求key1与key2的差集
SUNION key1 key2 求key1和key2的并集

2.3.2 数据结构

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

2.3.3 应用场景

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

2.4 Hash

2.4.1 常用命令

命令 作用
HSET key field value 添加或者修改hash类型key的filed的值
HGET key field 获取一个hash类型的key的field的值
HMSET key field value [field value …] 设置一个hash类型的key的多个field的值
HMGET key field [field …] 获取一个hash类型的key的多个field的值
HGETALL key 获取一个hash类型的key的所有field和value
HKEYS key 获取一个hash类型的key的所有field
HVALS key 获取一个hash类型的key的所有value
HSETNX key field value 设置filed-value,不存在就设置,存在则无效

2.4.2 数据结构

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

2.4.3 应用场景

  • 缓存对象
  • 购物车

2.5 有序集合Zset(sorted set)

2.5.1 常用命令

命令 作用
ZADD key score member 添加一个或多个元素到sorted set ,如果已经存在则更新其score值
ZREM key member 删除sorted set中的一个指定元素
ZSCORE key member 获取sorted set中的指定元素的score值
ZRANK key member 获取sorted set 中的指定元素的排名
ZCARD key 获取sorted set中的元素个数
ZCOUNT key min max 统计score值在给定范围内的所有元素的个数
ZINCRBY key increment member 让sorted set中的指定元素自增,步长为指定的increment值
ZRANGE key min max 按照score排序后,获取指定排名范围内的元素
ZRANGEBYSCORE key min max 按照score排序后,获取指定score范围内的元素
ZDIFF、ZINTER、ZUNION 求差集、交集、并集

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(基数计算)

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

  • PV**:全称P**age View,也叫页面访问量或点击量,用户每访问网站的一个页面,记录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

相关文章