Nasi użytkownicy piszą do siebie wiadomości, nie czując zmęczenia.
To całkiem sporo. Jeśli zaczniesz czytać wszystkie wiadomości wszystkich użytkowników, zajmie to ponad 150 tysięcy lat. Pod warunkiem, że jesteś dość zaawansowanym czytelnikiem i poświęcasz na każdą wiadomość nie więcej niż sekundę.
Przy takiej ilości danych niezwykle istotne jest optymalne zbudowanie logiki ich przechowywania i dostępu do nich. W przeciwnym razie w jednym niezbyt cudownym momencie może się okazać, że wkrótce wszystko pójdzie nie tak.
Dla nas ten moment nadszedł półtora roku temu. Jak do tego doszliśmy i co się ostatecznie wydarzyło - mówimy po kolei.
Tło
Już w pierwszej implementacji wiadomości VKontakte działały na kombinacji backendu PHP i MySQL. Jest to zupełnie normalne rozwiązanie dla małej strony studenckiej. Jednak ta witryna rozrosła się w niekontrolowany sposób i zaczęła domagać się optymalizacji struktur danych dla siebie.
Pod koniec 2009 roku powstało pierwsze repozytorium silnika tekstowego, do którego w 2010 roku przenoszone były wiadomości.
W silniku tekstowym wiadomości były przechowywane na listach - rodzaj „skrzynek pocztowych”. Każda taka lista jest określona przez uid – użytkownika, który jest właścicielem wszystkich tych wiadomości. Wiadomość ma zestaw atrybutów: identyfikator rozmówcy, tekst, załączniki i tak dalej. Identyfikator wiadomości wewnątrz „boxa” to local_id, nigdy się nie zmienia i jest przypisywany sekwencyjnie nowym wiadomościom. „Skrzynki” są niezależne i nie są ze sobą synchronizowane wewnątrz silnika, komunikacja pomiędzy nimi odbywa się na poziomie PHP. Możesz przyjrzeć się strukturze danych i możliwościom silnika tekstowego od środka .
To wystarczyło do korespondencji między dwoma użytkownikami. Zgadnij, co stało się później?
W maju 2011 r. VKontakte wprowadziło rozmowy z kilkoma uczestnikami – multiczat. Aby z nimi współpracować, utworzyliśmy dwa nowe klastry - czaty członkowskie i członkowie czatu. Pierwszy przechowuje dane o czatach prowadzonych przez użytkowników, drugi przechowuje dane o użytkownikach poprzez czaty. Oprócz samych list obejmuje to na przykład zapraszającego użytkownika i godzinę jego dodania do czatu.
„PHP, wyślijmy wiadomość na czat” – mówi użytkownik.
„No dalej, {username}” – mówi PHP.
Ten schemat ma wady. Za synchronizację nadal odpowiada PHP. Duże czaty i użytkownicy, którzy jednocześnie wysyłają do nich wiadomości, to niebezpieczna historia. Ponieważ instancja silnika tekstowego zależy od identyfikatora użytkownika, uczestnicy czatu mogą otrzymać tę samą wiadomość w różnym czasie. Można by z tym żyć, gdyby postęp się zatrzymał. Ale to się nie stanie.
Pod koniec 2015 roku uruchomiliśmy komunikaty społecznościowe, a na początku 2016 roku uruchomiliśmy dla nich API. Wraz z pojawieniem się dużych chatbotów w społecznościach można było zapomnieć o równomiernym rozłożeniu obciążenia.
Dobry bot generuje kilka milionów wiadomości dziennie – nawet najbardziej gadatliwy użytkownik nie może się tym pochwalić. Oznacza to, że niektóre instancje silnika tekstowego, na którym żyły takie boty, zaczęły ucierpieć w pełni.
Silniki wiadomości w 2016 r. to 100 wystąpień członków czatu i czatów członkowskich oraz 8000 silników tekstowych. Hostowane były na tysiącu serwerów, każdy z 64 GB pamięci. Jako pierwszy środek awaryjny powiększyliśmy pamięć o kolejne 32 GB. Oszacowaliśmy prognozy. Bez drastycznych zmian wystarczyłoby to na około kolejny rok. Musisz albo zdobyć sprzęt, albo zoptymalizować same bazy danych.
Ze względu na naturę architektury sensowne jest jedynie wielokrotne zwiększanie sprzętu. Oznacza to przynajmniej podwojenie liczby samochodów - oczywiście jest to dość kosztowna ścieżka. Będziemy optymalizować.
Nowy koncept
Główną istotą nowego podejścia jest czat. Czat zawiera listę powiązanych z nim wiadomości. Użytkownik ma listę czatów.
Wymagane minimum to dwie nowe bazy danych:
- silnik czatu. To jest repozytorium wektorów czatu. Każdy czat ma wektor wiadomości, które się z nim wiążą. Każda wiadomość ma tekst i unikalny identyfikator wiadomości na czacie - chat_local_id.
- silnik użytkownika. To jest magazyn wektorów użytkowników - linków do użytkowników. Każdy użytkownik ma wektor peer_id (rozmówcy - inni użytkownicy, multi-czat lub społeczności) i wektor wiadomości. Każdy peer_id ma wektor powiązanych z nim komunikatów. Każda wiadomość ma chat_local_id i unikalny identyfikator wiadomości dla tego użytkownika - user_local_id.
Nowe klastry komunikują się ze sobą za pomocą protokołu TCP - gwarantuje to, że kolejność żądań nie ulegnie zmianie. Same żądania i potwierdzenia ich zapisywania zapisywane są na dysku twardym – dzięki temu w każdej chwili możemy przywrócić stan kolejki po awarii lub ponownym uruchomieniu silnika. Ponieważ silnik użytkownika i silnik czatu mają po 4 tysiące fragmentów każdy, kolejka żądań pomiędzy klastrami będzie rozłożona równomiernie (choć w rzeczywistości nie ma jej wcale - i działa to bardzo szybko).
Praca z dyskiem w naszych bazach danych w większości przypadków opiera się na połączeniu binarnego dziennika zmian (binlog), statycznych migawek i częściowego obrazu w pamięci. Zmiany w ciągu dnia są zapisywane w binlogu i okresowo tworzona jest migawka bieżącego stanu. Migawka to zbiór struktur danych zoptymalizowanych do naszych celów. Składa się z nagłówka (metaindex obrazu) i zestawu metaplików. Nagłówek jest trwale przechowywany w pamięci RAM i wskazuje, gdzie szukać danych ze migawki. Każdy metaplik zawiera dane, które mogą być potrzebne w określonym momencie — na przykład dotyczące pojedynczego użytkownika. Kiedy wysyłasz zapytanie do bazy danych za pomocą nagłówka migawki, odczytywany jest wymagany metaplik, a następnie brane są pod uwagę zmiany w dzienniku binarnym, które nastąpiły po utworzeniu migawki. Możesz przeczytać więcej o zaletach tego podejścia .
Jednocześnie dane na samym dysku twardym zmieniają się tylko raz dziennie - późno w nocy w Moskwie, kiedy obciążenie jest minimalne. Dzięki temu (wiedząc, że struktura na dysku jest stała przez cały dzień) możemy sobie pozwolić na zastąpienie wektorów tablicami o stałym rozmiarze – i dzięki temu zyskać na pamięci.
Wysłanie wiadomości w nowym schemacie wygląda następująco:
- Backend PHP kontaktuje się z silnikiem użytkownika z prośbą o wysłanie wiadomości.
- user-engine przekazuje żądanie do żądanej instancji chat-engine, która zwraca do user-engine chat_local_id - unikalny identyfikator nowej wiadomości na tym czacie. Następnie chat_engine rozsyła wiadomość do wszystkich odbiorców na czacie.
- user-engine otrzymuje chat_local_id od chat-engine i zwraca user_local_id do PHP - unikalny identyfikator wiadomości dla tego użytkownika. Identyfikator ten jest następnie wykorzystywany np. do pracy z wiadomościami poprzez API.
Ale oprócz faktycznego wysyłania wiadomości musisz wdrożyć kilka innych ważnych rzeczy:
- Podlisty to na przykład najnowsze wiadomości, które widzisz po otwarciu listy wątków. Nieprzeczytane wiadomości, wiadomości ze znacznikami („Ważne”, „Spam” itp.).
- Kompresja wiadomości w silniku czatu
- Buforowanie wiadomości w silniku użytkownika
- Szukaj (we wszystkich oknach dialogowych i w określonym).
- Aktualizacja w czasie rzeczywistym (Longpolling).
- Zapisywanie historii w celu wdrożenia buforowania na klientach mobilnych.
Wszystkie podlisty mają szybko zmieniającą się strukturę. Do pracy z nimi używamy . Wybór ten tłumaczymy tym, że na szczycie drzewa czasami przechowujemy cały segment wiadomości ze migawki - np. po nocnym reindeksowaniu drzewo składa się z jednego wierzchołka, który zawiera wszystkie wiadomości z podlisty. Drzewo Splay ułatwia wstawienie w środek takiego wierzchołka bez konieczności myślenia o balansowaniu. Dodatkowo Splay nie przechowuje zbędnych danych, co oszczędza nam pamięć.
Wiadomości zawierają dużą ilość informacji, głównie tekstu, który warto skompresować. Ważne jest, abyśmy mogli dokładnie rozarchiwizować nawet jedną pojedynczą wiadomość. Służy do kompresji wiadomości dzięki naszej własnej heurystyce - na przykład wiemy, że w wiadomościach słowa występują na przemian z „nie-słowami” - spacjami, znakami interpunkcyjnymi - pamiętamy też o niektórych osobliwościach używania symboli w języku rosyjskim.
Ponieważ użytkowników jest znacznie mniej niż na czatach, aby zapisać żądania dysku o dostępie swobodnym w silniku czatu, buforujemy wiadomości w silniku użytkowników.
Wyszukiwanie wiadomości jest realizowane jako zapytanie ukośne z silnika użytkownika do wszystkich instancji silnika czatu, które zawierają czaty tego użytkownika. Wyniki są łączone w samym silniku użytkownika.
Cóż, wszystkie szczegóły zostały wzięte pod uwagę, pozostaje tylko przejść na nowy schemat - i najlepiej tak, aby użytkownicy tego nie zauważyli.
Migracja danych
Mamy więc silnik tekstowy przechowujący wiadomości według użytkowników oraz dwa klastry członków czatu i czatów członków, które przechowują dane o pokojach z wieloma czatami i znajdujących się w nich użytkownikach. Jak przejść z tego do nowego silnika użytkownika i silnika czatu?
czaty członkowskie w starym schemacie służyły głównie do optymalizacji. Szybko przenieśliśmy z niego niezbędne dane do członków czatu, po czym nie brał on już udziału w procesie migracji.
Kolejka dla członków czatu. Zawiera 100 instancji, natomiast chat-engine ma 4 tys. Aby przenieść dane, należy je dostosować - w tym celu członkowie czatu zostali podzieleni na te same 4 tysiące kopii, a następnie w silniku czatu włączono odczytywanie binlogu członków czatu.
Teraz silnik czatu wie o wielokrotnym czacie z członkami czatu, ale nie wie jeszcze nic o dialogach z dwoma rozmówcami. Takie dialogi znajdują się w silniku tekstowym w odniesieniu do użytkowników. Tutaj wzięliśmy dane „od razu”: każda instancja silnika czatu pytała wszystkie instancje silnika tekstowego, czy mają potrzebny dialog.
Świetnie – silnik czatu wie, jakie są czaty wieloczatowe i wie, jakie są dialogi.
Musisz połączyć wiadomości w czatach wieloczatowych, aby otrzymać listę wiadomości w każdym czacie. Najpierw silnik czatu pobiera z silnika tekstowego wszystkie wiadomości użytkowników z tego czatu. W niektórych przypadkach jest ich całkiem sporo (nawet do setek milionów), ale z bardzo rzadkimi wyjątkami czat mieści się w całości w pamięci RAM. Mamy nieuporządkowane wiadomości, każda w kilku kopiach - w końcu wszystkie są pobierane z różnych instancji silnika tekstowego odpowiadających użytkownikom. Celem jest posortowanie wiadomości i pozbycie się kopii, które zajmują niepotrzebne miejsce.
Każda wiadomość posiada znacznik czasu zawierający godzinę wysłania i tekst. Czas wykorzystujemy do sortowania - umieszczamy wskaźniki do najstarszych wiadomości uczestników multichatu i porównujemy skróty z tekstów zamierzonych kopii, zmierzając w stronę zwiększania znacznika czasu. Logiczne jest, że kopie będą miały ten sam skrót i znacznik czasu, ale w praktyce nie zawsze tak jest. Jak pamiętacie, synchronizację w starym schemacie przeprowadzał PHP - i w rzadkich przypadkach czas wysłania tej samej wiadomości różnił się pomiędzy różnymi użytkownikami. W takich przypadkach pozwoliliśmy sobie na edycję znacznika czasu - zwykle w ciągu sekundy. Drugim problemem jest różna kolejność komunikatów dla różnych odbiorców. W takich przypadkach umożliwiliśmy utworzenie dodatkowej kopii z różnymi opcjami zamawiania dla różnych użytkowników.
Następnie dane o wiadomościach w multiczacie są wysyłane do silnika użytkownika. I tu pojawia się nieprzyjemna cecha importowanych wiadomości. Podczas normalnej pracy wiadomości przychodzące do silnika są uporządkowane ściśle w kolejności rosnącej według user_local_id. Wiadomości zaimportowane ze starego silnika do silnika użytkownika utraciły tę przydatną właściwość. Jednocześnie dla wygody testowania trzeba mieć możliwość szybkiego dostępu do nich, szukać w nich czegoś i dodawać nowe.
Do przechowywania zaimportowanych wiadomości używamy specjalnej struktury danych.
Reprezentuje wektor rozmiaru gdzie są wszyscy - są różne i uporządkowane w kolejności malejącej, ze specjalnym uporządkowaniem elementów. W każdym segmencie z indeksami elementy są sortowane. Poszukiwanie elementu w takiej konstrukcji wymaga czasu przez wyszukiwania binarne. Dodanie elementu jest amortyzowane .
Wymyśliliśmy więc, jak przenieść dane ze starych silników do nowych. Proces ten zajmuje jednak kilka dni i jest mało prawdopodobne, aby w tych dniach nasi użytkownicy porzucili nawyk pisania do siebie. Aby w tym czasie nie stracić wiadomości, przechodzimy na schemat pracy, który wykorzystuje zarówno stare, jak i nowe klastry.
Dane są zapisywane do członków czatu i silnika użytkownika (a nie do silnika tekstowego, jak podczas normalnego działania zgodnie ze starym schematem). silnik użytkownika przekazuje żądanie do silnika czatu - i tutaj zachowanie zależy od tego, czy ten czat został już połączony, czy nie. Jeśli czat nie został jeszcze połączony, silnik czatu nie zapisuje wiadomości do siebie, a jej przetwarzanie odbywa się tylko w silniku tekstowym. Jeśli czat został już połączony z silnikiem czatu, zwraca chat_local_id do silnika użytkownika i wysyła wiadomość do wszystkich odbiorców. user-engine przekazuje wszystkie dane do text-engine - dzięki czemu jeśli coś się stanie, zawsze możemy cofnąć dane, mając wszystkie aktualne dane w starym silniku. Text-Engine zwraca user_local_id, który silnik użytkownika przechowuje i zwraca do backendu.
W rezultacie proces przejścia wygląda następująco: łączymy puste klastry silnika użytkownika i silnika czatu. chat-engine czyta cały binlog członków czatu, następnie rozpoczyna się proxy zgodnie ze schematem opisanym powyżej. Przesyłamy stare dane i otrzymujemy dwa zsynchronizowane klastry (stary i nowy). Pozostaje tylko przełączyć odczyt z silnika tekstowego na silnik użytkownika i wyłączyć proxy.
wyniki
Dzięki nowemu podejściu poprawiono wszystkie wskaźniki wydajności silników i rozwiązano problemy ze spójnością danych. Teraz możemy szybko wdrażać nowe funkcje w wiadomościach (i już zaczęliśmy to robić - zwiększyliśmy maksymalną liczbę uczestników czatu, wdrożyliśmy wyszukiwanie przekazywanych wiadomości, uruchomiliśmy przypięte wiadomości i podnieśliśmy limit całkowitej liczby wiadomości na użytkownika) .
Zmiany w logice są naprawdę ogromne. I chciałbym zauważyć, że nie zawsze oznacza to całe lata rozwoju przez ogromny zespół i niezliczone linie kodu. silnik czatu i silnik użytkownika wraz ze wszystkimi dodatkowymi historiami, takimi jak Huffman do kompresji wiadomości, drzewa Splay i struktura importowanych wiadomości to mniej niż 20 tysięcy linii kodu. A napisało je 3 programistów w zaledwie 10 miesięcy (warto jednak o tym pamiętać - mistrzowie świata ).
Co więcej, zamiast podwoić liczbę serwerów, zmniejszyliśmy ich liczbę o połowę - teraz silnik użytkownika i silnik czatu działają na 500 fizycznych maszynach, podczas gdy nowy schemat ma dużą przestrzeń do obciążenia. Zaoszczędziliśmy dużo pieniędzy na sprzęcie – około 5 milionów dolarów + 750 tysięcy dolarów rocznie na kosztach operacyjnych.
Staramy się znaleźć najlepsze rozwiązania dla najbardziej złożonych i wielkoskalowych problemów. Mamy ich mnóstwo - dlatego poszukujemy utalentowanych programistów do działu baz danych. Jeśli lubisz i potrafisz rozwiązywać tego typu problemy, masz doskonałą wiedzę z zakresu algorytmów i struktur danych, zapraszamy Cię do dołączenia do zespołu. Skontaktuj się z nami , тобы узнать подробности.
Nawet jeśli ta historia nie dotyczy Ciebie, pamiętaj, że cenimy rekomendacje. Opowiedz o tym znajomemu , a jeśli pomyślnie ukończy okres próbny, otrzymasz premię w wysokości 100 tysięcy rubli.
Źródło: www.habr.com