Классические вопросы для интервью на больших фабриках: почему Redis такой быстрый?

предисловие

Привет всем, я маленький мальчик, который собирает улиток. Все мы знаем, что Redis очень быстр, и его QPS может достигать 100 000 (запросов в секунду).Почему Redis такой быстрый, Эта статья будет изучаться с вами.

• публика:маленький мальчик собирает улиток
• гитхаб-адрес, спасибо за каждую звезду

на основе памяти

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

эффективные структуры данных

Мы знаем, что индекс MySQL выбирает структуру данных дерева B+ для повышения эффективности. На самом деле, разумная структура данных может сделать ваше приложение/программу быстрее. Давайте сначала посмотрим на структуру данных и схему внутреннего кодирования Redis:

Простая динамическая строка SDS

struct sdshdr { //SDS简单动态字符串
    int len;    //记录buf中已使用的空间
    int free;   // buf中空闲空间长度
    char buf[]; //存储的实际内容
}

Обработка длины строки

На языке C, чтобы получить捡田螺的小男孩Длина этой строки, ее нужно пройти с самого начала, а сложность — O(n); В Redis уже естьlenПоле записывает длину текущей строки, вы можете получить ее напрямую, а временная сложность — O(1).

Уменьшите количество перераспределений памяти

В языке C изменение строки требует перераспределения памяти.Чем чаще модификация, тем чаще выделение памяти, и выделение памяти будетпроизводительность потребленияиз. В Redis SDS предлагает две стратегии оптимизации: предварительное выделение пространства и отложенное освобождение пространства.

предварительное выделение пространства

При простой динамической модификации строки SDS и расширении пространства помимо выделения необходимого пространства памяти будет выделено дополнительное неиспользуемое пространство. Правила раздачи закваски:

• После изменения SDS, если длина len меньше 1M, будет выделено дополнительное неиспользуемое пространство той же длины, что и len. Например, len=100, после перераспределения фактическая длина buf станет равной 100 (использованное пространство) + 100 (дополнительный пробел) + 1 (нулевой символ) = 201.
• После изменения SDS, если длина len больше 1M, программа выделит 1M неиспользуемого пространства.

Выпуск инертного пространства

Когда SDS укорачивается, вместо освобождения избыточного пространства памяти используйте free для записи избыточного пространства. Последующие операции модификации будут напрямую использовать свободное пространство, чтобы уменьшить выделение памяти.

хэш

В качестве базы данных K-V в памяти Redis использует глобальный хэш для хранения всех пар ключ-значение. Эта хеш-таблица состоит из нескольких хэш-сегментов, и элемент записи в хэш-сегменте хранит*keyи*valueуказатель, где*keyуказывает на фактический ключ,*valueуказывает на действительное значение.

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

У некоторых друзей могут возникнуть сомнения: когда вы записываете в хеш-таблицу большое количество данных, вы не столкнетесь схэш-коллизияПроблема в том, что эффективность упадет.

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

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

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

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

стол для прыжков

Таблица переходов — это структура данных, характерная для Redis, которая на самом деле находится вНа основе связанного списка добавить многоуровневый индексДля повышения эффективности поиска. Таблица переходов простых схем выглядит следующим образом:

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

почтовый список

Сжатый список ziplist — это одна из низкоуровневых реализаций ключей списка и ключей словаря. Это список, состоящий из ряда специально закодированных блоков памяти.Ziplist может содержать несколько записей, и каждая запись может содержать массив символов или целое число ограниченной длины, как показано ниже:

• zlbytes : запись количества байтов памяти, занимаемых всем сжатым списком
• zltail: смещение от хвостового узла до начального узла
• zllen : записать количество узлов, содержащихся во всем сжатом списке.
• entryX: каждый узел, содержащийся в сжатом списке.
• zlend : специальное значение 0xFF (десятичное число 255), используемое для обозначения конца сжатого списка.

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

Разумное кодирование данных

Redis поддерживает различные базовые типы данных, каждый базовый тип соответствует своей структуре данных, а каждая структура данных соответствует разной кодировке. Чтобы повысить производительность, разработчики Redis пришли к выводу, что структура данных является наиболее подходящей кодировкой.

