Sharding: boshqa tomonlari

2.1 Qanday qilib shard qilib, N marta sekinlashtirish mumkin?

Mana shunday shard qilib, N marta sekinlashtirish mumkin:

• docs00...docs15 so'rovlarini ketma-ket yuborish, parallel emas.
• Oddiy so'rovlarda kalit bo'yicha emas, WHERE something=234 tanlov qiladi.

Bunday holatda, serializatsiya qismi zamonaviy ma'lumotlar bazalarida 1% yoki 5% emas, balki taxminan 20% ni tashkil qiladi. Agar ma'lumotlar bazasiga juda samarali binar protokol orqali murojaat qilsangiz yoki Python skriptida dinamik kutubxona sifatida bog'lasangiz, serializatsiya qismini 50% ga yetkazish mumkin.

Barcha oddiy so'rovlarni qayta ishlash vaqti so'rovni tahlil qilish, reja tayyorlash va h.k. kabi parallel bo'lmagan operatsiyalarni egallaydi. Ya'ni, yozuvni o'qish sekinlashtirilmayapti.

Agar biz ma'lumotlarni 16 ta jadvalga taqsimlasak va ketma-ket ishga tushirsak, masalan, PHP tilida qabul qilinganidek (u asenkron jarayonlarni ishga tushirishda unchalik yaxshi emas), biz 16 marta sekinlashtirish olamiz. Ehtimol, hatto ko'proq, chunki boshqa network round-trips ham qo'shiladi.

Kutilmaganda, sharding jarayonida dasturlash tilini tanlash muhimdir.

Dasturlash tilini tanlashni unutmang, chunki agar ma'lumotlar bazasiga (yoki qidiruv serveriga) so'rovlarni ketma-ket yuborsangiz, qanday qilib tezlikni oshirish mumkin? Aksincha, sekinlashish kuzatilishi mumkin.

2.2 Yarim avtomat haqida

Ma'lum texnologiyalarning ba'zan dahshatli ko'rinishlari mavjud. Masalan, MySQL asosiy nusxasida qandaydir versiyalargacha shardingni amalga oshirishga ega emas edi, ammo jangda ekspluatatsiya qilinadigan bazalarning hajmi juda katta darajaga yetadi.

Judolikda azob chekish, alohida olingan DBAlarning kishilari yillar davomida sharding uchun bir necha yomon yechimlarni ishlab chiqaradi, qandaydir noma'lum narsaga asoslanishgan. Shundan keyin bir muncha yaxshi bir yechim uchun sharding deb nomlangan ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...) ishlab chiqiladi. Bu mashhur misollardan biridir.

