校园失物招领网站 | Dorian

项目介绍 :book:

👉基于Springboot+vue+uni-app的校园失物招领平台. 含平台主体PC端、微信小程序和web后台数据管理平台.

• 失物招领信息一览
• 信息发布(支持图片上传)

项目技术栈 :star:

• PC端（WarmSearch-PC)：Vue 2.0+Vue-router+Vuex+Element-ui+Axios
• 后台管理系统(WarmSearch-Web)：基于Vue-admin-ui脚手架
• 微信小程序(WarmSearch-uniapp)：uni-app + Vue.js
• 后端(WarmSearch)：Springboot 2.4.2 + Java Web Token +MybatisPlus + Swagger
• 数据库：MySql 5.7

项目地址 :link:

项目采用前后端分离开发模式，PC端使用:Vue + Element-ui, 小程序使用Uni-app开发，后端数据API采用Java、Spring-Boot开发.

PC端Code地址：github.com/Dorian1015/…

小程序端code地址：github.com/Dorian1015/…

后端code地址：github.com/Dorian1015/…

web管理端code地址: github.com/Dorian1015/…

体验地址

由于项目还在不断完善中，所以目前还未上线；

主要还是因为穷，买不起服务器

演示视频：在线演示视频

前言：

🏫本人目前（2021年5月8日）是一名大二在校大学生从去年（2020年)5月开始准备自学java，从基础到框架，利用课余时间从JavaWeb开始，到SSM,到SpringBoot,再到前端Html5,CSS3,JS,Vue.js,最后到Node.js，学完之后开始着手开始做这个校园失物招领网站，目前该项目大概原型已经呈现出来，这是基于前后端分离项目，目前利用课余时间，不断完善改项目。小白开始，若有错误，还望大家多多指教。各部分源码将在Github上持续更新。

这是我的邮箱lijinghailjh@163.com,欢迎大家来指正

最新代码将在GitHub上持续更新

在读大二学生（2021年5月8日）

说明

本项目前后端分离，前端(WarmSearch-PC）参考锤子商城

这是本项目的前台源码，后端源码请看WarmSearch,本项目包括后台管理系统(WarmSearch-Web)，前台系统（WarmSearch-PC)，微信小程序部分（WarmSearch-uniapp)

如果您觉得这项目还不错，可以在右上角Star支持一下，万分感谢！！！

项目简介

• 本项目前后端分离，前端基于Vue+Vue-router+Vuex+Element-ui+Axios，参考锤子商城实现。后端基于SpringBoot(框架) + JSON WEB TOKEN(令牌机制) + MybatisPlus + Mysql实现。
• 总体架构

系统设计秉承“前后端分离/SOA”的总体思想，前端使用Vue/ElementUI作为主要框架技术、Nginx作为HTTP服务器，用来提供静态页面访问服务和反向代理作用；后端则以Springboot主流框架技术为主、采用MySQL开源数据库，前后端使用Restful规范交换数据。

系统采用JWT令牌鉴权方式，降低服务器运行消耗，提升系统的伸缩性和扩展性。

• 总体架构

总体设计按“前后端分离”方式，当浏览器请求页面或静态资源时，HTTP Server直接响应；当浏览器请求数据时，该请求仍然先发给HTTP Server，经由该Server转发至Web APP Server。Web APP Server业务处理后将结果数据返回给HTTP Server，最终返回浏览器。在此过程中，Web APP Server返回的仅仅是数据（json格式），没有任何与显示（视图）相关的信息，做到了完全的前后端分离，前端负责页面与展示，后端负责业务处理与数据。

技术栈

• 前台页面展示系统（WarmSearch-PC)：Vue+Vue-router+Vuex+Element-ui+Axios
• 后台管理系统：基于Vue-admin-ui脚手架
• 微信小程序：uni-app + Vue.js
• 后端：Springboot + Java Web Token +MybatisPlus + Swagger 框架
• 数据库：MySql

功能模块

1.前台页面展示（WarmSearch-PC)

• WarmSearch-PC首页部分展示

• 物品详情页

• 寻失物部分页面展示

• 认领页面

• 信息发布页面

• 寻失主部分页面展示

• 捐赠部分页面展示

2.微信小程序页面(WarmSearch-uniapp)

• 登录页面

• 首页部分页面展示

• 寻物页面部分展示

3.后台管理系统(WarmSearch-web)

• 登录页面展示

• 首页页面展示

• 部分功能页面展示

后期打算

如果你觉得我的项目，还不错，可以给我一下赞赏，本人现是一名大二学生，打算不断完善这个项目，所以我打算购买服务器，并部署上去；开源不易，如果你喜欢我的项目，可以给我投资一下我的服务器基金，苦逼大学生，万分感谢您！！！！

如果你能看到这里说明你肯定对我的项目感兴趣，那么请访问我的博客吧，里面会更新更详细的关于我这个项目的信息 博客

或者你也可以通过我的Github 首页的邮箱来联系我 lijinghailjh@163.com

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

同学们好，我是王老师——二哥呀！（笑喷）

好巧！前几天有同学私信问过我这个问题：大学计算机专业，面临分专业，计科，软工，大数据，物联网，网络工程，该选什么？再加上高考结束后填报志愿，想必有很多同学挺迷茫的。

我就来（主观地）一一分析下，从后往前。

网络工程，听起来还算是蛮高端大气上档次的，大家可以去百度百科或者维基百科看一下这个专业的解释。我的理解是网络工程是将计算机以及其他设备串联完成网络通信，以及智能化监控的学科。主要的分支有：路由交换、网络安全、无线网络等等。

我之前在的一个公司（十年前了），一百多号开发，但就两三个网络专业的人才，他们很重要，一旦机房的网络出问题，都得靠他们解决。嗯，说句“心怀鬼胎”的话，平常我们最喜欢的一件事就是网络出问题，或者公司断电，嗯，天赐的“摸鱼好时机”。当然了，这种机会不多，这两三位同事总是能在最短的时间内把问题解决掉。

物联网，也简称为 IoT，是近些年比较火的一个概念，是指将日常的物理对象连接到互联网的过程——从医疗设备，到可穿戴设备，小到智慧家居，大到智慧城市。

先说说我家的情况吧，比较常用的智能设备有两个，一个是扫地机器人，需要地面墙角比较规整一点才能比较顺利地完成清洁工作；一个是小夜灯，人经过的时候就亮起来，过一会自己就灭了，但经常夜里翻个身它就亮了，还有点“智障”。

相对来说，物联网还有很大的发展空间，比如智慧交通，再比如智慧农业，具体点的例子就是通过湿度传感器来自动触发灌溉等。

大数据，也就是 Big Data，我了解到的适用于大数据的技术有：分布式文件系统、分布式数据库、云计算平台、可扩展的存储系统等。奥巴马曾说“大数据”是未来的石油，可见其重要性。

大数据专业是典型的交叉学科，不仅涉及到计算机，还会涉及到数学和统计学，不仅对学校的学科实力有要求，对个人的硬性基本功也是有要求的。

软件工程专业是以计算机科学为基础的，更加强调软件开发的工程性，包括软件需求分析、软件设计、软件测试、软件维护和软件项目管理等。

计算机科学，也就是计科（Computer Science，简称 CS），不仅会研究计算机的硬件，也会研究计算机的软件，更具体的主题包括编程语言、程序设计等。

先插个楼，开局一张图：计科最佳指南。

我之前读过邹欣大佬（目前是 CSDN 副总裁）的一本书——《构建之法》，第一章就对软件工程和计算机科学的关系做了解释，它们开设的课程很相似，但本质上它俩是完全不同的。

计算机科学这一学术领域可以分为：计算机理论、信息和编码理论、算法和数据结构、形式化方法、编程语言等。

偏实践的领域：计算机体系结构（或者叫计算机组成原理）、操作系统、计算机网络、安全性和密码学、人工智能、计算机图形学、人机交互、嵌入式系统和软件工程。

按照武侠小说来讲，计算机科学更像是九阳神功、乾坤大挪移这种顶级内功；而软件工程更像是七伤拳、龙抓手、太极拳法等武功招式。在内功浑厚的基础上，武功招式就可以打出最大的伤害值。

另外还有一种比较功利性的说法：如果打算本科毕业后就参加工作，可选软件工程，如果打算考研进修，可选计算机科学。

不过，在我看来，无论选择计算机科学还是软件工程，大部分同学最终的选择都是做一名软件工程师。（落脚点还是很实在，增删改查嘛，hhh）

当然了，软件工程师可以分为两种：一种是充分理解了计算机科学，从而有能力应对充满挑战的创造性工作；另一种仅仅凭着对一些高级工具或者框架的熟悉而勉强应付。

第一种工程师能随着时间的流逝，不停地成长，最终成为技术大牛；而第二种工程师往往浮于表面，只学习某些特定的工具和技术，而不研究底层的原理，慢慢就会停滞不前。

我个人的总结就是，软工的内核还是计科，计科学得好，软工、大数据、物联网、网络工程都是可以自如应对的。

接下来就很重要了！怎么才能好学计科呢？怎么才能成为别人眼中的大牛呢？

先说理论。

如果你要学习物理，我推荐你顺着物理的发展史学习，先学习牛顿的经典物理，再学习热力学、电磁学，然后学习相对论、量子力学这些彻底推翻经典物理的，最后学习电动力学这种硬核的。

整个学习过程，是自底向上的。学计科也要这样吗？

先学习电路，然后学习冯诺依曼结构，造一台计算机？接着再学习如何用汇编写个 mini os？接着学习如何写一个简易版的编译器？最后再学习高级编程语言，比如说 Java、Python、C++？

显然这样是行不通的！计算机科学的学习最好是自顶向下。

什么是顶？在我看来，就是一门高级的编程语言，比如说 Java、C++ 或者 Python。我个人从事 Java 后端开发的时间比较久，所以还是拿老本行来说。

当你学习到 Java 并发编程中的“原子性”、“同步”、“异步”、“进程”、“内存分配”这些概念的时候，你自然而然会产生很多疑问，然后就会去学习操作系统，学习计算机组成原理，然后你的一系列问题就会逐渐被解决。

当你在学习 Java 的时候遇到性能问题时，你就会去研究，啊，原来 Java 是一门解释型的编程语言，而 C 语言是一门编译型的编程语言，所以 Unix/Linux 这种操作系统要用 C 语言来实现，因为要最大限度的压榨硬件的瓶颈。

当然了，Java 为了提升自身的性能也是费尽心思，比如说即时编译（JIT，Just-In-Time）通过在运行时将字节码编译为本机机器代码来提高性能；比如说垃圾回收机制的升级，从 GC 到 ZGC，GC 的痛点在于垃圾回收期间，所有的线程都会停止活动，等待 STW（Stop The World）的结束，而 ZGC 在标记、转移和重定位阶段几乎都是并发的，大大缩短了停顿的时间。

跑偏了，继续来说。

当你用 Java 实现某个业务需求时，发现人家的算法实现比你快得多，你自然会好奇，为什么会这样？然后你发现人家用的数据结构和你的不同，接着你就会去学习数据结构，再了解一些高效的算法，比如动态规划等。

你看，从学 Java 的语法开始，你一步步学到了操作系统、计算机组成原理、数据结构与算法。

跟着需求去学习，才能真正学好计算机科学。

我也会给你推荐《CSAPP》这本黑皮书，毕竟永远的神，但如果你没有编程基础就去啃，你可能很快就会被劝退的；反而，一开始，你读一读我写的《教妹学Java》，或者去 B 站上看尚硅谷或者动力节点这些培训机构的 Java 视频课，没准你会越学越觉得有信心——这么简单的东西，我这么聪明，还能学不会？你会有这种自信的错觉的！

反而一开始去啃 CSAPP，你会感觉，老天！我特么是个废材啊，我学的什么鬼玩意，这竟然看不懂，学不会？

你可能要问，编程语言有很多种，Java、Python、C/C++、Go、JavaScript 等等，选哪一个呢？

选择 Java 吧，常听人说“人生苦短，我用 Python”；选择 Python 吧，常听人说“Go 是 Google 的亲儿子，发展势头正劲”；选择 Go 吧，常听人说“前端（JavaScript 必学）更容易学习一些”；选择 JavaScript 吧，常听人说“C/C++ 具备现代程序设计的基础要求，是很多编程语言的基础。”

然后就又麻了！

我是从大一就开始学习的 Java，当时没有选择，因为不知道还有其他编程语言（嘘），学校让学 Java 就学了 Java。只能说非常的幸运，选对了。

那么同学们也不需要纠结，前端、Java、Python、C++/C，到底怎么选？学校安排啥就学啥，如果学校没安排，那么选 Java 可能是最朴实无华的选择，因为综合（就业岗位和薪资）考虑的话，Java 是其他编程语言无法替代的。

当然了，你也可以选择 C 语言，这也是一个无法反驳的选择，C 语言是其他很多编程语言的基石，学了这个，再学其他任何一门编程语言都是很好的基础，只不过，指针这块确实令人头痛！

选择一门编程语言后，踏踏实实地去学习，就会连根拔起很多其他方面的内容，比如说数据库、数据结构与算法、计算机组成原理、操作系统、计算机网络等等。

• 那 C 语言该怎么学呢？
• 那 Java 该怎么学呢？
• 那数据库该怎么学呢？
• 那数据结构与算法该怎么学呢？
• 那计算机组成原理该怎么学呢？
• 那操作系统该怎么学呢？
• 那计算机网络该怎么学呢？

一个一个来解决。

C 语言：

推荐翁恺教授的《C 语言程序设计》，B 站地址：

www.bilibili.com/video/BV19W…

Java：

你可以先看看我整理的这份 GitHub 上星标 115k+ 的 Java 教程，里面涵盖了 Java 所有的知识点，包括 Java 语法、Java 集合框架、Java IO、Java 并发编程和 Java 虚拟机，内容不多，只讲重点。

GitHub 星标 115k+的 Java 教程，超级硬核！

数据库：

• 《SQL 必知必会》
• 《高性能 MySQL》
• 《MySQL技术内幕-InnoDB存储引擎》
• 《Redis 深度历险：核心原理与应用实践》

数据结构与算法：

• 《算法 4》
• 吃完 300 道 LeetCode 题后，我胖得快炸了

计算机组成原理：

• 《计算机是如何跑起来的》
• 《CSAPP》，也就是《深入理解计算机系统》

操作系统：

• 龙书《操作系统概念》
• 《现代操作系统》

计算机网络：

• 网络是怎样连接的
• 图解 HTTP
• 图解TCP/IP
• TCP/IP详解 卷1：协议

你可能要问，一定要按照这个次序吗？

答案是可以不按照，但我这里有 3 个重要的“先决条件”：

• 你最好先从一门编程语言开始，然后不断纵向和横向扩展；
• 你最好先学计算机组成原理再学操作系统；
• 你最好先学计算机网络和操作系统再学分布式系统；

限于篇幅的原因，学习资源我这里没法列全。

但考虑到同学们的诉求，我上周末花了两天的时间，整理了一份 CS 自学指南，里面囊括了所有我认为值得推荐给大家的学习资料（有书、有视频、有公开课、有在线文档），这些学习资料不用怀疑，我都看过，虽然有些没有看完，已经在 GitHub 上开源了。

github.com/itwanger/Le…

你可以大致按照我列出的顺序，借助我推荐的教材和视频课程，最好是两者兼顾，然后花 100-200 个小时去学完每一个科目，然后在之后的程序生涯里，不断重温这些精华，你会来感谢我的！

要把这些内容全部学完，当然是需要花时间的，不可能一朝一夕就能完成，大学期间可能完全学不完，即便是工作几年后仍然可能学不完，但相信我，你会在这条路上得到快乐，得到满足的。

还有什么比学习更重要的事情呢？

如果有，那就是给二哥点个赞，来个三连了！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

这是我参与更文挑战的第14天，活动详情查看： 更文挑战

首先分享之前的所有文章 , 欢迎点赞收藏转发三连下次一定 >>>> 😜😜😜

文章合集 : 🎁 juejin.cn/post/694164…

Github : 👉 github.com/black-ant

一 .前言

之前分别介绍了 Seata 的启动和配置 , 这一篇来看一下 Client 端的启动过程 :

盘点 Seata : Seata Server 启动流程

盘点 Seata : Seata Server 配置流程

盘点 Seata : Client 端配置流程

Seata 的事务发起其实可以分为2个阶段 , 第一阶段是 Client 发起 Request , 第二阶段是 Server 端对 Request 进行处理 , 以及创建 TX 对象等 , 这一篇先来看一下 Seata Client 端发起流程 , 下面来详细看一下 :

1.1 Seata AT 模式的主流程梳理

Seata 中存在三个角色 :

1
2
3
4
5
6
7
8

java复制代码// TC (Transaction Coordinator) - 事务协调者 
维护全局和分支事务的状态，驱动全局事务提交或回滚。

// TM (Transaction Manager) - 事务管理器 
定义全局事务的范围：开始全局事务、提交或回滚全局事务。

