Какие основные структуры данных используются для Redis?

Question

Я пытаюсь ответить на два вопроса в окончательном списке:

1. Какие основные структуры данных используются для Redis?
2. И каковы основные преимущества / недостатки /варианты использования для каждого типа?

Итак, я читал, что списки Redis фактически реализованы с помощью связанных списков.Но для других типов я не могу выкапывать какую-либо информацию.Кроме того, если бы кто-то наткнулся на этот вопрос и не получил сводную информацию о плюсах и минусах изменения или доступа к различным структурам данных, у них был бы полный список , когда лучше всего использовать конкретные типы чтобы ссылаться также.

В частности, я хочу обрисовать в общих чертах все типы: строку, список, набор, zset и хэш.

О, я смотрел на эту статью, среди другихНа данный момент:

• http://redis.io/topics/data-types
• http://redis.io/topics/data-types-intro
• http://redis.io/topics/faq

Answer 1

Я попытаюсь ответить на ваш вопрос, но сначала я начну с того, что может показаться странным: если вы не интересуетесь внутренними компонентами Redis, вам не нужно беспокоиться о том, как реализованы типы данных внутренне. Это по простой причине: для каждой операции Redis вы найдете сложность времени в документации и, если у вас есть набор операций и сложность времени, единственное, что вам нужно, - это некоторое представление об использовании памяти (и потому что мы проводим много оптимизаций, которые могут варьироваться в зависимости от данных, лучший способ получить эти последние цифры - провести несколько тривиальных реальных испытаний).

Но, как вы и просили, вот базовая реализация каждого типа данных Redis.

• Строки реализованы с использованием библиотеки динамических строк C, поэтому мы не платим (асимптотически) за выделения в операциях добавления. Таким образом, мы добавляем O (N), например, вместо квадратичного поведения.
• Списки реализованы с помощью связанных списков.
• Наборы и Хэши реализованы с помощью хеш-таблиц.
• Сортированные множества реализованы с помощью пропускаемых списков (особый тип сбалансированных деревьев).

Но когда списки, наборы и отсортированные наборы малы по количеству элементов и размеру самых больших значений, используется другое, гораздо более компактное кодирование. Эта кодировка отличается для разных типов, но имеет особенность, заключающуюся в том, что она представляет собой компактный блок данных, который часто вызывает сканирование O (N) для каждой операции. Поскольку мы используем этот формат только для небольших объектов, это не проблема; при сканировании небольшого большого (O) большого двоичного объекта кэш не обращает внимания , поэтому практически он выполняется очень быстро, и при слишком большом количестве элементов кодирование автоматически переключается на собственное кодирование (связанный список, хэш и т. д. ).

Но на самом деле ваш вопрос был не только о внутренних органах, ваша точка зрения была Какой тип использовать для достижения чего? .

Строка

Это базовый тип всех типов. Это один из четырех типов, но также является базовым типом сложных типов, потому что List - это список строк, Set - это набор строк и т. Д.

Строка Redis - это хорошая идея во всех очевидных сценариях, когда вы хотите сохранить HTML-страницу, но также и когда вы хотите избежать преобразования уже закодированных данных. Например, если у вас есть JSON или MessagePack, вы можете просто хранить объекты в виде строк. В Redis 2.6 вы даже можете манипулировать такого рода объектной серверной стороной, используя сценарии Lua.

Другое интересное использование строк - это битовые карты и, как правило, массивы байтов произвольного доступа, поскольку Redis экспортирует команды для доступа к произвольным диапазонам байтов или даже к отдельным битам. Например, проверьте это хорошее сообщение в блоге: Fast Easy метрики в реальном времени с использованием Redis .

Списки

Списки хороши, когда вы можете касаться только крайностей списка: около хвоста или около головы. Списки не очень хорошо разбивают на страницы, потому что произвольный доступ медленный, O (N). Поэтому хорошим использованием списков являются простые очереди и стеки или обработка элементов в цикле с использованием RPOPLPUSH с тем же источником и назначением для «вращения» кольца элементов.

Списки также хороши, когда мы хотим просто создать ограниченную коллекцию из N элементов, где обычно мы получаем доступ только к верхним или нижним элементам или когда N мало.

Установка

Наборы - это неупорядоченный сбор данных, поэтому они хороши каждый раз, когда у вас есть коллекция элементов, и очень важно очень быстро проверить наличие или размер коллекции. Еще одна интересная вещь о наборах - поддержка просмотра или выталкивания случайных элементов (команды SRANDMEMBER и SPOP).

