В первый день строительства в 2021 году друг прислал мне личное сообщение и поделился рецептом его с Али.redisвопрос(Этот парень, должно быть, получил награду в конце года.), мне было очень интересно после прочтения.Тема очень простая. Разберитесь и выложите сюда.Кстати, я сам буду консолидировать фонд.Надеюсь, это поможет братьям, которые берут интервью и которые хотят брать интервью.
Тема примерно такая
Интервьюер: УзнайтеredisизStringЧто лежит в основе реализации структуры данных?
Тиези: Конечно, я знаю, основываясь наSDSосуществленный
Интервьюер:redisиспользуетсяCЯзык разработан, так почему бы не использовать его напрямуюCСтрока, также индивидуально разработанаSDSКак быть с такой структурой?
Железо:...
"На самом деле видно, что интервьюер хочет увидеть, остается ли Тиези только на уровне использования Redis или проводит более глубокое исследование базовой структуры данных.
мы знаемredisиспользуетсяCнаписано, но не полностью используется напрямуюCСтрока, но его имя снова построено простой динамической строкойSDSАбстрактный тип для (простая динамическая строка).
redisтакже поддерживает использованиеCТрадиционная строка языка используется только в некоторых местах, где строку не нужно изменять, например, при выводе статических символов.
И мы используем в разработкеredis, часто часто изменяйте значение строки, на этот раз будет использоватьсяSDSдля представления строкового значения. это стоит тогоУведомление: В базе данных Redis,key-valueПары ключ-значение, содержащие строковые значения, определяютсяSDSбыть реализованным.
Например: вredisвыполнить самое простоеsetкоманда, тоredisБудет создана новая пара ключ-значение.
127.0.0.1:6379> set xiaofu "程序员内点事"
пара ключ-значениеkeyиvalueОба являются строковыми объектами, а базовая реализация объекта представляет собой две строки хранения.xiaofuи程序员内点事изSDSструктура.
Другой пример: я помещаю данные в список, и Redis создаст новую пару ключ-значение.
127.0.0.1:6379> lpush xiaofu "程序员内点事" "程序员小富"
В настоящее время ключ пары "ключ-значение" такой же, как указано выше, и он по-прежнему является строковым объектом, реализованным SDS. Значением пары "ключ-значение" является объект-список, содержащий два строковых объекта, а нижняя часть Слой этих двух объектов также реализуется SDS.
Структура паспорта безопасности
Структура данных значений SDS, в основном состоящая изlen,free,buf[]Эти три свойства складываются.
struct sdshdr{
int free; // buf[]数组未使用字节的数量
int len; // buf[]数组所保存的字符串的长度
char buf[]; // 保存字符串的数组
}
вbuf[]Фактическая строка сохраненаcharтип массива;freeУказывает количество неиспользуемых байтов в массиве buf[];lenПредставляет длину строки, сохраненной массивом buf[].
Например, на рисунке выше показаноbuf[]Содержит строку длиной 6 байт, количество неиспользуемых байтовfreeЭто 0, но зоркие ученики обнаружат, что это, очевидно, 7 символов, и есть еще один"\0"А?
упомянутый вышеSDSне используется напрямуюCСтрока по-прежнему использует некоторые функции C, такие как следующиеCПравило о том, что строка заканчивается символом пробела, так что вы также можете использовать функции части строки C. Для SDS один байт, занимаемый пустой строкой, не учитывается.lenВ атрибуте для него будет выделено дополнительное место.
После краткого понимания структуры SDS давайте рассмотрим преимущества SDS по сравнению со строками C.
эффективный
Например: использовать на работеredis, часто черезSTRLENкоманда для получения длины строки вSDSв структуреlenАтрибут записывает длину строки, поэтому мы получаем длину строки напрямую.len, сложность O(1).
Если строка C, длина строки во время приобретения, необходимость прохождения всей строки, до конца траверса к пробелам (C Cinsoutered String представляет собой полный пространственный символ), когда сложность o (n) Отказ
В сценариях с высоким параллелизмом строки часто перебираются, и получение длины строки, вероятно, станетredisузкое место в производительности, поэтому производительность SDS выше.
переполнение данных
Как упоминалось выше, строка C не записывает свою длину, способ хранения двух соседних строк может быть следующим, и для строки выделяется соответствующее место в памяти.
Если я хочу поставить“程序员内点事”изменить на“程序员内点事123”, но память, выделенная ранее, составляет всего 6 байт, а измененная строка требует проставления 9 байт, что мне делать?
ни за что侵占Пространство соседних строк, переполнение собственных данных вызывает изменение содержимого других строк.
SDS очень хорошо избегает этого.Когда нам нужно изменить данные, мы сначала проверяем текущее пространство SDS.lenЕсли он удовлетворен, если нет, он автоматически расширит пространство до размера, необходимого для модификации, а затем выполнит модификацию, как показано на следующем рисунке.
Но есть особое местов“程序员内点事”6 байт расширения до“程序员内点事123”9 байт спустя, найденоfreeЗначение атрибута становится общей длиной расширенной строки, которая включает описанную ниже стратегию перераспределения памяти.
стратегия перераспределения памяти
Длина строки C фиксирована, поэтому каждый раз, когда строка увеличивается или сокращается, необходимо выполнять перераспределение памяти, а алгоритм перераспределения памяти обычно требует много времени.Если программа не изменяет строку часто, она еще приемлемо.
Но, к сожалению,redisКак база данных, данные определенно будут часто изменяться.Если каждое изменение выполняется, память выполняется, то это серьезно повлияет на производительность.
SDS решает проблему выделения памяти, когда строки увеличиваются и уменьшаются, с помощью двух стратегий перераспределения памяти.
1. Предварительное выделение места
Стратегия предварительного распределения пространства для оптимизации SDSрост строкиОперация, когда строка изменяется и пространство SDS необходимо расширить, не только пространство, необходимое для модификации, будет выделено SDS, но и дополнительное неиспользуемое пространство будет выделено SDSfree, в следующий раз, когда вы его измените, сначала проверьте неиспользуемое пространствоfreeЕсли он удовлетворен, он не доступен для расширения пространства.
Благодаря стратегии предварительного распределения пространства,redisЭто может эффективно уменьшить количество перераспределений памяти, вызванных непрерывными операциями роста строк.
Дополнительное выделение неиспользуемого пространстваfreeправило:
- Если строка SDS изменена,
lenзначение меньше, чем1M, Затем на время выделяется дополнительное неиспользуемое пространствоfreeразмер сlenравный. - Если строка SDS изменена,
lenзначение больше или равно1M, то дополнительно выделить неиспользуемое в это время местоfreeразмер1M.
2. Освобождение инертного пространства
Стратегия высвобождения инертного пространства используется для оптимизации SDSСокращение строкиоперации, когда строка SDS укорачивается, перераспределение памяти не будет выполняться немедленно, чтобы освободить лишнее пространство, ноfreeСвойство записывает эти пробелы и может использоваться напрямую, если есть последующая операция увеличения.
Разнообразие форматов данных
Символы в строке C должны соответствовать определенному формату кодирования, и, как мы упоминали выше, строка C начинается с\0Нулевая строка символов, которая определяет конец, поэтому не может содержать строку внутри\0Да, иначе его примут за несколько.
Из-за этого ограничения строки C могут хранить только текстовые данные, а данные в двоичном формате, такие как аудио, видео и изображения, не могут быть сохранены.
Redis будет работать в бинарном режимеBufДанные в массиве, так что делать какие-либо ограничения и фильтрация данных, хранящихся в нем, до тех пор, что хранится в, что извлекается.
Суммировать
Вышеупомянутое является лишь небольшим базовым знанием структуры данных Redis, это не сложно, но, исходя из моего опыта интервью, если вам задают такой вопрос, не просто расплывчато говорите, что нижний слой - это SDS, и объясните, почему это реализовано таким образом.
Во-первых, вы можете показать, что у вас есть прочные базовые навыки, если вы изложите это четко и организованно, это очень хороший бонус, если вы проявите инициативу, чтобы рассеять мысль интервьюера, спрашивающего, конечно, вы боитесь людей, которые не играют в карты по заведенному порядку!
"Сотни различных технических электронных книг перебраны, и общедоступное количество студентов, которым это нужно [Внутри программатора] в ответ[666] Поднимать. Техническая группа почти заполнена, и студенты, которые хотят присоединиться, могут добавить меня в друзья, и давайте поговорим о технологиях с большими парнями.