// RM (Resource Manager) - 资源管理器
管理分支事务处理的资源，与TC交谈以注册分支事务和报告分支事务的状态，并驱动分支事务提交或回滚。

1.2 主要流程梳理

不说废话 , 流程图就在这 , 能看懂 , 就可以不看下文了(PS : 还不是很详细 , 后面再完整的补充) :

以下流程主要参考官方文档 , 只做个总结 , 整个流程分为2个阶段 :

针对语句 : update product set name = 'GTS' where name = 'TXC';

一阶段

1. 解析 SQL：得到 SQL 的类型（UPDATE），表（product），条件（where name = ‘TXC’）等相关的信息。
2. 查询前镜像 : 根据解析得到的条件信息，生成查询语句，定位数据。
3. 执行业务 SQL：更新这条记录的 name 为 ‘GTS’。
4. 查询后镜像：根据前镜像的结果，通过 主键 定位数据。
5. 插入回滚日志：把前后镜像数据以及业务 SQL 相关的信息组成一条回滚日志记录，插入到 UNDO_LOG 表中。
6. 提交前，向 TC 注册分支：申请 product 表中，主键值等于 1 的记录的 全局锁 。
7. 本地事务提交：业务数据的更新和前面步骤中生成的 UNDO LOG 一并提交。
8. 将本地事务提交的结果上报给 TC。

二阶段 : 提交

1. 收到 TC 的分支提交请求，把请求放入一个异步任务的队列中，马上返回提交成功的结果给 TC。
2. 异步任务阶段的分支提交请求将异步和批量地删除相应 UNDO LOG 记录。

1.3 GlobalLock 介绍

声明事务只在单个本地RM中执行，但是事务需要确保要更新(或选择更新)的记录不在全局事务的中间阶段

1
2
3
4
5
6
7
8
9
10
11

java复制代码public @interface GlobalLock {
    /**
     * 自定义全局锁重试间隔(单位:ms)
     */
    int lockRetryInternal() default 0;

    /**
     * 自定义的全局锁重试次数
     */
    int lockRetryTimes() default -1;
}

1.4 GlobalTransactional 介绍

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

java复制代码@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.METHOD,ElementType.TYPE})
@Inherited
public @interface GlobalTransactional {

    /**
     * 全局事务超时mills(毫秒)
     */
    int timeoutMills() default DefaultValues.DEFAULT_GLOBAL_TRANSACTION_TIMEOUT;

    /**
     * 全局事务实例的给定名称
     */
    String name() default "";

    /**
     * 回滚到指定class
     */
    Class<? extends Throwable>[] rollbackFor() default {};

    /**
     * 回滚的 Class 类名
     */
    String[] rollbackForClassName() default {};

    /**
     * 不回滚的指定类
     */
    Class<? extends Throwable>[] noRollbackFor() default {};

    /**
     * 不回滚的指定类名
     */
    String[] noRollbackForClassName() default {};

    /**
     * 全局事务的传播
     */
    Propagation propagation() default Propagation.REQUIRED;

    /**
     * 自定义全局锁重试间隔(单位:ms)
     */
    int lockRetryInternal() default 0;

    /**
     * 自定义的全局锁重试时间
     */
    int lockRetryTimes() default -1;
}

二 . Client 事务的发起

事务的发起是有 TM 开始 , 然后由 RM 完成事务分支 , 看一下主要的流程 :

整个流程这一次只说前面2步 :

• Interceptor 对操作进行拦截
• TransactionalTemplate 处理事务整体流程

看一下类流程 :

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

java复制代码//  TM 流程一 ：注解处理阶段 , 此阶段方法上标注注解 , 将创建一个新的事务
GlobalTransactionalInterceptor # invoke : 拦截器拦截被代理的方法
GlobalTransactionalInterceptor # handleGlobalTransaction : 注解处理详情
TransactionalTemplate # execute : 事务处理主流程
TransactionalTemplate # beginTransaction : 开启事务主流程
DefaultGlobalTransaction # begin : 调用 API 流程
DefaultTransactionManager # begin : 调用 API 实际流程
    
    
// App A RM 流程一 : 此方法中创建 Proxy 的 Statement 类
PreparedStatementHandler # instantiateStatement
PreparedStatementProxy # PreparedStatementProxy() : 构造器构建 StatementProxy

// App A RM 流程二 : 代理执行方案
ExecuteTemplate # execute 
BaseTransactionalExecutor # execute(Object... args)
AbstractDMLBaseExecutor # doExecute(Object... args)
AbstractDMLBaseExecutor # executeAutoCommitTrue(Object[] args)
AbstractDMLBaseExecutor # executeAutoCommitFalse(Object[] args)
ConnectionProxy # doCommit()
ConnectionProxy # processGlobalTransactionCommit()

// App A RM 流程三 : 调用实际Connect执行
DruidPooledConnection # commit() : 因为使用的 Druid 连接池 , 此处为 DruidPooledConnection
	?- 此处将会提交 commit

2.1 注解的入口

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

java复制代码// 注解的扫描方式 : 
@GlobalTransactional(timeoutMills = 300000, name = "dubbo-gts-seata-example")

// Step 1 : 核心扫描类 GlobalTransactionScanner

// 先看一下该类的继承体系
C01- GlobalTransactionScanner
    E- AbstractAutoProxyCreator : Aop 代理 -> PS:C01_001
    I- ConfigurationChangeListener : -> PS:C01_002
    I- InitializingBean : 意味着会初始化运行
    I- ApplicationContextAware : ApplicationContext 运行时被通知 
    I- DisposableBean : 销毁 Bean 时会处理

PS:C01_001 AbstractAutoProxyCreator 作用
简单点说 , 就是为这个类做了代理 . 使用AOP代理包装每个合格bean的BeanPostProcessor实现，在调用bean本身之前将委托给指定的拦截器。

GlobalTransactionScanner 详情

详见 Client 配置 >>>> Client端配置流程

2.2 注解的拦截

通常方法上标注注解来实现某种功能 , 其最终原理都是代理 , 不论是Java 原生得 Proxy 类创建的 , 还是 Aop 实现的 , 其核心是一致的.

Step 1 : 代理的方式

此处使用的代理是 CglibAopProxy

Step 2 : 调用的流程

第一个调用的对象为 GlobalTransactionalInterceptor , 由其 invoke 方法完成了相关的代理操作

PS : 我原本以为框架会优先扫描所有的标注了 @GlobalTransactional 的方法 , 并且通过相关的Manager 进行管理 , 但是单独看这一处的代码 , 采用的是代理后直接获取的方式

GlobalTransactionalInterceptor # invoke 主流程

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

java复制代码// 先来纵观一下 invoke 方法主流程
C50- GlobalTransactionalInterceptor
    I- MethodInterceptor
    M50_01- invoke(final MethodInvocation methodInvocation)
    	- 通过 MethodInvocation 解析目标 class
    	- 通过 ClassUtils 解析目标 Method
    	- 通过 findBridgedMethod 找到原始方法 ->  PS:M50_01_01
    	- 获得原始方法的 GlobalTransactional 注解
    	- 获得原始方法的 GlobalLock 注解
    	- 如果GlobalTransactional 注解存在 , 则执行 globalTransactionalAnnotation
    	- 如果 GlobalLock 存在且 GlobalTransactional 不存在 , 则执行 handleGlobalLock
            ?- 注意 , 这里优先执行了 globalTransactionalAnnotation

GlobalTransactionalInterceptor 其他主要方法

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

java复制代码            
// PS : 此处随便来看一下其他的方法 
M- initDefaultGlobalTransactionTimeout
            
            
M- 支持配置 Configuration 变动加载
    public void onChangeEvent(ConfigurationChangeEvent event) {
        if (ConfigurationKeys.DISABLE_GLOBAL_TRANSACTION.equals(event.getDataId())) {
            disable = Boolean.parseBoolean(event.getNewValue().trim());
        } else if (ConfigurationKeys.CLIENT_DEGRADE_CHECK.equals(event.getDataId())) {
            degradeCheck = Boolean.parseBoolean(event.getNewValue());
            if (!degradeCheck) {
                degradeNum = 0;
            }
        }
    }



M- handleGlobalLock
M- handleGlobalTransaction
    
// 注意 , 该方法中就会调用 transactionalTemplate 完成主要逻辑
Object handleGlobalTransaction(final MethodInvocation methodInvocation,
        final GlobalTransactional globalTrxAnno) throws Throwable {
        boolean succeed = true;
        try {
            // 核心 , 调用 Template , 同时构建了一个 TransactionalExecutor 传入
            // TransactionalExecutor 为 template 中具体执行的方法 , 即 executor 的对象
            return transactionalTemplate.execute(new TransactionalExecutor() {
                @Override
                public Object execute() throws Throwable {
                    // 此处是对应的方法代理 , 用于执行具体的对象 -> PRO22001
                    return methodInvocation.proceed();
                }

                public String name() {
                    String name = globalTrxAnno.name();
                    if (!StringUtils.isNullOrEmpty(name)) {
                        return name;
                    }
                    return formatMethod(methodInvocation.getMethod());
                }

                // 该方法用于tempalte 中调用 事务信息
                @Override
                public TransactionInfo getTransactionInfo() {
                    // reset the value of timeout
                    int timeout = globalTrxAnno.timeoutMills();
                    if (timeout <= 0 || timeout == DEFAULT_GLOBAL_TRANSACTION_TIMEOUT) {
                        timeout = defaultGlobalTransactionTimeout;
                    }
                    
                    // 构建了当前的事务信息
                    TransactionInfo transactionInfo = new TransactionInfo();
                    transactionInfo.setTimeOut(timeout);
                    transactionInfo.setName(name());
                    transactionInfo.setPropagation(globalTrxAnno.propagation());
                    transactionInfo.setLockRetryInternal(globalTrxAnno.lockRetryInternal());
                    transactionInfo.setLockRetryTimes(globalTrxAnno.lockRetryTimes());
                    Set<RollbackRule> rollbackRules = new LinkedHashSet<>();
                    
                    // 构建了回退的方法以及无需回退的方法
                    for (Class<?> rbRule : globalTrxAnno.rollbackFor()) {
                        rollbackRules.add(new RollbackRule(rbRule));
                    }
                    for (String rbRule : globalTrxAnno.rollbackForClassName()) {
                        rollbackRules.add(new RollbackRule(rbRule));
                    }
                    for (Class<?> rbRule : globalTrxAnno.noRollbackFor()) {
                        rollbackRules.add(new NoRollbackRule(rbRule));
                    }
                    for (String rbRule : globalTrxAnno.noRollbackForClassName()) {
                        rollbackRules.add(new NoRollbackRule(rbRule));
                    }
                    transactionInfo.setRollbackRules(rollbackRules);
                    return transactionInfo;
                }
            });
        } catch (TransactionalExecutor.ExecutionException e) {
            TransactionalExecutor.Code code = e.getCode();
            // 通过 Failure 类型调用failureHandler不同的处理方法
            switch (code) {
                case RollbackDone:
                    throw e.getOriginalException();
                case BeginFailure:
                    succeed = false;
                    failureHandler.onBeginFailure(e.getTransaction(), e.getCause());
                    throw e.getCause();
                case CommitFailure:
                    succeed = false;
                    failureHandler.onCommitFailure(e.getTransaction(), e.getCause());
                    throw e.getCause();
                case RollbackFailure:
                    failureHandler.onRollbackFailure(e.getTransaction(), e.getOriginalException());
                    throw e.getOriginalException();
                case RollbackRetrying:
                    failureHandler.onRollbackRetrying(e.getTransaction(), e.getOriginalException());
                    throw e.getOriginalException();
                default:
                    throw new ShouldNeverHappenException(String.format("Unknown TransactionalExecutor.Code: %s", code));
            }
        } finally {
            if (degradeCheck) {
                EVENT_BUS.post(new DegradeCheckEvent(succeed));
            }
        }
    }

[PRO22001] : methodInvocation 详情

[PRO22002] : TransactionInfo 详情

总结 :

从此处可以看到 , 在GlobalTransactionalInterceptor 拦截器中 , 首先调用了 template 方法 , 同时把 executor 需要执行的具体方法传入 , 而 method 通过 invoke 代理调用

另外 , 处理异常是在 拦截器 中执行 ,而不是 Template 的模板类型

三 . Client 事务的逻辑处理

Client 的事务处理为 TransactionalTemplate 模板方法来完成 , 来看一下 TransactionalTemplate 的功能

上一步当拦截器拦截完成后 , 就会来到 template 处理环节 , 该环节最核心的类为 : TransactionalTemplate , 这一步是模板方法设计模式 , 这一步中会调用 TransactionalExecutor 执行最终的逻辑

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

java复制代码C51- TransactionalTemplate
	M51_01- execute 
        
// 注释已经很清楚了,  就喜欢这种源码 , 清清楚楚 , 直译一下就知道流程了
public Object execute(TransactionalExecutor business) throws Throwable {
     // 1. 获取 transactionInfo
     TransactionInfo txInfo = business.getTransactionInfo();
     if (txInfo == null) {
           throw new ShouldNeverHappenException("transactionInfo does not exist");
     }
     // 1.1 获取当前 transaction, 如果不为空，tx role 为 'GlobalTransactionRole.Participant'.
     GlobalTransaction tx = GlobalTransactionContext.getCurrent();

     // 1.2 事务传播处理 -> PS:M51_01_01
     Propagation propagation = txInfo.getPropagation();
     SuspendedResourcesHolder suspendedResourcesHolder = null;
     try {
           switch (propagation) {
                case NOT_SUPPORTED:
                     // 如果事务存在，则暂停它.
                     if (existingTransaction(tx)) {
                           suspendedResourcesHolder = tx.suspend();
                     }
                     // 在没有事务的情况下执行并返回.
                     return business.execute();
                case REQUIRES_NEW:
                     // 如果事务存在，暂停它，然后开始新的事务.
                     if (existingTransaction(tx)) {
                           suspendedResourcesHolder = tx.suspend();
                           tx = GlobalTransactionContext.createNew();
                     }
                     // 继续并使用新事务执行
                     break;
                case SUPPORTS:
                     // 如果事务不存在，则不执行事务.
                     if (notExistingTransaction(tx)) {
                           return business.execute();
                     }
                     // 继续并使用新事务执行
                     break;
                case REQUIRED:
                     // 如果当前事务存在，则使用当前事务执行，否则继续并使用新事务执行
                     break;
                case NEVER:
                     // 如果事务存在，抛出异常.
                     if (existingTransaction(tx)) {
                           throw new TransactionException(
                                String.format("Existing transaction found for transaction marked with propagation 'never', xid = %s"
                                           , tx.getXid()));
                     } else {
                           // 在没有事务的情况下执行并返回.
                           return business.execute();
                     }
                case MANDATORY:
                     // 如果事务不存在，抛出异常.
                     if (notExistingTransaction(tx)) {
                           throw new TransactionException("No existing transaction found for transaction marked with propagation 'mandatory'");
                     }
                     // 继续并执行当前事务.
                     break;
                default:
                     throw new TransactionException("Not Supported Propagation:" + propagation);
           }

           // 1.3 如果当前 GlobalTransaction 为 null , 使用 role 'GlobalTransactionRole.Launcher' 创建一个新的 Transaction.
           if (tx == null) {
                tx = GlobalTransactionContext.createNew();
           }

           // 设置当前tx配置为holder
           GlobalLockConfig previousConfig = replaceGlobalLockConfig(txInfo);

           try {
                // 2. 如果当前 tx(GlobalTransaction) role 为 'GlobalTransactionRole.Launcher', 发送beginTransaction的请求到TC,
                //  否则不做任何事. 不过 , hooks 始终会被触发.
                beginTransaction(txInfo, tx);

                Object rs;
                try {
                     // 执行业务
                     rs = business.execute();
                } catch (Throwable ex) {
                     // 3. 回滚所需的业务异常.
                     completeTransactionAfterThrowing(txInfo, tx, ex);
                     throw ex;
                }

                // 4. 一切正常后 , 提交事务.
                commitTransaction(tx);

                return rs;
           } finally {
                //5. 清空事件
                resumeGlobalLockConfig(previousConfig);
                triggerAfterCompletion();
                cleanUp();
           }
     } finally {
           // 如果事务挂起，则恢复它.
           if (suspendedResourcesHolder != null) {
                tx.resume(suspendedResourcesHolder);
           }
     }
}


// PS:M51_01_01 Propagation 是什么对象 , 有什么作用 ?

可以看到 , 这个中已经把整个事务处理的主流程完成了

接上一小结 , 当执行 business.execute() 后出现异常 , 会在 execute 中处理 , 而 Template 中 , 主要是对事务的管理和回退等操作 , 这也是使用模板方法设计模式的核心 , 只涉及统一的逻辑

总结

这一篇我们看到了 Seata 逻辑的发起流程 ,可以看到 ,通过以下几个步骤发起了事务的处理 :

• beginTransaction(txInfo, tx)
• business.execute()
• completeTransactionAfterThrowing(txInfo, tx, ex)
• commitTransaction(tx)

