Внимательно пишите статьи и делитесь ими с душой.
Персональный сайт:yasinshaw.com
Общедоступный номер: технический круг xy
В предыдущей статье были представлены пять наиболее часто используемых объектов Redis и лежащие в их основе структуры данных. В этой статье в основном представлен объект, который не так часто используется, но очень подходит для некоторых особых сценариев: растровые изображения.
проблема, с которой мы сталкиваемся
Сначала рассмотрим несколько распространенных сценариев:
- Запрос количества пользователей, вошедших сегодня
- Проверьте, какие пользователи вошли в систему сегодня
- Запрос, понравилась ли пользователю статья
- Запрос, входил ли пользователь в систему в течение двух дней подряд
- Опросите пользователей, которым понравилась статья А и статья Б.
Эти требования могут быть выполнены с использованием базы данных, некоторых таблиц журналов, а затем запросов к ним через SQL. но это будетОтнимает много места на диске, а производительность низкая. В случае большого объема данных использование базы данных для запросов и анализа будет очень медленным.
Я хотел бы поблагодарить наших ученых-компьютерщиков за изобретение структуры данных, которую можно использовать для решения такого рода задач. этоBitMap. То есть структура данных, используемая в нижней части растровых изображений Redis, которую в основном представляет эта статья.
Первая статья в Programming Pearl посвящена использованию BitMap для сортировки данных в больших файлах. В некоторых интервью есть похожие вопросы.
Вопрос для интервью: Файл 10G, все из которых являются натуральными числами, по одному в строке, расположенными в случайном порядке и отсортированными. Выполнено на 32-битной машине с ограничением памяти 2G.
На LeetCode есть проблема с алгоритмом, которую также можно решить с помощью BitMap:
Название алгоритма: Возьмите n различных чисел от 0 до n и найдите пропущенное. Примечание. Ваш алгоритм должен иметь линейную временную сложность. Можете ли вы реализовать алгоритм, который занимает только постоянную дополнительную сложность пространства?
Принцип растрового изображения
BitMap на самом деле является структурой данных.Высокая производительность с использованием битовых операций, чтобы хранить и вычислять некоторую информацию. Далее познакомимся с принципом BitMap.
BitMap записывает информацию на основе расположения битов. Например, теперь у нас есть 8-битный BitMap. Изначально все биты равны 0.
0, 0, 0, 0, 0, 0, 0, 0
Тогда есть такое требование: Предположим, что сегодня в нашу систему вошли четыре пользователя с идентификаторами 1, 2, 4 и 7. Если мы хотим записать эту информацию для входа, нам нужно только пометить соответствующую позицию как 1. :
1, 1, 0, 1, 0, 0, 1, 0
В настоящее время, если вы хотите знать, вошел ли пользователь с идентификатором 7 в систему сегодня, вам нужно только проверить, равна ли 7-я цифра в этом BitMap 1.
Видно, что если вы используете список или набор для хранения, если идентификатор представляет собой байт, занимающий 8 бит (реальная ситуация может быть типом long, занимающим 64 бита), то 8 идентификаторов будут занимать 64 бита, и использовать BitMap нужно только для того, чтобы занимать 8 бит. Точно так же, если наше поле id занимает 64 бита, оно может сэкономить в 64 раза больше места. Более того, характеристики битовых операций можно использовать для быстрой реализации таких операций, как статистика, объединение и пересечение.
Люди, которые прочитали статью А: 1, 2, 4, 7:
1, 1, 0, 1, 0, 0, 1, 0
Люди, которые прочитали статью B: 1, 3, 4, 8:
1, 0, 1, 1, 0, 0, 0, 1
Люди, которые прочитали статью А и прочитали статью Б:
1, 1, 0, 1, 0, 0, 1, 0
&
1, 0, 1, 1, 0, 0, 0, 1
=
1, 0, 0, 1, 0, 0, 0, 0
Люди, которые прочитали статью А и прочитали статью Б: 1, 4
В приведенном выше примере можно поместить только 8 бит, что, если мой идентификатор равен 9?
BitMap состоит из таких данных, как указано выше. вы можете использоватьрасширяемый целочисленный массивДелать, например, длинный массив. Так что его можно расширять бесконечно.
Что делать, если идентификаторы разрежены?
Например, идентификатор, который я хочу сохранить, может быть 1, 101, 1001, что является относительно редким.Если я использую BitMap, это займет некоторое пространство. Хотя некоторые реализации с открытым исходным кодом могут решить эту проблему путем записи смещений, это также повлияет на производительность из-за частых разбиений.В этом случае не рекомендуется использовать BitMap..
Заинтересованные студенты могут узнать об EWAHCompressedBitMap с открытым исходным кодом от Google, который решает проблему разреженного ввода.
Реализация растрового изображения
Поскольку автор в основном знаком с языком Java, я представлю реализацию BitMap на языке Java.
JDK предоставляет реализацию BitMap, называемуюBitSet,родыjava.utilпод пакет. Нижний слой используетlongМассив типа, где long представляет слово. Но BitSet не решает упомянутую выше проблему разреженного ввода. EWAHCompressedBitMap с открытым исходным кодом от Google решает проблему разреженного ввода.
Redis предоставляет растровые объекты. Фактически используется строковый объект, а нижний слой использует SDS, упомянутый в нашей предыдущей статье. Так что будет максимальный предел 512M, то есть он может хранить до2^32данные. Если ваш идентификатор имеет тип long и занимает 64 бита, тоМожно использовать два растровых изображения для хранения.
Из базовой реализации SDS его можно расширять и сокращать, но если ввод разреженный, он все равно будет тратить много памяти. Поэтому, если ввод очень разреженный, не рекомендуется использовать растровые изображения Redis.
Основные операции с растровыми изображениями Redis
Суммировать
Redis предоставляет растровые объекты. ЭтоЭкономия места и значительное повышение производительности в некоторых сценариях. Но если ввод разреженный (например, на сайте 100 миллионов зарегистрированных пользователей, но только 100 000 пользователей заходят каждый день), то лучше использовать set.
с другой стороны,Вход может быть только целым числом. Если это строковый тип, эту структуру данных использовать нельзя.
Обратите внимание на общедоступный номер: технический круг xy