周二的時(shí)候接到一個(gè)新的任務(wù)，統(tǒng)計(jì)分塊大小對(duì)系統(tǒng)的讀寫(xiě)影響。
具體的描述一下：（注：由于oceanbase已開(kāi)源痊班，不涉及泄密問(wèn)題）在我們的系統(tǒng)中，每天要做一次增量合并的操作摹量，比如說(shuō)整體數(shù)據(jù)為1到1000涤伐，增量數(shù)據(jù)為1到100馒胆，我們按大小把整體數(shù)據(jù)分為10塊。那么第一塊數(shù)據(jù)的范圍為1-100凝果，第二塊為101-200祝迂，以此類(lèi)推。我們系統(tǒng)的讀寫(xiě)是按塊來(lái)的器净，也就是說(shuō)型雳，一次要把所有的一整塊（100個(gè)數(shù)據(jù)）都讀到內(nèi)存中，這樣的話掌动，當(dāng)增量數(shù)據(jù)為1-100時(shí)四啰，全部請(qǐng)求都落在了1號(hào)塊上，那么合并中涉及到的塊數(shù)量為1粗恢；如果增量數(shù)據(jù)稍微分散一下柑晒，變成隨機(jī)的100個(gè)數(shù)，很可能造成這100個(gè)數(shù)落在了不同的塊上眷射，那么一次合并操作涉及到的塊的數(shù)量就可能為10個(gè)匙赞。
我們需要做的事情就是如何選擇塊的大小，使得系統(tǒng)中被修改的塊的數(shù)量比上總塊數(shù)量的這個(gè)比率盡可能小妖碉。
最開(kāi)始這個(gè)事情是一個(gè)實(shí)習(xí)生同學(xué)負(fù)責(zé)的涌庭，后來(lái)由于各種原因，被交接到我這里欧宜。
那天接到任務(wù)的時(shí)候坐榆，覺(jué)得這其實(shí)是一個(gè)數(shù)學(xué)問(wèn)題，或者說(shuō)冗茸，一個(gè)概率問(wèn)題席镀。
我們可以將這個(gè)問(wèn)題抽象一下，假設(shè)所有的數(shù)據(jù)全部隨機(jī)夏漱，同時(shí)豪诲，增量數(shù)據(jù)也全部隨機(jī)，在這樣的前提下挂绰，這個(gè)問(wèn)題可以轉(zhuǎn)化為：
將u個(gè)不同的小球放入y個(gè)不同的盒子中屎篱，在操作完成后，不為空的盒子的數(shù)量的期望為多少葵蒂？
將u個(gè)不同的小球放入y個(gè)不同的盒子中交播，一共可能有
種方式。
那么践付，將u個(gè)不同的小球都放入同一個(gè)盒子中時(shí)秦士，概率為：
將u個(gè)不同的小球放入2個(gè)不同的盒子中時(shí)，概率為：
以此類(lèi)推荔仁，在考慮將u個(gè)小球放入n個(gè)不同的盒子中時(shí)伍宦，概率應(yīng)該為：
合并這些子概率，可以得到最終的結(jié)果為：
本來(lái)以為這樣是正確的了乏梁，發(fā)郵件出去的時(shí)候次洼，同事提醒我第二個(gè)式子有問(wèn)題，那個(gè)累加是沒(méi)有必要的遇骑，后來(lái)仔細(xì)思考了一下卖毁，發(fā)現(xiàn)確實(shí)是不對(duì)的，推導(dǎo)過(guò)程如下：
假設(shè)Si為n個(gè)球放入i個(gè)盒子中落萎，且每一個(gè)盒子不空亥啦，那么可以得到：
如上證明，可以得到正確的期望為：
當(dāng)使用這個(gè)式子進(jìn)行模擬實(shí)驗(yàn)時(shí)练链，發(fā)現(xiàn)在一些情況下會(huì)出現(xiàn)負(fù)值翔脱。也就是說(shuō)，這個(gè)式子的結(jié)果仍然是錯(cuò)誤的媒鼓，我們又一次得到的是一個(gè)看似正確的結(jié)論届吁。
今天一個(gè)下午都在思考這個(gè)問(wèn)題，終于發(fā)現(xiàn)錯(cuò)誤的原因绿鸣。
我們?cè)谑褂脺p法處理空盒情況時(shí)疚沐，其實(shí)違反了互斥原理。
考慮3個(gè)盒子的情況潮模，假設(shè)集合｛Ai亮蛔，第i個(gè)盒子為空，i=1,2,3}擎厢。
總的方式為
所以可以得到：
*（注意：其中的“+”） *
這個(gè)值的計(jì)算究流，其實(shí)來(lái)源一個(gè)經(jīng)典問(wèn)題：
【定義】n個(gè)有區(qū)別的球放到m個(gè)相同的盒子中，要求無(wú)一空盒锉矢，其不同的方案數(shù)用S(n,m)表示梯嗽，稱(chēng)為第二類(lèi)Stirling數(shù)。
【定理】S(n,m)=mS(n-1,m)+S(n-1,m-1) (n>1,m>1)
在相同盒子的基礎(chǔ)上沽损，我們只要乘以盒子數(shù)的全排列灯节，就可以得到不同盒的情況。
所以绵估，我們的結(jié)論公式應(yīng)該為：
其中炎疆，
每一個(gè)看似正確的地方都可能蘊(yùn)含著無(wú)數(shù)的錯(cuò)誤和謬論。
**The simple things are always hard. **
over
原文時(shí)間(2013-9-4 )
