Projektuję bazę danych obiektów w pamięci dla bardzo konkretnego przypadku użycia. Jest to pojedynczy program piszący, ale musi obsługiwać wydajne jednoczesne odczyty. Odczyty muszą być izolowane. Nie ma języka zapytań, baza danych obsługuje tylko:
- pobierz obiekt / -y przez atrybut / zestaw atrybutów (może istnieć obsługa wyrażeń, np.
x.count < 5
) - pobierz atrybut obiektu
Zapytanie jest skryptem imperatywnym złożonym z dowolnej liczby powyższych operacji. Rozmiar danych będzie wynosił << pamięć, więc wszystkie obiekty i indeksy większości atrybutów powinny pasować wygodnie bez zamiany.
Potrzebuję struktury danych dla indeksu atrybutów obiektu, którym może być O (n) przy zapisie, nie obsługuje współbieżności zapisu, ale najlepiej powinien obsługiwać migawki O (1) (być może kopiowanie przy zapisie) i dostęp O (logN). Idealnie byłoby to pozwolić na wysoką współbieżność odczytów przy maksymalnym współdzieleniu strukturalnym między wersjami.
Patrzyłem na CTries , Concurrent BST i Concurrent Splay Trees, ale nie jestem pewien, czy naprawdę patrzę tutaj w dobrym kierunku. Powyższe struktury przywiązują dużą wagę do złożoności wstawek, na których mi nie zależy.
Pytanie : czy istnieje znana struktura danych, która dobrze pasuje do mojego przypadku użycia od razu po wyjęciu z pudełka?
EDYCJA : po przemyśleniu wydaje się, że trwałe drzewo BST / Splay będzie działać. Pisarz zaktualizowałby kopię „wzorcową”, a zapytania pobierałyby drzewo na początku wykonywania i wyrzucały je po ich zakończeniu. Jednak nadal jestem zainteresowany, czy istnieje lepsze rozwiązanie.
Odpowiedzi:
Użyj dowolnej trwałej / niezmiennej (tj. Funkcjonalnej) struktury danych opartej na drzewie. Kluczem jest prawidłowe zablokowanie, jak zauważył @Raphael w komentarzach.
Zaletą funkcjonalnych / trwałych struktur danych opartych na drzewach jest to, że otrzymujesz „migawki” za darmo. Załóżmy, że używasz pułapki (losowego drzewa wyszukiwania binarnego) do struktury danych. Oto przykład jednego napisanego w Go: https://github.com/steveyen/gtreap . Autor opisuje to w ten sposób:
Blokada służy do ochrony wskaźnika do katalogu głównego. Ponieważ struktura danych jest niezmienna, odczyty mogą być wykonywane jednocześnie i można zapisywać wskaźniki do starych migawek. Odczyt to:
Mimo że wyszukiwanie może chwilę potrwać, blokada jest przytrzymywana tylko podczas kopiowania wskaźnika, więc wyszukiwanie może odbywać się jednocześnie.
Zapis to:
W tej wersji zapisy muszą przytrzymywać blokadę podczas całego procesu tworzenia nowej wersji drzewa. Możesz poprawić wydajność odczytu (kosztem czasami niepowodzenia transakcji zapisu), zmieniając zapis na coś takiego:
Możesz być w stanie zrobić nawet nieco lepiej (uczynić go „wolnym od blokady”), jeśli twój język programowania ma zmienne atomowe z atomową operacją porównywania i zamiany. (Na przykład za pomocą C ++ 11
atomic<T*>
).źródło
Microsoft opublikował szczegółowe informacje na temat swojej nowej bazy danych pamięci, ma indeksy, które nie blokują odczytów podczas zapisywania.
Na przykład:
Zobacz http://research.microsoft.com/en-us/projects/main-memory_dbs/, aby uzyskać listę ich publikacji.
źródło