Рубрики
Uncategorized

[Изучение исходного кода Redis5] Простая динамическая строка SDS, 2009-04-15

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

байюнь

Все видео: https://segmentfault. com/a/11…

  • Сегодня мы официально вводим redis 5 изучение исходного кода. Redis-это база данных ключевых значений, написанная на языке Си, основанная на памяти, однопроцессорная и постоянная. Он решает проблему низкой скорости доступа к диску и значительно повышает скорость доступа к данным, поэтому его часто используют в качестве кэша .
  • Так почему же красный цвет такой быстрый? Давайте сначала шаг за шагом раскроем эту тайну с точки зрения структуры данных внутреннего хранилища.
  • Среди распространенных команд для поездок, таких как set, get и т. Д., Наиболее часто используется строковый тип. В redis тип данных, в котором хранятся строки, называется Простой динамической строкой или SDS. Как это работает в redis?

Вводить

  • Обзор структуры zend_string, о которой мы упоминали ранее в анализе исходного кода PHP7:
struct _zend_string {
    Zend_refcounted_h gc; /* reference count, related to garbage collection, not yet expanded*/
    Zend_ulong h; /* redundant hash value to avoid repeated calculation when calculating hash value of array key*/
    Size_t len; /* memory length*/
    Charval [1]; /* Flexible Array, True Storage of String Values*/
};
  • Как упоминалось ранее в примечаниях к строкам PHP в PHP 7 Source Learning 2019-03-13, самое важное при разработке структуры для хранения строк-это их хранение. длина и Содержимое самой строки . Что касается того, почему длина хранилища должна решать проблему двоичной безопасности и может получить доступ к длине строки с постоянной сложностью, подробности можно увидеть в приведенной выше статье.

Сравнение новых и старых структур SDS

  • До redis 3.2.x структура хранения SDS была следующей:
struct sdshdr {
    Int len; // memory length
    Int free; // Residual space for flexible arrays that store string content
    Char buf []; // Flexible Array, True Storage of String Values 
};
  • Возьмем в качестве примера сильное “Красное”. Давайте посмотрим, как он хранится в старой структуре SDS:
  • Свободное поле равно 0, представляя поле buf без оставшегося места для хранения
  • Поле len равно 5, что представляет собой строку длиной 5
  • В поле buf хранится истинное содержимое строки “Redis”
  • Гибкие массивы, в которых хранится строковое содержимое, занимают 6 байт памяти, в то время как остальные поля занимают 8 байт (4 + 4 + байта).
  • В новой версии redis 5 для дальнейшего сокращения объема памяти в процессе хранения строк разделены пять специальных структур хранения, адаптированных к различным длинам строк:
struct __attribute__ ((__packed__)) sdshdr5 {
    Unsigned char flags; // low three-bit storage type, high five-bit storage string length, which is rarely used
    Char buf []; // Flexible array for storing string content
};
struct __attribute__ ((__packed__)) sdshdr8 {
    Uint8_t len; // string length
    Uint8_t alloc; //allocated total space
    Unsigned char flags; //Identify which storage type
    Char buf []; // Flexible array for storing string content
};
struct __attribute__ ((__packed__)) sdshdr16 {
    Uint16_t len; // string length
    Uint16_t alloc; //allocated total space
    Unsigned char flags; //Identify which storage type
    Char buf []; // Flexible array for storing string content
};
struct __attribute__ ((__packed__)) sdshdr32 {
    Uint32_t len; // string length
    Uint32_t alloc; //allocated total space
    Unsigned char flags; //Identify which storage type
    Char buf []; // Flexible array for storing string content
};
struct __attribute__ ((__packed__)) sdshdr64 {
    Uint64_t len; // string length
    Uint64_t alloc; //allocated total space
    Unsigned char flags; //Identify which storage type
    Char buf []; // Flexible array for storing string content
};
  • Мы видим, что структура хранения SDS изменилась с одного до пяти. Разница между ними заключается в том, что поле len длины строки и поле выделения выделенных байтов занимают 1, 2, 4 и 8 байт соответственно (независимо от типа sdshdr5), что определяет, как долго строка может храниться этой структурой (2 ^ 8/2 ^ 16/2 ^ 32/2 ^ 64).
  • Мы отмечаем, что все эти структуры имеют ключевое слово _attribute_((_packed_)), которое указывает компилятору не выравнивать память структуры. Это ключевое слово будет подробно объяснено ниже. Для получения информации о выравнивании структур в памяти, пожалуйста, обратитесь к [Изучение исходного кода PHP 7] 2019-03-08 Примечания по управлению памятью PHP 2.

