Java

Java 随机数问题综述

Java 随机数问题综述

最后修改于:

Contention in java.util.Random

  • it’s thread-safe
  • it’s lock-free

To better understand this, let’s see how one of its primary operations, next(int), is implemented:

1
2
3
4
5
6
7
8
9

    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));
    }

Instead of a dedicated instance of Random per thread, each thread only needs to maintain its own seed value. As of Java 8, the Thread class itself has been retrofitted to maintain the seed value:

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

public class Thread implements Runnable {
    // omitted

    @jdk.internal.vm.annotation.Contended("tlr")
    long threadLocalRandomSeed;

    @jdk.internal.vm.annotation.Contended("tlr")
    int threadLocalRandomProbe;

    @jdk.internal.vm.annotation.Contended("tlr")
    int threadLocalRandomSecondarySeed;
}

The threadLocalRandomSeed variable is responsible for maintaining the current seed value for ThreadLocalRandom. Moreover, the secondary seed, threadLocalRandomSecondarySeed, is usually used internally by the likes of ForkJoinPool.

This implementation incorporates a few optimizations to make ThreadLocalRandom even more performant:

  • Avoiding false sharing by using the @Contented annotation, which basically adds enough padding to isolate the contended variables in their own cache lines
  • Using sun.misc.Unsafe to update these three variables instead of using the Reflection API
  • Avoiding extra hashtable lookups associated with the ThreadLocal implementation

Contention in java.util.SecureRandom

it’s the subclass of java.util.Random

one of the most common locking issues within Java applications is triggered through an innocent-looking java.io.File.createTempFile() calls. Under the hood, this temporary file creation is relying upon a SecureRandom class to calculate the name of the file.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

private static final SecureRandom random = new SecureRandom();
static File generateFile(String prefix, String suffix, File dir) {
    long n = random.nextLong();
    if (n == Long.MIN_VALUE) {
        n = 0;      // corner case
    } else {
        n = Math.abs(n);
    }
    return new File(dir, prefix + Long.toString(n) + suffix);
}

And SecureRandom, when nextLong is called, eventually calls its method nextBytes(), which is defined as synchronized:

1
2
3

synchronized public void nextBytes(byte[] bytes) {
    secureRandomSpi.engineNextBytes(bytes);
}

One may say, that if I create new SecureRandom in each thread, I will not get any issues. Unfortunately, it’s not that simple. SecureRandom uses an implementation of java.security.SecureRandomSpi, which will eventually be contended anyhow (you may look at the following bug discussion with some benchmarks in Jenkins issue tracker)

This in combination with certain application usage patterns (especially if you have lots of SSL connections which rely on SecureRandom for their crypto-handshaking magic) has a tendency to build up into long-lasting contention issues.

The fix to the situation is simple if you can control the source code – just rebuild the solution to rely upon the java.util.ThreadLocalRandom for multithreaded designs. In cases where you are stuck with a standard API making the decisions for you the solution can be more complex and require significant refactoring.

urandom and random Devices

https://www.ibm.com/docs/en/aix/7.2?topic=files-urandom-random-devices

Linux Kernel 5.8 之前的版本，如果熵池的数据不足，从 /dev/random 读取数据可能阻塞，但是从 /dev/urandom 不会阻塞。Java 程序一般会指定 -Djava.security.egd=file:/dev/./urandom 参数避免阻塞的发生(但不一定生效)。 需要注意的是，

  • -Djava.security.egd=file:/dev/urandom 是错误的；
  • -Djava.security.egd=file:/dev/./urandom 才是正确的； 见：https://stackoverflow.com/questions/137212/how-to-deal-with-a-slow-securerandom-generator

