Session 和 Cookie

每个客户端（浏览器）在与服务器端产生连接后，都会在服务器端为该客户端创建一个独有的 Session 对象。Session 就是 Tomcat 服务器内存中保存的一个 Map 对象，所有 Session 对象都放到一个 SessionManager 里进行管理，不同的 Session 代表与不同的客户端进行的会话。

Session 和 Cookie 的关系：

• 在某个客户端（浏览器）第一次访问服务器时，将创建一个 Session 对象，并保存到服务器端
• 同时令客户端保存一个 jsessionid = sessionId 的 Cookie。其 key 值是固定的 jsessionid，value 是 sessionId。浏览器关闭前该 Cookie 将一直存在
• Cookie 中还保存着一个重要信息：Domain（域名）。该值保存着该 Cookie 可以访问的网站域名。当访问一个网站时，浏览器会从目前存活的所有 Cookie 中选出 Domain 匹配当前网站的那些 Cookie，并在访问该网站时在请求头里带上这些 Cookie。
• 之后 Cookie 存在期间每次访问对应 Domain 的服务器都将带上 Cookie 信息（在请求头中）
• 浏览器关闭后，清除掉 Cookie，服务器端清除掉 Session

Cookie 是浏览器负责保存，Session 是服务器负责保存。Cookie 中保存着 Session 信息，对应唯一的一个 Session。

示意图：

关于 Session 和 Cookie 的完整介绍见文章【JavaWeb】Session 和 Cookie

Session 共享问题

在分布式下存在着 Session 共享问题：

• 不同微服务间无法共享 Session：因为每个 Session 都是存储在当前微服务的内存中的，所以无法获取其他微服务内存中的 Session 里数据，即：Session 不能跨不同的域名共享
• 在集群环境下同一个服务的不同实例也无法共享：在负载均衡算法作用下，可能第一次访问节点1，将数据存储到了节点1的 Session 里。而第二次访问节点2时，其内并没有保存节点1里的 Session 数据，所以仍然无法共享

二者的共同原因是：Session 是保存在服务器的内存中的，A 服务内存中的 Session 数据显然无法被 B 服务访问到：

转发不需要考虑 Session 共享问题。因为转发是可以直接在请求域中传递数据的，根本不需要保存到 Session。只有重定向才需要从 Session 中取数据

Session 共享问题解决方案

方案一：Session 复制（同步）

缺点是每个服务都需要保存其他所有服务的 Session 数据，消耗了大量空间。并且 Session 同步占用了大量的网络宽带，降低了服务器集群的业务处理能力。不推荐使用。

方案二：客户端存储

这种方式的缺点也很明显，同样不推荐使用。

方案三：一致性 Hash

在负载均衡时，使用 ip_hash 策略将同一个 ip 的请求负载均衡到同一个服务节点上，这样就能保证同一个 ip 每次都能访问到同一台服务器上的 Session 了。这种方案的缺点不是很大，可以考虑使用。

方案四：统一存储到 Redis（推荐）

为了做到多个微服务间共享 Session，我们可以把所有微服务的 Session 都统一存储到 Redis 中。这样就可以同时解决两种共享问题，既能让同一服务的不同实例访问到彼此的 Session，也能让不同的微服务也能访问到彼此的 Session。

该方案的缺点就是增加了一次网络调用，并且需要修改代码，例如将原本获取 Session 的方法 getSession() 修改成从 Redis 中读取。不过这些缺点可以使用 Spring Session 完美解决。

方案五：不同服务的子域 Session 共享（推荐）

通过方案四，我们实现了所有微服务都可以通过 sessionId 从 Redis 中查询某个 Session 数据。但是问题又来了，其他微服务如何得知要查询的 sessionId 是多少呢？ 此时就需要先解释一下浏览器是如何让后端服务知道是要访问哪个 sessionId 的：

Domain：每个 Cookie 都有一个 Domain（域名）。该值保存着该 Cookie 可以访问的网站域名。当访问一个网站时，浏览器会从目前存活的所有 Cookie 中选出 Domain 匹配当前网站的那些 Cookie，并在访问该网站时在请求头里带上这些 Cookie。这些 Cookie 里就保存了 jsessionId = sessionid 信息，也就是其要向该 sessionId 对应的 Session 获取数据。这样，浏览器在发出请求时，就会在请求头里携带上该 Cookie，从而携带了要查询的 sessionId，这样后端服务就可以根据该 Id 去 Redis 中查询出对应的 Session 数据了。

那么我们只需要保证所有微服务都拥有同一份 Cookie 即可。在某个服务给浏览器发放 Cookie 时，需要指定 Domain 为当前服务域名的父域的值，这样浏览器在访问该父域的其他子域时也能带上该 Cookie，也就可以获取到当前服务的 Session 数据（Session 存储在 Redis 中，所有服务都可以根据 sessionId 获取到 Session 数据）了。

关于 Domian 域名：

• 父域：yunmall.com
• 子域： auth.yunmall.com、order.yunmall.com 等

例如认证服务 mall-auth-server 的域 auth.yunmall.com 在发放 Session 时，需要设置 Domain 为父域 yunmall.com。这样浏览器在访问其他微服务时也可以带上此 Cookie，也就可以获取到认证服务存储的 Session 数据了。

在 JavaWeb 原生 API 中指定父域的方式：

1

new Cookie("JSESSIONID", ".....").setDomain("yunmall.com");

下面将介绍如何使用 Spring Session 框架快速实现微服务间的 Session 共享。

Spring Session

Spring Session 是 Spring 的项目之一，它提供了一套创建和管理 Servlet HttpSession 的完美方案。Spring Session 提供了 API 和实现，用于管理用户的 Session 信息。除此之外，它还提供了如下特性：

