Sharding: reverse side

2.1 Paano i-shard at pabagalin ang N beses?

Maaari mong i-shard at pabagalin nang eksakto N beses tulad nito:

• Magpadala ng docs00...docs15 na mga kahilingan nang sunud-sunod , hindi magkatulad.
• Sa mga simpleng query, gumawa ng pagpili hindi sa pamamagitan ng key , WHERE something=234.

Sa kasong ito, ang serialized na bahagi (serial) ay tumatagal ng hindi 1% at hindi 5%, ngunit humigit-kumulang 20% ​​sa mga modernong database. Maaari ka ring makakuha ng 50% ng serialized na bahagi kung maa-access mo ang database gamit ang isang wildly efficient binary protocol o i-link ito bilang isang dynamic na library sa isang Python script.

Ang natitirang oras ng pagpoproseso ng isang simpleng kahilingan ay sasakupin ng mga di-parallelizable na operasyon ng pag-parse ng kahilingan, paghahanda ng plano, atbp. Ibig sabihin, bumabagal ang hindi pagbabasa ng record.

Kung hahatiin natin ang data sa 16 na talahanayan at patakbuhin nang sunud-sunod, gaya ng nakaugalian sa PHP programming language, halimbawa, (hindi ito masyadong mahusay sa paglulunsad ng mga asynchronous na proseso), pagkatapos ay makakakuha tayo ng 16 na beses na pagbagal. At, marahil, higit pa, dahil idadagdag din ang mga round-trip sa network.

Biglang, ang pagpili ng programming language ay mahalaga kapag sharding.

Tandaan ang tungkol sa pagpili ng programming language, dahil kung magpadala ka ng mga query sa database (o search server) nang sunud-sunod, kung gayon saan nanggagaling ang acceleration? Sa halip, magkakaroon ng pagbagal.

2.2 Tungkol sa semi-awtomatikong

Sa mga lugar, ang pagiging sopistikado ng teknolohiya ng impormasyon ay nagbibigay inspirasyon sa chthonic horror. Halimbawa, ang MySQL out of the box ay walang pagpapatupad ng sharding sa ilang mga bersyon para sigurado, gayunpaman, ang mga sukat ng mga database na ginamit sa labanan ay lumalaki sa mga malaswang halaga.

Ang pagdurusa ng sangkatauhan sa harap ng mga indibidwal na DBA ay pinahirapan sa loob ng maraming taon at nagsusulat ng ilang masamang solusyon sa sharding batay sa wala. Pagkatapos nito, isa pa o mas kaunting disenteng sharding solution ang isinulat na tinatawag na ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...). Ito ay isang kilalang halimbawa ng napaka-blotch na ito.

Ang ProxySQL sa kabuuan ay, siyempre, isang ganap na solusyon sa enterprise-class para sa open source, para sa pagruruta at higit pa. Ngunit ang isa sa mga gawain na dapat lutasin ay sharding para sa isang database, na kung saan sa kanyang sarili ay hindi maaaring shard sa isang tao na paraan. Nakikita mo, walang switch na "shards = 16", kailangan mong muling isulat ang bawat kahilingan sa application, at marami sa mga ito sa mga lugar, o maglagay ng intermediate layer sa pagitan ng application at ng database na mukhang: "Hmm ... PUMILI * MULA sa mga dokumento? Oo, dapat itong hatiin sa 16 maliit na SELECT * FROM server1.document1, SELECT * FROM server2.document2 - sa server na ito na may ganoong login / password, sa isang ito sa isa pa. Kung hindi sumagot ang isa, kung gayon ... ", atbp. Eksaktong ito ay maaaring gawin sa pamamagitan ng mga intermediate blotches. Ang mga ito ay bahagyang mas mababa kaysa para sa lahat ng mga database. Para sa PostgreSQL, sa pagkakaintindi ko,

Ang pag-configure sa bawat partikular na patch ay isang hiwalay na higanteng paksa na hindi akma sa isang ulat, kaya tatalakayin lamang natin ang mga pangunahing konsepto. Mas mahusay na pag-usapan natin ang tungkol sa teorya ng buzz.

2.3 Ganap na perpektong automation?

Ang buong teorya ng pagiging mataas sa kaso ng sharding sa titik na ito F() , ang pangunahing prinsipyo ay palaging pareho halos: shard_id = F(object).

