2013-02-14 101 views
6

這個問題在StackOverflow上經常出現,但我已經閱讀了所有以前的相關答案,並且對這個問題略有改動。在C中的大型磁盤文件上進行二進制搜索 - 問題

我有一個23Gb文件,其中包含4.75億行的大小相等,每行由40個字符的哈希代碼後跟一個標識符(整數)組成。

我有一個傳入哈希代碼流 - 總計數十億 - 我需要找到每個傳入哈希代碼並打印出相應的標識符。這項工作雖然很大,但只需要進行一次。

文件太大,我讀入內存,所以我一直在嘗試通過以下方式來usemmap:

codes = (char *) mmap(0,statbuf.st_size,PROT_READ,MAP_SHARED,codefile,0); 

然後我使用基於地址的地址算術做一個二進制搜索碼。

這似乎開始工作美麗,並在幾秒鐘內使用100%的cpu產生幾百萬個標識符,但後來一些,看似隨機的時間量減緩到爬行。當我使用ps查看進程時,使用100%的cpu將狀態「R」更改爲使用1%cpu的狀態「D」(磁盤綁定)。

這是不可重複的 - 我可以在相同的數據上再次啓動進程,並且在「慢速爬行」發生之前它可能運行5秒或10秒。昨晚一次,在發生這種情況之前,我花了將近一分鐘時間。

一切都是隻讀的,我沒有試圖對文件進行任何寫操作,並且我已經停止了機器上的所有其他進程(我控制的)。它是一個現代化的紅帽企業Linux 64位機器。

有誰知道爲什麼這個過程變成了磁盤綁定以及如何阻止它?

UPDATE:

感謝大家的回答,和你的想法;之前我以前沒有嘗試過所有的各種改進,因爲我想知道我是否以某種方式錯誤地使用了mmap。但答案的要點似乎是,除非我能把所有東西都記在腦海中,否則我將不可避免地遇到問題。所以我將散列碼的大小壓縮到了不會產生任何重複的前綴前綴的大小 - 前15個字符就足夠了。然後我將結果文件拖入內存,並分別以大約20億次的批量運行傳入的哈希代碼。

+1

你正在碰到虛擬內存的限制。雖然活動數據集適合內存,但一切都是虛擬的。當您需要對數據集進行隨機訪問時,您的數據集太大而無法存儲在內存中,因此您可以開始分頁,併成爲磁盤綁定。這不是一個簡單的方法。是整數存儲爲4字節或8字節的二進制值,還是字符串?重構23 GiB文件是否有可能? – 2013-02-14 02:34:40

+1

@paxdiablo:問題不在於虛擬內存大小的限制;問題是底層的物理內存。該程序仍在運行,但是當物理內存爲16 GiB時,隨機訪問超過23 GiB的數據意味着一旦在內存中獲得了2/3的文件,平均而言,您必須三個內存訪問讀取新頁面,這是痛苦的緩慢。 – 2013-02-14 02:40:14

+0

@JonathanLeffler:是的,我意識到你的意思後,重新閱讀(因此我的刪除評論)。拋出我的是斷言它是虛擬內存的限制(我把它看作是size)而不是虛擬內存_man​​agement_(即映射,正如你在響應中所解釋的那樣)。 – paxdiablo 2013-02-14 02:52:07

回答

3

要做的第一件事是分割文件。

用散列碼和另一個整數ID構成一個文件。由於行是相同的,所以在找到結果後它會排隊。您也可以嘗試一種方法,將每個第n個散列放入另一個文件,然後存儲索引。

例如,每1000個散列鍵放入帶有索引的新文件中,然後將其加載到內存中。然後進行二進制掃描。這將告訴您需要在文件中進一步掃描的1000個條目的範圍。是的,這將做得很好!但可能比這少得多。就像大概每隔20個記錄一樣,將文件大小減少20 + - 如果我想的很好。

換句話說,掃描後只需觸摸磁盤上幾千字節的文件即可。

另一種選擇是拆分文件並將其放入多臺機器的內存中。然後只是二進制掃描每個文件。這將產生絕對最快的可能的搜索零磁盤訪問...

+0

拆分40字節的散列碼和4字節或8字節的整數可能效果不大,你談論的是減少9%或17%。你的第二個建議似乎更有希望。 – paxdiablo 2013-02-14 02:49:57

+0

我接受了這個答案,因爲它包含兩個好主意,即使它沒有涵蓋其他答案的所有方面。 – Gordon 2013-02-15 07:05:43

2

你有沒有考慮黑客一個PATRICIA特里算法?在我看來,如果你可以爲數據文件建立一個PATRICIA樹形表示,它指向散列和整數值的文件,那麼你可能能夠將每個項目減少到節點指針(2 * 64位?), (這種情況下1字節)和文件偏移量(uint64_t,它可能需要對應多個fseek())。

