Struktura na dysku do przechowywania dużego zestawu 128-bitowych liczb całkowitych?

Question

Mam około 500 milionów 128-bitowych liczb całkowitych, dodając około 100M na rok. Nic nie jest nigdy usunięte. Liczby mają jednolity rozkład, pod względem skali i czasu.

Zasadniczo wszystko, czego potrzebuję, to operacja dodawania, która również zwraca informację, czy liczba już istnieje w DB. Ponadto, nie chcę używać zbyt dużo pamięci RAM dla tego systemu, więc po prostu przechowywanie wszystkiego w pamięci nie jest tym, czego szukam.

Do tej pory używaliśmy kilku tabel MyISAM w MySQL, używając dwóch bigintów jako klucza podstawowego. To daje nam dobrą wydajność, ale podejrzewam, że nie jest to właściwe narzędzie do tej pracy. Przed rozdzieleniem tabel wystąpiły pewne problemy z wydajnością, a także mieliśmy zepsute przerwy w zasilaniu. Ponadto, DB daje nam znacznie więcej funkcji, których nie potrzebujemy.

Używam Pythona na Linuksie, ale jestem otwarty na sugestie.

Similar question in C++.

AKTUALIZACJA: Komentarz Marcelo wspomniał o Bloom Filter, co wydaje mi się bardzo obiecujące. Ponieważ pracuję z hashe, już zrezygnowałem z pełnej dokładności, więc może to być świetna kompromitacja precyzja/wydajność.

Answer 1

Każda wkładka całkowitą w jednej puli 2 ⁿ baz SQLite (2 jest dobrym liczba) wybrane przez wyliczania n bitowych mieszania liczbą całkowitą. Ustaw jedną kolumnę tabeli jako klucz podstawowy, aby próba wstawienia istniejącego numeru zakończyła się niepowodzeniem.

Zakładając, że liczby całkowite są już wystarczająco losowe, prawdopodobnie po prostu wybierzemy najmniej znaczący bajt jako "hash".

EDYCJA: Zrobiłem kilka testów. Wprowadziłem 25 milionów wpisów w ciągu około dwóch godzin, ale w tym czasie pochłonęło ponad 1 GB. Odbywa się to poprzez generowanie liczb losowych i rozprowadzanie ich do 32 podprocesów, z których każdy ma jedną bazę danych SQLite i kontroluje raz na 100 000 wkładów. Wstawki są obecnie chugowane na około 1350 Hz, daleko poza 3 Hz, twój problem wymaga, ale cała baza danych wciąż mieści się w pamięci podręcznej (mam 8 GB pamięci RAM). Nie będę znać wydajności w stanie ustalonym, dopóki nie zbliży się do obecnego rozmiaru bazy danych. W tym momencie każde wstawienie wywoła co najmniej cztery ruchy głowicy dysku (odczyt i zapis indeksu i tabeli, prawdopodobnie więcej, aby drążyć w drzewie B +), a wtedy dowiesz się, ile bólu naprawdę cię dotyka .

Zaczynam myśleć, że jest to naprawdę interesujący problem, który można rozwiązać znacznie skuteczniej dzięki niestandardowemu rozwiązaniu. Podejrzewam jednak, że podjęcie znacznego wysiłku, aby znacznie przewyższyć silnik bazy danych, wymaga sporo wysiłku.

Answer 2

Hash hasze?