2.1 Jak shardować i spowolnić N razy?

Możesz shardować i zwalniać dokładnie N razy w ten sposób:

  • Wysyłaj żądania docs00...docs15 sekwencyjnie , a nie równolegle.
  • W prostych zapytaniach dokonuj wyboru nie według klucza , WHERE coś=234.

W tym przypadku część serializowana (szeregowa) zajmuje nie 1% i nie 5%, ale około 20% we współczesnych bazach danych. Możesz również uzyskać 50% części serializowanej, jeśli uzyskasz dostęp do bazy danych za pomocą niezwykle wydajnego protokołu binarnego lub połączysz ją jako bibliotekę dynamiczną ze skryptem Pythona.

Resztę czasu przetwarzania prostego żądania zajmą nierównoległe operacje analizowania żądania, przygotowania planu itp. Oznacza to, że nie odczytywanie rekordu spowalnia.

Jeśli podzielimy dane na 16 tabel i uruchomimy sekwencyjnie, jak to jest w zwyczaju np. w języku programowania PHP (nie radzi sobie zbyt dobrze z uruchamianiem procesów asynchronicznych), to otrzymamy 16-krotne spowolnienie. A może nawet więcej, ponieważ dodane zostaną również połączenia sieciowe w obie strony.

Nagle wybór języka programowania jest ważny podczas shardingu.

Pamiętaj o wyborze języka programowania, bo jeśli zapytania do bazy danych (lub serwera wyszukiwania) wysyłasz sekwencyjnie, to skąd bierze się przyspieszenie? Raczej nastąpi spowolnienie.

2.2 O półautomatycznym

W niektórych miejscach wyrafinowanie technologii informacyjnej inspiruje chtoniczny horror. Na przykład MySQL po wyjęciu z pudełka na pewno nie miał implementacji shardingu do niektórych wersji, jednak rozmiary baz danych używanych w bitwie rosną do nieprzyzwoitych wartości.

Cierpiąca ludzkość w obliczu poszczególnych DBA dręczona jest od lat i pisze kilka złych rozwiązań shardingu opartych na niczym. Następnie powstaje jedno mniej lub bardziej przyzwoite rozwiązanie do shardingu o nazwie ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...). To dobrze znany przykład tej właśnie plamy.

ProxySQL jako całość jest oczywiście pełnoprawnym rozwiązaniem klasy korporacyjnej dla open source, do routingu i nie tylko. Ale jednym z zadań do rozwiązania jest sharding dla bazy danych, która sama w sobie nie może shardować w ludzki sposób. Widzisz, nie ma przełącznika „shards = 16”, albo musisz przepisać każde żądanie w aplikacji, a miejscami jest ich bardzo dużo, albo umieścić jakąś warstwę pośrednią między aplikacją a bazą danych, która wygląda: „Hmm ... WYBRAĆ * Z dokumentów? Tak, musi być rozbity na 16 małych SELECT*FROM server1.document1, SELECT*FROM server2.document2 - do tego serwera z takim loginem/hasłem, do tego z innym. Jeśli ktoś nie odpowiedział, to ... ”, itd. Dokładnie to można zrobić za pomocą plam pośrednich. Są one nieco mniejsze niż dla wszystkich baz danych. Dla PostgreSQL, o ile rozumiem,

Konfigurowanie każdej konkretnej poprawki to osobny, gigantyczny temat, który nie zmieści się w jednym raporcie, dlatego omówimy tylko podstawowe pojęcia. Lepiej porozmawiajmy trochę o teorii szumu.

2.3 Absolutnie doskonała automatyzacja?

Cała teoria zdobywania haju w przypadku shardingu w tej literze F() , podstawowa zasada jest zawsze taka sama z grubsza: shard_id = F(object).

Sharding – o co w tym wszystkim chodzi? Mamy 2 miliardy rekordów (lub 64). Chcemy podzielić je na kilka części. Pojawia się nieoczekiwane pytanie – jak? Na jakiej zasadzie mam rozproszyć moje 2 miliardy rekordów (lub 64) na 16 dostępnych dla mnie serwerach?

Ukryty w nas matematyk powinien zasugerować, że w końcu zawsze istnieje jakaś magiczna funkcja, która dla każdego dokumentu (obiektu, wiersza itp.) określi, w którym kawałku go umieścić.

Java university

