一次数学式的抓虫经历
by snnn
at 2012-09-14 21:55:03
original http://www.udpwork.com/item/8114.html
我们这有一个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/?p=4141
<div style="margin-top:8px;padding:6px 0;border-top:1px solid #3cf">
<div style="text-align:center;margin:16px 0;padding:6px;border:0px dashed #999;font-family:arial;font-size:26px;font-weight:bold">
<a href="http://www.udpwork.com/item/8114.html#review_form" title="不喜欢" style="text-decoration:none">
<img src="http://www.udpwork.com//images/thumb_down24.gif" alt="">
<span style="color:#f33">0</span>
</a>
<a href="http://www.udpwork.com/item/8114.html#review_form" title="喜欢" style="text-decoration:none">
<img src="http://www.udpwork.com//images/thumb_up24.gif" alt="">
<span style="color:#3c3">0</span>
</a>