• 将 session 所保存的状态卸载到特定的外部 session 存储汇总，如 Redis 中，他们能够以独立于应用服务器的方式提供高质量的集群。
• 控制 sessionid 如何在客户端和服务器之间进行交换，这样的话就能很容易地编写 Restful API ，因为它可以从 HTTP 头信息中获取 sessionid ，而不必再依赖于 cookie。
• 在非 Web 请求的处理代码中，能够访问 session 数据，比如在 JMS 消息的处理代码中。
• 支持每个浏览器上使用多个 session，从而能够很容易地构建更加丰富的终端用户体验。
• 当用户使用 WebSocket 发送请求的时候，能够保持 HttpSession 处于活跃状态。

配置与使用

1. 导入 Maven 依赖

1
2
3
4
5
6
7
8
9
10
11

<!-- 整合 Spring Session -->
<dependency>
    <groupId>org.springframework.session</groupId>
    <artifactId>spring-session-data-redis</artifactId>
</dependency>

<!-- 需要 Redis 依赖 -->
<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>

2. 配置文件中指定 Session 存储到 Redis 中，并且配置 Redis 信息

1
2
3
4
5
6
7
8
9

spring:
  application:
    name: yunmall-auth-server
  redis:
    host: yuyunzhao.cn
    port: 6379
    password: zhaoyuyun # 设置密码防止被别人利用
  session:
    store-type: redis

3. 配置 Session 过期时间

1
2
3
4
5

server:
  port: 20000
  servlet:
    session:
      timeout: 30m  # Session 30分钟后过期

4. 在主启动类上添加注解 @EnableRedisHttpSession 开启 Spring Session 功能

1
2
3
4
5
6
7
8
9

@EnableRedisHttpSession  // 整合 Redis 作为 Session 存储地点
@EnableFeignClients
@EnableDiscoveryClient
@SpringBootApplication
public class MallAuthServerApplication {
    public static void main(String[] args) {
        SpringApplication.run(MallAuthServerApplication.class, args);
    }
}

5. 编写自定义配置类，更改容器中默认的 Spring Session 序列化方式与 Cookie 保存内容。指定存储到 Redis 中序列化方式为 JSON 格式（默认是 JDK 序列化方式），指定 Cookie 中保存的 Domain 为父域 yunmall.com

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

@Configuration
public class MallSessionConfig {
    /**
     * 自定义存储到 Redis 中序列化方式为 JSON 格式，默认是 JDK 序列化方式
     */
    @Bean
    public RedisSerializer<Object> springSessionDefaultRedisSerializer() {
        // 使用 JSON 序列化方式
        return new GenericJackson2JsonRedisSerializer();
    }
    /**
     * 自定义 Cookie 名和父域
     */
    @Bean
    public CookieSerializer cookieSerializer() {
        DefaultCookieSerializer serializer = new DefaultCookieSerializer();
        // 设置 Cookie 名
        serializer.setCookieName("YUNSESSIONID");
        // 设置父域
        serializer.setDomainName("yunmall.com");
        return serializer;
    }
}

如果使用默认的 JDK 序列化方式保存对象，则必须要给要保存的 POJO 实现序列化接口 Serializable

6. 向 Session 中存储 POJO

1
2
3
4
5
6
7
8

@RequestMapping("/oauth2.0/weibo/success")
public String authorize(String code, HttpSession session) {
    MemberResponseVo memberResponseVo = new MemberResponseVo();
    // 将 POJO 直接存储到 Session 中，Spring Session 会使用我们自定义的 JSON 序列化器将该对象转换成 JSON 字符串后保存到 Redis 中
    session.setAttribute("loginUser", memberResponseVo);
	// 重定向到父域
    return "redirect:http://yunmall.com";
}

Spring Session 会使用我们自定义的 JSON 序列化器将该对象转换成 JSON 字符串后保存到 Redis 中。同时将该 Session 的 id 以 Cookie 的形式返回给浏览器进行保存。在 Redis 中查看保存结果：

可以看到，POJO 已经成功保存到了 Redis 中，这样其他微服务同样可以在进行上述配置也访问到该数据（其他想访问到 Redis 中 Session 数据的服务必须也得配置 Spring Session）。

7. 该 Session 的 id 信息将以 Cookie 的形式返回给浏览器进行保存，并且保存的 Cookie 的 Domain 是父域 yunmall.com：

这样在重定向到商品服务 mall-product 的首页时，浏览器会带着该 Cookie 进行访问（因为 Domain 匹配上要访问的 URL 了）。这样就可以根据该 Cookie 里存的 sessionid 去 Redis 中查找出对应的 Session 数据，从而成功访问到认证服务存储的 MemberRespVo 数据，并渲染到页面上：

1
2
3
4
5

<li>
    <a href="http://auth.yunmall.com/login.html">
        你好，[[${session.loginUser.username}]]
    </a>
</li>

Spring Session 核心原理

Spring Session 的实现使用了装饰器模式，核心原理是：

• 将普通的 HttpRequest 进行了包装，将其包装成了 SessionRepositoryRequestWrapper 类型的对象
• 并且向容器中注入了一个过滤器 SessionRepositoryFilter，在 Controller 的方法执行前先拦截请求，将原生的 HttpRequest 包装成了 SessionRepositoryRequestWrapper 。
• 这样 Controller 层在调用HttpRequest.getSession() 时，真正在执行的就是包装后的 SessionRepositoryRequestWrapper 的 getSession() 方法了。
• 根据我们选择的 Redis 配置 RedisHttpSessionConfiguration，该方法的真正执行逻辑是根据 Cookie 中的 sessionid 去 Redis 里查询该 Session 的真实数据。从而做到了与业务代码的解耦。

