App下載

java高并發(fā)情況下高效的隨機(jī)數(shù)生成器

猿友 2021-07-19 15:38:47 瀏覽數(shù) (2723)
反饋

在 java 語言中有提供現(xiàn)成的 Random類的方法來實(shí)現(xiàn)生成隨機(jī)數(shù)，但并不屬于是“高并發(fā)”的。本文將為您介紹在 java 高并發(fā)的情況下實(shí)現(xiàn)生成隨機(jī)數(shù)，對于性能有要求的小伙伴們，這篇文章值得參考一下。

前言

在代碼中生成隨機(jī)數(shù)，是一個非常常用的功能，并且JDK已經(jīng)提供了一個現(xiàn)成的Random類來實(shí)現(xiàn)它，并且Random類是線程安全的。

下面是Random.next()生成一個隨機(jī)整數(shù)的實(shí)現(xiàn)：

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
      //CAS 有競爭是效率低下
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

不難看到，上面的方法中使用CAS操作更新seed，在大量線程競爭的場景下，這個CAS操作很可能失敗，失敗了就會重試，而這個重試又會消耗CPU運(yùn)算，從而使得性能大大下降了。

因此，雖然Random是線程安全的，但是并不是“高并發(fā)”的。

為了改進(jìn)這個問題，增強(qiáng)隨機(jī)數(shù)生成器在高并發(fā)環(huán)境中的性能，于是乎，就有了ThreadLocalRandom——一個性能強(qiáng)悍的高并發(fā)隨機(jī)數(shù)生成器。

ThreadLocalRandom繼承自Random，根據(jù)里氏代換原則，這說明ThreadLocalRandom提供了和Random相同的隨機(jī)數(shù)生成功能，只是實(shí)現(xiàn)算法略有不同。

在Thread中的變量

為了應(yīng)對線程競爭，Java中有一個ThreadLocal類，為每一個線程分配了一個獨(dú)立的，互不相干的存儲空間。

ThreadLocal的實(shí)現(xiàn)依賴于Thread對象中的ThreadLocal.ThreadLocalMap threadLocals成員字段。

與之類似，為了讓隨機(jī)數(shù)生成器只訪問本地線程數(shù)據(jù)，從而避免競爭，在Thread中，又增加了3個成員：

/** The current seed for a ThreadLocalRandom */
@sun.misc.Contended("tlr")
long threadLocalRandomSeed;
/** Probe hash value; nonzero if threadLocalRandomSeed initialized */
@sun.misc.Contended("tlr")
int threadLocalRandomProbe;
/** Secondary seed isolated from public ThreadLocalRandom sequence */
@sun.misc.Contended("tlr")
int threadLocalRandomSecondarySeed;

這3個字段作為Thread類的成員，便自然和每一個Thread對象牢牢得捆綁在一起，因此成為了名副其實(shí)的ThreadLocal變量，而依賴這幾個變量實(shí)現(xiàn)的隨機(jī)數(shù)生成器，也就成為了ThreadLocalRandom。

消除偽共享

不知道大家有沒有注意到， 在這些變量上面，都帶有一個注解@sun.misc.Contended，這個注解是干什么用的呢？要了解這個，大家得先知道一下并發(fā)編程中的一個重要問題——偽共享：

我們知道，CPU是不直接訪問內(nèi)存的，數(shù)據(jù)都是從高速緩存中加載到寄存器的，高速緩存又有L1，L2，L3等層級。在這里，我們先簡化這些負(fù)責(zé)的層級關(guān)系，假設(shè)只有一級緩存和一個主內(nèi)存。

CPU讀取和更新緩存的時候，是以行為單位進(jìn)行的，也叫一個cache line，一行一般64字節(jié)，也就是8個long的長度。

因此，問題就來了，一個緩存行可以放多個變量，如果多個線程同時訪問的不同的變量，而這些不同的變量又恰好位于同一個緩存行，那會發(fā)生什么呢？

如上圖所示，X,Y為相鄰2個變量，位于同一個緩存行，兩個CPU core1 core2都加載了他們，core1更新X，同時，core2更新Y，由于數(shù)據(jù)的讀取和更新是以緩存行為單位的，這就意味著當(dāng)這2件事同時發(fā)生時，就產(chǎn)生了競爭，導(dǎo)致core1和core2有可能需要重新刷新自己的數(shù)據(jù)（緩存行被對方更新了），這就導(dǎo)致系統(tǒng)的性能大大折扣，這就是偽共享問題。

