Isulat muli ang database ng mensahe ng VKontakte mula sa simula at mabuhay

Ang aming mga gumagamit ay nagsusulat ng mga mensahe sa isa't isa nang hindi nalalaman ang pagkapagod.

Medyo marami iyon. Kung itinakda mong basahin ang lahat ng mga mensahe ng lahat ng mga gumagamit, aabutin ito ng higit sa 150 libong taon. Sa kondisyon na ikaw ay isang medyo advanced na mambabasa at gumugugol ng hindi hihigit sa isang segundo sa bawat mensahe.

Sa ganoong dami ng data, kritikal na ang lohika para sa pag-iimbak at pag-access nito ay binuo nang mahusay. Kung hindi, sa isang hindi-kahanga-hangang sandali, maaaring maging malinaw na ang lahat ay malapit nang magkamali.

Para sa amin, dumating ang sandaling ito isang taon at kalahati na ang nakalipas. Paano kami nakarating dito at kung ano ang nangyari sa huli - sasabihin namin sa iyo sa pagkakasunud-sunod.

kasaysayan ng kaso

Sa pinakaunang pagpapatupad, ang mga mensahe ng VKontakte ay nagtrabaho sa isang kumbinasyon ng PHP backend at MySQL. Ito ay isang ganap na normal na solusyon para sa isang maliit na website ng mag-aaral. Gayunpaman, ang site na ito ay lumago nang hindi mapigilan at nagsimulang humingi ng pag-optimize ng mga istruktura ng data para sa sarili nito.

Sa katapusan ng 2009, ang unang text-engine repository ay isinulat, at noong 2010 ang mga mensahe ay inilipat dito.

Sa text-engine, ang mga mensahe ay naka-imbak sa mga listahan - isang uri ng "mga mailbox". Ang bawat naturang listahan ay tinutukoy ng isang uid - ang user na nagmamay-ari ng lahat ng mga mensaheng ito. Ang isang mensahe ay may isang hanay ng mga katangian: interlocutor identifier, text, attachment, at iba pa. Ang identifier ng mensahe sa loob ng "kahon" ay local_id, hindi ito nagbabago at itinalaga nang sunud-sunod para sa mga bagong mensahe. Ang "mga kahon" ay independyente at hindi naka-synchronize sa isa't isa sa loob ng engine; ang komunikasyon sa pagitan ng mga ito ay nangyayari sa antas ng PHP. Maaari mong tingnan ang istraktura ng data at mga kakayahan ng text-engine mula sa loob dito.

Ito ay sapat na para sa pagsusulatan sa pagitan ng dalawang user. Hulaan mo kung ano ang sumunod na nangyari?

Noong Mayo 2011, ipinakilala ng VKontakte ang mga pag-uusap sa ilang kalahok—multi-chat. Upang makipagtulungan sa kanila, nagtaas kami ng dalawang bagong kumpol - mga chat ng miyembro at mga miyembro ng chat. Ang una ay nag-iimbak ng data tungkol sa mga chat ng mga user, ang pangalawa ay nag-iimbak ng data tungkol sa mga user sa pamamagitan ng mga chat. Bilang karagdagan sa mga listahan mismo, kabilang dito, halimbawa, ang nag-iimbitang user at ang oras na idinagdag sila sa chat.

"PHP, magpadala tayo ng mensahe sa chat," sabi ng user.
“Halika, {username},” sabi ng PHP.

May mga disadvantages sa scheme na ito. Ang pag-synchronize ay responsibilidad pa rin ng PHP. Ang malalaking chat at user na sabay-sabay na nagpapadala ng mga mensahe sa kanila ay isang mapanganib na kwento. Dahil ang text-engine instance ay nakadepende sa uid, ang mga kalahok sa chat ay maaaring makatanggap ng parehong mensahe sa iba't ibang oras. Ang isa ay mabubuhay sa ganito kung ang pag-unlad ay tumigil. Ngunit hindi iyon mangyayari.

Sa pagtatapos ng 2015, naglunsad kami ng mga mensahe sa komunidad, at sa simula ng 2016, naglunsad kami ng API para sa kanila. Sa pagdating ng malalaking chatbots sa mga komunidad, posible na kalimutan ang tungkol sa kahit na pamamahagi ng pag-load.

Ang isang mahusay na bot ay bumubuo ng ilang milyong mga mensahe bawat araw - kahit na ang pinakamadaldal na mga gumagamit ay hindi maaaring ipagmalaki ito. Nangangahulugan ito na ang ilang mga pagkakataon ng text-engine, kung saan nabuhay ang naturang mga bot, ay nagsimulang magdusa nang husto.

