Jak bazy danych przechowują wartości kluczy indeksu (na dysku) dla pól o zmiennej długości?


16

Kontekst

To pytanie dotyczy szczegółów implementacji indeksów niskiego poziomu w systemach baz danych SQL i NoSQL. Rzeczywista struktura indeksu (drzewo B +, skrót, SSTable itp.) Jest nieistotna, ponieważ pytanie dotyczy konkretnie kluczy przechowywanych w jednym węźle dowolnej z tych implementacji.

tło

W bazach danych SQL (np. MySQL) i NoSQL (CouchDB, MongoDB itp.), Gdy budujesz indeks na polu danych kolumny lub dokumentu JSON, tak naprawdę powoduje to, że baza danych tworzy zasadniczo posortowaną listę wszystkich wartości te wraz z przesunięciem pliku do głównego pliku danych, w którym znajduje się rekord dotyczący tej wartości.

(Dla uproszczenia mogę ręcznie wymachiwać innymi ezoterycznymi szczegółami konkretnych implantów)

Prosty klasyczny przykład SQL

Rozważmy standardową tabelę SQL z prostym 32-bitowym kluczem podstawowym int, na którym tworzymy indeks, skończymy z indeksem na dysku kluczy całkowitych posortowanych i skojarzonych z 64-bitowym przesunięciem do pliku danych, w którym płyta żyje, np .:

id   | offset
--------------
1    | 1375
2    | 1413
3    | 1786

Przedstawienie na dysku kluczy w indeksie wygląda mniej więcej tak:

[4-bytes][8-bytes] --> 12 bytes for each indexed value

Trzymając się podstawowych zasad optymalizacji optymalizacji I / O dysku za pomocą systemów plików i systemów baz danych, załóżmy, że przechowujesz klucze w blokach 4KB na dysku, co oznacza:

4096 bytes / 12 bytes per key = 341 keys per block

Ignorując ogólną strukturę indeksu (B + drzewo, skrót, posortowana lista itp.), Odczytujemy i zapisujemy bloki 341 kluczy naraz w pamięci i w razie potrzeby z powrotem zapisujemy na dysk.

Przykładowe zapytanie

Korzystając z informacji z poprzedniej sekcji, powiedzmy, że pojawia się zapytanie o „id = 2”, klasyczne wyszukiwanie indeksu DB wygląda następująco:

  1. Przeczytaj katalog główny indeksu (w tym przypadku 1 blok)
  2. Przeszukaj binarnie posortowany blok, aby znaleźć klucz
  3. Uzyskaj przesunięcie pliku danych od wartości
  4. Wyszukaj rekord w pliku danych, używając przesunięcia
  5. Zwróć dane dzwoniącemu

Konfiguracja pytania ...

Ok, tutaj pojawia się pytanie ...

Krok # 2 jest najważniejszą częścią, która pozwala na wykonanie tych zapytań w czasie O (logowania) ... informacje muszą być posortowane, ALE musisz być w stanie przeglądać listę w szybki sposób ... więcej w szczególności musisz być w stanie przeskoczyć do dobrze zdefiniowanych przesunięć do woli, aby odczytać wartość klucza indeksu w tej pozycji.

Po przeczytaniu w bloku musisz być w stanie natychmiast skoczyć na 170. pozycję, przeczytać kluczową wartość i zobaczyć, czy to, czego szukasz, to GT lub LT tej pozycji (i tak dalej itd.)

Jedynym sposobem, w jaki możesz przeskakiwać dane w bloku w ten sposób, jest to, że wszystkie wielkości wartości klucza są dobrze zdefiniowane, tak jak w naszym przykładzie powyżej (4 bajty, a następnie 8 bajtów na klucz).

PYTANIE

Ok, więc tutaj utknąłem z wydajnym projektowaniem indeksów ... dla kolumn varchar w bazach SQL, a dokładniej, całkowicie dowolnych pól w bazach dokumentów takich jak CouchDB lub NoSQL, gdzie dowolne pole, które chcesz indeksować, może być dowolne długość w jaki sposób wdrażasz kluczowe wartości, które są wewnątrz bloków struktury indeksu, z których budujesz swoje indeksy?

Załóżmy na przykład, że używasz sekwencyjnego licznika dla identyfikatora w CouchDB i indeksujesz tweety ... po kilku miesiącach będziesz mieć wartości od „1” do „100 000 000 000”.

Załóżmy, że budujesz indeks na bazie danych w dniu 1, gdy w bazie danych są tylko 4 tweety, CouchDB może ulec pokusie użycia następującej konstrukcji kluczowych wartości w blokach indeksu:

[1-byte][8-bytes] <-- 9 bytes
4096 / 9 = 455 keys per block

W pewnym momencie to się psuje i potrzebujesz zmiennej liczby bajtów, aby zapisać wartość klucza w indeksach.

Problem jest jeszcze bardziej rażący, jeśli zdecydujesz się zaindeksować pole o naprawdę zmiennej długości, takie jak „tweet_message” lub coś w tym rodzaju.

Ponieważ sam klucz ma całkowitą zmienną długość, a baza danych nie ma możliwości inteligentnego odgadnięcia „maksymalnego rozmiaru klucza” podczas tworzenia i aktualizacji indeksu, w jaki sposób klucze są faktycznie przechowywane w blokach reprezentujących segmenty indeksów w tych bazach danych ?

Oczywiście, jeśli klucze są zmienne wielkości i można przeczytać w bloku klawiszy, nie tylko nie masz pojęcia, jak wiele klucze są rzeczywiście w bloku, ale nie masz pojęcia, jak skakać na środku listy, aby zrobić binarny szukaj na nich.

To tutaj zaczynam się potykać.

W przypadku pól o typie statycznym w klasycznych bazach danych SQL (takich jak bool, int, char itp.) Rozumiem, że indeks może po prostu wstępnie zdefiniować długość klucza i trzymać się jej ... ale w tym świecie magazynów danych dokumentów jestem zakłopotany tym, jak wydajnie modelują te dane na dysku, aby można je było skanować w czasie O (logowania) i docenilibyśmy tutaj wszelkie wyjaśnienia.

Daj mi znać, jeśli potrzebne będą jakieś wyjaśnienia!

Aktualizacja (odpowiedź Grega)

Proszę zobaczyć moje komentarze dołączone do odpowiedzi Grega. Po tygodniu dalszych badań wydaje mi się, że naprawdę natknął się na cudownie prostą i wydajną sugestię, że w praktyce jest bardzo łatwa do wdrożenia i użycia, a jednocześnie zapewnia dużą wydajność, unikając deserializacji kluczowych wartości, na których ci nie zależy.

Przyjrzałem się 3 oddzielnym implementacjom DBMS (CouchDB, kivaloo i InnoDB) i wszystkie one rozwiązują ten problem, deserializując cały blok do wewnętrznej struktury danych przed przeszukaniem wartości w środowisku wykonawczym (erlang / C).

To, co myślę, jest tak genialne w sugestii Grega; normalny rozmiar bloku 2048 normalnie miałby 50 lub mniej przesunięć, co skutkowałoby bardzo małym blokiem liczb, który musiałby zostać wczytany.

Aktualizacja (potencjalne wady sugestii Grega)

Aby jak najlepiej kontynuować ten dialog ze sobą, zdałem sobie sprawę z następujących wad tego ...

  1. Jeśli do każdego „bloku” dołączone są dane przesunięcia, nie można pozwolić na dostosowanie rozmiaru bloku w konfiguracji później, ponieważ może to spowodować odczyt danych, które nie zaczynają się poprawnie od nagłówka lub bloku, który zawiera wiele nagłówków.

  2. Jeśli indeksujesz ogromne wartości kluczy (powiedzmy, że ktoś próbuje zaindeksować kolumnę char (8192) lub blob (8192)), możliwe jest, że klucze nie mieszczą się w jednym bloku i muszą zostać przepełnione przez dwa bloki obok siebie . Oznacza to, że pierwszy blok miałby przesunięty nagłówek, a drugi blok natychmiast zaczynałby się od kluczowych danych.

Rozwiązaniem tego wszystkiego jest ustalony rozmiar bloku bazy danych, który nie jest regulować, i tworzenie wokół niego struktur danych bloku nagłówka ... na przykład, naprawiasz wszystkie rozmiary bloków do 4KB (zazwyczaj najbardziej optymalne i tak) i piszesz bardzo mały nagłówek bloku, który zawiera na początku „typ bloku”. Jeśli jest to normalny blok, to bezpośrednio po nagłówku bloku powinien znajdować się nagłówek przesunięć. Jeśli jest to typ „przepełnienia”, to bezpośrednio po nagłówku bloku znajdują się dane surowego klucza.

Aktualizacja (potencjalnie niesamowity wzrost)

Po wczytaniu bloku jako serii bajtów i dekodowaniu przesunięć; technicznie możesz po prostu zakodować szukany klucz do surowych bajtów, a następnie dokonać bezpośrednich porównań w strumieniu bajtów.

