Рубрики
Uncategorized

Следуйте за исходным кодом DBB для чтения – Redis 7 – кодирование объектов простая динамическая строка

Автор оригинала: David Wong.

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

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

журнал сервера(LL_WARNING,”SIGTERM получен, но при попытке завершить работу сервера возникли ошибки, проверьте журналы для получения дополнительной информации”);

Redis адаптирует SDS для представления строк, когда ему требуется не только буквальное количество строк, но и строковое значение, которое можно изменить. Например, в базе данных пары ключ-значение, содержащие строковые значения, реализуются с помощью SDS внизу.

Или, например, возьмите простую команду SET и выполните следующие команды

redis> SET msg "hello world"
ok

Затем Redis создаст новую пару ключ-значение в данных, где:

  • Ключом пары ключ-значение является строка-строка, а базовой реализацией объекта является SDS, содержащий строку “msg”.
  • Значение пары ключ-значение также является строковым объектом, а базовой реализацией объекта является SDS, содержащий строку “привет, мир”.

В дополнение к хранению строковых значений в базе данных, SDS также используется в качестве буфера. Буфера в модуле A и входной буфер в состоянии клиента-все это реализовано SDS.

Далее давайте подробно познакомимся с SDS.

Определение 1 SDS

В sds.h мы увидим следующую структуру:

typedef char *sds;

Как вы можете видеть, SDS эквивалентен символу char. Тип. Это связано с тем, что SDS должен быть совместим с традиционным сохранением строк C, поэтому его тип установлен в char. 。 Однако следует отметить, что SDS-это не то же самое, что char*, он также включает структуру заголовка, существует пять типов заголовков, исходный код выглядит следующим образом:

