Skuteczne metody przechowywania dziesiątek milionów obiektów do wyszukiwania, z dużą liczbą wstawek na sekundę?

15

Jest to w zasadzie aplikacja do rejestrowania / zliczania, która zlicza liczbę pakietów i typ pakietu itp. W sieci czatu p2p. Odpowiada to około 4-6 milionom pakietów w ciągu 5 minut. A ponieważ robię tylko „migawkę” tych informacji, usuwam tylko pakiety starsze niż 5 minut co pięć minut. Zatem maksymalna liczba przedmiotów, które będą w tej kolekcji, wynosi od 10 do 12 milionów.

Ponieważ muszę nawiązać 300 połączeń z różnymi supereperami, istnieje możliwość, że każdy pakiet próbuje wstawić co najmniej 300 razy (prawdopodobnie dlatego właśnie zatrzymywanie tych danych w pamięci jest jedyną rozsądną opcją).

Obecnie używam Słownika do przechowywania tych informacji. Ale z powodu dużej ilości przedmiotów, które próbuję przechowywać, mam problemy ze stertą dużych obiektów, a ilość pamięci stale rośnie z czasem.

Dictionary<ulong, Packet>

public class Packet
{
    public ushort RequesterPort;
    public bool IsSearch;
    public string SearchText;
    public bool Flagged;
    public byte PacketType;
    public DateTime TimeStamp;
}

Próbowałem użyć mysql, ale nie był w stanie nadążyć za ilością danych, które muszę wstawić (sprawdzając, czy nie jest to duplikat), i to było podczas korzystania z transakcji.

Próbowałem mongodb, ale użycie procesora do tego celu było szalone i też tego nie utrzymałem.

Mój główny problem pojawia się co 5 minut, ponieważ usuwam wszystkie pakiety starsze niż 5 minut i robię „migawkę” tych danych. Ponieważ używam zapytań LINQ do zliczenia liczby pakietów zawierających określony typ pakietu. Wywołuję także odrębne () zapytanie dotyczące danych, w którym usuwam 4 bajty (adres IP) z klucza keyvaluepair i łączę go z wartością port-żądania w wartości klucza-wartości i używam tego, aby uzyskać odrębną liczbę rówieśnicy ze wszystkich pakietów.

Aplikacja oscyluje obecnie wokół 1,1 GB pamięci, a gdy wywoływana jest migawka, może sięgać nawet dwukrotnie.

Teraz nie byłoby problemu, gdybym miał szaloną ilość pamięci RAM, ale vm, na którym mam to działa, jest obecnie ograniczony do 2 GB pamięci RAM.

Czy jest jakieś łatwe rozwiązanie?

Josh
źródło
To bardzo wymagający scenariusz, a do tego używasz VM do uruchamiania aplikacji, wow. W każdym razie, czy odkryłeś memcached do przechowywania pakietów. Zasadniczo możesz uruchomić memcached na osobnej maszynie, a aplikacja może nadal działać na samej maszynie wirtualnej.
Ponieważ wypróbowałeś już zarówno MySQL, jak i MongoDB, może się wydawać, że wymagania twojej aplikacji (jeśli chcesz to zrobić dobrze) dyktują, że potrzebujesz po prostu większej mocy. Jeśli Twoja aplikacja jest dla Ciebie ważna, rozbuduj serwer. Możesz także ponownie sprawdzić kod „przeczyszczający”. Jestem pewien, że możesz znaleźć bardziej zoptymalizowany sposób radzenia sobie z tym, o ile nie sprawi to, że Twoja aplikacja będzie bezużyteczna.
Matt Beckman,
4
Co mówi ci twój profiler?
jasonk
Nie dostaniesz nic szybciej niż lokalna kupa. Moją propozycją byłoby ręczne wywołanie odśmiecania po czyszczeniu.
vartec
@vartec - w rzeczywistości, wbrew powszechnemu przekonaniu, ręczne wywoływanie modułu wyrzucania śmieci nie gwarantuje w rzeczywistości natychmiastowego, dobrze ... wyrzucania elementów bezużytecznych. GC może odroczyć akcję na późniejszy okres zgodnie z własnym algorytmem gc. Wywoływanie go co 5 minut może nawet zwiększyć obciążenie, zamiast go złagodzić. Tylko mówię;)
Jas

