关于阿里面试、学习路线、公众号的一些想法

还记得上一篇记录我心情的随笔是写在离开魔都,去往南京的时候,此时的我,又来到了杭州。工作发生了变故,心境也发生了变化,倒是有不少东西想跟各位来聊一聊,择其三汇成此文。

查看更多

分享到

Java 随机数探秘

本文的前 3 节参考修改自微信公众号「咖啡拿铁」的文章,感谢李钊同学对这个话题热情的讨论。

1 前言

一提到 Java 中的随机数,很多人就会想到 Random,当出现生成随机数这样需求时,大多数人都会选择使用 Random 来生成随机数。Random 类是线程安全的,但其内部使用 CAS 来保证线程安全性,在多线程并发的情况下的时候它的表现是存在优化空间的。在 JDK1.7 之后,Java 提供了更好的解决方案 ThreadLocalRandom,接下来,我们一起探讨下这几个随机数生成器的实现到底有何不同。

2 Random

Random 这个类是 JDK 提供的用来生成随机数的一个类,这个类并不是真正的随机,而是伪随机,伪随机的意思是生成的随机数其实是有一定规律的,而这个规律出现的周期随着伪随机算法的优劣而不同,一般来说周期比较长,但是可以预测。通过下面的代码我们可以对 Random 进行简单的使用:

img

Random 原理

Random 中的方法比较多,这里就针对比较常见的 nextInt()和 nextInt(int bound) 方法进行分析,前者会计算出 int 范围内的随机数,后者如果我们传入 10,那么他会求出 [0,10) 之间的 int 类型的随机数,左闭右开。我们首先看一下 Random() 的构造方法:

img

可以发现在构造方法当中,根据当前时间的种子生成了一个 AtomicLong 类型的 seed,这也是我们后续的关键所在。

nextInt()

nextInt() 的代码如下所示:

img

这个里面直接调用的是 next() 方法,传入的 32,代指的是 Int 类型的位数。

img

这里会根据 seed 当前的值,通过一定的规则 (伪随机算法) 算出下一个 seed,然后进行 CAS,如果 CAS 失败则继续循环上面的操作。最后根据我们需要的 bit 位数来进行返回。核心便是 CAS 算法。

nextInt(int bound)

nextInt(int bound) 的代码如下所示:img

这个流程比 nextInt() 多了几步,具体步骤如下:

  1. 首先获取 31 位的随机数,注意这里是 31 位,和上面 32 位不同,因为在 nextInt()方法中可以获取到随机数可能是负数,而 nextInt(int bound) 规定只能获取到 [0,bound) 之前的随机数,也就意味着必须是正数,预留一位符号位,所以只获取了 31 位。(不要想着使用取绝对值这样操作,会导致性能下降)
  2. 然后进行取 bound 操作。
  3. 如果 bound 是 2 的幂次方,可以直接将第一步获取的值乘以 bound 然后右移 31 位,解释一下: 如果 bound 是 4,那么乘以 4 其实就是左移 2 位,其实就是变成了 33 位,再右移 31 位的话,就又会变成 2 位,最后,2 位 int 的范围其实就是 [0,4) 了。
  4. 如果不是 2 的幂,通过模运算进行处理。

并发瓶颈

在我之前的文章中就有相关的介绍,一般而言,CAS 相比加锁有一定的优势,但并不一定意味着高效。一个立刻被想到的解决方案是每次使用 Random 时都去 new 一个新的线程私有化的 Random 对象,或者使用 ThreadLocal 来维护线程私有化对象,但除此之外还存在更高效的方案,下面便来介绍本文的主角 ThreadLocalRandom。

3 ThreadLocalRandom

在 JDK1.7 之后提供了新的类 ThreadLocalRandom 用来在并发场景下代替 Random。使用方法比较简单:

1
2
ThreadLocalRandom.current().nextInt();
ThreadLocalRandom.current().nextInt(10);

在 current 方法中有:

img 可以看见如果没有初始化会对其进行初始化,而这里我们的 seed 不再是一个全局变量,在我们的 Thread 中有三个变量:

img

  • threadLocalRandomSeed:ThreadLocalRandom 使用它来控制随机数种子。
  • threadLocalRandomProbe:ThreadLocalRandom 使用它来控制初始化。
  • threadLocalRandomSecondarySeed:二级种子。

可以看见所有的变量都加了 @sun.misc.Contended 这个注解,用来处理伪共享问题。

在 nextInt() 方法当中代码如下:

img

我们的关键代码如下:

1
UNSAFE.putLong(t = Thread.currentThread(), SEED,r=UNSAFE.getLong(t, SEED) + GAMMA);

