Jakie są podstawowe struktury danych wykorzystywane w Redis?

Przez większość czasu nie musisz rozumieć podstawowych struktur danych używanych przez Redis. Ale odrobina wiedzy pomaga w wymianie pamięci CPU v / s. Pomaga również modelować dane w efektywny sposób.

Wewnętrznie Redis wykorzystuje następujące struktury danych:

1. String
2. Słownik
3. Lista Podwójnie Połączona
4. Pomiń Listę
5. Lista Zip
6. Int Sets
7. Mapy Zip (przestarzałe na rzecz listy zip od Redis 2.6)

Aby znaleźć kodowanie używane przez dany klucz, użyj polecenia object encoding <key>.

1. Stringi

W Redis, ciągi są nazywane proste dynamiczne ciągi, lub SDS . Jest to mała owijka nad char *, która pozwala zapisać Długość łańcucha i liczbę wolnych bajtów jako prefiks.

Ponieważ długość łańcucha jest przechowywana, strlen jest operacją O(1). Ponadto, ponieważ długość jest znana, ciągi Redis są bezpieczne binarnie. Jest całkowicie legalne, aby łańcuch zawierał znak null .

Ciągi są najbardziej wszechstronną strukturą danych dostępną w Redis. Ciąg jest Wszystkie Z NASTĘPUJĄCYCH:

1. ciąg znaków, który może przechowywać tekst. Zobacz SETi GET.
2. tablica bajtów, która może przechowywać dane binarne.
3. a long, które mogą przechowywać liczby. Zobacz INCR, DECR, INCRBY i DECRBY polecenia.
4. an Array (of chars, ints, longs lub innego typu danych), które mogą umożliwić efektywny dostęp losowy. Zobacz SETRANGEI GETRANGE polecenia.
5. tablica bitów , która pozwala ustawić lub pobrać poszczególne bity. Zobacz polecenia SETBITi GETBIT.
6. blok pamięci, który można wykorzystać do budowy innych struktur danych. Jest to używane wewnętrznie do budowania ziplists i intsets, które są kompaktowymi, wydajnymi pamięcią danymi konstrukcje dla małej liczby elementów. Więcej na ten temat poniżej.

2. Słownik

Redis używa słownika dla następujących:

1. mapowanie klucza do powiązanej z nim wartości, gdzie wartością może być łańcuch, hash, set, sorted set lub list.
2. mapowanie klucza do znacznika czasu jego wygaśnięcia.
3. aby zaimplementować Hash, Set i posortowane typy danych Set.
4. mapowanie poleceń Redis do funkcji obsługujących te polecenia.
5. aby mapować Redis klucz do listy klientów, którzy są zablokowani na tym kluczu. Zobacz BLPOP .

1. Słowniki używają struktury o nazwie dictType, Aby rozszerzyć zachowanie tabeli hash. Struktura ta ma Wskaźniki funkcji, a więc następujące operacje są rozszerzalne: a) funkcja hash, b) porównanie kluczy, C) Klucz Destruktor, oraz D) Destruktor wartości.
2. Słowniki używają murmurhash2 . (Wcześniej używali djb2 funkcja hash, Z seed=5381, ale potem funkcja hash została zamieniona na murmur2. Zobacz to pytanie, aby uzyskać wyjaśnienie algorytmu haszującego djb2 .)
Redis używa hashowania przyrostowego, znanego również jako przyrostowa Zmiana rozmiaru . Słownik posiada dwie tabele hash. Za każdym razem gdy słownik jest dotknięty , jeden bucket jest przenoszony z pierwszej (mniejszej) tabeli hash do drugiej. W ten sposób Redis zapobiega kosztownej operacji zmiany rozmiaru.

Struktura danych Set używa słownika, aby zagwarantować, że nie ma duplikatów. Sorted Set używa słownika do mapowania elementu do jego wyniku, dlategoZSCORE jest operacją O(1).

3. Listy Podwójnie Połączone

Typ danych list jest zaimplementowany przy użyciuPodwójnie połączonych list . Realizacja Redis jest prosto z podręcznika algorytmu. Jedyną zmianą jest to, że Redis przechowuje długość w strukturze danych listy. Zapewnia to, że LLEN ma złożoność O(1).

4. Pomiń Listy

Sortowane Zestawy używają zarówno listy przeskoków, jak i Słownik. Słownik przechowuje wynik każdego elementu.