那怎么改進(jìn)呢？如下圖：

上圖中，我們把X單獨(dú)占用一個緩存行，Y單獨(dú)占用一個緩存行，這樣各自更新和讀取，都不會有任何影響了。

而上述代碼中的@sun.misc.Contended(“tlr”)就會在虛擬機(jī)層面，幫助我們在變量的前后生成一些padding，使得被標(biāo)注的變量位于同一個緩存行，不與其它變量沖突。

在Thread對象中，成員變量threadLocalRandomSeed，threadLocalRandomProbe，threadLocalRandomSecondarySeed被標(biāo)記為同一個組tlr，使得這3個變量放置于一個單獨(dú)的緩存行，而不與其它變量發(fā)生沖突，從而提高在并發(fā)環(huán)境中的訪問速度。

反射的高效替代方案

隨機(jī)數(shù)的產(chǎn)生需要訪問Thread的threadLocalRandomSeed等成員，但是考慮到類的封裝性，這些成員卻是包內(nèi)可見的。

很不幸，ThreadLocalRandom位于java.util.concurrent包，而Thread則位于java.lang包，因此，ThreadLocalRandom并沒有辦法訪問Thread的threadLocalRandomSeed等變量。

這時，Java老鳥們可能就會跳出來說：這算什么，看我的反射大法，不管啥都能摳出來訪問一下。

說的不錯，反射是一種可以繞過封裝，直接訪問對象內(nèi)部數(shù)據(jù)的方法，但是，反射的性能不太好，并不適合作為一個高性能的解決方案。

有沒有什么辦法可以讓ThreadLocalRandom訪問Thread的內(nèi)部成員，同時又具有遠(yuǎn)超于反射的，且無限接近于直接變量訪問的方法呢？答案是肯定的，這就是使用Unsafe類。

這里，就簡單介紹一下用的兩個Unsafe的方法：

public native long    getLong(Object o, long offset);
public native void    putLong(Object o, long offset, long x);

其中g(shù)etLong()方法，會讀取對象o的第offset字節(jié)偏移量的一個long型數(shù)據(jù)；putLong()則會將x寫入對象o的第offset個字節(jié)的偏移量中。

這類類似C的操作方法，帶來了極大的性能提升，更重要的是，由于它避開了字段名，直接使用偏移量，就可以輕松繞過成員的可見性限制了。

性能問題解決了，那下一個問題是，我怎么知道threadLocalRandomSeed成員在Thread中的偏移位置呢，這就需要用unsafe的objectFieldOffset()方法了，請看下面的代碼：

上述這段static代碼，在ThreadLocalRandom類初始化的時候，就取得了Thread成員變量threadLocalRandomSeed，threadLocalRandomProbe，threadLocalRandomSecondarySeed在對象偏移中的位置。

因此，只要ThreadLocalRandom需要使用這些變量，都可以通過unsafe的getLong()和putLong()來進(jìn)行訪問(也可能是getInt()和putInt())。

比如在生成一個隨機(jī)數(shù)的時候：

protected int next(int bits) {
    return (int)(mix64(nextSeed()) >>> (64 - bits));
}
final long nextSeed() {
    Thread t; long r; // read and update per-thread seed
    //在ThreadLocalRandom中，訪問了Thread的threadLocalRandomSeed變量
    UNSAFE.putLong(t = Thread.currentThread(), SEED,
                   r = UNSAFE.getLong(t, SEED) + GAMMA);
    return r;
}

這種Unsafe的方法掉地能有多快呢，讓我們一起看做個試驗(yàn)看看：

這里，我們自己寫一個ThreadTest類，使用反射和unsafe兩種方法，來不停讀寫threadLocalRandomSeed成員變量，比較它們的性能差異，代碼如下：

上述代碼中，分別使用反射方式byReflection() 和Unsafe的方式byUnsafe()來讀寫threadLocalRandomSeed變量1億次，得到的測試結(jié)果如下：

byUnsafe spend :171ms
byReflection spend :645ms

