[Золото Три Серебро Четыре] Базовая реализация горячих точек интервью Redis

0. Предисловие

Автор работает лихорадочно и даже немного тревожно, вплоть до бессонницы, а так как времени на изучение нового нет, то нахожу время подытожить увиденное.

Планируется разделить на три статьи, чтобы разобраться с горячими проблемами, связанными с Redis.На этот раз это статья о реализации нижнего уровня Kaishan.Из этой статьи вы узнаете следующее:

Автор, эволюция и статус Redis
Обзор вопросов интервью Redis

Проблемы, связанные с базовой реализацией Redis, включают:

  **常用数据类型底层实现、SDS的原理和优势、字典的实现原理、跳表和有序集合的原理、Redis的线程模式和服务模型**

Советы:Содержание не сложное, боюсь вы не прочитаете.

Если вы не понимаете, вы можете сначала собрать Марк, а затем перевернуть его, когда у вас будет время для более глубокого исследования.Вы обнаружите, что это действительно 24К галантереи! Перестаньте хвастаться и напишите что-нибудь другое!

1. Прошлое Redis

Redis — это сетевая высокопроизводительная база данных с открытым исходным кодом, работающая в памяти и написанная на языке ANSI C с дополнительным сохранением. Отец Редиса из Сицилии, Италия.Salvatore Sanfilippo, на гитхабе название антирез, автор нашел краткую информацию об авторе и перевел ее, как показано на рисунке:

Redis прошло 10 лет с момента выхода первой версии в 2009 году, и Redis по-прежнему остается одной из самых популярных баз данных в памяти.

Отличные проекты с открытым исходным кодом неотделимы от поддержки крупных компаний, до мая 2013 года их разработкой занималасьVMwareСпонсируется и разрабатывается в период с мая 2013 г. по июнь 2015 г. компаниейБеверлиСпонсирует с июня 2015 года разработку Redis компаниейRedis Labsспонсор.

Автор также использовал некоторые другие NoSQL, и некоторые из них поддерживают очень один тип значения, поэтому многие операции должны быть реализованы на стороне клиента.Например, значение представляет собой структурированные данные.Если вам нужно изменить одно из полей, нужно прочитать его целиком, а потом модифицировать.Общее написание очень громоздко, но значение Redis поддерживает несколько типов, и многие операции могут быть выполнены на стороне сервера, что очень удобно для клиента.

Конечно, поскольку Redis является базой данных в памяти, объем хранилища данных ограничен, а стоимость распределенных кластеров очень высока, поэтому многие компании разработали системы, подобные Redis на основе SSD, например, 360 разработали SSDB, Pika и другие базы данных , но я думаю, что Сложность от 0 до 1 больше, чем сложность от 1 до 2 Да, нет никаких сомнений в том, что Redis — это сильный удар в NoSQL, и он стоит нашего глубокого изучения и использования.

2. Статус Redis

Redis предоставляет Java, C/C++, C#, PHP, JavaScript, Perl, Object-C, Python, Ruby, Erlang, Golang и т. д. Клиенты на нескольких основных языках , поэтому в каком бы языковом стеке ни находился пользователь, он всегда найдет своего клиента, а аудитория очень широкая.

Автор заглянул на сайт datanyze.com и посмотрел на Redis и MySQL. Последние доли рынка и рейтинги контраст и Количество развертываний топовых сайтов мира Сравнение (данные сайта обновлены до 11.12.2019 на день написания):

можно увидеть Redis занимает 9-е место по общей доле и практически такое же, как MySQL по количеству развертываний на 100 лучших сайтах мира. , поэтому Redis по-прежнему имеет определенный статус на арене.

3. Расскажите о настоящем бою

В настоящее время стабильная версия, выпущенная Redis, достигла 5.x, а ее функции становятся все более и более мощными.С точки зрения отечественных и зарубежных интернет-компаний Redis является почтиСтандарт. Как разработчик, вероятность столкнуться с проблемами, связанными с Redis, в ежедневных письменных собеседованиях и работе очень высока, и очень важно овладеть знаниями, связанными с Redis.

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

Точки практических знаний Redis можно просто разделить натри уровня:

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

Глубокое понимание и квалифицированное использованиеRedisНа обучение нужно время,Это не просто сделать на кончиках ваших пальцев, Если вы хотите прорваться за короткое время, вы можете начать только с горячих тем.Хотя это выглядит немного утилитарно, это понятно.Чтобы есть, мы все же склонны прощать нашу ленивую самость, или иначе есть земля и пить ветер?

4. Базовая реализация горячих тем

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

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

Пять часто используемых типов данных, поддерживаемых Redis, относятся к типу значения, а именно:Строка Строка, Список Список, Хэш Хэш, Набор коллекций, Упорядоченная коллекция Zset, но в будущем Redis обогатит несколько типов данных, а именно растровые изображения,HyperLogLogs, ГЕО.

Поскольку Redis написан на основе стандарта C и имеет только самые основные типы данных, Redis разработал свой собственный, чтобы соответствовать пяти типам данных, используемым извне.Уникальный набор базовых структур данных, используя эти структуры данных для реализации 5 типов данных.

