Sharding: bahagian belakang

2.1 Bagaimana untuk membelah dan memperlahankan N kali?

Anda boleh membelah dan memperlahankan tepat N kali seperti ini:

• Hantar docs00...docs15 permintaan secara berurutan , bukan selari.
• Dalam pertanyaan mudah, buat pilihan bukan dengan kunci , WHERE something=234.

Dalam kes ini, bahagian bersiri (siri) tidak mengambil 1% dan bukan 5%, tetapi kira-kira 20% dalam pangkalan data moden. Anda juga boleh mendapatkan 50% daripada bahagian bersiri jika anda mengakses pangkalan data menggunakan protokol binari yang sangat cekap atau memautkannya sebagai perpustakaan dinamik ke dalam skrip Python.

Selebihnya masa pemprosesan permintaan mudah akan diduduki oleh operasi tidak boleh selari untuk menghurai permintaan, menyediakan pelan, dsb. Iaitu, tidak membaca rekod menjadi perlahan.

Jika kita membahagikan data kepada 16 jadual dan berjalan secara berurutan, seperti kebiasaan dalam bahasa pengaturcaraan PHP, sebagai contoh, (ia tidak begitu baik untuk melancarkan proses tak segerak), maka kita akan mendapat kelembapan 16 kali ganda. Dan, mungkin, lebih banyak lagi, kerana perjalanan pergi balik rangkaian juga akan ditambah.

Tiba-tiba, pilihan bahasa pengaturcaraan adalah penting apabila sharding.

Ingat tentang pilihan bahasa pengaturcaraan, kerana jika anda menghantar pertanyaan ke pangkalan data (atau pelayan carian) secara berurutan, maka dari mana pecutan itu datang? Sebaliknya, akan berlaku kelembapan.

2.2 Mengenai separa automatik

Di beberapa tempat, kecanggihan teknologi maklumat memberi inspirasi kepada seram chthonic. Sebagai contoh, MySQL out of the box tidak mempunyai pelaksanaan sharding kepada versi tertentu yang pasti, bagaimanapun, saiz pangkalan data yang digunakan dalam pertempuran berkembang kepada nilai yang tidak senonoh.

Kemanusiaan yang menderita dalam menghadapi DBA individu telah diseksa selama bertahun-tahun dan menulis beberapa penyelesaian sharding yang buruk berdasarkan apa-apa. Selepas itu, satu penyelesaian sharding yang lebih atau kurang baik ditulis dipanggil ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...). Ini adalah contoh yang terkenal tentang tompok ini.

ProxySQL secara keseluruhan, sudah tentu, penyelesaian kelas perusahaan sepenuhnya untuk sumber terbuka, untuk penghalaan dan banyak lagi. Tetapi salah satu tugas yang perlu diselesaikan ialah sharding untuk pangkalan data, yang dengan sendirinya tidak dapat dipecahkan dengan cara manusia. Anda lihat, tiada suis "serihan = 16", anda sama ada perlu menulis semula setiap permintaan dalam aplikasi, dan terdapat banyak daripadanya di tempat, atau meletakkan beberapa lapisan perantaraan antara aplikasi dan pangkalan data yang kelihatan: "Hmm ... PILIH * DARI dokumen? Ya, ia mesti dipecahkan kepada 16 kecil SELECT * FROM server1.document1, SELECT * FROM server2.document2 - ke pelayan ini dengan log masuk / kata laluan sedemikian, ke pelayan ini dengan yang lain. Jika seseorang tidak menjawab, maka ... ", dsb. Tepat ini boleh dilakukan oleh tompok perantaraan. Mereka sedikit kurang daripada untuk semua pangkalan data. Untuk PostgreSQL, sejauh yang saya faham,

Mengkonfigurasi setiap tampung khusus ialah topik gergasi yang berasingan yang tidak akan dimuatkan dalam satu laporan, jadi kami hanya akan membincangkan konsep asas. Lebih baik kita bercakap sedikit tentang teori buzz.

