Серия статей по анализу исходного кода Redis
Строковая базовая реализация — динамическая строковая SDS
Двусвязный список Redis знает все
Интервьюер: Расскажите о нижнем слое Redis Hash. Я: ... (вопросы интервью от Reading)
предисловие
Всем привет, увидимся в пятницу. За последние несколько недель мы рассмотрели базовые структуры данных Redis, такие как динамическая строка SDS, двусвязный список Adlist и словарь Dict. Если вы не понимаете общие типы или базовые структуры данных Redis, см. портал выше.
Сегодня давайте взглянем на базовую архитектуру ZSET.Если вы не знаете, что такое ZSET, вы можете прочитать первую часть портала выше. Проще говоря, ZSET предоставляется Redis.根据数据和分数来判断其排名структура данных. Наиболее распространенным является рейтинг WeChat Sports, каждому пользователю соответствует свое количество шагов, и рейтинг пользователей может даваться каждую ночь.
Некоторые друзья могут подумать, что если для достижения ранжирования можно использовать различные методы сортировки, нет необходимости вводить структуру ZSET Redis?
Конечно, если используется метод сортировки, та же функция может быть достигнута, но код должен быть жестко запрограммирован, что увеличит рабочую нагрузку и приведет к ошибкам в коде, хахаха. Более того, нижний слой Redis реализован на C, который напрямую манипулирует памятью, а скорость будет улучшена по сравнению с методом Java.
Подводя итог, можно сказать, что использование структуры Redis ZSET дает много преимуществ. Без лишних слов, давайте начнем. Перед официальным стартом нам нужно представить концепцию следующей таблицы переходов, которая является базовой реализацией структуры ZSET. Следующее может быть немного скучным, я постараюсь сделать его простым.
Что такое таблица прыжков?
Для структуры связанного списка с большим объемом данных вставка и удаление выполняются быстрее, но скорость запроса очень низкая. Это связано с тем, что узел нельзя получить напрямую, необходимо начинать с головного узла и использовать следующий указатель узла для получения следующего узла. Даже если данные расположены по порядку, если вы хотите запросить определенные данные, вы можете пройти только переменные от начала до конца, эффективность запроса будет очень низкой, а временная сложность O (n).
Что, если нам нужно быстро запросить связанный список? Некоторые студенты говорят, что они хранятся в массиве, но что, если структура данных не изменена?
Мы можем сначала подумать о дихотомии в структуре упорядоченного массива, каждый раз уменьшая диапазон вдвое, чтобы значительно повысить скорость запроса, а затем можно ли использовать эту идею и в связанном списке.
Это главный герой сегодняшнего разговора — таблица прыжков. (Это также грубое введение в концепцию 😊)
Шаг 1 Создайте упорядоченный список одного ожерелья
Сначала взгляните на упорядоченный односвязный список на рисунке ниже, в котором хранятся 7 элементов 1, 2, 3, 4, 5, 6 и 7.
Шаг 2. Извлеките вторичные индексы
Мы можем извлечь некоторые узлы в связанном списке.На следующем рисунке извлекаются четыре узла 1, 3, 5 и 7, то есть каждые два узла извлекают один узел на верхний уровень, а извлеченный называется индексом.
Обратите внимание, что не всегда возможно нарисовать так идеально, это фактически то же самое, что и подбрасывание монеты, вероятность того, что обе стороны каждой монеты одинаковы, обе равны 1/2. Когда количество данных невелико, вероятность положительных и отрицательных результатов может сильно различаться. Но по мере увеличения количества данных вероятность положительного и отрицательного становится все ближе и ближе к 1/2. Аналогия - это смысл, шанс каждого узла одинаков, либо остаться на исходном уровне, либо извлечь на более высокий уровень, вероятность 1/2. Но по мере увеличения количества узлов извлекаемые узлы становятся все ближе и ближе к 1/2.
Шаг 3. Извлеките узел индекса третьего уровня.
Мы можем извлечь некоторые узлы в связанном списке.На следующем рисунке извлекаются два узла 1 и 5, то есть каждые два узла извлекают один узел на верхний уровень, а извлеченный называется индексом.
Шаг 4: Запрос дихотомии классов
Предположим, что мы хотим найти узел со значением 6. Сначала начнем с индекса третьего уровня, найдем узел со значением 1 и обнаружим, что он меньше 5. Согласно следующему указателю узел со значением 1, найти узел со значением 5, и нет другого после 5. Индекс уровня 3.
Итак, я спустился и нашел вторичный индекс.Согласно следующему указателю узла со значением 5, я нашел узел со значением 7 и обнаружил, что он меньше 6, что указывает на то, что узел 6 должен быть найденное находится в этом диапазоне.
Затем он переходит в позицию индекса первого уровня.Согласно следующему указателю узла со значением 5, он указывает на узел со значением 6. Обнаруживается, что это данные, которые вы хотите запросить, поэтому процесс запроса заканчивается.
Согласно приведенному выше процессу запроса (синяя линия на рисунке ниже) мы обнаружили, что основной идеей метода является дихотомия, которая постоянно сужает область запроса.Если интервал найден в верхнем индексе, он будет идти на следующий слой, чтобы найти реальные данные.
Суммировать
Из всего вышеописанного процесса видно, что при небольшом объеме данных этот метод обмена пространства на время и потребление памяти не является оптимальным решением. Таким образом, структура zset Redis использует сжатую таблицу, когда объем данных небольшой, и использует таблицу перехода, когда объем данных велик.
Структура, подобная этому связанному списку плюс многоуровневый индекс, представляет собой таблицу переходов. Изображение имени, процесс переходит к запросу.
Схема таблицы переходов в Redis
Следующий рисунок представляет собой просто усовершенствование и повторную инкапсуляцию таблицы переходов. Во-первых, вводится понятие заголовка таблицы. Это то же самое, что двусвязный список и структура словаря. Все они представляют собой инкапсуляцию данных, потому что они все указатели, а указатели должны быть. Это приводит к проблеме производительности, поскольку запрос слишком медленный при вычислении длины и получении данных последнего узла, поэтому заголовок инкапсуляции предназначен для повышения скорости в этих задачах, и только время добавление, удаление и другие операции тратятся впустую, по сравнению с этим их можно игнорировать.
Второй - ввести массив слоев, который управляет всеми узлами.Мы видим, что есть 32 слоя, то есть 32 массива, которые совпадают со структурой следующих узлов данных. Он был введен для облегчения поиска каждого элемента непосредственно на основе уровня этого массива.
Во-вторых, каждый уровень узла данных имеет уровень и диапазон (то есть число на стрелке-указателе на рисунке ниже, что для удобства подсчета длины двух узлов).
Последний является обратным указателем узла данных.Цель введения состоит в том, что массив Level имеет только передний указатель, то есть он может указывать только на адрес следующего узла, а обратный указатель должен найти узел обратно .
Приведенное выше изображение в основном разделено на 3 основные части: (Просто посмотрите на него примерно здесь, и код для каждого модуля будет подробно объяснен ниже)
заголовок
В основном он включает четыре атрибута, а именно заголовок указателя головы, хвост указателя хвоста, длину узла и максимальный уровень всех узлов.
заголовок: указывает на узел заголовка таблицы переходов, заголовок можно найти непосредственно по этому адресу указателя, а временная сложность равна O(1).
хвост: указывает на хвостовой узел таблицы переходов, через который хвост таблицы можно найти напрямую, а временная сложность равна O (1).
длина: запишите длину таблицы переходов, то есть сколько элементов во всей таблице переходов без узла заголовка.
уровень: запишите уровень с наибольшим количеством слоев всех узлов в текущей таблице переходов (исключая узел заголовка).
Массив для управления уровнем всех узлов
Его объектное значение пусто, а массив уровней — 32 слоя, цель — управлять реальными узлами данных. Относительно того, какие атрибуты определенного уровня размещены в узле данных.
узел данных
В основном он включает в себя четыре значения объекта атрибута obj, оценку, обратный указатель назад и массив уровней. Количество слоев в массиве уровней каждых данных генерируется случайным образом, что совпадает с упомянутой выше таблицей переходов.
Объект-член obj: реальные фактические данные, данные каждого узла уникальны, но оценки узлов могут быть одинаковыми. Два узла с одинаковой оценкой сортируются в соответствии с размером объекта-члена в словаре, узел с меньшим объектом-членом будет ранжироваться первым, а узел с большим объектом-членом будет ранжирован последним.
Оценка: Число в каждом узле - это оценка, сохраненная узлом.В таблице переходов узлы расположены от меньшего к большему в соответствии с их сохраненными оценками.
Указатель назад: используется для перехода от конца таблицы к началу таблицы, каждый узел имеет только один указатель назад, то есть только один шаг назад за раз.
Иерархический уровень: слова 1, 2, 3 и т. д. используются для обозначения различных уровней узла в узле: L1 представляет первый уровень, L2 представляет второй уровень, L3 представляет третий уровень и так далее.
Определение таблицы пропуска
структура заголовка zskiplist
typedef struct zskiplist {
//表头的头指针header和尾指针tail
struct zskiplistNode *header, *tail;
//一共有多少个节点length
unsigned long length;
// 所有节点最大的层级level
int level;
} zskiplist;Конкретный узел данных zskiplistNode
//跳表的具体节点
typedef struct zskiplistNode {
sds ele; //具体的数据，对应张三
double score;//分数，对应70
struct zskiplistNode *backward;//后退指针backward
//层级数组 struct zskiplistLevel {
struct zskiplistNode *forward;//前进指针forward
unsigned int span;//跨度span
} level[];
} zskiplistNode; Реализация таблицы пропуска (анализ исходного кода)
API Redis для таблицы переходов определен в файле t_zset.c.
Не убегайте, увидев анализ исходного кода, обязательно посмотрите его.
Создать таблицу пропуска
Создание пустой таблицы переходов фактически создает заголовок и массив уровней, который управляет всеми узлами. Во-первых, определите некоторые переменные и попытайтесь выделить место в памяти. Второй — инициализировать уровень и длину заголовка и присвоить 1 и 0 соответственно. Затем создайте массив уровней, которые управляют всеми узлами, вызовите функцию zslCreateNode, входным параметром является макроконстанта размера массива ZSKIPLIST_MAXLEVEL (32), оценка равна 0, а значение объекта равно NULL. (Это ключ к реализации таблицы прыжков). Затем происходит инициализация прямого указателя forword и span для каждого элемента этого массива. Наконец, инициализируйте хвостовой указатель и верните значение.
Вы можете обратиться к следующей схеме и исходному коду:
//创建一个空表头的跳跃表
zskiplist *zslCreate(void) {
int j;
zskiplist *zsl;
//尝试分配内存空间
zsl = zmalloc(sizeof(*zsl));
//初始化level和length
zsl->level = 1;
zsl->length = 0;
//调用下面的方法zslCreateNode,传入的参数有数组长度ZSKIPLIST_MAXLEVEL 32
//分数0，对象值NuLL
//这一步就是创建管理所有节点的数组
//并且设置表头的头头指针为此对象的地址
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
//为这32个数组赋值前指针forward和跨度span
for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
zsl->header->level[j].forward = NULL;
zsl->header->level[j].span = 0;
}
//设置尾指针
zsl->header->backward = NULL;
zsl->tail = NULL;
//返回对象
return zsl;
}
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
zskiplistNode *zn =
zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
zn->score = score;
zn->ele = ele;
return zn;
}
вставить узел
Например, на рисунке ниже 6 элементов, и нужно вставить элемент со значением Чжао Лю и оценкой 101. Давайте подумаем об этом грубо. Общие шаги включают в себя:找到要插入的位置,新建一个数据节点,Потом调整与之相关的头尾指针的level数组. Тогда давайте посмотрим, что делает Redis, отличается ли он от того, что мы думаем?
Dengdengdengdeng, ответ раскрыт. Конечно, большая рама такая же.
Текст начинается: (картинка идет первой)
1. Пройдите массив уровней, который управляет всеми узлами, начиная с самого большого уровня, то есть 3, и сравните значения по одному.Если есть значение с большей оценкой или такая же оценка, но значение данные больше его, запишите их в массив и запишите в тот же промежуток времени.
Это слишком абстрактно. Возьмите приведенное выше изображение в качестве примера, начните с уровня заголовка, который равен 3, сначала перейдите к L3 Чжан Саня и обнаружите, что счет равен 70, что меньше целевого показателя 101. Целевой показатель равен 101. , а Zhao Liu L3 записывается в обновляемом массиве update, а диапазон записи равен 4. Затем перейдите к следующему слою, слою L2 Чжан Саня, обнаружите, что оценка 70 меньше, чем целевая оценка 101, и найдите L2 Ван Ву в соответствии с предыдущим указателем, и обнаружите, что оценка равна 90, что меньше, чем целевую оценку 101 и найти Чжао Лю в соответствии с предыдущим указателем L2, обнаружено, что оценка 102 больше, чем целевая оценка 101, и L2 Чжао Лю записывается в обновление массива для обновления, и запись размах 2. Наконец, перейдите к следующему слою, слою L1 Чжан Саня, логика такая же, как и сейчас, также запишите слой L1 Чжао Лю и диапазон как 1.
2. Случайным образом сгенерируйте количество уровней (с помощью битовой операции) для нового узла.Если сгенерированный уровень больше, чем текущий максимальный уровень 3, он будет проходить большие части одну за другой и записывать диапазон и другую информацию в таблицу обновлений выше.
Например, уровень, созданный новым узлом, равен 5, а текущий максимальный уровень равен 3, что указывает на то, что существует только один узел, и он охватывает все предыдущие узлы, тогда мы пройдем от четвертого и пятого слоев и запишем To. обновляться в обновлении массива.
3. Все приготовления сделаны.Узнайте, куда будет вставлен узел, в каком слое он находится и каков соответствующий диапазон каждого слоя.Далее добавьте узлы данных. Добавьте информацию о предыдущих двух шагах в новый узел и отрегулируйте положение переднего и заднего указателей.
4. Наконец, некоторые завершающие работы, такие как изменение уровня заголовка, размера узла, длины и хвоста указателя, хвоста и других атрибутов.
В общем, весь процесс завершен. Это может показаться немного сложным, вы можете сравнить код ниже.
//插入节点，输入参数为
//zsl:表头
//score:插入元素的分数score
//ele:插入元素的具体数据ele
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
//使用update数组记录每层待插入元素的前一个元素
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
//记录前置节点与第一个节点之间的跨度，即元素在列表中的排名-1
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
serverAssert(!isnan(score));
x = zsl->header;
//从最大的level开始遍历，从顶到底，找到每一层待插入的位置
for (i = zsl->level-1; i >= 0; i--) {
/* store rank that is crossed to reach the insert position */
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
//直接找到第一个分数比该元素大的位置
//或者分数与该元素相同但是对象的ASSICC码比该元素大的位置
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
//将已走过元素的跨越元素进行计数，得到元素在列表中排名，或者是已搜寻的路径长度
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
//记录待插入位置
update[i] = x;
}
//随机产生一个层数，在1到32之间，层数越高，生成的概率越低
level = zslRandomLevel();
//如果产生的层数大于现有的最高层数，则超出层数都需要初始化
if (level > zsl->level) {
//开始循环
for (i = zsl->level; i < level; i++) {
rank[i] = 0;
//该元素作为这些层的第一个节点，前节点就是header
update[i] = zsl->header;
//初始化后这些层每层有两个元素，走一步就是跨越所有元素
update[i]->level[i].span = zsl->length;
}
zsl->level = level;
}
//创建节点
x = zslCreateNode(level,score,ele);
for (i = 0; i < level; i++) {
//将新节点插入到各层链表中
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
// rank[0]是第0层的前置节点P1（也就是底层插入节点前面那个节点）与第一个节点的跨度
// rank[i]是第i层的前置节点P2（这一层里在插入节点前面那个节点）与第一个节点的跨度
// 插入节点X与后置节点Y的跨度f(X,Y)可由以下公式计算
// 关键在于f(P1,0)-f(P2,0)+1等于新节点与P2的跨度，这是因为跨度呈扇形形向下延伸到最底层
// 记录节点各层跨越元素情况span, 由层与层之间的跨越元素总和rank相减而得
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
// 插入位置前一个节点的span在原基础上加1即可(新节点在rank[0]的后一个位置)
update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}
/* increment span for untouched levels */
for (i = level; i < zsl->level; i++) {
update[i]->level[i].span++;
}
// 第0层是双向链表, 便于redis常支持逆序类查找
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}Получить рейтинг узла
Я беспокоюсь, что все забыли эту картинку, поэтому я вставлю ее снова. Как показано на рисунке ниже, эта часть логики относительно проста, поэтому я не буду ее расписывать, за подробностями обратитесь к анализу кода.
//得到节点的排名
//输入参数为表头结构zsl，分数score，真正的数据ele
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
zskiplistNode *x;
unsigned long rank = 0;
int i;
//先获取表头的头指针，即找到管理所有节点的level数组
x = zsl->header;
//从表头的level，即最大值开始循环遍历
for (i = zsl->level-1; i >= 0; i--) {
//如果找到分数小于目标分数的，排名加上其跨度
//或者分数相同，但是具体数据小于目标数据的，排名也加上跨度
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) <= 0))) {
rank += x->level[i].span;
x = x->level[i].forward;
}
//确保在第i层找到分值相同，且对象相同时才会返回排位值
if (x->ele && sdscmp(x->ele,ele) == 0) {
return rank;
}
}
return 0;
}Эпилог
В этой статье в основном рассказывается о базовой реализации таблицы переходов типа данных ZSET Redis.Во-первых, что такое таблица переходов, вводятся концепция и структура данных таблицы переходов, анализируются ее основные компоненты, а затем объясняется с помощью нескольких диаграмм процессов. Как работает Redis? При разработке таблицы переходов, наконец, опишите таблицу переходов в сочетании с исходным кодом, например, процесс создания, процесс добавления узлов, процесс получения определенного рейтинга узлов , а также перемежающиеся примеры и схемы процессов.
Если вы считаете, что сочинение в порядке, пожалуйста, поставьте лайк 👍, ваше одобрение является движущей силой для моего письма!
Если вы считаете, что что-то не так, пожалуйста, прокомментируйте.
Хорошо, пока.