过滤器里的代码：

错题集

• 剑指 Offer 30. 包含min函数的栈：记得 Integer 类型的比较要用 equals() 方法
• 34. 在排序数组中查找元素的第一个和最后一个位置：注意边界为 -1 时可能越界。可以参考题解中的复用思想
• 剑指 Offer 35. 复杂链表的复制：必须先遍历一遍设置 copy.next，再遍历一遍设置 random，如果依次遍历同时设置，则前面设置的 random 会被后面设置的 copy 给覆盖
• 剑指 Offer 53 - II. 0～n-1中缺失的数字：题解里的思路很好，将数组分为左子数组和右子数组，右子数组的首位元素就是答案
• 162. 寻找峰值：自己的思路里，注意退出循环时要判断 left 和 right 谁的值更大（可能出现左侧降序时 left 停在了索引为 1 的位置；右侧升序时 left 停在了索引为最大值的位置。这时前者是错误的，后者是正确的。所以需要额外判断停止时到底是哪种情况。或者直接用题解里的合并思路）
• 剑指 Offer 26. 树的子结构：区分两个递归 isSubStructer() 和 recur() 的区别
• 746. 使用最小花费爬楼梯：注意题目的意思，需要引入天台和地平线的概念来理解，dp[] 的长度要包含最后的天台。到达天台才是答案要求的值
• 55. 跳跃游戏：贪心
• 45. 跳跃游戏 II：贪心。注意逻辑起跳的概念（提前预约起跳，但还没真正起跳），只是记录了下次起跳后能到达的最远位置，并未真正起跳
• 740. 删除并获得点数：本质上是打家劫舍问题
• 剑指 Offer 63. 股票的最大利润：动态规划问题。规定当前天必须卖出的情况下的收益最，与前 i-1 天内的最大收益间的最大值
• 438. 找到字符串中所有字母异位词：题解中的两种思路都不错。需要注意题目场景符合固定长度的数组，可以限制好每次都对比当前长度的 s 数组与 p 数组是否相同
• 剑指 Offer 47. 礼物的最大价值：记得使用压缩技巧的话，在每个 loop 里都需要先给 dp[0] 更新值
• 剑指 Offer 46. 把数字翻译成字符串：记住博客里记录的代码思路。也可以从右往左遍历，使用求余的方式计算当前 i 位置的值，从而省掉 String 的空间
• 141. 环形链表：需要先判断一下链表的长度是否小于等于 2，然后在 while 循环里需要判断 quick != null && quick.next != null。因为每次 quick 都移动两步，所以必须保证 quick.next != null，否则就会空指针异常
• 90. 子集 II：策略：先排序。如果当前值等于前一个值。那么判断前一个值是否被选中。如果被选中，则当前值可以被选中，也可以不被选中；如果没被选中，则当前值不能被选中（因为这种情况会和第一种中的某一个情况重复，例如前选中，后没选中）
• 713. 乘积小于K的子数组：每次移动一次 right，然后迭代 left 直到找到 [left, right] 区间内为符合条件的区间，然后更新该子区间内的新增子数组个数（规定每次必须以 right 位置为子数组的末尾，这样就不会重复计算）
• 209. 长度最小的子数组：该题和上面那题都体现为一种滑动窗口的模板：外层的循环不断增加 right，在内层使用 while 不断循环更新 left 直到满足条件后退出，此时更新了 left。
• 剑指 Offer 12. 矩阵中的路径：DFS 问题。经典套路是主函数里遍历图中每一个位置，以其作为开头进行递归，判断当前位置作为第一个元素时能否成功找到目标字符串，剪枝操作为：修改已访问过的成功字符串为’ ’
• 剑指 Offer 13. 机器人的运动范围：注意机器人只能从[0,0]位置出发，所以不能使用for循环遍历每一个位置，和上一题还不一样（上一题可以从任意位置出发寻找目标字符串）
• Pow(a, b)
• 剑指 Offer 34. 二叉树中和为某一值的路径：需要在叶子节点时判断，而不是在 null 时判断。并且记得在叶子结点处也要加上当前的数字到集合中
• 剑指 Offer 36. 二叉搜索树与双向链表：记得退出循环时将链表头 head 和尾 pre 也连接起来
• 剑指 Offer 32 - III. 从上到下打印二叉树 III：每层判断奇偶，据此决定是添加到当前层的 last 还是 first（注意 tmp 需要设置为 LinkedList 类型，否则没有 addFirst 方法）。左右节点的添加还是一致的先左后右，只是添加到 list 时顺序需要判断奇偶。如果题目要求的不是保存到 list 而是打印，则这种思路就不行，因为这种思路遍历的顺序还是原顺序，只是在保存时使用技巧使得奇偶不一致。此时仍需要双端队列，每次打印两层。
• 剑指 Offer 41. 数据流中的中位数：大小根堆，始终保证大的一半的堆保存的数据比小的一半的堆多一个，添加时都是先加入到其中的一个堆里，过滤一下后再将堆顶的元素弹出放到另一个堆里。并且计算中位数时一定要保证是 double 类型，要用 (a + b) / 2.0。
• 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先：利用好搜索和唯一的特性，根据 p 和 q 的值与 root 值的关系判断公共祖先节点在 root 的左还是右

更优解

