Course All lectures for ID purposes - Lecture: Sharding: sisi sebaliknya

2.1 Bagaimana cara melakukan shard dan memperlambat N kali?

Anda dapat melakukan shard dan memperlambat persis N kali seperti ini:

Kirim permintaan docs00...docs15 secara berurutan , bukan paralel.
Dalam kueri sederhana, pilih bukan dengan key , WHERE something=234.

Dalam hal ini, bagian serial (serial) mengambil bukan 1% dan bukan 5%, tetapi sekitar 20% dalam database modern. Anda juga bisa mendapatkan 50% dari bagian serial jika Anda mengakses database menggunakan protokol biner yang sangat efisien atau menautkannya sebagai pustaka dinamis ke dalam skrip Python.

Sisa waktu pemrosesan permintaan sederhana akan ditempati oleh operasi parsing permintaan yang tidak dapat diparalelkan, menyiapkan rencana, dll. Artinya, tidak membaca catatan akan melambat.

Jika kita membagi data menjadi 16 tabel dan dijalankan secara berurutan, seperti kebiasaan dalam bahasa pemrograman PHP, misalnya, (tidak terlalu bagus dalam meluncurkan proses asinkron), maka kita akan mengalami pelambatan 16 kali lipat. Dan, mungkin, bahkan lebih, karena perjalanan pulang-pergi jaringan juga akan ditambahkan.

Tiba-tiba, pilihan bahasa pemrograman menjadi penting saat sharding.

Ingat tentang pilihan bahasa pemrograman, karena jika Anda mengirim kueri ke database (atau server pencarian) secara berurutan, lalu dari mana asal percepatannya? Sebaliknya, akan ada perlambatan.

2.2 Tentang semi-otomatis

Di beberapa tempat, kecanggihan teknologi informasi menginspirasi horor chthonic. Misalnya, MySQL di luar kotak tidak memiliki implementasi sharding untuk versi tertentu, namun, ukuran database yang digunakan dalam pertempuran tumbuh menjadi nilai yang tidak senonoh.

Kemanusiaan yang menderita di hadapan DBA individu telah disiksa selama bertahun-tahun dan menulis beberapa solusi sharding yang buruk berdasarkan ketiadaan. Setelah itu, satu solusi sharding yang kurang lebih layak ditulis disebut ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...). Ini adalah contoh terkenal dari noda ini.

ProxySQL secara keseluruhan, tentu saja, merupakan solusi kelas perusahaan lengkap untuk open source, untuk perutean, dan lainnya. Tetapi salah satu tugas yang harus diselesaikan adalah sharding untuk database, yang dengan sendirinya tidak dapat dipecah dengan cara manusia. Anda lihat, tidak ada sakelar "pecahan = 16", Anda harus menulis ulang setiap permintaan dalam aplikasi, dan ada banyak permintaan di beberapa tempat, atau meletakkan beberapa lapisan perantara antara aplikasi dan database yang terlihat: "Hmm ... PILIH * DARI dokumen? Ya, itu harus dipecah menjadi 16 kecil SELECT * FROM server1.document1, SELECT * FROM server2.document2 - ke server ini dengan login / kata sandi seperti itu, ke server ini dengan yang lain. Jika ada yang tidak menjawab, maka ... ", dll. Persisnya ini bisa dilakukan dengan bercak perantara. Mereka sedikit kurang dari semua database. Untuk PostgreSQL, sejauh yang saya mengerti,

Mengonfigurasi setiap tambalan tertentu adalah topik raksasa terpisah yang tidak muat dalam satu laporan, jadi kami hanya akan membahas konsep dasar. Lebih baik mari kita bicara sedikit tentang teori buzz.

2.3 Otomatisasi sempurna mutlak?

Seluruh teori menjadi tinggi dalam kasus sharding dalam huruf ini F() , prinsip dasarnya selalu sama kira-kira: shard_id = F(object).

Sharding - tentang apa semua ini? Kami memiliki 2 miliar catatan (atau 64). Kami ingin memecahnya menjadi beberapa bagian. Sebuah pertanyaan tak terduga muncul - bagaimana caranya? Dengan prinsip apa saya harus menyebarkan 2 miliar catatan saya (atau 64) pada 16 server yang tersedia untuk saya?

Ahli matematika laten dalam diri kita harus menyarankan bahwa pada akhirnya selalu ada beberapa fungsi ajaib yang, untuk setiap dokumen (objek, garis, dll.), akan menentukan bagian mana yang akan diletakkan.

