Masalah Avalanche dan Penembusan dalam Cache dan Penyelesaian Java

Cache avalanche

Cache avalanche bermakna sejumlah besar cache dalam Redis akan tamat tempoh pada masa yang sama Jika sejumlah besar permintaan berlaku dalam tempoh ini, permintaan akan terus mengakses pangkalan data . , yang mungkin mengatasi pangkalan data.

Cache avalanche secara amnya menerangkan data yang tiada dalam cache tetapi berada dalam pangkalan data dan permintaan pergi terus ke pangkalan data kerana masa tamat.

Penyelesaian

Terdapat banyak cara untuk menyelesaikan runtuhan cache:

• 1. Dengan cara ini, tidak akan ada banyak permintaan yang mengakses pangkalan data pada masa yang sama.

• 2. Jangan tetapkan masa tamat tempohnya. Contoh biasa ialah apabila memulakan data pemanasan Apabila menyimpan data dalam cache, masa rawak boleh digunakan untuk memastikan bahawa sejumlah besar cache tidak luput pada masa yang sama.

• 3 Jika ingatan membenarkan, cache boleh ditetapkan untuk tidak tamat tempoh.

Pecahan cache

Pecahan cache sangat serupa dengan runtuhan cache Perbezaannya ialah pecahan cache secara amnya merujuk kepada kegagalan cache tunggal, dan terdapat sejumlah besar kegagalan cache pada masa yang sama Permintaan serentak perlu mengakses kunci ini, menyebabkan tekanan pada pangkalan data.

Penyelesaian

Kaedah menyelesaikan pecahan cache sangat serupa dengan kaedah menyelesaikan runtuhan cache:

• 1 capaian cache. Dengan cara ini, cache akan ditulis semula selepas permintaan pertama mencapai pangkalan data, dan permintaan seterusnya boleh membaca cache secara langsung.

• 2 Jika ingatan membenarkan, cache boleh ditetapkan untuk tidak tamat tempoh.

Penembusan Cache

Perbezaan penting antara penembusan cache dan dua fenomena di atas ialah data yang diakses pada masa ini tidak wujud dalam pangkalan data, jadi sejak pangkalan data tidak wujud, jadi ia pasti tidak akan wujud dalam cache Jika konkurensi terlalu besar, data akan terus tiba di pangkalan data, menyebabkan tekanan besar pada pangkalan data.

Penyelesaian

Untuk masalah penembusan cache, penguncian tidak memberi kesan yang baik kerana kunci itu sendiri tidak wujud, jadi walaupun bilangan capaian benang dikawal, permintaan tetap akan terus tiba di pangkalan data.

Untuk menyelesaikan masalah penembusan cache, penyelesaian berikut secara amnya boleh digunakan bersama:

• 1 Lapisan antara muka melakukan pengesahan dan mengembalikan kunci haram secara langsung jika ditemui. Sebagai contoh, jika pangkalan data menggunakan id penambahan automatik, maka jika id bukan integer atau id negatif datang, ia boleh dikembalikan secara langsung Atau jika uuid 32-bit digunakan, maka jika panjang id tidak sama dengan 32 bit, ia boleh dikembalikan terus.

• 2. Cache data yang tidak wujud Anda boleh terus cache nilai tidak sah kosong atau lain-lain. Dengan penyelesaian ini, adalah lebih baik untuk menetapkan masa tamat tempoh yang singkat untuk kunci, jika tidak, sejumlah besar kunci yang tidak wujud akan disimpan dalam Redis, yang juga akan menduduki banyak memori.

Penapis Bloom

Mengenai penyelesaian penembusan cache di atas, mari kita fikirkan: jika kunci boleh memintas Pengesahan kaedah pertama, dan pada masa ini sejumlah besar kunci yang tidak wujud diakses (seperti 100 juta atau 1 bilion), kemudian kesemuanya disimpan dalam cache, yang akan menduduki ruang yang sangat besar, membazirkan banyak memori pelayan, dan membawa kepada memori yang tidak mencukupi.

Jadi adakah penyelesaian yang lebih baik? Ini adalah penapis Bloom yang akan kami perkenalkan seterusnya Penapis Bloom boleh menyelesaikan masalah terlalu banyak nilai utama ke tahap yang terbaik.

Apakah itu penapis Bloom

Kebanyakan orang mungkin tahu bahawa terdapat soalan temu bual sedemikian: Bagaimana untuk menentukan dengan cepat sama ada unsur wujud dalam jumlah besar 1 bilion data bercelaru?

Untuk menyelesaikan masalah ini, anda perlu menggunakan penapis Bloom, jika tidak, memori kebanyakan pelayan tidak dapat menyimpan jumlah data yang begitu besar.

Bloom Filter telah dicadangkan oleh Bloom pada tahun 1970. Ia sebenarnya vektor binari panjang (bitmap) dan satu siri fungsi pemetaan rawak (fungsi cincang).