ProxySQL umumiy holda, open source uchun enterprise-klass to'liq yechimi hisoblanadi, rouyting va boshqa narsalar uchun. Lekin hal qilinadigan vazifalardan biri — shard qilish, ma'lumotlar bazasi uchun, o'zi o'zini o'zini o'zi o'zini o'zi tanqid qiladigan tarzda shard qila olmaydi. Tushunyapsizmi, «shards=16» o'chirilgan degan tugma yo'q, har bir so'rovni ilovada qayta yozish kerak, joylarda ularning ko'p, yoki ma'lumotlar bazasi va dasturlar orasiga biror o'rta qavat qo'ying, u bunday qilar: «Hmm... SELECT*FROM hujjatlar? Uni 16 ta kichik SELECT*FROM server1.document1, SELECT*FROM server2.document2 - bu serverga bunday login/parol bilan, bunga boshqa bilan. Agar bir javob bermasa, unda...» va hokazo. Aynan shu bilan oraliq qoplamalar shug'ullanadi. Ular deyarli barcha ma'lumotlar bazalari uchun mavjud. PostgreSQL uchun, menimcha, bir vaqtning o'zida qandaydir ichki yechimlar mavjud (PostgresForeign Data Wrappers, menimcha, bu talaffuz PostgreSQLning o'zidagi), tashqi qoplamalar mavjud.

Har bir konkret qoplamani sozlash - bu alohida ulkan bir mavzudir, bu bir taqdimotga sig'maydi, shuning uchun biz faqat asosiy tushunchalarni muhokama qilamiz. Qani keling, biroz kayfiyot nazariyasini muhokama qilamiz.

2.3 Mutlaqo ideal avtomatika?

Kayfiyot nazariyasida sharding haqida gap ketganda, bu F() harfida, asosiy prinsipi har doim bir xil oddiy tarzda: shard_id = F(object).

Sharding nima haqida? Bizda 2 milliard yozuvlar (yoki 64). Biz ularni bir necha bo'laklarga bo'lishni xohlaymiz. Kutilmagan savol tug'iladi - qanday qilib? Men o'zimning 2 milliard yozuvlarimni (yoki 64) qanday qilib mavjud 16 serverlarga taqsimlashim kerak?

Ichimizdagi latent matematik bizga shuni aytishi kerakki, oxir oqibat har doim bir sehrli funksiya mavjud, u har bir hujjat (ob'ekt, qator va hokazolar) uchun qanday qisqa olishni aniqlaydi.

Agar matematikani yanada chuqurroq kirishsa, bu funksiya har doim nafaqat o'zi ob'ektdan (o'zi qatoridan), balki umumiy shardinglar soni kabi tashqi sozlamalardan ham bog'liqdir. Har bir ob'ekt uchun uni qayerga qo'yishni aytadigan funksiya, tizimda mavjud bo'lgan serverlardan ko'ra katta qiymatni qaytara olmaydi. Va funktsiyalar bir oz turlicha:

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

Afsuski, biz alohida funktsiyalarni o'rganishga chuqurroq kirmaymiz, faqat qanday sehrli funktsiyalar F() mavjudligini gaplashamiz.

2.4 Qanday F() lar mavjud?

Ular turli xil va amalga oshirish mexanizmlari ko'p bo'lishi mumkin. Qisqacha ro'yxat:

• 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 |… ]

Qiziqarli fakt — barcha ma'lumotlarni tasodifiy taqsimlash mumkin — navbatdagi yozuvni tasodifiy serverga, tasodifiy yadroga, tasodifiy jadvarga tashlaymiz. Bu orqali biron-bir maxsus baxtga erishilmaydi, lekin ish beradi.

Reproducible yoki hatto konsistent xesh-funksiyaga shard qilish, yoki qandaydir atribut bo'yicha shard qilish uchun biroz intellektual metodlar mavjud. Har bir usulni ko'rib chiqamiz.

F = rand()

Tasodifiy tashlash - juda to'g'ri usul emas. Bir muammo: biz o'z 2 milliard yozuvlarimizni tasodifiy 1000 serverga tasodifiy tarqatdik, va yozuv qayerda ekanligini bilmaymiz. Biz user_1ni chiqarishimiz kerak, lekin u qayerda ekanligini bilmaymiz. 1000 serverga o'tib, hammasini ko'rib chiqamiz — bu qandaydir samarasiz.

F = somehash()

Keling, foydalanuvchilarni kattalar kabi tarqataylik: user_id dan reproducible xesh-funksiyani hisoblang, serverlar soniga bo'lingan qoldiqni oling va darhol kerakli serverga murojaat qiling.

Nega buni qilishimiz kerak? Chunki bizda highload bor va bitta serverga ko'proq hech narsa sig'maydi. Agar sig’sa edi, hayot juda oddiy bo'lardi.

Ajoyib, vaziyat yaxshilandi, bitta yozuvni olish uchun, biz oldindan ma'lum serverga boramiz. Ammo agar bizda kalitlar doirasi mavjud bo'lsa, unda bu doirada barcha kalit qiymatlarini ko'rib chiqish kerak va yakuniy bosqichda bizda kalitlar doirasida qancha shardlar bo'lsa, yoki hamma serverga borish kerak. Vaziyat, albatta, yaxshilandi, lekin barcha so'rovlar uchun emas. Ba'zi so'rovlar zarar ko'rdi.

Tabiiy sharding (F = object.date % num_shards)

Ba'zida, ya'ni tez-tez, trafikaning 95% va yuklanishning 95% - bu qandaydir tabiiy shardingga ega bo'lgan so'rovlar. Masalan, 95% ijtimoiy-analitik so'rovlar faqat oxirgi 1 kun, 3 kun, 7 kunlik ma'lumotlarni qamrab oladi, qolgan 5% esa bir necha oxirgi yillarga murojaat qiladi. Ammo shunday qilib, foydalanuvchilarning qiziqishi oxirgi bir necha kunga qaratilgan bo'lsa, 95% so'rov tabiiy sharding bilan taqsimlangan.

Bunday holda, ma'lumotlarni sana bo'yicha, masalan, bir kunga bo'lish mumkin va biror kunga oid ma'lumot yoki obyekt bo'yicha so'rovga javob olish uchun ushbu shardga borish kerak bo'ladi.

Hayot yaxshilanadi - endi biz nafaqat muayyan ob'ektning joylashuvidan xabardormiz, balki diapazon haqida ham bilamiz. Agar bizdan sanalar diapazonini emas, balki boshqa kolonkalarning diapazonini so'rasalar, albatta, barcha shardlarni ko'rib chiqish kerak. Ammo o'yin shartlariga ko'ra, bunday so'rovlarning faqat 5% mavjud.

Ko'rinib turibdiki, biz barchasini ideal bir yechim topdik, lekin ikkita muammo bor:

• Bu yechim faqat maxsus holat uchun mo'ljallangan, qachonki 95% so'rovlar faqat oxirgi haftani qamrab oladi.
• Chunki 95% so'rovlar oxirgi haftani qamrab oladi, ularning barchasi bu oxirgi haftani xizmat qiladigan bitta shardga tushadi. Bu shard eritilib ketadi, shu bilan birga boshqalar bekor qo'yib turishadi. Shu bilan birga, ularni tashlab bo'lmaydi, arxiv ma'lumotlar ham saqlanishi kerak.

Bu yomon sharding sxemasi emasligini aytish mumkin emas - biz issiq ma'lumotlarni ajratib oldik, biroq eng issiq shard bilan bir narsa qilish kerak.

Muammo turli hiyla va chayqashlar, ya'ni hozirgi kun uchun yondirilgan replikalar sonini oshirish, keyin kun o'tgan va arxivga o'tganda replikalar sonini asta-sekin kamaytirish orqali hal qilinadi. Bu yerda "ma'lumotlarni klaster bo'ylab shunday tarqatish uchun sehrli xesh-funksiyani qo'llab" deb nomlangan ideal bir yechim yo'q.

2.5 To'lanadigan narx

Rasman, biz hozir hammasini bilamiz. Rostdan ham, biz bir ulkan bosh og'rig'i va ikki kichik bosh og'rig'ini bilmaymiz.

1. Oddiy og'riq: yomon taqsimlandi

Bu darslikka oid misol, jangda deyarli uchramaydi, lekin birdan.

• Sanaga oid misol keltiring, faqat sanasiz!
• Qasddan emas notekis (sezilarli) taqsimot.

Sharding mexanizmini tanladik, va/yoki ma'lumotlar o'zgardi, va, albatta, PM talablarni etkazmadi (kodda hech qachon xatolar bo'lmaydi, har doim PM talablar etkazilmaydi), va taqsimot dahshatli notekis bo'ldi. Ya'ni tanlov mezoni bilan adashdik.

Qo'lga olish uchun shardlarning o'lchamlarini ko'rib chiqish kerak. Muammoni biz albatta bir daqiqada, qachonki bizda bitta shard ya isiydi, ya 100 marta boshqalardan katta bo'ladi. Muammoni hal qilish oddiygina kalit yoki sharding funktsiyasini almashtirish bilan amalga oshiriladi.

Bu oddiy muammo, rostini aytsam, men o'ylaymanki, hayotida hech kim bunga duch kelmaydi, lekin birdan kimga yordam berar.

2. 'Yengilmas' og'riq: agregatsiya, join

Milliard yozuvlarni bir jadvalda boshqa jadvalda milliard yozuvlarga qanday join qilish mumkin?

• Qaerda "tezda" hisoblash... RAND() ORASIDA aaa VA bbb?
• Qanday qilib "mo'rt" qilish... users_32shards JOIN posts_1024 shards?

Qisqa javob: hech qanday, azoblansin!

Agar siz birinchi jadvalda milliard yozuvlarni mingta serverga taqsimlandim, ular tezroq ishlashi uchun, ikkinchi jadvalda ham xuddi shu narsani qildingiz, demak, mingdan ming server o'zaro juft-juft gaplashishi kerak. Million ulanishlar yaxshi ishlamaydi. Agar biz bazaga so'rovlar (qidiruv, dokumentlar do'koni yoki tarqatilgan fayl tizimi) qilsak, ular shardlashga to'g'ri kelmasa, bu so'rovlar juda sekinlashadi.

Muqim bir nuqta - ba'zi so'rovlar doimo noqulay taqsimlanadi va sekinlashadi. Ularning foizini kamaytirishga harakat qilish muhimdir. Natijada, milliard yozuvlardan milliardga ulkan joinlar qilish kerak emas. Agar kichik jadval mavjud bo'lsa, unga bog'liq ravishda ulkan shardlangan jadvalda joinlar qilinsa, har bir tugunda nusxalash imkoniyati bo'lsa, buni qilish kerak. Agar joinlar qandaydir mahalliy amalga oshirilsa, masalan, foydalanuvchini va uning postlarini yonma-yon joylashtirish, ularni bir xil joylashda sharding qilish va barcha joinlarni bitta mashina doirasida amalga oshirish imkoniyati mavjud bo'lsa, buni aynan shunday qilish kerak.

Bu alohida uch kunlik ma'ruzalar kursidir, shuning uchun oxirgi adashgan og'riqqa va unga qarshi turish algoritmlariga o'tamiz.

2.6. Murakkab/uzoq og'riq: resharding

Tayyor bo'ling: agar siz birinchi marta o'z ma'lumotlaringizni sharding qilsangiz, o'rtacha besh marta ulardan ko'rib o'tasiz.

Qanday qilib klasterni sozlamang, baribir resharding bo'ladi.

Agar siz juda aqlli va omadlisaningiz bo'lsa, kamida bir marta resharding qilasiz. Lekin bir marta albatta, chunki siz o'ylab ko'rgan vaqtda foydalanuvchiga 10 birliklar yetarli, kimdir shu paytda 30 ga buyurtma yozadi va 100 birlik noma'lum resurslarga so'rov qilingan rejalarda mavjud. Shardlar hech qachon yetarli bo'lmaydi. Birinchi sharding sxemasi bilan siz har qanday holatda adashasiz - doim serverlar sonini oshirishingiz yoki boshqa narsani qilishingiz kerak bo'ladi - umuman olganda, qandaydir ma'lumotlarni qayta joylashtirish kerak bo'ladi.

Xo'sh, agar bizda yoqimli 2 darajali sonlar bo'lsa, masalan, 16 shard-serverlar bo'lsa, ular 32 ga aylangan. 17dan 23ga bo'lingan bo'lsa, ikki o'zaro oddiy sonlar. Qanday qilib ba'zi ma'lumotlar bazalari buni amalga oshiradilar, ehtimol, ularning ichida qandaydir sehr bor? To'g'ri javob: yo'q, ichkarida hech qanday sehr yo'q, ularning ichida bir jahannam bor.

Keyin, nima qilish mumkinligini 'qo'l bilan' ko'rib chiqamiz, ehtimol, 'avtomatik' tushunamiz.

To'g'ridan-to'g'ri #1. Hammasini ko'chirish

Barcha obyektlar uchun NewF(object) hisoblang, yangi shardga joylashtiring.

NewF()=OldF() bir xil bo'lish ehtimoli past.

Deyarli hammasini ko'chiramiz.

Oh.

Hamma 2 milliard yozuvlarni eski shardlardan yangi shardlarga ko'chirish kabi jahannam umid qilamanki, hech qayerda yo'q. Oddiy yondashuv aniq: biz 17 ta mashinaga ega boʻldik, klasterga 6 ta mashina qoʻshdik, 2 milliard yozuvlarni koʻrib chiqdik, ularni 17 ta mashinadan 23 ta mashinaga koʻchiramiz. 10 yilda bir marta, ehtimol, hatto buni ham qilishingiz mumkin. Ammo umuman olganda, bu yomon qaror.

To'g'ridan-to'g'ri #2. Yarmini ko'chiring

Kuzatuvning keyingi sodda yaxshilanishi - keling, bunday ahmoqona sxemadan voz kechamiz – 17 mashinani 23 ga resharding qilishni taqiqlaymiz, va doim 16 mashinani 32 mashinaga resharding qilamiz! Shunda nazariy jihatdan bizga hamma ma'lumotning faqat yarmini ko'chirish kerak bo'ladi va amalda biz buni amalga oshiramiz.

Barcha obyektlar uchun NewF(object) hisoblang, yangi shardga joylashtiring.

Qattiq 2^N bo'ldi, qattiq 2^(N+1) sharding bo'ldi.

NewF()=OldF() ning bir xil bo'lish ehtimoli 0,5.

Taxminan 50% ma'lumotlarni ko'chiramiz.

Optimal, lekin faqat ikki darajalarga bog'langan sonlar uchun ishlaydi.

Aslida, hammasi juda yaxshi, faqat mashinalar soniga ko'ra darajaga bog'liqdir. Bu sodda yondashuv, ajablanarli joyi yo'q ki, ishlay oladi.

E'tibor bering, bu yerda klasterning ikki darajalarga bo'linishi hali ham optimaldir. Har qanday holda, 16 mashinadan klaster qo'shib, biz ma'lumotlarning yarmini qo'shishimiz kerak - va yarmini qo'shamiz.

Yaxshi, lekin insoniyat hech narsa o'ylab topmaganmi - qiziq bir savol tug'iladi. Keling, masalan, biror narsa o'ylab topishimiz mumkinmi?

Qiziqarli #3. Consistent hashing

Albatta, bu yerda consistent hashing haqida doira bilan bir rasm bo'lishi kerak.

Agar "consistent hashing" ni google qilsangiz, albatta doira chiqadi, barcha chiqarish doiralar bilan to'ldirilgan.

Fikr: Keling, shard identifikatorlarini (xeshlarni) doirada chizib qo'yamiz va tepasiga serverlarning xesh identifikatorlarini belgilaymiz. Server qo'shish kerak bo'lganda doiraga yangi joy belgisi qo'yamiz va unga yaqin bo'lgan narsani (va faqat unga yaqin bo'lgan narsani) ko'chirish.

Shardi qo'shishda: hammasini ko'rib chiqmaymiz, faqat 2 "qo'shnini", o'rtacha 1/n ni ko'chiramiz.

Shardi o'chirishda: faqat o'chiriladigan shardni ko'rib chiqamiz, faqat uni ko'chiramiz. Optimum turdagi.

Shardi qo'shishda trafikni minimallashtirish jihatidan juda samarali, va ma'lumotlarni normal taqsimlash jihatidan juda yomon. Chunki, biz ko'p sonli mashinaga taqsimlayotgan barcha bu obyektlarni xesh qilayotganda, biz buni notekis qilamiz: doiradagi nuqtalar notekis joylashadi, va ma'lum bir tugunning yuklashi boshqalardan ancha farq qilishi mumkin.

Bu muammoni hal qilish maqbulida virtual tugunlarning oxirgi qatorini qabul qilishdir. Har bir tugun, har bir server doirada bir nuqta bilan belgilanadi. Server, shard va h.k. qo'shayotganda, bir nechta nuqta qo'shamiz. Haqiqatan ham, bir narsani o'chirganda, shunga mos ravishda bir nechta nuqtani o'chiramiz va ma'lumotlarning kichik qismini ko'chiramiz.

Men bu ajoyib doiralar haqida gapiryapman, chunki, masalan, Cassandra ichida aynan shunday sxema. Ya'ni, u sizda yozuvlarni tugunlar o'rtasida aylantirishni boshlaganda, bilingki, doira sizga qarab turgan va, ehtimol, tasdiqlamasligini ham nazarda tutadi.

Shunga qaramay, birinchi usullarga nisbatan hayot yaxshilandi - biz endi shard qo'shish/o'chirishda barcha yozuvlarni ko'rib chiqmaymiz, faqat ba'zilarini o'rganamiz va faqat ba'zilarini ko'chiramiz.

E'tibor bering, savol: yana yaxshilashning imkoni bormi? Va yana shardlarning yuklashni tenglashtirishni yaxshilashning imkoni bormi? - Aytiladiki, mumkin!

Qiziqarli #4. Rendezvous/HRW

Keyingi oddiy fikr (material o'quv bo'lgani uchun, hech qanday murakkab narsa): shard_id = arg max hash(object_id, shard_id).

U ning nomi nima uchun Rendezvous hashing deyiladi, bilmayman, lekin nima uchun u Highest Random Weight deb ataladi, bilaman. Buni quyidagi tarzda vizualizatsiya qilish juda oson:

Bizda masalan, 16 ta shard bor. Har bir obyekt (satir) uchun, uni bir joyga qo'yish kerak, biz 16 xeshni hisoblaymiz, bu obyekt va shard raqamiga bog'liq bo'lgan. Hash-funksiyasining eng yuqori qiymatiga ega bo'lgan g'olibdir.

Bu deb atalar HRW-hashing, u Rendezvous hashing deb ham ataladi. Shardingning raqamlarini hisoblashning ahmoqona tartibi, bir tomondan, doiralardan ko'ra ko'zga ko'rinadigan sodda tartib, boshqa tomondan.

Yagona minus, yangi shard qo'shishimizda yomonlashdi. Yangi shard qo'shishda ba'zi xeshlar o'zgarib ketishi va hammasini ko'rib chiqishimiz kerak bo'lishi mumkin. Shardni o'chirish texnologiyasi hech o'zgarishsiz.

Yana bir muammo, bu katta shardlar sonida hisoblash qiyin.

Qiziqarli #5. Yana texnika

Qiziq, tadqiqotlar bir joyda turmaydi va Google har yili nimadir yangi kosmik texnikani chop etadi:

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

Agar mavzu sizni o'ziga tortsa, ko'plab dissertationlarni o'qish mumkin. Men bu ma'lumotlarni keltiraman, chunki muammo hal etilmagan, super yechim, uni barcha ma'lumotlar bazalarida amalga oshirish mumkin emas. Hali ham odamlar dissertationlar himoya qilmoqda.

Xulosalar

Gallius Yulius Sezarning sharding deb nomlangan muhim asosiy texnikasi mavjud: "Bo'lin va hukmronlik qil, hukmronlik qil va bo'lin!" Agar ma'lumotlar bitta serverga sig'dirmasa, uni 20 ta serverga bo'lish kerak.

Bularning barchasini bilib, shard qilmaslik yaxshiroq edi, degan tasavvur paydo bo'lishi kerak. Agar siz sharding qilmaslik yaxshiroq deb qaror qilsangiz, bu to'g'ri his. Agar serverga 100$ uchun qo'shimcha xotira qo'shish va hech qanday shard qilmaslik mumkin bo'lsa, unda shunday qilish kerak. Sharding qilganda murakkab tarqatuv tizimi ma'lumotlarni u yoqqa-bu yoqqa ko'chirish bilan paydo bo'ladi, ma'lumotlarni qayerga qo'yishni bilmaslik. Agar buni oldini olish mumkin bo'lsa - kerak oldini olish.

Buni qo'lda qilish yaxshiroq, "baza" (qidiruv, DFS, ...) o'zi sharding qila olishini yaxshiroqdir. Har qanday holda, sooner or later, highload kelib ma'lumotlarni qandaydir bo'lish kerak bo'ladi. Baza o'z-o'zidan buni qila oladi, deb hisoblash mumkin emas, lekin albatta ushbu muammolar yuzaga kelishi mumkin. Algoritmik fundamentalizmni eslang - ichki qayerda nimalar borligini tushunishingiz kerak.

Shardingni sozlayotganda birinchi marta aniq F() ni tanlang, so'rovlar, tarmoq va boshqalar haqida o'ylang. Lekin tayyorlaning, ehtimol, sizga ikki marta tanlash kerak bo'ladi va kamida bir marta hamma narsani qayta qilish kerak bo'ladi.