乐趣区

关于java:硬核-Java-随机数相关-API-的演进与思考上

本系列将 Java 17 之前的随机数 API 以及 Java 17 之后的对立 API 都做了比拟具体的阐明,并且将随机数的个性以及实现思路也做了一些简略的剖析,帮忙大家明确为何会有这么多的随机数算法,以及他们的设计思路是什么。

本系列会分为两篇,第一篇讲述 Java 随机数算法的演变思路以及底层原理与考量,之后介绍 Java 17 之前的随机算法 API 以及测试性能,第二篇详细分析 Java 17 之后的随机数生成器算法以及 API 和底层实现类以及他们的属性,性能以及应用场景,如何抉择随机算法等等,并对 Java 的随机数对于 Java 的一些将来个性的实用进行瞻望

这是第一篇

如何生成随机数

咱们个别应用随机数生成器的时候,都认为随机数生成器(Pseudo Random Number Generator,PRNG)是一个黑盒:

这个黑盒的产出,个别是一个数字。假如是一个 int 数字。这个后果能够转化成各种咱们想要的类型,例如:如果咱们想要的的其实是一个 long,那咱们能够取两次,其中一次的后果作为高 32 位,另一次后果作为低 32 位,组成一个 long(boolean,byte,short,char 等等同理,取一次,取其中某几位作为后果)。如果咱们想要的是一个浮点型数字,那么咱们能够依据 IEEE 规范组合屡次取随机 int 而后取其中某几位组合成浮点型数字的整数位以及小数位。

如果要限度范畴,最简略的形式是将后果取余 + 偏移实现。例如咱们想取范畴在 1 ~ 100 之间,那么咱们就将后果先对 99 取余,而后取绝对值,而后 +1 即可。当然,因为取余操作是一个性能耗费比拟高的操作,最简略的优化即查看这个数字 N 与 N-1 取与运算,如果等于 0 即这个书是 2 的 n 次方(2 的 n 次方 2 进制示意肯定是 100000 这样的,减去 1 之后 为 011111,取与必定是 0);对于 2 的 n 次方取余相当于对 2 的 n 次方减一取与运算。这是一个简略的优化,理论的优化要比这个简单多。

初始化这个黑盒的时候,个别采纳一个 SEED 进行初始化,这个 SEED 的起源可能多种多样,这个咱们先按下不表,先来看一些这个黑盒中的一些算法。

线性同余算法

首先是最常见的随机数算法:线性同余(Linear Congruential Generator)。即依据以后 Seed 乘以一个系数 A,而后加上一个偏移 B,最初依照 C 进行取余(限度整体在肯定范畴内,这样能力抉择出适合的 A 和 B,为什么要这么做前面会说),得出随机数,而后这个随机数作为下次随机的种子,即:

X(n+1) = (A * X(n) + B ) % C

这种算法的劣势在于,实现简略,并且性能算是比拟好的。A,B 取值必须精挑细算,让在 C 范畴内的所有数字都是等可能的呈现的 。例如一个极其的例子就是 A = 2,B = 2,C = 10,那么 1,3,5,7,9 这些奇数在后续都不可能呈现。为了能计算出一个适合的 A 和 B,要限度 C 在一个比拟可控的范畴内。个别为了计算效率,将 C 限度为 2 的 n 次方。这样取余运算就能够优化为取与运算。 不过好在,数学巨匠们曾经将这些值(也就是魔法数)找到了,咱们间接用就好了。

这种算法生成的随机序列,是确定的,例如 X 下一个是 Y,Y 下一个是 Z,这能够了解成一个确定环(loop)。

这个环的大小,即 Period。因为 Period 足够大,初始 SEED 个别也是每次不一样的,这样近似做到了随机。然而,假如咱们须要多个随机数生成器的时候,就比拟麻烦了,因为咱们尽管能保障每个随机生成器的初始 SEED 不一样,然而在这种算法下,无奈保障某个随机数生成器的初始 SEED 就是另一个随机数生成器初始 SEED 的下一个(或者很短步骤内的)SEED。举个例子,假如某个随机数生成器的初始 SEED 是 X,另一个是 Z,尽管 X 和 Z 可能看上去差距很大,然而他们在这个算法的随机序列中仅隔了一个 Y。这样的不同的随机数生成器,成果不好