可以看见由于我们每个线程各自都维护了种子,这个时候并不需要 CAS,直接进行 put,在这里利用线程之间隔离,减少了并发冲突;相比较 ThreadLocal<Random>,ThreadLocalRandom 不仅仅减少了对象维护的成本,其内部实现也更轻量级。所以 ThreadLocalRandom 性能很高。

4 性能测试

除了文章中详细介绍的 Random,ThreadLocalRandom,我还将 netty4 实现的 ThreadLocalRandom,以及 ThreadLocal<Random> 作为参考对象,一起参与 JMH 测评。

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
@BenchmarkMode({Mode.AverageTime})
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 3, time = 5)
@Measurement(iterations = 3, time = 5)
@Threads(50)
@Fork(1)
@State(Scope.Benchmark)
public class RandomBenchmark {

Random random = new Random();

ThreadLocal<Random> threadLocalRandomHolder = ThreadLocal.withInitial(Random::new);

@Benchmark
public int random() {
return random.nextInt();
}

@Benchmark
public int threadLocalRandom() {
return ThreadLocalRandom.current().nextInt();
}

@Benchmark
public int threadLocalRandomHolder() {
return threadLocalRandomHolder.get().nextInt();
}

@Benchmark
public int nettyThreadLocalRandom() {
return io.netty.util.internal.ThreadLocalRandom.current().nextInt();
}

public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(RandomBenchmark.class.getSimpleName())
.build();

new Runner(opt).run();
}

}

测评结果如下:

1
2
3
4
5
Benchmark                                Mode  Cnt     Score     Error  Units
RandomBenchmark.nettyThreadLocalRandom avgt 3 192.202 ± 295.897 ns/op
RandomBenchmark.random avgt 3 3197.620 ± 380.981 ns/op
RandomBenchmark.threadLocalRandom avgt 3 90.731 ± 39.098 ns/op
RandomBenchmark.threadLocalRandomHolder avgt 3 229.502 ± 267.144 ns/op

从上图可以发现,JDK1.7 的 ThreadLocalRandom 取得了最好的成绩,仅仅需要 90 ns 就可以生成一次随机数,netty 实现的 ThreadLocalRandom 以及使用 ThreadLocal 维护 Random 的方式差距不是很大,位列 2、3 位,共享的 Random 变量则效果最差。

可见,在并发场景下,ThreadLocalRandom 可以明显的提升性能。

5 注意点

注意,ThreadLocalRandom 切记不要调用 current 方法之后,作为共享变量使用

1
2
3
4
5
6
7
8
9
public class WrongCase {

ThreadLocalRandom threadLocalRandom = ThreadLocalRandom.current();

public int concurrentNextInt(){
return threadLocalRandom.nextInt();
}

}

这是因为 ThreadLocalRandom.current() 会使用初始化它的线程来填充随机种子,这会带来导致多个线程使用相同的 seed。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Main {

public static void main(String[] args) {
ThreadLocalRandom threadLocalRandom = ThreadLocalRandom.current();
for(int i=0;i<10;i++)
new Thread(new Runnable() {
@Override
public void run() {
System.out.println(threadLocalRandom.nextInt());
}
}).start();

}
}

输出相同的随机数:

1
2
3
4
5
6
7
8
9
10
-1667209487
-1667209487
-1667209487
-1667209487
-1667209487
-1667209487
-1667209487
-1667209487
-1667209487
-1667209487

请在确保不同线程获取不同的 seed,最简单的方式便是每次调用都是使用 current():

1
2
3
4
5
public class RightCase {
public int concurrentNextInt(){
return ThreadLocalRandom.current().nextInt();
}
}

彩蛋 1

梁飞博客中一句话常常在我脑海中萦绕:魔鬼在细节中。优秀的代码都是一个个小细节堆砌出来,今天介绍的 ThreadLocalRandom 也不例外。

dubbo

在 incubator-dubbo-2.7.0 中,随机负载均衡器的一个小改动便是将 Random 替换为了 ThreadLocalRandom,用于优化并发性能。

彩蛋 2

ThreadLocalRandom 的 nextInt(int bound) 方法中,当 bound 不为 2 的幂次方时,使用了一个循环来修改 r 的值,我认为这可能不必要,你觉得呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int nextInt(int bound) {
if (bound <= 0)
throw new IllegalArgumentException(BadBound);
int r = mix32(nextSeed());
int m = bound - 1;
if ((bound & m) == 0) // power of two
r &= m;
else { // reject over-represented candidates
for (int u = r >>> 1;
u + m - (r = u % bound) < 0;
u = mix32(nextSeed()) >>> 1)
;
}
return r;
}

欢迎关注李钊同学的微信公众号:「咖啡拿铁」

咖啡拿铁

