转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!

看到很多小伙伴简历上写了“熟练使用缓存”，但是被我问到“缓存常用的3种读写策略”的时候却一脸懵逼。

在我看来，造成这个问题的原因是我们在学习 Redis 的时候，可能只是简单了写一些 Demo，并没有去关注缓存的读写策略，或者说压根不知道这回事。

但是，搞懂3种常见的缓存读写策略对于实际工作中使用缓存以及面试中被问到缓存都是非常有帮助的！

下面介绍到的三种模式各有优劣，不存在最佳模式，根据具体的业务场景选择适合自己的缓存读写模式。

Cache Aside Pattern（旁路缓存模式）#

Cache Aside Pattern 是我们平时使用比较多的一个缓存读写模式，比较适合读请求比较多的场景。

Cache Aside Pattern 中服务端需要同时维系 db 和 cache，并且是以 db 的结果为准。

下面我们来看一下这个策略模式下的缓存读写步骤。

写 ：

• 先更新 db
• 然后直接删除 cache 。

简单画了一张图帮助大家理解写的步骤。

读 :

• 从 cache 中读取数据，读取到就直接返回
• cache 中读取不到的话，就从 db 中读取数据返回
• 再把数据放到 cache 中。

简单画了一张图帮助大家理解读的步骤。

你仅仅了解了上面这些内容的话是远远不够的，我们还要搞懂其中的原理。

比如说面试官很可能会追问：“在写数据的过程中，可以先删除 cache ，后更新 db 么？”

答案： 那肯定是不行的！因为这样可能会造成 数据库（db）和缓存（Cache）数据不一致的问题。

举例：请求 1 先写数据 A，请求 2 随后读数据 A 的话，就很有可能产生数据不一致性的问题。

这个过程可以简单描述为：

请求 1 先把 cache 中的 A 数据删除 -> 请求 2 从 db 中读取数据【此时请求2把脏数据(对于请求1来说是)更新到缓存去了】->请求 1 再把 db 中的 A 数据更新，即请求1的操作非原子

转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!

什么是内存碎片?#

你可以将内存碎片简单地理解为那些不可用的空闲内存。

举个例子：操作系统为你分配了 32 字节的连续内存空间，而你存储数据实际只需要使用 24 字节内存空间，那这多余出来的 8 字节内存空间如果后续没办法再被分配存储其他数据的话，就可以被称为内存碎片。

Redis 内存碎片虽然不会影响 Redis 性能，但是会增加内存消耗。

为什么会有 Redis 内存碎片?#

Redis 内存碎片产生比较常见的 2 个原因：

1、Redis 存储存储数据的时候向操作系统申请的内存空间可能会大于数据实际需要的存储空间。

以下是这段 Redis 官方的原话：

To store user keys, Redis allocates at most as much memory as the maxmemory setting enables (however there are small extra allocations possible).

Redis 使用 zmalloc 方法(Redis 自己实现的内存分配方法)进行内存分配的时候，除了要分配 size 大小的内存之外，还会多分配 PREFIX_SIZE 大小的内存。

zmalloc 方法源码如下（源码地址：https://github.com/antirez/redis-tools/blob/master/zmalloc.c）：

void *zmalloc(size_t size) {
   // 分配指定大小的内存
   void *ptr = malloc(size+PREFIX_SIZE);
   if (!ptr) zmalloc_oom_handler(size);
#ifdef HAVE_MALLOC_SIZE
   update_zmalloc_stat_alloc(zmalloc_size(ptr));
   return ptr;
#else
   *((size_t*)ptr) = size;
   update_zmalloc_stat_alloc(size+PREFIX_SIZE);
   return (char*)ptr+PREFIX_SIZE;
#endif
}

另外，Redis 可以使用多种内存分配器来分配内存（ libc、jemalloc、tcmalloc），默认使用 jemalloc，而 jemalloc 按照一系列固定的大小（8 字节、16 字节、32 字节……）来分配内存的。jemalloc 划分的内存单元如下图所示：