关于性能

  • ThreadLocalRandom 和 SecureRandom 都是 Random 的子类；
  • 性能：ThreadLocalRandom > Random > SecureRandom；
  • Random 和 ThreadLocalRandom 使用的都是「线性同余发生器」算法，速度很快，区别是：
    • Random 使用 CAS 方式更新种子，高并发情况下竞争大，性能会下降；
    • ThreadLocalRandom 将种子存在在 Thread 对象上，性能更好：
      • 种子封闭在线程内，不需要 CAS；
      • 避免额外的『间接』计算：
        • 相比 ThreadLocal + Random，在 Java8 中，ThreadLocalRandom 只需要直接读取存储在 Thread 对象上的 threadLocalRandomSeed 然后直接更新就可以，不需要调用 ThreadLocal.get 进行一次 HashTable Lookup；
      • 通过 UNSAFE 的 native 方法更新种子值，而不是反射，效率更高；
      • 通过使用 Contended 注解，避免伪共享问题；
  • SecureRandom 使用 OS 维护的随机数据来生成随机数，底层会使用 synchronized 锁，因此性能比较差，且可能发生阻塞；
  • SecureRandom 使用的某些算法，需要读取 /dev/random 来获取随机数据，当 OS 维护的熵池中的熵不足时，会发生阻塞，导致严重的性能问题；
  • 在 Linux 的 v5.6 及其以后的内核中，读取 /dev/random 不会再被阻塞了，但是就像 /dev/urandom 一样，在一个全新的系统刚启动时由于系统尚未产生熵值，此时还是可能阻塞等待足够的熵值产生；
  • UUID.randomUUID 底层使用的就是 SecureRandom，因此性能会比较差；
  • File.createTempFile 底层也会使用 SecureRandom，因此性能会比较差；
  • 建立 SSL 连接同样依赖 SecureRandom，因此也要小心；

如何预测下一个随机数

以下方法仅对基于 LCG 算法有效，利用公式 𝑋𝑛+1=(𝑎𝑋𝑛+𝑐) mod 𝑚。

给定两个连续的 int 类型值，或一个 double，或一个 long 类型值，即可预测后续的随机数。

 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

Predict Next Random Number.java

import java.util.ArrayList;
import java.util.Random;
 
public class ReplicatedRandom extends Random {
 
    public static void main(String[] args) {
        predictByNextDouble();
        predictByNextInt();
    }
 
    private static void predictByNextInt() {
        long seed = System.currentTimeMillis();
        Random r = new Random(seed);
        int v1 = r.nextInt();
        int v2 = r.nextInt();
        ReplicatedRandom rr = new ReplicatedRandom();
        rr.replicateState(v1, v2);
        System.out.println(r.nextInt() == rr.nextInt()); // True
        System.out.println(r.nextInt() == rr.nextInt()); // True
        System.out.println(r.nextInt() == rr.nextInt()); // True
    }
 
    private static void predictByNextDouble() {
        long seed = System.currentTimeMillis();
        Random r = new Random(seed);
        ReplicatedRandom rr = new ReplicatedRandom();
        rr.replicateState(r.nextDouble());
        System.out.println(r.nextDouble() == rr.nextDouble()); // True
        System.out.println(r.nextDouble() == rr.nextDouble()); // True
        System.out.println(r.nextDouble() == rr.nextDouble()); // True
    }
 
    // Replicate the state of a Random using a single value from its nextDouble
    public boolean replicateState(double nextDouble) {
        // nextDouble() is generated from ((next(26) << 27) + next(27)) / (1L << 53)
        // Inverting those operations will get us the values of next(26) and next(27)
        long numerator = (long) (nextDouble * (1L << 53));
        int first26 = (int) (numerator >>> 27);
        int last27 = (int) (numerator & ((1L << 27) - 1));
        return replicateState(first26, 26, last27, 27);
    }
 
    // Replicate the state of a Random using a single value from its nextLong
    public boolean replicateState(long nextLong) {
        int last32 = (int) (nextLong & ((1L << 32) - 1));
        int first32 = (int) ((nextLong - last32) >> 32);
        return replicateState(first32, 32, last32, 32);
    }
 
    // Replicate the state of a Random using two consecutive values from its nextInt
    public boolean replicateState(int firstNextInt, int secondNextInt) {
        return replicateState(firstNextInt, 32, secondNextInt, 32);
    }
 
    // Replicate the state of a Random using two consecutive values from its nextFloat
    public boolean replicateState(float firstNextFloat, float secondNextFloat) {
        return replicateState((int) (firstNextFloat * (1 << 24)), 24, (int) (secondNextFloat * (1 << 24)), 24);
    }
 