Zagłębiając się w matematykę, ta funkcja zawsze zależy nie tylko od samego obiektu (samego wiersza), ale także od ustawień zewnętrznych, takich jak całkowita liczba odłamków. Funkcja, która dla każdego obiektu musi powiedzieć, gdzie go umieścić, nie może zwrócić wartości większej niż liczba serwerów w systemie. A funkcje są nieco inne:

shard_func = F1(object); 
shard_id = F2(shard_func, ...); 
shard_id = F2(F1(object), current_num_shards, ...).

Ale dalej nie będziemy zagłębiać się w te dziczy poszczególnych funkcji, porozmawiamy tylko o tym, czym są magiczne funkcje F ().

2.4 Czym są F()?

Mogą wymyślić wiele różnych i wiele różnych mechanizmów wdrażania. Przykładowe podsumowanie:

  • F = rand() % nums_shards
  • F = somehash(object.id) % num_shards
  • F = obiekt.data % liczba_odłamków
  • F = obiekt.identyfikator_użytkownika % liczba_odłamków
  • ...
  • F = shard_table [ somehash() |… obiekt.data |… ]

Ciekawostka - można naturalnie rozrzucić wszystkie dane losowo - kolejny rekord wrzucamy na dowolny serwer, na dowolny rdzeń, w dowolną tabelę. Nie będzie w tym wiele szczęścia, ale zadziała.

Istnieją nieco bardziej inteligentne metody dzielenia na fragmenty za pomocą powtarzalnej lub nawet spójnej funkcji skrótu lub dzielenia na fragmenty według jakiegoś atrybutu. Przejdźmy przez każdą metodę.

F = rand()

Rozpraszanie się nie jest zbyt poprawną metodą. Jeden problem: rozproszyliśmy losowo nasze 2 miliardy rekordów na tysiącach serwerów i nie wiemy, gdzie się one znajdują. Musimy wyciągnąć użytkownika user_1, ale nie wiemy, gdzie on jest. Wchodzimy na tysiące serwerów i sortujemy wszystko - jakoś to jest nieefektywne.

F = jakiś hash()

Rozproszmy użytkowników w sposób dla dorosłych: oblicz powtarzalną funkcję skrótu z user_id, weź resztę z dzielenia przez liczbę serwerów i natychmiast skontaktuj się z żądanym serwerem.

Dlaczego to robimy? A potem, że mamy duże obciążenie i nic więcej nie mieści się na jednym serwerze. Gdyby to pasowało, życie byłoby takie proste.

Świetnie, sytuacja już się poprawiła, aby zdobyć jeden rekord, idziemy wcześniej na jeden znany serwer. Ale jeśli mamy zakres kluczy, to w całym tym zakresie musimy przejść przez wszystkie wartości kluczy i, w limicie, przejść albo do tylu odłamków, ile mamy kluczy w zakresie, albo nawet do każdy serwer. Sytuacja oczywiście się poprawiła, ale nie w przypadku wszystkich wniosków. Wpłynęło to na niektóre zapytania.

Naturalne sharding (F = data_obiektu % num_shards)

Czasami, to znaczy często, 95% ruchu i 95% obciążenia to żądania, które mają pewien rodzaj naturalnego shardingu. Na przykład 95% warunkowych zapytań społeczno-analitycznych wpływa na dane tylko z ostatniego 1 dnia, 3 dni, 7 dni, a pozostałe 5% odnosi się do ostatnich kilku lat. Ale 95% żądań jest więc naturalnie dzielonych według daty, zainteresowanie użytkowników systemu koncentruje się na ostatnich dniach.

W takim przypadku możesz podzielić dane według daty, na przykład przez jeden dzień, i śledzić odpowiedź na żądanie raportu za jakiś dzień lub obiekt od tego dnia do tego sharda i iść.

Życie się poprawia - teraz nie tylko znamy lokalizację konkretnego obiektu, ale wiemy też o zasięgu. Jeśli zostaniemy poproszeni nie o zakres dat, ale o zakres innych kolumn, to oczywiście będziemy musieli przejść przez wszystkie odłamki. Ale zgodnie z regułami gry mamy tylko 5% takich próśb.

Wydaje się, że znaleźliśmy idealne rozwiązanie na wszystko, ale są dwa problemy:

  • To rozwiązanie jest dostosowane do konkretnego przypadku, gdy 95% zapytań dotyczy tylko ostatniego tygodnia.
  • Ponieważ 95% próśb dotyczy ostatniego tygodnia, wszystkie trafią na jeden fragment obsługujący ten ostatni tydzień. Ten odłamek stopi się, podczas gdy wszystkie inne będą w tym czasie bezczynne. Jednocześnie nie można ich wyrzucić, dane archiwalne też trzeba przechowywać.