Sharding - tungkol saan ang lahat? Mayroon kaming 2 bilyong talaan (o 64). Gusto naming hatiin ang mga ito sa ilang piraso. Ang isang hindi inaasahang tanong ay lumitaw - paano? Sa anong prinsipyo ko dapat ikalat ang aking 2 bilyong talaan (o 64) sa 16 na server na magagamit ko?

Ang nakatagong mathematician sa atin ay dapat magmungkahi na sa dulo ay palaging may ilang magic function na, para sa bawat dokumento (object, linya, atbp.), ay magpapasiya kung aling piraso ito ilalagay.

Sa mas malalim na pag-aaral sa matematika, palaging nakadepende ang function na ito hindi lamang sa mismong object (ang row mismo), kundi pati na rin sa mga external na setting gaya ng kabuuang bilang ng mga shards. Ang isang function na para sa bawat bagay ay dapat sabihin kung saan ito ilalagay, ay hindi maaaring magbalik ng isang halaga nang higit pa sa mga server sa system. At ang mga pag-andar ay bahagyang naiiba:

shard_func = F1(object); 
shard_id = F2(shard_func, ...); 
shard_id = F2(F1(object), current_num_shards, ...). 

Ngunit higit pa ay hindi namin huhukay ang mga wild na ito ng mga indibidwal na pag-andar, pag-uusapan lang namin kung ano ang mga magic function na F ().

2.4 Ano ang F()?

Maaari silang makabuo ng maraming iba't ibang at maraming iba't ibang mekanismo ng pagpapatupad. Halimbawang buod:

• F = rand() % nums_shards
• F = somehash(object.id) % num_shards
• F = object.date % num_shards
• F = object.user_id % num_shards
• ...
• F = shard_table [ somehash() |… object.date |… ]

Isang kawili-wiling katotohanan - maaari mong natural na ikalat ang lahat ng data nang sapalaran - itinapon namin ang susunod na tala sa isang arbitrary na server, sa isang arbitrary na core, sa isang arbitrary na talahanayan. Walang gaanong kaligayahan dito, ngunit gagana ito.

Mayroong bahagyang mas matalinong mga pamamaraan sa shard sa pamamagitan ng isang reproducible o kahit pare-parehong hash function, o shard sa pamamagitan ng ilang attribute. Dumaan tayo sa bawat pamamaraan.

F = rand()

Ang pagkalat sa paligid ay hindi isang napakatamang paraan. Isang problema: ikinalat namin ang aming 2 bilyong record sa isang libong server nang random, at hindi namin alam kung nasaan ang record. Kailangan naming i-pull out ang user_1, ngunit hindi namin alam kung nasaan ito. Pumunta kami sa isang libong server at pinag-uuri-uriin ang lahat - kahit papaano ay hindi ito mahusay.

F = somehash()

Ikalat natin ang mga user sa isang pang-adultong paraan: kalkulahin ang reproducible hash function mula sa user_id, kunin ang natitira sa dibisyon ayon sa bilang ng mga server, at agad na makipag-ugnayan sa gustong server.

Bakit natin ito ginagawa? At pagkatapos, na mayroon kaming isang highload at wala nang iba pang bagay sa isang server. Kung ito ay magkasya, ang buhay ay magiging napakasimple.

Mahusay, ang sitwasyon ay bumuti na, upang makakuha ng isang rekord, pumunta kami sa isang kilalang server nang maaga. Ngunit kung mayroon tayong hanay ng mga susi, kung gayon sa buong hanay na ito kailangan nating dumaan sa lahat ng mga halaga ng mga susi at, sa limitasyon, pumunta sa alinman sa pinakamaraming shards na mayroon tayong mga susi sa hanay, o kahit sa bawat server. Ang sitwasyon ay bumuti, siyempre, ngunit hindi para sa lahat ng mga kahilingan. Naapektuhan ang ilang query.

Natural sharding (F = object.date % num_shards)

Minsan, iyon ay, madalas, 95% ng trapiko at 95% ng load ay mga kahilingan na may ilang uri ng natural na sharding. Halimbawa, 95% ng mga query na may kondisyong social-analytic ay nakakaapekto sa data lamang sa huling 1 araw, 3 araw, 7 araw, at ang natitirang 5% ay tumutukoy sa mga nakaraang taon. Ngunit 95% ng mga kahilingan ay natural na pinaghiwa-hiwalay ayon sa petsa, ang interes ng mga gumagamit ng system ay nakatuon sa mga huling araw.

Sa kasong ito, maaari mong hatiin ang data ayon sa petsa, halimbawa, sa isang araw, at sundin ang tugon sa kahilingan para sa isang ulat para sa ilang araw o isang bagay mula sa araw na ito hanggang sa shard na ito at pumunta.

Bumubuti ang buhay - hindi lamang natin alam ang lokasyon ng isang partikular na bagay, ngunit alam din natin ang tungkol sa saklaw. Kung hihilingin sa amin hindi para sa isang hanay ng mga petsa, ngunit para sa isang hanay ng iba pang mga haligi, kung gayon, siyempre, kailangan nating dumaan sa lahat ng mga shards. Ngunit ayon sa mga patakaran ng laro, mayroon lamang kaming 5% ng mga naturang kahilingan.

Tila nakaisip tayo ng perpektong solusyon sa lahat, ngunit may dalawang problema:

• Ang solusyon na ito ay iniakma para sa isang partikular na kaso, kapag ang 95% ng mga kahilingan ay nagsasangkot lamang sa nakaraang linggo.
• Dahil ang 95% ng mga kahilingan ay umabot sa nakaraang linggo, lahat sila ay mahuhulog sa isang shard na nagsisilbi nitong nakaraang linggo. Matutunaw ang shard na ito, habang ang lahat ng iba ay magiging idle sa panahong ito. Kasabay nito, hindi mo maaaring itapon ang mga ito; dapat ding naka-imbak ang data ng archival.

Hindi upang sabihin na ito ay isang masamang sharding scheme - pinutol namin ang mainit na data, gayunpaman, may kailangang gawin sa pinakamainit na shard.

Ang problema ay nalutas sa pamamagitan ng mga kalokohan, pagtalon at pagtapal, iyon ay, isang pagtaas sa bilang ng mga replika para sa nasusunog na kasalukuyang araw, pagkatapos ay isang unti-unting pagbaba sa bilang ng mga replika kapag ang araw na ito ay naging nakaraan at napupunta sa archive. Walang perpektong solusyon na tinatawag na "kailangan mo lang ikalat ang data sa cluster na may magic hash function sa maling paraan."

2.5 Presyong babayaran

Pormal, alam na natin ngayon alam na natin ang "lahat". Totoo, hindi natin alam ang isang higanteng sakit ng ulo at dalawang mas maliit na sakit ng ulo.

1. Simpleng sakit: masama ang pahid

Ito ay isang halimbawa mula sa isang aklat-aralin, na halos hindi nangyayari sa labanan, ngunit biglaan.

• Bilang isang halimbawa na may petsa, walang petsa lamang!
• Hindi sinasadyang hindi pantay (nakikita) na pamamahagi.

Pinili nila ang mekanismo ng sharding, at/o nagbago ang data, at, siyempre, hindi ipinarating ng PM ang mga kinakailangan (wala kaming mga error sa code, palaging hindi iniuulat ng PM ang mga kinakailangan), at ang pamamahagi naging napakalaking hindi pantay. Ibig sabihin, napalampas nila ang criterion.

Upang mahuli, kailangan mong tingnan ang laki ng mga shards. Tiyak na makikita natin ang problema sa sandaling ang isa sa ating mga shards ay nag-overheat o nagiging 100 beses na mas malaki kaysa sa iba. Maaayos mo ito sa pamamagitan lamang ng pagpapalit ng key o sa sharding function.

Ito ay isang simpleng problema, sa totoo lang, hindi ko iniisip na kahit isang tao sa isang daan ang tatakbo sa buhay na ito, ngunit biglang makakatulong ito kahit isang tao.

2. "Invincible" pain: pagsasama-sama, pagsali

Paano gumawa ng mga seleksyon na sumali sa isang bilyong talaan mula sa isang talahanayan para sa isang bilyong talaan mula sa isa pang talahanayan?

• Paano "mabilis" kalkulahin... SAAN randcol PAGITAN aaa AT bbb?
• Paano "matalinong" gawin... users_32shards SUMALI sa mga post_1024 shards?

Maikling sagot: hindi, magdusa!

Kung namahagi ka ng isang bilyong tala sa isang libong mga server sa unang talahanayan upang gumana ang mga ito nang mas mabilis, at ginawa ang parehong sa pangalawang talahanayan, natural na isang libo hanggang isang libong mga server ang dapat makipag-usap sa bawat isa nang magkapares. Ang isang milyong koneksyon ay hindi gagana nang maayos. Kung gagawa kami ng mga kahilingan sa database (paghahanap, imbakan, tindahan ng dokumento o distributed file system) na hindi angkop sa sharding, ang mga kahilingang ito ay bumagal nang husto.

Ang isang mahalagang punto ay ang ilang mga kahilingan ay palaging hindi matagumpay na smeared at babagal . Mahalagang subukang bawasan ang kanilang porsyento. Bilang kinahinatnan, hindi na kailangang gumawa ng napakalaking pagsasama na may isang bilyon sa pamamagitan ng isang bilyong talaan. Kung posible na kopyahin ang isang maliit na talahanayan, na nauugnay sa kung saan ka sumali sa isang higanteng nakabahaging talahanayan, sa lahat ng mga node, dapat mong gawin ito. Kung ang mga pagsali ay aktwal na lokal sa ilang paraan, halimbawa, posibleng ilagay ang user at ang kanyang mga post nang magkatabi, paghiwa-hiwalayin ang mga ito sa parehong paraan, at gawin ang lahat ng pagsali sa loob ng parehong makina - kailangan mong gawin iyon. .

Ito ay isang hiwalay na kurso ng mga lektura sa loob ng tatlong araw, kaya lumipat tayo sa huling mala-impiyernong sakit at iba't ibang mga algorithm para sa pagharap dito.

2.6. Kumplikado/Mahabang Sakit: Resharding

Humanda ka: kung na-shard mo ang iyong data sa unang pagkakataon sa iyong buhay, sa average, hihimayin mo pa ito nang limang beses.

Kahit gaano karaming mga kumpol ang iyong na-configure, kailangan mo pa ring i-reshard.

Kung ikaw ay napakatalino at masuwerte, pagkatapos ay mag-overshard kahit isang beses. Ngunit kapag sigurado ka na, dahil sa sandaling naisip mo na sapat na ang 10 unit para sa user, may isang tao sa sandaling iyon ay nagsusulat ng kahilingan para sa 30, at nagpaplanong magkaroon ng kahilingan para sa 100 unit ng hindi kilalang mga mapagkukunan. Ang mga shards ay hindi kailanman sapat. Sa unang scheme ng sharding, sa anumang kaso, makaligtaan ka - palagi mong kailangang dagdagan ang bilang ng mga server na idaragdag, o gumawa ng iba pa - sa pangkalahatan, kahit papaano ay i-repackage ang data.

Mabuti kung mayroon tayong magagandang kapangyarihan ng dalawa: mayroong 16 na server shards, ngayon ay 32. Mas masaya kung ito ay 17, ito ay 23 - dalawang vasimally prime number. Paano ito ginagawa ng mga database, marahil mayroon silang ilang uri ng magic sa loob?

Ang tamang sagot ay: hindi, walang magic sa loob, mayroon silang impiyerno sa loob.

Susunod, isasaalang-alang natin kung ano ang maaaring gawin "sa pamamagitan ng kamay", marahil ay mauunawaan natin "bilang isang awtomatikong makina".

Sa noo #1. Ilipat ang Lahat

Para sa lahat ng mga bagay, isinasaalang-alang namin ang NewF(object), shift sa isang bagong shard.

Ang pagkakataon ng NewF()=OldF() na pagtutugma ay mababa.

Sakupin natin ang halos lahat.

Oh.

Sana walang ganoong impiyerno na ilipat ang lahat ng 2 bilyong tala mula sa mga lumang shards patungo sa mga bago. Ang walang muwang na diskarte ay nauunawaan: mayroong 17 na makina, 6 na makina ang idinagdag sa kumpol, 2 bilyong mga talaan ang naayos, sila ay inilipat mula sa 17 na makina sa 23 na makina. Minsan sa bawat 10 taon, maaari mo ring gawin ito. Ngunit sa pangkalahatan ito ay isang masamang hakbang.

Sa noo #2. Ilipat ang kalahati

Ang susunod na walang muwang na pagpapabuti - abandunahin natin ang gayong hangal na pamamaraan - ay magbabawal sa 17 na mga kotse na mag-reshard sa 23, at palagi nating reshard ang 16 na mga kotse sa 32 na mga kotse! Pagkatapos, ayon sa teorya, kakailanganin nating ilipat ang eksaktong kalahati ng data, at sa pagsasagawa, magagawa rin natin ito.

Para sa lahat ng mga bagay, isinasaalang-alang namin ang NewF(object), shift sa isang bagong shard.

Ito ay mahigpit na 2^N, ngayon ito ay mahigpit na 2^(N+1) shards.

Ang posibilidad ng pagtutugma ng NewF()=OldF() ay 0.5.

Ilipat natin ang tungkol sa 50% ng data.

Pinakamainam, ngunit gumagana lamang para sa mga kapangyarihan ng dalawa.

Sa prinsipyo, ang lahat ay maayos, maliban sa pagbubuklod sa kapangyarihan ng dalawa sa mga tuntunin ng bilang ng mga kotse. Ang walang muwang na diskarte na ito, kakaiba, ay maaaring gumana.

Pakitandaan na ang karagdagang paghahati ng cluster sa pamamagitan ng mga kapangyarihan ng dalawa sa kasong ito ay pinakamainam din. Sa anumang kaso, ang pagdaragdag ng 16 na makina sa isang kumpol ng 16, obligado kaming ilipat ang kalahati ng data - eksaktong kalahati at ilipat.

Okay, ngunit ang sangkatauhan ba ay talagang hindi nag-imbento ng anumang bagay - ang tanong ay nagmumula sa isang matanong na isip.

Mas masaya #3. Pare-parehong pag-hash

Siyempre, kailangan dito ang isang larawan na may bilog tungkol sa pare-parehong pag-hash.

Kung mag-google ka ng "pare-parehong pag-hash", tiyak na lalabas ang isang bilog, ang lahat ng mga resulta ay puno ng mga lupon.

Ideya: gumuhit tayo ng mga shard identifier (hashes) sa isang bilog, at markahan ang mga na-hash na identifier ng server sa itaas. Kapag kailangan mong magdagdag ng isang server, naglalagay kami ng bagong punto sa bilog, at kung ano ang naging malapit dito (at kung ano lamang ang naging malapit dito), lumipat kami.

Kapag nagdaragdag ng isang shard: hindi namin tinitingnan ang lahat, ngunit 2 "kapitbahay" lamang, nagbabago kami sa average na 1/n.

Kapag nagtatanggal ng shard: tinitingnan lang namin ang shard na tinatanggal, inililipat lang namin ito. Uri ng pinakamainam.

Napaka-epektibo sa mga tuntunin ng pagliit ng trapiko kapag nagdaragdag ng isang shard, at talagang kasuklam-suklam sa mga tuntunin ng normal na pagbabalanse ng data. Dahil kapag na-hash namin ang lahat ng mga bagay na ito na ipinamahagi namin sa isang malaking bilang ng mga makina, ginagawa namin ito nang medyo hindi pantay: ang mga punto sa paligid ng bilog ay hindi pantay na espasyo, at ang pagkarga ng bawat partikular na node ay maaaring ibang-iba mula sa iba.

Ang problemang ito ay nalutas sa pamamagitan ng huling linya ng virtual node. Ang bawat node, ang bawat server sa bilog ay ipinahiwatig ng higit sa isang tuldok. Sa pamamagitan ng pagdaragdag ng server, shard, atbp., nagdaragdag kami ng ilang puntos. Sa bawat oras na nag-aalis kami ng isang bagay, naaayon kaming nag-aalis ng ilang mga punto at naglilipat ng maliit na bahagi ng data.

Pinag-uusapan ko ang puwang na ito na may mga bilog, dahil, halimbawa, ang gayong pamamaraan ay nasa loob ng Cassandra. Iyon ay, kapag nagsimula siyang humabol ng mga tala sa pagitan ng mga node, alamin na ang bilog ay nakatingin sa iyo at malamang na hindi aprubahan.

Gayunpaman, kumpara sa mga unang pamamaraan, bumuti ang buhay - kapag nagdaragdag / nag-aalis ng isang shard, tinitingnan na namin ang hindi lahat ng mga talaan, ngunit isang bahagi lamang, at inilipat lamang ang isang bahagi.

Pansin, ang tanong ay: mapapabuti pa ba ito? At pagbutihin din ang pagkakapareho ng paglo-load ng mga shards? Sabi nila pwede daw!

Mas masaya #4. Rendezvous/HRW

Ang susunod na simpleng ideya (ang materyal ay pang-edukasyon, kaya walang kumplikado): shard_id = arg max hash(object_id, shard_id).

Kung bakit ito tinatawag na Rendezvous hashing ay hindi ko alam, ngunit alam ko kung bakit ito tinatawag na Highest Random Weight. Napakadaling mailarawan ito tulad nito:

Mayroon kaming, halimbawa, 16 shards. Para sa bawat bagay (string) na kailangang ilagay sa isang lugar, kinakalkula namin ang 16 na hash depende sa bagay mula sa shard number. Kung sino ang may pinakamataas na halaga ng hash ang mananalo.

Ito ang tinatawag na HRW-hashing, aka Rendezvous hashing. Pipi bilang isang stick, ang pamamaraan para sa pagkalkula ng bilang ng isang shard, una, ay mas madali sa mata kaysa sa mga bilog at nagbibigay ng pare-parehong pagkarga, sa kabilang banda.

Ang negatibo lamang ay ang pagdaragdag ng isang bagong shard ay lumala para sa amin. May panganib na kapag nagdaragdag ng bagong shard, mayroon pa rin kaming ilang mga hash na magbabago at maaaring kailanganin na suriin ang lahat. Hindi gaanong nagbago ang teknolohiya sa pagtanggal ng shard.

Ang isa pang problema ay na ito ay mabigat sa computation na may malaking bilang ng mga shards.

Mas masaya #5. Higit pang mga diskarte

Kapansin-pansin, hindi tumitigil ang pananaliksik at naglalathala ang Google ng ilang bagong teknolohiya sa espasyo bawat taon:

• Jump Hash - Google '2014.
• Multi Probe—Google '2015.
• Maglev-Google '2016.

Kung interesado ka sa paksa, maaari kang magbasa ng maraming disertasyon. Ipinakita ko ang data na ito upang gawing malinaw na ang problema ay hindi pa nalutas, walang super-solusyon na maaaring ipatupad sa lahat ng mga database. Hanggang ngayon, ipinagtatanggol ng mga tao ang mga disertasyon.

mga konklusyon

Mayroong isang mahalagang pangunahing pamamaraan na tinatawag na sharding na pinangalanan kay Gallius Julius Caesar: "Divide and rule, rule and divide!". Kung ang data ay hindi magkasya sa isang server, ito ay kinakailangan upang hatiin ito sa 20 server.

Ang pagkakaroon ng natutunan ang lahat ng ito, ang isa ay dapat makakuha ng impresyon na ito ay mas mahusay na hindi shard. Kung magpasya ka na ito ay mas mahusay na hindi shard, ito ang tamang pakiramdam. Kung maaari kang magdagdag ng memorya sa server para sa $100 at hindi shard kahit ano, dapat mong gawin ito. Kapag sharding, lalabas ang isang kumplikadong distributed system na may paglilipat ng data pabalik-balik, na nag-stack ng data sa walang nakakaalam kung saan. Kung maiiwasan, dapat iwasan.

Mas mainam na huwag gawin ito sa pamamagitan ng kamay, mas mabuti na ang "base" (paghahanap, DFS, ...) ay maaaring mag-shard mismo. Sa anumang kaso, maaga o huli, darating ang highload at kahit papaano ay kailangang hatiin ang data. Ito ay hindi isang katotohanan na kahit na ang base ay maaaring gawin ito mismo, hindi ka magkakaroon ng anumang mga problema. Tandaan ang tungkol sa algorithmic fundamentalism - kailangan mong maunawaan kung paano gumagana ang lahat sa loob.

Kapag nagse-set up ng sharding sa unang pagkakataon, piliin nang mabuti ang F(), isipin ang mga kahilingan, network, atbp. Ngunit maghanda, malamang na kailangan mong pumili ng 2 beses at hindi bababa sa isang beses kailangan mong gawing muli ang lahat.