Когда мы ранее представили список сжатия ziplist, мы упомянули, что внутри zset есть две структуры хранения: одна — ziplist, а другая — skiplist. Чтобы полностью понять внутреннюю структуру zset, давайте снова представим список пропусков.
Введение в список пропусков
Как следует из названия, skiplist — это, по сути, упорядоченный многомерный список. Начнем с рассмотрения того, как выполняется поиск в одномерном списке.
Как показано на рисунке выше, если мы хотим найти элемент, нам нужно пройти от головного узла, пока мы не найдем соответствующий узел или первый узел, который больше, чем искомый элемент (не найден). Временная сложность O(N).
Эффективность такого поиска относительно невысока, если мы поднимем некоторые узлы в списке, например, на один уровень, то превратим один узел из каждых двух узлов в два слоя. Тогда узлы второго слоя составляют лишь половину от узлов первого слоя, и эффективность поиска повысится.
Шаг поиска заключается в том, чтобы начать с верхнего уровня головного узла, когда будет найден первый узел, больший указанного элемента, вернуться к предыдущему узлу и продолжить поиск на следующем уровне.
Например, мы хотим запросить 16 в приведенном выше списке.
- Начните с верхнего уровня головного узла, начиная с узла 7.
- следующий узел 7 равен 39, что больше 16, поэтому мы возвращаемся к 7
- Начните с 7 и продолжайте смотреть на следующий слой, и вы можете найти 16.
В этом примере обходит не меньше узлов, чем в одномерном списке, но когда узлов больше и их нужно искать, преимущество такого подхода становится очевидным. Тем не менее в приведенном выше примере, если мы ищем 39, нам нужно посетить только два узла (7, 39), чтобы найти его. Это половина количества одномерных списков.
Чтобы избежать временной сложности операции вставки, равной O (N), количество каждого слоя в списке пропуска не будет строго соответствовать соотношению 2: 1, а будет случайным числом слоев для каждого вставляемого элемента.
Процесс расчета случайного номера слоя выглядит следующим образом:
- Каждый узел имеет первый слой
- Тогда вероятность того, что у него есть второй слой, равна p, а вероятность того, что у него есть третий слой, равна p*p.
- Не может превышать максимальное количество слоев
Реализация в Redis есть
/* Returns a random level for the new skiplist node we are going to create.
* The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
* (both inclusive), with a powerlaw-alike distribution where higher
* levels are less likely to be returned. */
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
Значение ZSKIPLIST_P равно 0,25, а вероятность существования предыдущего слоя равна 1/4, что означает, что он более плоский, чем в нашем примере выше. Значение ZSKIPLIST_MAXLEVEL равно 64, то есть максимально допустимым 64 слоям.
список пропусков в Redis
Список пропусков в Redis — это внутренняя структура хранения в виде zset.
/* ZSETs use a specialized version of Skiplists */
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;
Вы можете видеть, что zset состоит из хэша и списка пропуска.
Структура списка пропуска включает указатели начала и конца, длину и количество слоев текущего списка пропуска.
А в zskiplistNode, то есть узел списка пропуска, входит
- ele, данные, хранящиеся узлом
- оценка узла
- Указатель возврата — это указатель на предыдущий узел на первом уровне, то есть первый уровень списка пропусков Redis — это двусторонний список.
- Уровень указателя [] каждого уровня узла, каждый уровень соответствует указателю вперед, и сколько узлов охватывает этот указатель. span используется для вычисления ранжирования элементов
Разобравшись со структурой zset и skiplist, давайте взглянем на реализацию основных операций zset.
Процесс вставки
Когда мы представили процесс вставки сжатого списка, мы упомянули вставку списка пропуска.В функции zsetAdd Redis оценивает метод кодирования zset и обрабатывает список пропуска и список zip соответственно. часть почтового спискаПреамбулаУже представлено, давайте сегодня посмотрим на часть списка пропуска.
if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
zset *zs = zobj->ptr;
zskiplistNode *znode;
dictEntry *de;
de = dictFind(zs->dict,ele);
if (de != NULL) {
/* NX? Return, same element already exists. */
if (nx) {
*flags |= ZADD_NOP;
return 1;
}
curscore = *(double*)dictGetVal(de);
/* Prepare the score for the increment if needed. */
if (incr) {
score += curscore;
if (isnan(score)) {
*flags |= ZADD_NAN;
return 0;
}
if (newscore) *newscore = score;
}
/* Remove and re-insert when score changes. */
if (score != curscore) {
znode = zslUpdateScore(zs->zsl,curscore,ele,score);
/* Note that we did not removed the original element from
* the hash table representing the sorted set, so we just
* update the score. */
dictGetVal(de) = &znode->score; /* Update score ptr. */
*flags |= ZADD_UPDATED;
}
return 1;
} else if (!xx) {
ele = sdsdup(ele);
znode = zslInsert(zs->zsl,score,ele);
serverAssert(dictAdd(zs->dict,ele,&znode->score) == DICT_OK);
*flags |= ZADD_ADDED;
if (newscore) *newscore = score;
return 1;
} else {
*flags |= ZADD_NOP;
return 1;
}
}
Во-первых, выяснить, существует ли соответствующий элемент, если он существует, а параметра NX нет, то записывается текущий счет этого элемента.Здесь видно, что хеш-словарь в zset используется для получения оценок по элементам.
Затем решите, следует ли выполнять команду увеличения.Если это так, добавьте указанный счет к текущему счету, чтобы получить новый счет, newscore. Если оценка изменяется, вызывается функция zslUpdateScore для обновления узла в списке пропусков, и требуется еще один шаг для обновления оценки в хэш-словаре.
Если вставляемый элемент не существует, вызовите функцию zslInsert напрямую.
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
serverAssert(!isnan(score));
x = zsl->header;
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];
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;
}
/* we assume the element is not already inside, since we allow duplicated
* scores, reinserting the same element should never happen since the
* caller of zslInsert() should test in the hash table if the element is
* already inside or not. */
level = zslRandomLevel();
if (level > zsl->level) {
for (i = zsl->level; i < level; i++) {
rank[i] = 0;
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;
/* update span covered by update[i] as x is inserted here */
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
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++;
}
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;
}
Функция определяет два массива в начале, массив обновления используется для хранения пути поиска, а массив рангов используется для хранения диапазона узлов.
Первый шаг — найти путь поиска, в который должен быть вставлен узел, и записать количество отрезков узлов.
Затем начните вставлять, сначала рандомизируйте номер слоя. Если количество случайно сгенерированных слоев больше, чем текущее количество слоев, необходимо продолжить заполнение массивов обновления и ранжирования, а также обновить максимальное количество слоев в списке пропуска.
Затем вызовите функцию zslCreateNode, чтобы создать новый узел.
После создания узла путь поиска к данным положения, предусмотренный из начала первого слоя, слой по слое вставлен узлом (обновляет указатель) и значение промежутки других узлов.
Наконец, узел возврата обновляется, а длина списка пропуска увеличивается на единицу.
Это весь процесс вставки нового элемента.
процесс обновления
Разобравшись с процессом прошивки, вернемся назад и посмотрим на процесс обновления
zskiplistNode *zslUpdateScore(zskiplist *zsl, double curscore, sds ele, double newscore) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
int i;
/* We need to seek to element to update to start: this is useful anyway,
* we'll have to update or remove it. */
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < curscore ||
(x->level[i].forward->score == curscore &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
x = x->level[i].forward;
}
update[i] = x;
}
/* Jump to our element: note that this function assumes that the
* element with the matching score exists. */
x = x->level[0].forward;
serverAssert(x && curscore == x->score && sdscmp(x->ele,ele) == 0);
/* If the node, after the score update, would be still exactly
* at the same position, we can just update the score without
* actually removing and re-inserting the element in the skiplist. */
if ((x->backward == NULL || x->backward->score < newscore) &&
(x->level[0].forward == NULL || x->level[0].forward->score > newscore))
{
x->score = newscore;
return x;
}
/* No way to reuse the old node: we need to remove and insert a new
* one at a different place. */
zslDeleteNode(zsl, x, update);
zskiplistNode *newnode = zslInsert(zsl,newscore,x->ele);
/* We reused the old node x->ele SDS string, free the node now
* since zslInsert created a new one. */
x->ele = NULL;
zslFreeNode(x);
return newnode;
}
Как и при вставке, сначала сохраняется путь поиска. И найдите узел для обновления, если положение узла остается неизменным после обновления, вернитесь напрямую. В противном случае необходимо вызвать функцию zslDeleteNode для удаления узла, а затем вставить новый узел.
удалить процесс
Процесс обновления списка пропусков в Redis относительно прост для понимания, то есть сначала удалите, а затем вставьте, а затем давайте посмотрим, как он удаляет узлы.
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
int i;
for (i = 0; i < zsl->level; i++) {
if (update[i]->level[i].forward == x) {
update[i]->level[i].span += x->level[i].span - 1;
update[i]->level[i].forward = x->level[i].forward;
} else {
update[i]->level[i].span -= 1;
}
}
if (x->level[0].forward) {
x->level[0].forward->backward = x->backward;
} else {
zsl->tail = x->backward;
}
while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
zsl->level--;
zsl->length--;
}
Код процесса удаления также относительно прост для понимания.Во-первых, в соответствии с путем поиска, снизу вверх, прямой указатель обновляется слой за слоем. Затем обновите указатель возврата. Если уровень удаленных узлов является максимальным уровнем, то поле уровня списка пропуска также необходимо обновить. Окончательная длина уменьшается на единицу.
Суммировать
Список пропусков представляет собой иерархический список узлов, и процесс поиска узла может охватывать несколько узлов, что экономит время поиска.
Zset в Redis состоит из хэш-словаря и списка пропуска, который отвечает за соответствие между данными и оценками, а список пропуска отвечает за поиск данных по оценкам.
Операции вставки и удаления списка пропуска в Redis зависят от пути поиска, а операция обновления заключается в том, чтобы сначала удалить, а затем вставить.
Рекомендуемое чтение
Skip Lists: A Probabilistic Alternative to Balanced Trees
"Redis Deep Adventure: основные принципы и практика применения》