Nie mówiąc już o tym, że jest to zły schemat shardingu - odcięliśmy gorące dane, niemniej jednak coś trzeba zrobić z najgorętszym shardem.

Problem rozwiązują wybryki, skoki i okłady, czyli zwiększanie liczby replik na płonący bieżący dzień, a następnie stopniowe zmniejszanie liczby replik, gdy ten dzień staje się przeszłością i trafia do archiwum. Nie ma idealnego rozwiązania o nazwie „wystarczy rozłożyć dane w klastrze za pomocą funkcji magicznego skrótu w niewłaściwy sposób”.

2.5 Cena do zapłaty

Formalnie wiemy, że teraz wiemy „wszystko”. To prawda, że ​​nie znamy jednego wielkiego bólu głowy i dwóch mniejszych bólów głowy.

1. Prosty ból: źle rozmazany

To przykład z podręcznika, który prawie nigdy nie występuje w bitwie, ale nagle.

  • Jako przykład z datą, tylko bez daty!
  • Niezamierzona nierówna (widoczna) dystrybucja.

Wybrali mechanizm shardingu i/lub zmienili dane i oczywiście PM nie przekazał wymagań (nie mamy błędów w kodzie, PM zawsze nie zgłasza wymagań), a dystrybucja stał się potwornie nierówny. Oznacza to, że nie spełnili kryterium.

Aby złapać, musisz spojrzeć na rozmiar odłamków. Problem na pewno zobaczymy w momencie, gdy któryś z naszych shardów albo się przegrzeje, albo stanie się 100 razy większy od pozostałych. Możesz to naprawić, po prostu wymieniając klucz lub funkcję shardingu.

To prosty problem, szczerze mówiąc, nie sądzę, aby przynajmniej jedna osoba na sto napotkała go w życiu, ale nagle pomoże to przynajmniej komuś.

2. Ból „niezwyciężony”: agregacja, łączenie

Jak dokonać selekcji łączących miliard rekordów z jednej tabeli dla miliarda rekordów z innej tabeli?

  • Jak "szybko" obliczyć... GDZIE randcol MIĘDZY aaa I bbb?
  • Jak „sprytnie” zrobić... users_32shards DOŁĄCZYĆ do posts_1024 shards?

Krótka odpowiedź: nie ma mowy, cierp!

Jeśli rozdzieliłeś miliard rekordów na tysiąc serwerów w pierwszej tabeli, aby działały szybciej, i zrobiłeś to samo w drugiej tabeli, to naturalnie tysiąc do tysiąca serwerów powinno rozmawiać ze sobą w parach. Milion połączeń nie będzie dobrze działać. Jeśli wyślemy żądania do bazy danych (przeszukiwania, przechowywania, przechowywania dokumentów lub rozproszonego systemu plików), które nie pasują dobrze do shardingu, żądania te znacznie spowalniają.

Ważną kwestią jest to, że niektóre prośby zawsze będą bezskutecznie rozmazane i spowalniają . Ważne jest, aby starać się zminimalizować ich odsetek. W konsekwencji nie ma potrzeby wykonywania gigantycznych połączeń z miliardem na miliard rekordów. Jeśli możliwe jest zreplikowanie małej tabeli, względem której łączysz się w gigantycznej wspólnej tabeli, do wszystkich węzłów, powinieneś to zrobić. Jeśli łączenia są w rzeczywistości w jakiś sposób lokalne, na przykład możliwe jest umieszczenie użytkownika i jego postów obok siebie, podzielenie ich w ten sam sposób i wykonanie wszystkich połączeń na tej samej maszynie - musisz to zrobić .

To osobny kurs wykładów na trzy dni, więc przejdźmy do ostatniego piekielnego bólu i różnych algorytmów radzenia sobie z nim.

2.6. Złożony/długi ból: Resharding

Przygotuj się: jeśli podzieliłeś swoje dane po raz pierwszy w życiu, to przeciętnie podzielisz je jeszcze pięć razy.

Bez względu na to, ile klastrów skonfigurujesz, nadal musisz ponownie przeprowadzić hardwar.

