Úvod do datových struktur Redis:sady

Redis (Remote Dictionary Server) je nesmírně populární úložiště klíč-hodnota v paměti, které také poskytuje volitelnou odolnost, dělení, replikaci a řadu dalších funkcí. V současné době jde o nejoblíbenější databázi klíč–hodnota a je známá svou jednoduchostí, malou paměťovou náročností a nízkou křivkou učení. Redis je také označován jako server datových struktur a podporuje atomické operace s datovými strukturami, jako jsou hash, seznamy, sady, setříděné sady, bitmapy a hyperloglogy. V tomto příspěvku se podíváme na nastavený datový typ poskytovaný společností Redis spolu s jeho použitím a případy použití v reálném životě.

Sady Redis

Sady Redis jsou neuspořádané kolekce řetězců (řetězec je základní hodnota Redis, která může obsahovat téměř cokoli), které umožňují neustálé přidávání, odebírání a kontroly členství. Redis také podporuje přiměřeně rychlé operace sjednocení, průniku a odečítání mezi sadami. Podle očekávání neumožňuje opakované hodnoty.

Zde je několik příkladů sad Redis v akci z redis-cli . Zde je souhrn klíčových reprezentací v příkladu níže:

• users:all představuje množinu všech uživatelů registrovaných na webové stránce.
• users:actv představuje aktivní uživatele.
• users:inactv představuje neaktivní uživatele (uživatele, kteří web nějakou dobu nenavštívili).

# sadd key member [member ...] : add members to a set
127.0.0.1:6379> sadd users:all 11 12 13 14 15 Rocket Pocket Socket
(integer) 8
127.0.0.1:6379> type users:all
set
# smembers key: get all members of a set
127.0.0.1:6379> smembers users:all
1) "Pocket"
2) "11"
3) "Socket"
4) "13"
5) "14"
6) "Rocket"
7) "12"
8) "15"
# sismember key member: is the given value a member of the set?
127.0.0.1:6379> sismember users:all 00
(integer) 0
127.0.0.1:6379> sismember users:all 11
(integer) 1
127.0.0.1:6379> sismember users:all Socket
(integer) 1
127.0.0.1:6379> sadd users:inactv 11 12 13
(integer) 3
# sinter key [key ...]: Intersection of multiple sets
# Similar: sinterstore stores the result of intersection of sets to a new set
127.0.0.1:6379> sinter users:all users:inactv
1) "11"
2) "12"
3) "13"
# scard key: cardinality of the set i.e. number of members present in the set
127.0.0.1:6379> scard users:all
(integer) 8
# sdiff key [key ...] : Subtract multiple sets
# Similar: sdiffstore: subtract and store result in a new destination set
127.0.0.1:6379> sdiff users:all
1) "Pocket"
2) "11"
3) "Socket"
4) "13"
5) "14"
6) "12"
7) "Rocket"
8) "15"
127.0.0.1:6379> sdiff users:all users:inactv
1) "14"
2) "Pocket"
3) "Rocket"
4) "Socket"
5) "15"
# sdiffstore destination key [key ...]
127.0.0.1:6379> sdiffstore users:actv users:all users:inactv
(integer) 5
127.0.0.1:6379> smembers users:actv
1) "14"
2) "Pocket"
3) "Rocket"
4) "Socket"
5) "15"
127.0.0.1:6379> sdiff users:all users:actv users:inactv
(empty list or set)
# smove source destination member: move a member from source set to destination.
127.0.0.1:6379> smove users:inactv users:actv 11
(integer) 1
127.0.0.1:6379> smembers users:actv
1) "Pocket"
2) "11"
3) "Socket"
4) "14"
5) "Rocket"
6) "15"

Další důležité příkazy sady zahrnují:

• SUNION – sjednocení sady
• SPOP – náhodné odebrání prvku
• SREM – odeberte jeden nebo více prvků

Úplný seznam sad souvisejících příkazů Redis naleznete zde.

Redis Internals

Redis interně ukládá sady jako slovníky. Slovníky v Redis jsou implementovány jako hashovací tabulky, které používají hashovací funkci MurmurHash2 a rostou pomocí přírůstkové změny velikosti. Hašovací kolize jsou řešeny řetězením. Množiny mají speciální kódování pro malé množiny, když jsou všichni členové množiny v radixu 10 v rozsahu # 64bitových celých čísel se znaménkem nazývaných IntSets. Toto je v podstatě seřazené pole celých čísel. Vyhledávání v poli se provádí pomocí binárního vyhledávání. Je zřejmé, že tato implementace je účinná pro velmi malé soubory. Velikost, do které se toto kódování používá, se řídí podle set-max-intset-entries konfigurační parametr. Výchozí hodnota je 512. Dobrý popis interních datových struktur používaných Redisem naleznete zde.

Aplikace Redis

Zde je malý seznam několika možných aplikací Redis Set:

• Jako sadu jej lze použít ke sledování jedinečných položek:
  • Všechny jedinečné adresy IP navštěvující vaše stránky.
  • Všechny jedinečné instance úloh aktuálně v daném stavu atd.
• Jako množinu jej lze použít k označení „patří do“ nebo podobného vztahu:
  • Všechny SKU patřící do určité kategorie.
  • Všechny objekty s konkrétní značkou atd.
• Množiny lze použít pouze ke kombinování vztahů, tj. sjednocení/průnik/odčítání množin:
  • Všechny SKU, které patří do kategorie triček, ale ne do podkategorie polo s výstřihem.

Vezměme si příklad ze skutečného života a prozkoumáme další související případy použití.

Vizuální profilovač pro váš obchod s e-knihami