Redis использует объекты (redisObject) для представления значения ключа в базе данных.Когда мы создаем пару ключ-значение в Redis, создаются как минимум два объекта, один объект является ключевым объектом, используемым в качестве пары ключ-значение, а другой — key value Объект значения пары.

//关注公众号：捡田螺的小男孩
typedef struct redisObject{
    //类型
   unsigned type:4;
   //编码
   unsigned encoding:4;
   //指向底层数据结构的指针
   void *ptr;
    //...
 }robj;

редисОбъект,typeСоответствующие типы объектов, включая объекты String, объекты List, объекты Hash, объекты Set и объекты zset.encodingСоответствует кодировке.

• Строка: Если хранится число, оно кодируется в типе int; если хранится нецифровая строка, меньшая или равная 39 байтам, это embstr; если она больше 39 байт, это исходное кодирование.
• Список: если количество элементов в списке меньше 512, значение каждого элемента списка меньше 64 байт (по умолчанию), используйте кодировку ziplist, в противном случае используйте кодировку связанного списка.
• Хэш: количество элементов типа хэш меньше 512. Если все значения меньше 64 байт, используйте кодировку ziplist, в противном случае используйте кодировку хэш-таблицы.
• Набор: если все элементы в наборе являются целыми числами, а количество элементов меньше 512, используйте кодировку intset, в противном случае используйте кодировку хэш-таблицы.
• Zset: когда количество элементов в упорядоченном наборе меньше 128, а значение каждого элемента меньше 64 байт, используйте кодировку ziplist, в противном случае используйте кодировку skiplist (таблицу пропуска).

Разумная многопоточная модель

Однопоточная модель: позволяет избежать переключения контекста

Redis является однопоточным, что на самом деле означаетСетевой ввод-вывод Redis и пара ключ-значение для чтения и записиделается одной нитью. Но другие функции Redis, такие как сохранение, асинхронное удаление, синхронизация данных кластера и т. д., фактически выполняются дополнительными потоками.

Однопоточная модель Redis, которая позволяет избежатьНенужный переключатель контекста ЦПиИспользование конкурирующих замков. Поскольку это один поток, если команда выполняется слишком долго (например, команда hgetall), это вызовет блокировку. Redis — это база данных в памяти для сценариев быстрого выполнения, поэтому такие команды, как lrange, smembers и hgetall, следует использовать с осторожностью.

чтопереключатель контекста?Возьмите каштан:

• Например, вы читаете английский роман, видите определенную страницу, находите слово, которое не можете прочитать, добавляете закладку, а потом идете в словарь. После просмотра словаря вы возвращаетесь и начинаете читать с закладки, и этот процесс очень удобен.
• Если вы читаете эту книгу в одиночестве, у вас все будет хорошо. Но если вы идете к словарю, а кто-то пролистывает вашу книгу и ускользает. Когда вы вернетесь и обнаружите, что книга — это не та страница, на которую вы смотрели, вам придется потратить время, чтобы найти свою страницу.
• Для книги это нормально, если вы посмотрите на нее и назовете ее самостоятельно, но если ее пролистывает много людей, различные этикетки книги будут беспорядочными. Может быть, это объяснение грубое, но правда должна быть такой же.

Мультиплексирование ввода/вывода

Что такое мультиплексирование ввода/вывода?

• Ввод/вывод: сетевой ввод/вывод
• Мультиплекс: Несколько сетевых подключений
• Повторное использование: повторное использование одного и того же потока.
• Мультиплексирование ввода-вывода на самом деле является синхронной моделью ввода-вывода, которая позволяет потоку отслеживать несколько дескрипторов файлов; как только дескриптор файла готов, он может уведомить приложение о выполнении соответствующих операций чтения и записи; и когда дескриптор файла не готов, он блокируется. приложение и передать процессор.

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

механизм виртуальной памяти

Redis напрямую сам строит механизм ВМ, и он не будет вызывать системные функции для обработки, как общая система, и будет тратить определенное количество времени на перемещение и запрос.

Каков механизм виртуальной памяти Redis?

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

Ссылка и спасибо

• VM Механизм Redis
• В этой статье показано, почему однопоточный Redis такой быстрый?
• Insight|Redis является однопоточным, но почему Redis такой быстрый?