那么 如何能保障不同的随机数生成器之间距离比拟大呢 ?也就是,咱们能通过 简略计算 (而不是计算 100w 次从而调到 100w 次之后的随机数)间接使另一个随机数生成器的初始 SEED 与以后这个的初始 SEED,距离一个比拟大的数,这种性质叫做 可跳跃性 基于线性反馈移位寄存器算法的 Xoshiro 算法 给咱们提供了一种 可跳跃的随机数算法

线性反馈移位寄存器算法

线性反馈移位寄存器(Linear feedback shift register,LFSR)是指给定前一状态的输入,将该输入的线性函数再用作输出的移位寄存器。异或运算是最常见的单比特线性函数:对寄存器的某些位进行异或操作后作为输出,再对寄存器中的每个 bit 进行整体移位。

然而如何抉择这些 Bit,是一门学识,目前比拟常见的实现是 XorShift 算法以及在此基础上进一步优化的
Xoshiro 的相干算法。Xoshiro 算法是一种比拟新的优化随机数算法,计算很简略并且性能优异。同时实现了可跳跃性。

这种算法是 可跳跃的。假如咱们要生成两个差距比拟大的随机数生成器,咱们能够应用一个随机初始 SEED 创立一个随机数生成器,而后利用算法的跳跃操作,间接生成一个距离比拟大的 SEED 作为另一个随机数生成器的初始 SEED。

还有一点比拟有意思的是,线性同余算法并不可逆 ,咱们只能通过 X(n) 推出 X(n + 1),而不能依据 X(n + 1) 间接推出 X(n)。这个操作对应的业务例如随机播放歌单,上一首下一首,咱们不须要记录整个歌单,而是仅依据以后的随机数就能晓得。 线性反馈移位寄存器算法能实现可逆

线性反馈移位寄存器算法在生成不同的随机序列生成器也有局限性,即它们还是来自于同一个环,即便通过跳跃操作让不同的随机数生成器都距离开了,然而如果压力不够平衡,随着工夫的推移,它们还是有可能 SEED,又变成一样的了。那么有没有 那种能生成不同随机序列环的随机算法呢

DotMix 算法

DotMix 算法提供了另一种思路,即给定一个初始 SEED,设置一个固定步长 M,每次随机,将这个 SEED 加上步长 M,通过一个 HASH 函数,将这个值散列映射到一个 HASH 值:

X(n+1) = HASH(X(n) + M)

这个算法对于 HASH 算法的要求比拟高,重点要求 HASH 算法针对输出的一点扭转则造成输入大幅度扭转。基于 DotMix 算法的 SplitMix 算法应用的即 MurMurHash3 算法,这个即 Java 8 引入的 SplittableRandom 的底层原理。

这种算法好在,咱们很容易能明确 两个不同参数的随机生成器他们的生成序列是不同的 ,例如一个生成的随机序列是 1,4,3,7,… 另一个生成的是 1,5,3,2。这点正是线性同余算法无奈做到的,他的序列无论怎么批改 SEED 也是确定的,而咱们有不能随便更改算法中的 A、B、C 的值,因为可能会导致无奈遍历到所有数字,这点之前曾经说过了。Xoshiro 也是同理。而 SplitMix 算法不必放心,咱们指定不同的 SEED 以及不同的步长 M 就能够保障生成的序列是不同的。这种 能够生成不同序列的性质 ,称为 可拆分性

这也是 SplittableRandomRandom(Random 基于线性同余)更适宜多线程的起因:

  • 假如多线程应用同一个 Random,保障了序列的随机性,然而有 CompareAndSet 新 seed 的性能损失。
  • 假如每个线程应用 SEED 雷同的 Random,则每个线程生成的随机序列雷同。
  • 假如每个线程应用 SEED 不雷同的 Random,然而咱们不能保障一个 Random 的 SEED 是否是另一个 Random SEED 的下一个后果(或者是很短步长以内的后果),这种状况下如果线程压力不平均(线程池在比拟闲的时候,其实只有一部分线程在工作,这些线程很可能他们公有的 Random 来到和其余线程同一个 SEED 的地位),某些线程也会有雷同的随机序列。

