Naši korisnici pišu poruke jedni drugima ne svjesni umora.
To je dosta. Ako biste krenuli da čitate sve poruke svih korisnika, trebalo bi više od 150 hiljada godina. Pod uslovom da ste prilično napredan čitač i da ne potrošite više od sekunde na svaku poruku.
Sa takvom količinom podataka, kritično je da je logika za njihovo pohranjivanje i pristupanje izgrađena optimalno. U suprotnom, u jednom ne baš čudesnom trenutku može postati jasno da će sve uskoro krenuti naopako.
Za nas je ovaj trenutak došao prije godinu i po dana. Kako smo došli do ovoga i šta je na kraju bilo - pričamo vam redom.
Pozadina
U prvoj implementaciji, VKontakte poruke su radile na kombinaciji PHP backend-a i MySQL-a. Ovo je sasvim normalno rješenje za malu studentsku web stranicu. Međutim, ovaj sajt je nekontrolisano rastao i počeo da zahteva optimizaciju strukture podataka za sebe.
Krajem 2009. godine napisan je prvi text-engine repozitorij, au njega su 2010. godine prebačene poruke.
U tekstualnom motoru, poruke su bile pohranjene u listama - svojevrsnim "poštanskim sandučićima". Svaka takva lista je određena uid-om - korisnikom koji posjeduje sve ove poruke. Poruka ima skup atributa: identifikator sagovornika, tekst, priloge itd. Identifikator poruke unutar “kutije” je local_id, nikada se ne mijenja i dodjeljuje se sekvencijalno za nove poruke. „Kutije“ su nezavisne i nisu međusobno sinhronizovane unutar motora; komunikacija između njih se odvija na PHP nivou. Strukturu podataka i mogućnosti text-engine-a možete pogledati iznutra .
Ovo je bilo sasvim dovoljno za prepisku između dva korisnika. Pogodi šta se dalje dogodilo?
U maju 2011. VKontakte je uveo razgovore sa nekoliko učesnika—multi-chat. Da bismo radili s njima, podigli smo dva nova klastera - chat-chat i chat-member. Prvi pohranjuje podatke o četovima po korisnicima, drugi pohranjuje podatke o korisnicima po četovima. Osim samih lista, ovo uključuje, na primjer, korisnika koji poziva i vrijeme kada su dodani u chat.
"PHP, pošaljimo poruku u chat", kaže korisnik.
“Hajde, {username}”, kaže PHP.
Postoje nedostaci ove šeme. Sinhronizacija je i dalje odgovornost PHP-a. Veliki chatovi i korisnici koji im istovremeno šalju poruke su opasna priča. Budući da instanca motora teksta ovisi o uid-u, učesnici chata mogu primiti istu poruku u različito vrijeme. S tim bi se moglo živjeti da napredak stane. Ali to se neće dogoditi.
Krajem 2015. pokrenuli smo poruke zajednice, a početkom 2016. pokrenuli smo API za njih. S pojavom velikih chatbotova u zajednicama, bilo je moguće zaboraviti na ravnomjernu raspodjelu opterećenja.
Dobar bot generira nekoliko miliona poruka dnevno - time se ne mogu pohvaliti ni najpričljiviji korisnici. To znači da su neke instance text-engine-a, na kojima su živjeli takvi botovi, počele da pate u najvećoj mjeri.
Mehanizmi za poruke u 2016. su 100 instanci chat-članova i chat-ova članova i 8000 tekstualnih motora. Hostovani su na hiljadu servera, 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š godinu dana. Morate ili nabaviti hardver ili optimizirati same baze podataka.
Zbog prirode arhitekture, ima smisla samo višestruko povećavati hardver. Odnosno, barem udvostručiti broj automobila - očigledno, ovo je prilično skup put. Mi ćemo optimizirati.
Novi koncept
Centralna suština novog pristupa je ćaskanje. Chat ima listu poruka koje se odnose na njega. Korisnik ima listu razgovora.
Potreban minimum su dvije nove baze podataka:
- chat-engine. Ovo je spremište vektora za ćaskanje. Svaki chat ima vektor poruka koje se odnose na njega. Svaka poruka ima tekst i jedinstveni identifikator poruke unutar chata - chat_local_id.
- korisnički motor. Ovo je skladište korisničkih vektora - linkova do korisnika. Svaki korisnik ima vektor peer_id (sagovornici - 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 se snimaju na hard disk - tako da možemo vratiti stanje reda u bilo kojem trenutku nakon kvara ili ponovnog pokretanja motora. S obzirom na to da su user-engine i chat-engine po 4 hiljade shardova, red zahtjeva između klastera će biti ravnomjerno raspoređen (ali u stvarnosti ga uopće nema - i radi vrlo brzo).
Rad sa diskom u našim bazama podataka u većini slučajeva zasniva se na kombinaciji binarnog dnevnika promjena (binlog), statičkih snimaka i djelomične slike u memoriji. Promjene tokom dana se upisuju u binlog, a periodično se kreira snimak trenutnog stanja. Snimak je zbirka struktura podataka optimiziranih za naše potrebe. Sastoji se od zaglavlja (metaindeks slike) i skupa metadatoteka. Zaglavlje je trajno pohranjeno u RAM-u i pokazuje gdje tražiti podatke sa snimka. Svaka metadatoteka uključuje podatke koji će vjerovatno biti potrebni u bliskim vremenskim trenucima—na primjer, vezani za jednog korisnika. Kada postavljate upit bazi podataka koristeći zaglavlje snimka, potrebna metadatoteka se čita, a zatim se uzimaju u obzir promjene u binlogu koje su se dogodile nakon što je snimak napravljen. Možete pročitati više o prednostima ovog pristupa .
Istovremeno, podaci na samom tvrdom disku mijenjaju se samo jednom dnevno - kasno u noć u Moskvi, kada je opterećenje minimalno. Zahvaljujući tome (znajući da je struktura na disku konstantna tokom dana), možemo sebi priuštiti zamjenu vektora nizovima fiksne veličine - i zbog toga dobiti u memoriji.
Slanje poruke u novoj šemi izgleda ovako:
- PHP backend kontaktira korisnički motor sa zahtjevom da pošalje poruku.
- user-engine proksije zahtjev željenoj instanci chat-engine, koja se vraća na user-engine chat_local_id - jedinstveni identifikator nove poruke unutar ovog chata. Chat_engine zatim emituje poruku svim primaocima u chatu.
- user-engine prima chat_local_id od chat-engine i vraća user_local_id u PHP - jedinstveni identifikator poruke za ovog korisnika. Ovaj identifikator se zatim koristi, na primjer, za rad s porukama putem API-ja.
Ali pored stvarnog slanja poruka, morate implementirati još nekoliko važnih stvari:
- Podliste su, na primjer, najnovije poruke koje vidite kada otvarate listu razgovora. Nepročitane poruke, poruke sa oznakama (“Važno”, “Neželjena pošta” itd.).
- Kompresija poruka u chat-engine
- Keširanje poruka u korisničkom motoru
- Pretraga (kroz sve dijaloge i unutar određenog).
- Ažuriranje u realnom vremenu (Longpolling).
- Čuvanje historije za implementaciju keširanja na mobilnim klijentima.
Sve podliste su strukture koje se brzo mijenjaju. Za rad sa njima koristimo . Ovaj izbor se objašnjava činjenicom da na vrhu stabla ponekad pohranjujemo cijeli segment poruka iz snimka - na primjer, nakon noćnog ponovnog indeksiranja, stablo se sastoji od jednog vrha koji sadrži sve poruke podliste. 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 precizno dearhivirati čak i jednu pojedinačnu poruku. Koristi se za kompresiju poruka sopstvenom heuristikom - na primjer, znamo da se u porukama riječi izmjenjuju s "ne-riječima" - razmacima, interpunkcijskim znacima - a sjećamo se i nekih posebnosti upotrebe simbola za ruski jezik.
Budući da ima mnogo manje korisnika nego chatova, da bismo spremili zahtjeve diska sa slučajnim pristupom u chat-engine, keširamo poruke u korisničkom motoru.
Pretraga poruka je implementirana kao dijagonalni upit od korisničkog motora do svih instanci chat-engine koje sadrže razgovore ovog korisnika. Rezultati se kombinuju u samom korisničkom motoru.
Pa, svi detalji su uzeti u obzir, ostaje samo da se pređe na novu šemu - i po mogućnosti bez da korisnici to primete.
Migracija podataka
Dakle, imamo text-engine koji pohranjuje poruke po korisniku i dva klastera chat-members i members-chat koji pohranjuju podatke o multi-chat sobama i korisnicima u njima. Kako preći sa ovog na novi user-engine i chat-engine?
chat-ovi sa članovima u staroj šemi korišteni su prvenstveno za optimizaciju. Brzo smo prenijeli potrebne podatke sa njega na chat-članove, a zatim više nije učestvovao u procesu migracije.
Red za chat-članove. Uključuje 100 instanci, dok chat-engine ima 4 hiljade. Da biste prenijeli podatke, potrebno ih je uskladiti - za to su članovi chata podijeljeni u istih 4 hiljade kopija, a zatim je omogućeno čitanje binlog-a chat-članova u motoru za ćaskanje.
Sada chat-engine zna za multi-chat od članova chat-a, ali još ne zna ništa o dijalozima sa dva sagovornika. Takvi dijalozi se nalaze u tekstualnom motoru u odnosu na korisnike. Ovdje smo uzeli podatke "naprijed": svaka instanca chat-engine-a je pitala sve instance motora za tekst da li imaju dijalog koji joj je potreban.
Odlično - motor za ćaskanje zna koji multi-chat chatovi postoje i zna koji dijalozi postoje.
Morate kombinovati poruke u multi-chat chatovima tako da na kraju dobijete listu poruka u svakom ćaskanju. Prvo, chat-engine preuzima iz text-engine-a sve korisničke poruke iz ovog chata. U nekim slučajevima ih ima dosta (do stotine miliona), ali uz vrlo rijetke izuzetke chat se u potpunosti uklapa u RAM. Imamo neuređene poruke, svaka u nekoliko kopija - na kraju krajeva, sve su izvučene iz različitih instanci tekstualnog motora koji odgovaraju korisnicima. Cilj je sortirati poruke i riješiti se kopija koje zauzimaju nepotreban prostor.
Svaka poruka ima vremensku oznaku koja sadrži vrijeme kada je poslana i tekst. Koristimo vrijeme za sortiranje - postavljamo pokazivače na najstarije poruke učesnika multichata i upoređujemo hešove iz teksta predviđenih kopija, krećući se ka 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 sećate, sinhronizaciju u staroj šemi vršio je PHP - a u retkim slučajevima vreme slanja iste poruke se razlikovalo među različitim korisnicima. U ovim slučajevima, dozvolili smo sebi da uredimo vremensku oznaku - obično unutar jedne sekunde. Drugi problem je različit redoslijed poruka za različite primaoce. U takvim slučajevima, dozvolili smo kreiranje dodatne kopije, s različitim opcijama naručivanja za različite korisnike.
Nakon toga, podaci o porukama u multichatu se šalju korisničkom motoru. A tu dolazi i neugodna karakteristika uvezenih poruka. U normalnom radu, poruke koje dolaze u motor su poređane striktno uzlaznim redoslijedom prema user_local_id. Poruke uvezene sa starog motora u korisnički motor izgubile su ovo korisno svojstvo. Istovremeno, radi praktičnosti testiranja, morate biti u mogućnosti da im brzo pristupite, potražite nešto u njima i dodate nove.
Koristimo posebnu strukturu podataka za pohranjivanje uvezenih poruka.
Predstavlja vektor veličine gde su svi - različiti su i poređani u opadajućem redosledu, sa posebnim redosledom elemenata. U svakom segmentu sa indeksima elementi su sortirani. Potraga za elementom u takvoj strukturi zahtijeva vrijeme kroz binarne pretrage. Dodavanje elementa se amortizuje .
Dakle, shvatili smo kako prenijeti podatke sa starih motora na nove. Ali ovaj proces traje nekoliko dana - i malo je vjerovatno da će tokom ovih dana naši korisnici odustati od navike pisanja jedni drugima. Kako ne bismo izgubili poruke za to vrijeme, prelazimo na radnu šemu koja koristi i stare i nove klastere.
Podaci se upisuju u chat-članove i user-engine (a ne u text-engine, kao u normalnom radu prema staroj shemi). user-engine proksije zahtjev za chat-engine - i ovdje ponašanje ovisi o tome da li je ovaj chat već spojen ili ne. Ako chat još nije spojen, chat-engine ne piše poruku sebi, a njena obrada se događa samo u tekstualnom motoru. Ako je chat već spojen u chat-engine, on vraća chat_local_id korisničkom motoru i šalje poruku svim primaocima. user-engine proxy sve podatke u text-engine - tako da ako se nešto dogodi, uvijek možemo vratiti nazad, imajući sve trenutne podatke u starom motoru. text-engine vraća user_local_id, koji korisnički motor pohranjuje i vraća na pozadinu.
Kao rezultat, proces tranzicije izgleda ovako: povezujemo prazne user-engine i chat-engine clusters. chat-engine čita cijeli binlog članova chata, a zatim proxy počinje prema gore opisanoj šemi. Prenosimo stare podatke i dobijamo dva sinhronizovana klastera (stari i novi). Sve što ostaje je da prebacite čitanje sa tekstualnog na korisnički motor i onemogućite proxy.
Rezulʹtaty
Zahvaljujući novom pristupu, poboljšane su sve metrike performansi motora i riješeni su problemi s konzistentnošću podataka. Sada možemo brzo implementirati nove funkcije u porukama (i to smo već počeli raditi - povećali smo maksimalan broj sudionika u chatu, implementirali pretragu proslijeđenih poruka, pokrenuli zakačene poruke i podigli ograničenje ukupnog broja poruka po korisniku) .
Promjene u logici su zaista ogromne. I želio bih napomenuti da to ne znači uvijek čitave godine razvoja ogromnog tima i bezbroj linija koda. chat-engine i user-engine zajedno sa svim dodatnim pričama kao što su Huffman za kompresiju poruka, Splay stabla i struktura za uvezene poruke je manje od 20 hiljada linija koda. I napisala su ih 3 programera u samo 10 mjeseci (međutim, vrijedi imati na umu da - svjetski prvaci ).
Štaviše, umjesto da udvostručimo broj servera, smanjili smo njihov broj za polovicu – sada korisnički motor i chat-engine žive na 500 fizičkih mašina, dok nova šema ima veliki prostor za opterećenje. Uštedeli smo mnogo novca na opremi - oko 5 miliona dolara + 750 hiljada dolara godišnje na operativnim troškovima.
Nastojimo pronaći najbolja rješenja za najkompleksnije i najveće probleme. Imamo ih dosta - i zato tražimo talentovane programere u odjelu za baze podataka. Ako volite i znate kako riješiti ovakve probleme, odlično poznajete algoritme i strukture podataka, pozivamo vas da se pridružite timu. Kontaktirajte naše za detalje.
Čak i ako ova priča nije o vama, imajte na umu da cijenimo preporuke. Reci prijatelju o tome , a ako uspješno završi probni rok, dobićete bonus od 100 hiljada rubalja.
izvor: www.habr.com