Követelmények: Nemrégiben láttam egy videót a Redis Bloom algoritmusról a Bilibilin, amely megoldja a gyorsítótár behatolásának problémáját, egyszerűen fogalmazva: logikus ítélőképesség rétegét adjuk hozzá az adatbázis megkeresése előtt, hogy megállapítsuk, létezik-e az adat, és ha igen, akkor hozzáférhetsz az adatbázishoz. Például, ha egy weboldal hírrendszer, a cikkek URL-jeit önnöveglenő elsődleges kulcsazonosítók (URL formátum example:/news-1.html) generálják, így a weboldal csak tízezrek cikkeit és gyorsítótárakat tartalmazhat.
Eredetileg:
Hírforrás kérése -> Megállapítsuk, létezik-e a gyorsítótár -> Jelenlét -> A gyorsítótár adatot ad vissza.
Hírforrások kérése -> Megállapítsák, hogy létezik-e a gyorsítótár -> nem létezik -> Lekérdezés az adatbázisból -> Present -> Cache és visszaküldés adatok.
Hírforrás kérése -> Megállapítsák, hogy létezik-e a gyorsítótár -> nem létezik -> Lekérdezés az adatbázisból -> Nem létezik -> 404 hibát ad vissza.
Azonnal:
Kérj hírforrást -> Bloom algoritmusát -> Létezés -> Kövesd az eredeti logikát.
Hírforrás kérése -> Bloom algoritmusa -> nem létezik -> közvetlenül 404-es hibát ad.
BloomFilter
A BloomFilter algoritmus egy nagy adat ütemezési algoritmus. Egy nagy adatmennyiségű halmazban pontosan meghatározható, hogy egy objektum nincs a halmazban; Lehetséges egy tárgyat megítélni egy halmazban, és kevés helyet foglal el. őtNem alkalmas olyan helyzetekhez, ahol nagy pontosságot és nulla hibát igényelnek。 A tér hatékony felhasználása a részleges pontosság feláldásával érhető el.
Bloom algoritmusa egy olyan módszer, amely a következőképpen alapulÁldozz fel egy bizonyos pontosságot egy alacsony memóriafogyasztású szűrő algoritmusért cserébe, amely képes végrehajtani a nagy mennyiségű adat szűrését, deduplikálását és egyéb műveleteit.
A Bloom algoritmus csupán egy absztrakt fogalom, és sokféleképpen megvalósítható, és a BitMap használata a Redis esetében a cikkben egyszerű megvalósítás.
Utalás:A hiperlink bejelentkezés látható.
BitMap bevezetése
A BitMap egy bitmap, amely valójában egy bájttömb, bináris formában képviselve.Csak két szám van, 0 és 1, bitmap azt jelenti, hogy minden bináris bitet felhasználunk az elemhez tartozó érték tárolására vagy jelölésére. Általában arra használják, hogy meghatározzák, létezik-e egy adott adat, mivel az bitekben van tárolva, így maga a Bitmap jelentősen megtakarítja a tárolóhelyet.
Ahogy az alábbi ábrán látható, a láncszál bináris formában van tárolva a számítógépben.
BitMap adattípusok Redisben
A Redis által biztosított adattípus BitMap, és minden bit két állapotnak felel meg: 0 és 1. Bár a belső tároló továbbra is String típusú, a Redis néhány utasítást ad a BitMap közvetlen manipulálásához, amely egy bittömbként is értelmezhető, és a tömb indexe az offset.
Előnyei a következők:Alacsony memória költség és magas hatékonyságÉs a művelet egyszerű.
Térmegtakarítás: Egy bit az elem értékének vagy állapotának ábrázolására szolgál, ahol a kulcs a megfelelő elem értéke. Valójában 8 bit akár bájtot is alkothat, így helytakarékos.
Magas hatékonyság: A setbit és getbit időbeli összetettsége O(1), és más bitek hatékonysága is magas.
Íme egy példa a halmazgyűjtemény és a BitMap tárolás használatára:
| adattípus | Minden felhasználói azonosító helyet foglal el | A tárolandó felhasználók száma | Minden elfoglalja az emlékezetet | | beállít | A 32 bit 4 bájt (feltételezve, hogy a userid egész számokat használ, sok weboldal valójában hosszú egész számokat használ) | 50,000,000 | 32 bit * 50 000 000 = 200 MB | | Bitkép | 1 bit | 100,000,000 | 1 bit * 100,000,000 = 12,5 MB |
Az idő kicsit elnyúlik
| | Egy napon | Egy hónap | Egy év | | beállít | 200 m | 6G | 72G | | Bitkép | 12,5M | 375M | 4.5G |
Számítás után kiderült, hogy az idő teltével a rögzített adatok mennyisége nőtt, a kontraszt egyre nyilvánvalóbbá vált, és a BitMap kevesebb helyet foglalt el, mint amennyit beállított.
A Redis a következő utasításokat adja a BitMap működtetéséhez:
Parancsnoki dokumentáció:A hiperlink bejelentkezés látható.
Most, hogy röviden megértitek az algoritmust, valamint a Redis bitmap jellemzőit és szintaxisát, használjuk a redis segítségével egy egyszerű műveletet.
SETBIT szintaxis:SETBIT kulcs eltérítési érték
Állítsuk be az id:9, 10, 156 cikket 1-re, és a parancs a következő:
GETBIT szintaxis: GETBIT billentyű eltolása
Az id: 10 vagy 11 létezésének meghatározásához a parancs a következő:
A .NET/C# manipulálja a Redis BitMap típusát
Több BitMap parancsról is megismertünk a redisben, és hogyan lehet programozott módon kezelni őket. Hozz létre egy új .NET 3.1 konzolprojektet, hivatkozz a StackExchange.Redis csomagra, és használd a következő parancsot:
A forráskód a következő:
Számos más bitmap alkalmazási forgatókönyv létezik a Redishez, a következőkép:
- Egyszerű Bloom-szűrőként is használható annak megállapítására, hogy a felhasználó végrehajtott-e bizonyos műveleteket.
- A felhasználói napi aktivitás, havi aktivitás és megtartási arány statisztikákja
- Ismerd meg a felhasználói indítások számát
- Felhasználói online jelenlét és emberi statisztikák
(Vége)
|
Közzétéve 2023. 01. 02. 17:37:01
|
|
|
|
Háziúr|
Közzétéve 2023. 01. 02. 17:41:56
|
Közzétéve 2023. 01. 02. 20:42:47
|
