Overview_java

初识

官网介绍

​ Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache and message broker.

​ It supports data structures such as strings, hashes, lists, sets, sorted sets with range queries, bitmaps, hyperloglogs, geospatial indexes with radius queries and streams.

​ Redis has built-in replication, Lua scripting, LRU eviction, transactions and different levels of on-disk persistence, and provides high availability via Redis Sentinel and automatic partitioning with Redis Cluster

简单翻译下

​ 内存数据结构存储 ,被当成数据库、缓存、消息代理使用

​ 支持的数据结构,字符串 、哈希、列表、集合等

​ 副本集(主从复制)、Lua脚本、LRU淘汰策略(Least Recently Used、Least Frequently Used)、事务(不可回滚)、不同级别的磁盘持久、用Sentinel保证高可用、用集群来自动分区

​

单线程 、简单、高性能的key-value数据库

Redis 的特性:
1)更丰富的数据类型

2)进程内与跨进程;单机与分布式

3)功能丰富:持久化机制、过期策略

4)支持多种编程语言

5)高可用，集群

版本特征

1.Redis2.6

Redis2.6在2012年正式发布，相对于Redis2.4，主要特性如下：

• 支持Lua脚本
• 键的过期时间支持毫秒
• 从节点支持只读功能

2.Redis2.8

Redis2.8在2013年11月22日正式发布，相比于Redis2.6，主要特性如下：

• PSYNC 添加部分主从复制的功能
• Redis Sentinel生产可用
• 新增命令：SCAN、SSCAN、HSCAN和ZSCAN

3.Redis3.0（里程碑）

Redis3.0在2015年4月1日正式发布，相比于Redis2.8主要特性如下：

• Redis Cluster：Redis的官方分布式实现。
• 全新的embedded string对象编码结果，优化小对象内存访问，在特定的工作负载下载速度大幅提升

4.Redis3.2

Redis3.2在2016年5月6日正式发布，相比于Redis3.0主要特征如下：

• 新的List编码类型：quicklist。

5.Redis4.0

Redis4.0在2016年底正式发布，相比于Redis3.2主要特征如下： http://antirez.com/news/110

• 模块化
• PSYNC2.0：优化了之前版本中，主从节点切换必然引起全量复制的问题。
• 提供了新的缓存剔除算法：LFU（Last Frequently Used），并对已有算法进行了优化。
• 提供了非阻塞del和flushall/flushdb功能，有效解决删除了bigkey可能造成的Redis阻塞。
• 提供了RDB-AOF混合持久化格式，充分利用了AOF和RDB各自优势。

6.Redis5.0

Redis5.0在2018年5月正式发布相比于Redis4.0主要特征如下：

• Stream data type

more: https://raw.githubusercontent.com/antirez/redis/5.0/00-RELEASENOTES

数据结构

String

​ Redis 的字符串是动态字符串，是可以修改的字符串，内部结构实现上类似于 Java 的 ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配。 当字符串长度小于 1M 时，扩容都是加倍现有的空间，如果超过 1M，扩容时一次只会多扩 1M 的空间。需要注意的是字符串最大长度为 512M。

存储(实现)原理

数据模型

/*dict.h*/
typedef struct dictEntry {
    void *key; /* key 关键字定义 */
    union {
        void *val; uint64_t u64; /* value 定义 */
    int64_t s64; double d;
    } v;
    struct dictEntry *next; /* 指向下一个键值对节点 */
} dictEntry;

以set hello world 为例子

key 是字符串，但是 Redis 没有直接使用 C 的字符数组，而是存储在自定义的 SDS 中。

value 既不是直接作为字符串存储，也不是直接存储在 SDS 中，而是存储在 redisObject 中。实际上五种常用的数据类型的任何一种，都是通过 redisObject 来存储 的。

redisObject

/* server.h */
typedef struct redisObject {
    unsigned type:4; /* 对象的类型，包括:OBJ_STRING、OBJ_LIST、OBJ_HASH、OBJ_SET、OBJ_ZSET */ 			                       	 unsigned encoding:4; /* 具体的数据结构 */
    unsigned lru:LRU_BITS; /* 24 位，对象最后一次被命令程序访问的时间，与内存回收有关 */
    int refcount; /* 引用计数。当refcount为0的时候，表示该对象不被任何对象引用，可以进行垃圾回收了*/
    void *ptr; /* 指向对象实际的数据结构 */
} robj;

可以使用 type 命令来查看对外的类型。

可以使用 object encoding 来查看具体的数据结构。

