➖ ✈️ 🤱🏼 Distribusi Data di Apache Ignite 👨🏾‍🤝‍👨🏻 🆓 👨🏿‍💼

Halo! Posting ini adalah versi yang sedikit dipersingkat dari ceramah eponim saya pada pertemuan komunitas Apache Ignite . Anda dapat menonton versi video lengkap bersama dengan pertanyaan dan jawaban di sini , dan unduh slide di sini . Dalam laporan itu, saya mencoba menunjukkan dengan contoh bagaimana data didistribusikan di Apache Ignite.

Mengapa Anda perlu mendistribusikan apa pun

Sejarah standar yang cukup dari pengembangan sistem apa pun yang membutuhkan penyimpanan dan pemrosesan data adalah pencapaian pagu tertentu. Entah ada banyak data dan mereka tidak secara fisik ditempatkan pada perangkat penyimpanan, atau beban tumbuh pada tingkat yang satu server tidak lagi dapat memproses sejumlah permintaan seperti itu. Ada banyak kasus ketika keduanya terjadi.

Sebagai aturan, mereka datang ke salah satu dari dua solusi: baik sharding penyimpanan yang ada, atau beralih ke database terdistribusi. Kedua solusi memiliki sejumlah fitur umum, yang paling jelas di antaranya adalah penggunaan lebih dari satu node untuk bekerja dengan data. Selanjutnya, banyak node yang saya sebut topologi.

Masalah distribusi data antara node topologi dapat dirumuskan sebagai seperangkat persyaratan yang harus dipenuhi oleh distribusi kami:

Diperlukan suatu algoritma yang akan memungkinkan semua node dari topologi dan aplikasi klien untuk sampai pada kesimpulan yang sama tentang node atau node mana objek tertentu (atau kunci) aktif.
Keseragaman distribusi. Semakin merata data didistribusikan di antara node, semakin banyak beban pada node ini akan didistribusikan. Di sini saya membuat asumsi bahwa node kami memiliki sumber daya yang kira-kira sama.
. , , . , , , .

Mencapai dua persyaratan pertama cukup mudah.

Pendekatan yang akrab, sering digunakan ketika menyeimbangkan beban antara server yang setara secara fungsional, membagi modulo N, di mana N adalah jumlah node dalam topologi dan kami memiliki korespondensi satu-ke-satu antara nomor node dan pengenalnya. Maka semua yang perlu kita lakukan adalah merepresentasikan kunci objek sebagai nilai numerik menggunakan fungsi hash dan mengambil sisa pembagian dengan nilai N dari nilai yang diperoleh.Diagram

gambar

menunjukkan distribusi 16 kunci lebih dari 3 node. Dapat dilihat bahwa distribusi ini seragam, dan algoritma untuk mendapatkan node untuk objek sederhana dan menjamin bahwa jika semua node dari topologi menggunakan algoritma ini, maka hasil yang sama akan diperoleh untuk kunci yang sama dan N. yang sama

Tetapi apa yang terjadi jika kita memperkenalkan simpul ke-4 ke dalam topologi?

gambar

Fungsi kami telah berubah, sekarang kami mengambil sisa divisi dengan 4, bukan oleh 3. Dan jika fungsi telah berubah, maka distribusinya telah berubah, dan sangat banyak.

Di sini, lokasi objek sebelumnya untuk versi sebelumnya dari topologi tiga node ditunjukkan dengan warna merah, dan posisi objek untuk versi baru dari topologi empat node masing-masing berwarna hijau. Ini sangat mirip dengan file diff biasa, tetapi alih-alih file kita memiliki node.

Sangat mudah untuk melihat bahwa data telah pindah tidak hanya ke node baru, tetapi juga ada pertukaran data antara node yang sudah ada dalam topologi. Itu kami mengamati lalu lintas palsu antara node dan persyaratan perubahan minimal dalam distribusi tidak terpenuhi.

Dua cara populer untuk memecahkan masalah distribusi data, dengan mempertimbangkan persyaratan yang tercantum, adalah sebagai berikut:

Hashing yang konsisten
Algoritma Bobot Acak Terbesar (HRW), juga dikenal sebagai hashing Rendezvous.