后面一篇我们来看一下后面这几个步骤做了什么>>> 👉

附录 . 补充点

读隔离和写隔离可以参考官方文档 👉 Seata 隔离策略

4.1 读隔离详情

Seata（AT 模式）的默认全局隔离级别是 读未提交（Read Uncommitted） , 其通过 SELECT FOR UPDATE 实现

流程详情

• SELECT FOR UPDATE 语句的执行会申请 全局锁
• 如果 全局锁 被其他事务持有，则释放本地锁（回滚 SELECT FOR UPDATE 语句的本地执行）并重试 (意味着会一直等待正在的全局提交完成)

这个过程中，查询是被 block 住的，直到 全局锁 拿到，即读取的相关数据是 已提交 的，才返回

PS : 这里产生了疑问 , 如果插入比较多的情况 , 会导致全局锁一直被占用或者频繁占用 , 所以这里还是要做读写分离

4.2 写隔离详情

写隔离是保证事务统一的关键 , 其中涉及到全局锁和本地锁的特性 , 为了保证准确 , 使用如下模式 :

1,2 分别代表2个事务 :

一阶段提交流程

1. 开启本地事务 , 拿到本地锁 ,再拿到 全局锁 , 提交本地事务 , 释放本地锁 (PS :此时始终持有全局锁)
2. 其他事务提交 , 开启本地事务 , 拿到本地锁 ,等待全局锁 (PS :此时上一个事务持有全局锁)

二阶段成功提交流程

1. 全局处理完成 , 释放全局锁
2. 其他事务 拿到全局锁 , 按照原流程处理

二阶段回退流程 (如果出现异常导致 1 事务回退)

1 . 发生异常 , 尝试回退 , 等待本地锁 (PS : 因为本地锁被其他事务持有)

2 . 始终无法拿到全局锁 , 本地事务回退 , 释放本地锁

1 . 拿到 本地锁 ,完成回退

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

进入我的网站获得最佳阅读体验

开发过程中，在本地启动系统来进行一些测试、联调是很日常的操作。然而随着项目不断壮大，系统内会依赖越来越多的中间件或服务，例如 Rocket MQ、Dubbo、定时任务等。在系统启动的时候，需要对这些组件进行初始化，导致启动过程缓慢无比。

系统启动 5 分钟，测试运行 3 秒钟，这谁顶得住啊。而且在本地测试时，通常也用不到这些组件。

如果你也有同样的困扰，接下来就教你一招，利用 Spring 的扩展点 BeanFactoryPostProcessor，无侵入地“阉割”这些拖慢启动时间的组件，让你的系统一键弹射起步。

我们就以 Rocket MQ 为例，在启动的时候加载 5 个消费者。

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

java复制代码public class RocketMQConfiguration {

    /**
     * SpringBoot 启动时加载所有消费者
     */
    @PostConstruct
    public void initConsumer() {
        Map<String, AbstractRocketConsumer> consumers = applicationContext.getBeansOfType(AbstractRocketConsumer.class);
        if (CollectionUtils.isEmpty(consumers)) {
            log.info("no consumers");
        }
        for (String beanName : consumers.keySet()) {
            AbstractRocketConsumer consumer = consumers.get(beanName);
            consumer.init();
            createConsumer(consumer);
            log.info("init consumer: title {} , topics {} , tags {}", consumer.consumerTitle,
                    consumer.topics, consumer.tags);
        }
    }
    
}

运行一下测试类，系统启动耗时 30 秒，其中 Bean 的初始化过程就占了 28 秒。

这里计算 Bean 初始化耗时的方式，是使用了 BeanPostProcessor 的前后扩展点，收集所有 Bean 在初始化前后的时间点，用最大时间减去最小时间，来计算整个过程的耗时。

接下来我们就利用 BeanFactoryPostProcessor 这个扩展点，缩短初始化的时间。

首先回顾一下 Spring 初始化 Bean 的过程，大体上可以划分为解析配置，初始化 BeanFactory，注册 BeanDefinition，注册 BeanPostProcessor，然后初始化所有的单例 Bean，最后执行 BeanPostProcessor 的回调方法。

如果你熟悉 Spring 的源码，这段逻辑就在 org.springframework.context.support.AbstractApplicationContext#refresh 里，细看一下这段过程，其中会执行 invokeBeanFactoryPostProcessors(beanFactory) 方法，而 BeanFactory 里保存了所有 bean 的定义，也就是 BeanDefinition。之后，Spring 就是根据这些 BeanDefinition 来初始化对应的 bean。

因此，我们就可以自定义一个 BeanFactoryPostProcessor ，也就是在 bean 进行初始化之前，使用一招“狸猫换太子”，悄悄删除一些不需要的 BeanDefinition，这样，Spring 就不会初始化这些 bean 了。你也可以根据需要和实际情况，做一些针对性的处理。

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
28
29
30
31
32
33
34
35
36
37
38
39

java复制代码public class SpringTestLaunchControl implements BeanFactoryPostProcessor {

    private static final Set<String> EXCLUDE_BEAN_CLASSES = Sets.newHashSet(
            "co.lilpilot.springtestfield.mq.Consumer1",
            "co.lilpilot.springtestfield.mq.Consumer2",
            "co.lilpilot.springtestfield.mq.Consumer3",
            "co.lilpilot.springtestfield.mq.Consumer4",
            "co.lilpilot.springtestfield.mq.Consumer5"
            );

    private static final Set<String> ANNOTATION_BEAN_CLASSES = Sets.newHashSet();

    @Override
    public void postProcessBeanFactory(ConfigurableListableBeanFactory beanFactory) throws BeansException {
        DefaultListableBeanFactory defaultBeanFactory = (DefaultListableBeanFactory) beanFactory;

        ArrayList<String> definitionNames = Lists.newArrayList(defaultBeanFactory.getBeanDefinitionNames());

        for (String definitionName : definitionNames) {
            BeanDefinition beanDefinition = defaultBeanFactory.getBeanDefinition(definitionName);
            String beanClassName = beanDefinition.getBeanClassName();
            // 根据类名移除 BeanDefinition
            if (EXCLUDE_BEAN_CLASSES.contains(beanClassName)) {
                defaultBeanFactory.removeBeanDefinition(definitionName);
            }
            // 根据注解移除 BeanDefinition
            if (beanDefinition instanceof ScannedGenericBeanDefinition) {
                ScannedGenericBeanDefinition scannedGenericBeanDefinition = (ScannedGenericBeanDefinition) beanDefinition;
                AnnotationMetadata metadata = scannedGenericBeanDefinition.getMetadata();
                for (String annotationBeanClass : ANNOTATION_BEAN_CLASSES) {
                    if (metadata.hasAnnotation(annotationBeanClass)) {
                        defaultBeanFactory.removeBeanDefinition(definitionName);
                    }
                }
            }
        }
    }

}

在 BeanFactoryPostProcessor 中，获得 BeanFactory，然后自定义一些匹配规则，移除掉 factory 里的 BeanDefinition。

最后我们在测试类中配置上这个 processor，仅针对测试时才有效，不会影响系统正常启动。

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

java复制代码@SpringBootTest
class SpringTestFieldApplicationTests {

    @TestConfiguration
    static class MyConfig {
        @Bean
        public BeanFactoryPostProcessor beanFactoryPostProcessor() {
            return new SpringTestLaunchControl();
        }
    }

}

来重新运行一下测试，看看效果。

好家伙，系统启动仅用时 5 秒，Bean 的初始化缩减到了 3 秒（说明 MQ 消费者的初始化是真滴慢），弹射起步！

总结一下，本文中，利用 BeanFactoryPostProcessor 这个扩展点，移除了测试过程中所不需要的一些 bean，从而缩短了系统启动时间，而且仅针对测试启动环境有效，对系统正常启动无侵入。

希望有帮助到你。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

@Autowired和@Resource都可以用于来实现依赖注入，但前者是Spring提供的，后者为JDK（JSR-250标准）自带的。阿里Java开发规范中推荐使用@Resource。但大多数人往往并没有留意为何如此，甚至代码中的提示信息可能都没留意去看。

本文就带大家彻底了解一下这两个注解的功能、运用场景及区别。

IDE的提示

如果在项目中使用@Autowired进行注入，如下代码：

1
2
3
4
5

kotlin复制代码@RestController
public class InjectController {
    @Autowired
    private ConnectService connectService;
}

会有这样的提示信息：

1
2

csharp复制代码Field injection is not recommended 
Inspection info: Spring Team recommends: "Always use constructor based dependency injection in your beans. Always use assertions for mandatory dependencies".

翻译过来就是：字段注入是不推荐的，Spring团队建议：“始终在bean中使用基于构造函数的依赖项注入。始终对强制性依赖项使用断言”。

根据提示，我们来重新写一种注入方式：

1
2
3
4
5
6
7
8
9
10

typescript复制代码@RestController
public class InjectController {

    private ConnectService connectService;

    @Autowired
    public void setConnectService(ConnectService connectService) {
        this.connectService = connectService;
    }
}

上面将@Autowired的注解使用在了setter方法上，此时提示消失了。再看另外一种注入方式：

1
2
3
4
5
6
7
8
9
10

kotlin复制代码@RestController
public class InjectController {

    private ConnectService connectService;

    @Autowired
    public InjectController(ConnectService connectService) {
        this.connectService = connectService;
    }
}

此种方式将@Autowired的注解使用在了构造方法上，与Spring团队的建议一致。此时，也不会再出现警告信息。

也就是说IDE提示的信息并不是说不建议大家使用@Autowired注解，而且不要直接使用在字段（Field）上。

Spring注入的方式及场景

Spring常见的DI方式：构造器注入、Setter注入、字段注入。显然，我们经常使用的方式并不是官方最推荐的。

而上面三种注入方式所适用的场景也是有所区别的：1、构造器注入适用具有强依赖和不变性的依赖；2、Setter注入适用于具有可选性和可变性的依赖注入；3、Field注入，尽量少使用，如果需要则使用@Resource进行替代，以降低耦合性。

Field注入的缺点

Field注入的缺点很明显，比如不能像构造器注入那样注入不可变的对象，依赖对外部不可见（构造器和Setter可见，而private的属性不可见），会导致组件与IoC容器（比如Spring）紧密耦合，单元测试也需要使用IoC容器，依赖过多时相对构造器注入不能够明显的看出依赖过多（违反单一职责原则）。

既然Field注入这么多缺点，但为什么大家还是习惯使用呢？主要原因：太方便了，极大的缩减了代码。而且大多数业务并不需要用构造器强绑定，同时换IoC容器的可能性也极低。所以，虽然官方及IDE一直强调和提醒，但貌似并没有阻止程序员的使用。

为什么只对@Autowired警告

最主要的原因是：@Autowired是Spring提供的，是特定IoC提供的特定注解，与框架形成了强绑定，一旦换用其他IoC框架，是无法支持注入的。而@Resource是JSR-250提供的，IoC容器应当去兼容它，即使更换容器，也可以正常工作。

另外可能还跟这两种注解的工作机制有关。默认情况下@Autowired是以类型（ByType）进行匹配的，@Resource是以名字（ByName）进行匹配的。也就是说当容器中存在两个相同类型的Bean时，使用@Autowired注入会报错，而使用@Resource会更精准。当然@Autowired也可以指定名称（还需配合@Qualifier注解）。

@Autowired和@Resource功能

就Spring而言，不但支持自定义的@Autowired注解，还支持几个由JSR-250规范定义的注解，分别为@Resource、@PostConstruct以及@PreDestroy。

而@Autowired和@Resource的功能基本一致，@Resource的作用相当于@Autowired，只不过@Autowired默认按byType自动注入，而@Resource默认按byName自动注入。

@Resource有两个核心属性：name和type。Spring将@Resource注解的name属性解析为bean的名字，type属性则解析为bean的类型。默认情况下会通过反射机制使用byName自动注入策略。

@Resource装配场景：

• 1、如果同时指定了name和type，则从Spring上下文中找到唯一匹配的bean进行装配，找不到则抛出异常；
• 2、如果指定了name，则根据名称进行装配，找不到则抛出异常；
• 3、如果指定了type，则根据类型进行装配，找不到或者找到多个，都会抛出异常；
• 4、没有任何指定（默认情况），则采用byName方式进行装配，如果没有匹配到，则回退为一个原始类型进行匹配；

小结

处于对代码的洁癖，不习惯@Autowired的提示信息，于是整个项目中都强力推荐使用@Resource注解。了解了这一提示的底层原理，或许你就可以选择最适合自己的注入形式了。

原文链接：《只因多看了一眼提示，又一次刷新了@Autowired注释的认知》

程序新视界

\

公众号“ 程序新视界”，一个让你软实力、硬技术同步提升的平台，提供海量资料

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

这是我参与更文挑战的第22天，活动详情查看： 更文挑战

数据结构和算法 (DSA)
通常被认为是一个令人生畏的话题——一种常见的误解。它们是技术领域最具创新性概念的基础，对于工作/实习申请者和有经验的程序员的职业发展都至关重要。掌握DSA意味着你能够使用你的计算和算法思维来解决前所未见的问题，并为任何科技公司的价值做出贡献（包括你自己的！）。通过了解它们，您可以提高代码的可维护性、可扩展性和效率。

话虽如此，我决定将我所了解的数据结构和算法集中起来。本文旨在使 DSA 看起来不像人们认为的那样令人生畏。它包括 15 个最有用的数据结构和 15 个最重要的算法，可以帮助您在学习中和面试中取得好成绩并提高您的编程竞争力。后面等我还会继续对这些数据结构和算法进行进一步详细地研究讲解。

一、数据结构

1. 数组（Arrays）

数组是最简单也是最常见的数据结构。它们的特点是可以通过索引（位置）轻松访问元素。

它们是做什么用的？

想象一下有一排剧院椅。每把椅子都分配了一个位置（从左到右），因此每个观众都会从他将要坐的椅子上分配一个号码。这是一个数组。将问题扩展到整个剧院（椅子的行和列），您将拥有一个二维数组（矩阵）！

特性

• 元素的值按顺序放置，并通过从 0 到数组长度的索引访问；
• 数组是连续的内存块；
• 它们通常由相同类型的元素组成（这取决于编程语言）；
• 元素的访问和添加速度很快；搜索和删除不是在 O(1) 中完成的。

2. 链表（Linked Lists）

链表是线性数据结构，就像数组一样。链表和数组的主要区别在于链表的元素不存储在连续的内存位置。它由节点组成——实体存储当前元素的值和下一个元素的地址引用。这样，元素通过指针链接。

它们是做什么用的？

链表的一个相关应用是浏览器的上一页和下一页的实现。双链表是存储用户搜索显示的页面的完美数据结构。

特性

• 它们分为三种类型：单独的、双重的和圆形的；
• 元素不存储在连续的内存块中；
• 完美的优秀内存管理（使用指针意味着动态内存使用）；
• 插入和删除都很快；访问和搜索元素是在线性时间内完成的。

3. 堆栈（Stacks）

堆栈是一种抽象数据类型，它形式化了受限访问集合的概念。该限制遵循 LIFO（后进先出）规则。因此，添加到堆栈中的最后一个元素是您从中删除的第一个元素。

堆栈可以使用数组或链表来实现。

它们是做什么用的？

现实生活中最常见的例子是在食堂中将盘子叠放在一起。位于顶部的板首先被移除。放置在最底部的盘子是在堆栈中保留时间最长的盘子。

堆栈最有用的一种情况是您需要获取给定元素的相反顺序。只需将它们全部推入堆栈，然后弹出它们。

另一个有趣的应用是有效括号问题。给定一串括号，您可以使用堆栈检查它们是否匹配。

特性

• 您一次只能访问最后一个元素（顶部的元素）；
• 一个缺点是，一旦您从顶部弹出元素以访问其他元素，它们的值将从堆栈的内存中丢失；
• 其他元素的访问是在线性时间内完成的；任何其他操作都在 O(1) 中。

4. 队列（Queues）

队列是受限访问集合中的另一种数据类型，就像前面讨论的堆栈一样。主要区别在于队列是按照FIFO（先进先出）模型组织的：队列中第一个插入的元素是第一个被移除的元素。队列可以使用固定长度的数组、循环数组或链表来实现。

它们是做什么用的？

这种抽象数据类型 (ADT) 的最佳用途当然是模拟现实生活中的队列。例如，在呼叫中心应用程序中，队列用于保存等待从顾问那里获得帮助的客户——这些客户应该按照他们呼叫的顺序获得帮助。

一种特殊且非常重要的队列类型是优先级队列。元素根据与它们关联的“优先级”被引入队列：具有最高优先级的元素首先被引入队列。这个 ADT 在许多图算法（Dijkstra 算法、BFS、Prim 算法、霍夫曼编码 - 更多关于它们的信息）中是必不可少的。它是使用堆实现的。

另一种特殊类型的队列是deque 队列（双关语它的发音是“deck”）。可以从队列的两端插入/删除元素。

特性