应用 SplittableRandom 只有间接应用接口 split 就能给不同线程 调配一个参数不同 SplittableRandom,并且参数不同根本就能够保障生成不了雷同序列。

思考:咱们如何生成 Period 大于生成数字容量的随机序列呢?

最简略的做法,咱们将两个 Period 等于容量的序列通过轮询合并在一起,这样就失去了 Period = 容量 + 容量 的序列:

咱们还能够间接记录两个序列的后果,而后将两个序列的后果用某种运算,例如异或或者散列操作拼到一起。这样,Period = 容量 * 容量

如果咱们想扩大更多,都能够通过以上方法拼接。用肯定的操作拼接不同算法的序列,咱们能够失去每种算法的随机劣势。Java 17 引入的 LXM 算法就是一个例子。

LXM 算法

这是在 Java 17 中引入的算法 LXM 算法(L 即线性同余,X 即 Xoshiro,M 即 MurMurHash)的实现较为简单,联合线性同余算法和 Xoshiro 算法,之后通过 MurMurHash 散列,例如:

  • L34X64M:即应用一个 32 位的数字保留线性同余的后果,两个 32 位的数字保留 Xoshiro 算法的后果,应用 MurMurHash 散列合并这些后果到一个 64 位数字。
  • L128X256M:即应用两个 64 位的数字保留线性同余的后果,4 个 64 位的数字保留 Xoshiro 算法的后果,应用 MurMurHash 散列合并这些后果到一个 64 位数字。

LXM 算法通过 MurMurhash 实现了宰割性,没有保留 Xoshiro 的跳跃性。

SEED 的起源

因为 JDK 中所有的随机算法都是基于上一次输出的,如果咱们应用固定 SEED 那么生成的随机序列也肯定是一样的。这样在平安敏感的场景,不够适合,官网对于 cryptographically secure 的定义是,要求 SEED 必须是不可预知的,产生非确定性输入。

在 Linux 中,会采集用户输出,零碎中断等零碎运行数据,生成随机种子放入池中,程序能够读取这个池子获取一个随机数。然而这个池子是采集肯定数据后才会生成,大小无限,并且它的随机散布必定不够好,所以咱们不能间接用它来做随机数,而是用它来做咱们的随机数生成器的种子。这个池子在 Linux 中被形象为两个文件,这两个文件他们别离是:/dev/random/dev/urandom。一个是必须采集肯定熵的数据才放开从池子外面取否则阻塞,另一个则是不论是否采集够间接返回现有的。

在 Linux 4.8 之前:

在 Linux 4.8 之后:

在熵池不够用的时候,file:/dev/random会阻塞 file:/dev/urandom 不会 。对于咱们来说,/dev/urandom 个别就够用,所以个别 通过 -Djava.security.egd=file:/dev/./urandom 设置 JVM 启动参数,应用 urandom 来缩小阻塞。

咱们也能够通过 业务中的一些个性,来定时从新设置所有 Random 的 SEED 来进一步减少被破解的难度,例如,每小时用过来一小时的沉闷用户数量 * 下单数量作为新的 SEED。

测试随机算法随机性

以上算法实现的都是伪随机,即 以后随机数后果与上一次是强相干的关系 。事实上目前根本所有 疾速的随机算法,都是这样的

并且就算咱们让 SEED 足够隐秘,然而如果咱们晓得算法,还是能够通过以后的随机输入,揣测出下一个随机输入。或者算法未知,然而能从几次随机后果反推出算法从而推出之后的后果。