Просмотр архитектуры хранилища SDS с помощью GDB

  • Затем нам нужно сохранить пример “Redis”, прежде чем мы сможем увидеть, какую структуру использует строка “Redis”. Шаги GDB заключаются в следующем:
  • Сначала загрузите исходный пакет на официальный веб-сайт и скомпилируйте его.
  • Запустите терминал, введите каталог SRC исходного кода redis и запустите redis-сервер в фоновом режиме:
./redis-server &
  • Затем посмотрите на PID фонового процесса текущего redis:
ps -aux |grep redis
  • Запишите PID и отладьте порт с помощью команды gdb-p (например, номер порта 11430).:
gdb -p 11430
  • Затем разорвите точку останова в функции set Command, которая используется для выполнения команды set, а затем используйте команду C для выполнения до точки останова:
(gdb) b setCommand
(gdb) c
  • С сервером redis нам также необходимо запустить клиент redis, а затем запустить другой терминал (также в каталоге SRC), чтобы запустить клиент:
./redis-cli
  • Затем мы выполняем команду set в клиенте redis. Мы устанавливаем ключ на Redis и пару ключ-значение со значением 1:
127.0.0.1:6379> set Redis 1
  • Вернувшись на сервер в нашем предыдущем терминале, мы обнаружили, что он остановился на setCommand:
  • Затем продолжайте N, пока не войдет функция set Generic Command, s, вы можете увидеть наш ключ “Redis”. Это структура объекта (мы пока не будем ее рассматривать). PTR в нем указывает на поле buf строковой структуры. Давайте перевернем его и посмотрим содержимое строки “Red is”.
  • Мы знаем, что независимо от того, какая из этих пяти структур, первая должна быть полем флага, и мы выводим ее значение, равное 1. Что означает “1”? Он используется для определения того, какая из этих пяти струнных структур является:
#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
  • Он имеет значение 1, представляющее тип sdshdr8. Мы можем нарисовать структуру хранения текущей строки:
  • Как мы видим, он занимает 3 + байта, экономя 5 байтов из предыдущих 14 байтов. Уточнив предыдущую длину и разрешив поля (от предыдущего int до int8, int16, int32, int64), пространство памяти, занимаемое строками хранения redis, будет значительно сохранено. Объем памяти очень ценен, и наиболее часто используемым типом данных в redis является строковый тип. Хотя это, кажется, экономит очень мало места, потому что это очень распространено, поэтому преимущества от этого бесконечны.