Implementacja listy pominięć Redis różni się od standardowej implementacji w następujący sposób:

1. Redis pozwala na duplikowanie wyników. Jeśli dwa węzły mają ten sam wynik, są one sortowane według porządku leksykograficznego.
2. każdy węzeł ma wskaźnik wstecz na poziomie 0. Pozwala to na przesuwanie elementów w odwrotnej kolejności partytury.

5. Lista Zip

Lista Zip jest podobnie jak podwójnie połączona lista, z tą różnicą, że nie używa wskaźników i przechowuje dane w linii.

Każdy węzeł na podwójnie połączonej liście ma po 3 wskaźniki - jeden wskaźnik do przodu, jeden wskaźnik do tyłu i jeden wskaźnik do odwoływania się do danych przechowywanych w tym węźle. Wskaźniki wymagają pamięci (8 bajtów w systemie 64-bitowym), więc w przypadku małych list podwójnie połączona lista jest bardzo nieefektywna.

Lista Zip przechowuje elementy sekwencyjnie w łańcuchu Redis. Każdy element ma mały nagłówek, który przechowuje długość i typ danych elementu, przesunięcie do następnego elementu i przesunięcie do poprzedniego elementu. Te przesunięcia zastępują wskaźniki do przodu i do tyłu. Ponieważ dane są przechowywane w linii, nie potrzebujemy wskaźnika danych.

Lista Zip służy do przechowywania małych list, posortowanych zestawów i skrótów. Posortowane zestawy są spłaszczane do listy typu [element1, score1, element2, score2, element3, score3] i przechowywane na liście Zip. Hasze są spłaszczane do listy typu [key1, value1, key2, value2] itd.

Z listy Zip masz moc, aby kompromis między procesorem a pamięcią. Listy Zip są wydajne w pamięci, ale używają więcej procesora niż lista połączona(lub Lista skrótów / pominięć). Znajdowanie elementu na liście zip to O (n). Wstawianie nowego elementu wymaga ponownego przydzielenia pamięci. Z tego powodu Redis używa tego kodowania tylko dla małych list, skrótów i posortowanych zestawów. Możesz dostosować to zachowanie, zmieniając wartości <datatype>-max-ziplist-entries i <datatype>-max-ziplist-value> w redis.conf. Zobacz Optymalizacja pamięci Redis, sekcja " specjalne kodowanie małych zagregowanych danych typy " aby uzyskać więcej informacji.

Komentarze do ziplist.c są doskonałe i możesz zrozumieć tę strukturę danych całkowicie bez konieczności czytania kodu.

6. Int Sets

Zestawy Int są wymyślną nazwą dla "posortowanych tablic całkowitych".

W Redis, zestawy są zwykle implementowane przy użyciu tabel skrótów. W przypadku małych zestawów tabela hash jest nieefektywna pod względem pamięci. Gdy zbiór składa się tylko z liczb całkowitych, tablica jest często bardziej wydajny.

Zbiór Int jest posortowaną tablicą liczb całkowitych. Aby znaleźć element używany jest binarny algorytm wyszukiwania . Ma złożoność O (log N). Dodawanie nowych liczb całkowitych do tej tablicy może wymagać realokacji pamięci, co może stać się kosztowne dla dużych tablic całkowitych.

W celu dalszej optymalizacji pamięci, Zestawy Int występują w 3 wariantach o różnych rozmiarach: 16 bitów, 32 bitów i 64 bitów. Redis jest na tyle inteligentny, aby użyć odpowiedniego wariantu w zależności od wielkości żywioły. Gdy nowy element zostanie dodany i przekroczy bieżący rozmiar, Redis automatycznie przeniesie go do następnego rozmiaru. Jeśli zostanie dodany ciąg znaków, Redis automatycznie konwertuje zestaw Int na zwykły zestaw oparty na tabeli Hash.

Zestawy Int to kompromis między procesorem a pamięcią. Zestawy Int są niezwykle wydajne w pamięci, a dla małych zestawów są szybsze niż tabela hash. Ale po pewnej liczbie elementów, o (log N) czas pobierania i koszt realokacji pamięci stają się zbyt much. Na podstawie eksperymentów ustalono, że optymalny próg przejścia na zwykłą tabelę haszującą wynosi 512. Możesz jednak zwiększyć ten próg (zmniejszenie tego nie ma sensu) w zależności od potrzeb Twojej aplikacji. Zobacz {[14] } w redis.conf.