Masuk lebih dalam ke matematika, fungsi ini selalu bergantung tidak hanya pada objek itu sendiri (baris itu sendiri), tetapi juga pada pengaturan eksternal seperti jumlah pecahan. Fungsi yang untuk setiap objek harus mengetahui di mana harus meletakkannya, tidak dapat mengembalikan nilai lebih dari jumlah server dalam sistem. Dan fungsinya sedikit berbeda:

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

Tetapi lebih jauh kita tidak akan menggali lebih dalam tentang fungsi individu yang liar ini, kita hanya akan berbicara tentang apa itu fungsi ajaib F ().

2.4 Apa itu F()?

Mereka dapat menghasilkan banyak mekanisme implementasi yang berbeda dan banyak. Ringkasan sampel:

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

Fakta menarik - Anda dapat secara alami menyebarkan semua data secara acak - kami melempar catatan berikutnya ke server arbitrer, ke inti arbitrer, ke tabel arbitrer. Tidak akan ada banyak kebahagiaan dalam hal ini, tetapi itu akan berhasil.

Ada metode yang sedikit lebih cerdas untuk melakukan shard dengan fungsi hash yang dapat direproduksi atau bahkan konsisten, atau shard dengan beberapa atribut. Mari kita bahas setiap metode.

F = rand()

Berhamburan bukanlah metode yang sangat tepat. Satu masalah: kami menyebarkan 2 miliar catatan kami di seribu server secara acak, dan kami tidak tahu di mana catatan itu berada. Kami perlu menarik user_1, tetapi kami tidak tahu di mana dia berada. Kami pergi ke seribu server dan memilah semuanya - entah bagaimana ini tidak efisien.

F = beberapa hash()

Mari sebarkan pengguna dengan cara dewasa: hitung fungsi hash yang dapat direproduksi dari user_id, ambil sisa pembagian dengan jumlah server, dan segera hubungi server yang diinginkan.

Mengapa kita melakukan ini? Dan kemudian, kami memiliki beban tinggi dan tidak ada lagi yang cocok dengan satu server. Jika cocok, hidup akan sangat sederhana.

Hebat, situasinya sudah membaik, untuk mendapatkan satu catatan, kami pergi ke satu server yang dikenal terlebih dahulu. Tetapi jika kita memiliki rentang kunci, maka di seluruh rentang ini kita harus melalui semua nilai kunci dan, dalam batas, pergi ke pecahan sebanyak kunci yang kita miliki dalam rentang tersebut, atau bahkan ke setiap server. Situasinya telah membaik, tentu saja, tetapi tidak untuk semua permintaan. Beberapa kueri telah terpengaruh.

Pecahan alami (F = object.date % num_shards)

Terkadang, seringkali, 95% lalu lintas dan 95% beban adalah permintaan yang memiliki semacam sharding alami. Misalnya, 95% kueri analitik sosial bersyarat memengaruhi data hanya untuk 1 hari terakhir, 3 hari, 7 hari, dan 5% sisanya mengacu pada beberapa tahun terakhir. Tetapi 95% dari permintaan dengan demikian secara alami terpotong berdasarkan tanggal, minat pengguna sistem difokuskan pada beberapa hari terakhir.

Dalam hal ini, Anda dapat membagi data berdasarkan tanggal, misalnya, satu hari, dan mengikuti tanggapan atas permintaan laporan untuk beberapa hari atau objek dari hari ini ke pecahan ini dan pergi.

Hidup membaik - kita sekarang tidak hanya mengetahui lokasi objek tertentu, tetapi kita juga mengetahui jangkauannya. Jika kita ditanya bukan rentang tanggal, tetapi rentang kolom lain, maka, tentu saja, kita harus melalui semua pecahan. Tetapi menurut aturan permainan, kami hanya memiliki 5% dari permintaan tersebut.

Tampaknya kami telah menemukan solusi ideal untuk semuanya, tetapi ada dua masalah:

Solusi ini disesuaikan untuk kasus tertentu, ketika 95% permintaan hanya melibatkan minggu lalu.
Karena 95% permintaan menyentuh minggu lalu, semuanya akan jatuh pada satu pecahan yang ditayangkan minggu lalu ini. Pecahan ini akan meleleh, sementara yang lainnya akan menganggur selama ini. Pada saat yang sama, Anda tidak dapat membuangnya, data arsip juga harus disimpan.

Bukan untuk mengatakan bahwa ini adalah skema sharding yang buruk - kami memotong data panas, namun, sesuatu perlu dilakukan dengan pecahan terpanas.

