Словарь серии Redis (6) базовой структуры данных

Redis

предисловие

Redis уже всем знаком, используется в повседневной работе, часто используется на собеседованиях, так насколько глубоко мы его понимаем?

Я прочитал несколько книг, связанных с Redis, попытался понять его конкретную реализацию и записал некоторые базовые структуры данных и принципы реализации.

Эта статья познакомит вас с низкоуровневым интерфейсом Redis.дикт (словарь)метод реализации. Это одно из основных реализаций хэш-ключей и отсортированных клавишных клавиш в Redis.

2020-01-06-17-50-12

Как вы можете видеть на рисунке, когда я помещаю два коротких значения в хэш-структуру, метод кодирования хэшаziplist, а когда я вставляю более длинное значение, кодировка хеша становитсяhashtable.

Примечание. Читатель этой статьи по умолчанию имеет базовое представление о структуре данных хеш-таблицы, поэтому этот контент не будет подробно объясняться.

определение

Словарь

В качестве общей структуры данных словарь также встроен во многие языки программирования, такие как HashMap в Java и dict в Python, но не в языке C (узнайте, почему люди предпочитают писать на Java, Python и других языках высокого уровня).

Итак, Redis реализует сам словарь:

typedef struct dict{
  // 类型特定函数
  dictType *type;
  // 私有数据
  void *private;
  // 哈希表
  dictht ht[2];
  // rehash 索引，当当前的字典不在 rehash 时，值为-1
  int trehashidx;
}
  • тип и частный

Эти два атрибута установлены для реализации полиморфизма словаря.Когда в словаре хранятся разные типы значений, соответствующие функции копирования и сравнения также различны.Эти два атрибута работают вместе для реализации полиморфных вызовов методов.

  • ht[2]

это длина 2dicthtмассив структур,dicthtЭто хеш-таблица.

  • trehashidx

Это вспомогательная переменная для записи хода процесса REHASH и того, выполняет ли он такую ​​информацию, как REHASH.

Прочитав введение в поле, мы обнаружили, чтоСловарьЭта структура данных по существу вернаhashtableПростая инкапсуляция словаря, поэтому детали реализации словаря в основном сводятся к хеш-таблице.

хеш-таблица

Хеш-таблица определяется следующим образом:

typedef struct dictht{
  // 哈希表的数组
  dictEntry **table;
  // 哈希表的大小
  unsigned long size;
  // 哈希表的大小的掩码，用于计算索引值，总是等于 size-1
  unsigned long sizemasky;
  // 哈希表中已有的节点数量
  unsigned long used;
}

Узлы в хеш-таблице определяются следующим образом:

typedef struct dictEntry{
  // 键
  void *key;
  // 值
  union {
    void *val;
    uint64_tu64;
    int64_ts64;
  }v;

  // 指向下一个节点的指针
  struct dictEntry *next;
} dictEntry;

Если вы посмотрите на исходный код HashMap на Java, вы обнаружите, что все это так знакомо. Поэтому я не объясняю подробно каждое из этих свойств.

2020-01-06-18-22-43

На картинке выше показан словарь, который не находится в состоянии перефразирования. Видно, что словарь содержит две хэш-таблицы, одна из которых имеет значение null, а другая имеет размер = 4, две из которых хранят определенные пары ключ-значение, и не возникло конфликта хэшей.

хеш-алгоритм

При добавлении элемента в хеш-таблицу сначала необходимо вычислить хеш-значение текущего значения ключа, а затем найти слот, в который он будет помещен, в соответствии с хэш-значением. Так как значения хеша могут конфликтовать, выбор алгоритма хэширования особенно важен, а значения ключей должны быть разбросаны достаточно равномерно.

Redis использует некоторые отраслевые алгоритмы для реализации процесса хеширования.

В Redis 5.0 и 4.0 используется алгоритм хэширования siphash. Siphash может производить выходные данные с большей случайностью, когда входное значение ключа невелико.

В Redis 3.2, 3.0 и 2.8, используя хеш-алгоритм Murmurhash2, Murmurhash может дать лучшее случайное распределение, когда входное значение является регулярным.

Конечно, два вышеупомянутых алгоритма имеют одну общую черту: производительность вычислений очень хорошая, что соответствует характеристикам продукта Redis.

После того, как хэш закончится, индекс текущего значения ключа будет определяться по длине текущей хеш-таблицы, а из-за ограниченной длины рано или поздно возникнет проблема, что два значения ключа должны быть размещены в той же позиции, что часто называют проблемами хэш-конфликта.

хэш-коллизия