• 9. 回文数：题解中思想非常好
• 82. 删除排序链表中的重复元素 II：题解中的思路更加优雅
• 844. 比较含退格的字符串：双指针从右向左遍历，在一个大的 while(i >= 0 || j >= 0) 中先后的 while(i >=0) 与 while(j >= 0)，将 # 不断删掉。二者都出循环时，i 和 j 位置都是有效字符，此时进行比较判断。若 i 与 j 一个小于 0，一个大于等于 0，说明其中一个遍历完了，但是另一个还没遍历完，那就说明二者不匹配
• 剑指 Offer 22. 链表中倒数第k个节点：快慢指针的思路更好
• 剑指 Offer 25. 合并两个排序的链表：最后退出循环时，不需要逐个遍历每个 l1 或 l2，而是只需要将 cur.next 指向剩下的那个链表节点即可
• 剑指 Offer 52. 两个链表的第一个公共节点：题解里的思路更好。两个指针先后遍历两条链表，相交时就是答案
• 剑指 Offer 58 - I. 翻转单词顺序：题解中的双指针思路。借助 StringBuilder 实现拼接
• 剑指 Offer 54. 二叉搜索树的第k大节点：倒序进行中序遍历更加高效
• 剑指 Offer 45. 把数组排成最小的数：比较字符串的大小：s1.compareTo(s2)

重点

链表题目里，翻转的题目：

Vue 简介

Vue.js 是一套用于构建用户界面的渐进式框架（基于 JavaScript，本质上是一个 JS 框架）。与其它大型框架不同的是，Vue 被设计为可以自底向上逐层应用。Vue 的核心库只关注视图层，不仅易于上手，还便于与第三方库或既有项目整合。另一方面，当与现代化的工具链以及各种支持类库结合使用时，Vue 也完全能够为复杂的单页应用提供驱动。Vue 是视图层框架，遵守 Soc（关注度分离原则）

Vue 采用 MVVM 思想：

• M：model 包括数据和一些基本操作
• V：view 视图，页面渲染结果
• VM：View-model，模型与视图间的双向操作（无需开发人员干涉）

视图 View 和数据 Model 通过 VM 绑定起来，Model 里有变化会自动地通过 Directives 填写到视图 View 中，视图表单中添加了内容也会自动地通过 DOM Listeners 保存到模型中。Vue 使用虚拟 DOM 技术更新 View 中的数据，而不是更新真实 DOM。

即：视图中的数据变化会自动同步到模型中的变量上；模型中变量值的改变也会自动同步到视图上

View 视图写完后就不需要再修改了，只需要发出请求访问后端获取数据修改 Model 中的数据即可动态更新视图，实现与 View 与 Model 的解耦合。

Vue 本身只关注于视图层，不包含异步通信、页面跳转等功能，这些功能都需要使用其他框架或组件来实现，例如借助于 Axios 实现异步通信，借助于 Vue Router 实现页面跳转。

Vue.js 就是一个 MVVM 的实现者，他的核心就是实现了 DOM 监听与数据绑定。

Element

Element 是饿了么开发的基于 Vue 的桌面端组件库（提供了许多 Vue 组件），其提供了许多的 Vue 组件，可以直接使用。

Axios

Axios 是一个开源的可以用在浏览器端和 Node.js 的异步通信框架，其主要作用就是实现 Ajax 请求。

由于 Vue.js 是一个视图层框架并且作者（尤玉溪）严格遵守 Soc（关注度分离原则），所以 Vue.js 并不包含 Ajax 的通信功能，为了解决通信问题，推荐使用 Axios 框架，少用 jQuery，因为它需要频繁操控 Dom。

概率问题常见题目

蓄水池抽样算法（Reservoir Sampling）

https://www.jianshu.com/p/7a9ea6ece2af

给定一个数据流，数据流长度 N 很大，且 N 直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出 m 个不重复的数据。

这个场景强调了3件事：

1. 数据流长度N很大且不可知，所以不能一次性存入内存。
2. 时间复杂度为 O(N)。
3. 随机选取 m 个数，每个数被选中的概率为 m/N。

第 1 点限制了不能直接取 N 内的 m 个随机数，然后按索引取出数据。第 2 点限制了不能先遍历一遍，然后分块存储数据，再随机选取。第 3 点是数据选取绝对随机的保证。

算法思路：

1. 如果接收的数据量小于 m，则依次放入蓄水池。
2. 当接收到第 i 个数据时，i >= m，则使得其以 m / i 的概率进入蓄水池，同时从蓄水池中不放回地随机选出一个元素将其弹出（1 / m 的概率）。具体做法为：在 [0, i] 范围内取随机数 d，若 d 落在 [0, m-1] 范围内，则用接收到的第 i 个数据替换蓄水池中的第 d 个数据。
3. 重复步骤2。

算法的精妙之处在于：当处理完所有的数据时，蓄水池中的每个数据都是以 m/N 的概率获得的。

应用

蓄水池算法的 O(N) 时间复杂度，O(m) 空间复杂度令其适用于对流数据、大数据集的等概率抽样。比如一个大文本数据，随机输出其中的几行；抽奖系统，等概率抽取每个第一次登录的用户。使用该算法可以以很低的空间复杂度处理随机问题。

分布式蓄水池抽样（Distributed/Parallel Reservoir Sampling）

一块 CPU 的计算能力再强，也总有内存和磁盘 IO 拖他的后腿。因此为提高数据吞吐量，分布式的硬件搭配软件是现在的主流。

如果遇到超大的数据量，即使是 O(N) 的时间复杂度，蓄水池抽样程序完成抽样任务也将耗时很久。因此分布式的蓄水池抽样算法应运而生。运作原理如下：

1. 假设有 K 台机器，将大数据集分成 K 个数据流，每台机器使用单机版蓄水池抽样处理一个数据流，抽样m个数据，并最后记录处理的数据量为N1, N2, …, Nk, …, NK(假设m < Nk)。N1 + N2 + … + NK = N。
2. 取 [1, N] 一个随机数 d，若 d < N1，则在第一台机器的蓄水池中等概率不放回地（1 / m）选取一个数据；若 N1 <= d < (N1 + N2)，则在第二台机器的蓄水池中等概率不放回地选取一个数据；一次类推，重复 m 次，则最终从 N 大数据集中选出 m 个数据。