2.3 Automasi sempurna mutlak?

Keseluruhan teori untuk menjadi tinggi dalam kes sharding dalam huruf ini F() , prinsip asasnya sentiasa sama kira-kira: shard_id = F(objek).

Sharding - apa itu semua? Kami mempunyai 2 bilion rekod (atau 64). Kami mahu memecahkannya kepada beberapa bahagian. Soalan yang tidak dijangka timbul - bagaimana? Dengan prinsip apakah saya harus menyebarkan 2 bilion rekod saya (atau 64) pada 16 pelayan yang tersedia untuk saya?

Ahli matematik terpendam dalam diri kita harus mencadangkan bahawa pada akhirnya sentiasa ada beberapa fungsi ajaib yang, untuk setiap dokumen (objek, garis, dll.), akan menentukan bahagian mana untuk meletakkannya.

Melangkah lebih dalam ke dalam matematik, fungsi ini sentiasa bergantung bukan sahaja pada objek itu sendiri (baris itu sendiri), tetapi juga pada tetapan luaran seperti jumlah bilangan serpihan. Fungsi yang untuk setiap objek mesti memberitahu tempat untuk meletakkannya, tidak boleh mengembalikan nilai lebih daripada terdapat pelayan dalam sistem. Dan fungsinya sedikit berbeza:

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

Tetapi selanjutnya kita tidak akan menggali ke dalam liar fungsi individu ini, kita hanya akan bercakap tentang apakah fungsi ajaib F ().

2.4 Apakah F()?

Mereka boleh menghasilkan banyak mekanisme pelaksanaan yang berbeza dan pelbagai. Contoh ringkasan:

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

Fakta menarik - anda secara semula jadi boleh menyerakkan semua data secara rawak - kami membuang rekod seterusnya pada pelayan sewenang-wenangnya, pada teras sewenang-wenangnya, dalam jadual sewenang-wenangnya. Tidak akan ada banyak kebahagiaan dalam hal ini, tetapi ia akan berkesan.

Terdapat kaedah yang lebih pintar untuk dipecahkan oleh fungsi cincang yang boleh dihasilkan semula atau malah konsisten, atau serpihan oleh beberapa atribut. Mari kita pergi melalui setiap kaedah.

F = rand()

Bertebaran bukan kaedah yang betul. Satu masalah: kami menaburkan 2 bilion rekod kami pada seribu pelayan secara rawak, dan kami tidak tahu di mana rekod itu. Kami perlu mengeluarkan user_1, tetapi kami tidak tahu di mana ia berada. Kami pergi ke seribu pelayan dan menyusun segala-galanya - entah bagaimana ini tidak cekap.

F = somehash()

Mari serak pengguna dengan cara dewasa: hitung fungsi cincang yang boleh dihasilkan semula daripada user_id, ambil baki bahagian mengikut bilangan pelayan, dan segera hubungi pelayan yang dikehendaki.

Mengapa kita melakukan ini? Dan kemudian, bahawa kami mempunyai muatan tinggi dan tiada apa-apa lagi yang sesuai dengan satu pelayan. Jika ia sesuai, hidup akan menjadi begitu mudah.

Hebat, keadaan sudah bertambah baik, untuk mendapatkan satu rekod, kami pergi ke satu pelayan yang diketahui terlebih dahulu. Tetapi jika kita mempunyai julat kunci, maka dalam julat keseluruhan ini kita perlu melalui semua nilai kunci dan, dalam had, pergi sama ada kepada seberapa banyak serpihan yang kita ada kunci dalam julat, atau bahkan ke setiap pelayan. Keadaan telah bertambah baik, sudah tentu, tetapi tidak untuk semua permintaan. Beberapa pertanyaan telah terjejas.

Perpecahan semula jadi (F = object.date % num_shards)

