Naši korisnici pišu poruke jedni drugima bez osjećaja umora.
To je dosta. Kad biste krenuli čitati sve poruke svih korisnika, trebalo bi vam više od 150 tisuća godina. Pod uvjetom da ste prilično napredni čitač i ne trošite više od sekunde na svaku poruku.
S takvom količinom podataka, ključno je da je logika za njihovo pohranjivanje i pristup optimalno izgrađena. U suprotnom, u jednom ne tako divnom trenutku, moglo bi postati jasno da će sve uskoro krenuti po zlu.
Za nas je ovaj trenutak došao prije godinu i pol. Kako smo došli do ovoga i što se na kraju dogodilo – pričamo redom.
dosije
U prvoj implementaciji, VKontakte poruke radile su na kombinaciji PHP pozadine i MySQL-a. Ovo je sasvim normalno rješenje za malu studentsku web stranicu. Međutim, ova je stranica nekontrolirano rasla i počela zahtijevati optimizaciju struktura podataka za sebe.
Krajem 2009. godine napisano je prvo repozitorij text-enginea, a 2010. godine u njega su prebačene poruke.
U tekstualnom stroju poruke su bile pohranjene u popise - svojevrsne "poštanske sandučiće". Svaki takav popis određuje uid - korisnik koji posjeduje sve te poruke. Poruka ima skup atributa: identifikator sugovornika, tekst, privitke i tako dalje. Identifikator poruke unutar “kutije” je local_id, nikada se ne mijenja i dodjeljuje se sekvencijalno za nove poruke. “Kutije” su neovisne i nisu međusobno sinkronizirane unutar motora; komunikacija između njih odvija se na razini PHP-a. Možete pogledati strukturu podataka i mogućnosti text-enginea iznutra .
To je bilo sasvim dovoljno za dopisivanje između dva korisnika. Pogodite što se zatim dogodilo?
U svibnju 2011. VKontakte je uveo razgovore s nekoliko sudionika—multi-chat. Kako bismo radili s njima, podigli smo dva nova klastera - chatovi za članove i članovi za chatove. Prvi pohranjuje podatke o chatovima po korisnicima, drugi pohranjuje podatke o korisnicima po chatovima. Osim samih popisa, to uključuje, na primjer, korisnika koji je pozvao i vrijeme kada je dodan u chat.
"PHP, pošaljimo poruku u chat", kaže korisnik.
"Hajde, {username}", kaže PHP.
Ova shema ima nedostatke. Sinkronizacija je i dalje odgovornost PHP-a. Veliki chatovi i korisnici koji im istovremeno šalju poruke opasna su priča. Budući da instanca tekstualne mašine ovisi o uid-u, sudionici chata mogu primiti istu poruku u različito vrijeme. S tim bi se moglo živjeti da je napredak stao. Ali to se neće dogoditi.
Krajem 2015. pokrenuli smo community messages, a početkom 2016. pokrenuli smo API za njih. S pojavom velikih chatbota u zajednicama, bilo je moguće zaboraviti na ravnomjernu raspodjelu opterećenja.
Dobar bot generira nekoliko milijuna poruka dnevno - time se ne mogu pohvaliti ni najpričljiviji korisnici. To znači da su neke instance text-enginea, na kojima su živjeli takvi botovi, počele najviše patiti.
Motori za poruke u 2016. su 100 instanci članova chata i chatova članova te 8000 tekstualnih motora. Bili su smješteni na tisuću poslužitelja, svaki sa 64 GB memorije. Kao prvu hitnu mjeru povećali smo memoriju za još 32 GB. Procijenili smo prognoze. Bez drastičnih promjena, ovo bi bilo dovoljno za još otprilike godinu dana. Morate ili nabaviti hardver ili optimizirati same baze podataka.
Zbog prirode arhitekture, hardver ima smisla samo višestruko povećavati. Odnosno, barem udvostručiti broj automobila - očito je to prilično skup put. Mi ćemo optimizirati.
Novi koncept
Središnja bit novog pristupa je chat. Chat ima popis poruka koje se odnose na njega. Korisnik ima popis chatova.
Potreban minimum su dvije nove baze podataka:
- motor za chat. Ovo je spremište vektora za chat. Svaki chat ima vektor poruka koje se odnose na njega. Svaka poruka ima tekst i jedinstveni identifikator poruke unutar chata - chat_local_id.
- korisnik-motor. Ovo je pohrana korisničkih vektora - poveznica na korisnike. Svaki korisnik ima vektor peer_id (sugovornici - drugi korisnici, multi-chat ili zajednice) i vektor poruka. Svaki peer_id ima vektor poruka koje se odnose na njega. Svaka poruka ima chat_local_id i jedinstveni ID poruke za tog korisnika - user_local_id.
Novi klasteri međusobno komuniciraju koristeći TCP - to osigurava da se redoslijed zahtjeva ne mijenja. Sami zahtjevi i potvrde za njih snimaju se na tvrdi disk - tako da možemo vratiti stanje čekanja u bilo kojem trenutku nakon kvara ili ponovnog pokretanja motora. Budući da user-engine i chat-engine imaju po 4 tisuće shardova, red zahtjeva između klastera bit će ravnomjerno raspoređen (ali u stvarnosti ga uopće nema - i radi vrlo brzo).
Rad s diskom u našim bazama podataka u većini slučajeva temelji se na kombinaciji binarnog dnevnika promjena (binlog), statičkih snimaka i djelomične slike u memoriji. Promjene tijekom dana zapisuju se u binlog, a povremeno se stvara snimka trenutnog stanja. Snimak je skup struktura podataka optimiziranih za naše potrebe. Sastoji se od zaglavlja (metaindeksa slike) i skupa metadatoteka. Zaglavlje je trajno pohranjeno u RAM-u i pokazuje gdje tražiti podatke iz snimke. Svaka metadatoteka uključuje podatke koji će vjerojatno biti potrebni u bliskim vremenskim točkama—na primjer, povezani s jednim korisnikom. Kada postavljate upit bazi podataka koristeći zaglavlje snimke, potrebna meta datoteka se čita, a zatim se uzimaju u obzir promjene u binlogu koje su se dogodile nakon što je napravljena snimka. Možete pročitati više o prednostima ovog pristupa .
Istodobno, podaci na samom tvrdom disku mijenjaju se samo jednom dnevno - kasno noću u Moskvi, kada je opterećenje minimalno. Zahvaljujući tome (znajući da je struktura na disku konstantna tijekom dana), možemo si priuštiti zamjenu vektora nizovima fiksne veličine - i time dobiti na memoriji.
Slanje poruke u novoj shemi izgleda ovako:
- Pozadina PHP-a kontaktira korisnički stroj sa zahtjevom za slanje poruke.
- user-engine proksi zahtjev do željene instance chat-enginea, koja se vraća na chat_local_id korisničke mašine - jedinstveni identifikator nove poruke unutar ovog chata. Chat_engine zatim emitira poruku svim primateljima u chatu.
- user-engine prima chat_local_id od chat-enginea i vraća user_local_id u PHP - jedinstveni identifikator poruke za ovog korisnika. Taj se identifikator zatim koristi, na primjer, za rad s porukama putem API-ja.
Ali osim stvarnog slanja poruka, morate implementirati još nekoliko važnih stvari:
- Podpopisi su, na primjer, najnovije poruke koje vidite kada otvorite popis razgovora. Nepročitane poruke, poruke s oznakama (“Važno”, “Spam” itd.).
- Sažimanje poruka u chat motoru
- Spremanje poruka u predmemoriju u korisničkom stroju
- Pretraživanje (kroz sve dijaloge i unutar određenog).
- Ažuriranje u stvarnom vremenu (Longpolling).
- Spremanje povijesti za implementaciju predmemoriranja na mobilnim klijentima.
Svi podlisti brzo mijenjaju strukturu. Za rad s njima koristimo . Ovaj izbor se objašnjava činjenicom da na vrhu stabla ponekad pohranjujemo cijeli segment poruka iz snimke - na primjer, nakon noćnog ponovnog indeksiranja, stablo se sastoji od jednog vrha koji sadrži sve poruke podpopisa. Splay stablo olakšava umetanje u sredinu takvog vrha bez razmišljanja o balansiranju. Osim toga, Splay ne pohranjuje nepotrebne podatke, što nam štedi memoriju.
Poruke uključuju veliku količinu informacija, uglavnom teksta, što je korisno za komprimiranje. Važno je da možemo točno dearhivirati čak i jednu pojedinačnu poruku. Koristi se za komprimiranje poruka s vlastitom heuristikom - na primjer, znamo da se u porukama riječi izmjenjuju s "ne-riječima" - razmacima, interpunkcijskim znakovima - a također se sjećamo nekih osobitosti korištenja simbola za ruski jezik.
Budući da ima puno manje korisnika nego chatova, kako bismo spremili zahtjeve diska s nasumičnim pristupom u chat-enginu, poruke predmemoriramo u user-enginu.
Pretraživanje poruka implementirano je kao dijagonalni upit od korisničkog motora do svih instanci motora za chat koji sadrže razgovore ovog korisnika. Rezultati se kombiniraju u samom korisničkom stroju.
Pa, svi detalji su uzeti u obzir, preostaje samo prijeći na novu shemu - i po mogućnosti bez da korisnici to primijete.
Migracija podataka
Dakle, imamo tekstualnu mašinu koja pohranjuje poruke po korisniku, te dva klastera chat-members i member-chatovi koji pohranjuju podatke o multi-chat sobama i korisnicima u njima. Kako prijeći s ovog na novi korisnički i chat-engine?
chatovi članova u staroj shemi korišteni su prvenstveno za optimizaciju. Brzo smo prenijeli potrebne podatke s njega na chat-članove, a zatim više nije sudjelovao u procesu migracije.
Red za članove chata. Uključuje 100 instanci, dok ih chat-engine ima 4 tisuće. Da biste prenijeli podatke, morate ih uskladiti - za to su članovi chata podijeljeni u iste 4 tisuće kopija, a zatim je omogućeno čitanje binloga članova chata u motoru za chat.
Sada chat-engine zna za multi-chat članova chata, ali još ne zna ništa o dijalozima s dva sugovornika. Takvi se dijalozi nalaze u tekstualnom stroju s referencom na korisnike. Ovdje smo podatke uzeli direktno: svaka instanca motora za chat pitala je sve instance tekstualnog motora imaju li potreban dijalog.
Sjajno - chat-engine zna koji multi-chat razgovori postoje i zna koji dijalozi postoje.
Morate kombinirati poruke u multi-chat chatovima tako da na kraju dobijete popis poruka u svakom chatu. Prvo, chat-engine dohvaća iz text-engina sve korisničke poruke iz ovog chata. U nekim slučajevima ima ih dosta (i do stotine milijuna), ali uz vrlo rijetke iznimke chat u potpunosti stane u RAM. Imamo nesređene poruke, svaku u nekoliko primjeraka - na kraju krajeva, sve su izvučene iz različitih instanci tekstualnih motora koje odgovaraju korisnicima. Cilj je sortirati poruke i riješiti se kopija koje zauzimaju nepotreban prostor.
Svaka poruka ima vremensku oznaku koja sadrži vrijeme slanja i tekst. Koristimo vrijeme za sortiranje - postavljamo pokazivače na najstarije poruke sudionika multichata i uspoređujemo hashove iz teksta predviđenih kopija, krećući se prema povećanju vremenske oznake. Logično je da će kopije imati isti hash i vremensku oznaku, ali u praksi to nije uvijek slučaj. Kao što se sjećate, sinkronizaciju u staroj shemi provodio je PHP - au rijetkim slučajevima vrijeme slanja iste poruke razlikovalo se među različitim korisnicima. U tim slučajevima smo si dopustili da uredimo vremensku oznaku - obično unutar jedne sekunde. Drugi problem je različit redoslijed poruka za različite primatelje. U takvim smo slučajevima dopustili stvaranje dodatne kopije, s različitim opcijama naručivanja za različite korisnike.
Nakon toga se podaci o porukama u multichatu šalju korisničkom stroju. I tu dolazi do neugodne osobine uvezenih poruka. U normalnom radu, poruke koje dolaze u motor poredane su striktno uzlaznim redoslijedom prema user_local_id. Poruke uvezene iz starog stroja u korisnički stroj izgubile su ovo korisno svojstvo. U isto vrijeme, radi praktičnosti testiranja, morate im moći brzo pristupiti, tražiti nešto u njima i dodati nove.
Za pohranu uvezenih poruka koristimo posebnu strukturu podataka.
Predstavlja vektor veličine gdje su svi - su različiti i poredani silaznim redoslijedom, s posebnim redoslijedom elemenata. U svakom segmentu s indeksima elementi su sortirani. Traženje elementa u takvoj strukturi zahtijeva vrijeme kroz binarne pretrage. Dodavanje elementa amortizira se .
Dakle, shvatili smo kako prenijeti podatke sa starih motora na nove. Ali ovaj proces traje nekoliko dana - i malo je vjerojatno da će tijekom ovih dana naši korisnici odustati od navike pisanja jedni drugima. Kako ne bismo izgubili poruke tijekom tog vremena, prelazimo na shemu rada koja koristi i stare i nove klastere.
Podaci se zapisuju članovima chata i korisničkom stroju (a ne tekstualnom stroju, kao u normalnom radu prema staroj shemi). user-engine proksi zahtjev za chat-engine - i ovdje ponašanje ovisi o tome je li ovaj chat već spojen ili ne. Ako chat još nije spojen, chat-engine ne piše poruku sam sebi, a njena obrada se odvija samo u text-enginu. Ako je chat već spojen u chat-engine, on vraća chat_local_id u user-engine i šalje poruku svim primateljima. user-engine proksira sve podatke u text-engine - tako da ako se nešto dogodi, uvijek se možemo vratiti, imajući sve trenutne podatke u starom engineu. text-engine vraća user_local_id, koji user-engine pohranjuje i vraća u backend.
Kao rezultat toga, proces tranzicije izgleda ovako: povezujemo prazne klastere user-engine i chat-engine. motor za čavrljanje čita cijeli binlog članova čavrljanja, zatim počinje proxyiranje prema gore opisanoj shemi. Prebacujemo stare podatke i dobivamo dva sinkronizirana klastera (stari i novi). Sve što preostaje je prebaciti čitanje s text-engina na user-engine i onemogućiti proxying.
Nalazi
Zahvaljujući novom pristupu, poboljšane su sve metrike performansi motora i riješeni su problemi s dosljednošću podataka. Sada možemo brzo implementirati nove značajke u poruke (i to smo već počeli činiti - povećali smo maksimalan broj sudionika u chatu, implementirali pretraživanje proslijeđenih poruka, pokrenuli prikvačene poruke i podigli ograničenje ukupnog broja poruka po korisniku) .
Promjene u logici su doista goleme. I želio bih napomenuti da to ne znači uvijek cijele godine razvoja ogromnog tima i bezbroj redaka koda. chat-engine i user-engine zajedno sa svim dodatnim pričama kao što je Huffman za kompresiju poruka, Splay stabla i struktura za uvezene poruke je manje od 20 tisuća redaka koda. I napisala su ih 3 programera u samo 10 mjeseci (međutim, vrijedi imati na umu da - svjetski prvaci ).
Štoviše, umjesto udvostručenja broja poslužitelja, smanjili smo njihov broj za pola - sada korisnički motor i chat-motor žive na 500 fizičkih strojeva, dok nova shema ima veliki prostor za opterećenje. Uštedjeli smo mnogo novca na opremi - oko 5 milijuna dolara + 750 tisuća dolara godišnje operativnih troškova.
Nastojimo pronaći najbolja rješenja za najsloženije i velike probleme. Imamo ih mnogo - i zato tražimo talentirane programere u odjelu baze podataka. Ako volite i znate rješavati ovakve probleme, odlično poznajete algoritme i strukture podataka, pozivamo vas da se pridružite našem timu. Kontaktirajte nas za detalje.
Čak i ako ova priča nije o vama, imajte na umu da cijenimo preporuke. Recite prijatelju o , a ako uspješno završi probni rok, dobit ćete bonus od 100 tisuća rubalja.
Izvor: www.habr.com