Pecahan

1.1 Apa itu sharding?

Jika Anda terus-menerus google, ternyata ada batas yang agak kabur antara yang disebut partisi dan yang disebut sharding. Semua orang memanggil apa pun yang mereka inginkan, apa pun yang mereka inginkan. Beberapa orang membedakan antara partisi horizontal dan sharding. Yang lain mengatakan bahwa sharding adalah jenis partisi horizontal tertentu.

Saya tidak menemukan satu pun standar terminologis yang akan disetujui oleh para pendiri dan disertifikasi oleh ISO. Keyakinan batin pribadi adalah seperti ini: Partisi rata-rata adalah "memotong dasar menjadi beberapa bagian" dengan cara yang diambil secara sewenang-wenang.

• Partisi vertikal - berdasarkan kolom. Misalnya, ada meja raksasa dengan beberapa miliar catatan dalam 60 kolom. Alih-alih menyimpan satu tabel raksasa seperti itu, kami menyimpan setidaknya 60 tabel raksasa yang masing-masing berisi 2 miliar catatan - dan ini bukan basis kolom, tetapi partisi vertikal (sebagai contoh terminologi).
• Partisi horizontal - kami memotong baris demi baris, mungkin di dalam server.

Momen canggung di sini adalah perbedaan halus antara partisi horizontal dan sharding. Saya dapat dipotong-potong, tetapi saya tidak dapat memberi tahu Anda dengan pasti apa itu. Ada perasaan bahwa sharding dan partisi horizontal adalah hal yang sama.

Sharding , secara umum, ketika tabel besar dalam hal database atau pro-koleksi dokumen, objek, jika Anda tidak memiliki database, tetapi penyimpanan dokumen, dipotong persis oleh objek. Artinya, dari 2 miliar objek, kepingan dipilih terlepas dari ukurannya. Objek itu sendiri di dalam setiap objek tidak dipotong-potong, kami tidak meletakkannya di kolom terpisah, yaitu kami meletakkannya secara berkelompok di tempat yang berbeda.

Ada perbedaan terminologis yang halus. Misalnya, secara relatif, pengembang Postgres dapat mengatakan bahwa partisi horizontal adalah ketika semua tabel yang membagi tabel utama terletak pada skema yang sama, dan ketika pada mesin yang berbeda, ini sudah menjadi sharding.

Secara umum, tanpa terikat pada terminologi database tertentu dan sistem manajemen data tertentu, ada kesan bahwa sharding hanyalah mengiris baris demi baris / dokumen demi dokumen, dan seterusnya - itu saja.

Saya menekankan tipikal. Dalam arti bahwa kami melakukan semua ini tidak hanya untuk memotong 2 miliar dokumen menjadi 20 tabel, yang masing-masing akan lebih mudah dikelola, tetapi untuk mendistribusikannya ke banyak inti, banyak disk, atau banyak server fisik atau virtual yang berbeda .

1.2 Membagi yang tak terbagi

Dapat dipahami bahwa kami melakukan ini agar setiap pecahan - setiap bagian data - direplikasi berkali-kali. Tapi sungguh, tidak.

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

Faktanya, jika Anda melakukan pemotongan data seperti itu, dan dari satu tabel SQL raksasa di MySQL di laptop Anda yang gagah berani, Anda akan menghasilkan 16 tabel kecil, tanpa melampaui satu laptop, bukan skema tunggal, bukan database tunggal, dll. . dan seterusnya. - itu saja, Anda sudah memiliki sharding.

Ini menghasilkan yang berikut:

• Bandwidth meningkat.
• Latensi tidak berubah, yaitu, masing-masing, bisa dikatakan, pekerja atau konsumen dalam hal ini, mendapatkan miliknya sendiri. Permintaan yang berbeda dilayani pada waktu yang hampir bersamaan.
• Atau keduanya, dan lainnya, serta ketersediaan tinggi (replikasi).

Mengapa bandwidth? Kami kadang-kadang dapat memiliki volume data yang tidak cocok - tidak jelas di mana, tetapi tidak cocok - pada 1 {kernel | cakram | server | ...}. Tidak ada sumber daya yang cukup, itu saja. Untuk bekerja dengan kumpulan data besar ini, Anda harus memotongnya.