Kadangkala, iaitu, selalunya, 95% daripada trafik dan 95% daripada beban adalah permintaan yang mempunyai beberapa jenis sharding semula jadi. Contohnya, 95% pertanyaan analisis sosial bersyarat mempengaruhi data hanya untuk 1 hari, 3 hari, 7 hari terakhir dan 5% lagi merujuk kepada beberapa tahun lepas. Tetapi 95% permintaan secara semula jadi dipecahkan mengikut tarikh, minat pengguna sistem tertumpu pada beberapa hari terakhir.

Dalam kes ini, anda boleh membahagikan data mengikut tarikh, contohnya, dengan satu hari, dan mengikuti respons kepada permintaan untuk laporan untuk beberapa hari atau objek dari hari ini ke serpihan ini dan pergi.

Kehidupan bertambah baik - kita kini bukan sahaja mengetahui lokasi objek tertentu, tetapi kita juga tahu tentang julat. Jika kita diminta bukan untuk julat tarikh, tetapi untuk julat lajur lain, maka, sudah tentu, kita perlu melalui semua serpihan. Tetapi mengikut peraturan permainan, kami hanya mempunyai 5% daripada permintaan sedemikian.

Nampaknya kami telah menghasilkan penyelesaian yang ideal untuk segala-galanya, tetapi terdapat dua masalah:

• Penyelesaian ini disesuaikan untuk kes tertentu, apabila 95% permintaan hanya melibatkan minggu lepas.
• Memandangkan 95% permintaan menyentuh minggu lepas, mereka semua akan jatuh pada satu serpihan yang berfungsi minggu lepas. Serpihan ini akan cair, manakala yang lain akan terbiar pada masa ini. Pada masa yang sama, anda tidak boleh membuangnya; data arkib juga mesti disimpan.

Bukan untuk mengatakan bahawa ini adalah skim sharding yang buruk - kami memotong data panas, namun, sesuatu perlu dilakukan dengan shard yang paling hangat.

Masalahnya diselesaikan dengan telatah, lompat dan tuam, iaitu, peningkatan bilangan replika untuk hari semasa yang terbakar, kemudian penurunan beransur-ansur dalam bilangan replika apabila hari ini menjadi masa lalu dan masuk ke dalam arkib. Tiada penyelesaian ideal yang dipanggil "anda hanya perlu menyebarkan data ke atas kelompok dengan fungsi cincang ajaib dengan cara yang salah".

2.5 Harga yang perlu dibayar

Secara formal, kita tahu sekarang kita tahu "segala-galanya". Benar, kita tidak tahu satu sakit kepala gergasi dan dua sakit kepala yang lebih kecil.

1. Sakit mudah: berlumur teruk

Ini adalah contoh dari buku teks, yang hampir tidak pernah berlaku dalam pertempuran, tetapi tiba-tiba.

• Sebagai contoh dengan tarikh, hanya tanpa tarikh!
• Pengagihan tidak sekata (boleh dilihat) yang tidak disengajakan .

Mereka memilih mekanisme sharding, dan/atau data berubah, dan, sudah tentu, PM tidak menyampaikan keperluan (kami tidak mempunyai ralat dalam kod, PM sentiasa tidak melaporkan keperluan), dan pengedaran menjadi sangat tidak sekata. Iaitu, mereka terlepas kriteria.

Untuk menangkap, anda perlu melihat saiz serpihan. Kita pasti akan melihat masalah pada masa ini apabila salah satu serpihan kita sama ada terlalu panas atau menjadi 100 kali lebih besar daripada yang lain. Anda boleh membetulkannya hanya dengan menggantikan kunci atau fungsi sharding.

Ini adalah masalah mudah, sejujurnya, saya tidak fikir sekurang-kurangnya satu daripada seratus orang akan menghadapi ini dalam hidup, tetapi tiba-tiba ia akan membantu sekurang-kurangnya seseorang.

2. Kesakitan "tidak dapat dikalahkan": pengagregatan, bergabung