• 我们只能直接访问引入的“最旧”元素；
• 搜索元素将从队列的内存中删除所有访问过的元素；
• 弹出/推送元素或获取队列的前端是在恒定时间内完成的。搜索是线性的。

5. Map 和 哈希表（Hash Table）

Maps （dictionaries）是包含键集合和值集合的抽象数据类型。每个键都有一个与之关联的值。

哈希表是一种特殊类型的映射。它使用散列函数生成一个散列码，放入一个桶或槽数组：键被散列，结果散列指示值的存储位置。

最常见的散列函数（在众多散列函数中）是模常数函数。例如，如果常量是 6，则键 x 的值是x%6。

理想情况下，散列函数会将每个键分配给一个唯一的桶，但他们的大多数设计都采用了不完善的函数，这可能会导致具有相同生成值的键之间发生冲突。这种碰撞总是以某种方式适应的。

它们是做什么用的？

Maps 最著名的应用是语言词典。语言中的每个词都为其指定了定义。它是使用有序映射实现的（其键按字母顺序排列）。

通讯录也是一张Map。每个名字都有一个分配给它的电话号码。

另一个有用的应用是值的标准化。假设我们要为一天中的每一分钟（24 小时 = 1440 分钟）分配一个从 0 到 1439 的索引。哈希函数将为h(x) = x.小时*60+x.分钟。

特性

• 键是唯一的（没有重复）；
• 抗碰撞性：应该很难找到具有相同键的两个不同输入；
• 原像阻力：给定值 H，应该很难找到键 x，使得h(x)=H；
• 第二个原像阻力：给定一个键和它的值，应该很难找到另一个具有相同值的键；

术语：

• “map”：Java、C++；
• “dictionary”：Python、JavaScript、.NET；
• “associative array”：PHP。

因为maps 是使用自平衡红黑树实现的（文章后面会解释），所以所有操作都在 O(log n) 内完成；所有哈希表操作都是常量。

6. 图表（Graphs）

图是表示一对两个集合的非线性数据结构：G={V, E}，其中 V 是顶点（节点）的集合，而 E 是边（箭头）的集合。节点是由边互连的值 - 描述两个节点之间的依赖关系（有时与成本/距离相关联）的线。

图有两种主要类型：有向图和无向图。在无向图中，边(x, y)在两个方向上都可用：(x, y)和(y, x)。在有向图中，边(x, y)称为箭头，方向由其名称中顶点的顺序给出：箭头(x, y)与箭头(y, x) 不同。

它们是做什么用的？

图是各种类型网络的基础：社交网络（如 weixin、csdn、weibo），甚至是城市街道网络。社交媒体平台的每个用户都是一个包含他/她的所有个人数据的结构——它代表网络的一个节点。weixin 上的好友关系是无向图中的边（因为它是互惠的），而在 CSDN 或 weibo上，帐户与其关注者/关注帐户之间的关系是有向图中的箭头（非互惠）。

特性

图论是一个广阔的领域，但我们将重点介绍一些最知名的概念：

• 无向图中节点的度数是它的关联边数；
• 有向图中节点的内部/外部度数是指向/来自该节点的箭头的数量；
• 从节点 x 到节点 y 的链是相邻边的连续，x 是它的左端，y 是它的右边；
• 一个循环是一个链，其中 x=y；图可以是循环/非循环的；如果 V 的任意两个节点之间存在链，则图是连通的；
• 可以使用广度优先搜索 (BFS) 或深度优先搜索 (DFS) 遍历和处理图，两者都在 O(|V|+|E|) 中完成，其中 |S| 是集合S 的基数；查看下面的链接，了解图论中的其他基本信息。

7. 树（Trees）

一棵树是一个无向图，在连通性方面最小（如果我们消除一条边，图将不再连接）和在无环方面最大（如果我们添加一条边，图将不再是无环的） . 所以任何无环连通无向图都是一棵树，但为了简单起见，我们将有根树称为树。

根是一个固定节点，它确定树中边的方向，所以这就是一切“开始”的地方。叶子是树的终端节点——这就是一切“结束”的地方。
一个顶点的孩子是它下面的事件顶点。一个顶点可以有多个子节点。一个顶点的父节点是它上面的事件顶点——它是唯一的。

它们是做什么用的？

我们在任何需要描绘层次结构的时候都使用树。我们自己的家谱树就是一个完美的例子。你最古老的祖先是树的根。最年轻的一代代表叶子的集合。

树也可以代表你工作的公司中的上下级关系。这样您就可以找出谁是您的上级以及您应该管理谁。

特性

• 根没有父级；
• 叶子没有孩子；
• 根和节点 x 之间的链的长度表示 x 所在的级别；
• 一棵树的高度是它的最高层（在我们的例子中是 3）；
• 最常用的遍历树的方法是 O(|V|+|E|) 中的 DFS，但我们也可以使用 BFS；使用 DFS 在任何图中遍历的节点的顺序形成 DFS 树，指示我们访问节点的时间。

8. 二叉树（Binary Trees）和二叉搜索树（Binary Search Trees）

二叉树是一种特殊类型的树：每个顶点最多可以有两个子节点。在严格二叉树中，除了叶子之外，每个节点都有两个孩子。具有 n 层的完整二叉树具有所有2ⁿ-1 个可能的节点。

二叉搜索树是一棵二叉树，其中节点的值属于一个完全有序的集合——任何任意选择的节点的值都大于左子树中的所有值，而小于右子树中的所有值。

它们是做什么用的？

BT 的一项重要应用是逻辑表达式的表示和评估。每个表达式都可以分解为变量/常量和运算符。这种表达式书写方法称为逆波兰表示法 (RPN)。这样，它们就可以形成一个二叉树，其中内部节点是运算符，叶子是变量/常量——它被称为抽象语法树（AST）。

BST 经常使用，因为它们可以快速搜索键属性。AVL 树、红黑树、有序集和映射是使用 BST 实现的。

特性

BST 有三种类型的 DFS 遍历：

• 先序（根、左、右）；
• 中序（左、根、右）；
• 后序（左、右、根）；全部在 O(n) 时间内完成；
• 中序遍历以升序为我们提供了树中的所有节点；
• 最左边的节点是 BST 中的最小值，最右边的节点是最大值；
• 注意 RPN 是 AST 的中序遍历；
• BST 具有排序数组的优点，但有对数插入的缺点——它的所有操作都在 O(log n) 时间内完成。

9. AVL树（Adelson-Velsky and Landis Trees ）

所有这些类型的树都是自平衡二叉搜索树。不同之处在于它们以对数时间平衡高度的方式。

AVL 树在每次插入/删除后都是自平衡的，因为节点的左子树和右子树的高度之间的模块差异最大为 1。 AVL 以其发明者的名字命名：Adelson-Velsky 和 ​​Landis。

在红黑树中，每个节点存储一个额外的代表颜色的位，用于确保每次插入/删除操作后的平衡。

在 Splay 树中，最近访问的节点可以快速再次访问，因此任何操作的摊销时间复杂度仍然是 O(log n)。

它们是做什么用的？

AVL 似乎是数据库理论中最好的数据结构。

RBT（红黑树） 用于组织可比较的数据片段，例如文本片段或数字。在 Java 8 版本中，HashMap 是使用 RBT 实现的。计算几何和函数式编程中的数据结构也是用 RBT 构建的。

在 Windows NT 中（在虚拟内存、网络和文件系统代码中），Splay 树用于缓存、内存分配器、垃圾收集器、数据压缩、绳索（替换用于长文本字符串的字符串）。

特性

• ANY自平衡BST中ANY操作的摊销时间复杂度为O(log n)；
• 在最坏的情况下，AVL 的最大高度是 1.44 * log2n（为什么？==提示==：考虑所有级别都已满的 AVL 的情况，除了最后一个只有一个元素）；
• AVLs 在实践中搜索元素是最快的，但是为了自平衡而旋转子树的成本很高；
• 同时，由于没有旋转，RBT 提供了更快的插入和删除；
• 展开树不需要存储任何簿记数据。

10.堆（Heaps）

最小堆是一棵二叉树，其中每个节点的值都大于或等于其父节点的值：val[par[x]] <= val[x]，具有堆的 xa 节点，其中val[ x]是它的值，par[x] 是它的父级。

还有一个实现相反关系的最大堆。

二叉堆是一棵完整的二叉树（它的所有层都被填充，除了最后一层）。

它们是做什么用的？

正如我们几天前讨论过的，优先队列可以使用二叉堆有效地实现，因为它支持 O(log n) 时间内的 insert()、delete()、extractMax() 和 reduceKey() 操作。这样，堆在图算法中也是必不可少的（因为优先级队列）。

任何时候您需要快速访问最大/最小项目，堆都是最好的选择。

堆也是堆排序算法的基础。

特性

• 它总是平衡的：无论何时我们在结构中删除/插入一个元素，我们只需要“筛选”/“渗透”它直到它处于正确的位置；
• 节点k > 1的父节点是[k/2]（其中 [x] 是 x 的整数部分），其子节点是2k和2k+1；
• 设置优先级队列的替代方案，ordered_map（在 C++ 中）或任何其他可以轻松允许访问最小/最大元素的有序结构；
• 根优先，因此其访问的时间复杂度为O(1)，插入/删除在O(log n)中完成；创建一个堆是在 O(n) 中完成的；O(n*log n)中的堆排序。

11.字典树（Tries）

trie 是一种高效的信息检索数据结构。也称为前缀树，它是一种搜索树，允许以 O(L) 时间复杂度插入和搜索，其中 L 是键的长度。

如果我们将密钥存储在一个平衡良好的 BST 中，它将需要与 L * log n 成正比的时间，其中 n 是树中的密钥数量。这样，与 BST 相比，trie 是一种更快的数据结构（使用 O(L)），但代价是 trie 存储要求。

它们是做什么用的？

树主要用于存储字符串及其值。它最酷的应用程序之一是在 Google 搜索栏中键入自动完成和自动建议。特里是最好的选择，因为它是最快的选择：如果我们不使用特里，更快的搜索比节省的存储更有价值。

通过在字典中查找单词或在同一文本中查找该单词的其他实例，也可以使用 trie 来完成键入单词的正字法自动更正。

特性

• 它有一个键值关联；键通常是一个单词或它的前缀，但它可以是任何有序列表；
• 根有一个空字符串作为键；
• 节点值与其子节点值之间的长度差为 1；这样，根的子节点将存储长度​​为 1 的值；作为结论，我们可以说来自第 k 层的节点 x 具有长度k 的值；
• 正如我们所说，插入/搜索操作的时间复杂度是 O(L)，其中 L 是键的长度，这比 BST 的 O(log n) 快得多，但与哈希表相当；

空间复杂度实际上是一个缺点：O(ALPHABET_SIZE*L*n)。

12. 段树（Segment Trees）

段树是一个完整的二叉树，可以有效地回答查询，同时仍然可以轻松修改其元素。

给定数组中索引 i 上的每个元素代表一个用[i, i]间隔标记的叶子。将其子节点分别标记为[x, y]或[y, z]的节点将具有[x, z]区间作为标签。因此，给定 n 个元素（0-indexed），线段树的根将被标记为[0, n-1]。

它们是做什么用的？

它们在可以使用分而治之（我们将要讨论的第一个算法概念）解决的任务中非常有用，并且还可能需要更新其元素。这样，在更新元素时​​，包含它的任何区间也会被修改，因此复杂度是对数的。例如，n 个给定元素的总和/最大值/最小值是线段树最常见的应用。如果元素更新正在发生，二分搜索也可以使用段树。

特性

• 作为二叉树，节点 x 将2x和2x+1作为子节点，[x/2]作为父节点，其中[x]是x的整数部分；
• 更新段树中整个范围的一种有效方法称为“延迟传播”，它也是在 O(log n) 中完成的（有关操作的实现，请参见下面的链接）；
• 它们可以是 k 维的：例如，有 q 个查询来查找一个矩阵的给定子矩阵的总和，我们可以使用二维线段树；
• 更新元素/范围需要 O(log n) 时间；对查询的回答是恒定的(O(1))；
• 空间复杂度是线性的，这是一个很大的优势：O(4*n)。

13. 树状数组（Fenwick Trees）

fenwick 树，也称为二叉索引树 (BIT)，是一种也用于高效更新和查询的数据结构。与 Segment Trees 相比，BITs 需要更少的空间并且更容易实现。

它们是做什么用的？

BIT 用于计算前缀和——第 i 个位置的元素的前缀和是从第一个位置到第 i 个元素的总和。它们使用数组表示，其中每个索引都以二进制系统表示。例如，索引 10 相当于十进制系统中的索引 2。

特性

• 树的构建是最有趣的部分：首先，数组应该是 1-indexed 要找到节点 x 的父节点，您应该将其索引 x 转换为二进制系统并翻转最右边的有效位；ex.节点 6 的父节点是 4；

1
2

java复制代码6 = 1*2²+1*2¹+0*2⁰ => 1"1"0 (flip) 
=> 100 = 1*2²+0*2¹+0*2⁰ = 4;

• 最后，ANDing 元素，每个节点都应该包含一个可以添加到前缀和的间隔；
• 更新的时间复杂度仍然是 O(log n)，查询的时间复杂度仍然是 O(1)，但空间复杂度与线段树的 O(4*n) 相比是一个更大的优势：O(n)。

14. 并查集（Disjoint Set Union）

我们有 n 个元素，每个元素代表一个单独的集合。并查集 (DSU) 允许我们做两个操作：

1.UNION — 组合任意两个集合（或者统一两个不同元素的集合，如果它们不是来自同一个集合）；
2.FIND — 查找元素来自的集合。

它们是做什么用的？

并查集（DSU） 在图论中非常重要。您可以检查两个顶点是否来自同一个连接组件，或者甚至可以统一两个连接组件。

让我们以城市和城镇为例。由于人口和经济增长的邻近城市正在扩张，它们可以轻松创建大都市。因此，两个城市合并在一起，他们的居民住在同一个大都市。我们还可以通过调用 FIND 函数来检查一个人居住在哪个城市。

特性

• 它们用树表示；一旦两组组合在一起，两个根中的一个成为主根，另一个根的父代是另一棵树的叶子之一；
• 一种实用的优化是通过高度压缩树木；这样，联合由最大的树组成，以轻松更新它们的两个数据（参见下面的实现）；
• 所有操作都在 O(1) 时间内完成。

15. 最小生成树（Minimum Spanning Trees）

给定一个连通图和无向图，该图的生成树是一个子图，它是一棵树并将所有节点连接在一起。单个图可以有许多不同的生成树。加权、连通和无向图的最小生成树 (MST) 是权重（成本）小于或等于其他所有生成树权重的生成树。生成树的权重是赋予生成树每条边的权重之和。

它们是做什么用的？

最小生成树（MST ）问题是一个优化问题，一个最小成本问题。有了路线网，我们可以认为影响n个城市之间建立国道的因素之一是相邻两个城市之间的最小距离。

国家路线就是这样，由道路网络图的 MST 表示。

特性

作为一棵树，具有 n 个顶点的图的 MST 具有 n-1 条边；可以使用以下方法解决：

• Prim 算法 — 密集图的最佳选择（具有 n 个节点且边数接近n(n-1)/2)的图）；
• Kruskal 算法——主要使用；它是一种基于不相交集联合的贪心算法（我们后面也将讨论它）；
• 构建它的时间复杂度对于 Kruskal 来说是 O(n log n) 或 O(n log m)（这取决于图），对于 Prim 来说是 O(n²)。

二、算法

1.分治算法（Divide and Conquer）

分而治之（DAC）本身并不是一个特定的算法，而是在深入研究其他主题之前需要了解的重要算法类别。它用于解决可以划分为与原始问题相似但规模较小的子问题的问题。然后 DAC 递归地求解它们，最后合并结果以找到问题的解决方案。

它分为三个阶段：

• 划分——将问题分解为子问题；
• 用递归解决子问题；
• 合并——子问题的结果到最终解决方案中。

它是干什么用的？

分治算法（DAC） 的一种实际应用是使用多个处理器进行并行编程，因此子问题在不同的机器上执行。

DAC 是许多算法的基础，例如快速排序、合并排序、二分搜索或快速乘法算法。

特性

• 每个 DAC 问题都可以写成一个递推关系；因此，必须找到停止递归的基本情况；
• 它的复杂度是T(n)=D(n)+C(n)+M(n)，这意味着每个阶段都有不同的复杂度，具体取决于问题。

2. 排序算法（Sorting Algorithms）

排序算法用于根据元素上的比较运算符重新排列给定元素（来自数组或列表）。当我们提到一个排序数组时，我们通常会想到升序（比较运算符是“<”）。排序有多种类型，具有不同的时间和空间复杂度。其中一些是基于比较的，有些则不是。以下是最流行/最有效的排序方法：

冒泡排序（Bubble Sort）

冒泡排序是最简单的排序算法之一。它基于相邻元素之间的重复交换（如果它们的顺序错误）。它是稳定的，它的时间复杂度是 O(n²) 并且它需要 O(1) 辅助空间。

