hbase-common/src/main/java/org/apache/hadoop/hbase/util/Random64.java

   1 /**
   2  *
   3  * Licensed to the Apache Software Foundation (ASF) under one
   4  * or more contributor license agreements.  See the NOTICE file
   5  * distributed with this work for additional information
   6  * regarding copyright ownership.  The ASF licenses this file
   7  * to you under the Apache License, Version 2.0 (the
   8  * "License"); you may not use this file except in compliance
   9  * with the License.  You may obtain a copy of the License at
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 package org.apache.hadoop.hbase.util;
  21
  22 import java.util.HashSet;
  23 import java.util.Random;
  24 import java.util.Set;
  25 import java.util.concurrent.atomic.AtomicLong;
  26 import org.apache.yetus.audience.InterfaceAudience;
  27 import org.apache.hbase.thirdparty.com.google.common.base.Preconditions;
  28
  29 /**
  30  *
  31  * An instance of this class is used to generate a stream of
  32  * pseudorandom numbers. The class uses a 64-bit seed, which is
  33  * modified using a linear congruential formula.
  34  *
  35  * see https://en.wikipedia.org/wiki/Linear_congruential_generator
  36  */
  37 @InterfaceAudience.Private
  38 public class Random64 {
  39
  40   private static final long multiplier = 6364136223846793005L;
  41   private static final long addend = 1442695040888963407L;
  42
  43   private static final AtomicLong seedUniquifier
  44         = new AtomicLong(8682522807148012L);
  45
  46   private long seed;
  47
  48   /**
  49    * Copy from {@link Random#seedUniquifier()}
  50    */
  51   private static long seedUniquifier() {
  52     for (; ; ) {
  53       long current = seedUniquifier.get();
  54       long next = current * 181783497276652981L;
  55       if (seedUniquifier.compareAndSet(current, next)) {
  56         return next;
  57       }
  58     }
  59   }
  60
  61   public Random64() {
  62     this(seedUniquifier() ^ System.nanoTime());
  63   }
  64
  65   public Random64(long seed) {
  66     this.seed = seed;
  67   }
  68
  69   public long nextLong() {
  70     return next64(64);
  71   }
  72
  73   public void nextBytes(byte[] bytes) {
  74     for (int i = 0, len = bytes.length; i < len;) {
  75       // We regard seed as unsigned long, therefore used '>>>' instead of '>>'.
  76       for (long rnd = nextLong(), n = Math.min(len - i, Long.SIZE / Byte.SIZE);
  77            n-- > 0; rnd >>>= Byte.SIZE) {
  78         bytes[i++] = (byte) rnd;
  79       }
  80     }
  81   }
  82
  83   private long next64(int bits) {
  84     seed = seed * multiplier + addend;
  85     return seed >>> (64 - bits);
  86   }
  87
  88
  89   /**
  90    * Random64 is a pseudorandom algorithm(LCG). Therefore, we will get same sequence
  91    * if seeds are the same. This main will test how many calls nextLong() it will
  92    * get the same seed.
  93    *
  94    * We do not need to save all numbers (that is too large). We could save
  95    * once every 100000 calls nextLong(). If it get a same seed, we can
  96    * detect this by calling nextLong() 100000 times continuously.
  97    *
  98    */
  99   public static void main(String[] args) {
 100     long defaultTotalTestCnt = 1000000000000L; // 1 trillion
 101
 102     if (args.length == 1) {
 103       defaultTotalTestCnt = Long.parseLong(args[0]);
 104     }
 105
 106     Preconditions.checkArgument(defaultTotalTestCnt > 0, "totalTestCnt <= 0");
 107
 108     final int precision = 100000;
 109     final long totalTestCnt = defaultTotalTestCnt + precision;
 110     final int reportPeriod = 100 * precision;
 111     final long startTime = System.currentTimeMillis();
 112
 113     System.out.println("Do collision test, totalTestCnt=" + totalTestCnt);
 114
 115     Random64 rand = new Random64();
 116     Set<Long> longSet = new HashSet<>();
 117
 118     for (long cnt = 1; cnt <= totalTestCnt; cnt++) {
 119       final long randLong = rand.nextLong();
 120
 121       if (longSet.contains(randLong)) {
 122         System.err.println("Conflict! count=" + cnt);
 123         System.exit(1);
 124       }
 125
 126       if (cnt % precision == 0) {
 127         if (!longSet.add(randLong)) {
 128           System.err.println("Conflict! count=" + cnt);
 129           System.exit(1);
 130         }
 131
 132         if (cnt % reportPeriod == 0) {
 133           long cost = System.currentTimeMillis() - startTime;
 134           long remainingMs = (long) (1.0 * (totalTestCnt - cnt) * cost / cnt);
 135           System.out.println(
 136             String.format(
 137               "Progress: %.3f%%, remaining %d minutes",
 138               100.0 * cnt / totalTestCnt, remainingMs / 60000
 139             )
 140           );
 141         }
 142       }
 143
 144     }
 145
 146     System.out.println("No collision!");
 147   }
 148
 149 }