Bagaimana untuk membuat pilihan yang menyertai satu bilion rekod dari satu jadual untuk satu bilion rekod dari jadual lain?

• Bagaimana untuk "cepat" mengira... DI MANA randcol ANTARA aaa DAN bbb?
• Bagaimana untuk "bijak" melakukan... users_32shards JOIN posts_1024 shards?

Jawapan ringkas: tidak mungkin, menderita!

Jika anda mengedarkan satu bilion rekod kepada seribu pelayan dalam jadual pertama supaya mereka berfungsi dengan lebih pantas, dan melakukan perkara yang sama dalam jadual kedua, maka secara semula jadi seribu hingga seribu pelayan harus bercakap antara satu sama lain secara berpasangan. Sejuta sambungan tidak akan berfungsi dengan baik. Jika kami membuat permintaan kepada pangkalan data (carian, storan, stor dokumen atau sistem fail yang diedarkan) yang tidak sesuai dengan sharding, permintaan ini akan menjadi perlahan.

Perkara penting ialah sesetengah permintaan akan sentiasa tidak berjaya dicemari dan akan menjadi perlahan . Adalah penting untuk cuba meminimumkan peratusan mereka. Akibatnya, tidak perlu membuat gabungan gergasi dengan rekod satu bilion dengan satu bilion. Jika mungkin untuk meniru jadual kecil, berbanding yang anda sertai dalam jadual kongsi gergasi, kepada semua nod, anda harus melakukannya. Jika cantuman itu sebenarnya setempat dalam beberapa cara, contohnya, adalah mungkin untuk meletakkan pengguna dan siarannya bersebelahan, membelahnya dengan cara yang sama, dan melakukan semua cantuman dalam mesin yang sama - anda perlu berbuat demikian. .

Ini adalah kursus kuliah yang berasingan selama tiga hari, jadi mari kita beralih kepada kesakitan neraka terakhir dan algoritma yang berbeza untuk menanganinya.

2.6. Kesakitan Kompleks/Panjang: Penyatuan semula

Bersedia: jika anda membelah data anda buat kali pertama dalam hidup anda, maka secara purata anda akan membelahnya lima kali lagi.

Tidak kira berapa banyak kluster yang anda konfigurasikan, anda masih perlu mengeras semula.

Jika anda sangat bijak dan bertuah, maka overshard sekurang-kurangnya sekali. Tetapi apabila anda pasti, kerana pada masa ini apabila anda berfikir bahawa 10 unit sudah mencukupi untuk pengguna, seseorang pada masa itu menulis permintaan untuk 30, dan merancang untuk meminta 100 unit sumber yang tidak diketahui. Serpihan tidak pernah cukup. Dengan skim sharding pertama, dalam apa jua keadaan, anda akan terlepas - anda sentiasa perlu sama ada menambah bilangan pelayan untuk ditambah, atau melakukan sesuatu yang lain - secara umum, entah bagaimana membungkus semula data.

Adalah baik jika kita mempunyai kuasa dua yang bagus: terdapat 16 serpihan pelayan, kini 32. Lebih seronok jika 17, 23 - dua nombor perdana vasimally. Bagaimanakah pangkalan data melakukannya, mungkin mereka mempunyai sejenis keajaiban di dalamnya?

Jawapan yang betul ialah: tidak, tiada sihir di dalam, mereka mempunyai neraka di dalamnya.

Seterusnya, kita akan mempertimbangkan apa yang boleh dilakukan "dengan tangan", mungkin kita akan faham "sebagai mesin automatik".

Di dahi #1. Pindahkan Semuanya

Untuk semua objek, kami menganggap NewF(objek), beralih kepada shard baharu.

Peluang padanan NewF()=OldF() adalah rendah.

Mari kita tutup hampir semua perkara.

Oh.