内部编码

字符串类型的内部编码有三种:
1、int，存储 8 个字节的长整型(long，2^63-1)。
2、embstr, 代表 embstr 格式的 SDS(Simple Dynamic String 简单动态字符串)，

存储小于 44 个字节的字符串。
3、raw，存储大于 44 个字节的字符串(3.2 版本之前是 39 字节)

问题 1、什么是 SDS? Redis 中字符串的实现?

​ 在 3.2 以后的版本中，SDS 又有多种结构(sds.h): sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64，用于存储不同的长度的字符串，分别代表 2^5=32byte， 2^8=256byte，2^16=65536byte=64KB，2^32byte=4GB。

/* sds.h */
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 当前字符数组的长度 */
    uint8_t alloc; /*当前字符数组总共分配的内存大小 */
    unsigned char flags; /* 当前字符数组的属性、用来标识到底是 sdshdr8 还是 sdshdr16 等 */ 
    char buf[]; /* 字符串真正的值 */
};

问题 2、为什么 Redis 要用 SDS 实现字符串?

C 字符串	SDS
获取字符串长度的复杂度为 O(N)	获取字符串长度的复杂度为 O(1)
API 是不安全的，可能会造成缓冲区溢出	API 是安全的，不会造成缓冲区溢出
修改字符串长度 N 次必然需要执行 N 次内存重分配	修改字符串长度 N 次最多需要执行 N 次内存重分配
只能保存文本数据	可以保存文本或者二进制数据
可以使用所有<string.h>库中的函数	可以使用一部分<string.h>库中的函数

问题 3、embstr 和 raw 的区别?

​ embstr 的使用只分配一次内存空间(因为 RedisObject 和 SDS 是连续的,只读)，而 raw 需要分配两次内存空间(分别为 RedisObject 和 SDS 分配空间)。

问题 4、int 和 embstr 什么时候转化为 raw?

​ 当int数据不再是整数，或大小超过了 long 的范围 (2^63-1=9223372036854775807)时，自动转化为 raw

​ 对于 embstr，由于其实现是只读的，因此在对 embstr对象进行修改时，都会先转化为raw 再进行修改。

应用场景

缓存

数据共享分布式

分布式锁

​ STRING 类型 setnx 方法，只有不存在时才能添加成功，返回 true。

全局 ID

​ INT 类型，INCRBY，利用原子性

计数器

​ INT 类型，INCR 方法

限流

​ INT 类型，INCR 方法

位统计

​ bit count

Hash

​ Redis 的字典相当于 Java 语言里面的 HashMap，它是无序字典。不同的是，Redis 的字典的值只能是字符串，另外它们 rehash 的方式不一样，因为 Java 的 HashMap 在字典很大时，rehash 是个耗时的操作，需要一次性全部 rehash(在concurrentHashMap中也是渐进式,而且是多线程)。

Redis 为了高性能，不能堵塞服务，所以采用了渐进式 rehash 策略。(操作的时候会触发rehash,同时后台会有个定时任务在执行)

​ 相比字符串 ,可以进行部分获取,减少网络传输. 但hash 结构的存储消耗要高于单个字符串.

存储(实现)原理

​ 外层的哈希(Redis KV 的实现)只用到了 hashtable。当存储 hash 数据类型时， 我们把它叫做内层的哈希。

内层的哈希底层可以使用两种数据结构实现:

ziplist:OBJ_ENCODING_ZIPLIST(压缩列表)

hashtable:OBJ_ENCODING_HT(哈希表)

ziplist 压缩列表

ziplist 是一个经过特殊编码的双向链表，它不存储指向上一个链表节点和指向下一个链表节点的指针，而是存储上一个节点长度和当前节点长度，通过牺牲部分读写性能， 来换取高效的内存空间利用率，是一种时间换空间的思想。只用在字段个数少，字段值 小的场景里面。

内部结构

typedef struct zlentry {
    unsigned int prevrawlensize; 	/* 上一个链表节点占用的长度 */
    unsigned int prevrawlen; 			/* 存储上一个链表节点的长度数值所需要的字节数 */ 
    unsigned int lensize; 				/* 存储当前链表节点长度数值所需要的字节数 */
    unsigned int len; 						/* 当前链表节点占用的长度 */
    unsigned int headersize; /* 当前链表节点的头部大小(prevrawlensize + lensize)，即非数据域的大小 */
    unsigned char encoding;  /* 编码方式 */
    unsigned char *p; /* 压缩链表以字符串的形式保存，该指针指向当前节点起始位置 */
} zlentry;