针对这种伪随机算法,须要验证算法生成的随机数满足一些个性,例如:

  • period 尽可能长:a full cycle 或者 period 指的是随机序列将所有可能的随机后果都遍历过一遍,同时后果回到初始 seed 须要的后果个数。这个 period 要尽可能的长一些。
  • 均匀散布(equidistribution),生成的随机数的每个可能后果,在一个 Period 内要尽可能保障每种后果的呈现次数是雷同的。否则,会影响在某些业务的应用,例如抽奖这种业务,咱们须要保障概率要准。
  • 复杂度测试:生成的随机序列是否够简单,不会有那种有法则的数字序列,例如等比数列,等差数列等等。
  • 安全性测试:很难通过比拟少的后果反推出这个随机算法。

目前,曾经有很多框架工具用来针对某个算法生成的随机序列进行测试,评估随机序列后果,验证算法的随机性,罕用的包含:

  • testU01 随机性测试:https://github.com/umontreal-…
  • NIST 随机性测试:https://nvlpubs.nist.gov/nist…
  • DieHarder Suite 随机性测试

Java 中内置的随机算法,根本都通过了 testU01 的大部分测试 。目前,下面提到过的优化算法都或多或少的暴露出一些随机性问题。目前,Java 17 中的 LXM 算法是随机性测试中体现最好的 留神是随机性体现,而不是性能

Java 中波及到的所有随机算法(不包含 SecureRandom)

  • Linear Congruential generator: https://doi.org/10.1093%2Fcom…
  • Linear-feedback shift register: https://www.ams.org/journals/…
  • XORShift: https://doi.org/10.18637%2Fjs…
  • Xoroshiro128+: https://arxiv.org/abs/1805.01407
  • LXM: https://dl.packetstormsecurit…
  • SplitMix: http://gee.cs.oswego.edu/dl/p…

为什么咱们在理论业务利用中很少思考随机安全性问题

次要因为,咱们个别做了负载平衡多实例部署,还有多线程。个别每个线程应用不同初始 SEED 的 Random 实例(例如 ThreadLocalRandom)。并且一个随机敏感业务,例如抽奖,单个用户个别都会限度次数,所以很难采集够足够的后果反推出算法以及下一个后果,而且你还须要和其余用户一起抽。而后,咱们个别会限度随机数范畴,而不是应用原始的随机数,这就更大大增加了反解的难度。最初,咱们也能够定时应用业务的一些实时指标定时设置咱们的 SEED,例如:,每小时用过来一小时的(沉闷用户数量 * 下单数量)作为新的 SEED。

所以,个别事实业务中,咱们很少会用 SecureRandom。如果咱们想初始 SEED 让编写程序的人也不能猜出来(工夫戳也能猜出来),能够指定随机类的初始 SEED 源,通过 JVM 参数 -Djava.util.secureRandomSeed=true。这个对于所有 Java 中的随机数生成器都无效(例如,Random,SplittableRandom,ThreadLocalRandom 等等)

对应源码:

static {String sec = VM.getSavedProperty("java.util.secureRandomSeed");
        if (Boolean.parseBoolean(sec)) {
            // 初始 SEED 从 SecureRandom 中取
            // SecureRandom 的 SEED 源,在 Linux 中即咱们后面提到的环境变量 java.security.egd 指定的 /dev/random 或者 /dev/urandom
            byte[] seedBytes = java.security.SecureRandom.getSeed(8);
            long s = (long)seedBytes[0] & 0xffL;
            for (int i = 1; i < 8; ++i)
                s = (s << 8) | ((long)seedBytes[i] & 0xffL);
            seeder.set(s);
        }
    }

所以,针对咱们的业务,咱们个别只关怀算法的性能以及随机性中的均匀性 ,而通过测试的算法,个别随机性都没啥大问题,所以 咱们只次要关怀性能即可

针对安全性敏感的业务,像是 SSL 加密,生成加密随机散列这种,则须要思考更高的平安随机性。这时候才思考应用 SecureRandom。SecureRandom 的实现中,随机算法更加简单且波及了一些加密思维,咱们这里就不关注这些 Secure 的 Random 的算法了

Java 17 之前个别如何生成随机数以及对应的随机算法

首先放出算法与实现类的对应关系:

应用 JDK 的 API

