Dobra struktura danych migawkowych dla indeksu w pamięci

12

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.

dm3
źródło
1
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
2
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:

5

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(logn)

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
1

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