Jeśli jesteś bardzo sprytny i masz szczęście, przynajmniej raz wykonaj overshard. Ale gdy już jesteś pewien, bo w momencie, gdy myślisz, że użytkownikowi wystarczy 10 jednostek, ktoś właśnie w tym momencie pisze zapytanie o 30 i planuje mieć zapytanie o 100 jednostek nieznanych zasobów. Odłamków nigdy dość. W każdym razie przy pierwszym schemacie shardingu przegapisz - zawsze będziesz musiał albo zwiększyć liczbę serwerów do dodania, albo zrobić coś innego - ogólnie jakoś przepakować dane.

Dobrze, jeśli mamy ładną potęgę dwójki: było 16 odłamków serwera, teraz jest 32. Zabawniej jest, jeśli było 17, to jest 23 - dwie liczby vasimalnie pierwsze. Jak bazy danych to robią, może mają w sobie jakąś magię?

Prawidłowa odpowiedź brzmi: nie, w środku nie ma magii, mają w sobie piekło.

Następnie zastanowimy się, co można zrobić „ręcznie”, być może zrozumiemy „jako automat”.

Na czole #1. Przenieś wszystko

Dla wszystkich obiektów rozważamy NewF(object), przejście do nowego fragmentu.

Szansa na dopasowanie NewF()=OldF() jest niska.

Omówmy prawie wszystko.

Oh.

Mam nadzieję, że nie ma takiego piekła, aby przenieść wszystkie 2 miliardy rekordów ze starych shardów na nowe. Naiwne podejście jest zrozumiałe: maszyn było 17, do klastra dodano 6 maszyn, uporządkowano 2 miliardy rekordów, przesunięto je z 17 maszyn do 23 maszyn. Raz na 10 lat prawdopodobnie nawet możesz to zrobić. Ale ogólnie to zły ruch.

Na czole #2. Przenieś połowę

Kolejne naiwne ulepszenie - porzućmy taki głupi schemat - zabrania 17 samochodom przeróbki na 23, a my zawsze będziemy przerabiać 16 samochodów na 32 samochody! Wtedy zgodnie z teorią będziemy musieli przesunąć dokładnie połowę danych, aw praktyce też możemy to zrobić.

Dla wszystkich obiektów rozważamy NewF(object), przejście do nowego fragmentu.

To było ściśle 2^N, teraz jest to ściśle 2^(N+1) odłamków.

Prawdopodobieństwo dopasowania NewF()=StaryF() wynosi 0,5.

Prześlijmy około 50% danych.

Optymalne, ale działa tylko dla potęg dwójki.

W zasadzie wszystko jest w porządku, z wyjątkiem wiązania do potęgi dwóch pod względem liczby samochodów. To naiwne podejście, o dziwo, może zadziałać.

Należy zauważyć, że dodatkowe dzielenie klastra przez potęgi dwójki w tym przypadku jest również optymalne. W każdym razie dodając 16 maszyn do klastra 16, jesteśmy zobowiązani do przesunięcia połowy danych – dokładnie połowy i przesunięcia.

No dobrze, ale czy naprawdę ludzkość nie wymyśliła niczego innego – pytanie rodzi się z dociekliwego umysłu.

Więcej zabawy #3. Konsekwentne haszowanie

Oczywiście wymagane jest tutaj zdjęcie z kółkiem o spójnym mieszaniu.

Jeśli wpiszesz w Google „spójne mieszanie”, to na pewno pojawi się kółko, wszystkie wyniki są wypełnione kółkami.

Pomysł: narysujmy identyfikatory fragmentów (haszy) na okręgu i zaznaczmy zahaszowane identyfikatory serwerów na górze. Kiedy trzeba dodać serwer, stawiamy nowy punkt na okręgu, a to, co okazało się być blisko niego (i tylko to, co okazało się być blisko niego), przenosimy.

Dodając shard: przeglądamy nie wszystko, ale tylko 2 „sąsiadów”, przesuwamy się średnio o 1/n.

Podczas usuwania sharda: patrzymy tylko na usuwany shard, tylko go przesuwamy. Taki optymalny.

Bardzo skuteczny pod względem minimalizacji ruchu podczas dodawania fragmentu i absolutnie obrzydliwy pod względem normalnego równoważenia danych. Ponieważ kiedy mieszamy wszystkie te obiekty, które rozdzielamy na dużą liczbę maszyn, robimy to stosunkowo nierównomiernie: punkty wokół okręgu są nierównomiernie rozmieszczone, a obciążenie każdego poszczególnego węzła może bardzo różnić się od pozostałych.