1. 应用 java.util.Random 和基于它的 API

Random random = new Random();
random.nextInt();

Math.random() 底层也是基于 Random

java.lang.Math

public static double random() {return RandomNumberGeneratorHolder.randomNumberGenerator.nextDouble();
}
private static final class RandomNumberGeneratorHolder {static final Random randomNumberGenerator = new Random();
}

Random 自身是 设计成线程平安 的,因为 SEED 是 Atomic 的并且随机只是 CAS 更新这个 SEED:

java.util.Random

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

同时也看出,Random 是基于线性同余算法的

2. 应用 java.util.SplittableRandom 和基于它的 API

SplittableRandom splittableRandom = new SplittableRandom();
splittableRandom.nextInt();

后面的剖析咱们提到了,SplittableRandom 基于 SplitMix 算法实现,即给定一个初始 SEED,设置一个固定步长 M,每次随机,将这个 SEED 加上步长 M,通过一个 HASH 函数(这里是 MurMurHash3),将这个值散列映射到一个 HASH 值。

SplittableRandom 自身不是线程平安的
java.util.SplittableRandom

public int nextInt() {return mix32(nextSeed());
}   
private long nextSeed() {
    // 这里非线程平安
    return seed += gamma;
}

ThreadLocalRandom 基于 SplittableRandom 实现,咱们在多线程环境下应用 ThreadLocalRandom

ThreadLocalRandom.current().nextInt();

SplittableRandom 能够通过 split 办法返回一个参数全新,随机序列个性差别很大的新的 SplittableRandom,咱们能够将他们用于不同的线程生成随机数,这在 parallel Stream 中十分常见:

IntStream.range(0, 1000)
    .parallel()
    .map(index -> usersService.getUsersByGood(index))
    .map(users -> users.get(splittableRandom.split().nextInt(users.size())))
    .collect(Collectors.toList());

然而因为没有做 对齐性填充以及其余一些多线程性能优化的货色,导致其多线程环境下的性能体现还是比基于 SplittableRandomThreadLocalRandom 要差。

3. 应用 java.security.SecureRandom 生成安全性更高的随机数

SecureRandom drbg = SecureRandom.getInstance("DRBG");
drbg.nextInt();

个别这种算法,基于加密算法实现,计算更加简单,性能也比拟差,只有安全性十分敏感的业务才会应用,个别业务(例如抽奖)这些是不会应用的。

测试性能

单线程测试:

Benchmark                                      Mode  Cnt          Score          Error  Units
TestRandom.testDRBGSecureRandomInt            thrpt   50     940907.223 ±    11505.342  ops/s
TestRandom.testDRBGSecureRandomIntWithBound   thrpt   50     992789.814 ±    71312.127  ops/s
TestRandom.testRandomInt                      thrpt   50  106491372.544 ±  8881505.674  ops/s
TestRandom.testRandomIntWithBound             thrpt   50   99009878.690 ±  9411874.862  ops/s
TestRandom.testSplittableRandomInt            thrpt   50  295631145.320 ± 82211818.950  ops/s
TestRandom.testSplittableRandomIntWithBound   thrpt   50  190550282.857 ± 17108994.427  ops/s
TestRandom.testThreadLocalRandomInt           thrpt   50  264264886.637 ± 67311258.237  ops/s
TestRandom.testThreadLocalRandomIntWithBound  thrpt   50  162884175.411 ± 12127863.560  ops/s

多线程测试:

Benchmark                                      Mode  Cnt          Score           Error  Units
TestRandom.testDRBGSecureRandomInt            thrpt   50    2492896.096 ±     19410.632  ops/s
TestRandom.testDRBGSecureRandomIntWithBound   thrpt   50    2478206.361 ±    111106.563  ops/s
TestRandom.testRandomInt                      thrpt   50  345345082.968 ±  21717020.450  ops/s
TestRandom.testRandomIntWithBound             thrpt   50  300777199.608 ±  17577234.117  ops/s
TestRandom.testSplittableRandomInt            thrpt   50  465579146.155 ±  25901118.711  ops/s
TestRandom.testSplittableRandomIntWithBound   thrpt   50  344833166.641 ±  30676425.124  ops/s
TestRandom.testThreadLocalRandomInt           thrpt   50  647483039.493 ± 120906932.951  ops/s
TestRandom.testThreadLocalRandomIntWithBound  thrpt   50  467680021.387 ±  82625535.510  ops/s