计数排序（Counting Sort）

计数排序不是基于比较的排序。它基本上是使用每个元素的频率（一种散列），确定最小值和最大值，然后在它们之间迭代以根据其频率放置每个元素。它在 O(n) 中完成，空间与数据范围成正比。如果输入范围不明显大于元素数量，则它是有效的。

快速排序（Quick Sort）

快速排序是分而治之的一个应用。它基于选择一个元素作为枢轴（第一个、最后一个或中间值），然后交换元素以将枢轴放置在所有小于它的元素和所有大于它的元素之间。它没有额外的空间和 O(n*log n) 时间复杂度——基于比较的方法的最佳复杂度。

归并排序（Merge Sort）

归并排序也是一个分而治之的应用程序。它将数组分成两半，对每一半进行排序，然后合并它们。它的时间复杂度也是 O(n*log n)，所以它也像 Quick Sort 一样超快，但不幸的是它需要 O(n) 额外空间来同时存储两个子数组，最后合并它们。

基数排序（Radix Sort）

基数排序使用计数排序作为子程序，因此它不是基于比较的算法。我们怎么知道CS是不够的？假设我们必须对[1, n²] 中的元素进行排序。使用 CS，我们需要 O(n²)。我们需要一个线性算法——O(n+k)，其中元素在[1, k]范围内。它从最不重要的一个（单位）开始，到最重要的（十、百等）对元素进行逐位排序。额外空间（来自 CS）：O(n)。

3. 搜索算法（Searching Algorithms）

搜索算法旨在检查数据结构中元素的存在，甚至返回它。有几种搜索方法，但这里是最受欢迎的两种：

线性搜索（Linear Search）

该算法的方法非常简单：您从数据结构的第一个索引开始搜索您的值。您将它们一一比较，直到您的值和当前元素相等。如果该特定值不在 DS 中，则返回 -1。

时间复杂度：O(n)

二分查找（Binary Search）

BS 是一种基于分而治之的高效搜索算法。不幸的是，它只适用于排序的数据结构。作为一种 DAC 方法，您连续将 DS 分成两半，并将搜索中的值与中间元素的值进行比较。如果它们相等，则搜索结束。无论哪种方式，如果您的值大于/小于它，搜索应该继续在右/左半部分。

时间复杂度：O(log n)

4. 埃氏筛法（Sieve of Eratosthenes）

给定一个整数 n，打印所有小于或等于 n 的素数。
Eratosthenes 筛法是解决这个问题的最有效的算法之一，它完美地适用于小于10.000.000 的n 。

该方法使用频率列表/映射来标记[0, n]范围内每个数字的素数：如果 x 是素数，则ok[x]=0，否则ok[x]=1。

我们开始从列表中选择每个素数，并用 1 标记列表中的倍数——这样，我们选择未标记的 (0) 数。最后，我们可以在 O(1) 中轻松回答任意数量的查询。

经典算法在许多应用中都是必不可少的，但我们可以进行一些优化。首先，我们很容易注意到 2 是唯一的偶素数，因此我们可以单独检查它的倍数，然后在范围内迭代以找到从 2 到 2 的素数。其次，很明显，对于数字 x，我们之前在迭代 2、3 等时已经检查了 2x、3x、4x 等。这样，我们的乘数检查 for 循环每次都可以从 x² 开始。最后，即使这些倍数中有一半是偶数，而且我们也在迭代奇素数，因此我们可以在倍数检查循环中轻松地从 2x 迭代到 2x。

空间复杂度：O(n)
时间复杂度：O(n*log(log n)) 用于经典算法，O(n) 用于优化算法。

5. 字符串匹配算法（Knuth-Morris-Pratt）

给定长度为 n 的文本和长度为 m 的模式，找出文本中所有出现的模式。

Knuth-Morris-Pratt 算法 (KMP) 是解决模式匹配问题的有效方法。
天真的解决方案基于使用“滑动窗口”，每次设置新的起始索引时，我们都会比较字符与字符，从文本的索引 0 开始到索引 nm。这样，时间复杂度是 O(m*(n-m+1))~O(n*m)。

KMP 是对朴素解决方案的优化：它在 O(n) 中完成，并且当模式具有许多重复的子模式时效果最佳。因此，它也使用滑动窗口，但不是将所有字符与子字符串进行比较，而是不断寻找当前子模式的最长后缀，这也是它的前缀。换句话说，每当我们在某些匹配后检测到不匹配时，我们就已经知道下一个窗口文本中的某些字符。因此，再次匹配它们是没有用的，因此我们重新开始匹配文本中具有该前缀后的字符的相同字符。我们怎么知道我们应该跳过多少个字符？好吧，我们应该构建一个预处理数组，告诉我们应该跳过多少个字符。

6.贪婪算法（Greedy）

Greedy 方法多用于需要优化且局部最优解导致全局最优解的问题。

也就是说，当使用 Greedy 时，每一步的最优解都会导致整体最优解。然而，在大多数情况下，我们在一个步骤中做出的决定会影响下一步的决定列表。在这种情况下，必须用数学方法证明算法。Greedy 也会在一些数学问题上产生很好的解决方案，但不是全部（可能无法保证最佳解决方案）！

贪心算法通常有五个组成部分：

• 候选集——从中创建解决方案；
• 选择函数——选择最佳候选人；
• 可行性函数——可以确定候选人是否能够为解决方案做出贡献；
• 一个目标函数——将候选人分配给（部分）解决方案；
• 一个解决方案函数——从部分解决方案构建解决方案。

分数背包问题

给定n个物品的重量和价值，我们需要将这些物品放入容量为W的背包中，以获得背包中的最大总价值（允许取件物品：一件物品的价值与其重量成正比）。

贪心方法的基本思想是根据它们的价值/重量比对所有项目进行排序。然后，我们可以添加尽可能多的整个项目。当我们发现一件比背包中剩余重量 (w1) 重 (w2) 的物品时，我们将对其进行分割：仅取出w2-w1以最大化我们的利润。保证这个贪心的解决方案是正确的。

7. 动态规划（Dynamic Programming）

动态规划 (DP) 是一种类似于分而治之的方法。它还将问题分解为类似的子问题，但它们实际上是重叠和相互依赖的——它们不是独立解决的。

每个子问题的结果都可以在以后随时使用，它是使用记忆（预先计算）构建的。DP 主要用于（时间和空间）优化，它基于寻找循环。

DP 应用包括斐波那契数列、河内塔、Roy-Floyd-Warshall、Dijkstra 等。 下面我们将讨论 0-1 背包问题的 DP 解决方案。

0–1 背包问题

给定n个物品的重量和价值，我们需要将这些物品放入容量为W的背包中，以获得背包中的最大总值（不允许像贪婪解决方案中的那样分割物品）。
0-1 属性是由我们应该选择整个项目或根本不选择它的事实给出的。
我们构建了一个 DP 结构作为矩阵dp[i][cw]存储我们通过选择总权重为 cw 的 i 个对象可以获得的最大利润。很容易注意到我们应该首先用v[i]初始化dp[1][w[i] ]，其中w[i]是第 i 个对象的权重，v[i] 是它的值。
复现如下：

1

javascript复制代码dp[i][cw] = max(dp[i-1][cw], dp[i-1][cw-w[i]]+v[i])

我们稍微分析一下。

dp[i-1][cw]描述了我们没有在背包中添加当前物品的情况。dp[i-1][cw-w[i]]+v[i]就是我们添加item的情况。话虽如此，dp[i-1][cw-w[i]]是采用 i-1 个元素的最大利润：所以它们的重量是当前重量，没有我们的物品重量。最后，我们将项目的值添加到它。

答案存入dp[n][W]. 通过一个简单的观察进行优化：在循环中，当前行仅受前一行的影响。因此，将DP结构存储到矩阵中是不必要的，因此我们应该选择一个空间复杂度更好的数组：O(n)。时间复杂度：O(n*W)。

8. 最长公共子序列（Longest Common Subsequence）

给定两个序列，找出它们中存在的最长子序列的长度。子序列是以相同的相对顺序出现的序列，但不一定是连续的。例如，“bcd”、“abdg”、“c”都是“abcdefg”的子序列。

这是动态规划的另一个应用。LCS 算法使用 DP 来解决上述问题。

实际的子问题是要分别从序列 A 中的索引 i 开始，分别从序列 B 中的索引 j 中找到最长公共子序列。

接下来，我们将构建 DP 结构lcs[ ][ ]（矩阵），其中lcs[i][j]是从 A 中的索引 i 开始，分别是 B 中的索引 j 的公共子序列的最大长度。我们将以自顶向下的方式构建它。显然，解决方案存储在lcs[n][m] 中，其中 n 是 A 的长度，m 是 B 的长度。

递推关系非常简单直观。为简单起见，我们将考虑两个序列都是 1 索引的。首先，我们将初始化lcs[i][0] , 1<=i<=n和lcs[0][j] , 1<=j<=m , 0, 作为基本情况（没有从 0 开始的子序列）。然后，我们将考虑两种主要情况：如果A[i]等于B[j]，则lcs[i][j] = lcs[i-1][j-1]+1（比之前的 LCS 多一个相同的字符）。否则，它将是lcs[i-1][j]（如果不考虑A[i]）和lcs[i][j-1]（如果不考虑B[j]）之间的最大值）。

时间复杂度：O(n*m)
附加空间：O(n*m)

9. 最长递增子序列（Longest Increasing Subsequence）

给定一个包含 n 个元素的序列 A，找到最长子序列的长度，使其所有元素按递增顺序排序。子序列是以相同的相对顺序出现的序列，但不一定是连续的。例如，“bcd”、“abdg”、“c”是“abcdefg”的子序列。

LIS 是另一个可以使用动态规划解决的经典问题。

使用数组l[ ]作为 DP 结构来寻找递增子序列的最大长度，其中l[i]是包含A[i]的递增子序列的最大长度，其元素来自[A[i] ], ..., A[n]] 子序列。l[i]为 1，如果A[i]之后的所有元素比它小。否则，在 A[i] 之后大于它的所有元素之间的最大值为 1+。显然，l[n]=1，其中 n 是 A 的长度。 实现是自底向上的（从末尾开始）。

在搜索当前元素之后的所有元素之间的最大值时出现了一个优化问题。我们能做的最好的事情是二分搜索最大元素。

为了找到现在已知的最大长度的子序列，我们只需要使用一个额外的数组ind[]，它存储每个最大值的索引。

时间复杂度：O(n*log n)
附加空间：O(n)

10.凸包算法（Convex Hull）

给定同一平面中的一组 n 个点，找到包含所有给定点（位于多边形内部或其边上）的最小面积凸多边形。这种多边形称为凸包。凸包问题是一个经典的几何，在现实生活中有很多应用。例如，碰撞避免：如果汽车的凸包避免碰撞，那么汽车也能避免碰撞。路径的计算是使用汽车的凸表示完成的。形状分析也是在凸包的帮助下完成的。这样，图像处理很容易通过匹配模型的凸缺陷树来完成。

有一些算法用于寻找凸包，如 Jarvis 算法、Graham 扫描等。今天我们将讨论 Graham 扫描和一些有用的优化。

格雷厄姆扫描按极角对点进行排序——由某个点和其他选定点确定的线的斜率。然后用一个栈来存储当前时刻的凸包。当一个点 x 被压入堆栈时，其他点会被弹出堆栈，直到 x 与最后两个点所确定的线形成小于 180° 的角度。最后，引入堆栈的最后一个点关闭多边形。由于排序，这种方法的时间复杂度为 O(n*log n)。但是，这种方法在计算斜率时会产生精度误差。

一种改进的解决方案具有相同的时间复杂度，但误差较小，按坐标（x，然后是 y）对点进行排序。然后我们考虑由最左边和最右边的点形成的线，并将问题分为两个子问题。最后，我们在这条线的每一边找到了凸包。所有给定点的凸包是两个包的重聚。

11. 图遍历（Graph Traversals）

遍历图的问题是指以特定顺序访问所有节点，通常沿途计算其他有用信息。

广度优先搜索（Breadth-First Search）

广度优先搜索 (BFS) 算法是确定图是否连通的最常用方法之一——或者换句话说，查找 BFS 源节点的连通分量。

BFS 还用于计算源节点和所有其他节点之间的最短距离。BFS 的另一个版本是 Lee 算法，用于计算网格中两个单元格之间的最短路径。

该算法首先访问源节点，然后访问将被推入队列的邻居。队列中的第一个元素被弹出。我们将访问它的所有邻居，并将之前未访问的邻居推入队列。重复该过程直到队列为空。当队列为空时，表示所有可达顶点都已访问完毕，算法结束。

深度优先搜索（Depth-First Search）

深度优先搜索 (DFS) 算法是另一种常见的遍历方法。在检查图形的连通性时，它实际上是最好的选择。

首先，我们访问根节点并将其压入堆栈。虽然堆栈不为空，但我们检查顶部的节点。如果该节点有未访问的邻居，则选择其中一个并将其压入堆栈。否则，如果它的所有邻居都被访问过，我们就会弹出这个节点。当堆栈变空时，算法结束。

经过这样的遍历，就形成了一个DFS树。DFS 树有很多应用；最常见的一种是存储每个节点的“开始”和“结束”时间——它进入堆栈的时刻，分别是它从堆栈中弹出的时刻。

12. 弗洛依德算法（Floyd-Warshall）

Floyd-Warshall / Roy-Floyd 算法解决了所有对最短路径问题：找到给定边加权有向图中每对顶点之间的最短距离。

FW 是一个动态规划应用程序。DP 结构（矩阵）dist[ ][ ]用输入图矩阵初始化。然后我们将每个顶点视为其他两个节点之间的中间体。最短路径在每两对节点之间更新，任何节点 k 作为中间顶点。如果 k 是 i 和 j 之间排序路径中的中间值，则dist[i][j]成为dist[i][k]+dist[k][j]和dist[i][j]之间的最大值。

时间复杂度：O(n³)
空间复杂度：O(n²)

13. Dijkstra 算法和 Bellman-Ford 算法

迪杰斯特拉（Dijkstra） 算法

给定一个图和图中的一个源顶点，找出从源到给定图中所有顶点的最短路径。

Dijkstra 算法用于在加权图中找到这样的路径，其中所有的权重都是正的。

Dijkstra 是一种贪心算法，它使用以源节点为根的最短路径树（SPT）。SPT 是一种自平衡二叉树，但该算法可以使用堆（或优先级队列）来实现。我们将讨论堆解决方案，因为它的时间复杂度是 O(|E|*log |V|)。这个想法是使用图形的邻接列表表示。这样，节点将使用 BFS （广度优先搜索）在 O(|V|+|E|) 时间内遍历。

所有顶点都用 BFS 遍历，那些最短距离尚未最终确定的顶点被存储到最小堆（优先队列）中。

创建最小堆并将每个节点连同它们的距离值一起推入其中。然后，源成为距离为 0 的堆的根。其他节点将无限分配为距离。当堆不为空时，我们提取最小距离值节点 x。对于与 x 相邻的每个顶点 y，我们检查 y 是否在最小堆中。在这种情况下，如果距离值大于 (x, y) 的权重加上 x 的距离值，那么我们更新 y 的距离值。

贝尔曼-福特（Bellman-Ford）算法

正如我们之前所说，Dijkstra 仅适用于正加权图。贝尔曼解决了这个问题。给定一个加权图，我们可以检查它是否包含负循环。如果没有，那么我们还可以找到从我们的源到其他源的最小距离（可能为负权重）。

Bellman-Ford 非常适合分布式系统，尽管它的时间复杂度是 O(|V| |E|)。

我们初始化一个 dist[] 就像在 Dijkstra 中一样。对于 *|V|-1次，对于每个(x, y)边，如果dist[y] > dist[x] + (x, y) 的权重，那么我们用它更新dist[y]。

我们重复最后一步以可能找到负循环。这个想法是，如果没有负循环，最后一步保证最小距离。如果有任何节点在当前步骤中的距离比上一步中的距离短，则检测到负循环。

14.克鲁斯卡尔算法（Kruskal’s Algorithm）

我们之前已经讨论过什么是最小生成树。

有两种算法可以找到图的 MST：Prim（适用于密集图）和 Kruskal（适用于大多数图）。现在我们将讨论 Kruskal 算法。

Kruskal 开发了一种贪心算法来寻找 MST。它在稀有图上很有效，因为它的时间复杂度是 O(|E|*log |V|)。

该算法的方法如下：我们按权重的递增顺序对所有边进行排序。然后，选取最小的边。如果它不与当前 MST 形成循环，我们将其包括在内。否则，丢弃它。重复最后一步，直到 MST 中有 |V|-1 条边。

将边包含到 MST 中是使用 Disjoint-Set-Union 完成的，这也在前面讨论过。

15. 拓扑排序（Topological Sorting）

有向无环图 (DAG) 只是一个不包含循环的有向图。

DAG 中的拓扑排序是顶点的线性排序，使得对于每个拱形(x, y)，节点 x 出现在节点 y 之前。