Базовые структуры данных Redis включают:Простой динамический массив SDS, связанный список, словарь, переходный связанный список, набор целых чисел, упакованный список, объект.

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

Как видно из рисункаzip-список zip-списокЕго можно использовать в качестве базовой реализации трех типов данных Zset, Set и List. Он кажется очень мощным. Сжатие списка — это способ Последовательная структура данных непрерывного блока памяти, разработанная для экономии памяти и специально закодированная , основная структура все еще относительно сложна.

Q2: Каковы преимущества SDS Redis по сравнению со строками в C?

В языке C массив символов длиной N+1 используется для представления строки, а '\0' используется в качестве маркера конца в конце. Для этой реализацииНевозможно удовлетворить требования Redis к безопасности, эффективности и богатым функциям., поэтому Redis отдельно инкапсулирует простую динамическую строковую структуру SDS.

Прежде чем понять преимущества SDS, вам нужно взглянуть на SDS.детали реализации, нашел гитхабпоследний src/sds.hПосмотрите на определение:

`typedef char *sds;`

`/*这个用不到 忽略即可*/
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
`

`};`

`/*不同长度的header 8 16 32 64共4种 都给出了四个成员
len：当前使用的空间大小；alloc去掉header和结尾空字符的最大空间大小
flags:8位的标记 下面关于SDS_TYPE_x的宏定义只有5种 3bit足够了 5bit没有用
buf:这个跟C语言中的字符数组是一样的，从typedef char* sds可以知道就是这样的。
buf的最大长度是2^n 其中n为sdshdr的类型，如当选择sdshdr16，buf_max=2^16。
*/
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3
`

Прочитав предыдущее определение, автор нарисовал картину:

Из рисунка видно, что sds по существу делится на три части:заголовок, buf, нулевой терминатор, заголовок можно рассматривать как направляющую часть всей sds, учитывая размер используемого пространства, максимальный размер выделения и другую информацию, а затем использовать картинку в Интернете, чтобы увидеть ясно Экземпляр sdshdr8 :

Полные детали реализации sds хорошо видны в исходниках sds.h/sds.c.Эта статья не будет расширяться, иначе места будет слишком много.Давайте быстро войдём в тему и поговорим об этом.Преимущества сдс:

O(1) получить длину : строки C необходимо пройти, а len в sds можно получить напрямую;
предотвратить переполнение буфера : Когда sds необходимо изменить строку, сначала проверьте, соответствует ли пространство требованиям для модификации с помощью len и alloc.Если места недостаточно, SDS Автоматически расширять пространство , чтобы избежать перезаписи, как в строковых операциях C;
Эффективно сократить количество выделений памяти : Строка C изменит размер базового массива, когда она включает операции добавления или очистки, что приводит к перераспределению и использованию sds. Предварительное выделение пространства и отложенное освобождение пространства Механизм, грубо говоря, заключается в том, что каждый раз, когда он расширяется, он умножается на несколько распределений.Он также сначала резервируется и официально не возвращается в ОС при уменьшении.Эти два механизма также относительно просты для понимания. ;
бинарный сейф : Строки языка C могут сохранять только код ascii, но не могут сохранять изображения, аудио и другую информацию. бинарный сейф Да, что пишется, то и читается, без всяких фильтров и ограничений;

В старых правилах есть картина, подытоженная Хуан Цзяньхуном:

Q3: Как реализован словарь Redis? **** Кратко опишите процесс прогрессивного перефразирования.

Словарь является звездой среди распространенных типов данных в Redis 5. Как упоминалось ранее, словарь может быть реализован на основе ziplist и хеш-таблицы. Мы обсуждаем толькоРеализация на основе хеш-таблицыпринцип.

словарь - этоИерархические типы данных, как показано на рисунке:

Для общей концепции давайте взглянем на последний файл src/dict.h.определение исходного кода:

`//哈希节点结构
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

//封装的是字典的操作函数指针
typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
//哈希表结构 该部分是理解字典的关键
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

//字典结构
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;
`

Преимущество языка C в том, что определение должно быть снизу наружу, поэтому мы можем видеть очевидное изменение уровня, поэтому автор рисует другую картинку, чтобы показать конкретнуюуровеньконцепция:

О dictEntry

dictEntry — это узел хеш-таблицы, то есть там, где мы храним данные, а его защищенными членами являются: ключ, v, следующий указатель. key содержит ключ в паре ключ-значение, v содержит значение в паре ключ-значение, и значение может быть указателем или uint64_t или int64_t. next — это указатель на другой узел хэш-таблицы.Этот указатель может одновременно соединять несколько пар ключ-значение с одним и тем же хеш-значением, чтобы разрешать коллизии хешей Проблема.

На рисунке показаны отношения соединения между двумя конфликтующими хэш-узлами:

О диктте

