【算法】二分查找法

二分查找法模板

https://leetcode-cn.com/leetbook/read/binary-search/x6q6fi/

模板一

二分查找法的标准模板适用于只需要寻找某一个符合条件的值

  • 初始化 right = nums.length - 1
  • 更新区间时:left = mid + 1right = mid - 1
  • 查找的区间为 [left, right],左闭右闭
  • 跳出 while 循环的条件是 left == right + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int binarySearch(int[] nums, int target) {
if(nums == null || nums.length == 0)
return -1;

int left = 0;
int right = nums.length - 1;
int mid;

while (left <= right) {
mid = left + (right - left >> 1);
if (nums[mid] == target) {
// 只要找到一个目标值即可返回
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
// left == right + 1,如果到这里还没找到说明整个数组里没有任何一个满足条件的元素,返回-1
return -1;
}

模板二

二分查找法的标准模板适用于寻找符合条件的最左边界

  • 初始化 right = nums.length
  • 更新区间时:left = mid + 1right = mid
  • 查找的区间为 [left, right),左闭右开
  • 跳出 while 循环的条件是 left == right

之所以更新右指针为 right = mid

  • 一是因为要求解最左边界,则在 right 更新时需要保存着当前满足条件的值(该值左侧可能还有满足条件的值,需要用 right 保存着当前满足的值),最后跳出循环时其位置就是最左满足条件的值
  • 二是因为查找区间为左闭右开,不包含 right。因此在发现 mid 位置满足条件时,接下来的二分过程中,要令 right = mid,这样 mid 因为右开而不被考虑,mid - 1 能正常被考虑。否则若 right = mid - 1,则下一轮的二分中 mid - 1 就没有被考虑在内,从而漏算了该值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int binarySearch(int[] nums, int target) {
if(nums == null || nums.length == 0)
return -1;

int left = 0;
int right = nums.length;
int mid;

while (left < right) {
mid = left + (right - left >> 1);
if (nums[mid] >= target) {
// 要寻找满足条件的最左区间,因此满足条件也不能退出,而是继续更新右边界
// 右边界要保存着当前满足条件的值
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
// 退出循环时,left == right,需要额外判断一下left位置的元素值是否满足条件
return nums[left] == target ? left : -1;
}

许多求解最左/由边界的题目其实都可以使用模板一,只需要额外借助一个变量 ans,在二分过程中记录下满足条件的值(不要 return),然后继续二分直到跳出循环,这样到最后 ans 就保存了最左/右边界

模板二适合于在遍历过程中,mid 位置很可能就是符合题意的答案,但是因为在二分过程中没有写“遇到答案立即返回”的代码,因此需要考虑到 mid 就是答案的情况,在 right 更新时要包含 mid,不能将其跳过。

关于二分查找法模板的更多细节:https://blog.csdn.net/xiao_jj_jj/article/details/106018702

阅读全文

【算法】回溯算法

回溯算法简介

回溯法采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:

  • 找到一个可能存在的正确的答案;
  • 在尝试了所有可能的分步方法后宣告该问题没有答案。

回溯算法相关的典型题目:https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/

题型一:排列、组合、子集相关问题

提示:这部分练习可以帮助我们熟悉「回溯算法」的一些概念和通用的解题思路。解题的步骤是:先画图,再编码。去思考可以剪枝的条件, 为什么有的时候用 used 数组,有的时候设置搜索起点 begin 变量,理解状态变量设计的想法。

题型二:Flood Fill

题型三:字符串中的回溯问题

题型四:游戏问题

阅读全文

【分布式】幂等性问题

幂等性问题

什么是幂等性

接口幂等性就是用户对同一操作发起的一次请求和多次请求结果是一致的,不会因为多次点击而产生了副作用,比如支付场景,用户购买了商品,支付扣款成功,但是返回结果的时候出现了网络异常,此时钱已经扣了,用户再次点击按钮,此时就会进行第二次扣款,返回结果成功,用户查询余额发现多扣钱了,流水记录也变成了两条。这就没有保证接口幂等性

哪些情况需要防止幂等性问题:

  • 用户多次点击按钮
  • 用户页面回退再次提交
  • 微服务互相调用,由于网络问题,导致请求失败,feign 触发重试机制导致发送重复请求

以 SQL 为例,有些操作是天然幂等的:

  • SELECT * FROM table WHERE id =? 无论执行多少次都不会改变状态
  • UPDATE tab1 SET col1=1 WHERE col2=2 无论执行多少次状态都是一致的
  • DELETE FROM user WHERE userid=1 无论执行多少次状态都是一致的
  • INSERT INTO user(userid, name) VALUES(1, 'a' )userid 为唯一索引 UNIQUE,则无论执行多少次,都只会插入一条用户记录

不是幂等的操作:

  • UPDATE tab1 SET col1=col1+1 WHERE col2=2 每次执行的结果都会发生变化,不是幂等的
  • INSERT INTO user(userid, name) VALUES(1, 'a' )userid 不是唯一索引,则执行多次会重复插入相同的用户记录,不具备幂等性。

幂等性问题解决方案

1. token(令牌)机制

分析一个问题:当用户在前端连续多次点击【提交订单】,会发出多个创建订单的请求 /submitOrder。这会导致同一个订单被创建多次,从而不满足幂等性。因此我们必须要解决幂等性问题,使得一个用户只能同时处理一个订单,其他订单请求都失效。体现在 Redis 里就是同一时刻只能保存唯一的一个订单的 uuid(order:token:userId - uuid)。

解决方案:使用 token(令牌)机制。在购物车页面点击【去结算】时,就在 /toTrade 业务代码中为当前用户生成一个防重令牌(防止重复提交),并保存到 Redis 中(格式为 order:token:userId - uuid)。同时将该令牌保存到 OrderConfirmVo 对象中返回给前端保存。

代码:

1
2
3
4
5
6
// 任务6. 设置防重令牌。随机生成一个 UUID 作为令牌保存到 Reids 中,并且返回给客户端。
// 其在点击【提交订单】时将带上该令牌:key - value = order:token:userId - uuid
String token = UUID.randomUUID().toString().replace("-", "");
redisTemplate.opsForValue().set(OrderConstant.USER_ORDER_TOKEN_PREFIX + memberResponseVo.getId(),
token, 30, TimeUnit.MINUTES);
confirmVo.setOrderToken(token);

这样前端页面在点击【提交订单】按钮后跳转到 /submitOrder 业务时,就会将该防重令牌携带上。此时我们只需要再从 Redis 中根据该用户 id 获取到其保存在 Redis 中的令牌,并与客户端携带上来的令牌进行比较即可。流程:

  • 根据用户 order:token:userId 从 Redis 中获取令牌
  • 判断客户端携带的令牌Redis 中查询的令牌是否相等
  • 如果相等,说明验证成功,从 Redis 中删除令牌
  • 如果不相等,说明验证失败,当前请求是重复请求(或者用户同时开两个网页提交两个订单),拒绝访问,直接返回

这三个步骤的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
SubmitOrderResponseVo responseVo = new SubmitOrderResponseVo();
// 先从 ThreadLocal 中获取当前登录用户的信息
MemberResponseVo memberResponseVo = LoginInterceptor.loginUserThreadLocal.get();
// 获取前端传来的校验令牌
String orderToken = submitVo.getOrderToken();
// 1. 验证令牌。核心是要保证令牌的获取(1.1)、判断(1.2)与删除(1.3)必须是原子性的
// 1.1 去 Redis 中查找当前用户的令牌
String redisToken = redisTemplate.opsForValue().get(OrderConstant.USER_ORDER_TOKEN_PREFIX + memberResponseVo.getId());
// 1.2 判断客户端的令牌和服务端的令牌是否相等
if (orderToken != null && orderToken.equals(redisToken)) {
// 1.3 令牌验证通过。从 Redis 中删除令牌
redisTemplate.delete(OrderConstant.USER_ORDER_TOKEN_PREFIX + memberResponseVo.getId());
} else {
// 令牌不通过
}

注意:这三个操作必须是原子性的。否则高并发场景下会出现问题。因此可以使用 LUA 脚本保证这三个过程的原子性:

1
2
3
4
5
// 原子验证令牌并删除令牌
String script = "if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end";
Long result = redisTemplate.execute(new DefaultRedisScript<>(script, Long.class),
Arrays.asList(OrderConstant.USER_ORDER_TOKEN_PREFIX + memberResponseVo.getId()),
orderToken);

令牌机制的两个潜在问题:

1、先删除 token 还是后删除 token:

  • 先删除可能导致,业务确实没有执行,重试还得带上之前的 token, 由于防重设计导致,请求还是不能执行
  • 后删除可能导致,业务处理成功,但是服务闪断,出现超时,没有删除掉token,别人继续重试,导致业务被执行两次
  • 我们最后设计为先删除 token,如果业务调用失败,就重新获取 token 再次请求(重新跳转回去结算页面或者重新给其生成一个token,保存到redis并还给他

2、Token 获取,比较和删除必须是原子性。可以在 redis 使用 lua 脚本完成这个操作

1
"if redis.call('get',KEYS[1]) == ARGV[1] then return redis.call('del',KEYS[1]) else return 0 end"

2. 各种锁机制

数据库悲观锁

查询时添加悲观锁:SELECT * FROM xxx WHERE id = 1 FOR UPDATE。这样在查询时就会给该行加悲观锁,其他请求都需要阻塞等待。

悲观锁通常伴随事务一起使用,数据锁定时间可能会很长,需要根据实际情况选择是否使用。另外需要注意的是:id 字段一定是主键或唯一索引,不然可能造成锁表的结果,处理起来会非常麻烦。

数据库乐观锁

这种方法适合在更新的场景中:

1
UPDATE t_goods SET count = count - 1, version = version + 1 WHERE good_id = 2 and version = 1

根据 version 版本,也就是在操作数据库存前先获取当前商品的 version 版本号,然后操作的时候带上 version 版本号,这样就保证了不管执行几次该语句,只会真正处理一次。乐观锁主要使用于处理读多写少的问题

业务层分布式锁

如果多个机器可能在同一时间处理相同的数据,比如多台机器定时任务拿到了相同的数据,我们就可以加分布式锁锁定此数据,处理完成后后释放锁,获取锁必须先判断这个数据是否被处理过。

3. 各种唯一约束

数据库唯一约束

插入数据时应该按照唯一索引进行插入。比如为订单号字段 order_sn 添加唯一索引 UNIQUE,这样相同的订单就不可能插入两次,从而实现在数据库层面上防止重复插入。同时需要业务生成全局唯一的字段值,以保证不会同一个订单不会重复插入到数据库中。

示例:为订单号字段 order_sn 添加唯一性索引 UNIQUE,从而做到数据库层面的幂等性:

image-20220117164745600

这个机制利用了数据库的唯一索引约束的特性,解决了插入场景的幂等性问题。如果将主键设置为唯一索引,则需要注意主键不能设置为自增的。

如果是分库分表场景下,设置的路由规则要保证:相同的请求必须路由到同一个数据库和同一表中,不然数据库的唯一索引约束就不起效果了。

Redis Set 防重

一些不能重复的数据可以存放到 Redis 的 Set 结构中,例如百度网盘在防止重复上传相同文件数据时的做法是:第一次保存数据时先计算文件数据的 MD5 值将其放入 Redis 的 Set 中。之后再想重复上传该文件时,先去 Redis 中查看这个 MD5 值是否已经存在,存在就代表该文件数据之前上传过了,不需要再上传了。

4. 防重表

防重不仅可以在 Redis 里做,也可以使用数据库实现。

例如:在取消订单后执行解锁库存时,一旦解锁了库存,就需要在防重表(保存订单号和库存信息,该表设置了订单号 order_sn 为唯一索引 UNIQUE)里插入一条数据,表示该订单已经解锁了库存。之后重复解锁时再想插入到该防重表就会报错(因为设置了订单号的唯一索引 UNIQUE),此时就知道不能再解锁库存了。只有插入到该防重表成功,才可以执行解锁库存的业务。

防止重复解锁库存另一个思路:在工作单详情表里为每一条工作单添加一个字段,代表该工作单是否已被解锁。这样每次解锁前先查看该状态就可以得知是否仍需要解锁。

注意:去重表和业务表应该在同一个库中,这样就保证了在同一个事务,即使业务操作失败,也会把去重表的数据回滚,这个很好的保证了数据的一致性。

5. 全局请求唯一 id

前提:Feign 一旦远程调用失败后,就会不断重试发出相同请求。可能实际上远程服务已经收到了调用请求并且执行了业务,但是因为网络延迟等因素,Feign 认为没有调用成功,从而发出了同样的请求。

为了避免这种情况的发生,我们可以在 Feign 远程调用接口前,先生成一个唯一的 uuid,并存入到 Redis 的 Set 结构中(例如一个用户保存一个 Set,其内保存了该用户所有远程调用请求的 uuid,能够保证不重复)。远程服务在执行业务前先检查 Redis 中该用户的 Set 里是否存在该 uuid,如果存在即代表当前远程请求之前就被处理过了(该请求被重复调用了),那么就不再执行了。

注意:这种方式只适用于 Feign 的远程调用防重。如果是前端页面发来的重复请求是无法防住的(需要使用上面的令牌机制),因为即使使用 Nginx 给每个前端发来的请求添加唯一 id,点击两次前端页面也会发送两个 id 不同的请求,从而无法做到防重。但是 Nginx 添加 id 的思路可以用于实现链路追踪功能。

总结:Feign 防止重复调用可以使用这个方法。但是页面的重复提交防止不了。


在 Nginx 中为每一个请求设置一个唯一 id:

1
proxy_set_header X-Request-Id $Request_id

【算法】排序算法

排序算法总结

时间复杂度 空间复杂度 稳定性
选择排序 O(n2)O(n^2) O(1)O(1) NO
冒泡排序 O(n2)O(n^2) O(1)O(1) YES
插入排序 O(n2)O(n^2) O(1)O(1) YES
归并排序 O(NlogN)O(NlogN) O(N)O(N) YES
快速排序 O(NlogN)O(NlogN) O(logN)O(logN) NO
堆排序 O(NlogN)O(NlogN) O(1)O(1) NO
  • 插入排序的最优时间复杂度为 O(N)O(N),并且是稳定的,适合于数据量小的场景。

  • 快速排序的常数项经过试验是最低的,但是是不稳定的,适合于不需要稳定的数据量大的场景

  • 堆排序的时间复杂度在常数项比快速排序略高,但空间复杂度较低,也是不稳定的

  • 归并排序的空间复杂度是后三者中最高的,但是是稳定的

  • 当元素个数小于 60 时:使用插入排序,插入排序是稳定的,并且最优时间复杂度为 O(N)

  • 当元素个数大于 60 时:根据数据类型选择排序方式:

    • 基础类型:使用快速排序,它的常数项经过试验是最低的,并且不需要保证稳定性
    • 引用类型:使用归并排序,因为需要保证稳定性
阅读全文

【Docker】Docker 配置实战案例

安装 Docker

Docker官网: https://www.docker.com/; Docker中文网站: https://www.docker-cn.com/; Docker Hub官网:https://hub.docker.com/

  1. CentOS 7 安装 Docker:
1
yum install -y docker
  1. 开启 Docker 服务:
1
systemctl start docker.service
  1. 查看安装结果:
1
docker version
  1. 设置开机启动:
1
systemctl enable docker.service
  1. 配置 docker 镜像下载加速。编辑配置⽂件:
1
vim /etc/docker/daemon.json

在其中加入加速镜像源地址即可(https://cr.console.aliyun.com/cn-hangzhou/instances/mirrors):

1
2
3
{
"registry-mirrors": ["https://gc2odbl5.mirror.aliyuncs.com"]
}

加完加速地址后,重新加载配置⽂件,重启docker 服务即可:

1
2
systemctl daemon-reload
systemctl restart docker.service

Docker Hub 镜像仓库地址:https://hub.docker.com/

阅读全文

【MySQL】MySQL 索引

image-20210913132511709

MySQL官方对索引的定义为:索引(Index)是帮助 MySQL 高效查找数据的排好序数据结构。其中,排好序体现在 B+ 树最底层页结构组成的双向链表结构上。

索引的本质:索引是一种数据结构

  • 查找:体现在 WHERE、ON 等条件判断上
  • 排序:体现在 ORDER BY、GROUP BY 分组排序上

索引简介

索引在数据库表的字段上添加,是为了提高查询效率而存在的一种机制。索引是各种数据库进行优化时的重要手段,优化时优先考虑的因素就是索引。一张表的一个字段可以添加一个索引,多个字段联合起来也可以添加索引。

索引相当于一本书的目录,是为了缩小扫描范围而存在的一种机制。MySQL 在查询方面主要是两种方式:

  • 全表扫描:一条一条检索,效率较低
  • 根据索引检索:先通过索引定位大概位置,然后在此局部范围内扫描,效率较高

索引是在 MySQL 的存储引擎层中实现的,而不是在服务器层实现的。所以每种存储引擎的索引都不一定完全相同,也不是所有的存储引擎都支持所有的索引类型的。MySQL 目前提供了以下4种索引:

  • BTREE 索引 : 最常见的索引类型,大部分索引都支持 B 树索引。
  • HASH 索引:只有Memory引擎支持 , 使用场景简单 。
  • R-tree 索引(空间索引):空间索引是MyISAM引擎的一个特殊索引类型,主要用于地理空间数据类型,通常使用较少,不做特别介绍。
  • Full-text (全文索引) :全文索引也是MyISAM的一个特殊索引类型,主要用于全文索引,InnoDB从Mysql5.6版本开始支持全文索引。
MyISAM、InnoDB、Memory三种存储引擎对各种索引类型的支持
索引 InnoDB 引擎 MyISAM 引擎 Memory 引擎
BTREE 索引 支持 支持 支持
HASH 索引 不支持 不支持 支持
R-tree 索引 不支持 支持 不支持
Full-text 5.6 版本之后支持 支持 不支持

我们平常所说的索引,如果没有特别指明,都是指B+树(多路搜索树,并不一定是二叉的)结构组织的索引。其中聚集索引、复合索引、前缀索引、唯一索引默认都是使用 B+tree 索引,统称为索引。

索引的分类

在一个表中,主键索引只能有一个,唯一索引可以有多个

  • 主键索引(PRIMARY KEY):唯一的标识,主键不可重复,只能有一列作为主键
  • 唯一索引(UNIQUE KEY):唯一索引的名字不能重复出现,避免重复的列出现,唯一索引可以有多个
  • 常规索引(KEY/INDEX):默认的,用INDEX或KEY来设置
  • 全文索引(FULLTEXT):快速定位数据(一般用Elastic Search做全文索引)

索引的数据结构

索引的数据结构理论上可以采用以下五种:

  • 二叉树
  • 红黑树
  • Hash 表
  • B 树
  • B+ 树

在 MySQL 当中,索引采用最多的是 B+ 树(多路搜索树)数据结构。遵循左小右大原则存放,采用中序遍历方式遍历取数据。

阅读全文

【MySQL】MySQL 高级

image-20210913132511709

MySQL 逻辑架构

MySQL逻辑架构

  • Connectors:指的是不同语言中与SQL的交互。
  • Connection Pool:管理缓冲用户连接,线程处理等需要缓存的需求。MySQL数据库的连接层
  • Management Serveices & Utilities:系统管理和控制工具。备份、安全、复制、集群等等。。
  • SQL Interface:接受用户的SQL命令,并且返回用户需要查询的结果。
  • Parser:SQL语句解析器。
  • Optimizer:查询优化器,SQL语句在查询之前会使用查询优化器对查询进行优化。就是优化客户端请求query,根据客户端请求的 query 语句,和数据库中的一些统计信息,在一系列算法的基础上进行分析,得出一个最优的策略,告诉后面的程序如何取得这个 query 语句的结果。For Exampleselect uid,name from user where gender = 1;这个select查询先根据where语句进行选取,而不是先将表全部查询出来以后再进行gender过滤;然后根据uidname进行属性投影,而不是将属性全部取出以后再进行过滤。最后将这两个查询条件联接起来生成最终查询结果。
  • Caches & Buffers:查询缓存。
  • Pluggable Storage Engines可插拔的存储引擎接口。MySQL区别于其他数据库的最重要的特点就是其插件式的表存储引擎(注意:存储引擎是基于表的,而不是数据库)。
  • File System:数据落地到磁盘上,就是文件的存储。

MySQL数据库和其他数据库相比,MySQL有点与众不同,主要体现在存储引擎的架构上,插件式的存储引擎架构将查询处理和其他的系统任务以及数据的存储提取相分离。这种架构可以根据业务的需求和实际需求选择合适的存储引擎。

阅读全文

【JUC】AQS 源码分析

AQS 理论

AQS:AbstractQueuedSynchronizer 抽象的队列同步器

AQS是用来构建锁或者其它同步器组件的重量级基础框架整个JUC体系的基石, 通过内置的FIFO队列来完成资源获取线程的排队工作,并通过一个int类变量state表示持有锁的状态。

AQS 中大量应用了 CAS + Unsafe 保证自旋原子性地添加节点。

  • 每次在抢占锁的时候都会CAS,因为可能其他非公平锁并发地抢占了锁,那么当前线程就需要再次自旋尝试获取锁。
  • 每次在修改时(例如添加修改节点时)都使用 Unsafe 类的 native 方法保证修改的原子性。

img

CLH:Craig、Landin and Hagersten队列(三位科学家的名字简写),是一个单向链表,AQS中的队列是CLH变体的虚拟双向队列FIFO

image-20210926135141194

JUC的locks包下:

  • AbstractOwnableSynchronizer
  • AbstractQueuedLongSynchronizer
  • AbstractQueuedSynchronizer

AQS是一个抽象的父类,可以将其理解为一个框架。基于AQS这个框架,我们可以实现多种同步器,比如下方图中的几个Java内置的同步器。同时我们也可以基于AQS框架实现我们自己的同步器以满足不同的业务场景需求。

img

AQS中使用了模板方法的设计模式,AQS父类中的 tryAcquire() 方法和 tryRelease() 方法中只有 throw new UnsupportedOperationException();,说明如果子类不重写代码时被调用就会抛出异常:

image-20210927102559000

阅读全文

【JUC】i++ 源码详解

字节码自增指令

自增操作对应的JVM字节码为 iinc。下面逐个分析 i++ 操作和 ++i操作的字节码指令。

i++

1
2
3
4
public static void main(String[] args) {
int i = 0;
int a = i++;
}

上述代码的字节码解析:

  • iconst_0:将数字 0 入操作数栈
  • istore_1:弹出操作数栈顶元素 0 并存储到局部变量表索引位置为1的变量(此时操作数栈为空)
  • iload_1:从局部变量表中加载索引位置1的元素(0)到操作数栈(目的是备份一下i 自增前的值,待自增结束后再赋值给 a)
  • iinc 1 by 1:首先读取局部变量表中 i 的值,再进行加一操作,最后存储加一后的值1到索引位置 1,重新赋给了 i(该指令没有原子性)
  • istore_2:将操作数栈顶的元素 0(第三步存储的)赋值给局部变量表中的 a

所以最终结果就是,a 的值等于 0。而到这这一结果的根本原因是因为:在给 a 赋值前先从局部变量表中 load了 i 加一前的值,并在最后将该值又赋给了 a,所以造成了 i++ 后 a 的值等于 i 加一前的值。

image-20211021142230633

注意:iinc 1 by 1这条指令虽然在JVM层面只是一条命令,但是其在最底层的CPU层面却是包含了三个步骤:

  1. 读取:从局部变量表中读取 i 的值
  2. 累加:将该值进行加一
  3. 保存:将加一后的值保存回局部变量表中

其中的一条指令可以保证是原子操作,但是3条指令合在一起却不是,这就导致了i++语句不是原子操作。

如果在读取操作进行后,当前线程失去了执行权,那么在该线程再一次获取到执行权后,就不会再做一次读取操作,而是直接使用线程切换前读取到的值进行加一,这就导致了高并发下 i++ 操作的结果异常

i--

1
2
3
4
public static void main(String[] args) {
int i = 0;
int a = ++i;
}

image-20211021163147335

对比 ++ii++,可以看到二者的区别是:

  • ++i 是先执行 iinc 1 by 1,将 i 的值增加,然后再 iload_1 读取了加一后的 i 值,将该值赋给 a
  • i++ 则是在 iinc 1 by 1 执行前就先把 i 原本的值备份了一份,然后 i 自增后,再将之前备份的值赋给 a

补充:只有局部变量才使用 iinc 指令,如果是调用的成员变量属性++,则不会使用 iinc 指令,其指令更加复杂。先从局部变量表里 load 该值,然后再加一,最后存回局部变量表里去。

多线程场景下 i++ 的问题

情景:两个线程同时对 static int i = 0 进行各自连续100次的 i++ 操作,理想情况下结果为 200,但最极端的情况下,结果为 2。该过程图解:

幻灯片1

【JVM】JVM 调优实战案例

本文首先介绍内存泄漏的常见案例并详细分析四种OOM案例下的排查方案,然后介绍一些JVM的调优实战案例,并演示JVM常见监控与诊断工具的使用。

Java 内存泄露的 9 种情况

严格来说,只有对象不会再被程序用到了,但是GC又不能回收他们的情况,才叫内存泄漏。但实际情况很多时候一些不太好的实践(或疏忽)会导致对象的生命周期变得很长甚至导致OOM,也可以叫做宽泛意义上的“内存泄漏”。

可达性分析算法来判断对象是否是不再使用的对象,本质都是判断一个对象是否还被引用。那么对于这种情况下,由于代码的实现不同就会出现很多种内存泄漏问题(让JVM误以为此对象还在引用中,无法回收,造成内存泄漏)。

image-20200712195158470

如下图,当Y生命周期结束的时候,X依然引用着Y,这时候,垃圾回收器是不会回收对象Y的;如果对象X还引用着生命周期比较短的A、B、C,这样就可能造成大量无用的对象不能被回收,进而占据了内存资源,造成内存泄漏,直到内存溢出。

image-20211019200416595

申请了内存用完了不释放,比如一共有1024M的内存,分配了512M的内存一直不回收,那么可以用的内存只有512M了,仿佛泄露掉了一部分。

阅读全文