Řekněme, že jste vlastníkem velkého online knihkupectví, které nabízí miliony titulů. Vaše primární databáze je MongoDB a funguje docela dobře pro většinu vašich případů použití se správným použitím indexování, shardingu atd. Zde je částečné schéma DB dokumentu pro knihy sbírky:

...
sku: SKU,
pid: Product ID,
title: String,
auth: String,
pub: String,
isbn: ISBN,
edition: Int,
price: Float,
rating: Float,
cats: [String, String ...],
tags: [String, String ...],
...

Transakce také zaznamenáváte do kolekce nazvané txns který může vypadat takto:

txnid: TxnID,
cid: CustomerID,
amnt: Float,
curr: Currency,
sku: [sku1, sku2, ...],
time: TimeStamp,
...

A sbírka zobrazení nazvaná views:

time: TimeStamp, # daily aggregated
cid: CustomerID,
sku: [sku1, sku2, ...],
...

Toto je samozřejmě velmi zjednodušený příklad, který obsahuje široké předpoklady. Naším záměrem je ukázat příklad Redis v (téměř) reálném světě.

Dobře, takže nyní jako vedoucí prodejny chcete nástroj Visual Profiler k analýze vztahů a chování zákazníků napříč různými kategoriemi. Například:

• Jaká je nejoblíbenější kategorie?
• Dívají se lidé, kteří si prohlížejí nebo kupují sci-fi, také na literaturu faktu?

Chcete to udělat v reálném čase, tj. uživatelské uživatelské rozhraní profilovače zaškrtne políčka, tlačítka, která vám umožní měnit parametry a prohlížet výsledky (téměř) okamžitě.

Provádění takových operací na MongoDB bude vyžadovat provádění poměrně složitých dotazů pro spojení různých kategorií, značek a dalších dat, která by vás mohla zajímat. S pracovní sadou, která se nevejde do paměti, by to nebyly nejrychlejší operace. Například:

• Nalezení všech dnes prodaných knih, které byly fikcí, ale ne sci-fi, bude vyžadovat dotaz na txn sběr dnešních transakcí. Poté opakujte SKU pro shromáždění jejich kategorií a poté proveďte operace $in/$nin.

Podívejme se, jak by se to řešilo zapojením Redis do mixu. Na konci každého dne mohou přes tyto kolekce MongoDB běžet denní naplánované úlohy a vytvářet sady Redis. Druh sad, které chcete vytvořit, bude záviset na druhu filtrů, které chcete na svém rozhraní podporovat. Řekněme například, že chcete podporovat dotazy související s kategoriemi, budeme chtít vytvořit sady jako:

cat:type:catID
cat:sku:fiction
cat:sku:nonfiction
cat:sku:scfiction
cat:sku:history
cat:sku:milhistory
cat:sku:military
...
cat:cid:fiction
cat:cid:nonfiction
cat:cid:scfiction
cat:cid:history
cat:cid:milhistory
cat:cid:military
...

Sady cat:sku:* budou obsahovat SKU knih prodaných/zobrazených dnes v dané kategorii. Podobně cat:cid:* bude obsahovat CID zákazníků, kteří koupili/prodali knihy v dané kategorii. Příklady dotazů, na které můžeme odpovědět pomocí těchto sad, jsou:

• Zákazníci (nebo počet zákazníků), kteří si dnes prohlédli/zakoupili beletrii (jedna kategorie):smembers cat:cid:fiction
• Zákazníci, kteří si dnes prohlédli/zakoupili Historii, ale ne Vojenskou historii:sdiff cat:cid:history cat:cid:milhistory
• (Počet) dnes prodaných knih, které byly sci-fi a vojenské, tj. vojenské sci-fi:sinter cat:sku:scfiction cat:sku:military
• Libovolný počet takových operací sjednocení, průniku a rozdílu, na kterých vám záleží.

To samo o sobě nám poskytuje velmi výkonné možnosti dotazování. Přidejme další sady! Řekněme, že vytváříme další sady na základě hodnocení knih. Například:

rat:sku:5str: Set of books with ratings > 4.5
rat:sku:4str: Set of books with ratings > 3.5 && <= 4.5
rat:sku:3str: ...
rat:sku:2str: ...
...
rat:cid:5str: Set of customer who bought books with ratings as mentioned above.
rat:cid:4str: ...
..

Vybaveni těmito sadami jste nyní schopni rychle zjistit věci jako:

• 4hvězdičkové a více hodnocené beletristické knihy zakoupené dnes:  sunionstore rat:sku:4strabv rat:sku:5str rat:sku:5str/sinter rat:sku:4strabv cat :sku:fiction
• Zákazník, který si v historii koupil 3hvězdičkové a vyšší knihy:sunionstore rat:cid:5strabv rat:cid:3str rat:cid:5str rat:cid:5str/sinter cat:cid:history rat:cid:5strabv

Nyní řekněme, že chcete poslat slevový kupón všem svým zákazníkům, kteří si dnes zakoupili knihu astrologie s hodnocením 2 nebo nižším (jako omluvu za špatnou zkušenost že tu knihu musím číst!). Tento seznam CustomerID můžete exportovat a pošlete jej do vaší e-mailové aplikace. Podobně můžete vytvořit sady pro další věci, které byste mohli chtít vystavit jako filtry ve svém vizuálním profilovači, jako jsou značky, cenové rozpětí atd.

Výhody používání sad Redis jsou zde zřejmé. Úložiště v paměti povede k opravdu rychlému přístupu, takže frontend bude vypadat svižně. Operace sady Redis jsou navíc buď s konstantním časem, nebo lineární.

Závěr

V tomto příspěvku jsme s příklady představili jednu z nejužitečnějších datových struktur Redis:Sady. Zde jsou některé z našich dalších příspěvků ze série datových struktur Redis:

• Redis hashe
• Bitmapy Redis
• Sady Redis
• Řaděné sady Redis