Odpowiedzi:

12

Zamiast posiadania jednego słownika i przeszukiwania tego słownika w poszukiwaniu wpisów, które są zbyt stare; mieć 10 słowników. Co około 30 sekund utwórz nowy „aktualny” słownik i odrzuć najstarszy słownik bez wyszukiwania.

Następnie, gdy odrzucasz najstarszy słownik, umieść wszystkie stare obiekty w kolejce FILO na później i zamiast używać „nowego” do tworzenia nowych obiektów, ściągnij stary obiekt z kolejki FILO i użyj metody rekonstrukcji starego obiekt (chyba że kolejka starych obiektów jest pusta). Dzięki temu można uniknąć wielu przydziałów i dużego obciążenia związanego z odśmiecaniem.

Brendan
źródło
1
Partycjonowanie według przedziału czasu! Właśnie to zamierzałem zasugerować.
James Anderson
Problem polega na tym, że musiałbym wykonać zapytanie do wszystkich tych słowników, które zostały utworzone w ciągu ostatnich pięciu minut. Ponieważ jest 300 połączeń, ten sam pakiet dotrze do każdego co najmniej raz. Aby więc nie obsługiwać tego samego pakietu więcej niż raz, muszę je przechowywać przez co najmniej 5 minut.
Josh
1
Problem z ogólnymi strukturami polega na tym, że nie są one dostosowane do określonego celu. Być może powinieneś dodać pole „nextItemForHash” i pole „nextItemForTimeBucket” do struktury pakietu i zaimplementować własną tabelę skrótów i przestać używać Dictionary. W ten sposób możesz szybko znaleźć wszystkie pakiety, które są zbyt stare i wyszukiwać tylko raz, gdy pakiet jest włożony (tj. Weź ciasto i je też). Pomogłoby to również w narzuceniu zarządzania pamięcią (ponieważ „Słownik” nie przypisywałby / zwalniał dodatkowych struktur danych do zarządzania słownikiem).
Brendan
@Josh najszybszym sposobem ustalenia, czy coś już widziałeś, jest skrótem . Czasowe zestawy skrótów byłyby szybkie i nadal nie trzeba szukać, aby eksmitować stare przedmioty. Jeśli nie widziałeś go wcześniej, możesz zapisać go w swoim słowniku (t / ach).
Podstawowy
3

Pierwszą myślą, która przychodzi mi na myśl, jest to, dlaczego czekasz 5 minut. Czy mógłbyś częściej robić migawki, a tym samym zmniejszyć duże przeciążenie widoczne na granicy 5 minut?

Po drugie, LINQ świetnie nadaje się do zwięzłego kodu, ale w rzeczywistości LINQ jest cukrem syntaktycznym na „zwykłym” C # i nie ma gwarancji, że wygeneruje najbardziej optymalny kod. Jako ćwiczenie możesz spróbować przepisać gorące punkty bez LINQ, możesz nie poprawić wydajności, ale będziesz miał bardziej przejrzysty pomysł na to, co robisz i ułatwi to profilowanie.

Kolejną rzeczą, na którą należy spojrzeć, są struktury danych. Nie wiem, co robisz ze swoimi danymi, ale czy możesz w jakikolwiek sposób uprościć dane, które przechowujesz? Czy możesz użyć tablicy ciągów lub bajtów, a następnie wyodrębnić odpowiednie części z tych elementów, gdy są potrzebne? Czy możesz użyć struktury zamiast klasy, a nawet zrobić coś złego z stackalloc, aby odłożyć pamięć i uniknąć uruchamiania GC?

Steve
źródło
1
Nie używaj tablicy łańcuchowej / bajtowej, użyj czegoś takiego jak BitArray: msdn.microsoft.com/en-us/library/…, aby uniknąć konieczności ręcznego zmieniania bitów. W przeciwnym razie jest to dobra odpowiedź, nie ma tak naprawdę łatwej opcji poza lepszymi algorytmami, większym sprzętem lub lepszym sprzętem.
Ed James
1
Pięć minut wynika z faktu, że 300 połączeń może otrzymać ten sam pakiet. Muszę więc śledzić to, co już obsłużyłem, a 5 minut to czas, w którym pakiety w pełni propagują się do wszystkich węzłów w tej konkretnej sieci.
Josh
3

