байюнь
Все видео: [Запись ежедневного обучения] Используйте видеооборудование для записи ежедневного обучения
Что такое словарь?
Дикт, или словарь, также известен как хэш-таблица. В пяти структурах данных redis структура dict используется в следующих двух случаях:
- Хэш: ziplist используется, когда данные малы, и dict используется, когда данные большие
- Zset: Используйте ziplist, когда данные малы, и skiplist + dict, когда данные большие
Объединив два вышеперечисленных случая, мы видим, что dict также является более сложной структурой данных, которая обычно используется в случае большого объема данных. Обычно дикт выглядит так: в этой хэш-таблице каждая единица хранения называется ведром. Мы вставляем пару ключ-значение “имя”=> “байян” в дикт (хэш-таблицу). Предполагая, что результат хэширования для ключа “имя” равен 3, мы ищем позицию индекса 3 в хэш-таблице и вставляем его в нее, чтобы получить ситуацию, как показано на рисунке. Мы видим, что самым большим преимуществом dict является то, что временная сложность поиска равна O (1), что несравнимо с любой другой структурой данных. При поиске мы сначала хэшируем ключ “имя” и получаем результат 3. Когда мы ищем позицию индекса 3 напрямую, мы можем получить значение “байян”. Временная сложность составляет O (1), что довольно быстро.
Словарь в редисе
Базовая структура
В красном, на основе обычного словаря, добавлены некоторые описательные поля для облегчения расширения и сокращения. Основываясь на приведенном выше примере, структура хранилища в redis выглядит следующим образом: структура ditch выглядит следующим образом:
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;В ditch реальным местом для хранения данных является таблица**, вторичный указатель типа записи dict. Давайте разделим это. Во-первых, первый указатель может представлять одномерный массив, хэш-таблицу. Последний указатель представляет, что в каждом блоке хранения одномерного массива (хэш-таблицы) хранится указатель типа диктанта, который указывает, где мы храним структуру типа диктанта пар ключ-значение, как показано на рисунке выше. Структура ввода dict для хранения окончательной пары ключ-значение выглядит следующим образом:
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;Запись, в которой хранятся пары ключ-значение, в основном является полями ключ и значение здесь. Поскольку ключи и значения, хранящиеся в диктах, могут быть строками, целыми числами и т. Д., Они представлены здесь указателем void*. Мы заметили, что последний указатель next того же типа записи dict использовался для решения того, о чем мы часто говорили. Коллизии Хэшей Проблема.
Столкновения Хэшей
Когда мы хэшируем разные ключи с одинаковым результатом, мы сталкиваемся с проблемой конфликта хэшей. Существует два широко используемых решения конфликтов хэшей: метод открытого адреса и метод цепного адреса. Редис использует последнее. С помощью этого следующего указателя мы можем последовательно соединять элементы с одинаковым значением хэша, чтобы решить проблему конфликта хэшей. Обратите внимание, что в исходной реализации redis связанный список используется при вставке элементов в Dict Вставка заголовка Новый элемент вставляется в начало списка, так что сложность вставки уменьшается за счет того, что каждый раз не выполняется переход к концу списка.
Способ Адресации цепочки
Предполагая, что мы продолжаем вставлять элементы в dict, все ячейки в этой хэш-таблице будут заполнены, а список за каждой ячейкой будет очень длинным в процессе разрешения конфликтов хэша методом цепного адреса. Таким образом, временная сложность связанного списка постепенно уменьшится до O (n). Для dict в целом эффективность его запросов будет значительно снижена. Чтобы решить проблему снижения производительности dict, вызванную слишком большим количеством данных, нам нужно это сделать. Расширение емкости Для удовлетворения потребностей в хранении последующих вставных элементов.
Переосмысление принципа “разделяй и властвуй”
- Обычно мы будем расширять хэш – таблицу дважды, то есть с 2 – > 4, 4 – > 8 и так далее. Предполагая, что в одном из наших рационов было сохранено много данных, нам нужно вставить много данных в диктант. В последующем процессе вставки больших объемов данных, поскольку нам необходимо решить проблему снижения производительности dict, нам необходимо расширить ее. Поскольку при расширении емкости все пары ключ-значение должны быть снова хэшированы и переназначены в соответствующее расположение корзины, мы называем этот процесс как перефразирование .
- В процессе повторного хэширования требуется большое количество хэш-операций, что стоит больших денег и занимает много времени. Поскольку redis является архитектурой с одним процессом и одним потоком, в процессе выполнения повторного хэша из-за больших накладных расходов и длительного времени процесс redis будет заблокирован, что не позволит предоставлять онлайн-службы хранения данных, которые будут недоступны для внешней службы redis. Для решения проблемы блокировки процесса redis, вызванной одноразовым повторным хэшем, используйте Разделяй и властвуй Чтобы уменьшить загрузку ресурсов процесса redis, вызванную повторной обработкой, операция повторной обработки разделена на несколько этапов. Например, операция перестановки может быть выполнена в последующих операциях получения и установки. Для этого red на самом деле спроектировал его. Две хэш-таблицы Одна из них-это хэш-таблица, о которой мы говорили ранее, которая обеспечивает доступ к внешним сервисам, в то время как другая предназначена для операций повторного хэширования. Эта идея “разделяй и властвуй” рассеивает перепев
- Все дело в том, чтобы перефразировать. Как мы видим, на основе предыдущих рисунков мы добавили новую структуру dict, в которой поле HT [2] отвечает за указание на две хэш-таблицы. Размер следующей хэш-таблицы равен, без каких-либо элементов. Структура dict выглядит следующим образом:
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
Long rehashidx; /* rehash process identifier. If the value is - 1, it is not rehash, otherwise it is rehash.*/
unsigned long iterators; /* number of iterators currently running */
} dict;- Обратите внимание на поле rehashidx, которое представляет наш процесс перестановки. Обратите внимание, что каждый раз, когда мы выполняем такие команды, как get или set, rehash перемещает элемент исходной хэш-таблицы HT [0] в новую хэш-таблицу HT [1]. Обратите внимание, что за один раз перемещается только один элемент. После завершения перемещения rehashidx будет + 1 до тех пор, пока все элементы исходной хэш-таблицы не будут перемещены в новую хэш-таблицу. До тех пор. Когда повторный хэш будет завершен, для новой хэш-таблицы HT [1] будет установлено значение HT [0] для онлайн-обслуживания. Исходная хэш-таблица HT [0] будет уничтожена. Исходный код rehash выглядит следующим образом:
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 the elements in the old hash table HT [0] to the new hash table HT [1]*/
while(de) {
uint64_t h;
nextde = de->next;
/* Computing index subscripts of new hash table ht[1]*/
H = dictHashKey (d, de - > key) & D - > HT [1]. sizemask; //hash algorithm
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 whether rehash is complete, and if it is, set rehashidx to -1*/
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;
}Возможные проблемы в процессе перефразирования
Влияние перефразирования на поиск
Если в процессе перефразирования (например, увеличение емкости с 4 до 8), если вам нужно найти элемент. Сначала мы рассчитаем значение хэша (предполагая, что 3), чтобы найти старую хэш-таблицу HT [0]. Если мы обнаружим, что в позиции 3 нет элемента, это означает, что элемент был перефразирован, поэтому мы можем найти соответствующую позицию 3 или 7 в новой хэш-таблице.
Влияние перефразирования на эргодичность
проблема
Представьте себе следующее: перед повторным просмотром мы использовали команду СКАНИРОВАНИЯ для первого обхода dict; после повторного просмотра мы выполнили второй обход СКАНИРОВАНИЯ. Что случилось? Прежде чем обсуждать этот вопрос, давайте ознакомимся с командой СКАНИРОВАНИЯ. Мы знаем, что когда мы выполняем ключи, которые возвращают все ключи, потому что все ключи довольно часто складываются вместе, если их обойти все сразу, это может заблокировать повторное отображение одного процесса на довольно долгое время, в течение которого никакая услуга не может быть предоставлена извне. Чтобы решить эту проблему, появилась команда СКАНИРОВАНИЯ. Вместо того, чтобы возвращать все ключи сразу, он каждый раз возвращает часть ключей и записывает ход текущего обхода, для записи которого используется курсор. При следующем повторном выполнении команды СКАНИРОВАНИЯ redis продолжит перемещение вниз от позиции курсора. Команда СКАНИРОВАНИЯ на самом деле является идеей “разделяй и властвуй”, проходящей небольшую часть за раз, пока обход не будет завершен. Официальная интерпретация заказа на СКАНИРОВАНИЕ выглядит следующим образом
Команда СКАНИРОВАНИЯ-это команда на основе курсора итератор Каждый раз, когда вызывается команда СКАНИРОВАНИЯ, пользователю возвращается новый курсор. Пользователю необходимо использовать новый курсор в качестве параметра курсора команды СКАНИРОВАНИЯ на следующей итерации, чтобы продолжить процесс предыдущей итерации.
Команда СКАНИРОВАНИЯ используется следующим образом:
redis 127.0.0.1:6379> scan 0
1) "17"
2) 1) "key:12"
2) "key:8"
3) "key:4"
4) "key:14"
5) "key:16"
6) "key:17"
7) "key:15"
8) "key:10"
9) "key:3"
10) "key:7"
11) "key:1"
redis 127.0.0.1:6379> scan 17
1) "0"
2) 1) "key:5"
2) "key:18"
3) "key:0"
4) "key:2"
5) "key:19"
6) "key:13"
7) "key:6"
8) "key:9"
9) "key:11"- В приведенном выше примере первая итерация использует 0 в качестве курсора для указания начала новой итерации. Во второй итерации используется курсор, возвращенный на первой итерации, который является значением 17 команды, отвечающей на первый элемент.
- Как видно из приведенного выше примера, ответом на команду СКАНИРОВАНИЯ является массив из двух элементов, первый элемент массива представляет собой новый курсор для следующей итерации, а второй элемент массива представляет собой массив, содержащий все элементы, которые были повторены.
- При втором вызове команды СКАНИРОВАНИЯ команда возвращает курсор 0, что указывает на то, что итерация завершена и вся коллекция пройдена.
- Начиная новую итерацию с 0 в качестве курсора, мы вызываем команду СКАНИРОВАНИЯ до тех пор, пока команда не вернется к курсору 0, который мы называем полным обходом.
Возвращаясь к сути, давайте решим предыдущие проблемы. Давайте упростим структуру dict, оставив только две основные структуры хэш-таблиц. Теперь у нас есть четыре элемента: 12, 13, 14 и 15, если предположить, что алгоритм хэширования избыточен.
- Предположим, мы используем команду СКАНИРОВАНИЯ на нем перед повторным отображением. Основываясь на пунктах знаний, о которых мы говорили ранее, поскольку сканирование основано на постепенном обходе курсоров, мы предполагаем, что команда СКАНИРОВАНИЯ прекращает обход только до положения курсора 1:
- Мы получаем результат первого обхода следующим образом:
- Начните заново.
- В конце повторного просмотра мы снова пройдемся по нему, используя команду СКАНИРОВАНИЯ. Поскольку последний возвращенный курсор равен 1, мы продолжаем переход от 1, но на этот раз мы должны пройти в новой хэш-таблице:
- Результаты выполнения второй команды СКАНИРОВАНИЯ: 12, 13, 14, 15
Затем мы объединяем результаты двух сканирований, 12, 12, 13, 14, 15. Мы обнаружили, что элемент 12 был пройден более одного раза, что не соответствовало нашим ожиданиям. Таким образом, мы приходим к выводу, что: Выполнение команд СКАНИРОВАНИЯ во время повторного выполнения может привести к избыточности результатов обхода 。
Решение
Для того, чтобы решить проблему повторяющегося обхода в процессе повторного хэширования, расширения и сокращения, red вносит следующие изменения в индекс хэш-таблицы (v-индекс хэш-таблицы):
v = rev(v); v++; v = rev(v);
Сначала инвертируйте курсор, добавьте один, а затем инвертируйте, что мы называем операцией “high ++”. Эти шаги предназначены для вычисления индекса следующей ячейки в хэш-таблице через предыдущий индекс. Давайте возьмем пример: вначале ведро в 00 не движется. После нормального низкого + за ведром в 00 должно следовать 01. Но теперь это высокий ++, поэтому индекс для исходной позиции 01 будет равен 10… и так далее. Наконец, индексы хэш-таблицы изменяются с 00, 01, 10, 11 на 00, 10, 01, 11 в исходном порядке, как показано на рисунке: гарантирует ли это, что мы не повторим обход при многократном выполнении команд сканирования? Затем наступает момент, чтобы стать свидетелем чуда:
- Прежде всего, СКАНИРОВАНИЕ выполняется перед повторным просмотром. Аналогично, давайте предположим, что команда СКАНИРОВАНИЯ останавливается, перейдя только в положение курсора 1:
- Мы получаем результат первого обхода:12
Начните пересказывать
- В конце повторного просмотра мы снова пройдемся по нему, используя команду СКАНИРОВАНИЯ. Обратите внимание, что последний возвращенный курсор равен 2, и мы продолжаем переход с 2 позиций, также в новой хэш-таблице:
- Мы видим, что после небольшой модификации индекса мы можем решить проблему итерации СКАНИРОВАНИЯ, вызванную перестановкой. Исходный код для обхода dict выглядит следующим образом:
unsigned long dictScan(dict *d,
unsigned long v,
dictScanFunction *fn,
dictScanBucketFunction* bucketfn,
void *privdata)
{
dictht *t0, *t1;
const dictEntry *de, *next;
unsigned long m0, m1;
if (dictSize(d) == 0) return 0;
// If rehash is not performed at SCAN
if (!dictIsRehashing(d)) {
t0 = &(d->ht[0]);
m0 = t0->sizemask;
/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
de = t0->table[v & m0];
While (de) {// traverses the linked list that is attached to the back of the same bucket
next = de->next;
fn(privdata, de);
de = next;
}
/* Set unmasked bits so incrementing the reversed cursor
* operates on the masked bits */
v |= ~m0;
/* Increment the reverse cursor */
V = Rev (v); // inversion V
V++; // After inversion is high++.
V = Rev (v); // Reverse back to get the next cursor value
// If rehash is in progress at SCAN time
} else {
t0 = &d->ht[0];
t1 = &d->ht[1];
/* Make sure t0 is the smaller and t1 is the bigger table */
if (t0->size > t1->size) {
t0 = &d->ht[1];
t1 = &d->ht[0];
}
m0 = t0->sizemask;
m1 = t1->sizemask;
/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
de = t0->table[v & m0];
While (de) {// traverses the linked list that is attached to the back of the same bucket
next = de->next;
fn(privdata, de);
de = next;
}
/* Iterate over indices in larger table that are the expansion
* of the index pointed to by the cursor in the smaller table */
do {
/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
de = t1->table[v & m1];
While (de) {// traverses the linked list that is attached to the back of the same bucket
next = de->next;
fn(privdata, de);
de = next;
}
/* Increment the reverse cursor not covered by the smaller mask.*/
v |= ~m1;
V = Rev (v); // inversion V
V++; // After inversion is high++.
V = Rev (v); // Reverse back to get the next cursor value
/* Continue while bits covered by mask difference is non-zero */
} while (v & (m0 ^ m1));
}
return v;
}Влияние процесса повторной обработки на СКАНИРОВАНИЕ ограничено пространством, чтобы показать только эту ситуацию. Дополнительные сведения см. в разделе Принципы команды Redis scan