Riscrivi da zero il database dei messaggi VKontakte e sopravvivi

I nostri utenti si scrivono messaggi senza conoscere la fatica.

È parecchio. Se ti mettessi a leggere tutti i messaggi di tutti gli utenti, ci vorrebbero più di 150mila anni. A condizione che tu sia un lettore abbastanza avanzato e non dedichi più di un secondo a ciascun messaggio.

Con un tale volume di dati, è fondamentale che la logica per archiviarli e accedervi sia costruita in modo ottimale. Altrimenti, in un momento non così meraviglioso, potrebbe diventare chiaro che presto tutto andrà storto.

Per noi questo momento è arrivato un anno e mezzo fa. Come siamo arrivati ​​a questo e cosa è successo alla fine - te lo diciamo in ordine.

case history

Nella primissima implementazione, i messaggi VKontakte funzionavano su una combinazione di backend PHP e MySQL. Questa è una soluzione del tutto normale per un sito web di piccoli studenti. Tuttavia, questo sito è cresciuto in modo incontrollabile e ha iniziato a richiedere per sé l'ottimizzazione delle strutture dei dati.

Alla fine del 2009 è stato scritto il primo repository con motore di testo e nel 2010 vi sono stati trasferiti i messaggi.

Nel motore di testo, i messaggi venivano archiviati in elenchi, una sorta di "cassette postali". Ciascuno di questi elenchi è determinato da un uid: l'utente che possiede tutti questi messaggi. Un messaggio ha una serie di attributi: identificatore dell'interlocutore, testo, allegati e così via. L'identificativo del messaggio all'interno della “box” è local_id, non cambia mai e viene assegnato in sequenza per i nuovi messaggi. I “box” sono indipendenti e non sono sincronizzati tra loro all’interno del motore; la comunicazione tra loro avviene a livello PHP. Puoi osservare la struttura dei dati e le capacità del motore di testo dall'interno qui.

Questo era abbastanza per la corrispondenza tra due utenti. INDOVINA cosa è successo dopo?

Nel maggio 2011, VKontakte ha introdotto le conversazioni con più partecipanti: la multichat. Per lavorare con loro, abbiamo creato due nuovi cluster: chat-membri e membri-chat. Il primo memorizza i dati sulle chat degli utenti, il secondo memorizza i dati sugli utenti per chat. Oltre agli elenchi stessi, ciò include, ad esempio, l'utente che ha invitato e l'ora in cui è stato aggiunto alla chat.

"PHP, inviamo un messaggio alla chat", dice l'utente.
"Dai, {nomeutente}", dice PHP.

Ci sono degli svantaggi in questo schema. La sincronizzazione è ancora responsabilità di PHP. Le chat di grandi dimensioni e gli utenti che inviano loro messaggi contemporaneamente sono una storia pericolosa. Poiché l'istanza del motore di testo dipende dall'uid, i partecipanti alla chat potrebbero ricevere lo stesso messaggio in momenti diversi. Si potrebbe convivere con questo se il progresso si fermasse. Ma ciò non accadrà.

Alla fine del 2015 abbiamo lanciato i messaggi della community e all'inizio del 2016 abbiamo lanciato un'API per loro. Con l’avvento dei grandi chatbot nelle comunità, è stato possibile dimenticare la distribuzione uniforme del carico.

Un buon bot genera diversi milioni di messaggi al giorno: anche gli utenti più loquaci non possono vantarsene. Ciò significa che alcune istanze del motore di testo su cui vivevano tali robot hanno iniziato a soffrire in pieno.

I motori di messaggio nel 2016 sono 100 istanze di membri di chat e chat di membri e 8000 motori di testo. Erano ospitati su mille server, ciascuno con 64 GB di memoria. Come prima misura d'emergenza abbiamo aumentato la memoria di altri 32 GB. Abbiamo stimato le previsioni. Senza cambiamenti drastici, questo basterebbe per circa un altro anno. È necessario procurarsi l'hardware o ottimizzare i database stessi.

A causa della natura dell'architettura, ha senso aumentare l'hardware solo in multipli. Cioè, almeno raddoppiando il numero di auto: ovviamente questo è un percorso piuttosto costoso. Ottimizzeremo.

Nuovo concetto

L'essenza centrale del nuovo approccio è la chat. Una chat ha un elenco di messaggi ad essa correlati. L'utente ha un elenco di chat.