转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!

除了 5 种基本的数据结构之外，Redis 还支持 3 种特殊的数据结构 ：Bitmap、HyperLogLog、GEO。

Bitmap#

介绍#

Bitmap 存储的是连续的二进制数字（0 和 1），通过 Bitmap, 只需要一个 bit 位来表示某个元素对应的值或者状态，key 就是对应元素本身 。我们知道 8 个 bit 可以组成一个 byte，所以 Bitmap 本身会极大的节省储存空间。

你可以将 Bitmap 看作是一个存储二进制数字（0 和 1）的数组，数组中每个元素的下标叫做 offset（偏移量）。

常用命令#

Bitmap 基本操作演示 ：

转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!

Redis 共有 5 种基本数据结构：String（字符串）、List（列表）、Set（集合）、Hash（散列）、Zset（有序集合）。

这 5 种数据结构是直接提供给用户使用的，是数据的保存形式，其底层实现主要依赖这 8 种数据结构：简单动态字符串（SDS）、LinkedList（双向链表）、Hash Table（哈希表）、SkipList（跳跃表）、Intset（整数集合）、ZipList（压缩列表）、QuickList（快速列表）。

Redis 基本数据结构的底层数据结构实现如下：

Redis 3.2 之前，List 底层实现是 LinkedList 或者 ZipList。 Redis 3.2 之后，引入了 LinkedList 和 ZipList 的结合 QuickList，List 的底层实现变为 QuickList。

你可以在 Redis 官网上找到 Redis 数据结构非常详细的介绍：

• Redis Data Structures
• Redis Data types tutorial

未来随着 Redis 新版本的发布，可能会有新的数据结构出现，通过查阅 Redis 官网对应的介绍，你总能获取到最靠谱的信息。

String（字符串）#

介绍#

String 是 Redis 中最简单同时也是最常用的一个数据结构。

String 是一种二进制安全的数据结构，可以用来存储任何类型的数据比如字符串、整数、浮点数、图片（图片的 base64 编码或者解码或者图片的路径）、序列化后的对象。

转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!

Redis 事务#

如何使用 Redis 事务？#

Redis 可以通过 MULTI，EXEC，DISCARD 和 WATCH 等命令来实现事务(transaction)功能。

> MULTI
OK
> SET PROJECT "JavaGuide"
QUEUED
> GET PROJECT
QUEUED
> EXEC
1) OK
2) "JavaGuide"

MULTI 命令后可以输入多个命令，Redis 不会立即执行这些命令，而是将它们放到队列，当调用了 EXEC 命令后，再执行所有的命令。

这个过程是这样的：

1. 开始事务（MULTI）；
2. 命令入队(批量操作 Redis 的命令，先进先出（FIFO）的顺序执行)；
3. 执行事务(EXEC)。

你也可以通过 DISCARD 命令取消一个事务，它会清空事务队列中保存的所有命令。

> MULTI
OK
> SET PROJECT "JavaGuide"
QUEUED
> GET PROJECT
QUEUED
> DISCARD
OK

你可以通过 WATCH 命令监听指定的 Key，当调用 EXEC 命令执行事务时，如果一个被 WATCH 命令监视的 Key 被 其他客户端/Session 修改的话，整个事务都不会被执行。

# 客户端 1
> SET PROJECT "RustGuide"
OK
> WATCH PROJECT
OK
> MULTI
OK
> SET PROJECT "JavaGuide"
QUEUED

# 客户端 2
# 在客户端 1 执行 EXEC 命令提交事务之前修改 PROJECT 的值
> SET PROJECT "GoGuide"

# 客户端 1
# 修改失败，因为 PROJECT 的值被客户端2修改了
> EXEC
(nil)
> GET PROJECT
"GoGuide"