Поскольку это хеш-таблица, возникает проблема конфликта хэшей.

Хеш-таблица Redis обрабатывает конфликты хэшей так же, как HashMap в Java, выбирая метод группирования, который часто называют методом цепных адресов. Хеш-таблица имеет два измерения. Первое измерение — это массив, а второе — связанный список. При возникновении конфликта хэшей конфликтующие узлы соединяются с помощью связанного списка и помещаются в одно и то же ведро.

Поскольку вторым измерением является связанный список, мы все знаем, что эффективность поиска в связанном списке ниже, чем в массиве. Затем, если конфликт хэшей серьезный, а односвязный список слишком длинный, эффективность запросов к хэш-таблице быстро упадет.

Расширять и сжимать

Когда хэш-таблица слишком переполнена, эффективность поиска снижается.Когда хэш-таблица слишком разрежена, это слишком расточительно для памяти.В это время требуются соответствующие операции расширения и сжатия.

Если вы хотите расширить или сжать, вам нужно описать уровень заполнения текущей таблицы hasd, который не может быть основан на ощущениях. Вот и все负载因子это понятие.

负载因子используется для описания того, насколько хорошо заполнена хэш-таблица в данный момент. Формула расчета:负载因子=哈希表以保存节点数量 / 哈希表的大小.

В реализации Redis есть три правила расширения и сжатия:

  1. Когда Redis не выполняет операции, связанные с BGSAVE, и负载因子>1при расширении.
  2. когда负载因子>5, принудительное расширение.
  3. когда负载因子<0.1при усадке.

В зависимости от того, выполняет ли программа в настоящее время операции, связанные с BGSAVE, условия коэффициента загрузки, необходимые для расширения емкости, различаются.

Это связано с тем, что при выполнении операции BGSAVE присутствует дочерний процесс, и операционная система будет использовать копирование при записи для оптимизации эффективности дочернего процесса. Redis старается избегать расширения при наличии подпроцессов и старается максимально экономить память.

Читатели, знакомые с хеш-таблицами, должны знать, что во время раскрытия используется перехеширование.

Поскольку все текущие узлы необходимо переместить в хэш-таблицу непостоянного размера, и она должна быть как можно более однородной, необходимо повторно хешировать все узлы в текущей хеш-таблице, то есть повторно хэшировать.

прогрессивный хэш

принцип

В Java HashMap метод реализации заключается в создании новой хеш-таблицы, одновременном выполнении повторного хэширования всех текущих узлов, а затем освобождении исходной хеш-таблицы и сохранении новой таблицы.

В отличие от Redis, Redis использует метод, называемый прогрессивным хешированием, для удовлетворения собственных потребностей в производительности.

Это оригинальный вопрос из интервью, который я задал: в чем разница между структурой словаря Redis и Rehash в Java HashMap в перефразировании?

Rehash необходимо переместить все элементы, что является проблемой эффективности O (N).Выполнение этой операции со словарем с большим объемом данных требует много времени.

Для однопоточного Redis трудно принять такую ​​задержку, поэтому Redis предпочитает использовать стратегию пошагового перемещения.

Redis реализует прогрессивное хеширование, процесс выглядит следующим образом:

  1. Если текущие данные находятся в ht[0], то сначала выделите достаточно места для ht[1].
  2. В словаре поддерживается переменная, rehashindex = 0. Она используется для указания хода выполнения текущего перефразирования.
  3. Во время повторного хеширования каждый раз, когда словарь добавляется, удаляется, изменяется и выполняется поиск, после завершения фактической операции будет выполняться операция повторного хеширования, и ht[0] будет помещен вrehashindexЗначение в позиции перефразируется в ht[1]. Увеличьте rehashindex на единицу.
  4. При непрерывном выполнении все значения исходного ht[0] всегда будут перехэшироваться, и на этом процесс перехеширования завершится. Установите rehashindex на -1.

В описанном выше процессе не упомянуты две проблемы:

  1. А если сервер бесплатный? В течение нескольких часов в середине не поступает никаких запросов, так что это пустая трата памяти, чтобы держать две таблицы одновременно?

Решение состоит в том, чтобы добавить операцию, помогающую перефразировать в функции синхронизации Redis, чтобы, если сервер простаивает, перефразирование выполнялось быстрее.

  1. Как хеш-таблица может предоставлять услуги внешнему миру, поддерживая при этом две таблицы?

Решение: Для операции добавления добавьте ее непосредственно в ht[1], чтобы это могло гарантировать, что количество ht[0] будет только уменьшаться, а не увеличиваться, так что процесс повторного хеширования может быть завершен. И удаление, изменение, запрос и другие операции будут выполняться на ht[0], если результат не получен, он переходит на ht[1] и выполняет его снова.

