Ang among mga tiggamit nagsulat sa mga mensahe sa usag usa nga wala nahibal-an ang kakapoy.
Daghan kaayo kana. Kung gisugdan nimo ang pagbasa sa tanan nga mga mensahe sa tanan nga mga tiggamit, kini molungtad labaw pa sa 150 ka libo ka tuig. Sa kondisyon nga ikaw usa ka medyo advanced nga magbabasa ug mogugol og dili molapas sa usa ka segundo sa matag mensahe.
Uban sa ingon nga usa ka gidaghanon sa mga data, kini mao ang kritikal nga ang lohika alang sa pagtipig ug pag-access niini mao ang maayo nga gitukod. Kung dili, sa usa ka dili kaayo katingad-an nga higayon, mahimong klaro nga ang tanan sa dili madugay mahimong sayup.
Alang kanamo, kini nga higayon miabut usa ka tuig ug tunga ang milabay. Giunsa namon kini ug kung unsa ang nahitabo sa katapusan - gisultihan ka namon sa pagkasunud.
Background
Sa una nga pagpatuman, ang mga mensahe sa VKontakte nagtrabaho sa usa ka kombinasyon sa PHP backend ug MySQL. Kini usa ka hingpit nga normal nga solusyon alang sa usa ka gamay nga website sa estudyante. Bisan pa, kini nga site mitubo nga dili mapugngan ug nagsugod sa pagpangayo sa pag-optimize sa mga istruktura sa datos alang sa iyang kaugalingon.
Sa katapusan sa 2009, ang unang text-engine repository gisulat, ug sa 2010 mga mensahe gibalhin ngadto niini.
Sa text-engine, ang mga mensahe gitipigan sa mga lista - usa ka matang sa "mga mailbox". Ang matag ingon nga lista gitino sa usa ka uid - ang tiggamit nga tag-iya niining tanan nga mga mensahe. Ang usa ka mensahe adunay usa ka hugpong sa mga hiyas: interlocutor identifier, text, attachment, ug uban pa. Ang identifier sa mensahe sa sulod sa "kahon" mao ang local_id, dili kini mausab ug gi-assign nga sunud-sunod alang sa mga bag-ong mensahe. Ang "mga kahon" independente ug wala magkadungan sa usag usa sulod sa makina; ang komunikasyon tali kanila mahitabo sa lebel sa PHP. Mahimo nimong tan-awon ang istruktura sa datos ug mga kapabilidad sa text-engine gikan sa sulod .
Kini igo na alang sa mga sulat tali sa duha ka tiggamit. Ambot unsay sunod nga nahitabo?
Niadtong Mayo 2011, gipaila sa VKontakte ang mga panag-istoryahanay sa daghang mga partisipante-multi-chat. Aron makigtambayayong kanila, nagpataas kami og duha ka bag-ong mga cluster - mga miyembro-chat ug chat-mga miyembro. Ang una nagtipig data bahin sa mga chat sa mga tiggamit, ang ikaduha nagtipig data bahin sa mga tiggamit pinaagi sa mga chat. Dugang pa sa mga lista mismo, naglakip kini, pananglitan, ang nag-imbitar nga tiggamit ug ang oras nga gidugang sila sa chat.
"PHP, magpadala ta og mensahe sa chat," miingon ang user.
βDali, {username},β niingon ang PHP.
Adunay mga disbentaha niini nga laraw. Ang pag-synchronize kay responsibilidad gihapon sa PHP. Ang dagkong mga chat ug mga tiggamit nga dungan nga nagpadala og mga mensahe ngadto kanila usa ka makuyaw nga istorya. Tungod kay ang text-engine instance nagdepende sa uid, ang mga partisipante sa chat makadawat sa samang mensahe sa lain-laing mga panahon. Mahimong mabuhi ang usa niini kung ang pag-uswag mohunong. Apan dili kana mahitabo.
Sa katapusan sa 2015, naglunsad kami og mga mensahe sa komunidad, ug sa sinugdanan sa 2016, naglunsad kami og API alang kanila. Sa pag-abut sa dagkong mga chatbot sa mga komunidad, posible nga makalimtan ang bahin sa bisan ang pag-apod-apod sa load.
Ang usa ka maayo nga bot makamugna daghang milyon nga mga mensahe matag adlaw - bisan ang labi ka labi nga nagsulti nga tiggamit dili makapanghambog niini. Kini nagpasabot nga ang pipila ka mga higayon sa text-engine, diin ang maong mga bots nagpuyo, nagsugod sa pag-antus sa hingpit.
Ang mga makina sa mensahe sa 2016 mao ang 100 nga mga higayon sa mga miyembro sa chat ug mga chat sa miyembro, ug 8000 nga mga makina sa text. Gi-host sila sa usa ka libo nga mga server, ang matag usa adunay 64 GB nga memorya. Ingon usa ka una nga lakang sa emerhensya, gidugangan namon ang memorya sa lain nga 32 GB. Gibanabana namo ang mga panagna. Kung walaβy daghang mga pagbag-o, kini igo na alang sa mga usa pa ka tuig. Kinahanglan nimo nga makuha ang hardware o i-optimize ang mga database mismo.
Tungod sa kinaiyahan sa arkitektura, makatarunganon nga madugangan ang hardware sa daghang. Kana mao, labing menos pagdoble sa gidaghanon sa mga sakyanan - klaro, kini usa ka medyo mahal nga dalan. Atong i-optimize.
Bag-ong konsepto
Ang sentro nga diwa sa bag-ong pamaagi mao ang chat. Ang usa ka chat adunay lista sa mga mensahe nga may kalabutan niini. Ang tiggamit adunay usa ka lista sa mga chat.
Ang gikinahanglan nga minimum mao ang duha ka bag-ong database:
- chat-engine. Kini usa ka tipiganan sa mga vector sa chat. Ang matag chat adunay usa ka vector sa mga mensahe nga may kalabutan niini. Ang matag mensahe adunay usa ka teksto ug usa ka talagsaon nga identifier sa mensahe sulod sa chat - chat_local_id.
- user-engine. Kini usa ka pagtipig sa mga vector sa mga tiggamit - mga link sa mga tiggamit. Ang matag user adunay vector sa peer_id (mga interlocutors - ubang user, multi-chat o komunidad) ug vector sa mga mensahe. Ang matag peer_id adunay vector sa mga mensahe nga may kalabutan niini. Ang matag mensahe adunay chat_local_id ug usa ka talagsaon nga ID sa mensahe alang niana nga user - user_local_id.
Ang mga bag-ong cluster nakigsulti sa usag usa gamit ang TCP - kini nagsiguro nga ang han-ay sa mga hangyo dili mausab. Ang mga hangyo sa ilang kaugalingon ug mga kumpirmasyon alang kanila girekord sa hard drive - aron mapasig-uli namo ang kahimtang sa pila sa bisan unsang oras human sa pagkapakyas o pag-restart sa makina. Tungod kay ang user-engine ug chat-engine mga 4 ka libo nga mga shards matag usa, ang hangyo nga pila sa taliwala sa mga pungpong ipang-apod-apod nga parehas (apan sa tinuud wala gyud - ug kini molihok kaayo).
Ang pagtrabaho kauban ang disk sa among mga database sa kadaghanan nga mga kaso gibase sa usa ka kombinasyon sa usa ka binary log sa mga pagbag-o (binlog), static nga mga snapshot ug usa ka partial nga imahe sa memorya. Ang mga pagbag-o sa adlaw gisulat sa usa ka binlog, ug usa ka snapshot sa karon nga kahimtang gihimo matag karon ug unya. Ang snapshot usa ka koleksyon sa mga istruktura sa datos nga na-optimize alang sa among mga katuyoan. Naglangkob kini sa usa ka ulohan (metaindex sa imahe) ug usa ka hugpong sa mga metafile. Ang header permanente nga gitipigan sa RAM ug nagpaila kung asa pangitaon ang datos gikan sa snapshot. Ang matag metafile naglakip sa datos nga lagmit gikinahanglan sa duol nga mga punto sa panahonβpananglitan, may kalabotan sa usa ka user. Kung imong gipangutana ang database gamit ang snapshot header, ang gikinahanglan nga metafile gibasa, ug dayon ang mga pagbag-o sa binlog nga nahitabo pagkahuman nabuhat ang snapshot gikonsiderar. Makabasa ka og dugang mahitungod sa mga benepisyo niini nga pamaagi .
Sa parehas nga oras, ang datos sa hard drive mismo nagbag-o kausa sa usa ka adlaw - sa gabii sa Moscow, kung gamay ra ang karga. Salamat niini (nahibal-an nga ang istruktura sa disk kanunay sa tibuok adlaw), mahimo namong ilisan ang mga vector sa mga arrays sa usa ka fixed size - ug tungod niini, makaangkon sa memorya.
Ang pagpadala sa usa ka mensahe sa bag-ong laraw ingon niini:
- Ang PHP backend nagkontak sa user-engine nga adunay hangyo nga magpadala ug mensahe.
- user-engine proxy ang hangyo ngadto sa gusto nga chat-engine nga pananglitan, nga mobalik ngadto sa user-engine chat_local_id - usa ka talagsaon nga identifier sa usa ka bag-ong mensahe sulod niini nga chat. Ang chat_engine dayon nagsibya sa mensahe ngadto sa tanang nakadawat sa chat.
- Ang user-engine makadawat og chat_local_id gikan sa chat-engine ug ibalik ang user_local_id ngadto sa PHP - usa ka talagsaon nga identifier sa mensahe alang niini nga user. Kini nga identifier gigamit dayon, pananglitan, sa pagtrabaho sa mga mensahe pinaagi sa API.
Apan dugang sa aktwal nga pagpadala sa mga mensahe, kinahanglan nimong ipatuman ang pipila ka mas importante nga mga butang:
- Ang mga sublist, pananglitan, ang pinakabag-o nga mga mensahe nga imong makita sa dihang giablihan ang lista sa panag-istoryahanay. Wala pa mabasa nga mga mensahe, mga mensahe nga adunay mga tag ("Importante", "Spam", ug uban pa).
- Pag-compress sa mga mensahe sa chat-engine
- Pag-cache sa mga mensahe sa user-engine
- Pagpangita (sa tanan nga mga diyalogo ug sulod sa usa ka piho).
- Real-time nga update (Longpolling).
- Pag-save sa kasaysayan aron ipatuman ang caching sa mga kliyente sa mobile.
Ang tanan nga mga sublist paspas nga nagbag-o nga mga istruktura. Sa pagtrabaho uban kanila among gigamit . Kini nga pagpili gipatin-aw pinaagi sa kamatuoran nga sa ibabaw sa kahoy kita usahay magtipig sa tibuok nga bahin sa mga mensahe gikan sa usa ka snapshot - pananglitan, human sa matag gabii nga pag-reindex, ang kahoy naglangkob sa usa ka tumoy, nga naglangkob sa tanang mga mensahe sa sublist. Gipasayon ββsa Splay tree ang pagsal-ot sa tunga sa maong vertex nga dili na kinahanglang maghunahuna bahin sa pagbalanse. Dugang pa, ang Splay wala magtipig sa wala kinahanglana nga datos, nga nagluwas kanamo sa panumduman.
Ang mga mensahe naglakip sa daghang impormasyon, kasagaran teksto, nga mapuslanon aron ma-compress. Importante nga mahimo natong tukma nga dili ma-archive ang bisan usa ka indibidwal nga mensahe. Gigamit sa pag-compress sa mga mensahe uban sa atong kaugalingon nga heuristics - pananglitan, nahibal-an namon nga sa mga mensahe ang mga pulong gipuli-puli sa "dili mga pulong" - mga luna, mga marka sa punctuation - ug nahinumdom usab kami sa pipila ka mga lahi sa paggamit sa mga simbolo alang sa pinulongang Ruso.
Tungod kay adunay mas gamay nga tiggamit kay sa mga chat, aron sa pagluwas sa random-access nga mga hangyo sa disk sa chat-engine, among gi-cache ang mga mensahe sa user-engine.
Ang pagpangita sa mensahe gipatuman isip usa ka diagonal nga pangutana gikan sa user-engine ngadto sa tanang chat-engine nga mga instance nga adunay mga chat niini nga user. Ang mga resulta gihiusa sa user-engine mismo.
Aw, ang tanan nga mga detalye gikonsiderar, ang nahabilin mao ang pagbalhin sa usa ka bag-ong laraw - ug labing maayo nga wala ang mga tiggamit nga nakamatikod niini.
Paglalin sa datos
Busa, kami adunay usa ka text-engine nga nagtipig sa mga mensahe sa user, ug duha ka cluster nga chat-member ug member-chat nga nagtipig og datos mahitungod sa multi-chat nga mga lawak ug sa mga tiggamit niini. Unsaon pagbalhin gikan niini ngadto sa bag-ong user-engine ug chat-engine?
Ang mga chat sa miyembro sa daan nga laraw gigamit una alang sa pag-optimize. Gibalhin dayon namo ang gikinahanglang datos gikan niini ngadto sa mga membro sa chat, ug unya wala na kini moapil sa proseso sa paglalin.
Pila para sa mga membro sa chat. Naglakip kini sa 100 ka mga higayon, samtang ang chat-engine adunay 4 ka libo. Aron mabalhin ang datos, kinahanglan nimo nga madala kini sa pagsunod - alang niini, ang mga miyembro sa chat gibahin sa parehas nga 4 ka libo nga mga kopya, ug dayon ang pagbasa sa binlog sa mga miyembro sa chat gipalihok sa chat-engine.
Karon nahibal-an na sa chat-engine ang bahin sa multi-chat gikan sa mga miyembro sa chat, apan wala pa kini nahibal-an bahin sa mga dayalogo sa duha ka mga interlocutors. Ang ingon nga mga dayalogo nahimutang sa text-engine nga adunay paghisgot sa mga tiggamit. Dinhi among gikuha ang data nga "head-on": ang matag chat-engine nga instance nangutana sa tanan nga text-engine nga mga instances kung aduna ba silay dialogue nga gikinahanglan niini.
Maayo - ang chat-engine nahibal-an kung unsa ang naa sa daghang mga chat ug nahibal-an kung unsa ang mga dayalogo.
Kinahanglan nimo nga i-combine ang mga mensahe sa multi-chat nga mga chat aron ikaw adunay usa ka lista sa mga mensahe sa matag chat. Una, gikuha sa chat-engine gikan sa text-engine ang tanang mensahe sa user gikan niini nga chat. Sa pipila ka mga kaso adunay daghan niini (hangtod sa gatusan ka milyon), apan uban sa talagsaon nga mga eksepsiyon ang chat hingpit nga mohaum sa RAM. Kami adunay mga mensahe nga wala ma-order, matag usa sa daghang mga kopya - pagkahuman, tanan sila gikuha gikan sa lainlaing mga higayon sa text-engine nga katumbas sa mga tiggamit. Ang tumong mao ang paghan-ay sa mga mensahe ug pagtangtang sa mga kopya nga mokuha sa wala kinahanglana nga luna.
Ang matag mensahe adunay timestamp nga naglangkob sa oras nga kini gipadala ug text. Gigamit namo ang oras sa paghan-ay - among gibutang ang mga pointer sa labing karaan nga mga mensahe sa mga partisipante sa multichat ug itandi ang mga hash gikan sa teksto sa gituyo nga mga kopya, nga nagpadulong sa pagdugang sa timestamp. Makataronganon nga ang mga kopya adunay parehas nga hash ug timestamp, apan sa praktis dili kini kanunay ang kaso. Sama sa imong nahinumduman, ang pag-synchronize sa daan nga laraw gihimo sa PHP - ug sa talagsaon nga mga kaso, ang oras sa pagpadala sa parehas nga mensahe lahi sa lainlaing mga tiggamit. Niining mga kasoha, gitugotan namo ang among kaugalingon sa pag-edit sa timestamp - kasagaran sulod sa usa ka segundo. Ang ikaduha nga problema mao ang lain-laing han-ay sa mga mensahe alang sa lain-laing mga nakadawat. Sa ingon nga mga kaso, gitugotan namon ang usa ka dugang nga kopya nga mahimo, nga adunay lainlaing mga kapilian sa pag-order alang sa lainlaing mga tiggamit.
Human niini, ang datos mahitungod sa mga mensahe sa multichat gipadala ngadto sa user-engine. Ug dinhi moabut ang usa ka dili maayo nga bahin sa imported nga mga mensahe. Sa normal nga operasyon, ang mga mensahe nga moabut sa makina estrikto nga gimando sa pataas nga han-ay sa user_local_id. Ang mga mensahe nga gi-import gikan sa daan nga makina ngadto sa user-engine nawala kining mapuslanon nga kabtangan. Sa parehas nga oras, alang sa kasayon ββββsa pagsulay, kinahanglan nimo nga dali nga ma-access kini, pangitaa ang usa ka butang sa kanila ug pagdugang mga bag-o.
Gigamit namo ang usa ka espesyal nga istruktura sa datos aron tipigan ang mga imported nga mensahe.
Kini nagrepresentar sa usa ka vector sa gidak-on asa ang tanan - lahi ug gimando sa paubos nga han-ay, nga adunay espesyal nga han-ay sa mga elemento. Sa matag bahin nga adunay mga indeks ang mga elemento gisunod. Ang pagpangita sa usa ka elemento sa ingon nga istruktura nagkinahanglag panahon pinaagi sa binary nga pagpangita. Ang pagdugang sa usa ka elemento gi-amortize .
Mao nga, nahibal-an namon kung giunsa pagbalhin ang datos gikan sa daan nga mga makina ngadto sa bag-o. Apan kini nga proseso nagkinahanglan og pipila ka mga adlaw - ug kini dili tingali nga niining mga adlawa ang atong mga tiggamit mobiya sa batasan sa pagsulat sa usag usa. Aron dili mawala ang mga mensahe niining panahona, mobalhin kami sa usa ka laraw sa trabaho nga naggamit sa daan ug bag-ong mga cluster.
Ang datos gisulat sa mga chat-member ug user-engine (ug dili sa text-engine, sama sa normal nga operasyon sumala sa daan nga laraw). user-engine proxy ang hangyo sa chat-engine - ug dinhi ang kinaiya nagdepende kung kini nga chat gihiusa na o wala. Kung ang chat wala pa mahiusa, ang chat-engine dili magsulat sa mensahe sa iyang kaugalingon, ug ang pagproseso niini mahitabo lamang sa text-engine. Kung ang chat nahiusa na sa chat-engine, ibalik niini ang chat_local_id sa user-engine ug ipadala ang mensahe sa tanang nakadawat. gi-proxy sa user-engine ang tanang data ngadto sa text-engine - aron kung adunay mahitabo, kanunay namong i-roll back, nga naa sa daan nga makina ang tanang data karon. Ang text-engine nagbalik sa user_local_id, nga gitipigan sa makina sa user ug gibalik sa backend.
Ingon usa ka sangputanan, ang proseso sa transisyon ingon niini: among gikonektar ang walay sulod nga user-engine ug chat-engine clusters. Ang chat-engine nagbasa sa tibuok nga chat-members binlog, unya ang proxying magsugod sumala sa laraw nga gihulagway sa ibabaw. Gibalhin namo ang daan nga datos ug nagkuha og duha ka na-synchronize nga mga cluster (daan ug bag-o). Ang nahabilin mao ang pagbalhin sa pagbasa gikan sa text-engine ngadto sa user-engine ug pag-disable sa proxying.
Π Π΅Π·ΡΠ»ΡΡΠ°ΡΡ
Salamat sa bag-ong pamaagi, ang tanan nga mga sukatan sa pasundayag sa mga makina gipauswag ug ang mga problema sa pagkamakanunayon sa datos nasulbad. Karon mahimo na namon nga ipatuman dayon ang mga bag-ong bahin sa mga mensahe (ug nagsugod na kami sa pagbuhat niini - gidugangan namon ang labing kadaghan nga mga partisipante sa chat, gipatuman ang pagpangita alang sa gipasa nga mga mensahe, gilunsad ang mga pinned nga mensahe ug gipataas ang limitasyon sa kinatibuk-ang gidaghanon sa mga mensahe matag tiggamit) .
Ang mga pagbag-o sa lohika sa tinuud dako kaayo. Ug gusto nako nga timan-an nga dili kini kanunay nagpasabut sa tibuuk nga mga tuig sa pag-uswag sa usa ka dako nga team ug daghang mga linya sa code. chat-engine ug user-engine uban sa tanan nga mga dugang nga mga istorya sama sa Huffman alang sa compression sa mensahe, Splay nga mga kahoy ug istruktura alang sa imported nga mga mensahe mao ang ubos pa kay sa 20 ka libo ka mga linya sa code. Ug gisulat sila sa 3 nga mga developer sa sulod lang sa 10 ka bulan (bisan pa, angay nga hinumdoman nga - mga kampeon sa kalibutan ).
Dugang pa, imbes nga doblehon ang gidaghanon sa mga server, gikunhoran namo ang ilang gidaghanon sa katunga - karon ang user-engine ug chat-engine nagpuyo sa 500 ka pisikal nga mga makina, samtang ang bag-ong laraw adunay dako nga headroom alang sa load. Nakadaginot kami ug daghang salapi sa kagamitan - mga $5 milyon + $750 ka libo kada tuig sa mga galastuhan sa operasyon.
Gipaningkamutan namon nga makit-an ang labing kaayo nga mga solusyon alang sa labing komplikado ug dagkong mga problema. Daghan kami niini - ug kana ang hinungdan ngano nga nangita kami mga talento nga developer sa departamento sa database. Kung nahigugma ka ug nahibal-an kung giunsa pagsulbad ang ingon nga mga problema, adunay maayo kaayo nga kahibalo sa mga algorithm ug istruktura sa datos, gidapit ka namon nga moapil sa team. Kontaka ang among alang sa mga detalye.
Bisan kung kini nga istorya dili bahin kanimo, palihug timan-i nga gipabilhan namon ang mga rekomendasyon. Sultihi ang usa ka higala bahin sa , ug kung malampuson niyang makompleto ang panahon sa pagsulay, makadawat ka og bonus nga 100 ka libo nga mga rubles.
Source: www.habr.com