入職一周，還算比較清閑。沒(méi)有一些明確時(shí)間點(diǎn)的事情，所以目前的大部分時(shí)候，探索成分居多，絞盡腦汁做的某些架構(gòu)設(shè)計(jì)，不談結(jié)果，就過(guò)程而言，收獲頗豐。
總的來(lái)說(shuō)，蠻喜歡目前的狀態(tài)，思考>編碼。
今天下午，旁邊的同事在做一個(gè)關(guān)于庫(kù)上的檢查，簡(jiǎn)單說(shuō)就是判斷數(shù)據(jù)庫(kù)的某些字段是否唯一。
最開始是一條sql語(yǔ)句，大概是這樣的：

select * from aaa group by aaa.bbb, aaa.ccc having count(*) > 1;

全表大概1000w的數(shù)據(jù)，第一次執(zhí)行，用了16分鐘。

我們的mysql是架在一臺(tái)12核，128Gb內(nèi)存的機(jī)器上，應(yīng)該說(shuō)資源是足夠的，但是這樣的執(zhí)行時(shí)間，相比于oracle的2分鐘左右的處理速度，還是慢了太多。
單純select *大概在1分鐘左右，所以大部分的開銷在group by上，從這點(diǎn)上看，mysql的一些計(jì)算能力確實(shí)欠缺太多。

后來(lái)考慮優(yōu)化，將select *的結(jié)果全部裝入內(nèi)存，然后進(jìn)行查找。
思路上，沒(méi)有任何問(wèn)題，但他的實(shí)施是這樣的：
判斷重復(fù)時(shí)，使用了2個(gè)循環(huán)，如下：

vector<string> data;

for (int i = 0; i < data.size(); i++)
{
    for (int j = i + 1; j < data.size(); j++)
    {
        if (data[i] == data[j])
        {
            //do some
        }
    }
}

這個(gè)代碼執(zhí)行了大概30分鐘，仍然沒(méi)有結(jié)果。
正好當(dāng)時(shí)沒(méi)事，就幫他做了一些優(yōu)化。很顯然，這樣的一個(gè)唯一性檢查使用窮舉是有問(wèn)題的，復(fù)雜度在O(N^2)，對(duì)于1000w這樣的數(shù)量級(jí)，O(N^2)基本上是不可實(shí)現(xiàn)的。所以第一步的優(yōu)化，就是將這個(gè)算法的復(fù)雜度降下來(lái)。
增加一個(gè)排序操作，這樣，程序的處理流程將變?yōu)椋?br> 1 排序
2 兩兩比較，確定非唯一值

總體的復(fù)雜度為O(N logN)
在排序中，使用了stl的sort函數(shù)進(jìn)行排序，程序整體執(zhí)行一遍的時(shí)間為7分鐘。刨掉出庫(kù)select的1分鐘，排序的時(shí)間在6分鐘左右。這么說(shuō)來(lái)，還是有些慢。這個(gè)時(shí)候，更好的優(yōu)化方式是將算法更改為hash，這樣時(shí)間復(fù)雜度將降為O(N)，那么將會(huì)有質(zhì)的提升，但是考慮到stl的map是紅黑樹實(shí)現(xiàn)，復(fù)雜度為O(N logN)，并不是很好的選擇，而自己重新寫一個(gè)hash函數(shù)好像又比較麻煩。所以權(quán)衡了一下，還是繼續(xù)從排序入手。

最開始，想要將排序操作轉(zhuǎn)移到mysql上執(zhí)行，也就是在出庫(kù)的同時(shí)進(jìn)行排序，需要把出庫(kù)語(yǔ)句改為：

select * from aaa order by aaa.bbb, aaa.ccc;

這樣之后，內(nèi)存中只需要一次遍歷就好，時(shí)間開銷基本可以忽略，這條sql的執(zhí)行時(shí)間為4分鐘，雖然相比于前面有了一些提升，但還是不夠理想，還需要進(jìn)一步的優(yōu)化。

在上文的程序中，我們發(fā)現(xiàn)全部的數(shù)據(jù)存儲(chǔ)在一個(gè)vector里，每一條數(shù)據(jù)為一個(gè)string，因此核心的開銷為string的operator < 比較操作。string是一個(gè)相對(duì)來(lái)說(shuō)比較龐大的類，會(huì)造成許多的額外開銷。
我們只需要比較2個(gè)字段的唯一性，完全可以將這兩個(gè)字段拼接起來(lái)，存在一個(gè)char*中，之后的比較基于memcmp。
當(dāng)然，可能有這樣的問(wèn)題，第一條記錄的第一個(gè)字段為“123”，第二個(gè)字段為“456”；而第二條記錄的第一個(gè)字段為“12”，第二個(gè)字段為“3456”，這樣本來(lái)不等的兩個(gè)字段，拼接后相同。解決方式也很簡(jiǎn)單，在“123”的結(jié)束位置加入一個(gè)特殊字符，再拼接，這樣就可以了。
在更改為char*之后，數(shù)據(jù)的排序時(shí)間從原來(lái)的3分鐘降到了40秒。

目前來(lái)看，總體的執(zhí)行時(shí)間為1分鐘40秒，其中出庫(kù)1分鐘，排序40秒。系統(tǒng)的整體瓶頸轉(zhuǎn)移到了出庫(kù)這里，這里的優(yōu)化方式就相當(dāng)明顯了，我們只是用到了2個(gè)字段，完全沒(méi)有必要select *，只需要將select語(yǔ)句改為：

select aaa.bbb, aaa.ccc from aaa;

這樣更改后，出庫(kù)的時(shí)間為13秒，整體的執(zhí)行時(shí)間為50秒。

這個(gè)時(shí)間，已經(jīng)完全符合要求了，但是為了追求更高的速度，繼續(xù)將計(jì)算并行化，也就是說(shuō)，充分利用cpu的多核計(jì)算能力，將任務(wù)盡可能的拆分為多個(gè)線程來(lái)完成。對(duì)于本例來(lái)說(shuō)，我們并不需要整體有序的數(shù)據(jù)，因此，考慮hadoop的分桶思想，我們將取出的char*每位相加，得到的結(jié)果對(duì)10取余，將結(jié)果分散到10個(gè)線程去做，最后的執(zhí)行結(jié)果為4秒鐘。

經(jīng)過(guò)上面的一步步優(yōu)化，總共的執(zhí)行時(shí)間為17秒。
(原文時(shí)間2014-1-15)