Wyszukiwanie binarne na dużym pliku dyskowym w języku C - problemy

Question

To pytanie powtarza się często w StackOverflow, ale przeczytałem wszystkie poprzednie stosowne odpowiedzi i nieznacznie skręciłem pytanie.

Mam plik 23 GB zawierający 475 milionów linii o równej wielkości, z każdą linią składającą się z 40-znakowego kodu skrótu, po którym następuje identyfikator (liczba całkowita).

Mam strumień przychodzących kodów skrótu - w sumie miliardów - i dla każdego przychodzącego kodu skrótu muszę go zlokalizować i wydrukować odpowiedni identyfikator. Ta praca, choć duża, musi być wykonana tylko raz.

Plik jest zbyt duży dla mnie do odczytu do pamięci, a więc starali się usemmap w następujący sposób:

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

Potem po prostu zrobić wyszukiwania binarnego za pomocą adresu arytmetyczne na podstawie adresu w kody.

Wydaje się rozpocząć pracę pięknie i produkuje kilka milionów identyfikatorów w ciągu kilku sekund, przy użyciu 100% procesora, ale to po niektórych, pozornie przypadkowe, czas zwalnia do indeksowania. Kiedy patrzę na proces za pomocą ps, zmieniło się ze statusu "R" przy użyciu 100% procesora, na status "D" (diskbound), używając 1% procesora.

Nie można tego powtórzyć - mogę ponownie rozpocząć proces na tych samych danych i może to potrwać 5 sekund lub 10 sekund, zanim nastąpi "powolne indeksowanie". Kiedyś ubiegłej nocy, miałem prawie minutę przed tym, zanim to się stało.

Wszystko jest tylko do odczytu, nie próbuję żadnych zapisów do pliku i zatrzymałem wszystkie inne procesy (które kontroluję) na komputerze. Jest to nowoczesny 64-bitowy komputer Red Hat Enterprise Linux.

Czy ktoś wie, dlaczego proces staje się związany z dyskiem i jak go zatrzymać?

UPDATE:

Dzięki wszystkim za odbieranie i dla swoich pomysłów; Nie próbowałem wcześniej wszystkich różnych ulepszeń, ponieważ zastanawiałem się, czy w jakiś sposób niewłaściwie używam mmap. Ale istotą odpowiedzi wydawało się, że jeśli nie będę w stanie wcisnąć wszystkiego do pamięci, nieuchronnie napotkam problemy. Więc zgniotłem rozmiar kodu skrótu do rozmiaru przedrostka wiodącego, który nie tworzył żadnych duplikatów - wystarczało pierwszych 15 znaków. Następnie wyciągnąłem plik wynikowy do pamięci i uruchomiłem przychodzące kody skrótów w partiach po około 2 miliardy.

Answer 1

Pierwszą rzeczą do zrobienia jest podzielenie pliku.

Utwórz jeden plik z hash-codes, a drugi z integer ids. Ponieważ rzędy są takie same, to ustawią się dokładnie po znalezieniu wyniku. Możesz także wypróbować podejście, które umieszcza każdy n-ty mieszek w innym pliku, a następnie przechowuje indeks.

Na przykład co 1000-ty klucz hashowy umieszczany jest w nowym pliku z indeksem, a następnie ładowany do pamięci. Następnie zamiast tego skanuj plik binarny. To powie ci zakres 1000 wpisów, które muszą być dalej zeskanowane w pliku. Tak, zrobi to dobrze! Ale prawdopodobnie znacznie mniej. Jakby prawdopodobnie co 20 rekordów podzieliłoby ten rozmiar pliku o 20 + - jeśli dobrze myślę.

Innymi słowy po zeskanowaniu wystarczy dotknąć kilku kilobajtów pliku na dysku.

Inną opcją jest podzielenie pliku i umieszczenie go w pamięci na wielu komputerach. Następnie po prostu binarne skanowanie każdego pliku. Da to absolutnie najszybsze możliwe wyszukiwanie z zerowym dostępem do dysku ...

Answer 2

Czy rozważałeś włamanie się do algorytmu PATRICIA? Wydaje mi się, że jeśli możesz zbudować reprezentację drzewa PATRICIA pliku danych, która odnosi się do pliku dla wartości mieszania i liczby całkowitej, to możesz zmniejszyć każdy element do wskaźników węzła (2 * 64 bity?), przesunięcia testu bitowego (1 bajt w tym scenariuszu) i przesunięcia plików (uint64_t, które mogą wymagać dopasowania do wielu funkcji fseek() s).

