Mūsų vartotojai rašo žinutes vieni kitiems nepajutę nuovargio.
Tai gana daug. Jei užsibrėžtumėte perskaityti visas visų vartotojų žinutes, tai užtruktų daugiau nei 150 tūkstančių metų. Su sąlyga, kad esate gana pažengęs skaitytojas ir kiekvienam pranešimui skiriate ne daugiau nei sekundę.
Esant tokiam duomenų kiekiui, labai svarbu, kad jų saugojimo ir prieigos logika būtų sukurta optimaliai. Priešingu atveju per vieną ne itin nuostabią akimirką gali paaiškėti, kad greitai viskas susiklostys ne taip.
Mums ši akimirka atėjo prieš pusantrų metų. Kaip mes iki to atėjome ir kas galiausiai atsitiko - mes jums pasakysime eilės tvarka.
ligos istorija
Pačiame pirmajame diegime „VKontakte“ pranešimai veikė PHP backend ir MySQL derinyje. Tai visiškai normalus sprendimas mažam studentų tinklalapiui. Tačiau ši svetainė nevaldomai augo ir pradėjo reikalauti sau optimizuoti duomenų struktūras.
2009 metų pabaigoje buvo parašyta pirmoji teksto variklio saugykla, o 2010 metais į ją buvo perkelti pranešimai.
Tekstiniame variklyje pranešimai buvo saugomi sąrašuose - savotiškose „pašto dėžutėse“. Kiekvieną tokį sąrašą nustato uid – vartotojas, kuriam priklauso visi šie pranešimai. Pranešimas turi atributų rinkinį: pašnekovo identifikatorių, tekstą, priedus ir pan. Pranešimo identifikatorius „dėžutėje“ yra local_id, jis niekada nesikeičia ir priskiriamas nuosekliai naujiems pranešimams. „Dėžutės“ yra nepriklausomos ir nėra sinchronizuojamos viena su kita variklio viduje; ryšys tarp jų vyksta PHP lygiu. Galite pažvelgti į teksto variklio duomenų struktūrą ir galimybes iš vidaus .
To visiškai pakako susirašinėjimui tarp dviejų vartotojų. Spėkite, kas nutiko toliau?
2011 m. gegužę VKontakte pradėjo pokalbius su keliais dalyviais – daugiakalbį. Norėdami dirbti su jais, sukūrėme dvi naujas grupes – narių pokalbių ir pokalbių narius. Pirmasis saugo duomenis apie vartotojų pokalbius, antrasis saugo duomenis apie vartotojus pagal pokalbius. Be pačių sąrašų, tai apima, pavyzdžiui, kviečiantį vartotoją ir laiką, kada jis buvo įtrauktas į pokalbį.
„PHP, išsiųkime žinutę į pokalbį“, – sako vartotojas.
„Nagi, {username}“, – sako PHP.
Ši schema turi trūkumų. Už sinchronizavimą vis dar atsakinga PHP. Dideli pokalbiai ir vartotojai, kurie tuo pačiu metu siunčia jiems pranešimus, yra pavojinga istorija. Kadangi teksto variklio pavyzdys priklauso nuo uid, pokalbio dalyviai tą patį pranešimą gali gauti skirtingu laiku. Su tuo būtų galima gyventi, jei pažanga sustotų. Bet taip neatsitiks.
2015 m. pabaigoje paleidome bendruomenės pranešimus, o 2016 m. pradžioje – jiems skirtą API. Bendruomenėse atsiradus dideliems pokalbių robotams, apie tolygų apkrovos paskirstymą buvo galima pamiršti.
Geras robotas sugeneruoja kelis milijonus pranešimų per dieną – tuo negali pasigirti net patys kalbiausi vartotojai. Tai reiškia, kad kai kurie teksto variklio atvejai, kuriuose gyveno tokie robotai, pradėjo kentėti iki galo.
2016 m. pranešimų varikliai yra 100 pokalbių narių ir narių pokalbių atvejų bei 8000 teksto variklių. Jie buvo talpinami tūkstančiuose serverių, kurių kiekvienas turėjo 64 GB atminties. Pirmą kartą avariniu atveju atmintį padidinome dar 32 GB. Mes įvertinome prognozes. Be drastiškų pokyčių to užtektų dar maždaug metams. Turite arba gauti aparatinę įrangą, arba optimizuoti pačias duomenų bazes.
Dėl architektūros pobūdžio prasminga tik kelis kartus padidinti techninę įrangą. Tai yra, bent padvigubinti automobilių skaičių – akivaizdu, kad tai gana brangus kelias. Mes optimizuosime.
Nauja koncepcija
Pagrindinė naujojo požiūrio esmė yra pokalbiai. Pokalbyje yra su juo susijusių pranešimų sąrašas. Vartotojas turi pokalbių sąrašą.
Reikia mažiausiai dviejų naujų duomenų bazių:
- pokalbių variklis. Tai pokalbių vektorių saugykla. Kiekvienas pokalbis turi su juo susijusių pranešimų vektorių. Kiekvienas pranešimas turi tekstą ir unikalų pranešimo identifikatorių pokalbio viduje – chat_local_id.
- vartotojo variklis. Tai vartotojų vektorių saugykla – nuorodos į vartotojus. Kiekvienas vartotojas turi peer_id vektorių (pašnekovai – kiti vartotojai, multi-chat arba bendruomenės) ir pranešimų vektorių. Kiekvienas peer_id turi su juo susijusių pranešimų vektorių. Kiekvienas pranešimas turi chat_local_id ir unikalų to vartotojo pranešimo ID – user_local_id.
Nauji klasteriai tarpusavyje bendrauja naudodami TCP – taip užtikrinama, kad užklausų tvarka nesikeistų. Patys užklausos ir patvirtinimai dėl jų yra įrašomi į kietąjį diską – todėl sugedus varikliui ar iš naujo užvedus eilės būseną galime bet kada atkurti. Kadangi vartotojo variklis ir pokalbių variklis yra po 4 tūkstančius skeveldrų, užklausų eilė tarp klasterių bus paskirstyta tolygiai (tačiau realiai jos visai nėra – ir veikia labai greitai).
Darbas su disku mūsų duomenų bazėse daugeliu atvejų yra pagrįstas dvejetainio pakeitimų žurnalo (binlog), statinių momentinių vaizdų ir dalinio vaizdo atmintyje deriniu. Pakeitimai per dieną įrašomi į binlogą ir periodiškai sukuriama esamos būsenos momentinė nuotrauka. Momentinė nuotrauka yra duomenų struktūrų rinkinys, optimizuotas mūsų tikslams. Jį sudaro antraštė (vaizdo metaindeksas) ir metafailų rinkinys. Antraštė visam laikui saugoma RAM ir nurodo, kur ieškoti momentinės nuotraukos duomenų. Kiekviename metafaile yra duomenų, kurių gali prireikti artimiausiu metu, pavyzdžiui, susijusių su vienu vartotoju. Kai pateikiate duomenų bazės užklausą naudodami momentinės nuotraukos antraštę, nuskaitomas reikalingas metafailas, o tada atsižvelgiama į binlogo pakeitimus, įvykusius po momentinės nuotraukos sukūrimo. Galite perskaityti daugiau apie šio metodo naudą .
Tuo pačiu metu duomenys pačiame kietajame diske keičiasi tik kartą per dieną – vėlai vakare Maskvoje, kai apkrova minimali. Dėl to (žinodami, kad disko struktūra yra pastovi visą dieną), galime sau leisti pakeisti vektorius fiksuoto dydžio masyvais - ir dėl to padidinti atmintį.
Pranešimo siuntimas pagal naują schemą atrodo taip:
- PHP užpakalinė programa susisiekia su vartotojo varikliu, prašydama išsiųsti pranešimą.
- user-engine perduoda užklausą norimam pokalbių variklio egzemplioriui, kuris grįžta į vartotojo variklio chat_local_id – unikalų naujo pranešimo šiame pokalbyje identifikatorių. Tada „chat_engine“ transliuoja pranešimą visiems pokalbio gavėjams.
- user-engine gauna chat_local_id iš pokalbių variklio ir grąžina user_local_id į PHP – unikalų šio vartotojo pranešimo identifikatorių. Tada šis identifikatorius naudojamas, pavyzdžiui, dirbant su pranešimais per API.
Tačiau be faktinio pranešimų siuntimo turite įgyvendinti keletą svarbių dalykų:
- Posąraščiai yra, pavyzdžiui, naujausi pranešimai, kuriuos matote atidarydami pokalbių sąrašą. Neskaityti pranešimai, pranešimai su žymomis („Svarbu“, „Šlamštas“ ir kt.).
- Pranešimų glaudinimas pokalbių variklyje
- Pranešimų kaupimas talpykloje vartotojo variklyje
- Paieška (visuose dialoguose ir konkrečiame).
- Atnaujinimas realiuoju laiku (Longpolling).
- Išsaugoma istorija, kad būtų galima įdiegti talpyklą mobiliuosiuose klientuose.
Visi posąraščiai yra greitai besikeičiančios struktūros. Norėdami dirbti su jais, mes naudojame . Toks pasirinkimas paaiškinamas tuo, kad medžio viršuje kartais saugome visą segmentą pranešimų iš momentinės nuotraukos – pavyzdžiui, po naktinio pakartotinio indeksavimo medis susideda iš vienos viršūnės, kurioje yra visi subsąrašo pranešimai. Splay medis leidžia lengvai įterpti į tokios viršūnės vidurį, negalvojant apie balansavimą. Be to, „Splay“ nesaugo nereikalingų duomenų, o tai taupo atmintį.
Pranešimai apima daug informacijos, daugiausia teksto, kuri yra naudinga norint suspausti. Svarbu, kad galėtume tiksliai išarchyvuoti net vieną atskirą pranešimą. Naudojamas žinutėms suspausti su savo euristika – pavyzdžiui, žinome, kad žinutėse žodžiai kaitaliojasi su „nežodžiais“ – tarpais, skyrybos ženklais – taip pat prisimename kai kuriuos simbolių vartojimo rusų kalbai ypatumus.
Kadangi vartotojų yra daug mažiau nei pokalbių, norėdami išsaugoti atsitiktinės prieigos disko užklausas pokalbių variklyje, laiškus talpiname vartotojo variklyje.
Pranešimų paieška įgyvendinama kaip įstrižainė užklausa iš vartotojo variklio į visus pokalbių variklio atvejus, kuriuose yra šio vartotojo pokalbių. Rezultatai sujungiami pačiame vartotojo variklyje.
Na, į visas smulkmenas buvo atsižvelgta, belieka pereiti prie naujos schemos – ir pageidautina, kad vartotojai to nepastebėtų.
Duomenų perkėlimas
Taigi, mes turime tekstinį variklį, kuris saugo pranešimus pagal vartotoją, ir dvi grupes pokalbių narių ir narių pokalbių, kuriose saugomi duomenys apie kelių pokalbių kambarius ir juose esančius vartotojus. Kaip nuo to pereiti prie naujo vartotojo ir pokalbių variklio?
narių pokalbiai senojoje schemoje pirmiausia buvo naudojami optimizavimui. Greitai perdavėme iš jo reikiamus duomenis pokalbių nariams, o tada jis nebedalyvavo perkėlimo procese.
Eilė pokalbių nariams. Jame yra 100 atvejų, o pokalbių variklis turi 4 tūkst. Norėdami perkelti duomenis, turite juos suderinti - tam pokalbių nariai buvo suskirstyti į tuos pačius 4 tūkstančius kopijų, o tada pokalbių variklyje buvo įjungtas pokalbių narių žurnalo skaitymas.
Dabar pokalbių variklis žino apie daugialypį pokalbį iš pokalbių narių, bet dar nieko nežino apie dialogus su dviem pašnekovais. Tokie dialogai yra tekstiniame variklyje, nurodant vartotojus. Čia mes paėmėme duomenis „priešais“: kiekvienas pokalbių programos egzempliorius klausė visų teksto variklio atvejų, ar jie turi reikiamą dialogą.
Puiku – pokalbių variklis žino, kokie yra kelių pokalbių pokalbiai, ir žino, kokie yra dialogai.
Turite sujungti pranešimus kelių pokalbių pokalbiuose, kad kiekviename pokalbyje būtų pateiktas pranešimų sąrašas. Pirma, pokalbių programa iš teksto variklio nuskaito visus vartotojo pranešimus iš šio pokalbio. Kai kuriais atvejais jų yra gana daug (iki šimtų milijonų), tačiau su labai retomis išimtimis pokalbis visiškai telpa į RAM. Turime nerūšiuotų žinučių, kurių kiekviena yra po kelias kopijas – juk jos visos paimtos iš skirtingų teksto variklio egzempliorių, atitinkančių vartotojus. Tikslas yra surūšiuoti pranešimus ir atsikratyti kopijų, kurios užima nereikalingą vietą.
Kiekvienas pranešimas turi laiko žymą, kurioje nurodomas jo išsiuntimo laikas ir tekstas. Laiką išnaudojame rūšiavimui – dedame rodykles į seniausius multichat dalyvių pranešimus ir lyginame numatytų kopijų teksto maišas, judame link laiko žymos didinimo. Logiška, kad kopijos turės tą pačią maišą ir laiko žymą, tačiau praktiškai tai ne visada. Kaip prisimenate, sinchronizavimą senoje schemoje atliko PHP – retais atvejais skirtingų vartotojų to paties pranešimo išsiuntimo laikas skyrėsi. Tokiais atvejais leidome sau redaguoti laiko žymą – paprastai per sekundę. Antroji problema yra skirtinga pranešimų tvarka skirtingiems gavėjams. Tokiais atvejais leidome sukurti papildomą kopiją su skirtingomis užsakymo parinktimis skirtingiems vartotojams.
Po to duomenys apie daugiakalbių pokalbių pranešimus siunčiami į vartotojo variklį. Ir čia atsiranda nemaloni importuotų pranešimų savybė. Įprastai veikiant pranešimai, kurie ateina į variklį, yra išdėstyti griežtai didėjančia tvarka pagal user_local_id. Iš senojo variklio į vartotojo variklį importuoti pranešimai prarado šią naudingą savybę. Tuo pačiu metu testavimo patogumui reikia turėti galimybę greitai juos pasiekti, ko nors juose ieškoti ir pridėti naujų.
Importuotiems pranešimams saugoti naudojame specialią duomenų struktūrą.
Tai reiškia dydžio vektorių kur visi - yra skirtingi ir išdėstyti mažėjančia tvarka su specialia elementų tvarka. Kiekviename segmente su indeksais elementai rūšiuojami. Elemento paieška tokioje struktūroje užtrunka per dvejetainės paieškos. Elemento pridėjimas amortizuojamas .
Taigi, mes supratome, kaip perkelti duomenis iš senų variklių į naujus. Tačiau šis procesas užtrunka kelias dienas – ir mažai tikėtina, kad per šias dienas mūsų vartotojai atsisakys įpročio rašyti vieni kitiems. Kad per šį laiką neprarastume pranešimų, pereiname prie darbo schemos, kurioje naudojami ir senieji, ir nauji klasteriai.
Duomenys įrašomi į pokalbių narius ir vartotojo variklį (o ne į tekstinį variklį, kaip įprastai veikiant pagal seną schemą). user-engine perduoda užklausą pokalbių varikliui – ir čia elgsena priklauso nuo to, ar šis pokalbis jau buvo sujungtas, ar ne. Jei pokalbis dar nesujungtas, pokalbių variklis pranešimo sau nerašo, o jo apdorojimas vyksta tik tekstiniame variklyje. Jei pokalbis jau buvo sujungtas su pokalbių varikliu, jis grąžina chat_local_id vartotojo varikliui ir išsiunčia pranešimą visiems gavėjams. user-engine visus duomenis perduoda tekstiniam varikliui – kad, jei kas nors atsitiktų, visada galėtume grįžti atgal, turėdami visus esamus duomenis senajame variklyje. text-engine grąžina user_local_id, kurį vartotojo variklis išsaugo ir grąžina į užpakalinę programą.
Dėl to perėjimo procesas atrodo taip: sujungiame tuščias vartotojo ir pokalbių variklio grupes. pokalbių variklis nuskaito visą pokalbių narių žurnalą, tada pradedamas tarpinis serveris pagal aukščiau aprašytą schemą. Perkeliame senus duomenis ir gauname du sinchronizuotus klasterius (seną ir naują). Belieka perjungti skaitymą iš teksto į vartotojo variklį ir išjungti tarpinį serverį.
rezultatai
Dėl naujo požiūrio buvo patobulinti visi variklių veikimo rodikliai ir išspręstos duomenų nuoseklumo problemos. Dabar galime greitai įdiegti naujas žinučių funkcijas (ir jau pradėjome tai daryti – padidinome maksimalų pokalbio dalyvių skaičių, įdiegėme persiųstų pranešimų paiešką, paleidome prisegtus pranešimus ir padidinome bendro pranešimų skaičiaus vienam vartotojui limitą) .
Logikos pokyčiai tikrai didžiuliai. Ir norėčiau pastebėti, kad tai ne visada reiškia ištisus metus didžiulės komandos ir daugybės kodo eilučių. pokalbių variklis ir vartotojo variklis kartu su visomis papildomomis istorijomis, tokiomis kaip „Huffman“ pranešimų suspaudimui, „Splay“ medžiai ir importuotų pranešimų struktūra, yra mažiau nei 20 tūkstančių kodo eilučių. Ir juos parašė 3 kūrėjai vos per 10 mėnesių (tačiau verta turėti omenyje, kad – pasaulio čempionai ).
Be to, užuot padvigubinę serverių skaičių, sumažinome jų skaičių perpus – dabar vartotojo variklis ir pokalbių variklis veikia 500 fizinių mašinų, o naujoji schema turi didelę apkrovos erdvę. Sutaupėme daug pinigų įrangai – apie 5 mln. USD + 750 tūkst. USD per metus veiklos išlaidų.
Stengiamės rasti geriausius sprendimus sudėtingiausioms ir didelio masto problemoms spręsti. Jų turime daug – todėl duomenų bazių skyriuje ieškome talentingų kūrėjų. Jeigu mėgstate ir mokate spręsti tokias problemas, puikiai išmanote algoritmus ir duomenų struktūras, kviečiame prisijungti prie komandos. Susisiekite su mumis dėl detalių.
Net jei ši istorija ne apie jus, atkreipkite dėmesį, kad mes vertiname rekomendacijas. Papasakok draugui apie , o jei jis sėkmingai baigs bandomąjį laikotarpį, gausite 100 tūkstančių rublių premiją.
Šaltinis: www.habr.com