Utilizatorii noștri își scriu mesaje unul altuia fără să cunoască oboseala.
Asta e destul de mult. Dacă ți-ai propus să citești toate mesajele tuturor utilizatorilor, ar dura mai mult de 150 de mii de ani. Cu condiția să fiți un cititor destul de avansat și să nu petreceți mai mult de o secundă pentru fiecare mesaj.
Cu un astfel de volum de date, este esențial ca logica de stocare și accesare a acestora să fie construită în mod optim. Altfel, într-un moment nu atât de minunat, poate deveni clar că totul va merge prost în curând.
Pentru noi, acest moment a venit acum un an și jumătate. Cum am ajuns la asta și ce s-a întâmplat până la urmă - vă spunem în ordine.
anamneză
În prima implementare, mesajele VKontakte au funcționat pe o combinație de backend PHP și MySQL. Aceasta este o soluție complet normală pentru un site web pentru studenți mici. Cu toate acestea, acest site a crescut necontrolat și a început să solicite optimizarea structurilor de date pentru sine.
La sfârșitul anului 2009, a fost scris primul depozit de motor de text, iar în 2010 mesajele au fost transferate în acesta.
În motorul de text, mesajele erau stocate în liste - un fel de „cutii poștale”. Fiecare astfel de listă este determinată de un uid - utilizatorul care deține toate aceste mesaje. Un mesaj are un set de atribute: identificatorul interlocutorului, textul, atașamentele și așa mai departe. Identificatorul mesajului din interiorul „casetei” este local_id, nu se modifică niciodată și este atribuit secvenţial pentru mesajele noi. „Cutiile” sunt independente și nu sunt sincronizate între ele în interiorul motorului; comunicarea între ele are loc la nivel PHP. Puteți privi structura datelor și capacitățile motorului de text din interior .
Acest lucru a fost suficient pentru corespondența dintre doi utilizatori. Ghici ce s-a întâmplat mai departe?
În mai 2011, VKontakte a introdus conversații cu mai mulți participanți – multi-chat. Pentru a lucra cu ei, am creat două noi grupuri - membri-chat și membri-chat. Primul stochează date despre chat-uri de către utilizatori, al doilea stochează date despre utilizatori prin chat-uri. Pe lângă listele în sine, aceasta include, de exemplu, utilizatorul care a invitat și ora la care a fost adăugat la chat.
„PHP, hai să trimitem un mesaj pe chat”, spune utilizatorul.
„Hai, {username}”, spune PHP.
Există dezavantaje în această schemă. Sincronizarea este încă responsabilitatea PHP. Chaturile mari și utilizatorii care le trimit simultan mesaje sunt o poveste periculoasă. Deoarece instanța motorului de text depinde de uid, participanții la chat pot primi același mesaj în momente diferite. S-ar putea trăi cu asta dacă progresul s-ar opri. Dar asta nu se va întâmpla.
La sfârșitul anului 2015, am lansat mesaje comunitare, iar la începutul lui 2016, am lansat un API pentru ei. Odată cu apariția chatbot-urilor mari în comunități, a fost posibil să uităm de distribuția uniformă a încărcăturii.
Un bot bun generează câteva milioane de mesaje pe zi - chiar și cei mai vorbăreți utilizatori nu se pot lăuda cu asta. Aceasta înseamnă că unele cazuri de motor text, pe care au trăit astfel de roboți, au început să sufere din plin.
Motoarele de mesaje din 2016 sunt 100 de instanțe de membri de chat și chat-uri de membri și 8000 de motoare de text. Au fost găzduite pe o mie de servere, fiecare cu 64 GB de memorie. Ca primă măsură de urgență, am mărit memoria cu încă 32 GB. Am estimat prognozele. Fără schimbări drastice, acest lucru ar fi suficient pentru încă un an. Trebuie fie să puneți mâna pe hardware, fie să optimizați bazele de date în sine.
Datorită naturii arhitecturii, are sens doar creșterea hardware-ului în multipli. Adică, cel puțin dublarea numărului de mașini - evident, aceasta este o cale destul de costisitoare. Vom optimiza.
Concept nou
Esența centrală a noii abordări este chatul. Un chat are o listă de mesaje care se referă la el. Utilizatorul are o listă de chat-uri.
Minimul necesar este de două baze de date noi:
- motor de chat. Acesta este un depozit de vectori de chat. Fiecare chat are un vector de mesaje care se referă la el. Fiecare mesaj are un text și un identificator unic de mesaj în interiorul chat-ului - chat_local_id.
- utilizator-motor. Aceasta este o stocare a vectorilor utilizatorilor - link-uri către utilizatori. Fiecare utilizator are un vector de peer_id (interlocutori - alți utilizatori, multi-chat sau comunități) și un vector de mesaje. Fiecare peer_id are un vector de mesaje care se referă la el. Fiecare mesaj are un chat_local_id și un ID unic de mesaj pentru acel utilizator - user_local_id.
Noile clustere comunică între ele folosind TCP - acest lucru asigură că ordinea solicitărilor nu se schimbă. Solicitările în sine și confirmările pentru ele sunt înregistrate pe hard disk - astfel încât să putem restabili starea cozii în orice moment după o defecțiune sau repornire a motorului. Deoarece motorul utilizatorului și motorul de chat sunt 4 mii de fragmente fiecare, coada de solicitări între clustere va fi distribuită uniform (dar în realitate nu există deloc - și funcționează foarte repede).
Lucrul cu discul din bazele noastre de date se bazează în cele mai multe cazuri pe o combinație între un jurnal binar de modificări (binlog), instantanee statice și o imagine parțială în memorie. Modificările din timpul zilei sunt scrise într-un binlog și se creează periodic un instantaneu al stării curente. Un instantaneu este o colecție de structuri de date optimizate pentru scopurile noastre. Este format dintr-un antet (metaindex al imaginii) și un set de metafișiere. Antetul este stocat permanent în RAM și indică unde să caute datele din instantaneu. Fiecare metafișier include date care probabil vor fi necesare în momente apropiate – de exemplu, legate de un singur utilizator. Când interogați baza de date utilizând antetul instantaneului, metafișierul necesar este citit și apoi sunt luate în considerare modificările din jurnalul de date care au avut loc după crearea instantaneului. Puteți citi mai multe despre beneficiile acestei abordări .
În același timp, datele de pe hard disk în sine se schimbă o singură dată pe zi - noaptea târziu la Moscova, când încărcarea este minimă. Datorită acestui fapt (știind că structura de pe disc este constantă pe tot parcursul zilei), ne putem permite să înlocuim vectorii cu matrice de dimensiune fixă - și datorită acestui fapt, câștigăm în memorie.
Trimiterea unui mesaj în noua schemă arată astfel:
- Backend-ul PHP contactează motorul utilizatorului cu o solicitare de a trimite un mesaj.
- user-engine trimite cererea către instanța dorită a motorului de chat, care revine la user-engine chat_local_id - un identificator unic al unui mesaj nou din acest chat. Chat_engine transmite apoi mesajul către toți destinatarii din chat.
- user-engine primește chat_local_id de la chat-engine și returnează user_local_id la PHP - un identificator unic de mesaj pentru acest utilizator. Acest identificator este apoi folosit, de exemplu, pentru a lucra cu mesaje prin intermediul API-ului.
Dar, pe lângă trimiterea efectivă a mesajelor, trebuie să implementați câteva lucruri mai importante:
- Sublistele sunt, de exemplu, cele mai recente mesaje pe care le vedeți când deschideți lista de conversații. Mesaje necitite, mesaje cu etichete („Important”, „Spam”, etc.).
- Comprimarea mesajelor în motorul de chat
- Memorarea în cache a mesajelor în motorul utilizatorului
- Căutați (prin toate casetele de dialog și într-una anume).
- Actualizare în timp real (Longpolling).
- Salvarea istoricului pentru a implementa memorarea în cache pe clienții mobili.
Toate sublistele sunt structuri în schimbare rapidă. Pentru a lucra cu ei folosim . Această alegere se explică prin faptul că în partea de sus a arborelui stocăm uneori un întreg segment de mesaje dintr-un instantaneu - de exemplu, după reindexarea nocturnă, arborele constă dintr-un top, care conține toate mesajele sublistei. Arborele Splay facilitează inserarea în mijlocul unui astfel de vârf fără a fi nevoie să se gândească la echilibrare. În plus, Splay nu stochează date inutile, ceea ce ne economisește memorie.
Mesajele implică o cantitate mare de informații, mai ales text, care este utilă pentru a putea comprima. Este important să putem dezarhiva cu exactitate chiar și un singur mesaj individual. Folosit pentru comprimarea mesajelor cu propria noastră euristică - de exemplu, știm că în mesaje cuvintele alternează cu „non-cuvinte” - spații, semne de punctuație - și ne amintim, de asemenea, unele dintre particularitățile utilizării simbolurilor pentru limba rusă.
Deoarece există mult mai puțini utilizatori decât chat-uri, pentru a salva solicitările de disc cu acces aleatoriu în chat-engine, memorăm mesajele în cache în user-engine.
Căutarea de mesaje este implementată ca o interogare diagonală de la motorul utilizatorului la toate instanțele motorului de chat care conțin chat-uri ale acestui utilizator. Rezultatele sunt combinate în motorul utilizatorului însuși.
Ei bine, toate detaliile au fost luate în considerare, tot ce rămâne este să trecem la o nouă schemă - și de preferință fără ca utilizatorii să o observe.
Migratia datelor
Deci, avem un motor de text care stochează mesajele în funcție de utilizator și două grupuri de membri de chat și chat-uri de membri care stochează date despre camerele multi-chat și utilizatorii din ele. Cum să treci de la acesta la noul motor de utilizator și motor de chat?
chat-urile pentru membri în vechea schemă a fost folosită în primul rând pentru optimizare. Am transferat rapid datele necesare de la acesta către membrii de chat și apoi nu a mai participat la procesul de migrare.
Coadă pentru membrii de chat. Include 100 de instanțe, în timp ce chat-engine are 4 mii. Pentru a transfera datele, trebuie să le aduceți în conformitate - pentru aceasta, membrii de chat au fost împărțiți în aceleași 4 mii de copii, iar apoi citirea jurnalului de membri ai chat-ului a fost activată în motorul de chat.
Acum chat-engine știe despre multi-chat de la membrii de chat, dar încă nu știe nimic despre dialogurile cu doi interlocutori. Astfel de dialoguri sunt localizate în motorul de text cu referire la utilizatori. Aici am luat datele „direct”: fiecare instanță a motorului de chat a întrebat toate instanțele motorului de text dacă au dialogul necesar.
Excelent - motorul de chat știe ce chat-uri multi-chat există și știe ce dialoguri există.
Trebuie să combinați mesajele în chat-uri multi-chat, astfel încât să ajungeți cu o listă de mesaje în fiecare chat. În primul rând, chat-engine preia din text-engine toate mesajele utilizatorului din acest chat. În unele cazuri, există destul de multe (până la sute de milioane), dar, cu excepții foarte rare, chat-ul se potrivește în întregime în RAM. Avem mesaje neordonate, fiecare în mai multe copii - la urma urmei, toate sunt extrase din diferite instanțe de motor de text corespunzătoare utilizatorilor. Scopul este de a sorta mesajele și de a scăpa de copiile care ocupă spațiu inutil.
Fiecare mesaj are o marca temporală care conține ora la care a fost trimis și text. Folosim timpul pentru sortare - plasăm indicatori către cele mai vechi mesaje ale participanților la multichat și comparăm hash-urile din textul copiilor dorite, trecând spre creșterea marcajului de timp. Este logic ca copiile să aibă același hash și timestamp, dar în practică nu este întotdeauna cazul. După cum vă amintiți, sincronizarea în vechea schemă a fost efectuată de PHP - și, în cazuri rare, timpul de trimitere a aceluiași mesaj a diferit între diferiți utilizatori. În aceste cazuri, ne-am permis să edităm marcajul de timp - de obicei într-o secundă. A doua problemă este ordinea diferită a mesajelor pentru diferiți destinatari. În astfel de cazuri, am permis crearea unei copii suplimentare, cu diferite opțiuni de comandă pentru diferiți utilizatori.
După aceasta, datele despre mesajele din multichat sunt trimise către motorul utilizatorului. Și aici intervine o caracteristică neplăcută a mesajelor importate. În funcționarea normală, mesajele care vin la motor sunt ordonate strict crescător după user_local_id. Mesajele importate din vechiul motor în motorul utilizatorului au pierdut această proprietate utilă. În același timp, pentru confortul testării, trebuie să le puteți accesa rapid, să căutați ceva în ele și să adăugați altele noi.
Folosim o structură specială de date pentru a stoca mesajele importate.
Reprezintă un vector de mărime unde este toata lumea - sunt diferite și ordonate în ordine descrescătoare, cu o ordine specială a elementelor. În fiecare segment cu indici elementele sunt sortate. Căutarea unui element într-o astfel de structură necesită timp prin căutări binare. Adăugarea unui element este amortizată peste .
Așadar, ne-am dat seama cum să transferăm date de la motoarele vechi la cele noi. Dar acest proces durează câteva zile - și este puțin probabil ca în aceste zile utilizatorii noștri să renunțe la obiceiul de a se scrie unul altuia. Pentru a nu pierde mesaje în acest timp, trecem la o schemă de lucru care utilizează atât clustere vechi, cât și noi.
Datele sunt scrise pentru membrii de chat și motorul utilizatorului (și nu în motorul de text, ca în funcționarea normală conform schemei vechi). user-engine trimite cererea către chat-engine - iar aici comportamentul depinde dacă acest chat a fost deja îmbinat sau nu. Dacă chat-ul nu a fost încă îmbinat, motorul de chat nu scrie mesajul în sine, iar procesarea lui are loc numai în motorul de text. Dacă chat-ul a fost deja îmbinat în chat-engine, acesta returnează chat_local_id la user-engine și trimite mesajul tuturor destinatarilor. user-engine trimite toate datele către text-engine - astfel încât, dacă se întâmplă ceva, putem întotdeauna să revenim înapoi, având toate datele curente în vechiul motor. text-engine returnează user_local_id, pe care user-engine îl stochează și revine la backend.
Ca rezultat, procesul de tranziție arată astfel: conectăm clustere goale de motor de utilizator și de chat. chat-engine citește întregul jurnal al membrilor chat-ului, apoi începe proxy-ul conform schemei descrise mai sus. Transferăm datele vechi și obținem două clustere sincronizate (vechi și noi). Tot ce rămâne este să comutați citirea de la motorul de text la motorul utilizatorului și să dezactivați proxy-ul.
Constatări
Datorită noii abordări, toate valorile de performanță ale motoarelor au fost îmbunătățite și problemele legate de consistența datelor au fost rezolvate. Acum putem implementa rapid noi funcții în mesaje (și am început deja să facem acest lucru - am crescut numărul maxim de participanți la chat, am implementat o căutare pentru mesaje redirecționate, am lansat mesaje fixate și am crescut limita pentru numărul total de mesaje per utilizator) .
Schimbările de logică sunt cu adevărat enorme. Și aș dori să observ că acest lucru nu înseamnă întotdeauna ani întregi de dezvoltare de către o echipă uriașă și nenumărate linii de cod. chat-engine și user-engine, împreună cu toate poveștile suplimentare, cum ar fi Huffman pentru compresia mesajelor, arbori Splay și structura pentru mesajele importate, are mai puțin de 20 de mii de linii de cod. Și au fost scrise de 3 dezvoltatori în doar 10 luni (cu toate acestea, merită să rețineți că - campioni mondiali ).
Mai mult decât atât, în loc să dublăm numărul de servere, am redus numărul acestora la jumătate - acum motorul utilizatorului și motorul de chat trăiesc pe 500 de mașini fizice, în timp ce noua schemă are un spațiu mare pentru încărcare. Am economisit o mulțime de bani pe echipamente - aproximativ 5 milioane $ + 750 mii $ pe an în cheltuieli de exploatare.
Ne străduim să găsim cele mai bune soluții pentru problemele cele mai complexe și de amploare. Avem o mulțime de ei - și de aceea căutăm dezvoltatori talentați în departamentul de baze de date. Daca iubesti si stii sa rezolvi astfel de probleme, ai cunostinte excelente de algoritmi si structuri de date, te invitam sa te alaturi echipei. Contactați-ne pentru detalii.
Chiar dacă această poveste nu este despre tine, te rugăm să reții că prețuim recomandările. Spune-i unui prieten despre , iar dacă termină cu succes perioada de probă, vei primi un bonus de 100 de mii de ruble.
Sursa: www.habr.com