当然,也欢迎关注我的微信公众号:「Kirito 的技术分享」,关于文章的任何疑问都会得到回复,带来更多 Java 相关的技术分享。

关注微信公众号

分享到

Spring 中的 XML schema 扩展机制

前言

很久没有写关于 Spring 的文章了,最近在系统梳理 Dubbo 代码的过程中发现了 XML schema 这个被遗漏的知识点。由于工作中使用 SpringBoot 比较多的原因,几乎很少接触 XML,此文可以算做是亡羊补牢,另一方面,也为后续的 Dubbo 源码解析做个铺垫。

XML schema 扩展机制是啥?这并不是一块很大的知识点,翻阅一下 Spring 的文档,我甚至没找到一个贯穿上下文的词来描述这个功能,XML Schema Authoring 是文档中对应的标题,简单来说:

查看更多

分享到

JCTools -- 高性能内存队列探秘 (写作中...)

1
2
3
4
5
Benchmark                    (burstSize)  (qCapacity)            (queueType)  Mode  Cnt        Score        Error  Units
QueueBenchmark.offerAndPoll 100000 132000 ArrayBlockingQueue avgt 15 3746839.904 ± 214308.618 ns/op
QueueBenchmark.offerAndPoll 100000 132000 LinkedBlockingQueue avgt 15 6537598.922 ± 611003.544 ns/op
QueueBenchmark.offerAndPoll 100000 132000 ConcurrentLinkedQueue avgt 15 2944479.279 ± 41621.277 ns/op
QueueBenchmark.offerAndPoll 100000 132000 MpscArrayQueue avgt 15 1199839.760 ± 65991.348 ns/op

欢迎关注我的微信公众号:「Kirito 的技术分享」,关于文章的任何疑问都会得到回复,带来更多 Java 相关的技术分享。

关注微信公众号

分享到

如何向开源项目做贡献 (以 incubator-dubbo 为例)

Github 上有众多优秀的开源项目,大多数 IT 从业者将其当做了予取予求的工具库,遇到什么需求,先去 Github 搜一把,但有没有想过有一天自己也可以给开源事业做一些贡献呢?本文将会以 incubator-dubbo 项目为例,向你阐释,给开源项目做贡献并不是一件难事。

查看更多

分享到

Java 并发计数器探秘

前言

一提到线程安全的并发计数器,AtomicLong 必然是第一个被联想到的工具。Atomic* 一系列的原子类以及它们背后的 CAS 无锁算法,常常是高性能,高并发的代名词。本文将会阐释,在并发场景下,使用 AtomicLong 来充当并发计数器将会是一个糟糕的设计,实际上存在不少 AtomicLong 之外的计数器方案。近期我研究了一些 Jdk1.8 以及 JCTools 的优化方案,并将它们的对比与实现细节整理于此。

相关面试题:

单机场景下,有比 AtomicLong 更高效的并发计数器方案吗?

查看更多

分享到

JAVA 拾遗 — JMH 与 8 个测试陷阱

前言

JMH 是 Java Microbenchmark Harness(微基准测试)框架的缩写(2013 年首次发布)。与其他众多测试框架相比,其特色优势在于它是由 Oracle 实现 JIT 的相同人员开发的。在此,我想特别提一下 Aleksey Shipilev(JMH 的作者兼布道者)和他优秀的博客文章。笔者花费了一个周末,将 Aleksey 大神的博客,特别是那些和 JMH 相关的文章通读了几遍,外加一部公开课视频 《”The Lesser of Two Evils” Story》 ,将自己的收获归纳在这篇文章中,文中不少图片都来自 Aleksey 公开课视频。

查看更多

分享到

JAVA 拾遗 — CPU Cache 与缓存行

最近的两篇文章,介绍了我参加的中间件比赛中一些相对重要的优化,但实际上还存在很多细节优化,出于篇幅限制并未提及,在最近的博文中,我会将他们整理成独立的知识点,并归类到我的系列文章「JAVA 拾遗」中。

查看更多

分享到

天池中间件大赛百万队列存储设计总结【复赛】

维持了 20 天的复赛终于告一段落了,国际惯例先说结果,复赛结果不太理想,一度从第 10 名掉到了最后的第 36 名,主要是写入的优化卡了 5 天,一直没有进展,最终排名也是定格在了排行榜的第二页。痛定思痛,这篇文章将自己复赛中学习的知识,成功的优化,未成功的优化都罗列一下。

最终排名

查看更多

分享到

选择 Kong 作为你的 API 网关

Kong(https://github.com/Kong/kong)是一个云原生,高效,可扩展的分布式 API 网关。 自 2015 年在 github 开源后,广泛受到关注,目前已收获 1.68w+ 的 star,其核心价值在于高性能和可扩展性。

查看更多

分享到