Наборы также хороши для представления отношений, например, "Кто друзья пользователя X?" и так далее. Но другие хорошие структуры данных для такого рода вещей - это отсортированные наборы, как мы увидим.

Наборы поддерживают сложные операции, такие как пересечения, объединения и т. Д., Так что это хорошая структура данных для использования Redis «вычислительным» способом, когда у вас есть данные, и вы хотите выполнить преобразования этих данных для получения некоторого вывода.

Небольшие наборы кодируются очень эффективным способом.

Хэши

Хэши - это идеальная структура данных для представления объектов, состоящих из полей и значений.Поля хэшей также могут быть атомарно увеличены с помощью HINCRBY.Если у вас есть такие объекты, как пользователи, сообщения в блоге или какой-либо другой элемент item , то, скорее всего, стоит использовать хэши, если вы не хотите использовать свою собственную кодировку, такую ​​как JSON или аналогичную.

Однако имейте в виду, что Redis очень эффективно кодирует небольшие хэши, и вы можете попросить Redis атомарно получить, SET или очень быстро увеличить отдельные поля.

Хэши также можно использовать дляпредставлять связанные структуры данных, используя ссылки.Например, проверьте реализацию комментариев на lamernews.com.

Сортированные наборы

Сортированные наборы - это только другие структуры данных, кроме списков, для поддержки упорядоченных элементов .Вы можете сделать много интересных вещей с отсортированными наборами.Например, вы можете иметь в своем веб-приложении всевозможные списки Top Something .Лучшие пользователи по количеству баллов, лучшие посты по количеству просмотров страниц и тому подобное, но один экземпляр Redis будет поддерживать множество операций вставки и get-top-elements в секунду.

Сортированные наборы, как и обычные наборы, могут использоваться дляописать отношения, но они также позволяют разбивать список элементов на страницы и запоминать порядок.Например, если я помню друзей пользователя X с отсортированным набором, я могу легко запомнить их в порядке принятой дружбы.

Сортированные наборы хороши для приоритетных очередей.

Сортированные наборы похожи на большемощные списки, где вставка, удаление или получение диапазонов из середины списка всегда быстрая.Но они используют больше памяти и являются O (log (N)) структурами данных.

Заключение

Я надеюсь, что я предоставил некоторую информацию в этом посте, но гораздо лучше скачатьИсходный код lamernews от http://github.com/antirez/lamernews и понять, как это работает.Многие структуры данных из Redis используются внутри Lamer News, и есть много подсказок о том, что использовать для решения данной задачи.

Извините за грамматические опечатки, сейчас полночь, и вы слишком устали от просмотра поста;)

Answer 2

В большинстве случаев вам не нужно понимать базовые структуры данных, используемые Redis.Но немного знаний поможет вам сделать компромисс между ЦП и памятью.Это также помогает вам эффективно моделировать ваши данные.

Внутренне Redis использует следующие структуры данных:

1. Строка
2. Словарь
3. Двусвязный список
4. Пропуск списка
5. Список почтовых индексов
6. Int Наборы
7. Карты почтовых индексов (устарел в пользу списка почтовых индексов после Redis 2.6)

Чтобы найти кодировку, используемую определенным ключом, используйте команду object encoding <key>.

1.Строки

В Redis строки называются Простыми динамическими строками или SDS .Это небольшая оболочка над char *, которая позволяет вам хранить длину строки и количество свободных байтов в качестве префикса.

Поскольку длина строки сохраняется, strlen является операцией O (1).Кроме того, поскольку длина известна, строки Redis безопасны в двоичном формате.Вполне допустимо, чтобы строка содержала нулевой символ .

. Строки являются наиболее универсальной структурой данных, доступной в Redis.Строка - это all из следующих:

1. Строка символов, в которой может храниться текст.См. Команды SET и GET .
2. Массив байтов, который может хранить двоичные данные.
3. A long, который может хранить числа.См. INCR , DECR , INCRBY и DECRBY .
4. Массив (из chars, ints, longs или любой другой тип данных), который может обеспечить эффективный произвольный доступ.См. Команды SETRANGE и GETRANGE .
5. A битовый массив , который позволяет устанавливать или получать отдельные биты.См. Команды SETBIT и GETBIT .
6. Блок памяти, который можно использовать для построения других структур данных.Это используется внутри для создания ziplists и intsets, которые являются компактными, эффективными для памяти структурами данных для небольшого числа элементов.Подробнее об этом ниже.

2.Словарь

Redis использует Словарь для следующего:

1. Чтобы сопоставить ключ с соответствующим значением, где значением может быть строка, хэш, множество,отсортированный набор или список.
2. Чтобы сопоставить ключ с его отметкой времени истечения.
3. Для реализации типов данных Hash, Set и Sorted Set.
4. Для сопоставления команд Redis с функциямикоторые обрабатывают эти команды.
5. Чтобы сопоставить ключ Redis со списком клиентов, которые заблокированы на этом ключе.См. BLPOP .

Словари Redis реализованы с использованием Хеш-таблиц .Вместо объяснения реализации, я просто объясню конкретные вещи Redis:

1. Словари используют структуру с именем dictType для расширения поведения хеш-таблицы.Эта структура имеет указатели функций, и поэтому следующие операции являются расширяемыми: а) хеш-функция, б) сравнение ключей, в) деструктор ключей и г) деструктор значений.
2. В словарях используется murmurhash2 .(Ранее они использовали хеш-функцию djb2 с seed = 5381, но затем хеш-функция была переключена на murmur2 . См. этот вопрос для объяснения алгоритма хеширования djb2.)
3. Redis использует пошаговое хеширование, также известное как Инкрементальное изменение размера .В словаре есть две хеш-таблицы.Каждый раз, когда словарь касается , одна корзина переносится из первой (меньшей) хэш-таблицы во вторую.Таким образом, Redis предотвращает дорогостоящую операцию изменения размера.

Структура данных Set использует словарь, чтобы гарантировать отсутствие дубликатов.Sorted Set использует словарь для сопоставления элемента с его оценкой, поэтому ZSCORE является операцией O (1).

3.Дважды связанные списки

Тип данных list реализован с использованием Doubly Linked Lists . Реализация Redis - это учебник прямо из алгоритма. Единственное изменение заключается в том, что Redis сохраняет длину в структуре данных списка. Это гарантирует, что LLEN имеет сложность O (1).

4. Пропустить Списки

Redis использует Пропуск списков в качестве базовой структуры данных для отсортированных наборов. В Википедии есть хорошее введение. Статья Уильяма Пью Пропуск списков: вероятностная альтернатива сбалансированным деревьям содержит более подробную информацию.

Сортированные наборы используют как список пропусков, так и словарь. В словаре хранится оценка каждого элемента.

Реализация списка пропусков Redis отличается от стандартной реализации следующим:

1. Redis позволяет дублировать баллы. Если два узла имеют одинаковую оценку, они сортируются по лексикографическому порядку .
2. Каждый узел имеет обратный указатель на уровне 0. Это позволяет вам проходить элементы в обратном порядке оценки.

5. Почтовый список

Zip-список похож на двусвязный список, за исключением того, что он не использует указатели и сохраняет данные встроенными.

Каждый узел в двусвязном списке имеет по 3 указателя - один прямой указатель, один обратный указатель и один указатель для ссылки на данные, хранящиеся на этом узле. Указатели требуют памяти (8 байт в 64-битной системе), поэтому для небольших списков двусвязный список очень неэффективен.

Список Zip последовательно сохраняет элементы в строке Redis. Каждый элемент имеет небольшой заголовок, в котором хранится длина и тип данных элемента, смещение к следующему элементу и смещение к предыдущему элементу. Эти смещения заменяют прямые и обратные указатели. Поскольку данные хранятся в строке, нам не нужен указатель данных.

Zip-список используется для хранения небольших списков, отсортированных наборов и хэшей. Сортированные наборы сведены в список, подобный [element1, score1, element2, score2, element3, score3], и сохранены в Zip List. Хэши сведены в список вроде [key1, value1, key2, value2] и т. Д.

С помощью Zip Lists вы можете найти компромисс между процессором и памятью. Zip-списки эффективны при использовании памяти, но используют больше ресурсов ЦП, чем связанный список (или хэш-таблица / список пропусков). Поиск элемента в списке почтовых индексов O (n). Вставка нового элемента требует перераспределения памяти. Из-за этого Redis использует эту кодировку только для небольших списков, хэшей и отсортированных наборов. Вы можете настроить это поведение, изменив значения <datatype>-max-ziplist-entries и <datatype>-max-ziplist-value> в redis.conf. См. Redis Memory Optimization, раздел «Специальное кодирование небольших агрегированных типов данных» для получения дополнительной информации.

Замечания к ziplist.c превосходны, и вы можете полностью понять эту структуру данных, не читая код.

6. Int устанавливает

Int Наборы - причудливое название для "Sorted Integer Arrays".