Ten problem rozwiązuje ostatnia linia węzła wirtualnego. Każdy węzeł, każdy serwer na okręgu jest oznaczony więcej niż jedną kropką. Dodając serwer, shard itp., dodajemy kilka punktów. Za każdym razem, gdy coś usuwamy, odpowiednio usuwamy kilka punktów i przesuwamy niewielką część danych.

Mówię o tej przestrzeni z kółkami, bo np. taki schemat jest wewnątrz Cassandry. To znaczy, kiedy zaczęła gonić rekordy między węzłami, wiedz, że koło patrzy na ciebie i prawdopodobnie nie aprobuje.

Jednak w porównaniu z pierwszymi metodami życie uległo poprawie – podczas dodawania/usuwania sharda przeglądamy już nie wszystkie rekordy, a tylko część, i przesuwamy tylko część.

Uwaga, pytanie brzmi: czy można to jeszcze poprawić? A także poprawić jednorodność ładowania odłamków? Mówią, że to możliwe!

Więcej zabawy #4. Spotkanie/HRW

Kolejny prosty pomysł (materiał ma charakter edukacyjny, więc nic skomplikowanego): shard_id = arg max hash(object_id, shard_id).

Dlaczego nazywa się to mieszaniem Rendezvous, nie wiem, ale wiem, dlaczego nazywa się to najwyższą losową wagą. Bardzo łatwo jest to zwizualizować w następujący sposób:

Mamy na przykład 16 odłamków. Dla każdego obiektu (ciągu znaków), który trzeba gdzieś umieścić, obliczamy 16 skrótów w zależności od obiektu z numeru sharda. Kto ma najwyższą wartość hash, wygrywa.

Jest to tak zwane haszowanie HRW, czyli haszowanie Rendezvous. Głupi jak kij, schemat obliczania liczby odłamków, po pierwsze, jest łatwiejszy dla oka niż koła, az drugiej strony zapewnia równomierne obciążenie.

Jedynym minusem jest to, że dodanie nowego odłamka pogorszyło się dla nas. Istnieje ryzyko, że przy dodawaniu nowego sharda wciąż mamy jakieś hasze, które ulegną zmianie i konieczne może być przejrzenie wszystkiego. Technologia usuwania odłamków niewiele się zmieniła.

Innym problemem jest to, że jest ciężki obliczeniowo z dużą liczbą odłamków.

Więcej zabawy #5. Więcej technik

Co ciekawe, badania nie stoją w miejscu i co roku Google publikuje nowe technologie kosmiczne:

  • Jump Hash – Google '2014.
  • Wiele sond — Google „2015.
  • Maglev-Google '2016.

Jeśli jesteś zainteresowany tematem, możesz przeczytać wiele rozpraw. Przedstawiam te dane, aby było jasne, że problem nie został rozwiązany, nie ma superrozwiązania, które można zaimplementować we wszystkich bazach danych. Do tej pory ludzie bronią prac dyplomowych.

wnioski

Istnieje ważna podstawowa technika zwana shardingiem, nazwana na cześć Galiusza Juliusza Cezara: „Dziel i rządź, rządź i dziel!”. Jeśli dane nie mieszczą się na jednym serwerze, konieczne jest podzielenie ich na 20 serwerów.

Dowiedziawszy się tego wszystkiego, należy odnieść wrażenie, że lepiej byłoby nie shardować. Jeśli zdecydujesz, że lepiej nie shardować, to jest właściwe uczucie. Jeśli możesz dodać pamięć do serwera za 100 USD i niczego nie shardować, powinieneś to zrobić. Podczas shardingu pojawi się złożony system rozproszony z przesyłaniem danych tam iz powrotem, układając dane w nie wiadomo gdzie. Jeśli można tego uniknąć, należy tego unikać.

Lepiej nie robić tego ręcznie, lepiej, żeby „baza” (wyszukiwanie, DFS, ...) mogła się shardować. W każdym razie prędzej czy później nadejdzie duże obciążenie i jakoś dane będą musiały zostać podzielone. Nie jest faktem, że nawet jeśli baza może to zrobić sama, nie napotkasz żadnych problemów. Pamiętaj o fundamentalizmie algorytmicznym – musisz zrozumieć, jak wszystko działa w środku.

Konfigurując sharding po raz pierwszy, ostrożnie wybierz F(), pomyśl o żądaniach, sieci itp. Ale przygotuj się, prawdopodobnie będziesz musiał wybrać 2 razy i przynajmniej raz będziesz musiał wszystko powtórzyć.