显然，拓扑排序中的第一个顶点是一个入度为 0 的顶点（没有拱形指向它）。

另一个特殊属性是 DAG 没有唯一的拓扑排序。

BFS （广度优先搜索）实现遵循此例程：找到一个入度为 0 的节点并将第一个推入排序。该顶点已从图中删除。由于新图也是一个 DAG，我们可以重复这个过程。

在 DFS 期间的任何时候，节点都可以属于以下三个类别之一：

• 我们完成访问的节点（从堆栈中弹出）；
• 当前在堆栈上的节点；
• 尚未发现的节点。

如果在 DAG 中的 DFS 期间，节点 x 具有到节点 y 的输出边，则 y 属于第一类或第三类。如果 y 在堆栈上，则(x, y)将结束一个循环，这与 DAG 定义相矛盾。

这个属性实际上告诉我们一个顶点在它的所有传出邻居都被弹出后从堆栈中弹出。因此，要对图进行拓扑排序，我们需要跟踪弹出顶点的逆序列表。

更多相关文章及我的联系方式我放在这里：

gitee.com/haiyongcsdn…

哇，你已经到读了文章的结尾。感谢您的阅览！文章篇幅较长，如果有些出错的地方还请大家批评指正，可在评论区留言或者私信我。

整理不易，最后，不要忘了❤或📑支持一下哦

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

1

复制代码作者｜李小平

前天我参加了信通院的云原生产业大会，参加会议的企业非常多，并且来自于各行各业，我在会场上非常感慨。我想起 2019 年的时候，我在搜索引擎上搜索“云原生”这个词，那时的搜索频率还比较低，而 2019 年又是云原生在国内开始飞速发展的一年。而今年的云原生会场上，已经有非常多的企业来参加，这些企业在技术、产品、生态中都在应用云原生，所以说，整个云原生已经从最开始的技术变成了行业，现在发展成了比较大的产业，并且这个产业的规模每年以非常快的速度在增长。
​

在今天，可能有很多咨询机构、企业，或者是个人开发者都在解读云原生，也许很多人对云原生都有比较深入的认识了。大家都可以认同的是，云原生肯定与云有关，但是它改变了什么，为企业带来什么价值呢？最核心的点应该是可以改变企业的应用架构；还有一种可能是不改变应用架构，只是把整个运维体系基于云原生进行重塑。但所有的这些，背后的目的都是为了加速企业的价值创造过程，简单的说，和制造企业改良生产线是一样的，核心点就是改良我们作为软件企业的生产线。
​

阿里在云原生的实践从 2006 年就开始了。我们在做云原生的过程中积累了很多经验，我们认为，今天云原生对于企业数字创新主要提供了多个价值：
​

一是资源弹性。弹性这个词大家很容易理解，实际上弹性有不同的层面。比如说基于虚拟机的弹性，提供的弹性能力是分钟级的。如果基于这些技术的应用是毫秒级的，那么分钟级只解决了资源弹性问题，整个应用高可用问题还需要进一步解决。如果说弹性到了应用的层面，到了毫秒级，高可用问题也得到一定程度的解决。
​

除此以外，系统的稳定性也是大家非常关注的方面。云原生就是把整个软件构造过程中非功能性特性拉出来放到云原生产品上去，帮助应用开发从非功能性处理过程中解脱出来，更多的专注在功能性。同样的，云原生有很多工具理念，可以让我们变得更好，整个软件开发从代码到上线的时间大幅缩短。同样的，今天在基于云原生可观测性上面我们会积累非常多的数据，这些数据可以结合机器学习这些能力，帮助我们改善企业的用户体验。这些对于业务来讲会带来比较大的价值。
​

阿里云原生的实践历程

​
今天，云原生在 CNCF、国内相关的开源、还有三方组织的推动下，可以使得一家企业在做技术选型的时候有非常多的选项。大家通常会面临一个问题，在这么多选择里面，要真正达到生产可用的目的到底选谁？特别是当我们的业务需要在非常短的时间内就上线，在业务高速发展的阶段，我们应该选什么样的架构，选什么样的开源开放的产品，这个是摆在广大企业技术决策者以及架构师面前的难题。
​
在云原生领域中，阿里云是相对比较早开始做自研的。从 2006 年到 2009 年互联网的中间件开始发展，到阿里云正式成立，整个过程中我们通过云原生解决很多业务问题。通过应用云原生相关技术，从早期很好地支持了淘宝的高速发展，到了 2015 年以后很好地支持了阿里的中台建设，以及到今天随着阿里巴巴整个生产系统、核心系统全部 100% 上云，这个过程中我们运用的云原生技术，像容器技术、微服务技术支持的规模都是百万级以上。
​
相关调研显示，这样的云原生落地规模在全球范围内都是非常领先的。实际上，对于很多企业来讲，也许用不到这些规模，但是阿里通过解决这样的大规模下的性能、稳定性问题，积累了非常多的硬核技术，最终能够把这些技术转变成了产品，通过阿里云对外输出，服务于各行各业的广大客户。

我们认为，云原生对于整个软件的改变，或者对软件公司的开发流程的改变是非常深刻的。首先 K8s 已经变成了软件交付的标准界面，它改变的不止是运维，而是从 CICD 到后续发布上线整个生产链条。由于所有生产流程得到改变，以及很多企业通过云原生技术重塑了软件架构，使得软件架构从传统架构变成了新的、我们称之为现代化的应用架构，因此云原生可以通过这种生产工具的改良进一步改变企业的生产关系，最终影响企业，使得企业在软件开发过程中得到了极大的提速。
​
阿里云在云原生实践过程中，积累了很强的技术竞争力，体现在这些方面：
​
一、我们有非常多领先的技术解决云原生领域里面的稳定性问题、可靠性问题，大规模下的高并发问题等。同时，我们会把所有的这些技术通过开源开放的形式输出。我们知道，在云原生的世界，企业需要的是开源开放的技术，而不是被像阿里这样单独一个厂商所锁定的技术。这个过程中我们基于开源开放技术标准积累了很多产品的硬核能力。在产品上，除了大家看到的基于云原生应用架构里，还包括云原生数据库、云原生大数据等。
​

在云原生相关的领域有比较多的测评，在这些测评里，例如阿里云容器产品 ACK，在去年 Gartner 评测中拿到满分，全球厂商中只有两个厂商拿到满分，阿里云是其中之一。今年，阿里云再次入选 Gartner 容器竞争格局。在新兴的计算形态领域中，今年阿里云进入 Forrester FaaS 领导者象限，函数计算获得了全球 FaaS 产品最高分。
​
在可观测性里，阿里云代表国内云厂商进入 Gartner APM 象限。所有这些三方评估从另外一个层面反映了阿里云产品的能力。容器架构上，我们基于开源开放的 K8s 技术体系，基于阿里云的硬件做深度的优化，在比较多的领域和场景里为广大 K8s 应用提供服务。我们把在 K8s 集群里面超大规模集群管理的能力输出到 ACK 产品里面，使得阿里云的客户在管理集群的时候，可以摆脱大规模集群的管理复杂性问题。
​
比如完美日记，作为美妆行业的独角兽公司，他们的业务发展速度非常快，但在业务快速发展过程中，他们面临的问题就是在大促的场景中怎么更好地预留资源，以及在大促时怎么样比较好地解决新上线的功能，以及需求的稳定性问题。在这个过程中，他们利用 PTS 作为压测，所有应用跑在 ACK 平台上面，通过压测模拟大促的流量，从而能够把整个大促从需要投入较大的状态提升到具备可以常态化的做大促压测的能力，也通过这个能力使得系统稳定性相关问题得到快速收敛。
​

云原生中间件

​
从微服务、消息到各种应用工具以外，根据企业常见的 IT 场景，云原生中间件也提供了很多解决方案。阿里云中间件诞生于集团内的大规模调用场景，同时兼容开源，并且融入了更多产品能力，例如在整个大促过程中表现优异的可观测性、高可用能力等，都属于云原生中间件产品体系。
​
同样在中间件领域里，我们也和较多企业客户有相应的合作。畅捷通是一家做 SaaS 的企业，迄今已经为超过四百万的小微企业做了云管。ToB 类型的应用复杂度较高，最大的问题就是整个软件的发布频率是非常快的，怎么样在高频软件发布下面能够比较好的解决软件的各种 BUG，或者解决设计上的不足带来的稳定性的问题，这是在前期探讨过程中畅捷通提出来的关注点。通过应用云原生中间件，不仅解决了整个应用的可观测性问题，并且让应用具备 360 度无死角可观测能力，通过应用探测能够快速发现在整个压测过程中各种可能的不稳定风险，从而使得相应风险得到快速的收敛。
​

Serverless

​
很多学术机构在 Serverless 领域深入研究，我们预感 Serverless 极有可能会成为下一代主流技术趋势。阿里云在 Serverless 领域里做到业界领先的毫秒级计费，以及在整个阿里云底层做深度优化，使客户的应用真正达到了智能的弹性、极致的运维和大幅提升开发效率。阿里云也和许多企业客户达成深度合作，进行 Serverless 落地实践，通过帮助客户将应用迁到 Serverless 技术体系上，达到比较快的应用部署；同时，把应用的稳定性问题、运维都委托给 Serverless 这样的云产品去解决。
​

解决方案

​
云原生在快速发展过程中，只有通过不断的技术创新、产品创新，才有可能使得云原生技术更好的服务于广大的企业客户。今天，阿里云对外发布四大解决方案：全链路压测解决方案、异地多活解决方案、资源混部解决方案、可观测解决方案。这些解决方案可以高效地解决在传统领域里还没有很好解决的问题。比如全链路压测，大家都知道全链路压测是个好东西，比较大的问题是在应用压测过程中使应用改造最小，甚至不要做改造，所以这次阿里云升级的全链路压测就可以帮助企业应用解决这些问题。
​
今天企业在不断深入地使用云以后，不管公有云还是专有云上，都会碰到整体 CPU 利用率不高的问题，混部就使得各种离线任务和在线任务可以部署在一起，各自享用资源调度的优势，使得整体机房的 CPU 利用率得到比较大的提升。在这个过程中要解决混部之后带来的稳定性问题、资源占用问题。阿里是比较早地应用大规模的混部，像支撑电商双十一的云原生产品。今天我们也是把混部能力变成解决方案对外输出。
​
大家都知道，阿里是比较早实现了单元化的架构，通过单元化架构实现了多活。今天我们把单元化整体的架构能力作为多活的解决方案。同时，这样的多活不仅可以支持自有数据中心、私有云的场景，也能够支持公有云和混合云场景实现整个应用的多活。
​
可观测性一直都是大家特别关注的话题，因为通过可观测性使得我们可以主动发现在系统的运行过程中可能出现的各类风险。今天，阿里云升级的可观测性方案包括从拨测到各种前端的性能监控，一直延伸到后端应用，甚至延伸到云服务里。
​

产品升级

​
除了解决方案的创新以外，我们在相应的云原生产品上面也做了比较多的升级。容器 ACK 备份容灾中心全新发布，为容器用户提供集群、应用和数据的完整性保护：
​
1、支持自动分析应用依赖的元数据及存储，实现秒级创建应用+数据的一致性快照；
2、支持创建备份计划，自动按预设时间点创建备份；
3、完全兼容 Kubernetes，并支持多集群、多地域、跨数据中心进行备份和恢复。

容器镜像 ACR 发布企业级 Serverless 构建服务，大幅提升云原生制品的构建效率和体验：
​
1、支持多操作系统、多架构镜像的矩阵构建，支持大规模并发任务构建。
2、支持多级缓存的构建加速，平均构建提速 30%。
3、支持自动构建加速镜像，实现 AI 等大镜像秒级按需加载，平均启动时间减少 60 %。

在微服务领域，越来越多的应用考虑采用服务网格技术。用户希望服务网格在开源技术之上有更强的微服务治理能力，因此阿里云推出专业版 ASM Pro，具备增强多协议支持，提升动态扩展能力，精细化服务治理，完善零信任安全体系。专业版相比去年发布的普通版，在性能及规模上均有显著提升，与开源的差异化竞争力进一步增强，降低用户在生产环境落地服务网格的门槛。
​

Gartner 预测，未来事件驱动将成为业务开发的主流架构。企业客户上云过程中对于低代码、无服务器弹性应用架构，如何轻量集成众多异构云服务的数据流有着明确的痛点和诉求。基于此趋势，阿里云发布了事件总线 EventBridge 这款产品，其目标在于统一阿里云云服务、第三方 SaaS 厂商、用户自定义的事件标准，通过标准、弹性、轻量的核心能力帮助用户快速低成本获取并处理海量事件，驱动业务开发。
​
在过去的一段时间，我们对 EventBridge 的产品能力做了进一步的扩充和升级：
​

• 在事件生态集成的规模方面，新增 60+ 云产品官方事件源接入，涵盖计算、存储、网络、数据库等主流云产品；
• 在事件触达和处理方式上，内置了十多种过滤匹配转换逻辑，并且新增了跨网络、跨地域、跨账号等深度触达方式，方便企业大客户做深层次的安全、隔离等定制；
• 在此基础上，阿里云 EventBridge 首次推出事件驱动应用中心，内置常见的事件驱动应用模板，用户无需代码和部署即可简单配置完成常见的事件 ETL 处理、数据同步等场景功能。

阿里云拥有最广泛的云原生客户群体。随着更多的企业客户上云，将有更多复杂的场景，对于云原生技术、产品以及云原生理念提出更高的要求。阿里云希望跟社会各界的朋友一起在云原生领域里面做更多的探索，希望通过云原生技术，真正为企业带来更多的业务价值，助力企业整体的业务创新。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

前言

最近在学习一些关于响应式编程方面的内容，而在响应式编程中，响应式流（Reactive Stream，Java 9+）发挥了重要作用，在操作流的过程中，我发现其使用了大量的 Lambda 表达式及双冒号语法，这两个特性是 Java 8 出现并应用的，以前我也有过了解与使用，因此在这里对这两块内容进行梳理巩固并加以总结。

正文

匿名类

想要真正去理解 Lambda 表达式，我认为应该先从匿名类开始说起。

遥记那年冬天的第一场雪，比以往来得更晚一些……一帮初出茅庐、仍未褪去稚气的热血少年，正襟危坐的围坐在舒适温暖的教室里，用一双双渴望知识的眼神，注视着老师在黑板上郑重写下的四个大字——Java。不错，我们的 Java 学习之旅就此拉开了帷幕……

咳，扯远了、扯远了，闲话少说，圆规正转！！

在刚学习 Java 课程时，老师给的期末课程设计题目就是设计一款 Java GUI 应用，传送门：blog.csdn.net/weixin_4365…

现在想想仍是头大，不过还好在那时头比较铁，硬着头皮给磨了出来，虽然挺垃圾，但那也是我第一次敲代码搞到凌晨三点钟，一下子就把优秀程序猿必备的特质给抓的死死的，祸兮福所倚、福兮祸所伏，果不其然，第二天我就多掉了两根头发，使本就不富裕的脑袋瓜子又雪上加霜……

好像又扯远了。。。

在 Java GUI 应用中，存在多种监听器，如：ActionListener、KeyListener、MouseListener 等，它们都是以接口的形式存在，实现它们的类就是一个发挥具体作用的监听器。

以 ActionListener 接口为例，它只存在一个需要重写的方法：

1
2
3

java复制代码public interface ActionListener extends EventListener {
    public void actionPerformed(ActionEvent e);
}

设想这样一个场景，我们设计了一个登录的 JFrame 窗体（就是 B/S 中常说的登录表单），当我们输入账号密码后，点击登录按钮就会把身份信息提交给系统，由系统判断身份的合法性，从而提示登录成功或失败。

与 B/S 系统中提交登录表单思想一样，我们需要在点击登录按钮时，触发一个事件，这个事件的处理逻辑应为：获取用户输入的账号密码，提交给系统进行身份验证。

此时我们就要用 Java GUI 中的监听器来完成，以实现 ActionListener 的监听器为例，我们只需按上述处理逻辑重写其接口方法，最后将这个实现的监听器绑定到登录按钮上就可以了。

Talk is 糊里糊涂，Show you code：

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

java复制代码btn_login.addActionListener(new ActionListener() {
    @Override
    public void actionPerformed(ActionEvent e) {
        String username = txt_tel.getText(); // 获取账号
        String password = txt_pwd.getText(); // 获取密码
        if (validateUser(username, password)) {
            // …… 如果用户身份正确，登录成功
        } else {
            // …… 如果用户身份错误，登录失败
        }
    }
});

其中 btn_login.addActionListener(...) 就是为登录按钮绑定一个以匿名类方式实现的 ActionListener 监听器，并编写了登录时的处理逻辑。

好了，我们来分析一下这个匿名类，它并不像我们平常所看到的使用 class 等关键词定义的类，而是直接 new 出来的，其实如果我们换一种编写方式，就会好理解很多。首先实现一个监听器，实现登录处理逻辑：

1
2
3
4
5
6