Роль ключевого слова _attribute ((упаковано))

  • Этот ключ используется для информирования компилятора Выравнивание структуры в памяти не требуется 。
  • Чтобы проверить роль ключевого слова _attribute_((упаковано)) в строковой структуре redis, мы пишем следующий тестовый код:
  #include "stdio.h"
 
  int main(){
      struct __attribute__ ((__packed__))  sdshdr64{
          long long len;
          long long alloc;
          unsigned char flags;
          char buf[];
      };
 
      struct sdshdr64 s;
      s.len = 1;
      s.alloc = 2;
      printf("sizeof sds64 is %d", sizeof(s));
      return 1;
  }
  • Мы определяем структуру, поля которой в основном совпадают со строковой структурой в redis. Если добавлен _attribute_((_packed_)), он не должен быть выровнен по памяти. Если он удален, он должен быть выровнен по памяти, что приведет к потере большего объема памяти, чем предыдущий, поэтому выравнивание сэкономит память. Структурная схема памяти, которую мы теперь предполагаем, должна быть следующей:
  • Давайте сначала проверим, что добавление _attribute_(_packed_)) не ожидается однородным. Адрес памяти в GDB выглядит следующим образом:
  • Как мы видим, buf действительно начинается с адреса 0x171 и не выровнен. Итак, давайте рассмотрим другую ситуацию. Удалить _ Атрибут(_packed_), а затем отладить gdb:
  • Давайте посмотрим, совпадает ли эта картинка с предыдущей (я действительно удалил ее и перекомпилировал!!!). Это показывает, что в текущем случае начальная позиция гибкого массива в строковой структуре redis не зависит от добавления ключевого слова _attribute_((_packed_)). Закрыть за структурой Да, поэтому сохранение памяти неверно. (Гибкие массивы не обязательно во всех случаях следуют структуре. Если вы измените тип баффа на int, он не будет следовать внимательно. Если вам интересно, вы можете отладить его самостоятельно.)
  • Так зачем же добавлять _attribute_(_packed_) сюда? Давайте передумаем. Поскольку мы не можем сэкономить место, можем ли мы сэкономить время? Было бы лучше и эффективнее управлять несогласованной структурой или было бы удобнее и читабельнее писать код?
  • Автор предполагает, что здесь удобнее писать код в инженерном и более читабельным. Моя ссылка заключается в следующем:
  • В операторе sizeof он возвращает размер пространства, занимаемого структурой, который тесно связан с выравниванием. Например, если структура в предыдущем примере не добавляет _attribute_((_packed_)), это означает, что требуется выравнивание памяти, и возвращаемый результат sizeof (struct s) должен быть 24 (8+8+8); если _attribute_(_packed_)), это означает, что выравнивание не требуется, возвращаемый результат должен быть 17 (8+8+1). Давайте распечатаем:
  • Результаты соответствуют нашим ожиданиям. Как мы знаем, когда мы делали gdb, указатель rObj указывал непосредственно на адрес buf гибкого массива, начальный адрес содержимого строки. Итак, откуда вы знаете, что это значения len и alloc? Просто используйте адрес buf PTR – sizeof (структура s). Здесь, если добавляется _attribute_((_packed_)), результат, который он возвращает, равен 17, затем путем прямого вычитания значение len можно прочитать непосредственно в начале структуры. Если _attribute_((_packed_)) не добавлен, результат, который он возвращает, равен 24, и вычитание пойдет не в то место. Вот почему, как мы видим из исходного кода, он действительно находит заголовок текущей строковой структуры таким образом:
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
  • Поэтому мы могли бы спросить: разве вы не использовали buf [- 1] для доступа к нему только что? Или buf [-17], вы также должны иметь доступ к len. Здесь я просто предполагаю, что это может быть последний метод написания, который легче читать и удобнее при реализации инженерного кода. Дальнейшие причины еще предстоит обсудить.

