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ą IList
klasy abstrakcyjne . Jest dziedziczony z trzech klas
VectorList
- C dynamiczna tablica - podobna do std :: vector, ale wykorzystujerealloc
LinkList
- stworzony do kontroli i porównania wydajnościSkipList
- klasa, która w końcu zostanie użyta.
W przyszłości mógłbym również zrobić Red Black
drzewo.
Każdy IList
zawiera zero lub więcej wskaźników do par, posortowanych według klucza.
Jeśli IList
stał 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ęć
IList
jest przeszukiwana (SkipList
,SkipList
iLinkList
). - 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 IList
rzeczy.
To, co mnie obecnie zastanawia, to:
Pary są różnej wielkości, są przydzielane przez new()
i std::shared_ptr
wskazał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::Blob
pod Pair
, więc Pair::Blob
bę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 Pair
klasy i zastąpienie jej std::shared_ptr
oraz „wypchnięcie” wszystkich metod z powrotem Pair::Blob
, ale to nie pomoże mi w przypadku Pair::Blob
klasy 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
źródło
std::map
lubstd::unordered_map
? Dlaczego wartości (powiązane z kluczami) są niektórevoid*
? Prawdopodobnie w pewnym momencie będziesz musiał je zniszczyć; jak kiedy? Dlaczego nie używasz szablonów?IList::remove
lub gdy IList jest zniszczony. To zajmuje dużo czasu, ale zrobię to w osobnym wątku. Będzie to łatwe, ponieważ IList istd::unique_ptr<IList>
tak będzie . więc będę mógł „przełączyć” go z nową listą i zatrzymać stary obiekt w miejscu, w którym będę mógł wywołać d-tor.C string
a dane to zawsze buforvoid *
lubchar *
, więc można przekazać tablicę znaków. Możesz znaleźć podobne wredis
lubmemcached
. W pewnym momencie mogłem zdecydować się na użyciestd::string
lub naprawienie tablicy znaków dla klucza, ale podkreślę, że nadal będzie to ciąg C.Odpowiedzi:
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_map
powinien to być twój pierwszy wybór, a możemap
interfejs 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
new
przydaje 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śfirstFreeByte
indeks zainicjowany na zero, który wskazuje pierwszy wolny bajt w stercie. Kiedy pojawi się żądanieN
bajtów, zwracasz adresheap + firstFreeByte
i dodajeszN
dofirstFreeByte
. 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
Pair
zawierał 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.
źródło