java复制代码class LoginListener implements ActionListener {
    @Override
    public void actionPerformed(ActionEvent e) {
        // …… 与上面一致的登录逻辑
    }
}

之后我们把这个监听器对象绑定到登录按钮：

1

java复制代码btn_login.addActionListener(new LoginListener())

这种方式与上面匿名类所实现的功能完全一致。

经过这两种实现方式的对比，我们可以发现，匿名类其实就是某类的实现子类去掉其声明头，只保留方法体。有些拗口，大家自己捋捋~

可能在刚接触匿名类的时候会有些许的不适应，但到后面用熟练了，那可是真香，为啥呢？

很明显的一个优点是使用匿名类就不必再去使用 class 、 implements 等关键词去定义新的类（而且也不用绞尽脑汁、脚趾抠地，去想新类的名字了），而是直接使用 new + 父类类名 的方式实现相应的处理逻辑，简单快捷，岂不美哉！！！（说是这么说，如果真碰到有复杂处理逻辑的匿名类，还是得去单独创建一个子类，使结构更加清晰）。

就这样，我算是入了匿名类的坑，以至于到后面遇到了更多的可以使用匿名类的一些场景，比如自定义一个排序比较器：

1
2
3
4
5
6
7
8

java复制代码List<String> itemList = new ArrayList<>();
itemList.add("Eric"); itemList.add("CoderGeshu");
itemList.sort(new Comparator<String>() { // 进行排序
    @Override
    public int compare(String s1, String s2) {
        return s1.length() - s2.length();
    }
});

上述代码表示将 itemList 中的元素按照字符串长度进行排序。

这样看来，使用匿名类的方式是不是已经很简便了？

但是呢，有些人就总是想更懒一点，能少写几行代码就少写几行代码，能少用几个字母就少用几个字母（我可是勤快滴很），因此，直至 Java 8，Java Lambda 表达式诞生了……

Lambda 表达式

在 Java 8 中，出现了这样的一个注解：@FunctionalInterface，翻译成中文为函数式接口，在此接口的官方介绍中，提到：

1
2
3

sql复制代码Conceptually, a functional interface has exactly one abstract method.
……
Note that instances of functional interfaces can be created with lambda expressions, method references, or constructor references.

即一个函数式接口只有一个抽象方法，并说明了其实例可以用 Lambda 表达式、方法引用或构造函数引用来创建。

所以自 Java 8 开始，只要带有 @FunctionalInterface 注解的接口，就是仅有单个抽象方法的函数式接口，可以使用 Lambda 表达式来创建相应实例。（提一嘴：仅有单个抽象方法的接口并不等同于接口中只包含一个方法哦~）

那么 Lambda 表达式到底是个什么东东？它又是怎样的用法儿？

我们先来看两个例子，首先还是上面的登录场景，这次我们使用 Lambda 表达式来进行改写：

1
2
3
4
5
6
7
8
9

java复制代码btn_login.addActionListener((ActionEvent e) -> {
    String username = txt_tel.getText();
    String password = new String(txt_password.getPassword());
    if (validateUser(username, password)) {
        // …… 如果用户身份正确，登录成功
    } else {
        // …… 如果用户身份错误，登录失败
    }
});

这次更加简洁，直接把 new 关键字、类名、方法名等都去掉了，只保留了 (参数) -> { 方法体 } 这样的代码段。

那我们再来改写一下上面的排序器看看：

1
2
3

java复制代码List<String> itemList = new ArrayList<>();
itemList.add("Eric"); itemList.add("CoderGeshu");
itemList.sort((s1, s2) -> s1.length() - s2.length()); // 排序

我直接 WTF ？？这是个啥东西？？这样就能把上面那种排序功能给实现了？？

使用这种方式运行了一遍，还真他娘的管用，终究是我道行太浅了。

既然不懂，那就学呗，经过一阵叮咚哐啷地捣鼓，总算是掌握了关于 Java Lambda 表达式的使用方法，并且最终我果然喜新厌旧，抛弃了伴我良久的匿名类。。。

所以，就让我来简单介绍一下 Java Lambda 表达式的几种用法吧。

首先要说的是 Lambda 表达式的标准形式：(参数类型 参数名称) ‐> { 方法体 }

只有参数列表和方法体，中间再用 -> 指向连接，不过这里有几点说明：

1. 如果小括号里没有参数就留空 ()，如果存在多个参数就用逗号分隔；
2. -> 是 Java 8 Lambda 的语法格式；
3. 大括号内是编写方法体的地方，与传统方法体基本一致。

大家可以看到在上面的例子中，我写的形式与标准形式多多少少还是存在些不同，这是因为在 Lambda 标准形式的基础上，我们还可以省略部分内容，这些内容可以由 Lambda 表达式从上下文自行推断：

1. 参数：小括号内的参数类型可以省略，如果小括号中只有一个参数，那么连小括号也可以省略；
2. 方法体：如果大括号内的方法体只有一条语句，无论是否有返回值，都可以省略大括号、return 关键字及语句分号。

好了，了解了这些使用方法，我们就带着它们应用在具体例子上来看一看。

情况一：接口不含参数、无返回值

假如我们需要有一个显示器，来显示相应的信息。首先我们创建一个接口：

1
2
3
4

java复制代码@FunctionalInterface
public interface Displayer {
    void display();
}

当前接口只有一个无参无返回值的抽象方法，所以当我们使用 @FunctionalInterface 注解进行标记时 IDE 不会报错，如果接口里存在的抽象方法不唯一，就会编译报错。

当我们想要使用此接口显示信息时，按照传统的方法，首先想到的就是先创建一个具体实现类，然后调用实现类中的 display() 方法：

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

java复制代码class DisplayImpl implements Displayer {
    @Override
    public void display() {
        System.out.println("I'm CoderGeshu");
    }
}

public class Test {
    public static void main(String[] args) {
        Displayer displayer = new DisplayImpl();
        displayer.display();
    }
}

输出结果：

I’m CoderGeshu

但是如果 DisplayImpl 类只是为了实现 Display 接口而存在，并且只被使用了一次，那么就应该使用匿名内部类来简化这一操作：

1
2
3
4
5
6
7
8
9
10
11

java复制代码public class Test {
    public static void main(String[] args) {
        Displayer displayer = new Displayer() {
            @Override
            public void display() {
                System.out.println("I'm CoderGeshu");
            }
        };
        displayer.display();
    }
}

上面都是在 Java 支持 Lambda 表达式前的做法，如果使用的是 Java 8+，我们就可以使用 Lambda 表达式进一步简化，并且根据上面 Lambda 的标准形式以及省略表达（无参无返回值），我们可以这样编写：

1
2
3
4
5
6
7

java复制代码public class Test {
    public static void main(String[] args) {
        // 不含参数，所以使用()，方法体中只有一条语句，所以省略大括号
        Displayer displayer = () -> System.out.println("I'm CoderGeshu");
        displayer.display();
    }
}

一行代码就搞定了上面几行代码所完成的功能。

当然这也是最简洁最理想的情况，是应用 Lambda 的意义所在，就如是选择实现类还是选择匿名类一样，如果你在 Lambda 表达式里处理很复杂的逻辑操作，那倒还不如老老实实的创建一个具体类，否则就会导致程序的可读性大大降低。

情况二：接口中含有参数

向接口中增加 info 参数：

1
2
3
4

java复制代码@FunctionalInterface
public interface Displayer {
    void display(String info); 
}

标准形式的 Lambda 表达式为：

1
2

java复制代码Displayer displayer = (String e) -> { System.out.println(e); };
displayer.display("I'm CoderGeshu");

但是因为只有一个参数，所以可省略小括号，由于方法体中只有一条语句，又可以省略大括号，所以简化后的表达式：

1
2

java复制代码Displayer displayer = e -> System.out.println(e);
displayer.display("I'm CoderGeshu");

情况三：接口方法含有返回值

1
2
3
4

java复制代码@FunctionalInterface
public interface Displayer {
    int infoLength(String info); // 增加返回值
}

其 Lambda 表达式：

1
2
3

java复制代码Displayer displayer = (e) -> { return e.length(); };
int infoLength = displayer.infoLength("I'm CoderGeshu");
System.out.println(infoLength);

由于方法体中只有一条 return 语句，则可以省略大括号与 return 关键字

1
2
3

java复制代码Displayer displayer = (e) -> e.length();
int infoLength = displayer.infoLength("I'm CoderGeshu");
System.out.println(infoLength);

输出结果：

14

Lambda 总结

经过上面几个示例的介绍，相信大家对 Lambda 的使用有了更近一步的掌握，为了加深印象，这里再对贴一下总结。

使用 Lambda 的前提

• 使用 Lambda 表达式必须具有接口，无论这个接口是 JDK 内置的接口还是自定义接口，都要求接口中有且仅有一个抽象方法（函数式接口）。
• 使用 Lambda 必须具有上下文推断。也就是方法的参数或局部变量类型必须为 Lambda 对应的接口类型，才能使用 Lambda 作为该接口的实例。

标准形式：(参数类型 参数名称) ‐> { 方法体 }

• 参数：
  • 如果小括号里没有参数就使用空 ()，不可省略；
  • 小括号内的参数类型可以省略；
  • 如果只存在一个参数，可以省略小括号；
  • 如果存在多个参数，则参数名称之间使用逗号分隔，小括号不可省略；
• 方法体：
  • 如果大括号内的方法体只有一条语句，无论是否有返回值，都可以省略大括号、return 关键字及语句分号。
  • 如果方法体处理逻辑过于臃肿复杂，建议使用具体子类改写，保证可读性。

双冒号语法

其实对于上述的 Lambda 表达式，还可以进一步做代码简化，这就用到了 Java 8 中的另一个新特性：双冒号语法。

抽取其中的一个例子，就拿集合排序来说吧，用 Lambda 表达式是这样写的：

1
2
3
4
5
6
7
8

java复制代码List<String> itemList = new ArrayList<>();
itemList.add("Eric"); itemList.add("CoderGeshu");
itemList.sort(new Comparator<String>() {
    @Override
    public int compare(String s1, String s2) {
        return s1.length() - s2.length();
    }
});

如果使用双冒号语法进行简化，则可以改为：

1
2
3

java复制代码List<String> itemList = new ArrayList<>();
itemList.add("Eric"); itemList.add("CoderGeshu");
itemList.sort(Comparator.comparingInt(String::length));

是不是更加简洁了？？

双冒号语法非常简单，其使用格式为： 类名::方法名

没有其他任何复杂的处理，注意双冒号前使用的是类名，双冒号后使用方法名，并且不带 ()。

比如：

1
2
3
4
5
6
7

java复制代码user -> user.getName(); // user是实列对象
// 可以改写成：
User::getName;  // User是类名

() -> new HashMap<>();
// 可以替换成
HashMap::new;

Java 8 引入双冒号操作，在一些场景中非常有用，特别是在 Stream 的操作中，通过理解函数式接口可以更好地理解其原理，关于 Stream 流操作，这里就不再详述了，大家有兴趣可以去看下这篇文章：blog.csdn.net/mu_wind/art…

作者信息

大家好，我是 CoderGeshu，一位爱养爬的程序猿，如果这篇文章对您有所帮助，别忘了点赞收藏哦

点击关注👉 CoderGeshu，第一时间获取最新分享~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

文章首发于我的公众号「程序员cxuan」，欢迎大家关注呀～

说到做到！

之前有位读者给我留言说想要了解一下什么是 MQTT 协议，顺便还把我夸了一把，有点不好意思啦。

那么读者的要求必须要满足啊，所以现在 @一下这位小姐姐，来听课啦！

什么是 MQTT 协议

MQTT 协议的全称是 Message Queuing Telemetry Transport，翻译为消息队列传输探测，它是 ISO 标准下的一种基于发布 - 订阅模式的消息协议，它是基于 TCP/IP 协议簇的，它是为了改善网络设备硬件的性能和网络的性能来设计的。MQTT 一般多用于 IoT 即物联网上，广泛应用于工业级别的应用场景，比如汽车、制造、石油、天然气等。

在了解了 MQTT 的概念和应用场景后，我们下来就来走进 MQTT 的学习中了，先来看一下 MQTT 有哪些概念。

MQTT 基础

上面我们解释了 MQTT 协议的基本概念，MQTT 协议总结一点就是一种轻量级的二进制协议，MQTT 协议与 HTTP 相比具有一个明显的优势：数据包开销较小，数据包开销小就意味着更容易进行网络传输。还有一个优势就是 MQTT 在客户端容易实现，而且具有易用性，非常适合当今资源有限的设备。

你可能对这些概念有些讳莫如深，为什么具有 xxx 这种特性呢？这就需要从 MQTT 的设计说起了。

MQTT 协议由 Andy Stanford-Clark (IBM) 和 Arlen Nipper（Arcom，现为 Cirrus Link）于 1999 年发明。 他们需要一种通过卫星连接石油管道的协议，以最大限度地减少电池损耗和带宽。所以他们为这个协议规定了几种要求：

• 这个协议必须易于实现；
• 这个协议中的数据必须易于传输，消耗成本小；
• 这个协议必须提供服务质量管理；
• 这个协议必须支持连续的会话控制
• 假设数据不可知，不强求传输数据的类型与格式，保持灵活性。

这些设计也是 MQTT 的精髓所在，MQTT 经过不断的发展，已经成为了物联网 IoT 所必备的一种消息探测协议，官方强烈推荐使用的版本是 MQTT 5。

发布 - 订阅模式

发布 - 订阅模式我相信接触消息中间件架构的同学都听过，这是一种传统的客户端 - 服务器架构的替代方案，因为一般传统的客户端-服务器是客户端能够直接和服务器进行通信。

但是发布 - 订阅模式 pub/sub就不一样了，发布订阅模式会将发送消息的发布者 publisher与接收消息的订阅者 subscribers进行分离，publisher 与 subscribers 并不会直接通信，他们甚至都不清楚对方是否存在，他们之间的交流由第三方组件 broker 代理。

pub/sub 最重要的方面是 publisher 与 subscriber 的解藕，这种耦合度有下面三个维度：

• 空间解耦：publisher 与 subscriber 并不知道对方的存在，例如不会有 IP 地址和端口的交互，也更不会有消息的交互。
• 时间解藕：publisher 与 subscriber 并不一定需要同时运行。
• 同步 Synchronization 解藕：两个组件的操作比如 publish 和 subscribe 都不会在发布或者接收过程中产生中断。

总之，发布/订阅模式消除了传统客户-服务器之间的直接通信，把通信这个操作交给了 broker 进行代理，并在空间、时间、同步三个维度上进行了解藕。

可拓展性

pub/sub 比传统的客户端-服务器模式有了更好的拓展，这是由于 broker 的高度并行化，并且是基于事件驱动的模式。可拓展性还体现在消息的缓存和消息的智能路由，还可以通过集群代理来实现数百万的连接，使用负载均衡器将负载分配到更多的单个服务器上，这就是 MQTT 的深度应用了。

你可能不明白什么是事件驱动，我在这里解释下事件驱动的概念。

事件驱动是一种编程范式，编程范式是软件工程中的概念，它指的是一种编程方法或者说程序设计方式，比如说面向对象编程和面向过程编程就是一种编程范式，事件驱动中的程序流程会由诸如用户操作（点击鼠标、键盘）、传感器输出或者从其他程序或传递的消息事件决定。事件驱动编程是图形用户界面和其他应用程序比如 Web 中使用的主要范式，这些应用程序能够响应用户输入执行某些操作为中心，这同时也适用于驱动程序的编程。

消息过滤

在 pub/sub 的架构模式中，broker 扮演着至关重要的作用，其中非常重要的一点就是 broker 能够对消息进行过滤，使每个订阅者只接收自己感兴趣的消息。

broker 有几个可以过滤的选项

• 基于主题的过滤

MQTT 是基于 subject 的消息过滤的，每条消息都会有一个 topic ，接收客户端会向 borker 订阅感兴趣的 topic，订阅后，broker 就会确保客户端收到发布到 topic 中的消息。

• 基于内容的过滤

在基于内容的过滤中，broker 会根据特定的内容过滤消息，接受客户端会经过过滤他们感兴趣的内容。这种方法的一个显著的缺点就是必须事先知道消息的内容，不能加密或者轻易修改。

• 基于类型的过滤

在使用面向对象的语言时，基于消息（事件）的类型过滤是一种比较常见的过滤方式。

为了发布/订阅系统的挑战，MQTT 具有三个服务质量级别，你可以指定消息从客户端传到 broker 或者从 broker 传到客户端，在 topic 的订阅中，会存在 topic 没有 subscriber 订阅的情况，作为 broker 必须知道如何处理这种情况。

MQTT 与消息队列的区别

我们现在知道，MQTT 是一种消息队列传输探测协议，这种协议是看似是以消息队列为基础，但却与消息队列有所差别。