Il minimo richiesto è due nuovi database:

• motore di chat. Questo è un archivio di vettori di chat. Ogni chat ha un vettore di messaggi ad essa correlati. Ogni messaggio ha un testo e un identificatore di messaggio univoco all'interno della chat: chat_local_id.
• motore-utente. Questa è una memorizzazione dei vettori degli utenti: collegamenti agli utenti. Ogni utente ha un vettore di peer_id (interlocutori - altri utenti, multi-chat o community) e un vettore di messaggi. Ogni peer_id ha un vettore di messaggi ad esso correlato. Ogni messaggio ha un chat_local_id e un ID messaggio univoco per quell'utente: user_local_id.

I nuovi cluster comunicano tra loro tramite TCP: ciò garantisce che l'ordine delle richieste non cambi. Le richieste stesse e le relative conferme vengono registrate sul disco rigido, in modo da poter ripristinare lo stato della coda in qualsiasi momento dopo un guasto o un riavvio del motore. Poiché il motore utente e il motore chat sono 4mila frammenti ciascuno, la coda delle richieste tra i cluster sarà distribuita uniformemente (ma in realtà non ce n'è affatto - e funziona molto rapidamente).

Il lavoro con il disco nei nostri database nella maggior parte dei casi si basa su una combinazione di un registro binario delle modifiche (binlog), istantanee statiche e un'immagine parziale in memoria. Le modifiche durante il giorno vengono scritte in un binlog e periodicamente viene creata un'istantanea dello stato corrente. Uno snapshot è una raccolta di strutture dati ottimizzate per i nostri scopi. È costituito da un'intestazione (metaindice dell'immagine) e da un insieme di metafile. L'intestazione viene archiviata in modo permanente nella RAM e indica dove cercare i dati dallo snapshot. Ogni metafile include dati che potrebbero essere necessari in momenti ravvicinati nel tempo, ad esempio relativi a un singolo utente. Quando si esegue una query sul database utilizzando l'intestazione dello snapshot, viene letto il metafile richiesto e quindi vengono prese in considerazione le modifiche nel binlog verificatesi dopo la creazione dello snapshot. Puoi leggere di più sui vantaggi di questo approccio qui.

Allo stesso tempo, i dati sul disco rigido stesso cambiano solo una volta al giorno, a tarda notte a Mosca, quando il carico è minimo. Grazie a ciò (sapendo che la struttura sul disco è costante durante il giorno), possiamo permetterci di sostituire i vettori con array di dimensione fissa e, di conseguenza, guadagnare memoria.

L'invio di un messaggio nel nuovo schema è simile al seguente:

1. Il backend PHP contatta il motore utente con una richiesta di inviare un messaggio.
2. user-engine inoltra la richiesta all'istanza del motore di chat desiderata, che restituisce l'user-engine chat_local_id, un identificatore univoco di un nuovo messaggio all'interno di questa chat. Il chat_engine trasmette quindi il messaggio a tutti i destinatari nella chat.
3. user-engine riceve chat_local_id da chat-engine e restituisce user_local_id a PHP, un identificatore di messaggio univoco per questo utente. Questo identificatore viene poi utilizzato, ad esempio, per lavorare con i messaggi tramite l'API.

Ma oltre a inviare effettivamente i messaggi, devi implementare alcune cose più importanti:

• Le sottoliste sono, ad esempio, i messaggi più recenti che vedi quando apri l'elenco delle conversazioni. Messaggi non letti, messaggi con tag (“Importante”, “Spam”, ecc.).
• Compressione dei messaggi nel motore di chat
• Memorizzazione nella cache dei messaggi nel motore utente
• Cerca (attraverso tutte le finestre di dialogo e all'interno di una specifica).
• Aggiornamento in tempo reale (Longpolling).
• Salvataggio della cronologia per implementare la memorizzazione nella cache sui client mobili.

Tutte le sottoliste stanno cambiando rapidamente struttura. Per lavorare con loro usiamo Allarga gli alberi. Questa scelta è spiegata dal fatto che nella parte superiore dell'albero a volte memorizziamo un intero segmento di messaggi da un'istantanea - ad esempio, dopo la reindicizzazione notturna, l'albero è costituito da una parte superiore, che contiene tutti i messaggi della sottolista. L'albero Splay facilita l'inserimento al centro di tale vertice senza dover pensare al bilanciamento. Inoltre, Splay non memorizza dati non necessari, il che ci fa risparmiare memoria.

I messaggi contengono una grande quantità di informazioni, principalmente testo, che è utile poter comprimere. È importante poter estrarre con precisione dall'archivio anche un singolo messaggio. Utilizzato per comprimere i messaggi Algoritmo di Huffman con la nostra euristica - ad esempio, sappiamo che nei messaggi le parole si alternano a “non parole” - spazi, segni di punteggiatura - e ricordiamo anche alcune caratteristiche dell'uso dei simboli per la lingua russa.

Poiché ci sono molti meno utenti rispetto alle chat, per salvare le richieste del disco ad accesso casuale nel motore di chat, memorizziamo nella cache i messaggi nel motore dell'utente.

La ricerca dei messaggi è implementata come una query diagonale dal motore utente a tutte le istanze del motore di chat che contengono le chat di questo utente. I risultati vengono combinati nel motore utente stesso.

Bene, tutti i dettagli sono stati presi in considerazione, non resta che passare al nuovo schema - e preferibilmente senza che gli utenti se ne accorgano.

Migrazione dei dati

Quindi, abbiamo un motore di testo che memorizza i messaggi per utente e due cluster membri della chat e chat dei membri che memorizzano i dati sulle stanze multi-chat e sugli utenti in esse. Come passare da questo al nuovo motore utente e motore di chat?

le chat dei membri nel vecchio schema venivano utilizzate principalmente per l'ottimizzazione. Abbiamo trasferito rapidamente i dati necessari da esso ai membri della chat e quindi non ha più partecipato al processo di migrazione.

Coda per i membri della chat. Comprende 100 istanze, mentre il motore di chat ne ha 4mila. Per trasferire i dati, è necessario renderli conformi: per questo, i membri della chat sono stati divisi nelle stesse 4mila copie, e quindi la lettura del binlog dei membri della chat è stata abilitata nel motore della chat.

Ora il motore di chat conosce la multichat dei membri della chat, ma non sa ancora nulla dei dialoghi con due interlocutori. Tali dialoghi si trovano nel motore di testo con riferimento agli utenti. Qui abbiamo preso i dati “frontalmente”: ciascuna istanza del motore di chat ha chiesto a tutte le istanze del motore di testo se avevano il dialogo di cui avevano bisogno.

Fantastico: il motore di chat sa quali chat multi-chat ci sono e quali dialoghi ci sono.
Devi combinare i messaggi nelle chat multi-chat in modo da ottenere un elenco di messaggi in ciascuna chat. Innanzitutto, il motore di chat recupera dal motore di testo tutti i messaggi degli utenti da questa chat. In alcuni casi ce ne sono parecchi (fino a centinaia di milioni), ma con rarissime eccezioni la chat si inserisce interamente nella RAM. Abbiamo messaggi non ordinati, ciascuno in più copie: dopo tutto, sono tutti estratti da diverse istanze del motore di testo corrispondenti agli utenti. L'obiettivo è ordinare i messaggi ed eliminare le copie che occupano spazio non necessario.

Ogni messaggio ha un timestamp contenente l'ora in cui è stato inviato e il testo. Usiamo il tempo per l'ordinamento: inseriamo puntatori ai messaggi più vecchi dei partecipanti multichat e confrontiamo gli hash dal testo delle copie previste, spostandoci verso un timestamp crescente. È logico che le copie abbiano lo stesso hash e timestamp, ma in pratica non è sempre così. Come ricorderete, la sincronizzazione nel vecchio schema veniva eseguita da PHP e, in rari casi, il tempo di invio dello stesso messaggio differiva tra i diversi utenti. In questi casi, ci siamo permessi di modificare il timestamp, di solito entro un secondo. Il secondo problema è il diverso ordine dei messaggi per i diversi destinatari. In questi casi, abbiamo consentito la creazione di una copia aggiuntiva, con diverse opzioni di ordinazione per diversi utenti.

Successivamente, i dati sui messaggi in multichat vengono inviati al motore utente. E qui entra in gioco una caratteristica spiacevole dei messaggi importati. Durante il normale funzionamento, i messaggi che arrivano al motore sono ordinati rigorosamente in ordine crescente in base a user_local_id. I messaggi importati dal vecchio motore nel motore utente hanno perso questa utile proprietà. Allo stesso tempo, per comodità dei test, devi essere in grado di accedervi rapidamente, cercare qualcosa al loro interno e aggiungerne di nuovi.

Utilizziamo una struttura dati speciale per archiviare i messaggi importati.

Rappresenta un vettore di dimensione dove sono tutti - sono diversi e ordinati in ordine decrescente, con un ordine speciale degli elementi. In ogni segmento con indici gli elementi sono ordinati. La ricerca di un elemento in una struttura del genere richiede tempo attraverso ricerche binarie. L'aggiunta di un elemento viene ammortizzata .

Quindi, abbiamo capito come trasferire i dati dai vecchi motori a quelli nuovi. Ma questo processo richiede diversi giorni ed è improbabile che durante questi giorni i nostri utenti rinuncino all'abitudine di scriversi. Per non perdere messaggi in questo periodo passiamo ad uno schema di lavoro che utilizza sia i vecchi che i nuovi cluster.

I dati vengono scritti nei membri della chat e nel motore utente (e non nel motore di testo, come nel normale funzionamento secondo il vecchio schema). user-engine inoltra la richiesta a chat-engine - e qui il comportamento dipende dal fatto che questa chat sia già stata unita o meno. Se la chat non è stata ancora unita, il motore di chat non scrive il messaggio su se stesso e la sua elaborazione avviene solo nel motore di testo. Se la chat è già stata unita a chat-engine, restituisce chat_local_id a user-engine e invia il messaggio a tutti i destinatari. user-engine invia tutti i dati al text-engine, in modo che se succede qualcosa, possiamo sempre tornare indietro, avendo tutti i dati correnti nel vecchio motore. text-engine restituisce user_local_id, che il motore utente memorizza e restituisce al backend.

Di conseguenza, il processo di transizione si presenta così: colleghiamo cluster vuoti di motore utente e motore di chat. chat-engine legge l'intero binlog dei membri della chat, quindi il proxying viene avviato secondo lo schema descritto sopra. Trasferiamo i vecchi dati e otteniamo due cluster sincronizzati (vecchio e nuovo). Tutto ciò che resta è cambiare la lettura dal motore di testo al motore utente e disabilitare il proxy.

Giudizio

Grazie al nuovo approccio, tutti i parametri prestazionali dei motori sono stati migliorati e i problemi di coerenza dei dati sono stati risolti. Ora possiamo implementare rapidamente nuove funzionalità nei messaggi (e abbiamo già iniziato a farlo: abbiamo aumentato il numero massimo di partecipanti alla chat, implementato la ricerca dei messaggi inoltrati, lanciato i messaggi fissati e aumentato il limite del numero totale di messaggi per utente) .

I cambiamenti logici sono davvero enormi. E vorrei sottolineare che questo non significa sempre interi anni di sviluppo da parte di un team enorme e miriadi di righe di codice. il motore di chat e il motore utente insieme a tutte le storie aggiuntive come Huffman per la compressione dei messaggi, gli alberi Splay e la struttura per i messaggi importati contengono meno di 20mila righe di codice. E sono stati scritti da 3 sviluppatori in soli 10 mesi (vale comunque la pena tenerlo presente tutti tre sviluppatore - campioni del mondo nella programmazione sportiva).

Inoltre, invece di raddoppiare il numero di server, ne abbiamo ridotto il numero della metà: ora il motore utente e il motore chat risiedono su 500 macchine fisiche, mentre il nuovo schema ha un ampio margine di carico. Abbiamo risparmiato molti soldi sulle attrezzature: circa 5 milioni di dollari + 750mila dollari all'anno in spese operative.

Ci impegniamo a trovare le migliori soluzioni per i problemi più complessi e su larga scala. Ne abbiamo moltissimi ed è per questo che cerchiamo sviluppatori di talento nel reparto database. Se ami e sai come risolvere questi problemi, hai un'ottima conoscenza di algoritmi e strutture dati, ti invitiamo a unirti al team. Contatta il ns HRper dettagli.

Anche se questa storia non riguarda te, tieni presente che apprezziamo i consigli. Dillo a un amico posti vacanti per sviluppatorie se completa con successo il periodo di prova, riceverai un bonus di 100 mila rubli.

Fonte: habr.com