Programowanie magazynu kluczy / wartości do nowoczesnego C ++

Tworzę serwer bazy danych podobny do Cassandry.

Prace rozwojowe rozpoczęto w C, ale bez zajęć zajęcia stały się bardzo skomplikowane.

Obecnie przenosiłem wszystko w C ++ 11, ale wciąż uczę się „nowoczesnego” C ++ i mam wątpliwości co do wielu rzeczy.

Baza danych będzie działać z parami klucz / wartość. Każda para ma więcej informacji - kiedy jest tworzona, także kiedy wygaśnie (0, jeśli nie wygasa). Każda para jest niezmienna.

Kluczem jest ciąg C, wartość jest nieważna *, ale przynajmniej w tej chwili działam również z wartością jako ciąg C.

Istnieją IListklasy abstrakcyjne . Jest dziedziczony z trzech klas

• VectorList - C dynamiczna tablica - podobna do std :: vector, ale wykorzystuje realloc
• LinkList - stworzony do kontroli i porównania wydajności
• SkipList - klasa, która w końcu zostanie użyta.

W przyszłości mógłbym również zrobić Red Blackdrzewo.

Każdy IListzawiera zero lub więcej wskaźników do par, posortowanych według klucza.

Jeśli IListstał się zbyt długi, można go zapisać na dysku w specjalnym pliku. Ten specjalny plik jest swego rodzaju read only list.

Jeśli musisz wyszukać klucz,

• Pierwsza pamięć IListjest przeszukiwana ( SkipList, SkipListi LinkList).
• Następnie wyszukiwanie jest wysyłane do plików posortowanych według daty
  (najnowszy plik pierwszy, najstarszy plik - ostatni).
  Wszystkie te pliki są mmap-edowane w pamięci.
• Jeśli nic nie znaleziono, klucz nie zostanie znaleziony.

Nie mam wątpliwości co do realizacji IListrzeczy.

To, co mnie obecnie zastanawia, to:

Pary są różnej wielkości, są przydzielane przez new()i std::shared_ptrwskazały na nie.

class Pair{
public:
    // several methods...
private:
    struct Blob;

    std::shared_ptr<const Blob> _blob;
};

struct Pair::Blob{
    uint64_t    created;
    uint32_t    expires;
    uint32_t    vallen;
    uint16_t    keylen;
    uint8_t     checksum;
    char        buffer[2];
};

Zmienna składowa „buforowa” jest zmienna o innym rozmiarze. Przechowuje klucz + wartość.
Np. Jeśli klucz ma 10 znaków, a wartość to kolejne 10 bajtów, cały obiekt będzie sizeof(Pair::Blob) + 20(bufor ma początkowy rozmiar 2, z powodu dwóch bajtów kończących wartość null)

Ten sam układ jest również używany na dysku, więc mogę zrobić coś takiego:

// get the blob
Pair::Blob *blob = (Pair::Blob *) & mmaped_array[pos];

// create the pair, true makes std::shared_ptr not to delete the memory,
// since it does not own it.
Pair p = Pair(blob, true);

// however if I want the Pair to own the memory,
// I can copy it, but this is slower operation.
Pair p2 = Pair(blob);

Jednak ten inny rozmiar jest problemem w wielu miejscach z kodem C ++.

Na przykład nie mogę użyć std::make_shared(). Jest to dla mnie ważne, ponieważ gdybym miał 1M pary, miałbym przydziały 2M.

Z drugiej strony, jeśli zrobię „buforowanie” dynamicznej tablicy (np. Nowy znak [123]), stracę „lewę” mmapa, zrobię dwie dereferencje, jeśli chcę sprawdzić klucz i dodam pojedynczy wskaźnik - 8 bajtów do klasy.

Próbowałem też do „pull” wszystkich członków z Pair::Blobpod Pair, więc Pair::Blobbędzie tylko bufor, ale gdy testowałem go, to był dość powolna, prawdopodobnie z powodu kopiowania danych obiektów wokół.

Inną zmianą, o której myślę, jest również usunięcie Pairklasy i zastąpienie jej std::shared_ptroraz „wypchnięcie” wszystkich metod z powrotem Pair::Blob, ale to nie pomoże mi w przypadku Pair::Blobklasy o zmiennej wielkości .

Zastanawiam się, jak mogę ulepszyć projektowanie obiektów, aby być bardziej przyjaznym dla C ++.

Pełny kod źródłowy znajduje się tutaj:
https://github.com/nmmmnu/HM3

