Mengenai kehilangan data dalam kelompok besar

Terdapat tiga rutin replikasi yang biasa digunakan: Pangkalan data memastikan setiap data disalin ke tiga cakera bebas pada tiga komputer berbeza. Sebabnya adalah mudah: cakera hanya gagal pada masa tertentu Jika satu cakera mati, anda mempunyai masa untuk menggantikannya, dan anda masih boleh mengambil satu daripada dua salinan anda yang lain untuk memulihkan data dan menulisnya ke cakera baharu . Kebarangkalian bahawa cakera kedua akan mati sebelum anda memulihkannya adalah sangat rendah sehingga kebarangkalian kedua-dua cakera anda mati pada masa yang sama adalah tipis seperti asteroid yang menghempap ​​bumi.

Kami juga telah mengira khas bahawa kemungkinan kegagalan satu cakera adalah hampir 0.1% (mungkin kasar), kemungkinan dua cakera gagal adalah hampir 10 hingga kuasa 6, dan kemungkinan tiga cakera gagal pada masa yang sama Seks adalah kira-kira 10 kepada kuasa -9, iaitu satu bahagian dalam satu bilion. Pengiraan ini menunjukkan bahawa kegagalan satu cakera adalah bebas daripada kegagalan cakera lain - ini tidak begitu tepat, contohnya, jika cakera anda semua dihasilkan dari barisan pengeluaran yang sama, maka semuanya mungkin buruk - Tetapi itu sudah cukup baik untuk idea kami.

Setakat ini ini kelihatan munasabah, tetapi malangnya ini tidak benar untuk banyak sistem storan data. Dalam blog ini saya akan menunjukkan kepada anda mengapa.

Jika kluster pangkalan data anda hanya mengandungi tiga mesin, kemungkinan semua mesin ranap pada masa yang sama adalah terlalu rendah (tidak termasuk ralat berkaitan, seperti pusat data dimusnahkan). Walau bagaimanapun, sebaik sahaja anda menggunakan kluster yang lebih besar, masalah berubah dengan sewajarnya. Lebih banyak nod dan cakera yang anda gunakan dalam kelompok, lebih besar kemungkinan anda kehilangan data.

Ini berdasarkan pengiraan Anda mungkin berfikir "Benarkah? Saya telah menyalin data ke tiga cakera. Bagaimanakah kebarangkalian kegagalan menjadi lebih tinggi apabila kluster meningkat? Bagaimana pula dengan kapasiti kluster? "Tetapi saya mengira kemungkinan dan menunjukkan. anda mengapa dengan ikon berikut:

Jelas sekali, ini bukan kemungkinan satu nod gagal - ini adalah kemungkinan kehilangan ketiga-tiga salinan data secara kekal, jadi memulihkan data daripada sandaran hanyalah pendekatan konservatif. Lebih besar kluster anda, lebih besar kemungkinan anda kehilangan data. Ini adalah sesuatu yang anda mungkin tidak fikirkan apabila anda berfikir tentang membayar untuk meniru data anda.

Paksi-Y graf agak sewenang-wenang dan bergantung pada banyak imaginasi, tetapi arah garisan adalah luar biasa. Berdasarkan andaian sebelumnya, kebarangkalian nod gagal pada satu ketika adalah 0.1%. Walau bagaimanapun, angka menunjukkan bahawa dalam kelompok dengan 8,000 nod, kebarangkalian kehilangan tiga salinan data secara kekal adalah lebih kurang 0.2%. Ya betul, risiko kehilangan ketiga-tiga salinan adalah dua kali ganda risiko kehilangan satu data nod. Jadi untuk apa salinan ini digunakan?

Menilai secara intuitif daripada gambar ini: Dalam kelompok dengan 8,000 nod, adalah perkara biasa bagi sesetengah nod untuk turun pada masa tertentu. Ini mungkin bukan masalah: kebarangkalian tertentu huru-hara dan penggantian nod boleh disimpulkan, dan sebahagian daripadanya ialah penyelenggaraan rutin. Walau bagaimanapun, jika anda tidak bernasib baik dan nod destinasi data nod yang anda salin tidak berfungsi, maka data anda tidak akan dapat diambil semula. Kehilangan data adalah sebahagian kecil daripada keseluruhan set data kluster, tetapi apabila anda kehilangan tiga replika, anda mungkin berfikir "Saya benar-benar tidak mahu kehilangan data ini," dan bukannya "Saya tidak menjangkakan kehilangan beberapa data secara tidak sengaja, walaupun mereka tidak terlalu besar "Mungkin bahagian data yang hilang ini adalah bahagian penting data.

Kemungkinan ketiga-tiga replika adalah nod buruk bergantung pada algoritma replikasi yang digunakan oleh sistem. Gambar rajah di atas hanya bergantung pada data yang dibahagikan kepada bilangan partition tertentu (atau serpihan), supaya setiap partition menyimpan tiga nod yang dipilih secara rawak (atau fungsi cincang pseudo-rawak). Ini adalah kes khas pencincangan yang konsisten, digunakan dalam Cassandra dan Riak (setahu saya). Saya tidak pasti bagaimana sistem lain mengedarkan replikasi berfungsi, jadi saya melihatnya daripada seseorang yang mengetahui dalaman sistem berbilang storan.