Преимущества прогрессивного хеширования очевидны.Он принимает идею «разделяй и властвуй» и распределяет операцию перехеширования на каждую операцию хеш-таблицы и временной функции, избегая давления на производительность, вызванного централизованным перехешированием.

В то же время прогрессивное хеширование также приносит проблему, то есть во время перехеширования нужно сохранять две хеш-таблицы, что занимает немного больше памяти, и если сервер redis переполнен памятью, вдруг Rehash вызовет большое количество ключей, подлежащих выбраковке.

апплет

Изучаем ли мы прогрессивное хеширование для интервью? Если это не для интервью, то нам не нужно проектировать Redis, зачем нам это знать?

Я лично чувствую, что мы здесь, чтобы понять его разум. Через день после того, как я закончил изучать прогрессивное хеширование, я ответил на вопрос пользователя сети на форуме.

Его вопрос заключается в следующем сценарии:

有两张表，一张工作量表，一张积分表，积分=工作量*系数。
系数是有可能改变的，当系数发生变化之后，需要重新计算所有过往工作量的对应新系数的积分情况。
而工作量表的数据量比较大，如果在系数发生变化的一瞬间开始重新计算，可以会导致系统卡死，或者系统负载上升，影响到在线服务。
怎么解决这个问题？

Насколько я понимаю, это можно решить с помощью идеи прогрессивного перефразирования redis.

Исходные данные (исходная таблица рабочей нагрузки), коэффициент загрузки достигает определенного значения (изменение коэффициента), перефразирование (пересчет всех значений)

Все элементы живы.

Нам просто нужно записать дополнительную переменную, которая отмечает процесс пересчета в процессе. Идея после этого полностью соответствует Redis.

  1. Во-первых, мы можем помочь пользователю рассчитать новые баллы, когда он запрашивает свои баллы. для разгона давления в системе.
  2. Если давление в системе не высокое, вы можете пересчитать небольшую часть (партию) в системном запланированном задании, а конкретное количество можно определить по количеству данных.

Это прекрасно решает проблему производительности.На уровне кода просто добавляется параметр записи и добавляется «триггер» к интерфейсу, что не составляет труда~.

Вопросы для размышления: почему вам не нужно учитывать bgsave при уменьшении масштаба?

Это вопрос для размышления в «Redis Deep Adventure: основные принципы и практика применения», который я прочитал, и я записываю здесь свое личное понимание.

Учет BGSAVE при расширении емкости связан с тем, что для расширения емкости необходимо применить много дополнительной памяти, а связанный список будет повторно связан (в случае конфликта), что вызовет большую фрагментацию памяти и займет больше памяти. , вызывая давление в системе.

В процессе создания, поскольку память относительно мала, она освободит часть памяти, которая была использована, и давление системы не увеличит давление. Поэтому нет необходимости учитывать, выполняется ли операция BGSAVE.

Суммировать

Словарная структура данных Redis, как и структура данных таблицы переходов в следующей статье, является часто задаваемым вопросом в интервью.

В словаре Redis массив table[2] используется для хранения двух хэш-таблиц, обычно используется только одна из них, а другая таблица используется при перехешировании.

Чтобы повысить свою производительность, Redis не завершает процесс повторного хеширования за один раз, а использует стратегию прогрессивного хеширования, чтобы постепенно перефразировать исходные элементы в новую хеш-таблицу, пока она не будет завершена.

Что касается других аспектов, то она не сильно отличается от хэш-таблиц на других языках, таких как алгоритмы хеширования и способы разрешения хеш-коллизий.

Справочная статья

Проектирование и реализация Redis (второе издание)

«Redis Deep Adventures: основные принципы и практика применения»


над.

свяжитесь со мной

Наконец, приглашаю вас обратить внимание на мой личный публичный аккаунт [Huyan Shi], я буду время от времени обновлять учебные заметки многих бэкенд-инженеров. Вы также можете связаться со мной напрямую в публичном аккаунте, личном сообщении или электронной почте, Вы должны все знать и все говорить.


Все вышеизложенное является личными мыслями, если есть какие-либо ошибки, пожалуйста, исправьте их в комментариях.

Добро пожаловать на перепечатку, пожалуйста, подпишите и сохраните исходную ссылку.

Контактный адрес электронной почты: huyanshi2580@gmail.com

Дополнительные заметки об обучении см. в личном блоге или подпишитесь на общедоступную учетную запись WeChat ------>Хуян тен

Категории