Gereksinimler: Son zamanlarda, Bilibili üzerinde önbellek penetrasyonu sorununu çözmek için kullanılan Redis Bloom algoritmasının videosunu izledim; basitçe söylemek gerekirse, veritabanına erişmeden önce mantıksal bir değerlendirme katmanı ekleyin ve varsa veritabanına erişin. Örneğin, bir web sitesi bir haber sistemi ise, makalelerin URL'leri kendi kendine artan birincil anahtar kimlikleriyle (URL formatı example:/news-1.html) oluşturulur; web sitesi yalnızca on binlerce makale ve önbelleğe sahip olabilir.
Aslen:
Haber kaynağı talep et -> Önbelleğin var olup olmadığını belirleyin -> Varlık -> Önbellek veri döndürür.
Haber kaynakları talep et -> Önbelleğin var olup olmadığını belirleyin -> yok -> veritabanından sorgu -> Mevcut -> Önbellek ve veriyi geri döndür.
Haber kaynağı talep et -> Önbelleğin var olup olmadığını belirleyin -> yok -> veritabanından sorgu -> Yok -> 404 hatası döndürür.
Hemen şimdi:
Haber kaynağı talep edin -> Bloom'un algoritması -> Varoluş -> Orijinal mantığı takip edin.
Haber kaynağı iste -> Bloom'un algoritması -> mevcut değil -> doğrudan 404 hatası döndürüyor.
BloomFilter
BloomFilter algoritması, büyük veri zamanlama algoritmasıdır. Büyük miktarda veriye sahip bir kümede, bir nesnenin kümede olmadığı doğru şekilde belirlenebilir; Bir kümedeki bir nesneyi yargılamak ve az yer kaplamak mümkündür. oYüksek hassasiyet ve sıfır hata gerektiren durumlar için uygun değildir。 Uzayın verimli kullanımı, kısmi doğruluktan ödün vererek sağlanır.
Bloom'un algoritması, şu noktalara dayanan bir yöntemdirDüşük bellek tüketimine sahip bir filtreleme algoritması karşılığında belirli bir doğruluktan feda edin, bu da büyük miktarda verinin filtrelenmesi, deduplication ve diğer işlemlerini gerçekleştirebilir.
Bloom algoritması sadece soyut bir kavramdır ve birçok şekilde uygulanabilir; makalede Redis'te BitMap'in kullanımı ise sadece basit bir uygulamadır.
Referans:Bağlantı girişi görünür.
BitMap tanıtımı
BitMap, aslında bir bayt dizisi olan bir bitmap'tir ve ikili olarak temsil edilir.Sadece iki sayı vardır, 0 ve 1, bitmap, her ikili bitin bir elemana karşılık gelen değeri depolamak veya işaretlemek için kullanılmasıdır. Genellikle belirli bir verinin var olup olmadığını belirlemek için kullanılır, çünkü bit olarak depolanır, bu yüzden Bitmap kendisi depolama alanını büyük ölçüde tasarruf eder.
Aşağıdaki şekilde gösterildiği gibi, dizi bilgisayarda ikili formda saklanır.
Redis'te BitMap veri türleri
Redis tarafından sağlanan veri tipi BitMap'tir ve her bit iki duruma karşılık gelir: 0 ve 1. Dahili depolama hâlâ String tipinde olsa da, Redis BitMap'in doğrudan manipüle edilmesi için bazı talimatlar sunar; bu bit dizisi olarak düşünülebilir ve dizinin alt indeksi ofsettir.
Avantajları şunlardır:Düşük bellek yükü ve yüksek verimlilikVe işlem basit.
Alan tasarrufu: Bit, bir elemanın değerini veya durumunu temsil etmek için kullanılır; burada anahtar, karşılık gelen elemanın değeridir. Aslında, 8 bit bir bayt oluşturabilir, bu yüzden alan tasarrufu sağlar.
Yüksek verimlilik: Setbit ve getbit'in zaman karmaşıklığı O(1)'dir ve diğer bitlerin verimliliği de yüksektir.
İşte küme koleksiyonu ve BitMap depolama kullanımına bir örnek:
| veri tipi | Her kullanıcı adı alan kaplıyor | Depolanması gereken kullanıcı sayısı | Hepsi hafızayı işgal eder | | ayarlamak | 32 bit 4 bayttır (userid tam sayı kullanıyorsa, birçok web sitesi aslında uzun tam sayılar kullanır) | 50,000,000 | 32 bit * 50.000.000 = 200 MB | | Bit eşlem | 1 bit | 100,000,000 | 1 bit * 100,000,000 = 12,5 MB |
Zaman biraz uzuyor.
| | Bir gün | Bir ay | Bir yıl | | ayarlamak | 200M | 6G | 72G | | Bit eşlem | 12.5M | 375M | 4.5G |
Hesaplama sonrası, zaman arttıkça kaydedilecek veri miktarının arttığı, kontrastın daha belirgin hale geldiği ve BitMap'in belirlenenden daha az yer kapladığı tespit edildi.
Redis, BitMap'in işletilmesi için aşağıdaki talimatları sağlar:
| komut | Göstermek | Mevcut versiyonlar | Zaman karmaşıklığı | | Bağlantı girişi görünür. | Anahtarda saklanan dize değeri için belirtilen ofsetteki bitleri ayarlayın veya temizleyin. | >= 2.2.0 | O(1) | | Bağlantı girişi görünür. | Anahtarda depolanan dizim değeri için, belirtilen ofsetteki bitleri elde edin. | >= 2.2.0 | O(1) | | Bağlantı girişi görünür. | Belirli bir dizedeki 1 olarak ayarlanmış bit sayısını sayar. | >= 2.6.0 | O(N) | | Bağlantı girişi görünür. | Bit haritasında ikili bitin konumunu döndürür; burada ilk değer bittir. | >= 2.8.7 | O(N) | | Bağlantı girişi görünür. | İkili bitleri tutan bir veya daha fazla dize tuşu üzerinde bit manipülasyonu. | >= 2.6.0 | O(N) | | Bağlantı girişi görünür. | BITFIELD komutu aynı anda birden fazla bit aralığında tek bir çağrıda çalışabilir. | >= 3.2.0 | O(1) |
Komuta dokümantasyonu:Bağlantı girişi görünür.
Şimdi algoritma, Bitmap özellikleri ve Redis'in sözdizimi hakkında kısa bir anlayışınız olduğuna göre, basit bir işlem için redis kullanalım.
SETBIT sözdizimi:SETBIT anahtar ofset değeri
Makale id:9, 10, 156 olarak 1 olarak ayarlanır ve komut şu şekildedir:
GETBIT sözdizimi: GETBIT anahtar ofseti
id: 10 veya 11 olup olmadığını belirlemek için komut şöyledir:
.NET/C#, Redis'in BitMap tipini manipüle eder
Redis'te birkaç BitMap komutu ve bunların programatik olarak nasıl işletileceğini öğrendik. Yeni bir .NET 3.1 konsol projesi oluşturun, StackExchange.Redis paketine başvurun ve aşağıdaki komutu kullanın:
Kaynak kodu şöyledir:
Redis için aşağıdaki gibi birçok başka bitmap uygulama senaryosu vardır:
- Kullanıcının belirli işlemleri yapıp yapmadığını belirlemek için basit bir Bloom filtresi olarak kullanılabilir.
- Kullanıcı günlük aktivite, aylık aktivite ve tutma oranı istatistikleri
- Kullanıcı başlatma sayısının istatistiklerini fark edin
- Kullanıcı çevrimiçi varlığı ve insan istatistikleri
(Son)
|
Yayınlandı 2.01.2023 17:37:01
|
|
|
|
Ev sahibi|
Yayınlandı 2.01.2023 17:41:56
|
Yayınlandı 2.01.2023 20:42:47
|