Biar saya tunjukkan kepada anda cara saya mengira graf di atas menggunakan model kebarangkalian pangkalan data yang direplikasi.

Andaikan bahawa kebarangkalian nod bebas kehilangan data ialah p=P (kehilangan nod). Saya akan mengabaikan masa dalam model ini dan melihat secara ringkas kebarangkalian kegagalan dalam tempoh masa tertentu. Sebagai contoh, kita boleh menganggap bahawa p=0.001 ialah kebarangkalian nod gagal pada hari tertentu Adalah munasabah untuk menghabiskan satu hari menggantikan nod dan membuang data yang hilang ke nod baharu. Secara ringkasnya, saya tidak mahu membezakan antara kegagalan nod dan kegagalan cakera saya hanya akan bercakap tentang kegagalan kekal.

Biarkan n ialah bilangan nod dalam kelompok. f ialah bilangan nod yang gagal (dengan mengandaikan kegagalan adalah agak bebas) dan diedarkan binomial:

Ungkapan ialah kebarangkalian kegagalan nod f Ungkapan ialah kebarangkalian untuk memastikan nod n-f tidak gagal. Ia adalah bilangan nod f yang diekstrak daripada n dengan cara yang berbeza. Disebut "n pilih f", ia ditakrifkan sebagai:

. . . . . .

Proses terbitan khusus tidak akan diterangkan secara terperinci di sini. Berdasarkan formula di atas, kita boleh memperoleh kebarangkalian kehilangan satu atau lebih partition dalam kelompok dengan n nod dan faktor replikasi (bilangan nod sandaran yang direplikasi). Jika bilangan nod yang gagal f adalah kurang daripada faktor replikasi, kita boleh pastikan tiada data yang hilang. Walau bagaimanapun, kita perlu menambah semua kemungkinan apabila f berada di antara r dan n:

Ini sedikit bertele-tele, tetapi saya rasa ia tepat. Jika anda membiarkan r=3, p=0.001, k=256n, n adalah antara 3 dan 10000, maka anda boleh mendapatkan gambar di atas. Saya menulis beberapa program ruby ​​​​untuk melaksanakan pengiraan ini.

Kami menggunakan ikatan kesatuan untuk mendapatkan tekaan yang lebih mudah:

Walaupun kegagalan satu partition tidak sepenuhnya bebas daripada partition lain, andaian ini masih terpakai. Nampaknya lebih dekat dengan keputusan percubaan: dalam perjalanan, kebarangkalian kehilangan data adalah lebih seperti garis lurus, yang berkadar dengan bilangan nod. Konjektur menunjukkan bahawa kebarangkalian berkaitan secara positif dengan nombor, dan kami menganggap bahawa setiap nod mempunyai 256 partition tetap.

Bagaimana prestasinya dalam amalan, saya tidak pasti. Tetapi saya fikir ini adalah fenomena sensitif pengiraan yang menarik. Saya pernah mendengar situasi di mana syarikat yang mempunyai kluster pangkalan data yang besar telah mengalami kehilangan data sebenar. Tetapi ia tidak begitu biasa dalam artikel dan laporan. Jika anda sedang mempelajari topik ini, anda boleh beritahu saya.

Keputusan yang dikira menunjukkan bahawa jika anda ingin mengurangkan kemungkinan kehilangan data, anda harus mengurangkan bilangan partition dan meningkatkan faktor replikasi. Menggunakan lebih banyak sandaran kos lebih tinggi, jadi ini sudah mahal apabila mempertimbangkan kelompok besar. Walau bagaimanapun, bilangan partition menunjukkan proses pengimbangan beban yang bermakna. Cassandra pada asalnya mempunyai satu partition setiap nod, tetapi kemudian ia menjadi 256 partition setiap nod untuk mengatasi pengagihan beban yang lebih baik dan pengimbangan sekunder yang cekap.

Anda perlu mencari kluster yang agak besar sebelum ini benar-benar boleh berfungsi, tetapi kluster ribuan tahap digunakan oleh banyak syarikat besar. Jadi saya berminat untuk mendengar daripada orang yang berpengalaman dalam bidang ini. Jika kebarangkalian kehilangan data kekal untuk 10,000 nod dikawal dalam 0.25% setiap hari, bermakna 60% daripada data akan hilang dalam setahun.

Sebagai pereka sistem data teragih, apakah pendapat anda selepas membaca artikel ini? Jika apa yang saya katakan adalah betul, lebih banyak pertimbangan harus diberikan dalam mereka bentuk skema replikasi. Saya harap artikel ini dapat meningkatkan kesedaran anda tentang realiti. Kerana 3 nod replikasi sebenarnya tidak begitu selamat.

Atas ialah kandungan terperinci Mengenai kehilangan data dalam kelompok besar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!