不过，如果 WATCH 与 事务 在同一个 Session 里，并且被 WATCH 监视的 Key 被修改的操作发生在事务内部，这个事务是可以被执行成功的（相关 issue ： WATCH 命令碰到 MULTI 命令时的不同效果）。

转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!

Redis 基础#

什么是 Redis？#

Redis 是一个基于 C 语言开发的开源数据库（BSD 许可），与传统数据库不同的是 Redis 的数据是存在内存中的（内存数据库），读写速度非常快，被广泛应用于缓存方向。并且，Redis 存储的是 KV 键值对数据。

为了满足不同的业务场景，Redis 内置了多种数据类型实现（比如 String、Hash、【List、Set、】Sorted Set、Bitmap）。并且，Redis 还支持事务 、持久化、Lua 脚本、多种开箱即用的集群方案（Redis Sentinel、Redis Cluster）。

Redis 没有外部依赖，Linux 和 OS X 是 Redis 开发和测试最多的两个操作系统，官方推荐生产环境使用 Linux 部署 Redis。

个人学习的话，你可以自己本机安装 Redis 或者通过 Redis 官网提供的 在线 Redis 环境来实际体验 Redis。

全世界有非常多的网站使用到了 Redis ， techstacks.io 专门维护了一个 使用 Redis 的热门站点列表 ，感兴趣的话可以看看。

Redis 为什么这么快？#

Redis 内部做了非常多的性能优化，比较重要的主要有下面 3 点：

• Redis 基于内存，内存的访问速度是磁盘的上千倍；
• Redis 基于 Reactor 模式设计开发了一套高效的事件处理模型，主要是单线程事件循环和 IO 多路复用（Redis 线程模式后面会详细介绍到）；
• Redis 内置了多种优化过后的数据结构实现，性能非常高。

下面这张图片总结的挺不错的，分享一下，出自 Why is Redis so fast? 。

转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!

原文地址：https://juejin.cn/post/7122014462181113887，JavaGuide 对本文进行了完善总结。

我有一个朋友做了一个小破站，现在要实现一个站内信 Web 消息推送的功能，对，就是下图这个小红点，一个很常用的功能。

不过他还没想好用什么方式做，这里我帮他整理了一下几种方案，并简单做了实现。

# 什么是消息推送？#

推送的场景比较多，比如有人关注我的公众号，这时我就会收到一条推送消息，以此来吸引我点击打开应用。

消息推送通常是指网站的运营工作等人员，通过某种工具对用户当前网页或移动设备 APP 进行的主动消息推送。

消息推送一般又分为 Web 端消息推送和移动端消息推送。

移动端消息推送示例 ：

Web 端消息推送示例：

在具体实现之前，咱们再来分析一下前边的需求，其实功能很简单，只要触发某个事件（主动分享了资源或者后台主动推送消息），Web 页面的通知小红点就会实时的 +1 就可以了。

通常在服务端会有若干张消息推送表，用来记录用户触发不同事件所推送不同类型的消息，前端主动查询（拉）或者被动接收（推）用户所有未读的消息数。

消息推送无非是推（push）和拉（pull）两种形式，下边我们逐个了解下。

# 消息推送常见方案#

# 短轮询#

轮询(polling) 应该是实现消息推送方案中最简单的一种，这里我们暂且将轮询分为短轮询和长轮询。

短轮询很好理解，指定的时间间隔，由浏览器向服务器发出 HTTP 请求，服务器实时返回未读消息数据给客户端，浏览器再做渲染显示。

一个简单的 JS 定时器就可以搞定，每秒钟请求一次未读消息数接口，返回的数据展示即可。

setInterval(() => {
  // 方法请求
  messageCount().then((res) => {
      if (res.code === 200) {
          this.messageCount = res.data
      }
  })
}, 1000);

效果还是可以的，短轮询实现固然简单，缺点也是显而易见，由于推送数据并不会频繁变更，无论后端此时是否有新的消息产生，客户端都会进行请求，势必会对服务端造成很大压力，浪费带宽和服务器资源。

