Что мне делать, если я хочу вернуть все ключи в текущей базе данных Redis? Использовать команду ключей? В случае большого количества ключей эта команда вызовет длительное выполнение однопоточного сервера redis, а последующие команды не получат ответа, в то же время она также вызовет определенное давление на памяти, что серьезно снизит доступность сервиса Redis.
По этой причине Redis 2.8.0 и более поздние версии предоставляют несколько команд, связанных со сканированием, для предоставления связанных функций обхода для различных структур данных (таких как базы данных, наборы, хэши и упорядоченные наборы).
SCANКоманда и все, что с ней связаноSSCAN Заказ, HSCANкоманда иZSCANкоманды используются для постепенного перебора набора элементов
- SCANкоманда для перебора ключей базы данных в текущей базе данных
- SSCANкоманда для перебора элементов в ключе коллекции
- HSCANкоманда для перебора пар ключ-значение в хеш-ключе
- ZSCANКоманда используется для перебора элементов в отсортированном наборе (включая элементы элементов и оценки элементов).
SCAN
- Формат команды: SCAN курсор [MATCH pattern] [COUNT count]
- SCANКоманда представляет собой итератор на основе курсора:SCANПосле вызова каждой команды пользователю будет возвращен новый курсор, и пользователю необходимо использовать этот новый курсор в качестве следующей итерации.SCANПараметр курсора команды для продолжения предыдущей итерации процесса
- когда SCANПараметр курсора команды установлен на
0, сервер начнет новую итерацию, и когда сервер вернет пользователю значение0курсор , указывает, что итерация закончилась - SSCAN / HSCAN /ZSCANОна похожа на команду SCAN, за исключением того, что формат команды немного отличается, а метод обхода при реализации без хэш-таблицы отличается, поэтому я не буду вдаваться в подробности, подробнее можно узнать по ссылке.
- Гарантия: от начала полного обхода до конца полного обхода все элементы, которые всегда существовали в наборе данных, будут возвращены полным обходом.
- недостаток: 1) Один и тот же элемент может быть возвращен несколько раз, что может произойти после обхода после повторного сокращения или обхода во время повторного сокращения (личное понимание) 2) Если элемент добавляется в набор данных во время итерации или удаляется из набора данных во время итерации, то элемент может быть возвращен или не возвращен, что не определено.
Примечание. Приведенный выше контент взят с http://redisdoc.com/key/scan.html.
Для команды SCAN и набора, хэша и упорядоченного набора, реализованного хэш-таблицей внизу, для обхода используется один и тот же алгоритм сканирования (все вызывают функцию dictScan).Функция dictScan короткая и компактная, что является ядром попытки этой статьи объяснить, как следует
unsigned long dictScan(dict *d,//待遍历哈希表
unsigned long v,//cursor值，此次遍历位置，初始为0
dictScanFunction *fn,//单个条目遍历函数，根据条目类型，copy条目对象，以便加入到返回对象中
dictScanBucketFunction* bucketfn,//null
void *privdata)//返回对象
{
dictht *t0, *t1;
const dictEntry *de, *next;
unsigned long m0, m1;
if (dictSize(d) == 0) return 0;//如果dict为空，直接返回
if (!dictIsRehashing(d)) {//如果此刻哈希表没有在rehashing，只有ht[0]有数据
t0 = &(d->ht[0]);//将ht[0]作为遍历表
m0 = t0->sizemask;//遍历表的sizemask，即以遍历表的size为底取模，如表大小为8，则m0为111
/* 遍历cursor所在位置的所有条目 */
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);//这行if条件为false，不会执行
de = t0->table[v & m0];
while (de) {//遍历当前cursor位置的所有条目，即hash key取模hash table大小相同的所有条目
next = de->next;
fn(privdata, de);
de = next;
}
/* 作用是将v也就是cursor的高位置为1，低位不变，如v为001，则改为61个1再加001 */
v |= ~m0;
/* 将cursor高位0变成1或者（连续高位1都变成0且第一个0变为1） */
v = rev(v);//将cursor做二进制逆序，也就是变成100+61个1
v++;//末位加1，也就是101+61个0
v = rev(v);//将cursor做二进制逆序，也就是61个0+101
} else {//哈希表正在rehashing
t0 = &d->ht[0];
t1 = &d->ht[1];
/* 确保t0小t1大 */
if (t0->size > t1->size) {
t0 = &d->ht[1];
t1 = &d->ht[0];
}
m0 = t0->sizemask;//t0表sizemask，如表大小为8，则m0为7，即0111
m1 = t1->sizemask;//t1表sizemask，如表大小为64，则m1为63，即00111111
/* 将cursor位置的所有条目都添加进去 */
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);//不执行
de = t0->table[v & m0];
while (de) {//将t0的所有条目都加进去
next = de->next;
fn(privdata, de);
de = next;
}
/* 遍历小表cursor位置可能会rehash到大表的所有条目，
*如cursor为1，小表大小为8，大表大小为64，则0、8、16、24、32、40、48、56等位置的条目都会被添加返回
*/
do {
/* 添加大表v位置的所有元素，注意v位置跟着while循环不断变化 */
if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);//不执行
de = t1->table[v & m1];
while (de) {//添加v位置的所有条目
next = de->next;
fn(privdata, de);
de = next;
}
/* 作用同上，只不过换成了大表的元素，也就是小表cursor位置可能扩展到大表的所有位置*/
v |= ~m1;
v = rev(v);
v++;
v = rev(v);
/* 如上举例，m0为3位1，m1为6位1，二者做异或，也就是将二者不同的高位置为1，
*其他前后的61位均为0，然后遍历v在二者不同高位的所有可能，
*当v重新回到0时，跳出while循环 ，也就是将m0可能rehash到的m1位置的条目全部返回
*/
} while (v & (m0 ^ m1));
}
return v;
}
Алгоритм очень деликатный.Понадобилось много времени, чтобы понять смысл.Если есть что-то неуместное, добро пожаловать в кирпич.
Хэш-таблица имеет несколько состояний и может находиться в состоянии при обходе
- После расширения хэша
- после сокращения
- Перефразирование (расширение или сжатие)
Это делает ситуацию, с которой сталкивается алгоритм сканирования, очень сложной.Как обойти все элементы (элементы, которые не изменились в процессе обхода, гарантированно будут пройдены) и вернуть как можно меньше повторяющихся элементов, является проблемой.Конкретная блок-схема обхода трех состояний выводит портал:Принцип обхода итератора Redis Scan (2) – обратный двоичный итератор dictScan(Искал в сети, процесс очень долгий, будьте внимательны, но есть хорошие картинки)
Конкретный процесс алгоритма также можно найти в комментариях к исходному коду выше.
Алгоритмическое мышление (думайте о сокращении как об обратном расширении)
1. Если предположить, что размер хэш-таблицы увеличен с N до 2^M x N (размер хэш-таблицы может быть только степенью 2, а N также является степенью 2), то i элементов таблицы исходная хэш-таблица может быть распределена по i + jx N, где j
- 00001
- 00101
- 01001
- ...
- 11101
Если в процессе обхода после расширения позиции, где те же две позиции равны 01, можно игнорировать, то есть до тех пор, пока обход тех же N битов после обхода не завершится, то это означает, что все возможности первого Также перечислены M битов, то есть всегда сначала исчерпать предыдущие возможности, а затем исчерпать следующие биты, тогда расширенный слот (например, 1, 5, 9..., 29, соответствующий 1) не нужно проходить. опять же, сжатие похоже, но сжатая позиция может содержать возможность того, что исходная хэш-таблица не была исчерпана и ее необходимо пройти снова.
2. Как сначала пройти через возможность старшей позиции, dictScan дает обратный бинарный итеративный алгоритм (всегда сначала инвертировать самую высокую позицию, исчерпать возможность верхней позиции и, в свою очередь, перейти к нижней позиции, этот метод преобразования гарантирует, что все элементы будут пройдены до):
- Установите позицию, соответствующую первому встретившемуся старшему 0, в 1 (то есть до и после преобразования у двух из них самые последовательные младшие биты справа налево, то есть диапазон с одинаковым модулем равен 1). Согласно этому правилу, в хеш-таблице размером 32 следующая позиция после прохождения 00001 — 10001. Если хеш-таблица уменьшится до размера 16 при обходе 10001 в следующий раз, она повторно пройдет позицию 0001 (по модулю 10001 и 16). ), и в эту позицию сжимаются как 00001, так и 10001. В этом случае элементы могут возвращаться повторно, если 32 расширяется до 64, то 00001 расширяется до двух позиций 000001/100001. Из-за принципа исчерпания высокого порядка , эти последующие позиции не будут обрабатываться снова, что снижает вероятность повторного возврата элементов.
- или поставить предыдущий
连续1Устанавливается в 0, первый 0 устанавливается в 1, например 10001, следующий 01001, то есть возможность начала исчерпания следующего старшего бита
3. В случае перехеширования после обхода позиции курсора малой таблицы необходимо пройти все позиции большой таблицы, до которых может перехешироваться позиция курсора малой таблицы, а затем вернуться к пройденному элементу и позиция обхода следующей малой таблицы