2014/10/29

當隨機不再隨機的時候

前幾天, 我寫了一個 Unit Test, 用來測試一個非同步的資料庫寫入方法。如果我一次寫入一百筆, 那麼結果很順利; 寫入兩百筆, 也很順利; 一路測到一千筆, 都很順利, 都能夠在一秒之內成功結束。直到測到一千一百筆, 突然這個 Unit Test 執行不完了。我看到測試總管中狀態條不停地跑, 完全沒有停止的跡象, 直到我把測試取消為止

一開始, 我懷疑這是 .Net 的非同步機制出了問題。莫非是因為非同步處理機制一次應付不了太多 task? 但是應該不是如此; 我以前在同一部機器上測試非同步或平行作業時, 都是以一次幾萬筆的方式在做的。區區一千多筆, 應該不會造成問題。

後來, 我注意到並沒有任何一筆資料被寫入資料庫。我這才發現, 原來程式中的非同步作業根本都還沒開始。問題顯然不在這裡。

由於在 Unit Test 裡做測試並不容易, 我花了一點功夫, 才發現原來是我以隨機方式產生測試資料的程式, 才是問題所在。

這段程式是這樣寫的:

// 程式一
for (int i = 0; i < testCount; i++)
{
    G g = G.GenRandom();
    while (isKeyExists(list, g.Id))
        g = GenRandom();
    list.Add(g);
}

程式中 G.Id 代表這筆資料的 Primary Key (型別為 varchar), 它的值是使用 Random(9999) 產生的。而 list 是一個 List<G> 變數, isKeyExists 則是用來檢查一個 key 是否已存在 list 中的方法。如果我試圖產生一千一百筆隨機資料, 程式中的 while 迴圈就會跑不完。

我總認為, 凡是會寫程式的人一定寫過預測大樂透的程式 -- 因為我就寫過。所以我很久以前就知道在 .Net 中透過 Random 物件產生的隨機數字都不真正是隨機的; 它總會出現一組固定的數字。但是我卻沒有想到, 它原本應該能夠產生一萬組隨機的數字, 卻在大約產生一千一百筆之後, 就困在無窮的重複數字裡了。

有朋友問我是否餵給它相同的 seed。當然不是。我原本已經針對這種問題而預先避免了:

// 程式二
public static G GenRandom()
{
    DateTime now = DateTime.Now;
    G g = new G();
    g.Id = new Random(now.Second + now.Millisecond).Next(9999);
    ...
}

很可惜的, 若使用這種做法, 我的 Unit Test 跑了三十分鐘都跑不完; 它原本應該在一秒之內結束的。

確定問題之後, 我開始在網路上搜尋其他人的經驗。很顯然, 這個問題絕對不是只有我踫到; 相關的結論很多。我採用了其中一種做法, 結果相當有效:

// 程式三
private static int seeder = new Random(DateTime.Now.Second + DateTime.Now.Millisecond).Next();

public static G GenRandom()
{
    G g = new G();
    int seed = Interlocked.Increment(ref seeder);
    g.Id = new Random(seed).Next(9999);
    ...
}

根據 MSDN 的說明, Interlocked.Increment 方法的目的是「遞增特定變數並將結果儲存起來,成為不可部分完成的作業(atomic operation)」。所謂的 "Atomic Operation", 意思是把一段程式當作執行的最小單元; 換句話說, 這段程式不會因分時多工而被拆開執行。對應到上述程式, 假設 seeder 的值原本是 0, 那麼若同時有四個執行緒同時競逐, 它們拿到的 seed 值一定會是 1, 2, 3, 4 四種值, 而不會有像 1, 1, 1, 2 之類的重複值。

除了使用 Interlocked 類別之外, 在上述參考連結中, 也有人建議使用 GUID 作為 seed。我原本認為使用 GUID 恐怕會影響效能, 但是我後來稍作測試之後, 發現效能上的衝擊是觀測不到的。若採用 GUID, 程式可以這樣寫:

// 程式四
public static G GenRandom()
{
    G g = new G();
    int seed = Guid.NewGuid().GetHashCode();
    g.Id = new Random(seed).Next(9999);
    ...
}

不管採用 Interlocked.Increment() 方法或者 GUID, 我就算一次產生九千筆資料, 都能在一秒之內成功結束。但是若和一開始的方法 (程式二) 比較, 差別都只在如何賦予 seed 的值而已。所以我們可以推論, 由於 Second + Millisecond 的值很容易重複, 而一再重複的 seed 值會產生一再重複的「隨機」值, 才會造成程式跑不完的結果。

了解這一點之後, 我們可以把程式二稍為改一下:

// 程式五
public static G GenRandom()
{
    DateTime now = DateTime.Now;
    G g = new G();
    g.Id = new Random(now.Second * 1000 + now.Millisecond).Next(9999);
    ...
}

把 now.Second 的值乘上 1000 之後, 那麼我們就可以解決在一千一百筆時會跑不完的問題(而問題會在約一千多筆時發生, 也正是這個原因造成的)。我應該一開始就這麼做的, 卻忘了 (所以我朋友一開始問我是否餵給它重複的 seed, 他真的問對了)。只不過, 這仍然只是緩兵之計; 如果我們把筆數增加到六萬筆以上, 可以預期又會發生相同的問題。

所以, 在此種情況下, 使用程式三或程式四的做法, 恐怕還是比較好的方法。使用這兩種做法, 我們可以預期問題會在約莫兩億筆 (int.MaxValue) 時才發生; 這麼大的區間, 應該足夠一般應用了吧! 況且, 不要說兩億筆了, 如果你的資料會有超過幾萬、甚至幾百萬筆的機會, 直接使用 GUID 或自動識別值當作 key, 不是更適合嗎?

沒有留言:

張貼留言