# 长轮询#

长轮询是对上边短轮询的一种改进版本，在尽可能减少对服务器资源浪费的同时，保证消息的相对实时性。长轮询在中间件中应用的很广泛，比如 Nacos 和 Apollo 配置中心，消息队列 Kafka、RocketMQ 中都有用到长轮询。

转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!

为什么需要定时任务？#

我们来看一下几个非常常见的业务场景：

1. 某系统凌晨要进行数据备份。
2. 某电商平台，用户下单半个小时未支付的情况下需要自动取消订单。
3. 某媒体聚合平台，每 10 分钟动态抓取某某网站的数据为自己所用。
4. 某博客平台，支持定时发送文章。
5. 某基金平台，每晚定时计算用户当日收益情况并推送给用户最新的数据。
6. ……

这些场景往往都要求我们在某个特定的时间去做某个事情。

单机定时任务技术选型#

Timer#

java.util.Timer是 JDK 1.3 开始就已经支持的一种定时任务的实现方式。

Timer 内部使用一个叫做 TaskQueue 的类存放定时任务，它是一个基于最小堆实现的优先级队列。TaskQueue 会按照任务距离下一次执行时间的大小将任务排序，保证在堆顶的任务最先执行。这样在需要执行任务时，每次只需要取出堆顶的任务运行即可！

Timer 使用起来比较简单，通过下面的方式我们就能创建一个 1s 之后执行的定时任务。

// 示例代码：
TimerTask task = new TimerTask() {
    public void run() {
        System.out.println("当前时间: " + new Date() + "n" +
                "线程名称: " + Thread.currentThread().getName());
    }
};
System.out.println("当前时间: " + new Date() + "n" +
        "线程名称: " + Thread.currentThread().getName());
Timer timer = new Timer("Timer");
long delay = 1000L;
timer.schedule(task, delay);


//输出：
当前时间: Fri May 28 15:18:47 CST 2021n线程名称: main
当前时间: Fri May 28 15:18:48 CST 2021n线程名称: Timer

不过其缺陷较多，比如一个 Timer 一个线程，这就导致 Timer 的任务的执行只能串行执行，一个任务执行时间过长的话会影响其他任务（性能非常差），再比如发生异常时任务直接停止（Timer 只捕获了 InterruptedException ）。

转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!

系统需要对用户输入的文本进行敏感词过滤如色情、政治、暴力相关的词汇。

敏感词过滤用的使用比较多的 Trie 树算法 和 DFA 算法。

算法实现#

Trie 树#

Trie 树 也称为字典树、单词查找树，哈系树(这里是不是写错了，哈希树？)的一种变种，通常被用于字符串匹配，用来解决在一组字符串集合中快速查找某个字符串的问题。像浏览器搜索的关键词提示一般就是基于 Trie 树来做的。

假如我们的敏感词库中有以下敏感词：

• 高清有码
• 高清 AV
• 东京冷
• 东京热

我们构造出来的敏感词 Trie 树就是下面这样的：

当我们要查找对应的字符串“东京热”的话，我们会把这个字符串切割成单个的字符“东”、“京”、“热”，然后我们从 Trie 树的根节点开始匹配。

可以看出， Trie 树的核心原理其实很简单，就是通过公共前缀来提高字符串匹配效率。

Apache Commons Collecions 这个库中就有 Trie 树实现：

Trie<String, String> trie = new PatriciaTrie<>();
trie.put("Abigail", "student");
trie.put("Abi", "doctor");
trie.put("Annabel", "teacher");
trie.put("Christina", "student");
trie.put("Chris", "doctor");
Assertions.assertTrue(trie.containsKey("Abigail"));
assertEquals("{Abi=doctor, Abigail=student}", trie.prefixMap("Abi").toString());
assertEquals("{Chris=doctor, Christina=student}", trie.prefixMap("Chr").toString());

