Dużo stringów w pamięci

0

Witam, posiadam plik ważący około 3/4GB zawierający dużą listę adresów publicznych proxy. Potrzebuję napisać system, który weryfikowałby czy adres użytkownika łączącego się z moim serwisem jest w środku tego pliku. Czy gdybym po prostu załadował to do pamięci i wywoływał contains to wszystko byłoby okej? Na maszynie mam 16GB ramu, ale nie wiem czy to wystarczające. Chciałbym zrobić to jak najmniejszym kosztem tzn bez stawiania zadnej bazy danych oraz żeby sprawdzanie czy adres to proxy trwalo dosc szybko (max 1 sekunde?).

2

Wrzuć te adresy do bazy danych (np. MySQL H2 / SQLite), załóż indeks i wsio - baza już sobie ogra storage, RAM, cache itd.

2
Patryk27 napisał(a):

Wrzuć te adresy do bazy danych (np. MySQL / SQLite), załóż indeks i wsio - baza już sobie ogra storage, RAM, cache itd.

Jak Java to H2 / Derby.

jest pewna ilość bardzo lekkich (m.in. bez silnika interpretacji kwerend) bibliotek, często implementujących Map w oparciu o storage. Można sobie po nich obiecywac dużo w minimalistycznych konfiguracjach
Moja dobre doświadczenia z tym nie są już zbyt aktualne, sam poszukaj co na rynku fruwa: java file persistent key value

0
AnyKtokolwiek napisał(a):
Patryk27 napisał(a):

Wrzuć te adresy do bazy danych (np. MySQL / SQLite), załóż indeks i wsio - baza już sobie ogra storage, RAM, cache itd.

Jak Java to H2 / Derby.

Tutaj warto dodać że H2 i Derby (oraz SQLite) mogą działać w trybie embedded bez zewnętrznego serwera (Dla SQLite jest to jedyny możliwy tryb) . Dodaje się tylko bibliotekę do projektu a podczas działania aplikacji jest tworzony conajmniej jeden plik w którym trzymane są dane

0

Można to zrobić efektywnie, z użyciem Files.lines(..):

Path path = Paths.get(this.getClass().getResource("/test.txt").toURI());
List<String> foundAddresses = Files.lines(path)
                                  .filter(line -> line.contains("address to find"))
                                  .collect(Collectors.toList());
2

Generalnie używanie do tego bazy danych - przy podanych warunkach to raczej niepotrzebna zabawa. Nudne odtwarzanie korpostandardów pisania kodu.
Jeśli adresy to ip to wrzuć je w tablice bajtów i tak trzymaj w pamięci np. w hashset.
Możesz te adresy wrzucić w drzewo.
Jeśli w postaci nazw domen to wykorzystaj String.intern i raczej dużo w tych 16mb zmieścisz. (ale to raczej dziwna koncepcja).

0

To może zaangażuj jakieś przetwarzanie batchowe - Spring batch, Spark :D

0
wesolyludek napisał(a):

Witam, posiadam plik ważący około 3/4GB zawierający dużą listę adresów publicznych proxy. Potrzebuję napisać system, który weryfikowałby czy adres użytkownika łączącego się z moim serwisem jest w środku tego pliku. Czy gdybym po prostu załadował to do pamięci i wywoływał contains to wszystko byłoby okej? Na maszynie mam 16GB ramu, ale nie wiem czy to wystarczające. Chciałbym zrobić to jak najmniejszym kosztem tzn bez stawiania zadnej bazy danych oraz żeby sprawdzanie czy adres to proxy trwalo dosc szybko (max 1 sekunde?).

Jeśli objętość ruchu definiowana jako: (średnia liczba żądań x koszt pamięciowy obsługi żądania) nie jest zbyt duży to wczytaj to po prostu do pamięci (HashSet/TreeSet).
Problem zaczyna się gdy twoja apka robi coś ciężkiego. Wtedy chyba najlepszym sposobem będzie wyciągnięcie filtrowania do osobnego proxy.

W ekstremalnym przypadku możesz zrobić swoją optymalizację, tzn. podzielić ten jeden plik na mniejsze z konwencją nazw (np. plik "192.list" zawiera wszystkie IP z grupy 192.*), dorzucić limitowany cache i trzymać to. Przy czym zaznaczam, że to jest ekstremalny przypadek.

1