7. Mapy Zip

Mapy Zip to słowniki spłaszczone i przechowywane na liście. Są bardzo podobne do list Zip.

Mapy Zip są przestarzałe od Redis 2.6, A małe skróty są przechowywane na listach Zip. Aby dowiedzieć się więcej informacje na temat tego kodowania można znaleźć w komentarzach w zipmap.c .

Redis przechowuje klucze wskazujące na wartości. Klucze mogą być dowolnymi wartościami binarnymi do rozsądnego rozmiaru (użycie krótkich łańcuchów ASCII jest zalecane do celów czytelności i debugowania). Wartości są jednym z pięciu natywnych typów danych Redis.

1.strings-ciąg binarnych bezpiecznych bajtów do 512 MB

2.hashes-zbiór par wartości klucza

3.lists-an in-insertion-order collection of strings

4.zestawy-kolekcja unikalnych sznurków bez zamawianie

5.sortowane zbiory-zbiór unikalnych ciągów uporządkowanych według zdefiniowanej przez użytkownika punktacji

Stringi

Łańcuch Redis jest sekwencją bajtów.

Łańcuchy w Redis są bezpieczne binarnie (co oznacza, że mają znaną długość, która nie jest określona przez żadne specjalne znaki kończące), więc możesz przechowywać wszystko do 512 megabajtów w jednym łańcuchu.

Ciągi są kannoniczną koncepcją "przechowuj wartość klucza". Masz klucz wskazujący na wartość, gdzie oba klucz i wartość są ciągami tekstowymi lub binarnymi.

Dla wszystkich możliwych operacji na łańcuchach, zobacz http://redis.io/commands/#string

Hashes

Skrót Redis jest zbiorem par wartości klucza.

Skrót Redis zawiera wiele par wartości klucza, gdzie każdy klucz i wartość jest ciągiem znaków. Skróty Redis nie obsługują bezpośrednio złożonych wartości (co oznacza, że pole hash nie może mieć wartości listy, zestawu lub innego skrótu), ale można użyć pól hash, aby wskaż inne złożone wartości najwyższego poziomu. Jedyną specjalną operacją, którą można wykonać na wartościach pola hash, jest przyrost atomowy / dekrement zawartości liczbowej.

Można myśleć o skrócie Redis na dwa sposoby: jako bezpośredniej reprezentacji obiektu i jako sposób na przechowywanie wielu małych wartości w kompaktowy sposób.

Bezpośrednie reprezentacje obiektów są proste do zrozumienia. Obiekty mają nazwę (klucz hash) oraz zbiór kluczy wewnętrznych z wartościami. Zobacz poniższy przykład dla przykład.

Przechowywanie wielu małych wartości za pomocą skrótu jest sprytną techniką Redis massive data storage. Gdy hash ma niewielką liczbę pól (~100), Redis optymalizuje wydajność przechowywania i dostępu całego hasha. Optymalizacja małych skrótów Redis podnosi interesujące zachowanie: wydajniej jest mieć 100 skrótów z 100 wewnętrznymi kluczami i wartościami, a nie mieć 10 000 klawiszy najwyższego poziomu wskazujących na wartości łańcuchowe. Korzystanie z skrótów Redis w celu optymalizacji przechowywania danych to sposób wymaga dodatkowego narzutu programowania do śledzenia, gdzie dane kończą się, ale jeśli przechowywanie danych jest zasadniczo oparte na ciągach, można zaoszczędzić wiele narzutu pamięci za pomocą tej jednej dziwnej sztuczki.

Wszystkie możliwe operacje na hashach można znaleźć w docs hash

Listy

Listy Redis działają jak listy połączone.

Możesz wstawiać, usuwać i przesuwać listy z głowy lub ogona listy.

Użyj List, gdy potrzebujesz zachowaj wartości w kolejności, w jakiej zostały wstawione. (Redis daje możliwość wstawienia w dowolnej pozycji listy, jeśli zajdzie taka potrzeba, ale wydajność wstawiania spadnie, jeśli wstawisz daleko od pozycji początkowej.)

Listy Redis są często używane jako kolejki producentów/konsumentów. Wstaw elementy do listy, a następnie pop elementy z listy. Co się stanie, jeśli konsumenci spróbują wyskoczyć z listy bez elementów? Możesz poprosić Redisa, aby poczekał na pojawienie się elementu i zwrócił go tobie natychmiast po dodaniu. Zmienia to Redis w kolejkę komunikatów/Zdarzenie/zadanie/Zadanie/System powiadomień w czasie rzeczywistym.