В Redis наборы обычно реализуются с использованием хеш-таблиц. Для небольших наборов хеш-таблица неэффективна с точки зрения памяти. Когда набор состоит только из целых чисел, массив часто более эффективен.

Int Set - это отсортированный массив целых чисел. Для поиска элемента используется алгоритм двоичного поиска . Это имеет сложность O (log N). Добавление новых целых чисел в этот массив может потребовать перераспределения памяти, что может стать дорогостоящим для больших целочисленных массивов.

В качестве дальнейшей оптимизации памяти, наборы Int входят в 3 варианта с различными целочисленными размерами: 16 бит, 32 бита и 64 бита. Redis достаточно умен, чтобы использовать правильный вариант в зависимости от размера элементов. Когда добавляется новый элемент, и он превышает текущий размер, Redis автоматически переносит его на следующий размер. Если строка добавлена, Redis автоматически преобразует набор Int в обычный набор на основе хэш-таблицы.

Int Наборы - это компромисс между процессором и памятью.Наборы Int чрезвычайно эффективны в использовании памяти, а для небольших наборов они быстрее, чем хеш-таблица.Но после определенного количества элементов время поиска O (log N) и стоимость перераспределения памяти становятся слишком большими.На основе экспериментов было установлено, что оптимальное пороговое значение для переключения на обычную хэш-таблицу составляет 512. Однако вы можете увеличить это пороговое значение (уменьшать его не имеет смысла) в зависимости от потребностей вашего приложения.См. set-max-intset-entries в redis.conf.

7.Zip-карты

Zip-карты - это словари, сведенные и сохраненные в списке.Они очень похожи на Zip-списки.

Zip-карты устарели со времен Redis 2.6, а небольшие хеш-коды хранятся в Zip-списках.Чтобы узнать больше об этой кодировке, обратитесь к комментариям в zipmap.c .

Answer 3

Redis хранит ключи, указывающие на значения.Ключи могут быть любыми двоичными значениями вплоть до разумного размера (рекомендуется использовать короткие строки ASCII для удобства чтения и отладки).Значения являются одним из пяти собственных типов данных Redis.

1.strings - последовательность двоичных безопасных байтов размером до 512 МБ

2.hashes - коллекция пар значений ключа

3.lists - коллекция строк в порядке вставки

4.sets - коллекция уникальных строк без упорядочения

5.sortedsets - коллекцияуникальные строки, упорядоченные по пользовательской шкале

Strings

Строка Redis - это последовательность байтов.

Строки в Redis безопасны в двоичном формате.(это означает, что они имеют известную длину, не определяемую никакими специальными завершающими символами), поэтому вы можете хранить в одной строке все, что угодно, до 512 мегабайт.

Строки - это каноническое понятие «хранилище значений ключей».У вас есть ключ, указывающий на значение, где ключ и значение являются текстовыми или двоичными строками.

Для всех возможных операций со строками см. http://redis.io/commands/#string

Хэши

Хеш Redis представляет собой набор пар ключ-значение.

Хеш Redis содержит множество пар ключ-значение, где каждый ключ и значение является строкой.Хэши Redis не поддерживают сложные значения напрямую (т. Е. Вы не можете иметь в поле хеша значение списка, набора или другого хэша), но вы можете использовать поля хеша, чтобы указывать на другие сложные значения верхнего уровня.Единственная специальная операция, которую вы можете выполнить со значениями поля хеша, - это атомарный приращение / убывание числового содержимого.

Хэши Redis можно рассматривать двумя способами: как непосредственное представление объекта и как способ хранения множества маленькихзначения компактно.

Прямые представления объектов просты для понимания.Объекты имеют имя (ключ хеша) и набор внутренних ключей со значениями.Смотрите пример ниже, ну, в общем, пример.

Хранение множества небольших значений с использованием хэша - это умный способ хранения больших объемов данных Redis.Когда хеш имеет небольшое количество полей (~ 100), Redis оптимизирует хранение и эффективность доступа ко всему хешу.Оптимизация хранилища небольших хэшей в Redis вызывает интересное поведение: более эффективно иметь 100 хэшей, каждый из которых содержит 100 внутренних ключей и значений, а не 10 000 ключей верхнего уровня, указывающих на строковые значения.Использование хэшей Redis для оптимизации вашего хранилища данных таким способом требует дополнительных затрат на программирование для отслеживания того, где заканчиваются данные, но если ваше хранилище данных основано на строковых значениях, вы можете сэкономить много накладных расходов памяти, используя этот странный прием.

Для всех возможных операций с хэшами см. документы по хешу

Списки

Списки Redis действуют как связанные списки.