Zakładając, że adresy są w formie IPv4, to:

  • każdy adres można zamienić na uint32
  • można użyć bitsetu do trzymania listy wszystkich adresów - bit na pozycji N oznacza, że adres IPv4 o reprezentacji liczbowej N jest na liście, sprawdzenie adresu jest super szybkie
  • klasyczny bitset będzie wymagał 2^32 bitów = 512MB więc całkiem spoko
  • jeśli jednak szkoda pamięci to można spróbować innych implementacji bitsetu, np. takich które kompresują długie sekwencje 0 i 1 za pomocą RLE
1

Możesz załadować to do hashseta i robić .contains() ale 4GB to trochę zajmie. Przypuszczam że prościej będzie użyć do tego grepa zamiast pisać aplikacje w javie.

0

Zakładając, że nie potrzebujesz posiadać samych adresów, a jedynie wiedzę o tym, czy dowolny adres należy do ustalonego zbioru, możesz rozważyć wykorzystanie OBDD.
Ta struktura z łatwością przechowuje informacje o zbiorach o gigantycznym rozmiarze (10^100 elementów to pestka) w stosunkowo niewielkiej pamięci.
Czas wyszukiwania jest liniowy (zakładając górne ograniczenie możliwej długości adresu).
Kluczowe tu jest pominięcie przechowywania samych wartości, a jedynie przechowywanie informacji o przynależności.

0
ll -h proxy.txt 
-rw-rw-r-- 1 p p 1,4G Jul  1 17:01 proxy.txt
test$ tail proxy.txt 
IBAOBTKVFLAwBoMOPYvcj2yCn1VgD69xPwLVoprUZf77MuXcnxDeGqABmksNGclK
OhKlpHOo3jla/Q2hJwu+EKsRNAFC/0KL3PT9kIBLcb1cVdPehCZT/9omvJI0szD6
vnxnOTyvqCEg9mXsJdSENk9/LRIAAl40FDzLsA1VdiESp6czk0CSsN76sfgycYNd
jyosTHSi2k3XNYA9Nn37gmMUZasO3azSv77xPWNBww0IPm+hL+FHpNgSgwndDxn3
yN2L5QPoESBqwnig0aVjcxLO1aXcOUmR98GXazzz1x14zyAwInDJhdJvnbJPrjyH
vuqXm1g+fIDPFHXP2AckWNl5+C5OruGlwz2zUqP7ZLBU7RJPREKLxtz4RWiH1wue
NqmWr3vXfVZc0l+n4zLpDlaVeAdXMj5CKkPkQltYuoeoEXI0/K/J9kaRlNzkV8oP
WJ+qsCnFPD5Q+2MNX4q6+W4CLI+uWX3GSEuedJgRBu8fagngVq5dT0vU9jtw+aGz
Jp/dCY/a+NMGA5HNuaNs84sJeArGloxieTx/DJb1Yqw5UIXSlp9qmkliXRrBbQOx
7L6VePIb5sIbUIHI3iT6Uw==

screenshot-20200701171644.png

A próbowałeś tak zwyczanie sprawdzić najprostsze rozwiązanie - wrzucić wszystko do pamięci i już?

0

Tu sie az prosi zrobic jakies drzewko.
Moze Trie?

https://www.geeksforgeeks.org/trie-insert-and-search/

Hashmapa/hasharray bedzie miala pewien narzut pamieciowy.

1

Przeorganizowałem tego posta od pomysłów najprostszych do najbardziej złożonych:

  1. A gdybyś porównywał hashcode’y? Wtedy inty (hashe) może zmieszczą się w pamięci. W pamięci trzymasz probabilistyczną strukturę danych (filtr Blooma), która na 100% odpowiada czy stringa nie ma w pliku, wpp. trzeba iść do pliku i sprawdzić (struktura się myli - false positive).
  2. Ewentualnie drzewo TRIE wspomniane wcześniej albo jakaś metoda kompresji. Nic nie przebije wczytania wszystkiego do pamięci.
  3. gdyby duży plik był posortowany, to mógłbyś w pamięci trzymać coś a la indeks i iść do dysku po określony fragment.
0

A czy trzeba te adresy trzymać w jednym pliku? Jakby podzielić plik na mniejsze kierując się pierwszym bajtem adresu, to miałbyś maksymalnie 256 plików, czyli każdy miałby średnio 16 MB, jeśli to za dużo to drugi bajt można podzielić na cztery lub osiem partycji. Wtedy pierwszy bajt jest nazwą pliku, wczytujesz i szukasz czy są pozostałe 3 bajty. Wczytanie i przeszukanie kilkunastu MB daje około 1s.

1 użytkowników online, w tym zalogowanych: 0, gości: 1