Answer 3

Czy ktoś wie, dlaczego proces staje się związany z dyskiem i jak go zatrzymać?

Wyszukiwanie binarne wymaga wielu poszukiwań w pliku. W przypadku, gdy cały plik nie mieści się w pamięci, pamięć podręczna strony nie obsługuje dużego wyszukiwania, co powoduje obserwowane zachowanie.

Najlepszym sposobem radzenia sobie z tym jest zmniejszenie/uniemożliwienie dużego wyszukiwania i sprawienie, aby pamięć podręczna strony działała prawidłowo.

Trzy pomysły na ciebie:

Jeśli można sortować strumień wejściowy, możesz przeglądać plik w kawałki, używając coś podobnego z następującym algorytmem:

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 
} 

---

Jeśli nie można sortować strumienia wejściowego, można ograniczyć poszukiwania dysku, budując indeks danych w pamięci. Przejść przez duży plik, i zrobić table które jest:

record_hash, offset into file where this record starts 

Nie przechowywać wszystkie rekordy w tabeli - Przechowywać tylko każdy rekord KTH. Wybierz duże K, ale wystarczająco małe, aby zmieściło się w pamięci.

Aby wyszukać duży plik dla danego skrótu docelowego, wykonaj wyszukiwanie binarne w tabeli w pamięci, aby znaleźć największy skrót w wartości table, który jest mniejszy niż wartość skrótu docelowego. Powiedzmy, że jest to table[h]. Następnie przejdź do segmentu zaczynającego się od table[h].offset i kończącego się na table[h+1].offset, i wykonaj ostateczne wyszukiwanie binarne. Spowoduje to radykalne zmniejszenie liczby poszukiwanych dysków.

Jeśli to nie wystarczy, można mieć wiele warstw indeksów:

record_hash, offset into index where the next index starts 

Oczywiście, trzeba wiedzieć z wyprzedzeniem, jak wiele warstw indeksie istnieją.

---

Wreszcie jeśli masz dodatkowe pieniądze dostępne zawsze można kupić więcej niż 23 GB pamięci RAM, a zrobić to na pamięci związanego problemu ponownie (po prostu spojrzał na stronie internetowej firmy Dell - odebrać nowy niski stacja robocza z 32 GB pamięci RAM za niespełna 1400 dolarów australijskich). Oczywiście, trochę czasu zajmie odczytanie dużej ilości danych z dysku, ale gdy już to nastąpi, zostaniesz ustawiony.

Answer 4

Zamiast mmap, należy rozważyć przy użyciu tylko zwykły stary lseek + read.Można zdefiniować kilka funkcji pomocniczych odczytać wartość skrótu lub jego odpowiednią liczbę całkowitą:

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; 
} 

potem po prostu zrobić swoje wyszukiwanie binarne, jak zwykle. Może być nieco wolniej, ale nie zacznie żuć swojej wirtualnej pamięci.

Answer 5

Nie znamy historii z przeszłości. Tak więc trudno jest udzielić ci ostatecznej porady. Ile masz pamięci? Jak wyrafinowany jest twój twardy dysk? Czy to jest projekt edukacyjny? Kto płaci za twój czas? 32 GB pamięci RAM nie wydaje się tak drogie w porównaniu do dwóch dni pracy osoby, która zarabia 50 $/h. Jak szybko to trzeba uruchomić? Jak daleko poza pole jesteś gotowy? Czy Twoje rozwiązanie wymaga użycia zaawansowanych koncepcji systemu operacyjnego? Czy jesteś żonaty z programem w C? Co powiesz na to, żeby Postgres sobie z tym poradził?

Oto alternatywa niskiego ryzyka. Ta opcja nie jest tak atrakcyjna intelektualnie jak inne sugestie, ale może dać ci znaczące korzyści. Oddziel plik na 3 porcje o pojemności 8 GB lub 6 porcji 4 GB (w zależności od posiadanych komputerów, musi wygodnie zmieścić się w pamięci). Na każdej maszynie uruchom to samo oprogramowanie, ale w pamięci i umieść w pobliżu jeden z wywołań RPC. Napisz wywołującego RPC do każdego z 3 lub 6 pracowników, aby określić liczbę całkowitą związaną z danym kodem skrótu.