Masalahnya diselesaikan dengan kejenakaan, lompatan dan tapal, yaitu peningkatan jumlah replika untuk pembakaran hari ini, kemudian penurunan jumlah replika secara bertahap ketika hari ini menjadi masa lalu dan masuk ke arsip. Tidak ada solusi ideal yang disebut "Anda hanya perlu menyebarkan data ke cluster dengan fungsi hash ajaib dengan cara yang salah".

2.5 Harga yang harus dibayar

Secara formal, kita tahu sekarang kita tahu "segalanya". Benar, kita tidak tahu satu sakit kepala yang sangat besar dan dua sakit kepala yang lebih kecil.

1. Nyeri sederhana: tercoreng parah

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

Sebagai contoh dengan kencan, hanya tanpa kencan!
Distribusi tidak merata (terlihat) yang tidak disengaja .

Mereka memilih mekanisme sharding, dan/atau data berubah, dan, tentu saja, PM tidak menyampaikan persyaratan (kami tidak memiliki kesalahan dalam kode, PM selalu tidak melaporkan persyaratan), dan distribusi menjadi sangat tidak seimbang. Artinya, mereka melewatkan kriteria.

Untuk menangkap, Anda perlu melihat ukuran pecahannya. Kami pasti akan melihat masalah saat salah satu pecahan kami terlalu panas atau menjadi 100 kali lebih besar dari yang lain. Anda dapat memperbaikinya hanya dengan mengganti kunci atau fungsi sharding.

Ini adalah masalah sederhana, sejujurnya, saya tidak berpikir bahwa setidaknya satu dari seratus orang akan mengalami hal ini dalam hidup, tetapi tiba-tiba itu akan membantu setidaknya seseorang.

2. Rasa sakit "tak terkalahkan": agregasi, bergabung

Bagaimana cara membuat pilihan yang menggabungkan satu miliar catatan dari satu tabel untuk satu miliar catatan dari tabel lain?

Bagaimana cara menghitung "cepat"... DIMANA randcol ANTARA aaa DAN bbb?
Bagaimana cara "dengan cerdas" melakukan... users_32shards JOIN posts_1024 shards?

Jawaban singkat: tidak mungkin, menderita!

Jika Anda mendistribusikan satu miliar catatan ke seribu server di tabel pertama sehingga mereka bekerja lebih cepat, dan melakukan hal yang sama di tabel kedua, maka secara alami seribu hingga seribu server harus berbicara satu sama lain secara berpasangan. Sejuta koneksi tidak akan berfungsi dengan baik. Jika kami membuat permintaan ke basis data (pencarian, penyimpanan, penyimpanan dokumen, atau sistem file terdistribusi) yang tidak cocok dengan sharding, permintaan ini akan sangat melambat.

Poin penting adalah bahwa beberapa permintaan akan selalu tidak berhasil tercoreng dan akan melambat . Penting untuk mencoba meminimalkan persentase mereka. Akibatnya, tidak perlu membuat gabungan besar dengan satu miliar demi satu miliar catatan. Jika memungkinkan untuk mereplikasi tabel kecil, yang berhubungan dengan yang Anda gabungkan dalam tabel bersama raksasa, ke semua node, Anda harus melakukannya. Jika gabungan benar-benar lokal dalam beberapa cara, misalnya, adalah mungkin untuk menempatkan pengguna dan posnya berdampingan, membaginya dengan cara yang sama, dan melakukan semua gabungan dalam mesin yang sama - Anda hanya perlu melakukan itu .

Ini adalah kursus terpisah dari kuliah selama tiga hari, jadi mari beralih ke rasa sakit neraka terakhir dan berbagai algoritme untuk menghadapinya.

2.6. Nyeri Kompleks/Panjang: Resharding

Bersiaplah: jika Anda melakukan sharding data untuk pertama kali dalam hidup Anda, maka rata-rata Anda akan melakukan sharding sebanyak lima kali lagi.

Tidak peduli berapa banyak cluster yang Anda konfigurasikan, Anda tetap perlu melakukan reshard.

Jika Anda sangat pintar dan beruntung, maka lakukan overshard setidaknya sekali. Tetapi begitu Anda yakin, karena pada saat Anda berpikir bahwa 10 unit sudah cukup untuk pengguna, seseorang pada saat itu menulis permintaan untuk 30 unit, dan berencana untuk meminta 100 unit sumber daya yang tidak diketahui. Pecahan tidak pernah cukup. Dengan skema sharding pertama, bagaimanapun, Anda akan kehilangan - Anda harus selalu menambah jumlah server untuk ditambahkan, atau melakukan sesuatu yang lain - secara umum, entah bagaimana mengemas ulang datanya.

