Dobra struktura danych migawkowych dla indeksu w pamięci

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.

data-structures concurrency databases

— dm3
źródło

Czy potrzebujesz migawek w pamięci, czy chcesz zapisać je na dysku / sieci? Czysto funkcjonalna struktura danych automatycznie zapewnia migawki w pamięci, więc jeśli tego potrzebujesz, to najlepiej.

— Gilles „SO- przestań być zły”

Wszystko jest w pamięci. Zastanawiałem się, czy może istnieje skuteczna, modyfikowalna wersja z migawką o stałym czasie (jak CTrie, tylko bez równoczesnego zapisu).

— dm3

Problemem może być mniej wybór struktury danych, ale rodzaj kontroli współbieżności.

— Raphael

Może być, czy mógłbyś rozwinąć to nieco więcej?

— dm3

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:

Przez niezmienne, wszelkie aktualizacje / usunięcia pułapki zwrócą nową pułapkę, która może współdzielić węzły wewnętrzne z poprzednią pułapką. Wszystkie węzły w tej implementacji są tylko do odczytu po ich utworzeniu. Pozwala to współbieżnym czytnikom na bezpieczną obsługę współbieżnych programów piszących, ponieważ modyfikacje tworzą tylko nowe struktury danych i nigdy nie modyfikują istniejących struktur danych. Jest to proste podejście do uzyskania kontroli MVCC lub kontroli współbieżności wielu wersji.

$O(\log n)$

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:

lock
tmp = ptr_to_root
unlock
value = search(tmp, <value to search for>)
return value

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:

lock
old_ptr_to_root = ptr_to_root
ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
unlock

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:

top:
  lock
  old_ptr_to_root = ptr_to_root
  unlock
  new_ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
  lock
  if (ptr_to_root == old_ptr_to_root)   # make sure no other write happened in the interim
    ptr_to_root = new_ptr_to_root
    unlock
  else                                  # transaction fails, try again
    unlock
    goto top

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*>).

— Wędrująca logika
źródło

Dziękuję za wyszukaną odpowiedź. W pewnym sensie wiedziałem, że może nie postawiłem tego wystarczająco jasno w samym pytaniu. Jednak odpowiedź jest nadal świetna!

— dm3

Twoja „ulepszona” wersja zależy od modelu pamięci używanego systemu. Może być potrzebna weryfikacja zmienności w niektórych systemach i potrzeba wielkich umiejętności, aby poprawnie kodować.

— Ian Ringrose

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:

Justin Levandoski, David Lomet i Sudipta Sengupta, The Bw-Tree: A B-tree for New Hardware, in 2013 IEEE 29th International Conference on Data Engineering (ICDE), International Conference on Data Engineering, 8 kwietnia 2013.

Zobacz http://research.microsoft.com/en-us/projects/main-memory_dbs/, aby uzyskać listę ich publikacji.

— Ian Ringrose
źródło