周二的时候接到一个新的任务，统计分块大小对系统的读写影响。
具体的描述一下：（注：由于oceanbase已开源，不涉及泄密问题）在我们的系统中，每天要做一次增量合并的操作，比如说整体数据为1到1000，增量数据为1到100，我们按大小把整体数据分为10块。那么第一块数据的范围为1-100，第二块为101-200，以此类推。我们系统的读写是按块来的，也就是说，一次要把所有的一整块（100个数据）都读到内存中，这样的话，当增量数据为1-100时，全部请求都落在了1号块上，那么合并中涉及到的块数量为1；如果增量数据稍微分散一下，变成随机的100个数，很可能造成这100个数落在了不同的块上，那么一次合并操作涉及到的块的数量就可能为10个。
我们需要做的事情就是如何选择块的大小，使得系统中被修改的块的数量比上总块数量的这个比率尽可能小。
最开始这个事情是一个实习生同学负责的，后来由于各种原因，被交接到我这里。
那天接到任务的时候，觉得这其实是一个数学问题，或者说，一个概率问题。
我们可以将这个问题抽象一下，假设所有的数据全部随机，同时，增量数据也全部随机，在这样的前提下，这个问题可以转化为：
将u个不同的小球放入y个不同的盒子中，在操作完成后，不为空的盒子的数量的期望为多少？
将u个不同的小球放入y个不同的盒子中，一共可能有
种方式。
那么，将u个不同的小球都放入同一个盒子中时，概率为：
将u个不同的小球放入2个不同的盒子中时，概率为：
以此类推，在考虑将u个小球放入n个不同的盒子中时，概率应该为：
合并这些子概率，可以得到最终的结果为：
本来以为这样是正确的了，发邮件出去的时候，同事提醒我第二个式子有问题，那个累加是没有必要的，后来仔细思考了一下，发现确实是不对的，推导过程如下：
假设Si为n个球放入i个盒子中，且每一个盒子不空，那么可以得到：
如上证明，可以得到正确的期望为：
当使用这个式子进行模拟实验时，发现在一些情况下会出现负值。也就是说，这个式子的结果仍然是错误的，我们又一次得到的是一个看似正确的结论。
今天一个下午都在思考这个问题，终于发现错误的原因。
我们在使用减法处理空盒情况时，其实违反了互斥原理。
考虑3个盒子的情况，假设集合｛Ai，第i个盒子为空，i=1,2,3}。
总的方式为
所以可以得到：
*（注意：其中的“+”） *
这个值的计算，其实来源一个经典问题：
【定义】n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数。
【定理】S(n,m)=mS(n-1,m)+S(n-1,m-1) (n>1,m>1)
在相同盒子的基础上，我们只要乘以盒子数的全排列，就可以得到不同盒的情况。
所以，我们的结论公式应该为：
其中，
每一个看似正确的地方都可能蕴含着无数的错误和谬论。
**The simple things are always hard. **
over
原文时间(2013-9-4 )
网友评论