Mengapa latensi? Pada satu inti, memindai tabel berisi 2 miliar baris 20 kali lebih lambat daripada memindai 20 tabel pada 20 inti, melakukannya secara paralel. Data diproses terlalu lambat pada satu sumber daya.

Mengapa ketersediaan tinggi? Atau kami memotong data untuk melakukan keduanya sekaligus, dan pada saat yang sama beberapa salinan dari setiap pecahan - replikasi memastikan ketersediaan yang tinggi.

1.3 Contoh sederhana "bagaimana melakukannya dengan tangan"

Pecahan bersyarat dapat dipotong menggunakan tabel uji test.documents untuk 32 dokumen, dan menghasilkan 16 tabel uji dari tabel ini, masing-masing sekitar 2 dokumen test.docs00, 01, 02, ..., 15.

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

Mengapa tentang? Karena secara apriori kita tidak tahu bagaimana id didistribusikan, jika dari 1 sampai 32 inklusif, maka masing-masing akan ada 2 dokumen, jika tidak tidak.

Kami melakukannya di sini mengapa. Setelah kami membuat 16 tabel, kami dapat "mengambil" 16 dari yang kami butuhkan. Terlepas dari apa yang kami pukul, kami dapat memparalelkan sumber daya ini. Misalnya, jika ruang disk tidak cukup, masuk akal untuk menguraikan tabel ini pada disk terpisah.

Semua ini, sayangnya, tidak gratis. Saya menduga bahwa dalam kasus standar SQL kanonik (saya sudah lama tidak membaca ulang standar SQL, mungkin sudah lama tidak diperbarui), tidak ada sintaks standar resmi untuk mengatakan ke server SQL mana pun : "Server SQL yang terhormat, buatkan saya 32 pecahan dan bagi menjadi 4 disk. Namun dalam implementasi individu, seringkali ada sintaks khusus untuk melakukan hal yang pada dasarnya sama. PostgreSQL memiliki mekanisme untuk mempartisi, MySQL memiliki MariaDB, Oracle mungkin sudah melakukannya sejak lama.

Namun demikian, jika kita melakukannya dengan tangan, tanpa dukungan database dan dalam kerangka standar, maka kita membayar secara kondisional dengan kompleksitas akses data . Di mana ada SELECT * FROM dokumen sederhana WHERE id=123, sekarang 16 x SELECT * FROM docsXX. Dan alangkah baiknya jika kita mencoba mendapatkan record dengan kunci. Jauh lebih menarik jika kami mencoba mendapatkan rekor awal. Sekarang (jika kita, saya tekankan, seolah-olah bodoh, dan tetap dalam kerangka standar), hasil dari 16 SELECT * FROM ini harus digabungkan dalam aplikasi.

Perubahan kinerja apa yang dapat Anda harapkan?

• Secara intuitif - linier.
• Secara teoritis - sublinear, karena hukum Amdahl.
• Secara praktis, mungkin hampir linier, mungkin juga tidak.

Faktanya, jawaban yang benar tidak diketahui. Dengan penerapan teknik sharding yang cerdas, Anda dapat mencapai degradasi super-linier yang signifikan dalam kinerja aplikasi Anda, dan bahkan DBA akan berjalan dengan poker panas.

Mari kita lihat bagaimana ini bisa dicapai. Jelas bahwa hanya menyetel pengaturan ke PostgreSQL shards=16, lalu lepas dengan sendirinya, tidaklah menarik. Mari kita pikirkan tentang bagaimana kita dapat memastikan bahwa kita memperlambat sharding sebanyak 16 kali sebanyak 32 kali - ini menarik dari sudut pandang bagaimana tidak melakukan ini.

Upaya kami untuk mempercepat atau memperlambat akan selalu mengarah ke klasik - hukum Amdahl lama yang baik, yang mengatakan bahwa tidak ada paralelisasi sempurna dari permintaan apa pun, selalu ada bagian yang konsisten.

1.4 Hukum Amdahl

Selalu ada bagian serial.

Selalu ada bagian eksekusi query yang diparalelkan, dan selalu ada bagian yang tidak diparalelkan. Meskipun menurut Anda kueri paralel sempurna, setidaknya kumpulan baris hasil yang akan Anda kirim ke klien dari baris yang diterima dari setiap pecahan selalu ada, dan selalu berurutan.