Kedua algoritma ini sangat sederhana. Deskripsi mereka di Wikipedia sesuai dengan beberapa kalimat. Meskipun sulit untuk memanggil mereka dengan jelas. Bagi mereka yang tertarik, saya sarankan membaca artikel asli Hashing konsisten dan Pohon Acak: Protokol Caching Terdistribusi untuk Menghilangkan Hot Spot di World Wide Web dan Skema Pemetaan Berbasis Nama untuk Rendezvous . Yang paling dapat dimengerti, menurut pendapat saya, gagasan algoritma hashing yang konsisten disampaikan dalam kursus Stanford ini .

Mari kita lihat algoritma ini lebih terinci.

Hashing yang Konsisten

Trik yang mendasari algoritma hashing yang konsisten adalah memetakan kedua node dan objek yang disimpan ke ruang pengidentifikasi yang sama. Ini membuat entitas, objek, dan node kami yang tampaknya berbeda dapat dibandingkan.

Untuk mendapatkan pemetaan seperti itu, kita cukup menerapkan fungsi hash yang sama untuk kunci-kunci objek dan untuk pengidentifikasi node. Hasil dari fungsi hash untuk node akan disebut token, ini akan berguna bagi kita nanti.

Kami mewakili ruang pengenal kami dalam bentuk lingkaran, mis. kami hanya berasumsi bahwa nilai pengenal maksimum segera mengikuti nilai pengenal minimum.

Sekarang, untuk menentukan di simpul mana objek itu hidup, Anda perlu mendapatkan nilai fungsi hash dari kuncinya, dan kemudian hanya bergerak searah jarum jam di sekitar lingkaran sampai kita menemukan token dari simpul di jalan. Arah gerakan tidak penting, tetapi harus diperbaiki.

Gerakan searah jarum jam imajiner secara fungsional setara dengan pencarian biner dalam array token simpul yang diurutkan.

gambar

Dalam diagram, setiap sektor dengan warna tertentu mencerminkan ruang pengenal yang bertanggung jawab atas simpul tertentu.

Jika kita menambahkan simpul baru, maka ...

gambar

... itu akan membagi salah satu sektor menjadi dua bagian dan sepenuhnya mengambil alih kunci yang sesuai.

Dalam contoh ini, simpul 3 mengambil alih bagian dari kunci simpul 1.

Seperti yang Anda lihat, pendekatan ini memberikan distribusi objek yang agak tidak merata di seluruh node, karena itu sangat tergantung pada pengidentifikasi node itu sendiri. Bagaimana pendekatan ini dapat ditingkatkan?

Anda dapat menetapkan lebih dari satu token ke node (biasanya ratusan). Ini dapat dicapai, misalnya, dengan memperkenalkan banyak fungsi hash untuk node (satu per token) atau berulang kali menerapkan fungsi hash yang sama ke token yang diperoleh pada langkah sebelumnya. Tapi kita jangan lupa tentang tabrakan. Seharusnya tidak ada dua node dengan token yang sama.

gambar

Dalam contoh ini, setiap node memiliki 4 token.

Apa lagi yang penting untuk disebutkan: jika kita ingin memastikan keamanan data jika ada simpul yang meninggalkan topologi, maka kita perlu menyimpan kunci pada beberapa node (disebut replika atau cadangan). Dalam kasus algoritma hashing yang konsisten, replika akan menjadi simpul N-1 berikut pada lingkaran, di mana N adalah faktor replikasi. Tentu saja, urutan node harus ditentukan oleh token tertentu (misalnya, oleh yang pertama), karena saat menggunakan beberapa token untuk masing-masingnya, susunan node mungkin berbeda. Perhatikan skema: tidak memiliki pola pengulangan node yang jelas.

Adapun persyaratan perubahan minimal dalam distribusi ketika mengubah topologi, itu puas karena urutan timbal balik dari node pada lingkaran tidak berubah. Itu menghapus node dari topologi tidak akan mengubah hubungan urutan antara node yang tersisa.

Hashing pertemuan

Algoritma hashing Rendezvous tampaknya bahkan lebih sederhana daripada hashing yang konsisten. Algoritma ini didasarkan pada prinsip invarian hubungan keteraturan yang sama. Tetapi alih-alih membuat node dan objek sebanding, kami hanya membuat node untuk objek tertentu yang sebanding. Itu kami menentukan hubungan urutan antara node untuk setiap objek secara independen.