Вы можете вставлять, удалять и просматривать списки либо из заголовка, либо из конца списка.

Используйте списки, когда вам нужно сохранить значения в том порядке, в котором они были вставлены.(Redis дает вам возможность вставлять в любую произвольную позицию списка, если вам нужно, но производительность вставки будет ухудшаться, если вы вставляете далеко от начальной позиции.)

Списки Redis часто используются в качестве производителя / потребителя.очереди.Вставьте элементы в список, а затем вытолкните элементы из списка.Что произойдет, если ваши потребители попытаются выскочить из списка без элементов?Вы можете попросить Redis дождаться появления элемента и сразу же вернуть его вам, когда он будет добавлен.Это превращает Redis в систему сообщений / событий / заданий / задач / уведомлений в режиме реального времени.

Вы можете атомарно удалять элементы с любого конца списка, что позволяет рассматривать любой список как стек или очередь.

Вы также можете поддерживать списки фиксированной длины (ограниченные коллекции), обрезая свой список до определенного размера после каждой вставки.

Для всех возможных операций со списками см. Документы списков .

Наборы

RediНаборы, ну, в общем, наборы.

Набор Redis содержит уникальные неупорядоченные строки Redis, где каждая строка существует только один раз для каждого набора.Если вы добавите один и тот же элемент десять раз в набор, он появится только один раз.Наборы отлично подходят для ленивой проверки того, что что-то существует, по крайней мере, один раз, не беспокоясь о том, что дубликаты элементов накапливаются и тратят пространство.Вы можете добавлять одну и ту же строку столько раз, сколько хотите, без необходимости проверять, существует ли она.

Наборы быстрые для проверки членства, вставки и удаления членов в наборе.

Наборы имеют эффективные операции над множествами, как и следовало ожидать.Вы можете взять объединение, пересечение и различие нескольких множеств одновременно.Результаты могут быть либо возвращены вызывающей стороне, либо результаты могут быть сохранены в новом наборе для последующего использования.

Наборы имеют постоянный доступ к времени для проверок членства (в отличие от списков), а Redis даже имеет удобное удаление и возврат случайных элементов.(«вытолкнуть случайный элемент из набора») или случайного члена, возвращающегося без замены («дайте мне 30 уникальных случайных пользователей») или с заменой («дайте мне 7 карточек, но после каждого выбора кладите карточку обратно, чтобы онапотенциально может быть взята снова ").

Для всех возможных операций над наборами см. наборы документов .

Сортированные наборы

Сортированные наборы Redis - это наборы с заданным пользователем порядком.

Для простоты можно представить отсортированный набор как двоичное дерево с уникальными элементами.(Сортированные наборы Redis на самом деле пропускают списки .) Порядок сортировки элементов определяется оценкой каждого элемента.

Сортированные наборы все еще являются наборами.Элементы могут появляться только один раз в наборе.Элемент в целях уникальности определяется его содержимым строки.Вставка элемента «яблоко» с оценкой сортировки 3, затем вставка элемента «яблоко» с оценкой 500 сортировки приводит к получению одного элемента «яблоко» с оценкой 500 сортировки в вашем отсортированном наборе.Наборы уникальны только на основе данных, а не на основе пар (оценка, данные).

Убедитесь, что ваша модель данных опирается на содержимое строки, а не на оценку уникальности элемента.Счета могут быть повторены (или даже ноль), но, в последний раз, элементы набора могут существовать только один раз для отсортированного набора.Например, если вы попытаетесь сохранить историю каждого входа пользователя в систему как отсортированный набор, сделав счет эпохой входа в систему и значение идентификатором пользователя, вы в конечном итоге сохраните только последнюю эпоху входа для всех своих пользователей.Ваш набор будет увеличиваться до размера вашей пользовательской базы, а не до желаемого размера пользовательской базы * логинов.

Элементы добавляются в ваш набор с оценками.Вы можете обновить счет любого элемента в любое время, просто добавьте элемент снова с новым счетом.Результаты представлены двойными числами с плавающей запятой, так что вы можете указать гранулярность временных меток высокой точности, если это необходимо.Несколько элементов могут иметь одинаковую оценку.

Вы можете получить элементы несколькими различными способами.Поскольку все отсортировано, вы можете запросить элементы, начиная с самых низких баллов.Вы можете запросить элементы, начиная с самых высоких баллов («в обратном порядке»).Вы можете запросить элементы по их оценке сортировки либо в натуральном, либо в обратном порядке.

Для всех возможных операций над отсортированными наборами см. Документы по отсортированным наборам.