m/N 的概率验证如下：

1. 第 k 台机器中的蓄水池数据被选取的概率为 m / Nk。
2. 从第 k 台机器的蓄水池中选取一个数据放进最终蓄水池的概率为 Nk / N。
3. 第 k 台机器蓄水池的一个数据被选中的概率为 1 / m。（不放回选取时等概率的）
4. 重复 m 次选取，则每个数据被选中的概率为 m*(m/Nk*Nk/N*1/m)=m/N。

堆结构

堆结构本身比堆排序要重要

堆结构就是用数组实现的完全二叉树结构。

堆结构的节点公式：

• 节点 i 的父节点为 (i - 1) / 2（左右节点都可以统一用这个公式）
• 节点 i 的左子节点为 2 * i + 1
• 节点 i 的右子节点为 2 * i + 2

使用上述公式即直接定位到某个节点的父/子节点

大/小根堆

• 大根堆：堆中的每一个父节点都要比其子节点上的数字大（不考虑其对称的另一侧分支里的节点数字大小）。
• 小根堆：堆中的每一个父节点都要比其子节点上的数字小（不考虑其对称的另一侧分支里的节点数字大小）。

堆结构最重要的两个操作：

• heapInsert：add 操作，新增一个数据到已知堆中。具体做法是新增的数据不断向上遍历堆结构，将数字插入到合适的父节点位置
• heapify：poll 操作，弹出堆里第一个元素（根节点）的值，并重新调整堆结构，令其余部分的元素继续保持大/小根堆结构。具体做法是新的根结点的元素不断向下遍历堆结构，交换其到合适的子节点位置

heapInsert：add 操作。用于新增一个数据到堆中，当新来一个数字时，将其添加到堆结构中，并且满足大根堆（或小根堆）：向上遍历他的每一个父节点，判断其是否大于它的父节点，若大于则和父节点交换，若小于则停止遍历。直到当前数字放到合适的父节点位置，使得当前堆满足大根。

heapify：poll 操作。用于弹出堆中第一个元素，并令其余部分继续保持大/小根堆结构，若用户要求返回并删除当前大根堆的最大元素，并且要求删除后的其他元素依旧符合大根堆：返回当前堆的第一个节点（其肯定是最大元素），然后将当前堆的最后一个元素放到第一个元素的位置。之后开始向下遍历第一个元素的子节点，选出其子节点中最大的数字，并且判断该数字和自身的大小，若子节点数字更大，则交换自身和子节点，若子节点数字更小，则停止遍历；直到该元素被放到合适的子节点位置。

这两个操作的空间复杂度都是 O(logN)，因为 N 个节点的完全二叉树的高度为 O(logN)，上述两个操作都只需要遍历二叉树中的某一条分支即可，因此时间只有 O(logN)

heapInsert 的代码：

1
2
3
4
5
6
7

public static void heapInsert(int[] arr, int index) {
  // 向上遍历当前节点的父节点,直到满足条件: 父节点的值 > 当前节点的值
  while (arr[(index - 1) / 2] < arr[index]) {
    swap(arr, (index - 1) / 2, index);
    index = (index - 1) / 2; // index 记得变为父节点的值
  }
}

heapify 的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// heapSize 用于表示逻辑上的堆的大小, 其和数组的大小没关系
// 该方法的作用是, 在给定堆结构中, 当某个位置的元素被弹出,替换成了其他数字后
// 要保证新的数组仍然保持堆结构, 那么就需要从这个位置开始向下遍历
// 交换其子节点中最大的元素
public static void heapify(int[] arr, int index, int heapSize){
  if (heapSize > arr.length) {
    return;
  }

  while (2*index+1 < heapSize) {
    // 两个孩子中, 判断谁的值更大
    int largest = (2*index+2 < heapSize) && arr[2*index+1] < arr[2*index+2]
      ? 2*index+2 : 2*index+1;

    // 当前节点和子孩子中, 判断谁的值更大
    largest = arr[index] < arr[largest] ? largest : index;

    // 如果相等, 说明此时已经满足了大根堆的条件, 可以跳出循环
    if (largest == index) {
      break;
    }

    // 交换
    swap(arr, index, largest);
    index = largest;
  }
}

具体应用

若用户要求修改堆结构中任意一个位置的元素的值，并要求修改后的数字仍然满足大根堆，则只需要判断修改后的元素是比原先大还是小：

• 若修改后的元素比原先大，则进行 heapInsert 操作，将当前元素向上交换到合适的父节点位置
• 若修改后的元素比原先小，则进行 heapify 操作，将当前元素向下交换到合适的子节点位置

小根堆在 Java 中就是优先级队列默认的实现方式： PriorityQueue<Interger>，其两个方法：

• add() ：本质上就是 heapInsert 操作，将一个数字添加到已存在的小根堆中
• poll()：本质上就是 heapify 操作，首先弹出当前小根堆的根结点元素，并令剩余数字依旧保持小根堆结构。

但是其不能支持“修改堆中某个结构后以很轻的代价重新调整堆的结构”，只支持“弹出堆的根结点元素后重新调整堆的结构”，若想实现这些个性化的功能还需要自己定义堆结构。

其扩容机制是当 heapSize 快满时，将 heapSize * 2。这个操作的时间复杂度在每个元素平摊下来后其实很低

按照模式的应用目标分类，设计模式可以分为创建型模式、结构型模式和行为型模式。

