Wprowadzenie do struktur danych Redis:posortowane zestawy

Sorted Set to jedna z najbardziej zaawansowanych struktur danych w Redis. Posortowany zestaw jest zasadniczo unikalnym zbiorem uporządkowanych ciągów Redis, z którymi powiązany jest wynik liczbowy. Porządkowanie opiera się na wynikach i porządku leksykograficznym napisów (więcej o tym później). Ciągi znaków muszą być niepowtarzalne, a wyniki mogą się powtarzać.

Poza listami jest to jedyny zamówiony struktury danych w Redis i są preferowane od List, gdy ważny jest dostęp do dowolnej części listy (w przeciwieństwie do List, które zapewniają dostęp do końców listy). Średnie wstawianie, usuwanie i wyszukiwanie wielkości liter w posortowanych zestawach to O(N), gdzie N to liczba elementów w zestawie.

Sortowanie

Wyniki w posortowanym zestawie to podwójne 64-bitowe liczby zmiennoprzecinkowe z zakresu -(2^) i +(2^) włącznie. Posortowane zestawy są sortowane według ich wyniku w porządku rosnącym. Wyniki można aktualizować dla istniejących kluczy. Aby złamać remisy punktacji, ciągi w posortowanym zestawie są uporządkowane w porządku rosnącym w leksykograficznym porządku. W Redis 2.8 wdrożono nową funkcję, która wykorzystuje tę leksykograficzną kolejność:zapytania o zakres leksykograficzny. Ma to fascynujące przypadki użycia, które zobaczymy później.

Polecenia

Zbiory posortowane redis obsługują różnorodne operacje, od prostego zestawu, pobrania, liczenia elementów po złożone obliczenia zakresu leksykograficznego. Obsługiwanych jest około 25+ operacji. Przyjrzymy się podzbiorowi z nich. Zacznijmy od podstawowych:

# ZADD key [NX|XX] [CH] [INCR] score member [score member ...] Add elements into the set
# O(log(N) where N is the number of elements in the set
# [NX|XX], [CH] & [INCR] available on > 3.0.2
127.0.0.1:6379> zadd scoreboard 999 "anorak"
(integer) 1
# Analogous: use ZREM key member [member ...] to remove members from a sorted set.
# ZCARD key O(1): Cardinality of the set
127.0.0.1:6379> zcard scoreboard
(integer) 1
# Insert multi
127.0.0.1:6379> zadd scoreboard 99 "daito" 99 "shoto" 199 "aech" 299 "art3mis" 399 "parzival"
(integer) 5
# ZSCORE key member. O(1) Returns the score of member in the sorted set at key.
127.0.0.1:6379> zscore scoreboard parzival
"399"
# ZRANK key member O(log(N)) Get the rank of the member.
127.0.0.1:6379> zrank scoreboard anorak
(integer) 5
127.0.0.1:6379> zrank scoreboard shoto
(integer) 1
# ZREVRANK key member O(log(N)) Get the rank of the member with scores ordered high to low
127.0.0.1:6379> zrevrank scoreboard anorak
(integer) 0
127.0.0.1:6379> zrevrank scoreboard shoto
(integer) 4
# ZINCRBY key increment member O(log(N)) Increments the score of member in the sorted set stored at key by increment.
127.0.0.1:6379> zincrby scoreboard 100 parzival
"499"

Powyższe były jednymi z podstawowych operacji możliwych na posortowanym zestawie. Rzeczywista wartość posortowanych zestawów świeci w swoim zakresie na podstawie zapytań w zestawie. Przyjrzyjmy się im.

# ZRANGE key start stop [WITHSCORES]. O(log(N)+M) with N being the number of elements in the sorted set and M the number of elements returned.
# start and stop are inclusive zero based indexes.
127.0.0.1:6379> zrange scoreboard 0 -1 WITHSCORES
 1) "daito"
 2) "99"
 3) "shoto"
 4) "99"
 5) "aech"
 6) "199"
 7) "art3mis"
 8) "299"
 9) "parzival"
10) "499"
11) "anorak"
# 0: 1st member. -1: last member
# Analogous: ZREVRANGE key start stop [WITHSCORES]
127.0.0.1:6379> zrevrange scoreboard 0 -1 WITHSCORES
 1) "anorak"
 2) "999"
 3) "parzival"
 4) "499"
 5) "art3mis"
 6) "299"
 7) "aech"
 8) "199"
 9) "shoto"
10) "99"
11) "daito"
12) "99"
# ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]. O(log(N)+M) Returns all the elements in the sorted set at key with a score between min and max (inclusive)
# Analogous: ZREVRANGEBYSCORE key max min [WITHSCORES] [LIMIT offset count]
# 499 <= score <= +inf 127.0.0.1:6379> zrangebyscore scoreboard 499 +inf
1) "parzival"
2) "anorak"
# 499 < score <= +inf 127.0.0.1:6379> zrangebyscore scoreboard (499 +inf
1) "anorak"
# ZCOUNT key min max O(log(N)) Returns the number of elements in the sorted set at key with a score between min and max.
127.0.0.1:6379> zcount scoreboard -inf 499
(integer) 5
127.0.0.1:6379> zcount scoreboard -inf +inf
(integer) 6

Inne podobne polecenia związane z zakresem to ZREMRANGEBYRANK, ZREMRANGEBYSCORE itp.

Istnieje jeszcze inny zestaw poleceń zapytań zestawu, który został wprowadzony w Redis 2.8:polecenia zakresu leksykograficznego (*BYLEX). Szczegóły dotyczące określania interwałów dla tych poleceń są udokumentowane tutaj. Warunkiem poprawnego działania tych poleceń jest to, aby członkowie posortowanego zestawu mieli identyczny wynik. Główne polecenia do obsługi zakresów leksykograficznych to ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX i ZLEXCOUNT. Zobaczmy kilka przykładów:

127.0.0.1:6379> zadd lexscores 0 dd 0 aa 0 ccc 0 aaa 0 bb 0 d 
(integer) 6
# Once inserted, lexicographic sorting for free!
127.0.0.1:6379> zrange lexscores 0 -1
1) "aa"
2) "aaa"
3) "bb"
4) "ccc"
5) "d"
6) "dd"
# ZRANGEBYLEX key min max [LIMIT offset count]. O(log(N)+M). min max specify range. LIMIT is like limit in SQL.
# min: exclude a max: exclude c
127.0.0.1:6379> ZRANGEBYLEX lexscores (a (c
1) "aa"
2) "aaa"
3) "bb"
# min: exclude a max: include c
127.0.0.1:6379> ZRANGEBYLEX lexscores (a [c
1) "aa"
2) "aaa"
3) "bb"
# min: exclude a max: include ccc
127.0.0.1:6379> ZRANGEBYLEX lexscores (a [ccc
1) "aa"
2) "aaa"
3) "bb"
4) "ccc"
# min: exclude aa max: include cccc
127.0.0.1:6379> ZRANGEBYLEX lexscores (aa [ccc
1) "aaa"
2) "bb"
3) "ccc"
# min: exclude aa max: upto all
127.0.0.1:6379> ZRANGEBYLEX lexscores (aa +
1) "aaa"
2) "bb"
3) "ccc"
4) "d"
5) "dd"

Kolejny zestaw poleceń dla posortowanych zestawów to operacje łączenia i przecinania.

Wewnętrzne

Posortowane zestawy są zaimplementowane jako podwójna struktura danych:jest to połączenie zarówno listy skrótów, jak i listy pomijania. Część mieszająca odwzorowuje obiekty na wyniki, a lista pomijania odwzorowuje wyniki na obiekty. Jak hasze są zaimplementowane w Redisie wiemy już z naszego poprzedniego wpisu. Lista Pomiń zapewnia, że ​​wyszukiwania są szybkie, a większość operacji ma średnią wartość O(log N). Lista pomijania jest zaimplementowana w pliku t_zset.c.

Podobnie jak większość innych struktur danych Redis, nawet posortowane zestawy są optymalizowane pod kątem rozmiaru, gdy są małe. Posortowane zestawy są przechowywane tylko jako hasze, dopóki nie osiągną określonego rozmiaru. Parametry konfiguracji kontrolujące ten rozmiar to: zset-max-ziplist-entries (domyślnie 128) i zset-max-ziplist-value (domyślnie 64).
Oszacowanie rozmiaru:https://stackoverflow.com/questions/6076342/is-there-a-practical-limit-to-the-number-of-elements-in-a-sorted- set-in-redis

Aplikacje

Jako zaawansowana struktura danych, posortowane zestawy mają różne przypadki użycia:

1. Najbardziej oczywistym przypadkiem użycia jest tablica wyników:utrzymywanie uporządkowanej listy unikalnych członków posortowanych według ich wyników. Dla m.in. tablica wyników dla MMORPG, jak wyjaśniono w oficjalnej dokumentacji Redis.
2. Posortowane zestawy z identycznymi wynikami są używane jako indeksy w Redis. Może to być od bardzo prostego przypadku użycia do bardzo złożonego. Dokumentacja Redis zawiera wspaniały artykuł na temat indeksowania przy użyciu posortowanych zestawów.
3. Szczególnym przypadkiem indeksowania przy użyciu posortowanych zestawów jest GEO API dla Redis, które zostało wprowadzone w Redis 3.2.0.
4. Rozmiar jest brany pod uwagę podczas korzystania z posortowanych zestawów. Biorąc pod uwagę złożone struktury danych bazowych, posortowane zestawy będą miały stosunkowo większy rozmiar pamięci. Dokładne liczby będą zależeć od charakteru zestawu danych. Ten post StackOverflow wspomina o numerze ballparku dla zestawu danych o przyzwoitej wielkości.

Ponieważ posortowane zestawy mają dość zaawansowane przypadki użycia, omówimy takie przypadki użycia dla posortowanych zestawów w kolejnych postach. Na razie zobaczmy prosty przykład.

Gamifikuj swój MOOC!

W naszym poprzednim poście dotyczącym bitmap Redis byliśmy programistami obsługującymi bardzo popularny MOOC. Facylitatorzy decydują, że chcą grywalizować kurs za pomocą tablicy liderów śledzącej najlepszych uczniów, którzy publikują posty w społeczności. Studenci z największą liczbą zaakceptowanych odpowiedzi na problemy opublikowane w postach społeczności kursu będą co tydzień otrzymywać specjalne wyróżnienie.
Będzie to klasyczny przypadek użycia dla porządkowania unikalnych kluczy w oparciu o wynik, czyli posortowanego zestawu Redis. Członkami będą legitymacje studenckie, a punktacja – liczba zaakceptowanych odpowiedzi. Możemy zaktualizować wynik za pomocą ZINCRBY w czasie rzeczywistym lub w tle, które może działać codziennie lub co tydzień. Oczywiście w naszym przypadku użycia wymagana jest aktualizacja wyników w czasie rzeczywistym. Do początkowego wstawienia ZADD z jedną z nowych flag przyda się. Wyświetlenie tablicy wyników uczniom będzie wymagało wykorzystania zapytań o odwrócony zakres (ZREVRANGE itp)

Przypis

Inne posty w naszej serii struktur danych Redis:

• Zestawy
• Hasze
• Mapy bitowe