编码 encoding(ziplist.c 源码第 204 行)

#define ZIP_STR_06B (0 << 6) //长度小于等于 63 字节
#define ZIP_STR_14B (1 << 6) //长度小于等于 16383 字节 
#define ZIP_STR_32B (2 << 6) //长度小于等于 4294967295 字节

什么时候使用?

当 hash 对象同时满足以下两个条件的时候，使用 ziplist 编码:

1)所有的键值对的健和值的字符串长度都小于等于 64byte(一个英文字母一个字节);

2)哈希对象保存的键值对数量小于 512 个。

hashtable(dict)

在 Redis 中，hashtable 被称为字典(dictionary)，它是一个数组+链表的结构。

dictht

/* 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; /* 哈希表大小 */
    unsigned long sizemask; /* 掩码大小，用于计算索引值。总是等于 size-1 */ 
    unsigned long used; /* 已有节点数 */
} dictht;

dict

typedef struct dict {
    dictType *type; /* 字典类型 */
    void *privdata; /* 私有数据 */
    dictht ht[2]; /* 一个字典有两个哈希表 */
    long rehashidx; /* rehash 索引 */
    unsigned long iterators; /* 当前正在使用的迭代器数量 */
} dict;

rehash

步骤:
1、为字符 ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0]当前包含的键值对的数量。
扩展:ht[1]的大小为第一个大于等于 ht[0].used*2。
2、将所有的 ht[0]上的节点 rehash 到 ht[1]上，重新计算 hash 值和索引，然后放入指定的位置。
3、当 ht[0]全部迁移到了 ht[1]之后，释放 ht[0]的空间，将 ht[1]设置为 ht[0]表，并创建新的 ht[1]，为下次 rehash 做准备

https://blog.csdn.net/wangmaohong0717/article/details/84611426

http://redisbook.com/preview/dict/incremental_rehashing.html

扩容缩容?

负载因子

static int dict_can_resize = 1;
static unsigned int dict_force_resize_ratio = 5;

ratio = used / size，已使用节点与字典大小的比例

dict_can_resize 为 1 并且 dict_force_resize_ratio 已使用节点数和字典大小之间的 比率超过 1:5，触发扩容

应用场景

string

存储对象类型的数据

购物车

List

​ Redis 的列表相当于 Java 语言里面的 LinkedList，注意它是链表而不是数组。这意味着 list 的插入和删除操作非常快，时间复杂度为 O(1)，但是索引定位很慢，时间复杂度为 O(n)，这点让人非常意外。 常用于异步队列。

​

在列表元素较少的情况下会使用一块连续的内存存储，这个结构是 ziplist，也即是压缩列表。

当数据量比较多的时候才会改成 quicklist。因为普通的链表需要的附加指针空间太大，会比较浪费空间，而且会加重内存的碎片化。

比如这个列表里存的只是 int 类型的数据，结构上还需要两个额外的指针 prev 和 next 。

所以 Redis 将链表和 ziplist 结合起来组成了 quicklist。也就是将多个 ziplist 使用双向指针串起来使用。这样既满足了快速的插入删除性能，又不会出现太大的空间冗余。

存储(实现)原理

在早期的版本中，数据量较小时用 ziplist 存储，达到临界值时转换为 linkedlist 进 行存储，分别对应 OBJ_ENCODING_ZIPLIST 和 OBJ_ENCODING_LINKEDLIST 。

3.2 版本之后，统一用 quicklist 来存储。quicklist 存储了一个双向链表，每个节点 都是一个 ziplist。

quicklist

quicklist(快速列表)是 ziplist 和 linkedlist 的结合体。

typedef struct quicklist {
    quicklistNode *head; /* 指向双向列表的表头 */ 
    quicklistNode *tail; /* 指向双向列表的表尾 */
    unsigned long count; /* 所有的 ziplist 中一共存了多少个元素 */ 
    unsigned long len;	/* 双向链表的长度，node 的数量 */
    int fill : 16; /* fill factor for individual nodes */
    unsigned int compress : 16;  /* 压缩深度，0:不压缩; */
} quicklist;	

quicklistNode

quicklistNode 中的*zl 指向一个 ziplist，一个 ziplist 可以存放多个元素。