2

有誰知道爲什麼這個過程變成磁盤綁定,以及如何阻止它?

二進制搜索需要在文件中尋找很多。在整個文件不適合內存的情況下,頁面緩存不能很好地處理大的搜索,從而導致您看到的行爲。

處理這個問題的最好方法是減少/阻止大的尋找並使頁面緩存爲你工作。你

三個想法:

如果可以排序的輸入流,您可以搜索在塊的文件,使用類似下面的算法:

code_block <- mmap the first N entries of the file, where N entries fit in memory 
max_code <- code_block[N - 1] 
while(input codes remain) { 
    input_code <- next input code 
    while(input_code > max_code) { 
    code_block <- mmap the next N entries of the file 
    max_code <- code_block[N - 1] 
    } 
    binary search for input code in code_block 
} 

如果您無法對輸入流進行排序,您可以通過構建數據的內存中索引來減少您的磁盤搜索量。越過大文件,並進行了table是:

record_hash, offset into file where this record starts 

所有記錄不要存放在此表 - 商店只有每第K個記錄。選擇一個大K,但足夠小,這適合內存。

要在大文件中搜索給定的目標散列,請在內存中的表中執行二進制搜索以查找table中比目標散列小的最大散列。說這是table[h]。然後,mmap從table[h].offset開始並在table[h+1].offset結束的段,並進行最終的二分查找。這將大大減少磁盤搜索的數量。

如果這還不夠,你可以有索引的多層:

record_hash, offset into index where the next index starts 

當然,你需要提前知道時間指數的多層次怎麼有。


最後,如果你有多餘的錢可你總是可以再次購買的RAM超過23 GB,並且使這個內存約束問題(我只是看着戴爾公司的網站 - 你拿起新低帶32 GB內存的工作站,價格不到$ 1,400澳元)。當然,從磁盤讀取大量數據需要一段時間,但一旦存在,就會被設置。

1

而不是使用mmap,可以考慮只使用普通的舊lseek + read。您可以定義一些輔助功能來讀取哈希值及與其對應的整數:

void read_hash(int line, char *hashbuf) { 
    lseek64(fd, ((uint64_t)line) * line_len, SEEK_SET); 
    read(fd, hashbuf, 40); 
} 

int read_int(int line) { 
    lseek64(fd, ((uint64_t)line) * line_len + 40, SEEK_SET); 
    int ret; 
    read(fd, &ret, sizeof(int)); 
    return ret; 
} 

那麼就做你的二進制搜索如常。它可能會慢一點,但它不會開始咀嚼你的虛擬內存。

+0

+1。這仍然會填充頁面緩存,這在技術上是內核虛擬機子系統的一部分。但是,根據我的經驗,虛擬機子系統能夠更好地處理未映射頁面上的壓力,而不是mmap頁面。這種做法可能沒有幫助,但嘗試一下很容易。 – Nemo 2013-02-14 06:30:20

+0

這很好,但將它與內存中的部分有序地圖結合會更好。換句話說,不是使用24或16個磁盤讀取來定位記錄,而是使用部分搜索。換句話說,就是每64個記錄就是一個例子,而且這個記錄極其縮小。然後在更小的範圍內使用這種磁盤訪問技術。 – 2013-02-14 20:20:56

+0

是的,我同意。我認爲減少I/O總量至關重要,部分映射是一個很好的方法。 – nneonneo 2013-02-15 02:59:45

1

我們不知道背後的故事。所以很難給你明確的建議。你有多少內存?你的硬盤有多複雜?這是一個學習項目嗎?誰在爲你的時間付錢?與價格爲50美元/小時的人員的兩天工作相比,32GB的RAM似乎不那麼昂貴。這需要多快運行?你願意走多遠?您的解決方案需要使用高級操作系統概念嗎?你嫁給了一個C程序嗎?如何使Postgres處理這個問題?

這是一個低風險的選擇。這種選擇不像其他建議那樣具有智力上的吸引力,但有可能爲您帶來重大收益。將文件分成3個8GB塊或6個4GB塊(取決於你周圍的機器,它需要適合內存)。在每臺機器上運行相同的軟件,但在內存中並在每個機器上放置一個RPC存根。爲每個3或6個工人編寫一個RPC調用者,以確定與給定散列碼關聯的整數。

+0

所有的優點......事實證明,該機器已經擁有32Gb內存(這引發了爲什麼它首先存在磁盤綁定的問題)。我需要一個我的研究項目的數據,但這是一次創建一個數據集,我隨後將其存儲在一個數據庫中,所以它不是專門編程的學習項目,儘管我需要學習足夠的知識它可能會在將來做類似的事情。語言是C,因爲這就是我最清楚的。 – Gordon 2013-02-15 07:11:04