Ada baiknya jika kita memiliki kekuatan dua yang bagus: ada 16 pecahan server, sekarang menjadi 32. Lebih menyenangkan jika 17, menjadi 23 - dua bilangan prima yang sangat kecil. Bagaimana database melakukannya, mungkin mereka memiliki semacam keajaiban di dalamnya?

Jawaban yang benar adalah: tidak, tidak ada sihir di dalamnya, mereka memiliki neraka di dalamnya.

Selanjutnya, kita akan melihat apa yang bisa dilakukan "dengan tangan", mungkin kita akan mengerti "sebagai mesin otomatis".

Di dahi #1. Pindahkan Semuanya

Untuk semua objek, kami mempertimbangkan NewF(objek), bergeser ke pecahan baru.

Peluang pencocokan NewF()=OldF() rendah.

Mari kita bahas hampir semuanya.

Oh.

Saya harap tidak ada yang mau mentransfer semua 2 miliar catatan dari pecahan lama ke yang baru. Pendekatan naif dapat dimengerti: ada 17 mesin, 6 mesin ditambahkan ke cluster, 2 miliar catatan disortir, dipindahkan dari 17 mesin menjadi 23 mesin. Setiap 10 tahun sekali, Anda bahkan mungkin bisa melakukannya. Tapi secara keseluruhan itu langkah yang buruk.

Di dahi #2. Pindah setengah

Peningkatan naif berikutnya - mari tinggalkan skema bodoh seperti itu - akan melarang 17 mobil untuk diubah menjadi 23, dan kami akan selalu mengubah 16 mobil menjadi 32 mobil! Kemudian, menurut teori, kita harus menggeser tepat setengah dari data, dan dalam praktiknya kita juga bisa melakukannya.

Untuk semua objek, kami mempertimbangkan NewF(objek), bergeser ke pecahan baru.

Itu benar-benar 2 ^ N, sekarang benar-benar 2 ^ (N +1) pecahan.

Probabilitas pencocokan NewF()=OldF() adalah 0,5.

Mari mentransfer sekitar 50% data.

Optimal, tetapi hanya berfungsi untuk pangkat dua.

Pada prinsipnya, semuanya baik-baik saja, kecuali pengikatan kekuatan dua dalam hal jumlah mobil. Anehnya, pendekatan naif ini bisa berhasil.

Harap dicatat bahwa pemisahan cluster tambahan dengan pangkat dua dalam hal ini juga optimal. Bagaimanapun, menambahkan 16 mesin ke sekelompok 16, kami berkewajiban untuk menggeser setengah dari data - tepatnya setengah dan bergeser.

Oke, tetapi apakah umat manusia benar-benar tidak menemukan hal lain - pertanyaan muncul dari pikiran yang ingin tahu.

Lebih menyenangkan #3. Hashing yang konsisten

Tentu saja, gambar dengan lingkaran tentang hashing yang konsisten diperlukan di sini.

Jika Anda google "hashing konsisten", maka lingkaran pasti akan keluar, semua hasil diisi dengan lingkaran.

Ide: mari menggambar pengidentifikasi shard (hash) pada lingkaran, dan tandai pengidentifikasi server hash di atas. Saat Anda perlu menambahkan server, kami menempatkan titik baru di lingkaran, dan apa yang ternyata dekat dengannya (dan hanya yang ternyata dekat dengannya), kami pindahkan.

Saat menambahkan pecahan: kami tidak melihat semuanya, tetapi hanya 2 "tetangga", kami menggeser rata-rata 1/n.

Saat menghapus pecahan: kami hanya melihat pecahan yang dihapus, kami hanya menggesernya. Agak optimal.

Sangat efektif dalam hal meminimalkan lalu lintas saat menambahkan pecahan, dan benar-benar menjijikkan dalam hal penyeimbangan data normal. Karena ketika kita mencirikan semua objek yang kita distribusikan ke sejumlah besar mesin, kita melakukannya dengan relatif tidak merata: titik-titik di sekitar lingkaran berjarak tidak rata, dan beban setiap node tertentu bisa sangat berbeda dari yang lain.