typedef struct quicklistNode {
    struct quicklistNode *prev; /* 前一个节点 */
    struct quicklistNode *next; /* 后一个节点 */
    unsigned char *zl; /* 指向实际的 ziplist */
    unsigned int sz; /* 当前 ziplist 占用多少字节 */
    unsignedintcount:16;/* 当前ziplist中存储了多少个元素，占16bit(下同)，最大65536个*/ unsigned int   	 encoding : 2; /* 是否采用了 LZF 压缩算法压缩节点，1:RAW 2:LZF */
    unsigned int   container : 2; /* 2:ziplist，未来可能支持其他结构存储 */
    unsigned int   recompress : 1; /* 当前 ziplist 是不是已经被解压出来作临时使用 */
    unsigned int   attempted_compress : 1; /* 测试用 */
    unsigned int   extra : 10; /* 预留给未来使用 */
} quicklistNode;

应用场景

用户消息时间线 timeline

消息队列

Set

​ Redis 的集合相当于 Java 语言里面的 HashSet，它内部的键值对是无序的唯一的。它的内部实现相当于一个特殊的字典，字典中所有的 value 都是一个值NULL。

存储(实现)原理

​ Redis 用 intset 或 hashtable 存储 set。

如果元素都是整数类型，就用 inset 存储。

如果不是整数类型，就用 hashtable(数组+链表的存来储结构)。

应用场景

抽奖

​ 随机获取元素 spop myset

点赞、签到、打卡

​ 这条微博的 ID 是 t1001，用户 ID 是 u3001。

​ 用 like:t1001 来维护 t1001 这条微博的所有点赞用户。

​ 点赞了这条微博:sadd like:t1001 u3001

​ 取消点赞:srem like:t1001 u3001

​ 是否点赞:sismember like:t1001 u3001

​ 点赞的所有用户:smembers like:t1001

​ 点赞数:scard like:t1001

商品标签

用 tags:i5001 来维护商品所有的标签。

sadd tags:i5001 画面清晰细腻 sadd tags:i5001 真彩清晰显示屏 sadd tags:i5001 流畅至极

商品筛选

​ 获取差集

​ sdiff set1 set2

​ 获取交集(intersection )

​ sinter set1 set2
获取并集
​ sunion set1 set2

sadd brand:apple iPhone11
sadd brand:ios iPhone11
sad screensize:6.0-6.24 iPhone11 sad screentype:lcd iPhone11

筛选商品，苹果的，iOS 的，屏幕在 6.0-6.24 之间的，屏幕材质是 LCD 屏幕

​ sinter brand:apple brand:ios screensize:6.0-6.24 screentype:lcd

用户关注、推荐模型

思考

1)相互关注? 2)我关注的人也关注了他? 3)可能认识的人?

Zset

​ zset 可能是 Redis 提供的最为特色的数据结构。它类似于 Java 的 SortedSet 和 HashMap 的结合体，一方面它是一个 set，保证了内部 value 的唯一性，另一方面它可以给每个 value 赋予一个 score，代表这个 value 的排序权重。

​ 我们需要这个链表按照 score 值进行排序。这意味着当有新元素需要插入时，要定位到特定位置的插入点，这样才可以继续保证链表是有序的。通常我们会通过二分查找来找到插入点，但是二分查找的对象必须是数组，所以 它的内部实现用的是一种叫做「跳跃列表」的数据结构。

数据结构对比:

数据结构	是否允许重复元素	是否有序	有序实现方式
列表 list	是	是	索引下标
集合 set	否	否	无
有序集合 zset	否	是	分值 score

存储(实现)原理

同时满足以下条件时使用 ziplist 编码:
元素数量小于 128 个
所有 member 的长度都小于 64 字节

超过阈值之后，使用 skiplist+dict 存储。

什么是 skiplist?

二分查找法只适用于有序数组，不适用于链表。所以为了解决这个问题

插入一个数据的时候，决定要放到那一层，取决于一个算法 ,zslRandomLevel

/* t_zset.c */
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
    level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

为什么不用 AVL 树或者红黑树?因为 skiplist 更加简洁。

typedef struct zskiplistNode {
    sds ele; /* zset 的元素 */
    double score; /* 分值 */
    struct zskiplistNode *backward; /* 后退指针 */ 
  
  struct zskiplistLevel {
        struct zskiplistNode *forward; /* 前进指针，对应 level 的下一个节点 */
        unsigned long span; /* 从当前节点到下一个节点的跨度(跨越的节点数) */ 
  } 
  level[]; /* 层 */
} zskiplistNode; 

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; /* 指向跳跃表的头结点和尾节点 */ 
  unsigned long length; /* 跳跃表的节点数 */
    int level; /* 最大的层数 */
} zskiplist; 

