вперед от: "Redis Quest: выберите правильную структуру данных, чтобы сократить использование памяти на 80%》- Wu Weifeng JD Retail
Практические навыки, легкое для понимания и практическое обучение, достойное ссылки
предисловие
Как самая популярная база данных кэширования nosql в настоящее время, Redis стал предпочтительным инструментом кэширования в большинстве сценариев благодаря своей превосходной производительности и богатой структуре данных.
Поскольку Redis является纯内存база данных, в которой хранятся大量数据, использование памяти будет очень значительным. Затем в некоторых сценариях, выбрав合适数据结构хранить, можно大幅Уменьшите использование памяти и даже уменьшите использование памяти на 80%-99%.
Используйте zipList для замены большого количества ключей-значений
Давайте сначала посмотрим на сцену: в рекламной системе DSP и системе массового пользователя мы часто сталкиваемся с таким спросом.唯一标识быстрый查к用户id. Например, по mac-адресу или uuid или md5 номера мобильного телефона, чтобы запросить id пользователя.
Для него характерно большое количество данных, десятки миллионов или миллиардов, а ключ представляет собой относительно длинную строку, например 32-битный md5 или uuid.
Если он не обрабатывается и хранится напрямую в виде ключ-значение, мы можем его просто протестировать, вставить в редис 10 млн штук данных, 1550000000 — 1559999999, форма ключ (md5 (1550000000)) → значение (1550000000) .
Затем используйте команду внутри Redisinfo memoryПосмотрите на использование памяти.
Видно, что эти 10 миллионов фрагментов данных занимают в общей сложности 1,17 ГБ памяти Redis. Когда объем данных достигает 100 миллионов, фактическое измерение занимает около 8 Гб.
Для того же пакета данных давайте изменим метод хранения и сначала посмотрим на результаты:
После того, как мы используем zipList, использование памяти составляет 123 МБ, что уменьшает использование пространства примерно на 85%.Как это сделать?
Анализируется базовое хранилище Redis.
структура данных Redis и кодировка
Как Redis хранит строки
Строка является наиболее часто используемой структурой данных в Redis. Строка Redis по умолчанию отличается от строки языка C. Он сам по себе создает абстрактный тип, называемый «Simple Dynamic String SDS».
В зависимости от базового хранилища строк Redis разделяет три метода, а именно int, embstr и raw.
Например, set k1 abc и set k2 123 будут использовать embstr и int соответственно. Когда длина значения больше 44 (или 39, разные версии разные) байт, используется raw.
int — это структура фиксированной длины, занимающая 8 байт (обратите внимание, что она эквивалентна long в java) и может использоваться только для хранения длинных целых чисел.
embstr динамически расширяется, и емкость каждый раз удваивается. Когда она превышает 1 М, она каждый раз увеличивается только на 1 М.
raw используется для хранения строк размером более 44 байт.
Конкретно в нашем случае ключ представляет собой 32-байтовую строку (embstr), а значение — длинное целое число (int), так что если 32-битный md5 можно превратить в int, то ключ можно хранить напрямую. использование памяти на 3/4.
Это первая точка оптимизации.
Как Redis хранит хэш
На рисунке 1.1 мы видим структуру данных Hash, существует два метода кодирования: 1 — это hashTable, 2 — это zipList.
Все знакомы с hashTable, который очень похож на hashMap в java, это метод массив + связанный список. Чтобы уменьшить конфликты хэшей, хеш-карта в java устанавливает коэффициент загрузки равным 0,75. Точно так же хэш Redis имеет аналогичный коэффициент масштабируемой нагрузки. Я не упоминаю детали, просто оставьте впечатление.Если вы используете кодировку hashTable, для хранения данных потребуется не менее 25% места. Это выглядит так:
zipList, сжатый связанный список, выглядит так:
Видно, что самая большая особенность zipList заключается в том, что это вообще не хеш-структура, а относительно длинная строка, причем ключи-значения размещаются по порядку в длинной строке для хранения. Если вы хотите найти ключ, просто пройдите всю длинную строку напрямую.
Таким образом, очевидно, что zipList занимает гораздо меньше места, чем hashTable. Но это будет потреблять больше процессора для запроса.
Итак, когда использовать hashTable, zipList? В файле redis.conf можно найти:
То есть, когда количество внутренних полей-значений этой хеш-структуры не превышает 512, а количество байтов значения не превышает 64, используется zipList.
При фактическом измерении, когда количество значений равно 512, производительность почти такая же, как у простой хеш-таблицы, Когда количество значений не превышает 1024, производительность лишь немного снижается, что может быть игнорируется во многих случаях.
И использование памяти, zipList может быть значительно меньше, чем hashTable.
Это второй пункт оптимизации.
Используйте zipList вместо ключ-значение
Из вышеизложенного мы пришли к двум выводам. Использование int в качестве ключа сэкономит больше места, чем строка. Использование zipList в хэше сэкономит больше места, чем ключ-значение.
Затем давайте преобразуем исходные 10 миллионов пар "ключ-значение".
первый шаг:
Нам нужно поместить 10 миллионов пар ключ-значение в N сегментов, каждый сегмент представляет собой хэш-структуру данных redis, и каждый сегмент не должен превышать 512 элементов по умолчанию (если файл конфигурации изменен, например, 1024, он не может превышать измененный значение), чтобы избежать изменения метода кодирования хэша с zipList на hashTable.
10 миллионов / 512 = 19531. В дальнейшем все ключи будут хешироваться для максимально возможного распределения по всем корзинам, но из-за неопределенности хэш-функции возможно не совсем равномерное распределение. Таким образом, мы должны зарезервировать некоторое пространство, например, я выделяю 25 000 ведер или 30 000 ведер.
Шаг 2:
Используйте алгоритм хеширования, чтобы решить, в какое ведро поместить ключ. Здесь мы используем эффективный и сбалансированный известный алгоритм crc32.Этот хеш-алгоритм может превратить строку в длинное число.После получения crc32 ключа типа md5, а затем взятия остатка от количества сегментов, вы может определить, в какое ведро должен быть помещен ключ.
третий шаг:
На втором шаге мы определяем внешний ключ хеш-структуры в редисе, где будет храниться ключ.Для внутреннего поля мы выбираем другой алгоритм хеширования, чтобы избежать двух совершенно разных значений.Через crc32(key) % После COUNT, поле снова остается прежним, что приводит к конфликту хэшей, из-за которого значение перезаписывается. Мы используем хэш-алгоритм bkdr (или напрямую используем hashCode Java) для внутреннего поля, которое также получит длинное целое число. Хранение значения остается неизменным.
четвертый шаг:
Загрузить данные. Исходная структура данных — это ключ-значение, 0eac261f1c2d21e0bfdbd567bb270a68 → 1550000000.
Текущая структура данных — хеш, ключ — 14523, поле — 1927144074, значение — 1550000000.
Благодаря фактическим измерениям после того, как 10 миллионов данных хранятся в 25 000 сегментов, общий хэш относительно сбалансирован, и в каждом сегменте содержится около 300 пар «ключ-значение поля». Теоретически, если одно и то же значение генерируется после того, как алгоритм хеширования не повторяется дважды, исходное значение может быть полностью найдено по ключевому полю. В этом можно убедиться, подсчитав общую сумму. На самом деле, когда количество бакетов велико, а количество значений в каждом бакете невелико, вероятность непрерывной коллизии крайне мала.Фактически измерено, что явных коллизий не бывает, когда 5 миллиардов номеров мобильных телефонов хранятся.
Тестовая скорость запроса:
После сохранения 10 миллионов фрагментов данных мы провели тест запроса, используя тип ключ-значение и тип хэша для запроса 1 миллиона фрагментов данных соответственно, чтобы увидеть влияние на скорость запроса.
время ключ-значение: 10653, 10790, 11318, 9900, 11270, 11029 миллисекунд
время хэш-поля: 12042, 11349, 11126, 11355, 11168 миллисекунд.
Видно, что после того, как хеш-хранилище используется целиком, время, затрачиваемое на запрос 1 миллиона записей, увеличивается менее чем на 500 миллисекунд. Влияние на производительность минимально. Но использование памяти изменилось с 1,1 Гб до 120 Мб, что позволило сэкономить около 90% памяти.
Суммировать
Большое количество ключей-значений занимает слишком много ключей, чтобы справиться с коллизиями хэшей в redis, нужно больше места для хранения этих данных ключ-значение.
Если длина ключа различна, например, некоторые из них 40 бит, а некоторые 10 бит, из-за проблем с выравниванием будут генерироваться огромные фрагменты памяти, и использование пространства будет более серьезным. Следовательно, сохранение одинаковой длины ключа (например, одинаковое использование типа int и фиксированной длины 8 байтов) также поможет использовать память.
Строковый тип md5 занимает 32 байта. После хэш-алгоритма 32 сокращается до 8-байтового целого числа, что значительно уменьшает занимаемое пространство ключа.
По сравнению с hashTable, zipList значительно сокращает использование памяти, его хранилище очень компактно и мало влияет на эффективность запросов. Таким образом, вы должны эффективно использовать zipList, чтобы избежать хранения более 512 элементов значения поля в хеш-структуре.
Если значение представляет собой строку, объект и т. д., вы должны попытаться использовать byte[] для его хранения, что также может значительно сократить использование памяти. Например, алгоритм сжатия Google Snappy можно использовать для преобразования строк в byte[], который очень эффективен и имеет высокую степень сжатия.
Чтобы уменьшить предварительное выделение и расширение строк с помощью redis (удваивание каждый раз), вызывающее фрагментацию памяти, не следует использовать append, setrange и т. д. Вместо этого используйте set напрямую, чтобы заменить оригинал.
Недостатки программы:
Хэш-структура не поддерживает настройки времени ожидания для отдельных полей. Однако удалением можно управлять с помощью кода, и нет такой заботы о долговременном хранении данных, не требующем тайм-аута.
Существует небольшая вероятность конфликта хэшей, и этот метод сжатия не подходит для случаев, когда требуются очень точные данные.
Основываясь на приведенном выше решении, я переписал redisTemplate исходного кода Springboot и предоставил класс CompressRedisTemplate, который можно использовать непосредственно как redisTemplate.Он автоматически преобразует ключ-значение в хэш для хранения для достижения вышеуказанной цели.
Позже, основываясь на более экстремальных сценариях, таких как подсчет независимых посетителей, мы посмотрим, как необычная структура данных Redis снижает использование памяти с 20 Гб до 5 Мб.
Для случая кода, пожалуйста, свяжитесь с автором:wuweifeng10@jd.com