Masalah ini diselesaikan dengan baris terakhir dari node virtual. Setiap node, setiap server pada lingkaran ditunjukkan oleh lebih dari satu titik. Dengan menambahkan server, pecahan, dll., kami menambahkan beberapa poin. Setiap kali kami menghapus sesuatu, kami menghapus beberapa titik dan menggeser sebagian kecil data.

Saya berbicara tentang ruang dengan lingkaran ini, karena, misalnya, skema seperti itu ada di dalam Cassandra. Yaitu, ketika dia mulai mengejar rekor antar node, ketahuilah bahwa lingkaran itu melihat Anda dan mungkin tidak setuju.

Namun, dibandingkan dengan metode pertama, kehidupan telah meningkat - saat menambahkan / menghapus pecahan, kami tidak melihat semua catatan, tetapi hanya sebagian, dan hanya menggeser sebagian.

Perhatian, pertanyaannya adalah: dapatkah ditingkatkan lebih lanjut? Dan juga meningkatkan keseragaman pemuatan pecahan? Mereka bilang itu mungkin!

Lebih menyenangkan #4. Rendezvous/HRW

Ide sederhana berikutnya (materinya mendidik, jadi tidak rumit): shard_id = arg max hash(object_id, shard_id).

Mengapa ini disebut Rendezvous hashing Saya tidak tahu, tapi saya tahu mengapa ini disebut Berat Acak Tertinggi. Sangat mudah untuk memvisualisasikannya seperti ini:

Kami memiliki, misalnya, 16 pecahan. Untuk setiap objek (string) yang perlu diletakkan di suatu tempat, kami menghitung 16 hash tergantung pada objek dari nomor beling. Siapa pun yang memiliki nilai hash tertinggi akan menang.

Inilah yang disebut HRW-hashing, alias Rendezvous hashing. Bodoh seperti tongkat, skema untuk menghitung jumlah pecahan, pertama, lebih mudah dilihat daripada lingkaran dan sebaliknya memberikan beban yang seragam.

Satu-satunya negatif adalah menambahkan pecahan baru telah memperburuk kami. Ada risiko saat menambahkan pecahan baru, kami masih memiliki beberapa hash yang akan berubah dan mungkin perlu meninjau semuanya. Teknologi penghilangan pecahan tidak banyak berubah.

Masalah lainnya adalah berat secara komputasi dengan sejumlah besar pecahan.

Lebih menyenangkan #5. Lebih banyak teknik

Menariknya, penelitian tidak berhenti dan Google menerbitkan beberapa teknologi luar angkasa baru setiap tahun:

Langsung Hash - Google '2014.
Multi Penyelidikan—Google '2015.
Maglev-Google '2016.

Jika Anda tertarik dengan subjeknya, Anda dapat membaca banyak disertasi. Data ini saya sajikan untuk memperjelas bahwa masalah belum terselesaikan, tidak ada solusi super yang dapat diterapkan di semua database. Hingga saat ini, orang mempertahankan disertasi.

kesimpulan

Ada teknik dasar penting yang disebut sharding yang dinamai menurut nama Gallius Julius Caesar: “Pisahkan dan kuasai, kuasai dan bagi!”. Jika data tidak masuk ke dalam satu server, maka perlu dipecah menjadi 20 server.

Setelah mempelajari semua ini, seseorang harus mendapat kesan bahwa lebih baik tidak melakukan pecahan. Jika Anda memutuskan bahwa lebih baik tidak melakukan pecahan, ini adalah perasaan yang tepat. Jika Anda dapat menambahkan memori ke server seharga $100 dan tidak merusak apa pun, maka Anda harus melakukannya. Saat sharding, sistem terdistribusi yang kompleks akan muncul dengan transfer data bolak-balik, menumpuk data entah di mana. Kalau bisa dihindari, ya harus dihindari.

Lebih baik tidak melakukannya dengan tangan, lebih baik "basis" (pencarian, DFS, ...) dapat menghancurkan dirinya sendiri. Bagaimanapun, cepat atau lambat, beban tinggi akan datang dan entah bagaimana datanya harus dipecah. Bukan fakta bahwa meskipun pangkalan dapat melakukannya sendiri, Anda tidak akan mengalami masalah apa pun. Ingat tentang fundamentalisme algoritmik - Anda perlu memahami cara kerja semuanya di dalam.

Saat menyiapkan sharding untuk pertama kalinya, pilih F() dengan hati-hati, pikirkan tentang permintaan, jaringan, dll. Tapi bersiaplah, Anda mungkin harus memilih 2 kali dan setidaknya sekali Anda harus mengulang semuanya.