    public boolean replicateState(int nextN, int n, int nextM, int m) {
        // Constants copied from java.util.Random
        final long multiplier = 0x5DEECE66DL;
        final long addend = 0xBL;
        final long mask = (1L << 48) - 1;
 
        long upperMOf48Mask = ((1L << m) - 1) << (48 - m);
 
        // next(x) is generated by taking the upper x bits of 48 bits of (oldSeed * multiplier + addend) mod (mask + 1)
        // So now we have the upper n and m bits of two consecutive calls of next(n) and next(m)
        long oldSeedUpperN = ((long) nextN << (48 - n)) & mask;
        long newSeedUpperM = ((long) nextM << (48 - m)) & mask;
 
        // Bruteforce the lower (48 - n) bits of the oldSeed that was truncated.
        // Calculate the next seed for each guess of oldSeed and check if it has the same top m bits as our newSeed.
        // If it does then the guess is right and we can add that to our candidate seeds.
        ArrayList<Long> possibleSeeds = new ArrayList<Long>();
        for (long oldSeed = oldSeedUpperN; oldSeed <= (oldSeedUpperN | ((1L << (48 - n)) - 1)); oldSeed++) {
            long newSeed = (oldSeed * multiplier + addend) & mask;
            if ((newSeed & upperMOf48Mask) == newSeedUpperM) {
                possibleSeeds.add(newSeed);
            }
        }
 
        if (possibleSeeds.size() == 1) {
            // If there's only one candidate seed, then we found it!
            setSeed(possibleSeeds.get(0)
                    ^ multiplier); // setSeed(x) sets seed to `(x ^ multiplier) & mask`, so we need another `^ multiplier` to cancel it out
            return true;
        }
        if (possibleSeeds.size() >= 1) {
            System.out.println("Didn't find a unique seed. Possible seeds were: " + possibleSeeds);
        } else {
            System.out.println("Failed to find seed!");
        }
        return false;
    }
}

说明：

  • 上面的算法利用了 Java 生成的随机数有 48 个有效位这一信息；
  • 对于 nextInt 来说，返回值是 32 位，因此在返回结果时，会舍弃低 16 位，这是通过 »> 位移操作实现的；
  • 对于 nextLong 来说，它是由两个连续的 nextInt 组成的；
  • 对于 nextDouble 来说，它是由两个连续的分别是 27 bits 和 26 bits 数字组成的；
  • 因此，当给定一个 nextInt 值时，将其左移 16 位，即得到种子的最小可能值，该值加上 2^16 - 1，就是种子的最大可能值；因此，只需遍历该空间(包含 2^16 个数字)，即可推测出种子的实际值；
  • 现代 CPU 可以在 1 秒内用暴力方法逆向的推测出当前的种子值；

Benchmark

单线程结果： image1

4 线程结果： image1

 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

RandomBenchmark.java

package benchmark;
 
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.OutputTimeUnit;
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.results.format.ResultFormatType;
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;
 
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
 
/**
 */
@BenchmarkMode({Mode.AverageTime, Mode.Throughput})
@Warmup(iterations = 3, time = 1)
@Measurement(iterations = 5, time = 5)
@Threads(4)
@Fork(1)
@State(value = Scope.Benchmark)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class RandomBenchmark {
 
    private final Random random = new Random();
    private final ThreadLocal<Random> simpleThreadLocal = ThreadLocal.withInitial(Random::new);
 
    public static void main(String[] args) throws RunnerException {
        // 将结果文件上传到 https://jmh.morethan.io/ 可以得到可视化结果
        String now = LocalDateTime.now().format(DateTimeFormatter.ofPattern("yyyyMMddHHmmss"));
        String filePath = "/tmp/jmh_result_" + now + ".json";
 
        Options opt = new OptionsBuilder()
                .include(RandomBenchmark.class.getSimpleName())
                .result(filePath)
                .resultFormat(ResultFormatType.JSON).build();
        new Runner(opt).run();
    }
 
    @Benchmark
//    @BenchmarkMode(Throughput)
    public int regularRandom() {
        return random.nextInt();
    }
 
    @Benchmark
//    @BenchmarkMode(Throughput)
    public int simpleThreadLocal() {
        return simpleThreadLocal.get().nextInt();
    }
 
    @Benchmark
//    @BenchmarkMode(Throughput)
    public int builtinThreadLocal() {
        return ThreadLocalRandom.current().nextInt();
    }
}

Reference

© 2022 - 2025 All Rights Reserved
本文总阅读量 次 本文总访客量 人 本站总访问量 次 本站总访客数 人
发表了20篇文章 · 总计32.36k字
本博客已稳定运行
使用 Hugo 构建
主题 Stack 由 Jimmy 设计