001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, software 013 * distributed under the License is distributed on an "AS IS" BASIS, 014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 015 * See the License for the specific language governing permissions and 016 * limitations under the License. 017 */ 018package org.apache.hadoop.hbase.util; 019 020import java.util.HashSet; 021import java.util.Random; 022import java.util.Set; 023import java.util.concurrent.atomic.AtomicLong; 024import org.apache.yetus.audience.InterfaceAudience; 025 026import org.apache.hbase.thirdparty.com.google.common.base.Preconditions; 027 028/** 029 * An instance of this class is used to generate a stream of pseudorandom numbers. The class uses a 030 * 64-bit seed, which is modified using a linear congruential formula. see 031 * https://en.wikipedia.org/wiki/Linear_congruential_generator 032 */ 033@InterfaceAudience.Private 034public class Random64 { 035 036 private static final long multiplier = 6364136223846793005L; 037 private static final long addend = 1442695040888963407L; 038 039 private static final AtomicLong seedUniquifier = new AtomicLong(8682522807148012L); 040 041 private long seed; 042 043 /** 044 * Copy from {@link Random#seedUniquifier()} 045 */ 046 private static long seedUniquifier() { 047 for (;;) { 048 long current = seedUniquifier.get(); 049 long next = current * 181783497276652981L; 050 if (seedUniquifier.compareAndSet(current, next)) { 051 return next; 052 } 053 } 054 } 055 056 public Random64() { 057 this(seedUniquifier() ^ System.nanoTime()); 058 } 059 060 public Random64(long seed) { 061 this.seed = seed; 062 } 063 064 public long nextLong() { 065 return next64(64); 066 } 067 068 public void nextBytes(byte[] bytes) { 069 for (int i = 0, len = bytes.length; i < len;) { 070 // We regard seed as unsigned long, therefore used '>>>' instead of '>>'. 071 for (long rnd = nextLong(), n = Math.min(len - i, Long.SIZE / Byte.SIZE); n-- > 0; rnd >>>= 072 Byte.SIZE) { 073 bytes[i++] = (byte) rnd; 074 } 075 } 076 } 077 078 private long next64(int bits) { 079 seed = seed * multiplier + addend; 080 return seed >>> (64 - bits); 081 } 082 083 /** 084 * Random64 is a pseudorandom algorithm(LCG). Therefore, we will get same sequence if seeds are 085 * the same. This main will test how many calls nextLong() it will get the same seed. We do not 086 * need to save all numbers (that is too large). We could save once every 100000 calls nextLong(). 087 * If it get a same seed, we can detect this by calling nextLong() 100000 times continuously. 088 */ 089 public static void main(String[] args) { 090 long defaultTotalTestCnt = 1000000000000L; // 1 trillion 091 092 if (args.length == 1) { 093 defaultTotalTestCnt = Long.parseLong(args[0]); 094 } 095 096 Preconditions.checkArgument(defaultTotalTestCnt > 0, "totalTestCnt <= 0"); 097 098 final int precision = 100000; 099 final long totalTestCnt = defaultTotalTestCnt + precision; 100 final int reportPeriod = 100 * precision; 101 final long startTime = EnvironmentEdgeManager.currentTime(); 102 103 System.out.println("Do collision test, totalTestCnt=" + totalTestCnt); 104 105 Random64 rand = new Random64(); 106 Set<Long> longSet = new HashSet<>(); 107 108 for (long cnt = 1; cnt <= totalTestCnt; cnt++) { 109 final long randLong = rand.nextLong(); 110 111 if (longSet.contains(randLong)) { 112 System.err.println("Conflict! count=" + cnt); 113 System.exit(1); 114 } 115 116 if (cnt % precision == 0) { 117 if (!longSet.add(randLong)) { 118 System.err.println("Conflict! count=" + cnt); 119 System.exit(1); 120 } 121 122 if (cnt % reportPeriod == 0) { 123 long cost = EnvironmentEdgeManager.currentTime() - startTime; 124 long remainingMs = (long) (1.0 * (totalTestCnt - cnt) * cost / cnt); 125 System.out.println(String.format("Progress: %.3f%%, remaining %d minutes", 126 100.0 * cnt / totalTestCnt, remainingMs / 60000)); 127 } 128 } 129 130 } 131 132 System.out.println("No collision!"); 133 } 134 135}