Из исходного кода хеш-таблица включает в себя таблицу, размер, используемый и размерную маску. table представляет собой массив, каждый элемент массива является указателем на структуру dictEntry, каждая структура dictEntry содержит пару ключ-значение, атрибут size записывает размер хэш-таблицы, а атрибут used записывает хеш-таблицу. существующих узлов в таблице. sizemask равен size-1, а хеш-значение вычисляет индекс ключа в массиве таблиц, который используется при вычислении индекса.

На приведенном выше рисунке показана ситуация с хэш-узлом в таблице размера 4, где k1 и k0 имеют конфликт хэшей с индексом = 2, и существует открытый связанный список, который, по сути, k0 хранится первым, Размещение K1 является конфликтным для обеспечения эффективности и помещается непосредственно в начало конфликтующего списка, поскольку список не имеет хвостового указателя. .

О дикт

Из исходного кода мы видим, что структура dict является определением словаря, а в нее включены следующие члены: type, privdata, ht и rehashidx. Тип указателя dictType указывает на API словаря операций, который можно понимать как указатель на функцию. ht — это массив, содержащий 2 словаря , то есть словарь содержит две хеш-таблицы, переменные, используемые rehashidx для повторного хеширования, и privdata, используемые в сочетании с функцией, на которую указывает dictType в качестве параметра, так что у вас есть предварительное представление о нескольких членах словаря.

Алгоритм хеширования словаря

`//伪码：使用哈希函数，计算键key的哈希值
hash = dict->type->hashFunction(key);
//伪码：使用哈希表的sizemask和哈希值，计算出在ht[0]或许ht[1]的索引值
index = hash & dict->ht[x].sizemask;
//源码定义
#define dictHashKey(d, key) (d)->type->hashFunction(key)
`

Redis использует алгоритм MurmurHash для вычисления хэш-значений, который был первоначально изобретен Остином Эпплби в 2008 году,MurmurHashНезависимо от входных данных, алгоритм может дать значение хеш-функции с хорошим случайным распределением, а скорость вычислений очень высока.MurmurHash2 иMurmurHash3 и другие версии.

Обычная перефразировка

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

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

Выделить место для хеш-таблицы словаря ht[1]. Объем выделенного пространства зависит от выполняемой операции и количества пар ключ-значение, содержащихся в данный момент в ht[0]: Во время операции раскрытия размер ht[1] на первые 2^n больше или равен ht[0].used*2; Размер ht[1] во время операции сжатия на первые 2^n больше или равен ht[0].used;

При расширении, таком как h[0].used=200, вам нужно выбрать первую степень числа 2 больше 400, то есть 2^9=512.
Пересчитать хеш-значение и значение индекса ключа и перехешировать все пары ключ-значение, хранящиеся в ht[0], в ht[1];
Повторяйте перехеширование до тех пор, пока все пары ключ-значение, содержащиеся в ht[0], не будут перенесены в ht[1] и освободите ht[0], установите для ht[1] значение ht[0] и создайте новый пробел в ht[1] Надежда , будьте готовы к следующему перефразированию.

Прогрессивный процесс перефразирования

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

В этом случае Redis принимаетпрогрессивная перефразировка, подробные шаги процесса:

Выделить место для ht[1], этот процесс ничем не отличается от обычного Rehash;
Установка rehashidx на 0 означает, что работа по перехэшированию официально начинается, и этот rehashidx увеличивается, начиная с 0 означает, что перехеширование начинается с первого элемента массива.
Во время перефразирования каждый разСловарь выполняет операции добавления, удаления, модификации и поиска.час, кстати Перехешируйте пару ключ-значение в индексе rehashidx хеш-таблицы ht[0] до ht[1]. После завершения добавьте 1 к rehashidx, чтобы указать на следующую пару ключ-значение, которую необходимо перехэшировать.
При непрерывном выполнении операции со словарем все пары ключ-значение ht[0] будут повторно хешированы в ht[1], а затем значение атрибута rehashidx устанавливается равным -1, чтобы указать, что операция повторного хэширования была завершена. завершенный.

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

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

Q4: Вы понимаете список прыжков? Как Zset в Redis реализован с использованием таблицы пропуска?

Тип данных ZSet также очень полезен. Он очень полезен для требований ранжирования. Автор однажды использовал этот тип данных для ранжирования приложения с ежедневным энергопотреблением 2000 Вт, поэтому необходимо понимать базовую реализацию ZSet. , Перед автором я написал две статьи, чтобы представить реализацию переходного связанного списка и ZSet, так что просто проверьте это.

Q5: Почему Redis использует один поток? Расскажите о сетевой модели Redis и о том, как один поток координирует выполнение различных событий?

Redis не является чистым однопоточным сервисом в новой версии, некоторые вспомогательные работы будут выполнятьсяФоновая ветка БИОдля завершения, а базовый RedisИспользование epoll для реализации шаблона реактора, управляемого событиями, во всем основном потоке, выполняющем проектНепрерывная координация временных и файловых событийДля полноценной работы всей системы автор ранее написал две статьи по теме, и вы можете получить более подробные ответы, проконсультировавшись.