Saya harap tidak ada neraka untuk memindahkan semua 2 bilion rekod daripada serpihan lama kepada yang baru. Pendekatan naif boleh difahami: terdapat 17 mesin, 6 mesin telah ditambahkan ke kluster, 2 bilion rekod telah disusun, mereka telah dialihkan daripada 17 mesin kepada 23 mesin. Sekali setiap 10 tahun, anda mungkin boleh melakukannya. Tetapi secara keseluruhan ia adalah satu tindakan yang tidak baik.

Di dahi #2. Pindahkan separuh

Penambahbaikan naif seterusnya - mari kita tinggalkan skim bodoh seperti itu - akan melarang 17 kereta daripada diubah menjadi 23, dan kami akan sentiasa mengubah 16 kereta menjadi 32 kereta! Kemudian, mengikut teori, kita perlu mengalih tepat separuh daripada data, dan dalam amalan kita juga boleh melakukan ini.

Untuk semua objek, kami menganggap NewF(objek), beralih kepada shard baharu.

Dahulunya 2^N, kini 2^(N+1) serpihan.

Kebarangkalian untuk memadankan NewF()=OldF() ialah 0.5.

Mari kita pindahkan kira-kira 50% daripada data.

Optimum, tetapi hanya berfungsi untuk kuasa dua.

Pada dasarnya, semuanya baik-baik saja, kecuali untuk mengikat kuasa dua dari segi bilangan kereta. Pendekatan naif ini, anehnya, boleh berfungsi.

Sila ambil perhatian bahawa pemisahan tambahan kluster dengan kuasa dua dalam kes ini juga adalah optimum. Walau apa pun, menambah 16 mesin kepada kelompok 16, kami diwajibkan untuk mengalihkan separuh daripada data - betul-betul separuh dan beralih.

Baiklah, tetapi adakah manusia benar-benar tidak mencipta apa-apa lagi - persoalannya timbul daripada fikiran yang ingin tahu.

Lebih menyeronokkan #3. Pencincangan yang konsisten

Sudah tentu, gambar dengan bulatan tentang pencincangan yang konsisten diperlukan di sini.

Jika anda google "pencincangan konsisten", maka bulatan pasti akan keluar, semua hasil diisi dengan kalangan.

Idea: mari lukis pengecam serpihan (cincang) pada bulatan dan tandakan pengecam pelayan yang dicincang di atas. Apabila anda perlu menambah pelayan, kami meletakkan titik baharu pada bulatan, dan apa yang ternyata dekat dengannya (dan hanya apa yang ternyata dekat dengannya), kami berpindah.

Apabila menambah serpihan: kami tidak melihat semua perkara, tetapi hanya 2 "jiran", kami beralih secara purata 1/n.

Apabila memadam serpihan: kita hanya melihat serpihan yang dipadamkan, kita mengalihkannya sahaja. Macam optimum.

Sangat berkesan dari segi meminimumkan trafik apabila menambah serpihan, dan benar-benar menjijikkan dari segi pengimbangan data biasa. Kerana apabila kita mencincang semua objek yang kita edarkan kepada sebilangan besar mesin, kita melakukannya secara agak tidak sekata: titik di sekeliling bulatan tidak sekata, dan beban setiap nod tertentu boleh menjadi sangat berbeza daripada yang lain.

Masalah ini diselesaikan oleh baris terakhir nod maya. Setiap nod, setiap pelayan pada bulatan ditunjukkan oleh lebih daripada satu titik. Dengan menambahkan pelayan, serpihan, dsb., kami menambah beberapa mata. Setiap kali kami mengalih keluar sesuatu, kami sewajarnya mengalih keluar beberapa titik dan mengalihkan sebahagian kecil data.

Saya bercakap tentang ruang ini dengan bulatan, kerana, sebagai contoh, skema sedemikian berada di dalam Cassandra. Iaitu, apabila dia mula mengejar rekod antara nod, ketahui bahawa bulatan itu memandang anda dan mungkin tidak bersetuju.

Walau bagaimanapun, berbanding dengan kaedah pertama, kehidupan telah bertambah baik - apabila menambah / mengeluarkan serpihan, kami sudah melihat bukan semua rekod, tetapi hanya sebahagian, dan beralih hanya sebahagian.