typedef struct zset {
    dict *dict;
    zskiplist *zsl; 
} zset;

结构图

应用场景

排行榜

其他数据结构

BitMaps

Bitmaps 是在字符串类型上面定义的位操作。一个字节由 8 个二进制位组成。

应用场景:
用户访问统计
在线用户统计

Hyperloglogs

Hyperloglogs:提供了一种不太准确的基数统计方法，比如统计网站的 UV，存在 一定的误差

Streams

5.0 推出的数据类型。支持多播的可持久化的消息队列，用于实现发布订阅功能，借 鉴了 kafka 的设计。

总结

数据结构总结

编码转换总结

使用

• 管道（Pipelining）

  一次发送多个命令，可以包含Batch命令,节省往返时间。

• 淘汰策略 LRU LFU

  Least Recently Used 按照访问时间 这个可以用LinkHashMap 简单实现
  Least Frequently Used 按照访问次数 需要额外的队列记录访问频率

• Batch 命令

  批量相同指令

• 事务

  Redis 事务保证了其中的一致性（C）和隔离性（I），但并不保证原子性（A）和持久性（D）。

• 分布式锁

  Lua脚本实现原子性

• TTL 过期删除

  惰性、异步 删除, 注意过期时间要采用 一个常量加一个随机时间戳 防止大批量的key同一时间过期

发布订阅

传统list队列局限

1、如果生产者生产消息的速度远大于消费者消费消息的速度，List 会占用大量的内 存。

2、消息的实时性降低。

基于 list 实现的消息队列，不支持一对多的消息分发。

发布订阅模式

订阅频道

​ 我们有很多的频道(channel)，我们也可以把这个频道理解成 queue。订 阅者可以订阅一个或者多个频道。消息的发布者(生产者)可以给指定的频道发

订阅

​ subscribe channel-1 channel-2 channel-3

发布

​ publish channel-1 2673

按规则(Pattern)订阅频道

支持?和占位符。?代表一个字符，代表 0 个或者多个字符。

Redis事务

Redis 的事务有两个特点:

1、按进入队列的顺序执行。

2、不会受到其他客户端的请求的影响。

Redis 的事务涉及到四个命令:multi(开启事务)，exec(执行事务)，discard (取消事务)，watch(监视)

watch命令

它可以为 Redis 事务提供 CAS 乐观锁行为(Check and Set / Compare and Swap)

我们可以用 watch 监视一个或者多个 key，如果开启事务之后，至少有一个被监视 key 键在 exec 执行之前被修改了， 那么整个事务都会被取消(key 提前过期除外)。可 以用 unwatch 取消。

事务可能遇到的问题

在执行 exec 之前发生错误

比如:入队的命令存在语法错误，包括参数数量，参数名等等(编译器错误)。

在这种情况下事务会被拒绝执行，也就是队列中所有的命令都不会得到执行。

在执行 exec 之后发生错误

比如，类型错误，比如对 String 使用了 Hash 的命令，这是一种运行时错误。

为什么在一个事务中存在错误，Redis 不回滚?

• Redis 命令只会因为错误的语法而失败（并且这些问题不能在入队时发现），或是命令用在了错误类型的键上面：这也就是说，从实用性的角度来说，失败的命令是由编程错误造成的，而这些错误应该在开发的过程中被发现，而不应该出现在生产环境中。
• 因为不需要对回滚进行支持，所以 Redis 的内部可以保持简单且快速。

Lua脚本

Lua/ˈluə/是一种轻量级脚本语言，它是用 C 语言编写的，跟数据的存储过程有点类 似。 使用 Lua 脚本来执行 Redis 命令的好处:

1、一次发送多个命令，减少网络开销。

2、Redis 会将整个脚本作为一个整体执行，不会被其他请求打断，保持原子性。

3、对于复杂的组合命令，我们可以放在文件中，可以实现程序之间的命令集复用。

Lua应用

分布式锁

限流

管理

持久化

• 快照RDB

  全量备份

• AOF 指令

  • 1条指令执行一次刷盘
  • 1段时间执行一次刷盘
  • 1s执行一次刷盘

• RDB快照 +AOF同步

​

集群

​ 高可用 主从同步(RDB快照 +AOF同步) 、raft 一致性算法 、gossip 通信协议

​ 高性能 读写分离

​ 分片 横向扩展 算法槽

https://redis.io/topics/cluster-spec

参考:

redis深度历险

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 951488791@qq.com