Penapis Bloom boleh digunakan untuk mendapatkan semula sama ada elemen berada dalam koleksi. Kelebihannya ialah kecekapan ruang dan masa pertanyaan jauh lebih baik daripada algoritma biasa. Kelemahannya ialah ia mempunyai kadar salah pengiktirafan tertentu dan sukar untuk dipadamkan.

Bitmap

Salah satu struktur data dalam Redis ialah bitmap Pelaksanaan penting penapis Bloom ialah pelaksanaan bitmap, iaitu tatasusunan bit, dan dalam tatasusunan ini Setiap kedudukan dalam hanya mempunyai dua keadaan: 0 dan 1. Setiap kedudukan hanya menduduki 1 bait, di mana 0 bermakna tiada unsur wujud dan 1 bermakna terdapat unsur. Rajah di bawah ialah contoh mudah penapis Bloom (nilai utama boleh ditentukan dengan pencincangan dan operasi bit di mana ia sepatutnya jatuh):

Perlanggaran Hash

Kami mendapati di atas bahawa kesepian dan serigala jatuh dalam kedudukan yang sama Fenomena nilai kunci yang berbeza ini mendapat nilai yang sama selepas pencincangan dipanggil perlanggaran cincang. Selepas perlanggaran cincang berlaku dan kemudian operasi bit dilakukan, ia pasti akan berakhir di kedudukan yang sama.

Jika terlalu banyak perlanggaran cincang berlaku, ia akan menjejaskan ketepatan penghakiman, jadi untuk mengurangkan perlanggaran cincang, kami biasanya mempertimbangkan dua faktor berikut:

• 1. Meningkatkan saiz tatasusunan bitmap (semakin besar tatasusunan peta bit, semakin besar memori yang diduduki).

• 2. Menambah bilangan fungsi cincang (nilai kunci yang sama adalah sama selepas satu fungsi, kemudian selepas pengiraan dua atau lebih fungsi cincang, keputusan yang sama akan diperolehi Kebarangkalian akan secara semula jadi dikurangkan).

Kita perlu mempertimbangkan dua kaedah di atas secara menyeluruh: contohnya, meningkatkan tatasusunan bit akan menggunakan lebih banyak ruang, dan lebih banyak pengiraan cincang juga akan menggunakan CPU dan menjejaskan impak yang terakhir masa pengiraan, jadi berapa besar tatasusunan bit, dan berapa kali fungsi cincang perlu dikira memerlukan analisis khusus bagi situasi tertentu.

Dua ciri utama penapis Bloom

Berikut ialah penapis Bloom yang diperolehi oleh dua fungsi cincang Kita boleh melihatnya dengan mudah daripada rajah di bawah Jika Redis kami tidak wujud sama sekali dua kedudukan yang diperoleh oleh Redis selepas dua fungsi cincang sudah menjadi 1 (satu diperolehi oleh serigala melalui f2, dan satu lagi diperolehi oleh Nosql melalui f1).

Jadi melalui fenomena di atas, kita boleh simpulkan dari perspektif penapis Bloom bahawa penapis Bloom mempunyai dua ciri utama:

• 1. Jika penapis Bloom menentukan bahawa unsur wujud, maka unsur ini mungkin wujud.

• 2 Jika penapis Bloom menentukan bahawa unsur tidak wujud, maka elemen ini mestilah tidak wujud.

Dari perspektif elemen, kita juga boleh melukis dua ciri utama:

• 1 Jika elemen itu benar-benar wujud, maka penapis Bloom mesti Akan menilai kewujudan.

• 2 Jika unsur itu tidak wujud, penapis Bloom boleh menentukan ia wujud.

PS: Perlu diingatkan bahawa jika fungsi hash dilalui N kali, kedudukan N perlu 1 untuk menentukan kewujudan selagi salah satu daripadanya adalah 0, ia boleh ditentukan Unsur tersebut tidak wujud dalam penapis mekar.

fpp

Kerana sentiasa terdapat kadar positif palsu dalam penapis Bloom, kerana perlanggaran cincang tidak dapat dielakkan 100%. Penapis Bloom memanggil kebarangkalian positif palsu ini, iaitu: Kebarangkalian Positif Palsu, atau singkatannya fpp.

Apabila menggunakan penapis Bloom dalam amalan, anda boleh menentukan sendiri fpp, dan kemudian anda boleh mengira berapa banyak fungsi cincang dan berapa besar ruang tatasusunan sedikit diperlukan berdasarkan teori penapis Bloom. Perlu diingatkan bahawa fpp ini tidak boleh ditakrifkan sebagai 100%, kerana tiada jaminan 100% bahawa perlanggaran hash tidak akan berlaku.

Atas ialah kandungan terperinci Masalah Avalanche dan Penembusan dalam Cache dan Penyelesaian Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!