Można atomicznie usunąć elementy z każdego końca listy, umożliwiając traktowanie każdej listy jako stosu lub kolejki.

Możesz również utrzymywać listy o stałej długości (ograniczone Kolekcje), przycinając listę do określonego rozmiaru po każdym wstawianiu.

Wszystkie możliwe operacje na listach, zobacz listy docs

Zestawy

Zestawy Redis to, cóż, zestawy.

Zestaw Redis zawiera unikalne, nieuporządkowane ciągi Redis, w których każdy ciąg istnieje tylko raz na zestaw. Jeśli dodasz ten sam element dziesięć razy do zestawu, pojawi się on tylko raz. Zestawy są świetne do leniwego upewniania się, że coś istnieje przynajmniej raz, bez martwienia się o powielanie elementów gromadzących się i marnujących miejsce. Możesz dodać ten sam ciąg tyle razy, ile chcesz, bez konieczności sprawdzania, czy już istnieje.

Zestawy są szybkie do sprawdzania, wstawiania i usuwania członków w zestawie.

Zestawy mają wydajne operacje set, jak można się spodziewać. Możesz wziąć związek, przecięcie i różnicę wielu zestawów na raz. Wyniki mogą być zwrócone do wywołującego lub mogą być zapisane w nowym zestawie do późniejszego użycia.

Zestawy mają stały czas dostępu do kontroli członkostwa( w przeciwieństwie do list), a Redis ma nawet wygodne losowe usuwanie i zwracanie członków ("pop losowy element z zestawu") lub losowy członek powracający bez wymiany ("give me 30 random-ish unique users") lub z zamianą ("give me 7 cards, but after every selection, put the card back so it potencjalnie mogą być próbkowane ponownie").

Dla wszystkich możliwych operacji na zestawach, zobacz Sets docs .

Sortowane Zestawy

Redis sortowane zestawy są zestawami z kolejnością zdefiniowaną przez użytkownika.

Dla uproszczenia można myśleć o posortowanym zbiorze jako drzewo binarne z unikalnymi elementami. (Redis sortowane zbiory są w rzeczywistości pomiń listy.) Kolejność sortowania elementów jest określona przez wynik każdego elementu.

Sortowane zestawy są nadal zestawami. Elementy mogą pojawić się tylko raz w zestawie. Element, dla celów unikalności, jest definiowany przez jego zawartość ciągu znaków. Wstawienie elementu "apple" z wynikiem sortowania 3, a następnie wstawienie elementu "apple" z wynikiem sortowania 500 daje w jednym elemencie" apple " z wynikiem sortowania 500 w Twoim sortowanym zestawie. Zestawy są tylko unikalne na podstawie danych, a nie na podstawie (wynik, dane) par.

Upewnij się, że twój model danych opiera się na zawartości ciągu znaków, a nie na wyniku elementu dla unikalności. Wyniki mogą być powtarzane (lub nawet zerowe), ale po raz ostatni elementy zestawu mogą istnieć tylko raz na posortowany zestaw. Na przykład, jeśli spróbujesz zapisać historię każdego logowania użytkownika jako posortowany zestaw, czyniąc wynik epoką logowania i wartością ID użytkownika, będziesz przechowywać tylko ostatnią epokę logowania dla wszystkich Twoich użytkowników. Twój zestaw urosnie do rozmiaru twojej bazy użytkowników , a nie pożądanego rozmiaru loginów*.

Elementy są dodawane do zestawu z wynikami. Możesz zaktualizować wynik dowolnego elementu w dowolnym momencie, po prostu dodaj element ponownie z nowym wynikiem. Wyniki są reprezentowane przez podwojenia zmiennoprzecinkowe, więc w razie potrzeby można określić szczegółowość znaczników czasu o wysokiej precyzji. Wiele elementów może mieć ten sam wynik.

Elementy można pobierać na kilka różnych sposobów. Od wszystko jest posortowane, możesz poprosić o elementy zaczynając od najniższych wyników. Możesz poprosić o elementy zaczynające się od najwyższych wyników ("na odwrót"). Możesz poprosić o elementy według ich wyniku sortowania w kolejności naturalnej lub odwrotnej.

Wszystkie możliwe operacje na posortowanych zestawach, zobacz posortowane zestawy docs.