Любой, кто знаком с Redis, знает, что он однопоточный. Поэтому будьте очень осторожны при использовании некоторых команд с временной сложностью O(N). Процесс может быть заблокирован случайно, что приведет к зависанию Redis.
Иногда нам нужно работать с той частью команды, которая соответствует условиям, например, удалить ключ, начинающийся с test_. Так как же получить эти ключи? До Redis 2.8 мы могли использовать команду keys для получения нужных ключей путем обычного сопоставления. Но у этой команды есть два недостатка:
- Ограничений нет, мы можем получить только все квалифицированные ключи за один раз.Если есть миллионы результатов, то вас ждет «бесконечный» строковый вывод.
- Команда keys представляет собой алгоритм обхода, временная сложность которого равна O(N). Как мы только что сказали, эта команда может легко привести к зависанию службы Redis. Поэтому мы должны стараться избегать использования этой команды в производственной среде.
Как выбрать между удовлетворением потребностей и зависанием Redis? Столкнувшись с этой дилеммой, Redis предлагает решение в версии 2.8 — команду сканирования.
По сравнению с командой ключей команда сканирования имеет два очевидных преимущества:
- Хотя временная сложность команды сканирования также составляет O(N), она выполняется поэтапно и не блокирует поток.
- Команда сканирования предоставляет параметр limit, который может контролировать максимальное количество результатов, возвращаемых каждый раз.
Эти два преимущества помогают нам решить вышеуказанные проблемы, но команда сканирования не идеальна, и возвращаемые ею результаты могут повторяться, поэтому клиенту необходимо выполнить дедупликацию. Что касается того, почему это повторяется, я думаю, вы получите ответ после прочтения этой статьи.
Для основного использования команды сканирования см.Подробная команда Redis: ключиВведение в команду SCAN в этой статье.
Сегодня мы в основном обсуждаем, как работает сканирование с точки зрения базовой структуры и исходного кода.
Структура Redis
Redis использует хеш-таблицу в качестве базовой реализации, и причина этого не более чем в эффективности и простоте реализации. Когда дело доходит до хеш-таблиц, первая реакция многих Java-программистов — HashMap. Правильно, структура хранения базового ключа Redis представляет собой структуру массива + связанного списка, похожую на HashMap. где размер массива первого измерения равен 2n(n>=0). Длина массива удваивается каждый раз, когда он расширяется.
Команда сканирования предназначена для обхода этого одномерного массива. Значение курсора, возвращаемое каждый раз, также является индексом этого массива. Параметр limit указывает, сколько элементов массива пройдено, и возвращаются все квалифицированные результаты, прикрепленные к этим элементам. Поскольку размер связанного списка, прикрепленного к каждому элементу, разный, количество результатов, возвращаемых каждый раз, также разное.
Порядок обхода SCAN
Что касается порядка обхода команды сканирования, мы можем использовать маленький каштан, чтобы увидеть его в деталях.
127.0.0.1:6379> keys *
1) "db_number"
2) "key1"
3) "myKey"
127.0.0.1:6379> scan 0 MATCH * COUNT 1
1) "2"
2) 1) "db_number"
127.0.0.1:6379> scan 2 MATCH * COUNT 1
1) "1"
2) 1) "myKey"
127.0.0.1:6379> scan 1 MATCH * COUNT 1
1) "3"
2) 1) "key1"
127.0.0.1:6379> scan 3 MATCH * COUNT 1
1) "0"
2) (empty list or set)
У нас есть 3 ключа в Redis, и мы перебираем только элементы одномерного массива за раз. Как показано выше, порядок прохождения команды SCAN следующий:
0->2->1->3
Этот порядок кажется странным. Это легче понять, когда мы преобразуем его в двоичный формат.
00->10->01->11
Мы обнаружили, что каждый раз эта последовательность увеличивается на 1. Обычное двоичное сложение заключается в сложении и переносе справа налево. И эта последовательность добавляется и переносится слева направо. Это также подтверждается в исходном коде Redis.
Курсор обрабатывается следующим образом в функции dictScan файла dict.c
v = rev(v);
v++;
v = rev(v);
Это означает инвертировать курсор, добавить единицу, а затем инвертировать, что мы называем операцией «добавление 1 к старшему разряду».
У вас могут возникнуть вопросы, почему вы используете этот порядок обхода вместо обычного 0, 1, 2... Это потому, что вам нужно учитывать расширение и сжатие словаря во время обхода (должен восхищаться полнотой разработчик рассмотреть проблему).
Давайте посмотрим, как будет проходить обход, когда расширение происходит во время процесса обхода SCAN. Добавление нашего исходного массива имеет 4 элемента, то есть индекс имеет две цифры, в это время его нужно расширить до 3-х цифр и перехешировать.
Все элементы, изначально смонтированные под xx, размещаются под 0xx и 1xx. На приведенном выше рисунке, когда мы собираемся пройти 10, dict перефразируется.В это время команда сканирования начнет обход с 010, а 000 и 100 (элементы, прикрепленные к исходному 00) не будут проходить повторно.
Давайте еще раз посмотрим на усадку. Предполагая, что dict сжимается с 3 бит до 2 бит, когда 110 вот-вот будет пройдено, dict уменьшится, и сканирование пройдет 10. В это время элементы, прикрепленные под 010, будут проходиться повторно, но элементы до 010 не будут проходиться повторно. Таким образом, некоторые повторяющиеся элементы могут появляться при уменьшении масштаба.
перефразировать для Redis
Rehash — относительно сложный процесс, и чтобы не блокировать процесс Redis, он использует механизм прогрессивного rehash.
/* 字典 */
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时，值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在运行的安全迭代器的数量
int iterators; /* number of iterators currently running */
} dict;
В структуре словаря Redis есть две хеш-таблицы, новая таблица и старая таблица. В процессе повторного хеширования Redis постепенно переносит элементы из старой таблицы в новую таблицу.Далее давайте взглянем на исходный код операции повторного хеширования dict.
/* Performs N steps of incremental rehashing. Returns 1 if there are still
* keys to move from the old to the new hash table, otherwise 0 is returned.
*
* Note that a rehashing step consists in moving a bucket (that may have more
* than one key as we use chaining) from the old to the new hash table, however
* since part of the hash table may be composed of empty spaces, it is not
* guaranteed that this function will rehash even a single bucket, since it
* will visit at max N*10 empty buckets in total, otherwise the amount of
* work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
assert(d->ht[0].size > (unsigned long)d->rehashidx);
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
while(de) {
uint64_t h;
nextde = de->next;
/* Get the index in the new hash table */
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
/* Check if we already rehashed the whole table... */
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
/* More to rehash... */
return 1;
}
Комментируя, мы можем понять, что процесс перефразирования основан на ведре как базовой единице миграции. Так называемое ведро на самом деле является элементом одномерного массива, о котором мы упоминали ранее. Перенос одного списка за раз. Поясним этот код.
- Сначала определите, выполняется ли перефразирование, если да, продолжайте, в противном случае возвращайтесь напрямую.
- Затем нужно запустить прогрессивную перефразировку за n шагов. В то же время также оценивается наличие оставшихся элементов для обеспечения безопасности.
- Перед выполнением повторного хеширования сначала определите, не выходит ли за пределы контейнера, который нужно перенести.
- Затем пропустите пустое ведро.Существует переменная empty_visits, которая представляет максимальное количество доступных пустых ведер.Эта переменная в основном предназначена для того, чтобы Redis не блокировался слишком сильно.
- Следующим шагом является миграция элементов, перефразирование всех элементов в текущем сегменте и обновление количества элементов в двух таблицах.
- Каждый раз при переносе корзины корзина в старой таблице должна быть указана в NULL.
- Наконец, оцените, все ли переносы завершены. Если это так, освободите пространство и сбросьте индекс повторного хеширования. В противном случае сообщите вызывающей стороне, что еще есть данные, которые не были перенесены.
Поскольку Redis использует механизм прогрессивного повторного хеширования, команда сканирования одновременно сканирует новую и старую таблицы и возвращает результат клиенту.