От переводчика:
Хочу представить вашему вниманию перевод ответа одного из разработчиков 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
