Els nostres usuaris s'escriuen missatges entre ells sense saber-ne el cansament.
Això és bastant. Si us proposeu llegir tots els missatges de tots els usuaris, trigaria més de 150 mil anys. Sempre que siguis un lector bastant avançat i no dediquis més d'un segon a cada missatge.
Amb aquest volum de dades, és fonamental que la lògica per emmagatzemar-hi i accedir-hi es construeixi de manera òptima. En cas contrari, en un moment no tan meravellós, pot quedar clar que tot sortirà malament aviat.
Per a nosaltres, aquest moment va arribar fa un any i mig. Com vam arribar a això i què va passar al final, us ho expliquem per ordre.
Antecedents
En la primera implementació, els missatges de VKontakte van funcionar en una combinació de backend PHP i MySQL. Aquesta és una solució completament normal per a un lloc web d'estudiants petits. Tanmateix, aquest lloc va créixer sense control i va començar a exigir l'optimització de les estructures de dades per si mateix.
A finals de 2009, es va escriure el primer repositori de motor de text i el 2010 s'hi van transferir missatges.
Al motor de text, els missatges s'emmagatzemaven en llistes, una mena de "bústies de correu". Cada una d'aquestes llistes està determinada per un uid: l'usuari propietari de tots aquests missatges. Un missatge té un conjunt d'atributs: identificador de l'interlocutor, text, fitxers adjunts, etc. L'identificador del missatge dins de la "caixa" és local_id, no canvia mai i s'assigna seqüencialment per als missatges nous. Les "caixes" són independents i no estan sincronitzades entre elles dins del motor; la comunicació entre elles es produeix a nivell PHP. Podeu veure l'estructura de dades i les capacitats del motor de text des de dins .
Això era suficient per a la correspondència entre dos usuaris. Endevineu què va passar després?
El maig de 2011, VKontakte va introduir converses amb diversos participants: multi-xat. Per treballar amb ells, vam crear dos nous grups: xats de membres i membres de xat. El primer emmagatzema dades sobre xats per usuaris, el segon emmagatzema dades sobre usuaris per xats. A més de les llistes en si, això inclou, per exemple, l'usuari convidat i l'hora en què s'han afegit al xat.
"PHP, enviem un missatge al xat", diu l'usuari.
"Anem, {username}", diu PHP.
Aquest esquema té desavantatges. La sincronització encara és responsabilitat de PHP. Els grans xats i els usuaris que els envien missatges simultàniament són una història perillosa. Com que la instància del motor de text depèn de l'uid, els participants del xat podrien rebre el mateix missatge en diferents moments. Es podria viure amb això si el progrés s'atura. Però això no passarà.
A finals de 2015, vam llançar missatges de la comunitat i, a principis de 2016, vam llançar una API per a ells. Amb l'arribada dels grans chatbots a les comunitats, va ser possible oblidar-se de la distribució de la càrrega.
Un bon bot genera diversos milions de missatges al dia; fins i tot els usuaris més parlants no poden presumir d'això. Això significa que alguns casos de motor de text, en què vivien aquests robots, van començar a patir al màxim.
Els motors de missatges del 2016 són 100 instàncies de xats de membres i xats de membres, i 8000 motors de text. Estaven allotjades en mil servidors, cadascun amb 64 GB de memòria. Com a primera mesura d'emergència, hem augmentat la memòria en 32 GB més. Hem estimat les previsions. Sense canvis dràstics, això seria suficient per un any més. Heu de fer-vos amb el maquinari o optimitzar les bases de dades.
A causa de la naturalesa de l'arquitectura, només té sentit augmentar el maquinari en múltiples. És a dir, almenys duplicar el nombre de cotxes; òbviament, aquest és un camí força car. Optimitzarem.
Nou concepte
L'essència central del nou enfocament és el xat. Un xat té una llista de missatges relacionats amb ell. L'usuari té una llista de xats.
El mínim requerit són dues bases de dades noves:
- motor de xat. Aquest és un dipòsit de vectors de xat. Cada xat té un vector de missatges relacionats amb ell. Cada missatge té un text i un identificador de missatge únic dins del xat: chat_local_id.
- motor d'usuari. Aquest és un emmagatzematge de vectors d'usuaris: enllaços als usuaris. Cada usuari té un vector de peer_id (interlocutors - altres usuaris, multi-xat o comunitats) i un vector de missatges. Cada peer_id té un vector de missatges relacionats amb ell. Cada missatge té un chat_local_id i un ID de missatge únic per a aquest usuari: user_local_id.
Els nous clústers es comuniquen entre ells mitjançant TCP; això garanteix que l'ordre de les sol·licituds no canviï. Les sol·licituds i les confirmacions d'aquestes es registren al disc dur, de manera que podem restaurar l'estat de la cua en qualsevol moment després d'una fallada o reinici del motor. Com que el motor d'usuari i el motor de xat són 4 mil fragments cadascun, la cua de sol·licituds entre els clústers es distribuirà de manera uniforme (però en realitat no n'hi ha cap, i funciona molt ràpidament).
El treball amb el disc a les nostres bases de dades en la majoria dels casos es basa en una combinació d'un registre binari de canvis (binlog), instantànies estàtiques i una imatge parcial a la memòria. Els canvis durant el dia s'escriuen en un binlog i es crea periòdicament una instantània de l'estat actual. Una instantània és una col·lecció d'estructures de dades optimitzades per als nostres propòsits. Consisteix en una capçalera (metaíndex de la imatge) i un conjunt de metafitxers. La capçalera s'emmagatzema permanentment a la memòria RAM i indica on buscar dades de la instantània. Cada metafitxer inclou dades que és probable que es necessitin en moments propers, per exemple, relacionades amb un sol usuari. Quan consulteu la base de dades mitjançant la capçalera de la instantània, es llegeix el metafitxer requerit i, a continuació, es tenen en compte els canvis al binlog que es van produir després de crear la instantània. Podeu llegir més sobre els avantatges d'aquest enfocament .
Al mateix temps, les dades del propi disc dur canvien només un cop al dia, a la nit a Moscou, quan la càrrega és mínima. Gràcies a això (sabent que l'estructura del disc és constant durant tot el dia), ens podem permetre el luxe de substituir vectors per matrius de mida fixa i, per això, guanyar memòria.
L'enviament d'un missatge amb el nou esquema té aquest aspecte:
- El backend de PHP contacta amb el motor d'usuari amb una sol·licitud per enviar un missatge.
- user-engine envia la sol·licitud a la instància desitjada del motor de xat, que torna a user-engine chat_local_id: un identificador únic d'un missatge nou dins d'aquest xat. Aleshores, el chat_engine transmet el missatge a tots els destinataris del xat.
- user-engine rep chat_local_id del xat-engine i retorna user_local_id a PHP: un identificador de missatge únic per a aquest usuari. Aquest identificador s'utilitza, per exemple, per treballar amb missatges mitjançant l'API.
Però, a més d'enviar missatges, heu d'implementar algunes coses més importants:
- Les subllistes són, per exemple, els missatges més recents que veus en obrir la llista de converses. Missatges no llegits, missatges amb etiquetes (“Important”, “Spam”, etc.).
- Comprimint missatges al motor de xat
- Emmagatzemar missatges a la memòria cau al motor d'usuari
- Cerca (a través de tots els diàlegs i dins d'un de concret).
- Actualització en temps real (Longpolling).
- Desar l'historial per implementar la memòria cau als clients mòbils.
Totes les subllistes són estructures que canvien ràpidament. Per treballar amb ells fem servir . Aquesta elecció s'explica pel fet que a la part superior de l'arbre de vegades emmagatzemem tot un segment de missatges d'una instantània; per exemple, després de la reindexació nocturna, l'arbre consta d'una part superior, que conté tots els missatges de la subllista. L'arbre Splay facilita la inserció al mig d'aquest vèrtex sense haver de pensar en l'equilibri. A més, Splay no emmagatzema dades innecessàries, la qual cosa ens estalvia memòria.
Els missatges impliquen una gran quantitat d'informació, sobretot text, que és útil per poder comprimir. És important que puguem desarxivar amb precisió fins i tot un missatge individual. S'utilitza per comprimir missatges amb la nostra pròpia heurística -per exemple, sabem que en els missatges les paraules s'alternen amb "no paraules" -espais, signes de puntuació- i també recordem algunes de les peculiaritats de l'ús de símbols per a la llengua russa.
Com que hi ha molts menys usuaris que xats, per desar les sol·licituds de disc d'accés aleatori al motor de xat, deixem els missatges a la memòria cau a motor d'usuari.
La cerca de missatges s'implementa com una consulta en diagonal des del motor d'usuari a totes les instàncies del motor de xat que contenen xats d'aquest usuari. Els resultats es combinen en el propi motor d'usuari.
Bé, s'han tingut en compte tots els detalls, només queda canviar a un nou esquema -i preferiblement sense que els usuaris se n'adonin.
Migració de dades
Així doncs, tenim un motor de text que emmagatzema missatges per usuari i dos grups de xats de membres i xats de membres que emmagatzemen dades sobre sales de xat múltiples i els usuaris que hi ha. Com passar d'aquest al nou motor d'usuari i motor de xat?
Els xats de membres de l'antic esquema es van utilitzar principalment per a l'optimització. Vam transferir ràpidament les dades necessàries als membres del xat i després ja no va participar en el procés de migració.
Cua per als membres del xat. Inclou 100 instàncies, mentre que el motor de xat en té 4 mil. Per transferir les dades, heu de complir-les; per això, els membres del xat es van dividir en les mateixes 4 mil còpies i, a continuació, es va habilitar la lectura del binlog dels membres del xat al motor de xat.
Ara xat-engine sap sobre el xat múltiple dels membres del xat, però encara no sap res sobre els diàlegs amb dos interlocutors. Aquests diàlegs es troben al motor de text amb referència als usuaris. Aquí vam agafar les dades "de front": cada instància del motor de xat va demanar a totes les instàncies del motor de text si tenien el diàleg necessari.
Genial: el motor de xat sap quins xats de múltiples xats hi ha i sap quins diàlegs hi ha.
Heu de combinar missatges en xats de múltiples xats de manera que acabeu amb una llista de missatges a cada xat. En primer lloc, xat-engine recupera de text-engine tots els missatges d'usuari d'aquest xat. En alguns casos n'hi ha bastants (fins a centenars de milions), però amb excepcions molt rares, el xat s'adapta completament a la memòria RAM. Tenim missatges no ordenats, cadascun en diverses còpies; després de tot, tots s'extreuen de diferents instàncies de motor de text corresponents als usuaris. L'objectiu és ordenar els missatges i eliminar les còpies que ocupen espai innecessari.
Cada missatge té una marca de temps que conté l'hora en què s'ha enviat i el text. Utilitzem el temps per ordenar: col·loquem punters als missatges més antics dels participants del multichat i comparem els hashes del text de les còpies previstes, avançant cap a augmentar la marca de temps. És lògic que les còpies tinguin el mateix hash i marca de temps, però a la pràctica no sempre és així. Com recordeu, la sincronització a l'antic esquema la portava a terme PHP i, en casos rars, el temps d'enviament del mateix missatge variava entre els diferents usuaris. En aquests casos, ens vam permetre editar la marca de temps, normalment en un segon. El segon problema és el diferent ordre dels missatges per a diferents destinataris. En aquests casos, vam permetre que es creés una còpia addicional, amb diferents opcions de comanda per a diferents usuaris.
Després d'això, les dades sobre missatges en multixat s'envien al motor d'usuari. I aquí ve una característica desagradable dels missatges importats. En funcionament normal, els missatges que arriben al motor s'ordenen estrictament en ordre ascendent per user_local_id. Els missatges importats del motor antic al motor d'usuari van perdre aquesta propietat útil. Al mateix temps, per a la comoditat de les proves, cal poder accedir-hi ràpidament, buscar-hi alguna cosa i afegir-ne de noves.
Utilitzem una estructura de dades especial per emmagatzemar missatges importats.
Representa un vector de mida on és tothom - són diferents i ordenats en ordre descendent, amb un ordre especial d'elements. A cada segment amb índexs els elements estan ordenats. Cercar un element d'aquesta estructura requereix temps a través d' cerques binàries. L'addició d'un element s'amortitza .
Així doncs, vam descobrir com transferir dades de motors antics a nous. Però aquest procés dura diversos dies, i és poc probable que durant aquests dies els nostres usuaris renunciïn a l'hàbit d'escriure's entre ells. Per no perdre missatges durant aquest temps, canviem a un esquema de treball que utilitza clústers antics i nous.
Les dades s'escriuen als membres del xat i al motor d'usuari (i no al motor de text, com en el funcionament normal segons l'antic esquema). user-engine envia la sol·licitud a chat-engine, i aquí el comportament depèn de si aquest xat ja s'ha fusionat o no. Si el xat encara no s'ha combinat, el motor de xat no escriu el missatge a si mateix i el seu processament només es produeix al motor de text. Si el xat ja s'ha fusionat amb xat-engine, retorna chat_local_id a user-engine i envia el missatge a tots els destinataris. user-engine envia totes les dades a text-engine, de manera que si passa alguna cosa, sempre podem retrocedir, tenint totes les dades actuals al motor antic. text-engine retorna user_local_id, que user-engine emmagatzema i torna al backend.
Com a resultat, el procés de transició té aquest aspecte: connectem clústers buits de motor d'usuari i de xat. xat-engine llegeix tot el binlog dels membres del xat i, a continuació, s'inicia el proxy segons l'esquema descrit anteriorment. Transferim les dades antigues i obtenim dos clústers sincronitzats (vells i nous). Tot el que queda és canviar la lectura del motor de text al motor d'usuari i desactivar el proxy.
Troballes
Gràcies al nou enfocament, s'han millorat totes les mètriques de rendiment dels motors i s'han resolt els problemes de coherència de les dades. Ara podem implementar ràpidament noves funcions als missatges (i ja hem començat a fer-ho: hem augmentat el nombre màxim de participants al xat, hem implementat una cerca de missatges reenviats, hem llançat missatges fixats i hem augmentat el límit del nombre total de missatges per usuari) .
Els canvis de lògica són realment enormes. I m'agradaria assenyalar que això no sempre significa anys sencers de desenvolupament per part d'un gran equip i miríades de línies de codi. motor de xat i motor d'usuari juntament amb totes les històries addicionals com Huffman per a la compressió de missatges, arbres Splay i l'estructura dels missatges importats és inferior a 20 mil línies de codi. I van ser escrits per 3 desenvolupadors en només 10 mesos (no obstant això, val la pena tenir en compte que -campions del món ).
A més, en comptes de duplicar el nombre de servidors, vam reduir-ne el nombre a la meitat; ara el motor d'usuari i el motor de xat viuen en 500 màquines físiques, mentre que el nou esquema té un gran marge per a la càrrega. Hem estalviat molts diners en equips: uns 5 milions de dòlars + 750 mil dòlars anuals en despeses d'explotació.
Ens esforcem per trobar les millors solucions per als problemes més complexos i de gran escala. En tenim molts, i per això busquem desenvolupadors amb talent al departament de bases de dades. Si t'agrada i saps com resoldre aquests problemes, tens un excel·lent coneixement d'algorismes i estructures de dades, et convidem a unir-te a l'equip. Contacta amb el nostre per als detalls.
Encara que aquesta història no sigui sobre tu, tingues en compte que valorem les recomanacions. Explica'l a un amic , i si completa amb èxit el període de prova, rebràs una bonificació de 100 mil rubles.
Font: www.habr.com