一次数学式的抓虫经历

我们这有一个http service,每次应答的时候,它会生一个长度为8的随机字符串发给client。我们假设这个字符串是不会重复的,所以我们把它作为request id来唯一标识一个http request。但是后来做日志分析的时候,我们经常发现这个字符串重复了。 然后我去翻代码,发现有段代码有问题:


static char[] alpha = ("0123456789ABCDEFGHIJKLMNOPQRSTUVWXZY"
           +"0123456789abcdefghijklmnopqrstuvwxzy").toCharArray();

static String getRandStr(int length) {
  char[] ret = new char[length];
  for (int i = 0; i != length; ++i) {
    int pos = ThreadLocalRandom.current().nextInt(alpha.length);
    ret[i] = alpha[pos];
  }
  return new String(ret);
}

我第一眼就发现,0123456789被写了两遍。但是问题是,这究竟是BUG的真正原因吗? 我们这个页面每天要处理200万次请求,如果是从0-9、a-z、A-Z这62个字符随机,那么有效的取值范围是\( 62^8 \),约等于200万亿,根据我之前blog中介绍的公式 \(p = 1- e ^ {-\frac{m(m-1)}{2n}} \) 那么可计算出产生冲突的概率(p)小于百分之一。 但是上面的代码写错了,导致0-9的出现概率增大了一倍,为0.28。我不知道这种情况下该怎么算冲突概率,于是我就想用信息熵的方式模拟,len = 10 *.2777777778 + 52*(1-.2777777778)= 40.3。然后用40.3代替上面的62,计算出来冲突概率是25%。然后我写代码模拟了一下,

public static void main(String[] args) {
  java.util.HashSet results = new java.util.HashSet();
  int badcount = 0;
  for (int j = 0; j != 20; ++j) {
    results.clear();
    for (int i = 0; i != 2000000; ++i) {
      if (!results.add(getRandStr(8))) {
    badcount++;
    break;
      }
    }
  }
  System.out.println(((double) badcount) / 20);
}

发现结果基本吻合。 关于那个冲突概率的计算公式的推导过程请见: http://www.sunchangming.com/blog/post/4141.html

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