Ang mga Message engine sa 2016 ay 100 instance ng mga chat-member at member-chat, at 8000 text-engine. Sila ay naka-host sa isang libong mga server, bawat isa ay may 64 GB ng memorya. Bilang unang panukalang pang-emergency, dinagdagan namin ang memory ng isa pang 32 GB. Tinantya namin ang mga pagtataya. Kung walang matinding pagbabago, ito ay magiging sapat para sa halos isa pang taon. Kailangan mong kunin ang hardware o i-optimize ang mga database mismo.

Dahil sa likas na katangian ng arkitektura, makatuwiran lamang na dagdagan ang hardware sa maramihang. Iyon ay, hindi bababa sa pagdodoble ng bilang ng mga kotse - malinaw naman, ito ay isang medyo mahal na landas. I-optimize namin.

Bagong konsepto

Ang pangunahing diwa ng bagong diskarte ay chat. Ang isang chat ay may listahan ng mga mensahe na nauugnay dito. Ang user ay may listahan ng mga chat.

Ang kinakailangang minimum ay dalawang bagong database:

• chat-engine. Ito ay isang imbakan ng mga vector ng chat. Ang bawat chat ay may vector ng mga mensahe na nauugnay dito. Ang bawat mensahe ay may isang text at isang natatanging identifier ng mensahe sa loob ng chat - chat_local_id.
• user-engine. Ito ay isang imbakan ng mga vector ng gumagamit - mga link sa mga gumagamit. Ang bawat user ay may vector ng peer_id (mga interlocutor - ibang user, multi-chat o mga komunidad) at isang vector ng mga mensahe. Ang bawat peer_id ay may vector ng mga mensahe na nauugnay dito. Ang bawat mensahe ay may chat_local_id at isang natatanging message ID para sa user na iyon - user_local_id.

Ang mga bagong cluster ay nakikipag-usap sa isa't isa gamit ang TCP - tinitiyak nito na ang pagkakasunud-sunod ng mga kahilingan ay hindi magbabago. Ang mga kahilingan mismo at mga kumpirmasyon para sa kanila ay naitala sa hard drive - upang maibalik namin ang estado ng pila anumang oras pagkatapos ng pagkabigo o pag-restart ng makina. Dahil ang user-engine at chat-engine ay 4 na libong shards bawat isa, ang queue ng kahilingan sa pagitan ng mga cluster ay ipapamahagi nang pantay-pantay (ngunit sa katotohanan ay wala - at ito ay gumagana nang napakabilis).

Ang pagtatrabaho sa disk sa aming mga database sa karamihan ng mga kaso ay batay sa isang kumbinasyon ng isang binary log ng mga pagbabago (binlog), mga static na snapshot at isang bahagyang imahe sa memorya. Ang mga pagbabago sa araw ay isinusulat sa isang binlog, at pana-panahong ginagawa ang isang snapshot ng kasalukuyang estado. Ang snapshot ay isang koleksyon ng mga istruktura ng data na na-optimize para sa aming mga layunin. Binubuo ito ng isang header (metaindex ng imahe) at isang set ng mga metafile. Ang header ay permanenteng nakaimbak sa RAM at nagpapahiwatig kung saan hahanapin ang data mula sa snapshot. Kasama sa bawat metafile ang data na malamang na kailanganin sa malapit na oras—halimbawa, nauugnay sa isang user. Kapag nag-query ka sa database gamit ang snapshot header, babasahin ang kinakailangang metafile, at pagkatapos ay isasaalang-alang ang mga pagbabago sa binlog na naganap pagkatapos malikha ang snapshot. Maaari kang magbasa nang higit pa tungkol sa mga benepisyo ng diskarteng ito dito.

Kasabay nito, ang data sa hard drive mismo ay nagbabago nang isang beses lamang sa isang araw - huli sa gabi sa Moscow, kapag ang load ay minimal. Salamat sa ito (alam na ang istraktura sa disk ay pare-pareho sa buong araw), maaari naming kayang palitan ang mga vector na may mga arrays ng isang nakapirming laki - at dahil dito, makakuha ng memorya.

Ang pagpapadala ng mensahe sa bagong scheme ay ganito ang hitsura:

1. Ang PHP backend ay nakikipag-ugnayan sa user-engine na may kahilingang magpadala ng mensahe.
2. proxies ng user-engine ang kahilingan sa gustong instance ng chat-engine, na babalik sa user-engine chat_local_id - isang natatanging identifier ng isang bagong mensahe sa loob ng chat na ito. Pagkatapos ay i-broadcast ng chat_engine ang mensahe sa lahat ng mga tatanggap sa chat.
3. tumatanggap ang user-engine ng chat_local_id mula sa chat-engine at ibinabalik ang user_local_id sa PHP - isang natatanging identifier ng mensahe para sa user na ito. Ang identifier na ito ay ginagamit, halimbawa, upang gumana sa mga mensahe sa pamamagitan ng API.

Ngunit bilang karagdagan sa aktwal na pagpapadala ng mga mensahe, kailangan mong ipatupad ang ilang mas mahahalagang bagay:

• Ang mga sublist ay, halimbawa, ang pinakakamakailang mga mensahe na nakikita mo kapag binubuksan ang listahan ng pag-uusap. Mga hindi pa nababasang mensahe, mensaheng may mga tag ("Mahalaga", "Spam", atbp.).
• Pag-compress ng mga mensahe sa chat-engine
• Pag-cache ng mga mensahe sa user-engine
• Maghanap (sa lahat ng mga dialog at sa loob ng isang partikular).
• Real-time na update (Longpolling).
• Sine-save ang history para ipatupad ang caching sa mga mobile client.

Ang lahat ng mga sublist ay mabilis na nagbabago ng mga istruktura. Upang magtrabaho kasama sila ginagamit namin Splay puno. Ang pagpipiliang ito ay ipinaliwanag sa pamamagitan ng katotohanan na sa tuktok ng puno kung minsan ay nag-iimbak kami ng isang buong segment ng mga mensahe mula sa isang snapshot - halimbawa, pagkatapos ng gabi-gabing muling pag-index, ang puno ay binubuo ng isang tuktok, na naglalaman ng lahat ng mga mensahe ng sublist. Pinapadali ng Splay tree ang pagpasok sa gitna ng naturang vertex nang hindi na kailangang mag-isip tungkol sa pagbabalanse. Bilang karagdagan, ang Splay ay hindi nag-iimbak ng hindi kinakailangang data, na nakakatipid sa amin ng memorya.

Ang mga mensahe ay nagsasangkot ng malaking halaga ng impormasyon, karamihan ay teksto, na kapaki-pakinabang upang makapag-compress. Mahalaga na maaari nating tumpak na alisin sa archive ang kahit isang indibidwal na mensahe. Ginagamit upang i-compress ang mga mensahe Algoritmo ng Huffman gamit ang aming sariling heuristics - halimbawa, alam namin na sa mga mensahe ang mga salita ay kahalili ng "hindi mga salita" - mga puwang, mga marka ng bantas - at naaalala din namin ang ilan sa mga kakaibang paggamit ng mga simbolo para sa wikang Ruso.

Dahil mas kaunti ang mga user kaysa sa mga chat, para i-save ang mga random-access na kahilingan sa disk sa chat-engine, ini-cache namin ang mga mensahe sa user-engine.

Ang paghahanap ng mensahe ay ipinatupad bilang isang dayagonal na query mula sa user-engine hanggang sa lahat ng mga instance ng chat-engine na naglalaman ng mga chat ng user na ito. Ang mga resulta ay pinagsama sa mismong user-engine.

Buweno, ang lahat ng mga detalye ay isinasaalang-alang, ang natitira lamang ay lumipat sa isang bagong pamamaraan - at mas mabuti nang hindi ito napapansin ng mga gumagamit.

Paglipat ng data

Kaya, mayroon kaming text-engine na nag-iimbak ng mga mensahe ayon sa user, at dalawang cluster na chat-member at member-chat na nag-iimbak ng data tungkol sa mga multi-chat room at ang mga user sa kanila. Paano lumipat mula dito sa bagong user-engine at chat-engine?

Ang mga chat sa miyembro sa lumang pamamaraan ay pangunahing ginamit para sa pag-optimize. Mabilis naming inilipat ang kinakailangang data mula dito sa mga miyembro ng chat, at pagkatapos ay hindi na ito lumahok sa proseso ng paglipat.

Pila para sa mga miyembro ng chat. Kabilang dito ang 100 mga pagkakataon, habang ang chat-engine ay may 4 na libo. Upang ilipat ang data, kailangan mong dalhin ito sa pagsunod - para dito, ang mga miyembro ng chat ay nahahati sa parehong 4 na libong kopya, at pagkatapos ay pinagana ang pagbabasa ng binlog ng mga miyembro ng chat sa chat-engine.

Ngayon alam na ng chat-engine ang tungkol sa multi-chat mula sa mga miyembro ng chat, ngunit wala pa itong alam tungkol sa mga dialogue sa dalawang kausap. Ang ganitong mga dialogue ay matatagpuan sa text-engine na may reference sa mga user. Dito namin kinuha ang data "head-on": ang bawat chat-engine instance ay nagtanong sa lahat ng text-engine instance kung mayroon sila ng dialogue na kailangan nito.

Mahusay - alam ng chat-engine kung ano ang mga multi-chat na chat at alam kung anong mga dialogue ang mayroon.
Kailangan mong pagsamahin ang mga mensahe sa mga multi-chat na chat upang magkaroon ka ng listahan ng mga mensahe sa bawat chat. Una, kinukuha ng chat-engine mula sa text-engine ang lahat ng mensahe ng user mula sa chat na ito. Sa ilang mga kaso ay medyo marami sa kanila (hanggang sa daan-daang milyon), ngunit may napakabihirang mga pagbubukod ang chat ay ganap na umaangkop sa RAM. Mayroon kaming mga hindi nakaayos na mensahe, bawat isa sa ilang mga kopya - pagkatapos ng lahat, lahat sila ay nakuha mula sa iba't ibang mga text-engine na instance na naaayon sa mga user. Ang layunin ay pag-uri-uriin ang mga mensahe at alisin ang mga kopya na kumukuha ng hindi kinakailangang espasyo.

Ang bawat mensahe ay may timestamp na naglalaman ng oras na ipinadala ito at text. Gumagamit kami ng oras para sa pag-uuri - naglalagay kami ng mga pointer sa mga pinakalumang mensahe ng mga kalahok sa multichat at naghahambing ng mga hash mula sa teksto ng mga nilalayong kopya, patungo sa pagtaas ng timestamp. Lohikal na ang mga kopya ay magkakaroon ng parehong hash at timestamp, ngunit sa pagsasagawa, hindi ito palaging nangyayari. Tulad ng naaalala mo, ang pag-synchronize sa lumang scheme ay isinagawa ng PHP - at sa mga bihirang kaso, ang oras ng pagpapadala ng parehong mensahe ay naiiba sa iba't ibang mga gumagamit. Sa mga kasong ito, pinahintulutan namin ang aming sarili na i-edit ang timestamp - kadalasan sa loob ng isang segundo. Ang pangalawang problema ay ang magkakaibang pagkakasunud-sunod ng mga mensahe para sa iba't ibang tatanggap. Sa ganitong mga kaso, pinayagan namin ang isang karagdagang kopya na malikha, na may iba't ibang mga opsyon sa pag-order para sa iba't ibang mga user.

Pagkatapos nito, ang data tungkol sa mga mensahe sa multichat ay ipinadala sa user-engine. At narito ang isang hindi kasiya-siyang tampok ng mga na-import na mensahe. Sa normal na operasyon, ang mga mensahe na dumarating sa engine ay mahigpit na inuutusan sa pataas na pagkakasunud-sunod ng user_local_id. Ang mga mensaheng na-import mula sa lumang engine papunta sa user-engine ay nawala ang kapaki-pakinabang na katangiang ito. Kasabay nito, para sa kaginhawaan ng pagsubok, kailangan mong mabilis na ma-access ang mga ito, maghanap ng isang bagay sa kanila at magdagdag ng mga bago.

Gumagamit kami ng espesyal na istraktura ng data upang mag-imbak ng mga na-import na mensahe.

Ito ay kumakatawan sa isang vector ng laki nasaan ang lahat - ay naiiba at inayos sa pababang pagkakasunud-sunod, na may espesyal na pagkakasunud-sunod ng mga elemento. Sa bawat segment na may mga indeks pinagsunod-sunod ang mga elemento. Ang paghahanap para sa isang elemento sa naturang istraktura ay nangangailangan ng oras sa pamamagitan ng binary na paghahanap. Ang pagdaragdag ng isang elemento ay amortized .

Kaya, naisip namin kung paano maglipat ng data mula sa mga lumang makina patungo sa mga bago. Ngunit ang prosesong ito ay tumatagal ng ilang araw - at ito ay malamang na sa mga araw na ito ay talikuran ng aming mga user ang ugali ng pagsulat sa isa't isa. Upang hindi mawala ang mga mensahe sa panahong ito, lumipat kami sa isang scheme ng trabaho na gumagamit ng mga luma at bagong cluster.

Ang data ay isinulat sa mga miyembro ng chat at user-engine (at hindi sa text-engine, tulad ng sa normal na operasyon ayon sa lumang pamamaraan). proxies ng user-engine ang kahilingan sa chat-engine - at dito ang pag-uugali ay depende sa kung ang chat na ito ay pinagsama na o hindi. Kung ang chat ay hindi pa pinagsama, ang chat-engine ay hindi nagsusulat ng mensahe sa sarili nito, at ang pagproseso nito ay nangyayari lamang sa text-engine. Kung ang chat ay pinagsama na sa chat-engine, ibabalik nito ang chat_local_id sa user-engine at ipapadala ang mensahe sa lahat ng mga tatanggap. Ini-proxy ng user-engine ang lahat ng data sa text-engine - nang sa gayon kung may mangyari, maaari tayong palaging mag-roll back, na nasa lumang engine ang lahat ng kasalukuyang data. ibinabalik ng text-engine ang user_local_id, na iniimbak at ibinabalik ng user-engine sa backend.

Bilang resulta, ganito ang hitsura ng proseso ng paglipat: ikinokonekta namin ang mga walang laman na cluster ng user-engine at chat-engine. Binabasa ng chat-engine ang buong binlog ng mga miyembro ng chat, pagkatapos ay magsisimula ang proxying ayon sa pamamaraang inilarawan sa itaas. Inilipat namin ang lumang data at kumuha ng dalawang naka-synchronize na kumpol (luma at bago). Ang natitira na lang ay ilipat ang pagbabasa mula sa text-engine patungo sa user-engine at huwag paganahin ang proxying.

Natuklasan

Salamat sa bagong diskarte, lahat ng sukatan ng pagganap ng mga makina ay napabuti at ang mga problema sa pagkakapare-pareho ng data ay nalutas. Ngayon ay mabilis na naming maipapatupad ang mga bagong feature sa mga mensahe (at sinimulan na naming gawin ito - dinagdagan namin ang maximum na bilang ng mga kalahok sa chat, nagpatupad ng paghahanap para sa mga ipinasa na mensahe, naglunsad ng mga naka-pin na mensahe at tinaasan ang limitasyon sa kabuuang bilang ng mga mensahe sa bawat user) .

Ang mga pagbabago sa lohika ay tunay na napakalaki. At nais kong tandaan na hindi ito palaging nangangahulugan ng buong taon ng pag-unlad ng isang malaking koponan at libu-libong mga linya ng code. chat-engine at user-engine kasama ang lahat ng karagdagang kwento tulad ng Huffman para sa pag-compress ng mensahe, Splay tree at istraktura para sa mga na-import na mensahe ay wala pang 20 libong linya ng code. At sila ay isinulat ng 3 developer sa loob lamang ng 10 buwan (gayunpaman, ito ay nagkakahalaga na tandaan na lahat tatlo developer - mga kampeon sa mundo sa sports programming).

Bukod dito, sa halip na doblehin ang bilang ng mga server, binawasan namin ang kanilang bilang ng kalahati - ngayon ang user-engine at chat-engine ay nakatira sa 500 pisikal na makina, habang ang bagong scheme ay may malaking headroom para sa pagkarga. Nakatipid kami ng maraming pera sa kagamitan - humigit-kumulang $5 milyon + $750 libo bawat taon sa mga gastusin sa pagpapatakbo.

Nagsusumikap kaming makahanap ng mga pinakamahusay na solusyon para sa mga pinakamasalimuot at malalaking problema. Marami kami sa kanila - at iyon ang dahilan kung bakit naghahanap kami ng mga mahuhusay na developer sa departamento ng database. Kung mahal mo at alam mo kung paano lutasin ang mga ganitong problema, may mahusay na kaalaman sa mga algorithm at istruktura ng data, inaanyayahan ka naming sumali sa koponan. Makipag-ugnayan sa aming HRpara sa mga detalye.

Kahit na ang kuwentong ito ay hindi tungkol sa iyo, pakitandaan na pinahahalagahan namin ang mga rekomendasyon. Sabihin sa isang kaibigan ang tungkol sa mga bakante sa developer, at kung matagumpay niyang nakumpleto ang panahon ng pagsubok, makakatanggap ka ng bonus na 100 libong rubles.

Pinagmulan: www.habr.com