Sekali lagi hashing membantu kita dengan ini. Tapi sekarang, untuk menentukan bobot simpul N untuk objek O yang diberikan, kita akan mencampur pengidentifikasi objek dengan pengidentifikasi simpul dan mengambil hash dari campuran ini. Setelah melakukan operasi ini untuk setiap node, kami mendapatkan satu set bobot yang digunakan untuk mengurutkan node.

Node yang ternyata menjadi yang pertama dan akan bertanggung jawab untuk menyimpan objek.

Karena semua node topologi menggunakan input data yang sama, hasilnya akan sama. Yang memenuhi persyaratan pertama.

gambar

Pertimbangkan sebuah contoh. Di sini kita memiliki relasi urutan antara tiga node untuk empat kunci yang berbeda. Kuning menunjukkan simpul dengan bobot tertinggi, mis. simpul yang pada akhirnya akan bertanggung jawab untuk kunci tertentu.

Tambahkan node lain ke topologi.

gambar

Saya sengaja meletakkannya di diagonal untuk memperhitungkan semua opsi yang mungkin. Di sini, simpul 3, ditunjukkan dengan warna hijau, memasuki topologi. Oleh karena itu, distribusi bobot node untuk masing-masing kunci telah berubah. Merah menunjukkan node yang telah mengubah lokasi mereka dalam daftar untuk kunci tertentu, karena bobot dari simpul-simpul ini kurang dari berat simpul yang ditambahkan. Namun, perubahan ini hanya mempengaruhi salah satu kunci, K3.

Mari kita secara tidak sengaja mengambil simpul dari topologi.

gambar

Sekali lagi, perubahan hanya mempengaruhi satu kunci, kali ini K1. Objek yang tersisa tidak terpengaruh. Alasannya, seperti dalam kasus hashing yang konsisten, adalah invarian dari hubungan urutan antara setiap pasangan node. Itu persyaratan perubahan minimum dalam distribusi terpenuhi dan tidak ada lalu lintas palsu antara node.

Distribusi untuk pertemuan terlihat cukup bagus dan tidak memerlukan trik tambahan dibandingkan dengan tanda hashing seperti yang konsisten.

Jika kita ingin mendukung replikasi, maka simpul berikutnya dalam daftar akan menjadi replika pertama untuk objek, simpul berikutnya akan menjadi replika kedua, dll.

Bagaimana hashing pertemuan digunakan di Apache Ignite

Fungsi afinitas disebut bertanggung jawab atas distribusi data di Apache Ignite (lihat antarmuka AffinityFunction ). Implementasi standarnya adalah hashing rendezvous (lihat kelas RendezvousAffinityFunction ).

Hal pertama yang perlu Anda perhatikan adalah bahwa Apache Ignite tidak memetakan objek yang disimpan secara langsung ke node topologi. Sebaliknya, konsep tambahan diperkenalkan - partisi.

Partisi adalah wadah untuk objek dan unit replikasi. Selain itu, jumlah partisi untuk cache tertentu (ini adalah analog dari tabel di database yang dikenal) diatur pada tahap konfigurasi dan tidak berubah selama siklus hidup cache.

Dengan demikian, kita dapat menampilkan objek pada partisi menggunakan pembagian modulo yang efektif, dan menggunakan hashing rendezvous untuk memetakan partisi ke node.

gambar

Karena jumlah partisi untuk cache adalah konstan, maka kita dapat menghitung distribusi partisi dengan node sekali dan cache hasilnya sampai topologi diubah.

Setiap node menghitung distribusi ini secara independen, tetapi pada semua node dengan data input yang sama distribusi ini akan identik.

Partisi dapat memiliki beberapa salinan, kami menyebutnya cadangan. Partisi primer disebut partisi primer.

Untuk distribusi kunci terbaik antara partisi dan partisi berdasarkan node, aturan berikut harus dipenuhi: jumlah partisi harus secara signifikan lebih besar dari jumlah node, pada gilirannya, jumlah kunci harus secara signifikan lebih besar daripada jumlah partisi.

Cache di Ignite dipartisi dan direplikasi.

