Структуры данных, используемые в Redis

в 17:56, , рубрики: nosql, redis, Алгоритмы, структуры данных

От переводчика:
Хочу представить вашему вниманию перевод ответа одного из разработчиков Redis, на вопрос о том, какие структуры данных используются внутри Redis. Оригинальную дискуссию вы можете найти на stackoverflow.

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

Но поскольку вы спросили, вот внутренние реализации каждой структуры данных Redis:

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


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

Но ваш вопрос, на самом деле, не только о внутренностях, вы хотели спросить: «Какую структуру использовать для того, или иного?».

Строки

Строки — это основная структура. Это одна их четырех базовых структур, а так же основа всех сложных структур, потому что Список — это список строк, Множество — это множество строк, и так далее.

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

Другое интересное использование строк — это битовые массивы, и вообще, случайный доступ к массивам байтов, так как Redis предоставляет команды доступа к произвольным диапазонам байтов, или даже к отдельным битам. В качестве примера, обратите внимание на этот хороший пост: Fast Easy real time metrics using Redis.

Списки

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

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

Множества

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

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

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

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

Хэши

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

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

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

Упорядоченные Множества

Упорядоченное Множество — это единственная структура данных, кроме списка, поддерживающая работу с упорядоченными элементами. С упорядоченными множествами можно делать много крутых вещей. Например, вы можете реализовать все виды Топа Чего-либо в вашем веб-приложении. Топ пользователей по рейтингу, топ постов по числу просмотров, топ чего угодно, и один экземпляр Redis будет обслуживать тонны вставок и запросов в секунду.

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

Упорядоченные множества хороши для очередей с приоритетами.

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

Заключение

Надеюсь, я предоставил некоторую информацию в этом посте, но будет гораздо лучше скачать исходный код lamernews и понять как это работает. Большинство структур данных Redis`а используются в Lamer News, и их использование может служить подсказкой, что использовать для решения данной задачи.

Автор: cheetah

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js