Зачем нам нужно поле выделения?

  • В предыдущих объяснениях мы никогда не упоминали о роли полей выделения. Мы знаем, сколько байтов он в настоящее время выделяет гибким массивам, в которых хранятся строки. Итак, какова роль записи этого поля? То есть Предварительное распределение пространства и Высвобождение инертного пространства Дизайнерские идеи.
  • Предварительное выделение пространства Когда требуется расширение пространства SDS, программа выделяет не только необходимое пространство для модификации SDS, но и дополнительное неиспользуемое пространство для SDS. Например, мы расширяем строку “Redis” до “Redis111”. Приложение не просто выделяет три байта, оно просто подгоняет их под выделенную длину, но и выделяет некоторое дополнительное пространство. Смотрите комментарии к коду ниже для получения подробной информации о том, как распределять. Давайте поговорим об одном из этих распределений, предполагая, что он выделяет 8 байт памяти. Теперь общее пространство памяти составляет 5 +, и мы использовали только первые восемь пространств памяти, оставив пять неиспользуемых пространств памяти. Так зачем же мы это делаем? Это связано с тем, что если мы продолжим расширять его, например, “Redis11111”, перед расширением пространства SDS API проверит, достаточно ли неиспользуемого пространства. Если достаточно, API будет напрямую использовать неиспользуемое пространство, тогда нам не нужно делать еще один системный вызов, чтобы подать заявку на место, и напрямую помещать дополнительные “11” в ранее выделенное пространство. Да. Таким образом,
sds sdsMakeRoomFor(sds s, size_t addlen) {

    void *sh, *newsh;
    Size_t avail = sdsavail (s); // Gets the remaining space available for the current string
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

    /* If the available space is longer than the length of the additional part, it means that the current string has extra space, enough to accommodate the expanded string, without allocating extra space, and returns directly.*/
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    If (newlen < SDS_MAX_PREALLOC) //SDS_MAX_PREALLOC = 1MB, if the length of the expanded string is less than 1MB, the space of the expanded string length * 2 is allocated directly.
        newlen *= 2;
    else
        Newlen += SDS_MAX_PREALLOC; //Expanded length greater than or equal to 1MB, additional allocation of expanded string + 1MB of space

     ...
     Real de-allocation of space
     ...
     sdssetalloc(s, newlen);
     return s;
}
  • Приведенная выше функция sdsavail использует поле alloc, когда она получает оставшееся доступное пространство в строке. В нем записывается общий размер выделенного пространства, что удобно для нас, чтобы определить, требуется ли дополнительное пространство для выделения при выполнении операций добавления строк. Текущий размер оставшегося доступного пространства выделен То есть общий размер выделенного пространства alloc – текущий размер используемого пространства len
static inline size_t sdsavail(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: {
            return 0;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}
  • Высвобождение инертного пространства Инертное пространство Освобождает Операции перехвата строк или сокращения для оптимизации SDS. Когда API SDS необходимо сократить сохраненную строку SDS, программа не сразу восстанавливает сокращенные байты. Таким образом, эти неиспользуемые пространства могут пригодиться, если в будущем будут реализованы операции по росту SDS. Например, мы сокращаем “Redis111” до “Redis”, а затем меняем его на “Redis111”, так что, если мы немедленно восстановим укороченные байты, а затем перераспределим пространство памяти, это пустая трата времени. Если вы подождете некоторое время для восстановления, вы сможете избежать операции перераспределения памяти, необходимой для сокращения строки, и предоставить пространство для расширения для возможных будущих операций роста. API SDS для пустой строки в исходном коде выглядит следующим образом:
/* Modify an sds string in-place to make it empty (zero length).
 * However all the existing buffer is not discarded but set as free space
 * so that next append operations will not require allocations up to the
 * number of bytes previously available. */
void sdsclear(sds s) {
    sdssetlen(s, 0);
    s[0] = '
/* Modify an sds string in-place to make it empty (zero length).
* However all the existing buffer is not discarded but set as free space
* so that next append operations will not require allocations up to the
* number of bytes previously available. */
void sdsclear(sds s) {
sdssetlen(s, 0);
s[0] = '\0';
}
';
}
  • Давайте сосредоточимся на приведенном выше комментарии: Но все дополнительное выделенное пространство не освобождается с пустой строкой, поэтому следующая дополнительная операция над строкой не будет снова вызывать системный вызов для выделения памяти. И исходный код напрямую не вызывает какую-либо функцию, оставшееся пространство сразу после операции опорожнения освобождается, что также подтверждает нашу предыдущую гипотезу.

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