Dalam cache yang dipartisi, jumlah cadangan diatur pada tahap pembuatan cache. Partisi - primary dan backup - didistribusikan secara merata di antara node. Cache seperti itu paling cocok untuk bekerja dengan data operasional, seperti memberikan kinerja penulisan terbaik, yang secara langsung tergantung pada jumlah cadangan. Secara umum, semakin banyak cadangan, semakin banyak node harus mengkonfirmasi catatan utama.

gambar

Dalam contoh ini, cache memiliki satu cadangan. Itu kita bisa kehilangan satu simpul dan tidak kehilangan data, karena Cadangan partisi tidak pernah disimpan pada simpul yang sama dengan partisi primer atau cadangan lainnya.

Dalam cache yang direplikasi, jumlah cadangan selalu sama dengan jumlah node topologi minus 1. Artinya, setiap node selalu berisi salinan semua partisi.

gambar

Cache seperti itu paling cocok untuk bekerja dengan data yang jarang berubah (misalnya, direktori) dan menyediakan ketersediaan terbesar, seperti kita bisa kehilangan N-1 node (dalam hal ini 3) tanpa kehilangan data. Juga dalam opsi ini, kita akan mendapatkan kinerja baca maksimum jika kita mengizinkan untuk membaca data dari partisi primer dan cadangan.

Colokasi data di Apache Ignite

Konsep penting yang perlu diingat untuk kinerja terbaik adalah kolokasi. Colocation adalah penempatan benda apa pun di tempat yang sama. Dalam kasus kami, objek adalah entitas yang disimpan dalam cache, dan tempat adalah simpul.

Jika objek didistribusikan di seluruh partisi dari fungsi afinitas yang sama, adalah logis bahwa objek dengan kunci afinitas yang sama akan jatuh ke partisi yang sama, dan karenanya, ke node yang sama. Dalam Ignite, ini disebut colocation afinitas.

Secara default, kunci afinitas adalah kunci utama suatu objek. Tapi di Ignite, Anda bisa menggunakan bidang objek apa pun lainnya sebagai kunci afinitas.

Kolokasi secara signifikan mengurangi jumlah data yang dikirim antara node untuk melakukan perhitungan atau query SQL, yang secara alami mengarah pada pengurangan waktu yang dihabiskan untuk tugas-tugas ini. Pertimbangkan konsep ini dengan contoh.

Biarkan model data kami terdiri dari dua entitas: order (Pesanan) dan posisi pesanan (OrderItem). Satu pesanan dapat sesuai dengan banyak item. Pengidentifikasi pesanan dan item baris independen, tetapi item baris memiliki kunci asing yang merujuk pada urutan yang sesuai.

Misalkan kita perlu melakukan beberapa tugas, yang untuk setiap pesanan harus melakukan perhitungan untuk posisi pesanan ini.

Secara default, kunci afinitas adalah kunci utama. Oleh karena itu, pesanan dan posisi akan didistribusikan antar node sesuai dengan kunci utama mereka, yang saya ingat, bersifat independen.

gambar

Pada diagram, pesanan diwakili oleh kuadrat, dan posisi dalam lingkaran. Warna menunjukkan bahwa barang itu milik pesanan.

Dengan distribusi data ini, tugas hipotetis kami akan dikirim ke node di mana urutan yang diinginkan berada, dan kemudian akan perlu membaca posisi dari semua node lain, atau mengirim subtugas ke node-node ini dan mendapatkan hasil perhitungan. Ini adalah interaksi jaringan yang tidak perlu yang dapat dan harus dihindari.

Bagaimana jika kita memberi tahu Ignite bahwa item pesanan harus ditempatkan pada node yang sama dengan pesanan itu sendiri, mis. mengumpulkan data?

Sebagai kunci afinitas untuk posisi tersebut, kami akan mengambil kunci asing OrderId dan bidang ini akan digunakan saat menghitung partisi tempat catatan tersebut berada. Selain itu, di dalam partisi, kita selalu dapat menemukan objek kita dengan kunci primer.

gambar

Sekarang, jika kedua cache (Order dan OrderItem) menggunakan fungsi afinitas yang sama dengan parameter yang sama, data kami akan berada di dekatnya dan kami tidak perlu berkeliling jaringan untuk item pesanan.

Konfigurasi afinitas di Apache Ignite