Podejście, które zaleciłbym, to skupienie się na interfejsie sklepu z kluczowymi wartościami, aby uczynić go tak czystym, jak to możliwe i tak nieograniczającym, jak to możliwe, co oznacza, że ​​powinien on zapewniać maksymalną swobodę dzwoniącym, ale także maksymalną swobodę wyboru jak to wdrożyć.

Następnie zaleciłbym, aby zapewnić możliwie jak najmniejszą implementację, tak czystą, jak to możliwe, bez jakichkolwiek problemów z wydajnością. Wydaje mi się, że unordered_mappowinien to być twój pierwszy wybór, a może mapinterfejs może ujawnić jakieś uporządkowanie kluczy.

Najpierw spraw, by działał czysto i minimalnie; następnie użyj go w prawdziwej aplikacji; w ten sposób dowiesz się, jakie problemy musisz rozwiązać w interfejsie; następnie śmiało i zwróć się do nich. Większość szans jest taka, że ​​w wyniku zmiany interfejsu będziesz musiał przepisać duże części implementacji, więc za każdym razem, gdy już zainwestowałeś w pierwszą iterację implementacji, po przekroczeniu minimalnego czasu potrzebnego na jej wykonanie ledwo praca to strata czasu.

Następnie profiluj go i zobacz, co należy poprawić w implementacji, bez zmiany interfejsu. Lub możesz mieć własne pomysły na ulepszenie wdrożenia, zanim jeszcze profilujesz. To dobrze, ale nadal nie ma powodu, aby pracować nad tymi pomysłami w dowolnym momencie.

Mówisz, że masz nadzieję zrobić lepiej niż map; można o tym powiedzieć dwie rzeczy:

a) prawdopodobnie nie będziesz;

b) unikać przedwczesnej optymalizacji za wszelką cenę.

Jeśli chodzi o implementację, twoim głównym problemem wydaje się być przydział pamięci, ponieważ wydaje się, że martwisz się, jak ustrukturyzować swój projekt, aby obejść problemy, które przewidujesz, że będziesz miał w związku z przydziałem pamięci. Najlepszym sposobem rozwiązania problemów związanych z alokacją pamięci w C ++ jest wdrożenie odpowiedniego zarządzania alokacją pamięci, a nie skręcenie i zgięcie wokół nich projektu. Powinieneś uważać się za szczęściarza, że ​​korzystasz z C ++, który pozwala ci zarządzać przydziałem pamięci, w przeciwieństwie do języków takich jak Java i C #, w których nie możesz się doczekać, co oferuje środowisko językowe.

Istnieją różne sposoby zarządzania pamięcią w C ++, a newprzydaje się możliwość przeciążenia operatora. Uproszczony alokator pamięci dla twojego projektu wstępnie przydzieli ogromną tablicę bajtów i użyje go jako sterty. ( byte* heap.) Miałbyś firstFreeByteindeks zainicjowany na zero, który wskazuje pierwszy wolny bajt w stercie. Kiedy pojawi się żądanie Nbajtów, zwracasz adres heap + firstFreeBytei dodajesz Ndo firstFreeByte. Przydział pamięci staje się tak szybki i wydajny, że praktycznie nie stanowi problemu.

Oczywiście wstępne przydzielenie całej pamięci może nie być dobrym pomysłem, więc może być konieczne podzielenie sterty na banki, które są przydzielane na żądanie, i nadal obsługują żądania alokacji z najnowszego banku w dowolnym momencie.

Ponieważ twoje dane są niezmienne, jest to dobre rozwiązanie. Pozwala zrezygnować z idei obiektów o zmiennej długości i sprawić, by każdy Pairzawierał wskaźnik do swoich danych tak, jak powinien, ponieważ dodatkowy przydział pamięci na dane praktycznie nic nie kosztuje.

Jeśli chcesz mieć możliwość odrzucania obiektów ze stosu, aby móc odzyskać ich pamięć, wówczas sprawy stają się bardziej skomplikowane: będziesz musiał używać nie wskaźników, ale wskaźników do wskaźników, aby zawsze można było przenosić obiekty wokół hałd, aby odzyskać przestrzeń usuniętych obiektów. Wszystko staje się nieco wolniejsze z powodu dodatkowej pośredniczości, ale wszystko jest błyskawicznie szybkie w porównaniu do korzystania ze standardowych procedur alokacji pamięci biblioteki wykonawczej.

Ale wszystko to jest oczywiście bezużyteczne, jeśli nie zbudujesz prostej, nieskomplikowanej, działającej wersji bazy danych i nie wykorzystasz jej w prawdziwej aplikacji.