不難看到，使用Unsafe的方法遠(yuǎn)遠(yuǎn)優(yōu)于反射的方法，這也是JDK內(nèi)部，大量使用Unsafe來替代反射的原因之一。

隨機(jī)數(shù)種子

我們知道，偽隨機(jī)數(shù)生成都需要一個種子，threadLocalRandomSeed和threadLocalRandomSecondarySeed就是這里的種子。其中threadLocalRandomSeed是long型的，threadLocalRandomSecondarySeed是int。

threadLocalRandomSeed是使用最廣泛的大量的隨機(jī)數(shù)其實(shí)都是基于threadLocalRandomSeed的。而threadLocalRandomSecondarySeed只是某些特定的JDK內(nèi)部實(shí)現(xiàn)中有使用，使用并不廣泛。

初始種子默認(rèn)使用的是系統(tǒng)時間：

上述代碼中完成了種子的初始化，并將初始化的種子通過UNSAFE存在SEED的位置（即threadLocalRandomSeed）。

接著就可以使用nextInt()方法獲得隨機(jī)整數(shù)了：

public int nextInt() {
    return mix32(nextSeed());
}    
final long nextSeed() {
    Thread t; long r; // read and update per-thread seed
    UNSAFE.putLong(t = Thread.currentThread(), SEED,
                   r = UNSAFE.getLong(t, SEED) + GAMMA);
    return r;
}

每一次調(diào)用nextInt()都會使用nextSeed()更新threadLocalRandomSeed。由于這是一個線程獨(dú)有的變量，因此完全不會有競爭，也不會有CAS的重試，性能也就大大提高了。

探針Probe的作用

除了種子外，還有一個threadLocalRandomProbe探針變量，這個變量是用來做什么的呢？

我們可以把threadLocalRandomProbe 理解為一個針對每個Thread的Hash值（不為0），它可以用來作為一個線程的特征值，基于這個值可以為線程在數(shù)組中找到一個特定的位置。

static final int getProbe() {
    return UNSAFE.getInt(Thread.currentThread(), PROBE);
}

來看一個代碼片段：

CounterCell[] as; long b, s;
if ((as = counterCells) != null ||
    !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
    CounterCell a; long v; int m;
    boolean uncontended = true;
    if (as == null || (m = as.length - 1) < 0 ||
        // 使用probe，為每個線程找到一個在數(shù)組as中的位置
        // 由于每個線程的probe值不一樣，因此大概率 每個線程對應(yīng)的數(shù)組中的元素也是不一樣的
        // 每個線程對應(yīng)了不同的元素，就可以沒有沖突的進(jìn)行完全的并發(fā)操作
        // 因此探針probe在這里 就起到了防止沖突的作用
        (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
        !(uncontended =
          U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {

在具體的實(shí)現(xiàn)中，如果上述代碼發(fā)生了沖突，那么，還可以使用ThreadLocalRandom.advanceProbe()方法來修改一個線程的探針值，這樣可以進(jìn)一步避免未來可能得沖突，從而減少競爭，提高并發(fā)性能。

static final int advanceProbe(int probe) {
    //根據(jù)當(dāng)前探針值，計算一個更新的探針值
    probe ^= probe << 13;   // xorshift
    probe ^= probe >>> 17;
    probe ^= probe << 5;
    //更新探針值到線程對象中 即修改了threadLocalRandomProbe變量
    UNSAFE.putInt(Thread.currentThread(), PROBE, probe);
    return probe;
}

總結(jié)

今天，我們介紹了ThreadLocalRandom對象，這是一個高并發(fā)環(huán)境中的，高性能的隨機(jī)數(shù)生成器。

我們不但介紹了ThreadLocalRandom的功能和內(nèi)部實(shí)現(xiàn)原理，還介紹介紹了ThreadLocalRandom對象是如何達(dá)到高性能的（比如通過偽共享，Unsafe等手段），希望大家可以將這些技術(shù)靈活運(yùn)用到自己的工程中。

以上就是java高并發(fā)情況下高效的隨機(jī)數(shù)生成器的詳細(xì)內(nèi)容，想要了解更多關(guān)于java高并發(fā)高效隨機(jī)數(shù)的資料請關(guān)注W3Cschool其它相關(guān)文章！


Java

0 人點(diǎn)贊