Dalam implementasi saat ini, objek fungsi afinitas adalah parameter konfigurasi cache.

Fungsi afinitas itu sendiri mengambil argumen berikut saat membuat:

Jumlah partisi;
Jumlah cadangan (sebenarnya, ini juga merupakan parameter konfigurasi cache);
Filter cadangan;
Tandai tidak termasuk Tetangga.

Pengaturan ini tidak dapat diubah.

Dengan jumlah partisi dan cadangan, semuanya tampak jelas. Saya akan berbicara tentang filter cadangan dan flag excludeNeighbors beberapa saat kemudian.

Saat run time, fungsi afinitas input menerima topologi cluster saat ini - pada dasarnya daftar node cluster - dan menghitung distribusi partisi dengan node sesuai dengan contoh yang saya tunjukkan ketika saya berbicara tentang algoritma hashing pertemuan.

Sedangkan untuk filter cadangan, ini adalah predikat yang memungkinkan Anda untuk melarang fungsi afinitas dari menetapkan partisi cadangan ke sebuah node yang predikatnya kembali salah.

Sebagai contoh, anggaplah bahwa node fisik kita - server - terletak di pusat data di rak yang berbeda. Biasanya, setiap rak memiliki kekuatan independen ...

gambar

... dan jika kita kehilangan rak, maka kita kehilangan datanya.

gambar

Dalam contoh ini, kami kehilangan setengah dari partisi.

Tetapi jika kita mengatur filter cadangan yang benar, maka distribusinya akan berubah sedemikian rupa ...

gambar

... bahwa jika raknya hilang, tidak akan ada kehilangan data dan mereka masih akan tersedia.

gambar

Bendera excludeNeighbors melakukan fungsi serupa, dan sebenarnya itu adalah singkatan untuk satu kasus tertentu.

Seringkali beberapa node Ignite dijalankan pada host fisik yang sama. Kasus ini sangat mirip dengan contoh dengan rak di pusat data, hanya sekarang kita berjuang kehilangan data dengan hilangnya tuan rumah, bukan rak.

gambar

Sisanya sama. Anda dapat menerapkan perilaku ini menggunakan filter cadangan. Bendera ini adalah warisan sejarah dan dapat dihapus dalam rilis utama berikutnya dari Ignite.

Tampaknya saya berbicara tentang fungsi afinitas dan distribusi data segala sesuatu yang perlu diketahui oleh pengembang menggunakan Apache Ignite.

Sebagai kesimpulan, mari kita lihat contoh distribusi 16 partisi sesuai dengan topologi 3 node. Untuk kesederhanaan dan kejelasan, kami percaya bahwa partisi tidak memiliki cadangan.

Saya hanya mengambil dan menulis sebuah tes kecil yang membawa saya pada distribusi yang sebenarnya:

gambar

Seperti yang Anda lihat, keseragaman distribusi tidak ideal. Tetapi kesalahan akan terasa lebih rendah dengan peningkatan jumlah node dan partisi. Aturan utama yang harus diperhatikan adalah jumlah partisi secara signifikan lebih besar dari jumlah node. Sekarang di Ignite jumlah default partisi untuk cache yang dipartisi adalah 1024.

Sekarang tambahkan node baru ke topologi.

gambar

Sebagian pihak pindah kepadanya. Pada saat yang sama, persyaratan perubahan minimal dalam distribusi diamati: node baru menerima bagian dari partisi, sementara node lain tidak bertukar partisi.

Kami menghapus dari topologi, simpul yang ada di dalamnya pada tahap awal:

gambar

Sekarang semua partisi yang terkait dengan simpul nol didistribusikan kembali di antara simpul-simpul topologi lainnya, tanpa melanggar persyaratan distribusi kami.

Seperti yang Anda lihat, solusi untuk masalah-masalah kompleks seringkali didasarkan pada ide-ide yang sepele, meskipun tidak sepenuhnya jelas. Solusi yang dijelaskan digunakan di sebagian besar database terdistribusi dan melakukan pekerjaan dengan baik. Tetapi keputusan ini diacak dan karena itu keseragaman distribusi jauh dari ideal. Bisakah keseragaman ditingkatkan tanpa mengorbankan kinerja dan persyaratan distribusi lainnya? Pertanyaannya tetap terbuka.