Proste podejście: spróbuj memcached .

  • Jest zoptymalizowany do uruchamiania takich zadań.
  • Może ponownie wykorzystać wolną pamięć na mniej obciążonych urządzeniach, nie tylko na dedykowanym urządzeniu.
  • Ma wbudowany mechanizm wygasania pamięci podręcznej, który jest leniwy, więc nie ma czkawek.

Minusem jest to, że jest oparty na pamięci i nie ma żadnej trwałości. Jeśli instancja nie działa, dane znikają. Jeśli potrzebujesz wytrwałości, serializuj dane samodzielnie.

Bardziej złożone podejście: wypróbuj Redis .

Minusem jest to, że jest nieco bardziej skomplikowana.

9000
źródło
1
Memcached można podzielić na różne maszyny, aby zwiększyć ilość dostępnego pamięci RAM. Możesz mieć drugi serwer serializujący dane do systemu plików, aby nie stracić rzeczy, jeśli spadnie pole memcache. Interfejs API Memcache jest bardzo prosty w obsłudze i działa z dowolnego języka, dzięki czemu można używać różnych stosów w różnych miejscach.
Michael Shopsin
1

Nie musisz przechowywać wszystkich pakietów dla wspomnianych zapytań. Na przykład - licznik rodzaju pakietu:

Potrzebujesz dwóch tablic:

int[] packageCounters = new int[NumberOfTotalTypes];
int[,] counterDifferencePerMinute = new int[6, NumberOfTotalTypes];

Pierwsza tablica śledzi liczbę pakietów w różnych typach. Druga tablica śledzi liczbę kolejnych pakietów dodawanych w każdej minucie, dzięki czemu wiesz, ile pakietów należy usunąć w każdej minucie. Mam nadzieję, że możesz powiedzieć, że druga tablica jest używana jako okrągła kolejka FIFO.

Tak więc dla każdego pakietu wykonywane są następujące operacje:

packageCounters[packageType] += 1;
counterDifferencePerMinute[current, packageType] += 1;
if (oneMinutePassed) {
  current = (current + 1) % 6;
  for (int i = 0; i < NumberOfTotalTypes; i++) {
    packageCounters[i] -= counterDifferencePerMinute[current, i];
    counterDifferencePerMinute[current, i] = 0;
}

W dowolnym momencie liczniki pakietów mogą być natychmiast odczytane przez indeks i nie przechowujemy wszystkich pakietów.

Codism
źródło
Głównym powodem, dla którego muszę przechowywać dane, które robię, jest fakt, że te 300 połączeń może otrzymać ten sam dokładny pakiet. Muszę więc zatrzymać każdy widziany pakiet przez co najmniej pięć minut, aby upewnić się, że nie będę go obsługiwał / liczył więcej niż raz. Do tego właśnie służy długi klucz słownika.
Josh
1

(Wiem, że to stare pytanie, ale natknąłem się na nie, szukając rozwiązania podobnego problemu, w którym przechodzenie do śmiecia drugiej generacji wstrzymywało aplikację na kilka sekund, więc nagrywanie dla innych osób w podobnej sytuacji).

Używaj struktury zamiast klasy dla swoich danych (pamiętaj jednak, że jest ona traktowana jako wartość z semantyką pass-by-copy). To eliminuje jeden poziom przeszukiwania, który musi wykonać każdy gc.

Użyj tablic (jeśli znasz rozmiar danych, które przechowujesz) lub Listy - która używa tablic wewnętrznie. Jeśli naprawdę potrzebujesz szybkiego dostępu losowego, skorzystaj ze słownika indeksów tablicowych. To usuwa kolejne kilka poziomów (lub kilkanaście lub więcej, jeśli używasz SortedDictionary), aby gc musiał wyszukiwać.

W zależności od tego, co robisz, wyszukiwanie listy struktur może być szybsze niż wyszukiwanie w słowniku (ze względu na lokalizację pamięci) - profil dla konkretnej aplikacji.

Kombinacja struct i lista znacznie zmniejsza zarówno użycie pamięci, jak i rozmiar czyszczenia modułu czyszczącego.

Malcolm
źródło
Mam niedawny eksperyment, który tak szybko generuje kolekcje i słowniki na dysku, używając sqlite github.com/modma/PersistenceCollections
ModMa