Partitioning & Replication Flashcards
(24 cards)
W jaki sposób można rozdzielać dane między partycjami?
Jakie wady i zalety mają te sposoby?
Albo po prostu po kluczu danej porcji danych albo po hashu tego klucza.
Pierwszy jest lepszy, jeśli chcemy efektywnie wykonywać range queries, ale jest w nim ciężej o równe dystrybuowanie danych pomiędzy partycjami.
Drugi jest lepszy, jeśli istnieje ryzyko występowania nierównomiernego występowania kluczy. Utrudnia jednak range query - tail latency amplification.
Opisz znane ci metody rebalansingu partycji. W których bazach danych stosowany jest każdy z nich?
- fixed number of partitions, e.g. Riak or Elastic Search or Couchbase or Voldemort
- dynamic number of partitions, e.g. MongoDB or HBase or RethinkDB
- fixed numer of partitions per nodes, e.g. Cassandra, Ketama
W jaki sposób działają local i global secondary index w przypadku partycjonowanych baz danych?
Local (zwany też document-based) - indeksuje tylko dane w obrębie partycji, czyli przydatny jak chcemy uporządkować dane dla danego klucza.
Global (zwany też term-based) - tworzony przez podział danych na drugi sposób pomiędzy partycjami (w inny sposób niż główny), tak aby można było robić wydajne range query po innym kluczu niż główny. Zazwyczaj aktualizowany asynchronicznie.
Dlaczego partycjonowanie za pomocą mod n, gdzie n to liczba node’ów, to nienajlepszy pomysł?
Ponieważ rebalansing po dodaniu/odjęciu node’a wymaga dużej wymiany danych pomiędzy node’ami. Większość danych po zmianie wyląduje w zupełnie innej partycji.
Na czym polega dynamiczne partycjonowanie? W jakiej bazie danych jest stosowane? Jakie są jej wady i zalety?
Mechanizm partycjonowania, w którym liczba partycji dynamicznie się zmienia. W momencie, gdy partycja przekracza pewien rozmiar, dzielona jest na pół i potencjalnie dystrybuowana do innego node’a.
Pozwala w łatwy sposób zachowywać względnie stałe rozmiary partycji nawet gdy dane dzielone są pomiędzy partycje po kluczu a nie po hashu. Sprawdzi się zatem, gdy chcemy wykonywać na danych range query.
Stosowane w: HBase, MongoDB.
W jaki sposób requesty routowane są do właściwego node’a (i partycji)?
- Osobna warstwa routująca przekierowująca zapytania do odpowiednich node’ów
- Każdy z node’ów może znać podział partycji i robić przekierowania (klienci mogą stosować round robin wtedy)
- Klienci mogą znać bezpośrednio podział i od razu uderzać do odpowiedniego node’a
W każdym przypadku potrzebny jest mechanizm przez który „świadoma” warstwa będzie utrzymywać aktualny podział partycji do node’ów (service discovery, coordination service). Często oparte jest to o ZooKeepera albo inny podobny system.
Cassandra i Riak opierają się o gossip protocol. Takie podejście zwiększa skomplikowanie w node’ach ale uwalnia od zależności na zewnętrznym serwisie koordynującym.
Dlaczego możemy chcieć replikować dane?
-bliskość geograficzna do użytkowników
-jako backup (zwiększone availability)
-żeby zwiększyć obsługiwaną liczbę requestow (horizontal scaling)
Opisz różne opcje replikacji danych przy systemie leader-follower
Jakie są ich wady/zalety?
-synchroniczna replikacja - leader zatwierdza operacje tylko gdy wszyscy followerzy potwierdzą zapis
-asynchroniczna - followerzy od razu notyfikowani, ale nie czekamy na odpowiedź od nich, żeby zatwierdzić zapis
-semisynchroniczna - jeden follower replikowany synchronicznie, reszta asynchronicznie
Przy synchronicznej mamy mocniej zapewnione durability ale kosztem high availability - niedostępny follower blokuje jakikolwiek zapis. Z kolei przy asynchronicznej jeśli leader się wywali a nie zdąży zreplikowac jakichś danych, to te zapisy są stracone
Jak przebiega proces dodania nowego followera do już istniejącego leadera?
-pobieramy z leadera consistent snapshot, następnie po jego przetworzeniu prosimy leadera o wszystkie transakcje od momentu w którym snapshot powstał
Snapshot musi mieć dowiązanie do dokładnej pozycji w replication logu (np. log sequence number w Postgres, binlog coordinates w MySQL)
W jakich krokach odbywa się failover replikowanego mastera?
- Stwierdzenie, że konieczny jest failover. Zwykle w oparciu o brak odpowiedzi przez określony czas.
- Wybór nowego leadera, np. konsensu algorytm albo wybrany przez wcześniej ustanowiony controller node.
- Przepięcie write’ów do nowego leadera, przepięcie pozostałych node’ow żeby followały nowego leadera.
Co może pójść nie tak w wyniku failoveru?
-nowy leader może być to tylu - tracimy durability
-niezsynchronizowane dane mogą już być używane przez inne systemy, np. cache - ponownie użyte klucze główne mogą referować do czegoś innego
-stary leader może powrócić i uważać że dalej jest leaderem, czy ogólnie system może widzieć dwóch liderów, tzw. brain split.
-
Sposoby replikacji w systemie leader follower. Ograniczenia każdego z nich.
-statement based - problem z niedeterministycznymi komendami, np. rand(), now(), problem z kolejnością musi być taka sama, jeśli np. autoincrement stosujemy
-WAL shipping - kopiujemy to co w WAL do replik, ale wiążemy się do binarnego formatu stosowanego przez bazę, może być problem przy upgradeach bazy, mogą np. wymagać downtimeu
-logical log replication (rów based) - przesyłamy co się zmieniło w jakim wierszu (coś co identyfikuje wiersz i wartości kolumn). Format może być przydatny jeśli chcemy skorzystać z Change Data Capture. Łatwiej sparsowac zewnętrznym systemom, np. analitycznym bazom.
-trigger based replication - możemy uruchomić trigger na bazie, który zapisze do dedykowanej tabeli co chcemy replikować. Przydatne jeśli chcemy replikować tylko część danych. Zewnętrzna aplikacja czyta tą dodatkową tabelę. Rozwiązanie z np. Bucardo dla Postgresa. Zwykle większy overhead, wolniejsze, łatwiej o bugi.
W jaki sposób zaimplementować read-after-write consistency?
-jeśli potencjalnie niewiele danych, które może zedytowac użytkownik, to odczyty tylko tych danych routować do leadera
-zapamiętywać timestamp ostatniego zapisu, X czasu od ostatniego zapisu routowac tylko do leadera
-można zapamiętywać logiczny timestamp ostatniego zapisu (log sequence number) i odczytywać tylko z replik, które mają już przetworzony ten timestamp
Sprawy się komplikują, jeśli użytkownik może działać na kilku urządzeniach lub followerzy są w oddzielonych geograficznie centrach danych
Czym jest monotonic read gwarancja? Jak ją osiągnąć?
Jeśli mamy dwa odczyty od danego użytkownika, to drugi w kolejności nie może widzieć stanu sprzed pierwszego odczytu. Użytkownik nie może doświadczać cofnięcia się w czasie.
Aby to osiągnąć możemy np. zawsze uderzać do tej samej repliki (routing np. po hashu user ID). Problem gdy replika się wywali.
Czym jest consistent prefix read?
Gwarancja, że reader będzie widział zapisy w takiej samej kolejności jak się one dokonały. Problem szczególnie uwidoczniony w shardowanych bazach, bo partycje działają niezależnie. Rozwiązanie wymaga globalnego przetrzymywania informacji o kolejności zapisów.
Co jest głównym wyzwaniem systemów typu multi-leader? Jak do niego można podejść?
Conflict resolution - dwaj liderzy mogą nadpisywać ten sam rekord w tym samym czasie. Rozwiązania:
-unikanie konfliktów, np. zapisy dotyczące konkretnych danych idą przez konkretnego lidera, ale co w przypadku failoveru?
-przydzielanie zapisom ID/UUID/timestampu i write z najwyższą wartością wygrywa (LWW), ale wiąże się z data loss
-przydzielanie ID liderom i lider z najwyższym ID wygrywa, ale znowu data loss
-zapisywanie zaistniałych konfliktów do późniejszego rozwiązania, np. przez zaangażowanie użytkownika
-mergowanie konfliktujacych wartości, np. przez konktatenacje
Dodatkowo podział na rozwiązywanie konfliktów on-write vs on-read.
Kiedy i dlaczego możemy chcieć używać multi-leader replikacji?
Może mieć sens przy kilku centrach danych. Wtedy w każdym centrum jest leader-follower, ale leaderzy dodatkowo między sobą synchronizują zapisy. Jakie ma to zalety?
-performance - użytkownik uderza z zapisem do najbliższego centrum
-fault tolerance - awaria jednego centrum nie zaburza funkcjonowania drugiego; można nawet zrobić failover lidera do drugiego centrum
-network fault tolerance - komunikacja między centrami idzie przez publiczny internet, mniej niezawodny niż sięc lokalna w centrum; przy asynchronicznej replikacji, chwilowy problem z siecią nie stanowi poważnego outagu (zsynchronizuje się później)
W jaki sposób w leaderless replication osiągnąć eventual consistency?
-read repair - przy odczycie korygowane node’y, które mają przedawnione wartości dla klucza
-anti-entropy process - proces w tle, który wykrywa różnice między replikami
W jaki sposób przy leaderless replication zagwarantować, że zawsze read zwróci najnowsza wartość wiersza?
Kworum
N - liczba replik
R - liczba replik z których czytamy
W - liczba replik do których zapisujemy
Jeśli R+W>N mamy pewność że zwrócona zostanie najnowsza wartość chociaż z jednego node’a.
Side note: zapisy i odczyty mogą być wysyłane do wszystkich node’ów ale czekamy na odpowiedź z W/R pierwszych.
Przykłady sytuacji brzegowych przy zapisie/odczycie przez kworum
-dwa zapisy równoległe wykonywane - który był pierwszy? LWW - wtedy musi być dobra synchronizacja zegarów
-zapis z kworum udany, ale jedna z replik przywrócona z backupu
-zapis się udał na mniej niż W replikach, ale nie został skutecznie zrollbackowany
-odczyt i zapis wykonywane równolegle - zapis jeszcze mógł nie osiągnąć W replik
Czym jest sloppy quorum I hinted handoff?
-sloppy quorum - możliwość osłabienia gwarancji quorum przez akceptowanie W zapisów w jakichkolwiek node’ach (a nie tylko w tych, które są desygnowane do ustalania kworum) ; zwiększa durability, ale tracimy gwarancję ze dostaniemy najświeższa wartość przy odczycie, wciąż eventual consistency, bo..
-gdy desygnowany node powraca do systemu, zastępczy node przekazuje mu zapisy, które w jego imieniu odebrał
Zazwyczaj sloppy quorum konfigurowalne, w niektórych systemach włączone domyślnie, w innych nie.
W jaki sposób obsługiwane są zapisy z pomocą relacji happens-before?
Kiedy zapisujemy dostajemy w zwrotce wersję zapisu. Kiedy aktualizujemy wysyłamy wersje na podstawie jakiej nadpisujemy. W odpowiedzi możemy dostać dwie różne wersje zapisu, jeśli nie byliśmy świadomi innego concurrent zapisu. Do nas należy tak dokonać dalszy zapis aby połączyć dwie wersje w jedną. Czyli generalnie opieramy się na rozwiązywaniu konfliktów pomiędzy współbieżnymi zapisami, zamiast cicho je ignorować/nadpisywac.
Jeśli do tego mamy kilka replik, to każda ma swoje wersje rekordu i mówimy o wektorze wersji.
W jakich przypadkach partycjonowanie dynamiczne może mieć więcej sensu niż posiadanie stałej liczby partycji?
Kiedy partycjonujemy dane po kluczu (key-range partitioning), a nie po hashu. Z dynamicznym partycjonowaniem automatycznie rozwiązujemy problem hotspotów.
Jakie zalety/wady ma routowanie z użyciem świadomej warstwy vs routowanie przez gossip protocol?
Gossip protocol - nie ma single point of failure w postaci systemu koordynującego (np. zookeper), ale za to jest bardziej skomplikowany.