Po znalezieniu szukanego klucza wskaźnik można zdekodować i śledzić.

Kolejny niesamowity efekt uboczny pomysłu Grega! Potencjał optymalizacji czasu procesora tutaj jest na tyle duży, że ustawienie stałego rozmiaru bloku może być tego warte, aby to wszystko uzyskać.


Dla wszystkich zainteresowanych tym tematem główny programista Redis napotkał dokładnie ten problem, próbując zaimplementować niedziałający składnik „magazynu dysków” dla Redis. Początkowo wybrał 32-bajtowy „wystarczająco duży” klucz statyczny, ale zdał sobie sprawę z potencjalnych problemów i zamiast tego zdecydował się na przechowywanie skrótu kluczy (sha1 lub md5) tylko w celu uzyskania jednolitego rozmiaru. Zabija to zdolność wykonywania zapytań dystansowych, ale ładnie równoważy drzewo FWIW. Szczegóły tutaj redis.hackyhack.net/2011-01-12.html
Riyad Kalla

Znalazłem więcej informacji. Wygląda na to, że SQLite ma ograniczenie co do wielkości kluczy lub w rzeczywistości przycina wartość klucza w górnej granicy i umieszcza resztę na „stronie przepełnienia” na dysku. Może to powodować, że zapytania o ogromne klucze są przerażające, ponieważ losowe operacje we / wy podwajają się. Przewiń w dół do sekcji „Strony B-drzewa” sqlite.org/fileformat2.html
Riyad Kalla

Odpowiedzi:


7

Możesz przechowywać swój indeks jako listę przesunięć o stałym rozmiarze w bloku zawierającym twoje kluczowe dane. Na przykład:

+--------------+
| 3            | number of entries
+--------------+
| 16           | offset of first key data
+--------------+
| 24           | offset of second key data
+--------------+
| 39           | offset of third key data
+--------------+
| key one |
+----------------+
| key number two |
+-----------------------+
| this is the third key |
+-----------------------+

(cóż, kluczowe dane zostałyby posortowane na prawdziwym przykładzie, ale masz pomysł).

Zauważ, że niekoniecznie odzwierciedla to faktyczną konstrukcję bloków indeksów w dowolnej bazie danych. To jest jedynie przykładem, w jaki sposób można zorganizować blok danych indeksowych gdzie kluczowe dane o zmiennej długości.


Greg, nie wybrałem jeszcze twojej odpowiedzi jako odpowiedzi defacto, ponieważ liczę na więcej informacji zwrotnych, a także na dalsze badania innych DBMS (dodaję swoje komentarze do oryginalnego Q). Jak dotąd najczęstszym podejściem wydaje się być górna granica, a następnie reszta klucza w tabeli przepełnienia, która jest sprawdzana tylko wtedy, gdy potrzebny jest pełny klucz. Nie takie eleganckie. Twoje rozwiązanie ma w sobie pewną elegancję, którą lubię, ale w przypadku krawędzi, w której klucze powiększają rozmiar twojej strony, twoja droga nadal wymagałaby przepełnienia tabeli lub po prostu nie pozwalałaby na to.
Riyad Kalla

Skończyło mi się miejsce ... Krótko mówiąc, jeśli projektant db mógłby żyć z pewnymi twardymi ograniczeniami wielkości klucza, myślę, że twoje podejście jest najbardziej wydajne i elastyczne. Ładne połączenie przestrzeni i wydajności procesora. Tabele przepełnienia są bardziej elastyczne, ale może być okropne dodawanie losowych operacji we / wy do wyszukiwania kluczy, które ciągle się przepełniają. Dzięki za wkład w to!
Riyad Kalla

Greg, zastanawiałem się nad tym coraz bardziej, patrząc na alternatywne rozwiązania i myślę, że przybiłeś go pomysłem nagłówka offsetowego. Jeśli utrzymujesz małe bloki, możesz uciec z 8-bitowymi (1-bajtowymi) przesunięciami, przy większych blokach 16-bitowy byłby najbezpieczniejszy nawet do 128 KB lub 256 KB, co powinno być rozsądne (przy założeniu 4 lub 8-bajtowych kluczy). Wielką wygraną jest to, jak tanio i szybko można odczytać dane przesunięcia oraz ile zaoszczędzisz na deserializacji. Doskonała sugestia, jeszcze raz dziękuję.
Riyad Kalla

Jest to również podejście stosowane w UpscaleDB: upscaledb.com/about.html#varlength
Mathieu Rodic
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.