Selalu ada bagian yang konsisten. Itu bisa kecil, sama sekali tidak terlihat dengan latar belakang umum, bisa sangat besar dan, karenanya, sangat memengaruhi paralelisasi, tetapi selalu ada.

Selain itu, pengaruhnya berubah dan dapat tumbuh secara signifikan, misalnya jika kita memotong meja kita - mari kita naikkan taruhannya - dari 64 record menjadi 16 tabel dari 4 record, bagian ini akan berubah. Tentu saja, dilihat dari jumlah data yang sangat besar, kami sedang mengerjakan ponsel dan prosesor 2 MHz 86, dan kami tidak memiliki cukup file yang dapat dibuka pada saat yang bersamaan. Rupanya, dengan input seperti itu, kami membuka file satu per satu.

• Itu Total = Serial + Paralel . Di mana, misalnya, paralel adalah semua pekerjaan di dalam DB, dan serial mengirimkan hasilnya ke klien.
• Menjadi Total2 = Serial + Paralel/N + Xserial . Misalnya, ketika secara keseluruhan ORDER BY, Xserial>0.

Dengan contoh sederhana ini, saya mencoba menunjukkan bahwa beberapa Xserial muncul. Selain fakta bahwa selalu ada bagian serial, dan fakta bahwa kami mencoba bekerja dengan data secara paralel, ada bagian tambahan untuk menyediakan pemotongan data ini. Secara kasar, kita mungkin perlu:

• temukan 16 tabel ini di kamus internal basis data;
• buka file;
• mengalokasikan memori;
• membatalkan alokasi memori;
• menggabungkan hasil;
• sinkronisasi antar core.

Beberapa efek tidak sinkron masih muncul. Mereka bisa jadi tidak penting dan menempati sepersejuta dari total waktu, tetapi mereka selalu bukan nol dan selalu ada. Dengan bantuan mereka, kami dapat kehilangan kinerja secara dramatis setelah sharding.

Ini adalah gambaran standar tentang hukum Amdahl. Yang penting di sini adalah bahwa garis-garis, yang idealnya harus lurus dan tumbuh secara linier, menjadi asimtot. Tetapi karena grafik dari Internet tidak dapat dibaca, menurut pendapat saya, saya membuat lebih banyak tabel visual dengan angka.

Katakanlah kita memiliki beberapa bagian serial dari pemrosesan permintaan yang hanya membutuhkan waktu 5%: serial = 0.05 = 1 / 20 .

Secara intuitif, tampaknya dengan bagian serial yang hanya membutuhkan 1/20 dari pemrosesan permintaan, jika kita memparalelkan pemrosesan permintaan untuk 20 inti, itu akan menjadi sekitar 20, dalam kasus terburuk 18, kali lebih cepat.

Faktanya, matematika adalah hal yang tidak berperasaan :

dinding = 0,05 + 0,95/num_cores, percepatan = 1 / (0,05 + 0,95/num_cores)

Ternyata jika Anda menghitung dengan hati-hati, dengan bagian serial 5%, percepatannya akan menjadi 10 kali lipat (10,3), yaitu 51% dibandingkan dengan ideal teoretis.

Setelah menggunakan 20 core (20 disk, jika Anda suka) untuk tugas yang pernah dikerjakan, kami bahkan tidak akan pernah secara teoritis mendapatkan akselerasi lebih dari 20 kali, tetapi dalam praktiknya - apalagi. Selain itu, dengan bertambahnya jumlah paralel, inefisiensi meningkat pesat.

Ketika hanya 1% dari pekerjaan serial yang tersisa, dan 99% diparalelkan, nilai percepatan agak meningkat:

Untuk kueri termonuklir sempurna, yang secara alami membutuhkan waktu berjam-jam untuk diselesaikan, dan pekerjaan persiapan serta perakitan hasilnya membutuhkan waktu yang sangat singkat (serial = 0,001), kita akan melihat efisiensi yang baik:

Harap dicatat bahwa kami tidak akan pernah melihat 100% . Dalam kasus yang sangat bagus, Anda dapat melihat, misalnya, 99,999%, tetapi tidak persis 100%.