Struct attribute ((packed) sdshdr5 {// discarded
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
Strct__attribute_((_packed_)) sdshdr8 {// string type with length less than 2 ^ 8
    Uint8_t len; // SDS saved string length
    Uint8_t alloc; //SDS allocation length
    Unigned char flags; // tag bit, 1 byte, using the type of SDS stored in low 3 bits, not used in high 5 bits
    Char buf []; // Stored real string data
};
Strct__attribute_((_packed_)) sdshdr16 {// string type with length less than 2 ^ 16
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
Strct__attribute_((_packed_)) sdshdr32 {// string type with length less than 2 ^ 32
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
Strct__attribute_((_packed_)) sdshdr64 {// string type with length less than 2 ^ 64
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

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

Полная структура SDS состоит из двух смежных частей по адресу памяти:

  • Заголовок: Включает длину строки (len), максимальную емкость (alloc) и флаги (за исключением sdshdr5).
  • Buf []: Массив строк. Длина этого массива равна максимальной емкости плюс 1, в которой хранятся реальные строковые данные.

На рис. 1-1 показан пример SDS:

В примере поля описаны следующим образом:

  • Выделение: Пространство, выделенное SDS. На рисунке показано, что размер выделенного пространства равен 10.
  • Len: SDS сохраняет размер строки. На рисунке показана строка с сохраненными пятью байтами.
  • Buf []: Длина этого массива равна максимальной емкости плюс 1, в которой хранятся реальные строковые данные. Первые пять байтов, представляющих число на рисунке, сохраняют пять символов “H”, “e”, “l”, “l”, “o”, в то время как последний байт сохраняет пустую строку “0”.

SDS следует соглашению о том, что строки C заканчиваются пустыми символами, и размер сохраненных пустых символов не учитывается в атрибуте len SDS. Кроме того, добавление пустых строк в конец строки и другие операции автоматически выполняются функциями SDS (связанные функции в sds. Файл C).

Кроме того, в соответствии с Соглашением о окончании нулевого символа вы можете напрямую повторно использовать некоторые функции в библиотеке строк C.

Например, мы можем использовать его напрямую. printf() Функция печати s->buf : printf("%s", s->buf); Таким образом, мы можем распечатать строку “Redis” непосредственно с помощью функций C, не записывая функции печати транскодирования для SDS.

2 В чем преимущества SDS перед строками C

В языке Си массив символов длиной N + 1 используется для представления строки длиной N, и последним элементом массива символов всегда является пустой символ “0”.

Это строковое представление на языке Си не может соответствовать требованиям готовности к повторной защите, эффективности и функциональности строк. Таким образом, Red разработан SDS для удовлетворения своих собственных потребностей. Далее, мы признаем преимущества SDS перед строками C из следующих аспектов:

  1. Возвращает длину строки;
  2. Переполнение буфера;
  3. Количество перераспределений памяти при изменении строк;
  4. Двоичная безопасность;

2.1 Постоянная сложность для длины строки

Поскольку строка C не записывает информацию о своей собственной длине на языке C, чтобы получить длину строки C, программа должна пройти всю строку, пока не встретит пустой символ, представляющий конец строки. Сложность этой операции составляет O (N).

Для Redis, как только вы столкнетесь с очень длинной строкой, используйте STRLEN При командовании это может легко повлиять на производительность системы.

В отличие от строки C, поскольку SDS записывает длину строки, сохраненной SDS в атрибуте len, сложность получения длины SDS составляет всего O (1).

И работа по настройке и обновлению длины SDS выполняется автоматически API SDS при ее выполнении, поэтому нет необходимости изменять длину вручную с помощью SDS.

Используя SDS, Redis снижает сложность, необходимую для получения длины строки с O (N) до (1), гарантируя, что получение длины строки не является узким местом производительности для Redis.

2.2 Устранение Переполнения Буфера

Строка C не записывает свою собственную длину, что не только усложняет получение длины строки, но и Легко вызывает переполнение буфера 。

На языке Си strcat() Функция соединяет содержимое строки SRC с концом строки dest:

char *strcat(char *dest, const char *src);

Поскольку строка C не записывает свою собственную длину, при выполнении функции strcat предполагается, что пользователь выделил достаточно памяти для dest, чтобы вместить все содержимое строки SRC. Как только это предположение не подтвердится, произойдет переполнение буфера.

Например, предположим, что программа имеет две строки C S1 и S2, которые находятся рядом друг с другом в памяти, где S1 содержит строку “redis”, а S2 содержит строку “mysql”. Структура хранилища показана на рис. 2-1.

Если мы выполним следующее утверждение:

strcat(s1, " 666");

Измените содержимое S1 на “красный-666”, но это не реализовано strcat() Прежде чем выделить достаточно места для s1, выполните strcat() После этого данные S1 будут удалены в пространство, где находится S2, что приведет к неожиданному изменению содержимого, сохраненного s2, как показано на рисунке 2-2:

В отличие от строки C, стратегия пространственного распределения Sdss полностью исключает возможность переполнения буфера: когда API SDS необходимо изменить SDS, API сначала проверяет, удовлетворяет ли пространство SDS требованиям модификации. Если нет, API автоматически расширяет пространство SDS до размера, необходимого для модификации, а затем выполняет фактическую операцию модификации. Таким образом, использование SDS не требует ручного изменения размера пространства SDS и не вызывает проблемы переполнения буфера, упомянутой ранее.

2.3 Уменьшите количество перераспределений памяти

Поскольку длина строки C slen и длина базового массива salen всегда имеют следующую взаимосвязь:

Сален + 1;//1-длина пустых символов

Поэтому каждый раз, когда строка C увеличивается или сокращается, операция перераспределения памяти всегда выполняется над массивом строк C:

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

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

Для Redis необходимо оптимизировать все трудоемкие операции. Исходя из этого, SDS для быстрого роста и сокращения операций, за счет Пространственного предварительного распределения и Высвобождение инертного пространства Два способа оптимизации.

2.3.1 Пространственное Перераспределение

Предварительное пространственное распределение относится к: Когда пространство SDS необходимо расширить, программа не только выделяет необходимое пространство, но и выделяет дополнительное неиспользуемое пространство для SDS. 。

Для пространственного расширения SDS исходный код выглядит следующим образом:

# sds.c/sdsMakeRoomFor()
...
Newlen = len + addlen; // SDS latest length
If (newlen < SDS_MAX_PREALLOC)// Pre-assigned maximum SDS_MAX_PREALLOC is defined in sds.h with a value of 1024*1024
    newlen *= 2;
else
    newlen += SDS_MAX_PREALLOC;
...

Как видно из исходного кода, пространственное расширение можно разделить на два случая:

  • Новая длина меньше Предварительно выделенного максимума. На этом этапе программа напрямую добавит последнюю длину неиспользуемого пространства для SDS. Каштан, например, имеет 10-байтовую строку s1. Когда строка “redis” добавляется в s1, программа не только выделит достаточно места для s1, но и перераспределит предварительно используемое пространство последней длины для s1. Таким образом, фактическая длина S1 становится: 15 + 15 + Байт.
  • Новая длина больше Предварительно выделенного максимума. На этом этапе, поскольку последняя строка большая, программа не будет предварительно выделять так много места, а только предварительно выделит максимальное пространство. Возьмем, к примеру, каштан, существующую 3-метровую строку s2. Когда строка длиной 2 М добавляется в s1, программа не только добавляет 2 М для хранения новой длины, но также выделяет 1 миллион (SDS_MAX_PREALLOC) предварительно используемого пространства для s2. Таким образом, фактическая длина S2 становится: 3 М + 2 М +1 М + 1 байт 。

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

2.3.2 Высвобождение Инертного Пространства

Предварительное выделение соответствует росту строки, в то время как высвобождение пространства соответствует сокращению строки.

Высвобождение инертного пространства относится к: При сокращении SDS программа не сразу восстанавливает лишние байты после сокращения, ожидая дальнейшего использования. 。

Возьмите каштан, мы его используем. sdstrim() Функция удаления всех указанных символов из SDS, показанная ниже:

Для приведенных выше SDS выполните: Sdstrim (s, "l");////Удалите все буквы "l" в Строки SDS

SDS будет изменен, как показано на рисунке 2-4:

Как вы можете видеть, выполните sdstrim() Позже SDS не освободил дополнительное 3-байтовое пространство, но сохранил 3-байтовое пространство в качестве неиспользуемого пространства в SDS для ожидания.

Это происходит благодаря Стратегии высвобождения ленивого пространства SDS позволяет избежать перераспределения памяти при сокращении строк и оптимизирует возможные будущие операции роста.

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

резюме

  1. Redis использует только строки C в качестве литералов, а в большинстве случаев SDS в качестве строкового представления.
  2. SDS имеет несколько преимуществ перед строками C: Постоянная сложность Получает длину строки 、 Устранение переполнения буфера 、 Уменьшите количество перераспределений памяти, необходимых для изменения строк 。

Оригинал: “https://developpaper.com/follow-dbb-read-source-code-redis-7-object-encoding-simple-dynamic-string/”

Читайте ещё по теме: