Sharding

Ang awkward na sandali dito ay ang banayad na pagkakaiba sa pagitan ng horizontal partitioning at sharding. Maaari akong maputol, ngunit hindi ko masasabi sa iyo kung ano ito. May pakiramdam na ang sharding at horizontal partitioning ay tungkol sa parehong bagay.

Ang Sharding ay, sa pangkalahatan, kapag ang isang malaking talahanayan sa mga tuntunin ng mga database o isang pro-collection ng mga dokumento, mga bagay, kung wala kang database, ngunit isang tindahan ng dokumento, ay eksaktong pinutol ng mga bagay. Ibig sabihin, mula sa 2 bilyong bagay, pinipili ang mga piraso kahit anong laki. Ang mga bagay mismo sa loob ng bawat bagay ay hindi pinutol, hindi namin inilalagay ang mga ito sa magkakahiwalay na mga hanay, ibig sabihin, inilalagay namin ang mga ito sa mga batch sa iba't ibang lugar.

May mga banayad na pagkakaiba sa terminolohikal. Halimbawa, medyo nagsasalita, maaaring sabihin ng mga developer ng Postgres na ang pahalang na pagkahati ay kapag ang lahat ng mga talahanayan kung saan ang pangunahing talahanayan ay nahahati sa parehong schema, at kapag sa iba't ibang mga makina, ito ay sharding na.

Sa isang pangkalahatang kahulugan, nang hindi nakatali sa terminolohiya ng isang tiyak na database at isang tiyak na sistema ng pamamahala ng data, mayroong isang pakiramdam na ang sharding ay pagpipiraso lamang ng linya sa linya / dokumento sa pamamagitan ng dokumento, at iba pa - iyon lang.

Binibigyang-diin ko ang tipikal. Sa diwa na ginagawa namin ang lahat ng ito hindi lamang para putulin ang 2 bilyong dokumento sa 20 talahanayan, ang bawat isa ay magiging mas mapapamahalaan, ngunit upang maipamahagi ito sa maraming core, maraming disk o maraming iba't ibang pisikal o virtual na server .

1.2 Hatiin ang hindi mahahati

Nauunawaan na ginagawa namin ito upang ang bawat shard - bawat piraso ng data - ay ginagaya nang maraming beses. Pero sa totoo lang, hindi.

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

Sa katunayan, kung gagawin mo ang gayong paghiwa ng data, at mula sa isang higanteng talahanayan ng SQL sa MySQL sa iyong magiting na laptop, bubuo ka ng 16 na maliliit na talahanayan, nang hindi lalampas sa isang laptop, hindi isang solong schema, hindi isang solong database, atbp . at iba pa. - ayan, may sharding ka na.

Nagreresulta ito sa mga sumusunod:

• Tumataas ang bandwidth.
• Ang latency ay hindi nagbabago, ibig sabihin, bawat isa, wika nga, manggagawa o mamimili sa kasong ito, ay nakakakuha ng kanyang sarili. Ang iba't ibang mga kahilingan ay sineserbisyuhan nang halos parehong oras.
• O pareho, at isa pa, at mataas din ang kakayahang magamit (pagtitiklop).

Bakit bandwidth? Kung minsan, maaari tayong magkaroon ng ganoong dami ng data na hindi magkasya - hindi malinaw kung saan, ngunit hindi magkasya ang mga ito - sa 1 {kernel | disk | server | ...}. Kulang lang ang resources, yun lang. Upang gumana sa malaking dataset na ito, kailangan mong i-cut ito.

Bakit latency? Sa isang core, ang pag-scan sa isang talahanayan ng 2 bilyong row ay 20 beses na mas mabagal kaysa sa pag-scan ng 20 mga talahanayan sa 20 mga core, ginagawa ito nang magkatulad. Masyadong mabagal na pinoproseso ang data sa iisang mapagkukunan.

Bakit mataas ang availability? O pinutol namin ang data upang magawa ang pareho nang sabay, at sa parehong oras ilang kopya ng bawat shard - tinitiyak ng pagtitiklop ang mataas na kakayahang magamit.

1.3 Isang simpleng halimbawa "kung paano ito gawin sa pamamagitan ng kamay"

Maaaring putulin ang conditional sharding gamit ang test table test.documents para sa 32 na dokumento, at pagbuo ng 16 na test table mula sa talahanayang ito, humigit-kumulang 2 dokumento bawat pagsubok.docs00, 01, 02, ..., 15.

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

bakit naman? Dahil sa isang priori hindi namin alam kung paano ipinamamahagi ang id, kung mula 1 hanggang 32 kasama, pagkatapos ay magkakaroon ng eksaktong 2 mga dokumento bawat isa, kung hindi man ay hindi.

Ginagawa namin dito kung bakit. Pagkatapos naming gumawa ng 16 na talahanayan, maaari naming "grab" ang 16 sa kung ano ang kailangan namin. Anuman ang naabot natin, maaari nating iparallelize ang mga mapagkukunang ito. Halimbawa, kung walang sapat na espasyo sa disk, makatuwirang i-decompose ang mga talahanayang ito sa magkahiwalay na mga disk.

Ang lahat ng ito, sa kasamaang-palad, ay hindi libre. Pinaghihinalaan ko na sa kaso ng canonical SQL standard (matagal ko nang hindi binabasa ang SQL standard, marahil ito ay hindi na-update sa loob ng mahabang panahon), walang opisyal na standardized syntax para sa pagsasabi sa anumang SQL server : "Mahal na SQL server, gawin mo ako ng 32 shards at hatiin ang mga ito sa 4 na disk. Ngunit sa mga indibidwal na pagpapatupad, madalas mayroong isang partikular na syntax para sa paggawa ng parehong bagay. Ang PostgreSQL ay may mga mekanismo para sa paghati, MySQL ay may MariaDB, malamang na ginawa ng Oracle ang lahat ng ito matagal na ang nakalipas.

Gayunpaman, kung gagawin namin ito sa pamamagitan ng kamay, nang walang suporta sa database at sa loob ng balangkas ng pamantayan, pagkatapos ay magbabayad kami nang may kondisyon sa pagiging kumplikado ng pag-access ng data . Kung saan nagkaroon ng simpleng SELECT * FROM documents WHERE id=123, ngayon 16 x SELECT * FROM docsXX. At ito ay mabuti kung sinubukan naming makuha ang rekord sa pamamagitan ng susi. Mas kawili-wili kung sinusubukan nating makakuha ng maagang hanay ng mga talaan. Ngayon (kung tayo, binibigyang-diin ko, ay parang mga tanga, at mananatili sa loob ng balangkas ng pamantayan), ang mga resulta ng mga 16 SELECT * FROM ay kailangang pagsamahin sa aplikasyon.

Anong pagbabago sa pagganap ang maaari mong asahan?

• Intuitively - linear.
• Theoretically - sublinear, dahil Amdahl batas.
• Sa praktikal, marahil halos linearly, marahil hindi.

Sa katunayan, ang tamang sagot ay hindi alam. Sa isang matalinong aplikasyon ng sharding technique, makakamit mo ang isang makabuluhang super-linear na degradasyon sa pagganap ng iyong aplikasyon, at kahit na ang DBA ay tatakbo nang may napakainit na poker.

Tingnan natin kung paano ito makakamit. Malinaw na ang pagtatakda lamang ng setting sa PostgreSQL shards=16, at pagkatapos ay mag-isa itong aalis, ay hindi kawili-wili. Pag-isipan natin kung paano natin matitiyak na bumagal tayo mula sa sharding ng 16 na beses ng 32 - ito ay kawili-wili mula sa punto ng view kung paano hindi ito gagawin.

Ang aming mga pagtatangka na pabilisin o pabagalin ay palaging aabot sa mga klasiko - ang magandang lumang batas ng Amdahl, na nagsasabing walang perpektong parallelization ng anumang kahilingan, palaging may ilang pare-parehong bahagi.

1.4 Batas sa Amdahl

Laging may serialized part.

Palaging may bahagi ng pagpapatupad ng query na parallelize, at palaging may bahagi na hindi parallelized. Kahit na sa tingin mo ay isang perpektong parallel na query, hindi bababa sa koleksyon ng row ng resulta na iyong ipapadala sa kliyente mula sa mga row na natanggap mula sa bawat shard ay palaging nandoon, at ito ay palaging sequential.

Palaging may ilang pare-parehong bahagi. Maaari itong maging maliit, ganap na hindi nakikita laban sa pangkalahatang background, maaari itong maging napakalaki at, nang naaayon, malakas na nakakaapekto sa parallelization, ngunit ito ay palaging umiiral.

Bilang karagdagan, ang impluwensya nito ay nagbabago at maaaring lumago nang malaki, halimbawa, kung pinutol natin ang ating talahanayan - itaas natin ang mga pusta - mula sa 64 na talaan sa 16 na talahanayan ng 4 na talaan, magbabago ang bahaging ito. Siyempre, ayon sa napakalaking dami ng data, nagtatrabaho kami sa isang mobile phone at isang 2 MHz 86 processor, at wala kaming sapat na mga file na maaaring panatilihing bukas sa parehong oras. Tila, na may ganitong mga input, binubuksan namin ang isang file sa isang pagkakataon.

• Ito ay Kabuuan = Serial + Parallel . Kung saan, halimbawa, parallel ang lahat ng gawain sa loob ng DB, at ipinapadala ng serial ang resulta sa kliyente.
• Naging Total2 = Serial + Parallel/N + Xserial . Halimbawa, kapag ang kabuuang ORDER BY, Xserial>0.

Sa simpleng halimbawang ito, sinusubukan kong ipakita na lumilitaw ang ilang Xserial. Bilang karagdagan sa katotohanan na palaging mayroong isang serialized na bahagi, at ang katotohanan na sinusubukan naming gumana nang magkatulad ang data, mayroong isang karagdagang bahagi upang maibigay ang data slicing na ito. Sa halos pagsasalita, maaaring kailanganin natin:

• hanapin ang 16 na talahanayan na ito sa panloob na diksyunaryo ng database;
• buksan ang mga file;
• maglaan ng memorya;
• unallocate memory;
• pagsamahin ang mga resulta;
• i-synchronize sa pagitan ng mga core.

Lumilitaw pa rin ang ilang mga out-of-sync effect. Maaari silang maging hindi gaanong mahalaga at sumasakop sa isang bilyon ng kabuuang oras, ngunit sila ay palaging hindi zero at palaging nandiyan. Sa tulong nila, maaari tayong mawalan ng performance pagkatapos ng sharding.

Ito ay isang karaniwang larawan tungkol sa batas ni Amdahl. Ang mahalagang bagay dito ay ang mga linya, na kung saan ay dapat na tuwid at lumalago nang linearly, ay tumatakbo sa isang asymptote. Ngunit dahil ang graph mula sa Internet ay hindi nababasa, gumawa ako, sa aking opinyon, ng mas maraming visual na talahanayan na may mga numero.

Sabihin nating mayroon kaming ilang serialized na bahagi ng pagproseso ng kahilingan na tumatagal lamang ng 5%: serial = 0.05 = 1 / 20 .

Sa madaling salita, tila sa isang serialized na bahagi na tumatagal lamang ng 1/20 ng pagpoproseso ng kahilingan, kung ihahalintulad natin ang pagpoproseso ng kahilingan para sa 20 core, ito ay magiging humigit-kumulang 20, sa pinakamasamang kaso 18, mas mabilis.

Sa katunayan, ang matematika ay isang walang pusong bagay :

wall = 0.05 + 0.95/num_cores, speedup = 1 / (0.05 + 0.95/num_cores)

Lumalabas na kung maingat mong kalkulahin, na may serialized na bahagi na 5%, ang speedup ay magiging 10 beses (10.3), na 51% kumpara sa theoretical ideal.

Ang pagkakaroon ng paggamit ng 20 core (20 disk, kung gusto mo) para sa gawain na ginamit ng isang tao, hinding-hindi tayo magkakaroon ng teoretikal na pagbilis ng higit sa 20 beses, ngunit sa pagsasanay - mas kaunti. Bukod dito, sa isang pagtaas sa bilang ng mga parallel, ang inefficiency ay tumataas nang malaki.

Kapag 1% na lang ng serialized na trabaho ang natitira, at 99% ay parallelize, medyo bubuti ang mga value ng speedup:

Para sa isang perpektong thermonuclear na query, na natural na tumatagal ng mga oras upang makumpleto, at ang paghahanda at ang pagpupulong ng resulta ay tumatagal ng napakakaunting oras (serial = 0.001), makikita na natin ang mahusay na kahusayan:

Pakitandaan na hindi namin makikita ang 100% . Sa partikular na magagandang kaso, makikita mo, halimbawa, 99.999%, ngunit hindi eksaktong 100%.