• 创建型模式：是对对象创建过程的各种问题和解决方案的总结，包括各种工厂模式（Factory、Abstract Factory）、单例模式（Singleton）、构建器模式（Builder）、原型模式（ProtoType）
• 结构型模式：是针对软件设计结构的总结，关注于类、对象继承、组合方式的实践经验。常见的结构型模式，包括桥接模式（Bridge）、适配器模式（Adapter）、装饰者模式（Decorator）、代理模式（Proxy）、组合模式（Composite）、外观模式（Facade）、享元模式（Flyweight）等
• 行为型模式：是从类或对象之间交互、职责划分等角度总结的模式。比较常见的行为型模式有策略模式（Strategy）、解释器模式（Interpreter）、命令模式（Command）、观察者模式（Observer）、迭代器模式（Iterator）、模板方法模式（Template Method）、访问者模式（Visitor）

单例模式

线程安全的懒汉式单例模式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// 1. final 修饰：禁止被继承，防止子类继承后破坏单例特性
public final class Singleton implements Serializable {
    // 2. 私有构造方法：防止被外部直接构造，但仍然无法防止以反射的方式创建新实例
    private Singleton() {}
    // 3. 懒汉模式初始设置为 null。如果为饿汉模式，则需要在这里 new Singleton，其会在类被加载时被创建，也是线程安全的
    // 4. volatile 修饰：保证 instance 的有序性
    private static volatile Singleton instance = null;
    // 5. 提供静态方法获取实例对象而不是直接将其设置为 public：保证更好的封装性，并且懒汉模式必须在调用方法时创建实例，如果用 public 修饰 instance 直接获取，就只能写成饿汉模式
    public static Singleton getInstance() {
        // 6. 双端检锁机制：DCL（Double Check Lock ），提供并发性
        // 第一个 if 判断是为了防止创建好实例后每次获取实例都需要加锁导致并发性降低
        if (instance == null){
            // 对类加锁
            synchronized(Singleton.class) {
                // 第二个 if 判断是为了防止第一次创建对象前被并发的创建多个实例对象，在锁内再判断一次就能使得后面抢到锁的线程再去重复创建
                if (instance == null) {
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
    // 7. 防止反序列化破坏单例：当被反序列化创建对象时，调用该方法直接返回实例，而不需要再去创建一个新的实例，保证了线程安全性
    public Object readResovle() {
        return instance;
	}
}

其中需要注意的几个点：

1. final 修饰 Singleton 类：禁止被继承，防止子类继承后破坏单例特性
2. 私有构造方法：防止被外部直接构造，但仍然无法防止以反射的方式创建新实例
3. 懒汉模式初始设置为 null。如果为饿汉模式，则需要在这里 new Singleton()，其会在类被加载时被创建，也是线程安全的
4. volatile 修饰：保证 instance 的有序性
5. 提供静态方法获取实例对象而不是直接将其设置为 public：保证更好的封装性，并且懒汉模式必须在调用方法时创建实例，如果用 public 修饰 instance 直接获取，就只能写成饿汉模式
6. 双端检锁机制：DCL（Double Check Lock ），提供并发性
   1. 第一个 if 判断是为了防止创建好实例后每次获取实例都需要加锁导致并发性降低
   2. 第二个 if 判断是为了防止第一次创建对象前被并发的创建多个实例对象，在锁内再判断一次就能使得后面抢到锁的线程再去重复创建
7. 防止反序列化破坏单例：当被反序列化创建对象时，调用该方法直接返回实例，而不需要再去创建一个新的实例，保证了线程安全性

简介

https://blog.csdn.net/u011863024/article/details/115721328

The Elastic Stack，包括 Elasticsearch、 Kibana、 Beats 和 Logstash（也称为 ELK Stack）。能够安全可靠地获取任何来源、任何格式的数据，然后实时地对数据进行搜索、分析和可视化。

Elaticsearch，简称为 ES， 是一个开源的高扩展的分布式全文搜索引擎， 是整个 ElasticStack 技术栈的核心，是一个可以用于检索、存储和分析的引擎。它可以近乎实时的存储、检索数据；本身扩展性很好，可以扩展到上百台服务器，处理 PB 级别的数据。

全文搜索引擎

Google，百度类的网站搜索，它们都是根据网页中的关键字生成索引，我们在搜索的时候输入关键字，它们会将该关键字即索引匹配到的所有网页返回；还有常见的项目中应用日志的搜索等等。对于这些非结构化的数据文本，关系型数据库搜索不是能很好的支持。

一般传统数据库，全文检索都实现的很鸡肋，因为一般也没人用数据库存文本字段。进行全文检索需要扫描整个表，如果数据量大的话即使对 SQL 的语法优化，也收效甚微。建立了索引，但是维护起来也很麻烦，对于 insert 和 update 操作都会重新构建索引。

基于以上原因可以分析得出，在一些生产环境中，使用常规的搜索方式，性能是非常差的：

• 搜索的数据对象是大量的非结构化的文本数据
• 文件记录量达到数十万或数百万个甚至更多。
• 支持大量基于交互式文本的查询
• 需求非常灵活的全文搜索查询
• 对高度相关的搜索结果的有特殊需求，但是没有可用的关系数据库可以满足
• 对不同记录类型、非文本数据操作或安全事务处理的需求相对较少的情况。为了解决结构化数据搜索和非结构化数据搜索性能问题，我们就需要专业，健壮，强大的全文搜索引擎

这里说到的全文搜索引擎指的是目前广泛应用的主流搜索引擎。它的工作原理是计算机索引程序通过扫描文章中的每一个词，对每一个词建立一个索引，指明该词在文章中出现的次数和位置，当用户查询时，检索程序就根据事先建立的索引进行查找，并将查找的结果反馈给用户的检索方式。这个过程类似于通过字典中的检索字表查字的过程（倒排索引）。

ELK

ELK 是 Elasticsearch、Logstash、 Kibana 三大开源框架首字母大写简称。市面上也被称为 Elastic Stack。

• 其中 Elasticsearch 是一个基于 Lucene、分布式、通过 Restful 方式进行交互的近实时搜索平台框架。像百度、谷歌这种大数据全文搜索引擎的场景都可以使用 Elasticsearch 作为底层支持框架，可见 Elasticsearch 提供的搜索能力确实强大，市面上很多时候我们简称 Elasticsearch 为ES。
• Logstash 是 ELK 的中央数据流引擎，用于从不同目标（文件/数据存储/MQ）收集的不同格式数据，经过过滤后支持输出到不同目的地（文件/MQ/redis/elasticsearch/kafka等）。
• Kibana 可以将 ElasticSearch 的数据通过友好的页面展示出来，提供实时分析的功能。

市面上很多开发只要提到 ELK 能够一致说出它是一个日志分析架构技术栈总称，但实际上 ELK 不仅仅适用于日志分析，它还可以支持其它任何数据分析和收集的场景，日志分析和收集只是更具有代表性，并非唯一性。

收集清洗数据（Logstash） ==> 搜索、存储（ElasticSearch） ==> 展示（Kibana）

Elasticsearch 应用案例

• GitHub：2013 年初，抛弃了 Solr，采取 Elasticsearch 来做 PB 级的搜索。 “GitHub 使用Elasticsearch 搜索 20TB 的数据，包括 13 亿文件和 1300 亿行代码”。
• 维基百科：启动以 Elasticsearch 为基础的核心搜索架构
• 百度：目前广泛使用 Elasticsearch 作为文本数据分析，采集百度所有服务器上的各类指标数据及用户自定义数据，通过对各种数据进行多维分析展示，辅助定位分析实例异常或业务层面异常。目前覆盖百度内部 20 多个业务线（包括云分析、网盟、预测、文库、直达号、钱包、 风控等），单集群最大 100 台机器， 200 个 ES 节点，每天导入 30TB+数据。
• 新浪：使用 Elasticsearch 分析处理 32 亿条实时日志。
• 阿里：使用 Elasticsearch 构建日志采集和分析体系。
• Stack Overflow：解决 Bug 问题的网站，全英文，编程人员交流的网站。

Lucene

• 是 apache软件基金会 4 jakarta 项目组的一个子项目
• 是一个开放源代码的全文检索引擎工具包
• 不是一个完整的全文检索引擎，而是一个全文检索引擎的架构，提供了完整的查询引擎和索引引擎，部分文本分析引擎（英文与德文两种西方语言）
• 当前以及最近几年最受欢迎的免费 Java 信息检索程序库。

Lucene 和 ElasticSearch 的关系：ElasticSearch 基于 Lucene 做了封装和增强。ES 使用 Java 开发并使用 Lucene 作为其核心来实现所有索引和搜索的功能，但是它的目的是通过简单的 RESTful API 来隐藏 Lucene 的复杂性，从而让全文搜索变得简单。

Solr 简介

• Solr 是 Apache 下的一个顶级开源项目，采用 Java 开发，它是基于Lucene的全文搜索服务器。Solr 提供了比 Lucene 更为丰富的查询语言，同时实现了可配置、可扩展，并对索引、搜索性能进行了优化
• Solr 可以独立运行，运行在 letty，Tomcat 等这些 Selrvlet 容器中，Solr 索引的实现方法很简单，用 POST 方法向 Solr 服务器发送一个描述 Field 及其内容的 XML 文档，Solr根据 XML 文档添加、删除、更新索引。Solr 搜索只需要发送HTTP GET请求，然后对 Solr 返回 XML、JSON 等格式的查询结果进行解析，组织页面布局
• Solr 不提供构建 UI 的功能，Solr提供了一个管理界面，通过管理界面可以查询 Solr 的配置和运行情况
• Solr 是基于 Lucene 开发企业级搜索服务器，实际上就是封装了lucene.
• Solr 是一个独立的企业级搜索应用服务器，它对外提供类似于 Web-service 的 API 接口。用户可以通过 HTTP 请求，向搜索引擎服务器提交指定格式的文件，生成索引。也可以通过提出查找请求，并得到返回结果

ES 和 Solr

https://www.kuangstudy.com/bbs/1354069127022583809

• ElasticSearch 是一个实时分布式搜索和分析引擎，它让你以前所未有的速度处理大数据成为可能。
• 它用于全文搜索、结构化搜索、分析以及将这三者混合使用：
  • 维基百科使用 ElasticSearch 提供全文搜索并高亮关键字，以及输入实时搜索（search-asyou-type）和搜索纠错（did-you-mean）等搜索建议功能。
  • 英国卫报使用 ElasticSearch 结合用户日志和社交网络数据提供给他们的编辑以实时的反馈，以便及时了解公众对新发表的文章的回应。
  • StackOverflow 结合全文搜索与地理位置查询，以及 more-like-this 功能来找到相关的问题和答案。
  • Github 使用 ElasticSearch 检索 1300 亿行的代码。
• ElasticSearch 是一个基于 Apache Lucene 的开源搜索引擎。无论在开源还是专有领域，Lucene可被认为是迄今为止最先进、性能最好的、功能最全的搜索引擎库。但是，Lucene 只是一个库。 想要使用它，你必须使用 Java 来作为开发语言并将其直接集成到你的应用中。更糟糕的是，Lucene非常复杂，你需要深入了解检索的相关知识来理解它是如何工作的。
• ElasticSearch 也使用 Java 开发并使用 Lucene 作为其核心来实现所有引和搜索的功能，但是它的目的是通过简单的 RESTful API 来隐藏 Lucene 的复杂性，从而让全文搜索变得简单。

ElasticSearch 与 Solr 比较：

• 当单纯的对已有数据进行搜索时，Solr 更快
• 当实时建立索引时，Solr 会产生 io 阻塞，查询性能较差，ElasticSearch 具有明显的优势
• 随着数据量的增加，Solr 的搜索效率会变得更低，而 ElasticSearch 却没有明显的变化

总结

• Solr 利用 Zookeeper 进行分布式管理，而 ElasticSearch 自身带有分布式协调管理功能
• Solr 支持更多格式的数据,比如JSON/XML/CSV，而 Elasticsearch 仅支持 JSON 文件格式
• Solr 官方提供的功能更多,而Elasticsearch本身更注重于核心功能，高级功能多有第三方插件提供，例如图形化界面需要 kibana 友好支撑
• Solr 查询快，但更新索引时慢（即插入删除慢） ，用于电商等查询多的应用。ES 建立索引快（实时性查询快），用于 facebook，新浪等搜索。
• Solr是传统搜索应用的有力解决方案，但 Elasticsearch 更适用于新兴的实时搜索应用。
• Solr 比较成熟，有一个更大，更成熟的用户、开发和贡献者社区，而Elasticsearch相对开发维护者较少，更新太快，学习使用成本较高。

JSR 303 数据校验

https://www.jianshu.com/p/48725b7328c9

JSR 是 Java Specification Requests 的缩写，即 Java 规范提案。简单的理解为 JSR 是一种 Java 标准，存在各种各样的 JSR，JSR 303 就是数据检验的一个标准。JSR-303 是 Java EE 6 中的一项子规范，叫做 Bean Validation，官方参考实现是hibernate Validator。此实现与 Hibernate ORM 没有任何关系。 JSR 303 用于对 Java Bean 中的字段的值进行验证。 Spring MVC 3.x 之中也大力支持 JSR-303，可以在控制器中对表单提交的数据方便地验证。

Spring Boot 2.2 版本之前的场景启动器依赖中默认内置了该依赖（2.3之后的版本失效），如果需要单独引入依赖，可以使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

<dependency>
    <groupId>org.hibernate</groupId>
    <artifactId>hibernate-validator</artifactId>
    <version>5.4.0.Final</version>
</dependency>
<dependency>
    <groupId>javax.el</groupId>
    <artifactId>el-api</artifactId>
    <version>2.2</version>
</dependency>
<dependency>
    <groupId>org.glassfish.web</groupId>
    <artifactId>javax.el</artifactId>
    <version>2.2.4</version>
</dependency>

相关注解

Bean Validation 中内置的 constraint：

Hibernate Validator 附加的 constraint：

OSS 简介

对象存储服务（Object Storage Service，OSS）用于是一种海量、安全、低成本、高可靠的云存储服务，适合存放任意类型的文件。容量和处理能力弹性扩展，多种存储类型供选择，全面优化存储成本。

阿里巴巴提供了云对象存储服务 Alibaba OSS，可以将对象数据存储在云端，在本地数据库仅存储 URL。本文章将介绍如何在项目中使用 Alibaba OSS。

创建 Bucket

创建自己的对象存储 Bucket：yunmall-project

设置读写权限为公共读：

简介

https://zhuanlan.zhihu.com/p/266804094

为在项目中使用缓存技术（例如 Redis），我们通常要将添加缓存的代码耦合到业务代码中，这样每个业务代码都需要添加重复的缓存代码。自然可以想到，使用 Spring AOP 的思想进行解耦。

Spring Cache 就是这么一个框架。它利用了 Spring AOP，实现了基于注解的缓存功能，并且进行了合理的抽象，业务代码不用关心底层是使用了什么缓存框架，只需要简单地加一个注解并配置缓存框架的类型，就能实现缓存功能了。而且 Spring Cache 也提供了很多默认的配置，用户可以为自己的业务代码快速加上一个很不错的缓存功能。

官网地址：https://docs.spring.io/spring-framework/docs/5.2.10.RELEASE/spring-framework-reference/integration.html#cache-strategie

Spring 从3.1开始定义了 org.springframework.cache.Cache 和 org.sprngframework.cache.CacheManager 接口来统一不同的缓存技术，并支持使用 JCache（JSR-107）注解简化我们的开发。

CacheManager 接口为缓存的组件定义存储规则，其内部的缓存组件（Cache 接口类型）才是真正向缓存中存储数据的（以 k:v 存储数据）。这些组件根据名字进行区分，存储的规则是由 CacheManager 制定的。例如：

• 如果使用ConcrrentMapCache 类型的 CacheManager，则其内部存储的 ConcrrentMapCache 里面都是使用 ConcurrentMap 存储数据的，通常用于本地缓存。
• 如果使用 RedisCache类型的 RedisCacheManager，则其内部存储的 RedisCache对象存储的数据都是存放在 Redis 中的，通常用于分布式缓存。

从图中可以看到，不同的 CacheManager 中保存着不同类型的 Cache，并且这些 Cache 都有自己的名字（在 Redis 中显示的 Key 的名字），并且其内按照 k:v 的方式保存数据。

以 RedisCache 为例。使用 Spring Cache 时，在方法上标注注解 @Cacheable。这样每次在调用该方法前会向 Redis 检查该缓存是否已存在：

• 如果已存在就直接从缓存中获取方法调用后的结果，方法内代码将不再被执行
• 如果不存在再执行方法内代码并将方法的返回结果到 Redis 中，下次就可以直接调用从缓存中获取该数据了