在传统的消息队列模式中，一条消息会存储在消息队列中等待被消费，每个传入的消息都存储在消息队列中，直到它被客户端（通常称之为消费者）所接收，如果没有客户端消费消息的话，这条消息就会存在消息队列中等待被消费。但是在消息队列中，不会存在消息没有客户端消费的情况，但是在 MQTT 中，确存在 topic 无 subscriber 订阅的情况。

在传统的消息队列模式中，一条消息只能被一个客户端所消费，负载会分布在队列的每个消费者之间；而在 MQTT 中，每个订阅者都会受到消息，每个订阅者有相同的负载。

在传统的消息队列模式中，必须使用单独的命令来显式创建队列，只有队列创建后，才可以生产或者消费消息；而在 MQTT 中，topic 比较灵活，可以即时创建。

HiveMQ 现在是开源的，HiveMQ 社区版实现了 MQTT broker 规范，并兼容了 MQTT 3.1、3.1.1 和 MQTT 5。HiveMQ MQTT Client 是一个基于 Java 的 MQTT 客户端实现，兼容 MQTT 3.1.1 和 MQTT 5。这两个项目都可以在 HiveMQ 的 github github.com/hivemq 上找到。

我们知道，broker 将 publisher 和 subscriber 进行分离，因此客户端的连接由 broker 代理，所以在我们深入理解 MQTT 之前，我们需要先知道客户端和代理的含义。

MQTT 重要概念

MQTT client

当我们讨论关于客户端的概念时，一般指的就是 MQTT Client，publisher 和 subscriber 都属于 MQTT Client。之所以有发布者和订阅者这个概念，其实是一种相对的概念，就是指当前客户端是在发布消息还是在接收消息，发布和订阅的功能也可以由同一个 MQTT Client 实现。

MQTT 客户端是指运行 MQTT 库并通过网络连接到 MQTT broker 的任何设备，这些设备可以从微控制器到成熟的服务器。基本上，任何使用 TCP/IP 协议使用 MQTT 设备的都可以称之为 MQTT Client。MQTT 协议的客户端实现非常简单直接。易于实施是 MQTT 非常适合小型设备的原因之一。 MQTT 客户端库可用于多种编程语言。 例如，Android、Arduino、C、C++、C#、Go、iOS、Java、JavaScript 和 .NET。

MQTT broker

与 MQTT client 对应的就是 MQTT broker，broker 是任何发布/订阅机构的核心，根据实现的不同，代理可以处理多达数百万连接的 MQTT client。

broker 负责接收所有消息，过滤消息，确定是哪个 client 订阅了每条消息，并将消息发送给对应的 client，broker 还负责保存会话数据，这些数据包括订阅的和错过的消息。broker 还负责客户端的身份验证和授权。

MQTT Connection

MQTT 是基于 TCP/IP 协议基础之上的，所以 MQTT 的 client 和 broker 都需要 TCP/IP 协议的支持。

MQTT 的连接总是在 client 和 broker 之间进行，client 和 client 之间并不会相互连接。如果要发起连接的话，那么 client 就会向 broker 发起 CONNECT 消息，代理会使用 CONNACK 消息和状态码进行响应。一旦 client 和 broker 的连接建立后，broker 就会使客户端的连接一直处于打开状态，直到 client 发出断开命令或者连接中断。

消息报文

MQTT 的消息报文主要分为 CONNECT 和 CONNACK 消息。

CONNECT

我们上面提到了为了初始化连接，需要 client 向 broker 发送 CONNECT 消息，如果这个 CONNECT 消息格式错误或者打开套接字（因为基于 TCP/IP 协议栈需要初始化 Socket 连接）时间过长，亦或是发送连接消息时间过长的话，broker 就会关闭这条连接。

一个 MQTT 客户端发送一条 CONNECT 连接，这条 CONNECT 连接可能会包含下面这些信息：

我这里解释一下这些信息都是什么概念

• ClientId：显而易见，这个就是每个客户端的 ID 标识，也就是连接到 MQTT broker 的每个 client。这个 ID 应该是每个 client 和 broker 唯一的，如果你不需要 broker 持有状态的话，你可以发送一个空的 ClientId，空的 ClientId 会没有任何状态。在这种情况下，ClientSession 需要设置为 true，否则将会拒绝连接。

clientSession 是什么我们下面会说。

• CleanSession：CleanSession 会话标志会告诉 broker client 是否需要建立持久会话。在持久会话 （CleanSession = false）中，broker 存储 client 的所有订阅以及服务质量(Qos) 是 1 或 2 订阅的 client 的所有丢失的消息。如果会话不是持久的（CleanSession = true），那么 broker 则不会为 client 存储任何内容并且会清除先前持久会话中的所有信息。
• Username/Password ：MQTT 会发送 username 和 password 进行 client 认证和授权。如果此信息没有经过加密或者 hash ，那么密码将会以纯文本的形式发送。所以，一般强烈建议 username 和 password 要经过加密安全传输。像 HiveMQ 这样的 broker 可以与 SSL 证书进行身份验证，因此不需要用户名和密码。
• LastWillxxx ：LastWillxxx 表示的是遗愿，client 在连接 broker 的时候将会设立一个遗愿，这个遗愿会保存在 broker 中，当 client 因为非正常原因断开与 broker 的连接时，broker 会将遗愿发送给订阅了这个 topic（订阅遗愿的 topic）的 client。
• keepAlive：keepAlive 是 client 在连接建立时与 broker 通信的时间间隔，通常以秒为单位。这个时间指的是 client 与 broker 在不发送消息下所能承受的最大时长。

在聊完 client 与 broker 之间发送建立连接的 CONNECT 消息后，我们再来聊一下 broker 需要对 CONNECT 进行确认的 CONNACK 消息。

CONNACK

当 broker 收到 CONNECT 消息时，它有义务回复 CONNACK 消息进行响应。CONNACK 消息包括两部分内容

• SessionPresent：会话当前标识，这个标志会告诉 client 当前 broker 是否有一个持久性会话与 client 进行交互。SessionPresent 标志和 CleanSession 标志有关，当 client 在 CleanSession 设置为 true 的情况下连接时，SessionPresent 始终为 false，因为没有持久性会话可以使用。如果 CleanSession 设置为 false，则有两种可能性，如果 ClientId 的会话信息可用，并且 broker 已经存储了会话信息，那么 SessionPresent 为 true，否则如果没有 ClientId 的任何会话信息，那么 SessionPresent 为 false。

• ReturnCode：CONNACK 消息中的第二个标志是连接确认标志。这个标志包含一个返回码，告诉客户端连接尝试是否成功。连接确认标志有下面这些选项。

关于每个连接的详细说明，可以参考 docs.oasis-open.org/mqtt/mqtt/v…

消息类型

发布

当 MQTT client 在连接到 broker 之后就可以发送消息了，MQTT 使用的是基于 topic 主题的过滤。每条消息都应该包含一个 topic ，broker 可以使用 topic 将消息发送给感兴趣的 client。除此之外，每条消息还会包含一个负载(Payload)，Payload 中包含要以字节形式发送的数据。

MQTT 是数据无关性的，也就是说数据是由发布者 - publisher 决定要发送的是 XML 、JSON 还是二进制数据、文本数据。

MQTT 中的 PUBLISH 消息结构如下。

• Packet Identifier：这个 PacketId 标识在 client 和 broker 之间唯一的消息标识。packetId 仅与大于零的 Qos 级别相关。
• TopicName：主题名称是一个简单的字符串，/ 代表着分层结构。
• Qos：这个数字表示的是服务质量水平，服务质量水平有三个等级：0、1 和 2，服务级别决定了消息到达 client 或者 broker 的保证类型，来决定消息是否丢失。
• RetainFlag：这个标志表示 broker 将最近收到的一条 RETAIN 标志位为true的消息保存在服务器端（内存或者文件）。

MQTT 服务器只会为每一个 Topic 保存最近收到的一条 RETAIN 标志位为true的消息。也就是说，如果MQTT 服务器上已经为某个 Topic 保存了一条 Retained 消息，当客户端再次发布一条新的 Retained 消息时，那么服务器上原来的那条消息会被覆盖。

• Payload：这个是每条消息的实际内容。MQTT 是数据无关性的。可以发送任何文本、图像、加密数据以及二进制数据。
• Dupflag：这个标志表示该消息是重复的并且由于预期的 client 或者 broker 没有确认所以重新发送了一次。这个标志仅仅与 Qos 大于 0 相关。

当 client 向 broker 发送消息时，broker 会读取消息，根据 Qos 的级别进行消息确认，然后处理消息。处理消息其实就是确定哪些 subscriber 订阅了 topic 并将消息发送给他们。

最初发布消息的 client 只关心将 PUBLISH 消息发送给 broker，一旦 broker 收到 PUBLISH 消息，broker 就有责任将其传递给所有 subscriber。发布消息的 client 不会知道是否有人对发布的消息感兴趣，同时也不知道多少 client 从 broker 收到了消息。

订阅

client 会向 broker 发送 SUBSCRIBE 消息来接收有关感兴趣的 topic，这个 SUBSCRIBE 消息非常简单，它包含了一个唯一的数据包标识和一个订阅列表。

• Packet Identifier：这个 PacketId 和上面的 PacketId 一样，都表示消息的唯一标识符。
• ListOfSubscriptions：SUBSCRIBE 消息可以包含一个 client 的多个订阅，每个订阅都会由一个 topic 和一个 Qos 构成。订阅消息中的 topic 可以包含通配符。

确认消息

client 在向 broker 发送 SUBSCRIBE 消息后，为了确认每个订阅，broker 会向 client 发送 SUBACK 确认消息。这个 SUBACK 包含原始 SUBSCRIBE 消息的 packetId 和返回码列表。

其中

• Packet Identifier ：这个数据包标识符和 SUBSCRIBE 中的相同。
• ReturnCode：broker 为每个接收到的 SUBSCRIBE 消息的 topic/Qos 对发送一个返回码。例如，如果 SUBSCRIBE 消息有五个订阅消息，则 SUBACK 消息包含五个返回码作为响应。

到现在我们已经探讨过了三种消息类型，发布 - 订阅 - 确认消息，这三种消息的示意图如下。

退订

SUBSCRIBE 消息对应的是 UNSUBSCRIBE 消息，这条消息发送后，broker 会删除关于 client 的订阅。所以，UNSUBSCRIBE 消息与 SUBSCRIBE 消息类似，都具有 packetId 和 topic 列表。

确认退订

取消订阅也需要 broker 的确认，此时 broker 会向 client 发送一个 UNSUBACK 消息，这个 UNSUBACK 消息非常简单，只有一个 packetId 数据标识符。

退订和确认退订的流程如下。

当 client 收到来自 broker 的 UNSUBACK 消息后，就可以认为 UNSUBSCRIBE 消息中的订阅被删除了。

聊聊 Topic

聊了这么多关于 MQTT 的内容，但是我们还没有好好聊过 Topic。在 MQTT 中，Topic 是指 broker 为每个连接的 client 过滤消息的 UTF-8 字符串。Topic 是一种分层的结构，可以由一个或者多个 Topic 组成。每个 Topic 由 / 进行分割。

与传统的消息队列相比，MQTT Topic 非常轻量级，client 在发布或订阅之前不需要先创建所需要的 Topic，broker 在接收每个 Topic 前不用进行初始化操作。

通配符

当客户端订阅 Topic 时，它可以订阅已发布消息的确切 Topic，也可以使用通配符来同时订阅多个 Topic。通配符有两种：单级和多级。

单级通配符

单级通配符可以替换 Topic 的一个级别，+ 号代表 Topic 中的单级通配符。

如果 Topic 包含任意字符串而不是通配符，则任何 Topic 都能够和单级通配符匹配。例如

myhome/groundfloor/+/temperature 就有下面这几种匹配方式。

多级通配符

多级通配符涵盖多个 Topic，# 代表 Topic 中的多级通配符。为了让 broker 能够确定和哪些 Topic 匹配，多级通配符必须作为 Topic 中的最后一个字符放置，并以 / 开头。

下面是 myhome/groundfloor/# 的几个例子

当 client 订阅带有多级通配符的 Topic 时，不论 Topic 有多长多深，它都会收到通配符之前 Topic 的所有消息。如果你只将 Topic 定义为 # 的话，那么你将会收到所有的消息。

我自己肝了六本 PDF，全网传播超过10w+ ，微信搜索「程序员cxuan」关注公众号后，在后台回复 cxuan ，领取全部 PDF，这些 PDF 如下

六本 PDF 链接

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

背景

上个月跟朋友一起做了个微信小程序，趁着5.20节日的热度，两个礼拜内迅速积累了一百多万用户，我们在小程序页面增加了收集formid的埋点，用于给微信用户发送模板消息通知。

随着数据量的增大，之前使用的服务器空间开始有点不够用，最近新写了一个专门用于做小程序后台开发的框架，于是想把原来的数据迁移到新系统的数据库。买了一台4核8G的机器，开始做数据迁移。下面对迁移过程做一个简单的记录。

方案选择

mysqldump迁移

平常开发中，我们比较经常使用的数据备份迁移方式是用mysqldump工具导出一个sql文件，再在新数据库中导入sql来完成数据迁移。试验发现，通过mysqldump导出百万级量的数据库成一个sql文件，大概耗时几分钟，导出的sql文件大小在1G左右，然后再把这个1G的sql文件通过scp命令复制到另一台服务器，大概也需要耗时几分钟。在新服务器的数据库中通过source命令来导入数据，我跑了一晚上都没有把数据导入进来，cpu跑满。

脚本迁移

直接通过命令行操作数据库进行数据的导出和导入是比较便捷的方式，但是数据量较大的情况下往往会比较耗时，对服务器性能要求也比较高。如果对数据迁移时间要求不是很高，可以尝试写脚本来迁移数据。虽然没有实际尝试，但是我想过大概有两种脚本方案。

第一种方式，在迁移目标服务器跑一个迁移脚本，远程连接源数据服务器的数据库，通过设置查询条件，分块读取源数据，并在读取完之后写入目标数据库。这种迁移方式效率可能会比较低，数据导出和导入相当于是一个同步的过程，需要等到读取完了才能写入。如果查询条件设计得合理，也可以通过多线程的方式启动多个迁移脚本，达到并行迁移的效果。

第二种方式，可以结合redis搭建一个“生产+消费”的迁移方案。源数据服务器可以作为数据生产者，在源数据服务器上跑一个多线程脚本，并行读取数据库里面的数据，并把数据写入到redis队列。目标服务器作为一个消费者，在目标服务器上也跑一个多线程脚本，远程连接redis，并行读取redis队列里面的数据，并把读取到的数据写入到目标数据库。这种方式相对于第一种方式，是一种异步方案，数据导入和数据导出可以同时进行，通过redis做数据的中转站，效率会有较大的提升。

可以使用go语言来写迁移脚本，利用其原生的并发特性，可以达到并行迁移数据的目的，提升迁移效率。

文件迁移

第一种迁移方案效率太低，第二种迁移方案编码代价较高，通过对比和在网上找的资料分析，我最终选择了通过mysql的。

1

sql复制代码select data into outfile file.txt、load data infile file.txt into table

的命令，以导入导出文件的形式完成了百万级数据的迁移。

迁移过程

在源数据库中导出数据文件

1

csharp复制代码select * from dc_mp_fans into outfile '/data/fans.txt';

复制数据文件到目标服务器

1

ruby复制代码zip fans.zip /data/fans.txtscp fans.zip root@ip:/data/

在目标数据库导入文件

1
2

less复制代码unzip /data/fans.zip
load data infile '/data/fans.txt' into table wxa_fans(id,appid,openid,unionid,@dummy,created_at,@dummy,nickname,gender,avatar_url,@dummy,@dummy,@dummy,@dummy,language,country,province,city,@dummy,@dummy,@dummy,@dummy,@dummy,@dummy,@dummy,@dummy,@dummy);

按照这么几个步骤操作，几分钟内就完成了一个百万级数据表的跨服务器迁移工作。

注意项

mysql安全项设置

在mysql执行load data infile和into outfile命令都需要在mysql开启了secure_file_priv选项， 可以通过show global variables like ‘%secure%’;查看mysql是否开启了此选项，默认值Null标识不允许执行导入导出命令。

通过vim /etc/my.cnf修改mysql配置项，将secure_file_priv的值设置为空：

[mysqld] secure_file_priv=''

则可通过命令导入导出数据文件。

导入导出的数据表字段不对应

上面示例的从源数据库的dc_mp_fans表迁移数据到目标数据库的wxa_fans表，两个数据表的字段分别为：

dc_mp_fans

wxa_fans

在导入数据的时候，可以通过设置字段名来匹配目标字段的数据，可以通过@dummy丢弃掉不需要的目标字段数据。

总结

结合本次数据迁移经历，总结起来就是：

小数据量可以使用mysqldump命令进行导入导出，这种方式简单便捷。

数据量较大，且有足够的迁移耐心时，可以选择自己写脚本，选择合适的并行方案迁移数据，这种方式编码成本较高。

数据量较大，且希望能在短时间内完成数据迁移时，可以通过mysql导入导出文件的方式来迁移，这种方式效率较高。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有