后果和咱们之前阐明的预期基本一致,多线程环境下 ThreadLocalRandom 的性能最好。单线程环境下 SplittableRandomThreadLocalRandom 根本靠近,性能要好于其余的。SecureRandom 和其余的相比性能差了几百倍。

测试代码如下(留神尽管 Random 和 SecureRandom 都是线程平安的,然而为了防止 compareAndSet 带来的性能衰减过多,还是用了 ThreadLocal。):

package prng;

import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.util.Random;
import java.util.SplittableRandom;
import java.util.concurrent.ThreadLocalRandom;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Threads;
import org.openjdk.jmh.annotations.Warmup;
import org.openjdk.jmh.infra.Blackhole;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

// 测试指标为吞吐量
@BenchmarkMode(Mode.Throughput)
// 须要预热,排除 jit 即时编译以及 JVM 采集各种指标带来的影响,因为咱们单次循环很屡次,所以预热一次就行
@Warmup(iterations = 1)
// 线程个数
@Threads(10)
@Fork(1)
// 测试次数,咱们测试 50 次
@Measurement(iterations = 50)
// 定义了一个类实例的生命周期,所有测试线程共享一个实例
@State(value = Scope.Benchmark)
public class TestRandom {ThreadLocal<Random> random = ThreadLocal.withInitial(Random::new);
    ThreadLocal<SplittableRandom> splittableRandom = ThreadLocal.withInitial(SplittableRandom::new);
    ThreadLocal<SecureRandom> drbg = ThreadLocal.withInitial(() -> {
        try {return SecureRandom.getInstance("DRBG");
        }
        catch (NoSuchAlgorithmException e) {throw new IllegalArgumentException(e);
        }
    });

    @Benchmark
    public void testRandomInt(Blackhole blackhole) throws Exception {blackhole.consume(random.get().nextInt());
    }

    @Benchmark
    public void testRandomIntWithBound(Blackhole blackhole) throws Exception {
        // 留神不取 2^n 这种数字,因为这种数字个别不会作为理论利用的范畴,然而底层针对这种数字有优化
        blackhole.consume(random.get().nextInt(1, 100));
    }

    @Benchmark
    public void testSplittableRandomInt(Blackhole blackhole) throws Exception {blackhole.consume(splittableRandom.get().nextInt());
    }

    @Benchmark
    public void testSplittableRandomIntWithBound(Blackhole blackhole) throws Exception {
        // 留神不取 2^n 这种数字,因为这种数字个别不会作为理论利用的范畴,然而底层针对这种数字有优化
        blackhole.consume(splittableRandom.get().nextInt(1, 100));
    }

    @Benchmark
    public void testThreadLocalRandomInt(Blackhole blackhole) throws Exception {blackhole.consume(ThreadLocalRandom.current().nextInt());
    }

    @Benchmark
    public void testThreadLocalRandomIntWithBound(Blackhole blackhole) throws Exception {
        // 留神不取 2^n 这种数字,因为这种数字个别不会作为理论利用的范畴,然而底层针对这种数字有优化
        blackhole.consume(ThreadLocalRandom.current().nextInt(1, 100));
    }

    @Benchmark
    public void testDRBGSecureRandomInt(Blackhole blackhole) {blackhole.consume(drbg.get().nextInt());
    }

    @Benchmark
    public void testDRBGSecureRandomIntWithBound(Blackhole blackhole) {
        // 留神不取 2^n 这种数字,因为这种数字个别不会作为理论利用的范畴,然而底层针对这种数字有优化
        blackhole.consume(drbg.get().nextInt(1, 100));
    }

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

微信搜寻“我的编程喵”关注公众号,每日一刷,轻松晋升技术,斩获各种 offer

退出移动版