Aho-Corasick（AC）自动机是一种建立在 Trie 树上的一种改进算法，是一种多模式匹配算法，由贝尔实验室的研究人员 Alfred V. Aho 和 Margaret J.Corasick 发明。

AC 自动机算法使用 Trie 树来存放模式串的前缀，通过失败匹配指针（失配指针）来处理匹配失败的跳转。

转载自https://github.com/Snailclimb/JavaGuide（添加小部分笔记）感谢作者!

作者：转转技术团队

原文：https://mp.weixin.qq.com/s/ONMuELjdHYa0yQceTj01Iw

ly：比较繁琐，大概看了前面的部分

老权限系统的问题与现状#

转转公司在过去并没有一个统一的权限管理系统，权限管理由各业务自行研发或是使用其他业务的权限系统，权限管理的不统一带来了不少问题：

1. 各业务重复造轮子，维护成本高
2. 各系统只解决部分场景问题，方案不够通用，新项目选型时没有可靠的权限管理方案
3. 缺乏统一的日志管理与审批流程，在授权信息追溯上十分困难

基于上述问题，去年底公司启动建设转转统一权限系统，目标是开发一套灵活、易用、安全的权限管理系统，供各业务使用。

业界权限系统的设计方式#

目前业界主流的权限模型有两种，下面分别介绍下：

• 基于角色的访问控制（RBAC）
• 基于属性的访问控制（ABAC）

RBAC 模型#

基于角色的访问控制（Role-Based Access Control，简称 RBAC） 指的是通过用户的角色（Role）授权其相关权限，实现了灵活的访问控制，相比直接授予用户权限，要更加简单、高效、可扩展。

一个用户可以拥有若干角色，每一个角色又可以被分配若干权限这样，就构造成“用户-角色-权限” 的授权模型。在这种模型中，用户与角色、角色与权限之间构成了多对多的关系。

用一个图来描述如下：

当使用 RBAC模型 时，通过分析用户的实际情况，基于共同的职责和需求，授予他们不同角色。这种 用户 -> 角色 -> 权限 间的关系，让我们可以不用再单独管理单个用户权限，用户从授予的角色里面获取所需的权限。

以一个简单的场景（Gitlab 的权限系统）为例，用户系统中有 Admin、Maintainer、Operator 三种角色，这三种角色分别具备不同的权限，比如只有 Admin 具备创建代码仓库、删除代码仓库的权限，其他的角色都不具备。我们授予某个用户 Admin 这个角色，他就具备了 创建代码仓库 和 删除代码仓库 这两个权限。

通过 RBAC模型 ，当存在多个用户拥有相同权限时，我们只需要创建好拥有该权限的角色，然后给不同的用户分配不同的角色，后续只需要修改角色的权限，就能自动修改角色内所有用户的权限。

ABAC 模型#

基于属性的访问控制（Attribute-Based Access Control，简称 ABAC） 是一种比 RBAC模型 更加灵活的授权模型，它的原理是通过各种属性来动态判断一个操作是否可以被允许。这个模型在云系统中使用的比较多，比如 AWS，阿里云等。

考虑下面这些场景的权限控制：

1. 授权某个人具体某本书的编辑权限
2. 当一个文档的所属部门跟用户的部门相同时，用户可以访问这个文档
3. 当用户是一个文档的拥有者并且文档的状态是草稿，用户可以编辑这个文档
4. 早上九点前禁止 A 部门的人访问 B 系统
5. 在除了上海以外的地方禁止以管理员身份访问 A 系统
6. 用户对 2022-06-07 之前创建的订单有操作权限

可以发现上述的场景通过 RBAC模型 很难去实现，因为 RBAC模型 仅仅描述了用户可以做什么操作，但是操作的条件，以及操作的数据，RBAC模型 本身是没有这些限制的。但这恰恰是 ABAC模型 的长处，ABAC模型 的思想是基于用户、访问的数据的属性、以及各种环境因素去动态计算用户是否有权限进行操作。