Perhatian, persoalannya ialah: bolehkah ia diperbaiki lagi? Dan juga meningkatkan keseragaman pemuatan serpihan? Mereka berkata ia mungkin!

Lebih menyeronokkan #4. Rendezvous/HRW

Idea mudah seterusnya (bahannya adalah pendidikan, jadi tiada yang rumit): shard_id = arg max hash(object_id, shard_id).

Mengapa ia dipanggil pencincangan Rendezvous saya tidak tahu, tetapi saya tahu mengapa ia dipanggil Berat Rawak Tertinggi. Sangat mudah untuk memvisualisasikannya seperti ini:

Kami mempunyai, sebagai contoh, 16 serpihan. Untuk setiap objek (rentetan) yang perlu diletakkan di suatu tempat, kami mengira 16 cincang bergantung pada objek daripada nombor serpihan. Sesiapa yang mempunyai nilai hash tertinggi menang.

Ini adalah apa yang dipanggil HRW-hashing, aka Rendezvous hashing. Bodoh seperti kayu, skema untuk mengira bilangan serpihan, pertama, lebih mudah pada mata daripada bulatan dan memberikan beban seragam, sebaliknya.

Satu-satunya negatif ialah menambah serpihan baru telah memburukkan kita. Terdapat risiko apabila menambah serpihan baharu, kami masih mempunyai beberapa cincang yang akan berubah dan mungkin perlu menyemak segala-galanya. Teknologi penyingkiran serpihan tidak banyak berubah.

Masalah lain ialah ia adalah berat secara pengiraan dengan sejumlah besar serpihan.

Lebih menyeronokkan #5. Lebih banyak teknik

Menariknya, penyelidikan tidak berdiam diri dan Google menerbitkan beberapa teknologi angkasa lepas baharu setiap tahun:

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

Jika anda berminat dengan subjek tersebut, anda boleh membaca banyak disertasi. Saya membentangkan data ini untuk menjelaskan bahawa masalah itu belum diselesaikan, tidak ada penyelesaian super yang boleh dilaksanakan dalam semua pangkalan data. Sampai sekarang orang pertahankan disertasi.

kesimpulan

Terdapat teknik asas penting yang dipanggil sharding yang dinamakan sempena Gallius Julius Caesar: "Divide and rule, rule and divide!". Jika data tidak masuk ke dalam satu pelayan, adalah perlu untuk membahagikannya kepada 20 pelayan.

Setelah mempelajari semua ini, seseorang harus mendapat tanggapan bahawa lebih baik tidak membelah. Jika anda memutuskan bahawa adalah lebih baik untuk tidak membelah, ini adalah perasaan yang betul. Jika anda boleh menambah memori pada pelayan dengan harga $100 dan bukan shard apa-apa, maka anda harus melakukannya. Apabila sharding, sistem teragih yang kompleks akan muncul dengan memindahkan data ke sana ke mari, menyusun data tanpa sesiapa yang tahu di mana. Kalau boleh dielakkan, mesti dielakkan.

Adalah lebih baik untuk tidak melakukannya dengan tangan, lebih baik "asas" (carian, DFS, ...) boleh memecah dirinya sendiri. Walau apa pun, lambat laun, muatan tinggi akan datang dan entah bagaimana data perlu dipecahkan. Ia bukan fakta bahawa walaupun pangkalan boleh melakukannya sendiri, anda tidak akan menghadapi sebarang masalah. Ingat tentang fundamentalisme algoritma - anda perlu memahami bagaimana semuanya berfungsi di dalamnya.

Apabila menyediakan sharding buat kali pertama, pilih F() dengan berhati-hati, fikirkan tentang permintaan, rangkaian, dsb. Tetapi bersedia, anda mungkin perlu memilih 2 kali dan sekurang-kurangnya sekali anda perlu membuat semula segala-galanya.