Примечание. Версия исходного кода Redis, проанализированная в этой серии статей:GitHub.com/SID судьба/Горячие…, является последней версией на момент публикации статьи.
Все мы знаем, что пятью часто используемыми структурами данных Redis являются: string (строка), hash (хэш), list (список), set (набор) и sorted set (сортированный набор). Условно говоря, отсортированный набор (далее zset) используется относительно мало, но его структура реализации очень интересна, эта структура называется skiplist skiplist, и я объясню ее позже на примере из повседневной жизни.
Прежде всего, я кратко представлю, что такое zset и для чего он полезен.Если вы уже знаете о детской обуви, вы можете перейти непосредственно к следующей главе.
Тип данных упорядоченного набора, аналогичный комбинации набора и хэша. Отсортированные множества, как и множества, имеют уникальные элементы. И каждый элемент в отсортированном наборе может соответствовать значению оценки, так что это тоже похоже на хэш-таблицу. Кроме того, элементы в отсортированном наборе можно сортировать и просматривать в соответствии со значением оценки.
zset
Прочитав приведенное выше введение, вы, возможно, догадались, что zset — это комбинация двух структур данных, что объясняется в комментариях к исходному коду:
Zset — это упорядоченный набор, который использует 2 структуры данных для хранения одних и тех же элементов, а также гарантирует O(log(N)) операций вставки и удаления. Элементы в Zset добавляются в хэш-таблицу, содержащую сопоставление объекта Redis и оценки. В то же время эти элементы добавляются в список пропусков, который сопоставляет оценку с объектами Redis (объекты сортируются по оценке).
Обратите внимание на это предложение: «В то же время операции вставки и удаления со сложностью O(log(N)) могут быть гарантированы». гордость, проявленная в ее словах, пожалуйста, запомните это, я также упомяну об этом ниже. Хеш-таблица (хэш), которая была проанализирована в предыдущих статьях, вы можете проверить мою статью для деталей"[Самая полная серия] Статьи-словарь Redis-структуры", так что больше объяснять не буду, далее сосредоточусь на анализе skiplist.
skiplist
Списки пропуска придумали давно, если интересно, можете почитать [его историю] (Списки пропуска: вероятностная альтернатива сбалансированным деревьям). Во-первых, это список по именам, и, как мы уже говорили, он по-прежнему упорядочен. В общем виде упорядоченный связанный список выглядит так:
Крайний левый узел — это пустой головной узел, а а — это имя, которое я получил сам, что удобно для различения.
Подумайте о том, что нам нужно сделать, чтобы вставить новый элемент "23". Во-первых, нам нужно пройти по связанному списку и сравнить элементы узла, пока мы не найдем элемент больше, чем "23", поэтому сложностьO(N), это тоже правда удалить элемент.Обнаружили ли вы, что на самом деле, после добавления и удаления, это процесс запроса.
С этой целью, если мы проведем небольшую оптимизацию и немного изменим структуру связанного списка, добавим указатель на соседний узел, чтобы он указывал на следующий узел:
На приведенном выше рисунке видно, что формируется новый связанный список b (7 - 19 - 26), а количество узлов соответствует исходному связанному списку. В это время мы повторно запрашиваем «23»:
- Пройдите по связанному списку b и найдите первый элемент «26» больше 23.
- Вернитесь к связанному списку a и обнаружите, что 21 меньше 23, поэтому оно вставлено между узлами «21» и «26».
Вы заметили, что он очень похож на бинарный поиск, в конце концов мы уменьшаем количество запросов, и мы даже можем снова создать новый связанный список c:
Шаг запроса в это время становится:
- Проходя по связанному списку c, мы обнаруживаем только один элемент «19», и оказывается, что 23 больше 19, поэтому ищите его после «19».
- Вернитесь к связанному списку b и найдите первый элемент «26» больше 23.
- Вернитесь к связанному списку a и обнаружите, что 21 меньше 23, поэтому оно вставлено между узлами «21» и «26».
Можно обнаружить, что количество элементов, которые мы просматриваем, постепенно уменьшается.Можно предположить, что если количество содержащихся элементов достаточно велико, эффективность запроса значительно повысится. Ниже я привожу пример из повседневной жизни, чтобы проиллюстрировать преимущества такого подхода:
Процесс запроса элемента в упорядоченном связанном списке подобен подъему на лифте в гостинице. Если гостиница 10-этажная, то с 1-го по 5-й этажи занимают общие апартаменты, и там проживает много людей; Я живу на 9-м этаже (хе-хе), поэтому, когда я поднимусь на лифте на 1-й этаж, я, вероятно, остановлюсь на нижних этажах (потому что на нижних этажах живет много людей), что определенно не хорошо для высоких этажей. поднять гостей. Позже гостиницу поменяли, лифт построили заново, разделив его на одинарные и двойные остановки, для меня он должен быть быстрее, чем раньше, но 1, 3 и 5 этажи все равно будут останавливаться часто и высоко- Уровень гостей по-прежнему не устраивает. После этого в отеле отлично поработали, прямо построили лифт с 1-го на 5-й этаж на верхний этаж без остановок.Это было удобно, и оценка клиентов сразу пошла вверх.
Если вы понимаете приведенный выше пример, то фактически обнаружили недостаток такого подхода: нужно строить больше «лифтов», то есть нужно создавать больше связанных списков, что называется «пространство для времени».
Наш список пропусков разработан на основе приведенного выше многоуровневого связанного списка. Фактически, в соответствии с описанным выше методом создания связанного списка количество узлов в каждом слое приведенного выше связанного списка составляет половину количества узлов в следующем слое, что аналогично бинарному поиску, так что время сложность поиска может быть снижена доO(log n) (помните ту сложность, которую я заставил вас вспомнить ранее?). Однако у этого метода есть большая проблема при вставке данных. После вставки нового узла соотношение количества узлов в верхнем и нижнем смежных связанных списках 2:1 будет уничтожено. Чтобы сохранить это соответствие, необходимо перенастроить все узлы за вновь вставленным узлом (включая вновь вставленный узел), что снижает временную сложность доO(n), а также удаление узлов.
Разумеется, шиплист тоже учитывает эту проблему, по этой причине он не требует строго пропорционального соотношения между количеством узлов между верхним и нижним смежными связанными списками, а каждый узел имеет случайное количество уровней уровня. Например, если количество слоев, случайно сгенерированных узлом, равно 3, то он связывается в трехслойный связанный список со слоями с 1 по 3. Чтобы было понятно, на следующем рисунке показано, как сформировать список пропуска с помощью пошаговой операции вставки:
Чтобы уменьшить сомнения в отношении детской обуви, я сначала суммирую 3 характеристики описанного выше процесса:
- Связанный список первого уровня всегда содержит наиболее полные данные элемента.
- Элемент, расположенный в n-м слое, также должен находиться в слое 1~n-1.
- Вставка нового элемента не влияет на слои других элементов.
Предупреждение о высоком ореоле впереди, следующее содержание включает в себя некоторые знания о вероятности и математике, взятые из статьи изобретателя. Вы можете сразу перейти к следующей главе.
Интересным моментом является то, что количество слоев элементов является случайным, а это означает, что список пропусков является «вероятностной» структурой данных. Фактически, случайное вычисление, определяющее количество слоев, оказывает большое влияние на производительность поиска в таблице пропуска.Это не обычное случайное число, которое подчиняется равномерному распределению.Процесс его вычисления выглядит следующим образом:
- Задайте максимальный уровень MaxLevel узла, задайте вероятность p, и уровень по умолчанию равен 1 .
- Сгенерировать случайное число r от 0 до 1. Если r
- Повторяйте шаг 2 до тех пор, пока не будет сгенерировано r > p, где уровень — это количество слоев, которые необходимо вставить.
Псевдокод выглядит следующим образом:
randomLevel()
level = 1
// random()返回一个[0...1)的随机数
while random() < p and level < MaxLevel do
level := level + 1
return level
В реализации списка пропусков Redis p=1/4, MaxLevel=64.
структура исходного кода
Redis внес некоторые изменения в инфраструктуру списка пропуска, чтобы удовлетворить свои потребности, сначала покажите исходный код:
#define ZSKIPLIST_MAXLEVEL 64 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4 */
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
ZSKIPLIST_MAXLEVELа такжеZSKIPLIST_PДве константы — это последняя часть, которую мы упомянули в предыдущей главе.
| Атрибуты | имея в виду |
|---|---|
| header | указатель |
| tail | хвостовой указатель |
| length | Длина связанного списка, то есть общее количество узлов, содержащихся в связанном списке, за исключением указателя на начало. |
| level | Общее количество слоев в списке пропусков |
Почему zskiplistNode имеет только один прямой указатель назад?
Я обнаружил, что практически ни в одной статье об этом не упоминается, но я счел необходимым объяснить. Прежде всего, узел имеет только один обратный указатель, а это означает, что только связанный список первого слоя является двусвязным списком. Связный список в нашем предыдущем примере является однонаправленным. Почему первый слой должен стать двунаправленным? Одна причина в том, что данные в первом слое самые полные, а вторая причина: представьте, что у нас есть элемент с оценкой 8, а его соседние узлы в первом слое с оценкой 7 и 10, а теперь мы хотим обновить этот элемент Оценка 9. По идее, мы хотим удалить и вставить, но на самом деле положение этого элемента вообще не нужно менять.В этом случае можно сначала судить о размере соседние узлы в первом слое. Если он все еще находится в интервале, обновите значение напрямую. , опуская шаг удаления-вставки.
Значение пролета в уровне?
Объяснение этой проблемы требует помощи изображений, сначала поместите изображение списка пропуска:
Число на стрелке — это значение диапазона. Диапазон имеет много преимуществ. Например, если мы хотим найти ранжирование с оценкой 3, мы можем напрямую взять диапазон = 3 из L5 в головном указателе. Если есть потребность в многоуровневом запросе, это процесс накопления, и наоборот, обратное ранжирование также может быть рассчитано с помощью операции накопления длины.
| Атрибуты | имея в виду |
|---|---|
| ele | Онтология данных. Здесь вы можете видеть, что это структура sds, а sds — это строковая структура в Redis. Для получения подробной информации о структуре структуры sds вы можете обратиться к моей статье «[Самая полная серия] Redis-Structure-String». |
| score | Оценка, соответствующая данным. |
| backward | Указатель (прямой указатель) на предыдущий узел связанного списка. |
| level[] | Массив zskiplistLevel, в котором хранится указатель (обратный указатель) на следующий узел связанного списка каждого уровня. |
| level[].forward | Указатель назад, представляющий один слой. |
| level[].span | Указывает, сколько узлов охватывает текущий указатель. |
Суммируйте 3 корректировки, сделанные redis для списка пропуска:
- Данные не могут быть дублированы.
- При сравнении сравниваются не только баллы (эквивалентные ключам списка пропуска), но и сами данные. В реализации списка пропуска Redis содержимое самих данных однозначно идентифицирует данные, а не ключ. Кроме того, когда несколько элементов имеют одинаковую оценку, их также необходимо отсортировать в соответствии с содержанием данных.
- Имеется обратный указатель, и все связанные списки первого уровня являются двусвязными списками.
Причина, по которой Redis Zset использует список пропусков вместо сбалансированного дерева
Расширяя это, посмотрите, что говорит автор:
-
Они не очень требовательны к памяти. В основном это зависит от вас. Изменение параметров вероятности узла иметь заданное количество уровней сделает их менее интенсивными по памяти, чем b-деревья.
Он не очень требователен к памяти. На самом деле он зависит от вероятности p в функции уровня генерации. Если он правильно определен, он фактически похож на сбалансированное дерево.
-
A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
Поскольку отсортированные наборы часто выполняют операции поиска по диапазонам, такие как ZRANGE или ZREVRANGE, двусвязный список в таблице переходов может быть очень удобным для таких операций.
-
They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
Реализация проста, и операция ZRANK также позволяет достичьO(logN)Временная сложность .