Storage and Retrieval Flashcards
(23 cards)
Jaka jest charakterystyka Bitcaska? Jakie są jego główne ograniczenia? W jakiej bazie danych jest używany?
Charakterystyka:
- szybki i przewidywalny zapis i odczyt par klucz-wartość.
- oparty o log (insert/update ląduje na koniec loga)
- w pamięci RAM przechowywana mapa, która wskazuje offset na dysku, gdzie trzymana jest wartość dla danego klucza (1 disc seek, żeby pobrać wartość z dysku)
-dodatkowo niemożliwe jest wykonywanie efektywnych range queries
Główne ograniczenie: zbiór kluczy musi mieścić się w pamięci RAM.
Używany przez bazę danych: Riak.
Dla jakich zastosowań nada się baza danych Riak?
Dużo zapisów (zapis szybki, bo to tylko append na koniec pliku), ale na niedużym zbiorze kluczy (bo zbiór kluczy musi się mieścić w pamięci).
Co oznacza branching factor w kontekście B-tree?
Branching factor to liczba definiująca, ile referencji do child pages zawiera jeden page.
Jak przebiega insert nowej watości w B-tree?
Znajdź leaf page, gdzie powinna znaleźćsię wartość. Jeśli jest jeszcze miejsce w danym page’u, dopisz nową wartość. Jeśli nie ma, podziel page na dwa półpełne page’e (uwzględniając nową wartość) i zaktualizuj parent page o informację o podziale.
Zalety String Sorted Table względem tabeli haszującej z prostym append logiem?
-łatwe compaction (mergesort)
-można trzymać więcej par klucz wartość, bo można użyć sparse index dla tablicy haszujacej
-jako że wyciąga się cały segment, można go skompresować przed zapisem
W jaki sposób bazy danych in-memory mogą zapewnić durability?
-zapis snapshota co jakiś czas
-log na podstawie którego można odtworzyć stan (synchroniczny lub asynchroniczny)
- zaczytanie stanu z repliki
Różnice między grupami:
- VoltDB/MemSQL
-Memcached
-RamCloud
-Redis/couchbase
Wszystkie inmemory.
Volt - relacyjny model
RamCloud - KV store log structured with durability
Refdis/Couchbase - weak durability
Memcached - no durability
Wyjaśnij czym jest Star Schema. Czym różni się od Snowflake Schema?
Star schema - schemat relacyjnej bazy do analitycznych zastosowań. W centrum tabela faktów reprezentująca zdarzenia w systemie. Posiada wiele referencji do dimension tables, które rozszerzają informacje o evencie o różne wymiary (who, what, why, when where, how).
Snowflake - dimension table mogą mieć dalsze referencje do subdimensions.
Objaśnij column oriented storage. Jakie techniki kompresji można zastosować?
Dane nie trzymane całymi wierszami, ale obok siebie wartości danej kolumny dla kolejnych wierszy. Jest to optymalne jeśli zazwyczaj wyciągamy niewielki podzbiór kolumn z olbrzymiego zbioru danych.
Można zastosować kompresję:
-bit mapę encoding
-jeśli zbiór wartości duży, dodatkowo run-length encoding
Dlaczego sortowanie w kolumnowych bazach danych ma znaczenie?
Możliwość dobrej kompresji na sort key, zwłaszcza primary key (run length encoding). Szybsze przetwarzanie najpopularniejszych query. Niektóre bazy na różnych replikach używają różnego sort Key.
Jak efektywnie wykonać zapis/update w kolumnowej bazie danych z wierszami posortowanymi?
Podobne podejście jak z LSM tree: in-memory sorted structure, która później mergowana bulkiem z plikami kolumnowymi.
Charakterystyka OLTP vs OLAP
OLTP - miks odczytów i zapisów w dużych ilościach ale zazwyczaj dotyczących małej ilości danych, bottleneck to seek time, najczęściej rozwiązania dla użytkowników końcowych
OLAP - mało analitycznych głównie read only odczytów ale na dużych zbiorach danych, Disk bandwidth bottleneckiem.
Dlaczego enkodowanie z użyciem mechanizmów wbudowanych w język programowania może być złym pomysłem? Jakie są przykłady takiego enocodowania?
Przykłady: Ruby - Marshal, Python - pickle, Java - Serializable
Problemy:
-efektywność i wersjonowanie jest często afterthought (zwłaszcza Javowe Serializable jest znane ze złego performance)
-często brak interoperability pomiędzy językami
-problemy Security: często wymagają możliwości instancjonowania dowolnej klasy, a to daje dużo możliwości atakującemu który podstawi nam obiekt do deserializacji)
Czym różni się binarne enkodowanie JSONa w stylu MessagePack od rozwiązań Thrift/Protocol Buffers?
MessagePack: schema zakodowana razem z danymi. Podobnie pewne sekwencje bajtów wyznaczają, jaki jest typ i w niektórych przypadkach długość (np. Stringa).
Protobuf/Thrift: schema dostarczana zewnętrznie, nadaje poszczególnym polom tag number i tylko number (a nie cała nazwa pola) jest referowany w zakodowanych danych. Stosują bardziej kompaktowe enkodowanie liczb (najwyższy bit wskazuje czy jest kolejny bajt dla danej liczby). Thrift wyróżnia Binary oraz Compact Protocol. W Binary są osobne bajty na field type i na tag number. W Compact jest to upchane w jednym bajcie. Protocol Buffers ma tylko jedno enkodowanie analogiczne do Compact z Thrifta.
Jak Apache Thrift/Protocol Buffers zapewniają forward/backward compatibility?
Schema w nowej wersji może zmienić nazwę pola, bo jest referowane przez numer, ale typu juz nie. Może dodać nowe pole, bo stary kod może po prostu zignorować tag number którego nie zna (jako że wie jaki jest typ tego pola, wie ile bajtów pominąć). Może usunąć opcjonalne pole i wtedy po prostu ignoruje dany tag number, nie można tylko reuzyc starego taga.
Jeśli chcemy zachować backward compatibility: musimy albo dodawać tylko opcjonalne pola albo nadawać im domyślną wartość.
Czym różni się forward compatibility od backward compatibility?
Forward: stary kod może czytać nowe dane.
Backward: nowy kod może czytać stare dane.
Co umożliwia zastosowanie typu repeated w Protocol Buffer? Co ogranicza?
Możliwość zmiany typu optional na listę. Stary kod widząc nowe dane czyta tylko ostatni element. Nowy kod czytając stare dane widzi listę z jednym lub żadnym elementem.
Co tracimy? Parametryzowana lista jak w Thrift umożliwia zastosowanie zagnieżdżonych list.
Czym różni się Apache Avro od Protocol Buffers / Apache Thrift?
- podział na writer schema i reader schema
-brak tag number dla pól czy w ogóle wyróżnienia pola, pola pomiędzy schemami matchowane po nazwie pola
-bardziej kompaktowy - typ i nazwa pola nie są enkodowane, pola są po prostu czytane w kolejności z writer schema
Rezultat: łatwość generowania schematu np. na podstawie bazy danych, bo kolejność pól nie ma znaczenia
Ewolucja schematu w przypadku Avro
Forward compatibility: new writer schema, old reader schema
Backward compatibility: na odwrót
Dla kompatybilności: można dodawać lub usuwać tylko pola z domyślną wartością.
Null może być domyślną wartością tylko jeśli jest explicite zdefiniowany jako dozwolony (jest w union typie)
Zmiana typu pola możliwa jeśli Avro może je sobie skonwertować.
Zmiana nazwy pola możliwe przez stworzenie aliasu ale jest tylko backward compatible.
Podobnie jak wyżej z dodaniem typu do union.
Skąd reader może wziąć writer schema (w kontekście Avro)?
-przechowywana raz razem z dużą ilością rekordów na początku pliku (Avro object container file)
-w bazie kolumna mówiąca o wersji i po enkodowaniu ta wersja na początku rekordu
-w przypadku network connection schemat może być negocjowany i ważny przez długość połączenia
Zalety posiadania schematu encji w binarnym enkodowaniu
-dane bardziej kompaktowe niż w tekstowych formatach czy nawet JSON binary
-dokumentacja schematu która musi być utrzymywana up to date siłą rzeczy bo potrzebna do dekodowania
-możliwe generowanie kodu w statycznych językach programowania
-mając bazę wersji schematów łatwo zanalizować ich kompatybilność przed deployem
Dlaczego używanie abstrakcji, która ukrywa, że RPC nie jest lokalnym wywołaniem funkcji może być złym pomysłem?
Lokalne wywołanie i RPC są fundamentalnie różne:
-lokalna funkcja albo kończy się sukcesem albo błędem, network call może mieć również problemy sieciowe przez które nie wiemy, jak skończyło się wywołanie - warto świadomie obsłużyć timeout czy inne błędy sieciowe
-większe i mniej przewidywalne latency i czas wykonania
-serwis i klient mogą być w różnych językach, co może powodować pewne niezgodności, np. w typach
-trzeba rozważyć kompatybilność
-możliwość przekazywania referencji lokalnie, brak możliwości zdalnie
Rozwiązania jak Java RMI czy CORBA nie miały również obsługi kompatybilności.
SOAP vs REST
WSDL - Web Service Description Language
Stanard opierający się na XMLach i abstrahujący to, że opiera się na HTTP - nie opiera się na większości funkcjonalności HTTP. Opiera się na WSDL.
Możliwość generowania kodu request i response.
WSDL nie jest human readable i ciężkie manualnie budować requesty i eksperymentować. Wymaga toolingu.
REST - bardziej filozofia, silnie opiera się na HTTP (cache control, authentication, content type negotiation). Zazwyczaj JSON bez scheme. Łatwo debugować i eksperymentować.
