Когда набор содержит только целые числа и количество элементов невелико, Redis будет использовать целочисленный набор в качестве базового хранилища. Одно из его преимуществ заключается в том, что он может сэкономить много памяти. Хотя структура словаря очень эффективна, ее реализация структура относительно сложная и будет выделять больше памяти.
И наш целочисленный набор (intset) может достичь той же эффективности, что и словарь, используя меньше памяти, но также предполагается, что набор может содержать только целочисленные данные, и число не может быть слишком большим. Максимальное количество элементов, которое может хранить целочисленный набор, также отражено в Redis.
OBJ_SET_MAX_INTSET_ENTRIES 512
То есть более 512 элементов или добавление строки или другой структуры данных в коллекцию, Redis преобразует целочисленную коллекцию в структуру словаря.
Во-первых, основная структура данных
Определение структуры intset очень простое и состоит из следующих членов:
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents [];
} intset;
encoding записывает кодировку, используемую текущим intset, с тремя значениями:
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))
length записывает, сколько элементов в настоящее время хранится в целочисленной коллекции, а content записывает нашу фактическую коллекцию данных.Хотя мы видим, что тип элементов массива в структуре зафиксирован как int8_t, на самом деле определение этого int8_t бессмысленно, потому что здесь Метод обработки - нетрадиционные операции с массивами.Хотя поле содержимого определяется как указатель на данные типа int8_t, на самом деле, читает ли redis элементы массива или добавляет новые элементы, это зависит от памяти, непосредственно управляемой кодировкой и поля длины. .
Базовая структура данных по-прежнему очень проста, давайте рассмотрим некоторые из ее основных методов.
2. Реализация основного API
1. Инициализируйте intset
intset *intsetNew(void) {
intset *is = zmalloc(sizeof(intset));
is->encoding = intrev32ifbe(INTSET_ENC_INT16);
is->length = 0;
return is;
}
Можно видеть, что конфигурация вставки по умолчанию использует INTSET_ENC_INT16 в качестве размера хранилища данных и не инициализирует массив содержимого. Обычные массивы должны предварительно определять длину массива, затем выделять память, а затем обращаться к любому элементу массива через content[x].
Однако вставка здесь представляет собой нетрадиционный массив операций, поле кодирования определяет фактический тип каждого элемента в массиве, а поле длины определяет фактическое количество элементов в массиве, поэтому содержимое [x] недопустимо, этот метод будет только выполняться в соответствии с int8_t. Для смещения памяти этот метод не может получить правильные данные, поэтому Redis использует memcpy для прямого смещения адреса в соответствии со значением поля кодирования, чтобы оперировать памятью для чтения данных.
Вот почему массив содержимого не инициализируется при инициализации intset, потому что это не нужно. Всякий раз, когда добавляется элемент, длина исходного массива будет динамически увеличиваться, чтобы вместить новый вставленный элемент.Расширение не будет сильно увеличиваться, только память, занимаемая новым элементом. Конкретные детали мы увидим.
2. Добавьте новые элементы
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
//计算得到新插入的元素的编码
uint8_t valenc = _intsetValueEncoding(value);
uint32_t pos;
if (success) *success = 1;
//如果大于 intset 目前存储元素的编码大小
if (valenc > intrev32ifbe(is->encoding)) {
//触发 intset 升级
return intsetUpgradeAndAdd(is,value);
} else {
//二分搜索当前元素，如果元素已经存在会直接返回
//如果没找到元素，pos 的值就是该元素的位置索引
if (intsetSearch(is,value,&pos)) {
if (success) *success = 0;
return is;
}
//resize 集合，扩容一个元素的内存空间
is = intsetResize(is,intrev32ifbe(is->length)+1);
//移动 pos 后面的元素，以插入我们的新元素
if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
}
//赋值
_intsetSet(is,pos,value);
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
Отсюда мы должны знать, почему данные в intset упорядочены и не повторяются, бинарный поиск — это O(logN), а вставка элемента в intset — это не O(logN), потому что в некоторых случаях будет запускаться операция обновления, или крайние случаи , все элементы будут перемещены, а временная сложность достигнет O(N).
3. Обновление
Сначала мы смотрим на изменения в схеме, а затем анализируем исходный код.Предположим, исходный intset использует 16-битную кодировку для хранения данных, а сначала идут 32-битные данные, что запускает обновление нашей кодировки.
Исходная структура inset выглядит следующим образом:
Новая структура intset расширится и будет выглядеть следующим образом:
Несмотря на то, что память, занимаемая данными, уже выделена, все еще необходимо перенести биты, занимаемые каждым элементом. Подход такой, предположим, что наш новый элемент является значением 65536 типа int_32, тогда сначала мы поместим это 65536 в битовый диапазон [128-159], затем поместим 78 в битовый диапазон [96-127] и Двигаясь вперед и так далее, наконец, мы получим intset после завершения обновления.
Посмотрим на реализацию кода в redis:
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
//intset目前的编码
uint8_t curenc = intrev32ifbe(is->encoding);
//intset即将扩展到的编码
uint8_t newenc = _intsetValueEncoding(value);
int length = intrev32ifbe(is->length);
int prepend = value < 0 ? 1 : 0;
//根据新的元素内存大小重新分配 intset 内存大小
is->encoding = intrev32ifbe(newenc);
is = intsetResize(is,intrev32ifbe(is->length)+1);
//这个地方我先标记一下 @1，下面详细分析
//总体上你可以理解，就是我们上图画的那样，从原集合的最后一个元素
//开始扩大它占用的比特位
while(length--)
_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
//将新元素放进 intset 中
if (prepend)
_intsetSet(is,0,value);
else
_intsetSet(is,intrev32ifbe(is->length),value);
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
Больше ничего объяснять не буду, сосредоточусь на объяснении отмеченного мной @1. Этот цикл, собственно, и есть суть метода, он завершает операцию расширения старого элемента по битам.
Во-первых, ясно, что есть только два случая, в которых будет запущена операция обновления: один — новая вставка большого значения, а другой — новая вставка большого отрицательного значения. Оба этих случая приведут к недостаточно памяти типа и необходимо расширить биты данных.
_intsetGetEncoded Этот метод может вынуть соответствующий элемент в старом массиве по заданной длине, то есть индекс элемента в массиве Очевидно, что это с конца наперед.
Так как наш метод intsetResize завершил операцию расширения памяти, то есть память нового элемента была выделена, то метод _intsetSet переназначит элементы, извлеченные _intsetGetEncoded, в массив. В конце цикла, когда все элементы переставлены, новый элемент, наконец, присваивается последней позиции массива.
Но на самом деле, внимательные студенты обнаружат, что метод _intsetSet на самом деле передает length+prepend при передаче нижнего индекса, что на самом деле то, что мы говорим, если значение меньше нуля, length+prepend в конечном итоге приведет к тому, что все старые элементы будут удалены. Назад Переместите смещение, и тогда новому элементу будет присвоена позиция нулевого индекса. То есть, если вновь вставленное значение отрицательное, оно будет помещено в первую позицию массива.
Мы уже представили несколько основных API, для других API вы можете обратиться к исходному коду самостоятельно, я думаю, это не сложно для вас.
Подводя итог, целочисленный набор (intset) использует очень краткую структуру данных, которая может хранить некоторые целые числа в меньшем объеме памяти, но в конце концов он основан на массивах, поэтому он не может избежать недостатка, заключающегося в невозможности хранения большого объема. данных. В общем, при вставке элемента в лучшем случае O(logN), в худшем случае O(N), амортизированная временная сложность O(N), а при поиске элемента в соответствии с индексом временная сложность O( Н) (1). Когда intset содержит более 512 элементов или к нему добавляется строка, Redis преобразует intset в словарь.
Точно так же, если вы считаете, что то, что я написал, немного полезно для вас, нажмите и подпишитесь, и вы можете добавить WeChat автора для углубленного обсуждения.Мы сократим список в следующей лекции, поэтому, пожалуйста, будьте внимательны.
Обратите внимание на публику и не теряйтесь, программист, который любит делиться. Официальный аккаунт отвечает на "1024" и добавляет WeChat автора для совместного обсуждения и изучения! Все материалы кода кейса, использованные в каждой статье, будут загружены на мой личный github. GitHub.com/один батат/о… Добро пожаловать!